Минимизировать Gl = $1 (для выполнения условия по рекламной аудитории),

минимизировать G2 = s, (для выполнения условия по бюджету)

при выполнении ограничений

4xl + 8х2 + s* - s~ = 45 (условие по рекламной аудитории),

8jc, + 24х, + s2r - = 100 (условия по бюджету),

jc, + 2jc2 < 10 (ограничение по рекламным агентам), jc, < 6 (ограничение на рекламу по радио),

1 -2* 1 1 2 > 2 -0.

Менеджеры рекламного агентства считают, что выполнение условия по объему рекламной аудитории в два раза важнее, чем выполнение условия по бюджету. Поэтому обобщенная целевая функция будет записана следующим образом.

Минимизировать г = 2G, + G2 = 2 s* + .

Оптимальное решение этой задачи (полученное с помощью программы TORA) следующее: z = 10, х, = 5 минут, х2 = 2,5 минуты, = 5 миллионов человек. Остальные переменные равны нулю.

Тот факт, что оптимальное значение целевой функции не равно нулю, указывает, что по крайней мере одна из исходных целевых функций не достигла своего оптимального значения. Действительно, так как s* = 5, значит, объем рекламной аудитории меньше запланированного на 5 миллионов. При этом условие по бюджету выполнено, поскольку s~ = 0.

Еще раз повторим, что методы целевого программирования позволяют получить только эффективное решение задачи, которое не всегда будет оптимальным. Например, решение = 6 и х2 = 2 дает такой же объем рекламной аудитории (4x6 + 8x2= 40 миллионов человек), но при меньшей стоимости рекламной кампании (8x6+ 24 х 2 = 96 000 долл.). Существенно, что методы целевого программирования в общем случае не находят оптимум каждой целевой функции исходной модели. Этот дефект методов целевого программирования поднимает общий вопрос о жизнеспособности целевого программирования в качестве технологии оптимизации (дальнейшее обсуждение этого вопроса см. в примере 8.2.3).

УПРАЖНЕНИЯ 8.2.1

1. Решите задачу из упражнения 8.1.1, предполагая, что в обобщенную целевую функцию все частные целевые функции входят с одинаковыми весовыми коэффициентами. Будет ли в этом случае достигнут оптимум всех частных целевых функций?

2. Пусть в задаче упражнения 8.1.2 привлечение посетителей средней возрастной группы в два раза важнее, чем привлечение посетителей других возрастных групп. Найдите соответствующее решение и проверьте, будет ли достигнут оптимум всех частных целевых функций.

3. Пусть в задаче о приеме студентов на первый курс университета (см. упражнение 8.1.3) ограничение, касающееся общего количества принятых первокурсников, должно быть выполнено обязательно, остальные ограничения не являются жесткими. Кроме того, считаем, что ограничение на средний балл ACT в два раза важнее, чем остальные ограничения. .

a) Решите данную задачу и проверьте, все ли частные целевые функции достигнут своего оптимума.

b) Пусть ограничение на количество принятых первокурсников не является жестким, но все равно имеет в два раза важнее, чем ограничение на средний балл ACT. Как в этом случае изменится решение?

4. Можно ли в условиях задачи из упражнения 8.1.4 удовлетворить всем требованиям рационального питания?

5. Найдите решение задачи из упражнения 8.1.5 и определите, можно ли сбалансировать ежедневное производство колес и сидений.

6. В задаче из упражнения 8.1.6 выполнение ограничения, касающегося удовлетворения спроса на изделия, считается в два раза важнее, чем сбалансированность рабочего времени станков. Пусть также допустимы сверхурочные работы. Решите эту задачу и проверьте, все ли частные целевые функции достигнут своего оптимума.

7. В задаче из упражнения 8.1.7 производственные квоты должны быть реализованы в любом случае; при необходимости можно использовать сверхурочные работы. Найдите решение этой задачи и определите объем сверхурочных работ, если они используются.

8. Пусть в задаче из упражнения 8.1.8 все частные целевые функции в выражении обобщенной целевой функции имеют равные весовые коэффициенты. Могут ли все частные целевые функции достичь своего оптимума?

9. Отдел кадров компании составил следующую таблицу о своих пяти работниках, чтобы установить зависимость между заработком работника и его возрастом, образованием (выражается в количестве лет, проведенных в колледже) и опытом (количество лет работы в компании).

Используя формулировку задачи целевого программирования из упражнения 8.1.10, постройте уравнение линейной регрессии у - b0 + bxxx + Ьгх2 + Ь3хъ на основе данных этой таблицы.

10. Решите предыдущую задачу, используя условие Чебышева из упражнения 8.1.11.

8.2.2. Метод приоритетов

В методе приоритетов п частных целевых функций ранжируются в порядке их важности, так как их оценивает специалист по принятию решений, т.е.

минимизировать G, = pi (наивысший приоритет),

минимизировать Gn = рп (наинизший приоритет). Переменные $ - это компоненты отклоняющих переменных, т.е. или s~, которые определяют i-ю целевую функцию. Например, в задаче из примера 8.2.1 А = si и А = *2

В методе приоритетов поочередно решаются задачи с одной целевой функцией, начиная с задачи с целевой функцией Gv имеющей наивысший приоритет, и заканчивая задачей с целевой функцией Gn, имеющей минимальный приоритет. В процессе решения последовательных задач решение задачи с целевой функцией, имеющей более низкий приоритет, не может ухудшить полученные ранее решения задач с целевой функцией, имеющих более высокий приоритет. Это означает, что если z(G) - оптимальное значение целевой функции Gt, то для всех i > 1 оптимизация любой целевой функции Gj (j1 > i) с меньшим приоритетом не может ухудшить значение z{G).

В литературе по целевому программированию описан специальный симплекс-метод, который гарантирует неухудшаемость решений задач с целевыми функциями более высокого приоритета. Этот метод использует правило исключения столбцов, которое применяется для удаления из оптимальной симплекс-таблицы задачи с целевой функцией Gk небазисной переменной xf с гу - с. * 0 до начала решения задачи с целевой функцией Gk+1. Это правило распознает, что небазисная переменная х., если она получит ненулевое значение, может ухудшить (но никогда не улучшит) оптимальное значение задачи с целевой функцией, имеющей более высокий приоритет.

К сожалению, этот метод изменения симплекс-таблиц требует более сложных вычислений, чем необходимо на самом деле. Мы покажем, что такого же результата можно достичь более простым способом.

Этап 0. Определяем частные целевые функции задачи и ранжируем их в порядке приоритетов: G, = /О, >- G2 = р2 у ... >- Gn = рп. Положим 1=1.

Этап L Решаем i-ю задачу ЛП с целевой функцией G(. Обозначим через р

полученное оптимальное значение отклоняющей переменной р. Если i = п, вычисления заканчиваются, поскольку решена последняя п-я задача. В противном случае вводим в задачу новое ограничение pt = р*, тогда значение pt не сможет измениться при решении последующих задач. Полагаем i = i + 1 и повторяем этап L

Последовательное введение дополнительных ограничений вида pt = р* теоретически не так элегантно , как правило исключения столбцов. Однако это приводит точно к такому же результату. Кроме того, обоснование введения дополнительных ограничений совершенно очевидно и понятно.

Определенным аргументом в пользу правила исключения столбцов может служить то, что при использовании этого правила происходит удаление переменной, т.е. уменьшается размерность задачи. В то же время описанная выше процедура увеличивает размерность задачи при добавлении новых ограничений. Но если повнимательнее присмотреться к этим ограничениям (вида р = р*), то легко изменить