Транспортная задача линейного программирования

4.1. Постановки задачи

4.1.1. Закрытая транспортная модель

Некоторый однородный продукт, сосредоточенный у m поставщиков А_i в количестве a_i (i = 1,..., m) единиц соответственно, необходимо доставить n потребителям В_j в количестве b_j (j = 1,..., n) единиц. Известна стоимость с_ij перевозки единицы груза от i-го поставщика к j-му потребителю.

Обозначим через х_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке х_ij единиц груза, то стоимость перевозки составит с_ijx_ij.

Стоимость всего плана перевозок выразится двойной суммой:

.

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть вывезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

.

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

найти минимальное значение линейной функции

(4.1)

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

, i = 1, m (4.2)

4.3)

x_ij ³ 0, i = 1, …, m; j = 1, …, n. (4.4)

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.

(4.5)

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие (4.5), называется закрытой моделью; в противном случае – открытой, а условие (4.5) – условием баланса.

Пример 4.1.

Таблица 4.1.

Bj Ai

Предложение

Спрос

4.1.2. Открытая транспортная модель

Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности

б) суммарные потребности превышают суммарные запасы

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

Найти минимальное значение линейной функции:

при ограничениях
(случай «а»)

Открытая модель решается приведением к закрытой модели.

В случае «а», когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель В_{n + 1}, потребность которого:

.

В случае «б», когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик А_{m + 1}, запасы которого:

Стоимость перевозки единицы груза до фиктивного потребителя полагаем равной:

0, если безразлично у какого из поставщиков останется излишек груза , штрафу за невывоз груза у i-го поставщика

М, если существует запрет на невывоз груза у i-го поставщика

От фиктивного поставщика:

0, если безразлично, какой потребитель недополучит заявленного количества груза

, штрафу за недопоставку j-му потребителю

М, при невозможности недопоставки j-му потребителю.

4.1.3. Транспортная задача с запрещенными перевозками.

Если от поставщика i потребителю j перевозка запрещена, то стоимость перевозки полагается равной М, где М – большое число.

4.1.4. Транспортная задача с ограничением на пропускную способность канала.

В этом случае, модель транспортной задачи имеет следующий вид:

; (4.1)

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

(4.2)

(4.3)

, i = 1, …, m; j = 1, …, n, где (4.4)

-ограничение на пропускную способность «канала»