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

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

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

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

Пусть имеется 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.

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

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

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

Постановка вспомогательной задачи

Сформулируем задачу, таким образом, чтобы её оптимальное решение при x_m+1n+1k+1=0 совпадало с оптимальным решением исходной. Для построения вспомогательной задачи введём новые обозначения:

M — это достаточно большое положительное число.

; ; ; .

Математическая модель вспомогательной задачи принимает следующий вид:

.

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

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

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

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, иначе конец работы.

Пример ТТЗ

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

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

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

• Транспортная задача;
• Распределительная задача;
• Задача о назначениях;
• Транспортная задача с промежуточными пунктами;
• Транспортная задача с промежуточными пунктами с запретами;
• Транспортная задача с промежуточными пунктами и ограничением по транзиту;
• Открытая транспортная задача с промежуточными пунктами 1;
• Открытая транспортная задача с промежуточными пунктами 2;
• Открытая транспортная задача с промежуточными пунктами 3;
• Открытая транспортная задача с промежуточными пунктами 4;
• Трёхиндексная транспортная задача.

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

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

Ссылки

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