Приведение задачи линейного программирования от одной эквивалентной формы к другой

1. Сведение задачи минимизации к задаче максимизации:

Преобразование сводится к смене знака критерия.

() ~ ( ())

*

2. Переход от ограничений-неравенств к уравнениям:

· (20)

Неравенство (20) заменяется на уравнение (21) и условие (22)

+ = (21)

(22)

Переменные – дополнительные или балансовые, так как обеспечивают баланс правой и левой частей.

·

Аналогично, неравенство (23) заменяется на уравнение (24) и условие (25)

3. Переход от переменных произвольного знака к неотрицательным переменным:

= -

4. Переход от переменных, ограниченных снизу, к неотрицательным:

= +

5. Переход от уравнений к неравенствам:

· Если имеется уравнение:

· Пусть есть несколько ограничений:

Пусть ранг (количество линейно-независимых уравнений) системы ограничений равен , тогда переменных можно выразить через остальные:

Задавая произвольные значения свободным переменным, получаем частные решения, но не все они удовлетворяют условиям неотрицательности:

Тогда для свободных переменных получаем ограничения в виде неравенств:

Если () = 2, то задача допускает иллюстрацию в пространстве двух переменных.

Для задачи в канонической форме, если все уравнения независимы и переменных на две больше, чем уравнений (т.е. () = 2), то свободных переменных в общем решении будет две и задача допускает графическое решение.