Трёхиндексная транспортная задача с аксиальными суммами

Математическая модель ТТЗАС

Трёхиндексная транспортная задача с аксиальными суммами (ТТЗАС) — ТТЗ с аксиальными суммами — это транспортная задача оптимизации перевозок однородных грузов для различных типов транспорта, являющаяся трёхмерным обобщением транспортной задачи.

Постановка задачи ТТЗАС

Пусть имеется m поставщиков (A1,A2,…,Am), n потребителей (B1,B2,…,Bn) и k различных видов транспорта (C1,C2,…,Ck). Пусть заданы объёмы поставок грузов a_i поставщиком Ai, объёмы потребностей грузов b_j у потребителя Bj, объёмы перевозок грузов c_t транспортом типа Ct. Пусть известны транспортные расходы d_ijt на перевозку единицы груза от поставщика Ai к потребителю Bj транспортом типа Ct и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда трёхиндексная транспортная задача с аксиальными суммами (ТТЗАС) формулируется следующим образом ([1],с.312):

$L(X)=\sum _{i=1}^{m}\sum _{j=1}^{n}\sum _{t=1}^{k}d_{ijt}x_{ijt}\rightarrow \min$

${\begin{cases}\sum \limits _{j=1}^{n}\sum \limits _{t=1}^{k}x_{ijt}=a_{i},\forall i\in N_{m}\\\sum \limits _{i=1}^{m}\sum \limits _{t=1}^{k}x_{ijt}=b_{j},\forall j\in N_{n}\\\sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}x_{ijt}=c_{t},\forall t\in N_{k}\\x_{ijt}\geq 0,\forall (i,j,t)\in N_{m}\times N_{n}\times N_{k}\end{cases}}$ ,

где x_ijt — объём перевозок груза от поставщика Ai к потребителю Bj транспортом типа Ct.

Условия разрешимости

Для разрешимости задачи необходимо выполнение условий баланса:

$\sum _{i=1}^{m}a_{i}=\sum _{j=1}^{n}b_{j}=\sum _{t=1}^{k}c_{t}$ ,

то есть необходимо, чтобы общий объём поставок груза равнялся общему объёму потребностей в нём и равнялся общему объёму перевозок всеми типами транспорта.

Метод решения ТТЗАС

Трёхиндексная транспортная задача с аксиальными суммами решается методом потенциалов для решения транспортной задачи обобщённым на трёхмерный случай (по аналогии с методом потенциалов для ТТЗ) с учётом особенностей задачи. Пусть имеется допустимое опорное решение ТТЗАС. Начальное допустимое опорное решение может быть получено с помощью алгоритма трёхгранного угла для ТТЗАС. Базис ТТЗАС содержит m+n+k-2 базисных элементов. Тогда метод потенциалов для ТТЗАС принимает вид.

Метод потенциалов

1. Берём допустимое опорное решение Xmxnxk и базис Zmxnxk.

2. Определяем значение целевой функции L=ΣΣΣd_ijtx_ijt и базис опорного решения Bo={(i, j, t)|z_ijt=1}.

3. Определяем оценку Δo и элемент (i_o, j_o, t_o) с помощью алгоритма расчёта потенциалов для ТТЗАС.

4. Проверяем решение на оптимальность. Если Δo=0, то решение Xmxnxk — оптимальное и конец работы, иначе определяем E⁺={(i, j,t)|Δ_ijt≥0}\Bo.

5. Определяем оценку Δx, элемент (i_x, j_x, t_x) и новое опорное решение Xmxnxk с помощью алгоритма перераспределения перевозок для ТТЗАС. Если нового допустимого опорного решения нет, то переходим к пункту 7.

6. Определяем новое значение целевой функции L=L-ΔoΔx и новый базис Bo=Bo\(i_x, j_x, t_x)U(i_o, j_o, t_o). Переходим к пункту 3.

7. Переопределяем множество E⁺=E⁺\(i_o, j_o, t_o) и определяем новую оценку Δo и элемент (i_o, j_o, t_o) из множества E⁺.

Если новый элемент (i_o,j_o,t_o) есть, то переходим к пункту 5, иначе конец работы.

Пример

Транспортная задача

Допустимое решение

Оптимальное решение

Другие задачи:

1. Транспортная задача;
2. Распределительная задача;
3. Задача о назначениях;
4. Транспортная задача с промежуточными пунктами;
5. Транспортная задача с промежуточными пунктами с запретами;
6. Транспортная задача с промежуточными пунктами и ограничением по транзиту;
7. Открытая транспортная задача с промежуточными пунктами;
8. Открытая транспортная задача с промежуточными пунктами 1;
9. Открытая транспортная задача с промежуточными пунктами 2;
10. Открытая транспортная задача с промежуточными пунктами 3;
11. Открытая транспортная задача с промежуточными пунктами 4;
12. Трёхиндексная транспортная задача;
13. Трёхиндексная транспортная задача с аксиальными суммами;
14. Трёхиндексная транспортная задача с промежуточными пунктами.

Литература

• Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, с.344.
• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. М.,ВИМИ, 1990 г. деп.№Д08221.
• Кривопалов Ю. А. Метод потенциалов для решения трёхиндексной транспортной задачи. Сборник ХI конференции «Наука. Творчество» 2015, Самара, Т.1,стр.39.

Ссылки

• Участник:Logic-samara