Сентябрь 19

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

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

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

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

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


Примечание:

В данной заметке рассмотрен  основной подход к виду стандартной формы задачи ЛП. Существует и другой подход, например в книге Соколов А. В., Токарев В.В. Методы оптимальных решений. В 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.




Опубликовано 19.09.2016 Тушавин В.А. в категории "Прикладные методы оптимизации