Инструменты пользователя

Инструменты сайта


examination:mo:question13

Вопрос 13. Пример решения задачи целочисленного программирования методом ветвей и границ. Содержательный комментарий.

Из предыдущего билета

F(x) = 2*x1 +3*x2 → max

3*x1 + 4*x2 ⇐ 24

2*x1 + 5*x2 ⇐ 22

x1,X2 >= 0 - целые

  1. Сначала находится симплекс методом оптимальное дробное решение

x1 = 2 целых 4/7 x2 = 2 целых 4/7 Fmax = 16 целых 6/7

Так как обе переменные в оптимальном решении не являются целыми, так что любую можно выбрать в качестве переменной для деления

Если выбрать в качестве переменной x2, то получим две системы

Первая система

F(x) = 2*x1 +3*x2 → max

3*x1 + 4*x2 ⇐ 24

2*x1 + 5*x2 ⇐ 22

x2 ⇐ 2

x1,X2 >= 0 - целые

Вторая система

F(x) = 2*x1 +3*x2 → max

3*x1 + 4*x2 ⇐ 24

2*x1 + 5*x2 ⇐ 22

x2 >= 3

x1,X2 >= 0 - целые


На втором шаге снова высчитывается значение переменных (в нашем случае переменной x1 и Fmax)

x1 = 5 целых 1/3

x2 = 2

FMax = 16 целых 2/3

Переменная x1 не является целой, поэтому снова продолжаем ветвление вводя ограничение x1 ⇐ 5, x1 >=6

Первая система

F(x) = 2*x1 + 3*x2 → max

3*x1 + 4*x2 ⇐ 24

2*x1 + 5*x2 ⇐ 22

x2 ⇐ 2

x1 ⇐ 5

x1,X2 >= 0 - целые

Вторая система F(x) = 2*x1 + 3*x2 → max

3*x1 + 4*x2 ⇐ 24

2*x1 + 5*x2 ⇐ 22

x2 >= 3

x1 >= 6

x1,X2 >= 0 - целые

Для первой системы оптимальным решением будет

x1 = 5,

x2 = 2,

F = 16

Здесь все значения являются целочисленными, но еще не значит, что оптимальными.Поэтому рассматривают также вторую систему, там оптимальным решением будет

x1 = 6,

x2 = 1.5,

F = 16.5

Данные значения нам не подходят, так как они дробные, следовательно оптимальное целочисленное решение было уже найдено

examination/mo/question13.txt · Последние изменения: 2014/01/15 08:19 (внешнее изменение)