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

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

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума F -» max, уменьшение — при отыскании минимума F-> min).

Такой перебор позволяет сократить число шагов при отыска­нии оптимума. Поясним это на фафическом примере.

Пусть область допустимых решений изображается многоуголь­ником ABCDEGH (рис. 5.1). Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать семь допустимых базисных решений, соответствующих семи угловым точкам мно­гоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем — к оптимальной точке С.

Хг а

\ F=0 N \ \

0\

Рис. 5.1

Вместо семи перебрали только три вершины, последовательно улучшая линейную функцию.

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного профаммирова­ния — симплексного¹ метода.

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

¹ Симплекс (лат. simplex — простой) — простейший выпуклый много-фанник в л-мерном пространстве с л+1 вершиной (например, тетраэдр в 3-мерном пространстве); симплексом является также область допустимых

N

решений неравенства вида У, ^xj - 1-

1=1

 

i«-*w.:

3 Исследование операций

В ЭКОНОМИКС

Глава 5

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

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В.Канторовичем.

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

Для реализации симплексного метода — последовательного улучшения решения — необходимо освоить три основных элемента:

• способ определения какого-либо первоначального допустимого базисного решения задачи;

• правило перехода к лучшему (точнее, не худшему) решению;

• критерий проверки оптимальности найденного решения.

Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде урав­нений. Алгоритм конкретной вычислительной реализации этих элементов рассмотрим на примерах.

---

123