Как я продавал программу
(компьютерный этюд)
Валерий Очков
У Михаила Жванецкого часто спрашивают, откуда он берет темы для своих миниатюр. “Выглядываю в окно и прислушиваюсь к разговорам на улице”, — таков ответ великого сатирика. Житейские сюжеты стоит коллекционировать и для написания компьютерных этюдов, что является хобби автора этой статьи [ 1-4] .
Автор по профессии преподаватель ВУЗа — Московского энергетического института, где он читает курс лекций по информатике, а также руководит группой технологов и программистов, разрабатывающих обучающие программы и компьютерные тренажеры для ТЭС и АЭС. Электростанциям и энергообъединениям нужны наши программы, но их приобретению мешает пресловутый кризис неплатежей. Вот какой компьютерный этюд (см. сноску 2) имел место совсем недавно — в марте 1997 г..
Акционерное общество Тамбовэнерго, не имея свободных денег, тем не менее, изъявило желание приобрести наши программы. Котовскому лакокрасочному заводу (Тамбовская обл.) для производства нужна электроэнергия. Московскому энергетическому институту для ремонта аудиторий требуется краска. Нашей научной группе необходимо новое компьютерное “железо” и инструментальные средства. Для решения подобных проблем человечество еще на заре цивилизации придумало деньги. Перипетии перехода нашей страны от непонятно чего к рынку возродило натуральный обмен — бартер. В вышеописанной товарной цепочке не хватало одного звена, чтобы она замкнулась. К счастью, в МЭИ поступила партия компьютеров, парочку которых мы договорились обменять на краску. В этой комбинации заключается только часть описываемого компьютерного этюда, если вспомнить шахматное толкование слова “этюд” — решение головоломки составлением цепочки ходов фигур.
Вторая часть компьютерного этюда имела место уже в Тамбове и в Котовске — на лакокрасочном заводе (ЛКЗ). В Тамбовэнерго мне (автор переходит к рассказу от первого лица) после сдачи программ выдали доверенность на получение лакокрасочной продукции на 14 млн. руб. в счет задолжности завода за электроэнергию и отправили в Котовск. В отделе сбыта ЛКЗ сначала наотрез отказались отпускать краску за какие-то там непонятные задолжности, а не за живые деньги, но после угрозы отключения света и тепла согласились. Краска, которая мне подходила, вернее не мне, а отделу снабжения МЭИ, стоила 14 600 рублей за литр и разливалась в тару (в барабаны, если следовать москательному жаргону, которого я нахватался в Котовске) объемом 15 и 55 литров. Пустые барабаны стоили 24 и 30 тыс. рублей, соответственно. Работница отдела сбыта ЛКЗ (ее звали Оля), выписывая на компьютере накладную, спросила, в каких емкостях (пардон, барабанах) я возьму краску. Чутье давнего собирателя компьютерных этюдов сразу подсказало, что тут кроется типичная и, главное, реальная задача линейного программирования, где целевая функция, которую нужно максимизировать, — суммарный объем краски, переменные — количества наполненных краской барабанов по 15 и 55 литров, которые нужно забрать, и три ограничения — (1) стоимость краски не должна превышать оговоренных с Тамбовэнерго 14 млн. рублей, (2) нельзя брать неполную банку (ограничение на целочисленность переменных) и (3) количества банок разной вместимости не должны быть отрицательными числами. Оля вызвалась помочь решить эту оптимизационную задачу и тут же с помощью калькулятора прикинула, что мне нужно взять 16 больших и 2 маленьких барабанов, вмещающих 910 литров краски на сумму 13 млн. 814 тыс. рублей. Вспомнив, как я отчаянно торговался в Тамбовэнерго и все-таки увеличил цену программ с 12 до 14 млн. руб., я спросил у Оли, а можно ли не терять 186 тысяч. Она сказала, что нет, так как такие задачи решает чуть ли не каждый день, оптимизируя не только стоимость краски, но и ее загрузку в контейнеры различной вместимости, и что она “собаку съела“ на решении таких проблем.
Наблюдая за “танцем” Олиных пальцев на кнопках калькулятора и за числами на его дисплее, я понял, что Оля использует так называемый “рабоче-крестьянский” и, главное, надежный алгоритм оптимизации: сначала выбирается краска в большой таре, а затем остаток денег (или объема контейнера) заполняется краской в маленькой таре. Примерно так, мы пакуем чемодан, отправляясь в поездку, — сначала кладем в него крупные вещи, а потом напихиваем пустые пространства всякой мелочью. Еще раз вспомнив Вийона (смотри сноску 9), я спросил у Оли, почему она для таких задач не использует компьютер и, в частности, табличный процессор Excel, рабочий лист которого как будто специально был выведен на экран ее компьютера. Я тут же вызвался показать, как это делается. В среде Excel есть так называемый Решатель (Solver), диалоговое окно которого (см. рис. 1) вызывается командой Найти решение... из меню Сервис. В этом окне пользователь указывает ячейку, хранящую целевую функцию, значение которой нужно максимизировать, ячейки с переменными поиска (в начале оптимизации они либо пустые либо хранят значения первого приближения к максимуму) и ограничения.
Рис. 1
Алгоритм оптимизации с помощью Решателя Excel можно назвать “ленивым”: пользователь формирует таблицу расчета (рис. 1) и говорит: “По щучьему велению, по моему хотению сделай так, чтобы” целевая функция приняла максимальное (минимальное, определенное) значение, но при этом были выполнены все ограничения”. Для этого пользователю достаточно нажать кнопку Выполнить (см. рис. 1). Решатель Excel выдал нам старый результат — 16 больших и 2 маленьких барабана. Но сдаваться не хотелось.
Есть хорошее правило проверять решение задачи не только другими методами, но и другими программными средствами. Кроме того, следует не забывать о KISS-принципе программирования. С поцелуями он ничего общего не имеет, хотя хорошее отношение к решаемой задаче и к компьютеру в нем просматривается. KISS — это аббревиатура английской фразы: “Keep It Simple, Stupid! — Делай это проще, дурачок!”. Она призывает решать поставленную задачу наипростейшими способами и прибегать к изощренным алгоритмам и методикам только тогда, когда эти способы не годятся из-за длительности времени счета или из-за нерационального использования других ресурсов человека и/или компьютера11.
Простейший способ решить на компьютере поставленную задачу — это перебрать все варианты и остановиться на оптимальном. Благо вариантов не так уж много — 1170: на отпущенные 14 миллионов можно было взять не более 17 больших барабанов с краской или не более 64 маленьких12. Перебор можно назвать “компьютерно-рабоче-крестьянским” методом решения. Но помимо прочего он может дать стопроцентную уверенность не только в правильности, но и в едиственности найденного решения и даже показать, что таких решений несколько. А такая ситуация нередка в задачах целочисленного линейного программирования (см., например, этюд “Рассказ плановика” о поиске максимального плана выпусков компьютера в [2]).
Итак, перебор. Следуя вышеописанному правилу, новый метод решения задачи необходимо совместить с новым программным средством для его реализации. Это, конечно, можно было сделать и в среде Excel, составив таблицу всех решений и/или13 написав программу перебора на языке Visual Basic for Applications (VBA), встроенном в Excel. Но у Оли на компьютере был установлен еще и Mathcad (феномен рояля в кустах). Эта математическая программа фирмы Mathsoft. Inc. в настоящее время очень популярна у студентов и школьников. Она довольно успешно решает задачи самого разного плана (включая и экономические) без обращения к чистому программированию (Basic, C, Pascal и др.). Кроме того, я сейчас заканчиваю работу над второй редакцией книги [4], а по сути пишу новую по седьмой версии Mathcad, которую тестирую как официальный beta-tester. Пример с краской эту книгу только украсит (нечаянный каламбур).
Рис. 2
Протокол “контрольного взвешивания” краски в среде Mathcad приведен на рис. 2. Комментарии (синий цвет) поясняют, что происходит в формулах (черный цвет): формируются две матрицы с именами Объем (п. 3) и Стоимость (п. 4), элементы которых (из 170 — у матриц 18 столбцов и 65 строк) хранят значения объема и стоимости краски в зависимости от комбинаций расфасовки; далее (п. 5) некоторыми элементам матрицы Объем присваиваются нулевые значения, если данные комбинации расфасовки не проходят по стоимости. Остальное — ловкость рук и никакой математики: в п. 6 определяются номер строки (переменная N_15) и столбца (N_55) матрицы Объем, на пересечении которых находится элементом с максимальным значением. Ответ (6 маленьких барабанов и 15 больших) неприятно удивил Олю. Она невольно обманывала меня на 5 литров краски и на 139 тыс. руб. Я уже давно [5] подозревал, что Решатель таблиц Excel не просто плохо справляется с работой, но и частенько врет. И не просто врет, а настаивает на своем вранье: если в ячейки B9 и B10 таблицы на рис. 1 записать в качестве первого приближения 6 и 15 (оптимальный план расфасовки краски)14 и вызвать Решатель, то он вернет старые неверные числа 2 и 16. Вот так-то! Но это не вина, а беда Решателя, и я об этом еще скажу.
Когда готовилась к публикации статья [5], я связался с московским представительством Microsoft15 (с группой поддержки Excel) и сообщил, что встроенный в Excel Решатель нередко выдает неверный результат даже по простейшим задачам (функция Розенброка, функция Пауэла и др.). Мой запрос был отфутболен в Мюнхен — в европейское представительство Microsoft. Оттуда пришел не ответ, а отписка — мол, это не Решатель плох, а очень уж сложные задачи вы ему подсунули. Решатель, встроенный в Excel, — это разработка субподрядчиков Microsoft — фирм Frontline System и Optimals Methods, которым я также пожаловался, вернее, передал суть критики.
Третий вариант названия данной статьи “Как Mathcad сэкономил мне 139 тысяч рублей”. Деньги не такие уж большие, но если присовокупить к ним новый компьютерный этюд в книгу, новую тему лекции и новую лабораторную работу по информатике, а также гонорар за эту статью, то.... игра стоила свеч.
Вернувшись из Тамбова домой в Москву, я в спокойной обстановке у своего родного компьютера еще раз проанализировал задачу. И вот что получилось.
Во-первых, заставить Решатель Excel правильно “разъяснять” задачу о краске можно было, изменив начальные установки Решателя. А для этого нужно было не полениться и нажать на кнопку Параметры... в диалоговом окне Поиск решения (см. рис. 1). В новом диалоговом окне Параметры поиска решения достаточно было допустимое отклонение уменьшить с 5 до 1%. После этого правильное решение (15 больших и 6 маленьких барабанов) было бы найдено. Честно говоря, в Excel плох не Решатель, а его начальные установки. Очень мало пользователей Excel, прибегающих к услугам Решателя, нажимает кнопку Параметры... Тот же, кто разбирается в сути установок оптимизации, как правило, с Excel не работает. Отсюда и недоразумения.
Во-вторых, и Оля, и Excel, и Mathcad в разной степени меня немножко обманули: 910 литров краски можно было отгрузить и вторым вариантом (см. п. 7 на рис. 2, который был вставлен уже в Москве) — 13 маленьких и столько же больших барабанов. В этом случае осталось бы “сдачи” всего 12 тыс. рублей. Более того, решение задачи о краске с новой целевой функцией (стоимость) дало еще один результат: 37 маленьких и 6 больших барабанов, выбирающий еще одну тысячу из Тамбовэнерго.
| Вариант расфасовки (число маленьких барабанов/число больших барабанов) | 2/16 |
6/15 |
13/13 |
37/6 |
| Объем краски (л) | 910 |
915 |
910 |
885 |
| Остаток невыбранных денег (руб.) | 186 000 |
47 000 |
12 000 |
11 000 |
В-третьих, когда я показал эту таблицу в отделе снабжения МЭИ, то мне было сказано, что самый оптимальный вариант и для меня (мне важны деньги) и для МЭИ (ему нужна краска) четвертый: у Тамбовэнерго были бы выбраны почти все деньги, а 885 литров, как это не покажется странным, больше чем 910 и 915. Дело в том, что при крупной расфасовке теряется много краски из-за переливов в меньшую тару. 15-и литровый барабан можно взять в ремонтируемую аудиторию и там полностью использовать.
Неверное решение задачи случается не только из-за плохих методик или дефектных программных средств, но и из-за того, что пользователь сам толком не знает, чего он хочет. Все программы решения задачи линейного программирования требуют четкого формулированная одной единственной целевой функции. При решении учебных задач цель ясна. А что является целью в жизни! Но это уже не математика, а философия.
Из задачи все выжито, поэтому я заканчиваю статью.
Литература и другие источники дополнительной информации:
Web-страница фирмы Mathsoft, Inc.: http://www.mathsoft.com
Web-страница фирмы СофтЛайн — официального представителя Mathsoft, Inc. в России: http://www.softline.ru, тел.: (095) 232-00-23
Отзывы на статью
1.
Уважаемый господин Очков!
Ваша статья об оптимизационном решении "задачи с краской" получила неоднозначную реакцию. Позвольте предложить Вам еще один пример из жизни, с которым столкнулось наше предприятие.
Станки по производству пластмассы методом литья под давлением могут производить только определенный предмет в течение смены (в нашем примере это или тарелка, или миска, или стакан, или набор ложек и вилок). Есть план по производству комплектов из данной посуды. В один комплект входит разное количество предметов (см. верхнюю таблицу строка 5.). Известно, что для выполнения данного плана понадобится закупка дополнительного оборудования, но предварительно надо узнать, сколько комплектов можно произвести с помощью одного станка для определения объемов закупки. Исходные данные представлены в формате Excel. В таблицах жирным шрифтом выделено решение начальника отдела по подготовке производства. Интересно было бы узнать Ваше решение (если это возможно - то методом Excel).
Если Вас заинтересовал данныйй пример и требуются дополнительные пояснения к условию - всегда рады ответить Вам.
2.
Здравствуйте, Валерий!
С большим удовольствием прочитал в КомпьютерПресс Вашу красочную статью. Она хороша, как по форме, так и содержанию.Мне она была интересна вдвойне, поскольку я только закончил описание Решателя В настоящее время я с моим коллегой - Дехтярем М.И. работаю над книгой по программированию на VBA в Office 97. Эта книга должна выйти в издательстве "Русская редакция" . Если Вы не будете возражать, то мне хотелось бы привести Вашу задачу в нашей книге, естественно, с соответствующими ссылками. В ней есть много поучительного. Несколько слов о Решателе. Мне кажется Вы чуть сгустили краски - он не так уж и плох. Конечно, это не Универсальный Решатель. ( но где найти такой?) Решая уравнение 4-й степени, я не получил корень при заданном начальном приближении, хотя обычный Ньютон дал ответ. С Вашей задачей Решатель справляется отлично, по крайней мере с его точки зрения. Как он решает целочисленные задачи - вначале он находит оптимальное решение без учета этих ограничений - в данном случае это решение 16, 8 больших банок, что дает, если не ошибаюсь 924л. краски. Затем находит ближайшую целочисленную точку в пределах точности, заданной параметром Tolerance (Зачем я Вам это объясняю не знаю - Вы знаете это не хуже меня. Просто, я выступаю адвокатом Решателя). Хочу заметить, что Решатель может получить 4-е решение, оптимальное для Вас, не только при минимизации остатка денег, но и при максимизации объема краски, если ввести потери на переливку для больших банок. Решение получается, когда эти потери составляют 10% (5,5л.) Еще раз повторяю, что с удовольствием прочитал Вашу статью.
С уважением Владимир Биллиг.