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

Литература

УПРАЖНЕНИЯ 8.2.2

1. Пусть в задаче из примера 8.2.2 бюджет рекламной компании возрос до 110 ООО долл. Желаемый объем рекламной аудитории остался неизменным - 45 млн. чел. Найдите решение данной задачи методом приоритетов.

2. Решите задачу из упражнения 8.1.1, используя следующую иерархию приоритетов частных целевых функций: G, у G2 у G3 у GA.

3. Вернитесь к задаче из упражнения 8.1.2. Пусть частные целевые функции, описывающие количество привлеченных посетителей подросткового, среднего и старшего возрастов, обозначаются соответственно G G2 и G,. Решите эту задачу при следующих иерархиях приоритетов частных целевых функций:

a) G,yG2y G3,

b) G3y G2y <?,.

4. С помощью метода приоритетов решите задачу из упражнения 8.1.3, предполагая, что порядок приоритетов частных целевых функций совпадает с порядком их описания в задаче.

ЛИТЕРАТУРА

1. Cohon Т. L. Multiobjective Programming and Planning. Academic Press, New York, 1978.

2. Ignizio J. P., Cavalier T.M. Linear Programming. Prentice-Hall, Upper Saddle River, NJ, 1994.

3. Steuer R. E. Multiple Criteria Optimization: Theory, Computations, and Application, Wiley, New York, 1986.

Литература, добавленная при переводе

1. Поляк Б. Т. Введение в оптимизацию. - М.: Наука, 1983.

2. Поспелов Г. С, Ириков В. А. Программно-целевое планирование и управление. - М.: Сов. радио, 1976.

3. Соболь И. М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями. - М.: Наука, 1981.

4. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. - М.: Наука, 1986.

КОМПЛЕКСНЫЕ ЗАДАЧИ

8.1. 1 Лесозаготовительная компания использует три участка леса площадью 100 ООО, 180 ООО и 200 000 акров для заготовки древесины и последующих лесопосадок. Древесная продукция компании разбита на три основные категории: пиломатериал, клееная фанера и древесная измельченная масса. Для каждого участка лесного массива возможны различные альтернативные варианты его эксплуатации, которые различаются стоимостью разработок, арендной платой, периодом чередования вырубок и лесопосадок, объемом произведенной продукции. Эти альтернативы показаны в следующей таблице.

1 Задача основана на материалах статьи Rustagi К.Р. Forest Management Planning for Timber Prodaction: A Goal Programming Approach, Bulletin No. 89, Yale University, New Haven, 1976.

долл. в год/акр Период м3 в год/акр

Участок Альтернатива Стоимость Аренда чередова- Пиломатериалы Фанера Древесная

ния (годы) масса

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

Компания преследует следующие цели.

Ежегодное производство пиломатериалов, фанеры и древесной массы должно быть не менее 200 000,150 000 и 350 000 кубических метров соответственно.

1. Ежегодный бюджет на восстановление леса составляет 2,5 млн. долл.

2. Ежегодная арендная плата должна составлять 100 долл. за акр.

Какой вариант эксплуатации для каждого участка леса следует выбрать?

8.2. Благотворительная организация помогает детскому приюту. Для этого она привлекает волонтеров ежедневно с 8 до 14 часов. Волонтеры могут начать работу в любое время с 8 до 11 часов. Длительность работы волонтера не более 6 и не менее 2 часов. С 12 до 13 часов обеденное время. Благотворительная организация считает, что в приюте ежедневно необходимо 15 волонтеров для работы с 8 до 9, 16 волонтеров - с 9 до 10, 18 волонтеров - с 10 до 11, 20 волонтеров - с 11 до 12 и 16 волонтеров - с 12 до 14 часов (но это работа на один час, так как с 12 до 13 обеденное время). Здесь частными целевыми функциями могут быть волонтеры (т.е. их количество), работающие в течение каждого часа с 8 до 14. Цель всей задачи - определить количество волонтеров, приступающих к работе в начале каждого часа, и длительность их работы. Сформулируйте и решите эту задачу как задачу целевого программирования.