Постановка задачи и ее математическая модель

Пусть имеется однородный груз, сосредотачиваемый у m поставщиков  в количестве , i=1…m, который необходимо доставить n потребителям  в количестве  единиц, k=1…n. Известна стоимость  перевозки единицы груза от i -го поставщика к k -му потребителю, требуется составить план перевозок, позволяющий вывезти весь груз, полностью удовлетворить заявки потребителей, и имеющий минимальную стоимость.

Обозначим через  количество единиц груза, запланированных к перевозке от i -го поставщика к k -му потребителю, тогда целевая функция будет иметь вид (1):

,                         (1)

Отграничения можно записать следующим способом:

  i =()                                 (2)

  i =()                                   (3)

Необходимым и достаточным условием решения задачи является уравнение баланса (4)

                                              (4)

Транспортная задача, в которой объем запасов груза и количество заявок потребителей равны, т.е. выполняется условие (4) называется закрытой.

Теорема 1. Любая закрытая транспортная задача имеет решение.

Условие задачи (1) – (4) обычно записывается в виде транспортной таблицы, т.к. транспортная задача является задачей линейного программирования, то решение ее состоит из опорного и оптимального плана

							запасы
			…		…
	…	…		…	…	…	…
	…	…		…	…	…	…
			…		…
потребности			…		…

 

§2. Построение опорного плана

Теорема 2. Опорное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонентов – занятых клеток таблицы, соответствующих объему перевозок .

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

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

1. Сумма перевозок в каждой строке таблицы равна запасу , а в данной строке  .                                           (6)

2. Сумма перевозок в каждом столбце равна соответствующему столбцу заявок (7):

  k =                                   (7)

Опорный план называется вырожденным, если число ненулевых перевозок (количество занятых клеток таблицы) меньше условия m+n-1

Невырожденный опорный план – если число ненулевых перевозок будет равно S=m+n-1.

При переходе от вырожденного опорного плана к невырожденному в транспортную таблицу записываются нули, обычно в клетках с наименьшей стоимостью. Записывают так, чтобы количество занятых клеток было равно m+n-1.

Решение транспортной задачи начинается с определения опорного плана. Для его нахождения существуют следующие способы:

· Метод северо-западного угла;

· Способ линейной стоимости по строке/столбцу и линейной стоимости таблицы;

· Метод двойственного предпочтения.