Рассмотрим подробнее стандартную и каноническую форму задач линейного программирования. В стандартной форме все ограничения являются неравенствами, а в канонической — равенствами (за исключением ограничений, требующих чтобы все ограничения были неотрицательны), но есть определенные нюансы.
Стандартная форма
В стандартной форме задаются \( n \) действительных чисел \(с_1, c_2, \ldots, c_n \); \( m \) действительных чисел \( b_1,b_2,\ldots ,b_m \); и \( mn \) действительных чисел \( a_{ij} \), где \( i=1,2, \ldots, m \) и \( j = 1,2, \ldots, n \).
Требуется найти \( n \) действительных чисел \( x_1,x_2,\ldots,x_n \) которые:
Максимизируют целевую функцию \( \sum\limits_{j=1}^n c_j x_j \) при заданных ограничениях: \( \sum\limits_{j=1}^n a_{ij} x_j \le b_i\) при \( i=1,2, \ldots, m \) и ограничениях неотрицательности \( x_j \ge 0 \) при \( j= 1,2,\ldots,n \)
Преобразование в стандартную форму
Задача находится не в стандартной форме если:
- Целевая функция минимизируется, а не максимизируется
- На имеющиеся переменные не наложены условия неотрицательности
- Некоторые ограничения имеют форму равенства, т.е. имеют знак равенства вместо меньше или равно
- Некоторые ограничения вместо знака «меньше или равно» имеют знак «больше или равно».
Как получить стандартную форму в таких случаях? Рассмотрим по пунктам:
- Достаточно поменять знаки целевой функции, например: \( -5x_1+2x_2 \to min \) эквивалентно \( 5x_1-2x_2 \to max \).
- Если отсутствует ограничение неотрицательности для переменной \(x_j\), то заменяем эту переменную выражением \( x_j^{‘}-x_j^{«} \) из двух неотрицательных переменных \(x_j^{‘},x_j^{«} \ge 0 \).
- Если ограничение имеет вид равенства, то заменяем его парой из двух неравеств «меньше или равно» и «больше или равно».
- Для смены смены выда неравенства с «больше или равно» на «меньше или равно» умножаем обе части неравества на -1 и меняем знак сравнения.
Пример:
\[-5x_1+3x_2 \to min \]
\[ \left\{ {\begin{array}{} {x_1 + 2x_2 = 9 } \\ {x_1 — 3x_2 \le 7 } \\ {x_1 \ge 0 } \end{array}} \right. \]
Шаг 1. Меняем знак целевой функции
\[5x_1-3x_2 \to max \]
\[ \left\{ {\begin{array}{} {x_1 + 2x_2 = 9 } \\ {x_1 — 3x_2 \le 7 } \\ {x_1 \ge 0 } \end{array}} \right. \]
Шаг 2. Для второй переменной \(x_2\) ограничений неотрицательности нет. Заменим на выражение \(x_2=x_2^{‘}-x_2^{»} \):
\[5x_1-3x_2^{‘}+3x_2^{»} \to max \]
\[ \left\{ {\begin{array}{} {x_1 + 2x_2^{‘}-2x_2^{»} = 9 } \\ {x_1 — 3x_2^{‘}+3x_2^{»} \le 7 } \\ {x_1,x_2^{‘},x_2^{»} \ge 0 } \end{array}} \right. \]
Шаг 3. Заменяем равенство на два неравенства:
\[5x_1-3x_2^{‘}+3x_2^{»} \to max \]
\[ \left\{ {\begin{array}{} {x_1 + 2x_2^{‘}-2x_2^{»} \ge 9 } \\ {x_1 + 2x_2^{‘}-2x_2^{»} \le 9 }\\ {x_1 — 3x_2^{‘}+3x_2^{»} \le 7 } \\ {x_1,x_2^{‘},x_2^{»} \ge 0 } \end{array}} \right. \]
Шаг 4. Изменяем знак неравества:
\[5x_1-3x_2^{‘}+3x_2^{»} \to max \]
\[ \left\{ {\begin{array}{} {-x_1-2x_2^{‘}+2x_2^{»} \le -9 } \\ {x_1 + 2x_2^{‘}-2x_2^{»} \le 9 }\\ {x_1 — 3x_2^{‘}+3x_2^{»} \le 7 } \\ {x_1,x_2^{‘},x_2^{»} \ge 0 } \end{array}} \right. \]
Получили задачу в стандартном виде.
Примечание:
В данной заметке рассмотрен основной подход к виду стандартной формы задачи ЛП. Существует и другой подход, например в книге Соколов А. В., Токарев В.В. Методы оптимальных решений. В 2-х т. Т 1. Общие положения. математическое программирование. — 3-е изд. — 564 с. на с. 423 выделяется стандартный вид задачи на максимум:
\[ \left\{ {\begin{array}{} {с_1 x_1 +\ldots+ c_n x_n \to max } \\{a_{11} x_1 +\ldots+ a_{1n} x_n \le b_1 } \\ {\ldots} \\{a_{m1} x_1 +\ldots+ a_{mn} x_n \le b_m }\\{ x_1 ,\ldots ,x_n \ge 0 }\end{array}} \right. \]
и на минимум
\[ \left\{ {\begin{array}{} {с_1 x_1 +\ldots+ c_n x_n \to min } \\{a_{11} x_1 +\ldots+ a_{1n} x_n \ge b_1 } \\ {\ldots} \\{a_{m1} x_1 +\ldots+ a_{mn} x_n \ge b_m }\\{ x_1 ,\ldots ,x_n \ge 0 }\end{array}} \right. \]
Однако в общепринят первый вариант из которого второй получается простым умножением обеих частей неравенств на -1.