Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Шаг 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, либо констатация того, что целочисленных решений в данной задаче нет.
Пример.
Решение. В результате решения задачи симплекс-методом найдём оптимальное решение: ; L 1 = 29,5; где верхний индекс переменных – номер задачи.
В полученном решении х 2 = 7,5 – нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.
Задача 2: | Задача 3: |
Результаты решения симплекс-методом задачи 2: ; L 2 = 29,4; задачи 3: ; L 3 = 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.
Дата публикования: 2014-11-18; Прочитано: 966 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!