ЛР-02: Школьные автобусные запчасти

Содержание

ЛР-02: Школьные автобусные запчасти#

Worked example: civil 03#

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

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

Открытая транспортная задача с избыточным запасом и фиктивным потребителем.

Запасы#

Поставщик	Объём
Склад A	28
Склад B	32
Склад C	25

Спрос#

Потребитель	Объём
Автопарк 1	18
Автопарк 2	22
Автопарк 3	20
Автопарк 4	15

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

Откуда / Куда	Автопарк 1	Автопарк 2	Автопарк 3	Автопарк 4
Склад A	4	5	7	8
Склад B	6	4	5	7
Склад C	7	6	4	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([28, 32, 25], dtype=float)
demands = np.array([18, 22, 20, 15], dtype=float)
costs = np.array([[4, 5, 7, 8], [6, 4, 5, 7], [7, 6, 4, 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)

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

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

	Автопарк 1	Автопарк 2	Автопарк 3	Автопарк 4	Фиктивный потребитель
Склад A	18.0	0.0	0.0	0.0	10.0
Склад B	0.0	22.0	10.0	0.0	-0.0
Склад C	0.0	0.0	10.0	15.0	0.0

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

	Автопарк 1	Автопарк 2	Автопарк 3	Автопарк 4
Склад A	4.0	5.0	7.0	8.0
Склад B	6.0	4.0	5.0	7.0
Склад C	7.0	6.0	4.0	6.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	18.0	4.0	72.0
1	Склад A -> Фиктивный потребитель	10.0	0.0	0.0
2	Склад B -> Автопарк 2	22.0	4.0	88.0
3	Склад B -> Автопарк 3	10.0	5.0	50.0
4	Склад C -> Автопарк 3	10.0	4.0	40.0
5	Склад C -> Автопарк 4	15.0	6.0	90.0

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

	план	запас
Склад A	28.0	28.0
Склад B	32.0	32.0
Склад C	25.0	25.0

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

	план	спрос
Автопарк 1	18.0	18.0
Автопарк 2	22.0	22.0
Автопарк 3	20.0	20.0
Автопарк 4	15.0	15.0
Фиктивный потребитель	10.0	10.0

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

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

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