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

Лабораторная работа №1:
Целочисленное линейное программирование



1. Общая постановка задачи ЦЛП
Если управляющие переменные в ЗЛП определяют количество неделимой продукции, то оптимальное решение должно быть получено в целых числах. Такие ЗЛП называют задачами ЦЛП.
Математическая модель задачи ЦЛП имеет следующий вид:

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



2. Распределение капиталовложений
Оценивается четыре проекта с точки зрения их возможного финансирования на пред-стоящий трехлетний период. Следующая таблица содержит ожидаемую прибыль от реализации каждого проекта и распределение необходимых капиталовложений по годам.
Проект Расходы (млн. долл./год) Прибыль
(млн. долл.)
1-й год 2-ой год 3-й год
1 5 7 3 25
2 3 2 8 24
3 12 6 5 30
4 4 10 9 30
Доступный капитал (млн. долл.) 20 20 20
Предполагается, что каждый утвержденный проект будет реализован за трехлетний период. Не-обходимо определить совокупность проектов, которой соответствует максимум суммарной прибыли.

Решение. Задача сводится к решению типа «да – нет» относительно каждого проекта. Определим двоичные переменные :

Задача ЦЛП будет записана следующим образом.
Максимизировать
при ограничениях

Оптимальным целочисленным решением (полученным с помощью Поиска решений в Excel) является с млн. долл. Это решение означает, что необходимо выбрать для финансирования все проекты, кроме третьего.



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

Решение. Пусть
– количество минут разговора (на дальние расстояния) в месяц через компанию MaBell,
– количество минут разговора в месяц через компанию PaBell,
– количество минут разговора в месяц через компанию BabyBell,

Переменные вводятся лишь для учета месячной платы за телефон. Для обеспечения равенства при используем ограничение , где – достаточное большое число, которое не должно ограничивать величину . Так как звонки на дальние расстояния занимают около 200 минут в месяц, т.е. для всех , поэтому достаточно положить .
Теперь можно сформулировать задачу.
Минимизировать
при ограничениях

Формулировка задачи показывает, что помесячная -ая оплата за пользование телефоном явля-ется частью целевой функции лишь при условии , которое по определению может вы-полняться лишь тогда, когда . Если в оптимальном решении будет , то минимума функции (с учетом положительности коэффициента при ) можно достичь только при ра-венстве нулю , что и требуется.
Оптимальным решением данной задачи (получено с помощью Поиска решений в Excel) является , все остальные переменные равны нулю. Это означает, что компания BabyBell должна быть выбрана для услуг по дальней связи.



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


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

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

В соответствии с оптимальным решением (полученным с помощью Поиска решений в Excel) необходимо установить телефоны на перекрестках 1, 2, 5 и 7.



5. Задача с ограничениями типа «или – или»
Машиностроительная компания использует один станок для выполнения трех заказов. Время выполнения, а также срок сдачи каждого заказа даны в таблице. Сроки сдачи заказов вы-числяются от начальной даты, т.е. предполагаемого начала выполнения первого заказа.
Заказ Время выполнения
заказа (дни) Срок сдачи
заказа (дни) Штраф за задержку
заказа (долл./день)
1 5 25 19
2 20 22 12
3 15 35 34
Требуется определить последовательность выполнения заказов, которая минимизирует штраф за задержку сдачи заказов.

Решение. Пусть
– начало выполнения заказа , ,
– время выполнения заказа ,
– срок сдачи заказа ,
– количество дней между концом выполнения и сроком сдачи заказа . Если , то заказ сдается в срок, если же , получаем убытки, связанные с задержкой сдачи заказа.
Задача имеет два типа ограничений: 1) ограничения, которые гарантируют, что никакие два заказа не выполняются одновременно; 2) ограничения по срокам сдачи заказов. Сначала рассмотрим первый тип ограничений.
Два заказа и не будут выполняться одновременно, если

в зависимости от того, будет ли заказ предшествовать выполнению заказа или наоборот. Поскольку все математические модели имеют дело лишь с совместными ограничениями, мы преобразуем ограничения типа «или – или», введя дополнительную двоичную переменную

При достаточно большом ограничение типа «или – или» преобразуется в следующие два совместных ограничения:

Указанное преобразование гарантирует, что лишь одно из двух ограничений может быть актив-ным в любой момент времени. Если , первое ограничение является активным, а второе – избыточным (так как его левая часть будет содержать величину , которая намного больше ). Если , первое ограничение является избыточным, а второе – активным.
Введем теперь ограничения по срокам сдачи заказов:

Используя стандартную замену приводим ограничения к виду

Штраф за задержку сдачи заказа пропорционален .
Математическая модель задачи принимает вид.
Минимизировать
при ограничениях

Для решения задачи выберем – число, которое больше суммы времени изготов-ления всех трех заказов.
Оптимальным решением (полученным с помощью Поиска решений в Excel) является . Следовательно, оптимальной последовательностью выполнения заказов будет . В соответствии с оптимальным решением заказ 2 выполняется за время 0+20=20, заказ 1 – за время 20+5=25 и заказ 3 – за 25+15=40 дней. В результате сдача заказа 3 задерживается на 40-35=5 дней, что приводит к штрафу в размере 5*34=170 долл.



6. Задачи для самостоятельного решения
Сформулируйте каждую задачу в виде задачи ЦЛП и найдите оптимальное решение с помощью Поиска решений в Excel.

вариант задачи
1 1, 8
2 2, 9
3 3, 10
4 4, 14
5 5, 15
6 6, 16
7 7, 17
8 8, 11
9 9, 12
10 10, 13

1. Оценивается пять проектов с точки зрения их возможного финансирования на пред-стоящий трехлетний период. Следующая таблица содержит ожидаемую прибыль от реализации каждого проекта и распределение необходимых капиталовложений по годам.
Проект Расходы (млн. долл./год) Прибыль
(млн. долл.)
1-й год 2-ой год 3-й год
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
Доступный капитал (млн. долл.) 25 25 25
Проект 5 должен быть обязательно выбран, если выбирается либо проект 1, либо 3. Предполага-ется, что каждый утвержденный проект будет реализован за трехлетний период. Необходимо определить совокупность проектов, которой соответствует максимум суммарной прибыли.

2. Пусть есть 7 полных бутылок вина, 7 бутылок, заполненных наполовину, и 7 пустых бутылок. Необходимо распределить 21 бутылку между тремя персонами так, чтобы каждый по-лучил 7 бутылок. В то же время каждый должен получить одинаковое количество вина. (Совет: используйте фиктивную целевую функцию, все коэффициенты которой равны 0.)

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

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

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

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

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

8. Нефтедобывающая компания решает вопрос о бурении четырех нефтяных скважин на двух нефтеносных участках. Издержки подготовки к бурению на каждом участке и затраты на бурение скважины на участке ( ) приведены в следующей таблице.
Участок Затраты на бурение скважины
(млн. долл.) Издержки подготовки
к бурению (млн. долл.)
1 2 3 4
1 2 1 8 5 5
2 4 6 3 1 6

9. Рассматриваются три промышленных участка для размещения обрабатывающих заво-дов, которые снабжают своей продукцией трех потребителей. Объемы производства продук-ции, объемы потребления и себестоимость перевозки продукции от заводов к потребителям содержатся в следующей таблице.
1 2 3 Объем производства
1 $10 $15 $12 1800
2 $17 $14 $20 1400
3 $15 $10 $11 1300
Спрос 1200 1700 1600
В дополнение к транспортным, имеются еще фиксированные затраты в объеме 10 000, 15 000 и 12 000 долларов, связанные с 1, 2 и 3 заводом соответственно.

10. Компания планирует производство некоторой продукции на трех станках, которой должно быть изготовлено не менее 1500 единиц. Следующая таблица содержит необходимую информацию для рассматриваемой задачи.
Станок Расходы
на переналадку Затраты на производство
единицы продукции Производительность
(в единицах продукции)
1 300 2 600
2 100 10 800
3 200 5 1200

11. Американский университет формирует комитет по рассмотрению жалоб студентов. В соответствии с указаниями, полученными из администрации, в эту комиссию необходимо включить, по крайней мере, одну женщину, одного мужчину, одного студента, одного администратора и одного преподавателя. Выдвинуты десять кандидатур (обозначенных для удобства буквами от а до j). Принадлежность этих кандидатур к различным категориям отражена в следующей таблице.
Категория Кандидатуры
Женщины a, b, c, d, e
Мужчины f, g, h, i, j
Студенты a, b, c, j
Администрато-ры e, f
Преподаватели d, g, h, i
Университет заинтересован создать наименьшую по составу комиссию, гарантирующую представительство каждой из указанных категорий.

12. Округ Вашингтон определил шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некоторых или во всех шести го-родах. Однако в силу территориальной близости некоторых городов одна станция может обслу-живать более одного населенного пункта. Единственным условием является время поездки: оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами. Необходимо определить наименьшее количество станций и их распо-ложение.
1 2 3 4 5 6
1 0 23 14 18 10 32
2 23 0 24 13 22 11
3 14 24 0 60 19 20
4 18 13 60 0 55 17
5 10 22 19 55 0 12
6 32 11 20 17 12 0

13. Сокровища короля Тута находятся в музее в Новом Орлеане. План музея, состоящего из нескольких комнат, соединенных открытыми дверями, показан на рисунке. Сторож, находя-щийся у двери, может наблюдать за двумя смежными комнатами. Администрация музея заинте-ресована, чтобы в каждой комнате присутствовал сторож, но число сторожей должно быть ми-нимальным.


14. Компания владеет фабрикой, которая производит изделия трех типов. Необходимые трудовые затраты и потребности сырья для производства одной единицы каждого из трех изде-лий приведены в таблице.
Тип изделия Необходимое время (час./ед.) Необходимое сырье (фунты/ед.)
1 3 4
2 4 3
3 5 6
Наличный дневной объем 100 100
Доходы от производства единицы каждого из трех типов изделий равны 25, 30 и 45 долл. соот-ветственно. Если будет производиться изделие типа 3, то его ежедневный объем производства должен быть не менее 5 единиц. Компании необходимо организовать выпуск изделий на фабрике.

15. Рассмотрите задачу о загрузке самолета грузами пяти типов. Вес, объем и стоимость единицы груза каждого типа приведены в следующей таблице.
Номер груза Вес единицы груза,
(тонны) Объем единицы груза, (куб. ярд) Стоимость единицы
груза, (тыс. долл.)
1 5 1 4
2 8 8 7
3 3 6 6
4 2 5 5
5 7 4 4
Если берется груз 1, то взять его нужно не менее 15 единиц. Максимальная грузоподъемность и объем самолета равны 112 тонн и 109 куб. ярдов соответственно. Необходимо определить набор грузов, обеспечивающего максимальную стоимость груза.

16. Игральная доска состоит из девяти равных квадратов, расположенных 3x3. Требуется заполнить каждый квадрат числом из интервала от 1 до 9 таким образом, чтобы сумма чисел каждой строки, каждого столбца и каждой диагонали была равна 15. При этом числа в угловых квадратах должны быть различны.

17. Компания планирует производство некоторой продукции на трех станках, которой должно быть изготовлено не менее 2000 единиц. Минимальная производительность любого станка равна 500 единиц. Следующая таблица содержит необходимую информацию для рас-сматриваемой задачи.
Станок Расходы
на переналадку Затраты на производство
единицы продукции Производительность
(в единицах продукции)
1 300 2 600
2 100 10 800
3 200 5 1200