Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

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

Материал из Циклопедии
(перенаправлено с «ТТЗ»)
Перейти к навигации Перейти к поиску

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

Постановка задачи ТТЗ[править]

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

Допустимое решение[править]

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

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

Решение методом потенциалов[править]

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

Другие задачи:[править]


Литература[править]

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

Транспортная задача (классическая) • Решение симплекс-методомРешение в ExcelТранспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента)

Начальное решение

Метод северо-западного углаМетод минимальных тарифовМетод Фогеля‎

Вырожденные случаи

Вырожденность в ТЗАцикличность в ТЗ

Ссылки[править]