Основные этапы решения задачи целочисленного программирования (ЗЦП) методом ветвей и границ
Основные этапы решения задачи целочисленного программирования (ЗЦП) методом ветвей и границ - раздел Информатика, РАЗДЕЛ 1.МЕСТО И РОЛЬ ПРОЦЕССОВ ПОДГОТОВКИ И ПРИНЯТИЯ РЕШЕНИЙ В ОБЩЕЙ ТЕХНОЛОГИИ УПРАВЛЕНИЯ СЛОЖНЫМИ ОРГАНИЗАЦИОННО-ТЕХНИЧЕСКИМИ СИСТЕМАМИ (СОТС
Шаг 1. Исходная Зцп Решается Как Задача Лине...
Шаг 1. Исходная ЗЦП решается как задача линейного программирования (ЗЛП) (снимаем ограничения вида (г)). При этом за «рекорд» в ЗЦП принимают значение целевой функции, полученное при решении ЗЛП .
Шаг 2. Если все переменные приняли целочисленные значения, то получено оптимальное решение в ЗЦП, уход на шаг 8. Если нет, то в решенной на шаге 1 ЗЛП выбирают одну из переменных, которая приняла нецелочисленное значение. Пусть это будет переменная . Для нее вводят следующие два дополнительных ограничения.
(1),
(2),
где — целая часть нецелочисленного значения переменной , полученной при решении ЗЛП.
Шаг 3. Решаются уже две новые ЗЛП вида (а)–(в) п. 3.5 , в каждой из которых введены по одному дополнительному ограничению (1) и (2). Другими словами, исходная задача ЛП разбивается на две новые ЗЛП (происходит ветвление). Обозначим их соответственно ЗЛП–II и ЗЛП–III. Результаты решения получает , .
Шаг 4. Если в ЗЛП–II получаем целочисленное значение всех переменных, то .
Шаг 5. Если в ЗЛП–III получаем целочисленное значение всех переменных, то .
В том случае, когда в ЗЛП–II и ЗЛП–III получены целочисленные решения, то происходит их сравнение.
, выбирается то решение, которому соответствует максимальное значение целевой функции. Переход на шаг 8.
Шаг 6. Если в сформированных на шаге 3 решения не являются целочисленными, то происходит проверка следующих двух условий
, .
Если указанные ограничения выполняются, то дальнейшее ветвление в ЗЦП прекращается, т. к. введение дополнительных ограничений на целочисленность переменных будет только ухудшать значения ЦФ.
Если , , то уход на шаг 7, а ЗЛП вида (II) дальше не решается.
Если , , то уход на шаг 7, а ЗЛП вида (III) дальше не решается.
Шаг 7. Осуществляется проверка все ли нецелочисленные переменные, полученные на шаге 2, просмотрены. Если нет, то формирование новых условий вида (6) в ЗЛП–II и III и переход на шаг 3, если да, то переход на шаг 8.
Шаг 8. Вывод оптимальных целочисленных значений переменных, соответствующих задаче I, либо констатация того, что целочисленных решений в данной задаче нет.
Пример.
Решение. В результате решения задачи симплекс-методом найдём оптимальное решение: ; L1 = 29,5; где верхний индекс переменных – номер задачи.
В полученном решении х2 = 7,5 – нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.
Задача 2:
Задача 3:
Результаты решения симплекс-методом задачи 2: ; L2 = 29,4; задачи 3: ; L3 = 29,25.
В задаче 1 переменная х11=1 – целочисленная, а в последующих задачах при целочисленности х2, х1 перестала быть целочисленной. Затем следует накладывать ограничения целочисленности на х1 и т.д. (рис.3.6.1).
Рис.3.6.1
Результаты решения непрерывной и целочисленной задачи вводятся в табл.3.6.1. В качестве оптимального принимается решение задачи 5, которое даёт наибольшее из целочисленных решений значение целевой функции.
Таблица 3.6.1
№ задачи
х1
х2
L
7,5
29,5
Из примера видно, что метод ветвей и границ достаточно трудоёмкий. При этом оптимальное решение может быть получено в результате сравнения всех допустимых целочисленных решений.
Поэтому при решении задач реальной размерности может потребоваться память, не имеющаяся даже у современных компьютеров или потребоваться практически неприемлемое время решения.
Обязательное условие метода – наличие верхних границ на значения переменных Dj. Если Dj не назначена, то её определяют по зависимости:
,
где - минимальные значения всех хj, для которых определяется верхняя граница Dj.
Концептуальная модель принятия решений
Анализ многочисленных публикаций по различным аспектам проблемы выбора показывает, что в настоящее время наметилась прогрессивная тенденция к интеграции различных научных направлени
Постановка задачи линейного программирования
Значительная часть задач принятия решения – это задачи распределения ресурсовмежду объектами.
Пусть имеется т видов ресурсов, каждый i
Двойственные задачи линейного программирования
Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):
Прямая задача (ПЗ)
Обобщенный алгоритм решения задач НЛП
Эффективное решение различных задач нелинейного программирования может быть осуществлено на основе учета конкретных особенностей этих задач. При этом под эффективностью того или иного алгоритма, ка
Аналитические методы решения задач НЛП
В некоторых случаях задачи НЛП удается решить аналитически. Это, в частности, удается в том случае, если ЦФ и ОДА являются выпуклыми. Обобщенный алгоритм решения задачи НЛП включает в себя следующи
Численные методы решения задач НЛП
В качестве r(xk) используется направление, в котором наиболее сильно возрастает целевая функция. Это направление задается градиентом функции ÑF(xk). Суть метода состоит
Постоянный шаг.
Задается hk = h = const, при этом должно выполняться условие
F(xk+1) = F(xk + hkÑF(xk)) > F(xk).
Пусть
Наискорейший подъем.
Если подставить в выражение для F(x) значение x=xk+1 в соответствии с (1), то получим выражение F(xk+hkÑF(xk)), как функцию от величины шага. След
Функции Лагранжа
Исторически первым способом сведения задачи с ограничениями к задаче безусловной оптимизации явилось использование функции Лагранжа L(x,m)
L(x, m) = f(x) + mт(b - j(x)) = f(x) +
Штрафные функции
Исходная задача условной оптимизации сводится к последовательности задач безусловной оптимизации функций
Fk(x, m) = f(x) - Sk(x, mk), k = 1,2,3,....
Методы прямой условной оптимизации
Методы прямой условной оптимизации предназначены для непосредственного решения задачи выпуклого программирования в условиях ограничений, описывающих множество допустимых решений D.
Итак, п
Метод условного градиента
Существо метода условного градиента состоит в том, что, если известна некоторая точка xkÎD, то направление возрастания целевой функции может задаваться некоторой внутренней или кра
Постановка задачи целочисленного программирования
Первые упоминания о линейных уравнениях возникли ещё за несколько веков до нашей эры.
В Древней Греции Диофант (II-III в.) формулирует уравнения, в которых искомые переменн
Характерные особенности задач многокритериального выбора
Реальные задачи выбора, возникающие на практике, чрезвычайно разнообразны, но всех их объединяет общая схема поиска решения, суть которой состоит в формировании совокупности операци
Принцип В.Парето в задачах многокритериального выбора
В п. 4.1 было установлено, что для корректного решения задач многокритериального выбора необходимо в исходную постановку задачи (4.1)‑(4.2) привнести дополнительную информацию
Методы построения множества Парето
Приведенные в п.4.2.2 свойства множества Парето могут быть использованы для построения (исследования) данного множества (либо его подмножеств) или определения его характеристик в ко
Принятие решений в условиях стохастической среды
Постановка задач принятия решений в условиях стохастической среды имеет вид
(D(w), f(w)), wÎW,
где D(w) - множество допустимых альтернатив, f(w) - целевая функция.
Методы детерминизации.
При решении конкретных задач выбора на вероятностных структурах часто вводится предположение о том, что задание целевой функции f(w) и ограничивающих отношений ri(w), i=1,...,m, определя
Методы имитационной оптимизации.
В методах имитационной оптимизации (прямых методах стохастического выбора) не производится преобразование задачи к ее детерминированному эквиваленту. Суть данных методов заключается в том, что гене
Принятие решений в условиях целенаправленной среды
Принятие решений в условиях целенаправленной среды связано с тем, что известна цель среды, в соответствии с которой она выбирает свои состояния и которую преследует в своих действиях. Эти действия
Постановка задач игрового выбора.
Рассмотрим формализованное представление задачи принятия решений в условиях целенаправленной среды. Обобщенную задачу принятия решения в условиях неопределенности можно записать в виде
(D
Матричные игры. Чистые и смешанные стратегии.
Простейшим вариантом игры является антагонистическая игра, в которой противодействуют две оперирующих стороны (2 игрока), при этом множества различных альтернатив из которых они выбирают решения ко
Методы нахождения оптимальных смешанных стратегий.
Процедура нахождения оптимальных чистых или смешанных стратегий соответствует выявлению рациональной линии поведения противников в конфликтной ситуации, описываемой игровой моделью. Поэтому такую п
Принятие решений в условиях неизвестной среды
В случае неизвестной среды нет достаточных оснований для предположений о том, какие значения будут принимать параметры, характеризующие состояние среды на рассматриваемом временном интервале. При э
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов