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

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

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

Содержание

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

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

[math]L(X) = \sum\limits_{i=1}^m\sum\limits_{j=1}^n c_{ij}x_{ij} \rightarrow \min[/math]
[math]\begin{cases}\sum\limits_{j=1}^n x_{ij}=a_i, \ \forall i\in N_m \\ \sum\limits_{i=1}^m x_{ij}=b_j, \ \forall j\in N_n \\ x_{ij} \ge 0, \forall (i,j)\in N_m\times N_n\end{cases}[/math]

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

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

ТЗ3.JPG.

[править] Условия разрешимости

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

[math]\sum\limits_{i=1}^m a_i = \sum\limits_{j=1}^n b_j[/math]

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

[править] Метод решения

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

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

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

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

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


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

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