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

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

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

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

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

ТТЗ.JPG,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример ТТЗ

ТТЗ01.JPG

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

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

ТТЗ11.JPG ТТЗ10.JPG

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

ТТЗ12.JPG ТТЗ13.JPG ТТЗ14.JPG

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

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

Ссылки

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