2. Лекции Практические и лабораторные занятия


Теорема. (Об альтернативном оптимуме.)



бет16/46
Дата06.01.2022
өлшемі0,77 Mb.
#11583
1   ...   12   13   14   15   16   17   18   19   ...   46
Байланысты:
УМКД метод матер МО и Исл опер

Теорема. (Об альтернативном оптимуме.) Если мак­симум или минимум линейной функции достигается в не­скольких опорных решениях, то любое оптимальное решение есть выпуклая линейная комбинация оптимальных решений.

Геометрическая интерпретация симплекс-метода

Из приведенных выше основных теорем линейного пре­мирования следует, что если задача линейного пре­мирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений.

На основании этого можно предложить достаточно простой метод решения задачи линейного программирования, который сводится к следующей принципиальной схеме:

  • необходимо найти все опорные решения (точки много­гранника), множество которых является конечным;

  • вычислить для каждого из опорных решений значение целевой функции;

  • сравнить значения целевой функции в каждом из опорных решений и выбрать оптимальное (максималь­ное или минимальное).

Теоретически данная схема приведет к нахождению оптимального решения, но практически ее осуществление связано с большими вычислительными трудностями.

Если же указанный перебор опорных решений произво­дить направленно, т.е. на каждом из шагов улучшая (или, по крайней мере, не ухудшая) значение целевой функции, то число перебираемых опорных решений можно резко сокра­тить, что в конечном итоге приводит к весьма существенно­му сокращению числа шагов при отыскании оптимума целе­вой функции. При использовании такой схемы, в отличие от первой, каждое последующее опорное решение выбирается таким образом, чтобы оно было лучше, (или, по крайней ме­ре, не хуже) предыдущего, именно поэтому на каждом из шагов значение целевой функции улучшается (или, по край­ней мере, не ухудшается).

Фундаментом универсального метода решения задач иного программирования, который называется симплекс-методом, является метод направленного перебора. (По латыни симплекс означает — простой, что в данном случае интерпретируется как простой выпуклый многогранник.)

Геометрическая интерпретация симплекс-метода состоит в последовательном переходе от одной вершины многогран­ника к другой (от первоначально выбранной вершины к од­ной из соседних вершин, а именно к той, у которой линейная функция принимает лучшее или, по крайней мере, не худшее значение). Этот процесс происходит до тех пор, пока не бу­дет найдено оптимальное решение — вершина, где достига­ется оптимальное значение функции (если задача имеет ко­нечный оптимум).

Идея симплекс-метода разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американ­ский ученый Д. Данциг в 1949 г. разработал симплекс-метод, позволяющий решить любую задачу линейного программи­рования.

В настоящее время на основе этого метода разработан пакет программ, с применением которого решаются задачи линейного программирования.




Достарыңызбен бөлісу:
1   ...   12   13   14   15   16   17   18   19   ...   46




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет