Лаб. работа “Линейное программирование”

Разработка и оптимизация интеллектуальных информационных систем
Практика
Автор

Бизюк Андрей

Дата публикации

9 апреля 2026 г.

Цель работы

Освоить методы решения задач линейного программирования:

  1. Графический метод — для задач с двумя переменными
  2. Симплекс-метод — аналитическое решение в канонической форме
  3. Транспортная задача — метод потенциалов

Общие указания

  • Каждое задание выполняется индивидуально (номер варианта совпадает с номером в журнале)
  • Для графического метода — построить ОДР, отметить вершины, показать линию уровня
  • Для симплекс-метода — привести полные симплекс-таблицы
  • Для транспортной задачи — построить начальный план, проверить оптимальность методом потенциалов
  • Результаты свести в отчёт (можно оформить в Markdown / Word / LaTeX)

Задание 1. Графический метод

Решить задачу линейного программирования графическим методом:

Найти максимум (или минимум) целевой функции при заданных ограничениях.

Порядок выполнения:

  1. Построить область допустимых решений (ОДР)
  2. Построить вектор-градиент \(\nabla Z = (c_1, c_2)\)
  3. Построить линию уровня \(Z = Z_0\) и перемещать её в направлении градиента (для \(\max\)) или против (для \(\min\))
  4. Найти оптимальную вершину ОДР
  5. Вычислить \(Z^*\) — оптимальное значение целевой функции

Задание 1. Варианты (нечётные)

Вариант \(Z\) Ограничения
1 \(2x_1 + 3x_2 \to \max\) \(x_1 + 2x_2 \leq 8,\; 3x_1 + x_2 \leq 9,\; x_1, x_2 \geq 0\)
3 \(x_1 + 4x_2 \to \max\) \(2x_1 + x_2 \leq 10,\; x_1 + 3x_2 \leq 12,\; x_1, x_2 \geq 0\)
5 \(3x_1 + 2x_2 \to \min\) \(x_1 + x_2 \geq 4,\; 2x_1 + x_2 \geq 5,\; x_1, x_2 \geq 0\)
7 \(5x_1 + 3x_2 \to \max\) \(x_1 + x_2 \leq 6,\; 2x_1 + 3x_2 \leq 14,\; x_1, x_2 \geq 0\)
9 \(x_1 + 2x_2 \to \max\) \(3x_1 + 2x_2 \leq 12,\; x_1 + 4x_2 \leq 16,\; x_1, x_2 \geq 0\)
11 \(4x_1 + x_2 \to \max\) \(x_1 + 2x_2 \leq 8,\; 3x_1 + x_2 \leq 9,\; x_1, x_2 \geq 0\)
13 \(2x_1 + 5x_2 \to \max\) \(x_1 + x_2 \leq 7,\; 2x_1 + 3x_2 \leq 18,\; x_1, x_2 \geq 0\)
15 \(3x_1 + x_2 \to \min\) \(x_1 + x_2 \geq 3,\; 2x_1 + x_2 \geq 4,\; x_1, x_2 \geq 0\)

Задание 1. Варианты (чётные)

Вариант \(Z\) Ограничения
2 \(3x_1 + 2x_2 \to \max\) \(x_1 + 3x_2 \leq 12,\; 2x_1 + x_2 \leq 8,\; x_1, x_2 \geq 0\)
4 \(x_1 + x_2 \to \max\) \(2x_1 + x_2 \leq 10,\; x_1 + 2x_2 \leq 8,\; x_1, x_2 \geq 0\)
6 \(2x_1 + x_2 \to \min\) \(x_1 + x_2 \geq 5,\; 3x_1 + 2x_2 \geq 12,\; x_1, x_2 \geq 0\)
8 \(x_1 + 3x_2 \to \max\) \(x_1 + x_2 \leq 6,\; x_1 + 2x_2 \leq 10,\; x_1, x_2 \geq 0\)
10 \(4x_1 + 2x_2 \to \max\) \(2x_1 + x_2 \leq 10,\; x_1 + 3x_2 \leq 12,\; x_1, x_2 \geq 0\)
12 \(2x_1 + 3x_2 \to \min\) \(x_1 + 2x_2 \geq 6,\; 3x_1 + x_2 \geq 9,\; x_1, x_2 \geq 0\)
14 \(x_1 + 5x_2 \to \max\) \(x_1 + x_2 \leq 8,\; 3x_1 + 2x_2 \leq 18,\; x_1, x_2 \geq 0\)
16 \(3x_1 + 4x_2 \to \max\) \(x_1 + 2x_2 \leq 10,\; 2x_1 + x_2 \leq 8,\; x_1, x_2 \geq 0\)

Задание 1. Пример решения (вариант 0)

\[Z = 3x_1 + 5x_2 \to \max, \quad \begin{cases} 2x_1 + x_2 \leq 100 \\ x_1 + 2x_2 \leq 80 \\ x_1, x_2 \geq 0 \end{cases}\]

Шаг 1. Строим ОДР — пересечение полуплоскостей.

Шаг 2. Градиент \(\nabla Z = (3, 5)\) — направление роста \(Z\).

Шаг 3. Находим вершины ОДР:

Вершина \(Z = 3x_1 + 5x_2\)
\((0, 0)\) \(0\)
\((50, 0)\) \(150\)
\((0, 40)\) \(200\)
\((40, 20)\) \(220\)

Ответ: \(Z^* = 220\) при \(x_1^* = 40\), \(x_2^* = 20\).

Задание 1. Пример: графическая иллюстрация

Графический метод

Графический метод

Задание 2. Симплекс-метод

Решить задачу линейного программирования симплекс-методом.

Порядок выполнения:

  1. Привести задачу к канонической форме (добавить балансовые переменные)
  2. Записать начальную симплекс-таблицу
  3. Определить разрешающий столбец (максимальный \(\Delta_j > 0\)) и разрешающую строку (минимальное \(\theta\))
  4. Выполнить итерацию (пересчёт таблицы методом Жордана-Гаусса)
  5. Повторять до выполнения признака оптимальности
  6. Записать ответ

Задание 2. Варианты (нечётные)

Вар. \(Z\) Ограничения
1 \(2x_1 + x_2 + x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 12,\; 2x_1 + x_2 \leq 8,\; x_2 + 2x_3 \leq 10,\; x_1, x_2, x_3 \geq 0\)
3 \(x_1 + 3x_2 + 2x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 15,\; x_1 + 2x_2 \leq 10,\; x_2 + x_3 \leq 8,\; x_1, x_2, x_3 \geq 0\)
5 \(3x_1 + 2x_2 + x_3 \to \max\) \(x_1 + x_2 + 2x_3 \leq 14,\; 2x_1 + x_2 \leq 10,\; x_2 + x_3 \leq 6,\; x_1, x_2, x_3 \geq 0\)
7 \(x_1 + 2x_2 + 3x_3 \to \max\) \(2x_1 + x_2 + x_3 \leq 12,\; x_1 + x_2 + 2x_3 \leq 15,\; x_1 + 2x_2 \leq 8,\; x_1, x_2, x_3 \geq 0\)
9 \(2x_1 + x_2 + 3x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 10,\; x_1 + 2x_2 \leq 8,\; x_2 + x_3 \leq 6,\; x_1, x_2, x_3 \geq 0\)
11 \(4x_1 + x_2 + 2x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 12,\; 2x_1 + x_2 \leq 8,\; x_2 + 2x_3 \leq 10,\; x_1, x_2, x_3 \geq 0\)
13 \(x_1 + 4x_2 + 2x_3 \to \max\) \(x_1 + x_2 + 2x_3 \leq 14,\; 2x_1 + x_2 \leq 10,\; x_2 + x_3 \leq 8,\; x_1, x_2, x_3 \geq 0\)
15 \(2x_1 + 3x_2 + x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 16,\; 2x_1 + x_2 \leq 12,\; x_2 + 2x_3 \leq 10,\; x_1, x_2, x_3 \geq 0\)

Задание 2. Варианты (чётные)

Вар. \(Z\) Ограничения
2 \(x_1 + 2x_2 + x_3 \to \max\) \(2x_1 + x_2 + x_3 \leq 10,\; x_1 + x_2 + 2x_3 \leq 12,\; x_1 + 2x_2 \leq 8,\; x_1, x_2, x_3 \geq 0\)
4 \(3x_1 + x_2 + 2x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 14,\; 2x_1 + x_2 \leq 8,\; x_2 + x_3 \leq 10,\; x_1, x_2, x_3 \geq 0\)
6 \(2x_1 + 2x_2 + x_3 \to \max\) \(x_1 + 2x_2 + x_3 \leq 12,\; 2x_1 + x_2 \leq 10,\; x_2 + 2x_3 \leq 8,\; x_1, x_2, x_3 \geq 0\)
8 \(x_1 + x_2 + 4x_3 \to \max\) \(x_1 + 2x_2 + x_3 \leq 10,\; x_1 + x_2 + x_3 \leq 8,\; 2x_2 + x_3 \leq 6,\; x_1, x_2, x_3 \geq 0\)
10 \(3x_1 + 2x_2 + x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 16,\; 2x_1 + x_2 \leq 12,\; x_2 + x_3 \leq 8,\; x_1, x_2, x_3 \geq 0\)
12 \(x_1 + 3x_2 + 2x_3 \to \max\) \(2x_1 + x_2 + x_3 \leq 14,\; x_1 + 2x_2 \leq 10,\; x_2 + 2x_3 \leq 12,\; x_1, x_2, x_3 \geq 0\)
14 \(2x_1 + x_2 + 3x_3 \to \max\) \(x_1 + x_2 + 2x_3 \leq 12,\; x_1 + 2x_2 \leq 8,\; 2x_2 + x_3 \leq 10,\; x_1, x_2, x_3 \geq 0\)
16 \(x_1 + 2x_2 + x_3 \to \max\) \(x_1 + x_2 + x_3 \leq 10,\; 2x_1 + x_2 \leq 6,\; x_2 + 2x_3 \leq 8,\; x_1, x_2, x_3 \geq 0\)

Задание 2. Пример решения

\[Z = 3x_1 + 5x_2 \to \max, \quad \begin{cases} 2x_1 + x_2 \leq 100 \\ x_1 + 2x_2 \leq 80 \\ x_1, x_2 \geq 0 \end{cases}\]

Каноническая форма:

\[Z = 3x_1 + 5x_2 \to \max, \quad \begin{cases} 2x_1 + x_2 + x_3 = 100 \\ x_1 + 2x_2 + x_4 = 80 \\ x_1, x_2, x_3, x_4 \geq 0 \end{cases}\]

Начальный базис: \(\{x_3, x_4\}\), начальный план: \(x_3 = 100\), \(x_4 = 80\), \(x_1 = x_2 = 0\), \(Z = 0\).

Пример: начальная симплекс-таблица

Базис \(x_1\) \(x_2\) \(x_3\) \(x_4\) \(b\) \(\theta\)
\(x_3\) 2 1 1 0 100 100
\(x_4\) 1 2 0 1 80 40
\(\Delta_j\) -3 -5 0 0 0

Разрешающий столбец — \(x_2\) (\(\Delta_2 = -5\) — наименьший). Разрешающая строка — \(x_4\) (\(\theta = 40\) — наименьшее). Разрешающий элемент — 2.

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

Базис \(x_1\) \(x_2\) \(x_3\) \(x_4\) \(b\) \(\theta\)
\(x_3\) 3/2 0 1 -1/2 60 40
\(x_2\) 1/2 1 0 1/2 40 80
\(\Delta_j\) -1/2 0 0 5/2 200

Разрешающий столбец — \(x_1\) (\(\Delta_1 = -1/2\)). Разрешающая строка — \(x_3\) (\(\theta = 40\)). Разрешающий элемент — 3/2.

Пример: оптимальная таблица

Базис \(x_1\) \(x_2\) \(x_3\) \(x_4\) \(b\)
\(x_1\) 1 0 2/3 -1/3 40
\(x_2\) 0 1 -1/3 2/3 20
\(\Delta_j\) 0 0 1/3 7/3 220

Все \(\Delta_j \geq 0\) — план оптимален.

Ответ: \(Z^* = 220\) при \(x_1^* = 40\), \(x_2^* = 20\).

Задание 3. Транспортная задача

Решить транспортную задачу методом потенциалов.

Порядок выполнения:

  1. Проверить задачу на сбалансированность (\(\sum a_i = \sum b_j\))
  2. Построить начальный опорный план (метод северо-западного угла или метод наименьшей стоимости)
  3. Вычислить потенциалы поставщиков (\(u_i\)) и потребителей (\(v_j\))
  4. Найти косвенные стоимости \(\Delta_{ij} = c_{ij} - u_i - v_j\) для свободных клеток
  5. Если все \(\Delta_{ij} \geq 0\) — план оптимален
  6. Если есть \(\Delta_{ij} < 0\) — построить цикл, найти \(\theta\), пересчитать план
  7. Повторять до оптимальности

Задание 3. Варианты (нечётные)

Вариант 1: \(m = 3\) поставщика, \(n = 4\) потребителя

\[c = \begin{pmatrix} 3 & 5 & 7 & 2 \\ 2 & 8 & 4 & 6 \\ 5 & 1 & 3 & 9 \end{pmatrix}, \quad a = (40, 60, 50), \quad b = (30, 45, 35, 40)\]

Вариант 3:

\[c = \begin{pmatrix} 2 & 4 & 6 & 3 \\ 5 & 3 & 2 & 7 \\ 1 & 8 & 5 & 4 \end{pmatrix}, \quad a = (50, 40, 60), \quad b = (35, 40, 30, 45)\]

Вариант 5:

\[c = \begin{pmatrix} 4 & 2 & 5 & 8 \\ 3 & 6 & 1 & 4 \\ 7 & 3 & 2 & 6 \end{pmatrix}, \quad a = (30, 50, 40), \quad b = (25, 35, 30, 30)\]

Вариант 7:

\[c = \begin{pmatrix} 1 & 6 & 3 & 5 \\ 4 & 2 & 7 & 3 \\ 5 & 4 & 1 & 8 \end{pmatrix}, \quad a = (45, 35, 55), \quad b = (30, 40, 25, 40)\]

Вариант 9:

\[c = \begin{pmatrix} 5 & 3 & 2 & 7 \\ 1 & 4 & 6 & 3 \\ 3 & 8 & 1 & 5 \end{pmatrix}, \quad a = (35, 55, 45), \quad b = (40, 30, 35, 30)\]

Вариант 11:

\[c = \begin{pmatrix} 2 & 7 & 4 & 1 \\ 6 & 3 & 5 & 8 \\ 4 & 1 & 8 & 3 \end{pmatrix}, \quad a = (50, 40, 50), \quad b = (35, 45, 25, 35)\]

Вариант 13:

\[c = \begin{pmatrix} 6 & 1 & 4 & 3 \\ 3 & 5 & 2 & 7 \\ 2 & 8 & 6 & 1 \end{pmatrix}, \quad a = (40, 50, 45), \quad b = (30, 35, 40, 30)\]

Вариант 15:

\[c = \begin{pmatrix} 3 & 4 & 1 & 6 \\ 5 & 2 & 7 & 3 \\ 1 & 6 & 3 & 8 \end{pmatrix}, \quad a = (45, 40, 50), \quad b = (35, 30, 35, 35)\]

Задание 3. Варианты (чётные)

Вариант 2:

\[c = \begin{pmatrix} 4 & 1 & 6 & 3 \\ 2 & 5 & 3 & 7 \\ 6 & 2 & 4 & 1 \end{pmatrix}, \quad a = (45, 55, 35), \quad b = (30, 40, 35, 30)\]

Вариант 4:

\[c = \begin{pmatrix} 1 & 5 & 3 & 8 \\ 4 & 2 & 6 & 3 \\ 7 & 3 & 1 & 5 \end{pmatrix}, \quad a = (40, 50, 40), \quad b = (35, 30, 40, 25)\]

Вариант 6:

\[c = \begin{pmatrix} 5 & 2 & 4 & 6 \\ 3 & 7 & 1 & 4 \\ 2 & 4 & 8 & 3 \end{pmatrix}, \quad a = (35, 45, 55), \quad b = (30, 35, 30, 40)\]

Вариант 8:

\[c = \begin{pmatrix} 2 & 6 & 5 & 1 \\ 7 & 3 & 4 & 8 \\ 4 & 1 & 7 & 3 \end{pmatrix}, \quad a = (50, 35, 50), \quad b = (25, 40, 35, 35)\]

Вариант 10:

\[c = \begin{pmatrix} 3 & 1 & 7 & 4 \\ 5 & 4 & 2 & 6 \\ 1 & 8 & 3 & 5 \end{pmatrix}, \quad a = (40, 45, 50), \quad b = (35, 25, 40, 35)\]

Вариант 12:

\[c = \begin{pmatrix} 6 & 3 & 1 & 5 \\ 2 & 7 & 4 & 3 \\ 4 & 1 & 8 & 2 \end{pmatrix}, \quad a = (35, 55, 40), \quad b = (30, 40, 25, 35)\]

Вариант 14:

\[c = \begin{pmatrix} 1 & 4 & 6 & 2 \\ 5 & 3 & 2 & 7 \\ 3 & 8 & 4 & 1 \end{pmatrix}, \quad a = (50, 40, 45), \quad b = (35, 30, 35, 35)\]

Вариант 16:

\[c = \begin{pmatrix} 4 & 6 & 2 & 5 \\ 1 & 3 & 7 & 4 \\ 6 & 2 & 3 & 8 \end{pmatrix}, \quad a = (45, 35, 55), \quad b = (30, 40, 30, 35)\]

Задание 3. Пример решения

\[c = \begin{pmatrix} 2 & 3 & 1 & 5 \\ 4 & 1 & 2 & 3 \\ 3 & 5 & 4 & 2 \end{pmatrix}, \quad a = (40, 35, 45), \quad b = (30, 25, 30, 35)\]

\(\sum a_i = 120 = \sum b_j\) — задача сбалансирована.

Начальный план (метод северо-западного угла):

\(B_1\) \(B_2\) \(B_3\) \(B_4\) \(a_i\)
\(A_1\) 30 10 40
\(A_2\) 15 20 35
\(A_3\) 10 35 45
\(b_j\) 30 25 30 35 120

\(Z_0 = 30 \cdot 2 + 10 \cdot 3 + 15 \cdot 1 + 20 \cdot 2 + 10 \cdot 4 + 35 \cdot 2 = 255\)

Пример: потенциалы и проверка

Потенциалы: \(u_1 = 0\) (фиксируем)

Из занятых клеток: \(v_1 = 2\), \(v_2 = 3\), \(v_3 = 4\), \(u_2 = -2\), \(u_3 = 0\)

Косвенные стоимости свободных клеток:

\(B_1\) \(B_2\) \(B_3\) \(B_4\)
\(A_1\) 0 0 \(\Delta_{13} = 1 - 0 - 4 = -3\) \(\Delta_{14} = 5 - 0 - 2 = 3\)
\(A_2\) \(\Delta_{21} = 4 - (-2) - 2 = 4\) 0 0 \(\Delta_{24} = 3 - (-2) - 2 = 3\)
\(A_3\) \(\Delta_{31} = 3 - 0 - 2 = 1\) \(\Delta_{32} = 5 - 0 - 3 = 2\) 0 0

\(\Delta_{13} = -3 < 0\) — план не оптимален. Строим цикл из клетки \((1, 3)\)…

Программная проверка

Для проверки результатов используйте Python:

from scipy.optimize import linprog

# Графический метод / Симплекс-метод
c = [-3, -5]  # минимум -Z = максимум Z
A_ub = [[2, 1], [1, 2]]
b_ub = [100, 80]
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=(0, None))
print(f"x* = {res.x}, Z* = {-res.fun}")

# Транспортная задача (PuLP)
from pulp import LpProblem, LpMinimize, LpVariable, lpSum
# ... см. лекцию 6, раздел 7

Требования к отчёту

  1. Титульный лист — название, дисциплина, вариант, ФИО, группа
  2. Задание 1 — построение ОДР, таблица вершин, ответ (можно добавить график из Python/Matplotlib)
  3. Задание 2 — каноническая форма, все симплекс-таблицы, ответ
  4. Задание 3 — начальный план, таблицы потенциалов, все итерации, ответ
  5. Программная проверка — код и результат, сравнение с ручным решением
  6. Выводы — сравнение методов, оценка сложности

Контрольные вопросы

  1. Что такое область допустимых решений? Какими свойствами она обладает?
  2. В чём суть признака оптимальности в симплекс-методе?
  3. Как выбрать разрешающий элемент в симплекс-таблице?
  4. Что такое вырожденный опорный план? Как с ним бороться?
  5. В чём разница метода северо-западного угла и метода наименьшей стоимости?
  6. Как проверяется оптимальность плана в транспортной задаче?
  7. Что такое цикл в транспортной задаче? Как он строится?
  8. Как проверить решение задач ЛП программно?
Наверх