|
|
|
|
Учебный материал
РОССИЙСКОЙ КОЛЛЕКЦИИ РЕФЕРАТОВ (с) 1996
http://referat.students.ru; http://www.referats.net; http://www.referats.com
Лабораторная работа ? 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. Решим задачу с учетом изменившихся данных.
Функция цели:.
Приводим ограничения к каноническому