УМК (1013374), страница 36
Текст из файла (страница 36)
Для клетки (2,1) построим означенныйцикл и найдем значение θ = min [ 10, 20 ] = 10 . Выполним сдвиг по циклу на числоθ = 10 .ПунктыB1A11A22A30Потребности2010•30β1 = 1B2230B3•3•102030320•200β3 = 2β2 = 2Получим: f = 20 + 20 + 30 + 60 = 130 ; Δ12 = 2 − (0 + 2) = 0,Δ 31 = 0 − (−2 + 1) = 1 ,Таблица 10Запасыα1 = 02040α2 = 120α 3 = −280Δ13 = 3 − (0 + 2) = 1,Δ 33 = 0 − (−2 + 2) = 0 .Поскольку все Δ i j ≥ 0 , условие окончания выполнено. Оптимальный план перевозок исходной задачи содержится в найденном оптимальном плане:x11 = 20, x12 = x13 = 0, x 21 = 10, x 22 = 10, x 23 = 20 .Значение x 32 = 20 свидетельствует о том, что в п.
B 2 на эту величину не удовлетвореныпотребности.Пример 3. Решить транспортную задачу, заданную матрицей перевозок (табл. 11).ПунктыA1B1B2Таблица 11Запасы2097A26980A31220Потребности502070/120 Так как в поставленной задаче нарушен баланс и суммарные запасы большесуммарных потребностей, то:1) введем фиктивный пункт потребления B3 с потребностью, равной 120 − 70 = 50 ;2) положим стоимости перевозки единицы груза в фиктивный пункт потребленияравными нулю.В результате перейдем к задаче, в которой выполняется условие баланса.Начальный план перевозок найдем методом минимального элемента:x13 = min [ 20, 50] = 20 ; x11 = x12 = 0 (в табл. 12 здесь и далее ставятся точки);223x 23 = min [80, (50 − 20) ] = 30 , x 33 = 0 ;x 31 = min [ 20,50] = 20 , x 32 = 0 ;x 21 = min [ (80 − 30),(50 − 20) ] = 30 ;x 22 = min [ 20, 20] = 20 .Его стоимость составляет f = 180 + 180 + 20 = 380 .Решим полученную задачу методом потенциалов.
Результаты решения приведеныв табл. 12–13.Таблица 12Запасыα1 = 020ПунктыA19•7⊕ •020 -A26309- 20030 ⊕80α2 = 0A3120502•200•5020α 3 = −5B1ПотребностиB2β1 = 6Получим:B3120β3 = 0β2 = 9Δ 11 = 3 − (0 + 6) = 3,Δ12 = 7 − (0 + 9) = −2, ⊗Δ 32 = 2 − (−5 + 9) = −2 ,Δ 33 = 0 − (−1 + 2) = −1 .Для клетки (1,2) построим означенный цикл и найдем значение θ = min[ 20, 20 ] = 20 . Выполним сдвиг по циклу на число θ = 20 . Поскольку наименьшее значение θ = 20 достигается сразу в двух отрицательных клетках, то согласно шагу 6 алгоритма в одной из этихклеток ставится базисный нуль (выбрана клетка (1,3) с наименьшей стоимостью).ПунктыB1A19A2A3ПотребностиB2•761B32000309•020502•20050•50β1 = 6Δ 32 = 2 − (−5 + 7) = 0 ,80α2 = 020α 3 = −5120β3 = 0β2 = 7Получим: Δ 11 = 3 − (0 + 6) = 3,Таблица 13Запасыα1 = 020Δ 22 = 9 − (0 + 7) = 2,Δ 33 = 0 − (−5 + 0) = 5 ,f = 140 + 180 + 20 = 340 .Поскольку Δ i j ≥ 0 , условие окончания выполнено.
Оптимальный план перевозокисходной задачи содержится в найденном оптимальном плане:x11 = 0, x12 = 20, x 21 = 30, x 22 = 0, x 31 = 20, x32 = 0 .Значение x 23 = 50 свидетельствует о том, что в п. A2 остается неперевезенным груз в количестве 50 единиц.224Пример 4. Решить транспортную задачу, заданную матрицей перевозок (табл.
14),при дополнительном требовании полного вывоза груза из п. A2 .ПунктыA1A2ПотребностиB1Таблица 14Запасы251530/40B212341020 Так как в поставленной задаче нарушен баланс и суммарные запасы большесуммарных потребностей, то:1) введем фиктивный пункт потребления B3 с потребностью, равной 40 − 30 = 10 ;2) положим стоимости перевозки единицы груза в фиктивный пункт потребленияравными: c13 = 0 (из пункта A1 ), c 23 = M (из пункта A2 , из которого требуется обеспечить полный вывоз груза).В результате получим задачу, удовлетворяющую условию баланса.
Решим ее методом потенциалов. Начальный план перевозок найдем методом северо-западного угла(табл. 15). Последовательный переход от матрицы к матрице приведен в табл. 15 и 16.ПунктыB1A11A23Потребности10•10B224β1 = 1B30- 15⊕520M•⊕10 10Таблица 15Запасыα1 = 02515α2 = 240β3 = M − 2β2 = 2Получим: Δ13 = 0 − (0 + M − 2) = −M + 2 < 0 ⊗ (поскольку M – достаточнобольшое положительное число), Δ 21 = 3 − (2 + 1) = 0 . Для клетки (1,3) построим означенный цикл и найдем значение θ = min [ 10, 15 ] = 10 .
Выполним сдвиг по циклу на число θ = 10 .ПунктыB1A11A23Потребности10•10β1 = 1B224B3051520M10•10Таблица 16Запасыα1 = 02515α2 = 240β3 = 0β2 = 2Получим: Δ 21 = 3 − (2 + 1) = 0 , Δ 23 = M − (2 + 0) = M − 2 > 0 (поскольку M – достаточно большое положительное число). Условие окончания Δ ij ≥ 0 выполнено, решениеисходнойзадачисодержитсявоптимальномпланерешеннойзадачи:x11 = 10, x12 = 5, x 21 = 0, x 22 = 15 . Очевидно, из пункта A2 весь груз вывозится, а значение x13 = 10 свидетельствует об остающемся грузе в пункте A1 .225Пример 5. Решить транспортную задачу, заданную матрицей перевозок (табл. 17),при дополнительном требовании полного удовлетворения потребностей в п. B1 .ПунктыB1A1A2ПотребностиТаблица 17Запасы102040/30B212342515 Так как в поставленной задаче нарушен баланс и суммарные запасы меньшесуммарных потребностей, то:1) введем фиктивный пункт хранения A3 с запасами, равными 40 − 30 = 10 ;2) положим стоимости перевозки единицы груза из фиктивного пункта храненияравными: c11 = M (в пункт B1 , потребности которого должны быть полностью удовлетворены), c 21 = 0 (в пункт B 2 ).В результате получим задачу, удовлетворяющую условию баланса.
Решим ее методом потенциалов. Начальный план перевозок найдем методом минимального элемента(табл. 18).Таблица 18ПунктыB1A11A23A3MПотребности1015•25B22•4501015β1 = 1Запасы102010α1 = 0α2 = 2α 3 = −240β2 = 2Результаты нахождения начального плана перевозок методом минимального элемента:x 32 = min [10,15] = 10 , x 31 = 0 ; x11 = min [10, 25] = 10 , x12 = 0 ;x 21 = min [ 20, (25 − 10) ] = 15 ;x 22 = min [ (20 − 15), (15 − 10) ] = 5 .f = 10 + 45 + 20 = 75 . Далее получим: Δ 12 = 2 − (0 + 2) = 0 ,Его стоимостьΔ 31 = M − (−2 + 1) = M + 1 . Поскольку M – достаточно большое положительное число, тоусловие окончания Δ ij ≥ 0 выполнено, решение исходной задачи содержится в оптимальном плане решенной задачи: x11 = 10, x12 = 0, x 21 = 15, x 22 = 5 .
Очевидно, в пунктеB1 потребности полностью удовлетворены, а значение x 32 = 10 свидетельствует о том,что в п. B 2 на эту величину потребности не удовлетворены.226Занятие 10. МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХАЛГЕБРАИЧЕСКИХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИРассматривается проблема решения систем линейных алгебраических уравнений (СЛАУ), записываемых в видеAx = bили⎛ a11 " a1n ⎞ ⎛ x1 ⎞ ⎛ b1 ⎞⎜⎟⎜ ⎟ ⎜ ⎟⎜ # % # ⎟ ⎜ # ⎟ = ⎜ # ⎟,⎜a⎟⎜ ⎟ ⎜ ⎟⎝ n1 " ann ⎠ ⎝ x n ⎠ ⎝ bn ⎠где A = (ai j ) ∈ R n × n – действительная матрица размеров (n × n) , i , j – переменные,соответствующие номерам строк и столбцов (целые числа); b = (b1 ,..., bn )T ∈ R n –вектор-столбец размеров (n × 1) , x = ( x1 ,..., x n )T ∈ R n – вектор-столбец неизвестных,R n – n -мерное евклидово пространство, верхний индекс "T " здесь и далее обозначаетоперацию транспонирования.Требуется найти решение x ∗ = ( x ∗1 ,..., x ∗ n )T ∈ R n системы, подстановка кото-рого в систему приводит к верному равенству A x ∗ = b .А.
МЕТОД ПРОСТЫХ ИТЕРАЦИЙМетодика решения задачиШаг 1. Преобразовать систему Ax = b к виду x = αx + β одним из описанныхспособов.x (0 )Шаг 2. Задать начальное приближение решения x (0) произвольно или положить= β , а также малое положительное число ε (точность).
Положить k = 0 .Шаг 3. Вычислить следующее приближение x (k +1) по формулеx (k +1) = αx (k ) + β .Шаг 4. Если выполнено условие окончания x (k +1) − x (k ) < ε , процесс завершить и положить x ∗ ≅ x (k +1) . Иначе положить k = k + 1 и перейти к п.3.Пример 1. Методом простых итераций с точностью ε = 0,01 решить системулинейных алгебраических уравнений:2 x1 + 2 x 2 + 10 x 3 = 14 ,10 x1 + x 2 + x 3 = 12 ,2 x1 + 10 x 2 + x 3 = 13.227 1.
Так как 2 < 2 + 10 , 1 < 10 + 1 , 1 < 2 + 10 , условие преобладаниядиагональных элементов не выполняется. Переставим уравнения местами так, чтобывыполнялось условие преобладания диагональных элементов:10 x1 + x 2 + x 3 = 12 ,2 x1 + 10 x 2 + x 3 = 13,2 x1 + 2 x 2 + 10 x 3 = 14 .10 > 1 + 1 , 10 > 2 + 1 , 10 > 2 + 2 . Выразим из первого уравненияПолучаемx1 , из второго x 2 , из третьего x 3 :x1 = − 0,1 ⋅ x 2 − 0,1 ⋅ x 3 + 1,2 ,x 2 = − 0,2 ⋅ x1 − 0,1 ⋅ x 3 + 1,3 ,x 3 = − 0,2 ⋅ x1 − 0,2 ⋅ x 2 + 1,4 ;Заметим, чтоα1⎛ 0 − 0,1 − 0,1 ⎞⎛1,2 ⎞⎜⎟⎜ ⎟0 − 0,1 ⎟ ; β = ⎜ 1,3 ⎟ .α = ⎜ − 0,2⎜ − 0,2 − 0,2⎜1,4 ⎟0 ⎟⎠⎝⎝ ⎠= max { 0,2 ; 0,3 ; 0,4 } = 0,4 < 1 , следовательно, условие сходимости(теорема) выполнено.2. Зададим x(0 )⎛1,2 ⎞⎜ ⎟= β = ⎜ 1,3 ⎟ .
В поставленной задаче ε = 0,01 .⎜1,4 ⎟⎝ ⎠3. Выполним расчеты по формуле x (k +1) = αx (k ) + β :x (k +1)(k )⎛ 0 − 0,1 − 0,1 ⎞ ⎛⎜ x1 ⎞⎟ ⎛1,2 ⎞⎜⎟⎜ ⎟= ⎜ − 0,20 − 0,1 ⎟ ⋅ ⎜ x 2(k ) ⎟ + ⎜ 1,3 ⎟ , k = 0,1,... ,⎜ − 0,2 − 0,2⎟ ⎜⎜ x (k ) ⎟⎟ ⎜1,4 ⎟0⎝⎠ ⎝ 3 ⎠ ⎝ ⎠илиx1(k +1) = − 0,1x 2(k ) − 0,1x 3(k ) + 1,2 ;x 2(k +1) = − 0,2 x1(k ) − 0,1x 3(k ) + 1,3 ;k = 0,1,... ,x 3(k +1) = − 0,2 x1(k ) − 0,2 x 2(k ) + 1,4 ;до выполнения условия окончания и результаты занесем в табл.
1.Таблица 1kx1(k )x 2(k )x 3(k )x (k ) − x (k −1)0123451,20000,93001,01800,99461,00150,99961,30000,92001,02400,99341,00200,99951,40000,9001,03000,99161,00240,99930,50,130,03840,01080,0027< ε22814. Расчет закончен, поскольку условие окончания x (k +1) − x (k ) = 0,0027 < εвыполнено.Приближенное решение задачи: x ∗ ≅ (0,9996 ; 0,9995 ; 0,9993)T . Очевидно, точное решение: x ∗ = (1 ; 1 ; 1)T .Б.
МЕТОД ЗЕЙДЕЛЯМетодика решения задачиШаг 1. Преобразовать систему Ax = b к виду x = αx + β одним из описанныхспособов.Шаг 2. Задать начальное приближение решения x (0) произвольно или положитьx (0) = β , а также малое положительное число ε (точность). Положить k = 0 .Шаг 3. Произвести расчеты по формулеx1(k +1) = α11 x1(k ) + α12 x 2(k ) + α13 x 3(k ) + ... + α1n x n(k ) + β1 ,x 2(k +1) = α 21 x1(k +1) + α 22 x 2(k ) + α 23 x 3(k ) + ...
+ α 2n x n( k ) + β 2 ,(*)x 3(k +1) = α 31 x1( k +1) + α 32 x 2( k +1) + α 33 x 3( k ) + ... + α 3n x n( k ) + β 3 ,#x n( k +1) = α n1 x1(k +1) + α n 2 x 2( k +1) + α n3 x 3( k +1) + ... + α nn −1 x n(k−+11) + α nn x n(k ) + β n .(в каждое последующее уравнение подставляются значения неизвестных, полученныхиз предыдущих уравнений, что показано в записи стрелками)илиx (k +1) = Lx (k +1) + Ux (k ) + β ,где L,U являются разложениями матрицы α :⎛ 0⎜⎜ α 21L = ⎜ α 31⎜⎜"⎜⎝ α n10000α 320""α n2α n30⎞⎟0⎟" 0 ⎟,⎟" "⎟⎟" 0⎠""⎛ α11⎜⎜ 0U =⎜ 0⎜⎜"⎜⎝ 0α12α 220"0α13 " α1n ⎞⎟α 23 " α 2n ⎟α 33 " α 3n ⎟ .⎟" " " ⎟⎟0 " α nn ⎠и найти x (k +1) .Шаг 4.
Если выполнено условие окончания x (k +1) − x (k ) < ε , процесс завершить и положить x ∗ ≅ x (k +1) . Иначе положить k = k + 1 и перейти к п.3.229Пример 2. Методом Зейделя с точностью ε = 0,001 решить систему линейныхалгебраических уравнений:2 x1 + 2 x 2 + 10 x 3 = 14 ,10 x1 + x 2 + x 3 = 12 ,2 x1 + 10 x 2 + x 3 = 13 . 1. Приведем систему Ax = b к виду x = αx + β так же, как в примере 1:x1 = − 0,1 ⋅ x 2 − 0,1 ⋅ x 3 + 1,2 ,x 2 = − 0,2 ⋅ x1 − 0,1 ⋅ x 3 + 1,3 ,x 3 = − 0,2 ⋅ x1 − 0,2 ⋅ x 2 + 1,4 ;Так как α1⎛ 0 − 0,1 − 0,1 ⎞⎟⎜α = ⎜ − 0,20 − 0,1 ⎟ ;⎜ − 0,2 − 0,20 ⎟⎠⎝⎛1,2 ⎞⎜ ⎟β = ⎜ 1,3 ⎟ .⎜1,4 ⎟⎝ ⎠= max { 0,2 ; 0,3 ; 0,4 } = 0,4 < 1 , условие сходимости выполняется.2. Зададим x (0) = (1,2; 0; 0)T .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
