УМК (1013374), страница 12
Текст из файла (страница 12)
5).ПунктыA1A2ПотребностиB1B2B32•3•41101022020568201030Таблица 5Запасы204060 Заполним клетку с наименьшей стоимостью, равной 1:x 21 = min [ 40, 10 ] = 10 .Тогда потребности в пункте B1 удовлетворены и x11 = 0 (в табл. 5 ставится точка), первый столбец выбывает из рассмотрения.Из оставшихся клеток найдем клетку с наименьшей стоимостью и заполним ее:x 22 = min [ (40 − 10),20 ] = 20 . Тогда x12 = 0 (в табл.
5 ставится точка), потребности впункте B 2 удовлетворены и выбывает второй столбец.Из оставшихся двух клеток заполним клетку с наименьшей стоимостью:x13 = min [ 20, 30 ] = 20 . Тогда первая строка выбывает (запасы в пункте A1 исчерпаны)и x 23 = min [ (40 − 30), (30 − 20) ] = 10 .Таким образом, получен начальный план перевозокx11 = 0,x12 = 0,x13 = 20 ,x 21 = 10,x 22 = 20,x 23 = 10с суммарной стоимостьюf = 2 ⋅ 0 + 3 ⋅ 0 + 4 ⋅ 20 + 1 ⋅ 10 + 2 ⋅ 20 + 5 ⋅ 10 = 180 .Заметим, что она меньше полученной с помощью метода северо-западного угла(см.
пример 1). Число базисных клеток, очевидно, составляет m + n − 1 = 2 + 3 − 1 = 4 . МЕТОД ПОТЕНЦИАЛОВМетод обеспечивает улучшение начального плана перевозок. При этом происходитпереход от одного плана перевозок к другому (от одной матрицы перевозок к другой) дотех пор, пока уменьшение суммарной стоимости перевозок станет невозможным.Введем следующие понятия.1. Цикл – замкнутая ломаная с вершинами в клетках и звеньями, расположеннымивдоль строк и столбцов матрицы перевозок. В каждой вершине встречаются два звена,причем одно из них располагается по строке, а другое – по столбцу. Число вершин циклачетно.
Циклом может быть самопересекающаяся ломаная, но точки ее самопересеченияне могут быть вершинами цикла.2. Означенный цикл – цикл, в котором некоторой вершине приписан знак «+», а затем при обходе цикла в каком-либо направлении знаки чередуются.3. Сдвиг по циклу на число θ ≥ 0 . При этом значения x i j , стоящие в положительных вершинах цикла, увеличиваются на число θ , а стоящие в отрицательных вершинах,уменьшаются на число θ .4. Потенциалы – числа α i , i = 1,2,..., m; β j , j = 1,2,..., n . Каждому пункту храненияAi ставится в соответствие число α i , пункту потребления B j – число β j .69АлгоритмШаг 1. Найти начальный план перевозок методом северо-западного угла или методом минимального элемента.Шаг 2.
Для каждой базисной клетки составить уравнениеα i + β j = ci j .Так как эти уравнения образуют систему (m + n − 1) уравнений с (m + n) неизвестными(она имеет бесконечное множество решений), то для определенности следует положитьα1 = 0 . Тогда все остальные потенциалы находятся однозначно.Шаг 3. Для каждой свободной клетки вычислить относительные оценки:Δ i j = ci j − (α i + β j ) .Шаг 4. Проанализировать относительные оценки:а) если все относительные оценки неотрицательные, т.е. выполняется условиеΔi j ≥ 0 ,то задача решена, и следует выписать полученный оптимальный план перевозокиз последней матрицы, подсчитать его стоимость;б) если среди оценок Δ i j есть отрицательные, найти среди них наименьшую отрицательную оценку и пометить знаком ⊗ .Шаг 5. Для свободной клетки (i, j ) с выбранной оценкой Δ i j , помеченной ⊗ , построить означенный цикл.
Все его вершины, кроме расположенной в клетке (i, j ) , должны находиться в базисных клетках. Свободная клетка берется со знаком «+».Шаг 6. Выполнить сдвиг по построенному на шаге 5 циклу на величину θ , равнуюнаименьшему из чисел, стоящих в отрицательных вершинах. При этом числа, стоящиев положительных вершинах, увеличить на θ , а числа, стоящие в отрицательных вершинах, уменьшить на θ .Если наименьшее значение θ достигается в нескольких отрицательных вершинахцикла, то при сдвиге следует поставить базисный нуль во всех таких вершинах, кромеодной.
Тогда число базисных клеток сохранится и будет равно (m + n − 1) , что необходимо проверять при расчетах. Базисный нуль рекомендуется ставить в клетку (клетки)с наименьшей стоимостью перевозок.Элементы матрицы, не входящие в цикл, остаются без изменений.Перейти к шагу 2.З а м е ч а н и я.1. При решении задач может возникнуть ситуация, когда θ = 0 .
Тогда при сдвигесвободная клетка становится базисной (точка заменяется на базисный нуль).2. Значения суммарной стоимости перевозок при переходе от одной матрицы кдругой связаны соотношениемf k +1 = f k + θ ⋅ Δ i j ,где k – номер итерации, f k – текущее значение суммарной стоимости перевозок, значения θ и Δ i j находятся на шагах 3 и 6 соответственно.70Пример 5. Решить транспортную задачу (табл. 6).ПунктыB1A11A23A31Потребности- 30•⊕ •30β1 = 1B210 ⊕3030 70224Таблица 6Запасы403030100α1 = 0α2 = 0α3 = 2β2 = 2 Решим задачу согласно алгоритму.1.
Найдем начальный план перевозок методом северо-западного угла:x11 = min [ 40, 30 ] = 30 ; x 21 = x 31 = 0 (в табл. 6 ставятся точки);x12 = min [ (40 − 30), 70 ] = 10 ,x 22 = min [ 30, (70 − 10) ] = 30 ,x 32 = min [ 30, (70 − 10 − 30) ] = 30 .Его стоимость f = 30 + 20 + 60 + 120 = 230 .21. Найдем потенциалы, составляя для каждой базисной клетки уравнениеα i + β j = cij .Положим α1 = 0 . Тогда для базисных клеток (1,1) и (1,2) получимα1 + β1 = 1 ,α1 + β 2 = 2 .Отсюда β1 = 1, β 2 = 2 .Далее для базисных клеток (2,2) и (3,2) имеемα 2 + β2 = 2 ,α3 + β2 = 4 .Отсюда α 2 = 0, α 3 = 2 .31.
Для каждой свободной клетки вычислим относительные оценки:Δ 21 = c 21 − (α 2 + β1 ) = 3 − (0 + 1) = 2 > 0 ,Δ 31 = c31 − (α 3 + β1 ) = 1 − (2 + 1) = −2 < 0 . ⊗41. Проанализируем относительные оценки. Так как условие окончания Δ i j ≥ 0не выполнено, то найдем наименьшую отрицательную оценку: Δ 31 .7151. Для клетки (3,1) построим означенный цикл. Все его вершины, кроме данной,находятся в базисных клетках. Знак «+» ставится в свободной клетке (3,1).61. Найдем число θ = min [ 30, 30 ] = 30 , равное наименьшему из чисел, стоящих вотрицательных вершинах цикла. Выполним сдвиг по циклу на число θ = 30 : числа,стоящие в положительных вершинах, увеличиваются на 30, а числа, стоящие в отрицательных вершинах, уменьшаются на 30. Так как наименьшее значение θ = 30 достигаетсяв двух отрицательных вершинах, то в клетку (3,2) ставится точка, а в клетку (1,1) с наименьшей стоимостью – базисный нуль.
Элементы матрицы, не входящие в цикл, остаются без изменений. Результат сдвига представлен в табл. 7. Перейдем к шагу 2.ПунктыB1A11A23A31Потребности0•3030B224030•7024β1 = 1Таблица 7Запасы40α1 = 030α2 = 030α3 = 0100β2 = 222. Найдем потенциалы. Для базисных клеток (1,1) и (1,2) получимα1 + β1 = 1 ,α1 + β 2 = 2 .Поскольку α1 = 0 , то β1 = 1, β 2 = 2 .Для базисной клетки (2,2) имеем α 2 + β 2 = 2 , откуда α 2 = 0 .
Для базисной клетки (3, 1) получим α 3 + β1 = 1 , отсюда α 3 = 0 .32. Для каждой свободной клетки вычислим относительные оценки:Δ 21 = c 21 − (α 2 + β1 ) = 3 − (0 + 1) = 2 > 0 ,Δ 32 = c32 − (α 3 + β 2 ) = 4 − (0 + 2) = 2 > 0 .42. Поскольку условие окончания Δ i j ≥ 0 выполнено, задача решена. Оптимальный план перевозокx11 = 0,x12 = 40,x 21 = 0,x 22 = 30 ,x 31 = 30,имеет суммарную стоимостьx 32 = 0f = 80 + 60 + 30 = 170 . Согласно п.2 замечаний это жезначение может быть найдено по формуле f 1 = f 0 + θ ⋅ Δ 31 = 230 + 30 ⋅ (−2) = 170 . 72З а м е ч а н и я.1.
Задачи с нарушенным балансом решаются путем сведения к задачам, удовлетворяющим условию баланса. Далее применяется метод потенциалов. Оптимальный планперевозок новой задачи содержит оптимальный план перевозок исходной задачи.Здесь могут быть два случая.Первый случай. Суммарные запасы больше суммарных потребностей, т.е.mni =1j =1∑ ai > ∑ b j .В этом случае следует:1) ввести фиктивный пункт потребления B n +1 с потребностьюbn +1 =mni =1j =1∑ ai − ∑ b j ;2) положить стоимости перевозок единицы груза в фиктивный пункт потребленияравными нулю: ci , n +1 = 0, i = 1,2,..., m .Второй случай. Суммарные запасы меньше суммарных потребностей, т.е.mni =1j =1∑ ai < ∑ b j .В данном случае следует:1) ввести фиктивный пункт хранения Am +1 с запасом груза, равнымam + 1 =nmj =1i =1∑ b j − ∑ ai ;2) положить стоимости перевозок единицы груза из фиктивного пункта храненияравными нулю: cm +1, j = 0, j = 1,2,..., n .2.
В задачах с нарушенным балансом может встречаться дополнительное требование к оптимальному плану перевозок. В первом случае: полностью вывезти продукциюиз заданного пункта хранения, а во втором – полностью удовлетворить потребности заданного пункта потребления. В обоих случаях действия при решении аналогичны описанным в п.1, только стоимости перевозок единицы груза для заданных пунктов следуетположить равными M , где M – достаточно большое положительное число. Однако следует заметить, что такие задачи могут не иметь решения, например, в следующих случаях:• суммарные запасы больше суммарных потребностей, требуется полностью вывезти груз из заданного пункта хранения, но запасы в нем превышают суммарные потребности;• суммарные запасы меньше суммарных потребностей, требуется полностью обеспечить потребности данного пункта потребления, но потребности в нем превышают суммарные запасы.73Лекция 9Раздел II.
ЧИСЛЕННЫЕ МЕТОДЫ1. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХАЛГЕБРАИЧЕСКИХ УРАВНЕНИЙПОСТАНОВКА ЗАДАЧИРассматривается проблема решения систем линейных алгебраических уравнений(СЛАУ), записываемых в виде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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
