semopt8 (1013535)
Текст из файла
Занятие 8. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГОЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯМЕТОД ВЕТВЕЙ И ГРАНИЦПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x jj =1≤ bi , i = 1, … , m ;x j ≥ 0 , целые, j = 1, … , n .АлгоритмШаг 1. Положить k = 0 , решить задачу ЗЛП-0 без учета требований на целочис-ленность переменных и определить x 0∗ , f ( x 0∗ ) . Проверить целочисленность решения:а) если решение целочисленное, то расчет закончен: x ∗ = x 0∗ , f ( x ∗ ) = f (x 0∗ );б) если решение x 0∗ нецелочисленное, включить k = 0 в множество J = {k }номеров задач, подлежащих дальнейшему ветвлению, и перейти к шагу 2.Шаг 2. Выбрать задачу для приоритетного ветвления:а) если k = 0 , выбрать для ветвления задачу ЗЛП-0 , исключить номер k = 0 измножества J = {k } и перейти к шагу 3;б) если k ≠ 0 и J ≠ ∅ , выбрать номер задачи k ∈ J , которому соответствует максимальное значение целевой функции на оптимальном решении x k∗ , исключитьномер k из множества J = {k } и перейти к шагу 3;в) если k ≠ 0 и J = ∅ , перейти к шагу 7.Шаг 3.
Осуществить ветвление задачи ЗЛП- 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
