ЛР-02: Лекарства в больницы

Worked example: civil 01

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

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

Базовый гражданский пример на закрытой транспортной задаче.

Запасы

Поставщик	Объём
Склад A	35
Склад B	50
Склад C	40

Спрос

Потребитель	Объём
Больница 1	20
Больница 2	30
Больница 3	25
Больница 4	50

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

Откуда / Куда	Больница 1	Больница 2	Больница 3	Больница 4
Склад A	4	6	8	13
Склад B	5	4	7	9
Склад C	6	3	4	7

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([35, 50, 40], dtype=float)
demands = np.array([20, 30, 25, 50], dtype=float)
costs = np.array([[4, 6, 8, 13], [5, 4, 7, 9], [6, 3, 4, 7]], 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)

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

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

	Больница 1	Больница 2	Больница 3	Больница 4
Склад A	20.0	15.0	0.0	0.0
Склад B	0.0	15.0	0.0	35.0
Склад C	0.0	0.0	25.0	15.0

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

	Больница 1	Больница 2	Больница 3	Больница 4
Склад A	4.0	6.0	8.0	13.0
Склад B	5.0	4.0	7.0	9.0
Склад C	6.0	3.0	4.0	7.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 -> Больница 1	20.0	4.0	80.0
1	Склад A -> Больница 2	15.0	6.0	90.0
2	Склад B -> Больница 2	15.0	4.0	60.0
3	Склад B -> Больница 4	35.0	9.0	315.0
4	Склад C -> Больница 3	25.0	4.0	100.0
5	Склад C -> Больница 4	15.0	7.0	105.0

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

	план	запас
Склад A	35.0	35.0
Склад B	50.0	50.0
Склад C	40.0	40.0

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

	план	спрос
Больница 1	20.0	20.0
Больница 2	30.0	30.0
Больница 3	25.0	25.0
Больница 4	50.0	50.0

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

• после решения полезно отдельно сверить суммы по строкам и столбцам;

• нужно посмотреть, есть ли дорогие маршруты, которые solver избегает;

• вывод должен объяснять не только стоимость, но и структуру плана.

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