Трёхиндексная транспортная задача

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

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

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

,

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

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

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

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

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

Трёхиндексная транспортная задача решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. Пусть имеется допустимое опорное решение ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид.

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

1.Берём допустимое опорное решение Xmxnxk и базис Zmxnxk.

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

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

4.Проверяем решение на оптимальность. Если Δo=0, то решение Xmxnxk - оптимальное и конец работы, иначе определяем E⁺={(i,j,t)|Δ_ijt>=0}.

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

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

7.Переопределяем множество E⁺=E⁺\(i_o,j_o,t_o) и определяем новую оценку Δo и элемент (i_o,j_o,t_o). Если новый элемент (i_o,j_o,t_o) есть, то переходим к пункту 5, иначе конец работы.

Пример ТТЗ

Допустимое решение

Допустимое решение X в транспортной таблице

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

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

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

Ссылки

• Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313
• Кривопалов Ю.А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
• Участник:Logic-samara