Программа транспортной задачи с транзитными пунктами

При решении конкретной задачи оптимизации исследователь прежде всего должен выбрать математический метод, который приводил бы конечным результатам с наименьшими затратами на вычисления или же давал возможность получить наибольший объем информации об искомом решении. Выбор того или иного метода в значительной степени определяется постановкой оптимальной задачи, а также используемой математической моделью объекта оптимизации.

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

- методы исследования функций классического анализа; - методы, основанные на использовании неопределенных множителей Лагранжа; - вариационное исчисление; - динамическое программирование; - принцип максимума; - линейное программирование; - нелинейное программирование.

В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.

Мы остановимся только на исследовании методов оптимизации линейного программирования, поскольку это наиболее распространенные и эффективные методы. И хотя все методы оптимизации линейного программирования достаточно трудоемки, но в свою очередь они очень алгоритмичны. Именно это свойство позволяет исключить ручные расчеты и полностью их автоматизировать (программировать).

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

Минимизировать стоимость выполнения заказов транспортной компании с учетом использования транзитных пунктов.

Целью исследования является классическая пример транспортной задачи, которая является одной из распространенных специальных задач линейного программирования.

Транспортная задача - это задача о более экономичном плане перевозок груза.

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

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

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

Пусть имеется 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 и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда транспортная задача с промежуточными пунктами формулируется следующим образом:

Где xTi -- объем перевозок продукта от поставщика Ai на склад Ct,

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

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

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

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

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

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

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

Склад	Поставщики	Потребители	AI
B1	B2...	BNp	BNp+1	BNp+2...	BN
A1	C11	C12	...	C1np	C1np+1	C1np+2	...	C1n	A1
X11	X12	X1np	X1np+1	X1np+2	X1n
A2	C21	C22	...	C2np	C1np+1	C2np+2	...	C2n	A2
X21	X22	X2np	X2np+1	X2np+2	X2n
...	...	...	...	...	...	...	...	...	...
AM	CM1	CM2	...	CMnp	CMnp+1	CMnp+2	...	CMn	AM
XM1	XM2	XMnp	XMnp+1	XMnp+2	XMn
A4	B1	B2	...	BNp	BNp+1	BNp+2	...	BN

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

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

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

Метод решения транспортной задачи с транзитными пунктами:

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

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

Разработка алгоритма

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

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

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. Наконец, удовлетворяем потребности потребителей (bJIj=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).

Пример работы алгоритма

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

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

Проверим, является ли полученное решение является оптимальным.

Каждому поставщику A I ставим в соответствие некоторое число u I, называемое потенциалом поставщика.

Каждому потребителю B J ставим в соответствие некоторое число v J, называемое потенциалом потребителя.

Для задействованного маршрута, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута.

Значение одного потенциала необходимо задать. Пусть u1 = 0. Последовательно найдем значения потенциалов.

A1B1	V1+u1=1	V1=1-0=1	A2B6	V6+u2=-8	V6=-8-4=-12
A2B1	V1+u2=5	U2=5-1=4	A3B6	V6+u3=-3	U3=-3-(-12)=9
A2B2	V2+u2=2	V2=2-4=-2	A4B6	V6+u4=-1	U4=-1-(-12)=11
A2B3	V3+u2=3	V3=3-4=-1	A4B7	V7+u4=-9	V7=-9-11=-20
A2B4	V4+u2=-7	V4=-7-4=-11	A5B7	V7+u5=-1	U5=-1-(-20)=19
A2B5	V5+u2=-2	V5=-2-4=-6

Найдем оценки незадействованных маршрутов:

A1B2: Д12 = c12 - ( u1 + v2 ) =7-(0-2)=9	A3B7: Д37 = c37 - ( u3 + v7 ) =-2-(9-20)=9
A1B3: Д13 = c13 - ( u1 + v3 ) =4-(0-1)=5	A4B1: Д41 = c41 - ( u4 + v1 ) =1-(11+1)=-11
A1B4: Д14 = c14 - ( u1 + v4 ) =-2-(0-11)=9	A4B2: Д42 = c42 - ( u4 + v2 ) =2-(11-2)=-7
A1B5: Д15 = c15 - ( u1 + v5 ) =-1-(0-6)=5	A4B3: Д43 = c43 - ( u4 + v3 ) =3-(11-1)=-7
A1B6: Д16 = c16 - ( u1 + v6 ) =-3-(0-12)=9	A4B4: Д44 = c44 - ( u4 + v4 ) =-1-(11-11)=-1
A1B7: Д17 = c17 - ( u1 + v7 ) =-4-(0-20)=16	A4B5: Д45 = c45 - ( u4 + v5 ) =-5-(11-6)=-10
A2B7: Д27 = c27 - ( u2 + v7 ) =-1-(4-20)=15	A5B1: Д51 = c51 - ( u5 + v1 ) =7-(19+1)=-13
A3B1: Д31 = c31 - ( u3 + v1 ) =2-(9+1)=-8	A5B2: Д52 = c52 - ( u5 + v2 ) =9-(19-2)=-8
A3B2: Д12 = c32 - ( u3 + v2 ) =4-(9-2)=-3	A5B3: Д53 = c53 - ( u5 + v3 ) =4-(19-1)=-14
A3B3: Д33 = c33 - ( u3 + v3 ) =1-(9-1)=-7	A5B4: Д54 = c54 - ( u5 + v4 ) =-6-(19-11)=-14
A3B4: Д34 = c34 - ( u3 + v4 ) =-2-(9-11)=0	A5B5: Д55 = c55 - ( u5 + v5 ) =-2-(19-6)=-15
A3B5: Д35 = c35 - ( u3 + v5 ) =-1-(9-6)=-4	A5B6: Д56 = c56 - ( u5 + v6 ) =-3-(19-12)=-10

Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки.

Оценка А1В7=16.

Данное преобразование не изменит баланса.

А вот общая стоимость доставки продукции изменится на величину:

-4*(-20)-1*(-20)+ 5*(-20)+8*(-20)-1*(-20)+9*(-20)=16*(-20) ден. ед.

Мы можем заметить, что 16*(-20)= Д17 *(-20)

Следовательно, мы теперь должны прибавить(или вычесть) (-20) к угловым элементам. Исходя из задействованного маршрута, нужно пересчитать ui и vi, а также оценки незадействованных маршрутов.

Общую сумму доставки продукции, для данного решения, легко посчитать.

L = 1870 + Д17 * (-20) = 1870 +16 * (-20) = 1550 ден. ед.

Полученное решение является оптимальным?

Проверим.

В нашем случае изменяется v7=-4-0=-4 и u5=-1-(-4)=3. Остальные потенциалы не изменяются.

Найдем оценки незадействованных маршрутов:

A1B2: Д12 = c12 - ( u1 + v2 ) =7-(0-2)=9	A4B1: Д41 = c41 - ( u4 + v1 ) =1-(11+1)=-11
A1B3: Д13 = c13 - ( u1 + v3 ) =4-(0-1)=5	A4B2: Д42 = c42 - ( u4 + v2 ) =2-(11-2)=-7
A1B4: Д14 = c14 - ( u1 + v4 ) =-2-(0-11)=9	A4B3: Д43 = c43 - ( u4 + v3 ) =3-(11-1)=-7
A1B5: Д15 = c15 - ( u1 + v5 ) =-1-(0-6)=5	A4B4: Д44 = c44 - ( u4 + v4 ) =-1-(11-11)=-1
A1B6: Д16 = c16 - ( u1 + v6 ) =-3-(0-12)=9	A4B5: Д45 = c45 - ( u4 + v5 ) =-5-(11-6)=-10
A2B7: Д27 = c27 - ( u2 + v7 ) =-1-(4-4)=-1	A4B7: Д47 = c47 - ( u4 + v7 ) =-9-(11-4)=-16
A3B1: Д31 = c31 - ( u3 + v1 ) =2-(9+1)=-8	A5B1: Д51 = c51 - ( u5 + v1 ) =7-(3+1)=3
A3B2: Д12 = c32 - ( u3 + v2 ) =4-(9-2)=-3	A5B2: Д52 = c52 - ( u5 + v2 ) =9-(3-2)=8
A3B3: Д33 = c33 - ( u3 + v3 ) =1-(9-1)=-7	A5B3: Д53 = c53 - ( u5 + v3 ) =4-(3-1)=2
A3B4: Д34 = c34 - ( u3 + v4 ) =-2-(9-11)=0	A5B4: Д54 = c54 - ( u5 + v4 ) =-6-(3-11)=2
A3B5: Д35 = c35 - ( u3 + v5 ) =-1-(9-6)=-4	A5B5: Д55 = c55 - ( u5 + v5 ) =-2-(3-6)=1
A3B7: Д37 = c37 - ( u3 + v7 ) =-2-(9-4)=-7	A5B6: Д56 = c56 - ( u5 + v6 ) =-3-(3-12)=6

Оценка A4B1=-11

Данное преобразование не изменит баланса.

А вот общая стоимость доставки продукции изменится на величину:

1*(-40)-5*(-40)-8*(-40)+1*(-40) = -11*(-40) ден. ед.

Мы можем заметить, что -11*(-40)= Д41 *(-40)

Следовательно, мы теперь должны прибавить(или вычесть) (-40) к угловым элементам. Исходя из задействованного маршрута, нужно пересчитать ui и vi, а также оценки незадействованных маршрутов.

Общую сумму доставки продукции, для данного решения, легко посчитать.

L = 1550 + Д17 * (-40) = 1550 +-11* (-40) = 1990 ден. ед.

Полученное решение является оптимальным?

Проверим.

В нашем случае изменяется v6=-1и u4=0, u3=-2. Остальные потенциалы не изменяются.

Найдем оценки незадействованных маршрутов:

A1B2: Д12 = c12 - ( u1 + v2 ) =7-(0-2)=9	A3B7: Д37 = c37 - ( u3 + v7 ) =-2-(9-2)=-9
A1B3: Д13 = c13 - ( u1 + v3 ) =4-(0-1)=5	A4B2: Д42 = c42 - ( u4 + v2 ) =2-(0-2)=4
A1B4: Д14 = c14 - ( u1 + v4 ) =-2-(0-11)=9	A4B3: Д43 = c43 - ( u4 + v3 ) =3-(0-1)=4
A1B5: Д15 = c15 - ( u1 + v5 ) =-1-(0-6)=5	A4B4: Д44 = c44 - ( u4 + v4 ) =-1-(0-11)=10
A1B6: Д16 = c16 - ( u1 + v6 ) =-3-(0-1)=-2	A4B5: Д45 = c45 - ( u4 + v5 ) =-5-(0-6)=1
A2B6: Д26 = c26 - ( u2 + v6 ) =-8-(4-1)=-11	A4B7: Д47 = c47 - ( u4 + v7 ) =-9-(0-4)=-5
A2B7: Д27 = c27 - ( u2 + v7 ) =-1-(4-4)=-1	A5B1: Д51 = c51 - ( u5 + v1 ) =7-(3+1)=3
A3B1: Д31 = c31 - ( u3 + v1 ) =2-(-2+1)=3	A5B2: Д52 = c52 - ( u5 + v2 ) =9-(3-2)=8
A3B2: Д12 = c32 - ( u3 + v2 ) =4-(-2-2)=8	A5B3: Д53 = c53 - ( u5 + v3 ) =4-(3-1)=2
A3B3: Д33 = c33 - ( u3 + v3 ) =1-(-2-1)=4	A5B4: Д54 = c54 - ( u5 + v4 ) =-6-(3-11)=2
A3B4: Д34 = c34 - ( u3 + v4 ) =-2-(-2-11)=11	A5B5: Д55 = c55 - ( u5 + v5 ) =-2-(3-6)=1
A3B5: Д35 = c35 - ( u3 + v5 ) =-1-(-2-6)=7	A5B6: Д56 = c56 - ( u5 + v6 ) =-3-(3-1)=-5

Оценка A3B4=11.

Данное преобразование не изменит баланса.

А вот общая стоимость доставки продукции изменится на величину:

-2*(-10)+7*(-10)+5*(-10)-1*(-10)-1*(-10)+3*(-10)= 11*(-10) ден. ед.

Мы можем заметить, что 11*(-10)= Д34 *(-10)

Следовательно, мы теперь должны прибавить(или вычесть) (-10) к угловым элементам.

Исходя из задействованного маршрута, нужно пересчитать ui и vi, а также оценки незадействованных маршрутов

Выводы

Таким образом, с помощью транспортной задачи можно моделировать многочисленные практические процессы. В первую очередь, это моделирование перемещения продукции от поставщика к потребителю. При этом оптимальное перемещение наступает при минимуме затрат на перемещение.

В курсовом проекте были рассмотрены следующие вопросы:

- Разработан алгоритм метода решения поставленной задачи; - Приведено решение задачи разработанным методом.

В нашей работе мы решили транспортную задачу с транзитными пунктами методами северо-западного угла и методом потенциалов для решения транспортной задачи модифицированным с учетом отрицательных перевозок.

Алгоритм расчета на основе метода потенциалов имел большое применение из-за наглядности процесса решения и сравнительно небольшого количества вычислений. Появление его позволило ускорить ручной счет. С появлением вычислительных машин актуальность применения этих методов значительно снизилась. В настоящее время наибольшее предпочтение следует отдать симплекс-методу, на основе которого разработаны эффективные программные средства.

Программа транспортной задачи с транзитными пунктами

Похожие статьи