python

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

  • воскресенье, 4 июня 2017 г. в 03:14:20
https://habrahabr.ru/post/330138/
  • Python


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


Стандартная транспортная задача приведена в следующей таблице [1].



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

Для открытой задачи запасы поставщиков и потребности равны — Для закрытой задачи они разные —

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


Для закрытой задачи. В математической модели для закрытой задачи целевая функция та же что и в открытой, а условий два.
Для условия — :
— целые числа; (3)

Для условия — ;

— целые числа; (4)

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

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



Такие модели не всегда имеют решение. Условием решаемости является наличие хотя бы одного допустимого решения.

Ограничение по задержке на таможне однородного груза объёмом d.



где натуральное число d, удовлетворяет условию:



В этом случае решение модели (6) дает план перевозок минимизирующий транспортные расходы, и, соответственно, план размещения груза на таможнях:

Если или , то модель (6) принимает вид (1, 3) или (1, 4), соответственно.

Приоритеты


При условии в соотношении (3) для некоторых значений индекса i, пробегаемых переменной I, добавляются ограничения .

При условии в соотношениям (4) для некоторых значений индекса j, пробегаемых переменной J, добавляются ограничения.



Ограничения (7, 8) появляются тогда, когда торговые отношения с каким-либо поставщиком или потребителем ограничены по времени, например, при покупке или продажи энергоносителей сезонного потребления. То, что в определенный срок не вывезено – будет продано другим. То, что не завезено – позже восполнить нельзя, а значит, такие пункты должны быть обязательно закрыты.

Паритет


При условии в (1, 3) для некоторых значений i, k добавляется ограничение то есть из пунктов и вывозятся равные объемы груза.

При условии в (1, 4) для некоторых значений j, r добавляются ограничения то есть в пункты и завозятся равные объемы груза.

Об особенностях решателя CVXOPT в среде моделирования Python [2]


CVXOPT обеспечивает возможность задавать элементы модели в матричном виде, что очень удобно. Переменные модели могут быть заданы при помощи класса cvxopt. modeling. variable. Например, так x = variable (9, 'x').

Для класса variable ограничения могут определяться как логические выражения с одним из операторов “<=”, “==”, “>=”, операндами которого являются линейные выражения относительно объектов variable. В том числе, могут использоваться и векторные операции. Например, для скалярных выражений применительно к транспортной задаче:




Функция cvxopt. modeling. op по переданым в качестве параметров целевой функции переменным и набору ограничений создает объект модели, например, применительно к транспортной задаче.

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

Пример исходных данных для моделирования




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

  1. Модель закрытой транспортной задачи минимизации расходов на закупку товаров
    #!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy
from cvxopt.modeling import variable, op
def count(mass1, mass2, mass3, mass4,mass5,mass6,z):         
         x_non_negative = (x >= 0) #общее условие для всех х      
         problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, x_non_negative])
         problem.solve(solver='glpk')  
         problem.status
         print("Минимальная стоимость закупки -",problem.objective.value()[0])
         print("Матрица закупок:")
         for i in [1,4,7]:
                  print("|",x.value[i-1],"|", x.value[i],"|", x.value[i+1],"|")
x = variable(9, 'x')
z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* 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)#условия для столбца
count (mass1, mass2, mass3, mass4, mass5,mass6,z)

    Решение:

    Минимальная стоимость закупки — 215.0
    Матрица закупок:

    | 0.0 | 45.0 | 0.0 |
    | 0.0 | 0.0 | 30.0 |
    | 20.0 | 0.0 | 0.0 |

  2. Вносим небольшие изменения в предыдущую программу – добавляем переменную mass7 = (x[1] == 30).

    Торговые ограничения для второго поставщика в 30 условных единиц
    #!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy
from cvxopt.modeling import variable, op
def count(mass1, mass2, mass3, mass4,mass5,mass6,mass7,z):         
         x_non_negative = (x >= 0)       
         problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6 ,mass7,x_non_negative])
         problem.solve(solver='glpk')  
         problem.status
         print("Минимальная стоимость закупки -",problem.objective.value()[0])
         print("Матрица закупок:")
         for i in [1,4,7]:
                  print("|",x.value[i-1],"|", x.value[i],"|", x.value[i+1],"|")
x = variable(9, 'x')
z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* 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)
count(mass1, mass2, mass3, mass4,mass5,mass6,mass7,z)


    Решение:

    Минимальная стоимость закупки — 245.0
    Матрица закупок:

    | 0.0 | 30.0 | 0.0 |
    | 0.0 | 0.0 | 30.0 |
    | 20.0 | 15.0 | 0.0 |

  3. Ограничение по пропускной способности таможни на общий товарооборот в 80 условных единиц
    Для этого в программе п.1 заменим строку:
    mass5 = (x[1] +x[4] + x[7] == 45)
    на
    mass5 = (x[1] +x[4] + x[7] == 30)

    #!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy
from cvxopt.modeling import variable, op
def count(mass1, mass2, mass3, mass4,mass5,mass6,z):         
         x_non_negative = (x >= 0)    
         problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, x_non_negative])
         problem.solve(solver='glpk')  
         problem.status
         print("Минимальная стоимость закупки -",problem.objective.value()[0])
         print("Матрица закупок:")
         for i in [1,4,7]:
                  print("|",x.value[i-1],"|", x.value[i],"|", x.value[i+1],"|")
x = variable(9, 'x')
z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* 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)
count(mass1, mass2, mass3, mass4,mass5,mass6,z)

    Решение:

    Минимальная стоимость закупки — 170.0
    Матрица закупок:

    | 0.0 | 30.0 | 0.0 |
    | 0.0 | 0.0 | 30.0 |
    | 20.0 | 0.0 | 0.0 |

  4. Ограничения на поставку товара у второго поставщика
    Для этого в программе п.1 заменим строку:

    mass2 = (x[3] + x[4] +x[5] <= 40)
    на
    mass2 = (x[3] + x[4] +x[5] == 40)

    #!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy
from cvxopt.modeling import variable, op
def count(mass1, mass2, mass3, mass4,mass5,mass6,z):         
         x_non_negative = (x >= 0)    
         problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, x_non_negative])
         problem.solve(solver='glpk')  
         problem.status
         print("Минимальная стоимость закупки -",problem.objective.value()[0])
         print("Матрица закупок:")
         for i in [1,4,7]:
                  print("|",x.value[i-1],"|", x.value[i],"|", x.value[i+1],"|")
x = variable(9, 'x')
z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* 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)
count(mass1, mass2, mass3, mass4,mass5,mass6,z)


    Решение:

    Минимальная стоимость закупки — 245.0
    Матрица закупок:

    | 0.0 | 45.0 | 0.0 |
    | 10.0 | 0.0 | 30.0 |
    | 10.0 | 0.0 | 0.0 |

  5. Паритеты на поставки второго и третьего поставщиков
    Для этого в программе п.1 заменим строки:
    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)

    #!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy
from cvxopt.modeling import variable, op
def count(mass1, mass2, mass3, mass4,mass5,mass6,z):         
         x_non_negative = (x >= 0)    
         problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, x_non_negative])
         problem.solve(solver='glpk')  
         problem.status
         print("Минимальная стоимость закупки -",problem.objective.value()[0])
         print("Матрица закупок:")
         for i in [1,4,7]:
                  print("|",x.value[i-1],"|", x.value[i],"|", x.value[i+1],"|")
x = variable(9, 'x')
z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* 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)
count(mass1, mass2, mass3, mass4,mass5,mass6,z)


    Решение:

    Минимальная стоимость закупки — 235.0
    Матрица закупок:

    | 0.0 | 35.0 | 0.0 |
    | 0.0 | 0.0 | 30.0 |
    | 20.0 | 10.0 | 0.0 |


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

Анализ интерфейса решателя Excel Solver при решении данной закрытой транспортной задачи.



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

Анализ интерфейса решателя Minimize Mathcad при решении данной закрытой транспортной задачи.



Для работы функции Minimize необходимо устанавливать условия x>=0 для каждой переменной отдельно и вручную вычислять затраты по полученным значениям –x. В решателе CVXOPT для указанных действий предусмотрены следующие функции:

x_non_negative = (x >= 0)
problem. objective.value () [0]

Вывод


На простом примере приведено решение закрытой транспортной задачи с ограничениями средствами решателя CVXOPT среды моделирования Python.

Ссылки


  1. А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. — Минск: Высшая школа, 1978. — С. 110.
  2. CVXOPT Modeling.