Лабораторная
работа № 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 |
,
Данное оптимальное
решение является
вырожденным,
т.к. положительных
компонентов
меньше числа
ограничений.
На существование
вырожденного
оптимального
решения указывает
наличие в
симплекс-таблице
нулевого свободного
члена при найденном
оптимальном
решении.
В случае
вырожденного
решения симплекс-таблица
может зацикливаться.
Существует
2 способа предупреждения
зацикливания:
а)
– изменение
хода ограничения
на некоторые
величины
.
Они должны быть
малы, чтобы
изменения были
несущественны.
б) Если минимальное
отношение
свободных
коэффициентов
к положительным
членам разрешающего
столбца определяется
неоднозначно,
то выбирается
отношение
любого другого
столбца к
положительным
коэффициентам
данного столбца,
пока строка
не определится
однозначно.
4
вариант.
В связи с
неожиданно
полученной
стипендией,
запасы пива
резко увеличились.
Функция цели:
.
Приводим
ограничения
к каноническому
виду:
=>
В матрице
условий нет
единичной
подматрицы,
поэтому используем
метод искусственного
базиса. Построим
вспомогательную
задачу.
,
при этом
.
Решаем
вспомогательную
задачу симплекс-методом:
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Св
|
Б.П. |
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
X8
|
X9
|
X10
|
в |
1 |
X7
|
2 |
2 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1,5 |
1 |
X8
|
3.5 |
1 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
1,5 |
1 |
X9
|
10 |
4 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
4,5 |
1 |
X10
|
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0,7 |
|
F |
15,5 |
8 |
-1 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Св
|
Б.П. |
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
X8
|
X9
|
X10
|
в |
1 |
X7
|
0 |
1,428 |
-1 |
0,571 |
0 |
0 |
1 |
-0,571 |
0 |
0 |
0,642 |
0 |
X1
|
1 |
0,285 |
0 |
-0,285 |
0 |
0 |
0 |
0,285 |
0 |
0 |
0,428 |
1 |
X9
|
0 |
1,142 |
0 |
2,857 |
-1 |
0 |
0 |
-2,85 |
1 |
0 |
0,214 |
1 |
X10
|
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0,7 |
|
F |
0 |
3.571 |
-1 |
3,428 |
-1 |
-1 |
0 |
-4,42 |
0 |
0 |
1,557 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Св
|
Б.П. |
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
X8
|
X9
|
X10
|
в |
1 |
X7
|
0 |
0 |
-1 |
-3 |
1,25 |
0 |
1 |
3 |
-1,25 |
0 |
0,375 |
0 |
X1
|
1 |
0 |
0 |
-1 |
0,25 |
0 |
0 |
1 |
-0,25 |
0 |
0,375 |
0 |
X2
|
0 |
1 |
0 |
2,5 |
-0,875 |
0 |
0 |
-2,5 |
0,875 |
0 |
0,187 |
1 |
X10
|
0 |
0 |
0 |
-2,5 |
0,875 |
-1 |
0 |
2,5 |
-0,875 |
1 |
0,512 |
|
F |
0 |
0 |
-1 |
-5,5 |
2,125 |
-1 |
0 |
4,5 |
-3,12 |
0 |
0,887 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Св
|
Б.П. |
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
X8
|
X9
|
X10
|
в |
1 |
X8
|
0 |
0 |
-0,333 |
-1 |
0,416 |
0 |
0,333 |
1 |
-0,416 |
0 |
0,125 |
0 |
X1
|
1 |
0 |
0,333 |
0 |
-0,166 |
0 |
-,333 |
0 |
0,166 |
0 |
0,25 |
0 |
X2
|
0 |
1 |
-0,833 |
0 |
0,166 |
0 |
0,833 |
0 |
-0,166 |
0 |
0,5 |
1 |
X10
|
0 |
0 |
0,833 |
0 |
-0,166 |
-1 |
-0,833 |
0 |
0,166 |
1 |
0,2 |
|
F |
0 |
0 |
0,5 |
-1 |
0,25 |
-1 |
-1,5 |
0 |
-1,25 |
0 |
0,325 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Св
|
Б.П. |
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
X8
|
X9
|
X10
|
в |
1 |
X8
|
0 |
0 |
0 |
-1 |
0,35 |
-0,4 |
0 |
1 |
-0,35 |
0,4 |
0,205 |
0 |
X1
|
1 |
0 |
0 |
0 |
-0,1 |
0,4 |
0 |
0 |
0,1 |
-0,4 |
0,17 |
0 |
X2
|
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0,7 |
0 |
X3
|
0 |
0 |
1 |
0 |
-0,2 |
-1,2 |
-1 |
0 |
0,2 |
1,2 |
0,24 |
|
F |
0 |
0 |
0 |
-1 |
0,35 |
-0,4 |
-1 |
0 |
-1,35 |
-0,6 |
0,205 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Св
|
Б.П. |
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
X7
|
X8
|
X9
|
X10
|
в |
0 |
X5
|
0 |
0 |
0 |
-2,85 |
1 |
-1,14 |
0 |
2,857 |
-1 |
-1,142 |
0,585 |
0 |
X1
|
1 |
0 |
0 |
-0,285 |
0 |
0,285 |
0 |
0,285 |
0 |
-0,285 |
0,228 |
0 |
X2
|
0 |
1 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0,7 |
0 |
X3
|
0 |
0 |
1 |
-0,571 |
0 |
-1,42 |
-1 |
-1,571 |
0 |
1,428 |
0,357 |
|
F |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
-1 |
0 |
–
оптимальное
решение вспомогательной
задачи. Искусственные
переменные
являются свободными
и равны нулю.
Т.о. это решение
является опорным
планом исходной
задачи.
Решим исходную
задачу:
-
|
16 |
10 |
0 |
0 |
0 |
0 |
|
Св
|
Б.П. |
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
в |
0 |
X5
|
0 |
0 |
0 |
-2,85 |
1 |
-1,14 |
0,585 |
16 |
X1
|
1 |
0 |
0 |
-0,285 |
0 |
0,285 |
0,228 |
10 |
X2
|
0 |
1 |
0 |
0 |
0 |
-1 |
0,7 |
0 |
X3
|
0 |
0 |
1 |
-0,571 |
0 |
-1,42 |
0,357 |
|
F |
0 |
0 |
0 |
-4,576 |
0 |
-5,424 |
3,648 |
К
ритерий
можно улучшить,
т.к.
,
,
|