ЛР-02: Учебные материалы и оборудование

Worked example: civil 02

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

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

Здесь один маршрут сделан аварийно дорогим, чтобы увидеть реакцию оптимального плана.

Запасы

Поставщик	Объём
Центр A	25
Центр B	45
Центр C	35

Спрос

Потребитель	Объём
Колледж 1	15
Колледж 2	30
Колледж 3	25
Колледж 4	35

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

Откуда / Куда	Колледж 1	Колледж 2	Колледж 3	Колледж 4
Центр A	4	8	50	9
Центр B	6	5	7	8
Центр C	7	4	6	5

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

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

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

	Колледж 1	Колледж 2	Колледж 3	Колледж 4
Центр A	15.0	10.0	0.0	-0.0
Центр B	0.0	20.0	25.0	0.0
Центр C	0.0	0.0	0.0	35.0

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

	Колледж 1	Колледж 2	Колледж 3	Колледж 4
Центр A	4.0	8.0	50.0	9.0
Центр B	6.0	5.0	7.0	8.0
Центр C	7.0	4.0	6.0	5.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	15.0	4.0	60.0
1	Центр A -> Колледж 2	10.0	8.0	80.0
2	Центр B -> Колледж 2	20.0	5.0	100.0
3	Центр B -> Колледж 3	25.0	7.0	175.0
4	Центр C -> Колледж 4	35.0	5.0	175.0

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

	план	запас
Центр A	25.0	25.0
Центр B	45.0	45.0
Центр C	35.0	35.0

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

	план	спрос
Колледж 1	15.0	15.0
Колледж 2	30.0	30.0
Колледж 3	25.0	25.0
Колледж 4	35.0	35.0

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

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

• важно интерпретировать, какой альтернативой этот маршрут был вытеснен;

• для отчёта удобно перечислить только ненулевые перевозки.

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