Методы принятия управленческих решений: для менеджеров

45 §5. Симплекс-метод решения задачи линейного программирования. Метод искусственного базиса Симплекс-метод является основным методом решения задач линейного программирования. Он предложен в 1949 году американ­ ским математиком Джорджем Бернардом Данцигом (1914-2005). Симплекс-метод применяется для решения задач вида, т.е. задач ли­ нейного программирования, записанных в каноническом виде L = L{xy,x2,. ;x „) = c q - I - С ] * ! - I - С 2 Х 2 + . . . + с„х„ — ^ m i n ; (33) X] +012*2 +-+"l7n+l*m+l +- + ^ln*n = ^1' Xl + — + "2m+\^m+\ +--- + 02 „X„ =62. (34) ДГ] > 0 , *2 > 0 , ... , > 0 . (35) Запишем систему ограничений (34) в векторной форме + А2Х2 + ...+ ^ » г п 0 ю II о ' 1 ,... , = О О ч ' ^т+1 ~ / \ ^lm+1 <^2т+2 о .0. ^тт+\ ^ ^\п II ' * 0 ^2 •J^mn, Переменные xi,x2,--,x „ называются базисными перемен­ ными, а столбцы ^1,^2' - '^ш называются базисными столбцами. Переменные ' •••*« называются свободными племенными.