Трёхиндексная транспортная задача — различия между версиями
Строка 14: | Строка 14: | ||
== Метод решения ТТЗ == | == Метод решения ТТЗ == | ||
Трёхиндексная [[Классическая транспортная задача|транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. | Трёхиндексная [[Классическая транспортная задача|транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. | ||
− | Пусть имеется допустимое опорное решение ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид. | + | Пусть имеется допустимое опорное решение ТТЗ. Начальное допустимое опорное решение может быть получено с помощью '''[[Алгоритм минимального элемента для ТТЗ|алгоритма минимального элемента для ТТЗ]]'''. Тогда метод потенциалов для ТТЗ принимает вид. |
=== Метод потенциалов === | === Метод потенциалов === | ||
'''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''. | '''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''. | ||
Строка 30: | Строка 30: | ||
'''7.'''Переопределяем множество '''E<sup>+</sup>=E<sup>+</sup>\(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' и определяем новую оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. | '''7.'''Переопределяем множество '''E<sup>+</sup>=E<sup>+</sup>\(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' и определяем новую оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. | ||
Если новый элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' есть, то переходим к пункту 5, иначе конец работы. | Если новый элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' есть, то переходим к пункту 5, иначе конец работы. | ||
− | |||
− | |||
== Пример ТТЗ == | == Пример ТТЗ == | ||
[[файл:ТТЗ01.JPG]] | [[файл:ТТЗ01.JPG]] |
Версия 12:38, 29 сентября 2016
Трёхиндексная транспортная задача (ТТЗ) – это многопродуктовая транспортная задача оптимизации перевозок, являющаяся трёхмерным обобщением транспортной задачи.
Содержание
Постановка задачи ТТЗ
Пусть имеется 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 в транспортной таблице
Решение методом потенциалов
Задачи транспортного типа:
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Транспортная задача с промежуточными пунктами с запретами;
- Транспортная задача с промежуточными пунктами и ограничением по транзиту;
- Открытая транспортная задача с промежуточными пунктами 1;
- Открытая транспортная задача с промежуточными пунктами 2;
- Открытая транспортная задача с промежуточными пунктами 3;
- Открытая транспортная задача с промежуточными пунктами 4;
- Трёхиндексная транспортная задача.
Другие задачи:
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Задачи транспортного типа;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки
- Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.
- Участник:Logic-samara