Векторно-матричная запись

Постановка задачи

Линейное программирование

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

,

.

(Р_к)

где .

– целевая функция,

– вектор стоимости,

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

– матрица условий.

Обозначение: − численное значение задачи (P), – множество решений задачи (P), т.е. множество допустимых точек , для которых .

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

(Р)

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

(Р_n)

Каноническая форма более удобна при описании алгоритмов решения, общая – используется при рассмотрении проблем существования решения, нормальная – двойственность.

Задачи в различных формах сводятся друг к другу путем введения дополнительных координат и изменением матрицы A.

Нормальная к канонической: введение дополнительных координат :

Общая к канонической: переход к задаче на максимум и введение дополнительных координат :

Каноническая к нормальной: от системы равенств перейти к системе с единичным базисом , где , . Из последней системы выразить неотрицательные переменные и подставить их в целевую функцию. Получаем следующую задачу ЛП в нормальной форме

Каноническая к общей: аналогично + переход к задаче на минимум

Дата добавления: 2014-01-05