В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 11
Текст из файла (страница 11)
В результате применения этихшагов получим в каждой строке клетку со знаком +! и темсамым завершим работу алгоритма.2.1. Пример. Пусть матрица A имеет вид793782689419347Тогда M = max aij = 9 и C равно951244382880В. А. Артамонов2062173105806520487556171Припишем слева столбец значений u1 = 0, . . . , u5 = 0, а сверхустроку v1 = 0, v2 = 0, v3 = 0, v4 = 0, v5 = 1.
Получаем таблицуu v00000020621073105080652004875156171Расставляем знаки + и получаемu v0000000270+ 3612 0+15080+65200+48751561+71+080 +!65200 +!48751561 +!71+Расставляем знаки ! и получаемu v0000000270+3612 0 +!15Совершаем основной шаг. Выбираем 5-ую и 3-ю строки. Дляних θ = 1. Меняем значения u1 , . . . , u5 и v1 , . . . , v5 . ПолучаемРасстояния на графеu v− 12− 1212− 1212811212121220+6217310 +!580 +!6520 +!4875− 12561 +!71+Добавляем знаки + и получаемu v− 12− 1212− 12121212121220+621+731+0 +!580 +!6520 +!48751212− 12561 +!71+Добавляем знаки ! и получаемu v− 12− 1212− 121212122780+30 +!61+620 +!51 +!520 +!4875− 12561 +!71+Работа алгоритма закончена.
Первый претендент занимает 4ую должность, второй претендент — 3-ю должность, третий —5-ую должность, четвертый — 2-ую должность, пятый — 1-уюдолжность.3. Кратчайшие расстояния на графеОриентированным графом Γ называется множество вершинX = (P0 , . . . , Pn ) и множество пар (Pi , Pj ) ∈ X × X, i 6= j.Пара (Pi , Pj ) называется ребром графа. Путем из Pr в Ps в Γназывается последовательность ребер(Pr , Pi1 ), (Pi1 , Pi2 ), .
. . , (Pik , Ps ).(67)82В. А. АртамоновПредположим, что граф Γ связен, т. е. для любых Pr и Ps существует путь из Pr в Ps . Пусть каждой паре (Pi , Pj ) предписанадлина lij > 0, причем lij = ∞, если пара (Pi , Pj ) не являетсяребром в Γ. Кроме того, предполагается, что lij = lji , если пары (Pi , Pj ), (Pj , Pi ) принадлежат Γ. Длиной пути (67) назовемсумму длин входящих в него ребер. В задаче требуется найтиминимальной длину пути из P0 в Pn .Для решения задачи необходимо найти такую квадратнуюматрицу X = (xij ) размера n+1, что xij = 1, если ребро (Pi , Pj )принадлежит выбранному пути, и xij = 0 в противном случае.Элементы xij являются целочисленным решением следующиезадачи линейного программирования:Pnz(X) = min i,j=0 lij xij → max,(68)0 6 xij 6 1;PnPn0 < i < n;j=1 xij =j=1 xji ,PnPnj=1 x0j = 1 +j=1 xj0 ;PnPn(69)j=1 xjn .j=1 xnj = 1 −Второе условие означает, что выбранный путь не кончается не вкакой внутренней точке P1 , .
. . , Pn−1 . Третье и четвертое условие означают, что путь начинается в P0 и кончается в Pn . Такимобразом, для решения задачи необходимо найти целочисленноерешение (68), минимизирующее z(X).Следующий алгоритм принадлежит Дейкстре (DijkstraE.W. // Num. Math. – 1959. - 1. - C. 269-271.) Этот алгоритм неявляется самым быстрым, но идея, заложенная в этом алгоритмы достаточно проста и ее изложение не занимает много места.В ходе работы алгоритма строится набор текущих систем путейиз P0 в каждую вершину P1 , . . . , Pn и их длины обозначаютсячерез λ1 , . .
. , λn .ШАГ 1.Заполняем квадратную матрицу размера n + 1, в которой наместе (i, j) стоит число lij , если lij < ∞. Положим λ0 = 0. Еслив на месте (i, j) стоит lij < ∞ и λi уже определено, но λj неопределено, то положим λj = λi + lij . Если же λj определено иимеет значение λ0j , то введем новое значение λj = min(λ0j , λi +lij ).Расстояния на графе83ШАГ 2.Если λj − λi 6 lij для всех i, j, то процесс останавливается.Если же λj0 − λi0 > li0 j0 для некоторых i0 , j0 , то заменим λj0на λ0j0 = λi0 + li0 j0 < λj0 .
Повторяя шаг 2, добиваемся, чтобыλ0j − λ0i 6 lij для всех i, j.Теорема 3.12. Если λj − λi 6 lij для всех i, j, то λj равнократчайшему расстоянию от P0 до Pj для всех j.Доказательство. По построению существует такое t1 ,что λi −λt1 = lt1 j . Далее существует такое t2 , что λt1 −λt2 = lt2 t1и т. д. Таким образом, в силу построения и связности Γ получаем последовательностьλi > λt1 > . .
. > λts > λ0 = 0.Рассмотрим путь из P0 в Pi , проходящий через точкиPts , . . . , Pt1 . Его длина равнаlots + · · · + lt2 t1 + lt1 i = λtk − λ0 + · · · + λt1 − λi= λi − λ0 = λi .Если же взять другой пусть P0 , Pr1 , . . . , Prk , Pi , то его длинаравнаl0r1 + · · · + lrk i > λr1 − λ0 + · · · + λi − λrk =λi − λ0 = λi .¤3.1.
Пример. Рассмотрим работу этого алгоритма на следующем примере. Пусть задан граф (см. Рис. 3.1). Пути безстрелок означают, что обе пары (Pi , Pj ), (Pj , Pi ) входят в Γ.Стрелка Pi → Pj означает, что пара (Pi , Pj ) входит в Γ, а пара(Pj , Pi ) не входит. Внесем эти данные в таблицу и вычислим84В. А. АртамоновP0P17tt»HH»»»HH 7D H»P2»HHYHHHDHH»»»» 1t3bHHDP5¤¤@bbHHD@Htb¤D³³@ b¤6 ³³³ LbD 5@bL¤1³³Db4@³³Lb¤³D¤º9@ ³³³bLbD ¤³³@b15L³D ¤b@³³L 10bD ¤ ³³³@bLD¤t³¾@tPbPPbL¢ P33P6PbPP¢LbPP¢PPbb L5PPb L¢2PbPPbLt P7¢P411Рис.
3.1значения λj (шаг 1).λjP0P1P2P3P4P5P6P7λi07659111015P00P17P2677359P35P49591P511P715415711415P6102(70)62631110511105Проверяя положительность λi − λj − lji имеем λ4 − λ3 − l34 = 2.Полагаем λ04 = λ3 + l34 = 7 заменим в таблице (70) λ4 = 9на λ04 = 7. Полученная новая система удовлетворяет условиюλ0j − λ0i 6 lij для всех i, j. Ответ: λ7 = 15.Упражнения85Возможны другие постановки задачи.1) В графе Γ задано время движения tij из Pi в Pj при движении с постоянной скоростью. Требуется найти минимальнойвремя, за которое из P0 можно добраться до Pn .2) В графе Γ задана стоимость перевозки tij единицы груза изPi в Pj . Требуется найти минимальную стоимость перевозкииз P0 в Pn .4.
УпражненияУпражнение 3.13. Доказать, что транспортная задачаневырождена тогда и только тогда, когда она не имеет вырождения как задача линейного программирования.Упражнение 3.14. Пусть транспортная задача вырождена и заданы подмножестваG ⊂ {1, . . . , m},H ⊂ {1, . . .
, n}.Пусть матрицы X1 , X2 – решения транспортных задач для наборов индексов G, H и {1, . . . , m} \ G, {1, . . . , n} \ H. Верноли, что матриц൶X1 0.0 X2будет1) допустимым планом исходной транспортной задачи,2) решением исходной транспортной задачи.Упражнение 3.15.
Показать, что система уравнений длянахождения первоначальной системы потенциалов состоит изn + m − 1 уравнения.Упражнение 3.16. Верно ли, что оптимальный плантранспортной задачи единствен.Упражнение 3.17. Доказать, что допустимый план невырожденной транспортной задачи не имеет циклов тогда и только тогда, когда он является крайней точкой полиэдра, задаваемого системой неравенств (50).Глава 4Нормированные пространства иалгебрыВсюду в этой главе под F понимается либо поле вещественных чисел R, либо поле комплексных чисел C.Определение.
Векторное пространство V над полем F называется нормированным векторным пространством с нормойkxk, если на V задана функция x → kxk, принимающая неотрицательные вещественные значения, причем1) kxk = 0 тогда и только тогда, когда x = 0;2) kλxk = |λ|kxk для всех x ∈ V, λ ∈ F;3) kx + yk 6 kxk + kyk.Из этого определения вытекаетПредложение 4.1. Для любых элементов x, y из нормированного векторного пространства справедливо равенствоkx − yk ≥ |kxk − kyk|.Доказательство.
По свойству 3) имеем kxk = k(x − y) +yk 6 kx − yk + kyk. Отсюда kxk − kyk 6 kx − yk. Аналогичноkyk − kxk 6 ky − xk = | − 1|kx − yk = kx − yk. Из полученныхдвух неравенств вытекает утверждение.¤Пример 4.2. Рассмотрим различные виды норм.1) Пусть V – евклидово или эрмитово пространство. ТогдаV являетсянормированным пространством, если положитьpkxk = (x, x).8788В. А. Артамонов2) Пусть Fn – пространство строк длины n с коэффициентамииз F. Для любого вещественного числа p ≥ 1 положимsXkxkp = p|xj |p .jnТогда F является нормированным векторным пространством с нормой kxkp . Эта норма называется lp -нормой.3) В пространстве Fn положимkxk∞ = max |xj |.jnТогда F является нормированным векторным пространством с нормой kxk∞ .
Эта норма называется l∞ -нормой.4) Пространство всех непрерывных функций на отрезке [0, 1]является нормированным пространством с нормой kf k =maxx |f (x)|, а также с нормамиvuZ1uuptf (x)p dx,0где p ≥ 1 – заданное вещественное число.Теорема 4.3. Пусть V - конечномерное нормированноевекторное пространство над полем F. Зафиксируем базис e =(e1 , . . .
, en ) в V и рассмотрим функцию f : Fn → R, гдеf (x1 , . . . , xn ) = kx1 e1 + · · · xn en k. Тогда функция f непрерывна.Доказательство. Для любыхx1 , . . . , xn , y1 , . . . , yn ∈ Fпо предложению 4.1 имеем|f (x1 , . . . xn ) − f (y1 , . . . yn )| = |kxk − kyk| 6PPkx − yk = k j (xj − yj )ej k 6 j |xj − yj |kej k.(71)Положим M = maxj kej k. Тогда в (71) получаем|f (x1 , . . . xn ) − f (y1 , . . . yn )| 6 M max |xj − yj |.jОтсюда следует утверждение.¤Нормированные пространства89Теорема 4.4.
Пусть V - конечномерное нормированноепространство с двумя нормами kxk и kxk0 . Тогда существуют такие положительные вещественные числа C1 , C2 , чтодля всех x ∈ V справедливы неравенства C1 kxk 6 kxk0 6 C2 kxk.Доказательство. Без ограничения общности можнопредполагать, что одна из норм, например, kxk – евклидова (эрмирова). Выберем в V ортонормированный базис e =(e1 , P. . . , en ) и обозначим через S множество всех таких x ∈ V ,что j |x2j | = 1. Тогда S является n-мерной сферой и, следовательно, компактом.
Отсюда в силу теоремы 4.3 вытекает, чтофункция kxk0 на S, принимающая положительные значения,ограничена сверху и снизу, т.е. существуют такие положительные вещественные числа C1 , C2 , что для всех x ∈ S справедлиxвы неравенства C1 6 kxk0 6 C2 . Если x ∈ V \ 0, то y = kxk∈ S.Таким образом,C1 6 kyk0 = kxkxk0=6 C2 ,kxk0kxkОтсюда вытекает утверждение.¤Определение. Пусть xn – последовательность элементовнормированного пространства V . Скажем, что эта последовательность сходится к элементу x ∈ V , если для любого ε > 0существует такое натуральное число N , что для всех n > Nсправедливо неравенство kxn − xk < ε.Аналогичным образом определяются последовательностиКоши и полные нормированные векторные пространства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
