2. Лекции Практические и лабораторные занятия
Теорема. (Об альтернативном оптимуме.)
жүктеу/скачать 0,77 Mb.
|
- Бұл бет үшін навигация:
- Геометрическая интерпретация симплекс-метода
| Теорема. (Об альтернативном оптимуме.) Если максимум или минимум линейной функции достигается в нескольких опорных решениях, то любое оптимальное решение есть выпуклая линейная комбинация оптимальных решений.
Геометрическая интерпретация симплекс-метода Из приведенных выше основных теорем линейного премирования следует, что если задача линейного премирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. На основании этого можно предложить достаточно простой метод решения задачи линейного программирования, который сводится к следующей принципиальной схеме: необходимо найти все опорные решения (точки многогранника), множество которых является конечным; вычислить для каждого из опорных решений значение целевой функции; сравнить значения целевой функции в каждом из опорных решений и выбрать оптимальное (максимальное или минимальное). Теоретически данная схема приведет к нахождению оптимального решения, но практически ее осуществление связано с большими вычислительными трудностями. Если же указанный перебор опорных решений производить направленно, т.е. на каждом из шагов улучшая (или, по крайней мере, не ухудшая) значение целевой функции, то число перебираемых опорных решений можно резко сократить, что в конечном итоге приводит к весьма существенному сокращению числа шагов при отыскании оптимума целевой функции. При использовании такой схемы, в отличие от первой, каждое последующее опорное решение выбирается таким образом, чтобы оно было лучше, (или, по крайней мере, не хуже) предыдущего, именно поэтому на каждом из шагов значение целевой функции улучшается (или, по крайней мере, не ухудшается). Фундаментом универсального метода решения задач иного программирования, который называется симплекс-методом, является метод направленного перебора. (По латыни симплекс означает — простой, что в данном случае интерпретируется как простой выпуклый многогранник.) Геометрическая интерпретация симплекс-метода состоит в последовательном переходе от одной вершины многогранника к другой (от первоначально выбранной вершины к одной из соседних вершин, а именно к той, у которой линейная функция принимает лучшее или, по крайней мере, не худшее значение). Этот процесс происходит до тех пор, пока не будет найдено оптимальное решение — вершина, где достигается оптимальное значение функции (если задача имеет конечный оптимум). Идея симплекс-метода разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американский ученый Д. Данциг в 1949 г. разработал симплекс-метод, позволяющий решить любую задачу линейного программирования. В настоящее время на основе этого метода разработан пакет программ, с применением которого решаются задачи линейного программирования. жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|