Незамкнутая транспортная задача с избытком

Компания, занимающаяся добычей песка и доставкой его собственным транспортом к потребителям, разрабатывает 4 песчаных карьера. Недельная производительность карьеров 210, 170, 270 и 360 тонн. Песок направляется на три завода железобетонных изделий (ЖБИ). Недельные потребности заводов в песке составляют 300, 290 и 320 тонн. Транспортные затраты c_ij; (в условных денежных единицах — у.е.), связанные с доставкой 1 тонны песка от карьеров до заводов, известны и приведены в табл. 7.3.

Табл.7.3.

Требуется:

1) составить такой план перевозок песка из карьеров на заводы, при котором совокупные транспортные издержки будут минимальны;

2) выяснить, какое количество песка и на каких карьерах окажется невостребованным;

3) установить размер минимальных транспортных издержек.

Решение

Потребности заводов в песке (спрос) составляют 300 + 290 + 320 = = 910 т, в то время как мощности карьеров позволяют добывать 210 + 170 + 270 + 360 = 1010 т. Предложение превышает спрос на 100 т. Следовательно, эта задача незамкнутая (п. 7.1).

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

Табл.7.4.

Обозначим через х_ij количество песка (в тоннах), которое будет вывезено из карьера i (i = 1, 2, 3, 4) и доставлено на завод j (j = 1,2,3,4). Тогда искомый план перевозок, представленный в табл. 7.5., состоит из 16 управляемых переменных.

Табл.7.5.

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

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

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

Рис.7.4.Табличное представление задачи в Excel