![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых оазисных решений системы. Путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором функция цели принимает оптимальное решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор в конце концов приведет к оптимальному решению (если оно существует), однако практическое его осуществление связано с огромными трудностями, так как для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.
Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь, чтобы каждое следующее решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее по значениям линейной функции (увеличение ее при отыскании максимума F max, уменьшение при отыскании минимума F
min). Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере.
Пусть область допустимых решений изображается многоугольником ABCDEGH (рис. 5.1). Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать 7 допустимых базисных решений, соответствующих 7 угловым точкам многоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем — к оптимальной точке С.
Рис. 5.1
Вместо 7 перебрали только 3 вершины, последовательно улучшая линейную функцию.
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования — симплексного метода. Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение (по отношению к цели задачи) до тех пор, пока не будет найдено оптимальное решение — вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. его идеи были разработаны советским ученым Л.В. Канторовичем.
Для осуществления основной цели симплексного метода - последовательного улучшения решения – используются три основных элемента:
1. Способ определения какого-либо первоначального допустимого базисного решения задачи.
2. Правило перехода к лучшему (точнее, не худшему) решению.
3. Критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений. Алгоритм конкретной вычислительной реализации этих элементов рассмотрим на примерах.
Дата публикования: 2014-10-18; Прочитано: 2805 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!