Трёхиндексная транспортная задача — различия между версиями
Строка 1: | Строка 1: | ||
[[файл:ТТЗ.JPG|thumb|300|[[Математическая модель]] ТТЗ]] | [[файл:ТТЗ.JPG|thumb|300|[[Математическая модель]] ТТЗ]] | ||
+ | '''Трёхиндексная транспортная задача (ТТЗ)''' – это многопродуктовая транспортная задача оптимизации перевозок, являющаяся трёхмерным обобщением транспортной задачи. | ||
== Постановка задачи ТТЗ == | == Постановка задачи ТТЗ == | ||
Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''', '''n''' потребителей '''(B1,B2,…,Bn)''' и '''k''' различных продуктов '''(C1,C2,…,Ck)'''. Пусть заданы объёмы поставок '''a<sub>it</sub>''' продукта '''Ct''' поставщиком '''Ai''', объёмы потребностей '''b<sub>jt</sub>''' в продукте '''Ct''' у потребителя '''Bj''', объёмы перевозок '''c<sub>ij</sub>''' от поставщика '''Ai''' к потребителю '''Bj'''. Пусть известны транспортные расходы '''d<sub>ijt</sub>''' на перевозку единицы продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТТЗ) формулируется следующим образом: | Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''', '''n''' потребителей '''(B1,B2,…,Bn)''' и '''k''' различных продуктов '''(C1,C2,…,Ck)'''. Пусть заданы объёмы поставок '''a<sub>it</sub>''' продукта '''Ct''' поставщиком '''Ai''', объёмы потребностей '''b<sub>jt</sub>''' в продукте '''Ct''' у потребителя '''Bj''', объёмы перевозок '''c<sub>ij</sub>''' от поставщика '''Ai''' к потребителю '''Bj'''. Пусть известны транспортные расходы '''d<sub>ijt</sub>''' на перевозку единицы продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТТЗ) формулируется следующим образом: | ||
Строка 6: | Строка 7: | ||
где '''x<sub>ijt</sub>''' - объём перевозок продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''. | где '''x<sub>ijt</sub>''' - объём перевозок продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''. | ||
− | |||
== Условия разрешимости == | == Условия разрешимости == | ||
Для разрешимости задачи необходимо выполнение условий баланса: | Для разрешимости задачи необходимо выполнение условий баланса: | ||
Строка 12: | Строка 12: | ||
т.е. необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему. | т.е. необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему. | ||
− | |||
== Метод решения ТТЗ == | == Метод решения ТТЗ == | ||
Трёхиндексная [[Классическая транспортная задача|транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. | Трёхиндексная [[Классическая транспортная задача|транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай. | ||
Пусть имеется допустимое опорное решение ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид. | Пусть имеется допустимое опорное решение ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид. | ||
− | |||
=== Метод потенциалов === | === Метод потенциалов === | ||
'''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''. | '''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''. | ||
Строка 32: | Строка 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]] | ||
− | |||
=== Допустимое решение === | === Допустимое решение === | ||
Допустимое решение '''X''' в транспортной таблице | Допустимое решение '''X''' в транспортной таблице | ||
Строка 41: | Строка 37: | ||
[[файл:ТТЗ11.JPG]] | [[файл:ТТЗ11.JPG]] | ||
[[файл:ТТЗ10.JPG]] | [[файл:ТТЗ10.JPG]] | ||
− | |||
=== Решение методом потенциалов === | === Решение методом потенциалов === | ||
[[файл:ТТЗ12.JPG]] | [[файл:ТТЗ12.JPG]] | ||
[[файл:ТТЗ13.JPG]] | [[файл:ТТЗ13.JPG]] | ||
[[файл:ТТЗ14.JPG]] | [[файл:ТТЗ14.JPG]] | ||
− | |||
== Другие задачи: == | == Другие задачи: == | ||
*[[Каноническая задача]]; | *[[Каноническая задача]]; | ||
Строка 52: | Строка 46: | ||
*[[Общая прямая задача линейного программирования]]; | *[[Общая прямая задача линейного программирования]]; | ||
*[[Общая двойственная задача линейного программирования]]; | *[[Общая двойственная задача линейного программирования]]; | ||
− | *[[ | + | *[[Транспортная задача]]; |
*[[Распределительная задача]]; | *[[Распределительная задача]]; | ||
*[[Задача о назначениях]]; | *[[Задача о назначениях]]; | ||
Строка 58: | Строка 52: | ||
*[[Задача целочисленного программирования]]; | *[[Задача целочисленного программирования]]; | ||
*[[Задача о рюкзаке]]. | *[[Задача о рюкзаке]]. | ||
− | |||
== Ссылки == | == Ссылки == | ||
* Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313 | * Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313 |
Версия 18:54, 13 января 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 в транспортной таблице
Решение методом потенциалов
Другие задачи:
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки
- Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
- Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.
- Участник:Logic-samara