Решение транспортной задачи

                                               Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

             

        Введение

 

Одна из наиболее распространённых задач математического(обычно-линейного) программирования – транспортная задача. В общем виде её можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки(или суммарная дальность, или объём транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). Из описания транспортной задачи можно понять , что используются в современном мире они довольно часто, ведь каждый день многим людям , в том числе тем, кто занимается  логистикой нужно просчитывать оптимальный маршрут движения грузов и перевозок.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Транспортная задача

1.1. Описание

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

 

Имеется ряд пунктов  производства , …., с объёмами производства в единицу времени(месяц, квартал), равными соответственно , ….., и пункты потребления

, …., ,потребляющие за тот же промежуток времени соответственно , …, продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объектов производства на всех т пунктах-поставщиках равна сумме объёмов потребления на всех n пунктах-получателях:

.

 

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

 

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

 

Min F(x)= .

При этом каждый потребитель получает нужное количество продукта:

 

= .

И каждый поставщик отгружает  весь произведённый им продукт:

 

= .

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

 

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

 

Несбалансированную (открытую) транспортную задачу приводят к виду, показанному  выше , искусственно: в  модель вводятся так называемые фиктивный  поставщик или фиктивный потребитель , которые балансируют спрос и потребление.

                                1.2 Определение исходного опорного решения.

Существует несколько  способов, наиболее популярными являются:

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

- метод минимальной  стоимости,

- метод потанциалов.

Они перечислены в порядке усложнения алгоритма, но при этом получаемое решение, как правило, меньше отличается от оптимального.

В каждом методе на любом  шаге в выбранную ячейку ( ) таблицы помещаются максимальная допустимая перевозка – минимальное из того, что есть у соответствующего поставщика (ПО) и требуется соответствующему потребителю (ПН) .При этом каждый раз <закрывается> строка таблицы, если у соответствующего поставщика (ПО)  больше нет груза, или <закрывается> столбец, если соответствующему потребителю (ПН) больше не надо груза. Методы отличаются лишь способом построения последовательности заполнения ячеек таблицы.

В методе минимального элемента заполнение начинается с ячейки с  минимальной стоимостью.

Рассмотрим задачу:

Заданы мощности поставщиков ai(i=1,2,3), емкости потребителей bj

(j=1,2,3) и матрица стоимостей перевозок единицы продукции от каждого  поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные  транспортные задачи будут наименьшими.

	Потребители	B1	B2	B3
Поставщики		14	20	22
A1	50	3	8	9
A2	18	3	4	5
A3	12	2	7	6

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

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

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

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

 

Заполнение таблицы  транспортной задачи начинается с левого верхнего угла, поэтому и называется метод северо-западного угла.

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

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

Последовательность заполнения таблицы:

(

Стоимость перевозок:

F=

 

 

 

	B1	B2	B3	B4	Запас
A1	3    14	8      20	9           16	0	50
A2	3	4	5         6	0          12	18
A3	2	7	6	0          12	12
Потр	14	20	22	24	80

 

Таблица 1

1.4 Метод минимального элемента

Метод минимальной стоимости  прост и позволяет построить  опорное решение, достаточно близкое  к оптимальному.

 

Как и метод северо-западного  угла, он состоит из ряда однотипных шагов, на каждому из которых заполняется  только одна клетка таблицы,

 

Соответствующая минимальной  стоимости:

и исключается из рассмотрения только одна строка (поставщик) или один

 

столбец (потребитель). Очередную  клетку, соответствующую

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

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

 

 

 

 

 

 

 

 

	B1	B2	B3	B4	Запас
A1	3	8          4	9             22	0	50
A2	3        2	4          16	5	0          12	18
A3	2       12	7	6	0          12	12
Потр	14	20	22	24	80

 

 

        Таблица 2

 

Стоимость перевозок:

1.5 Классическая транспортная задача метод потанциалов.

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

Пусть имеется m пунктов отправления (ПО): , …., в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно , ….., единиц. Также имеется n пунктов назначения (ПН): , …., , подавших заявки соответственно на , …, единиц груза. Считаем что сумма всех заявок равна сумме всех запасов (сбалансированная транспортная задача):

 

.

Известны стоимости  перевозки единицы груза от каждого пункта отправления до каждого пункта назначения ( i= ,j = ).

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

Экономико-математическая модель задачи имеет вид задачи линейного  программирования. Обозначим  - количество единиц груза, отправляемого из i-го ПО

 в j-й ПН . Совокупность чисел ( ) будем называть планом перевозок, а сами величины -перевозками.

Необходимо найти такой  план перевозок ( ),при котором целевая функция (суммарная стоимость перевозок) будет минимальной:

 

min

 

И который удовлетворяет  следующим ограничениям:

 

1)Суммарное количество  груза, направляемого из каждого  ПО во все ПН должно быть равно запасу груза в данном пункте:

 

 

 

 

 

2)Суммарное количество  груза, доставляемого в каждый  ПН из всех ПО, должно быть  равно заявке, поданной данным  пунктом:

 

 

 

 

 

3)Условие отрицательности:

 

Решение транспортной задачи разбивается на два этапа:

1)Определение исходного  опорного решения;

2)Построение последовательных  итераций -  приближение к оптимальному  решению.

Обычно для решении  транспортной задачи используют её табличную модель, в которой ячейкам поставлены в соответствие перевозки – переменные , при заполнении таблицы задаются значения неизвестных

 

 

	B1	B2	B3	B4	Запас
A1	3    +	8     -    4	9             22	0	50
A2	3   -     2	4   +         16	5	0          12	18
A3	2       12	7	6	0          12	12
Потр	14	20	22	24	80