Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Задачи для самостоятельного решения

Решить графическим методом следующие задачи:

93

4.3. Алгоритм симплексного метода

Рассмотрим задачу линейного программирования, записанную в канонической форме:

(базисной точкой), если векторы-столбцы матрицы А: Ai1 ,..., Aik ,

k n , соответствующие его ненулевым координатам, линейно независимы.

Симплекс-метод решения ЗЛП (1)-(3) представляет собой итерационную процедуру последовательного перехода от одного базисного решения к другому с меньшим (большим) значением целевой функции до получения оптимального решения. Следует отметить, однако, что на начальном этапе решения обязательно наличие исходной базисной точки.

Известно, что число положительных координат базисной точки не может быть более, чем ранг матрицы r(А)= m. Если базисная точка содержит ровно т положительных координат, то она называется невырожденной, в противном случае - вырожденной. Задача называется невырожденной, если допустимое множество не имеет вырожденных базисных точек.

Перебор базисных точек осуществляется с помощью преобразований Жордана-Гаусса.

Пусть имеется исходная базисная точка допустимого множества ЗЛП xBT (xi ,i I; xj 0, j J ) . Координаты xi ,i I

94

будем в дальнейшем называть базисными, xj 0, j J -

небазисными. Соответственно множество I - множеством базисных (зависимых) индексов, J -множеством небазисных

(свободных) индексов. В случае невырожденной задачи каждой базисной точке соответствует известный базис, состоящий из

векторов Ai ,i I . Обозначим его через В. Заметим далее, что

каждая итерация метода Жордана-Гаусса соответствует переходу от одной базисной точки к другой при замене одной базисной (зависимой) переменной на одну небазисную (свободную). При этом выбору подлежит номер небазисной переменной k и жестко

определяется номер базисной переменной l ( alk 0 ). Координаты новой базисной точки вычисляются следующим образом:

Таким образом, получается алгоритм, позволяющий перебрать все базисные точки ЗЛП. Однако возникает естественное желание исключить из рассмотрения точки, обеспечивающие «худшее» значение целевой функции, нежели уже известные. С целью такой «фильтрации», вычислим значение целевой функции в

точке xBH , представленной в виде (4.3.4).

следующей итерации будет получена точка с большим значением

95

допустимую, но не базисную точку. (см. (4.3.4)). Значение целевой функции в этой точке изменяется в соответствии с формулой (4.3.5), откуда видно, что если выбирать как угодно большим, то значение функции цели будет как угодно увеличиваться. Следовательно, в таком случае можно сделать вывод о неограниченности целевой функции на допустимом множестве.

6.Осуществить переход к новой базисной точке с помощью преобразований Жордана-Гаусса с направляющим элементом alk .

7.Изменить исходную информацию:

Перейти к п.1.

96

единственное решение задачи.

10.Выписать ответ: задача решений не имеет из-за неограниченности целевой функции на допустимом множестве:

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

базисной точки. Далее переписываем элементы матрицы

помещая над каждым столбцом коэффициент соответствующей переменной в целевой функции. Последний столбец предназначается для определения значения . В отдельной строке вычисляются

оценки векторов Aj . В ячейке, находящейся на пересечении

97