Закрыть

Каноническая постановка задачи линейного программирования

Автор: Васин Алексей
Опубликовано 08.02.2008 в 15:56
Раздел: Методы оптимизации

В различных задачах линейного программирования допустимое множество может описываться различными способами: системами неравенств различных знаков, наборами равенств и, наконец, комбинациями равенств и неравенств.

Такое разнообразие описаний является, с точки зрения теории, определенным недостатком, так как вынуждает каждый тип описания рассматривать по-своему. Однако все варианты постановок могут быть сведены к задаче линейного программирования, содержащей лишь равенства и условие неотрицательности переменных:

$\displaystyle{min_{Ax = b, x \geq 0} cx}$

Такая формулировка называется канонической.

Сведения к канонической форме задачи линейного программирования осуществляются, в зависимости от первоначальной формулировки, с помощью несложных приемов, изложенных ниже.

Ограничение типа неравенства $ax \leq b$ сводится к равенству $ax+s=b$ добавлением искусственной (дополнительной) переменной $s \geq 0$.

В задаче линейного программирования иногда присутствуют переменные, которые могут принимать как положительные, так и отрицательные значения. Чтобы свести такую задачу к канонической, каждая такая переменная $x_i$ может быть представлена как разность 

$x_i = u_i - v_i$ (*)

неотрицательных переменных $u_i , v_i$. В частности, например, можно положить

$x_i = \max(x_i , 0) - \max(-x_i ,0)$

Следует сразу отметить, что представление (*) не единственно и, соответственно, оптимальное решение становится также не единственным.

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей