←предыдущая следующая→
1 2
Лабораторная работа № 2
Телешовой Елизаветы, гр. 726,
Цель работы: Решение задач линейного программирования симплекс-методом. Варианты разре-шимости задач линейного программирования.
1 вариант.
1. Четыре студента: Иванов, Петров, Сидоров и Васильев пошли на концерт группы «Чайф», за-хватив пиво 2 сортов: «Русич» и «Премьер». Определить план распития напитков для получе-ния максимального суммарного опьянения (в ). Исходные данные даны в таблице:
Студент Норма выпитого Запасы
(в литрах)
«Русич» «Премьер»
Иванов 2 2 1.5
Петров 3,5 1 1,5
Сидоров 10 4 4,5
Васильев – 1 0,7
Крепость напитка 16 % 10 %
2. Математическая модель.
2.1 Управляемые параметры
x1[л] – количество выпитого пива «Русич».
x2[л] – количество выпитого пива «Премьер».
– решение.
2.2 Ограничения
– количество пива «Русич», выпитого Ивановым.
– количество пива «Премьер», выпитого Ивановым.
– общее количество пива, выпитого Ивановым.
Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него запасов пива, поэтому:
(л).
Аналогично строим другие ограничения:
(л).
(л).
(л).
3. Постановка задачи.
Найти *, где достигается максимальное значение функции цели:
4. Решение.
при:
Приведем задачу к каноническому виду:
Определим начальный опорный план: .
Это решение является опорным, т.к. вектора условий при положительных компонентах ре-шения линейно независимы, также , где , но не все оценки положительны ( , где )
Опорный план является оптимальным, если для задачи максимизации все его оценки неот-рицательны. не является оптимальным, значит критерий можно улучшить, если увеличить одну их отрицательных свободных переменных. Будем увеличивать , т.к. ее увеличение вы-зовет большее увеличение функции цели.
Предположим, что , тогда:
Запишем новый опорный план: . Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:
=>
При увеличении , первой перестает выполнять условие неотрицательности переменная , т.к. она первая обращается в ноль. Значит выведем из базиса . Теперь базисными перемен-ными являются , а свободными . Для анализа этого плана выразим функцию цели через новые переменные.
Из ограничения (2) имеем: .
Подставляя в функцию цели: получаем:
Оформим данный этап задачи в виде симплекс-таблицы:
Начальная симплекс-таблица:
16 10 0 0 0 0
Св
Б.П. X1 X2 X3 X4 X5 X6 в
0 X3 2 2 1 0 0 0 1,5
0 X4 3,5 1 0 1 0 0 1,5
0 X5 10 4 0 0 1 0 4,5
0 X6 0 1 0 0 0 1 0,7
F -16 -10 0 0 0 0 0
;
Пересчитаем элементы исходной таблицы по правилу четырехугольника:
16 10 0 0 0 0
Св
Б.П. X1 X2 X3 X4 X5 X6 В
0 X3 0 1,428 1 -0,572 0 0 0,642
16 X1 1 0,286 0 0,286 0 0 0,428
0 X5 0 1,14 0 -2,86 1 0 0,214
0 X6 0 1 0 0 0 1 0,7
F 0 -5,424 0 4,576 0 0 6,857
;
Пересчитав все оценки, видим, что , значит критерий можно улучшить. Бу-дем увеличивать . Пусть , тогда:
откуда получаем:
;
Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться ус-ловия:
=>
Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:
, а из ограничений (2) и (3): . То-гда: ;
16 10 0 0 0 0
Св
Б.П. X1 X2 X3 X4 X5 X6 В
0
X3 0 0 1 3 -1,25 0 0,375
16 X1 1 0 0 1 -0,25 0 0,375
10 X2 0 1 0 -2,5 0,875 0 0,1875
0 X6 0 0 0 2,5 -0,875 1 0,5125
F 0 0 0 -9 4,75 0 7,875
Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:
откуда получаем:
;
Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться ус-ловия:
=>
Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:
, а из ограничений (1) и (2): . Тогда: ;
16 10 0 0 0 0
Св Б.П. X1 X2 X3 X4 X5 X6 в
0 X4 0 0 0,333 1 -0,416 0 0,125
16 X1 1 0 -0,333 0 0,166 0 0,25
10 X2 0 1 1,833 0 -0,166 0 0,5
0 X6 0 0 -0,833 0 0,166 1 0,2
F 0 0 3 0 1 0 9
Видим, что все оценки положительны, значит любое увеличение какой-либо свободной пе-ременной уменьшит критерий. Данное решение является оптимальным. Изобразим это решение на графике:
Видим, что единственное и достигается в угловой точке области допустимых решений.
2 вариант.
Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в та-ких же пропорциях, за исключением того, что вместо пива «Премьер» было куплено пиво «Ок-ское», крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в ).
Функция цели: .
Приводим ограничения к каноническому виду:
=>
Решаем симплекс-методом:
16 6,4 0 0 0 0
Св
Б.П. X1 X2 X3 X4 X5 X6 В
0 X3 2 2 1 0 0 0 1,5
0 X4 3,5 1 0 1 0 0 1,5
0 X5 10 4 0 0 1 0 4,5
0 X6 0 1 0 0 0 1 0,7
F -16 -10 0 0 0 0 0
,
16 6,4 0 0 0 0
Св
Б.П. X1 X2 X3 X4 X5 X6 В
0 X3 0 1,428 1 -0,571 0 0 0,642
16 X1 1 1,286 0 0,286 0 0 0,428
0 X5 0 1,142 0 -2,85 1 0 0,214
0 X6 0 1 0 0 0 1 0,7
F 0 -1,82 0 4,571 0 0 6,857
;
16 6,4 0 0 0 0
Св Б.П. X1 X2 X3 X4 X5 X6 В
0 X3 0 0 1 3 -1,25 0 0,375
16 X1 1 0 0 1 -0,25 0 0,375
6,4 X2 0 1 0 -2,5 0,875 0 0,1875
0 X6 0 0 0 2,5 -0,875 1 0,5125
F 0 0 0 0 1,6 0 7,2
;
Видим, что все оценки положительны, значит оптимальное решение достигнуто. Но одна из свободных переменных ( ) обратилась в ноль, и если мы ее будем увеличивать, то функция цели не изменится, а решение будет другим, т.е. получим еще одно оптимальное решение, которое бу-дет называться альтернативным.
16 10 0 0 0 0
Св Б.П. X1 X2 X3 X4 X5 X6 в
0 X4 0 0 0,333 1 -0,416 0 0,125
16 X1 1 0 -0,333 0 0,166 0 0,25
10 X2 0 1 1,833 0 -0,166 0 0,5
0 X6 0 0 -0,833 0 0,166 1 0,2
F 0 0 0 0 1 0 7,2
Если оптимальное решение достигнуто в 2-х точках, то оно достигается и на отрезке между ними. Можно составить уравнение данного отрезка по формуле:
;
;
На графике видно, что оптимальное решение достигается на отрезке, значит является альтер-нативным. Вектор градиента целевой функции (F) параллелен радиус-вектору ограничения (3). Это ограничение образует все множество оптимальных решений.
Можно сделать вывод, что альтернативные решения имеются, когда все оценки свободных переменных больше 0, а среди коэффициентов целевой функции оценка одной из свободных пе-ременных равна 0.
3 вариант.
Студент Петров, решив догнать по количеству выпитого студента Сидорова, выпил 4 доли пива «Русич» вместо запланированных 3,5. Решим задачу с учетом изменившихся данных.
Функция цели: .
Приводим ограничения к каноническому виду:
=>
Решим задачу симплекс-методом.
16 10 0 0 0 0
Св
Б.П. X1 X2 X3 X4 X5 X6 в
0 X3 2 2 1 0 0 0 1,5
0 X4 4 1 0 1 0 0 1,5
0 X5 10 4 0 0 1 0 4,5
0 X6 0 1 0 0 0 1 0,7
F -16 -10 0 0 0 0 0
, .
16 10 0 0 0 0
Св
Б.П. X1 X2 X3 X4 X5 X6 В
0 X3 0 1,5 1 -0,5 0 0 0,75
16 X1 1 0,25 0 0,25 0 0 0,375
0 X5 0 1,5 0 -2,5 1 0 0,75
0 X6 0 1 0 0 0 1 0,7
F 0 -6 0 4 0 0 6
, .
16 10 0 0 0 0
Св Б.П. X1 X2 X3 X4 X5 X6 в
10 X2 0 1 1,666 -0,333 0 0 0,5
16 X1 1 0 -0,166 0,333 0 0 0,25
0 X5 0 0 -1 -2 1 0 0
0 X6 0 0 -0,666 0,333 0 1 0,2
F 0 0 4 2 0 0 9
←предыдущая следующая→
1 2