Трёхиндексная транспортная задача — различия между версиями
м (Защищена страница «Трёхиндексная транспортная задача» ([Редактирование=Разрешено только автоподтверждённым участникам] (бессрочно) […) |
|||
Строка 50: | Строка 50: | ||
*[[Задача о назначениях]]; | *[[Задача о назначениях]]; | ||
*[[Транспортная задача с промежуточными пунктами]]; | *[[Транспортная задача с промежуточными пунктами]]; | ||
+ | *[[Трёхиндексная транспортная задача]]; | ||
*[[Задача целочисленного программирования]]; | *[[Задача целочисленного программирования]]; | ||
*[[Задача о рюкзаке]]. | *[[Задача о рюкзаке]]. |
Версия 17:54, 2 февраля 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