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

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

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


( ) ~ ( ( ))

*
( ) = ( ( ))

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

·
(20) (21) (22)

+ =

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

·
(23)

(24) (25)
- =

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

= -

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

= +

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

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

(26)

(27) (28)
то оно заменяется на два неравенства:

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

(29)

(30)
А также:

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

(31)
Под решением систем уравнений (29) понимается зависимость одних переменных через другие. Эта зависимость (31) называется общим решением, независимые переменные – свободными (их можно произвольно менять), а – базисными переменными.

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

(32)

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

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

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


8499982201017446.html
8500048256869345.html

8499982201017446.html
8500048256869345.html
    PR.RU™