Введение в методы оптимизации

Приведение ЗЛП к канонической форме сопровождается увеличением размерности вектора независимых переменных. Можно убедиться, что вектор / = е является решением задачи (2.1) - (2.5) в том и только в том случае, ес­ ли вектор X* является решением задачи (2.6) - (2.10). Пример. Пусть дана ЗЛП F(x) = 3xi - 5x2 + 2X3 min; 2Xi — Xj + 5X3 < 2; -Зх, 4- 4x2 ~ ^3 - 5; X, - 4X2 + 2X3 > 3; X, > О, X2 > 0. Приведем ее к эквивалентной ЗЛП, имеющей канониче­ скую форму. Для того чтобы избавиться от неравенств, необ­ ходимо в левые части ввести дополнительные неотрицатель­ ные переменные х^, х^, Xg и заменить их равенствами. По­ скольку переменная Х3 может иметь произвольный знак, сле­ дует положить Хз = Хз - Х3, где Х3 и Х3 неотрицательны. М нимизация функции /(х) сводится к максимизации функции (-/(х)) = -3xj -1-5X2 ~2хз. Таким образом, исходная задача приводится к следую­ щей ЗЛП, имеющей каноническую форму: / ( х ) = -3Xi -1- 5X2 - 2X3 -1- 2X3 —> max; , - X j 4- 5X3 - 5X3 -I- Х4 =2; - 3X i -I- 4X2 - X3 + X3 - X5 =5; 29