Теория игр. Оуэн (1971) (1186151), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

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

Затем, имея базисную допустимую точку, мы должны стараться улучшить (увеличить или уменьшить) целевую функцию, придерживаясь все время базисных допустимых сделать у! базисной переменной, а о; небазисной. Как и выше, выражаем из этого уравнения у; через о! и остальные у! и получаем ип е У! — ° ° ° Уг-!+ ог+ ° ° + и =У! Ц Ц Ц г! Подставим это значение для у! в остальные уравнения; тогда для первого столбца получим (предполагая, конечно, !Ф 1) ) ици!!~ иц ! Сеи,! 1 ап — — !! у!+ ...

+ —, о,+ ... — ~с, — !1=о,; ц ц ц для остальных столбцов получаются аналогичные результаты. Если представить эти преобразования схематически, как в (3.4.10), то получаем диаграмму !!!. б. Алгорифм симплекс-метода (продоласеиие) точек, пока не будет достигнуто решение (т. е. такая точка, что дальнейшее улучшение невозможно). Мы дадим, таким образом, два набора правил: первый (без всяких априорных предположений) будет давать базисную допустимую точку; второй (в предположении, что мы начинаем с базисной допустимой точки) будет давать решение. Назовем их соответственно случаем ! и случаем П. 1П.51. Правила выбора ведущего элемента.

(3.5.1) Случай 1. Пусть — Ьи есть наименьший положительный элемент в правом столбце (кроме, может быть, нижнего). Возьмем произвольный отрицательный элемент а,и в й-й строке. Ведущий элемент будет в !о-м столбце. Далее, для всех ! ~ й, для которых — Ь!/а! отрицательно, пусть /о есть то значение /, для которого это отношение наибольшее (т. е. ближе всего к нулю). Тогда а, ! будет искомым ведущим элементом. (Если имеется ! !в равенство, то может быть выбран любой из тех элементов, которые дают максимум.) (3.5.2) Случай П.

Пустьс, — любой положительный элемент нижней строки (снова исключая, быть может, крайний правый элемент). Ведущий элемент будет в !о-м столбце. Для всех !, для которых — Ь (а!! отрицательно, пусть !о есть то значение /, для которого это отпйошение наибольшее (т. е, ближайшее к нулю). Тогда а, будет искомым ведущим элементом. (В случае равенства снова можно выбирать любой из соответствующихэлементов.) П1.52.

Дока з а тельство сходи м о ст и. Теперь докажем, что указанный алгорифм действительно сходится через конечное число шагов. Сделаем предположение о невырожденности, т. е. о том, что ни нижняя строка, ни правый столбец не содержат нулей (снова за исключением правого нижнего элемента). (3.5.3) В случае 1 мы докажем, что все элементы правого столбца ниже й-го элемента остаются отрицательными, а й-й элемент уменьшается. Мы знаем, что для каждого !Ф!о элемент — Ь/ будет заменен на а! /ь! — Ь' — Ь + а!вв Мы также знаем, что — Ь (а!! отрицательно.

Следовательно, если а <О, то, очевидно, — Ь'< — Ь. !,/ ! /' Если, с другой стороны, а!/>О, то мы знаем (согласно нашему !в/ правилу), что для / =' й будет ьп ь, в а- — а и!» !,! Гд !П. Линейное программирование Тогда Член в скобках будет неположительным. Следовательно, — Ь'<О. Наконец заметим, что — Ьу, будет заменено на — Ьь/аг,г„которое, по предположению, отрицательно. Следовательно, для 1 ) Ь имеем Ь! < О. Кроме того, — Ье < — Ьь Существует только конечное число возможных симплекс-таблиц, и поэтому если продолжать определять ведущие элементы согласно указанному правилу„то в конце концов будет получена таблица, в которой — Ь; < О для каждого 1' '= Ь. Тогда преобразуем предыдущую (сверху) строку и т.

д., пока все элементы правого столбца не станут неположительными. (3.5.4) В с,чучае Н на тех же основаниях, что и выше, каждое l Р— Ь! будет заменено на — Ь!, где — Ь! ~ О. Нижний правый элемент 6 будет заменен на Ь 6 =6+ — ' У е! !г а! Мы знаем, что с, )О, а — Ь,(а! <О. Следовательно, 6') 6. Далее 6 и 6' являются значениями целевой функции в двух данных базисных допустимых точках. Значит, целевая функция возрастает. Так как имеется только конечное число базисных допустимых точек, мы в конце концов достигнем решения. Таким образом, мы получаем, что (при предположении о невырожденности) если можно продолжать находить ведущие элементы согласно правилам из Ш.5.1, то алгорифм симплекс-метода даст решение задачи линейного программирования через конечное число шагов.

Однако может случиться, что наборы правил (3.5.1) и (3.5.2) осуществить не удастся. Здесь могли бы не пройти два пункта. В случае 1 может оказаться, что все элементы строки, кончающейся положительным элементом, неотрицательны. В случае П может оказаться, что в столбце, имеющем положительный нижнин элемент, все остальные элементы неположительны. В обоих случаях невозможно следовать правилам 111.5.1. Мы увидим ниже, что в такой ситуации задача неразрешима (либо по причине недопустимости, либо по причине неограниченности).

Итак предположим, что в случае 1 все элементы строки, кончающейся положительным элементом, неотрицательны. Эта строка представляет уравнение ~~'.~ п,гг, — Ь! = — з!. (3.5.5) ! 1 Тогда все ап и гь по предположению, неотрицательны, а — Ьэ положительно. Но это означает, что з! должно быть отрицательно !!!. Б, Алгорифм симолекс-метода (ородолесение) 75 Следовательно, ограничения несовместны, т. е. задача является не- допустимой. В случае П предположим, что в столбце с положительным ниж- ним элементом остальные элементы неположительны.

Тогда, если коэффициент ам неположнтелен, из уравнения (3.5.5) следует„что т; может неограниченно возрастать без убывания зр Так как все элементы данного столбца (кроме нижнего элемента) неположи- тельны, отсюда следует, что мы можем неограниченно увеличивать ть оставляя все остальные тр равными нулю и сохраняя их в до- пустимом множестве. Но так как нижний элемент указанного столбца положителен, это будет неограниченно увеличивать целе- вую функцию. Следовательно, задача неограниченна. ! ! !.5.3. В ы р о ж д е н н о с т ь. В предыдущих рассуждениях было сделано явное предположение о невырожденности: мы пред- полагали, что нули никогда не появляются в правом столбце (кроме, быть может, нижнего элемента).

Если же нули появятся, то ясно, что некоторые строгие неравенства, которые приводились выше, должны быть заменены нестрогими неравенствами. Напри- мер, неравенство 6') 6, которое характеризует ведущие преобра- зования в случае П в предположении невырожденности, должно быть заменено на более слабое 6' ~ 6. Но 6') 6 означает, что це- левая функция возрастает при каждом преобразовании, откуда следует, что мы не можем проходить дважды через одну и ту же базисную допустимую точку, Это гарантирует окончание процесса. Более слабое неравенство 6' ) 6 допускает возможность, что мы выполним ведущие преобразования несколько раз и после всех этих шагов снова получим ту же самую таблицу. Вырожденность задачи, характеризуемая появлением нулей в правом столбце, возникает тогда, когда более чем пт переменных одновременно обращается в нуль, т.

е. когда более чем т гипер- плоскостей, ограничивающих допустимое множество, проходят че- рез одну точку. Таким образом, невырожденность будет иметь ме- сто, если еп + п ограничивающих гиперплоскостей находятся в об- щем положении в пространстве. Но это означает, что в вырожден- ной задаче произвольно малое возмущение ограничений устранит вырожденность. Обычно для борьбы с вырожденностью используется метод воз- мущения. Если одна из строк заканчивается нулем, т.

е. если она имеет вид )а! ае! ... а ! О!= — з!, то мы заменяем переменную з; на переменную е'=з +е и полу! ! чаем строку )а а ... а — е)= — е', ! и е! '',! )= где е предполагается положительным, но очень малым. Далее ре- шаем модифицированную задачу симплекс-методом. Поскольку Гл. 1П. Линейное программирование Чз такие возмУЩениЯ УстРанЯют всЯкУю выРожденностен задача, измененная конечным числом возмущений, будет этим способом решена (если она имеет решение). Решение будет функцией наборавозмущений, т.

е. значения переменных хь ..., х будут зависеть от частных значений, которые получают е, введенные при этих возмущениях. Однако, вообще говоря, значения переменных линейно зависят от этих е; остается просто положить все е равными нулю, получая тем самым решение исходной задачи (без возмущений). На самом деле возмущения, которые заменяют ограничения з; ~ 0 более слабыми ограничениями з1)0, имеют тенденцию увеличивать допустимое множество. Нас интересуют крайние точки допустимого множества; ясно, что при таком возмущении меняются только те из них, для которых зг = О.

Характеристики

Список файлов книги