Задачи линейного программирования

ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

План ремонта станков

    Машиностроительный цех делает семь изделий (Р1,…,Р7), используя следующий станочный парк: четыре шлифовальных, два вертикально-сверлильных, три горизонтально-сверлильных, один расточный и один строгальный. Каждое изделие приносит некоторую прибыль (определенную как долл./единица, продажная цена минус стоимость сырья). Эти количества (в долл. на единицу продукции) вместе с количеством времени (часы), требующимся на обработку изделия на каждом станке, даются ниже. Прочерк указывает, что обработки на данном станке не требуется.

	Р1	Р2	Р3	Р4	Р5	Р6	Р7
Прибыль за единицу, $	10	6	8	4	11	9	3
Шлифовка	0,5	0,7	-	-	0,3	0,2	0,5
Вертикальное сверление	0,1	0,2	-	0,3	-	0,6	-
Горизонтальное сверление	0,2	-	0,8	-	-	-	0,6
Растачивание	0,05	0,03	-	0,07	0,1	-	0,08
Строгание	-	-	0,01	-	0,05	-	0,05

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

	1	2	3	4	5	6	7
Январь	500	1000	300	300	800	20	100
Февраль	600	500	200	0	400	300	150
Март	300	600	0	0	500	400	100
Апрель	200	300	400	500	200	0	100
Май	0	100	500	100	1000	300	0
Июнь	500	500	100	300	1100	500	60

    Фабрика работает 6 дней в неделю в две смены по 8 ч каждый день. Примите, что каждый месяц состоит только из 24 рабочих дней.

    Для простоты считайте, что любой порядок обработки изделия на разных станках может быть обеспечен.

a. Когда и чтодолжна делать фабрика, чтобы максимизировать полную прибыль?

b. В текущем месяце (январь) и в пять последующих месяцев некоторые станки будут отключены для обслуживания: январь – 1 шлифовальный; февраль – 2 горизонтально-сверлильных; март – 1 расточный; апрель – 1 вертикально-сверлильный; май – 1 шлифовальный и 1 вертикально-сверлильный; июнь – 1 строгальный и 1 горизонтально-сверлильный. Каков теперь должен быть оптимальный план производства?

c. Возможно хранение 100 шт. каждого изделия одновременно за 0,5 долл. за 1 шт. в месяц. Не имеется никаких запасов в настоящее время, но необходимо иметь запас 50 изделий каждого типа в конце июня. Каков будет оптимальный план производства? Сколько добавочной прибыли удастся извлечь?

d. Вместо спущенного сверху плана остановки каждого станка спланируйте наилучший график остановки станков для обслуживания. Каждый станок должен быть остановлен один раз в полгода (на месяц) для обслуживания, кроме двух шлифовальных станков. Сколько можно заработать на лучшем плане остановки станков в расчете на полгода?

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

 

Бакалейная лавка

Бакалейная лавка продает различные типы орехов. Владельца занимает проблема расфасовки орехов и их смесей. Лавка закупает 4 типа орехов и продает их в пакетах по 1 кг. Кроме того, лавка продает пакеты со смесью орехов, состоящей из 40% арахиса и равных весовых частей остальных орехов.

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

Таблица 1

Пакет	Цена 1 пакета, $	Стоимость 1 кг, $	Имеющееся количество, кг
Смесь «Фирменная»	4,00
Арахис	1,50	1,00	600
Кешью	4,80	3,00	360
Грецкие орехи	4,60	2,50	500
Миндаль	5,00	3,50	400

Каковы теневые цены пакетов с различными продуктами? Что значат эти величины?

«b». Дело происходит в период Рождества. Владелец планирует получить больше прибыли, поэтому не хочет ждать новой поставки товара от своего поставщика и решает закупить 1000 кг орехов у конкурента с соседней улицы. Цены у конкурента такие же, как и у нашего владельца. Как вы думаете, он сумасшедший? Если нет, то, какое количество различных типов орехов вы посоветуете ему закупить?

Сухофрукты.

Магазин, расположенный на окраине большого города, продает сушеные плоды и орехи. Торговля идет бойко, но взвешивание занимает много времени. Из-за жалоб клиентов относительно длинных очередей некий менеджер выдвинул предложение – готовить часть пакетов заранее и размещать их на полках для самообслуживания. Менеджер определил, что около 50% товара распродается в пакетах по 1 фунту, поэтому решил, что 50% текущих поставок должно быть предварительно расфасовано по пакетом весом в 1 фунт, а остальное будет продаваться на развес. Кроме того, из тех же соображений не больше 30% расфасованного товара должны занимать смеси. Предложение было принято для испытания.

В настоящее время в магазине имеются запасы: сушеных бананов – 800 кг, сушеных абрикосов – 600, кокосовых кусочков – 500, изюма – 700, грецких орехов – 900 кг. Цены на товары указаны в таблице:

 

	Закупочные цены, $/кг	Цены продаж, $/кг
Смесь «Попутчик»	–	3,95
Смесь «Метро»	–	4,2
Сушеные бананы	1,35	2,8
Сушеные абрикосы	1,55	3,25
Кокосовые кусочки	1,7	3,6
Изюм	1,7	3,5
Грецкие орехи	2,6	5,5

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

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

a. Определите, что это за план?

b. Выгодно ли продавать все типы орехов и смесей? Если имеется смесь, которая невыгодна, что должно быть изменено, чтобы сделать её продажу выгодной? Исследуйте эти вопросы.

c. Менеджер хочет уговорить руководство пустить в расфасовку дополнительно 200 кг сухофруктов, но не может решить, что выбрать: кокосовые дольки или сушеные абрикосы? Что выгоднее? А может лучше изюм? Как увеличится при этом прибыль? Подтвердите ваши ответы вычислениями.

Сэндвичи Жаннет

Жаннет Гурман продает сэндвичи строителям и заводским рабочим в обеденный перерыв с собственного грузовичка. Её сэндвичи пользуются особой популярностью, поскольку она закупает свежие продукты у местных поставщиков каждое утро. Перечень необходимых для ее бизнеса продуктов приведен в таблице.

Продукт	Стоимость, $
3 шт. 8-фунтовых запеченных грудки индюшек (20 $ каждая)	60
3 шт. 12-фунтовых куска жареной говядины (42 $ каждая)	126
3 шт. 10-фунтовых куска ветчины (30 $ каждая)	90
3 шт. 8-фунтовых головки швейцарского сыра (18 $ каждая)	54
300 шт. булочек для сэндвичей	60
Различные приправы	30

В дополнение к 420 долл., которые она тратит на эти продукты, Жаннет ежедневно расходует в среднем 280 долл. на бензин, обслуживание грузовика, страховку и зарплату помощникам.

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

a. Сколько сэндвичей каждого типа следует готовить, чтобы максимизировать доход? Какова чистая прибыль Жаннет (до уплаты налогов) за год, если она работает 200 дней в году?

b. Жаннет рассматривает возможность закупки еще одного куска какого-нибудь мяса или сыра от тех же поставщиков. Если только один

дополнительный кусок будет закупаться, что именно выгоднее всего закупить Жаннет? Увеличение какого ресурса наиболее выгодно для нее?

c. Насколько чувствительно оптимальное решение к изменению цен за один сэндвич? Как изменится решение при изменении цен на каждый вид продукции?

d. Как изменится решение, если цены на все сэндвичи увеличить на 1, 2, 10 долл.,? Почему?

Тип сэндвича	цена	индейка	говядина	ветчина	сыр
диетический	2,75	4	0	0	1
говядина для мальчиков	3,5	0	4	0	1
ветчина для голодных	3,25	0	0	4	2
клубный	4	2	2	2	2
мясной	4,25	3	3	3	0

 

Компания «Корвет»

Компания «Корвет» производит обеспечение на CD-ROM, которое продаётся в пакете с драйверами CD-ROM основными производителями компьютерного оборудования. Она оценивает возможность развития 6 новых программных приложений. В таблице представлена информация о затратах и ожидаемой чистой приведённой прибыли от продажи приложения (с учётом временной стоимости денег).

Приложение	Ожидаемые затраты на развитие, $	Требуемое число программистов	Ожидаемая чистая приведённая прибыль,$
1	400 000	6	2 000 000
2	1 100 000	18	3 600 000
3	940 000	20	4 000 000
4	760 000	16	3 000 000
5	1 260 000	28	4 400 000
6	1 800 000	34	6 200 000

У «Корвета» 60 программистов. Фирма может выделить 3,5 млн. долл. На развитие новых программных приложений.

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

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

2) приобретение приложения 2 имеет смысл, только если в пакет включено приложение 1. Таким образом, если решено развивать приложение 1, то и приложение 2 должно быть развито. Если же решено приложение 1 не развивать, то приложение 2 развивать не нужно;

3) приложения 3 и 6 эксплуатируют одну и ту же тему. Следовательно, если одно из них развивается, то другое определённо нет;

4) стремясь обеспечить качество продукции, «Корвет» не склонен развивать более 3 программных продуктов.

б. Проанализируйте влияние каждого из 4 ограничений на оптимальное решение.

1.30 Фильм! Фильм! Фильм!!!»

Кинокомпания «Блокбастер» рассматривает возможность производства 10 кинокартин в следующем году. Список включает кинокартины трёх типов: мелодрамы, комедии и боевики. Эксперты студии очень приблизительно оценивают рейтинги сценариев, затраты и ожидаемые кассовые сборы от того или иного потенциального фильма, в зависимости от того, будут ли приглашены для участия в фильме звёзды или нет. Эти данные представлены в таблице.

№ п/п	Фильм	Рейтинг	Тип	Затраты и сборы, млн. $
				без звёзд		со звёздами
				затраты	ожидаемые сборы	затраты	ожидаемые сборы
1	«Обоюдоострый меч»	PG-13	боевик	5	8	10	15
2	«Женщина ждёт»	R	М/драма	12	20	25	35
3	«Все прошло»	PG	М/драма	8	10	12	26
4	«Святая лошадка»	PG	комедия	7	12	15	26
5	«Почему я плачу»	PG-13	М/драма	15	30	30	45
6	«Капитан Кид»	PG	комедия	10	20	17	28
7	«О да»	R	комедия	4	7	8	12
8	«Симпатичная Гритти»	PG	комедия	11	15	14	20
9	«Катастрофа»	R	боевик	20	28	40	65
10	«Разбомбить!»	R	боевик	25	37	50	80

В дополнение к указанным затратам каждый фильм имеет 1 млн. $ бюджета на рекламу, который увеличивается до 3 млн. $, если в фильме участвуют актёры-звёзды. Предполагается, что студия получает 80% кассовых сборов. Компания хотела бы максимизировать чистую прибыль (за вычетом затрат на производство и рекламу) в следующем году.

«Блокбастер» имеет бюджет 100 млн. $ на производство и 15 млн. $ на рекламу. В дополнении к этому руководство компании считает необходимым удовлетворять следующим условиям:

1) по крайней мере, половина произведённых фильмов должна иметь рейтинг PG или PG-13;

2) нужно произвести не менее двух комедий;

3) нужно произвести не менее одной мелодрамы;

4) если решено производить фильм «Катастрофа», то фильм «Разбомбить!» производить не следует;

5) по крайней мере, 2 фильма должны включать актёров-звёзд;

6) нужно произвести, по крайней мере, 2 фильма рейтинга PG;

7) нужно произвести хотя бы один боевик, включающий актёров-звёзд.

А. Подготовьте отчёт для «Блокбастера», который бы рекомендовал, какие фильмы производить и привлекать или не привлекать для них актеров-звёзд. Покажите, как будет использован бюджет компании. Проанализируйте, как изменения бюджета для производства и для рекламы (при сохранении общей суммы 115 млн. $) повлияют на оптимальное решение.

Б. Проанализируйте влияние каждого из семи ограничений, выдвинутых руководством компании, и отметьте, как изменится решение, если сохранить только 6 из 7 ограничений. 5 из 7? 4 из 7 (удаляя условия, наиболее сильно ограничивающие прибыль)?

Предприятие «Маяк»

Предприятие имеет 11 линий 5 типов. Производительность линий, выпускающих 7 видов продуктов, время (часы), за которое на данной линии производится единица продукции, и стоимость 1 ч работы линии отражены в таблице.

Количество	Тип	П1	П2	П3	П4	П5	П6	П7	Стоимость 1 ч работы, $
3	Линия 1	0,5	0,7	0,8	0,4	0,7	0,8	0,5	20
3	Линия2	0,65	0,91	1,04	-	0,91	1,04	0,65	15
2	Линия 3	0,35	0,49	0,56	0,28	0,49	0,56	0,35	30
2	Линия 4	0,25	0,35	0,4	-	0,35	0,4	0,25	40
1	Линия 5	-	0,28	0,32	0,16	0,28	0,32	0,2	50

Потребность рынка в продуктах 1, …7 составляет 3500, 1000, 1000, 2000, 800, 200, и 1000 шт. в месяц соответственно, а разница между стоимостью сырья и ценой этих продуктов равна 25, 26, 28, 24, 27, 29, 23 $.

Учтите, что предприятие может работать в нормальном режиме 16 ч в день и в среднем 24 дня в месяц. Известно также, что постоянные издержки для работающей линии составляют 1000$ в месяц (издержки запуска).

«а». Рассчитайте, какую прибыль может получить предприятие за 1 месяц.

«b». Как изменится прибыль, если придется отказаться от выпуска продукта 6?

Англия, Франция, и Испания

Предположим, что Англия, Франция и Испания производят всю пшеницу, ячмень и овес в мире. Мировой спрос требует отводить под пшеницу 125 млн. акров земли, под ячмень-60 млн. акров, под овес-75 млн. акров.

Общее количество земли, пригодной для этих целей в Англии, Франции и Испании,- 70млн,110 млн. и 80 млн. акров соответственно. Число часов, необходимых в Англии, Франции и Испании, чтобы вырастить 1 акр пщеницы,18, 13 и 16 соответственно; 1акр ячменя-15, 12, и 12ч соответственно; 1 акр овса-12, 10 и 16ч. Заработная плата в час в Англии, Франции и Испании при выращивании пшеницы – 3; 2,40 и 3,30долл. соответственно; при выращивании ячменя – 2,70; 3; 2,80 долл. соответственно и при выращивании овса – 2,30; 2,50 и 2,10 долл. соответственно.

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

Собачья еда

Компания производит три вида еды для животных: Regular, Extra и Puppy delite из трёх ингредиентов К9, К8 и К1.

Regular содержит 1/3 каждого из ингредиентов и даёт прибыль 0,20 долл. за банку. Extra содержит 50% К9 и по 25% каждого из ингредиентов К8 и К1 и даёт прибыль 0,18 долл. за банку. Puppy delite содержит 10% К8, 90% К1 и даёт прибыль 0,25 долл. за банку. Продукция идёт в банках по 1 кг.

Запасы ингредиентов на неделю – 1900 кг К9 и по 1000 кг К8 и К1.

а. Определить оптимальный план производства смесей Regular, Extra и Puppy, максимизирующий прибыль.

б. Все ли типы смесей выгодно производить? Что должно быть изменено, чтобы производство убыточной смеси стало выгодным? Можно ли изменить что-то в технологии или в ценовой политике так, чтобы все смеси стало выгодно производить? Попытайтесь сделать это.

в. Допустим, вы можете купить дополнительно 500 кг одного из ингредиентов? Какой именно (К9, К8 или К1) вы предпочтёте? Как увеличится прибыль? Подтвердите ваши ответы вычислениями.

Фармацевтическая компания

Фармацевтическая компания исследует возможность продвижения на рынок новой пищевой добавки, которая должна содержать микроэлементы: железо, кальций, фосфор. Добавка может быть получена путём смешивания 3 ингредиентов, которые компания обозначает как Т5, N1 и Т4. Количество трех микроэлементов (мг на 100 мл), содержащихся в каждом из ингредиентов, минимальный и максимальный уровень каждого микроэлемента в 1,2-литровой бутылке и издержки на производство 100 мл каждого ингредиента приведены в таблице

Издержки на 100 мл	0,75 руб.	0,60 руб.	0,55 руб.	Минимум в бутылке	Максимум в бутылке
Ингредиент	Т5	N1	T4
Железо	10	16	12	100 мг	150 мг
Калий	400	600	800	6000 мг	8000 мг
Фосфор	800	550	500	3000 мг	8000 мг

Менеджер хочет найти комбинацию ингредиентов в пищевой добавке, минимизирующую издержки на их производство.

а) Сформулировать ЗЛП.

б) Менеджер внёс предложение продавать компонент N1 по 0,7 руб. за 100 мл. В этом случае новую пищевую добавку придется готовить только из смеси Т5 и Т4. Стоит ли принимать это предложение?

Пять предприятий

Корпорация решила производить три новых изделия. Пять ее предприятий имеют избыточные возможности для производства этих изделий. Общезаводские накладные расходы на единицу изделия X были бы равны 31, 29, 32, 28 и 29 долл. для предприятий 1, 2, 3, 4 и 5 соответственно. Расходы на единицу изделия Y были бы 45, 41, 46, 42 и 43 долл. соответственно. Накладные расходы на единицу изделия Zбыли бы 38, 35 и 40 долл. для предприятий 1, 2 и 3 соответственно, а предприятия 4 и 5 не имеют возможности производить это изделие. Коммерческие прогнозы указывают, что должно быть произведено 600, 1000 и 800 единиц изделий X, Y и Z в день. Предприятия 1, 2, 3, 4 и 5 имеют возможность производить соответственно 400, 600, 400, 600 и 1000 изделий ежедневно независимо от изделия или комбинации изделий. Любое предприятие может производить любую комбинацию изделий в любом количестве в рамках изложенных ограничений.

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

b. Управляющие предприятиями требуют, чтобы недогрузка предприятий распределялась по справедливости, т. е. поровну. Как при выполнении этого требования изменятся общие издержки и план производства?

Лайф-микс №4

Российская фармацевтическая фирма планирует обновить линию поливитаминов, заменив старые, теряющие привлекательность марки. Поливитамин Лайф-микс №4 будет продаваться в виде драже весом 0,3 г. Необходимо обеспечить содержание в одном драже следующих количеств витаминов: Е – от 28 до 30 мг, Р – от 54 до 60, FA – от 36 до 40 мг. Кроме того, одно драже должно содержать от 330 до 350 мкг., комплекса микроэлементов.

Данный набор витаминов и микроэлементов нужно сформировать, используя четыре базовых препарата: Е225, Е303, D120, D125. Препараты различаются как закупочной ценой, так и содержанием нужных компонентов (в 1 г. ингредиента).

Цена, руб./г.	Ингредиент	Витамины, мг.			Микроэлементы, мкг.
		Е	Р	FA
0,8	Е225	200	340	20	800
0,35	Е303	100	250	30	0
0,5	D120	0	70	280	1400
0,3	D125	200	0	50	3000

Если общий вес ингредиентов будет меньше 0,28 г. (остальные 0,02 г. придутся на оболочку драже), для обеспечения нужного веса может быть добавлен инертный заполнитель.

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

А. Сформулируйте и решите задачу ЛП.

В. Какова будет стоимость ингредиентов, необходимых для производства одной упаковки поливитамина Лайф-микс №4 (100 драже)?

С. Можно ли отказаться от использования какого-нибудь ингредиента? На сколько процентов от минимальной при этом возрастет стоимость компонентов в 1 драже?

Школьные обеды

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

Базовый состав продуктов, которые решено использовать для приготовления обедов исходя из их доступности в различных местностях, приведен в таблице 1. В таблице 2 приведены значения минимальных потребностей в некоторых веществах и калориях для старшеклассников в расчете на один обед.

 

Таблица 1

Продовольствие	Цена за кг, руб.
овядина	100
Масло	70
Хлеб	10
Морковь	30
Рыба	95
Яйца	105
Молоко	20
Сыр	100
Картофель	20

 

Таблица 2

	Количество	Единицы
Калории	2000	ккал
Белки	70	г
Железо	10	мг
Кальций	800	мг
А	1,5	мг
В1	1	мг
В2	1,5	мг
РР	8	мг

 

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

Таблица 3

	Говядина	Масло	Хлеб	Морковь	Рыба	Яйца	Молоко	Сыр	Картофель
Калории	1200	7800	2000	400	650	1500	600	3000	900
Белки	160		70		140	110	50	300	17
Железо	25		20						12
Кальций			250				1200	8000	100
А	0,1	6		90		7	0,5	2
В1	2,5		2,6
В2	2		1,3		2	8	1,9	4,5	0,5
РР	20		4,5		50	2			9

Исходя из того, что в таблице учтены не все необходимые вещества и из некоторых других требований, при выборе составных частей обеда следует удовлетворить следующим условиям:

ü Количество масла должно составлять от 20 до 30г.

ü Расчетное количество хлеба не должно превышать 400г.

ü Количество мяса и рыбы не должно быть меньше 50г.

ü Количество яиц не должно быть меньше 20г.

ü Количество картофеля не должно превысить 300г.

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

 

ТРАНСПОРТНЫЕ ЗАДАЧИ

Два груза разных объемов

Менеджер отдела логистики составляет план перевозки продукции фирмы с 3 ее складских комплексов База1,…, База 3 к четырем клиентам: X, Y, Z и W. Речь идет о перевозке двух видов продукции: А и В.

Стоимость перевозки каждого вида продукции складывается из постоянной издержки доставки (погрузка-разгрузка и факт использования автофургона) плюс оплата за километраж. Постоянная издержка доставки составляет 100 у.е., плата за километраж – 1 у.е. за 1 км. Расстояния от баз до клиентов даны в таблице.

	Клиент Х	Клиент У	Клиент Z	Клиент W
База 1	40	45	45	35
База 2	40	45	30	40
База3	40	35	50	45

В одном автофургоне умещается количество товаров суммарным объемом 1. Объем упаковки 1 шт. А составляет 0,1 объемной единицы. Объем упаковки 1 шт. В составляет 0,2 объемной единицы. Любая комбинация товаров А и В, умещающаяся в автофургоне, по весу не превышает допустимого предела.

Клиенты заказывают следующие количества товаров А, В:

	Клиент Х	Клиент У	Клиент Z	Клиент W
	А	А	А	А
Заказ	7	12	15	28
	В	В	В	В
Заказ	3	4	14	10

На базах же в настоящий момент имеются следующие запасы товара:

	А	В
База 1	16	19
База 2	25	15
База 3	28	7

Составьте и решите задачу минимизации общих издержек доставки обоих грузов к потребителям.

 

Воздушные перевозки

Авиакомпания имеет во владении и лизинге следующий парк самолетов:

	Il 96-300	Il 62M	Il-86	Tu-154	Tu-134	A-310	B737-400	B767-300ER	B777-200
Вместимость, человек	235	162	350	158	76	191	137	269	400
Парк самолетов, шт.	6	13	15	24	12	11	10	4	2

На некоторых маршрутах величина пассажиропотока изменилась, и менеджер должен составить план использования авиалайнеров так, чтобы занять как можно меньше машин. Количества пассажиров на каждом из маршрутов даны в таблице.

	Париж	Токио	Нью-Йорк	Хурген	Малага
Количество пассажиров в день	1000	5000	850	1300	500

 

Следует учесть, что лайнеры российского производства не могут выполнять европейские рейсы. Вообще из российских лайнеров только II-96-300 и II-86 могут выполнять рейсы в Токио и Хурген, а II-62M, Tu-154, Tu-134 использовать на приведенных пяти маршрутах невозможно.

Учтите также, что общая вместимость лайнеров, назначенных на маршрут, не должна превышать более чем на 10%

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

«b». Используйте целые переменные и вновь решите задачу. Сравните два решения задачи.

(при выборе переменных постарайтесь свести их количество до необходимого минимума, иначе задача будет решаться очень долго. С минимальным набором переменных решение занимает 2-3 мин на среднем компьютере.)

Рейс машины инкассатора

Менеджер банка желает установить оптимальный маршрут для машины службы инкассации, чтобы определить общее время рейса и точнее договориться с администрацией магазинов о времени визита инкассатора. Инкассатор должен посетить 9 магазинов. Машина выезжает с внутренней стоянки банка и после завершения рейса должна вернуться снова в банк.

Менеджер рассчитал протяженность всех 45 возможных отрезков пути между пунктами назначения. Она приведена в таблице.

Расстояние, км	Б	1	2	3	4	5	6	7	8	9
База	0	20	22	14	14	10	15	11	13	24
Маг. № 1	20	0	11	7	7	22	16	10	33	7
Маг. № 2	22	11	0	14	9	28	10	16	34	6
Маг. № 3	14	7	14	0	6	16	15	3	27	13
Маг. № 4	14	7	9	6	0	19	9	8	27	10
Маг. № 5	10	22	28	16	19	0	24	12	16	28
Маг. № 6	15	16	10	15	9	24	0	16	26	15
Маг. № 7	11	10	16	3	8	12	16	0	24	16
Маг. № 8	13	33	34	27	27	16	26	24	0	37
Маг. № 9	24	7	6	13	10	28	15	16	37	0

a. Сформулируйте задачу линейной оптимизации, которая позволяет найти самый короткий по общей протяженности маршрут для автомашины, позволяющий объехать все 9 магазинов и вернуться на базу. Никаких ограничений на порядок объезда магазинов нет. Какова минимальная длина маршрута?

b. Определите длительность маршрута при средней скорости в пути 60 км/час и среднем времени визита в магазины 10 минут.

c. В предстоящем времени магазин № 5 закрывается на ремонт. Какой маршрут теперь будет самым коротким? Насколько уменьшится время поездки?

Команд

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

	Р1	Р2	Р3	Р4	Р5	Р6	Р7
М1	10	13	7	1	11	6	6
М2	7	3	5	1	8	2	13
М3	1	6	4	12	11	4	9
М4	4	1	13	5	11	4	3
М5	7	4	5	1	7	3	12
М6	8	11	13	5	8	1	9
М7	6	13	2	13	9	5	2

а) Какова величина суммарного индекса? Каков наихудший индекс в отобранных парах?

b) Есть ли у задачи альтернативные решения? Какое из решений лучше? Почему?

Команд с проблемой

Необходимо составить 8 команд по два человека из бригадира и инженера для вахтовой работы по монтажу базовых станций сотовой связи в одной из северных областей. Составленные пары возглавят 8 бригад рабочих. Среди опытных сотрудников, работавших в центральных районах и встречавшихся друг с другом, проведён специальный психологический тест на взаимную совместимость. Индекс совместимости по теории варьирует от 1 (возможность дружеских отношений) до 20 (выраженная враждебность) и для каждой потенциальной пары приведён в таблице.