Автор: Пользователь скрыл имя, 13 Октября 2011 в 17:34, контрольная работа
Понятие целочисленного программирования, метод ветвей и границ
Проиллюстрируем метод ветвей и границ на примере.
Z = Зх1 + х2à max
при ограничениях:
4xl + Зх2 < 18,
x1 + 2x2 £ 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 Задача 3
Z=3x1+x2→max Z=3x1+x2→max
при ограничениях: при ограничениях:
4xl + Зх2 < 18 4x1+3x2<18
x1 + 2x2 £ 6 x1 + 2x2 £ 6
0 £ x1 £ 4 5 £ x1 £ 5
0 £ x2 £ 4 0 £ x2 £ 4
х1, x2 - целые числа. х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 Задача 5
Z=3x1+x2→max Z=3x1+x2→max
при ограничениях: при ограничениях:
4xl + Зх2 < 18 4xl + Зх2 < 18
x1 + 2x2 £ 6 x1 + 2x2 £ 6
0 £ x1 £ 4 0 £ x1 £ 4
0 £ x2 £ 0 1 £ x2 £ 4
х1, x2 - целые числа. х1, x2 - целые числа.
Список задач: 4 и 5. Значение Z0 = 0.
IV этап. Решаем задачу 4 симплексным методом.
Получим Zmax = 12 при X4* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z0; Z0 = Z(X4*) = 12, ибо план Х4* целочисленный.
V этап. Решаем задачу 5 симплексным методом.
Получим Zmax = 12,25 при X5* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z 0 не меняется, т.е. Z0 = 12, ибо план X5* нецелочисленный. Так как х1* - дробное, из области решений исключаем полосу 3<x1<4, и задача 5 разбивается на две задачи: 6 и 7.
Задача 6 Задача 7
Z=3x1+x2→max Z=3x1+x2→max
при ограничениях: при ограничениях:
4xl + Зх2 < 18 4xl + Зх2 < 18
x1 + 2x2 £ 6 x1 + 2x2 £ 6
0 £ x1 £ 3 4 £ x1 £ 4
1 £ x2 £ 4 1 £ x2 £ 4
х1, x2 - целые числа. х1, x2 - целые числа.
Список задач: 6 и 7. Значение Z0 = 12.
VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом.
Получим, что условия задачи 7 противоречивы (рис. 3).
VII этап. Решаем задачу 6 симплексным методом.
Получим Zmax = 10,5,при X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как Z(X6*) = =10,5 < Z0 = 12, то задача исключается из списка.
Итак,
список задач исчерпан и оптимальным
целочисленным решением исходной задачи
будет X* = Х4* = (4; 0; 2; 2;
0; 0), а оптимум линейной функции Zmax
= 12.
Рис.
3
Замечание
1. Нетрудно видеть, что каждая последующая
задача, составляемая в процессе применения
метода ветвей и границ, отличается от
предыдущей лишь одним неравенством -
ограничением. Поэтому при решении каждой
последующей задачи нет смысла решать
ее симплексным методом с самого начала
(с I шага). А целесообразнее начать решение
с последнего шага (итерации) предыдущей
задачи, из системы ограничений которой
исключить "старые" (одно или два)
уравнения - ограничения и ввести в эту
систему "новые" уравнения – ограничения
[4].
ЗАКЛЮЧЕНИЕ
В данной работе была рассмотрена сущность целочисленного программирования. Описан специальный метод решения целочисленных задач – метод ветвей и границ. Такие задачи возникают при моделировании разнообразных производственно-экономических, технических, военных и других ситуаций. В то же время ряд проблем самой математики может быть сформулирован как целочисленные экстремальные задачи.
Задачи
такого типа весьма актуальны, так как
к их решению сводится анализ разнообразных
ситуаций, возникающих в экономике,
технике, военном деле и других областях.
Эти задачи интересны и с математической
точки зрения. С появлением ЭВМ, ростом
их производительности повысился интерес
к задачам такого типа и к математике
в целом.
СПИСОК
ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ