Трёхиндексная транспортная задача
Трёхиндексная транспортная задача (ТТЗ) — это многопродуктовая транспортная задача оптимизации перевозок, являющаяся трёхмерным обобщением транспортной задачи.
Постановка задачи ТТЗ[править]
Пусть имеется 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 и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная транспортная задача (ТТЗ) формулируется следующим образом:
где xijt — объём перевозок продукта Ct от поставщика Ai к потребителю Bj.
Условия разрешимости[править]
Для разрешимости задачи необходимо выполнение условий баланса:
,
то есть необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему.
Метод решения ТТЗ[править]
Трёхиндексная транспортная задача решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. Пусть имеется допустимое опорное решение ТТЗ. Начальное допустимое опорное решение может быть получено с помощью алгоритма минимального элемента для ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид.
Метод потенциалов[править]
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, иначе конец работы.
Пример ТТЗ[править]
Допустимое решение[править]
Допустимое решение X в транспортной таблице
Решение методом потенциалов[править]
Другие задачи[править]
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Классическая транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Литература[править]
- Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990 г. деп.№Д08221.
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.
| ||||
Транспортная задача | Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача | |||
---|---|---|---|---|
Начальное решение | Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля | |||
Вырожденные случаи | Вырожденность в ТЗ • Ацикличность в ТЗ |