Промежуточные вычислении 8 страница

нет. Это та гибкость, которая позволяет целевому программированию достичь ком­промиссного решения. Естественно, хорошее компромиссное решение минимизи­рует число невыполняемых ограничений.

В нашем примере первые три ограничения являются неравенствами типа ">", а четвертое— неравенством типа "<". Вследствие этого положительные значения отклоняющих переменных s,⁺, s₂, s$ и s₄ будут указывать на то, что соответст­вующие ограничения не выполняются. Поэтому ведется поиск такого компромисс­ного решения, которое будет удовлетворять по возможности большему числу сле­дующих частных целей (целевых функций).

Минимизировать G, = Минимизировать G₂ - s₂ Минимизировать G₃ = s* Минимизировать G_t = s~

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

УПРАЖНЕНИЯ 8.1

1. Сформулируйте заново задачу о налогах из примера 8.1.1, предполагая, что городской совет определил дополнительное ограничение, которое заключает­ся в том, что поступления от налога на бензин должны составлять не менее 10% от общих налоговых поступлений.

2. Руководство супермаркета планирует провести несколько специальных ме­роприятий для привлечения потенциальных покупателей. Два основных (наиболее популярных) мероприятия — эстрадный концерт и выставка ис­кусств и ремесел — посещают практически все слои населения, которые ме­неджеры супермаркета условно разбивают по трем возрастным группам: ти-нэйджеры (подростковая группа), группа среднего возраста (сюда вошла и молодежь, вышедшая из подросткового возраста) и старшая возрастная группа. Стоимость одного концерта и одной выставки составляет 1 500 и 3 ООО долл. соответственно. Общий годовой бюджет этих мероприятий не должен превышать 15 ООО долл. Менеджеры супермаркета оценивают посе­щаемость своих мероприятий следующим образом.

Глава 8. Целевое программирование

Мероприятие		Количество посетителей
	Подростки	Средняя группа	Старшая группа
Концерт
Выставка искусств

Руководство супермаркета желает, чтобы их мероприятия посетило не менее 1000 подростков, 1200 людей из средней возрастной группы и не менее 800 по­тенциальных покупателей старшего возраста. Сформулируйте модель целе­вого программирования.

3. Университет Озарк проводит прием студентов. Всех поступающих можно разбить на три категории: жители данного штата, приезжие из других шта­тов и поступающие из других стран. Соотношения между мужчинами и женщинами среди поступающих данного штата и других штатов равны со­ответственно 1: 1 и 3: 2. Для "международных" студентов это соотношение составляет 8:1. При зачислении студентов на первый курс одним из основ­ных факторов, влияющих на зачисление, является средний балл ACT (American College Test — Американский тест для поступающих в колледж). Статистика, накопленная университетом, свидетельствует, что средний балл ACT равен 27, 26 и 23 соответственно для поступающих данного штата, дру­гих штатов и других стран. Приемная комиссия университета при приеме первокурсников желает добиться следующего.

a) На первый курс желательно принять не менее 1200 студентов.

b) Средний балл ACT всех первокурсников должен быть не ниже 25.

c) Студенты-неамериканцы должны составлять не менее 10% от всего коли­чества первокурсников.

d) Отношение количества женщин и мужчин желательно не менее 3: 4.

e) Среди всех принятых на первый курс жители других штатов должны со­ставлять не менее 20%.

Сформулируйте данную проблему как модель целевого программирования.

4. Птицефабрика ежедневно потребляет 3 тонны специальных кормов. Кормо­вая смесь состоит из известняка, зерна и соевой муки и должна удовлетво­рять требованиям рационального питания:

кальций — не менее 0,8 и не более 1,2%,

белок — не менее 22%,

клетчатка — не более 5%.

В следующей таблице приведен состав ингредиентов кормовой смеси.

	Кальций	Белок	Клетчатка
Ингредиент		(в фунтах на фунт ингредиента)
Известняк	0,380	0,00	0,00
Зерно	0,001	0,09	0,02
Соевая мука	0,002	0,50	0,08

Сформулируйте модель целевого программирования. Как вы думаете, стоит ли в данной ситуации применять модель целевого программирования?

8.1. Формулировка задачи целевого программирования

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

Смена	Количество изделий в партии
Колеса Сиденья
	500 300
	600 280
	640 360

В идеале количество произведенных колес должно точно в два раза превы­шать количество произведенных сидений (напомним, что на каждую тележ­ку идет четыре колеса и два сиденья). Но так как число произведенных изде­лий колеблется от смены к смене, невозможно обеспечить точный баланс между количествами произведенных колес и сидений. Фабрика планирует определить, какое количество партий изделий необходимо изготовлять каж­дую смену, чтобы свести к минимуму дисбаланс между произведенными ко­лесами и сидениями. В первую смену можно произвести 4 или 5 партий изде­лий, во вторую — от 10 до 20 партий, а в третью — от 3 до 5. Сформулируйте задачу целевого программирования.

6. Завод продает четыре типа изделий, для производства которых используются токарный и сверлильный станки. Каждый из этих станков может работать 10 часов в рабочий день. В следующей таблице показано, сколько минут ра­бочего времени необходимо для изготовления изделия каждого типа.

Изделие Токарный станок Сверлильный станок

1 5 3

2 6 2

3 4 6

4 7 4

Завод пытается сбалансировать время использования станков таким обра­зом, чтобы разность между полными временами работы станков не превы­шала 30 минут. Спрос на изделия каждого типа составляет не менее 10 единиц. Кроме того, количество изделий первого типа не может превышать количество изделий второго типа. Сформулируйте задачу целевого про­граммирования.

7. Производство двух изделий требует двух последовательных операций. В сле­дующей таблице показано время (в минутах) выполнения каждой операции при изготовлении изделий.

Операция	Изделие 1	Изделие 2

Глава 8. Целевое программирование

Ежедневная квота на производство первого и второго изделий составляет со­ответственно 80 и 60 единиц. На выполнение каждой операции отводится по 8 часов в рабочий день. Сверхурочные работы не желательны, хотя при необ­ходимости, чтобы выполнить производственный план, их можно применять. Сформулируйте задачу целевого программирования.

8. Городская больница планирует организовать для больных кратковременный (до 4 дней) стационар на свободных местах. Предполагается, что в течение 4-дневного периода будет 30, 25 и 20 больных, которым потребуется 1-, 2- и 3-дневный стационар. Также рассчитано, что на тот же период будет свободно 20, 30, 30 и 30 мест соответственно. Используйте целевое программирование, чтобы вычислить максимальное и минимальное количество больных, кото­рых можно принять на кратковременное лечение.

9. Семейство Траппов собирается переезжать в новый город, где оба супруга нашли новую работу. Сейчас они пытаются определить идеальное местопо­ложение своего нового дома, составив список своих пожеланий:

а) новый дом должен быть как можно ближе к месту работы м-ра Траппа (в пределах четверти мили),

б) дом должен быть как можно дальше от шумного аэропорта (не ближе 10 миль),

в) желательно, чтобы в пределах одной мили от дома был супермаркет.

Для решения своей задачи супруги нанесли на карту города координатную сетку и пометили место работы, аэропорт и супермаркет. Получили следую­щие их координаты: место работы— (1, 1), аэропорт— (20,15), супермар­кет — (4, 7) (все расстояния приведены в милях). Сформулируйте задачу це­левого программирования. (Примечание. Ограничения не обязательно должны быть линейными.)

10. Регрессионный анализ. Предположим, что в лабораторном эксперименте ка­ждому значению y_t независимого параметра у соответствует л измерений х, i=l,2, т, j = 1, 2, л, зависимой величины х. Требуется построить ли­нию регрессии, проходящую через экспериментальные точки. Обозначим че­рез b_Jt j = 0, 1, л, коэффициенты уравнения регрессии. Коэффициенты Ь_; находятся из условия минимума суммы абсолютных значений разностей на­блюдаемых и расчетных (т.е. рассчитанных на основании уравнения регрес­сии) значений зависимой величины. Сформулируйте эту задачу в виде моде­ли целевого программирования.

11. Задача Чебышева. Здесь, в отличие от предыдущей задачи, коэффициенты регрессии находятся из условия минимизации максимума абсолютных зна­чений разностей наблюдаемых и расчетных значений зависимой величины. Сформулируйте задачу целевого программирования.

8.2. АЛГОРИТМЫ ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ

В этом разделе представлены два метода решения задач целевого программиро­вания. Оба метода основаны на сведении множества частных целей к одной целевой функции. В методе весовых коэффициентов единственная целевая функция фор­мируется как взвешенная сумма исходных частных целевых функций. В методе приоритетов на частные цели устанавливаются приоритеты в порядке их важности.

8.2. Алгоритмы целевого программирования

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

Эти методы различны по своей природе и в общем случае дают оптимальные ре­шения, не совпадающие между собой. Вместе с тем нельзя сказать, что один из этих методов лучше другого; в сущности, они предназначены для решения задач с раз­ными предпочтениями в процессе принятия решений.

8.2.1. Метод весовых коэффициентов

Предположим, что модель целевого программирования имеет п целей следую­щего вида.

Минимизировать G_t, £ = 1,2,п.

В методе весовых коэффициентов обобщенная целевая функция определяется следующим образом.

Минимизировать г = m;,G₁ + w₂G₂ +... + w_nG_n.

Здесь w_t (i = 1, 2, n)— положительные весовые коэффициенты, которые ото­бражают предпочтения, отдаваемые каждой цели. Например, вариант ш, = 1 для всех i говорит о равнозначности всех целей. Задание значений весовым коэффици­ентам очень субъективно. В настоящее время разработаны различные методы (см. [1]), которые уменьшают субъективный фактор при определении весовых ко­эффициентов.

Пример 8.2.1

Новое рекламное агентство, в составе которого 10 рекламных агентов, получило контракт на рекламу нового продукта. Агентство может провести рекламную ак­цию на радио и телевидении. В следующей таблице приведены данные о количестве людей, охватываемых тем или иным видом рекламы, стоимость этой рекламы и количество необходимых рекламных агентов. Все эти данные отнесены к одной минуте рекламного времени.

	Радио	Телевидение
Рекламная аудитория (млн. чел.)
Стоимость (тыс. долл.)
Количество рекламных агентов

Реклама на радио и телевидении должна охватить не менее 45 миллионов человек (так называемая рекламная аудитория), но контракт запрещает использовать более 6 минут рекламы на радио. Рекламное агентство может выделить на этот проект бюджет, не превышающий 100 ООО долл. Сколько минут рекламного времени агентство должно купить на радио и сколько на телевидении?

Обозначим через дг, и х₂ количество минут рекламного времени, закупленного соот­ветственно на радио и телевидении. Для данной задачи целевого программирова­ния можно задать следующие частные целевые функции.

Глава 8. Целевое программирование

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

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

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

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

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

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

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

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

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

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

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

УПРАЖНЕНИЯ 8.2.1

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

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

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

Возраст (года)	Образование (года)	Опыт (года)	Заработок (долл.)
			40 ООО
			48 ООО
			38 ООО
			36 ООО
			41 ООО

Используя формулировку задачи целевого программирования из упражне­ния 8.1.10, постройте уравнение линейной регрессии у — Ь₀ + Ь,х, + Ь_гх₂ + Ь₃х_ъ на основе данных этой таблицы.

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

Глава 8. Целевое программирование

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

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

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

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

В методе приоритетов поочередно решаются задачи с одной целевой функцией, начиная с задачи с целевой функцией G_v имеющей наивысший приоритет, и закан­чивая задачей с целевой функцией G_n, имеющей минимальный приоритет. В процессе решения последовательных задач решение задачи с целевой функцией, имеющей бо­лее низкий приоритет, не может ухудшить полученные ранее решения задач с целе­вой функцией, имеющих более высокий приоритет. Это означает, что если z(G) — оптимальное значение целевой функции G_t, то для всех i > 1 оптимизация любой це­левой функции Gj (j¹ > i) с меньшим приоритетом не может ухудшить значение z{G).

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

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

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

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

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

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

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

8.2. Алгоритмы целевого программирования

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

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

Пример 8.2.2

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

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

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

4jc, + 8jc₂ + s\ - j," = 45 (условие по рекламной аудитории),

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

+ 2jc₂ < 10 (ограничение по рекламным агентам), jc, < 6 (ограничение на рекламу по радио), x_x,x_v si, si, si, s; >0.

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

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

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

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

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

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

Глава 8. Целевое программирование

Но в данном случае в решении второй задачи нет необходимости, поскольку уже в решении первой имеем 5," = 0. Следовательно, решение первой задачи автомати­чески является оптимальным решением второй (можете проверить это утвержде­ние с помощью программы TORA). Решение 5; = 0 показывает, что ограничение, касающееся бюджета рекламной компании, выполняется.

Дополнительное ограничение 5* = 5 можно также учесть путем подстановки значе­ния 5 вместо переменной 5* в первое ограничение. В результате правая часть этого неравенства изменится со значения 45 на 40. Получим следующую задачу ЛП.

Минимизировать G₂ = 5; при ограничениях

4jc, + 8х₂ - s; = 40,

8х, + 24jc₂ + 5,* - s; = 100, х_г + 2х₂ < 10,

X,) X₂j 5,, 5,, 5₂ ^0.

В новой формулировке этой задачи на одну переменную меньше, чем в первой задаче.

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

Пример 8.2.3

Цели, поставленные в задаче из примера 8.2.2, можно переформулировать сле­дующим образом.

Цель 1. Максимизировать объем рекламной аудитории (/>,).

Цель 2. Минимизировать стоимость рекламной кампании (Р₂).

Математически эти цели можно выразить с помощью следующих целевых функций.

Максимизировать Р, = 4jc, + 8х₂, минимизировать Р₂ = 8х, + 24х₂.

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

Получили новую задачу.

Максимизировать Р, = 4х, + 8х₂, минимизировать Р₂ = 8х_х + 24х₂

8.2. Алгоритмы целевого программирования

при ограничениях

х, + 2х_г < 10,

л-,<6,

x_vx₂>0.

Сначала решим эту задачу с помощью процедуры, описанной в примере 8.2.2. Этап 1. Решаем первую задачу ЛП.

Максимизировать />, = 4jc, + 8х_г

при ограничениях

х_х + 2х₂<\0,

а-,<6,

jc„jc₂>0.

Оптимальное решение этой задачи (полученное с помощью программы TORA) со­ставляет х, = 0, х₂ — 5 и Р, = 40. Отсюда видно, что объем рекламной аудитории не может превысить 40 миллионов человек.

Этап 2. Добавим ограничение 4х_х + 8х₂ > 40, которое гарантирует, что решение, полу­ченное на предыдущем этапе, не будет ухудшено, и решаем следующую задачу ЛП.

Минимизировать/⁵,, = 8х₁ + 24х_г

при ограничениях

дг, + 2х₂ < 10,

4дг, + 8х₂ > 40, х_х,х₂>0.

Программа TORA дает следующее оптимальное решение этой задачи: Р₂ = 96 000 долл., х_: = 6 минут их₂ = 2 минуты. Мы получили тот же объем реклам­ной аудитории (Р, = 40 млн. чел.), но за меньшую стоимость. Это результат того, что здесь мы искали оптимальные значения соответствующих величин, а не просто удовлетворяли ограничениям, как в примере 8.2.2.

Теперь решим ту же задачу, используя правило исключения столбцов. Это правило применяется последовательно к строкам симплекс-таблицы, соответствующим ча­стным целевым функциям.

Первая задача ЛП. Максимизация объема рекламной аудитории. При решении этой задачи симплекс-таблица содержит строки, соответствующие как целевой функции P_v так и целевой функции Р₂. Строка целевой функции Р₂ пока играет пассивную роль, но будет изменена перед решением второй задачи ЛП.

Первая задача решается за две симплексные итерации, как показано в следующей таблице.

Нижняя часть этой таблицы показывает оптимальное решение^ = 0, х₂ = 5 и Р_х = 40 первой задачи.

Глава 8. Целевое программирование

Итерация		Базис	Xl	Х2	Si	s2	Решение
		Р,	1 -4	-8
		Рг	-8	-24
		Si
		Si
		Pi			4 '
		Р2
		*2	1/2		ч. 1/2 •
		s2

Правило исключения столбцов применяется перед решением второй задачи для удаления из симплекс-таблицы с оптимальным решением первой задачи небазис­ной переменной х_р для которой г₁ - Cj ф 0. Такие переменные, приняв положитель­ные значения в задаче с более низким приоритетом, ухудшают решение задач с бо­лее высоким приоритетом.