Теория игр. Оуэн (1971) (1186151), страница 14
Текст из файла (страница 14)
Х 1 Гм Ш. Ланеаное программированне 88 Рассмотрим теперь задачу максимизации (3.2.1) — (3,2.3), представленную строками схемы (3.4.5), Мы имеем систему и + 1 уравнений с лч + л + 1 неизвестными хь ..., х, иь ..., ип и гв. Можно, вообще говоря, выразить л + 1 этих неизвестных через остальные гл неизвестных, Схема, конечно, дает представление для иь ., ин и в через хь но, кроме вырожденных случаев, когда мы сталкиваемся с обращением вырожденной матрицы, можно выразить любые л + 1 неизвестных через остальные гл. Предположим, что мы уже выразили л + 1 переменных зь зг, ..., зн, ео через переменные гь гг, ..., г и получили новую схему (симплекс-таблицу) г, га ... г 1 — Ь' — Ь' 2 = — $, а (3.4.6) — Ь' и где каждый элемент нижней строки (кроме, может быть, стоящего справа элемента 6) н каждый элемент крайнего правого столбца (снова кроме нижнего элемента) неположительны.
Если это так, то таблица (3.4.6) дает решение задачи (3.2.1) — (3.2.3). Действительно, если мы положим все переменные гь ..., г равными' нулю, то каждая из переменных з; будет равна соответствующему Ьь Но величины — Ь; неположительны. Следовательно, все з; будут неотрицательными. Так как все г; равны нулю, эта точка принадлежит допустимому множеству для задачи (3.2,!) — (3.2.3). Кроме того, нижняя строка дает уравнение в=с,'г,+ ... +с„'г +Ь, где все с,' неположительны. Ясно, что наибольшее возможное значение для ш получится, если положить все ге равными нулю (так как меньше они быть не могут). Таким образом, решение задачи (3.2 1) — (3.2.3) получается из (3.4 6», если положить г,=О, 1=1, ...„т, (3.4,7) з, = Ь;, 1 = 1, ", и, (3.4.8) ш=б. (3.4.9) Мы ищем метод, который позволит переписать систему (3.4.5) в виде (3.4.6) с неположительными элементами в правом столбце 1Н.
4. Алгорифм симплекс-метода 69 н в нижней строке (кроме, быть может, правого нижнего элемента б). Дадим сначала некоторые определения. !Н.4.1. Оп редел ение. В симплекс-таблице (схеме) (3.4.6) переменные з; называются базиснвгми переменными„а переменные т, — небазисными переменными. Ш.4.2. Определение. Симплекс-таблица будет также называться базисной точкой, Если все элементы в правом столбце (кроме, быть может, нижнего элемента) неположительны, она будет называться базисной допустимой точкой. Если все элементы нижней строки (кроме, быть может, крайнего правого элемента) неположительны, она будет называться базисной двойственно допустимой точкои" Как уже отмечалось, если элементы правого столбца неположительны,мы получаем точку в допустимом множестве для задачи (3.2.1) — (3.2.3), полагая небазисные переменные равными нулю.
Именно это и понимается под базисной допустимой точкой. Если все элементы нижней строки неположительны, то мы получаем точку в допустимом множестве двойственной задачи (3.2.4)— (3,2.6), Это базисная двойственно допустимая точка. Наконец, если базисная допустимая точка есть также и базисная двойственно допустимая точка, то, как было отмечено выше, она является решением задачи. С геометрической точки зрения базисная допустимая точка представляет некоторую вершину выпуклого многогранника, являющегося допустимым множеством для задачи (3.2.1) — (3.2.3). Как пояснялось выше, нужно рассматривать далее те ребра, которые проходят через эту вершину, или, что равносильно, те вершины, которые лежат на других концах этих ребер. Вершина получается, если положить пг переменных (небазисных) равными нулю; ребро получается, если положить тп — 1 этих переменных равными нулю.
Ребро проходит через вершину, если эти т — 1 переменных находятся среди тех т, которые соответствуют вершине. Значит, две вершины лежат па одном ребре, если они имеют общими и — 1 своих небазисных переменных. Это приводит к следующему определению. П1.4.3. О и р е д е л е н и е. Две базисные точки называются смежными, если они представляют различные точки в пространстве и их множества базисных переменных различаются не более чем одним элементом, Следует заметить, что две симплекс-таблицы могут представлять одну и ту же точку даже в том случае, когда их базисные переменные различны.
Действительно, ничто не мешает элементам правого столбца быть равными нулю. Если какое-то Ьг равно нулю, то соответствующее зг будет нулем, когда небазисные переменные Гл, 7!!. Линейное нролроммооовоние 70 будут нулевыми. Значит, можно поместить его среди небазисных переменных без изменения точки, представленной таблицей. 111.4.4. Ведущие преобр азов а ни я.
Ведущее преобразование есть операция изменения множества базисных переменных на один элемент; иначе говоря, это операция решения т + 1 уравнений из (3.4.6) относительно п — 1 переменных гя одной из переменных т; и переменной иь; эти переменные выражаются через оставшиеся тп переменных. Покажем, как это делается. Пусть мы хотим сделать э; небазисной переменной, а т; — базисной переменной.
Решаем уравнение аыт,+аз!Гэ+ ... +а 1т — Ь1= — в! ( - — ) (- —,)-— ! о1-ь. ! ! ои ап — — 71т, + ... +~а. ь,1 — ' 71ть, — — э!+ ... о, ! ' ' ' ~ ' о! ! о ... -(ь,—,')- —,;, И аналогично изменятся и другие уравнения (кроме, конечно, !иго). Чтобы получить новую таблицу, мы просто пересчитываем коэффициенты и меняем местами переменные т, и эь Элемент аи, который не может быть нулевым, называется ведущим элементом преобразования. Само преобразование называется ведущим преобразованием. Это преобразование можно коротко изобразить соответствующей диаграммой: 1 Р Р Р Р (3.4.10) Здесь р представляет ведущий элемент, а — любой другой элемент ведущей строки, т — любой другой элемент ведущего столбца, а э — элемент из строки, соответствующей т, и столбца, соответствующего ь7, Таким образом, ведущий элемент заменяется на обратный ему элемент !!р.
Остальные элементы ведущей строки просто делятся на р, а остальные элементы ведущего столбца делятся относительно — т;: о! аь ь! 1 о о ть+ ° ° ° + ' тьь+ — э!+ ... + — т и "! 'ь! ь! ь! (предполагаем, конечно, что ап чь0).
Это новое уравнение будет 1-й строкой преобразованной симплекс-таблицы. Для того чтобы получить остальные строки, нужно подставить в них это выражение для то Тогда (предполагаем, что ! Ф 1) первое уравнение будет иметь вид П1. 4. Алгорифм сималекс-метода на р и меняют знак. Наконец, остальные элементы таблицы уменьшаются на произведение элементов той же строки и ведущего столбца, и того же столбца и ведущей строки, деленное на р. И!.4.5.
П р и м е р. Пусть дана симплекс-таблица тт гг 4 1 3 2 — 1'. 2 — 1 4 1 2 2 О О 1 4 1 — зь — зт, — зг, 3 . 4' (3.4.11) 4 9 — 1 18 — 1 — 2 1 — 4 1 4 1 4 О 1 4 1 3, ! — т„ — Яг, — 3 . г (3.4.12) Можно проверить, что система уравнений (3.4.12) равносильна системе (3.4.11). Ш.4.6. Двойственна я зада ч а. В Ш.4,4 была определена форма преобразования, которое нужно произвести иад симплекс- таблицей для того, чтобы система уравнений, представляемая строками новой таблицы, была равносильна системе, представляемой старой таблицей.
С другой стороны, мы говорили выше, что таблица может быть использована для представления пары двойственных задач одновременно. Остается проверить тогда,что уравнения, представляемые столбцами этой таблицы, также будут равносильны старой системе. Столбец ! таблицы (3.4.5) представляет линейное уравнение ~т.) аПУ1 — с, = оп Здесь, конечно, о; являются базисными переменными, а уз — неба. знсными. Пусть мы хотим менять ролями о; и уь т. е. мы хотим Она представляет систему уравнений, разрешеннуюотносительноэь эг, зг, зь которые выражены через т„гм г„а мы хотим решить эту систему относительно зь ть з,, зг и выразить их через зг, ть гг.
Велущим будет тогда отмеченный звездочкой элемент, который расположен ниже гг и левее зь Выполняя преобразование, описанное в (3.4.10), и меняя положения т~ и эв получаем таблицу тг Гм ПА Линейное ирогроммировиние ! Р Р г 8— Р Р ["~-[ Но это в точности схема (3.4.10). Таким образом, преобразование, которое сохраняет прямую задачу (3,2.1) — (3.2.3), будет сохранять и двойственную задачу (3.2.4) — (3.2.6). Иначе говоря, любая симплекс-таблица, полученная при помощи ведущих преобразований, будет представлять пару двойственных задач одновременно. И1.
5. АЛГОРИФМ СИМПЛЕКС-МЕТОДА (ПРОДОЛЖЕНИЕ) Мы дали описание основного ведущего преобразования, которое является главным орудием симплекс-метода. Теперь нужно установить, как пользоваться этим орудием, В самом деле, симплекс-таблица будет, вообще говоря, иметь много ненулевых элементов, которые могут быть использованы в качестве ведущих; необходимо правило, указывающее, какой из них следует брать. Обращаясь к геометрической модели, мы замечаем, что каждую из т + л переменных хь ..., х, иь ..., и„можно считать представляющей граничную гиперплоскость допустимого множества, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
