лекции рогов / Рогов_лекция_3

§5. Симплекс– метод

1. Идея симплекс– метода

В предыдущем разделе было показано, что если задача линейного программирования имеет оптимальное решение, то одним из оптимальных решений является допустимое базисное решение ее системы ограничений, которое соответствует некоторой угловой точке многогранника допустимых решений системы. Было показано, как с помощью конечного перебора базисных решений системы ограничений задачи, найти это оптимальное решение. Однако с ростом размерности n системы ограничений задачи объем вычислений решения задачи методом полного перебора базисных решений растет экспоненциально и становится непригодным на практике. Можно организовать перебор только допустимых базисных решений и число перебираемых решений резко сократить, если каждое следующее допустимое базисное решение выбирать так, чтобы соответствующее значение целевой функции улучшалось или хотя бы не ухудшалось. Такой подход позволяет сократить число шагов при отыскании оптимального базисного решения. Эту идею поясним графически.

Пусть многоугольник ABCDEFGH изображает множество допустимых решений ЗЛП с двумя переменными, а вектор – градиент целевой функции.

Рис. 5. 1

Нужно найти точку этого многоугольника, в которой целевая функция принимает наименьшее значение. Пусть определено начальное допустимое базисное решение задачи, соответствующее угловой точке B. При полном переборе всех допустимых базисных решений придется исследовать восемь таких решений, соответствующих восьми угловым точкам многоугольника. Однако из рисунка видно, что, учитывая направление градиента , выгоднее перейти к соседней вершине C, затем к соседней вершине D, которой соответствует оптимальное базисное решение задачи. Таким образом, вместо восьми решений придется перебрать только три допустимых базисных решения.

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

Геометрический смысл симплекс–метода состоит в том, что выполняется последовательный переход от одной вершины многогранника допустимых решений задачи к соседней, в которой целевая функция принимает значение не худшее, чем в предыдущей вершине. Этот переход продолжается до тех пор, пока не будет найдено оптимальное решение или не будет обнаружено, что задача его не имеет.

Впервые симплекс–метод и его название были предложены американским математиком Джоном Данцигом в 1947 году, хотя идеи метода были опубликованы российским математиком Л.В. Канторовичем еще в 1939 году в статье «Математические методы организации и планирования производства».

Симплекс–метод состоит из трех основных элементов:

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

 правила перехода к следующему не худшему допустимому базисному решению;

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

Симплекс–метод применяется к задаче линейного программирования, записанной в канонической форме.

2. Симплексные преобразования системы линейных уравнений

Рассмотрим ЗЛП в канонической форме.

Пусть задана система линейных уравнений:

Нужно найти неотрицательное решение этой системы, которое минимизирует линейную функцию .

Обозначим – матрицу системы уравнений (1),

– расширенную матрицу этой системы.

Будем рассматривать случай, когда ранги матриц A и B равны: , т.е. когда система (1) имеет бесконечное множество решений. Наша задача заключается в том, чтобы выяснить, есть ли в этом случае оптимальные решения задачи и как найти одно из них.

Для определенности предположим, что линейно независимыми являются первые r столбцов матрицы A, тогда систему (1) можно, применяя метод исключения Гаусса, преобразовать к виду:

(3)

Эта система равносильна системе уравнений (1). Столбцы коэффициентов

, , …, образуют базис системы столбцов матрицы системы (2) и поэтому переменные являются базисными, а набор – базисным набором. Для краткости базисный набор переменных также будем называть базисом, имея в виду соответствующий базис столбцов коэффициентов. Остальные переменные являются свободными.

Выразим в системе (3) базисные переменные через свободные, получим систему (4):

(4)

Принято говорить, что (4) – общее решение системы уравнений (1). Придавая свободным переменным нулевые значения, определим значения базисных переменных и построим базисное решение, соответствующее построенному базисному набору переменных.

Итак, базисное решение системы (1).

В дальнейшем будет показано, что, если система (1) имеет допустимые решения, то ее можно так преобразовать к виду (3), что будет выполняться условие (5) .

Поэтому мы будем считать, что условие (5) выполняется. Тогда базисное решение является допустимым базисным решением.

Используя равенства (4), можно функцию f выразить через свободные переменные: (6) . Теперь можно вычислить значение функции , соответствующее базисному решению : .

Осуществляя идею симплекс–метода, научимся переходить от одного допустимого базисного решения к другому. Для этого одна из базисных переменных удаляется из базиса и заменяется некоторой свободной переменной . При этом изменении базиса система уравнений (4) и линейная функция (6) преобразуются. Для этого i-ое уравнений системы (4) нужно разрешить относительно . Получится уравнение (7):

Подставив вместо его выражение из (7) в остальные уравнения системы (4) и в функцию (6), мы получим новую систему, равносильную системе (1), которая будет разрешена относительно нового базиса .

Указанные преобразования системы (4) удобно выполнять с помощью специальной «симплекс–таблицы». Системе (4) и равенству (6) соответствует симплекс–таблица:

Переменные Базис		…		…			…		…		Свободные члены
	1	…	0	…	0		…		…
…	…	…	…	…	…	…	…	…	…	…	…
	0	…	1	…	0		…		…
…	…	…	…	…	…	…	…	…	…	…	…
	0	…	0	…	1		…		…
f	0	…	0	…	0		…		…

Коэффициент , указывающий, что в базисе происходит замена на свободную переменную , называют разрешающим элементом симплекс-таблицы. Из равенства (7) следует, что .

Так как новое базисное решение должно быть допустимым (неотрицательным), то должно выполняться условие , а значит, . Иначе говоря, разрешающий элемент (– свободная переменная) в j–том столбце надо выбирать положительным. Описанное преобразование назовем симплексным, если разрешающий элемент выбирается по следующему правилу:

1. Элемент выберем из такого j – ого столбца, в котором есть положительные элементы.

2. Если в этом столбце есть несколько положительных элементов, то составим отношения свободных членов к коэффициентам . Из всех отношений выберем наименьшее. Пусть это будет

(8) ;

Знаменатель этой дроби и выберем разрешающим элементом. Если несколько из этих отношений будут минимальными (равными), то выберем любой из знаменателей этих отношений.

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

Доказательство. Обозначим новые свободные члены после симплексного преобразования в (4) через

Тогда при .

Если , то из (8) следует, что .

Если , .

Если , то .

Следствие. С помощью симплексного преобразования можно перейти от одного допустимого базисного решения ЗЛП к другому допустимому базисному решению этой задачи.