ЛР-01: Комплектование медицинских наборов поддержки

Worked example: military 03

Это полностью разобранный example. Его задача — показать образец оформления, логики решения и интерпретации результата.

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

Нужно выбрать объёмы двух типов медицинских наборов при ограничении по медикаментам и упаковке.

Обозначим:

• \(x_1\) — количество наборов первой помощи;

• \(x_2\) — количество наборов расширенной поддержки.

Целевая функция:

\[ \max z = 11x_1 + 7x_2 \]

Ограничения:

\[ 2x_1 + 1x_2 \le 22 \]

\[ 1x_1 + 3x_2 \le 24 \]

\[ x_1 \ge 0, \quad x_2 \ge 0 \]

import itertools
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.optimize import linprog


def feasible_vertices(A: np.ndarray, b: np.ndarray) -> np.ndarray:
    """Находит кандидатов в вершины допустимой области для задачи с двумя переменными.

    Args:
        A: Матрица ограничений размера `(m, 2)`.
        b: Вектор правых частей.

    Returns:
        np.ndarray: Массив допустимых вершин без повторов.
    """
    candidates = [np.array([0.0, 0.0])]

    for row, rhs in zip(A, b):
        if row[0] > 0:
            candidates.append(np.array([rhs / row[0], 0.0]))
        if row[1] > 0:
            candidates.append(np.array([0.0, rhs / row[1]]))

    for i, j in itertools.combinations(range(len(A)), 2):
        matrix = np.vstack([A[i], A[j]])
        if abs(np.linalg.det(matrix)) > 1e-9:
            point = np.linalg.solve(matrix, np.array([b[i], b[j]], dtype=float))
            candidates.append(point)

    feasible = []
    for point in candidates:
        if np.all(point >= -1e-9) and np.all(A @ point <= b + 1e-9):
            feasible.append(np.maximum(point, 0.0))

    unique = []
    for point in feasible:
        if not any(np.allclose(point, saved, atol=1e-9) for saved in unique):
            unique.append(point)
    return np.array(unique, dtype=float)


A = np.array([[2, 1], [1, 3]], dtype=float)
b = np.array([22, 24], dtype=float)
objective = np.array([11, 7], dtype=float)

vertices = feasible_vertices(A, b)
values = vertices @ objective
vertices_df = pd.DataFrame(vertices, columns=['x1', 'x2'])
vertices_df['z'] = values
display(vertices_df.round(4))

	x1	x2	z
0	0.0	0.0	0.0
1	11.0	0.0	121.0
2	0.0	8.0	56.0
3	8.4	5.2	128.8

# Строим ту же задачу геометрически, чтобы увидеть допустимую область глазами.
x = np.linspace(0, max(22, 24) + 2, 400)
line_1 = (22 - 2 * x) / 1
line_2 = (24 - 1 * x) / 3

best_idx = int(np.argmax(values))
best_point = vertices[best_idx]
best_value = values[best_idx]

fig, ax = plt.subplots(figsize=(8, 6))
ax.plot(x, line_1, label=r'$2x_1 + 1x_2 = 22$', linewidth=2)
ax.plot(x, line_2, label=r'$1x_1 + 3x_2 = 24$', linewidth=2)
ax.fill(vertices[:, 0], vertices[:, 1], alpha=0.25, color='#74c476', label='Допустимая область')
ax.scatter(vertices[:, 0], vertices[:, 1], color='black')
ax.scatter(best_point[0], best_point[1], color='crimson', s=90, label='Оптимум')

for vx, vy in vertices:
    ax.annotate(f'({vx:.2f}, {vy:.2f})', (vx, vy), textcoords='offset points', xytext=(6, 6))

ax.set_xlim(left=0)
ax.set_ylim(bottom=0)
ax.set_xlabel('$x_1$')
ax.set_ylabel('$x_2$')
ax.set_title('Комплектование медицинских наборов поддержки')
ax.grid(alpha=0.3)
ax.legend()
plt.show()

print('Лучшая вершина по геометрическому анализу:', best_point)
print('Значение z в ней:', best_value)

Лучшая вершина по геометрическому анализу: [8.4 5.2]
Значение z в ней: 128.8

# Теперь подтверждаем ответ через linprog.
c = -objective
result = linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], method='highs')

print('success =', result.success)
print('message =', result.message)
print('x* =', result.x)
print('z_max =', -result.fun)

assert result.success
assert np.allclose(result.x, best_point)
assert np.isclose(-result.fun, best_value)

success = True
message = Optimization terminated successfully. (HiGHS Status 7: Optimal)
x* = [8.4 5.2]
z_max = 128.79999999999998

2. Как интерпретировать результат

• найденная вершина даёт лучший допустимый план;

• ни один другой допустимый угол не даёт большее значение цели;

• проверка через linprog совпала с геометрическим анализом.

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

1. Какие ограничения оказались определяющими для оптимума.

2. Почему решение лежит именно в вершине допустимой области.

3. Какой практический смысл имеют значения \(x_1^*\) и \(x_2^*\).