Кому нужна математика? Понятная книга о том, как устроен цифровой мир (Литвак, Райгородский) - страница 74
Заметьте, что это число не зависит от (x>1,x>2). Значит, в какой бы точке прямой (П.1) мы не начали движение, в результате перемещения по этой прямой, изменение значения целевой функции зависит только от коэффициента
Если он отрицательный, то, увеличивая x>1 и двигаясь по прямой, мы можем только уменьшить целевую функцию. Аналогично если коэффициент положительный, то, двигаясь по прямой в сторону увеличения x>1, мы можем целевую функцию только увеличить. Наконец, если коэффициент равен нулю, значение целевой функции на всей прямой постоянно.
Стало быть, из любой точки на данной стороне S мы можем двигаться либо в сторону уменьшения, либо в сторону увеличения x>1 так, чтобы значение целевой функции не уменьшалось. Таким образом мы можем менять значение x>1, пока какое-то другое ограничение не превратится в равенство. В этом случае мы столкнулись с углом многоугольника S, в котором достигается максимальное значение целевой функции на всей рассмотренной нами стороне. Поскольку сторону мы выбрали произвольно, делаем вывод, что максимальное значение целевой функции достигается в одном из углов S и мы можем выбрать этот угол в качестве x>*>1, x>*>2.
Очевидно, что это доказательство легко обобщить на любое количество 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>321=1. Если этого не происходит (то есть грузовик 3 в первой половине дня никуда не едет или едет к другому клиенту), то x>321=0.
В нашей небольшой задаче всего 4×2×2=16 переменных, то есть ее можно решить и вручную.
Целевая функция – это цена доставки, и вычисляется она очень просто:
Например, если грузовик 3 едет к клиенту 2 в первой половине дня, то x>321 = 1 и мы прибавим к общей стоимости c>32. А если грузовик 3 к клиенту 2 не поедет, тогда x>321 = x>322 = 0 и c>32 не войдет в общую сумму.
Самое интересное – это ограничения. Например, грузовик i не может поехать к двум клиентам в одно и то же время. Это можно записать в виде ограничения:
x>i1t +x>i2t ≤,i=1,2,3,4;