 |
 |
 |
 |
|
 |
 |
18
основанные на последовательном, целенаправленном переборе базисных планов ЗЛП.
Классическим методом решения ЗЛП стал симплекс-метод, получивший также в литературе
название метода последовательного улучшения плана, разработанный в 1947г. американским
математиком Джорджем Данцигом.
Идея такого перехода от одного базисного плана к другому, при котором происходит «улучшение»
значения целевой функции, может быть продемонстрирована для случая m = 2 с помощью рис. 1.4. Если
вектор ограничений b принадлежит конусу, натянутому на некоторые два базисных вектора условий
{а
j1
,а
j2
}, то существует такой базисный план х с базисными компонентами х
j1
,
х
j2
, что b= х
j1
a
j1
+ х
j2
a
j2
.
Разумеется, таких планов может быть несколько в зависимости от выбора системы базисных векторов.
Чтобы различать их по соответствующей величине целевой функции
f(x)=c
j1
x
j1
+с
j2
х
j2
, вводятся так
называемые расширенные векторы условий и ограничений. В общем случае расширенный столбец
условий a
j
получается соединением коэффициента целевой функции с
j
и столбца а
j
:
расширенный вектор ограничений определим как
В дальнейшем для удобства нумерации элементов будем считать, что добавляемый коэффициент
целевой функции с
j
является нулевым элементом j-го расширенного столбца условий, т. е. a
0,j
= с
j
. При
изображении расширенных векторов нулевая координата откладывается вдоль вертикальной оси — оси
аппликат.
Рассмотрим также вектор
=
Геометрически определение вектора b означает, что он принадлежит конусу, натянутому на
расширенные векторы, а вектор служит его проекцией. Нулевая координата вектора b имеет вид:
т. е. равна значению целевой функции для выбранного базисного плана.
Из геометрической иллюстрации следует, что для решения задачи мы должны среди векторов а
j
выбрать такой набор {а
j1
,а
j2
}, чтобы, прямая, проведенная через конец вектора параллельно оси
аппликат, пересекала конус, натянутый на систему соответствующих расширенных столбцов { a
j1
,
a
j2
}, в «наивысшей» точке.
На рис. 1.4 выделен конус, натянутый на систему расширенных столбцов a² и a³, отвечающих
текущему допустимому базису. Нетрудно заметить, что данный базис не является оптимальным,
например, для базиса {а³, а
4
} точка пересечения соответствующего конуса и прямой будет находиться
выше. Можно, наоборот, указать базис с «худшим» значением целевой функции: {а¹ а²}. Наконец,
рассматриваемая геометрическая интерпретация КЗЛП иллюстрирует и общую идею критерия, который
используется в симплекс-методе для определения оптимальности (или неоптимальности) текущего
плана: если существуют векторы-столбцы, лежащие выше плоскости,
проходящей через векторы
текущего базиса, то он не является оптимальным и может быть «улучшен».