ЛР-01: Муниципальная пекарня

ЛР-01: Муниципальная пекарня#

Student notebook: civil 01#

Этот notebook предназначен для самостоятельного заполнения. Готовых численных ответов и выполненного решателя здесь нет.

1. Зачем нужен этот кейс#

Пекарня распределяет рабочее время и муку между двумя видами наборов: хлебными и булочными.

После этого notebook-а студент должен уметь:

  1. выделять переменные, целевую функцию и ограничения;

  2. находить вершины допустимой области вручную;

  3. переводить задачу max в формат linprog;

  4. проверять ответ через Python и объяснять его простыми словами.

2. Постановка задачи#

Обозначим:

  • \(x_1\) — количество хлебных наборов;

  • \(x_2\) — количество булочных наборов.

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

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

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

\[ 4x_1 + 2x_2 \le 40 \quad \text{(мука)} \]
\[ x_1 + 2x_2 \le 22 \quad \text{(печное время)} \]
\[ x_1 \ge 0, \quad x_2 \ge 0 \]

Числа из условия#

  • прибыль с одного хлебного набора: 7

  • прибыль с одного булочного набора: 5

  • мука: 4 и 2, лимит 40

  • печное время: 1 и 2, лимит 22

3. Задание 1. Геометрическое решение#

Выполните по шагам:

  1. Найдите по две опорные точки для каждой граничной прямой.

  2. Постройте допустимую область.

  3. Найдите все вершины допустимой области.

  4. Вычислите целевую функцию в каждой вершине.

  5. Сделайте вывод, какая вершина даёт оптимум.

# Сюда перенесите результаты ручного решения.
# Этот блок нужен как аккуратный черновик перед проверкой через Python.

vertices = None
objective_values = None
optimal_point = None
optimal_value = None

print('vertices =', vertices)
print('objective_values =', objective_values)
print('optimal_point =', optimal_point)
print('optimal_value =', optimal_value)

4. Задание 2. Проверка через linprog#

Здесь нужно вручную заполнить массивы для решателя.

Подсказка по порядку работы:

  1. Сначала перепишите коэффициенты в c, A_ub, b_ub.

  2. Затем проверьте, что вы правильно поменяли знак у целевой функции.

  3. Только после этого запускайте решатель.

import numpy as np
from scipy.optimize import linprog


def describe_result(result) -> None:
    """Печатает найденный план в удобном для отчёта виде.

    Args:
        result: Объект результата от `linprog`.
    """
    print('success =', result.success)
    print('message =', result.message)
    if result.success:
        print('x =', result.x)
        print('f_min =', result.fun)
        print('z_max =', -result.fun)


# TODO: перепишите коэффициенты целевой функции для ЗАДАЧИ МИНИМИЗАЦИИ.
c = np.array([np.nan, np.nan], dtype=float)

# TODO: заполните матрицу ограничений A_ub @ x <= b_ub.
A_ub = np.array([
    [np.nan, np.nan],
    [np.nan, np.nan],
], dtype=float)

# TODO: заполните правые части ограничений.
b_ub = np.array([np.nan, np.nan], dtype=float)

bounds = [(0, None), (0, None)]

if np.isnan(c).any() or np.isnan(A_ub).any() or np.isnan(b_ub).any():
    print('Сначала заполните c, A_ub и b_ub числами из постановки.')
else:
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
    describe_result(result)

5. Что должно быть в отчёте#

  1. Полная математическая постановка задачи.

  2. Геометрическое решение с рисунком допустимой области.

  3. Все вершины и значения целевой функции.

  4. Проверка через linprog.

  5. Пояснение, почему найденный план является оптимальным.

6. Контрольный чек-лист#

  • [ ] Я сам нашёл вершины допустимой области.

  • [ ] Я правильно выполнил переход max -> min.

  • [ ] Я осмысленно заполнил c, A_ub, b_ub, bounds.

  • [ ] Я не подставлял готовый ответ до собственной попытки решения.