УМК (1013374), страница 11
Текст из файла (страница 11)
Если ни одна из них не имеет целочисленного решения, то выбирается задача для приоритетного дальнейшего ветвленияпо установленному правилу: например приоритетному ветвлению подлежит та задача, вкоторой значение f ( x ) на оптимальном нецелочисленном решении максимально. Допус-( ) ( )тим, что f x 1∗ > f x 2∗ и задача ЗЛП-1 первой ветвится на ЗЛП-3 и ЗЛП-4, которые решаются симплекс-методом без учета требований на целочисленность с последующиманализом решений.
Если ни одна из задач ЗЛП-3 и ЗЛП-4 не имеет целочисленного решения, приступают к ветвлению задачи ЗЛП-2.Процесс ветвления продолжается до тех пор, пока не будет получено в одной изветвей целочисленное решение. Пусть задача ЗЛП-4 (рис. 2) имеет целочисленное решение. Обозначим f – значение функции на первом целочисленном решении: f = f x 4 ∗ .( )Соответствующее целочисленное решение включается в множество X ∗ возможных оптимальных решений исходной задачи. После того как найдено первое целочисленное решение, вопрос о дальнейшем ветвлении других задач решается на основании сравнениязначений f (x k ∗ ) на оптимальных нецелочисленных решениях в оставшихся ветвях созначением f .( )Если f x k ∗ ≤ f для всех оставшихся k , то расчет закончен.
Решениями исходнойзадачи являются те целочисленные решения x k ∗ , для которых f ( x k ∗ ) = f . Если62( )f x k ∗ > f , то соответствующая этому номеру k задача ветвится далее. Так, на рис. 2( )( )имеем f x 2 ∗ > f и f x 3 ∗ < f . Задача ЗЛП-2 подлежит ветвлению на ЗЛП-5 и ЗЛП-6, аЗЛП-3 не подлежит ветвлению. Задача ЗЛП-6 не имеет решения, так как множество допустимых решений пустое, и поэтому далее она не рассматривается. Задача ЗЛП-5 имеетнецелочисленное решение x 5∗ , f (x 5∗ ) . Если f x 5 ∗ < f , то решение задачи закончено и( )x ∗ = x 4∗ , f ( x ∗ ) = f .
В противном случае задача ЗЛП-5 ветвится дальше.Если в одной из задач получено целочисленное решение, то ее ветвление далее непроизводится. Если соответствующее значение целевой функции не меньше f , решениесчитается принадлежащим множеству X ∗ возможных оптимальных решений исходнойзадачи.
Если значение целевой функции меньше f , целочисленное решение не включается в множество X ∗ .Таким образом, ветвление какой-либо задачи заканчивается, если выполняется одно из условий, а именно: решение целочисленное; значение целевой функции данной задачи не больше f ; множество допустимых решений пустое.Если ветвление всех задач закончено, то в множестве X ∗ выбирается решение(решения), которому соответствует наибольшее значение целевой функции. Оно и является решением исходной задачи. Если множество X ∗ пустое, то исходная задача не имеет решения.Алгоритм определяет правила ветвления задач и правила окончания ветвления (нахождения границ), что соответствует его названию.З а м е ч а н и е. Распространенным методом решения задач линейного целочисленного программирования, опирающимся на сведение исходной задачи к решению последовательности задач линейного программирования без учета требования целочисленности, является метод Гомори [1,2].63Лекция 88.
ТРАНСПОРТНЫЕ ЗАДАЧИПОСТАНОВКА ЗАДАЧИПредположим, что в пунктах 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 .64Решение xi j , i = 1,2,..., m ; j = 1,2,..., n , системы называется планом перевозок.Требуется найти такой план перевозок, чтобы их суммарная стоимость была минимальной, т.е.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) производится улучшение начального плана, т.е.
последовательный переход отодного плана к другому, связанный с уменьшением суммарной стоимости перевозок.Процесс перехода от одного плана к другому завершается, когда уменьшение суммарнойстоимости перевозок станет невозможным.65МЕТОДЫ НАХОЖДЕНИЯ НАЧАЛЬНОГО ПЛАНА ПЕРЕВОЗОККлетки матрицы перевозок, где x ij > 0 , называются базисными, а остальные, гдеx i j = 0 , – свободными.
В матрице имеется (m + n − 1) базисных клеток. Их число совпа-дает с числом независимых уравнений-ограничений.Значение x ij в матрице перевозок находится по формуле⎧ остаток груза в пункте Ai ,x i j = min ⎨⎩ неудовлетворенные потребности в пункте B j .(*)Значение x i j = 0 в свободной клетке не пишется явно, а вместо этого в ней ставится точка.А. Метод северо-западного углаВычисления осуществляются по формуле (*), начиная с элемента x11 , стоящего всеверо-западном углу матрицы перевозок.Пример 1. Найти начальный план перевозок в транспортной задаче, заданной матрицей перевозок (табл.
2).Таблица 2ЗапасыПунктыB1B2B323420A11010•12540A2•1030Потребности10203060 Начнем с северо-западного угла, т.е. x11 = min [ 20, 10 ] = 10 . Тогда в пункте B1потребности удовлетворены и, следовательно, x 21 = 0 (в табл. 2 ставится точка). Первыйстолбец выбывает из рассмотрения.Продолжим с северо-западного угла, т.е. x12 = min [ (20 − 10), 20 ] = min[10, 20] = 10 .Тогда запасы в пункте A1 исчерпаны и x13 = 0 (в табл.
2 ставится точка). При этом первая строка выбывает из рассмотрения.Продолжим с северо-западного угла: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 = 30с суммарной стоимостью f = 2 ⋅ 10 + 3 ⋅ 10 + 4 ⋅ 0 + 1 ⋅ 0 + 2 ⋅ 10 + 5 ⋅ 30 = 220 . Число базисных клеток, очевидно, составит m + n − 1 = 2 + 3 − 1 = 4 .66З а м е ч а н и е.
При нахождении начального плана перевозок возможен случайвырождения, когда в результате вычислений значения x i j получается, что потребности впункте B j удовлетворены, а запасы в пункте Ai исчерпаны. Тогда одновременно из рассмотрения выбывают строка и столбец. В этом случае рекомендуется поставить в одну изклеток выбывающих строки и столбца (лучше в клетку с наименьшей стоимостью) такназываемый базисный нуль. Клетка с базисным нулем считается базисной (в ней пишется0 ), а общее число базисных клеток остается равным (m + n − 1) .Пример 2. Методом северо-западного угла найти начальный план перевозок втранспортной задаче, заданной матрицей перевозок (табл.
3).ПунктыB1A11A24A31Потребности30••30B2212B33200•2015Таблица 3Запасы504060150B4•5•4010502•105050□ Начнем заполнение таблицы с северо-западного угла:x11 = min [ 50, 30 ] = 30 ;x 21 = x 31 = 0 (ставится точка).Далее снова продолжим с северо-западного угла:x12 = min [ (50 − 30), 20 ] = min [ 20, 20 ] = 20 (это случай вырождения, так как выбываютпервая строка и второй столбец: x13 = x14 = x 22 = x 32 = 0 .Базисный нуль поставим в клетку (2,2) с наименьшей стоимостью, равнойmin [ 3; 5; 1; 2 ] = 1 . В остальных выбывающих клетках ставятся точки.Продолжим с северо-западного угла:x 23 = min [ 40, 50 ] = 40 ; x 24 = 0 (ставится точка).Из рассмотрения выбывает вторая строка.Продолжим с северо-западного угла:x 33 = min [ 60, (50 − 40) ] = 10 иx 34 = min [ (60 − 10), 50 ] = 50 .Таким образом, получен начальный план перевозокx11 = 30,x12 = 20,x13 = x14 = 0 ,x 21 = x 22 = 0,x 23 = 40,x 24 = 0 ,x 31 = x 32 = 0,x 33 = 10,x 34 = 50с суммарной стоимостьюf = 30 + 40 + 40 + 50 + 500 = 660 .Число базисных клетокm + n − 1 = 3 + 4 − 1 = 6 .сучетом67базисногонуля,очевидно,составитПример 3.
Методом северо-западного угла найти начальный план перевозок втранспортной задаче, заданной матрицей перевозок (табл. 4).ПунктыB1A13A22A33A42B240•••40ПотребностиB3B44•5•1530••30610••1011325B5010••10361•10501060410Таблица 4Запасы40505010150 Решим аналогично примеру 2:а) x11 = min [ 40, 40 ] = 40 (случай вырождения);x12 = x13 = x14 = x15 = x 21 = x 31 = x 41 = 0 (базисный нуль ставится в клетку(1,4) с наименьшей стоимостью, а в остальные ставятся точки);б) x 22 = min [ 50, 30 ] = 30 , x 32 = x 42 = 0 (ставятся точки);в) x 23 = min [ (50 − 30), 10 ] = 10, x 33 = x 43 = 0 (ставятся точки);г) x 24 = min [ (50 − 30 − 10), 10 ] = min [ 10, 10 ] = 10 (случай вырождения);x 25 = 0 (ставится базисный нуль, так как это клетка с наименьшей стоимостью среди выбывающих клеток), x 34 = x 44 = 0 (ставятся точки);д) x 35 = min [ 50, 60 ] = 50 ;е) x 45 = min [ 10, (60 − 50) ] = 10 .Таким образом, начальный план перевозок содержит два базисных нуля, следовательно, число базисных клеток составит m + n − 1 = 4 + 5 − 1 = 8 .Б.
Метод минимального элементаПолучаемый методом северо-западного угла начальный план перевозок не зависитот их стоимости и поэтому в общем случае далек от наилучшего. В методе минимальногоэлемента учитываются затраты на перевозку, следовательно, соответствующий начальный план, как правило, позволяет обеспечить меньшую суммарную стоимость, болееблизкую к оптимальной.В этом методе по формуле (*) последовательно заполняются клетки с наименьшейстоимостью перевозок. Если имеется несколько клеток с наименьшей стоимостью, то изних выбирается любая.Пример 4. Найти начальный план перевозок в транспортной задаче, заданной матрицей перевозок (табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
