2015-03-27
327
Условие задачи.
Решить методом ветвей и границ задачу, имеющую следующую математическую модель.
Решение:
1. Находим координаты точек каждого линейного уравнения системы ограничений и строим прямые
1 прямая: 3х1+2х2=1, если х1=1, то 2х2=12, х2=6, если х2= 0, то 3х1=12, х1=4
2 прямая: 2х1+5х2=20, если х1=0, то 5х2=20, х2=4; если х2=0, то 2х1=20, х1=10
2. Находим ОДР.
Так как х1, х2 ≥ 0, то область будет ограничен прямыми ОХ1 и ОХ2 и построенными прямыми (см. рис.1).
3. Находим координаты точек целевой функции и строим прямую целевой функции:
7х1+4х2=0
- первая точка х1=0; х2=0
- вторая точка х1=4, х2=(-7).
4. Перемещаем прямую целевой функции по направлению через ОДР до тех пор, пока она не станет касательной к ней, и находим точку А0.
5. Находим координаты точек А0 и значение целевой функции в ней:
Х1=1,8; х2=3,27;
Z=7×1,8+4×3,27=12,6+13,08=25,68
Получен не целочисленный оптимальный план
6. выделим область относительно точки А0 беря целые значения
1 ≤ х1 ≤ 2; 3 ≤ х2 ≤ 4.
Получим координаты точек по границе этой области:
А1 (1;3,6) А2 (2;3); А3 (0;4); А4 (1;3); А5 (0;3); А6 (1;0); А7 (2;0).
|
|
|
7. Строим граф (рис.2)
8. Для точек с целыми значениямиих координат (искомые значения х1 и х2) находим значения целевой функции:
Для точки А2 (2;3) Z2= 7×2+4×3=26
Для точки А3 (0;4) Z3= 7×0+4×4=16
Для точки А4 (1;3) Z4= 7×1+4×3=19
Для точки А5 (0;3) Z5= 7×0+4×3=12
Для точки А6 (1;0) Z6= 7×1+4×0=7
Для точки А7 (2;0) Z7= 7×2+4×0=14
Так как максимальное значение целевой функции находится для точки А2 (2;3), то она и будет оптимальным целочисленным решением задачи.
Ответ: Z=26; х1=2; х2=3.
Контрольные вопросы.
Сформулируйте постановку задачи целочисленного программирования.
Математическая модель задачи целочисленного программирования и ее особенности.
Метод ветвей и границ и его применение.
Алгоритм графического решения задачи целочисленного программирования.
Как построить граф целочисленной области возможных решений задачи?
Как определить целочисленный план и экстремальное значение целевой функции?
