Классическая транспортная задача

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

Классическая транспортная задача — это транспортная задача оптимизации перевозок в классической постановке.

Содержание

[править] Постановка задачи

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

ТЗ01.JPG,

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

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

ТЗ3.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 ТЗ15.JPG ТЗ14.JPG

[править] Решение методом потенциалов

ТЗ21.JPG ТЗ22.JPG ТЗ24.JPG

[править] Другие задачи

[править] Ссылки

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


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты