Задача о краске
Мне нравится рассказывать об этой задаче, которая принадлежит В. Очкову, и взята "из жизни" в период середины 90-х годов, когда бартер играл основную роль при расчетах. С тех пор ситуация в экономике существенно изменилась в лучшую сторону, хотя до нормы еще далеко. При описании содержательной постановки я хочу сохранить весь внешний "антураж". Заметьте, цены в те годы примерно на 4 порядка отличались от нынешних. Суть задачи такова. Коллектив программистов под руководством В. Очкова написал программу и продал ее за 14 миллионов лакокрасочному предприятию. "Живых" денег предприятие не платило, но могло в пределах указанной суммы расплатиться краской - своей продукцией. Институт, в котором работал В. Очков, нуждался в краске и готов был оплатить привезенную краску. Краска выпускалась в двух видах тары - больших и малых банках (барабанах), емкость которых составляла 55 и 15 литров, а стоимость пустых барабанов составляла - 30 и 24 тысячи рублей. Литр краски стоит 14 600 рублей. Спрашивается, сколько больших и сколько малых барабанов следует взять, если учесть, что институт заинтересован получить как можно больше краски, а создатель программы скорее заинтересован в том, чтобы как можно меньше денег оставить "лакокрасочникам". Типичная оптимизационная задача!
Для решения этой задачи (кстати, это задача с целочисленными переменными) автор использовал Решатель. Благо Excel уже тогда можно было найти повсюду, в том числе и в бухгалтерии лакокрасочного завода. В поставленной Решателю задаче требовалось максимизировать объем получаемой краски при естественном ограничении на сумму имеющихся денег и ограничений целочисленности на искомые переменные - число больших и малых барабанов. Используя установки параметров, принятые по умолчанию, найденный Решателем "оптимальный" ответ гласил, следует взять 2 малых и 16 больших барабанов с краской. Это давало 910 литров краски, но оставляло предприятию 186000 рублей. Возможно, остаток денег был большой, но В. Очков не поверил Решателю и стал искать другой ответ. И нашел лучшее решение. Оно таково: следует взять 15 больших и 6 малых барабанов. При этом краски будет больше (915 л), а денег, заработанных автором, у завода останется значительно меньше (47 000 руб.). Надеюсь, Вы понимаете, что второе решение было получено за счет разумного управления параметрами Решателя. Я напомню, что когда решается задача с целочисленными ограничениями на переменные, вначале ищется решение без учета таких ограничений. Здесь такое оптимальное решение можно найти самому, поскольку понятно, что максимизации объема можно добиться, закупая краску в больших банках. Наша сумма денег позволяет взять примерно 16,8 больших барабанов, т. е. около 924 л. Но брать неполные банки нельзя и, следовательно, нужно искать целочисленное значение. В окрестности найденного оптимального решения Решатель ищет ближайшую целочисленную точку. Значение целевой функции в ней не должно отличаться более чем на величину, заданную параметром Tolerance. Напомним, по умолчанию это значение равно 5%, что в данном примере немало: 46,2 л. Первое решение, выданное Решателем, вполне укладывается в допустимые рамки. Если уменьшить значение параметра Tolerance до 1%, Решатель найдет другое, действительно оптимальное целочисленное решение.
История с "оптимальными" решениями имеет продолжение. Рассмотрим еще одно решение с другой целевой функцией, в котором минимизировалась сумма денег, оставляемая заводу. В этом решении следует взять 37 малых и только 6 больших барабанов. Тогда заводу останется только 11 000 руб., так что краска будет закуплена почти на все заработанные автором деньги. Правда, краски будет меньше, - всего 885 литров. Но! Когда это решение было показано тем, кому предназначалась краска, они также признали его наилучшим. С большими барабанами больше возни, и краски на переливах из большого барабана теряется больше. Если ввести дополнительные ограничения на потери, то нормальное решение 37 и 6 может быть получено и при максимизации объема закупаемой краски. Обратите внимание, как, решая, по сути, одну и ту же оптимизационную задачу, можно найти принципиально разные решения. Многое зависит от удачной постановки, выбора критериев, ограничений. Немаловажное значение имеет и умение управлять параметрами алгоритмов оптимизации.
Давайте и мы решим эту задачу. Приведу два решения с различными целевыми функциями. Я не буду подробно рассказывать, в какие ячейки помещаются исходные данные, какие формулы записаны в ячейках. Все это, как и результаты, показано на рисунке:
Рис. 2.24. Две постановки и два решения задачи о красках
В первой постановке этой задачи максимизируется объем закупаемой краски при ограничении на сумму истраченных денег и требовании целочисленности искомых переменных. Во второй постановке минимизировалась сумма денег, оставляемая заводу. В качестве целевой функции можно выбирать функцию, задающую остаток денег, или рассматривать квадратичную целевую функцию. Ограничения на положительность переменных, их целочисленность и на остаток денег во всех случаях одни и те же. Вот как выглядит окно Решателя в момент постановки задачи, когда минимизируется остаток денег:
увеличить изображение
Рис. 2.25. Минимизация остатка денег
