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

Материал из ALL
Перейти к: навигация, поиск
(Новая страница: «[[Математическая модель ТЗПП]] файл:ТЗППэ.JPG|thumb|300|Математическая мод…»)
 
Строка 109: Строка 109:
 
*[[Общая прямая задача линейного программирования]];
 
*[[Общая прямая задача линейного программирования]];
 
*[[Общая двойственная задача линейного программирования]];
 
*[[Общая двойственная задача линейного программирования]];
*[[Классическая транспортная задача]];
+
*[[Транспортная задача]];
 
*[[Распределительная задача]];
 
*[[Распределительная задача]];
 
*[[Задача о назначениях]];
 
*[[Задача о назначениях]];

Версия 10:39, 15 ноября 2015

Математическая модель эквивалентной ТЗПП
Математическая модель классической ТЗПП

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

Пусть имеется 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

Другие ТЗПП:

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

Ссылки