В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 9
Текст из файла (страница 9)
. , um , v1 , . . . , vn ,для которых1) ui + vj 6 cij при всех i, j;2) ui + vj = cij , если xij > 0.Доказательство. Проверим достаточность. Пусть X =(xij ) – допустимый план, иu 1 , . . . , u m , v 1 , . . . , vnиз условий теоремы. Предположим, что Y = (yij ) – произвольный допустимый план. Из (50) и условий 1), 2) следует, чтоXXz(Y ) =cij yij >(ui + vj )yiji,j=XiuiXii,jyij +XjvjXiyij66В.
А. Артамонов=Xui ai +i=Xuii=XXXvj b jjxij +iXj(ui + vj )xij =i,jvjXXxijicij xij = z(X).i,jПроверим теперь необходимость. Рассмотрим задачу, двойственную к транспортной задаче. Для этого положим перепишем ограничения из (50) и целевую функцию в видеX− z(X) =(−cij xij ) → max,i,jnXxij 6 ai ,i = 1, . . . , m;j=1nX(−xij ) 6 −ai ,j=1mXxij 6 bj ,i=1mXi = 1, . . . , m;j = 1, . .
. , n;(−xij ) 6 −bj ,j = 1, . . . , n;i=1xij > 0.Тогда по определению 2.7 двойственная задача с переменными0w1 , . . . wm , w10 , . . . , wm, s1 , . . . , sn , s01 , . . . , s0n > 0к транспортной задаче имеет видPnPmT 0 = i=1 (wi − wi0 )ai + j=1 (sj − s0j )bj → min,wi0(52)s0j> −cij , 1 6 i 6 m; 1 6 j 6 n;00, s1 , . . . , sn , s01 , . . . , s0n > 0.w1 , . . . wm , w1 , . . . , wmПоложим ui = wi0 − wi , vj = s0j − sj . Тогда (52) записываетсяwi −+ sj −ввидеui + vj 6 cijPnPmT = −T = i=1 ui ai + j=1 vj bj → max .0(53)Специальные задачи67Как отмечено в предложении 3.2 ограничения (50) задают ограниченный полиэдр P . Следовательно, как отмечено в следствии 3.3 функция z(X) на P достигает минимум в некоторойточке X 0 .
Заметим, что полиэдр Q, задаваемый неравенствами(53) содержит начало координат, поскольку cij > 0. Следовательно, Q непусто и по теореме 2.10min(z(X)) = − max(−z(X)) = − min(T 0 )= max T =mXui ai +i=1nXvj bj .j=1Пусть в точке (u1 , . . . , um , v1 , . . . , vn ) ∈ Q достигается максимум. По теореме 2.11 о равновесии получаем ui + vj = cij , еслиx0ij > 0.¤Перейдем к изложению алгоритма решения транспортнойзадачи при некоторых ограничениях.Определение.
Транспортная задача называется вырожденной, если существуют такие собственные подмножестваинPa=дексовG⊂{1,...,m},H⊂{1,...,n},чтоii∈GPj∈H bj . Другими словами, суммарный запас продукта в пунктах Ai , i ∈ G, совпадает с потреблением в пунктах Bj , j ∈ H.Далее мы будет предполагать, что рассматриваемая транспортная задача невырождена. Для полного обоснования алгоритма в этом случае нам потребуется ряд утверждений.Предложение 3.5. Пусть план X = (xij ) допустим,и xi0 j0 = 0. Тогда существует такая последовательностьi0 , i1 , . . . , ik и последовательность столбцов j1 , .
. . , jk , j0матрицы X, что элементыxi0 j1 , xi1 j1 , . . . , xik jk , xik j0(54)отличны от нуля.Доказательство. Предположим противное, в любой последовательности (54) встречается нулевой элемент. Обозначимчерез H множество всех таких индексов j ∈ {1, . . . , n}, для которых найдется последовательность ненулевых элементовxi0 q1 , xp1 q1 , .
. . , xps qs , xps j .68В. А. АртамоновЗаметим, что j0 ∈/ H. Через G обозначим множество всех такихиндексов i ∈ {1, . . . , m}, что xij 6= 0 для некоторого j ∈ H. Изопределения G вытекает, что если i ∈ G и xis 6= 0, то s ∈ H.ПоэтомуXXXbj =xij =ai .j∈HОтсюдаi∈G,j∈HXi∈G/ai =Xi∈Gbj > 0.i∈H/Следовательно, G 6= {1, . . . , n}, и H 6= {1, . . . , m}. Это противоречит невырожденности задачи.¤Определение 3.6. Пусть X = (xij ) – допустимый план.Циклом в X назовем последовательность ненулевых элементов xp1 q1 , xp1 ,q2 , . .
. , xps ,qs , xps ,q1 , причем среди первых и средивторых индексов в этой последовательности имеются нет совпадений.Предложение 3.7. Если допустимый план не содержитциклов, то в предложении 3.5 по набору i0 , j0 последовательность (54) определена однозначно.Доказательство.
Пусть кроме (54) существуют еще и последовательность ненулевых элементовxi0 j10 , xi01 j10 , . . . , xi0t jt0 , xi0t j0 .Рассмотрим последовательностьxi1 j1 , . . . , xik jk , xik j0 , xi0t j0 , xi0t jt0 , . . . , xi01 j10 , xi0 j10 , xi0 j1 .По условию она не является циклом. Поэтому либо среди первых, либо среди вторых индексов имеются совпадения. Пусть,например, ir = i0s . Тогда имеется более короткая последовательность ненулевых элементов0xi1 j1 , .
. . , xit−1 jt−1 , xi0s js0 , xi0s js−1, . . . , xi01 j10 , xi0 j10 , xi0 j1 .Продолжаю этот процесс получаем, что в X имеется цикл,что невозможно. Аналогичная ситуация, если совпадают двавторых индекса. Следовательно, наборы индексов i1 , . . . , ik иj1 , . . . , jk определены однозначно.¤Специальные задачи69Изложим теперь алгоритм решения невырожденной транспортной задачи.ШАГ 1. Построение первоначального плана методом минимального элемента. В соответствии с предложением 3.1 строим первоначальный план X 0 = (x0ij ).Предложение 3.8.
План X 0 не содержит циклов. В каждой строке и столбце плана X 0 содержится ненулевой элемент. Всего в X 0 число ненулевых элементов равно m + n − 1.Доказательство. Пусть план X 0 содержит циклxp1 q1 , xp1 ,q2 , . . . , xpk ,qk , xpk ,q1 , из определения 3.6. Выберем вэтой последовательности тот элемент, который построен первым. Пусть, например, это xp1 q1 . Тогда элементы xp1 ,q2 , xps ,q1 ,построены позднее, что невозможно, ибо при построении xp1 q1либо на месте (p1 , q2 ), либо на (ps , q1 ) ставится 0.
Аналогичнорассматриваются остальные случаи.В силу (50) в каждой строке и столбце плана X 0 содержитсяненулевой элемент. Последнее утверждение легко проверяетсяиндукцией по m + n.¤ШАГ 2. Построение первоначальной системы потенциалов.Для каждой из n + m − 1 клеток (i, j), в которых находитсяненулевой элемент из X 0 рассмотрим уравнениеui + vj = cij(55)с неизвестными vi , ui . Полученная система состоит из n + m − 1уравнений с n + m неизвестными. Если crs – минимальный элемент и ar < bs , то неизвестная ur входит только в одно уравнение (55)ur + vs = crs .(56)Индуктивные соображения показывают, что система (55) без(56) совместна. Из (56) находим ur .
Аналогично рассматривается случай ar 6 bs . Итак, решая систему (55) находим первоначальную системы потенциалов.ШАГ 3.Проверяем, удовлетворяет ли построенный план и система потенциалов условиям теоремы 3.4.70В. А. АртамоновЗаметим, что условие 2 из теоремы 3.4 выполнено по построению. Остается лишь проверить условие 1). Если оно выполнено,то полученный план оптимален. В противном случае переходимк следующему шагу.ШАГ 4. Улучшение плана X.Пусть относительно системы потенциалов ui , vj план X не оптимален, т.
е. не выполнено условие 1) теоремы 3.4. Выберемотклонениеαi0 j0 = ui0 + vj0 − ci0 j0 > 0.(57)Тогда xi0 j0 = 0 и по предложению 3.5 существует последовательность ненулевых элементовxi0 j1 , xi1 j1 , . . . , xik jk , xik j0Расставим во всех выбранных клетках(i0 , j0 ), (i0 , j1 ), . . . , (ik , j0 )последовательно чередующиеся метки метки +, -, +, . . . , -.Пусть θ – минимальный среди элементовxi0 j1 , xi1 j2 , . . .
, xik−1 jk , xik j0 ,в клетках, помеченных знаком -. В клетках со знаком + числоxij увеличиваем на θ, а со знаком - уменьшаем на θ, т. е.x0i0 j0 = xi0 j0 + θ = θ;x0i0 j1 = xi0 j1 − θ;x0i1 j1 = xi1 j1 + θ;.........................x0ik−1 jk−1 = xik−1 jk−1 + θ;x0ik−1 jk = xik−1 jk − θ.Для остальных пар индексов положим x0ij = xij . Получаем новый допустимый план X 0 = (x0ij ).Предложение 3.9. Если допустимый план X не содержал циклов, то и новый план X 0 не содержит циклов.Доказательство.
Пусть план X 0 содержит циклx0p1 ,q1 , x0p1 ,q2 , . . . , x0ps ,qs , x0ps .q1 .Специальные задачи71Как и предложении 3.5 можно считать, что все индексыp1 , p2 , . . . , ps , (соответственно, q1 , q2 , . . . , qs ) различны. Eслиx0ij 6= 0 и (i, j) 6= (i0 , j0 ), то xij 6= 0. Так как X не содержитциклов, то среди элементовxp1 q1 , xp1 ,q2 , . . . , xps ,qs , xps ,q1встречается xi0 j0 = 0.
Пусть, например, (i0 , j0 ) = (pr , qr ). Тогдаимеем последовательность ненулевых элементовxpr qr+1 , xpr+1 ,qr+1 , . . . , xps ,qs , xps ,q1 , . . . , xpr−1 qr ,не содержащую xi0 j0 6= 0. По предложению 3.7 получаем, что(pr , . . . , ps , p1 , . . . , pr−1 ) = (i0 , . . . , ik ),(qr+1 , . . . , qs , q1 , . . . , qr ) = (j0 , . . . , jk ).В силу выбора θ один из элементов x0pi−1 qi = 0. Следовательно,этот случай невозможен.Пусть (i0 , j0 ) = (pr−1 , qr ).
Тогда имеем последовательностьненулевых элементовxpr−1 qr−1 , xpr−2 ,qr−1 , . . . , xp1 ,q1 , xps ,q1 , . . . , xpr qr ,что снова приводит к противоречию.¤Переходим к следующему шагу.ШАГ 5. Улучшение потенциалов.Положим vj0 0 = vj0 − αi0 ,j0 , u0i0 = ui0 . Если задана пара индексов (i, j), i 6= i0 , и существует последовательность индексовp1 = i 6= i0 , p2 6= i0 , .
. . , ps 6= i0 ;q1 = j, q2 , . . . , qs = j0 ,(58)причем все элементыx0p1 ,q1 , x0p1 ,q2 , . . . , x0ps ,qs(59)отличны от нуля. В этом случае положимvj0 = vj − αi0 j0 ,u0i = ui + αi0 j0 ,где ai0 j0 из (57). Для всех оставшихся индексов i (соответственно, j) полагаем vj0 = vj , u0i = ui . В частности, u0i0 = ui0 .Предложение 3.10. Если x0ij 6= 0, то u0i + vj0 = cij .72В. А. АртамоновДоказательство. Если x0ij 6= 0, и i 6= i0 , то, как отмечалось выше, xij 6= 0. Пусть существует последовательность вида(58) со свойством (59).
Тогда в силу ШАГА 5u0i + vj0 = ui + vj = cij .Кроме того, u0i0 +vj0 0 = ui0 +vj0 −αi0 j0 = ci0 j0 . Рассмотрим клетку (i0 , j), j 6= j0 , причем x0i0 j 6= 0. Пусть существует последовательность вида (58) со свойством (59) для некоторого i 6= i0 . Таккак в (59) нет элемента x0i0 j0 , то xp1 q1 , xp1 ,q2 , .
. . , xps ,qs отличны от нуля и поэтому имеется последовательность ненулевыхэлементовxi0 j , xp1 q1 , xp1 ,q2 , . . . , xps ,qs .(60)Можно считать, по предложению 3.7, что(p1 , . . . , i, . . . , ps ) = (i1 , . . . , ik ),(q1 , . . . , qs ) = (j1 , . . . , jk ).Но тогда в последовательности (60), как и выше, встречаетсянулевой элемент, что невозможно. Итак, если x0i0 j 6= 0, где j 6=j0 , то vj = vj0 , и поэтому в этой клетке ci0 ,j = vj0 + u0i0 .¤ШАГ 6.Проверяем для плана X 0 и потенциалов u0i , vj0 выполнение условия 1) из теоремы 3.4.Если оно не выполнено, то переходим в шагу 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
