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

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

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

Содержание

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

Пусть имеется 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). Тогда математическая модель задачи принимает вид:

ТЗПП1.JPG.

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

ТТ.JPG.

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

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

ТЗ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.

Пример ТЗПП

СЗУ10.JPG

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

СЗУ11.JPG СЗУ12.JPG СЗУ13.JPG СЗУ04.JPG

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

МП01.JPG МП02.JPG МП03.JPG МП04.JPG

Другие ТЗПП

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

Ссылки


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты