Условие задачи

21 22 23 24 25 26 27

Решить методом ветвей и границ задачу, имеющую следующую математическую модель.

Решение:

1. Находим координаты точек каждого линейного уравнения системы ограничений и строим прямые

1 прямая: 3х₁+2х₂=1

если х₁=1, то 2х₂=12, х₂=6

если х₂= 0, то 3х₁=12, х₁=4

2 прямая: 2х₁+5х₂=20

если х₁=0, то 5х₂=20, х₂=4;

если х₂=0, то 2х₁=20, х₁=10

2. Находим ОДР.

Так как х₁, х₂ ≥ 0, то область будет ограничен прямыми ОХ₁ и ОХ₂ и построенными прямыми (см. рис.1).

3. Находим координаты точек целевой функции и строим прямую целевой функции:

7х1+4х2=0

- первая точка х₁=0; х₂=0

- вторая точка х₁=4, х₂=(-7).

4. Перемещаем прямую целевой функции по направлению через ОДР до тех пор, пока она не станет касательной к ней, и находим точку А₀.

5. Находим координаты точек А₀ и значение целевой функции в ней:

Х1=1,8; х2=3,27;

Z=7×1,8+4×3,27=12,6+13,08=25,68

Получен не целочисленный оптимальный план

6. выделим область относительно точки А₀ беря целые значения 1 ≤ х₁ ≤ 2; 3 ≤ х₂ ≤ 4.

Получим координаты точек по границе этой области:

А₁ (1;3,6) А₂ (2;3); А₃ (0;4); А₄ (1;3); А₅ (0;3); А₆ (1;0); А₇ (2;0).

7. Строим граф (рис.2)

8. Для точек с целыми значениямиих координат (искомые значения х₁ и х₂) находим значения целевой функции:

Для точки А₂ (2;3) Z₂= 7×2+4×3=26

Для точки А₃ (0;4) Z₃= 7×0+4×4=16

Для точки А₄ (1;3) Z₄= 7×1+4×3=19

Для точки А₅ (0;3) Z₅= 7×0+4×3=12

Для точки А₆ (1;0) Z₆= 7×1+4×0=7

Контрольные вопросы.

1. Сформулируйте постановку задачи целочисленного программирования.

2. Математическая модель задачи целочисленного программирования и ее особенности.

3. Метод ветвей и границ и его применение.

4. Алгоритм графического решения задачи целочисленного программирования.

5. Как построить граф целочисленной области возможных решений задачи?

6. Как определить целочисленный план и экстремальное значение целевой функции?

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1. Красс М.С. Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. –М.: Дело 2000.688с.

2. Кремер Н.Ш. Исследование операций в экономике - М.: Банки и биржи, 1997. - 408 с.

3. Орлов А.И. Теория принятия решений. Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.

4. Федосеев В.В. Экономико-математические методы и прикладные модели. Москва, 2000. – 391 с.

5. Косоруков О.А., Мищенко А.В.. Исследование операций. Учебник для вузов - М.: Изд. Экзамен,2003,-445с.

6. Кундышева Е.С.. Математическое моделирование в экономике. Уч. пособие. –М: Изд «Дашков и К⁰», 2004,-350с.

7. Экономико – математическое моделирование.Учебник для студентов вузов.Под общ.ред.И.Н.Дрогобыцкого. – изд.»Экзамен»,2004. – 800с. 13. Шапкин А.С, Мазаева Н.П. Математические методы и модели исследования операций:Учебник. – М.:Изд.-торговая корпорация «Дашков и К⁰»,2004.-400 с.