В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 8
Текст из файла (страница 8)
Заметим, что начало координат O лежит в P , но не лежит в Q. Кроме того, если все координаты tдостаточно большие, то t ∈ Q. Поэтому P, Q непусты.56В. А. АртамоновПо предположению матрица A неотрицательна и в A нетнулевых столбцов. Поэтому для любого j = 1, . . . , m найдетсятакой индекс i, что aij > 0, откудаaij uj 6mXais us 6 1,s=11. Остается воспользоваться теоремой 2.10.aijТак как O ∈/ Q, то mint∈Q g > 0.¤и поэтому uj 61.
Тогда v > 0. Обознаv∗ ∗чим через u , t – оптимальные решения задач (43), (44), соответственно. Положим x∗ = vt∗ , y ∗ = vu∗ .Положим maxu∈P f = mint∈Q g =Теорема 2.14. Точка (x∗ , y ∗ ) является седловой для рассматриваемой матричной игры с матрицей A > 0, не содержащей нулевых столбцов.Доказательство. Заметим, чтmmXXyi∗ = vu∗i = v max f = 1,i=1u∈Pi=1т.
е. y ∗ ∈ M , где M из (42). Аналогичноx∗ ∈ N .Pm∗По теореме 2.11 получаем ti ( j=1 aij u∗j − 1) = 0. ДомножаяPmна v 2 получаем x∗i j=1 aij yj∗ = x∗i v, откудаXXF (x∗ , y ∗ ) =x∗i aij yj∗ =x∗ v = v,(45)iji∗поскольку x ∈ N . Кроме того, для любых x ∈ N, y ∈ M по (43)и (45)XXF (x, y ∗ ) =xi aij u∗j v 6xi v = v = F (x∗ , y ∗ ).ij∗∗i∗Аналогично F (x , y ) 6 F (x , y).¤Сделаем одно полезное замечание о редукции матрицыA при решении задачи о нахождении седловой точки.
ПустьA1 , . . . , Am – строки матрицы A и Ã1 , . . . , Ãn – ее столбцы.Если Ai > Aj , Ai 6= Aj для некоторых i, j, то первый игрок,Линейное программирование57стремясь к наибольшему выигрышу, всегда будет выбирать i-уюстратегию. Таким образом, мы можем исключить j-ую строкуиз рассмотрения, уменьшив тем самым число строк матрицы A.Аналогично, если Ãi > Ãj , Ãi 6= Ãj для некоторых i, j, то второй игрок, стремясь уменьшить выигрыш первого игрока, будетво всех случаях выбирать j-ую стратегию.
Таким образом, мыможем исключить из рассмотрения i-ый столбец и уменьшитьразмер матрицы A.Рассмотрим решение матричной игры с смешанных стратегиях на примере (40). Прибавим ко всем элементам 1, чтобыматрица A стала бы неотрицательной. Получаем матрицуµ¶3 0 4A1 =4 5 2При этом цена игру увеличится на 1. Решая за первого игрокавведем переменные t1 , t2 > 0, получаем задачуt1 + t2 → min,3t1 + 4t2 > 1,5t2 > 1,4t1 + 2t2 > 1,t1 , t2 > 0.(46)Решая за второго игрока введем переменные u1 , u2 , u3 > 0, получаем задачуu1 + u2 + u3 → max,3u1 + 4u3 6 1,4u1 + 5u2 + 2u3 6 1,u1 , u2 , u3 > 0.Эти задачи двойственны одна другой.Подробно решим задачу за первого игрока.
Запишем задачу(46) в виде−t1 − t2 → max,3t1 + 4t2 − t3 = 1,5t2 − t4 = 1,4t1 + 2t2 − t5 = 1,58В. А. Артамоновt1 , t2 > 0.Составим таблицуt13041t2 t34 -15 02 01 0t40-100t500-101110В первом столбце выбираем третью строку и делим ее на 4.Получаемt13011t2 t34 -15 01/2 01 0t40-100t500-1/40111/40Далее из всех строк вычитаем третью с соответствующим коэффициентом.
Получаемt10010t2 t35/2 -15 01/2 01/2 0t40-100t53/40-1/41/41/411/4-1/4Выбираем второй столбец и в нем первую строку. Деля ее на 5и получаемt10010t2151/21/2t3 t4-2/5 00 -10 00 0t53/100-1/41/41/1011/4-1/4Линейное программирование59Из всех строк вычитаем первую с соответствующим коэффициентом. Получаемt10010t21000t3-2/521/51/5t4t50 3/10-1 -3/20 -2/50 1/101/101/21/5-3/10Выбираем третий столбец и в нем вторую строку. Дели ее на 2и получаемt10010t21000t3-2/511/51/5t4t50 3/10-1/2 -3/40 -2/50 1/101/101/41/5-3/10Из всех строк вычитаем вторую с соответствующим коэффициентом.
Получаемt10010t21000t30100t4-1/5-1/21/101/10t50-3/41/201/41/51/43/20-7/20Решение закончено. Если v – результат игры с матрицей A, торезультат игры с матрицей A! равен v + 1. При это쵶1−77=−=.v+12020Поэтому v =207−1=137 .Из последней таблицы видно, чтоt1 =3,20t2 =1.560В. А. АртамоновПоэтомуx1 = (v + 1)t1 =3,7x2 = (v + 1)t2 =4.7Аналогично решается игра за второго игрока.5. УпражненияУпражнение 2.15. Пусть A ∈ Mat(m × n, R) не имеет нулевых столбцов, A > 0, b > 0 – столбец высоты m, с – столбецвысоты n. Обозначим через P – полиэдр, состоящий из множества столбцов X с условием AX 6 b, X > 0.
Доказать, чтокаждая аффинная функция на P достигает минимума и максимума.Упражнение 2.16. Пусть полиэдр P задается неравенствамиnXaj xj 6 b, x1 , . . . , xn > 0,j=1где b, a1 , . . . , an > 0. Предположим, что c1 , . . . , cn ∈ R, причемcвсе числа ajj различны и отличны от нуля. Доказать, что существует единственнаяточка в P , в которой достигает максимумPnфункция j=1 cj xj .Упражнение 2.17.
Пусть A ∈ Mat(m × n, R). Доказать,что следующие условия эквивалентны:1) для любых столбцов b, c высоты m, n, соответственно, существует max(t cx), где x удовлетворяет условиям Ax 6 b, x >0;2) существуют такие y ∈ An , p ∈ Am , что Ay < 0, t Ap > 0, p >0, y > 0.Упражнение 2.18.
Пусть A ∈ Mat(m × n, R) и c – столбецвысоты n. Предположим, что существует maxx∈P (t cx), где Pзадается условиями Ax = 0, x > 0. Доказать, что максимумдостигается на нулевом векторе.Линейное программирование61Упражнение 2.19. Найти min(x2 − x3 + 2x4 + 3), при условии−2x1 + x3 + x4 > 1,x1 + x2 + x3 = 4,−x2 + x3 − x4 6 3,x1 , x2 , x3 , x4 > 0.Упражнение 2.20.
Используя теорию двойственности решить задачуx1 + 2x2 + · · · + nxn → min,x1 > 1,x1 + x2 > 2,............................x1 + x2 + · · · + xn > n,x1 , . . . , xn > 0.Упражнение 2.21. Являются ли ограниченными многогранники, задаваемые следующими неравенствами:1)2)3)4)5)6)−3x1 + 5x2 6 10, 5x1 + 2x2 6 35, x1 > 0, x2 > 0;−x1 + x2 6 2, 5x1 − x2 6 10;3x1 − x2 > 4, −x1 + 3x2 > 4;−3x1 +4x2 6 17, 3x1 +4x2 6 47, x1 −x2 6 4, x1 +x2 > 0;−x1 + 2x2 6 6, 5x1 − 2x2 6 26, x1 + 2x2 > 10;5x1 − 2x2 > 6, 5x1 − 2x2 6 36, 2 6 x1 6 7.Упражнение 2.22. Найти угловые точки многогранников:1) x1 + 2x2 + x3 + 3x4 + x5 = 5,x1 + x3 − 2x4 = 3,x1 > 0, x2 > 0, x3 > 0, x4 > 0,2) x1 + x2 − x3 = 10,x1 − x2 + 7x3 = 7,x1 > 0, x2 > 0, x3 > 0;3) 4x1 + 5x2 + x3 + x4 = 29,6x1 − x2 − x3 + x4 = 11,x1 > 0, x2 > 0, x3 > 0, x4 > 0;4) x1 + 2x2 + x3 = 4,2x1 + 2x2 + 5x3 = 5,x1 > 0, x2 > 0, x3 > 0.x5 > 0;62В.
А. АртамоновУпражнение 2.23. Найти максимальные и минимальныезначения линейной функции z на ограниченном многограннике.1) x1 + 2x2 + x3 + 3x4 + x5 = 5,2x1 + x3 − 2x4 = 3,x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0,z = x1 − 2x2 + x3 + 3x5 ;2) 3x1 − x2 + 2x3 + x4 + x5 = 12,x1 − 5x2 − x4 + x5 = −4,x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0,z = 4x1 − x2 + 2x3 + x5 ;3) 5x1 + 2x2 − x3 + x4 + x5 = 42,4x1 − 4x2 + x3 + x4 = 16,x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0,z = x1 − 2x2 + 4x4 − x5 ;4) x1 − 3x2 + x3 + 2x5 = 8,4x2 − 3x4 − x5 = 3,x1 > 0, x2 > 0, x3 > 0, x4 > 0, x5 > 0,z = x1 − 2x2 + x3 − x5 .Упражнение 2.24.
Пусть (x∗ , y ∗ ), (x◦ , y ◦ ) – седловые точки для функции F (x, y). Доказать, что точки (x∗ , y ◦ ), (x◦ , y ∗ )также седловые. Вывести отсюда, что F (x∗ , y ◦ ) = F (x◦ , y ∗ ) =F (x∗ , y ∗ ) = F (x◦ , y ◦ ).Упражнение 2.25. Решить матричную задачу с матрице鶵3 −1 4.2 3 1Глава 3Специальные задачи линейногопрограммированияВ предыдущей главе описан симплекс-метод решения задачи линейного программирования. Однако число шагов в этомметоде может быть довольно большим. Вместе с тем специальные задачи линейного программирования, используемые впрактике, обладают рядом особенностей, которые выражаютсяв специфическом строении матрицы ограничений.
Это позволяет существенно упростить общий метод решения и выработатьболее простые алгоритмы решения рассматриваемых задач. Вэтой главе мы разберем лишь две такие задачи — транспортную задачу и задачу о нахождении кратчайшего расстояния награфе.1. Транспортная задачаПусть в заданных m городахA1 , . . .
, Am .(47)производится некоторый однородный продукт в количествахa1 , . . . , am > 0. Этот продукт перевозится в заданные n городовB1 , . . . , Bn ,(48)где он полностью потребляется в количествах b1 , . . . , bn > 0.Предполагаются заданными стоимости cij > 0 перевозок единицы продукта из Ai в Bj .Назовем планом перевозок неотрицательную матрицу X =(xij ) размера m × n, в которой xij > 0 указывается количество6364В. А.
Артамоновпродукта, перевозимого из Ai в Bj , 1 6 i 6 m, 1 6 j 6 n.Стоимость перевозок является линейной функцией от X,Xz(X) =cij xij , xij > 0.(49)i,jВ задаче требуется найти такой план перевозок X, чтобы егостоимость была бы минимальной, весь продукт был бы вывезениз (47) и потребности городов (48) были бы полностью удовлетворены.Транспортная задача является задачей линейного программирования.
Действительно, весь продукт, производимый в (47)вывозится в (48), где он полностью потребляется, причем всепотребности удовлетворены. Таким образом, возникают следующие условияPni = 1, . . . , m;j=1 xij = ai ,Pmj = 1, . . . , n;i=1 xij = bj ,xij > 0.(50)Требуется в условиях (50) найти минимум функции (49). Ввиду специфичности условий (50) можно предложить более специальный метод потенциалов решения этой задачи.Назовем план перевозок X допустимым, если выполненыусловия (50).Предложение 3.1.
Полиэдр P , задаваемый условиями(50), непуст тогда и только тогда, когдаXXai =bj .(51)ijДоказательство. Если X = (xij ) – допустимый план, топо (50)XXXXXXai =xij =xij =bj .iijjijОбратно, пусть выполнено условие (51). Построим первоначального плана X 0 = (x0ij ) методом минимального элемента. Выберем клетку (i, j) с минимальным значением cij . В эту клеткуставим число x0ij = min(ai , bj ). Если x0ij = bj , то в остальныеСпециальные задачи65клетки столбца j ставим 0, а число ai заменяем на ai − bj . Дуальным образом поступаем, если x0ij = ai .
Если ai 6 bj , то изAi весь продукт вывезен в Bj и потребность Bj становится равной bj − ai . Если же bj < ai , то в Bj весь необходимый продуктзавезен, и в Ai осталось ai − bj продукта. Таким образом, числолибо пунктов At , либо пунктов Bs уменьшилось.Повторяя эту процедуру, получим первоначальный допу¤стимый план X 0 = (x0ij ).Предложение 3.2. Полиэдр P , задаваемый условиями(50), ограничен.Доказательство.
Если X = (xij ) – допустимый план, тодля любых индексов i, j имеем 0 6 xij 6 min(ai , bj ).¤Следствие 3.3. Транспортная задача (50) имеет решениетогда и только тогда, когда выполнено равенство (51).Доказательство. По предложению 3.1 полиэдр P допустимых планов непуст. По предложению 3.2 он ограничен. Следовательно, непрерывная функция z(X) достигает на P минимума.¤Теорема 3.4. Для того, чтобы допустимый план перевозок X был оптимальным необходимо и достаточно, чтобы существовали такие числа (потенциалы) u1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
