H Решение транспортной задачи с использованием библиотеки CVXOPT Python в черновиках
Стандартная транспортная задача приведена в следующей таблице [1].
где — запасы на складах поставщиков, потребности потребителей и стоимости товара для каждого потребителя соответственно.
Для открытой задачи запасы поставщиков и потребности равны — Для закрытой задачи они разные —
Математическая модель открытой задачи состоит из целевой функции и балансовых уравнений.
Для закрытой задачи. В математической модели для закрытой задачи целевая функция та же что и в открытой, а условий два. Для условия — : — целые числа; (3)
Рассмотрим условия и ограничения к транспортной задаче, которые могут возникать в реальной практике.
Ограничения на грузоподъемность транспорта определяется следующим условием.
Такие модели не всегда имеют решение. Условием решаемости является наличие хотя бы одного допустимого решения.
Ограничение по задержке на таможне однородного груза объёмом 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])
Пример исходных данных для моделированияДля демонстрации метода напишем программы с приведенными выше условиями и ограничениями. Программы просто адаптировать на матрицы любого заданного размера, но эта задача уже за рамками данной статьи.
Минимальная стоимость закупки — 215.0 Матрица закупок:
| 0.0 | 45.0 | 0.0 | | 0.0 | 0.0 | 30.0 | | 20.0 | 0.0 | 0.0 |
Минимальная стоимость закупки — 245.0 Матрица закупок:
| 0.0 | 30.0 | 0.0 | | 0.0 | 0.0 | 30.0 | | 20.0 | 15.0 | 0.0 |
Для этого в программе п.1 заменим строку: mass5 = (x[1] +x[4] + x[7] == 45) на mass5 = (x[1] +x[4] + x[7] == 30)
Минимальная стоимость закупки — 170.0 Матрица закупок:
| 0.0 | 30.0 | 0.0 | | 0.0 | 0.0 | 30.0 | | 20.0 | 0.0 | 0.0 |
Для этого в программе п.1 заменим строку:
mass2 = (x[3] + x[4] +x[5] <= 40) на mass2 = (x[3] + x[4] +x[5] == 40)
Минимальная стоимость закупки — 245.0 Матрица закупок:
| 0.0 | 45.0 | 0.0 | | 10.0 | 0.0 | 30.0 | | 10.0 | 0.0 | 0.0 |
Для этого в программе п.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)
Минимальная стоимость закупки — 235.0 Матрица закупок:
| 0.0 | 35.0 | 0.0 | | 0.0 | 0.0 | 30.0 | | 20.0 | 10.0 | 0.0 |
Анализ интерфейса решателя Excel Solver при решении данной закрытой транспортной задачи.
Для расчёта минимальной стоимости транспортных затрат (матрица может быть заполнена и общими затратами включая транспортные), кроме ввода запасов, потребностей и матрицы цен, условий закупки необходимо устанавливать суммы по строкам и столбцам матрицы цен. В решателе CVXOPT этого делать не нужно.
Анализ интерфейса решателя Minimize Mathcad при решении данной закрытой транспортной задачи.
Для работы функции Minimize необходимо устанавливать условия x>=0 для каждой переменной отдельно и вручную вычислять затраты по полученным значениям –x. В решателе CVXOPT для указанных действий предусмотрены следующие функции:
x_non_negative = (x >= 0) problem. objective.value () [0]
Кроме этого реализация транспортной задачи на Python позволяет разделить исполнительную часть программа -решатель и исходные данные — матрицу и ограничения, разместив их в отдельном файле.При этом можно набрать библиотеку решений, снять ограничения с размера матрицы и проводить сравнительный анализ результатов.
ВыводБиблиотека CVXOPT Python позволяет эффективно решать транспортные задачи с условиями на приоритеты и паритеты поставок, создать базу решений чем расширить область их практического применения.