вычисления таким образом, чтобы это ограничение учитывалось непосредственно путем подстановки значения р вместо переменной р, что также уменьшает количество переменных в задаче. (Можно также использовать метод решения задач ЛП с ограниченными переменными из раздела 7.3 для выполнения замены р = р*,

предполагая при этом ограничение вида pt < р] ) С этой точки зрения правило исключения столбцов, если отвлечься от его теоретической привлекательности, не имеет особых вычислительных преимуществ по сравнению с описанной выше процедурой. Но ради объективности мы продемонстрируем, как работает правило исключения столбцов в примере 8.2.3. В следующем примере покажем использование описанной выше упрощенной процедуры решения задач с приоритетами.

Пример 8.2.2

Решим методом приоритетов задачу из примера 8.2.1. Предположим, что наибольший приоритет имеет частная целевая функция, соответствующая условию, налагаемому на объем рекламной аудитории. Этап 0. G, >- G2, где

G,: минимизировать s* (условие по рекламной аудитории), G2: минимизировать s, (условие по бюджету). Этап 1. Решаем первую задачу ЛП.

Минимизировать G, = s* при выполнении ограничений

4jc, 4- 8jc2 4- j* - j = 45 (условие по рекламной аудитории),

8х, 4- 24jc2 100 (условие по бюджету),

л:, 4- 2jc2 < 10 (ограничение по рекламным агентам), jc, < 6 (ограничение на рекламу по радио), xx,xv s*, j~ , j2 , s; >0.

Оптимальное решение этой задачи (найденное с помощью программы TORA) составляет хх = Ъ минут, дг2 = 2,5 минуты, s{ =5

миллионов человек, остальные переменные равны нулю. Решение показывает, что условие по объему рекламной аудитории не выполняется с дефицитом в 5 млн. чел.

В этой задаче мы имеем рх = s[. Поэтому в следующей задаче добавим ограничение s* = 5.

Этап 2. Теперь необходимо решить вторую задачу ЛП. Минимизировать G2 = sl

при выполнении тех же ограничений, что и в предыдущей задаче, плюс дополнительное ограничение =5. Мы можем решить эту

задачу, используя, как и на предыдущем этапе, программу TORA, и добавив с помощью опции MODIFY (Изменить) новое ограничение.

Но в данном случае в решении второй задачи нет необходимости, поскольку уже в решении первой имеем 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 первой задачи.