|
Процесс решения задачи линейного программирования носит итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет получено оптимальное решение. Одним из распространенных методов решения задач линейного программирования является симплекс-метод. Симлекс-метод это характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач. Симплекс-метод, известный также под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритмы симплекс-метода позволяют также установить, является ли задача линейного программирования разрешимой. Запишем ограничения задачи линейного программирования в таком виде: Аххх + А2х2 +... + Апх„ + Ап+1хп+1 +... + Ап+тхп+т =А0. (22) Пусть Ai,...,Am множество линейно независимых векторов. Тогда уравнение Ахх\+А2х\ +... + А„х*„ +A„+lx'„+i +... + An+mxl+m = А0 (23) определяет базисное решение xl,x*2,...,x'm. Предположим, что это решение допустимо, то есть *,' > 0,х* £ 0,...,х'т > 0. Базис {Ai,...,Am} образует m-мерное пространство, а потому каждый из векторов Am+i,...,Am+n единственным образом выражается через этот базис. Если Аг не входит в базис, то АухХг + А 2 х 2 г +... + А т х п г = А г , (24) 72 |
определенной последовательности повторяются до тех пор, пока не будет получено оптимапьное решение. Одним из распространенных является методов решения задач линейного это программирования симплекс-метод. Симлекс-метод характерный пример итерационных вычислений, используемых при решении большинства оптимизационных задач. Симплекс-метод, известный также под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритмы симплекс-метода позволяют также установить, является ли задача линейного программирования разрешимой. Запишем ограничения задачи линейного программирования в таком виде: А,х,+А,х, + ... + А„х„+А„^,х„^, + ... + 4,,„,х„^„, = Ао. Пусть А1,...,Ап1 множество линейно независимых векторов. Тогда уравнение (27) ^1X1* +А,х1+... + А„х1+ х^,, +... + А„^„,х1,„ = Л (28) определяет базисное решение Предположим, что это х',х2,...,х^,. решение допустимо, то есть X,'> 0,.Х2 > 0,...,х,*, > О. Базис потому каждый из векторов { А 1 , . . . , А т } образует т-мерное пространство, а единственным образом выражается А т + 1 , . . . , А т + п через этот базис. Если А г не входит в базис, то 87 |