УМК (1013374), страница 34
Текст из файла (страница 34)
Осуществить ветвление задачи ЗЛП- k . Для этого выбрать нецелочисленную координату x k∗j по установленному правилу и сформировать:[ ][ ]а) два дополнительных ограничения: x j ≤ x kj ∗ , x j ≥ x kj ∗ + 1 ;б) две задачи ЗЛП- 2k + i , i = 1,2 :ЗЛП- 2k + 1 , получаемую в результате добавления к задаче ЗЛП-k дополни-[ ]тельного ограничения x j ≤ x kj ∗ ;ЗЛП- 2k + 2 , получаемую в результате добавления к задаче ЗЛП-k дополни-[ ]тельного ограничения x j ≥ x kj ∗ + 1 .Положить i = 1 и перейти к шагу 4.Шаг 4. Решить задачу ЗЛП- 2k + i :210а) если множество допустимых решений задачи пустое, то исключить задачу израссмотрения и перейти к шагу 6;б) если множество допустимых решений задачи не пустое, определить()x 2k + i ∗ , f x 2k + i ∗ и перейти к шагу 5.Шаг 5.
Проверить решение x 2k +i ∗ на целочисленность:а) если решение x 2k +i ∗ целочисленное и получено первым при ветвлении задач,имеющих нецелочисленное решение, положить f = f ( x 2k + i ∗ ) и включить решение x 2k +i ∗ во множество X ∗ возможных оптимальных решений исходнойзадачи.Сравнить значения f (x k ∗ ), k ∈ J , с f для нецелочисленных решений, полученных раньше, чем первое целочисленное решение:• если f ( x k ∗ ) ≤ f , исключить номер k из множества J ;• если f ( x k ∗ ) > f , оставить задачу с номером k во множестве J для дальнейшего ветвления;Перейти к шагу 6;б) еслирешениеx 2k +i ∗целочисленное,значениеужеfнайденоиf ( x 2k + i ∗ ) ≥ f , то включить решение x 2k +i ∗ во множество X ∗ возможных оп-тимальных решений исходной задачи.
Если f ( x 2k + i ∗ ) < f , не включать решение x 2k +i ∗ во множество X ∗ и перейти к шагу 6;в) если решение x 2k +i ∗ нецелочисленное и значение f еще не найдено, включитьномер 2k + i во множество J и перейти к шагу 6;г) если решениеx 2k +i ∗нецелочисленное, значениеfуже найдено иf ( x 2k + i ∗ ) > f , то включить номер 2k + i в множество J.
В противном случаеисключить номер 2k + i из рассмотрения и перейти к шагу 6;Шаг 6. Проверить условие i ≤ 2 :а) если i < 2 , положить i = 2 и перейти к шагу 4;б) если i = 2 , перейти к шагу 2.Шаг 7. В множестве X ∗ выбрать решение (решения), которому соответствует наибольшее значение целевой функции.
Оно является решением x ∗ исходной задачи. Еслимножество X ∗ пустое, то исходная задача не имеет решения.Пример 1. Найти оптимальное решение задачиf (x ) = x1 + 2 x 2 → max,x1 + x 2 ≤ 4,x 2 ≤ 2,8 , x1 , x 2 ≥ 0, целые. 1. Положим k = 0 . Решим ЗЛП-0, т.е. исходную задачу без учета требованияцелочисленности, графически. Как следует из рис.
1, а, максимум достигается в точкеA = x 0∗ = (1,2; 2,8)T , f ( x 0∗ ) = 6,8. Решение не является целочисленным. Включим номерk = 0 во множество J и перейдем к шагу 2.2112 0 . Так как k = 0 , выберем для ветвления задачу ЗЛП-0 , исключим k = 0 измножества J и перейдем к шагу 3.3 0 . Осуществим ветвление задачи ЗЛП-0. Выберем нецелочисленную координатус наименьшим индексом: x10∗ = 1,2 . Сформируем:а) дополнительные ограничения: x1 ≤ [1,2] = 1 , x1 ≥ [1,2] + 1 = 2 ;б) две задачи ЗЛП- 2k + i , k = 0 ; i = 1,2 :ЗЛП-1ЗЛП-2f (x ) = x1 + 2 x 2 → max,f (x ) = x1 + 2 x 2 → max,x1 + x 2 ≤ 4,x1 + x 2 ≤ 4,x 2 ≤ 2,8 ,x 2 ≤ 2,8 ,x1 , x 2 ≥ 0, x1 ≤ 1 ;x1 , x 2 ≥ 0, x1 ≥ 2 .x2x2ЗЛП-04x 2 = 2,8A321x 2 = 2,82x1 + x 2 = 41∇f0x1∇f243x1012аx204x 2 = 2,83x 2 = 2,82Dx2 = 2x1 + x 2 = 41∇f1x1 = 13C2x1 + x 2 = 4∇f24ЗЛП-3x2x1 = 243бЗЛП-21ЗЛП-1B3x1 + x 2 = 41x1 = 1434x1в0123г2124x1ЗЛП-4x2x1 = 14x2 = 33x 2 = 2,82X =∅10∇f123x14дРис. 1x1 + x 2 = 4Положим i = 1 и перейдем к шагу 4.4 0 .
Решим задачу ЗЛП-1 графически (рис. 1, б). Максимум достигается в точкеx1∗ = B = (1; 2,8) T , f (x 1∗ ) = 6,6 . Перейдем к шагу 5.5 0 . Решение x 1∗ – нецелочисленное, и значение f еще не найдено. Поэтомувключим номер k = 1 во множество J и перейдем к шагу 6.6 0 . Проверим выполнение условия i ≤ 2 : i = 1 < 2 .
Положим i = 2 и перейдемк шагу 4.41 . Решим задачу ЗЛП-2 графически (рис. 1,в). Получим решение в точкеx 2∗ = C = (2; 2) T , f (x 2∗ ) = 6 . Перейдем к шагу 5.51 . Решение x 2∗ – первое целочисленное. Положим f = f ( x 2 ∗ ) = 6. Включимрешениеx 2∗во множествоX ∗ . Сравним значениеf (x 1∗ )сf . Так какf (x1∗ ) = 6,6 > f = 6 , оставим задачу ЗЛП-1 для дальнейшего ветвления и перейдем к шагу 6.61 . Проверим выполнение условия i ≤ 2 : i = 2 . Перейдем к шагу 2.21 . Имеем k = 1 и J = {1} ≠ ∅ . Выберем задачу ЗЛП-1 для ветвления. Исключимk = 1 из множества J и перейдем к шагу 3.31 .
Осуществим ветвление задачи ЗЛП-1. Выберем нецелочисленную координатус наименьшим индексом: x 12∗ = 2,8 . Сформируем:а) дополнительные ограничения: x 2 ≤ [ 2,8] = 2 , x 2 ≥ [2,8] + 1 = 3 ;б) две задачи ЗЛП- 2k + i , k = 1 ; i = 1,2 :ЗЛП-3ЗЛП-4f (x ) = x1 + 2 x 2 → max,f (x ) = x1 + 2 x 2 → max,x1 + x 2 ≤ 4,x1 + x 2 ≤ 4,x 2 ≤ 2,8x 2 ≤ 2,8x1 , x 2 ≥ 0, x1 ≤ 1 ,x1 , x 2 ≥ 0, x1 ≤ 1 ,x2 ≤ 2 ;x2 ≥ 3 .213Положим i = 1 и перейдем к шагу 4.4 2 .
Решим задачу ЗЛП-3 графически. Условный максимум достигается в точкеx 3∗ = D = (1; 2) T , f (x 3∗ ) = 5 (рис. 1,г). Перейдем к шагу 5.5 2 . Решение x 3∗ – целочисленное. Так как значение f уже найдено, то сравнимf (x 3∗ ) = 5 с f . Имеем f ( x 3 ∗ ) = 5 < f = 6 , поэтому не включаем решение x 3∗ в множе-ство X ∗ возможных оптимальных решений исходной задачи. Задачу ЗЛП-3 исключим издальнейшего рассмотрения. Перейдем к шагу 6.61 . Проверим выполнение условия i ≤ 2 : i = 1 < 2 .
Положим i = 2 и перейдем кшагу 4.4 3 . Решим задачу ЗЛП-4 графически. В этой задаче ограничения не совместны(рис. 1,д), множество допустимых решений пустое. Исключим задачу ЗЛП-4 из дальнейшего рассмотрения. Перейдем к шагу 6.6 2 . Проверим выполнение условия i ≤ 2 : i = 2 . Перейдем к шагу 2.2 2 .
Так как множество k ≠ 0 и J = ∅ , перейдем к шагу 7.x0∗ЗЛП-0= (1,2; 2,8)Tf (x 0∗ ) = 6,8x1 ≥ 2x1 ≤ 1ЗЛП-2ЗЛП-1x 2∗ = (2; 2) Tx1∗ = (1; 2,8) Tf (x 1∗ ) = 6,6x2 ≤ 2x3∗f (x 3∗ ) = 5f ( x 2∗ ) = 6НЦx2 ≥ 3ЗЛП-4ЗЛП-3= (1; 2)НTЦX =∅Рис. 27 0 . Так как множество X ∗ содержит единственное целочисленное решение, тоx ∗ = x 2∗ = (2, 2) T , f ( x ∗ ) = f = 6 – решение исходной задачи.
Процесс решения отраженна рис. 2. ■214Занятие 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) .Б. Метод минимального элементаПолучаемый методом северо-западного угла начальный план перевозок не зависитот их стоимости и поэтому в общем случае далек от наилучшего.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
