Логистика транспорта

 

Заполненные нами ячейки будем  называть базисными, остальные - свободными.

Для решения задачи методом  потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.

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

Z0 =345*7+147*14+384*9+88*10+232*9+132*0+82*0=10897 ден. единиц

Общие затраты на доставку всей продукции, для начального решения, составляют 10897 денежных единиц. 

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

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

Шаг 1.проведем оценку полученного решения.

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

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

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

Проверим найденное опорное  решение на оптимальность методом  потенциалов. Если решение оптимальное, то будет выполняться условие:

для занятых клеток     V i + Uj = Cij

для свободных клеток  Cij-( V i + Uj )≥0

Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v3=0

v2+u1=c12               v2+u1=7                     u4=0-0=0

v3+u1=c13                v3+u1=14                 u1=14-0=14

v1+u2=c21                v1+u2=9                    u2=10-0=10

v3+u2=c23                v3+u2=10                  v2=7-14=-7

v4+u3=c34                v4+u3=9                    v1=9-10=-1

v3+u4=c43                v3+u4=0                   v4=0-0=0

v4+u4=c44                v4+u4=0                  u3=9-0=9

Найдем оценки свободных  ячеек следующим образом:

∆11=c11-(u1+v1)=15-(14+(-1))=2

∆14=c14-(u1+v4)=14-(14+0)=0

∆22=c22-(u2+v2)=10-(10+(-7))=7

∆24=c24-(u2+v4)=12-(10+0)=2

∆31=c31-(u3+v1)=10-(9+(-1))=2

∆32=c32-(u3+v2)=7-(9+(-7))=5

∆33=c33-(u3+v3)11-(9+0)=2

∆41=c41-(u4+v1)=0-(0+(-1))=1

∆42=c42-(u4+v2)=0-(0+(-7))=7

Все оценки свободных решений  положительные, следовательно найдено оптимальное решение.

Ответ:

x=

Zmin=345*7+147*14+384*9+88*10+232*9+132*0+82*0=10897 ден. единиц

 

 

                    xi.j≥0

2.3.Транспортная задача №2

Постановка задачи: На заводах № 1, 2 и 3 производится однородная продукция в количестве а, а₂ и а₃. При этом затраты на производство единицы продукции на заводах составляют s₁ s₂ и s₃ ден. ед. Четырем потребителям требуется соответственно b₁, b₂, b₃ и b₄ единиц продукции. Расходы с_ij по перевозке единицы продукции с i-гo завода j-му потребителю известны.

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

1) увеличить производство продукции на заводе № 1 с дополнительными затратами на единицу продукции, равными с1 = 7

2) увеличить производство продукции на заводе № 2 с дополнительными затратами на единицу продукции, равными с2 = 5

3) наладить выпуск продукции на заводе № 4 с затратами на производство единицы продукции, равными с4 = 10, и расходами по перевозке единицы продукции, равными соответственно с41 = 5, с42 = 4, с43 = 6 и с44 = 4.        

Решение:            

Проверим : 

∑Вi - ∑Ai = 1224-449=775

В системе выпускается  меньше, чем требуется. Задача открытого  типа.

1.Увеличим производство  продукции на первом заводе на 775 ед.          (775 + 122= 897) и будем рассматривать его в строке A5:

4+9=13 ( S=S1+∆C1)

2.Увеличим производство продукции на втором заводе на 775 ед.   и будем рассматривать его в строке А6  (775+ 155=930):

5+5=10 ( S=S2+∆C2)

3. Введем четвертый завод А4 с объемом выпуска А4 = 574 ед.

S4 = 8, C41 =9,C42 = 7, C43=5,C44 = 5

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

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

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

Маршруты доставки продукции  от поставщиков к фиктивному потребителю B5 мы будем рассматривать в последнюю  очередь. Не факт, но, скорее всего, это  позволит получить более рентабельное начальное решение.

5.Считаем общие затраты  на производство и перевозку  единицы продукции от i-го завода к  j-му поставщику:

Sij=si+cij

Данные приведем в таблице:

 

Поставщик	Потребитель      В1         В2           В3          В4         В5       Запасы
А1	6	14	9	7	0	122
А2	6	9	7	13	0	155
А3	15	13	8	12	0	172
А4	15	14	16	14	0	775
А5	15	23	18	16	0	897
А6	13	16	14	20	0	930
потребность	231	282	351	360	1827

 

6. Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 6, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.

 Запасы поставщика A1 составляют 122 единиц продукции. Потребность  потребителя B1 составляет 231 единиц  продукции. (см. таблицу пункта 1)

От поставщика A1 к потребителю B1 будем доставлять min = { 122 , 231 } = 122 единиц продукции.

Разместим в ячейку A1B1 значение равное 122

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

Поставщик	Потребитель      В1         В2           В3          В4         В5       Запасы
А1	122 6	14	9	7	0	122
А2	6	9	7	13	0	155
А3	15	13	8	12	0	172
А4	15	14	16	14	0	775
А5	15	23	18	16	0	897
А6	13	16	14	20	0	930
потребность	231	282	351	360	1827

 

7. Минимальный элемент матрицы тарифов находится в ячейке A2B1 и равен 6, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B1 наиболее рентабельный.

 Запасы поставщика A2 составляют 155 единиц продукции. Потребность  потребителя B1 составляет 109 единиц  продукции. (см. таблицу пункта 2)

От поставщика A2 к потребителю B1 будем доставлять min = { 155 , 109 } = 109 единиц продукции.

Разместим в ячейку A2B1 значение равное 109

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

Поставщик	Потребитель      В1         В2           В3          В4         В5       Запасы
А1	122 6	14	9	7	0	122
А2	109 6	9	7	13	0	155
А3	15	13	8	12	0	172
А4	15	14	16	14	0	775
А5	15	23	18	16	0	897
А6	13	16	14	20	0	930
потребность	231	282	351	360	1827

 

8. Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 7, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.

 Запасы поставщика A2 составляют 46 единиц продукции. Потребность  потребителя B3 составляет 351 единиц  продукции. (см. таблицу пункта 3) От поставщика A2 к потребителю B3 будем доставлять min = { 46 , 351 } = 46 единиц продукции.

Разместим в ячейку A2B3 значение равное 46 Мы полностью израсходовали запасы поставщика A2.

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

 

Поставщик	Потребитель      В1         В2           В3          В4         В5       Запасы
А1	122 6	14	9	7	0	122
А2	109 6	9	46  7	13	0	155
А3	15	13	8	12	0	172
А4	15	14	16	14	0	775
А5	15	23	18	16	0	897
А6	13	16	14	20	0	930
потребность	231	282	351	360	1827