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

В зависимости от вида ограничений различают следующие формы задач:

· Каноническая

· Симметричная

· Общая.

Задача в канонической форме – задача ЛП, в которой все ограничения (8) – (10) есть равенства (p = q = 0) и все переменные неотрицательные (r = n).

Общий метод решения задачи ЛП разработан именно для задачи в каноническом виде.

Матричный вид задачи в канонической форме:

(14’) (15’) (16’)

() = ( * ) →

 =

=   – вектор коэффициентов критерия

 

=  

 =  – матрица условий (технологических коэффициентов)

 = (  )

=  – вектор условий

 =   – вектор ограничений

Векторный вид задачи в канонической форме:

() = ( * )

 +  + …+  =

(16”)

,

Для неё разработан метод решения, который называется симплексным.

Задача в симметричной форме – задача ЛП, в которой все ограничения (8) - (10) есть неравенства (p = q = m) и все переменные неотрицательные (r = n).

(17)   (18)   (19)

Матричный вид задачи в симметричной форме:

Симметричная форма допускает графическое решение (иллюстрацию).

Задача в общей (смешанной) форме – задача ЛП, в которой присутствуют все виды ограничений и не все переменные неотрицательные.

 

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

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

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

() ~ ( ())

 

*

() = ( ())

 

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

·                                                  (20)

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

+  =                                              (21)

                                                         (22)

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

·

(23)

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

 

(24)   (25)

 -  =

 

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

 =  -

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

 = +

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

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

(26)

(27)     (28)

то оно заменяется на два неравенства:

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

(29)

(30)

А также:

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

(31)

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

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

(32)

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

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

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