Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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

⇐ ПредыдущаяСтр 8 из 9Следующая ⇒

α(A-6,B-3,A-5), β(B-5,A-5,C-4), γ(A-5,B-4,C-5)

α(A-6,B-4,A-5), β(B-5,A-6,C-4), γ(A-4,B-5,C-6)

α(A-6,B-4,A-5), β(B-5,A-7,C-4), γ(A-4,B-6,C-5)

α(A-6,B-7,A-3), β(B-5,A-7,C-4), γ(A-7,B-5,C-3)

α(A-6,B-3,A-7), β(B-5,A-7,C-4), γ(A-7,B-5,C-5)

α(A-8,B-3,A-7), β(B-5,A-7,C-4), γ(A-7,B-4,C-5)

α(A-8,B-5,A-7), β(B-5,A-7,C-6), γ(A-7,B-6,C-5)

α(A-8,B-3,A-7), β(B-5,A-7,C-6), γ(A-7,B-5,C-7)

α(A-8,B-4,A-7), β(B-5,A-7,C-6), γ(A-7,B-5,C-7)

α(A-8,B-4,A-6), β(B-5,A-7,C-6), γ(A-9,B-5,C-7)

α(A-8,B-4,A-5), β(B-6,A-7,C-6), γ(A-9,B-5,C-7)

α(A-8,B-4,A-7), β(B-6,A-7,C-8), γ(A-7,B-5,C-9)

α(A-8,B-6,A-7), β(B-6,A-7,C-8), γ(A-9,B-5,C-7)

α(A-8,B-6,A-7), β(B-7,A-7,C-8), γ(A-9,B-5,C-7)

α(A-8,B-6,A-8), β(B-8,A-7,C-5), γ(A-9,B-5,C-7)

α(A-7,B-6,A-8), β(B-8,A-7,C-8), γ(A-9,B-7,C-7)

α(A-6,B-6,A-9), β(B-8,A-7,C-8), γ(A-9,B-7,C-7)

α(A-8,B-6,A-9), β(B-8,A-7,C-8), γ(A-9,B-7,C-9)

α(A-10,B-6,A-9), β(B-86,A-7,C-7), γ(A-9,B-7,C-9)

α(A-7,B-6,A-9), β(B-8,A-9,C-6), γ(A-9,B-7,C-7)

α(A-7,B-6,A-9), β(B-8,A-9,C-6), γ(A-9,B-7,C-8)

α(A-10,B-6,A-9), β(B-8,A-9,C-10), γ(A-11,B-7,C-9)

α(A-10,B-8,A-9), β(B-8,A-9,C-10), γ(A-11,B-7,C-9)

α(A-10,B-8,A-9), β(B-9,A-9,C-10), γ(A-11,B-7,C-9)

α(A-11,B-6,A-9), β(B-9,A-11,C-6), γ(A-8,B-9,C-11)

α(A-9,B-6,A-9), β(B-9,A-6,C-6), γ(A-8,B-9,C-9)

α(A-9,B-6,A-7), β(B-4,A-7,C-5), γ(A-7,B-9,C-6)

α(A-9,B-6,A-7), β(B-6,A-7,C-5), γ(A-8,B-9,C-6)

α(A-9,B-6,A-8), β(B-8,A-7,C-5), γ(A-8,B-9,C-6)

α(A-9,B-6,A-7), β(B-8,A-7,C-8), γ(A-8,B-9,C-5)

α(A-9,B-6,A-5), β(B-8,A-7,C-8), γ(A-8,B-9,C-6)

α(A-9,B-8,A-5), β(B-8,A-7,C-7), γ(A-8,B-9,C-6)

α(A-9,B-8,A-5), β(B-8,A-9,C-7), γ(A-7,B-9,C-6)

α(A-9,B-8,A-7), β(B-8,A-9,C-8), γ(A-7,B-9,C-6)

α(A-9,B-7,A-8), β(B-8,A-9,C-7), γ(A-7,B-9,C-6)

α(A-9,B-7,A-7), β(B-8,A-9,C-8), γ(A-7,B-9,C-6)

α(A-9,B-8,A-7), β(B-8,A-9,C-9), γ(A-8,B-9,C-6)

α(A-9,B-8,A-7), β(B-8,A-7,C-9), γ(A-5,B-9,C-6)

α(A-9,B-8,A-5), β(B-8,A-7,C-9), γ(A-7,B-9,C-6)

α(A-9,B-8,A-5), β(B-9,A-7,C-6), γ(A-7,B-9,C-9)

α(A-9,B-8,A-7), β(B-9,A-7,C-6), γ(A-7,B-9,C-5)

α(A-5,B-8,A-7), β(B-9,A-7,C-6), γ(A-7,B-9,C-9)

α(A-5,B-8,A-7), β(B-9,A-7,C-5), γ(A-7,B-5,C-9)

α(A-5,B-8,A-4), β(B-9,A-7,C-5), γ(A-4,B-5,C-9)

α(A-5,B-8,A-6), β(B-9,A-7,C-6), γ(A-6,B-5,C-9)

α(A-7,B-8,A-7), β(B-7,A-7,C-6), γ(A-6,B-5,C-9)

α(A-8,B-8,A-7), β(B-7,A-8,C-6), γ(A-6,B-5,C-8)

α(A-9,B-8,A-7), β(B-7,A-9,C-6), γ(A-6,B-5,C-9)

α(A-9,B-8,A-5), β(B-7,A-5,C-5), γ(A-6,B-5,C-9)

α(A-9,B-8,A-7), β(B-7,A-5,C-7), γ(A-6,B-7,C-9)

α(A-4,B-8,A-7), β(B-7,A-5,C-7), γ(A-6,B-7,C-4)

Раздел 7. Оптимизация линейных задач с бинарными переменными

Задача решается методом ветвей и границ с использованием частичных решений в качестве ветвей и значений целевой функции в качестве нижней границы. Решение называется частичным, если известны значения не всех переменных. Остальные переменные называются свободными. Свободные переменные, которым присвоены конкретные значения, называют дополнением частичного решения. Дополнение допустимо, если ограничительные неравенства не нарушаются, а новое значение целевой функции превышает текущее.

Задача оптимизации ставится так: максимизировать (минимизировать) целевую функцию

∑ с_j*x_j, j = 1,…,n (7.1)

при ограничениях ∑ a_ij*x_j ≤ b_j, i = 1, …, m, где x_i = {0,1}, j = 1,…, n

Алгоритм решения в задачи линейного программирования с бинарными переменными состоит из четырёх этапов:

1. Если список частичных решений пуст, задача решена. Иначе выбрать частичное решение, исключить его из списка и перейти к шагу 2.

2. Если есть свободная переменная, увеличивающая оценку целевой функции при любом допустимом дополнении, включить её в частичное решение.

Если нет допустимого дополнения со значением целевой функции, превосходящей текущую оценку целевой функции, вернуться к шагу 1.

3. Если частичное решение - полное, зафиксировать его с заменой текущей оценки целевой функции новой, соответствующей зафиксированному решению и вернуться к шагу 1. Иначе перейти к шагу 4.

4. Выбрать свободную переменную x_k и внести в список частичных решений два решения со значениями соответственно x_k = 0 и x_k = 1. Запомнить текущую оценку целевой функции и вернуться к шагу 1.

Для текущего частичного решения линейные ограничения надо представить в следующем виде:

∑ a_ij*x_j ≤ b_j - ∑ a_ij*x_j , i = 1, …, m

своб.перем. част.перем.

Для целевой функции (i = 0) a₀_j = - c_j и b₀ = - x₀^t - 1.

Если для заданного частичного решения

∑ min(a_ij,,0) > b_j - ∑ a_ij*x_j для любого i = 0,1, …, m (7.2)

своб.перем. част.перем.

то допустимого дополнения, которому соответствует значение целевой функции, превосходящее нижнюю оценку x₀^t, не существует.

Если для заданного частичного решения и свободной переменной x_k

∑ min(a_ij,,0) + │a_ik │ > b_j - ∑ a_ij*x_j для любого i = 0,1, …, m (7.3)

своб.перем. част.перем.

то для a_ik > 0 переменная x_k = 0, а для a_ik < 0 переменная x_k = 1.

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

Максимизировать 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).

Варианты заданий для линейных задач с бинарными переменными