lopt8 (1013502), страница 2
Текст из файла (страница 2)
Для свободной клетки (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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
