Лабораторные работы по Основам теории систем



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

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

|Студент |Норма выпитого                  |Запасы  |
|        |                                |(в      |
|        |                                |литрах) |
|        |«Русич»        |«Премьер»      |        |
|Иванов  |2              |2              |1.5     |
|Петров  |3,5            |1              |1,5     |
|Сидоров |10             |4              |4,5     |
|Васильев|–              |1              |0,7     |
|Крепость|16 %           |10 %           |        |
|напитка |               |               |        |

2. Математическая модель.
2.1 Управляемые параметры
x1[л] – количество выпитого пива «Русич».
x2[л] – количество выпитого пива «Премьер».
[pic] – решение.
2.2 Ограничения
[pic] – количество пива «Русич», выпитого Ивановым.
[pic] – количество пива «Премьер», выпитого Ивановым.
[pic]– общее количество пива, выпитого Ивановым.
Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него
запасов пива, поэтому:
[pic](л).
Аналогично строим другие ограничения:
[pic](л).
[pic](л).
[pic](л).

3. Постановка задачи.
Найти [pic]*, где достигается максимальное значение функции цели:
[pic]
4. Решение.
[pic]   при:
[pic]  [pic]
Приведем задачу к каноническому виду:
[pic]  [pic]
Определим начальный опорный план:   [pic].
Это решение является опорным, т.к. вектора условий при положительных
компонентах решения линейно независимы, также [pic], где [pic], но не все
оценки положительны ([pic], где [pic] [pic])
Опорный план является оптимальным, если для задачи максимизации все его
оценки неотрицательны. [pic] не является оптимальным, значит критерий можно
улучшить, если увеличить одну их отрицательных свободных переменных. Будем
увеличивать [pic], т.к. ее увеличение вызовет большее увеличение функции
цели.
Предположим, что [pic], тогда:
[pic]
Запишем новый опорный план: [pic]. Все оценки опорного плана должны быть
неотрицательны, а значит должны выполняться условия:
[pic]=> [pic]
При увеличении [pic], первой перестает выполнять условие неотрицательности
переменная [pic], т.к. она первая обращается в ноль. Значит выведем из
базиса [pic]. Теперь базисными переменными являются [pic], а свободными
[pic]. Для анализа этого плана выразим функцию цели через новые переменные.
Из ограничения (2) имеем: [pic].
Подставляя в функцию цели: [pic] получаем:
[pic]
Оформим данный этап задачи в виде симплекс-таблицы:
Начальная симплекс-таблица:
|            |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     |


[pic];
Пересчитаем элементы исходной таблицы по правилу четырехугольника:
|            |16   |10   |0    |0    |0    |0    |      |
|Св   |Б.П. |X1   |X2   |X3   |X4   |X5   |X6   |В     |
|0    |X3   |0    |1,428|1    |-0,57|0    |0    |0,642 |
|     |     |     |     |     |2    |     |     |      |
|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,42|0    |4,576|0    |0    |6,857 |
|     |     |     |4    |     |     |     |     |      |


[pic];
Пересчитав все оценки, видим, что [pic], значит критерий можно улучшить.
Будем увеличивать [pic]. Пусть [pic], тогда:
[pic]
откуда получаем:
[pic];
Все оценки опорного плана должны быть неотрицательны, а значит должны
выполняться условия:
[pic]  =>  [pic]
Выведем из базиса [pic]. Теперь базисными переменными являются [pic], а
свободными [pic]. Выразим функцию цели через новые переменные:
[pic], а из ограничений (2) и (3): [pic]. Тогда: [pic];
|            |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,87|1    |0,5125|
|     |     |     |     |     |     |5    |     |      |
|     |F    |0    |0    |0    |-9   |4,75 |0    |7,875 |


[pic]
Пересчитав все оценки, видим, что [pic], значит критерий можно улучшить.
Будем увеличивать [pic]. Пусть [pic], тогда:
[pic]
откуда получаем:
[pic];
Все оценки опорного плана должны быть неотрицательны, а значит должны
выполняться условия:
[pic]  =>  [pic]
Выведем из базиса [pic]. Теперь базисными переменными являются [pic], а
свободными [pic]. Выразим функцию цели через новые переменные:
[pic], а из ограничений (1) и (2): [pic]. Тогда: [pic];
|            |16   |10   |0    |0    |0    |0    |      |
|Св   |Б.П. |X1   |X2   |X3   |X4   |X5   |X6   |в     |
|0    |X4   |0    |0    |0,333|1    |-0,41|0    |0,125 |
|     |     |     |     |     |     |6    |     |      |
|16   |X1   |1    |0    |-0,33|0    |0,166|0    |0,25  |
|     |     |     |     |3    |     |     |     |      |
|10   |X2   |0    |1    |1,833|0    |-0,16|0    |0,5   |
|     |     |     |     |     |     |6    |     |      |
|0    |X6   |0    |0    |-0,83|0    |0,166|1    |0,2   |
|     |     |     |     |3    |     |     |     |      |
|     |F    |0    |0    |3    |0    |1    |0    |9     |


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



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

2 вариант.
Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же
пива и в таких же пропорциях, за исключением того, что вместо пива
«Премьер» было куплено пиво «Окское», крепость которого 6,4 % (дешевое и
разбавленное). Определить план распития напитков для получения
максимального суммарного опьянения (в [pic]).
Функция цели: [pic].
Приводим ограничения к каноническому виду:
[pic]  [pic] =>  [pic]  [pic]
Решаем симплекс-методом:
|            |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     |


[pic], [pic]
|            |16   |6,4  |0    |0    |0    |0    |      |
|Св   |Б.П. |X1   |X2   |X3   |X4   |X5   |X6   |В     |
|0    |X3   |0    |1,428|1    |-0,57|0    |0    |0,642 |
|     |     |     |     |     |1    |     |     |      |
|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 |


[pic]; [pic]
|            |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,87|1    |0,5125|
|     |     |     |     |     |     |5    |     |      |
|     |F    |0    |0    |0    |0    |1,6  |0    |7,2   |


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

|            |16   |10   |0    |0    |0    |0    |      |
|Св   |Б.П. |X1   |X2   |X3   |X4   |X5   |X6   |в     |
|0    |X4   |0    |0    |0,333|1    |-0,41|0    |0,125 |
|     |     |     |     |     |     |6    |     |      |
|16   |X1   |1    |0    |-0,33|0    |0,166|0    |0,25  |
|     |     |     |     |3    |     |     |     |      |
|10   |X2   |0    |1    |1,833|0    |-0,16|0    |0,5   |
|     |     |     |     |     |     |6    |     |      |
|0    |X6   |0    |0    |-0,83|0    |0,166|1    |0,2   |
|     |     |     |     |3    |     |     |     |      |
|     |F    |0    |0    |0    |0    |1    |0    |7,2   |


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



На графике видно, что оптимальное решение достигается на отрезке, значит
является альтернативным. Вектор градиента целевой функции (F) параллелен
радиус-вектору ограничения (3). Это ограничение образует все множество
оптимальных решений.
Можно сделать вывод, что альтернативные решения имеются, когда все оценки
свободных переменных больше 0, а среди коэффициентов целевой функции оценка
одной из свободных переменных равна 0.

3 вариант.
Студент Петров, решив догнать по количеству выпитого студента Сидорова,
выпил 4 доли пива «Русич» вместо запланированных 3,5. Решим задачу с учетом
изменившихся данных.
Функция цели:[pic].
Приводим ограничения к каноническому виду:
[pic]  [pic]  => [pic]  [pic]
Решим задачу симплекс-методом.
|            |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     |


[pic], [pic].
|            |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     |


[pic], [pic].
|            |16   |10   |0    |0    |0    |0    |      |
|Св   |Б.П. |X1   |X2   |X3   |X4   |X5   |X6   |в     |
|10   |X2   |0    |1    |1,666|-0,33|0    |0    |0,5   |
|     |     |     |     |     |3    |     |     |      |
|16   |X1   |1    |0    |-0,16|0,333|0    |0    |0,25  |
|     |     |     |     |6    |     |     |     |      |
|0    |X5   |0    |0    |-1   |-2   |1    |0    |0     |
|0    |X6   |0    |0    |-0,66|0,333|0    |1    |0,2   |
|     |     |     |     |6    |     |     |     |      |
|     |F    |0    |0    |4    |2    |0    |0    |9     |


[pic], [pic]
Данное оптимальное решение является вырожденным, т.к. положительных
компонентов меньше числа ограничений. На существование вырожденного
оптимального решения указывает наличие в симплекс-таблице нулевого
свободного члена при найденном оптимальном решении.
В случае вырожденного решения симплекс-таблица может зацикливаться.
Существует 2 способа предупреждения зацикливания:
а) [pic] – изменение хода ограничения на некоторые величины [pic]. Они
должны быть малы, чтобы изменения были несущественны.
б) Если минимальное отношение свободных коэффициентов к положительным
членам разрешающего столбца определяется неоднозначно, то выбирается
отношение любого другого столбца к положительным коэффициентам данного
столбца, пока строка не определится однозначно.



4 вариант.
В связи с неожиданно полученной стипендией, запасы пива резко увеличились.
Функция цели: [pic].
Приводим ограничения к каноническому виду:
[pic]  [pic] =>  [pic]  [pic]
В матрице условий нет единичной подматрицы, поэтому используем метод
искусственного базиса. Построим вспомогательную задачу.
[pic]
[pic], при этом [pic].
Решаем вспомогательную задачу симплекс-методом:

|        |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,57|0    |0    |0,642|
|   |    |     |     |     |     |     |     |     |1    |     |     |     |
|0  |X1  |1    |0,285|0    |-0,28|0    |0    |0    |0,285|0    |0    |0,428|
|   |    |     |     |     |5    |     |     |     |     |     |     |     |
|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,87|0    |0    |-2,5 |0,875|0    |0,187|
|   |    |     |     |     |     |5    |     |     |     |     |     |     |
|1  |X10 |0    |0    |0    |-2,5 |0,875|-1   |0    |2,5  |-0,87|1    |0,512|
|   |    |     |     |     |     |     |     |     |     |5    |     |     |
|   |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,33|-1   |0,416|0    |0,333|1    |-0,41|0    |0,125|
|   |    |     |     |3    |     |     |     |     |     |6    |     |     |
|0  |X1  |1    |0    |0,333|0    |-0,16|0    |-,333|0    |0,166|0    |0,25 |
|   |    |     |     |     |     |6    |     |     |     |     |     |     |
|0  |X2  |0    |1    |-0,83|0    |0,166|0    |0,833|0    |-0,16|0    |0,5  |
|   |    |     |     |3    |     |     |     |     |     |6    |     |     |
|1  |X10 |0    |0    |0,833|0    |-0,16|-1   |-0,83|0    |0,166|1    |0,2  |
|   |    |     |     |     |     |6    |     |3    |     |     |     |     |
|   |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,14|0,585|
|   |    |     |     |     |     |     |     |     |     |     |2    |     |
|0  |X1  |1    |0    |0    |-0,28|0    |0,285|0    |0,285|0    |-0,28|0,228|
|   |    |     |     |     |5    |     |     |     |     |     |5    |     |
|0  |X2  |0    |1    |0    |0    |0    |-1   |0    |0    |0    |1    |0,7  |
|0  |X3  |0    |0    |1    |-0,57|0    |-1,42|-1   |-1,57|0    |1,428|0,357|
|   |    |     |     |     |1    |     |     |     |1    |     |     |     |
|   |F   |0    |0    |0    |0    |0    |0    |-1   |-1   |-1   |-1   |0    |


[pic]– оптимальное решение вспомогательной задачи. Искусственные переменные
являются свободными и равны нулю. Т.о. это решение является опорным планом
исходной задачи.
Решим исходную задачу:
|        |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,28|0    |0,285|0,228|
|   |    |     |     |     |5    |     |     |     |
|10 |X2  |0    |1    |0    |0    |0    |-1   |0,7  |
|0  |X3  |0    |0    |1    |-0,57|0    |-1,42|0,357|
|   |    |     |     |     |1    |     |     |     |
|   |F   |0    |0    |0    |-4,57|0    |-5,42|3,648|
|   |    |     |     |     |6    |     |4    |     |


Критерий можно улучшить, т.к. [pic], [pic], но нельзя найти такое [pic],
при котором базисные переменные обращаются в 0. Значит задача неразрешима
из-за неограниченности критерия.



5 вариант.
После отмеченного таким образом праздника обязательно наступает похмелье.
Решим задачу из предыдущего варианта, минимизируя этот неприятный фактор,
т.е. функция цели: [pic].
Приводим ограничения к каноническому виду:
[pic]  [pic] =>  [pic]  [pic]
Эта задача решается методом искусственного базиса, т.к. в ней нет единичной
подматрицы. Вспомогательная задача получается точно такой же, как и в
предыдущем варианте, поэтому просто возьмем опорный план из предыдущей
задачи.
[pic];
|        |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,28|0    |0,285|0,228|
|   |    |     |     |     |5    |     |     |     |
|10 |X2  |0    |1    |0    |0    |0    |-1   |0,7  |
|0  |X3  |0    |0    |1    |-0,57|0    |-1,42|0,357|
|   |    |     |     |     |1    |     |     |     |
|   |F   |0    |0    |0    |-4,57|0    |-5,42|3,648|
|   |    |     |     |     |6    |     |4    |     |


Видим, что оценки свободных переменных меньше нуля, значит решение
оптимальное.
[pic]; F = 3,648.
Делаем вывод: оптимальное решение может существовать и при неограниченности
области.



Область не ограничена, но существует оптимальное решение [pic], причем
единственное, которое достигается в угловой точке.
-----------------------
X(3)

X(2)

X(оп)

X(3)

(3)

(1)

(4)

(2)

[pic]

X(2)

X(4)

F

X(оп)

[pic]

(1)

(4)

F,(3)

[pic]

X(4)

(2)

(1)

X(1)

F

X(оп)

F

(3)

(2)

(4)

(1)

[pic]

(4)

(2)

(3)

F

X(оп)

X(1)

X(2)

(3)

(2)

(4)

(1)

[pic]