Но в данном случае в решении второй задачи нет необходимости, поскольку уже в решении первой имеем 5," = 0. Следовательно, решение первой задачи автоматически является оптимальным решением второй (можете проверить это утверждение с помощью программы TORA). Решение s, = 0 показывает, что ограничение, касающееся бюджета рекламной компании, выполняется.
Дополнительное ограничение 5* = 5 можно также учесть путем подстановки значения 5 вместо переменной 5* в первое ограничение. В результате правая часть этого неравенства изменится со значения 45 на 40. Получим следующую задачу ЛП.
Минимизировать G2 = s2~ при ограничениях
4*! + 8х2 - s; = 40,
8х1 + 24х2 + 5,* - s; = 100, хг + 2х2 < 10,
xi> X2j 5j , 5, , 5т 0.
В новой формулировке этой задачи на одну переменную меньше, чем в первой задаче.
Теперь мы используем ту же задачу, чтобы показать, что наилучшее решение получается тогда, когда в методе приоритетов используется оптимизация "настоящих" целевых функций, а не тех целевых функций, которые строятся только для того, чтобы выполнялись определенные ограничения. Следующий пример также демонстрирует правило исключения столбцов при решении задач целевого программирования.
Пример 8.2.3
Цели, поставленные в задаче из примера 8.2.2, можно переформулировать следующим образом.
Цель 1. Максимизировать объем рекламной аудитории (/>,).
Цель 2. Минимизировать стоимость рекламной кампании (Р2).
Математически эти цели можно выразить с помощью следующих целевых функций.
Максимизировать />, = 4х, + 8х2, минимизировать Р2 = 8х, + 24х2.
Отдельные ограничения на желаемый объем рекламной аудитории и стоимость рекламной кампании в данном случае излишни, поскольку для этих величин мы получим границы после решения соответствующих задач.
Получили новую задачу.
Максимизировать Р1 = 4х1 + 8х2, минимизировать Р2 = 8хг + 2Ах2
при ограничениях
х, + 2хг < 10,
л-,<6,
х„х2>0.
Сначала решим эту задачу с помощью процедуры, описанной в примере 8.2.2. Этап 1. Решаем первую задачу ЛП.
Максимизировать />, = 4х, + 8хг
при ограничениях
х, + 2х2<10,
хх<&,
х„х2>0.
Оптимальное решение этой задачи (полученное с помощью программы TORA) составляет х, = 0, х2 - 5 и />, = 40. Отсюда видно, что объем рекламной аудитории не может превысить 40 миллионов человек.
Этап 2. Добавим ограничение 4jc1 + 8х2 > 40, которое гарантирует, что решение, полученное на предыдущем этапе, не будет ухудшено, и решаем следующую задачу ЛП.
Минимизировать/5,, = 8*, + 24х,
при ограничениях
дг, + 2х2 < 10, х,<6,
4jc, + 8х2 > 40, xvx2>0.
Программа TORA дает следующее оптимальное решение этой задачи: Р2 = 96 000 долл., дг, = 6 минут и х2 = 2 минуты. Мы получили тот же объем рекламной аудитории (Р, = 40 млн. чел.), но за меньшую стоимость. Это результат того, что здесь мы искали оптимальные значения соответствующих величин, а не просто удовлетворяли ограничениям, как в примере 8.2.2.
Теперь решим ту же задачу, используя правило исключения столбцов. Это правило применяется последовательно к строкам симплекс-таблицы, соответствующим частным целевым функциям.
Первая задача ЛП. Максимизация объема рекламной аудитории. При решении этой задачи симплекс-таблица содержит строки, соответствующие как целевой функции />,, так и целевой функции Р2. Строка целевой функции Р2 пока играет пассивную роль, но будет изменена перед решением второй задачи ЛП.
Первая задача решается за две симплексные итерации, как показано в следующей таблице.
Нижняя часть этой таблицы показывает оптимальное решение д:, = 0, х2 = 5 и Рх = 40 первой задачи.
Итерация | | Базис | | | | | Решение |
| | | 1 -4 | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | ч. 1/2 • | | |
| | | | | | | |
Правило исключения столбцов применяется перед решением второй задачи для удаления из симплекс-таблицы с оптимальным решением первой задачи небазисной переменной хр для которой г1 - Cj Ф 0. Такие переменные, приняв положительные значения в задаче с более низким приоритетом, ухудшают решение задач с более высоким приоритетом.
Вторая задача ЛП. Минимизация стоимости рекламной кампании. Правило исключения столбцов удаляет переменную s,, для которой г, - сг = 4. Из Р2-строки приведенной выше симплекс-таблицы видно, что если не удалить переменную s,, то на первой итерации решения второй задачи она должна войти в базис, при этом из базиса будет исключена переменная х2. После этого будет получено оптимальное решение второй задачи (в этом решении хх = х2 = 0), которое ухудшает оптимальное решение первой, поскольку теперь Р, = 0 вместо Р, = 40, как было ранее.
В данном случае вторая задача ЛП является задачей минимизации. После удаления переменной 5, в базис вводится небазисная переменная х, со значением разности Zj - сг равным 4 (> 0), что может улучшить значение целевой функции Р2. В следующей симплекс-таблице показаны две итерации решения второй задачи ЛП. Р,-строку можно удалить из этой таблицы, так как она не участвует в процессе поиска оптимального решения задачи с целевой функцией Р2.
Итерация Базис Xi хг Si вг Решение
Pi 40
1 -V-P- 4 0 0 120
х2 1/2 1 0 5
s2 1 0 16
Pi 40
2 Р2 0 0 -4 96 х2 0 1 -1/2 2 Xi 1 0 16
Полученное здесь оптимальное решение (х, = 6, х2 = 2) со значениями целевых функций Р, = 40 и Р2 - 96 такое же, как и полученное ранее.