Подробное описание метода

Рассмотрим частично целочисленную задачу следующего вида:

F( )= ( ) ;

A = , ;

;

x_j – целочисленная переменная при j  I,

где I – множество индексов целочисленных переменных задачи.

В качестве первого шага необходимо решить сформулированную задачу как задачу ЛП, рассматривая все ее переменные как непрерывные. Получаемая таким образом задача ЛП обозначается через ЛП-1, оптимальное значение ее целевой функции – через F( ). Пусть в оптимальном решении задачи ЛП-1 некоторые целочисленные переменные принимают дробные значения; тогда оптимальное решение исходной задачи не совпадает с оптимальным решением ЛП-1. В этом случае величина F( ) представляет собой верхнюю границу оптимального значения исходной задачи.

На следующем шаге производится ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном решении задачи ЛП-1. Часто выбирают переменную, которая имеет наибольшее дробное значение.

Пусть ветвление происходит по целочисленной переменной x_j, значение которой в оптимальном решении ЛП-1 равно . Далее рассматриваются две новые задачи ЛП, обозначаемые через ЛП-2 и ЛП-3. Они получаются путем введения ограничений [ ] и  [ ] + 1 соответственно. Условия задач ЛП-2 и ЛП-3 можно записать следующим образом:

ЛП-2 ЛП-3

F( )= ( ) F( )= ( )

A = , A = ,

 [ ]  [ ] + 1

Допустим, что оптимальные решения задач ЛП-2 и ЛП-3 также содержат дробные значения целочисленных переменных и поэтому не являются допустимыми для исходной задачи.

На следующем шаге необходимо выбрать задачу ЛП-2 или ЛП-3 и произвести ветвление в соответствующей вершине, вводя новое ограничение. Выбор вершины (задачи ЛП) для дальнейшего ветвления часто осуществляется с использованием оптимального значения целевой функции, т.е. выбирается вершина, соответствующая наибольшему оптимальному значению целевой функции задачи ЛП.

После выбора вершины для дальнейшего ветвления выбирается целочисленная переменная, которая имеет в оптимальном решении соответствующей задачи ЛП дробное значение, и производится ветвление по этой переменной. Процесс ветвления и решения задач ЛП продолжается до получения целочисленного оптимального решения одной из задач ЛП. «начение Z₀ в полученной точке представляет собой текущую нижнюю границу оптимального значения целевой функции исходной задачи ЦЛП. На этом этапе отбрасываются все вершины (задачи ЛП), для которых оптимальное значение F( ) не превосходит полученной нижней границы. Про такие вершины также говорят, что они являются прозондированными, поскольку в соответствующих им допустимых областях нет целочисленных решений, лучших, чем уже полученное, следовательно, промежуточная вершина (задача ЛП) является прозондированной (явным или неявным образом) в том случае, если она удовлетворяет хотя бы одному из следующих условий.

1. Оптимальное решение, соответствующее данной вершине, целочисленно.

2. «адача ЛП, соответствующая рассматриваемой вершине, не имеет допустимых решений.

3. Оптимальное значение F( ) соответствующей задачи ЛП не превосходит текущей нижней границы Z₀.

Дальнейшее ветвление можно производить только в вершинах, для которых F( )  Z₀.  ак только полученное допустимое целочисленное решение одной из задач ЛП окажется лучше имеющегося текущего значения Z₀, оно фиксируется вместо зафиксированного ранее (т.е. меняется значение Z₀).

При использовании метода ветвей и границ выбор вершин для дальнейшего ветвления происходит до тех пор, пока остается хотя бы одна непрозондированная вершина. Прозондированная вершина с наилучшим значением Z₀ дает решение исходной задачи ЦЛП.

ЗАМЕЧАНИЕ: Получение перед реализацией метода ветвей и границ допустимого целочисленного решения может оказаться весьма полезным, так как сразу дает начальную нижнюю границу.

Домашнее задание №15

Решите ЗЦЛП методом ветвей и границ.

1. max(3x₁ + 4x₂) 2. max(3x₁ + 4x₂)

4x₁ + 5x₂  20 3x₁ + 7x₂  21

x₁ + 6x₂  12 x₁ + x₂  4

0 x₁  5 0  x₁  4

0 x₂  4 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

3. max(x₁ + x₂) 4. max(4x₁ + x₂)

3x₁ + 4x₂  12 2x₁ - 3x₂  6

3x₁ + 2x₂  9 4x₁ + 9x₂  18

0 x₁  4 0  x₁  2

0 x₂  2 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

5. max(3x₁ + x₂) 6. max(x₁ + 2x₂)

4x₁ + 3x₂  18 x₁ + x₂  5

x₁ + 2x₂  6 3x₁ + 8x₂  24

0 x₁  5 0  x₁  5

0 x₂  3 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

7. max(2x₁ + x₂) 8. max(3x₁ - 2x₂)

5x₁ + 2x₂  30 2x₁ + 3x₂  6

3x₁ + 8x₂  48 x₁ - x₂  2

0 x₁  6 0  x₁  3

0 x₂  6 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

9. max(3x₁ + 2x₂) 10. max(x₁ + 2x₂)

2x₁ + x₂  7 5x₁ + 9x₂  45

4x₁ + 3x₂  18 x₁ + 3x₂  12

0 x₁  3 0  x₁  9

0 x₂  4 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

11. max(2x₁ + 5x₂) 12. max(4x₁ + 6x₂)

4x₁ + 5x₂  20 3x₁ + 7x₂  21

x₁ + 6x₂  12 x₁ + x₂  4

0 x₁  6 0  x₁  5

0 x₂  5 0  x₂  4

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

13. max(2x₁ + 3x₂) 14. max(5x₁ + 2x₂)

3x₁ + 4x₂  12 2x₁ - 3x₂  6

3x₁ + 2x₂  9 4x₁ + 9x₂  18

0 x₁  6 0  x₁  3

0 x₂  3 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

15. max(4x₁ + 2x₂) 16. max(2x₁ + 5x₂)

4x₁ + 3x₂  18 x₁ + x₂  5

x₁ + 2x₂  6 3x₁ + 8x₂  24

0 x₁  6 0  x₁  4

0 x₂  4 0  x₂  4

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

17. max(3x₁ + 2x₂) 18. max(5x₁ - 3x₂)

5x₁ + 2x₂  30 2x₁ + 3x₂  6

3x₁ + 8x₂  48 x₁ - x₂  2

0 x₁  7 0  x₁  3

0 x₂  6 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

19. max(4x₁ + 3x₂) 20. max(x₁ + 3x₂)

2x₁ + x₂  7 5x₁ + 9x₂  45

4x₁ + 3x₂  18 x₁ + 3x₂  12

0 x₁  4 0  x₁  8

0 x₂  4 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

21. max(4x₁ + 4x₂) 22. max(3x₁ + 3x₂)

4x₁ + 5x₂  20 3x₁ + 7x₂  21

x₁ + 6x₂  12 x₁ + x₂  4

0 x₁  6 0  x₁  4

0 x₂  5 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

23. max(2x₁ + 3x₂) 24. max(5x₁ + x₂)

3x₁ + 4x₂  12 2x₁ - 3x₂  6

3x₁ + 2x₂  9 4x₁ + 9x₂  18

0 x₁  4 0  x₁  2

0 x₂  2 0  x₂  3

x₁ , x₂  0 x₁ , x₂  0

x₁ , x₂ – целые. x₁ , x₂ – целые.

25. max(4x₁ + x₂)

4x₁ + 3x₂  18

x₁ + 2x₂  6

0 x₁  5

0 x₂  3

x₁ , x₂  0

x₁ , x₂ – целые.