В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 10
Текст из файла (страница 10)
Если оно выполнено, то оптимальный план построен.Приведенный алгоритм конечен. Действительно на 4-омшаге получаем новый план X 0 . Если ai0 j0 из (57), то считаяjk+1 = j0 получаемXz(X 0 ) − z(X) =cij (x0ij − xij )i,j=k−1Xcis js (x0is js − xis js ) +s=0=k−1Xs=0kXcis js+1 (x0is js+1 − xis js+1 )s=0cis js θ −kXs=0cis js+1 θ£= θ ci0 j0 + (ui1 + vj1 ) + · · · + (uik−1 + vjk−1 )Специальные задачи73¤− (ui0 + vj1 ) − · · · − (uik + vjk+1 )= θ [ci0 j0 − (ui0 + vj0 )] = −θαi0 j0 < 0.При этом для нового плана X 0 выполнено условие 2) из теоремы 3.4.
Таким образом, число шагов не превосходит числаподмножеств клеток с ненулевыми элементами из допустимого плана X 0 . Так как значение Z(X) уменьшается, то у нас невозникает повторений.Изложение алгоритма завершено.Следствие 3.11. Если в условии невырожденной транспортной задачи числа a1 , . . . , am , b1 , . . .
, bn являются целыми, то задача имеет целочисленное решение.Предложенный алгоритм может быть использован при решении ряда близких задач.1) Количество производимого в (47) продукта больше количества продукта, потребляемого в (48). Требуется перевестис минимальными затратами из (47) производимый продукт,чтобы полностью удовлетворить потребности в (48).Решение задачи сводится к общей транспортнойзадачеPPвведением пункта Bn+1 с потреблением bn+1 = i ai − j bj ,причем ci,n+1 = 0 для всех i.2) Количество потребляемого в (48) продукта больше количества продукта, производимого в (47). Требуется перевестис минимальными затратами из (47) производимый продукт,чтобы полностью удовлетворить потребности в (48).Решение задачи сводится к общей транспортнойPзадачевведением пункта Am+1 с производством am+1 =j bj −Pb,причемc=0длявсехj.im+1,ji3) Если же имеется запрет на перевозки из Ai в Bj , то полагаемcij = ∞.4) Если от Ai в Bj имеются фиксированные поставки в количестве dij , то заменяем ai , bj и cij на ai − dij , bj − dij и∞.
Решая получаемую транспортную задачу и находя оптимальный план X = (xrs ), мы затем общие затраты Z(X)увеличиваем на cij dij .74В. А. Артамонов5) Если между Ai и Bj имеются минимальные поставки в количестве dij , то заменяем ai , bj на ai −dij , bj −dij . Решая получаемую транспортную задачу и находя оптимальный планX = (xrs ), мы затем заменяем xij на dij .6) Если от Ai к Bj поставки не должны превышать объем dij ,то мы заменим Bj на два объекта Bj0 Bj00 , где b0j = dij , b00j =bj − dij .
Кроме того, полагаем c0tj = ctj , c00tj = ∞ для всехt = 1, . . . , m.Случай вырожденной транспортной задачи рассматривается в[ZA, c. 218-219].1.1. Пример. Пусть в пунктах A1 , A2 , A3 , A4 производится продукт в количествахa1 = 13, a2 = 7, a3 = 13, a4 = 4.В пунктах B1 , B2 , B3 , B4 , B5 потребности составляютb1 = 5, b2 = 9, b3 = 9, b4 = 5, b5 = 9.Матрица C стоимостей перевозок единицы товара имеет вид2 4 5 3 63 4 3 2 5 4 6 5 3 7 .2 3 7 6 4Требуется найти оптимальный допустимый план перевозок X ∈Mat(4 × 5, R)ШАГ 1. Строим первоначальный план X 0 методом минимального элемента.
Наименьшее значение cij равно c11 = 2. В этуклетку ставим min(a1 , b1 ) = min(13, 5) = 5 = b1 . При этом a1заменяем на a01 = a1 − 5 = 8, а во все остальные клетки первого столбца ставим нули. Далее минимальное значение c24 = 2,причем min(a2 , b4 ) = 5 = b4 . Поэтому в клетку ставим 5, всеостальные элементы четвертого столбца заполняем нулями, иполагаем a02 = a2 − 5 = 2. В незаполненных клетках минимальное значение cij равно 3, например, c23 = 3. Ставим в этуклетку min(a02 , b3 ) = min(2, 9) = 2.
При этом заменяем b2 наb02 = b2 − 2 = 7 и заполняем пустые клетки второй строки нулями. Продолжая этот процесс, получаем первоначальный планСпециальные задачиX 0 , имеющий вид50005004324005007500.90ШАГ 2. Строим первоначальную систему потенциалов. Дляэтого решаем систему линейных уравненийu1 + v1 = 2,u1 + v2 = 4, u1 + v3 = 5,u2 + v3 = 3, u2 + v4 = 2,u3 + v3 = 5,u3 + v5 = 7,u4 + v2 = 3.Возьмем частное решениеu1 = 0, u2 = −2, u3 = 0,v1 = 2, v2 = 4, v3 = 5,u4 = −1v4 = 4, v5 = 7.Таким образом, если составить матрицу C 0 , в которой на месте(i, j) стоит ui + vj , то она имеет вид2 4 5 4 70 2 3 2 3C0 = 2 4 5 4 7 .1 3 4 3 6ШАГ 3. Убеждаемся, что C 0 C, т.
е. построенный план неудовлетворяет условию 1) из теоремы 3.4. Например, c15 = 6 <7 = u 1 + v5 .ШАГ 4. Улучшаем план X 0 . Начиная с x015 строим последовательность x013 , x033 , x035 6= 0,. Расставляем пометки + вклетки (1, 5), (3, 3) и - в клетки (1, 3), (3, 5). полагаем θ =min(x013 , x033 ) = min(3, 9) = 3. Меняем план, полагаяx015 = 3,x013 = 0,x033 = 7,x035 = 6.В остальных случаях полагаем x0ij = x0ij . Получаем новый план5 5 0 0 30 0 2 5 0X0 = 0 0 7 0 6 .0 4 0 0 076В.
А. АртамоновШАГ 5. По новой матрице X 0 составляем систему уравненийдля новых потенциаловu1 + v1 = 2,u1 + v2 = 4,u1 + v5 = 6u2 + v3 = 3, u2 + v4 = 2,u3 + v3 = 5,u3 + v5 = 7,u4 + v2 = 3.Возьмем частное решениеu1 = 0, u2 = −1, u3 = 1,v1 = 2, v2 = 4, v3 = 4,Строим матрицу2100C =31435343353u4 = −1v4 = 3, v5 = 6.62425.75Возвращаемся к шагу 3 и находим, что C 0 C, т. е. построенный план не удовлетворяет условию 1) из теоремы 3.4.
Например, c24 = 3 < 4 = u2 + v4 . Выбираем путь x034 = 0, x033 6=0, x023 6= 0, x024 6= 0. Расставляем пометки + в клетки (3, 4), (2, 3)и - в клетки (3, 3), (2, 4). Тогда θ = min(7, 5) = 5. Составляемновый план5 5 0 0 30 0 7 0 0X 00 = 0 0 2 5 6 .0 4 0 0 0По новой матрице X 00 составляем систему уравнений для новыхпотенциаловu1 + v1 = 2,u1 + v2 = 4,u1 + v5 = 6u2 + v3 = 3,u3 + v3 = 5, u3 + v4 = 3u3 + v5 = 7,u4 + v2 = 3.Возьмем частное решениеu1 = 0, u2 = −1, u3 = 1,v1 = 2, v2 = 4, v3 = 4,u4 = −1v4 = 2, v5 = 6.Специальные задачиСтроим матрицуC 00021=314353435331317765.75В этом случае C 000 6 C. Отсюда следует оптимальность плана.При этомz(X 00 ) = 5 · 2 + 5 · 4 + 3 · 6 + 7 · 3 + 2 · 5 + 5 · 3 + 6 · 7 + 4 · 3 = 148.2. Задача о назначенияхРассмотрим важную специальную задачу линейного программирования – задачу о назначениях, – решение которойможно найти, применяя изложеный выше алгоритм решениятранспортной задачи.Предположим, что у нас имеется n претендентов на n вакантных должностей, причем известны эффективности aij , 1 6i, j 6 n, работы i-го претендента на j-ой должности.
Предполагается, что матрица A = (aij ) целочисленна. Распределением наработу называется такая подстановка σ ∈ Sn , что i-ый претендент занимает σ(i)-ую должность. Требуется найти такое распределение, чтобы суммарная эффективностьnXai,σ(i)i=1была бы максимальной. Покажем, что эта решение задача о назначениях сводится к решению некоторой транспортной задаче.Для этого сопоставим каждому распределению претендентов подолжностям неотрицательную матрицу X = (xij ) ∈ Mat(n, Z),где(1, если j = σ(i);xij =0, в противном случае.Условие того, что каждая должность занята можно выразить ввиде систем уравненийnXxij = 1, j = 1, .
. . , n.(61)i=178В. А. АртамоновУсловие того, что каждый претендент получил назначение записывается в виде систему уравненийnXxij = 1,i = 1, . . . , n.(62)j=1При этом все xij > 0 и нам требуется найти максимум функцииnXaij xij .(63)ij=1Положим M = maxij aij . Тогда задача (61), (62), (63) эквивалентна следующей транспортной задачеPn(64)ij=1 (M − aij )xij → min,Pnxij = 1, j = 1, . . . , n;Pi=1ni = 1, . . .
, n;j=1 xij = 1,xij > 0.(65)Заметим, что M − aij > 0 в силу выбора M .К сожалению, возникающая транспортная задача вырождена и изложеный выше алгоритм не применим. Для решениязадачи о назначениях применяется другой способ – венгерскийметод. Он также основан на теореме 3.4. Пусть C = (cij =M − aij ) > 0.Строим первоначальную систему потенциаловu1 = . . .
= un = 0,v1 = min ci1 , . . . , vn = min cin .ii(66)Пометим знаком + все клетки (i, j), в которых cij = ui + vj , т.е. выполнено условие 2) из теоремы 3.4. В силу выбора (66) вкаждом столбце содержится клетка со знаком +. Выберем среди этих клеток подмножество таким образом, чтобы в каждомстолбце и каждой строке содержалось не более одного элемента.Пометим эти клетки дополнительным знаком ! . Таким образом, эти клетки помечены знаком +! . Если в каждой строке (истолбце) содержится клетка (i, j), помеченная +!, то сопоставимi-ому претенденту место j.Предположим, что не все строки содержат клетки со знаком+! . Применим в этом случаеСпециальные задачи79Основной шаг алгоритма.Итак, у нас выделены клетки со знаками + и +! . Кроме того,задана текущая система потенциаловu1 , . . .
, un , v1 , . . . , vn .Выделим теперь наименьшее множество строк со следующимисвойствами:1) выделены все строки, не содержащие клеток со знаком +! ;2) если выделенная i-ая строка содержит клетку (i, j) со знаком+ или +! и t-ая строка содержит клетку (t, j) со знаком +или +! , то выделяется и t-ая строка.Пусть θ – минимум всех ненулевых cij −ui −vj , где 1 6 j 6 n и i– пробегает все выделенные строки. Если i-ая строка выделена,θто заменяем ui на u0i = ui + . Если s-ая строка не выделена,2θто то заменяем us на u0s = us − . Затем каждое vj заменяем2θна vj0 ± , где знак выбирается таким образом, чтобы во всех2клетках со знаком + или +! выполнялось равенство cij = u0i +vj0 .В силу выбора строк этот шаг возможен.После применения основного шага число клеток со знаком+ или +! увеличивается, поскольку к ним добавляется клетка(i, j), в которой θ = cij − ui − vj .После применения основного шага можно перераспределитьзнак ! по клеткам со знаком +.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
