ЛИТЕРАТУРА

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

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

Плановые возможности существующего завода по выпуску продукции показаны в табл. 5.47.

Таблица 5.47

Компания имеет 6 складов для стеклотары: N1 и N2 расположены в северной части острова, С1 и С2 - в центральной части, S1 и S2 - в южной. Доля стеклотары, обрабатываемой каждым складом, показана в табл. 5.48.

Таблица 5.48

Склад Доля (в процентах)

N1 85

N2 15

С1 60

С2 40

51 80

52 20

Из общего количества стеклотары примерно 60% приходится на северные склады, 15% - на центральные и 25% - на южные.

Компания планирует построить новый завод по производству безалкогольных напитков либо в центре, либо на юге острова. Транспортные расходы, рассчитанные на одну упаковку напитка в стеклянных бутылках, приведены в табл. 5.49. Транспортные расходы на напитки в банках и пластмассовых бутылках составляют соответственно 60 и 70% от аналогичных расходов на транспортировку напитков в стеклянных бутылках.

Определите, где целесообразнее построить новый завод: в центральном районе или на юге острова?

Поскольку спрос на безалкогольные напитки постоянно растет, компания ABC Cola планирует построить еще один завод в центральной или южной части острова. Прогнозируемый спрос на безалкогольные напитки (выраженный в количестве упаковок) на следующие пять лет показан в табл. 5.46.

Таблица 5.46

Транспортные расходы на одну упаковку (долл.)

5.2. В ходе строительства международного аэропорта в г. Брисбен для укрепления болотистого грунта необходимо произвести песчаную насыпь общим объемом 1 355 000 м3 на девяти площадках аэропорта. Песок берется из расположенных вблизи аэропорта пяти небольших карьеров. Некоторые строительные подразделения, обслуживающие стройплощадки, выделены для прокладки дорог внутри аэропорта и по его периметру. Для насыпи песок берется со стройплощадок. Расстояние (в сотнях метров) от карьеров до стройплощадок показано в табл. 5.50, где также приведены потребности в песке стройплощадок и возможности карьеров (в 100 м3).

Таблица 5.50

стройплощадок

a) Управление строительством оценивает объем перемещения песка [объем (м3) х расстояние (100 м)] в 2 495 000 соответствующих единиц при стоимости 0,65 долл. за единицу. Достаточно ли приведенного объема песка для выполнения запланированных работ?

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

Задача построена на материалах статьи Perry С, Ilief М. Earth Moving on Construction Projects , Interfaces, Vol. 13, No. 1, pp. 79-84, 1983.

Таблица 5.49