Linear Programming Output summary 11 страница

Минимизировать z = 80jc„ + 215.v₁₂ + 100.v₂₁ +108jc₂₂ + 102jc₃₁ + 68x,₂ при ограничениях

x_u +jc₁₂ = 1000 (Лос-Анджелес),

jc₂₁ +jc₂₂ = 1500 (Детройт),

*3i ^+хз2 ⁼ 1200 (Новый Орлеан),

5.1. Определение транспортной модели

л-,, + х₂₁ + х₃₁ = 2300 (Денвер),

х₁₂ + х₂₂ + х₃₂ = 1400 (Майами),

x_tj>0, /=1,2,3,7 = 1,2.

Эти ограничения выражены в виде равенств, поскольку общий объем произведен­ных автомобилей (1000 + 1500 + 1200 = 3700) равен суммарному спросу распреде­лительных центров(2300 + 1400 = 3700).

Данную задачу ЛП можно решить симплекс-методом. Но специфическая структура ограничений позволяет решить эту задачу более простым способом с помощью так называемой транспортной таблицы (табл. 5.3).

Таблица 5.3

Денвер Майами Объем производства

Лос-Анджелес	Хп		Х|2
Детройт	Х21		х:2
Новый Орлеан	X3I		Х.12
Спрос

Оптимальное решение (полученное с помощью программы TORA) показано на рис. 5.2. Оно предполагает перевозку 1000 автомобилей из Лос-Анджелеса в Денвер, 1300 автомобилей— из Детройта в Денвер, 200 автомобилей— из Дет­ройта в Майами и 1200 — из Нового Орлеана в Майами. Минимальная стоимость перевозок составляет 313 200 долл.

1000-

150О

1200-

Новый Орлеан

Рис. 5.2. Схема оптимальных перевозок

Чтобы получить в программе TORA решение транспортной задачи, в меню Main Menu выберите команду Transportation Model (Транспортная модель). Затем в меню SOLVE/MODIFY выберите команду Solved Final solution. Более подробно решение транспортных задач в про­грамме TORA описано в разделе 5.3.3.

Глава 5. Транспортные модели

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

Пример 5.1.2

В рамках модели компании MG Auto предположим, что завод в Детройте уменьшил выпуск продукции до 1300 автомобилей (вместо 1500, как было ранее). В этом случае общее количество произведенных автомобилей (3500) меньше общего числа зака­занных (3700). Таким образом, очевидно, что часть заказов распределительных центров Денвера и Майами не будет выполнена.

Поскольку в данной ситуации спрос превышает предложение, для восстановления ба­ланса введем фиктивный завод (пункт отправления), производящий 200 (3700 - 3500) автомобилей. Назначим нулевую стоимость транспортных перевозок от фиктивного за­вода до пунктов назначения, поскольку такого завода не существует. В принципе, стоимость транспортных перевозок от фиктивного пункта назначения может иметь любое положительное значение. Например, чтобы гарантировать выполнение всех заказов распределительного центра Майами, можно назначить очень высокую стои­мость перевозок (штраф) от фиктивного завода до Майами.

В табл. 5.4 представлена сбалансированная модель и ее оптимальное решение. Ре­шение показывает, что фиктивный завод поставит в Майами 200 автомобилей. Это означает, что для данного распределительного центра из заказа на 1400 автомоби­лей не будет поставлено 200 автомобилей.

Таблица 5.4

Денвер

Майами

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

Лос-Анджелес
Детройт
Новый Орлеан
Фиктивный завод
Спрос

5.1. Определение транспортной модели

Предположив, что заказ распределительного центра Денвера составляет всего 1900 ав­томобилей, получим ситуацию, когда предложение превышает спрос. В этой ситуации необходимо ввести фиктивный пункт назначения, "поглощающий" избыточное пред­ложение. Здесь также можно назначить нулевую стоимость перевозок в фиктивный пункт назначения, если не требуется выполнения каких-то особых условий. Напри­мер, если необходимо вывести всю продукцию какого-либо завода, следует назначить очень высокую стоимость перевозок от этого завода до фиктивного пункта назначения.

В табл. 5.5 показана новая модель и ее оптимальное решение (полученное с помо­щью программы TORA). Решение показывает, что 400 автомобилей завода Детрой­та не востребованы.

Таблица 5.5

Денвер	Майами	Фиктивный центр

Лос-Анджелес

Детройт

Новый Орлеан Спрос

УПРАЖНЕНИЯ 5.1

1. Истинны или ложны следующие утверждения?

a) Для сбалансированности транспортной модели может понадобиться ввести как фиктивные пункты отправления, так и фиктивные пункты назначения.

b) Объем перевозок в фиктивный пункт назначения равен объему превыше­ния предложения над спросом.

c) Объем перевозок из фиктивного пункта отправления равен разности меж­ду спросом и предложением.

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

a) Предложение: а, = 10, а₂ = 5, а₃ = 4, а₄ = 6. Спрос: Ь, = 10, Ь₂ = Ъ,Ь₃ = 7, Ь_л = 9.

b) Предложение: а_х — 30, а₂ = 44. Спрос: 6, = 25, Ь₂ = 30, Ь₃ = 10.

3. На основе табл. 5.4 из примера 5.1.2 (здесь введен фиктивный завод) интер­претируйте решение, при котором фиктивный завод "поставит" 150 автомо­билей распределительному центру в Денвере и 50 автомобилей распредели­тельному центру в Майами.

4. Как в табл. 5.5 из примера 5.1.2 учесть требование, что завод в Детройте должен отправить заказчикам все свои автомобили?

Глава 5. Транспортные модели

5. Пусть в примере 5.1.2 (табл. 5.4) введены штрафы в размере 200 и 300 долл. за каждый недопоставленный автомобиль в распределительные центры Денве­ра и Майами соответственно. Кроме того, поставки из Лос-Анджелеса в Майами не планируются изначально. Постройте транспортную модель и найдите схему оптимальных перевозок с помощью программы TORA.

6. Три электрогенерирующие станции мощностью 25, 40 и 30 миллионов кВт/ч поставляют электроэнергию в три города. Максимальная потребность в элек­троэнергии этих городов оценивается в 30, 35 и 25 миллионов кВт/ч. Цены за миллион кВт/ч в данных городах показаны в табл. 5.6.

Таблица 5.6

		Город 2
Станция 2

В августе на 20% возрастает потребность в электроэнергии в каждом из трех городов. Недостаток электроэнергии города могут восполнить из другой электросети по цене 1000 долл. за 1 миллион кВт/ч. К сожалению, третий город не может подключиться к альтернативной электросети. Электрогене­рирующие станции планируют разработать наиболее экономичный план рас­пределения электроэнергии и восполнения ее недостатка в августе.

a) Сформулируйте эту задачу в виде транспортной модели.

b) Решите транспортную задачу с помощью программы TORA и определите оптимальный план распределения электроэнергии электрогенерирующи-ми станциями.

c) Определите стоимость дополнительной электроэнергии для каждого из трех городов.

7. Выполните предыдущее упражнение, предполагая, что 10% электроэнергии теряется при передаче по электросетям.

8. Три нефтеперегонных завода с ежедневной производительностью 6, 5 и 8 мил­лионов галлонов бензина снабжают три бензинохранилища, ежедневная по­требность которых составляет 4, 8 и 7 миллионов галлонов бензина соответ­ственно. Бензин транспортируется в бензинохранилища по бензопроводу. Стоимость транспортировки составляет 10 центов за 1000 галлонов на 1 ми­лю длины трубопровода. В табл. 5.7 приведены расстояния (в милях) между заводами и хранилищами. Отметим, что первый нефтеперегонный завод не связан трубопроводом с третьим бензинохранилищем.

Таблица 5.7

		Бензохранилище 2
			—
Завод 2

5.1. Определение транспортной модели

a) Сформулируйте транспортную задачу.

b) С помощью программы TORA найдите оптимальную схему транспорти­ровки бензина.

9. Пусть в предыдущем упражнении ежедневная производительность третьего нефтеперерабатывающего завода составляет 6 миллионов галлонов бензина, а потребности первого бензинохранилища должны выполняться в обязательном порядке. Кроме того, на недопоставки бензина во второе и третье хранилища налагаются штрафы в размере 5 центов за каждый недо­поставленный галлон бензина.

a) Сформулируйте соответствующую транспортную задачу.

b) Решите сформулированную задачу с помощью программы TORA и найди­те оптимальную схему поставок бензина.

10. Пусть в упражнении 8 ежедневные потребности третьего бензинохранилища составляют 4 миллиона галлонов. Избыток своей продукции первый и второй нефтеперегонные заводы могут отправить на другие бензохранилища с по­мощью автотранспорта. В этом случае расходы на транспортировку 100 гал­лонов бензина составляют 1,50 и 2,20 долл. для первого и второго заводов со­ответственно. Третий нефтеперерабатывающий завод может использовать свои излишки бензина для нужд собственного химического производства.

a) Сформулируйте соответствующую транспортную задачу.

b) Решите сформулированную задачу с помощью программы TORA и найди­те оптимальную схему поставок бензина.

11. Три плодовых хозяйства поставляют апельсины в ящиках четырем оптовым покупателям. Ежедневная потребность этих покупателей составляет 150, 150, 400 и 100 ящиков соответственно. Предположим, что все три плодовых хозяй­ства используют только постоянную рабочую силу и могут ежедневно по­ставлять 150, 200 и 250 ящиков апельсинов соответственно. Первые два хо­зяйства могут увеличить поставки апельсинов, привлекая дополнительных рабочих, третье хозяйство такой возможности не имеет. Транспортные рас­ходы (в долл.) на один ящик апельсинов приведены в табл. 5.8.

Таблица 5.8

		Покупатели
Хозяйства 2

a) Сформулируйте соответствующую транспортную задачу.

b) Решите сформулированную задачу с помощью программы TORA.

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

12. Три распределительных центра поставляют автомобили пяти дилерам. Ав­томобили от распределительных центров к дилерам перевозятся на трейле­рах, и стоимость перевозок пропорциональна расстоянию между пунктами отправления и назначения и не зависит от степени загрузки трейлера.

Глава 5. Транспортные модели

В табл. 5.9 приведены расстояния между распределительными центрами и дилерами, а также соответствующие величины спроса и предложения, вы­раженные в количествах автомобилей. При полной загрузке трейлер вмеща­ет 18 автомобилей. Транспортные расходы составляют 25 долл. на одну милю пути, пройденного трейлером.

Таблица 5.9

			Дилеры
						Предложения
Центры 2
Спрос

a) Сформулируйте соответствующую транспортную задачу.

b) Решите сформулированную задачу с помощью программы TORA.

13. Компания MG Auto из примера 5.1.1 производит четыре модели автомоби­лей. Завод в Детройте выпускает модели Ml, М2 и М4. Модели Ml и М2 про­изводятся в Новом Орлеане, МЗ и М4 — в Лос-Анджелесе. Производитель­ность каждого завода и потребности распределительных центров в автомобилях разных моделей даны в табл. 5.10.

Таблица 5.10

Модель

М1 М2 МЗ М4 Всего

Завод

Лос-Анджелес — — 700 300 1000

Детройт 500 600 — 400 1500

Новый Орлеан 800 400 — — 1200 Распределительный центр

Денвер * 700 500 500 600 2300

Майами 600 500 200 100 1400

Расстояния между заводами и распределительными центрами приведены в примере 5.1.1, транспортные расходы составляют 8 центов за перевозку од­ного автомобиля (любой модели) на одну милю пути. Кроме всего прочего, есть возможность удовлетворить спрос на одну из моделей автомобилей за счет другой в соответствии с табл. 5.11.

Таблица 5.11

Распределительный центр Заменяемая часть спроса (%) Взаимозаменяемые модели Денвер 10 М1.М2

20 МЗ, М4

Майами 10 М1, МЗ

5 М2, М4

5.2. Нетрадиционные транспортные модели

a) Сформулируйте соответствующую транспортную задачу.

b) Решите сформулированную задачу с помощью программы TORA.

(Совет. Введите четыре новых пункта назначения, соответствующих комби­нациям (Ml, М2), (МЗ, М4), (Ml, М2) и (М2, М4). Объемы потребностей но­вых пунктов определяются на основании данных о процентном соотношении заменяемых моделей автомобилей.)

5.2. НЕТРАДИЦИОННЫЕ ТРАНСПОРТНЫЕ МОДЕЛИ

Использование транспортной модели не ограничивается задачей о транспорти­ровке чего-либо между географическими пунктами отправления и назначения. В этом разделе описано применение транспортной модели к задаче управления за­пасами и задаче распределения оборудования.

Пример 5.2.1. Управление запасами

Фабрика Boralis производит рюкзаки для путешественников. Спрос на эту продук­цию, в основном, есть только в марте-июне (т.е. четыре месяца в году). Фабрика оценивает спрос в эти месяцы соответственно в 100, 200, 180 и 300 единиц изделия. Так как производство не ритмично, на фабрике рабочие работают не полный рабо­чий день. В течение рассматриваемых четырех месяцев фабрика может выпустить 50, 180, 280 и 270 единиц изделия. Производство и спрос в различные месяцы не совпадают, спрос в текущем месяце можно удовлетворить следующими способами.

1. Производством изделий в течение текущего месяца.

2. Избытком произведенных в прошлом месяце изделий.

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

В первом случае стоимость одного рюкзака составляет 40,00 долл. Во втором случае возникают дополнительные расходы в расчете 0,50 долл. на один рюкзак за хранение в течение месяца. В третьем случае за просроченные заказы начисляются штрафы в размере 2,00 долл. на один рюкзак за каждый просроченный месяц. Фабрика пла­нирует разработать оптимальный план производства на эти четыре месяца.

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

Транспортная модель Модель управления запасами

1. Пункт отправления / 1. Период производства /

2. Пункт назначения j 2. Период потребления

3. Предложение в пункте отправления /' 3. Объем производства за период /

4. Спрос в пункте назначения j 4. Объем реализации продукции за период j

5. Стоимость перевозки из пункта /' в пункт / 5. Стоимость единицы продукции

(производство + хранение + штрафы) за период от / до j

Глава 5. Транспортные модели

Результирующая транспортная модель представлена в табл. 5.12 (данные выраже­ны в долл.).

Таблица 5.12

					Объем производства
	40,00	40,50	41,00	41,50
	42,00	40,00	40,50	41,00
	44,00	42,00	40,00	40,50
	46,00	44,00	42,00	40,00
Спрос

Стоимость "транспортировки" единицы изделия из периода < в периоду вычисляет­ся следующим образом.

стоимость производства в j'-й период, i = j, стоимость производства в;'-й период +

+ стоимость хранения от i до j, i < j, стоимость производства в i-й период + штраф от i до j, i > j.

Например,

с„ = 40,00,

c_2i = 40,00 + (0,50 + 0,50) = 41,00 долл.,

с₄₁ = 40,00 + (2,00 + 2,00 + 2,00) = 46,00 долл.

Оптимальное решение графически представлено на рис. 5.3. Здесь пунктирны­ми линиями показаны задолженности производства, линией из точек представ­лено производство для будущего периода (для удовлетворения будущего спро­са) и сплошными линиями — производство для удовлетворения спроса текущего периода.

© ©

Объем производства 50 180 280

Период производства

50 50,'' 130 /

/

¹ > /

Период спроса ^rf

Спрос 100 200 180

70/ 180

30-.. 270

© © та

Рис. 5.3. Оптимальное решение задачи управления запасами

5.2. Нетрадиционные транспортные модели

Пример 5.2.2. Распределение оборудования

Лесопильный завод обрабатывает различную древесину (от мягкой сосны до твер­дого дуба) по утвержденному недельному производственному плану. Согласно это­му плану в зависимости от типа древесины в разные рабочие дни 7-днев-ной рабо­чей недели требуется различное количество полотен для пил.

День	1 (Пн.)	2 (Вт.)	3 (Ср.)	4 (Чт.)	5 (Пт.)	6 (Сб.)	7 (Вс.)
Потребность (к-во полотен)

Завод может удовлетворить свои потребности в полотнах одним из следующих способов.

1. Купить новые полотна по 12 долл. за единицу.

2. Применить ночную заточку полотен стоимостью 6 долл. за одно заточенное полотно либо сдать пилы на 2-дневную заточку (эта услуга стоит 3 долл. За полотно).

Данную ситуацию можно описать как транспортную модель с восьмью пунктами от­правления и семью пунктами назначения. Пунктам назначения соответствуют 7 дней рабочей недели. Исходные пункты (т.е. "пункты отправления") определяются сле­дующим образом. Первый исходный пункт соответствует покупке новых полотен; в экстремальном случае возможна такая покупка, которая удовлетворит потребность в полотнах на все 7 дней рабочей недели. Исходные пункты со второго по восьмой со­ответствуют семи дням рабочей недели. Объем предложения каждого из этих исход­ных пунктов равен количеству полотен, использованных к концу соответствующего рабочего дня. Например, "предложение" второго исходного пункта (соответствует понедельнику) равно количеству полотен, необходимых для выполнения производст­венного плана этого рабочего дня. "Транспортные" расходы в этой модели составля­ют соответственно 12, 6 и 3 долл., в зависимости от того, является ли полотно но­вым, получено после ночной заточки или после 2-дневного обслуживания полотен. Отметим, что для ночной заточки использованные полотна передаются в конце /-го рабочего дня и могут использоваться с начала (/' + 1)-го или (;' + 2)-го рабочего дня. При 2-дневной заточке использованные полотна отдаются на заточку в конце;'-го рабочего дня и могут использоваться с начала (/ + 3)-го рабочего дня или в после­дующие дни. В приведенной ниже таблице столбец "Остаток" соответствует фик­тивному пункту назначения, в этом столбце приведено количество полотен, остав­шихся не заточенными в конце каждого рабочего дня. Полная транспортная модель для описанной ситуации представлена в табл 5.13 (данные приведены в долл.).⁴ Оптимальное решение (полученное с помощью программы TORA, файл ch5ToraEquipMainEx5-2-2.txt) показано в следующей таблице.

Рабочий день	Новые полотна	Ночная заточка	2-дневная заточка	Остаток
Понедельник	24 (Пн.)	10 (Вт.)+ 8 (Ср.)	6 (Вт.)
Вторник	2 (Вт.)	6 (Ср.)	6 (Пт.)
Среда		14 (Чт.)
Четверг		12(Пт.)	8 (Вс.)
Пятница		14 (Сб.)
Суббота		14 (Вс.)
Воскресенье

Общая стоимость 840 долл.

⁴ В табл. 5.13 буква М означает достаточно большое положительное число. — Прим. ред.

Глава 5. Транспортные модели

Таблица 5.13

	1 (Пн.)	2 (Вт.)	3 (Ср.)	4 (Чт.)	5 (Пт.)	6 (Сб.)	7 (Вс.)	8 (Остаток)
(Новые)
	М
(Пн.)
	М	м
(Вт.)
	м	м	М
(Ср.)
	м	м	М	М
(Чт.)
	м	м	м	М	М
(Пт.)
	м	м	м	М	М	М
(Сб.)
	м	м	м	М	М	М	М
(Вс.)

Объясним полученный результат. В понедельник завод покупает 24 новых полотна для пил. В конце того же дня остается 24 использованных полотна, из которых 18 отправляются на ночную заточку, 6 — на 2-дневную. Из 18 заточенных ночью по­лотен 10 используются во вторник, а 8 — в среду. Шесть полотен после 2-дневного обслуживания используются в четверг. Остальные позиции приведенного решения интерпретируются аналогично. В столбце "Остаток" показано количество исполь­зованных полотен, которые не передаются на заточку в конце рабочего дня.

УПРАЖНЕНИЯ 5.2

1. Пусть в примере 5.2.1 стоимость хранения продукции зависит от месяца, в котором она произведена, и составляет для первых трех месяцев соответст­венно 40, 30 и 70 центов за хранение единицы продукции. Величина штрафа за просроченные заказы и величины производственных расходов остаются такими же, как и в примере 5.2.1. С помощью программы TORA найдите оп­тимальное решение и интерпретируйте полученный результат.

2. Пусть в примере 5.2.2 также имеется 3-дневный сервис по заточке полотен пил, использованных в понедельник и вторник; при этом стоимость заточки одного полотна составляет 1 долл. Сформулируйте задачу заново и интерпре­тируйте ее оптимальное решение, полученное с помощью программы TORA.

3. Пусть в примере 5.2.2 заточенные полотна, не использованные сразу после за­точки, отправляются на хранение, причем стоимость хранения одного полотна в течение дня составляет 50 центов. Переформулируйте задачу и интерпрети­руйте ее оптимальное решение, полученное с помощью программы TORA.

5.2. Нетрадиционные транспортные модели

4. Компания планирует оптимизировать распределение станочного парка, со­стоящего из станков четырех типов, для выполнения станочных работ пяти видов. Пусть имеется 25, 30, 20 и 30 станков каждого типа. Приведем ко­личество работ каждого вида: 20, 20, 30, 10 и 25 соответственно. Отметим, что станки четвертого типа не используются для выполнения работ четвер­того вида. В табл. 5.14 представлена стоимость (в долл.) выполнения каж­дого вида работ на станках определенного типа. Сформулируйте транс­портную задачу, решите ее с помощью программы TORA и интерпретируйте полученный результат.

Таблица 5.14

			Вид работ
Тип 2
станка 3
				—

5. Спрос на некий скоропортящийся продукт в следующие 4 месяца составляет 400, 300, 420 и 380 тонн соответственно. Предложение этого товара в те же месяцы составляет 500, 600, 200 и 300 тонн. Отпускная цена на этот товар колеблется от месяца к месяцу и равна соответственно 100, 140, 120 и 150 долл. за тонну. Поскольку товар скоропортящийся, он должен быть реализован в течение трех месяцев (включая текущий). Стоимость хранения в течение месяца тонны товара равна 3 долл. Природа товара такова, что не­возможна задержка с выполнением заказа. Опишите данную ситуацию как транспортную модель и найдите ее оптимальное решение для 4-х месяцев с помощью программы TORA.