Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс...
Реферат - Компьютеры, программирование
Другие рефераты по предмету Компьютеры, программирование
/p>
На графике видно, что оптимальное решение достигается на отрезке, значит является альтернативным. Вектор градиента целевой функции (F) параллелен радиус-вектору ограничения (3). Это ограничение образует все множество оптимальных решений.
Можно сделать вывод, что альтернативные решения имеются, когда все оценки свободных переменных больше 0, а среди коэффициентов целевой функции оценка одной из свободных переменных равна 0.
3 вариант.
Студент Петров, решив догнать по количеству выпитого студента Сидорова, выпил 4 доли пива Русич вместо запланированных 3,5. Решим задачу с учетом изменившихся данных.
Функция цели:.
Приводим ограничения к каноническому виду:
=>
Решим задачу симплекс-методом.
16100000СвБ.П.X1X2X3X4X5X6в0X32210001,50X44101001,50X510400104,50X60100010,7F-16-1000000, .
16100000СвБ.П.X1X2X3X4X5X6В0X301,51-0,5000,7516X110,2500,25000,3750X501,50-2,5100,750X60100010,7F0-604006, .
16100000СвБ.П.X1X2X3X4X5X6в10X2011,666-0,333000,516X110-0,1660,333000,250X500-1-21000X600-0,6660,333010,2F0042009,
Данное оптимальное решение является вырожденным, т.к. положительных компонентов меньше числа ограничений. На существование вырожденного оптимального решения указывает наличие в симплекс-таблице нулевого свободного члена при найденном оптимальном решении.
В случае вырожденного решения симплекс-таблица может зацикливаться. Существует 2 способа предупреждения зацикливания:
а) изменение хода ограничения на некоторые величины . Они должны быть малы, чтобы изменения были несущественны.
б) Если минимальное отношение свободных коэффициентов к положительным членам разрешающего столбца определяется неоднозначно, то выбирается отношение любого другого столбца к положительным коэффициентам данного столбца, пока строка не определится однозначно.
4 вариант.
В связи с неожиданно полученной стипендией, запасы пива резко увеличились.
Функция цели: .
Приводим ограничения к каноническому виду:
=>
В матрице условий нет единичной подматрицы, поэтому используем метод искусственного базиса. Построим вспомогательную задачу.
, при этом .
Решаем вспомогательную задачу симплекс-методом:
0000001111СвБ.П.X1X2X3X4X5X6X7X8X9X10в1X722-100010001,51X83.510-10001001,51X910400-1000104,51X1001000-100010,7F15,58-1-1-1-100000
0000001111СвБ.П.X1X2X3X4X5X6X7X8X9X10в1X701,428-10,571001-0,571000,6420X110,2850-0,2850000,285000,4281X901,14202,857-100-2,85100,2141X1001000-100010,7F03.571-13,428-1-10-4,42001,557
0000001111СвБ.П.X1X2X3X4X5X6X7X8X9X10в1X700-1-31,25013-1,2500,3750X1100-10,25001-0,2500,3750X20102,5-0,87500-2,50,87500,1871X10000-2,50,875-102,5-0,87510,512F00-1-5,52,125-104,5-3,1200,887
0000001111СвБ.П.X1X2X3X4X5X6X7X8X9X10в1X800-0,333-10,41600,3331-0,41600,1250X1100,3330-0,1660-,33300,16600,250X201-0,83300,16600,8330-0,16600,51X10000,8330-0,166-1-0,83300,16610,2F000,5-10,25-1-1,50-1,2500,325
0000001111СвБ.П.X1X2X3X4X5X6X7X8X9X10в1X8000-10,35-0,401-0,350,40,2050X11000-0,10,4000,1-0,40,170X201000-100010,70X30010-0,2-1,2-100,21,20,24F000-10,35-0,4-10-1,35-0,60,205
0000001111СвБ.П.X1X2X3X4X5X6X7X8X9X10в0X5000-2,851-1,1402,857-1-1,1420,5850X1100-0,28500,28500,2850-0,2850,2280X201000-100010,70X3001-0,5710-1,42-1-1,57101,4280,357F000000-1-1-1-10 оптимальное решение вспомогательной задачи. Искусственные переменные являются свободными и равны нулю. Т.о. это решение является опорным планом исходной задачи.
Решим исходную задачу:
16100000СвБ.П.X1X2X3X4X5X6в0X5000-2,851-1,140,58516X1100-0,28500,2850,22810X201000-10,70X3001-0,5710-1,420,357F000-4,5760-5,4243,648Критерий можно улучшить, т.к. , , но нельзя найти такое , при котором базисные переменные обращаются в 0. Значит задача неразрешима из-за неограниченности критерия.
5 вариант.
После отмеченного таким образом праздника обязательно наступает похмелье. Решим задачу из предыдущего варианта, минимизируя этот неприятный фактор, т.е. функция цели: .
Приводим ограничения к каноническому виду:
=>
Эта задача решается методом искусственного базиса, т.к. в ней нет единичной подматрицы. Вспомогательная задача получается точно такой же, как и в предыдущем варианте, поэтому просто возьмем опорный план из предыдущей задачи.
;
16100000СвБ.П.X1X2X3X4X5X6в0X5000-2,851-1,140,58516X1100-0,28500,2850,22810X201000-10,70X3001-0,5710-1,420,357F000-4,5760-5,4243,648Видим, что оценки свободных переменных меньше нуля, значит решение оптимальное.
; F = 3,648.
Делаем вывод: оптимальное решение может существовать и при неограниченности области.
Область не ограничена, но существует оптимальное решение , причем единственное, которое достигается в угловой точке.