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

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

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

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

· Общая.

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

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

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

=

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

=

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

= ( )

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

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

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

( ) = ( * )

+ + …+ =

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

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

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

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

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

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

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

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

( ) ~ ( ( ))

*

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

· (20)

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

+ = (21)

(22)

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

·

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

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

= -

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

= +

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

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

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

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

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

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

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

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