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

Вторая задача ЛП. Минимизация стоимости рекламной кампании. Правило ис­ключения столбцов удаляет переменную s,, для которой г, - с, = 4. Из Р₂-строки приведенной выше симплекс-таблицы видно, что если не удалить переменную s_x, то на первой итерации решения второй задачи она должна войти в базис, при этом из базиса будет исключена переменная х₂. После этого будет получено оптимальное решение второй задачи (в этом решении х_х — х₂ = 0), которое ухудшает оптимальное решение первой, поскольку теперь Р, = 0 вместо Р, = 40, как было ранее.

В данном случае вторая задача ЛП является задачей минимизации. После удале­ния переменной 5, в базис вводится небазисная переменная х, со значением разно­сти Zj - c_jt равным 4 (> 0), что может улучшить значение целевой функции Р₂. В следующей симплекс-таблице показаны две итерации решения второй задачи ЛП. Р,-строку можно удалить из этой таблицы, так как она не участвует в процессе поиска оптимального решения задачи с целевой функцией Р₂.

Итерация Базис Xi Хг Si s₂ Решение

Pi 40

1 ''-Рг 4 0 0 120

х₂ 1/2 1 0 5

s₂ 1 0 16 Pi 40

2 Рг 0 0 -4 96 х₂ 0 1 -1/2 2 Xi 1 0 16

Полученное здесь оптимальное решение (х, = 6, х₂ = 2) со значениями целевых функций Р, = 40 и Р₂ — 96 такое же, как и полученное ранее.

Литература

УПРАЖНЕНИЯ 8.2.2

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

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

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

a) G,yG₂y G₃,

b) G₃y G₂y G,.

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 Applica­tion, Wiley, New York, 1986.

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

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

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

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

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

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

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

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

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

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

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

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

	А1
	А2
	A3
	А4
	А5
	А6
	А7
	А1
	А2
	A3
	А4
	А5
	А6
	А1
	А2
	A3
	А4
	А5

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

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

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

ГЛАВА 9

ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Целочисленное линейное программирование (ЦЛП) ориентировано на решение задач линейного программирования, в которых все или некоторые переменные должны принимать целочисленные (или дискретные) значения. Несмотря на ин­тенсивные исследования, проводимые на протяжении последних десятилетий, из­вестные вычислительные методы решения задач ЦЛП далеки от совершенства. На сегодня не существует надежных вычислительных алгоритмов решения таких задач.

В настоящей главе рассматриваются сначала примеры задач целочисленного программирования, а затем методы их решения.

9.1. ПРИМЕРЫ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Рассмотрим сначала простые практические задачи, которые сводятся к задачам ЦЛП, затем обратимся к более сложным. Для удобства задачи, в которых все пере­менные должны быть целочисленными, называются полностью целочисленными, а задачи, в которых лишь некоторые переменные должны принимать целочисленные значения, — частично-целочисленными.

Пример 9.1.1. Распределение капиталовложений

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

Проект		Расходы (млн. долл./год)		Прибыль
1 -й год	2-й год	3-й год	(млн. долл.)

Доступный капитал 25 25 25

(млн. долл.)

Глава 9. Целочисленное линейное программирование

Предполагается, что каждый утвержденный проект Ьудет реализован за трехлет­ний период. Необходимо определить совокупность проектов, которой соответствует максимум суммарной прибыли.

Задача сводится к решению типа "да-нет" относительно каждого проекта. Опреде­лим двоичные переменные хг.

fl, если проект j утвержден,

[О, если проект у не утвержден. Задача ЦЛП будет записана следующим образом.

Максимизировать г = 20л:, + 40ж₂ + 20ж₃ + 15ж₄ + 30ж₅ при ограничениях

5ж, + 4ж₂ + Зх₃ + 7x_t + 8*₅ < 25,

ж, + 7х₂ + 9ж₃ + 4ж₄ + 6ж₅ < 25,

8ж, + 10ж₂ + 2х₃ + x_t + 10*₅ < 25,

ж,, х₂, х₃, ж₄, ж₅ = 0 или 1.

Оптимальным целочисленным решением (полученным с помощью программы TORA¹) является ж, = х₂ = х₃ = ж₄ = 1, x_s = 0 с z = 95 млн. долл. Это решение означа­ет, что необходимо выбрать для финансирования все проекты, кроме пятого.

Интересно сравнить решение данной задачи ЦЛП с решением "обычной" задачи ЛП с теми же ограничениями, но без условия целочисленности переменных. За­дача линейного программирования получается в результате замены условия *. = О или 1 на ограничение 0<*_;< 1 для всех у. Эта задача имеет решение ж, = 0,5789, х₂ = х₃ = х₍ = 1, *₅ = 0,7368 и 2 =108,68 млн. долл. Такое решение с точки зрения целочисленной задачи лишено смысла, так как две переменные принимают дроб­ное значение. Можно было бы попытаться округлить полученный результат, что привело бы к ж, = *₅ = 1. Полученное при этом решение является недопустимым, так как нарушаются ограничения задачи. Более существенным в этой ситуации является то, что округление применять нельзя, так как х_} представляет решение типа "да-нет", для которого дробные значения лишены смысла.

УПРАЖНЕНИЯ 9.1.1²

1. В модели распределения капиталовложений из примера 9.1.1 предположим, что проект 5 должен быть обязательно выбран, если выбирается либо проект 1, либо 3. Измените математическую модель, включив в нее новое ограниче­ние, и решите полученную задачу с помощью программы TORA.

2. Рассмотрите задачу о загрузке самолета грузами пяти типов. Вес и»,, объем и,, а также стоимость г, единицы груза каждого типа приведены в следую­щей таблице.

¹ Для решения задач ЦЛП в программе TORA из основного меню выберите команду Inte­ger Programming (Целочисленное программирование). После ввода исходных данных (файл Ch9ToraCapitalBudgetEx9-l-l.txt) перейдите в выходное окно и для получения оптимально­го решения выберите Automated В&В (Автоматические вычисления методом ветвей и границ).

² Задачи 3-6 в адаптированном виде заимствованы из книги Malba Tahan. El Hombre Que Calculaba, Editorial Limusa, Mexico City, 1994, pp. 39-182.

9.1. Примеры задач целочисленного программирования

Груз /' Вес единицы груза, Объем единицы груза, Стоимость единицы груза,

iv, (тонны) V/(куб. ярд) Г/ (100 долл.)

15 1 4

2 8 8 7

3 3 6 6

4 2 5 5

5 7 4 4

Максимальная грузоподъемность и объем самолета равны 112 тонн и 109 куб. ярдов соответственно. Сформулируйте в виде модели ЦЛП задачу определе­ния набора грузов, обеспечивающего максимальную стоимость груза, и найдите решение с помощью программы TORA.

3. Пусть есть 7 полных бутылок вина, 7 бутылок, заполненных наполовину, и 7 пустых бутылок. Необходимо распределить 21 бутылку между тремя пер­сонами так, чтобы каждый получил 7 бутылок. В то же время каждый дол­жен получить одинаковое количество вина. Сформулируйте эту задачу в виде задачи ЦЛП с ограничениями в виде равенств и найдите решение, используя программу TORA. (Совет. Используйте фиктивную целевую функцию, все коэффициенты которой равны нулю.)

4. Эксцентричный шейх оставил завещание относительно распределения ста­да верблюдов между тремя детьми: Тарик получает не менее половины ста­да, Шариф - не менее одной трети, а Маиса — по меньшей мере одну девя­тую часть. Остаток завещался благотворительной организации. В завещании не упоминался размер стада, говорилось лишь, что количест­во верблюдов — число нечетное и благотворительная организация получа­ет в точности одного верблюда. Сколько верблюдов оставил шейх и сколько получил каждый из его детей?

5. Супружеская пара фермеров посылает трех своих сыновей на базар продать 90 яблок, чтобы обучить их числам и обращению с деньгами. Самый старший Джим получил для продажи 50 яблок, Билл (средний) — 30 и самый млад­ший Джон— лишь 10. Родители поставили пять условий. 1. Цена яблок должна быть равна либо 1 долл. за 7 яблок, либо 3 долл. за 1 яблоко. 2. Каж­дый ребенок может использовать один или оба варианта цен. 3. Все дети должны вернуться с одинаковой суммой денег. 4. Каждый ребенок приносит домой сумму, которая является четным числом (без центов). 5. Сумма денег, полученная каждым из детей, должна быть максимальной при сформулиро­ванных условиях. Считается, что дети могут продать все яблоки, которые они имеют. Как дети могут выполнить требования своих родителей?

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

Глава 9. Целочисленное линейное программирование

рос решил осуществить такой же план и, повторив деление на три части ос­тавшейся суммы, присвоил себе еще и монету, которая осталась после де­ления. На третью ночь третий матрос взял третью часть того, что осталось, и одну дополнительную монету, которая осталась после деления. Когда ко­рабль достиг берега, старший помощник капитана разделил остаток денег поровну между тремя матросами и снова осталась одна монета. Старший помощник отложил эту монету в сторону и вручил матросам предназначен­ные им равные части. Сколько денег было в самом начале? Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение, используя про­грамму TORA. (Совет. Задача имеет бесконечно много целочисленных ре­шений. Предположите для удобства, что следует определить минимальную сумму денег, которая удовлетворяет условиям задачи. Увеличивая затем полученное решение на 1, рассмотрите его как нижнюю границу и получи­те новое минимальное решение. Продолжая таким образом, можно най­ти формулу для общего решения.)

7. Имеются следующие слова, состоящие из трех букв: AFT, FAR, TVA, ADV, JOE, FIN, OSF и KEN. Предположим, что буквам алфавита приписаны числа (метки), начиная с А = 1 и заканчивая Z = 26. Каждое слово помечается чис­лом, равным сумме числовых меток составляющих его трех букв. Например, слово AFT имеет метку 1 + 6 + 20 = 27. Необходимо выбрать пять из задан­ных восьми слов таким образом, чтобы получить максимальную суммарную метку. Вместе с тем выбранные пять слов должны удовлетворять следующе­му условию: (сумма меток первых букв) < (сумма меток вторых букв) < (сумма меток третьих букв).

Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное реше­ние, используя программу TORA.

8. Фирма, специализирующаяся на грамзаписи песен, заключила договор с вос­ходящей звездой эстрады на запись восьми песен. Продолжительность песен равна 8, 3, 5, 5, 9, 6, 7 и 12 минут соответственно. Фирма планирует исполь­зовать для записи двусторонние кассеты. Каждая сторона имеет длитель­ность звучания 30 минут. Фирма намерена распределить песни на две сторо­ны кассеты сбалансированным образом. Это значит, что продолжительность звучания песен на каждой стороне кассеты должна быть примерно одинако­вой (насколько это возможно). Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение.

9. Рассмотрите задачу из предыдущего упражнения, предположив, что харак­тер мелодий песен диктует условия, согласно которым третья и четвертая песни не могут быть записаны на одной стороне кассеты. Сформулируйте за­дачу в виде задачи ЦЛП. Возможно ли использование 25-минутной (для ка­ждой стороны) кассеты для записи 8 песен? Если нет, используйте модель ЦЛП, чтобы определить минимальную емкость кассеты для записи.

9.1. Примеры задач целочисленного программирования

Пример 9.1.2. Задача с постоянными затратами

Три телефонные компании предложили мне подписаться на их услуги по дальней связи в пределах Соединенных Штатов. Услуги компании MaBell стоят 16 долл. в месяц плюс 0,25 долл. за каждую минуту связи. Компания PaBell оценивает свои услуги в 25 долл. в месяц, но имеет поминутную оплату в 0,21 долл. Что касается компании BabyBell, месячная плата равна 18 долл., а стоимость минуты связи — 0,22 долл. Мои телефонные звонки на дальние расстояния в среднем составляют обычно 200 минут в месяц. Предполагается, что я не вношу помесячной платы, ес­ли не использую телефон для звонков на дальние расстояния, и что я могу распре­делять звонки между тремя компаниями, как мне хочется. Как я должен использо­вать три компании, чтобы минимизировать свой месячный телефонный счет?

Эта задача может быть легко решена без использования методов ЦЛП. Тем не менее поучительно сформулировать ее как целочисленную задачу.

Пусть

— количество минут разговора (на дальние расстояния) в месяц через компа­нию MaBell,

х₂— количество минут разговора в месяц через компанию PaBell, х₃— количество минут разговора в месяц через компанию BabyBell, (/, = 1, если х_х > 0, и у, = 0 при x, = 0, у₂ = 1, если х_г > 0, и у₂ = 0 при х₂ = 0, у₃ = 1, если х₃ > 0, и у₃ = 0 при х₃ = 0.

Для обеспечения равенства г/ = 1 при положительном значении переменной x_t ис­пользуем ограничение х <My_jt j — 1, 2, 3, где М— достаточно большое число, ко­торое не должно ограничивать величину х. Так как звонки на дальние расстояния занимают около 200 минут в месяц, т.е. x_t < 200 для всех j, поэтому достаточно по­ложить М= 200.

Теперь можно сформулировать следующую задачу.

Минимизировать г = 0,25л:, + 0,21д:₂ + 0,22л:з + 16у, + 2Ьу₂ + 18у₃ при ограничениях

*, + х₂ + х₃ = 200, ж, S200y„ *,<200у„ х₃<200у₃,

2/i> у 2' г/₃ ^{= 0или} 1-

Формулировка задачи показывает, что помесячная у-я оплата за пользование теле­фоном является частью целевой функции г лишь при условии У,= 1, которое по оп­ределению может выполняться лишь тогда, когда х_} > 0. Если в оптимальном ре­шении будет Xj = 0, то минимума функции z (с учетом положительности коэффициента при у) можно достичь только при равенстве нулю y_jt что и требуется.

Оптимальным решением данной задачи (получено с помощью TORA, файл Ch9ToraFixedChargeEx9-l-2.txt) является х₃ = 200, у₃ = 1, все остальные перемен­ные равны нулю. Это значит, что копания BabyBell должна быть выбрана для

Глава 9. Целочисленное линейное программирование

услуг по дальней связи. Следует подчеркнуть, что информация, которую несет значение переменной j/₃ = 1, является избыточной, так как такой же результат следует из х_г > 0 (= 200). В самом деле, основной причиной использования пере­менных «/,, у₂ и у₃ является лишь учет месячной платы за телефон. В сущности, только эти двоичные переменные преобразуют исходную нелинейную задачу в частично-целочисленную, поддающуюся аналитическому решению.

Изложенная концепция "твердого гонорара" является типичной для задачи, известной в литературе как задача с постоянными затратами.

УПРАЖНЕНИЯ 9.1.2

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

Станок	Расходы на переналадку	Затрать! на производство единицы продукции	Производительность (в единицах продукции)

Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное реше­ние, используя программу TORA.

2. Нефтедобывающая компания изучает вопрос о бурении четырех нефтяных скважин на двух нефтеносных участках. Издержки подготовки к бурению на каждом участке и затраты на бурение скважины; на участке i (i=l, 2; j=l, 2, 3, 4) приведены в следующей таблице.

	Затраты на бурение скважины (млн. долл.)	Издержки подготовки
Участок	12 3 4	к бурению (млн. долл.)
	2 18 5
	4 6 3 1

Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное реше­ние, используя программу TORA.

3. Рассматриваются три промышленных участка для размещения обрабаты­вающих заводов, которые снабжают своей продукцией трех потребителей. Данные об объемах производства продукции, объемах потребления и себе­стоимости (в долл.) перевозки продукции от заводов к потребителям содер­жатся в следующей таблице.

1 2 3 Объем производства

Спрос 1200 1700 1600

9.1. Примеры задач целочисленного программирования

В дополнение к транспортным, существуют еще фиксированные затраты в объеме 10 ООО, 15 ООО и 12 ООО долл., связанные с 1, 2 и 3 заводом соответственно. Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, ис­пользуя программу TORA.

4. Повторите упражнение 3, предполагая, что спрос потребителей 2 и 3 умень­шился до 800 единиц.

Пример 9.1.3. Задача о покрытии

Для обеспечения безопасности студентов отдел безопасности американского уни­верситета устанавливает телефоны экстренного вызова на территории студенческо­го городка. Отделу желательно установить минимальное количество телефонов та­ким образом, чтобы на каждой из основных улиц этого городка был расположен по крайней мере один телефон. На рис. 9.1 представлены основные улицы (от А до К) студенческого городка.

Q

Улица А

а Я К

S

Улица В

®

Улица Е

ев Я Я

Улица С

ев Я К

Улица D

©

Рис. 9.1. Схема улиц студенческого городка

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

Определим, что переменная х_} равна 1, если телефон расположен на перекрестке / (j =1,2, 8), и 0 в противном случае.

Условия задачи требуют установки по меньшей мере одного телефона на каждой из 11 улиц (от А до К). Поэтому задачу можно сформулировать следующим образом.

Минимизировать г = х_г + х₂ + х₃ + x_t + x_s + х₆ + х₇ + x_s

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

Глава 9. Целочисленное линейное программирование

х_х + х₂ > 1 (улица А),

х₂ + х₃ > 1 (улица В),

x_t + х_& > 1 (улица С),

х₇ + х_е>1 (улица D),

х₆ + х₇ > 1 (улица £),

ж₂ + ж₆ > 1 (улица Р),

х_г + х_е > 1 (улица G),

ж₄ + ж₇ > 1 (улица Я),

х₂ + x_t > 1 (улица /),

ж₅ + ж₈ > 1 (улица J),

х₃ + х_& > 1 (улица К),

x_t = 0 или 1,= 1, 2,8.

В соответствии с оптимальным решением задачи (полученным с помощью про­граммы TORA, файл Ch9ToraSetCoverEx9-l-3.txt) необходимо установить телефо­ны на перекрестках 1, 2, 5 и 7.

Рассмотренная выше модель является типичным представителем общего класса задач, именуемых задачами о покрытии. В этой модели все переменные являются двоичными. Все коэффициенты левой части каждого ограничения равны 0 или 1, а правая часть ограничений имеет вид ">1". Целевая функция всегда имеет вид с₁х₁ + с_гх₂ +...+с_пх_п, где С;>0 для всех j = 1, 2 п, и подлежит минимизации. В рассмотренном примере с_; = 1 для всех Однако если величина с_; будет равна стоимости установки телефона на;'-м перекрестке, то эти коэффициенты могут принимать значения, отличные от 1.

УПРАЖНЕНИЯ 9.1.3

1. Компания ABC занимается доставкой грузов пяти потребителям. Можно вы­брать следующие маршруты перевозки грузов.

Маршрут	Потребители
	1, 2, 3, 4
	4, 3, 5
	1, 2, 5
	2, 3, 5
	1, 4, 2
	1, 3, 5

Эти маршруты определяются грузоподъемностью автомобиля, доставляюще­го грузы. Например, на маршруте 1 автомобиль имеет грузоподъемность, достаточную для доставки грузов лишь потребителям 1, 2, 3 и 4. Следующая таблица содержит расстояния (в милях) между терминалом компании ABC и потребителями.

9.1. Примеры задач целочисленного программирования

	ABC
ABC

Необходимо выполнить дневные поставки пяти потребителям, минимизируя при этом пройденный суммарный путь. Оптимальное решение может быть таким, что один и тот же потребитель обслуживается более чем одним мар­шрутом. Но при реализации такого решения используется только один из этих маршрутов. Сформулируйте задачу в виде задачи ЦЛП и найдите опти­мальное решение, используя программу TORA.