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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное автономное образовательное учреждение высшего образования

Курсовая работа

Дисциплина: Анализ и разработка алгоритма решения оптимизационных задач

Тема: Разработать алгоритм и программу транспортной задачи с транзитными пунктами

Выполнили:

Студенты группы КТбо3-4

Фонова А.Э.

Трехсвояков Е.В.

Преподаватель:

Кафедры АПР

Щеглов С.Н.

Таганрог, 2016



При постановке задачи оптимизации должен присутствовать объект, цель оптимизации и ресурсы оптимизации.

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации: транспортировка транзитный программирование стоимость

§ Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

§ Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

Существующие в настоящее время методы поиска можно разбить на три большие группы:

1. Детерминированные;

2. Случайные (стохастические);

3. Комбинированные.

По критерию размерности допустимого множества, методы оптими-зации делят на методы одномерной оптимизации и методы многомерной оптимизации.

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

§ Задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования.

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

§ если и -- выпуклые функции, то такую задачу называют задачей выпуклого программирования;

§ если , то имеют дело с задачей целочисленного (дискретного) программирования.

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

§ прямые методы, требующие только вычислений целевой функции в точках приближений;

§ методы первого порядка: требуют вычисления первых частных производных функции;

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

Помимо того, оптимизационные методы делятся на следующие группы:

§ аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

§ численные методы;

§ графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

§ задачи дискретного программирования (или комбинаторной оптимизации) -- если X конечно или счётно;

§ задачи целочисленного программирования -- если X является подмножеством множества целых чисел;

§ задачей нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X является подмножеством конечномерного векторного пространства.

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

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

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

1. Определение границ системы оптимизации

§ Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается

2. Выбор управляемых переменных

§ «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)

3. Определение ограничений на управляемые переменные

§ … (равенства и\или неравенства)

4. Выбор числового критерия оптимизации

§ Создаём целевую функцию

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

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

· методы исследования функций классического анализа;

· методы, основанные на использовании неопределенных множителей Лагранжа;

· вариационное исчисление;

· динамическое программирование;

· принцип максимума;

· линейное программирование;

· нелинейное программирование.

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

В экономической транспортной системе имеются n конечных пунктов (np поставщиков продукции и n-np потребителей продукции) и m промежуточных пунктов (складов). Продукция перевозится от поставщиков на склады, будем обозначать эти перевозки положительными переменными x_ij?0, (i=1,m,j=1,np). А со складов часть продукции перевозится потребителям - их обозначим отрицательными переменными x_ij?0, (i=1,m,j=np+1,n). Объёмы поставок поставщиков обозначим положительными числами b_j>0, (j=1,np), объёмы потребностей потребителей обозначим отрицательными числами b_j<0, (j=np+1,n). Если склад имеет дополнительные (внутренние) потребности продукции, то обозначим их положительными числами a_i>0, (i=1,mp). Если склад имеет излишки продукции или нулевые остатки, то обозначим их числами a_i?0, (i=mp+1,m).

Транспортные тарифы на перевозку единицы продукции от поставщика на склад выразим положительными числами c_ij>0, (i=1,m,j=1,np), транспортные тарифы на перевозку со склада к потребителю выразим отрицательными числами c_ij<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.Сначала удовлетворяем дополнительные потребности складов (a_i>0) за счёт поставщиков (b_j>0), т.е. назначаем соответствующие положительные перевозки по формулам: x_ij=min(ai,bj), ai=ai-x_ij, b_j=b_j-x_ij.

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

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

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

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

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

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

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

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

5.Определяем оценку Дx, элемент (i_x,j_x) и новое опорное решение Xmxn с помощью алгоритма перераспределения перевозок.



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

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

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

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

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

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

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

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

Значение одного потенциала необходимо задать. Пусть u₁ = 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)= Д₁₇ *(-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)= Д₄₁ *(-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)= Д₃₄ *(-10)

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

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



Выводы

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

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

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

· Приведено решение задачи разработанным методом.

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

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

Размещено на Allbest.ru