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