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

Стандартная форма задачи линейного программирования

Опубликовано 19.09.2016

Рассмотрим подробнее стандартную и каноническую форму задач линейного программирования. В стандартной форме все ограничения являются неравенствами, а в канонической - равенствами (за исключением ограничений, требующих чтобы все ограничения были неотрицательны), но есть определенные нюансы.

Стандартная форма

В стандартной форме задаются \( 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 \)

 

Преобразование в стандартную форму

Задача находится не в стандартной форме если:

  1. Целевая функция минимизируется, а не максимизируется
  2. На имеющиеся переменные не наложены условия неотрицательности
  3. Некоторые ограничения имеют форму равенства, т.е. имеют знак равенства вместо меньше или равно
  4. Некоторые ограничения вместо знака "меньше или равно" имеют знак "больше или равно".

Как получить стандартную форму в таких случаях? Рассмотрим по пунктам:

  1. Достаточно поменять знаки целевой функции, например: \( -5x_1+2x_2 \to min \) эквивалентно \( 5x_1-2x_2 \to max \).
  2. Если отсутствует ограничение неотрицательности для переменной \(x_j\), то заменяем эту переменную выражением \(x_j^{'}-x_j^{''} \) из двух неотрицательных переменных \(x_j^{'},x_j^{''}  \ge 0 \).
  3. Если ограничение имеет вид равенства, то заменяем его парой из двух неравеств "меньше или равно" и "больше или равно".
  4. Для смены смены выда неравенства с "больше или равно" на "меньше или равно" умножаем обе части неравества на -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. \]

 

Получили задачу в стандартном виде.