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

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

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

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

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

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

.

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

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

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

.

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

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

; (6.1)

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

; (6.2)

(6.3)

Xij ³ 0, i = 1,…, m; j = 1,…, n. (6.4)

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

. (6.5)

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

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

;

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

.

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

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

.

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

(случай «а»)

(случай «б»)

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

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

.

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

.

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

Транспортная задача имеет n + m уравнений с mn неизвестными.

Матрицу Х = (хij)m, n, удовлетворяющую условиям (6.2) – (6.4), называют планом перевозок транспортной задачи (хij-перевозками).

План Х*, при котором целевая функция (6.1) обращается в минимум, называется Оптимальным.

Теорема 6.1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса:

.

План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов (i = 1... m, j = 1… n), где – векторы при переменных хij (i = 1… m, j = 1… n) в матрице системы ограничений (6.2) – (6.4).

Теорема 6.2. Существует план, содержащий не более m + n – 1 положительных перевозок, при этом система векторов , соответствующая таким перевозкам (хij > 0), линейно независима.

Таким образом, опорный план транспортной задачи содержит m + n – 1 положительных перевозок. Если менее (m + n – 1) компонент оперного плана положительны, то он называется вырожденным. Дадим другое определение опорного плана.

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

< Предыдущая		Следующая >