Транспортная задача с промежуточными пунктами[править]

Материал из Мегапедии
Перейти к: навигация, поиск
Математическая модель эквивалентной ТЗПП
Математическая модель классической ТЗПП

Транспортная задача с промежуточными пунктами (ТЗПП) – это транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов. ТЗПП позволяет оптимизировать мультимодальные транспортные перевозки.

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

Пусть имеется m поставщиков (A1,A2,…,Am), n потребителей (B1,B2,…,Bn) и k промежуточных пунктов (C1,C2,…,Ck), однородного продукта. Пусть заданы объёмы поставок ai продукта поставщиком Ai, объёмы потребностей bj в продукте у потребителя Bj, объёмы дополнительных потребностей ct в продукте в промежуточном пункте (на складе) Ct, причём если ct<0, то дополнительные потребности являются избытком. Пусть известны транспортные расходы dti на перевозку единицы продукта от поставщика Ai на склад Ct, и транспортные расходы qtj на перевозку единицы продукта со склада Ct к потребителю Bj и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда транспортная задача с промежуточными пунктами формулируется следующим образом:

ТЗПП.JPG,

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

ytj — объём перевозок продукта со склада Ct к потребителю Bj.

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

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

ТЗПП02.JPG,

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

Постановка эквивалентной задачи

Введём новые обозначения:

ТЗПП2.JPG.

Математическая модель эквивалентной задачи принимает следующий вид:

ТЗППэ.JPG.

Условия разрешимости эквивалентной задачи

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

ТЗПП03.JPG,

то есть необходимо, чтобы объём поставок продукта на склады и объём отрицательных поставок со складов (потребностей в продукте) равнялся объёму дополнительных потребностей в продукте на складах. В этом случае транспортная задача с промежуточными пунктами называется закрытой.

Постановка классической задачи

В экономической транспортной системе имеются n конечных пунктов (np поставщиков продукции и n-np потребителей продукции) и m промежуточных пунктов (складов). Продукция перевозится от поставщиков на склады, будем обозначать эти перевозки положительными переменными xij≥0, (i=1,m,j=1,np). А со складов часть продукции перевозится потребителям - их обозначим отрицательными переменными xij≤0, (i=1,m,j=np+1,n). Объёмы поставок поставщиков обозначим положительными числами bj>0, (j=1,np), объёмы потребностей потребителей обозначим отрицательными числами bj<0, (j=np+1,n). Для упрощения метода решения задачи, будем считать, что склады имеющие дополнительные (внутренние) потребности продукции расположены вначале (в любом порядке) списка, а склады имеющие излишки продукции или нулевые остатки – в конце (в любом порядке). Если склад имеет дополнительные потребности продукции, то обозначим их положительными числами ai>0, (i=1,mp). Если склад имеет излишки продукции или нулевые остатки, то обозначим их числами ai≤0, (i=mp+1,m). Транспортные тарифы на перевозку единицы продукции от поставщика на склад выразим положительными числами cij>0, (i=1,m,j=1,np), транспортные тарифы на перевозку со склада к потребителю выразим отрицательными числами cij<0, (i=1,m,j=np+1,n). Тогда математическая модель задачи принимает вид:

ТЗППк.JPG.

Классическая транспортная задача с промежуточными пунктами может быть представлена в виде таблицы

ТЗПП0.png.

Условия разрешимости классической задачи

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

ТЗ02.JPG,

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

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

Необходимо найти начальное опорное решение, например, методом северо-западного угла для ТЗПП.

Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения ТЗ, модифицированным с учётом отрицательных перевозок.

Метод северо-западного угла

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

1.Сначала удовлетворяем дополнительные потребности складов (ai>0) за счёт поставщиков (bj>0), т.е. назначаем соответствующие положительные перевозки по формулам: xij=min(ai,bj), ai=ai-xij, bj=bj-xij.

2.Затем распределяем остатки грузов от поставщиков (bj>0) на последний используемый склад, т.е. начиная с последней заполненной строки по формулам: xij=bj, ai=ai-xij, bj=0.

3.Наконец, удовлетворяем потребности потребителей (bj<0), т.е. назначаем соответствующие отрицательные перевозки по формулам: xij=max(ai,bj), aij=ai-xij, bj=bj-xij.

Метод северо-западного угла реализуется с помощью алгоритма северо-западного угла для ТЗПП.

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

1.Берём решение Xmxn и базис Zmxn, найденные с помощью алгоритма северо-западного угла для ТЗПП.

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

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

4.Проверяем решение на оптимальность. Если Δo=0, то решение Xmxn - оптимальное и конец работы.

5.Определяем оценку Δx, элемент (ix,jx) и новое опорное решение Xmxn с помощью алгоритма перераспределения перевозок для ТЗПП.

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

Примеры ТЗПП:

Пример 1

ТЗПП001.png

Транспортная таблица

ТЗПП011.png

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

МП000.pngМП010.png

Решение методом потенциалов

МП001.pngМП011.png

МП002.pngМП012.png

МП003.pngМП013.png

Пример 2

ТЗПП002.png

Транспортная таблица

ТЗПП012.png

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

МП200.pngМП210.png

Решение методом потенциалов

МП201.pngМП211.png

МП202.pngМП212.png

МП203.pngМП213.png

МП204.pngМП214.png

Пример 3

ТЗПП01.png

Транспортная таблица

СЗУ00.png

Нахождение допустимого решения

СЗУ11.pngСЗУ01.png

СЗУ12.pngСЗУ02.png

СЗУ13.pngСЗУ03.png

СЗУ14.pngСЗУ04.png

СЗУ15.pngСЗУ05.png

СЗУ16.pngСЗУ06.png

СЗУ17.pngСЗУ07.png

СЗУ18.pngСЗУ08.png

СЗУ19.pngСЗУ09.png

СЗУ20.pngСЗУ10.png

СЗУ21.pngСЗУ22.png

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

МП00.png МП10.png

Решение методом потенциалов

МП01.pngМП11.png

МП02.pngМП12.png

МП03.pngМП13.png

МП04.pngМП14.png

МП05.pngМП15.png

МП06.pngМП16.png

МП07.pngМП17.png

МП08.pngМП18.png

МП09.pngМП19.png

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

Ссылки