Транспортная задача

Материал из ALL
Перейти к: навигация, поиск

Транспортная задача – это задача оптимизации перевозок однородных грузов от поставщиков к потребителям.

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

Пусть имеется m поставщиков (A1,A2,…,Am) и n потребителей (B1,B2,…,Bn) однородного продукта. Пусть заданы объёмы поставок ai продукта поставщиком Ai и объёмы потребностей bj в продукте у потребителя Bj. Пусть известны транспортные расходы cij на перевозку единицы продукта от поставщика Ai к потребителю Bj и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая транспортная задача (ТЗ) формулируется следующим образом:

ТЗ01.JPG,

где xij - объём перевозок продукта от поставщика Ai к потребителю Bj.

Транспортную задачу можно представить в виде таблицы

ТЗ03.JPG.

Условия разрешимости

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

ТЗ02.JPG,

т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём.

Метод решения

Необходимо найти начальное опорное решение, например, методом северо-западного угла.

Затем транспортная задача решается методом потенциалов.

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

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

1.Удовлетворяем потребности потребителей (bj>0) за счёт поставщиков (ai>0), т.е. назначаем соответствующие перевозки по формулам: xij=min(ai,bj), ai=ai-xij, bj=bj-xij.

2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности.

Метод потенциалов

1.Берём решение Xmxn и базис Zmxn, найденные, например, с помощью алгоритма северо-западного угла.

2.Определяем значение целевой функции L=ΣΣcijxij и базис опорного решения Bo={(i,j)|zij=1}.

3.Определяем оценку Δo и элемент (io,jo) с помощью алгоритма расчёта потенциалов и оценок оптимальности.

4.Проверяем решение на оптимальность. Если Δo=0, то решение Xmxn - оптимальное и конец работы.

5.Определяем оценку Δx, элемент (ix,jx) и новое опорное решение Xmxn с помощью алгоритма перераспределения перевозок.

6.Определяем новое значение целевой функции L=L-ΔoΔx и новый базис Bo=Bo\(ix,jx)U(io,jo). Переходим к пункту 3.

Пример ТЗ

ТЗ10.JPG

Нахождение допустимого решения

ТЗ11.JPG ТЗ12.JPG ТЗ13.JPG ТЗ14.JPG

Решение методом потенциалов

ТЗ21.JPG ТЗ22.JPG ТЗ23.JPG

Задачи транспортного типа:

Другие задачи:

Ссылки

  • Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
  • Участник:Logic-samara