Отклоняющие переменные и s. зависимы по определению, поэтому они обе одновременно не могут быть базисными. Это означает, что на любом этапе решения задачи одним из симплексных методов только одна из пары отклоняющих переменных может принимать положительное значение. Если исходное i-e ограничение является неравенством типа "<" и s* > О, то это ограничение выполняется. Если же
s. > О, то данное ограничение не выполняется. Таким образом, определенные значения отклоняющих переменных s* и j~ либо соответствуют i-e ограничению, либо
нет. Это та гибкость, которая позволяет целевому программированию достичь компромиссного решения. Естественно, хорошее компромиссное решение минимизирует число невыполняемых ограничений.
В нашем примере первые три ограничения являются неравенствами типа ">", а четвертое- неравенством типа "<". Вследствие этого положительные значения отклоняющих переменных s,+, s2, s3* и s4 будут указывать на то, что соответствующие ограничения не выполняются. Поэтому ведется поиск такого компромиссного решения, которое будет удовлетворять по возможности большему числу следующих частных целей (целевых функций).
Минимизировать G, = Минимизировать G2 - s2* Минимизировать G3 = s* Минимизировать Gt = s~
Как оптимизировать модель, имеющую несколько конфликтующих целевых функций? Для этого разработано множество разнообразных методов. В данной главе рассмотрим, во-первых, метод весовых коэффициентов и, во-вторых, метод приоритетов. Оба метода основаны на приведении множества частных целевых функций к одной целевой функции.
УПРАЖНЕНИЯ 8.1
1. Сформулируйте заново задачу о налогах из примера 8.1.1, предполагая, что городской совет определил дополнительное ограничение, которое заключается в том, что поступления от налога на бензин должны составлять не менее 10% от общих налоговых поступлений.
2. Руководство супермаркета планирует провести несколько специальных мероприятий для привлечения потенциальных покупателей. Два основных (наиболее популярных) мероприятия - эстрадный концерт и выставка искусств и ремесел - посещают практически все слои населения, которые менеджеры супермаркета условно разбивают по трем возрастным группам: ти-нэйджеры (подростковая группа), группа среднего возраста (сюда вошла и молодежь, вышедшая из подросткового возраста) и старшая возрастная группа. Стоимость одного концерта и одной выставки составляет 1 500 и 3 ООО долл. соответственно. Общий годовой бюджет этих мероприятий не должен превышать 15 ООО долл. Менеджеры супермаркета оценивают посещаемость своих мероприятий следующим образом.
Мероприятие | | Количество посетителей | |
| Подростки | Средняя группа | Старшая группа |
Концерт | | | |
Выставка искусств | | | |
Руководство супермаркета желает, чтобы их мероприятия посетило не менее 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 |
Сформулируйте модель целевого программирования. Как вы думаете, стоит ли в данной ситуации применять модель целевого программирования?
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 |
| | |
| | |