|
Студент
|
Норма
выпитого
|
Запасы
(в
литрах)
|
|
«Русич»
|
«Премьер»
|
|
Иванов
|
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
|
|
|
Св
|
Б.П.
|
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
|
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
|
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
|
-1,42
|
0,357
|
|
|
F
|
0
|
0
|
0
|
-4,576
|
0
|
-5,424
|
3,648
|
Критерий
можно улучшить, т.к. ,
, но нельзя
найти такое , при
котором базисные переменные обращаются в 0. Значит задача неразрешима из-за
неограниченности критерия.
5 вариант.
После отмеченного таким образом
праздника обязательно наступает похмелье. Решим задачу из предыдущего варианта,
минимизируя этот неприятный фактор, т.е. функция цели: .
Приводим ограничения к каноническому
виду:
=>
Эта задача решается методом
искусственного базиса, т.к. в ней нет единичной подматрицы. Вспомогательная
задача получается точно такой же, как и в предыдущем варианте, поэтому просто
возьмем опорный план из предыдущей задачи.
;
|
|
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
|
Видим, что оценки свободных
переменных меньше нуля, значит решение оптимальное.
; F = 3,648.
Делаем
вывод: оптимальное решение может существовать и при
неограниченности области.
Область не ограничена, но существует
оптимальное решение ,
причем единственное, которое достигается в угловой точке.