Формы записи задачи линейного программирования

Задача линейного программирования записывается в различных формах. В одних задачах ограничения имеют вид равенств, в других случаях − в виде неравенств. Многие правктические задачи сводятся к смешанным условиям, где часть ограничений неравенства, другие − равенства. Не во всех задачах требуется неотрицательность всех переменных. Такое разнообразие в формах записи требует разработки специальных методов для решения конкретных задач и затрудняет исследование общих особенностей линейного программирования и создания общих методов решения. Следовательно более удобно рассматривать способ сведения любой задачи линейного программирования к наиболее простой для исследования форме.

Каноническая форма задачи линейного программирования оказывается наиболее удобной при построении вычислительных алгоритмов. Для решения таких задач применяют симплекс метод.

Рассмотрим задачи линейного программирования записанные в различных формах.

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

(1)

называется общей задачей линейного программирования.

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

(2)

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

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

(3)

или

(3')

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

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

(4)

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

Для приведения задачи линейного программирования к каноничнскому виду (2), нужно преобразовать неравенства в равенства добавлением в каждое неравенство дополнительного неотрицательного переменного. Если в ограничениях задачи линейного программирования есть переменные, на которых не налагается ограничения в виде неотрицательности, то это можно исправить заменив каждое такое переменное на

где