Приведение общей ЗЛП к канонической форме

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

В том случае, когда требуется найти минимум функции , можно перейти к нахождению максимума функции , поскольку .

Ограничения-неравенства исходной ЗЛП можно преобразовать в ограничения-равенства добавлением к их левой части дополнительной неотрицательной переменной со знаком "+" в случае неравенства вида "" и со знаком "-" - в случае неравенства вида "". Таким образом, ограничение-неравенство

преобразуется в ограничение-равенство

,

а ограничение-неравенство

- в ограничение-равенство

.

Если на переменную не наложено условие неотрицательности, то эту переменную надо представить в виде разности двух новых неотрицательных переменных: , .

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

Вместо нахождения минимума функции F можно найти максимум функции при ограничениях, получающихся из ограничений-неравенств исходной задачи с помощью дополнительных неотрицательных переменных с соответствующим знаком. В первое ограничение системы добавим переменную со знаком «+», во второе ограничение – переменную со знаком «-» и в третье ограничение системы – переменную со знаком «+». Так как на переменные не наложено условие неотрицательности, то необходимо произвести следующую замену переменных:

Следовательно, исходная задача может быть записана в канонической форме так: найти максимум функции при условиях:

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