В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 7
Текст из файла (страница 7)
. , yj , . . . , xn . Поскольку в верхней строке (30) могутбыть лишь n элементов среди x1 , . . . , xn , y1 , . . . , ym , то учитывая, увеличение br при каждом шаге, мы через конечное числошагов мы добьемся того, что либо коэффициент br становится положительным, либо убедимся, что полиэдр ограниченийпуст. При этом по предложению 2.6 общее число положительных коэффициентов в последнем столбце на каждом шаге неуменьшается.Итак, совершая конечное число шагов вида 2 – 5 можнодобиться, чтобы либо все свободные коэффициенты стали быположительными, либо установили, что задача не имеет решения.Предположим теперь, что в матрице (30) все коэффициентыbi > 0.ВТОРОЙ ЭТАП – НАХОЖДЕНИЕ min z.ШАГ 6.Если все коэффициенты pi неотрицательны, то min z = q,так как x1 , .
. . , xn > 0.ШАГ 7.50В. А. АртамоновПусть ps < 0 для некоторого s. Если все коэффициенты s-го столбца a1s , . . . , ams матрицы (30) неотрицательны,sто луч (0, . . . , 0, t, 0, . . . , 0) ∈ P, для всех t > 0. При этомsz(0, . . . , 0, t, 0, . . . , 0) = tps + q принимает сколь угодно большие отрицательные значения. Следовательно, функция z неимеет минимума на P .ШАГ 8.Пусть ps < 0 для некоторого s и существует ars < 0.
Выбеbjбыло бы положительным ирем индекс j так, чтобы число − ajsминимальным. Переходим в шагу 5. Повторяя доказательствопредложения 2.6, получаем, что все bk остаются положительными. Кроме того, коэффициент при yj в z становится равнымpsajs > 0. Свободный член в z становится равнымq + ps (−bj) < q,ajsbjпоскольку ps < 0, − ajs> 0.Итак, совершив конечное число шагов, мы перейдем к вершине M , в которой функция z достигает минимума, либо выясним, что задача не имеет решения.3.
Двойственная задача линейного программированияРассмотрим задачу линейного программирования из определения 2.1, причем ограничения имеют вид (29). Обозначимчерез b – столбец t (b1 , . . . , bm ). Из предыдущих рассужденийвытекает, что без ограничения общности можно предполагать,что задача имеют видtpx → max,x > 0,Ax 6 b,(33)где A = (aij ) ∈ Mat(m × n, R).Определение 2.7. Двойственной задачей к задаче (33) называется задачаtby → min,tAy > p,y > 0.(34)Предложение 2.8. Двойственная задача к двойственнойзадаче совпадает с исходной задачей.Линейное программирование51Доказательство.
Вдвойственнойзадачеимеем(−A)y 6 −p, y > 0, причем необходимо найти max(− t by).Поэтому задача, двойственная к двойственной, имеет видt− t px → min, т. е. t px → max,(−A)x > −b, x > 0.¤Обозначим через P полиэдр, задаваемый неравенствами из(33), а через Q – полиэдр, задаваемый неравенствами из (34).Предложение 2.9. Пусть x ∈ P, y ∈ Q. Тогда t px 6 t by.В частности, maxx∈P (t px) 6 miny∈Q (t by).Доказательство. Пусть x ∈ P, y ∈ Q.
Тогдаtpx 6 t yAx 6 t yb = t by.Отсюда max(t px) 6 min(t by).¤Теорема 2.10. Пусть полиэдры P, Q непусты. Тогда существуют maxx∈P ( t px), miny∈Q ( t by) и они равны.Доказательство. Рассмотрим вAn+m = {(x, y) | x ∈ An , y ∈ Am }полиэдр M , задаваемый неравенствамиAx 6 b,tpx > t by,tAy > p,x ≥ 0, y > 0.Неравенства (35) можно записать в следующем видеµ ¶µ ¶A0bxx0 −t A −+ −p > 0,> 0.yytt−pb0(35)(36)Предположим сначала, что система неравенств (36) несовместна. По второму следствию из теоремы Фаркаша существуюттакие неотрицательные векторы c1 ∈ Rm , c2 ∈ Rn и неотрицательное число c3 , что µ t¶ c1A0 −p c2 = 0,0 −Abc352В. А. Артамонов c1( t b, − t p, 0) c2 < 0,c3илиtAc1 = pc3 ,Ac2 = bc3 ,tbc1 < t pc2 ,ci > 0.(37)Если с3 = 0, тоAc2 = t Ac1 = 0,tbc1 < t pc2 .(38)Пусть x0 ∈ P, y0 ∈ Q.
Тогдаtbc1 = t c1 b > t c1 Ax0 = t x0 t Ac1 = 0;tpc2 = t c2 p 6 t c2 t Ay0 = t y0 Ac2 = 0.Отсюда t pc2 6 0 6 t bc1 , что противоречит (38).Итак, c3 > 0. По (37)c2c1tA( ) = p, A( ) = b, t bc1 < t pc2 , ci > 0.c3c3В этом случаеc2c1c2c1∈ P,∈ Q, t p > t b ,c3c3c3c3что противоречит предложению 2.9.Таким образом, полиэдр M непуст. Пусть (x0 , y 0 ) ∈ M .этом случае x0 ∈ P, y 0 ∈ Q, причем t px0 > t by 0 . Отсюда t px0t 0by по предложение 2.9, и для любого x ∈ P получаем t pxt 0by = t px0 , т. е. maxx∈P t px = t px0 . Аналогично, miny∈Q t bytpx0 = maxx∈P t px.В=6=¤Отметим интерпретацию двойственной задачи в терминахсопряженных пространств. Пусть как и выше P – полиэдр, задаваемый неравенствами (33), а Q – полиэдр, задаваемый неравенствами (34).
В прямой задаче необходимо найти minx∈P (t px),а в двойственной — maxy∈Q (t by). Пусть A = (aij ) и O, e1 , . . . , en– выбранная система координат в An . Пусть V – векторноепространство с базой e1 , . . . , en и V ∗ – сопряженное простран∗ство. ОбозначимPn через li ∈ V , 1 6 i 6 m, линейные функции li (x) = j=1 aij xj .Тогда полиэдр P задается неравенствами l1 (x) 6 b1 , . . . , lm (x) 6 bm , x > 0. Рассмотрим конус KЛинейное программирование53c вершиной – нулевой функцией, порождаемый l1 , . . . , lm . Тогда Q можно отождествить с множеством всех таких линейныхфункций f ∈ V ∗ , что f (ei ) > pi , i = 1, . .
. , n.Установим связь между точками экстремума прямой идвойственной задач линейного программирования. СправедливаТеорема 2.11 (Теорема о равновесии). Пусть в точке x∗ ∈P достигается максимум t px, а в точке y ∗ ∈ Q – минимумфункции t by. Тогда yi∗ (ai1 x∗1 + · · · + ain x∗n − bi ) = 0, где bi – i-аякоордината b.Доказательство. Так как x∗ y ∗ > 0, и − t y ∗ A 6 − t p, то0 6 t y ∗ (b − Ax∗ ) = t y ∗ b − t y ∗ Ax∗ 6 t px∗ − t px∗ = 0.Следовательно, t y ∗ (b−Ax∗ ) = 0. Отсюда вытекает утверждение,поскольку b 6 Ax∗ , y ∗ > 0.¤Отметим, что если мы решаем прямую задачу линейного программирования, используя первый вариант симплексметода и сводя ограничения к системе линейных уравнений,то мы автоматически получаем точку экстремума двойственной задачи.
Действительно, пусть дана прямая задача (33), гдеA = (aij ) ∈ Mat(m × n, R), x, p – столбцы высоты n и b – столбец высоты m. Введем новые переменные xn+1 , . . . , xn+m > 0и перепишем (33) в видеtX > 0, (A E)X = b,(p 0)X = p1 x1 + · · · + pn xn → max,где X – столбец t (x1 , . . .
, xn , xn+1 , . . . , xn+m ) > 0. Здесь матрица (A E) ∈ Mat(m × (n + m), R) получается из A приписыванием справа единичной матрицы E размера m. Составляемтаблицуz01x1 , . . . xnA-pxn+1 , . . . , xn+mE0b054В. А. АртамоновМы приводим систему из m линейных уравнений (строки этойтаблицы, исключая первую и последнюю) к ступенчатому виду. Одновременно, мы преобразуем с помощью этой системыпоследнюю строку, соответствующую целевой функции, прибавляя к ней линейную комбинацию строк, соответствующихсистеме линейных уравнений. Другими словами, к последнейстроке (−p, 0, 0) прибавляется y ∗ (A, E, b) для некоторой строки y ∗ .
При этом результат имеет вид (−p + y ∗ A, y ∗ , y ∗ b), где(−p + y ∗ A, y ∗ ) > 0.(39)Теорема 2.12. Точка y ∗ является точкой экстремумадвойственной задачи (34).Доказательство. Из (39) вытекает, что t Ay ∗ > p, y ∗ > 0,т. е. y ∗ является допустимым решением двойственной задачи.Кроме того, значение целевой функции t by двойственной задачи совпадает с t y ∗ b и равно максимальному значению целевойфункции t px прямой задачи. В силу предложения 2.9 и теоремы 2.10 y ∗ является точкой экстремума.¤4.
Решение матричной игры с помощью линейногопрограммированияРассмотрим матричную игру с матрицей A = (aij ) ∈Mat(n × m, R) из главы 1 § 2. Применим алгоритм симплексметода для нахождения седловой точки смешанных стратегийиз теоремы 1.14.Заметим, что если мы прибавим ко всем элемента матрицыA одно и то же число d, то результат игры увеличится на d, носедловые точки не изменятся. Поэтому можно считать, что всеэлементы матрицы A неотрицательны, причем в матрице A > 0нет нулевых столбцов. Тогда результат игры v лежит в пределахmaxi minj aij 6 v 6 minj maxi aij и потому положителен.Рассмотрим пример игры с матрице鵶2 −1 3(40)3 4 1В первой строке минимальный элемент равен -1, а во второй –равен 1. Максимальный элемент расположен во второй строке.Следовательно, первый игрок выбирает 2-ю стратегию.Линейное программирование55Максимальный элемент в первом втором и третьем столбцах равен, соответственно, 3, 4, 3.
Из них минимальный равен3. Следовательно, второй игрок может выбрать 1-ую или 3-юстратегии. Тогда результатP игры 3 или 1.Положим F (x, y) = i,j aij xi yj . Напомним, что если x∗ =∗(x∗1 , . . . , x∗n ), y ∗ = (y1∗ , . . . , ym) – седловая точка, соответствующая оптимальным стратегиям первого и второго игрока,то для любых стратегий x, y первого и второго игрока имеемF (x, y ∗ ) 6 F (x∗ , y ∗ ) 6 F (x∗ , y),(41)В частности,v = max min F (x, y) = min max F (x, y) = F (x∗ , y ∗ ).x∈N y∈My∈M x∈NЗдесьN = {x ∈ An | x1 + · · · + xn = 1, xi > 0},M = {y ∈ Am | y1 + · · · + ym = 1, yi > 0}.(42)Рассмотрим следующую задачу линейного программированияf = u1 + · · · + um → max 1u1 Au 6 ...
, u = ... > 0,1(43)umРассмотрим также двойственную к (43) задачуg = t1 + · · · + tn → min, 1t1 .. .. tAt > . , t = . > 0.1(44)tnПредложение 2.13. Полиэдры P, Q, задаваемые, соответственно, неравенствами из (43), (44), непусты. Кроме того, P ограничено. В частности, maxu∈P f = mint∈Q g > 0.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
