Мир объектов Excel 2000


Задача о краске


Мне нравится рассказывать об этой задаче, которая принадлежит В. Очкову, и взята "из жизни" в период середины 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.  Минимизация остатка денег

Ограничения целочисленности, как я уже говорил, накладываются на переменные довольно просто. Для этого, задавая ограничения в левой его части, нужно указать диапазон регулируемых ячеек, а отношение, связывающее левую и правую часть ограничения, задать как int. Как видите, в правой части появляется слово integer - признак целочисленности переменных. Вот как изменялись установки в окне Параметры:

Изменение установок окна Параметры

Рис. 2.26.  Изменение установок окна Параметры

В этом окне включен флажок линейности модели, положительности переменных, автоматический выбор масштаба, а также уменьшено до 1% значение параметра Tolerance. Решатель находит наилучшее решение - 37 малых барабанов и 6 больших. Результаты можно увидеть на рисунке:

Успешное решение и уведомление о "неуспехе"

увеличить изображение
Рис. 2.27.  Успешное решение и уведомление о "неуспехе"

Однако заметьте, Решатель, получив правильное решение, вместе с тем уведомляет о неуспехе. Причина этого, если вспомнить то, что я говорил о настройках параметров, понятна. Найденное решение отличается от оптимального, нецелочисленного решения более чем на 1%, - отсюда и неуспех. Какие уроки можно извлечь из этой истории? Оптимизационные задачи сложны, сложен и сам инструментарий, так что не следует доверять первому полученному решению. Всегда следует пытаться решить эту же задачу в другой постановке. Правильная постановка задачи и умелое управление возможностями Решателя являются залогом успеха. Еще один вывод состоит в том, что только весьма квалифицированный пользователь способен применять Решатель в своих задачах. Чаще всего, программисту приходится делать надстройку, облегчающую пользователю решение той или иной оптимизационной задачи. Я посвятил отдельную главу созданию подобного инструмента, а сейчас дам краткий обзор методам программной работы с Решателем.




Начало  Назад  Вперед