Кому нужна математика? Понятная книга о том, как устроен цифровой мир - Андрей Райгородский

x_i1t + x_i2t ≤, i =1,2,3,4; t =1,2.

Тогда для любого i и t только одно (или ни одно) из значений х_i1t или х_i2t может равняться единице.

Еще одно универсальное ограничение: к клиенту j нужно послать только один грузовик, то есть

Ограничения могут учитывать особенности каждого грузовика, клиента и другие факторы. Например, мы не хотим, чтобы грузовик 3 работал утром (скажем, у этого грузовика запланирован техосмотр). Тогда мы просто включим ограничение:

x₃₁₁ + x₃₂₁ = 0.

Теперь допустим, что это условие желательное, но необязательное. Тогда к целевой функции можно добавить дополнительное слагаемое, которое будет означать штраф за невыполнение условия:

c_штраф (x₃₁₁ + x₃₂₁).

Заметьте, что это слагаемое действительно добавится, только если грузовик 3 работал в утреннюю смену. Естественно, оптимальное решение будет зависеть от коэффициента c_штраф. Если он больше любого c_ij в целевой функции, то оптимальный вариант – не задействовать грузовик 3 с утра. А если коэффициент с_штраф маленький, то, возможно, грузовик 3 все равно задействуют, если это обеспечит более низкую цену доставки.

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

x₃₁₁ + x₃₂₁ = x₃₁₂ + x₃₂₂. (П.2)

Это условие можно несколько усложнить. Например, если грузовик 3 в первой половине дня поехал к клиенту 1, то мы хотим, чтобы он работал и во второй половине дня. Как это записать в виде линейного неравенства? Часто используется такой прием. Вводим достаточно большое значение М и записываем:

(x₃₁₁ + x₃₂₁) − (x₃₁₂ + x₃₂₂) ≤ M (1 − x₃₁₁).

Если x₃₁₁=1, то значение справа при любом М равно нулю. Тогда неравенство выполняется (и на самом деле является равенством), только если x₃₁₂ + x₃₂₂=1 (вспомните, что x₃₁₁ + x₃₂₁=1). Но если x₃₁₁=0, то М можно выбрать достаточно большим, чтобы ограничение не играло никакой роли. В данном случае, кстати, достаточно, чтобы М=1. Для увеличения скорости решения М стараются выбирать «экономно» – не больше, чем нужно.

Есть еще множество интересных приемов записи обязательных и желательных условий в виде линейных выражений, но их более подробное описание выходит за рамки нашей книги.

3. Идея метода ветвей и границ

Допустим, нам нужно послать землекопов на объекты и мы хотим минимизировать стоимость работ. Для начала мы берем совершенно произвольное расписание и получаем стоимость работ, скажем 50 000 рублей. Это наш максимум, и мы постараемся его уменьшить.

Теперь запускаем симплекс-метод и получаем дробное решение. Например, на объект А нужно отправить 2 и 2/3 землекопа. Допустим, общая стоимость работ при этом составит 40 000 рублей. Это пока не дает нам плана работ, потому что решение не в целых числах. Зато мы знаем, что это решение оптимальное, то есть при любом другом (в том числе целочисленном) решении стоимость получится никак не меньше 40 000 рублей. Значит, наша стоимость в результате будет между 40 000 и 50 000 рублей.

Дальше начинаем «разветвлять» решение. У нас есть два варианта: A ≤ 2 и A ≥ 3. Для каждого из них мы снова решаем задачу линейного программирования. Допустим, стоимость получилась 43 000 рублей при A ≥ 3 и 51 000 при A ≤ 2. Отсекаем вариант A ≤ 2, поскольку у нас уже есть более выгодное решение. В результате делаем вывод, что A ≥ 3, а минимальная стоимость теперь 43 000 рублей. Если при этом все переменные получились целочисленные, то мы нашли решение. А если у нас еще остались дробные переменные, то каждую из них разветвляем снова. И так до тех пор, пока не найдем решения в целых числах.

Назад к Главе 2