Постановка транспортной задачи

Транспортная модель используется при разработке плана перевозок одного вида продукции из нескольких пунктов отправления в пункты назначения [3]. При построении модели используются:

1) величины, характеризующие объем производства в каждом исходном пункте и спрос в каждом пункте назначения;

2) стоимость перевозки единицы продукции из каждого исходного пункта в каждый пункт назначения.

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

Обозначим количество продукции, производимой в пункте i, через ; количество продукции, потребляемой в пункте j, – через ; стоимость перевозки единицы продукции из i в j – через ; через – количество продукции, перевозимой из исходного пункта в пункт назначения. Тогда задача линейного программирования в общем виде формулируется следующим образом: минимизировать

(1.10)

при ограничениях

, ; (1.11)

, . (1.12)

Из представленной модели видно, что суммарный объем производства равен суммарному спросу. Такая модель называется сбалансированной транспортной моделью.

Задача 1.Заводы автомобильной фирмы расположены в трех городах: Г1, Г2 и Г3. Основные центры распределения (магазины) расположены в городах Р1 и Р2. Объемы производства указанных трех заводов равняются 1000, 1500 и 1200 автомобилей ежеквартально.

Величины квартального спроса в центрах распределения составляют соответственно 2300 и 1400 автомобилей. Стоимости перевозки одного автомобиля между заводами и центрами распределения приведены в табл. 1.1.

Таблица 1.1

	Р1	Р2
Г1
Г2
Г3

Поскольку суммарный объем производства автомобилей (1000+1500+1200=3700) равен суммарному спросу (2300+1400=3700), данная модель является сбалансированной транспортной моделью, и соответствующая задача линейного программирования с ограничениями в виде равенств формулируется следующим образом: минимизировать

при ограничениях

;

;

;

;

;

; ; .

Таблица 1.2

	Магазин 1	Магазин 2	Объем производства
Завод 1
Завод 2
Завод 3
Спрос

Более компактный способ представления транспортной модели связан с использованием транспортной таблицы. Транспортная таблица (табл. 1.2) имеет вид матрицы, в которой строки соответствуют исходным пунктам, а столбцы – пунктам назначения. В правом верхнем углу каждой ячейки транспортной таблицы (i, j) расположены коэффициенты стоимости .

Задача 2.Изменим условия задачи 1, предположив, что завод 2 производит не 1500, а 1300 автомобилей (табл. 1.3). Это приведет к дисбалансу, поскольку суммарный объем производства (3500) не равен суммарному спросу (3700) .

Таблица 1.3

	Магазин 1	Магазин 2	Объем производства
Завод 1
Завод 2
Завод 3
Фиктивный завод
Спрос

В этом случае необходимо видоизменить транспортную модель таким образом, чтобы недостаток автомобилей (3700 – 3500=200) оптимально распределялся между центрами распределения. Поскольку спрос превышает объем производства, можно ввести дополнительный фиктивный завод ФЗ с производительностью 200 автомобилей.

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

Задача 3.Вновь изменим условия задачи 1, предположив, что объем производства превышает спрос из-за падения спроса на автомобили в магазине 1 до 1900 штук. В табл. 1.4 представлена модель с фиктивным центром распределения:

Таблица 1.4

	Магазин 1	Магазин 2	Фиктивный магазин ФМ	Объем производства
Завод 1
Завод 2
Завод 3
Спрос

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

Задача 4.Теперь рассмотрим пример, когда нужно перевезти несколько видов продукции, т.е. многопродуктовую транспортную модель. Пусть фирма производит автомобили четырех различных марок, которые для простоты будем обозначать как М1, М2, М3 и М4. Завод 1 производит автомобили марок М3 и М4; завод 2 – автомобили М1, М2 и М4; завод 3 – автомобили М1 и М2.

Таблица 1.5

	М1	М2	М3	М4	Всего
Объем производства
Завод 1
Завод 2
Завод 3
Спрос
Магазин 1
Магазин 2

В табл. 1.5. приведены данные по объемам выпуска разных заводов и по величине спроса в центрах распределения для автомобилей каждой марки.

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

Таблица 1.6

	Магазин 1	Магазин 2	Объем
М1	М2	М3	М4	М1	М2	М3	М4
Завод 1	М3	М	М		М	М	М		М
Завод 1	М4	М	М	М		М	М	М
Завод 2	М1		М	М	М		М	М	М
Завод 2	М2	М		М	М	М		М	М
Завод 2	М4	М	М	М		М	М	М
Завод 3	М1		М	М	М		М	М	М
Завод 3	М2	М		М	М	М		М	М
Спрос

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

Заметим, что некоторые маршруты в таблице недопустимы, поскольку автомобили различных марок не могут заменять друг друга. Этим маршрутам в таблице соответствует очень высокая стоимость перевозки М (например, 999).