Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

Лабораторная работа 2Телешовой Елизаветы, гр. 726,Цель работы Решение задач линейного программированиясимплекс-методом. Варианты разрешимости задач линейного программирования. 1 вариант.1. Четыре студента Иванов, Петров,Сидоров и Васильев пошли на концерт группы Чайф , захватив пиво 2 сортов

Русич и Премьер . Определить план распития напитков для получениямаксимального суммарного опьянения в . Исходные данные даны в таблице Студент Норма выпитого Запасы в литрах Русич Премьер Иванов 1.5 Петров 3,5 1 1,5 Сидоров 10 4 4,5 Васильев 1 0,7 Крепость напитка 2. Математическая модель.2.1Управляемые параметрыx1 л количество выпитого пива

Русич . x2 л количество выпитого пива Премьер . решение.2.2Ограничения количество пива Русич , выпитого Ивановым. количество пива Премьер , выпитого Ивановым. общее количество пива, выпитого Ивановым.Общее количество пива, выпитого Ивановым, не превосходитимеющихся у него запасов пива, поэтому л .Аналогично строим другие ограничения л . л . л .3.Постановка задачи.

Найти , где достигается максимальное значение функциицели 4. Решение. при Приведем задачу к каноническому виду Определим начальный опорный план .Это решение является опорным, т.к.вектора условий при положительных компонентах решения линейно независимы, также, где , но не все оценки положительны , где Опорный план является оптимальным, еслидля задачи максимизации все его оценки неотрицательны. не являетсяоптимальным, значит критерий можно улучшить,

если увеличить одну их отрицательныхсвободных переменных. Будем увеличивать , т.к. ее увеличение вызовет большее увеличение функции цели.Предположим, что , тогда Запишем новый опорный план . Все оценки опорного плана должны быть неотрицательны, азначит должны выполняться условия gt При увеличении , первой перестает выполнять условие неотрицательностипеременная , т.к. она первая обращается

в ноль. Значит выведем из базиса. Теперь базисными переменными являются , а свободными . Для анализа этого плана выразим функцию цели через новыепеременные.Из ограничения 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 -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 Пересчитав все оценки, видим, что , значит критерий

можно улучшить. Будем увеличивать . Пусть , тогда откуда получаем Все оценки опорного плана должны бытьнеотрицательны, а значит должны выполняться условия gt Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные , а из ограничений 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 Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда откуда получаем Все оценки опорного плана должны бытьнеотрицательны, а значит должны выполняться условия gt

Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные , а из ограничений 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 9 Видим, что все оценки положительны, значит любоеувеличение какой-либо свободной переменной уменьшит критерий. Данное решениеявляется оптимальным. Изобразим это решение на графике Видим, что единственное идостигается в угловой точке области допустимых решений.2 вариант.Отмечая успешно сданную сессию, вышеупомянутыестуденты взяли столько же пива и в таких же пропорциях, за исключением того,что вместо пива

Премьер было куплено пиво Окское , крепость которого 6,4 дешевое и разбавленное . Определить план распития напитков для получениямаксимального суммарного опьянения в .Функция цели .Приводим ограничения к каноническому виду gt Решаем симплекс-методом 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. Решим задачу с учетом изменившихся данных.Функция цели .Приводим ограничения к каноническому виду gt Решим задачу симплекс-методом. 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 вариант.В связи с неожиданно полученной стипендией, запасыпива резко увеличились.Функция цели .Приводим ограничения к каноническому виду gt

В матрице условий нет единичной подматрицы, поэтомуиспользуем метод искусственного базиса. Построим вспомогательную задачу. , при этом .Решаем вспомогательную задачу симплекс-методом 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 Критерийможно улучшить, т.к но нельзя найти такое , при котором базисные переменные обращаются в 0. Значитзадача неразрешима из-за неограниченности критерия.5 вариант.После отмеченного таким образом праздникаобязательно наступает похмелье. Решим задачу из предыдущего варианта,минимизируя этот неприятный фактор, т.е. функция цели .Приводим ограничения к каноническому виду gt Эта задача решается методом искусственного базиса,т.к.

в ней нет единичной подматрицы. Вспомогательная задача получается точнотакой же, как и в предыдущем варианте, поэтому просто возьмем опорный план изпредыдущей задачи. 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.Делаемвывод оптимальноерешение может существовать и при неограниченности области.Область не ограничена, но существует оптимальноерешение , причем единственное, которое достигается в угловой точке.