Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс...

Реферат - Компьютеры, программирование

Другие рефераты по предмету Компьютеры, программирование

 

Лабораторная работа № 2

Телешовой Елизаветы, гр. 726,

Цель работы: Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования.

 

1 вариант.

1. Четыре студента: Иванов, Петров, Сидоров и Васильев пошли на концерт группы Чайф, захватив пиво 2 сортов: Русич и Премьер. Определить план распития напитков для получения максимального суммарного опьянения (в ). Исходные данные даны в таблице:

 

СтудентНорма выпитогоЗапасы

(в литрах)РусичПремьерИванов221.5Петров3,511,5Сидоров1044,5Васильев10,7Крепость напитка16 %

2. Математическая модель.

2.1 Управляемые параметры

x1[л] количество выпитого пива Русич.

x2[л] количество выпитого пива Премьер.

решение.

2.2 Ограничения

количество пива Русич, выпитого Ивановым.

количество пива Премьер, выпитого Ивановым.

общее количество пива, выпитого Ивановым.

Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него запасов пива, поэтому:

(л).

Аналогично строим другие ограничения:

(л).

(л).

(л).

 

3. Постановка задачи.

Найти *, где достигается максимальное значение функции цели:

4. Решение.

при:

Приведем задачу к каноническому виду:

Определим начальный опорный план: .

Это решение является опорным, т.к. вектора условий при положительных компонентах решения линейно независимы, также , где , но не все оценки положительны (, где )

Опорный план является оптимальным, если для задачи максимизации все его оценки неотрицательны. не является оптимальным, значит критерий можно улучшить, если увеличить одну их отрицательных свободных переменных. Будем увеличивать , т.к. ее увеличение вызовет большее увеличение функции цели.

Предположим, что , тогда:

Запишем новый опорный план: . Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:

=>

При увеличении , первой перестает выполнять условие неотрицательности переменная , т.к. она первая обращается в ноль. Значит выведем из базиса . Теперь базисными переменными являются , а свободными . Для анализа этого плана выразим функцию цели через новые переменные.

Из ограничения (2) имеем: .

Подставляя в функцию цели: получаем:

Оформим данный этап задачи в виде симплекс-таблицы:

Начальная симплекс-таблица:

16100000СвБ.П.X1X2X3X4X5X6в0X32210001,50X43,5101001,50X510400104,50X60100010,7F-16-1000000;

Пересчитаем элементы исходной таблицы по правилу четырехугольника:

16100000СвБ.П.X1X2X3X4X5X6В0X301,4281-0,572000,64216X110,28600,286000,4280X501,140-2,86100,2140X60100010,7F0-5,42404,576006,857;

Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:

откуда получаем:

;

Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:

=>

Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:

, а из ограничений (2) и (3): . Тогда: ;

16100000СвБ.П.X1X2X3X4X5X6В0X30013-1,2500,37516X11001-0,2500,37510X2010-2,50,87500,18750X60002,5-0,87510,5125F000-94,7507,875

Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:

откуда получаем:

;

Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:

=>

Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:

, а из ограничений (1) и (2): . Тогда: ;

16100000СвБ.П.X1X2X3X4X5X6в0X4000,3331-0,41600,12516X110-0,33300,16600,2510X2011,8330-0,16600,50X600-0,83300,16610,2F0030109

Видим, что все оценки положительны, значит любое увеличение какой-либо свободной переменной уменьшит критерий. Данное решение является оптимальным. Изобразим это решение на графике:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Видим, что единственное и достигается в угловой точке области допустимых решений.

 

2 вариант.

Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в таких же пропорциях, за исключением того, что вместо пива Премьер было куплено пиво Окское, крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в ).

Функция цели: .

Приводим ограничения к каноническому виду:

=>

Решаем симплекс-методом:

166,40000СвБ.П.X1X2X3X4X5X6В0X32210001,50X43,5101001,50X510400104,50X60100010,7F-16-1000000,

166,40000СвБ.П.X1X2X3X4X5X6В0X301,4281-0,571000,64216X111,28600,286000,4280X501,1420-2,85100,2140X60100010,7F0-1,8204,571006,857;

166,40000СвБ.П.X1X2X3X4X5X6В0X30013-1,2500,37516X11001-0,2500,3756,4X2010-2,50,87500,18750X60002,5-0,87510,5125F00001,607,2;

Видим, что все оценки положительны, значит оптимальное решение достигнуто. Но одна из свободных переменных () обратилась в ноль, и если мы ее будем увеличивать, то функция цели не изменится, а решение будет другим, т.е. получим еще одно оптимальное решение, которое будет называться альтернативным.

 

16100000СвБ.П.X1X2X3X4X5X6в0X4000,3331-0,41600,12516X110-0,33300,16600,2510X2011,8330-0,16600,50X600-0,83300,16610,2F0000107,2

Если оптимальное решение достигнуто в 2-х точках, то оно достигается и на отрезке между ними. Можно составить уравнение данного отрезка по формуле:

;

;

 

 

 

 

 

 

 

 

 

 <