Изменения
Новая страница: «[[файл:ТТЗ.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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТТЗ) формулируется следующим образом:
[[файл:ТТЗ.JPG]],
где '''x<sub>ijt</sub>''' - объём перевозок продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''.
== Условия разрешимости ==
Для разрешимости задачи необходимо выполнение условий баланса:
[[файл:ТТЗ1.JPG]],
т.е. необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему.
== Метод решения ТТЗ ==
Трёхиндексная [[Классическая транспортная задача|транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай.
Пусть имеется допустимое опорное решение ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид.
=== Метод потенциалов ===
'''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''.
'''2.'''Определяем значение целевой функции '''L=ΣΣΣd<sub>ijt</sub>x<sub>ijt</sub>''' и базис опорного решения '''Bo={(i,j,t)|z<sub>ijt</sub>=1}'''.
'''3.'''Определяем оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' с помощью '''[[Алгоритм расчёта потенциалов для ТТЗ|алгоритма расчёта потенциалов для ТТЗ]]''' (также определяются оценки оптимальности '''Δ<sub>ijt</sub>''').
'''4.'''Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxnxk''' - оптимальное и конец работы, иначе определяем '''E<sup>+</sup>={(i,j,t)|Δ<sub>ijt</sub>>=0}'''.
'''5.'''Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)''' и новое опорное решение '''Xmxnxk''' с помощью '''алгоритма перераспределения перевозок для ТТЗ'''. Если нового допустимого опорного решения нет, то переходим к пункту 7.
'''6.'''Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. Переходим к пункту 3.
'''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, иначе конец работы.
== Пример ТТЗ ==
[[файл:ТТЗ01.JPG]]
=== Допустимое решение ===
Допустимое решение '''X''' в транспортной таблице
[[файл:ТТЗ11.JPG]]
[[файл:ТТЗ10.JPG]]
=== Решение методом потенциалов ===
[[файл:ТТЗ12.JPG]]
[[файл:ТТЗ13.JPG]]
[[файл:ТТЗ14.JPG]]
== Другие задачи: ==
*[[Каноническая задача]];
*[[Производственная задача]];
*[[Общая прямая задача линейного программирования]];
*[[Общая двойственная задача линейного программирования]];
*[[Классическая транспортная задача]];
*[[Распределительная задача]];
*[[Задача о назначениях]];
*[[Транспортная задача с промежуточными пунктами]];
*[[Задача целочисленного программирования]];
*[[Задача о рюкзаке]].
== Ссылки ==
* Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313
* Кривопалов Ю.А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
== Постановка задачи ТТЗ ==
Пусть имеется '''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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТТЗ) формулируется следующим образом:
[[файл:ТТЗ.JPG]],
где '''x<sub>ijt</sub>''' - объём перевозок продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''.
== Условия разрешимости ==
Для разрешимости задачи необходимо выполнение условий баланса:
[[файл:ТТЗ1.JPG]],
т.е. необходимо, чтобы объём поставок каждого продукта равнялся объёму потребностей в нём, чтобы объём поставок каждого поставщика равнялся объёму перевозок от него, чтобы объём потребностей каждого потребителя равнялся объёму перевозок к нему.
== Метод решения ТТЗ ==
Трёхиндексная [[Классическая транспортная задача|транспортная задача]] решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай.
Пусть имеется допустимое опорное решение ТТЗ. Тогда метод потенциалов для ТТЗ принимает вид.
=== Метод потенциалов ===
'''1.'''Берём допустимое опорное решение '''Xmxnxk''' и базис '''Zmxnxk'''.
'''2.'''Определяем значение целевой функции '''L=ΣΣΣd<sub>ijt</sub>x<sub>ijt</sub>''' и базис опорного решения '''Bo={(i,j,t)|z<sub>ijt</sub>=1}'''.
'''3.'''Определяем оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)''' с помощью '''[[Алгоритм расчёта потенциалов для ТТЗ|алгоритма расчёта потенциалов для ТТЗ]]''' (также определяются оценки оптимальности '''Δ<sub>ijt</sub>''').
'''4.'''Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxnxk''' - оптимальное и конец работы, иначе определяем '''E<sup>+</sup>={(i,j,t)|Δ<sub>ijt</sub>>=0}'''.
'''5.'''Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)''' и новое опорное решение '''Xmxnxk''' с помощью '''алгоритма перераспределения перевозок для ТТЗ'''. Если нового допустимого опорного решения нет, то переходим к пункту 7.
'''6.'''Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>,t<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>,t<sub>o</sub>)'''. Переходим к пункту 3.
'''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, иначе конец работы.
== Пример ТТЗ ==
[[файл:ТТЗ01.JPG]]
=== Допустимое решение ===
Допустимое решение '''X''' в транспортной таблице
[[файл:ТТЗ11.JPG]]
[[файл:ТТЗ10.JPG]]
=== Решение методом потенциалов ===
[[файл:ТТЗ12.JPG]]
[[файл:ТТЗ13.JPG]]
[[файл:ТТЗ14.JPG]]
== Другие задачи: ==
*[[Каноническая задача]];
*[[Производственная задача]];
*[[Общая прямая задача линейного программирования]];
*[[Общая двойственная задача линейного программирования]];
*[[Классическая транспортная задача]];
*[[Распределительная задача]];
*[[Задача о назначениях]];
*[[Транспортная задача с промежуточными пунктами]];
*[[Задача целочисленного программирования]];
*[[Задача о рюкзаке]].
== Ссылки ==
* Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313
* Кривопалов Ю.А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990г. деп.№Д08221.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
