Решение задачи симплексным методом
Суть этого метода состоит в переходе от одного опорного решения к другому при условии, что значение целевой функции при этом будет увеличиваться. Рассмотрим решение предыдущей задачи: 12x1 + 4х2 ≤ 300, 4х1 + 4х2 ≤ 120, 3х1 + 12х2 ≤ 252, x1, х2 ≥ 0.
F = 30x1 + 40х2 → max Перейдем к основной задаче линейного программирования путем введения дополнительных переменных x3, х4, x5, которые по физическому смыслу означают неиспользованный ресурс времени плиточников, штукатуров и маляров то есть от системы ограничений вида неравенств перейдем к системе ограничений вида равенств. 12x1 + 4х2 + х3 = 300, 4х1 + 4х2 + х4 = 120, 3х1 + 12х2 + х5 = 252, x1, х2, x3, х4, x5 ≥ 0.
F = 30∙x1 + 40∙х2 + 0∙х3 + 0∙х4 + 0∙х5 → max Запишем систему ограничений в векторной форме: , где векторы: ; ; ; ; ; . Среди системы векторов есть три единичных вектора , , , которые образуют базис. Задача имеет невырожденный опорный план X0 (0, 0, 300, 120, 252) и ее можно решить табличным симплекс-методом. Составим симплекс-таблицы:
Поясним заполнение симплекс-таблиц. Таблица I. В 4-ой строке в столбце P0 записываем скалярное произведение = 300 ∙ 0 + 120 ∙ 0 + 252 ∙ 0 = 0. Таким образом, прибыль по опорному плану составляет 0 у.е. В остальных столбцах этой строки записываем , j = 1,… n. ∆1 = 0 ∙ 12 + 0 ∙ 4 + 0 ∙ 3 – 30 = –30, ∆2 = 0 ∙ 4 + 0 ∙ 4 + 0 ∙ 12 – 40 = –40 и т.д. Определяем вектор для ввода в базис из векторов, для которых ∆j < 0 (4-ая строка). Возьмем вектор Р2, так как он соответствует наименьшему ∆j = ∆2 = –40. Столбец, соответствующий вектору Р2 является направляющим. Вектор для вывода из базиса определяем по числу . Это значение соответствует вектору Р5. Эта строка является направляющей. Элемент a23 = 12 является разрешающим элементом. Заполнение таблицы II начинается с заполнения направляющей строки делением всех ее элементов на a23 = 12. Остальные элементы таблицы II вычисляются по формуле Жордана-Гаусса. Например, , и т.д. В таблице II в 4-ой строке, есть отрицательное число ∆j. Оно соответствует вектору Р2. соответствует базисному вектору Р3. Таким образом, вектор Р3 выводим из базиса, а вектор Р2 вводим в базис Элемент a12 = 3 является разрешающим. Прибыль по этому плану составляет 840 у.е Перерасчет элементов таблицы III осуществляется как и раньше. В таблице III в 4-ой строке среди ∆j нет отрицательных, следовательно, получен оптимальный план: Xопт (12, 18, 84, 0, 0), Fmax = 1080 у.е. Покажем соответствие опорных решений и вершин области допустимых решений (ОДР). Опорное решение X0 (0, 0, 300, 120, 252) соответствует точке О (0; 0) ОДР. Решение X1 (0, 21, 216, 36, 0) соответствует точке А (0; 21). Оптимальное решение X2 (12, 18, 84, 0, 0) соответствует точке B (12; 18) ОДР.
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Почему стероиды повышают давление?: Основных причин три... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (360)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |