Кому нужна математика? Понятная книга о том, как устроен цифровой мир - читать онлайн книгу. Автор: Нелли Литвак, Андрей Райгородский cтр.№ 32

Рассмотрим задачу линейного программирования с двумя переменными в общем виде.

Заметьте, что, во-первых, задача максимизации эквивалентна задаче минимизации с коэффициентами −с₁ и −с₂. Во-вторых, любое неравенство со знаком ≤ можно превратить в эквивалентное неравенство со знаком ≥, умножив обе части неравенства на –1. Поэтому задача выше, для двух переменных и m ограничений, сформулирована действительно в общем виде. Все значения коэффициентов a, b, с – произвольные действительные числа, которые могут быть как положительными, так и отрицательными.

Каждое ограничение задает полуплоскость значений, на которой оно выполняется. Если пересечение всех m полуплоскостей пусто, то допустимого решения просто не существует. Поэтому допустим, что m полуплоскостей содержат общую ограниченную область S допустимых значений. (Мы не будем рассматривать случай, когда область не ограничена.) Очевидно, что S – это многоугольник, поскольку область S ограничена прямыми.

Утверждение. Максимальное значение целевой функции достигается в одном из углов S.

Доказательство. Обозначим оптимальное решение через x^*₁, x^*₂. Заметьте, что x^*₁, x^*₂ не может быть внутренней точкой S, потому что в этом случае оба значения переменных можно либо увеличить, либо уменьшить, таким образом увеличивая значение целевой функции. Например, в нашей задаче в главе 2 решение (58,8) является внутренней точкой, поэтому не может быть оптимальным.

Значит, x^*₁, x^*₂ лежит на одной из сторон многоугольника S. На каждой из сторон одно из ограничений превращается в равенство. Рассмотрим сторону, которая соответствует первому ограничению: a₁₁x₁ + a₁₂x₂ = b₁. Что происходит, если мы начнем двигаться вдоль этой стороны?

Не уменьшая общности, допустим, a₁₂ ≠ 0. Для начала перепишем равенство в более привычном виде как уравнение прямой:

Допустим, мы начали в точке (x₁,x₂). Теперь допустим, что мы немного изменили х₁ и получили новую координату x₁+δ, где δ>0 достаточно мало, чтобы все остальные ограничения, кроме первого, по-прежнему строго выполнялись. Тогда значение х₂ изменится на величину

При этом нетрудно проверить, что целевая функция изменится на величину

Заметьте, что это число не зависит от (x₁,x₂). Значит, в какой бы точке прямой (П.1) мы не начали движение, в результате перемещения по этой прямой, изменение значения целевой функции зависит только от коэффициента

Если он отрицательный, то, увеличивая x₁ и двигаясь по прямой, мы можем только уменьшить целевую функцию. Аналогично если коэффициент положительный, то, двигаясь по прямой в сторону увеличения x₁, мы можем целевую функцию только увеличить. Наконец, если коэффициент равен нулю, значение целевой функции на всей прямой постоянно.

Стало быть, из любой точки на данной стороне S мы можем двигаться либо в сторону уменьшения, либо в сторону увеличения x₁ так, чтобы значение целевой функции не уменьшалось. Таким образом мы можем менять значение x₁, пока какое-то другое ограничение не превратится в равенство. В этом случае мы столкнулись с углом многоугольника S, в котором достигается максимальное значение целевой функции на всей рассмотренной нами стороне. Поскольку сторону мы выбрали произвольно, делаем вывод, что максимальное значение целевой функции достигается в одном из углов S и мы можем выбрать этот угол в качестве x^*₁, x^*₂.

Очевидно, что это доказательство легко обобщить на любое количество n переменных.

2. Пример задачи целочисленного программирования

Допустим, нам нужно отправить грузовики с товаром к двум разным клиентам. Всего у нас в разных точках четыре грузовика. Обозначим через cij цену отправки грузовика i=1,2,3,4 к клиенту j=1,2. На любую доставку требуется полдня. Доставку можно осуществить либо утром (первая половина дня), либо днем (вторая половина дня). Нужно решить, к какому клиенту какой грузовик поедет и в какой момент времени.

Введем переменные x_ijt, i=1,2,3,4; j=1,2; t=1,2. Эти переменные могут принимать значение 0 или 1. Например, если грузовик 3 едет к клиенту 2 в первой половине дня, то x₃₂₁=1. Если этого не происходит (то есть грузовик 3 в первой половине дня никуда не едет или едет к другому клиенту), то x₃₂₁=0.

В нашей небольшой задаче всего 4×2×2=16 переменных, то есть ее можно решить и вручную.

Целевая функция – это цена доставки, и вычисляется она очень просто:

Например, если грузовик 3 едет к клиенту 2 в первой половине дня, то x₃₂₁ = 1 и мы прибавим к общей стоимости c₃₂. А если грузовик 3 к клиенту 2 не поедет, тогда x₃₂₁ = x₃₂₂ = 0 и c₃₂ не войдет в общую сумму.

Самое интересное – это ограничения. Например, грузовик i не может поехать к двум клиентам в одно и то же время. Это можно записать в виде ограничения: