Задачи ЦЛП

1. Рассмотрите задачу о загрузке самолетов грузами пяти типов. Вес w_i , объем v_i, а также стоимость r_i единицы груза каждого типа приведены в таблице.

Груз i	Вес единицы груза, wi (тонны)	Объем единицы груза, vi (куб. ярд)	Стоимость единицы груза, ri (100 долл.)
1	5	1	4
2	8	8	7
3	3	6	6
4	2	5	5
5	7	4	4

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

2. Шейх оставил завещание относительно распределения стада верблюдов между тремя детьми: Тарик получает не менее 1/2 стада, Шариф не менее 1/3, а Майса по меньшей мере 1/9 часть. Остаток завещался благотворительной организации. В завещании не упоминался размер стада, говорилось лишь, что количество верблюдов – число нечетное и благотворительная организация получает в точности одного верблюда. Сколько верблюдов оставил шейх и сколько получил каждый из его детей?

3. Супружеская пара фермеров посылает трех своих сыновей на базар продать 90 яблок, чтобы обучить их числам и обращению с деньгами. Самый старший Джим получил для продажи 50 яблок, Билл средний – 30 и самый младший Джон – 10. Родители поставили пять условий:

1. Цена яблок должна быть равна либо 1 долл. за 7 яблок, либо 3 долл. за 1 яблоко.

2. Каждый ребенок может использовать один или оба варианта цен.

3. Все дети должны вернуться с одинаковой суммой денег.

4. Каждый ребенок приносит домой сумму, которая является четным числом (без центов).

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

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

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

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

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

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

8. Задача инвестирования. Управляющему инвестиционным портфелем поручено распорядиться суммой $100 000. Выбор осуществляется из списка, в котором перечислено 20 видов ценных бумаг. Известно, что чистый доход от вложения $1 в акции i составляет r_i, тогда при вложении х_i, долларов в акции i в конце периода будет получена сумма

(1+ r_i)x_i,. Чтобы обеспечить сбалансированность инвестиционного портфеля, менеджер использует следующие (основанные на здравом смысле) правила.

А) не инвестировать более $20000 в один вид ценных бумаг

Б) если определенные акции покупаются, сумма покупки составляет не менее $5000.

9. Перед менеджером стоит задача максимизировать доход при условии соблюдения указанных правил. Сформулируйте данную задачу в виде модели частично целочисленного ЛП. Составление расписания полетов. Авиакомпания Alpha Airline хочет составить расписание полетов так, чтобы в нем было не более одного вылета из Чикаго в каждый из следующих городов: Колумбус, Денвер, Лос-Анджелес и Нью-Йорк. Возможное время вылетов 8-00, 10-00 и 12-00. Компания арендует самолеты, стоимость аренды составляет $5000, если вылет состоится до 10-00 включительно, и $3000 после 10-00. Допускается арендовать не более двух самолетов на одно время вылета. Кроме того, если в определенное время осуществляется вылет в Нью-Йорк, в это же время должен производиться вылет в Лос-Анджелес. Ожидаемая удельная прибыль до внесения арендной платы в тысячах долларов в расчете на один полет представлена в таблице. Сформулируйте и решите задачу, которая позволит составить расписание, дающее максимальную прибыль

	Время вылета
	8-00	10-00	12-00
Колумбус	10	6	6
Денвер	9	10	9
Лос-Анджелес	14	11	10
Нью-Йорк	18	15	10

10. Коммунальное предприятие, занимающееся энергоснабжением, ежедневно вынуждено решать, какие электрогенераторы запускать в работу. Рассматриваемое предприятие имеет в своем распоряжении три генератора, характеристики которых представлены в таблице. День можно условно разделить на два периода: в первый период потребность в энергии составляет 2900 МВт, а во второй период — 3900 МВт. Генератор, запущенный в первый период, можно использовать во втором периоде без дополнительных затрат на запуск. Все генераторы в конце каждого дня выключаются. Сформулируйте задачу в виде модели часточно-целочисленного ЛП и решите ее.

Генератор	Фиксированные затраты на запуск, $	Затраты на 1 МВт,$	Максимальная мощность за период, МВт
А	3000	5	2100
В	2000	4	1800
С	1000	7	3000

11. Производственное планирование. Некая технологическая линия используется для выпуска двух видов продукции. Соответствующие данные приводятся в таблице 1. Общий ресурс времени (для производства и переналадки) составляет 80 ч в неделю. В начале недели 1 и в конце недели 4 запасы продукции равны нулю. Стоимость хранения единицы запаса при переходе от одной недели к следующей составляет $4 для обоих видов продукции. Единица неудовлетворенного спроса оценивается в $10 для продукции А и в $15 для продукции В. Данные о спросе представлены в таблице 2. В конце каждой недели конвейер останавливается для профилактического осмотра и наладки. В течение недели может производиться только один вид продукции. Сформулируйте и решите задачу планирования на 4-недельный период как модель частично-целочисленного ЛП. Цель — максимизировать прибыль за период в 4 недели.

Таблица 1

Данные о продукции

	Продукция
	А	В
Время запуска конвейера, ч	5	10
Время производства единицы продукции, ч	0,5	0,75
Затраты на настройку конвейера	200	400
Удельные затраты на производство единицы продукции, $	10	15
Цена продажи, $	20	30

Таблица 2

Данные о спросе

	Неделя
	1	2	3	4
А	80	100	75	80
В	15	20	50	30

12. Совет директоров крупного производственного предприятия рассматривает ряд инвестиционных предложений, представленных в следующей таблице. Обозначим через R, суммарный доход от инвестиционного проекта i, а через С, затраты на этот проект. Совет директоров хочет максимизировать суммарный доход, при этом общий объем инвестиций не должен превышать М долларов. Сформулируйте данную задачу как модель ЦЛП. Дайте определение переменных решения и запишите уравнения модели.

Инвестиционный проект	Условия
1	Отсутствуют
2	Можно, если принят проект 1
3	Можно, если принят проект 2
4	Должен быть принят, если приняты проекты 1 и 2
5	Нет, если принят проект 1 или 2
6	Нет, если приняты проекты 2 или 3
7	Можно, если принят проект 2 и не принят проект 3

13. Компания-дистрибьютор хочет минимизировать затраты на транспортировку товаров с принадлежащих ей складов А, В и С в торговые точки 1, 2 и 3. Затраты на транспортировку единицы продукции со складов в торговые точки представлены в таблице.

	Торговые точки
Склад	1	2	3
А	15	32	21
В	9	7	6
С	11	18	5
Спрос	200	150	175

Фиксированные затраты на открытие склада составляют $500 для склада А, $750 для склада В и $600 для склада С, причем компании необходимо открыть не менее двух складов. Предполагается, что склады имеют неограниченный объем. Сформулируйте и решите задачу ЦЛП, которая позволит определить, какие склады следует открыть, и сколько продукции будет доставлено с каждого склада в каждую торговую точку.

14. Некая работа состоит из пяти операций А, В, С, D и Е, каждая из которых может выполняться любым из двух станков (станок 1 или 2). Время, необходимое для выполнения каждой операции на каждом станке, приводится в таблице.

	А	В	С	D	E
Станок 1	5	9	2	3	4
Станок 2	3	4	7	5	4

Сформулируйте и решите задачу ЦЛП, которая позволит распределить операции по станкам так, чтобы минимизировать величину Мах(Т1, Т2), где Tl — суммарное время работы станка 1, а Т2 — суммарное время работы станка 2.

15. Рассмотрим модель размещения складов компании STECO на рис. 6.8. При заданном оптимальном решении об аренде складов А, В и С запишите в математической форме транспортную модель, позволяющую оптимально распределить грузовики.

16. Городской совет пришел к выводу, что для нужд города необходимо открыть пожарные станции или в пунктахА, В и С или в А, Си D, либо в пунктах В, С и D. Затраты на открытие пожарной станции (в млн. долл.) составляют: в пункте А — 1,5, в В — 2,3, в С — 1,8 и в D — 2,1. Сформулируйте и решите задачу ЦЛП, которая позволит городскому совету определить, какие пожарные станции открыть, чтобы обслуживать город с минимальными затратами.

17. Коммунальное предприятие электроснабжения планирует расширение мощностей по производству электроэнергии на протяжении следующих пяти лет. В настоящее время генерирующая способность составляет 800 МВт, но, как следует из прогнозов спроса, предприятию потребуются дополнительные мощности (см. табл.).

Год	Минимальная необходима мощность, МВт
1	880
2	960
3	1050
4	1160
5	1280

Предприятие может повысить генерирующую способность путем установки дополнительных генераторов на 10, 50 и 100 МВт. Затраты на установку одного генератора зависят от его мощности и года подключения (см. табл.).

Мощность генератора, МВт	Год
	1	2	3	4	5
10	300	250	208	173	145
50	670	558	465	387	322
100	950	791	659	549	458

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

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

Р1 1	Р2 2	Р3 3
Р4 4	Р5 5	Р6 6

Так, на приведенной карте округа 1 и 2 являются соседними, а округа 1 и 5 — нет. Компания стремится сделать так, чтобы суммарное население в округах с назначенными представителями было максимальным. Пример допустимого решения: выбрать базовым округ 4 с соседним округом 1, а также сделать базовым округ 3 с соседним 2. Значение целевой функции для такого решения равно Р, + Р, + Р, + Р

Введем следующие переменные: В_J = 1, если округ выбран в качестве базового, и В_J =0 в противном случае (j = 1, ..., 6); Аij= 1, если округ i выбран в качестве соседнего для базового округа j, и Аij= 0 в противном случае (j = 1, ..., 6; округи i и j — соседние). Таким образом, заданы переменные решения В_1,В₂,В₃,В₄,В₅,В₆,А₂₁, А₄₁, А₁₂, А₅₂, А₃₂, А₂₃, А₆₃ и т.д.

1. В модели не должно быть двойного счета (т.е. в одном варианте назначения один и тот же округ не должен одновременно выступать в качестве базового и соседнего). Запишите ограничение, которое сделает невозможным двойной счет для округа 1.

2. Запишите ограничение: "если торговый представитель назначается в базовый округ 2, то этот же торговый представитель должен быть назначен в один из соседних округов".

3. Запишите ограничение: "если один из двух округов, соседних с округом 1, выбран в качестве соседнего округа (к округу 1), то округ 1 должен использоваться в качестве базового".

4. Верно ли утверждение, что данную модель можно описать с помощью ограничений в виде 12 неравенств и 1 равенства?

5. Верно ли утверждение, что данную модель можно описать с помощью ограничений в виде 7 неравенств и 6 равенств?

19. Прочитайте описание ситуации перед вопросом 21 в разделе "Контрольные вопросы". Предположим, что в дополнение к указанным там условиям с каждой отправкой груза от поставщика связаны фиксированные затраты R. Тогда если поставщик производит 4 отгрузки (непосредственно в торговые точки 3, 5 и 8 и на склад), то это влечет за собой дополнительные затраты в сумме 4R. Сформулируйте задачу частично-целочисленного ЛП.

20. Компания Bradford Electronics производит разнообразные DVD-дисководы, которые устанавливаются в домашние цифровые видеоплейеры. У компании пять сборочных заводов, где она может собирать DVD-дисководы. Некоторые заводы более автоматизированы, поэтому на них переменные затраты на сборку ниже, однако выше единовременные затраты переналадки при переходе к выпуску определенной модели DVD-дисковода. Компания получила заказ на сборку 2500 DVD-дисководов определенной модели. На основании приведенных в таблице данных о единовременных затратах на переналадку и переменных затратах на сборку на каждом из пяти сборочных заводов определите, сколько DVD- дисководов следует собрать на каждом заводе, чтобы минимизировать суммарные затраты.

Сборочный завод	Удельные затраты на сборку,$	Производственная мощность	Затраты на переналадку, $
1	62	500	12000
2	68	600	6000
3	72	700	3000
4	78	450	1500
5	85	1000	500

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

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

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

	АВС	1	2	3	4	5
АВС	0	10	12	16	9	8
1	10	0	32	8	17	10
2	12	32	0	14	21	20
3	16	8	14	0	15	18
4	9	17	21	15	0	11
5	8	10	20	18	11	0