Кому нужна математика? Понятная книга о том, как устроен цифровой мир - [7]
От задачи к решению
Несмотря на простую формулировку, решить задачу линейного программирования вовсе не просто. Самая большая сложность заключается в ограничениях. Это видно даже на нашем маленьком примере. Понятно, что выгоднее всего доставить товар обоим клиентам с дешевого южного склада. Трудность в том, что это невозможно, потому что там всего 70 листов, а нам нужно 100.
Чем больше переменных и ограничений, тем сложнее задача. В классической задаче о диете 77 переменных и 9 ограничений, и она уже представляет собой серьезную проблему с точки зрения вычислений. Линейное программирование стало рядовым инструментом менеджмента и планирования только благодаря тому, что математики придумали для таких задач множество совершенно нетривиальных методов решения.
Работы американского математика Джорджа Данцига появились в конце 1940-х годов – несколько позже, чем работы Канторовича. Тем не менее Данцига тоже по праву относят к основателям линейного программирования. Именно он придумал так называемый симплекс-метод, позволивший с помощью компьютера быстро решать задачи линейного программирования с большим количеством переменных и ограничений.
Симплекс-метод, сильно улучшенный и усиленный другими методами, по-прежнему остается неотъемлемой частью современного программного обеспечения.
Идея симплекс-метода
Подробности симплекс-метода выходят за рамки этой книги, но мы постараемся объяснить его суть на нашем маленьком примере.
Для начала давайте посмотрим, какие в принципе значения могут принимать переменные, чтобы не нарушить наших ограничений. Например, мы можем взять АЮ = 58, БЮ = 8. В этом случае получается решение, которое мы записали в виде табл. 2.2.
Таблица 2.2. Пример решения, где АЮ = 58, БЮ = 8
Ограничения выполнены, и оба клиента получили заказанное количество листов.
Но это не единственное решение. Например, мы могли отправить больше листов с дешевого южного склада клиенту А, скажем 60 листов, и 10 листов клиенту Б. Легко увидеть, что доставка клиенту А теперь обойдется в
5×60=300 руб.,
а доставка клиенту Б будет стоить
10×10+30×15=550 руб.
Тогда общая стоимость получается не 864, а 850 рублей, то есть немного меньше, чем указано в табл. 2.2.
Чтобы не выбирать наугад, нужно посмотреть на все возможные решения, которые удовлетворяют ограничениям. Мы их изобразили на рис. 2.1. По оси х мы откладываем АЮ, а по оси у – БЮ. Любая точка в заштрихованной области удовлетворяет ограничениям. В том числе точка (58,8), как в таблице выше.
Рис. 2.1. Решения, удовлетворяющие ограничениям
Примечание: любая точка в заштрихованной области удовлетворяет всем ограничениям. Точка (58,8) это решение из таблицы выше. Угловые точки (25,40), (30,40), (60,10) и (60,5) кандидаты на оптимальное решение (см. объяснение в тексте).
Ниже во врезке мы объясняем, как получилась заштрихованная область. Объяснения соответствуют уровню средней школы. При желании их можно пропустить.
Все значения АЮ и БЮ положительные.
Вертикальная прямая линия АЮ = 60 обеспечивает ограничение АЮ ≤ 60. Все возможные значения находятся либо на ней, либо слева от нее.
Аналогично горизонтальная прямая линия БЮ = 40 обеспечивает ограничение БЮ ≤ 40. Все возможные значения находятся либо на ней, либо под ней. Выражение штрихпунктирной прямой АЮ + БЮ = 70 можно переписать в более привычном виде:
БЮ = 70 − АЮ,
поэтому прямая идет под отрицательным углом 45°. Заметьте, что она пересекает ось х (в нашем случае ось АЮ), когда БЮ = 0 и, соответственно, АЮ = 70. Нам нужно, чтобы выполнялось неравенство АЮ + БЮ ≤ 70, то есть
БЮ ≤ 70 − АЮ.
Значения, удовлетворяющие этому неравенству, расположены на штрихпунктирной прямой или под ней.
Аналогично пунктирная прямая АЮ + БЮ = 65 обеспечивает ограничение АЮ + БЮ ≥ 65. Значения, которые удовлетворяют этому неравенству, находятся на этой прямой или над ней.
Заштрихованная область, включая границы, удовлетворяет всем ограничениям.
Важно отметить, что заштрихованная область – это четырехугольник с прямыми сторонами, поскольку все наши ограничения линейные, то есть их можно изобразить с помощью прямых линий. Данная область называется областью допустимых значений, потому что все значения в ней удовлетворяют всем ограничениям. Иначе говоря, любое решение из этой области физически возможно или допустимо.
Фундаментальное свойство задач линейного программирования заключается в том, что оптимальное решение обязательно находится в углах области допустимых значений. Это происходит потому, что наша стоимость тоже линейная. Когда мы движемся по прямой – горизонтальной, вертикальной или наклонной, – стоимость может либо только уменьшаться, либо только увеличиваться, пока мы не наткнемся на угол и идти дальше по той же прямой станет невозможно.
Для подготовленного читателя в приложении в конце книги мы приводим более формальное обоснование того, почему оптимальное решение задачи линейного программирования обязательно найдется в одном из углов области допустимых значений.
В нашем маленьком примере углов всего четыре: (25,40), (30,40), (60,10) и (60,5). Мы можем легко подставить значения и подсчитать, что самое лучшее решение в точке (30,40), то есть с южного склада нужно отправить 30 листов клиенту А и 40 листов клиенту Б. Оставшиеся 30 листов клиенту А следует отправить с северного склада. Результат приведен в табл. 2.3:
