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

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

Лабораторная работа № 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]