В любой задаче линейного программирования (ЗЛП) ограничения записываются в виде систем линейных неравенств или равенств.
Одним из ключевых требований, которое часто предъявляют к таким ограничениям, является неотрицательность правой части (RHS – Right‑Hand Side).
В данной статье мы подробно разберём, почему это требование важно, как оно связано с канонической формой задачи, какие математические преобразования позволяют привести любые ограничения к нужному виду, и какие последствия оно имеет для экономических моделей.
Что такое правые части ограничений?
При записи ограничения в виде Ax ≤ b (или Ax = b) вектор b называется правой частью.
Каждый элемент b_i определяет доступный ресурс (сырье, рабочее время, капитал и т.п.) или пороговое значение (максимальная нагрузка, минимальная требуемая выручка и т.д.).
Если b_i отрицательно, это означает, что требуемый ресурс уже «отрицательный», что в реальной экономике обычно не имеет смысла. Поэтому большинство учебных и практических моделей стремятся к тому, чтобы все b_i ≥ 0.
Почему в классическом ЗЛП правые части считаются неотрицательными?
- Экономический смысл. Положительные или нулевые правые части отражают наличие ограниченного, но не «отрицательного» количества ресурса.
- Теоретическая корректность. Многие фундаментальные теоремы (например, теорема Фейера о двойственности) формулируются при условии b ≥ 0. Это упрощает доказательства и гарантирует существование двойственной задачи.
- Алгоритмическая простота. Метод симплекса в своей базовой версии предполагает, что все ограничения приведены к канонической форме, где правые части неотрицательны. Это позволяет сразу задать базисные переменные со значениями b_i.
Приведение задачи к канонической форме
Любую задачу линейного программирования можно преобразовать к канонической форме (или стандартной форме), где:
- Все ограничения – равенства.
- Все переменные – неотрицательны (x_j ≥ 0).
- Все правые части b_i ≥ 0.
Алгоритм преобразования:
- Преобразование неравенств в равенства. Если ограничение имеет вид ∑ a_{ij}x_j ≤ b_i, вводится искусственная (слэк‑) переменная s_i ≥ 0:
∑ a_{ij}x_j + s_i = b_i
Если знак «≥», вводится переменная s_i ≥ 0 со знаком «‑»:
∑ a_{ij}x_j — s_i = b_i
- Обеспечение неотрицательности правой части. Если в результате преобразования получилось b_i < 0, меняем знак у соответствующего уравнения:
−∑ a_{ij}x_j ∓ s_i = −b_i
После этого правая часть становится неотрицательной (−b_i ≥ 0).
- Разделение свободных переменных. Если в исходной задаче встречаются переменные, не ограниченные условием неотрицательности, их заменяют разностью двух неотрицательных переменных:
x_j = x_j^{‘} − x_j^{»}, x_j^{‘}, x_j^{»} ≥ 0
Пример:
Макс: 3x₁ + 5x₂ при: 2x₁ + x₂ ≤ 4 -x₁ + 2x₂ ≥ -3 x₁, x₂ свободны
Преобразуем:
- Введём слэк‑переменную s₁ ≥ 0 → 2x₁ + x₂ + s₁ = 4 (RHS уже ≥ 0).
- Для ограничения «≥» меняем знак и вводим s₂ ≥ 0:
−(−x₁ + 2x₂) + s₂ = 3 ⟹ x₁ − 2x₂ + s₂ = 3
- Свободные переменные заменяем:
x₁ = x₁’ − x₁», x₂ = x₂’ − x₂»
После подстановки получаем каноническую форму, где все b_i ≥ 0.
Двойственная задача и роль правых частей
В двойственной задаче (ДЗП) коэффициенты правых частей исходной (прямой) задачи становятся коэффициентами целевой функции, а коэффициенты целевой функции прямой задачи – правыми частями двойственной.
Если в прямой задаче b ≥ 0, то в двойственной целевая функция стремится к максимизации (при условии, что прямая задача – минимум) и имеет вид:
Макс: bᵀy при: Aᵀy ≤ c, y ≥ 0
Отрицательные b_i могут привести к тому, что двойственная задача будет требовать y_i ≤ 0, что нарушает стандартное требование неотрицательности двойственных переменных и усложняет интерпретацию (например, «цену» ресурса). Поэтому приведение b к неотрицательному виду упрощает построение двойственной модели и её экономический смысл.
Практические последствия в экономических моделях
- Оптимизация прибыли. При планировании производства правые части ограничений часто представляют доступные объемы сырья, рабочей силы, мощностей. Наличие отрицательных значений означало бы «дефицит», который в реальном планировании обычно учитывается отдельными ограничениями (например, запасы, кредиты).
- Анализ чувствительности. При оценке влияния изменения ресурсов (правых частей) на оптимальное решение удобно рассматривать небольшие положительные приращения Δb_i ≥ 0. Наличие изначально отрицательных b_i усложняет интерпретацию «добавления» ресурса.
- Статистическая неопределённость. В реальной экономике параметры часто меняются (цены, спрос). При построении детерминированных моделей принято фиксировать b_i как известные и положительные, а затем проводить сценарный анализ (вариации b_i в положительном диапазоне).
Как работать с отрицательными правыми частями?
Если в исходных данных встречаются отрицательные b_i, есть несколько стандартных подходов:
- Смена знака у соответствующего ограничения. Как показано выше, меняем знак у обеих частей уравнения, получая положительное RHS.
- Модель с «отрицательными ресурсами». Иногда в задачах финансирования допускаются отрицательные балансы (долги). В таком случае правые части могут быть отрицательными, но тогда двойственная задача будет иметь переменные, допускающие отрицательные значения, что требует расширения базовой теории.
Алгоритмические детали: симплекс‑метод и RHS
В симплекс‑методе базисные переменные изначально выбираются из тех, у которых правые части неотрицательны. Если хотя бы один RHS b_i отрицателен, базисное решение не является допустимым, и необходимо выполнить фазу 0 (или фазу I):
- Добавляются искусственные переменные a_i в каждый «проблемный» ряд.
- Минимизируется сумма искусственных переменных (метод большой M).
- После получения базисного допустимого решения искусственные переменные удаляются, и переходим к основной фазе (оптимизация оригинальной ЦФ).
Таким образом, наличие отрицательных правых частей не делает задачу неразрешимой, но добавляет дополнительный вычислительный шаг.
Пример решения в Excel (по схеме «слеак‑переменные»)
В таблицах Excel часто используют добавление слэк‑переменных для построения модели:
- Создаём столбцы для переменных x₁, x₂, …, x_n и слэк‑переменных s₁, s₂, ….
- Заполняем коэффициенты ограничений в виде матрицы A.
- В ячейках правой части вводим значения b_i. Если b_i отрицательно, меняем знак у всей строки и ставим «=ABS(b_i)».
- Устанавливаем целевую функцию в отдельной ячейке и используем «Поиск решения» (Solver) с типом решения «Линейное программирование», указав ограничения «=» и «≥»/«≤».
Excel автоматически преобразует ограничения в каноническую форму, но пользователь должен убедиться, что все b_i ≥ 0 – иначе Solver может вернуть ошибку «Нет допустимого начального решения».
- Неотрицательные правые части – ключевой элемент стандартной формы линейного программирования, обеспечивающий экономический смысл и математическую корректность.
- При наличии отрицательных b_i задача всё равно решаема, но требует дополнительных преобразований (смена знака, искусственные переменные, фазовый метод).
- Для построения двойственной задачи и проведения анализа чувствительности предпочтительно работать с b ≥ 0, так как это упрощает интерпретацию двойственных переменных как «цен» ресурсов.
- В практических экономических моделях большинство ограничений естественно удовлетворяют условию b_i ≥ 0, однако при моделировании финансовых потоков, долгов или отрицательных запасов следует применять специальные техники.
Понимание и корректное использование неотрицательных правых частей позволяет эффективно формировать модели, применять симплекс‑метод и интерпретировать результаты в контексте реального бизнеса.