Применение метода ветвей и границ для задач календарного планирования
Категория реферата: Рефераты по кибернетике
Теги реферата: сочинение на тему онегин, решебник
Добавил(а) на сайт: Flavija.
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата
0 ( x1 ( 5,
0 ( x2 ( 4, х1, x2 — целые числа.
Решение. За нижнюю границу линейной функции примем, например, ее значение
в точке (0,0), т.е. Z0 = Z (0; 0) = 0.
I этап. Решая задачу симплексным методом, получим Zmax = 13 при Х1* = (4,5;
0; 0; 1,5; 0,5; 4); так как первая компонента х1* дробная, то из области
решения исключается полоса, содержащая дробное оптимальное значение х1*, т.е. 4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3:
Задача 2
Z=3x1+x2>max
при ограничениях:
4xl + Зх2 < 18 x1 + 2x2 ( 6
0 ( x1 ( 4
0 ( x2 ( 4 х1, x2 — целые числа.
Задача 3
Z=3x1+x2>max
при ограничениях:
4xl + Зх2 < 18 x1 + 2x2 ( 6
5 ( x1 ( 5
0 ( x2 ( 4 х1, x2 — целые числа.
Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0=
0.
II этап. Решаем (по выбору) одну из задач списка, например задачу 3
симплексным методом.
Получим, что условия задачи 3 противоречивы.
III этап. Решаем задачу 2 симплексным методом. Получим Zmax = 14/3 при
X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3*) = 14/3 > Z0 = 0, по-прежнему
сохраняется Z0 = 0, ибо план нецелочисленный. Так как х2* — дробное
число, из области решений исключаем полосу 0 < x2 < 1 и задачу 2 разбиваем
на две задачи 4 и 5.
Задача 4
Z=3x1+x2>max
при ограничениях:
4xl + Зх2 < 18 x1 + 2x2 ( 6
0 ( x1 ( 4
0 ( x2 ( 0 х1, x2 — целые числа.
Задача 5
Z=3x1+x2>max
при ограничениях:
Рекомендуем скачать другие рефераты по теме: реферат на тему русские, реферат охрана.
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата