Если известно некоторое опорное решение задачи линейного программирования в канонической форме, то ее можно решать симплекс-методом. Симплекс-метод—это направленный перебор опорных решений, при котором значение целевой функции на каждом последующем опорном решении меньше, чем на предыдущем (для задачи минимизации). [c.197]
Если все оценки некоторого базиса опорного решения не положительны, то оно является оптимальным решением задачи линейного программирования в канонической форме. (Признак оптимальности.) [c.195]
Для решения симплекс-методом задачи линейного программирования в канонической форме необходимо выполнить ряд последовательных шагов. На каждом шаге либо возникает базис нового опорного решения, причем на новом опорном решении значение целевой функции обязательно меньше, чем на предыдущем (для задачи минимизации), либо меняется базис исходного опорного решения. [c.197]
Конечность симплекс-метода. Если задача линейного программирования в канонической форме не имеет вырожденных опорных решений, то через конечное число шагов симплекс-метода она будет решена. [c.198]
Опорные решения играют важнз /Ю Роль ПРИ решении задачи линейного программирования. т канонической форме, так как если эта задача имеет оптм мальное решение, то одно из ее оптимальных решений обязательно будет ее опорным решением. Таким образом, оптимальное решение задачи линейного программирования в канонической форме можно искать только среди ее опорных решений (а их лишь конечное число). [c.194]