В нашей онлайн базе уже более 10821 рефератов!

Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров
Новости
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

Вы можете воспользоваться поиском готовых работ или же получить помощь по подготовке нового реферата практически по любому предмету. Также вы можете добавить свой реферат в базу.

Метод ветвей и границ

Страница 3

Как видно из табл. 2.41, при t =0 есть оптимальный план задачи. Однако является оптимальным планом и тогда среди его компонентов не окажется отрицательных чисел, т.е. при 5-3t0; 7+4t0;

13+t или при Таким образом, если то- оптимальный план задачи (80)-(82), при котором

Исследуем теперь, имеет ли задача оптимальные планы при . Если , то 5-3t<0 и следовательно, X=(0,5 – 3t, 7+4t, 13+t, 0) не является планом задачи. Поэтому при нужно перейти к новому плану, который был в то же время оптимальным. Это можно сделать в том случае, когда в строке вектора Р2 имеются отрицательные числа . В данном случае это условие выполняется. Поэтому переходим к новому опорному плану, для чего введем в базис вектор Р1 и исключаем из него вектор Р2 (табл. 2.42).

Таблица 2.42

i

Базис

Сб

Р0

3

-2

5

0

-4

Р1

Р2

Р3

Р4

Р5

1

Р3

5

17+2t

0

2

1

0

½

2

Р4

0

18-2t

0

1

0

1

1

3

Р1

3

-5+3t

1

-1

0

0

4

   

70-t

0

9

0

0

5

Как видно из табл. 2.42, -оптимальный план задачи для всех t, при которых Следовательно, если является оптимальным планом исходной задачи, причем .

Если t>17/2, то не является планом задачи, так как третья компонента 17 – 2t есть отрицательное число. Поскольку среди элементов 1-й строки табл. 2.42 нет отрицательных при t>17/2 исходная задача неразрешима.

Исследуем теперь разрешимость задачи при t< -7/4. В этом случае Х= (0,5 -3t, 7+4t, 13+t, 0) (см. табл.2.41) не является планом задачи, так как третья компонента 7+4t есть отрицательное число. Чтобы при данном значении параметра найти оптимальный план (это можно сделать, так как в строке вектора Р3 стоит отрицательное число -1/2), нужно исключить из базиса вектор Р3 и ввести в базис вектор Р5 (табл. 2.43).

Таблица 2.43

i

Базис

Сб

Р0

3

-2

5

0

-4

Р1

Р2

Р3

Р4

Р5

1

Р5

-4

-14-8t

-4

0

-2

0

1

2

Р4

0

20+5t

3

0

1

1

0

3

Р2

-2

12+t

1

1

1

0

0

4

   

32+30t

11

11

1

0

0

Как видно из табл. 2.43, является оптимальным планом задачи для всех значений параметра t, при которых

Таким образом, если , то задача (80)-(82) имеет оптимальный план , при котором

Из табл. 2.43 так же видно, что при t<4 задача неразрешима, поскольку в строке вектора Р4 нет отрицательных элементов.

Итак, если , то задача не имеет оптимального плана; если оптимал

1 2 [3] 4

скачать реферат скачать реферат

Новинки
Интересные новости


Заказ реферата
Заказать реферат
Счетчики

Rambler's Top100

Ссылки
Все права защищены © 2005-2020 textreferat.com