Чернов В.П. Математические модели и методы в экономике и менеджменте

Подождите немного. Документ загружается.

одна из базисных переменных выйдет из их набора, станет в результате

преобразования небазисной, и ровно одна из небазисных переменных

войдет вместо нее в базисный набор.

Геометрический смысл такого преобразования состоит в переходе

от одной вершины многогранной области допустимых планов к другой,

соседней вершине. Преобразование осуществляется таким образом,

чтобы для нового текущего опорного плана, то есть для новой вершины

области, значение целевой функции было больше (или, во всяком слу-

чае, не меньше), чем для предыдущего текущего опорного плана.

Само преобразование осуществляется методом Гаусса. Он преоб-

разует систему уравнений в равносильную систему. Смысл задачи при

таком преобразовании полностью сохраняется, изменяется лишь форма

записи системы ограничений и в полном соответствии с этим – содер-

жимое симплексной таблицы.

Опишем последовательность, в которой осуществляется преобра-

зование таблицы.

Разрешающий столбец

Сначала следует выбрать отрицательную величину среди



(если

таких несколько, то можно выбрать любую из них). Пусть индекс вы-

бранной величины есть q, то есть 0





. Соответствующему столбцу

таблицы, то есть столбцу коэффициентов при переменной x

, присваи-

вается название разрешающего столбца.

Отметим, что переменная x

, является небазисной. Если бы она

была базисной, то 

было бы равно 0.

В новой таблице, которая возникнет в результате преобразований,

переменная x

окажется в числе базисных переменных.

Разрешающий элемент

Среди элементов a

разрешающего столбца следует определить

разрешающий элемент. Для этого необходимо рассмотреть положи-

тельные величины среди a

. Для каждой из таких положительных ве-

личин следует рассмотреть отношение соответствующего элемента

столбца «В» к данной величине. Среди отношений нужно выбрать

наименьшее. Тот элемент a

разрешающего столбца, для которого от-

ношение оказалось наименьшим, и является разрешающим элементом.

Другими словами, разрешающий элемент – это тот положительный

элемент a

разрешающего столбца, для которого выполняется условие

a 0

pq iq

min .

a a





В том случае, если в данном разрешающем столбце наименьшее

отношение возникает для нескольких его элементов (в этом случае та-

кие наименьшие отношения, разумеется, равны друг другу), в качестве

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

Критерий неограниченности целевой функции

В том случае, если в разрешающем столбце среди его элементов

вообще нет положительных, разрешающий элемент не может быть оп-

ределен. Такая ситуация говорит о том, что целевая функция задачи

неограниченна. Для любого допустимого плана в этом случае сущест-

вует другой допустимый план с более высоким значением целевой

функции. Любой план может быть улучшен, самого лучшего, опти-

мального плана не существует. Продолжать его поиск не имеет смысла.

Процесс решения задачи на этом заканчивается.

Таким образом, мы получили еще один признак конца процедуры

решения задачи. Он состоит в том, что для некоторого столбца таблицы

критерий оптимальности нарушен и при этом среди элементов столбца

нет положительных, то есть



< 0; a

 0;

(i 1,m)

 .

Этот признак называется критерием неограниченности целевой

функции.

Разрешающая строка

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

положительные элементы. Та строка, в которой находится разрешаю-

щий элемент, получает название разрешающей строки. Первый индекс

выбранного разрешающего элемента a

указывает, что он находится в

строке с номером р. Это означает, что строка с этим номером является

разрешающей. Та базисная переменная, которая указана на пересече-

нии разрешающей строки и столбца «Х

», в результате преобразования

таблицы окажется небазисной. Именно вместо нее небазисная пере-

менная x

войдет в базисный набор.

Преобразование левой части таблицы

В таблице ее левая и правая часть преобразуются по отдельным

правилам. В левую часть входят первые три столбца таблицы. В пра-

вую часть входят все остальные столбцы (начиная со столбца «В»).

В левой части таблицы содержимое столбца «№» при преобразова-

нии сохраняется. В содержимом столбца «Х

» производится замена од-

ной из базисных переменных. Переменная, находящаяся в разрешаю-

щей строке, заменяется переменной, соответствующей разрешающему

столбцу. В столбце «С

», в полном соответствии с этим элемент, стоя-

щий в разрешающей строке, заменяется элементом, указанным вверху

таблицы над переменной разрешающего столбца.

Преобразование правой части таблицы

Правая часть таблицы преобразуется методом Гаусса. Процесс

преобразования состоит из нескольких шагов. На каждом шаге преоб-

разуется отдельная строка правой части таблицы. Число шагов равно

количеству строк.

Целью преобразования является превращение разрешающего

столбца в базисный столбец, то есть в такой, где на месте разрешающе-

го элемента стоит 1, а все остальные элементы равны 0.

Процедура начинается с преобразования разрешающей строки. На

первом шаге преобразования разрешающая строка делится на разре-

шающий элемент. В преобразованной строке на месте разрешающего

элемента оказывается 1.

Далее преобразование осуществляется отдельно с каждой строкой.

Для этого следует из преобразуемой строки вычесть преобразованную

разрешающую строку, умноженную предварительно на подходящее

число. Таким подходящим для каждой преобразуемой строки является

свое число. Оно находится на пересечении преобразуемой строки и

разрешающего столбца. В результате преобразования на месте этого

подходящего числа оказывается 0.

Формулы преобразования

Преобразование правой части таблицы можно описать в формуль-

ном виде. Отметим элементы преобразованной таблицы штрихом. На-

помним, что a

разрешающий элемент.

Тогда для разрешающей строки

pj p

pq pq

a b

a , b .

a a

 

 

Для произвольной i-й строки, кроме разрешающей (i  р) и крите-

риальной, выполняются равенства

ij ij pj iq i i p iq

a a a a ; b b b a .

   

   

Для критериальной строки

j j pj q p q

a ; d d b .

   

       

Легко проверить, что в соответствии с этими формулами элементы

разрешающего столбца преобразуются в элементы базисного столбца:

a 1;



 

iq iq pq iq

a a a a 0;

 

  

q q pq q

a 0.

 

     

Допустимость текущего опорного плана

Допустимый план удовлетворяет всем ограничениям системы. В

частности, его компоненты не могут быть отрицательными. Убедимся,

что начальный и все последующие текущие опорные планы содержат

только неотрицательные компоненты.

В текущем опорном плане небазисные компоненты равны 0, тем

самым они неотрицательны. Базисные компоненты равны элементам

столбца «В» во всех строках, кроме критериальной. Они тоже должны

быть неотрицательными.

Их неотрицательность в первоначальной таблице обеспечивается

предварительной подготовкой модели. Их неотрицательность в преоб-

разованной таблице вытекает из формулы преобразования.

Действительно, для разрешающей строки выполняется равенство

b .





По условию b

 0. Поскольку a

– разрешающий элемент, то a



0. Отсюда следует, что b

 0.

Для остальных строк таблицы

i i p iq

b b b a .

 

 

По условию b

 0. Только что было доказано, что b

 0. Если a

 0,

то из формулы сразу следует, что b

 0.

Рассмотрим противоположный случай, когда a

 0. Доказываемое

утверждение b

 0 равносильно неравенству

i p iq

b b a 0,

 

 

которое, в свою очередь, равносильно

i iq

b a 0,

 

то есть

i iq

b a .



Поскольку по предположению a

 0, то можно разделить обе час-

ти последнего неравенства на эту величину, сохранив его смысл:

iq pq

a a



Последнее неравенство верно. Его справедливость следует непо-

средственно из правила выбора разрешающего элемента по наимень-

шему отношению.

Таким образом, мы доказали, что при преобразовании симплекс-

ной таблицы элементы столбца «В» во всех строках, кроме критери-

альной, остаются неотрицательными (хотя сами их численные значе-

ния, конечно, изменяются).

Именно благодаря этому новый текущий план оказывается допус-

тимым. Свойство симплексной таблицы, состоящее в том, что все эле-

менты столбца свободных членов – столбца «В» таблицы неотрица-

тельны (кроме, быть может, критериального), называют свойством до-

пустимости таблицы.

Мы доказали, что при преобразовании таблицы ее допустимость

сохранится.

Заметим, что обычно элементы столбца «В» (кроме, возможно,

критериального) не просто неотрицательны, а строго положительны.

Случай, когда такой элемент равен 0, возможен, но встречается доста-

точно редко.

Рост значения целевой функции

Новой симплексной таблице соответствует новый текущий опор-

ный план. Этому плану соответствует новое значение целевой функ-

ции. Оно вычисляется по формуле:

p q

d d b .

 

  

Как мы выяснили ранее, b

 0. Кроме того, по определению раз-

решающего столбца имеем:

q < 0.

Поэтому во всех случаях d  d, новое значение целевой функции

не меньше предыдущего. Равенство возникает d = d только при b

= 0.

Обычно b

 0. Случай, когда b

= 0, встречается крайне редко.

Поэтому при переходе к новому опорному плану значение целевой

функции всегда не убывает, и в типичной ситуации оно строго возрас-

тает.

Алгоритм симплекс-метода

Блок-схема алгоритма симплекс-метода

Новый текущий опорный план, соответствующий новой симплекс-

ной таблице, следует проверить на оптимальность. Если он удовлетво-

ряет критерию оптимальности, то решение задачи окончено. Если нет,

то решение задачи следует продолжить. В таблице следует выбрать

разрешающий столбец, в нем найти разрешающий элемент, определить

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

Так следует продолжать до тех пор, пока последовательность пре-

образований таблицы не прервется. Прерваться же она может только в

одном их двух случаев.

Во-первых, если очередная таблица окажется удовлетворяющей

критерию оптимальности (отсутствует разрешающий столбец). Тогда

соответствующий ей текущий опорный план является оптимальным,

задача решена.

Во-вторых, если очередная таблица окажется удовлетворяющей

критерию неограниченности целевой функции (в разрешающем столб-

це отсутствует разрешающий элемент). Тогда задача не имеет решения.

Процесс решения задачи на этом заканчивается.

Последовательность преобразований таблиц и сопровождающих

их рассуждений образует алгоритм симплекс-метода. Он может быть

представлен в виде блок-схемы (рис. 1.10).

Предварительная

подготовка модели

Заполнение ис-

ходной симплекс-

ной таблицы

Выполнен ли

критерий оп-

тимальности?

нет

да Задача решена.

Текущий

опорный план

является

оптимальным

Выбор разрешаю-

щего столбца

Выполнен ли

критерий неог-

раниченности

целевой

функции?

да

Задача реше-

ния не имеет.

Целевая

функция

неограниченна

нет

Определение

разрешающего

элемента

Определение раз-

решающей строки

Преобразование

симплексной

таблицы

Рис. 1.10. Блок-схема алгоритма симплекс-метода

Рассуждения, участвующие в реализации этого алгоритма, носят

чисто формальный характер, сводятся к проверке определенных нера-

венств и расчетам по известным формулам. Такой алгоритм без труда

может быть запрограммирован. Это является большим преимуществом

симплекс-метода, поскольку реальные экономические задачи требуют

преобразования таблиц большой размерности, практически не под-

дающихся ручной обработке. В настоящее время разработаны разнооб-

разные компьютерные программы, позволяющие использовать совре-

менную вычислительную технику при решении и анализе задач линей-

ного программирования. Одна из таких удобных программ сформиро-

вана в виде процедуры «Поиск решения» в Excel.

Сходимость алгоритма симплекс-метода

В блок-схеме алгоритма симплекс-метода имеется цикл. Каждое

прохождение по циклу соответствует переходу от одной симплексной

таблицы к другой, от одного текущего опорного плана к следующему.

В схеме указаны четкие критерии выхода из цикла, критерии кон-

ца процесса решения задачи. Однако всегда ли произойдет такой вы-

ход? Не окажется ли, что в процессе решения задачи так и придется

пересчитывать симплексные таблицы до бесконечности?

Теорема о сходимости симплекс-метода утверждает, что можно

этого не опасаться. Через конечное число прохождения цикла процесс

решения задачи прекратится.

Обоснование сходимости основано на следующем рассуждении.

Каждой симплексной таблице соответствует свой базисный набор пе-

ременных. В задаче участвует конечное число (n) переменных. В ба-

зисном наборе участвует конечное число (m) этих же переменных.

Следовательно, количество всевозможных базисных наборов конечно.

Каждой симплексной таблице с ее базисным набором соответству-

ет свой текущий опорный план. Таким образом, число текущих опор-

ных планов конечно.

При прохождении по циклу блок-схемы осуществляется переход от

одного текущего опорного плана к другому. Каждому плану соответст-

вует свое значение целевой функции.

Как мы убедились, это значение при переходе от одного плана к

другому сохраняется или возрастает. Обычно же оно растет.

Если оно возрастает, то текущие опорные планы не могут повто-

ряться. Каждый раз при преобразовании таблицы будет возникать но-

вый план, не встречавшийся ранее.

Поскольку количество таких планов конечно, то процесс решения

задачи рано или поздно прекратится. Прекратиться же он может лишь

в одном из двух случаев, указанных в блок-схеме.

Если же значение целевой функции сохраняется, то в принципе

оказывается возможным повторение текущих опорных планов и зацик-

ливание процесса решения задачи. Однако разработан и обоснован

специальный прием, позволяющий обнаруживать такое зацикливание и

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

что процесс решения задачи прекращается через конечное число про-

хождений цикла, конечное число преобразований симплексных таблиц.

Теоретически сходимость алгоритма с помощью специального

приема выхода из цикла обеспечена безусловно. В практике програм-

мирования этим специальным приемом обычно не пользуются, по-

скольку он загромождает алгоритм, а практический эффект от него

весьма мал. Натолкнуться на задачу с зацикливанием практически не-

вероятно.

Метод искусственного базиса

Симплекс-метод можно непосредственно применять в тех ситуа-

циях, когда исходная модель после приведения к канонической форме

и установления неотрицательных значений правых частей ограничений

обладает базисным набором переменных. Если такой набор отсутству-

ет, то в модель вводят так называемые искусственные базисные пере-

менные и используют один из методов искусственного базиса. Наибо-

лее распространенным среди них является М-метод.

Пусть дана задача линейного программирования в канонической

форме:

1 1 2 2 n n

11 1 12 2 1n n 1

21 1 22 2 2n n 2

m1 1 m2 2 mn n m

1 2 n

max (c x c x c x )

a x a x ... a x b ,

x 0, x 0, x 0.

 

   





   







   



  











Предположим, что все правые части ограничений неотрицательны:

 0.