ЛР-02: Маршрутизация медико-эвакуационного снабжения

Worked example: military 03

Это полностью разобранный example. Он показывает образец постановки, решения и интерпретации транспортной модели.

1. Постановка кейса

Открытая задача с фиктивным поставщиком, который покрывает дефицит снабжения.

Запасы

Поставщик	Объём
Склад A	18
Склад B	24
Склад C	20

Спрос

Потребитель	Объём
Пункт 1	14
Пункт 2	18
Пункт 3	16
Пункт 4	22

Матрица затрат

Откуда / Куда	Пункт 1	Пункт 2	Пункт 3	Пункт 4
Склад A	6	5	8	10
Склад B	5	4	6	7
Склад C	7	6	5	6

import numpy as np
import pandas as pd
from scipy.optimize import linprog

def balance_transport_problem(supplies, demands, costs, supplier_names, consumer_names):
    supplies = supplies.astype(float).copy()
    demands = demands.astype(float).copy()
    costs = costs.astype(float).copy()
    supplier_names = list(supplier_names)
    consumer_names = list(consumer_names)

    diff = supplies.sum() - demands.sum()
    if diff > 0:
        demands = np.append(demands, diff)
        consumer_names.append('Фиктивный потребитель')
        costs = np.column_stack([costs, np.zeros(len(supplies))])
    elif diff < 0:
        supplies = np.append(supplies, -diff)
        supplier_names.append('Фиктивный поставщик')
        costs = np.vstack([costs, np.zeros(len(demands))])

    return supplies, demands, costs, supplier_names, consumer_names

def solve_transport_problem(supplies, demands, costs):
    m, n = costs.shape
    c = costs.flatten()

    A_eq = []
    b_eq = []

    for i in range(m):
        row = np.zeros(m * n)
        row[i * n:(i + 1) * n] = 1
        A_eq.append(row)
        b_eq.append(supplies[i])

    for j in range(n):
        row = np.zeros(m * n)
        row[j::n] = 1
        A_eq.append(row)
        b_eq.append(demands[j])

    result = linprog(
        c,
        A_eq=np.array(A_eq),
        b_eq=np.array(b_eq),
        bounds=[(0, None)] * (m * n),
        method='highs',
    )
    if not result.success:
        raise RuntimeError(result.message)
    return result, result.x.reshape(m, n)

supplier_names = ['Склад A', 'Склад B', 'Склад C']
consumer_names = ['Пункт 1', 'Пункт 2', 'Пункт 3', 'Пункт 4']
supplies = np.array([18, 24, 20], dtype=float)
demands = np.array([14, 18, 16, 22], dtype=float)
costs = np.array([[6, 5, 8, 10], [5, 4, 6, 7], [7, 6, 5, 6]], dtype=float)

balanced_supplies, balanced_demands, balanced_costs, supplier_names, consumer_names = balance_transport_problem(
    supplies, demands, costs, supplier_names, consumer_names
)

result, plan = solve_transport_problem(balanced_supplies, balanced_demands, balanced_costs)

plan_df = pd.DataFrame(plan, index=supplier_names, columns=consumer_names)
cost_df = pd.DataFrame(balanced_costs, index=supplier_names, columns=consumer_names)

print('Оптимальная стоимость:', round(result.fun, 2))
print()
print('План перевозок:')
display(plan_df)
print('Матрица затрат:')
display(cost_df)

Оптимальная стоимость: 334.0

План перевозок:

	Пункт 1	Пункт 2	Пункт 3	Пункт 4
Склад A	0.0	18.0	0.0	0.0
Склад B	14.0	-0.0	0.0	10.0
Склад C	0.0	0.0	16.0	4.0
Фиктивный поставщик	0.0	0.0	0.0	8.0

Матрица затрат:

	Пункт 1	Пункт 2	Пункт 3	Пункт 4
Склад A	6.0	5.0	8.0	10.0
Склад B	5.0	4.0	6.0	7.0
Склад C	7.0	6.0	5.0	6.0
Фиктивный поставщик	0.0	0.0	0.0	0.0

used_routes = []
for supplier in plan_df.index:
    for consumer in plan_df.columns:
        value = float(plan_df.loc[supplier, consumer])
        if value > 1e-9:
            used_routes.append({
                'маршрут': f'{supplier} -> {consumer}',
                'объём': round(value, 2),
                'тариф': float(cost_df.loc[supplier, consumer]),
                'затраты': round(value * float(cost_df.loc[supplier, consumer]), 2),
            })

used_routes_df = pd.DataFrame(used_routes)
print('Использованные маршруты:')
display(used_routes_df)
print('Проверка баланса по поставщикам:')
display(pd.DataFrame({'план': plan_df.sum(axis=1), 'запас': balanced_supplies}, index=plan_df.index))
print('Проверка баланса по потребителям:')
display(pd.DataFrame({'план': plan_df.sum(axis=0), 'спрос': balanced_demands}, index=plan_df.columns))

Использованные маршруты:

	маршрут	объём	тариф	затраты
0	Склад A -> Пункт 2	18.0	5.0	90.0
1	Склад B -> Пункт 1	14.0	5.0	70.0
2	Склад B -> Пункт 4	10.0	7.0	70.0
3	Склад C -> Пункт 3	16.0	5.0	80.0
4	Склад C -> Пункт 4	4.0	6.0	24.0
5	Фиктивный поставщик -> Пункт 4	8.0	0.0	0.0

Проверка баланса по поставщикам:

	план	запас
Склад A	18.0	18.0
Склад B	24.0	24.0
Склад C	20.0	20.0
Фиктивный поставщик	8.0	8.0

Проверка баланса по потребителям:

	план	спрос
Пункт 1	14.0	14.0
Пункт 2	18.0	18.0
Пункт 3	16.0	16.0
Пункт 4	22.0	22.0

2. Что важно проговорить в выводе

• фиктивный поставщик позволяет честно показать неудовлетворённый спрос;

• в интерпретации нужно отдельно описать объём, ушедший в дефицитный источник;

• если реальных запасов не хватает, часть спроса закрывается только фиктивной строкой.

Для отчёта обычно достаточно перечислить ненулевые маршруты, пояснить роль фиктивного узла, если он появился, и отдельно указать итоговую стоимость перевозок.