В статье описана актуальность применения программных средств для решения оптимизационных задач линейного программирования на примере транспортных задач в поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение в различных областях экономики и производства. Сделан вывод, что немашинный способ решения приводит к громоздким вычислениям и поэтому целесообразно использовать компьютерные расчеты.
В связи с этим основное внимание в статье уделяется применению различных программных средств для решения таких задач. На конкретном примере описаны алгоритмы вычисления транспортной задачи с помощью пакета OpenOffice.org Calc , САПР MathCAD, Lingo (demo – версия). Анализ различных программных продуктов предоставляет возможность осуществить правильный выбор для решении транспортной задачи в зависимости от специфики технического задания. Выбор конкретного программного продукта зависит также от возможности пользователей и его целей.
Транспортная задача для чайников по шагам за 15 минут. Применение транспортной задачи в экономике
транспортная задача
оптимизация
программные средства
1. Решение транспортных задач: учеб. пособие / А.В. Семериков. – Ухта: УГТУ, 2013. – 58 с.
2. Симаков Е.Е. Решение транспортных задач с применением программирования в системе MathCAD / Е.Е. Симаков, Е. Ким // Молодой ученый. – 2014. – № 5. – С. 8–13.
3. Приходькова И.В. Информатика в транспортной отрасли: лабораторный практикум. Решение транспортных задач: учеб. пособие / И.В. Приходькова, И.Г. Лемешкина, Е.С. Павлова. – Волгоград: ВолгГТУ, 2014. – 80 с.
5. LINGO Demo [Электронный ресурс]. URL: http://www.hearne.software/Software/lingo/demos (дата обращения: 19.05.2017).
7. Фурина К.О. О Решении задач большой размерности в пакете MATHCAD на примере транспортной задачи / К.О. Фурина // Современные проблемы науки и образования. – 2015. – № 1–1. URL: https://science-education.ru/ru/article/view?id=17348 (дата обращения: 16.06.2017).
8. Бексултанов Ж.Т., Баетов А.К. Решение транспортной задачи с помощью программы «Оптимал» / Ж.Т. Бексултанов, А.К. Баетов // Известия вузов Кыргыстана. – 2016.– № 2. – С. 3–6. URL: https://elibrary.ru/item.asp?id=25829247.
9. Родина Е.В. Общая постановка и применение транспортной задачи в сфере железнодорожного обслуживания / Е.В. Родина, Р.Х. Нураева, Х.Х. Сафаралиева// Современные наукоемкие технологии. – 2013. – № 6. – С. 84–86.
URL: https://top-technologies.ru/ru/article/view?id=31994 (дата обращения: 16.06.2017).
10. Цыплакова О.Н., Цысь Ю.В., Кобылина А.В. Транспортная задача и её применение в решении экономических задач / О.Н. Цыплакова, Ю.В. Цысь, А.В. Кобылина // Современные наукоемкие технологии. – 2014. – № 5–2. – С. 178–180.
Во многих областях производственно-экономической деятельности возникает необходимость в решении задач для определения максимального эффекта при заданных ограничениях на различные виды ресурсов [1]. Ввиду сложности современных объектов исследования для их модельного описания используются различные подходы, например – линейное программирование, частью которого являются транспортные задачи.
Транспортная задача (закрытая, с циклом). Метод потенциалов — подробно и понятно
В классическом варианте они ассоциируются с перемещением груза от поставщиков к потребителям. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки.
Всё это уменьшает стоимость доставки товаров, связанные с осуществлением процессов снабжения материалами, сырьём, оборудованием, топливом и т.д. Тем не менее алгоритмы и методы решения транспортной задачи могут быть использованы при рассмотрении других типов задач, не относящихся к классу объектов транспортировки груза, например сетевое, календарное планирование, составление расписания, оптимальное обеспечение материальными ресурсами предприятия, распределение торговых агентов и т.д. Известно, что при использовании методов линейного программирования необходимо выполнять многочисленные последовательные арифметические операции, причем ошибка на любом этапе решения приводит к неверному конечному результату, а повторные вычисления зачастую занимают много времени. Поэтому широкое практическое использование этой теории связано с появлением ЭВМ и соответствующего программного обеспечения.
При решении транспортной задачи используют стандартные программные средства (например, OpenOffice.org Calc, MS Excel, САПР MathCAD и др.) и специализированные программы (например, Lingo (demo-версия)), в том числе написанные на определенном языке программирования высокого уровня.
Как показал анализ литературы, например [1, 2, 6–10], ранее не проводилась оценка сложности в использовании и сравнительные характеристики современных программных средств для решения транспортных задач, что предоставило бы удобный инструмент для специалиста в области автоматизации такого рода вычислений для решения задач различного масштаба производственных и торговых предприятий. Поэтому рассмотрение способов решения транспортной задачи с использованием наиболее распространенных алгоритмических и программных средств с последующим их анализом является актуальной задачей и обладает научно-практической новизной.
Для решения поставленной задачи в качестве примера решим следующую типовую транспортную задачу. В трех пунктах отправления A1, A2 и A3 находится соответственно 34, 30 и 27 т горючего. Потребителям В1, В2, В3 и В4 требуется соответственно 25, 19, 29 и 21 т горючего. Стоимость перевозки одной тонны горючего из пункта А1 в пункты В1, В2, В3 и В4 соответственно 6, 2, 5 и 5 рублей за тонну горючего, из А2 – 4, 7, 3 и 6 руб., а из В3 – 2, 4, 1 и 5. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей (таблица).
План перевозок горючего
Источник: top-technologies.ru
Решение закрытой транспортной задачи с дополнительными условиями средствами 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] mass2 = (x[3] + x[4] +x[5] mass3 = (x[6] + x[7] + x[8] 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. Установка верхней границы объёма поставок товара для поставщика.
Для этого меняются условия на строку таблицы объёмов доставок товаров. Например, для объёмов доставки товаров второго поставщика было ограничение сверху mass2 = (x[3] + x[4] +x[5] заменим на mass2 = (x[3] + x[4] +x[5] == 40).
4. Паритет на поставки второго и третьего поставщиков
Для этого приравниваются объёмы поставок нескольких поставоких поставщиков, что обычно делается для улучшения бизнес климата. Например 6объёмы доставок товаров второго и третьего поставщика транспортных услуг соответственно ограничены сверху mass3 = (x[6] + x[7] + x[8] на 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] = 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] = 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] = 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] = 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
Результат:
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
Результат:
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
Результат:
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
Результат:
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 имеет более компактную запись условий транспортной задачи, что облегчает его работу с интерфейсом.
Всем спасибо за внимание!
Ссылки
- Решение задач линейного программирования с использованием Python.
- CVXOPT Modeling.
- Optimization.
- Optimization with PuLP.
Источник: habr.com
TMiAZhDS_Shulyndin_1 / Программы / Трансп_задача / TZ_Excel / транспортная_задача
. проги для решения транспортных задач (не знаю, что это за задачи, . Но программа нужна не мне, а моему хорошему знакомому (он живет не . forum.tsure.ru/index.php?showtopic. — Сохраненная копия — Похожие
Другие результаты поиска по форумам
Balabasnia forever 🙂
Назначение: программа автоматизации обучения решению транспортных задач в . Имеется подробный файл помощи по теории решения транспортных задач в . balabasnia.narod.ru/. /optimal.html — Сохраненная копия — Похожие
TransTrade — транспортная программа, решение транспортных задач .
Транспортная программа для автоматизации транспортного предприятия и решения транспортных задач, связанных с перевозками и грузоперевозками. transoft.ru/software/ — Сохраненная копия
Транспортная задача
В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, . naukoved.ru/content/view/901/44/ — Сохраненная копия — Похожие
Программа на Delphi для решения транспортной задачи — статья
Программа на Delphi для решения транспортной задачи в каталоге лучших рефератов сети, всего более 240 000 работ. referats.allbest.ru/. /110742.html — Сохраненная копия — Похожие
Поисковые запросы, связанные с Программа решения транспортной задачи
решение транспортной задачи симплекс методом
excel транспортная задача
Источник: studfile.net