Пример рещения

Максимизировать 3x₁ + 6x₂ + 3x₃ + 6x₄ + 13x₅ (7.4)

при ограничениях

- 3x₁ - 6x₂ + 6x₃ + 12x₄ + 7x₅ ≤ 8, i = 1 (7.5)

6x₁ + 12x₂ - 3x₃ - 6x₄ + 7x₅ ≤ 8, i = 2 (7.6)

x_i = {0,1}, j = 1,…, 5

Примем начальное значение нижней оценки целевой функции x₀¹ = 0 , что соответствует допустимому решению, в котором все переменные равны нулю. Введём в список частичных решений (ЧР) два решения: ЧР1 (x₅ = 1) и ЧР2 (x₅ = 0). Выбор объясняется тем, что при x₅ = 1 приращение оценки целевой функции максимально.

На шаге 1 исключаем ЧР1 из списка и отыскиваем для него допустимое дополнение со значением целевой функции, превосходящим оценку x₀¹ = 0, то есть удовлетворяющее условию

- 3x₁ - 6x₂ - 3x₃ - 6x₄ - 13x₅ ≤ -1, i = 0 (7.7)

и двум ограничительным неравенствам (7.5 - 7.6).

На шаге 2 найдём допустимые свободные переменные, применив условие (7.3).

Для i = 1 и k = 4 условие (7.3) примет вид:

- 3 – 6 + 12 > 8 – 7x₅ = 8 - 7 = 1 (7.8)

Для i = 2 и k = 2 условие (7.3) примет тот же вид:

- 3 – 6 + 12 > 8 – 7x₅ = 8 - 7 = 1 (7.9)

Из (7.8) следует, что неравенство (7.5) нарушается при x₄ = 1. Из (7.9) следует, что неравенство (7.6) нарушается при x₂ = 1. Значит для ЧР1 во всех допустимых дополнениях x₂ и x₄ должны быть равны нулю. Из ЧР1 следует ЧР11: (x₂, x₄, x₅) = (0, 0, 1). Для ЧР11 снова применим условие (7.3).

Для i = 1 и k = 3 условие (7.3) примет вид:

- 3 + 6 > 8 - 7 = 1. (7.10)

Для i = 2 и k = 1 условие (7.3) примет тот же вид:

6 > 8 - 7 = 1. (7.11)

Следовательно, повторное применение условия (7.3) позволяет получить допустимое полное решение ПР1: (x₁,x₂,x₃, x₄, x₅) = (0, 0, 0, 0, 1) с текущей оценкой максимума целевой функции x₀¹ =13.

Полагаем x₀² = x₀¹ =13 и возвращаемся к шагу 1. Исключаем из списка ЧР2, где x₅ = 0. Применение условия (7.2) для i = 0, 1, 2 не исключает допустимого дополнения со значением целевой функции, превосходящим x₀² = 13. Переходим к шагу 3 и 4, так как ЧР2 – неполное. Выбираем переменную x₁ и расчленяем ЧР2 на ЧР21 и ЧР22 со значениями (x₁ ,x₅) = (1, 0) и (x₁ ,x₅) = (0, 0).

На шаге 1 исключаем из списка ЧР21 и полагаем x₀³ = 13. Проверка условия (7.3) для i = 0, 1 не определяет однозначно ни одну свободную переменную. Для i = 2 проверка (7.3) даёт x₂ = 0 для любого допустимого дополнения:

12 x₂ – 3 – 6 > 8 – 6 = 2 (7.12)

Расширяя ЧР21 до ЧР211: (x₅,x₁,x₂) = (0, 1,1) и повторно применяя (7.3) для i = 0 можно убедиться, что допустимого дополнения не существует:

- 3(x₃ = 1) – 6(x₄ = 1) ≤ -13 + 3 = -10. (7.13)

Возвращаемся к шагу 1, исключая из списка ЧР22 (x₁, x₅) = (0, 0) и приняв x₀⁴ = 13.

Проверка (7.3) для i = 0 показывает, что для любого допустимого дополнения

x₃ = 1.

-6(x₂ = 1) – 3(x₃ = 1) – 6(x₄ = 1) ≤ -13 (7.14)

Применяя условие (7.3) для i = 1, 2, получаем, что x₄ = 0 и x₂ = 1.

Для i = 1 имеем

- 6(x₂ = 1) + 12(x₄ = 0) ≤ 8 - 6((x₃ = 1)) = 2. (7.15)

Для i = 2 имеем

+ 12(x₂ = 0) - 6(x₄ = 1) ≤ 8 + 3(x₃ = 1) = 11. (7.16)

При проверке условия (7.2) для i = 0 получаем, что не существует допустимого дополнения со значением целевой функции , превосходящим

x₀⁴ = 13.

3(x₁ = 1) + 6(x₂ = 0) + 3(x₃ = 1) + 6(x₄ = 0) + 13(x₅ = 0) = 6

Возвращаясь к шагу 1 прекращаем вычисления, так как все частичные решения в списке исчерпаны. Максимальное значение целевой функции равно 13, а оптимальные значения переменных равны (0, 0, 0, 0, 1).