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

xi1t + xi2t ≤, i =1,2,3,4; t =1,2.

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

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

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

x311 + x321 = 0.

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

cштраф (x311 + x321).

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

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

x311 + x321 = x312 + x322. (П.2)

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

(x311 + x321) − (x312 + x322) ≤ M (1 − x311).

Если x311=1, то значение справа при любом М равно нулю. Тогда неравенство выполняется (и на самом деле является равенством), только если x312 + x322=1 (вспомните, что x311 + x321=1). Но если x311=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

Приложения к главе 31. Число последовательностей из нулей и единиц заданной длины

Для начала рассмотрим последовательности длины 5. Сколькими способами мы можем выбрать первый элемент последовательности? Очевидно, что вариантов 2: ноль или единица. Теперь давайте посмотрим на второй элемент. Для него у нас тоже есть два варианта, причем при любом выборе первого элемента последовательности. Значит, число способов выставить друг за другом первые два элемента равно четырем. Точно так же для каждого из этих четырех вариантов есть два способа выбрать третий элемент последовательности и так далее. В итоге для кодового слова длины 5 получаем

2 × 2 × 2 × 2 × 2 = 25 = 32.

Аналогично число разных последовательностей длины 4 равно 24 = 16, а число разных последовательностей длины 8 равно 28 = 256. Для любой заданной длины n получаем 2n разных последовательностей из нулей и единиц.

2. Граница Хэмминга

Допустим, мы пользуемся словами длиной n и наш код состоит из N таких слов.

Если код исправляет d ошибок, то шары Хэмминга с центрами в кодовых словах и радиусами d попарно не пересекаются. Объем шара (то есть количество слов в нем) нетрудно вычислить. Сколько слов отстают от центра шара на заданное расстояние k? Разумеется, столько, сколькими способами можно выбрать те k позиций из n возможных, в которых произойдут помехи. Это число способов называется числом сочетаний из п по k и обозначается Ckn. Для того чтобы его записать, нам понадобятся произведения вида

k × (k − 1) × … × 2 × 1.

Такое произведение принято обозначать записью

k!

и она читается как k факториал. Легко увидеть, что, конечно, 1! = 1, и принято считать, что 0! = 1. Заметим, что факториал уже встречался нам в главе 2 в разделе «Проклятие размерности». Там мы показали, что факториал растет очень быстро. Например, 25! – это колоссальное число.