2.3. Теоретические основы симплексного метода

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

Пусть стоит задача максимизации  при условиях 

X_j  0 ( j = 1 ... n ) (3)

Предположим, что нам удалось найти опорный план X⁰, в котором, например, первые m компонент отличны от нуля:  и соответствующий базис Б=(A₁,A₂,…,A_m).

Попытаемся выбрать другую систему базисных векторов с целью построения нового опорного плана, в котором k-я переменная ( k > m ) принимает значение  > 0 :  Подставляя (4) в (2), имеем  Подставив (5) в (2), получаем 

Разложим вектор A_k по векторам исходного базиса  В общем случае для получения коэффициентов такого разложения придется решать систему m уравнений с m неизвестными, которая имеет единственное решение, поскольку базисные векторы линейно независимы и соответствующая матрица имеет ненулевой определитель. Заметим, что в ситуации, когда базисные векторы являются единичными (образуют единичную матрицу), искомые коэффициенты совпадают с компонентами исходного вектора; поэтому в дальнейшем мы будем питать любовь к единичному базису.

Подставляя (6) и (8) в (7), получаем  откуда имеем  Так как система уравнений (10) имеет единственное решение, то получаем представление первых m компонент нового плана 

Естественно потребовать неотрицательность компонент нового плана. Так как нарушение неотрицательности в (11) может возникнуть лишь при Z_jk>0, то значение нужно взять не превышающим наименьшего из отношений X⁰_j к положительным Z_jk.

Если к тому же учесть, что число положительных (базисных) компонент опорного плана должно оставаться равным m, то одну из первых m (ненулевых) компонент исходного плана обращаем в нуль выбором  Подставляя (11) в (1), имеем  Если обозначить  то (13) примет вид 

Из полученных соотношений напрашиваются следующие выводы.

Критерий 1 ( критерий оптимальности ). Если все _k0, то выбранный план для задачи максимизации является оптимальным. Для задачи на минимум признак оптимальности - неположительность всех _k.

Критерий 2. Если обнаруживается некоторое _k<0 и хотя бы одно из значений Z_jk>0, то переход к новому плану увеличит значение целевой функции.

Этот вывод с очевидностью следует из (16); в такой ситуации согласно (12) полагаем k-ю переменную равной и преобразуем значения остальных (базисных) переменных в соответствии с (11).

Критерий 3. Если обнаруживается некоторое k<0, но все Z_jk0, то линейная форма задачи не ограничена по максимуму неограниченность по минимуму устанавливается аналогично при k>0 и всех Z_jk0).

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

Предположение о том, что базисными являются первые m компонент плана, не является принципиальным, и указание диапазона по j от 1 до m в (11) - (15) можно заменить на указание о принадлежности к базису "jБ".

Если все опорные планы задачи являются невырожденными (число положительных компонент равно m), то  отлично от нуля и переход к новому плану согласно (16) изменяет значение целевой функции, что гарантирует достижение экстремума за конечное число шагов. При наличии вырожденных планов возможно т. н. зацикливание (возврат к ранее рассмотренным планам), но на практике зацикливание никогда не возникало.

№9 Свойства задач линейного программирования

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

(10.15)

при ограничениях

      АХ = В,  (10.16)

                                                                                  Х  0,  (10.17)

где

,  ,

Теорема 10.1. Множество всех планов задачи линейного программирования выпукло ( если оно не пусто).

Доказательство.

Пусть   и   – два допустимых плана задачи (10.15)-(10.17). Тогда  ,   и   ,  .

Рассмотрим выпуклую линейную комбинацию  ,  , и покажем, что Х также является планом задачи. Действительно,

,

 т.е. Х удовлетворяет (10.16). Но так как  ,  ,  ,  , то и  , т.е. удовлетворяет и условию (10.17).

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

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

Доказательство. Предположим, что многогранник решений является ограниченным, имеющим конечное число угловых точек. Обозначим его через К. В   К имеет вид многоугольника, изображенного на рисунке. Обозначим угловые точки К через  , , … ,  , а оптимальный план через  . Тогда   для всех Х из К. Если   - угловая точка, то первая часть теоремы доказана.

 

 

 

 

 

 

Рисунок 10.2.

Предположим, что   не является угловой точкой, тогда   можно представить как выпуклую линейную комбинацию угловых точек К, т.е.  ,  , .

Так как F(Х) – линейная функция, получаем

(10.18)

В этом разложении среди значений   выберем минимальное. Пусть оно соответствует угловой точке   и обозначим его через М, т.е.  . Заменим в (10.18) каждое значение   этим минимальным значением. Тогда, учитывая, что  ,  , получим

.

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

Для доказательства второй части теоремы допустим, что   принимает минимальное значение более чем в одной угловой точке, например в точках  , , … ,  ,  ; тогда  .

Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е.

,  , 

Так как   – линейная функция, получим

,

т.е. линейная функция F принимает минимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек  , , … ,  .

Теорема 10.3. Если система векторов   в разложении (10.14) линейно независима и такова, что

где все  , то точка   является  угловой точкой многогранника решений.

Теорема 10.4. Если   – угловая точка многогранника решений, то векторы  , соответствующие положительным    в разложении (10.14), линейно независимы.

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

№11 Симплексный метод решения ЗЛП. Геометрическая интерпретация симплексного метода