УМК (1013374), страница 35
Текст из файла (страница 35)
В методе минимальногоэлемента учитываются затраты на перевозку, следовательно, соответствующий начальный план, как правило, позволяет обеспечить меньшую суммарную стоимость, болееблизкую к оптимальной.В этом методе по формуле (*) последовательно заполняются клетки с наименьшейстоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью, то изних выбирается любая.МЕТОД ПОТЕНЦИАЛОВМетод обеспечивает улучшение начального плана перевозок. При этом происходитпереход от одного плана перевозок к другому (от одной матрицы перевозок к другой) дотех пор, пока уменьшение суммарной стоимости перевозок станет невозможным.Введем следующие понятия.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. 220Задачи с нарушенным балансом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 – достаточно большое положительное число. Однако следует заметить, что такие задачи могут не иметь решения, например, в следующих случаях:• суммарные запасы больше суммарных потребностей, требуется полностью вывезти груз из заданного пункта хранения, но запасы в нем превышают суммарные потребности;• суммарные запасы меньше суммарных потребностей, требуется полностью обеспечить потребности данного пункта потребления, но потребности в нем превышают суммарные запасы.221Пример 2.
Решить транспортную задачу, заданную матрицей перевозок (табл. 7).Таблица 7ПунктыЗапасыB1B2B312320A123340A2Потребности30302080/60 Поставленная задача является задачей с нарушенным балансом. Поскольку суммарные запасы меньше суммарных потребностей, то введем фиктивный пункт храненияA3 с запасами, равными 80 − 60 = 20 единиц груза. Стоимость перевозок из фиктивногопункта хранения положим равной нулю. В результате перейдем к задаче, в которой выполняется условие баланса.Начальный план перевозок найдем методом минимального элемента:x 31 = min [ 20, 30] = 20 ; x 32 = x 33 = 0 (в табл.
8 здесь и далее ставятся точки);x11 = min [ 20, (30 − 20) ] = 10 , x 21 = 0 ;x12 = min [ (20 − 10),30] = 10 , x13 = 0 ;x 22 = min [ 40,(30 − 10) ] = 20 ; x 23 = min[20, (40 − 20)] = 20 .Его стоимость составляет f = 10 + 20 + 60 + 60 = 150 .Решим полученную задачу методом потенциалов. Результаты решения приведеныв табл.
8 –10.ПунктыB1B2A11⊕ 102A22•3A30- 20300Потребностиβ1 = 1B310 20• ⊕303•320•200Таблица 8Запасы20402080α1 = 0α2 = 1α 3 = −1β3 = 2β2 = 2Δ 32 = 0 − (−1 + 2) = −1 ⊗ ,Получим: Δ 13 = 3 − (0 + 2) = 1,Δ 21 = 2 − (1 + 1) = 0,Δ 33 = 0 − (−1 + 2) = −1 . Для клетки (3,2) построим означенный цикл и найдем значениеθ = min [ 10, 20 ] = 10 . Выполним сдвиг по циклу на число θ = 10 .Таблица 9ПунктыЗапасыB1B2B3123α1 = 020A120••A22⊕ •3A30- 10300Потребностиβ1 = 120 10 ⊕303020•20β3 = 1β2 = 1222402080α2 = 2α 3 = −1Получим:f = 20 + 60 + 60 = 140 ;Δ 12 = 2 − (0 + 1) = 1,Δ 13 = 3 − (0 + 1) = 2,Δ 21 = 2 − (2 + 1) = −1 ⊗ ,Δ 33 = 0 − (−1 + 1) = 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
