[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

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

Если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. Путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором функция цели принимает оптимальное решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор в конце концов приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано с огромными трудностями, так как для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.
Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума F max, уменьшение - при отыскании минимума F min).
Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере.
Пусть область допустимых решений изображается многоугольником ABCDEGH (рис. 5.1). Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать семь допустимых базисных решений, соответствующих семи угловым точкам многоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем - к оптимальной точке С.

Рис. 5.1

Вместо семи перебрали только три вершины, последовательно улучшая линейную функцию.
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования - симплексного метода.
Симплекс (лат. simplex - простой) - простейший выпуклый многогранник в n-мерном пространстве с n+1 вершиной (например, тетраэдр в 3-мерном пространстве)
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение (по отношению к цели задачи) до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.
Для реализации симплексного метода - последовательного улучшения решения - необходимо освоить три основных элемента:
- способ определения какого-либо первоначального допустимого базисного решения задачи;
- правило перехода к лучшему (точнее, не худшему) решению;
- критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [В начало страницы]