Транспортная задача решение онлайн: Транспортная задача онлайн

Транспортная задача. Метод потенциалов и метод минимального элемента. Пример решения транспортной задачи линейного программирования

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

Классическая транспортная задача линейного программирования формулируется следующим образом:

Имеется  пунктов отправления: , в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно  единиц. Кроме того имеется  пунктов назначения: , подавших заявки соответственно на  единиц товара.

Предполагается, что сумма всех заявок равна сумме всех запасов:

Известная стоимость  перевозки единицы товара от каждого пункта отправления  до каждого пункта назначения .

Таблица (матрица) стоимостей перевозки  задана:

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

При такой постановке задачи показателем эффективности плана перевозок является стоимость, поэтому поставленную задачу точнее называют транспортной задачей по критерию стоимости.

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

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

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

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

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

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

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

Любую совокупность значений  будем называть планом перевозок или просто планом.

План  будем называть допустимым, если он удовлетворяет условиям системы равенств (так называемым «балансовым условиям»): все заявки удовлетворены, все запасы исчерпаны.

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

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

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

I этап.  Нахождение начального опорного плана .

II этап. Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов). Если все небазисные переменные удовлетворяют условию оптимальности, то следует закончить вычисления; в противном случае — перейти к III этапу.

III этап. Выбор выводимой из базиса переменной (используя условия допустимости) из числа переменных текущего базиса; затем нахождение нового опорного решения и возвращение ко II этапу.

Задача

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

Этот груз нужно доставить пяти заказчикам . Потребности в грузе в каждом пункте  известны и равны  соответственно. Известны также тарифы перевозки  — стоимость перевозки единицы груза из пункта  в пункт . Нужно найти такой план перевозок, при котором весь груз из пунктов потребления будет вывезен, потребности всех заказчиков будут удовлетворены, и при этом общая стоимость перевозки всего груза будет наименьшей. Данные в таблице,  в клетках которой проставлены элементы матрицы тарифов ; в последнем столбце таблицы указаны значения величин , в последней строке - значения величин .

 

Требуется:

• Составить математическую модель задачи.
• Найти оптимальное решение транспортной задачи методом потенциалов.

Если вам сейчас не требуется платная помощь с решением задач, контрольных работ и типовых расчетов, но может потребоваться в дальнейшем, то, чтобы не потерять контакт
вступайте в группу ВК
сохраните контакт WhatsApp (+79688494598)
сохраните контакт Телеграм (@helptask) .

Решение

Математическая модель задачи

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

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:   

Полученную задачу можно решить симплекс-методом, так как это классическая ЗЛП, однако относительная простота систем уравнений дает возможность использовать метод решения более простой. Особенности систем следующие:

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

Проверка задачи на закрытость модели

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

В нашем случае:

Модель транспортной задачи закрытая.

Нахождение начального опорного плана и метод потенциалов

Заполняем таблицу по правилу минимального элемента .

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту , поэтому в клетку помещаем . В этом случае 4-й столбец в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка

Далее действуя по аналогичной схеме:

 

 Решать задачу будем методом потенциалов. Число занятых клеток должно быть . Потенциал 1-й строки принимаем равным нулю. После этого мы можем вычислить остальные потенциалы (если известны потенциал и тариф занятой клетки, то из соотношения v + u =c легко определить неизвестный потенциал).

Найдем оценки свободных клеток по формуле: 

S ( 1, 1)= 4-( 0-1)=  5	S ( 1, 2)= 9-( 0+ 0)=  9
S ( 1, 4)= 5-( 0-4)=  9	S ( 2, 2)= 6-( 5+ 0)=  1
S ( 2, 3)= 2-( 5+ 2)= -5	S ( 3, 1)= 6-( 2-1)=  5
S ( 3, 3)= 3-( 2+ 2)= -1	S ( 3, 4)= 4-( 2-4)=  6

Для клетки ( 2, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 1 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)=  0	S ( 1, 2)= 9-( 0+ 0)=  9
S ( 1, 4)= 5-( 0+ 1)=  4	S ( 2, 2)= 6-( 0+ 0)=  6
S ( 2, 5)= 8-( 0+ 3)=  5	S ( 3, 1)= 6-( 2+ 4)=  0
S ( 3, 3)= 3-( 2+ 2)= -1	S ( 3, 4)= 4-( 2+ 1)=  1

 

Для клетки ( 3, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 7 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)=  0	S ( 1, 2)= 9-( 0+ 1)=  8
S ( 1, 4)= 5-( 0+ 1)=  4	S ( 2, 2)= 6-( 0+ 1)=  5
S ( 2, 5)= 8-( 0+ 3)=  5	S ( 3, 1)= 6-( 1+ 4)=  1
S ( 3, 4)= 4-( 1+ 1)=  2	S ( 3, 5)= 5-( 1+ 3)=  1

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

Ответ

Пункт      поставляет 8 единиц груза в пункт   и 15 единиц груза в пункт  

Пункт   поставляет 14 единиц груза в пункт  , 1 единицу груза в пункт  и 10 единиц груза в пункт

Пункт      поставляет 10 единиц груза в пункт   и 7 единиц груза в пункт  

Минимальные транспортные издержки оптимального плана:

Решение закрытой транспортной задачи с дополнительными условиями средствами Python

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

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

Решение закрытой транспортной задачи средствами Python с классическим условиями для поставщиков и потребителей товара приведено в моей статье “Решение задач линейного программирования с использованием Python” [1].

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

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

Рассмотрим пример исходных данных в виде таблицы (матрицы).

где C= [7,3,6,4,8,2,1,5,9]– список стоимости перевозки единицы товара от заказчиков к потребителям; X – список объёмов перевозимых товаров, обеспечивающих минимальные затраты; a= [74,40,36] – список объёмов однородных товаров на складах поставщиков; b= [20,45,30] – список объёмов спроса заказчиками однородных товаров.

Задача закрытая поскольку sum(a)> sum(b), поэтому для X из строк таблицы запишем неравенства ограниченные сверху, а для X из столбцов таблицы равенства. Для дальнейшей обработки возьмём полученные соотношения в скобки и приравняем их переменным.

mass1 = (x[0] + x[1] +x[2] <= 74)
mass2 = (x[3] + x[4] +x[5] <= 40)
mass3 = (x[6] + x[7] + x[8] <= 36
mass4 = (x[0] + x[3] + x[6] == 20
mass5 = (x[1] +x[4] + x[7] == 45)
mass6 = (x[2] + x[5] + x[8] == 30)

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

problem =op(C[0]*x[0] + C[1]*x[1] +C[2]* x[2] +C[3]*x[3] + C[4]*x[4] +C[5]* x[5]+C[6]*x[6] + C[7]*x[7] +C[8]* x[8], [mass1, mass2, mass3, mass4, mass5, mass6,x_non_negative])

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

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

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

1.Установка заданного объёма поставки товара от определённого поставщика определённому заказчику.

Для этого вводиться новая переменная с соответствующим ограничением. Например первый поставщик должен поставить второму заказчику ровно 30 единиц товара– mass7 = (x[1] == 30).

2.Изменение объёма поставки товара для определённого заказчика.

Для этого меняются условия на столбец таблицы объёмов доставок товаров. Например, для второго заказчика объём заказа уменьшился с 45 единиц товара до 30.

Строку условий mass5 = (x[1] +x[4] + x[7] == 45) следует заменить на
mass5 = (x[1] +x[4] + x[7] == 30).

3. Установка верхней границы объёма поставок товара для поставщика.

Для этого меняются условия на строку таблицы объёмов доставок товаров. Например, для объёмов доставки товаров второго поставщика было ограничение сверху <= 40, а возникла необходимость доставки ровно 40 единиц товара. Переменную условий mass2 = (x[3] + x[4] +x[5] <= 40) заменим на mass2 = (x[3] + x[4] +x[5] == 40).

4. Паритет на поставки второго и третьего поставщиков
Для этого приравниваются объёмы поставок нескольких поставоких поставщиков, что обычно делается для улучшения бизнес климата. Например 6объёмы доставок товаров второго и третьего поставщика транспортных услуг соответственно ограничены сверху <=40 и <=36. Заменим строки mass2 = (x[3] + x[4] +x[5] <= 40) и mass3 = (x[6] + x[7] + x[8] <= 36) на mass2 = (x[3] + x[4] +x[5] == 30) и mass3 = (x[6] + x[7] + x[8] == 30).

Решение закрытой транспортной задачи с дополнительными условиями средствами решателя cvxopt Python

Программа для дополнительного условия №1

from cvxopt. modeling import variable, op
import time
start = time.time()
x = variable(9, 'x')
c= [7,3,6,4,8,2,1,5,9]
z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
mass1 = (x[0] + x[1] +x[2] <= 74)
mass2 = (x[3] + x[4] +x[5] <= 40)
mass3 = (x[6] + x[7] + x[8] <= 36)
mass4 = (x[0] + x[3] + x[6] == 20)
mass5 = (x[1] +x[4] + x[7] == 45)
mass6 = (x[2] + x[5] + x[8] == 30)
mass7 = (x[1] == 30)
x_non_negative = (x >= 0)    
problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, mass7,x_non_negative])
problem.solve(solver='glpk')  
print("Результат Xopt:")
for i in x.value:
         print(i)
print("Стоимость доставки:")
print(problem.objective.value()[0])
stop = time.time()
print ("Время :")
print(stop - start)

Результат Xopt:
0.0
30.0
0.0
0.0
0.0
30.0
20.0
15.0
0.0
Стоимость доставки:
245.0
Время:
0.04002642631530762Программа для дополнительного условия №2

from cvxopt. modeling import variable, op
import time
start = time.time()
x = variable(9, 'x')
c= [7,3,6,4,8,2,1,5,9]
z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
mass1 = (x[0] + x[1] +x[2] <= 74)
mass2 = (x[3] + x[4] +x[5] <= 40)
mass3 = (x[6] + x[7] + x[8] <= 36)
mass4 = (x[0] + x[3] + x[6] == 20)
mass5 = (x[1] +x[4] + x[7] == 30)
mass6 = (x[2] + x[5] + x[8] == 30)
x_non_negative = (x >= 0)    
problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6,x_non_negative])
problem.solve(solver='glpk')  
print("Результат Xopt:")
for i in x.value:
         print(i)
print("Стоимость доставки:")
print(problem.objective.value()[0])
stop = time.time()
print ("Время :")
print(stop - start)

Результат Xopt:
0.0
30.0
0.0
0.0
0.0
30.0
20.0
0.0
0.0
Стоимость доставки:
170.0
Время:
0.040003299713134766Программа для дополнительного условия №3

from cvxopt. modeling import variable, op
import time
start = time.time()
x = variable(9, 'x')
c= [7,3,6,4,8,2,1,5,9]
z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
mass1 = (x[0] + x[1] +x[2] <= 74)
mass2 = (x[3] + x[4] +x[5] == 40)
mass3 = (x[6] + x[7] + x[8] <= 36)
mass4 = (x[0] + x[3] + x[6] == 20)
mass5 = (x[1] +x[4] + x[7] == 45)
mass6 = (x[2] + x[5] + x[8] == 30)
x_non_negative = (x >= 0)    
problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6,x_non_negative])
problem.solve(solver='glpk')  
print("Результат Xopt:")
for i in x.value:
         print(i)
print("Стоимость доставки:")
print(problem.objective.value()[0])
stop = time.time()
print ("Время :")
print(stop - start)

Результат Xopt:
0.0
45.0
0.0
10.0
0.0
30.0
10.0
0.0
0.0
Стоимость доставки:
245.0
Время:
0.041509151458740234Программа для дополнительного условия №4

from cvxopt. modeling import variable, op
import time
start = time.time()
x = variable(9, 'x')
c= [7,3,6,4,8,2,1,5,9]
z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
mass1 = (x[0] + x[1] +x[2] <= 74)
mass2 = (x[3] + x[4] +x[5] == 30)
mass3 = (x[6] + x[7] + x[8] == 30)
mass4 = (x[0] + x[3] + x[6] == 20)
mass5 = (x[1] +x[4] + x[7] == 45)
mass6 = (x[2] + x[5] + x[8] == 30)
x_non_negative = (x >= 0)    
problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6,x_non_negative])
problem.solve(solver='glpk')  
print("Результат Xopt:")
for i in x.value:
         print(i)
print("Стоимость доставки:")
print(problem.objective.value()[0])
stop = time.time()
print ("Время :")
print(stop - start)

Результат Xopt:
0.0
35.0
0.0
0.0
0.0
30.0
20.0
10.0
0.0
Стоимость доставки:
235.0
Время:
0.039984941482543945

Решение закрытой транспортной задачи с дополнительными условиями средствами решателя scipy.

optimize Python
Программа для дополнительного условия №1

from scipy.optimize import linprog
import time
start = time.time()
c = [7, 3,6,4,8,2,1,5,9]
b_ub = [74,40,36] 
A_ub = [[1,1,1,0,0,0,0,0,0],
               [0,0,0,1,1,1,0,0,0],
               [0,0,0,0,0,0,1,1,1]] 
b_eq = [20,45,30,30] 
A_eq = [[1,0,0,1,0,0,1,0,0],
               [0,1,0,0,1,0,0,1,0],
               [0,0,1,0,0,1,0,0,1],
               [0,1,0,0,0,0,0,0,0]] 
print(linprog(c, A_ub, b_ub, A_eq, b_eq))
stop = time.time()
print ("Время :")
print(stop - start)

Результат:
fun: 245.0
message: ‘Optimization terminated successfully.’
nit: 10
slack: array([ 44., 10., 1.])
status: 0
success: True
x: array([ 0., 30., 0., 0., 0., 30., 20., 15., 0.])
Время:
0.01000523567199707Программа для дополнительного условия №2

from scipy.optimize import linprog
import time
start = time.time()
c = [7, 3,6,4,8,2,1,5,9]
b_ub = [74,40,36] 
A_ub = [[1,1,1,0,0,0,0,0,0],
               [0,0,0,1,1,1,0,0,0],
               [0,0,0,0,0,0,1,1,1]] 
b_eq = [20,30,30] 
A_eq = [[1,0,0,1,0,0,1,0,0],
               [0,1,0,0,1,0,0,1,0],
               [0,0,1,0,0,1,0,0,1]]                
print(linprog(c, A_ub, b_ub, A_eq, b_eq))
stop = time. time()
print ("Время :")
print(stop - start)

Результат:
fun: 170.0
message: ‘Optimization terminated successfully.’
nit: 7
slack: array([ 44., 10., 16.])
status: 0
success: True
x: array([ 0., 30., 0., 0., 0., 30., 20., 0., 0.])
Время:
0.04005861282348633Программа для дополнительного условия №3

from scipy.optimize import linprog
import time
start = time.time()
c = [7, 3,6,4,8,2,1,5,9]
b_ub = [74,36] 
A_ub = [[1,1,1,0,0,0,0,0,0],             
               [0,0,0,0,0,0,1,1,1]] 
b_eq = [20,45,30,40] 
A_eq = [[1,0,0,1,0,0,1,0,0],
               [0,1,0,0,1,0,0,1,0],
               [0,0,1,0,0,1,0,0,1],
               [0,0,0,1,1,1,0,0,0]]                
print(linprog(c, A_ub, b_ub, A_eq, b_eq))
stop = time.time()
print ("Время :")
print(stop - start)

Результат:
fun: 245.0
message: ‘Optimization terminated successfully.’
nit: 8
slack: array([ 29., 26.])
status: 0
success: True
x: array([ 0. , 45., 0., 10., 0., 30., 10., 0., 0.])
Время:
0.04979825019836426Программа для дополнительного условия №4

from scipy.optimize import linprog
import time
start = time.time()
c = [7, 3,6,4,8,2,1,5,9]
b_ub = [74] 
A_ub = [[1,1,1,0,0,0,0,0,0]]             
b_eq = [20,45,30,30,30] 
A_eq = [[1,0,0,1,0,0,1,0,0],
               [0,1,0,0,1,0,0,1,0],
               [0,0,1,0,0,1,0,0,1],
               [0,0,0,1,1,1,0,0,0],
               [0,0,0,0,0,0,1,1,1]]                
print(linprog(c, A_ub, b_ub, A_eq, b_eq))
stop = time.time()
print ("Время :")
print(stop - start)

Результат:
fun: 235.0
message: ‘Optimization terminated successfully.’
nit: 8
slack: array([ 39.])
status: 0
success: True
x: array([ 0., 35., 0., 0., 0., 30., 20., 10., 0.])
Время:
0.05457925796508789

Решение закрытой транспортной задачи с дополнительными условиями средствами решателя pulp Python

Программа для дополнительного условия №1

from pulp import *
import time
start = time. time()
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
x3 = pulp.LpVariable("x3", lowBound=0)
x4 = pulp.LpVariable("x4", lowBound=0)
x5 = pulp.LpVariable("x5", lowBound=0)
x6 = pulp.LpVariable("x6", lowBound=0)
x7 = pulp.LpVariable("x7", lowBound=0)
x8 = pulp.LpVariable("x8", lowBound=0)
x9 = pulp.LpVariable("x9", lowBound=0)
problem = pulp.LpProblem('0',pulp.LpMaximize)
problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
problem +=x2==30
problem +=x1 + x2 +x3<= 74,"1" 
problem +=x4 + x5 +x6 <= 40, "2"
problem +=x7 + x8+ x9 <= 36, "3"
problem +=x1+ x4+ x7 == 20, "4"
problem +=x2+x5+ x8 == 45, "5"
problem +=x3 + x6+x9 == 30, "6"
problem.solve()
print ("Результат:")
for variable in problem.variables():
    print (variable.name, "=", variable.varValue)
print ("Стоимость доставки:")
print (abs(value(problem.objective)))
stop = time.time()
print ("Время :")
print(stop - start)

Результат:
x1 = 0. 0
x2 = 30.0
x3 = 0.0
x4 = 0.0
x5 = 0.0
x6 = 30.0
x7 = 20.0
x8 = 15.0
x9 = 0.0
Стоимость доставки:
245.0
Время:
0.16973495483398438Программа для дополнительного условия №2

from pulp import *
import time
start = time.time()
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
x3 = pulp.LpVariable("x3", lowBound=0)
x4 = pulp.LpVariable("x4", lowBound=0)
x5 = pulp.LpVariable("x5", lowBound=0)
x6 = pulp.LpVariable("x6", lowBound=0)
x7 = pulp.LpVariable("x7", lowBound=0)
x8 = pulp.LpVariable("x8", lowBound=0)
x9 = pulp.LpVariable("x9", lowBound=0)
problem = pulp.LpProblem('0',pulp.LpMaximize)
problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
problem +=x1 + x2 +x3<= 74,"1" 
problem +=x4 + x5 +x6 <= 40, "2"
problem +=x7 + x8+ x9 <= 36, "3"
problem +=x1+ x4+ x7 == 20, "4"
problem +=x2+x5+ x8 == 30, "5"
problem +=x3 + x6+x9 == 30, "6"
problem.solve()
print ("Результат:")
for variable in problem. variables():
    print (variable.name, "=", variable.varValue)
print ("Стоимость доставки:")
print (abs(value(problem.objective)))
stop = time.time()
print ("Время :")
print(stop - start)

Результат:
x1 = 0.0
x2 = 30.0
x3 = 0.0
x4 = 0.0
x5 = 0.0
x6 = 30.0
x7 = 20.0
x8 = 0.0
x9 = 0.0
Стоимость доставки:
170.0
Время:
0.18919610977172852Программа для дополнительного условия №3

from pulp import *
import time
start = time.time()
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
x3 = pulp.LpVariable("x3", lowBound=0)
x4 = pulp.LpVariable("x4", lowBound=0)
x5 = pulp.LpVariable("x5", lowBound=0)
x6 = pulp.LpVariable("x6", lowBound=0)
x7 = pulp.LpVariable("x7", lowBound=0)
x8 = pulp.LpVariable("x8", lowBound=0)
x9 = pulp.LpVariable("x9", lowBound=0)
problem = pulp.LpProblem('0',pulp.LpMaximize)
problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
problem +=x1 + x2 +x3<= 74,"1" 
problem +=x4 + x5 +x6 == 40, "2"
problem +=x7 + x8+ x9 <= 36, "3"
problem +=x1+ x4+ x7 == 20, "4"
problem +=x2+x5+ x8 == 45, "5"
problem +=x3 + x6+x9 == 30, "6"
problem. solve()
print ("Результат:")
for variable in problem.variables():
    print (variable.name, "=", variable.varValue)
print ("Стоимость доставки:")
print (abs(value(problem.objective)))
stop = time.time()
print ("Время :")
print(stop - start)

Результат:
x1 = 0.0
x2 = 45.0
x3 = 0.0
x4 = 10.0
x5 = 0.0
x6 = 30.0
x7 = 10.0
x8 = 0.0
x9 = 0.0
Стоимость доставки:
245.0
Время:
0.17000865936279297Программа для дополнительного условия №4

from pulp import *
import time
start = time.time()
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
x3 = pulp.LpVariable("x3", lowBound=0)
x4 = pulp.LpVariable("x4", lowBound=0)
x5 = pulp.LpVariable("x5", lowBound=0)
x6 = pulp.LpVariable("x6", lowBound=0)
x7 = pulp.LpVariable("x7", lowBound=0)
x8 = pulp.LpVariable("x8", lowBound=0)
x9 = pulp.LpVariable("x9", lowBound=0)
problem = pulp.LpProblem('0',pulp.LpMaximize)
problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
problem +=x1 + x2 +x3<= 74,"1" 
problem +=x4 + x5 +x6 == 30, "2"
problem +=x7 + x8+ x9 == 30, "3"
problem +=x1+ x4+ x7 == 20, "4"
problem +=x2+x5+ x8 == 45, "5"
problem +=x3 + x6+x9 == 30, "6"
problem. solve()
print ("Результат:")
for variable in problem.variables():
    print (variable.name, "=", variable.varValue)
print ("Стоимость доставки:")
print (abs(value(problem.objective)))
stop = time.time()
print ("Время :")
print(stop - start)

Результат:
x1 = 0.0
x2 = 35.0
x3 = 0.0
x4 = 0.0
x5 = 0.0
x6 = 30.0
x7 = 20.0
x8 = 10.0
x9 = 0.0
Стоимость доставки:
235.0
Время:
0.17965340614318848

Вывод

Полученные в публикации дополнительные условия к закрытой транспортной задаче позволяют получать решения, более приближенные к реальной ситуации по доставке товаров. Приведенные дополнения можно использовать по несколько в одной задаче применяя их в зависимости от возникшей ситуации. Исследован вопрос выбора решателя для транспортной задачи с условиями. Таким решателем является scipy. optimize, как более узко функциональный чем cvxopt и более быстрый чем pulp. Кроме того scipy. optimize имеет более компактную запись условий транспортной задачи, что облегчает его работу с интерфейсом.

Всем спасибо за внимание!

Ссылки

1. Решение задач линейного программирования с использованием Python.
2. CVXOPT Modeling.
3. Optimization.
4. Optimization with PuLP.

Решение транспортной задачи 📝 методом потенциалов онлайн

Если перед студентом стоит задание справиться с решением транспортной задачи, важно учитывать, что все действия должны быть выполнены пошагово с очень подробными пояснениями. Так же студенту необходимо дать определение, подобное тому, которое было озвучено на лекциях. Транспортные задачи представляют собой особый класс задач линейного программирования, они считаются очень объемными, поэтому выполнить их может не каждый студент. В этом случае заказать решение транспортной задачи методом потенциалов онлайн на специальном сервисе «Все Сдал!», будет лучшим выходом из сложившейся ситуации.

Решение задач на заказ по любым видам дисциплин – это одно из основных направлений деятельности онлайн помощника «Все Сдал!». За время работы на рынке студенческих услуг, квалифицированным исполнителям, представленным на сайте, удалось помочь тысячам студентов. Все они в свое время доверились нашим специалистам и взамен получили качественно и правильно оформленное решение транспортной задачи. Важно также акцентировать внимание на том, что на виртуальном ресурсе принимаются заказы на выполнение заказов со всех уголков нашей страны. При этом «Все Сдал!» гарантирует индивидуальный подход и качественную проработку материала.

Заказать решение транспортной задачи

Прямо здесь и сейчас в онлайн режиме каждый студент может заказать решение самой сложной задачи или выполнение любой другой работы (курсовой, дипломной, контрольной и т. д.). От пользователя требуется только заполнить специальную форму. Все преимущества сотрудничества с онлайн помощником «Все Сдал!»:

• Все работы выполняются в минимально короткие сроки
• Устранение недочетов и дополнения не требуют дополнительной оплаты
• В отличие от конкурирующих сервисов, здесь самые доступные цены
• Решение задач оформляется с учетом требований ВУЗа
• Все работы проверяются на уникальность

И, пожалуй, самое главное, – сотрудничая напрямую с онлайн помощником «Все Сдал!», студенты избегают встречи с недобросовестными исполнителями в лице мелких рефератных компаний, предоставляющих свои услуги по бросовой цене. Попав в руки мошенников велика вероятность того, что заказчик получит неправильно выполненную работу, поэтому деньги, пусть и не совсем большие, будут выброшены на ветер. Чтобы такого не случилось, предлагаем решение транспортной задачи методом потенциалов онлайн заказывать на проверенном и надежном сервисе, каким мы и являемся.

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

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

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

Транспортная задача — презентация онлайн

1. ТРАНСПОРТНАЯ ЗАДАЧА

Семинар 1:
ТРАНСПОРТНАЯ ЗАДАЧА
1

2.

Постановка задачи Имеется
m поставщиков A1 , A2, …, Am и n
потребителей B1 , B2, …, Bn некоторого груза.
Для каждого поставщика и потребителя
заданы запасы ai ≥ 0, i = 1, 2, …, m и объем
потребления bj ≥ 0, j = 1, 2, …, n.
Известна стоимость перевозки единицы
груза сij ≥ 0 от i-го поставщика к j-му
потребителю.
Требуется найти объемы всех перевозок xij
от i-го поставщика к j-му потребителю, при
которых общая стоимость минимальна.
2

3. Математическая постановка задачи

Пусть
X = (xij) – m×n матрица, где
xij – объем перевозок от i-го поставщика
к j-му потребителю.
Общие затраты на перевозку груза
определяются функцией:
m
n
z ( X ) cij xij
i 1 j 1
3
Математическая
постановка
транспортной задачи определяется задачей
линейного программирования:
m
n
z ( X ) cij xij min
i 1 j 1
при условиях
m
x
i 1
ij
b j , j 1,. .., n
ij
ai , i 1,…, m
n
x
j 1
xij 0
4
Решение
X = (xij) транспортной задачи,
удовлетворяющее условиям и имеющее не
более m+n–1 занятой клетки , будем называть
опорным планом транспортной задачи.
Закрытая модель: суммарные запасы
поставщиков равны суммарным запросам
потребителей, т.е.
m
n
a b
i 1
i
j 1
Открытая
m
модель:
n
a b
i 1
i
j
j 1
j
5

6. Задача 1

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
1
11
3
13
140
A2
12
4
8
2
160
A3
3
5
14
6
100
bj
80
40
150
130
400
400
400
6
1. Метод «северо-западного угла»
B1
A1
B2
1
80
11
40
A2
12
A3
3
bj
B3
B4
3
13
8
2
20
4
130
5
30
14
6
100
80
Начальный опорный план:
ai
40
150
130
140
160
100
400
80 40 20 0
X 0 0 130 30
0 0 0 100
z(X) = 1·80 + 11·40 + 3·20 + 8·130 + 2·30 + 6·100 = 2280
7
2. Метод наименьшей стоимости
B1
A1
1
B3
11
80
80
B4
ai
3
13
8
2
60
60
12
A2
4
30
30
130
130
3
A3
bj
B2
5
10
10
80
Начальный опорный план:
14
6
90
40
150
80 0 60 0
X 0 30 0 130
0 10 90 0
130
140
160
100
400
8
z(X) = 1·80 + 4·30 + 5·10 + 14·90 + 3·60 + 2·130 = 1950

9. Решение транспортной задачи методом потенциалов

Теорема
Если опорный план X = (xij) транспортной
задачи является оптимальным, то существуют
потенциалы поставщиков ui,
i = 1,…, m и потребителей vj, j = 1,…, n,
удовлетворяющие условиям:
ui + vj = сij при xij > 0 (для занятых клеток),
Δij = ui + vj — сij ≤ 0 при xij = 0 (для свободных
клеток).
9

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

B1
A1
A2
B2
1
80
B3
11
12
3
60
— 17
8
5
2
130
5
3
13
— 21
4
30
-1
B4
14
6
A3
9
bj
80
40
150
130
vj
1
–6
3
–8
10
90
-3
ai
ui
140
0
160
10
100
11
400
10
Цикл
80
—
+
+
—
60
90
80
—
+
+
—
140
10
Δ = min (80, 90) = 80
11
Новый опорный план
B1
A1
A2
A3
B2
1
-9
3
140
— 17
8
5
10
2
130
5
3
13
— 21
4
30
— 10
B4
11
12
80
B3
14
10
6
-3
bj
80
40
150
130
vj
3
5
14
3
ai
ui
140
-11
160
-1
100
0
400
z(X) = 3·80 + 5·10 + 4·30 + 14·10 + 3·140 + 2·130 = 1230
1950
12
Цикл
30
—
+
10
20
+
—
10
20
—
+
+
—
10
Δ = min (10, 30) = 10
13
Новый опорный план
B1
A1
A2
A3
B2
1
-4
11
B4
3
140
— 12
12
4
13
— 16
8
План
10
130
оптимален!
5
14
2
20
— 10
3
80
B3
20
-5
-3
bj
80
40
150
130
vj
2
4
8
2
6
ai
ui
140
-5
160
0
100
1
400
z(X) = 3·80 + 5·20 + 4·20 + 8·10 + 3·140 + 2·130 = 1180

15.

Открытая модель транспортной задачи Модель
транспортной задачи называется
m
n
открытой, если a b (суммарные
запасы не равны суммарным потребностям).
i 1
i
j 1
j
15
Открытая модель транспортной
задачи
Открытую модель можно свести к закрытой:
1. Если
m
n
i 1
j 1
ai b j
, то вводят фиктивного
потребителя Вn+1 с потребностью
m
n
i 1
j 1
bn 1 ai b j
и нулевыми тарифами перевозок в столбце.
m
n
i 1
j 1
2. Если ai b j ,то вводят фиктивного
поставщика А m+1 с запасом
n
m
j 1
i 1
am 1 b j ai
и
нулевыми тарифами перевозок в строке.
16

17. Задача 2

Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
3
7
4
7
100
A2
10
13
24
7
100
A3
8
19
12
18
200
bj
90
80
30
170
m
i 1
370
n
a b
i
j 1
400
j
17
Метод «северо-западного угла»
B1
A1
A2
3
90
B3
B4
B5
ai
7
4
7
0
13
24
7
0
12
18
0
10
10
70
8
A3
bj
B2
30
19
170
90
80
30
170
30
30
100
100
200
400
z(X) = 3·90 + 7·10 + 13·70 + 24·30 + 18·170 = 5030
18
Метод потенциалов
B1
A1
A2
B2
3
90
B3
7
4
10
14
10
13
70
-1
8
B4
7
17
30
0
6
24
19
— 18 0
B5
7
23
12
0
12
18
0
A3
— 11
bj
90
80
30
170
30
vj
3
7
18
24
6
170
30
ai
ui
100
0
100
6
200
-6
400
19
Цикл
30
0
—
+
—
+
+
—
+
—
170 30
30
140
Δ = min (30, 170) = 30
20
Новый опорный план
B1
A1
A2
B2
3
90
B3
7
10
10
4
-9
13
70
-1
8
B4
7
-6
— 23
0
7
30
12
0
— 11
18
0
A3
12
5
bj
90
80
30
170
30
vj
20
24
12
18
0
30
ai
— 17
24
19
B5
140
30
ui
100 -17
100
-11
200
0
400
z(X) = 3·90 + 7·10 + 13·70 + 7·30 + 18·140 + 12·30 = 4130
21
Цикл
90
—
+
—
+
20
10
70
+
—
—
30
+
140 70
+
—
80
+ 100
— 70
Δ = min (90, 70, 140) = 70
22
Новый опорный план
B1
A1
A2
A3
B2
3
20
B3
7
80
10
— 13
70
4
3
13
— 12
8
B4
-7
7
6
— 23
7
100
12
30
0
-5
24
19
B5
0
— 11
18
70
0
30
bj
90
80
30
170
30
vj
8
12
12
18
0
ai
ui
100
-5
100 -11
200
0
400
z(X) = 3·20 + 7·80 + 8·70 + 12·30 + 18·70 + 7·100 = 3500
23
Цикл
20
70
—
+
—
+
+
—
+
—
70
90
20
50
Δ = min (20, 70) = 20
24
Новый опорный план
B1
A1
A2
A3
bj
vj
B2
3
B3
7
4
80
-6
10
— 13
8
90
13
7
24
30
80
18
30
12
ai
0
— 11
7
План
100
-6
— 23
— 11
оптимален!
19
12
18
Оптимальный план:
8
B5
20
-3
-1
90
B4
50
30
0
0
ui
100 -11
100 -11
200
0
170 0
80 30
0 20 400
X 0 0 0 100
18 90 0 030 50
z(X) = 8·90 + 7·80 + 12·30 + 7·100 + 7·20 + 18·50 = 3380
25

26.

Задача 3 Решите транспортную задачу методом
потенциалов. В ответе укажите
минимальную стоимость всех перевозок.
B1
B2
B3
B4
ai
A1
1
13
12
3
60
A2
2
16
4
6
125
A3
13
4
17
16
75
bj
100
100
50
50
m
i 1
300
n
a b
i
j 1
260
j
26
Метод наименьшей стоимости
B1
A1
A2
B2
B4
ai
1
13
12
3
2
16
4
6
60
40
25
A3
13
A4
0
bj
B3
50
10
4
17
16
0
0
0
75
40
100
100
50
50
60
125
75
40
300
z(X) = 1·60 + 2·40 + 16·25+ 4·75 + 4·50 + 6·10 = 1100
27
Метод потенциалов
B1
A1
A2
B2
1
60
13
2
2
40
B3
B4
12
-9
16
25
3
2
4
50
6
10
A4
13
4
17
16
— 23 75
— 25
— 22
0
0
0
0
40
-4
10
-2
bj
100
100
50
50
vj
2
16
4
6
A3
ai
ui
60
-1
125
0
75
-12
40
-6
300
28
Цикл
25
—
+
+
—
10
40
25
—
+
+
—
35
15
Δ = min (25, 40) = 25
29
Новый опорный план
B1
A1
A2
B2
1
60
B3
13
-8
2
40
B4
12
-9
16
2
4
50
— 10
3
6
35
A4
13
— 13 75
0
25
-4
bj
100
100
50
50
vj
2
6
4
6
A3
4
17
16
— 15
— 12
0
0
0
15
-2
ai
ui
60
-1
125
0
75
-2
40
-6
300
z(X) = 1·60 + 2·40 + 4·75 + 4·50 + 6·35 = 850
30
Цикл
60
40
25
—
+
—
+
+
—
+
—
35
75
35
Δ = min (35, 60) = 35
31
Новый опорный план
B1
A1
A2
A3
B2
1
25
B3
13
— 10
2
B4
12
35
-9
16
3
4
50
— План
12
13
4
17
оптимален!
75
-2
16
— 13
— 12
0
0
0
15
0
75
— 11
6
0
A4
-2
bj
100
100
50
vj
1
3
3
25
Оптимальный план:
ai
ui
60
0
125
1
75
1
40
-3
0 0300
35
25
50
X 75 0 50 0
0 3 75 0 0
z(X) = 1·25 + 2·75 + 4·75 + 4·50 + 3·35 = 780
32
Транспортные задачи с
дополнительными ограничениями
В
некоторых транспортных задачах
наложены дополнительные ограничения на
перевозку грузов.
1. Если в закрытой задаче перевозки от
поставщика Ai к потребителю Bj не могут
быть осуществлены (стоит блокировка),
для определения оптимального решения
задач предполагают, что тариф перевозки
единицы груза равен сколь угодно
большому числу М.
33
2. Если дополнительным условием в задаче является
обеспечение перевозки от поставщика Ai к
потребителю Bj в точности aij единиц груза, в
клетку AiBj записывают указанное число aij, а эту
клетку считают свободной со сколь угодно
большим тарифом М.
3. Если от поставщика Ai к потребителю Bj должно
быть перевезено не менее aij единиц груза, то
запасы пункта Ai и потребности Bj полагают
меньше фактических на aij единиц. После
нахождения оптимального плана перевозку в
клетке AiBj увеличивают на aij единиц.
34
4. Если от поставщика Ai к потребителю Bj
требуется перевезти не более aij единиц
груза, то вводят дополнительного
потребителя Bn+1 = Bij, которому
записывают те же тарифы, что и для Bj, за
исключением тарифа в i–й строке, который
считают равным сколь угодно большому
числу М.
Потребности пункта Bj считают равными
aij, а потребности Bij полагают равными
bj — aij.
35

36. Спасибо за внимание!

36

Решение транспортной задачи в Excel (сбалансированная задача)

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

Цитата взята с википедии.

Решение транспортной задачи рассматривается практически на всех специальностях, где хоть как-то присутствует курс математики. Решить транспортную задачу можно различными способами и программными средствами. Причем если решение такой задачи в математических пакетах типа Mathcad или MATLAB обыденное дело, то решение такой задачи в программе 1С:Предприятие 8.2 уже интересная диковинка.

Смотрите также видео версию статьи «Решение транспортной задачи в Excel (сбалансированная задача)».

Сегодня мы рассмотрим решение сбалансированной транспортной задачи в табличном процессоре MS Excel.

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

Есть запасы однотипной продукции у поставщиков A1, A2, A3, A4.

Существует потребность в этой продукции B1, B2, B3

Стоимость доставки единицы продукции от поставщиков к потребителям представлена в таблице.

Поставщик	Потребитель			Запас
	В1	В2	В2
А1	6	5	2	250
А2	3	7	4	100
А3	7	8	1	80
А4	2	2	3	120
Потребность	150	150	250

Необходимо составить такой план перевозок, который бы удовлетворил все потребности и имел минимальную стоимость.

Решение задачи

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

Для решения транспортной задачи потребуются функции: СУММПРОИЗВ, СУММ и надстройка «Поиск решения».

Для отображения формул необходимо на вкладке «Формулы» в группе «Зависимости формул» выбрать «Показать формулы» либо горячее сочетание клавиш «Ctrl+` (тильда)».

Дальше выбираем команду «Поиск решения» на вкладке «Данные»

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

Решение поставленной задачи представлено ниже.

Примеры решения задач — Линейное программирование — Исследование операций — ЭММ

Условие задачи

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

Решение задачи

Экономико-математическая модель задачи

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

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:   

Проверка транспортной задачи на закрытость

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

В нашем случае:

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

Правило минимального элемента

Заполняем таблицу по правилу минимального элемента.

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту , поэтому в клетку помещаем . В этом случае 5-й столбец в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьшие тарифы имеют клетки  и

Далее действуя по аналогичной схеме:

Число занятых клеток должно быть .

Решение транспортной задачи методом потенциалов

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

Найдем оценки свободных клеток:

S ( 1, 1)= 7-( 0+ 10)= -3	S ( 1, 2)= 20-( 0+ 21)= -1
S ( 2, 3)= 10-(-7+ 3)=  14	S ( 2, 4)= 20-(-7+ 15)=  12
S ( 2, 5)= 0-(-7+ 0)=  7	S ( 3, 1)= 15-( 4+ 10)=  1
S ( 3, 3)= 11-( 4+ 3)=  4	S ( 3, 5)= 0-( 4+ 0)= -4
S ( 4, 1)= 11-(-9+ 10)=  10	S ( 4, 2)= 12-(-9+ 21)=  0
S ( 4, 3)= 18-(-9+ 3)=  24	S ( 4, 5)= 0-(-9+ 0)=  9

Для клетки ( 3, 5) строим цикл.

Найдем оценки свободных клеток:

S ( 1, 1)= 7-( 0+ 10)= -3	S ( 1, 2)= 20-( 0+ 21)= -1
S ( 1, 5)= 0-( 0-4)=  4	S ( 2, 3)= 10-(-7+ 3)=  14
S ( 2, 4)= 20-(-7+ 15)=  12	S ( 2, 5)= 0-(-7-4)=  11
S ( 3, 1)= 15-( 4+ 10)=  1	S ( 3, 3)= 11-( 4+ 3)=  4
S ( 4, 1)= 11-(-9+ 10)=  10	S ( 4, 2)= 12-(-9+ 21)=  0
S ( 4, 3)= 18-(-9+ 3)=  24	S ( 4, 5)= 0-(-9-4)=  13

Для клетки ( 1, 1) строим цикл.

Найдем оценки свободных клеток:

S ( 1, 2)= 20-( 0+ 18)=  2	S ( 1, 5)= 0-( 0-4)=  4
S ( 2, 3)= 10-(-4+ 3)=  11	S ( 2, 4)= 20-(-4+ 15)=  9
S ( 2, 5)= 0-(-4-4)=  8	S ( 3, 1)= 15-( 4+ 7)=  4
S ( 3, 2)= 25-( 4+ 18)=  3	S ( 3, 3)= 11-( 4+ 3)=  4
S ( 4, 1)= 11-(-9+ 7)=  13	S ( 4, 2)= 12-(-9+ 18)=  3
S ( 4, 3)= 18-(-9+ 3)=  24	S ( 4, 5)= 0-(-9-4)=  13

 

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

Минимальные транспортные издержки оптимального плана:

При реализации оптимального плана у поставщика  останется нереализованный товар в размере 85 ед.

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

Решим транспортную задачу в Excel.

Условие транспортной задачи приведено в виде таблицы в Excel

 

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

Далее

в диапазон ячеек h23:h27 запишем ограничения вида:

=F3

=F4

=F5

=F6

=F7

в диапазон ячеек B8:E8 запишем ограничения:

=B8

=C8

=D8

=E8

в диапазон ячеек F13:F17 запишем формулы суммы по строкам:

=СУММ(B13:E13)
=СУММ(B14:E14)
=СУММ(B15:E15)
=СУММ(B16:E16)
=СУММ(B17:E17)

в диапазон ячеек F13:F17 формулы суммы по столбцам:

=СУММ(B13:B17)
=СУММ(C13:C17)
=СУММ(D13:D17)
=СУММ(E13E17)

Затем в ячейки F22 (целевая функция) запишем формулу суммы произведения:

=СУММПРОИЗВ(B3:E7;B13:E17)

В итоги в Excel должна получиться следующая таблица

с формулами

Затем переходим на вкладку Данные -> Поиск решения

В параметре поиска решений задаём

Оптимизировать целевую функцию — задаем ячейку F22

Выбираем минимум

Изменяемые ячейки переменных — задаем диапазон ячеек $B$13:$E$17

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

Затем нажимаем на кнопку Добавить и задаем ограничения

Ограничения по строкам и нажимаем Добавить

Ограничения по столбцам и нажимаем Добавить

Задаем также целочисленные ограничения и нажимаем Добавить и Ок

Можно также зайти в параметры и настроить точность по желанию, нажимаем Ок.

Окно параметров поиска решения транспортной задачи и нажимаем Найти решение

Итак на листе Excel появятся решения, а также окно с результатами поиска решений, здесь можно выбрать Сохранить найденное решение и нажать Ок.

 

Итак, целевая функция равна 5840.

Распределение запасов 

Итак общее решение транспортной задачи в Excel имеет вид

Транспортная проблема 1 | решатель

Свернуть расходы на доставку товаров с заводов покупателям, при этом не более
р поставки доступны с каждой фабрики и удовлетворяют потребности каждого клиента.
Стоимость доставки ($ за товар)
	Направления
	Заказчик 1	Заказчик 2	Заказчик 3	Заказчик 4	Заказчик 5
Завод 1	$ 1.75	2,25 долл. США	$ 1,50	$ 2,00	$ 1,50
Завод 2	$ 2,00	$ 2,50	$ 2,50	$ 1,50	$ 1,00
Количество отгружено товаров
	Заказчик 1	Заказчик 2	Заказчик 3	Заказчик 4	Заказчик 5	Всего	Вместимость
Завод 1	0	0	0	0	0	0	60 000
Завод 2	0	0	0	0	0	0	60 000
Итого	0	0	0	0	0
Спрос	30 000	23 000	15 000	32 000	16 000
Общая стоимость доставка		$ 0
Проблема
А компания хочет минимизировать стоимость доставки товара из 2-х разных фабрики 5 разным клиентам.
каждый Завод имеет ограниченное предложение и у каждого покупателя есть определенный спрос. Как должен компания распространяет
товар?
Решение
1) Переменные — это количество продуктов, которые нужно отправить с каждой фабрики на клиенты.Им дан
наименование Отгружено товаров в листе Transport1.
2) Логический ограничение —
	Products_shipped> = 0 через параметр «Предположить неотрицательный результат»
Два других ограничения
	Всего_получено> = Спрос
	Total_shipped <= Вместимость
3) цель — минимизировать стоимость.Это называется Total_cost.
Примечания
Это это транспортная проблема в простейшей форме.Тем не менее, этот тип модели широко используется для спасения многих
тыс. Шт. долларов каждый год.
дюйм Рабочий лист Transport2 рассмотрим 2-х уровневую транспортировку, а в рабочий лист Transport3 мы расширяем его до
а многопродуктовая, двухуровневая транспортная задача.

Задача транспортировки в Excel — Easy Excel Tutorial

Сформулируйте модель | Метод проб и ошибок | Решите Модель

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

Сформулируйте модель

Модель, которую мы собираемся решить, выглядит в Excel следующим образом.

1. Чтобы сформулировать эту задачу перевозки , ответьте на следующие три вопроса.

а. Какие решения нужно принять? Для этой проблемы нам понадобится Excel, чтобы узнать, сколько единиц нужно отправить с каждой фабрики каждому покупателю.

г. Что сдерживает эти решения? Каждая фабрика имеет фиксированное предложение, и каждый покупатель имеет фиксированный спрос.

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

2. Чтобы облегчить понимание модели, создайте следующие именованные диапазоны.

Название диапазона	Ячейки
Стоимость единицы	C4: E6
Отгрузки	C10: E12
Итого	C14: E14
Спрос	C16: E16
Итого	G10: G12
Поставка	I10: I12
Общая стоимость	I16

3.Вставьте следующие функции.

Объяснение: Функции СУММ вычисляют общую сумму, отгруженную с каждого завода (Total Out) каждому покупателю (Total In). Общая стоимость равна сумме затрат на единицу и отгрузок.

Пробная версия и ошибка

С этой формулой становится легко анализировать любой пробный раствор.

Например, если мы отправляем 100 единиц с завода 1 клиенту 1, 200 единиц с завода 2 клиенту 2, 100 единиц с завода 3 клиенту 1 и 200 единиц с завода 3 клиенту 3, итоговый выход равен поставке и общему поступлению. равно Спросу.Это решение имеет общую стоимость 27800.

Необязательно использовать метод проб и ошибок. Далее мы опишем, как можно использовать Excel Solver для быстрого поиска оптимального решения.

Решите модель

Чтобы найти оптимальное решение, выполните следующие действия.

1. На вкладке «Данные» в группе «Анализ» щелкните «Решатель».

Примечание. Не можете найти кнопку «Решатель»? Щелкните здесь, чтобы загрузить надстройку Solver.

Введите параметры решателя (читайте дальше). Результат должен соответствовать рисунку ниже.

У вас есть выбор: ввести имена диапазонов или щелкнуть ячейки в электронной таблице.

2. Введите общую стоимость для цели.

3. Щелкните Мин.

4. Введите отгрузки для изменения ячеек переменной.

5. Щелкните Добавить, чтобы ввести следующее ограничение.

6.Щелкните Добавить, чтобы ввести следующее ограничение.

7. Отметьте «Сделать неограниченные переменные неотрицательными» и выберите «Simplex LP».

8. Наконец, нажмите «Решить».

Результат:

Оптимальное решение:

Заключение: оптимально отгрузить 100 единиц с завода 1 заказчику 2, 100 единиц с завода 2 заказчику 2, 100 единиц с завода 2 заказчику 3, 200 единиц с завода 3 заказчику 1 и 100 единиц с завода 3 до заказчика. Клиент 3.Это решение дает минимальную стоимость 26000. Все ограничения соблюдены.

Использование симплексного метода транспортировки для решения транспортных задач

Симплексный алгоритм транспортировки

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

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

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

Как это выглядит

Давайте начнем заполнять транспортную матрицу, чтобы у нас были все наши данные в одном месте. Во-первых, мы находим стоимость одной грузовой машины от каждого из наших поставщиков в каждый из наших пунктов назначения. Доставка от Поставщика 1 до пункта назначения 1 будет стоить 464 доллара США за грузовик, а доставка от Поставщика 1 до пункта назначения 2 и т. Д. Будет стоить 513 долларов США за грузовик.

Матрица транспортировки: стоимость доставки

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

Транспортная матрица: спрос и предложение

Метод наименьшей стоимости

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

Мы ищем в нашей транспортной матрице ячейку с наименьшей стоимостью (отмечена здесь красным). Мы хотим направить на этот транспортный маршрут как можно больше поставок. В пункте назначения 2 нужно 85 грузовиков, в пункте снабжения 2 — 125, поэтому мы собираемся выполнить весь заказ пункта назначения 2 из пункта снабжения 2 (синим цветом).

Теперь мы находим следующую наименьшую стоимость, Поставщик 2 для пункта назначения 1 (снова показан красным). Мы уже назначили 85 из доступных запасов Припуска 2, поэтому у нас есть только 40 для назначения 1 из Припуска 2.

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

Следующая самая низкая стоимость — Поставка 1 в пункт назначения 1.

Это оставляет нам 10 из Ресурса 1, чтобы заполнить Пункт назначения 3 по 654 доллара.

Расчет затрат

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

Откуда мы знаем, что у нас есть лучшее решение нашей транспортной проблемы? Надо это проверить!

Тест на оптимальность

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

Сначала, как и наша транспортная матрица, настроим данные о затратах:

Excel Solver: стоимость доставки

Затем мы настроим данные об объеме, включая формулы для суммирования спроса и предложения, а также общих транспортных расходов.

Решатель: Объем

Теперь мы готовы использовать Решатель. Давайте разделим диалоговое окно на более мелкие части, чтобы вы могли четко видеть каждую из них.

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

Решатель Excel: Целевая ячейка

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

Решатель: ограничения

Мы устанавливаем наш метод решения как Simplex LP (что является линейным программированием), а затем выбираем «Решить»

Excel Solver: метод решения

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

Решатель: Решение

Заставляет задуматься, почему мы просто не использовали для начала Excel Solver, не так ли?

Резюме урока

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

Если вы хотите увеличить прибыль и минимизировать расходы, наиболее точным методом является метод минимальной стоимости ячейки .Затем результаты подвергаются тесту на оптимальность, чтобы убедиться, что найдено лучшее решение. Инструмент Excel Solver — самый эффективный способ проверить решение.

Объяснение транспортной проблемы | Что такое проблема с транспортировкой?

1. Проблема с транспортировкой
2. Проблема с балансировкой
3. Проблема с несбалансировкой
4. Пример
5. Заключение

9058 Автор: Patrick

Введение

Исследование операций (OR) — это современный подход, используемый для решения проблем и принятия решений.ИЛИ помогает любой организации достичь наилучших результатов в данных ограничениях или обстоятельствах. Известные операционные методы:

• Линейное программирование
• Целевое программирование
• Целочисленное программирование
• Динамическое программирование
• Сетевое программирование

Одной из проблем, с которыми сталкиваются организации, является транспортная проблема. Первоначально это означает проблему транспортировки / доставки товаров из отрасли в пункты назначения с наименьшими возможными затратами при соблюдении ограничений спроса и предложения.Это особый класс техники линейного программирования, который был разработан для моделей с линейной целевой функцией и функциями ограничений. Их применение может быть распространено на другие сферы деятельности, в том числе на

• Планирование и управление временем
• Оптимизация сети
• Управление запасами
• Планирование ресурсов предприятия
• Планирование процессов
• Оптимизация маршрутов

Дуга задачи транспортировки LP и узловая диаграмма

Обозначения изображения:

млн источников и n направлений

(i, j) объединение источника (i) и назначения (j)

c _ij 🡪 Транспортные расходы за единицу

x _ij 🡪 отгруженное количество

a _i 🡪 объем поставки в источнике (i)

b _j 🡪 объем спроса в пункте назначения (j)

Транспортная задача работает таким образом, чтобы минимизировать функцию затрат.Здесь функция затрат — это сумма денег, потраченная поставщиком логистических услуг на транспортировку товаров от места производства или поставщика до места спроса. Стоимость транспорта зависит от многих факторов. Он включает в себя расстояние между двумя точками, пройденный путь, вид транспорта, количество перевозимых единиц, скорость транспортировки и т. Д. Таким образом, основное внимание здесь уделяется транспортировке товаров с минимальными транспортными затратами без каких-либо компромиссов в спрос и предложение. Транспортная проблема является расширением техники линейного программирования, потому что транспортные расходы формулируются как линейная функция от возможностей предложения и спроса.

Транспортная проблема существует в двух формах.

1. Сбалансированный
2. Несимметричный

Сбалансированный

Это случай, когда общее предложение равно общему спросу.

Несимметричный

Это случай, когда либо спрос превышает предложение, либо наоборот.

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

Давайте разберемся с этим гораздо проще на простом примере.

Пример

Предположим, что существует ведущая мировая компания-поставщик автомобилей под названием JIM. JIM имеет производственные предприятия во многих странах и поставляет продукцию всем ведущим автопроизводителям в мире.Например, предположим, что в Индии есть три завода в точках M, N и O. Производительность заводов составляет 700, 300, 550 в сутки. Завод обслуживает четырех клиентов A, B, C и D, потребность которых составляет 650, 200, 450, 250 в день. Стоимость транспортировки за единицу за км в INR и расстояние между каждым источником и пунктом назначения в км приведены в таблицах ниже.

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

Решение

Многие сложные языки программирования эволюционировали для решения задач ИЛИ гораздо более простым и легким способом. Но значение Microsoft Excel нельзя ставить под угрозу или обесценивать. Это также дает нам лучшее понимание проблемы, чем другие. Следовательно, мы будем использовать Excel для решения проблемы.

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

Шаги, которые необходимо выполнить для решения проблемы:

1. Создайте транспортную матрицу (определите переменные решения)
2. Определите целевую функцию
3. Сформулируйте ограничения
4. Решите с использованием метода LP

Шаг 1

Создание транспортной матрицы:

Транспортная матрица — это способ понять максимальные возможности перевозки. Он также известен как переменные решения, потому что это представляющие интерес переменные, которые мы изменим для достижения цели, то есть минимизации функции затрат.

ma 905 55 _oa 900

От / до	A	B	C	D	Поставка
M	x mb	x mc	x md	700
8	700
8 na	x nb	x nc	x nd	300	x ob	9058 8 x oc	x od	550
Спрос	650	2 200

Шаг 2

Определите целевую функцию:

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

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

Столбец «Всего отгружено» представляет собой сумму столбцов A, B, C и D для соответствующих строк, а строка «Общий спрос» представляет собой сумму строк M, N и O для соответствующих столбцов. Эти два столбца вводятся для удовлетворения ограничений количества спроса и предложения при решении функции затрат.

Шаг 3

Сформулируйте ограничения:

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

Например, четвертое ограничение, x _ma + x _na + x _oa = 650, используется для обеспечения того, чтобы количество единиц, поступающих от заводов M, N и O к потребителю A, не уменьшалось ниже или выше спроса, который имеет А. Точно так же первое ограничение x _ma + x _mb + x _mc + x _md = 700 гарантирует, что мощность завода M не будет ниже или выше заданной мощности, следовательно, установка может быть использована. в полной мере использовать без ущерба для инвентаря.

Шаг 4

Решите с помощью метода LP:

Самый простой и эффективный метод решения — использование решателя. Входные параметры вводятся, как указано ниже, и переходят к решению.

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

Из найденного решения видно, что завод M отгружает 100 единиц клиенту A, 350 единиц C и 250 единиц D.Но почему клиенту Б ничего не делать? Аналогичная тенденция наблюдается и для других растений.

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

Итак, когда эти поставщики нулевой единицы станут прибыльными и смогут поставлять этим клиентам? Ждать! Без паники. Excel тоже ушел. После продолжения решения появится диалоговое окно, в котором выберите отчет о чувствительности и нажмите OK.Вы получите прекрасный отчет о чувствительности, в котором подробно описываются альтернативные издержки или ценность ресурса.

Отчет о чувствительности

Основное объяснение переменных отчета,

Ячейка: Идентификатор ячейки в Excel

Имя: Сопряжение поставщика и клиента

Окончательное значение: Количество отгруженных единиц (после решения)

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

Объективный коэффициент: Текущие транспортные расходы на единицу на км для каждой пары поставщиков и клиентов

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

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

Посмотрите на первую строку отчета о чувствительности.Завод M поставляет покупателю A. Здесь стоимость транспортировки единицы на км составляет 14 фунтов стерлингов, а 100 единиц отгружаются клиенту A. В этом случае стоимость транспортировки может увеличиться максимум на 6 фунтов стерлингов и может снизиться до максимума. ₹ 1. Для любого значения в этом диапазоне окончательное решение не изменится.

Теперь кое-что интересное. Посмотрите на второй ряд. Между MB нет ни одной единицы, поставляемой потребителю B с завода M. Текущая стоимость доставки составляет 22 фунта стерлингов, и для того, чтобы сделать эту пару прибыльной и начать бизнес, стоимость должна снизиться на 6 фунтов стерлингов за единицу на км.Тогда как нет возможности увеличить стоимость даже на рупию. Если стоимость доставки для этой пары снизится до 16 фунтов стерлингов, мы можем ожидать, что между ними начнется бизнес, и окончательное решение изменится соответствующим образом.

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

Заключение

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

Если вы нашли это полезным и хотите узнать больше о таких концепциях, отправляйтесь в Great Learning Academy и записывайтесь на бесплатные онлайн-курсы сегодня.

2

Как решать транспортные проблемы с помощью Excel Solver

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

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

Транспортная проблема

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

Вот список информации, необходимой для решения транспортной проблемы:

• Спрос на продукцию на каждом объекте назначения.
• Расположение объектов и расстояния между каждым объектом-источником и пунктом назначения.
• Стоимость за километр пути.
• Максимальная емкость каждого источника.

Ниже представлена ​​схема сети, которую мы собираемся использовать. Это простая сеть с двумя этапами: три распределительных центра, а остальные восемь объектов — это магазины. Объекты нанесены на карту с помощью программы SCM Globe .

А ниже — более абстрактная сетевая диаграмма модели цепочки поставок, показанной выше:

Переход на Excel

Теперь, когда мы определили проблему и сетевую модель, пора перейти в Excel, чтобы ввести данные и провести анализ.

Первым шагом в нашем процессе является систематизированный ввод необходимых нам данных из модели цепочки поставок. Начните с ввода спроса каждого магазина; Это дает нам общую потребность в 1190 единиц в данном случае. Затем введите единицу складской емкости для каждого распределительного центра. Это дает нам общую емкость 2100 единиц. Мы легко видим, что у нас достаточно мощностей, чтобы удовлетворить рыночный спрос.

Второй шаг — ввести расстояния между всеми источниками и пунктами назначения.Эти расстояния туда и обратно предоставляются программным обеспечением SCM Globe . Стоимость 1 км составляет 0,60 доллара США, что является значением по умолчанию в программном обеспечении для больших грузовиков. Это значение по умолчанию может быть изменено для точного отражения текущих фактических затрат на километр на основе ваших исследований.

Затем создайте изменяющиеся переменные в шаблоне электронной таблицы. Помните, что наша цель — найти объемы доставки от РЦ до магазинов, которые минимизируют транспортные расходы и при этом удовлетворяют спрос магазина. Следовательно, изменяющиеся переменные в нашем случае — это количество единиц, движущихся по каждому маршруту.

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

Перед созданием и запуском нашей решающей модели мы должны определить формулу общей стоимости. Здесь у нас есть два варианта:

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

В нашем случае у нас есть только стоимость километра пути, поэтому мы воспользуемся первым вариантом. Чтобы узнать, сколько грузовиков нам нужно, чтобы доставить количество, понесенное из одного ЦОД в магазин, мы должны разделить это количество на максимальный объем перевозки наших грузовиков и округлить это число в большую сторону (функция ROUNDUP в Excel). В нашем примере мы предполагаем, что максимальная грузоподъемность одного большого грузовика составляет 110 единиц. В этом случае количество необходимых доставок будет равно « ЗА НЕДЕЛЮ (I15: K22 / 110; 0)» .Формула общей стоимости перевозки: « СУММПРОИЗВ (C15: E22; ROUNDUP (I15: K22 / 110; 0)) * C24 ».

Если у вас есть стоимость километра за единицу, то формула будет в основном « СУММПРОИЗВ (C15: E22; I15: K22) * C24» . Здесь следует иметь в виду, что в этой простой транспортной задаче стоимость за км или стоимость за км за единицу не меняют решения, а влияют только на общую стоимость.

Создание и запуск модели решателя

Давайте определим целевую функцию и ограничения нашей модели:

• Целевая функция : Цель нашей модели — минимизировать общие затраты.
• Ограничения : Во-первых, у нас есть ограничения спроса, поэтому для удовлетворения спроса общее количество, доставленное в каждый магазин, должно быть равно спросу этого магазина. Во-вторых, количество, поставляемое с каждого ЦОД, не должно превышать его единичной мощности. И, в-третьих, переменная решений, которая представляет собой поставленное количество, должна быть целым числом и быть больше или равна нулю.

Теперь давайте посмотрим, как мы можем применить это к надстройке Excel Solver. Сначала перейдите на вкладку «Данные» и нажмите кнопку «Решатель», которая находится справа.[Если вы еще не установили Решатель, перейдите по этой ссылке, чтобы узнать, как его установить: https://www.solver.com/excel-solver-how-load-or-start-solver.]

Когда откроется вкладка решателя, мы должны установить цель. В нашем случае мы выделяем ячейку «I25» зеленым цветом; это наша общая стоимость. Изменяемые нами переменные сгруппированы в желтой матрице, поэтому мы выбираем эту матрицу во втором блоке.

Что касается ограничений, мы должны нажать кнопку «Добавить». Три созданных ограничения показаны на рисунках ниже.После добавления всех этих ограничений мы должны сначала сделать неограниченные переменные неотрицательными, установив флажок. Соблюдая эти установленные ограничения, мы можем запустить нашу модель решателя, выбрав Simplex LP (метод решения, поскольку наша модель является линейной).

Наша модель готова, поэтому нажмите кнопку «Решить». Мы видим, что переменные решения и общая стоимость меняются. Результатом является предварительное оптимальное решение нашей транспортной задачи.

Интерпретация результатов

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

В этом примере мы получили общую стоимость 3991,20 доллара, что приемлемо, но мы замечаем, что единственный склад, который будет использовать его максимальную емкость, — это DC Nbr 1. DC Nbr 3 использует 60% своего максимального хранилища. мощность, а DC Nbr 2 использует только 10%. Отсюда вопрос: нужно ли открывать все три распределительных центра на следующий период?

Можно сказать, что при использовании всего двух объектов стоимость эксплуатации объектов снизится, но транспортные расходы могут возрасти.Чтобы найти оптимальное решение, мы должны сравнить общую стоимость двух разных сценариев. Какой сценарий предлагает наименьшую общую стоимость при одновременном удовлетворении спроса магазина? В первом сценарии компания открывает и использует все свои DC, оплачивая все свои постоянные затраты. Во втором сценарии компания управляет только двумя своими ДЦ, а третий закрывает.

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

Заключение

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

Ситуации меняются от месяца к месяцу. Оптимальное решение этого месяца может быстро стать большой ошибкой в ​​следующем месяце. Компании строят свой курс каждый месяц, сочетая числовые вычисления с профессиональным суждением, чтобы успешно ориентироваться в постоянно меняющемся мире.

Особая благодарность г-ну Кертису Фраю за качество его курса под названием «Анализ цепочки поставок Excel: решение транспортных проблем» в LinkedIn Learning.Мы основали нашу демонстрацию Excel на его способе организации шаблона электронной таблицы.

Оптимизация транспортной проблемы Решена в Excel

Для версий Excel : Excel для Office 365, Excel для Office 365 для Mac, Excel 2016, Excel 2016 для Mac, Excel 2013, Excel 2011 для Mac, Excel 2010, Excel 2008 для Mac, Excel 2007

Оптимизация сетевого транспорта и линейное программирование в Excel

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

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

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

• Вы пытаетесь СНИЗИТЬ расходы, одновременно удовлетворяя спрос
• Перемещение продукции с заводов (происхождение) в распределительные центры (место назначения)
• Обычно вам дают:
• Производственные мощности (снабжение) → что может производить каждое предприятие
• Требования (Спрос) → прогнозы потребностей потребителей по «регионам»
• Затраты на транспортировку продукции по каждому пути

Вам также может быть интересна оптимизация линейного программирования.

Таблицу, используемую в этом видео, можно скачать здесь.

Транспортная проблема | Набор 6 (Метод MODI — УФ-метод)

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

1. Метод северо-западного угла
2. Метод наименьшей стоимости ячейки
3. Метод аппроксимации Фогеля

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

Решение:

Шаг 1: Проверьте, устранена ли проблема.
Если общая сумма всех поставок из источников O1 , O2 и O3 равна общей сумме всех потребностей для пунктов назначения D1 , D2 , D3 и D4 тогда транспортная проблема — это проблема сбалансированного транспорта.

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

Шаг 2: Нахождение начального базового допустимого решения.
Для поиска начального базового допустимого решения можно использовать любой из трех вышеупомянутых методов. Здесь будет использоваться метод северо-западного угла. И согласно методу северо-западного угла, это окончательное начальное базовое возможное решение:

Теперь общая стоимость перевозки составит (200 * 3) + (50 * 1) + (250 * 6) + (100 * 5) + (250 * 3) + (150 * 2) = 3700 .

Шаг 3: Метод U-V для оптимизации исходного базового возможного решения.
Ниже приводится исходное базовое возможное решение:

— Для метода U-V необходимо найти значения u _i и v _j соответственно для строк и столбцов. Поскольку есть три строки, необходимо найти три значения u _i , т.е. u ₁ для первой строки, u ₂ для второй строки и u ₃ для третьей строка.
Аналогично, для четырех столбцов необходимо найти четыре значения v _j , т.е. v ₁ , v ₂ , v ₃ и v ₄ . Проверьте изображение ниже:

Существует отдельная формула для поиска u _i и v _j ,
u _i + v _j = C _ij где C _ij — значение стоимости только для выделенной соты.Об этом подробнее здесь.

Перед применением приведенной выше формулы нам необходимо проверить, равно ли m + n — 1 общему количеству выделенных ячеек или нет, где m — общее количество строк, а n — общее количество столбцов. .
В этом случае m = 3, n = 4 и общее количество выделенных ячеек равно 6, поэтому m + n — 1 = 6. Случай, когда m + n — 1 не равно общему количеству выделенных ячеек, будет обсуждаться в более поздние сообщения.

Теперь, чтобы найти значение для u и v, мы присваиваем любому из трех u или любому из четырех v как 0.Положим в этом случае u ₁ = 0 . Затем, используя приведенную выше формулу, мы получим v ₁ = 3 как u ₁ + v ₁ = 3 (т.е. C ₁₁ ) и v ₂ = 1 как u ₁ + v ₂ = 1 (т.е. C ₁₂ ). Точно так же мы получили значение для v ₂ = 1 , поэтому мы получаем значение для u ₂ = 5 , что подразумевает v ₃ = 0 .Из значения v ₃ = 0 мы получаем u ₃ = 3 , что подразумевает v ₄ = -1 . См. Изображение ниже:

Теперь вычислите штрафы по формуле P _ij = u _i + v _j — C _ij только для нераспределенных ячеек. У нас есть две нераспределенные ячейки в первой строке, две во второй строке и две в третьей строке. Давайте посчитаем это один за другим.

1. Для C ₁₃ , P ₁₃ = 0 + 0-7 = -7 (здесь C ₁₃ = 7 , u ₁ = 0 и v ₃ = 0 )
2. Для C ₁₄ , P ₁₄ = 0 + (-1) -4 = -5
3. Для C ₂₁ , P ₂₁ = 5 + 3 — 2 = 6
4. Для C ₂₄ , P ₂₄ = 5 + (-1) — 9 = -5
5. Для C ₃₁ , P ₃₁ = 3 + 3-8 = -2
6. Для C ₃₂ , P ₃₂ = 3 + 1-3 = 1

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

Теперь найдите максимальный положительный штраф. Здесь максимальное значение равно 6, что соответствует ячейке C ₂₁ . Теперь эта ячейка является новой базовой ячейкой. Эта ячейка также будет включена в решение.

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

Назначьте альтернативный знак плюс-минус всем ячейкам с прямым поворотом (или углом) в цикле со знаком плюс, назначенным в новой базовой ячейке.

Считайте ячейки с отрицательным знаком. Сравните назначенное значение (например, 200 и 250 в данном случае) и выберите минимальное (например, выберите 200 в этом случае). Теперь вычтите 200 из ячеек со знаком минус и прибавьте 200 к ячейкам со знаком плюс. И нарисуйте новую итерацию.Работа цикла окончена, и новое решение выглядит так, как показано ниже.

Убедитесь, что общее количество выделенных ячеек равно (m + n — 1). Снова найдите значения u и v, используя формулу u _i + v _j = C _ij , где C _ij — это стоимость только для выделенной ячейки. Присваиваем u ₁ = 0 , тогда получаем v ₂ = 1 . Аналогичным образом мы получим следующие значения для u _i и v _j .

Найдите штрафы для всех нераспределенных ячеек по формуле P _ij = u _i + v _j — C _ij .

1. Для C ₁₁ , P ₁₁ = 0 + (-3) — 3 = -6
2. Для C ₁₃ , P ₁₃ = 0 + 0 — 7 = -7
3. Для C ₁₄ , P ₁₄ = 0 + (-1) — 4 = -5
4. Для C ₂₄ , P ₂₄ = 5 + (-1) — 9 = -5
5. Для C ₃₁ , P ₃₁ = 0 + (-3) — 8 = -11
6. Для C ₃₂ , P ₃₂ = 3 + 1-3 = 1

Имеется одно положительное значение i.е. 1 для C ₃₂ . Теперь эта ячейка становится новой базовой ячейкой.

Теперь нарисуйте петлю, начиная с новой базовой ячейки. Назначьте альтернативный знак плюса и минуса с новой базовой ячейкой, назначенной знаком плюса.

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

Проверьте, равно ли общее количество выделенных ячеек (m + n — 1).Найдите значения u и v, как указано выше.

Теперь снова найдите штрафы для нераспределенных ячеек, как указано выше.

1. Для P ₁₁ = 0 + (-2) — 3 = -5
2. Для P ₁₃ = 0 + 1-7 = -6
3. Для P ₁₄ = 0 + 0-4 = -4
4. Для P ₂₂ = 4 + 1-6 = -1
5. Для P ₂₄ = 4 + 0-9 = -5
6. Для P ₃₁ = 2 + (-2) — 8 = -8

Все значения штрафа являются отрицательными.