close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Aвтор: Телешова Елизавета, студентка Нижегородский Университет (ННГУ), кафедра мировой экономики, преподаватель Громницкий В. С. 2001г.

Лабораторная работа № 2
Телешовой Елизаветы, гр. 726,
Цель работы: Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования.
1 вариант.
1. Четыре студента: Иванов, Петров, Сидоров и Васильев пошли на концерт группы "Чайф", захватив пиво 2 сортов: "Русич" и "Премьер". Определить план распития напитков для получения максимального суммарного опьянения (в ). Исходные данные даны в таблице:
СтудентНорма выпитогоЗапасы (в литрах)"Русич""Премьер"Иванов221.5Петров3,511,5Сидоров1044,5Васильев-10,7Крепость напитка16 %10 %
2. Математическая модель.
2.1 Управляемые параметры
x1[л] - количество выпитого пива "Русич". x2[л] - количество выпитого пива "Премьер". - решение.
2.2 Ограничения
- количество пива "Русич", выпитого Ивановым.
- количество пива "Премьер", выпитого Ивановым.
- общее количество пива, выпитого Ивановым.
Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него запасов пива, поэтому:
(л).
Аналогично строим другие ограничения:
(л).
(л).
(л).
3. Постановка задачи.
Найти *, где достигается максимальное значение функции цели:
4. Решение.
при:
Приведем задачу к каноническому виду: Определим начальный опорный план: .
Это решение является опорным, т.к. вектора условий при положительных компонентах решения линейно независимы, также , где , но не все оценки положительны (, где )
Опорный план является оптимальным, если для задачи максимизации все его оценки неотрицательны. не является оптимальным, значит критерий можно улучшить, если увеличить одну их отрицательных свободных переменных. Будем увеличивать , т.к. ее увеличение вызовет большее увеличение функции цели. Предположим, что , тогда:
Запишем новый опорный план: . Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:
=> При увеличении , первой перестает выполнять условие неотрицательности переменная , т.к. она первая обращается в ноль. Значит выведем из базиса . Теперь базисными переменными являются , а свободными . Для анализа этого плана выразим функцию цели через новые переменные.
Из ограничения (2) имеем: .
Подставляя в функцию цели: получаем:
Оформим данный этап задачи в виде симплекс-таблицы:
Начальная симплекс-таблица:
16100000СвБ.П.X1X2X3X4X5X6в0X32210001,50X43,5101001,50X510400104,50X60100010,7F-16-1000000 ;
Пересчитаем элементы исходной таблицы по правилу четырехугольника:
16100000СвБ.П.X1X2X3X4X5X6В0X301,4281-0,572000,64216X110,28600,286000,4280X501,140-2,86100,2140X60100010,7F0-5,42404,576006,857;
Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:
откуда получаем:
;
Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:
=> Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:
, а из ограничений (2) и (3): . Тогда: ;
16100000СвБ.П.X1X2X3X4X5X6В0X30013-1,2500,37516X11001-0,2500,37510X2010-2,50,87500,18750X60002,5-0,87510,5125F000-94,7507,875
Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:
откуда получаем:
;
Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:
=> Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:
, а из ограничений (1) и (2): . Тогда: ;
16100000СвБ.П.X1X2X3X4X5X6в0X4000,3331-0,41600,12516X110-0,33300,16600,2510X2011,8330-0,16600,50X600-0,83300,16610,2F0030109
Видим, что все оценки положительны, значит любое увеличение какой-либо свободной переменной уменьшит критерий. Данное решение является оптимальным. Изобразим это решение на графике:
Видим, что единственное и достигается в угловой точке области допустимых решений.
2 вариант.
Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в таких же пропорциях, за исключением того, что вместо пива "Премьер" было куплено пиво "Окское", крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в ).
Функция цели: .
Приводим ограничения к каноническому виду:
=> Решаем симплекс-методом:
166,40000СвБ.П.X1X2X3X4X5X6В0X32210001,50X43,5101001,50X510400104,50X60100010,7F-16-1000000 , 166,40000СвБ.П.X1X2X3X4X5X6В0X301,4281-0,571000,64216X111,28600,286000,4280X501,1420-2,85100,2140X60100010,7F0-1,8204,571006,857; 166,40000СвБ.П.X1X2X3X4X5X6В0X30013-1,2500,37516X11001-0,2500,3756,4X2010-2,50,87500,18750X60002,5-0,87510,5125F00001,607,2 ; Видим, что все оценки положительны, значит оптимальное решение достигнуто. Но одна из свободных переменных () обратилась в ноль, и если мы ее будем увеличивать, то функция цели не изменится, а решение будет другим, т.е. получим еще одно оптимальное решение, которое будет называться альтернативным.
16100000СвБ.П.X1X2X3X4X5X6в0X4000,3331-0,41600,12516X110-0,33300,16600,2510X2011,8330-0,16600,50X600-0,83300,16610,2F0000107,2
Если оптимальное решение достигнуто в 2-х точках, то оно достигается и на отрезке между ними. Можно составить уравнение данного отрезка по формуле:
;
;
На графике видно, что оптимальное решение достигается на отрезке, значит является альтернативным. Вектор градиента целевой функции (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.
Делаем вывод: оптимальное решение может существовать и при неограниченности области.
Область не ограничена, но существует оптимальное решение , причем единственное, которое достигается в угловой точке.
1
Документ
Категория
Теория систем управления
Просмотров
132
Размер файла
514 Кб
Теги
лабораторная
1/--страниц
Пожаловаться на содержимое документа