Незамкнутая транспортная задача с избытком
Компания, занимающаяся добычей песка и доставкой его собственным транспортом к потребителям, разрабатывает 4 песчаных карьера. Недельная производительность карьеров 210, 170, 270 и 360 тонн. Песок направляется на три завода железобетонных изделий (ЖБИ). Недельные потребности заводов в песке составляют 300, 290 и 320 тонн. Транспортные затраты cij; (в условных денежных единицах — у.е.), связанные с доставкой 1 тонны песка от карьеров до заводов, известны и приведены в табл. 7.3.
Табл.7.3.
| Песчаные карьеры | Заводы ЖБИ | Производительность карьеров (предложение) | ||
| №1 | №2 | №3 | ||
| Потребности заводов (спрос) | Предложение превышает спрос на 100 т 1010>910 |
Требуется:
1) составить такой план перевозок песка из карьеров на заводы, при котором совокупные транспортные издержки будут минимальны;
2) выяснить, какое количество песка и на каких карьерах окажется невостребованным;
3) установить размер минимальных транспортных издержек.
Решение
Потребности заводов в песке (спрос) составляют 300 + 290 + 320 = = 910 т, в то время как мощности карьеров позволяют добывать 210 + 170 + 270 + 360 = 1010 т. Предложение превышает спрос на 100 т. Следовательно, эта задача незамкнутая (п. 7.1).
Для приведения ее к стандартному виду (задаче замкнутого типа) введем дополнительно фиктивного потребителя, спрос которого будет равен 100 т, а стоимости перевозок от карьеров до фиктивного потребителя примем равными нулю, так как реально никаких перевозок по этому маршруту выполняться не будет. В итоге получаем замкнутую задачу, эквивалентную исходной (табл. 7.4).
Табл.7.4.
| Песчаные карьеры | Заводы ЖБИ | Фиктивный потребитель | Предложение | ||
| №1 | №2 | №3 | №4 | ||
| Спрос | 1010=1010 |
Обозначим через хij количество песка (в тоннах), которое будет вывезено из карьера i (i = 1, 2, 3, 4) и доставлено на завод j (j = 1,2,3,4). Тогда искомый план перевозок, представленный в табл. 7.5., состоит из 16 управляемых переменных.
Табл.7.5.
| Песчаные карьеры | Заводы ЖБИ | Фиктивный потребитель | Предложение | ||
| №1 | №2 | №3 | №4 | ||
| х11 | х12 | х13 | х14 | ||
| х21 | х22 | х23 | х24 | ||
| х31 | х32 | х33 | х34 | ||
| х41 | х42 | х43 | х44 | ||
| Спрос | 1010=1010 |
Далее можно посчитать совокупные транспортные издержки на перевозку (аналогично предыдущей задаче). Заметим, что введение фиктивного потребителя с нулевыми стоимостями перевозок никак не влияет на целевую функцию в силу того, что коэффициенты при х14, х24, х34, х44 равны нулю.
Ограничения, вытекающие из необходимости удовлетворения потребностей заводов в песке, и ограничения, связанные с необходимостью полностью задействовать мощности карьеров и вывезти весь имеющийся запас песка, могут быть легко записаны. Кроме того, все переменные неотрицательны.
В результате мы получили замкнутую транспортную задачу линейного программирования: необходимо минимизировать целевую функцию при условии, что на переменные наложены соответствующие ограничения.
Рис.7.4.Табличное представление задачи в Excel
Ответы
1. Оптимальный план перевозок найденный «Поиском решения», при котором будут обеспечены минимальные транспортные издержки, следующий:
из карьера № 1 доставляется 210 т на ЖБИ № 3;
из карьера № 2 доставляется 110 т на ЖБИ № 3;
из карьера № 3 доставляется 230 т на ЖБИ № 1;
из карьера № 4 доставляется 70 т на завод ЖБИ № 1 и 290 т на завод ЖБИ № 2.
2. Невостребованными окажутся 60т песка на карьере № 2 и 40т песка на карьере № 3.
3. Минимальные совокупные транспортные издержки при оптимальном плане перевозок составят 5240 у.е.