Транспортная задача и метод ветвей и границ

Мне нужно решить транспортную задачу с этими ограничениями (A — строка «Предложение», B — столбец «Спрос», матрица содержит цены на транспортировку):

А\Б 6 15 7 8 8 17 10 8 5 9 16 8 4 3 4 11 12 10 5 10 29 7 6 9 9 2 4 1 3

Я нашел решение и код работает корректно, потому что задачу я решил и ответы те же. В скобках указан объем для перевозки. Например, в элементе (1, 2) нам нужно перевезти 10 тонн по цене 8 долларов США за тонну = всего 80 долларов США.

А\Б 6 15 7 8 8 17 10 (10)\8 (7)\5 9 16 8 (3)\4 (5)\3 4 11 12 10 (3)\5 10 29 7 (7)\6 9 9 2 4 (8)\1 (1)\3

Однако в моей задаче есть ограничение. Для перевозки мне нужен 6-тонный грузовик. Например, в найденном решении в элементе (1, 2) мне нужно доставить 10 тонн по цене 8 долларов за тонну. Всего это означает 80 долларов, но с учетом моего ограничения это означает, что мне нужно забронировать 2 грузовика и заплатить 120 долларов.

Итак, принимая во внимание это ограничение и используя метод ветвей и границ, мне нужно найти оптимальное решение. Как мне это сделать?

import gurobipy as gp
from gurobipy import GRB

# Define data
supply = [17, 8, 10, 9]  # Supply nodes
demand = [6, 15, 7, 8, 8]  # Demand nodes
cost = [
    [10, 8, 5, 9, 16],
    [4, 3, 4, 11, 12],
    [5, 10, 29, 7, 6],
    [9, 2, 4, 1, 3]
]  # Cost of transportation from supply i to demand j

m = gp.Model()

# Define decision variables
flow = m.addVars(len(supply), len(demand), lb=0, vtype=GRB.INTEGER, name = "flow")

# Define supply constraints
for i in range(len(supply)):
    m.addConstr(gp.quicksum(flow[i, j] for j in range(len(demand))) <= supply[i], name=f"supply_{i}")

# Define demand constraints
for j in range(len(demand)):
    m.addConstr(gp.quicksum(flow[i, j] for i in range(len(supply))) >= demand[j], name=f"demand_{j}")

# Define objective function
m.setObjective(gp.quicksum(flow[i, j] * cost[i][j] for i in range(len(supply)) for j in range(len(demand))), sense=GRB.MINIMIZE)

# Solve model
m.optimize()

# Print results
if m.status == GRB.OPTIMAL:
    print(f"Optimal solution found with objective value {m.objVal:.2f}")
    for i in range(len(supply)):
        for j in range(len(demand)):
            if flow[i, j].x > 0:
                print(f"Flow from supply node {i+1} to demand node {j+1}: {flow[i, j].x:.0f}")
else:
    print("No solution found or problem is infeasible.")

"в квадрате 1\2 я должен поставить 10 тонн по цене 8$ за тонну" - это вообще не понятно из предоставленных вами данных. Существует один узел с поставкой 10 тонн, но ни один из узлов спроса не требует затрат в 8 долларов для этого узла, и не факт, что поставка пойдет на два узла спроса. Пожалуйста, уточните, что на самом деле означают ваши данные.

Grismar 08.04.2024 03:37

@Reinderien Я обновил свою таблицу. Да, мне приходится платить за вместимость грузовика, а в моей задаче грузовик может перевозить 6 тонн.

Pavel Jefimovich 08.04.2024 10:28

@Grismar Я обновил таблицу и надеюсь, что она станет более понятной.

Pavel Jefimovich 08.04.2024 10:30

Пожалуйста, отредактируйте, чтобы уточнить использование грузовиков. Приписан ли каждый грузовик к одной паре точек предложения/точки спроса?

Cary Swoveland 09.04.2024 08:47

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

Pavel Jefimovich 09.04.2024 10:33
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
5
112
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

Кроме того, меньше беспокойтесь о конкретном алгоритме ветвей и границ; просто выберите категорию решателя (MILP) и позвольте ему сделать свою работу.

import pandas as pd
import pulp

truck_capacity = 6
suppliers = pd.RangeIndex(name='supplier', stop=4)
consumers = pd.RangeIndex(name='consumer', stop=5)

supply = pd.Series(
    name='supply', index=suppliers, data=(17, 8, 10, 9),
)
demand = pd.Series(
    name='demand', index=consumers, data=(6, 15, 7, 8, 8),
)
price_per_tonne = pd.DataFrame(
    index=suppliers, columns=consumers,
    data=(
        (10,  8,  5,  9, 16),
        ( 4,  3,  4, 11, 12),
        ( 5, 10, 29,  7,  6),
        ( 9,  2,  4,  1,  3),
    ),
).stack()
price_per_tonne.name = 'price'

flow = pd.DataFrame(
    index=suppliers, columns=consumers,
    data=pulp.LpVariable.matrix(
        name='flow_s%d_c%d', cat=pulp.LpContinuous, lowBound=0,
        indices=(suppliers, consumers),
    ),
).stack()
flow.name = 'flow'

trucks = pd.DataFrame(
    index=suppliers, columns=consumers,
    data=pulp.LpVariable.matrix(
        name='trucks_s%d_c%d', cat=pulp.LpInteger, lowBound=0,
        indices=(suppliers, consumers),
    )
).stack()
trucks.name = 'trucks'

price = truck_capacity * pulp.lpDot(price_per_tonne, trucks)
prob = pulp.LpProblem(name='transportation', sense=pulp.LpMinimize)
prob.setObjective(price)

# The flow must not exceed the supply
for supplier, group in flow.groupby('supplier'):
    prob.addConstraint(
        name=f'flow_supply_s{supplier}',
        constraint=pulp.lpSum(group) <= supply[supplier],
    )

# The flow must exactly meet the demand
for consumer, group in flow.groupby('consumer'):
    prob.addConstraint(
        name=f'flow_demand_c{consumer}',
        constraint=pulp.lpSum(group) == demand[consumer],
    )

# The capacity must be able to carry the flow
for (supplier, consumer), truck_flow in flow.items():
    prob.addConstraint(
        name=f'capacity_s{supplier}_c{consumer}',
        constraint=truck_flow <= trucks[(supplier, consumer)] * truck_capacity
    )

print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal

print('Flow:')
flow = flow.apply(pulp.value).unstack(level='consumer')
print(flow)
print()

print('Trucks:')
trucks = trucks.apply(pulp.value).unstack(level='consumer')
print(trucks)
print()
transportation:
MINIMIZE
60*trucks_s0_c0 + 48*trucks_s0_c1 + 30*trucks_s0_c2 + 54*trucks_s0_c3 + 96*trucks_s0_c4 + 24*trucks_s1_c0 + 18*trucks_s1_c1 + 24*trucks_s1_c2 + 66*trucks_s1_c3 + 72*trucks_s1_c4 + 30*trucks_s2_c0 + 60*trucks_s2_c1 + 174*trucks_s2_c2 + 42*trucks_s2_c3 + 36*trucks_s2_c4 + 54*trucks_s3_c0 + 12*trucks_s3_c1 + 24*trucks_s3_c2 + 6*trucks_s3_c3 + 18*trucks_s3_c4 + 0
SUBJECT TO
flow_supply_s0: flow_s0_c0 + flow_s0_c1 + flow_s0_c2 + flow_s0_c3 + flow_s0_c4
 <= 17
...
flow_demand_c0: flow_s0_c0 + flow_s1_c0 + flow_s2_c0 + flow_s3_c0 = 6
...
capacity_s0_c0: flow_s0_c0 - 6 trucks_s0_c0 <= 0
...
Result - Optimal solution found

Objective value:                276.00000000
Enumerated nodes:               0
Total iterations:               33
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.01

Flow:
consumer    0    1    2    3    4
supplier                         
0         0.0  6.0  5.0  6.0  0.0
1         0.0  6.0  2.0  0.0  0.0
2         6.0  0.0  0.0  0.0  4.0
3         0.0  3.0  0.0  2.0  4.0

Trucks:
consumer    0    1    2    3    4
supplier                         
0         0.0  1.0  1.0  1.0  0.0
1         0.0  1.0  1.0  0.0  0.0
2         1.0  0.0  0.0  0.0  1.0
3         0.0  1.0  0.0  1.0  1.0

Огромное спасибо за помощь) Большое спасибо)

Pavel Jefimovich 09.04.2024 13:12

Другие вопросы по теме

Логика, которую нужно реализовать, чтобы получить максимальное количество очков
Что происходит с потерянной частью односвязного списка, когда я добавляю цикл в середине?
Эффективный способ найти сумму наибольших элементов x в подмассиве
Инициализируйте двумерный массив значениями, указанными в таблице ниже
Как я могу придумать алгоритм для разделения ряда чисел в заданном соотношении, чтобы округленные разделения складывались в исходное число?
Рекурсивное построение древовидной структуры данных из массива строк, сохраняющих порядок приоритета
Алгоритм разделения целого числа на группы определенных меньших целых чисел
Изменение масштаба массива в JavaScript или Python до определенного максимального значения и целевой суммы
Реализация визуализации дерева жизни в JavaFX с определением клады и иерархии
JS Структура/алгоритм данных для случайного выбора из набора с уменьшением вероятности

Похожие вопросы

Использование переменной из __init__.py в основном не работает
Django/Celery: Как задача может постоянно что-то делать? Можно ли установить бесконечный цикл для задачи?
Автономный Telegram-бот, который ежедневно отправляет сообщение группе
Найти среднее значение группы значений индекса в фрейме данных pandas на основе близости к другим значениям
Как мне заставить этот шаблон звезды работать только с одним циклом for в Python?
Использование счетчика циклов основной программы внутри модуля в качестве переменной
Python gspread – цикл по строкам – обновить ячейку суммой или разницей двух других ячеек в той же строке
Есть ли способ преобразовать QtCore.Qt.Key в строку
Как Alexa и другие голосовые помощники поддерживают систему плагинов, созданную с использованием нескольких разных языков программирования?
Проблема с установкой pip (FileNotFoundError: [Errno 2] Нет такого файла или каталога: 'requirements.txt')