semopt9 (Практические занятия)

Занятие 9. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧПОСТАНОВКА ЗАДАЧИПредположим, что в пунктах A1 , A2 ,..., Am хранится однородный груз в количествеa1 , a2 ,..., am единиц. Этот груз следует доставить в n заданных пунктов назначенияB1 , B 2 ,..., B n , причем в каждый из них требуется завезти соответственно b1 , b2 ,..., bn единиц этого груза. Обозначим через cij стоимость перевозки единицы груза из пункта Aiв пункт B j .Транспортные задачи делятся на две группы.1. Задачи, удовлетворяющие условию балансаmni =1j =1∑ ai = ∑ b j , означающему, что об-щий запас груза на всех пунктах хранения равен суммарной потребности всех пунктовназначения.2.

Задачи с нарушенным балансом, среди которых выделяются два случая:a)б)mni =1j =1mn∑ ai > ∑ b j (суммарные запасы больше суммарных потребностей);∑ ai <i =1∑bj(суммарные запасы меньше суммарных потребностей).j =1Рассмотрим формализацию транспортной задачи, удовлетворяющей условию баланса.Обозначим x ij – количество груза, перевозимого из пункта Ai в пункт B j . Тогдасуммарная стоимость перевозок имеет видf (x ) =mn∑ ∑ ci j ⋅ x i j .i = 1 j =1Ограничения представляются уравнениями вывоза и привоза груза:x i1 + x i 2 + ... + x in = ai ,x1 j + x 2 j + ... + x m j = b j ,x i j ≥ 0 , i = 1,2,..., m ;i = 1,2,..., m ;j = 1,2,..., n ;j = 1,2,..., n .Первое уравнение означает, что из каждого пункта хранения Ai вывозится весьгруз, а второе уравнение описывает факт удовлетворения всех потребностей в пункте B j .Условие неотрицательности свидетельствует о том, что груз либо вывозится из пункта Aiв пункт B j , и тогда x i j > 0 , либо нет, и в этом случае x i j = 0 .Решение xi j , i = 1,2,..., m ; j = 1,2,..., n , системы называется планом перевозок.215Требуется найти такой план перевозок, чтобы их суммарная стоимость была минимальной, т.е.f (x ) =mn∑ ∑ ci j ⋅ x i j→ min .i = 1 j =1Условия задачи удобно записывать в виде матрицы перевозок (табл.

1).Таблица 1ПунктыА1А2B2B1Bj...Bn...c11c12c1 jc1nа1c21c22c2 jc2 nа2#Аi#ci 1ci jci 2cinai#AmПотребностиЗапасы#cm1cm 2b1cm jb2cmnbj......ambnСуммаЗаметим, что с помощью линейных преобразований можно показать зависимостьодного из уравнений в системе от остальных, т.е. в этой системе имеется (m + n − 1) независимых уравнений. Лишнее уравнение может быть исключено из системы уравненийограничений.В матрице перевозок хранится текущий план перевозок x i j , i = 1,2,..., m ;j = 1,2,..., n .Стратегия решения задачиТак как поставленная задача является частным случаем задачи линейного программирования, то стратегия решения аналогична:1) находится начальный план перевозок;2) производится улучшение начального плана, т.е. последовательный переход отодного плана к другому, связанный с уменьшением суммарной стоимости перевозок.Процесс перехода от одного плана к другому завершается, когда уменьшение суммарнойстоимости перевозок станет невозможным.216МЕТОДЫ НАХОЖДЕНИЯ НАЧАЛЬНОГО ПЛАНА ПЕРЕВОЗОККлетки матрицы перевозок, где x ij > 0 , называются базисными, а остальные, гдеx i j = 0 , – свободными.

В матрице имеется (m + n − 1) базисных клеток. Их число совпа-дает с числом независимых уравнений-ограничений.Значение x ij в матрице перевозок находится по формуле⎧ остаток груза в пункте Ai ,x i j = min ⎨⎩ неудовлетворенные потребности в пункте B j .(*)Значение x i j = 0 в свободной клетке не пишется явно, а вместо этого в ней ставится точка.А. Метод северо-западного углаВычисления осуществляются по формуле (*), начиная с элемента x11 , стоящего всеверо-западном углу матрицы перевозок.З а м е ч а н и е. При нахождении начального плана перевозок возможен случайвырождения, когда в результате вычислений значения x i j получается, что потребности впункте B j удовлетворены, а запасы в пункте Ai исчерпаны.

Тогда одновременно из рассмотрения выбывают строка и столбец. В этом случае рекомендуется поставить в одну изклеток выбывающих строки и столбца (лучше в клетку с наименьшей стоимостью) такназываемый базисный нуль. Клетка с базисным нулем считается базисной (в ней пишется0), а общее число базисных клеток остается равным (m + n − 1) .Б. Метод минимального элементаПолучаемый методом северо-западного угла начальный план перевозок не зависитот их стоимости и поэтому в общем случае далек от наилучшего.

В методе минимальногоэлемента учитываются затраты на перевозку, следовательно, соответствующий начальный план, как правило, позволяет обеспечить меньшую суммарную стоимость, болееблизкую к оптимальной.В этом методе по формуле (*) последовательно заполняются клетки с наименьшейстоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью, то изних выбирается любая.МЕТОД ПОТЕНЦИАЛОВМетод обеспечивает улучшение начального плана перевозок. При этом происходитпереход от одного плана перевозок к другому (от одной матрицы перевозок к другой) дотех пор, пока уменьшение суммарной стоимости перевозок станет невозможным.Введем следующие понятия.1. Цикл – замкнутая ломаная с вершинами в клетках и звеньями, расположеннымивдоль строк и столбцов матрицы перевозок.

В каждой вершине встречаются два звена,причем одно из них располагается по строке, а другое – по столбцу. Число вершин цикла217четно. Циклом может быть самопересекающаяся ломаная, но точки ее самопересеченияне могут быть вершинами цикла.2. Означенный цикл – цикл, в котором некоторой вершине приписан знак «+», а затем при обходе цикла в каком-либо направлении знаки чередуются.3. Сдвиг по циклу на число θ ≥ 0 .

При этом значения x i j , стоящие в положительных вершинах цикла, увеличиваются на число θ , а стоящие в отрицательных вершинах,уменьшаются на число θ .4. Потенциалы – числа α i , i = 1,2,..., m; β j , j = 1,2,..., n . Каждому пункту храненияAi ставится в соответствие число α i , пункту потребления B j – число β j .АлгоритмШаг 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) , что необхо-218димо проверять при расчетах. Базисный нуль рекомендуется ставить в клетку (клетки)с наименьшей стоимостью перевозок.Элементы матрицы, не входящие в цикл, остаются без изменений.Перейти к шагу 2.З а м е ч а н и я.1. При решении задач может возникнуть ситуация, когда θ = 0 . Тогда при сдвигесвободная клетка становится базисной (точка заменяется на базисный нуль).2. Значения суммарной стоимости перевозок при переходе от одной матрицы кдругой связаны соотношениемf k +1 = f k + θ ⋅ Δ i j ,где k – номер итерации, f k – текущее значение суммарной стоимости перевозок, значения θ и Δ i j находятся на шагах 3 и 6 соответственно.Пример 1.

Решить транспортную задачу, заданную матрицей перевозок (табл. 2).Таблица 2ЗапасыПунктыB1B2B323420A112540A2Потребности10203060† Решим задачу согласно алгоритму.Начальный план перевозок методом северо-западного угла найден в табл. 3.Таблица 3ЗапасыПунктыB1B2B323420A11010•12540A2•1030Потребности10203060Начнем с северо-западного угла, т.е. x11 = min [ 20, 10 ] = 10 . Тогда в пункте B1потребности удовлетворены и, следовательно, x 21 = 0 (в табл. 3 ставится точка).

Первыйстолбец выбывает из рассмотрения.Продолжим с северо-западного угла, т.е. x12 = min [ (20 − 10), 20 ] = min[10, 20] = 10 .Тогда запасы в пункте A1 исчерпаны и x13 = 0 (в табл. 3 ставится точка). При этом первая строка выбывает из рассмотрения.Продолжим с северо-западного угла:x 22 = min [ 40, (20 − 10) ] = min [ 40, 10 ] = 10 .Потребности в пункте B 2 удовлетворены, и второй столбец выбывает из рассмотрения.Заполним последний элемент, находящийся в северо-западном углу:x 23 = min [ (40 − 10), 30 ] = 30 . Таким образом, получен начальный план перевозок:x11 = 10,x12 = 10,x13 = 0 ,x 21 = 0,x 22 = 10,x 23 = 30219с суммарной стоимостью f = 2 ⋅ 10 + 3 ⋅ 10 + 4 ⋅ 0 + 1 ⋅ 0 + 2 ⋅ 10 + 5 ⋅ 30 = 220 .

Число базисных клеток, очевидно, составит m + n − 1 = 2 + 3 − 1 = 4 .Последовательный переход от матрицы к матрице отображен в табл. 4 – 6.ПунктыB1A12A2110•10ПотребностиB232- 10⊕ 1020B345β2 = 3β1 = 2• ⊕30 30Таблица 4Запасы204060α1 = 0α 2 = −1β3 = 6Получим: f = 20 + 30 + 20 + 150 = 220 ; Δ13 = c13 − (α1 + β 3 ) = 4 − (0 + 6) = −2 < 0 ;Δ 21 = c 21 − (α 2 + β1 ) = 1 − (−1 + 2) = 0 . Для клетки (1,3) построим означенный цикл инайдем значение θ = min [ 10, 30 ] = 10 . Выполним сдвиг по циклу на число 10.ПунктыA1A2ПотребностиB12- 101⊕•10B2B33•4220205β2 = 1β1 = 210 ⊕20 30Таблица 5Запасыα1 = 02040α2 = 160β3 = 4Получим: f = 20 + 40 + 40 + 100 = 200; Δ12 = 3 − (0 + 1) = 2 > 0 , Δ 21 = 1 − (1 + 2) = −2 < 0 .Для клетки (2,1) построим означенный цикл и найдем значение θ = min [ 10, 20 ] = 10 .Выполним сдвиг по циклу на число 10.ПунктыB1B2B3A12•3•4A211010220205Потребностиβ1 = 0β2 = 1201030Таблица 6Запасы204060α1 = 0α2 = 1β3 = 4Получим: f = 80 + 10 + 40 + 50 = 180 ; Δ11 = 2 − (0 + 0) = 2 > 0 ;Δ12 = 3 − (0 + 1) = 2 > 0 .Условие окончания Δ i j ≥ 0 выполнено, получен оптимальный план перевозокx11 = x12 = 0,x13 = 20 , x 21 = 10, x 22 = 20, x 23 = 10с суммарной стоимостью 180.