Переход от неканонической формы ЗЛП к канонической.
Теорема 1. Каждому решению неравенства соответствует единственное решение уравнения и неравенства , и наоборот.
Из теоремы следует, что неравенство можно заменить уравнением и неравенством .
Переменную называют балансовой переменной.
Следовательно, чтобы привести задачу к каноническому виду, нужно заменить каждое неравенство системы ограничений соответствующим уравнением и неравенством , введя в каждое неравенство балансовую переменную с коэффициентом +1, если знак неравенства £, и с коэффициентом -1, если знак неравенства ³. В целевую функцию балансовые переменные вводятся с нулевыми коэффициентами.
Если на переменную не наложено условие на неотрицательность, то эту переменную надо представить в виде разности двух неотрицательных переменных: , где
Переход от канонической формы ЗЛП к симметричной форме.
Чтобы перейти от канонической формы ЗЛП к симметричной, нужно найти общее решение системы уравнений:
|
|
Так как все переменные должны быть неотрицательными, в том числе и базисные, получим систему неравенств:
Чтобы исключить базисные переменные из целевой функции, необходимо в целевую функцию вместо базисных переменных подставить их выражения через свободные переменные.
Пример 1. Дана ЗЛП: найти наибольшее значение функции при ограничениях:
.
Приведем ее к каноническому виду.
Канонический вид задачи: найти наибольшее значение функции при ограничениях:
.
Пример 2. Перейти от канонического вида задачи к симметричному. Найти наибольшее значение функции при ограничениях:
.
Разрешим систему относительно произвольного базиса, система примет вид
И так как , отбросив базисные переменные, получим систему неравенств
Выразим целевую функцию через свободные переменные:
Симметричный вид задачи: найти наибольшее значение функции при ограничениях:
.