Транспортная задача программа python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Problem from Operations Research

JKearnsl/transport_task

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Транспортная задача с GUI

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

Алгоритм проводит балансировку (если необходимо), а также проверяет и устраняет вырожденность.

Приложение написано на Python3.11 . Необходимо установить следующие библиотеки:

Для запуска приложения необходимо выполнить команду python3 main.pyw в корневой директории проекта. Не забудьте добавить в PYTHONPATH путь к директории с Вашим проектом, например: export PYTHONPATH=»/home/jkearnsl/Рабочий стол/project1″ .

About

Problem from Operations Research

Источник

H Решение транспортной задачи с использованием библиотеки CVXOPT 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])

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

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

#!/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]  

#!/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]  

#!/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]  

#!/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]  

#!/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]