200-
Рис. 5.11. Схема маршрутов для упражнения 1
2. Пусть в предыдущей задаче пункты 1 и 2 связаны транспортной магистралью со стоимостью перевозки в 1 долл., а стоимость перевозки из пункта 1 в пункт 3 возросла до 5 долл. Найдите оптимальную схему перевозок.
3. На рис. 5.12 показана транспортная сеть перевозок автомобилей между тремя заводами (пункты 1, 2 и 3) и тремя дилерами (пункты 6, 7 и 8) через два распределительных центра (пункты 4 и 5). Стоимость перевозок (в сотнях долларов) представлена на рисунке возле соответствующих дуг.
1400
1000-
-1100
-1000
-1200
Рис. 5.12. Схема маршрутов для упражнения 3
a) Сформулируйте задачу как транспортную задачу.
b) Предположим, распределительный центр (пункт 4) может продать 240 автомобилей самостоятельно. Найдите новое оптимальное решение.
4. Две фабрики" снабжают определенной продукцией три магазина. Объемы производства фабрик равны 200 и 300 единиц продукции, а потребности магазинов составляют 100, 200 и 50 единиц продукции. Исследуется возможность перевозок продукции через промежуточные пункты. Основываясь на величинах стоимости перевозок (в долл.), приведенных в табл. 5.45, найдите оптимальный план перевозок.
Таблица 5.45
| | Фабрики | | | | Магазины | |
| | | | | | | |
Фабрики | | | | | | | |
| | | | | | | |
Магазины | | | | " г | | | |
| | | | | | | |
| | | | | | | |
5. На рис. 5.13 показана сеть нефтепроводов. Узлы этой сети соответствуют насосным и принимающим станциям. Расстояния (в милях) между станциями приведены на схеме сети. Стоимость транспортировки одного галлона нефти между двумя станциями пропорциональна длине нефтепровода, соединяющего эти станции. Сформулируйте транспортную задачу с промежуточными пунктами и найдите ее оптимальное решение для перекачки нефти из пунктов 1 и 3 в пункты 2 и 4.
50 ООО 60 ООО (галлоны)
Рис. 5.13. Сеть нефтепроводов для упражнения 5
6. Задача нахождения кратчайшего пути. Чтобы найти кратчайший путь между пунктами 1 и 7 транспортной сети, показанной на рис. 5.14, сформулируйте транспортную задачу с промежуточными пунктами. Расстояния между промежуточными пунктами показаны на рисунке. (Совет. Пусть в пункте 1 есть предложение в одну единицу, а в пункте 7 - спрос такой же величины.)
Рис. 5.14. Транспортная сеть для упражнения 6
7. В модели примера 5.5.1 обозначим через xtj объем перевозок между пунктами i и у. Задачу этого примера можно сформулировать как задачу линейного программирования, у которой каждому пункту транспортной сети соответствует ограничение в виде равенства. Сформулируйте задачу ЛП и покажите, что в ограничениях коэффициенты а1} при переменных xtj определяются следующим образом.
ЛИТЕРАТУРА
1. BazaraaM., Jarvis J., SheraliM. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.
2. Dantzig G. Linear Programming and Extensions, Princeton University Press, Princeton, N. J., 1963. (Русский перевод: Данциг Дж. Линейное программирование, его применение и обобщение. - М.: Прогресс, 1966.)
3. Murty К. Network Programming, Prentice Hall, Upper Saddle River, N. J., 1992.
Литература, добавленная при переводе
1. Ашманов С. А. Линейное программирование. - М.: Наука, 1981.
2. Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. - М.: Наука, 1969.
КОМПЛЕКСНЫЕ ЗАДАЧИ
5.1. 9 Компания ABC Cola имеет завод по производству безалкогольных напитков в северной части островного государства Таванда. Напитки выпускаются в трех различных упаковках: возвращаемых стеклянных бутылках, алюминиевых консервных банках и невозвращаемых пластмассовых бутылках. Стеклянные бутылки складируют и затем возвращают на завод для повторного использования.
Задача построена на материалах статьи Cheng Т., Chiu С. "A Case Study of Production Expansion Planning in a Soft-Drink Manufacturing Company", Omega, Vol. 16, No. 6, pp. 521-532,1988.
1, для ограничения /, а = < - I, для ограничения j, О, в противном случае.
8. Агентство по трудоустройству имеет заявки на рабочих на следующие пять месяцев.
Месяц 1 2 3 4 5
К-во рабочих 100 120 80 170 50
Стоимость рабочей силы зависит от длительности периода трудоустройства (см. следующую таблицу).
Длительность периода трудоустройства (месяцы) 1 2 3 4 5
Стоимость трудоустройства одного рабочего (долл.) 100 130 180 220 250
Сформулируйте задачу линейного программирования. Затем путем алгебраических преобразований ограничений покажите, что эту задачу можно свести к транспортной. Найдите ее оптимальное решение. (Совет. Для преобразования общей задачи ЛП в транспортную используйте представление коэффициентов ограничений из предыдущего упражнения.)