- 1
- 2
- 3
- 4
- 5
- . . .
- последняя »
значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
3. Находят решение задач (5) и (6), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (5) и (6), и находят их решение.
Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(4) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.
Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод.
§4. Пример использования метода ветвей и границВ качестве примера к методу ветвей и границ рассмотрим функцию z=4х1+х2+1max (7) при ограничениях:
(8). x1, x2 , (9).Пусть Х0 = (0; 0), z0 = 1 - «оптимальное»1 решение (10). Выполним 1-й этап общего алгоритма и найдем с помощью симплекс-метода, а затем и двойственного симплекс-метода (см. Приложение 1) X1, исходя из ограничений (8). Итак, X1 = (3; 0,5; 0; 1; 0; 2,5), z1 = 13,5 (11). Так как z1 дробное, то «оптимальным» так и остается план Х0,
Согласно 2-му пункту нашего плана, составим 2 новых системы ограничений для (7):(12) и(13). Выполним 3-й пункт алгоритма. Для начала, решим задачу (7), (12) с помощью табличного процессора Microsoft Excel (см. Приложение 2) и получим X2 = (2; 1)2, z2 = 10 (14). Так как z2 ≥ z0, «оптимальным» становится план Х0.
Решим задачу (7), (13). Из последнего уравнения очевидно, что x2 = 0. Отсюда следует, что x1 = 3 (максимально возможное). Тогда Х3 = (3; 0), z3 = 13 (15), а следовательно, данный план является оптимальным (теперь уже без кавычек).
Нам не пришлось выполнять 4-й пункт нашего алгоритма в связи с тем, что оптимальное решение найдено, переменные целочисленные. К тому же, все необходимые моменты решения уже были показаны в пунктах 1-3.
Пример, в котором всё складывается не так просто, приведен в Приложении 3.
календарное планирование программирование
- Применение метода ветвей и границ для задач календарного планирования
Метод ветвей и границ является универсальным методом решения комбинаторных задач дискретного программирования. Сложность практического применения метода заключается в трудностях нахождения способа ветвления множества на подмножества и вычисления соответствующих оценок, которые зависят от специфики конкретной задачи.
Для того, чтобы выяснить области применения данного метода и ознакомиться с практической его формой, мы обратимся к задаче трех станков1, как к классическому примеру.
§1. Алгоритм решения задачи трех станков методом ветвей и границЗаданы n деталей di (i = 1, 2, ..., n), последовательно обрабатываемых на трех станках R1, R2, R3, причем технологические маршруты всех деталей одинаковы. Обозначим ai ,bi ,ci — длительность обработки деталей di на первом, втором и третьем станках соответственно.
Определить такую очередность запуска деталей в обработку, при которой минимизируется суммарное время завершения всех работ Tц.
Можно показать, что в задаче трех станков очередность
- 1
- 2
- 3
- 4
- 5
- . . .
- последняя »
Похожие работы
Тема: Применение метода ветвей и границ для задач календарного планирования |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Реферат) |
Тема: Применение метода ветвей и границ для задач календарного планирования |
Предмет/Тип: Менеджмент (Диплом) |
Тема: Применение метода ветвей и границ для задач календарного планирования |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Реферат) |
Тема: Сущность календарного планирования |
Предмет/Тип: Менеджмент (Реферат) |
Тема: Задачи оптимизации календарного планирования |
Предмет/Тип: Менеджмент (Контрольная работа) |
Интересная статья: Быстрое написание курсовой работы