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

Математическая модель ТЗ

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

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

Пусть имеется m поставщиков (A₁, A₂, …, A_m) и n потребителей (B₁, B₂, …, B_n) однородного продукта. Пусть заданы объёмы поставок a_i продукта поставщиком A_i и объёмы потребностей b_j в продукте у потребителя B_j. Пусть известны транспортные расходы c_ij на перевозку единицы продукта от поставщика A_i к потребителю B_j и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая транспортная задача (ТЗ) формулируется следующим образом:

$L(X)=\sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min$

${\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}\geq 0,\forall (i,j)\in N_{m}\times N_{n}\end{cases}}$

где x_ij — объём перевозок продукта от поставщика A_i к потребителю B_j.

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

.

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

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

$\sum \limits _{i=1}^{m}a_{i}=\sum \limits _{j=1}^{n}b_{j}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Каноническая задача;
• Производственная задача;
• Общая прямая задача линейного программирования;
• Общая двойственная задача линейного программирования;
• Распределительная задача;
• Задача о назначениях;
• Транспортная задача с промежуточными пунктами;
• Трёхиндексная транспортная задача;
• Задача целочисленного программирования;
• Задача о рюкзаке.

Ссылки

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