semopt8 (1013535)

Файл №1013535 semopt8 (Практические занятия)semopt8 (1013535)2017-06-17СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Занятие 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-файл
Размер
276,08 Kb
Тип материала
Высшее учебное заведение

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6487
Авторов
на СтудИзбе
303
Средний доход
с одного платного файла
Обучение Подробнее