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

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

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

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

Пусть имеется 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.
• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.