MathCAD

       

Определение плана выпуска стульев: перебор


Оказывается, при переборе всех вариантов выпуска стульев (а их не так уж много – на рис. 3.10 мы просчитали 150 на 150 = 22 500 вариантов) можно найти два оптимальных плана, причем самый оптимальный и по цене, и по количеству (20+112=132 стула стоимостью 1504 у.е.) – это не округление дробного ответа, полученного на рис. 2.9. Возвращаясь к теме враждебности задачи, можно так подобрать ее условия, что ответ окажется совсем вдалеке от первоначального дробного…

Это был эпиграф, приступаем к рассказу.

У Михаила Жванецкого часто спрашивают, откуда он берет темы для своих миниатюр. «Выглядываю в окно и прислушиваюсь к разговорам на улице», – таков ответ великого сатирика. «А как Вы все это запоминаете?», – следует новый вопрос. «Да я забыть не могу!»

Житейские сюжеты стоит коллекционировать и для написания компьютерных этюдов, что является хобби автора этой книги.

По профессии автор – преподаватель вуза (Московского энергетического института), где он читает курс лекций по информатике и смежным дисциплинам, а также руководит группой технологов и программистов, разрабатывающих обучающие программы и компьютерные тренажеры для ТЭС и АЭС[12]. Электростанциям и энергообъединениям нужны наши программы, но их приобретению мешает пресловутый кризис неплатежей. Вот какой компьютерный этюд имел место в марте 1997 года.

Акционерное общество Тамбовэнерго, не имея свободных денег, тем не менее изъявило желание приобрести наши программы. Котовскому лакокрасочному заводу (ЛКЗ – Тамбовская обл.) для производства нужна электроэнергия. Московскому энергетическому институту для ремонта аудиторий требуется краска. Нашей научной группе необходимо новое компьютерное «железо», инструментальные средства и, естественно, зарплата. Для решения подобных проблем человечество еще на заре цивилизации придумало деньги[13]. Переход же нашей страны от непонятно чего к рынку возродил натуральный обмен – бартер[14]. В вышеописанной товарной цепочке не хватало одного звена, чтобы она замкнулась. К счастью, в МЭИ поступила партия компьютеров, парочку которых мы договорились обменять на краску. В этой комбинации заключается только часть описываемого компьютерного


этюда, если вспомнить шахматное толкование слова «этюд» – решение головоломки путем составления цепочки ходов.

Вторая часть компьютерного этюда имела место уже в Тамбове и в Котовске – на ЛКЗ. В Тамбовэнерго мне (автор переходит к рассказу от первого лица) после сдачи программ выдали доверенность на получение лакокрасочной продукции на 14 млн., естественно, старых рублей в счет задолженности завода за электроэнергию и отправили в Котовск. В отделе сбыта ЛКЗ сначала наотрез отказались отпускать краску за какие-то там непонятные задолженности, а не за живые деньги, но после угрозы отключения света и тепла с трудом, но согласились. Краска, которая мне подходила[15], вернее не мне, а отделу снабжения МЭИ, стоила 14 600 рублей за литр и разливалась в тару (в барабаны, если следовать москательному жаргону, которого я нахватался в Котовске) объемом 15 и 55 литров. Пустые барабаны стоили 24 и 30 тыс. рублей соответственно. Работница отдела сбыта ЛКЗ (ее звали Оля), выписывая на компьютере накладную, спросила, в каких емкостях (пардон, барабанах) я возьму краску. Чутье давнего собирателя компьютерных этюдов сразу подсказало, что тут кроется типичная и, главное, реальная задача линейного программирования, где целевая функция, которую нужно максимизировать, – суммарный объем краски, переменные – количество наполненных краской барабанов по 15 и 55 литров, которые нужно забрать, и три ограничения – (1) стоимость краски не должна превышать оговоренных с Тамбовэнерго 14 млн. рублей, (2) нельзя брать неполную банку (ограничение на целочисленность

переменных) и (3) количество банок разной вместимости не должно быть отрицательными числами[16]. Оля вызвалась помочь решить эту оптимизационную задачу и тут же с помощью калькулятора[17]

прикинула, что мне нужно взять 16 больших и 2 маленьких барабана, вмещающих 910 литров краски на сумму 13 млн. 814 тыс. рублей. Вспомнив, как я отчаянно торговался в Тамбовэнерго и все-таки увеличил цену программ с 12 до 14 млн. руб., я спросил у Оли, а можно ли не терять 186 тысяч – не оставлять их Тамбовэнерго. Она сказала, что нет, так как такие задачи решает чуть ли не каждый день, оптимизируя не только стоимость краски, но и ее загрузку в контейнеры различной вместимости[18], и что она «собаку съела» на решении таких проблем.



Наблюдая за «танцем» Олиных пальцев на кнопках калькулятора и за числами на его дисплее, я понял, что Оля использует так называемый «рабоче-крестьянский» и, главное, ненадежный алгоритм оптимизации: сначала выбирается краска в большой таре, а затем остаток денег (или объема контейнера) заполняется краской в маленькой таре. Примерно так мы пакуем чемодан, отправляясь в поездку, – сначала кладем в него крупные вещи, а потом напихиваем в пустые пространства всякую мелочь. Еще раз вспомнив Вийона (смотри сноску 17), я спросил у Оли, почему она не использует для решения таких задач компьютер и табличный процессор Excel, рабочий лист которого как будто специально был выведен на экран ее компьютера. Я тут же вызвался показать, как это делается. В среде Excel есть так называемый Решатель (Solver), диалоговое окно которого вызывается командой Найти решение... из меню Сервис.

В этом окне пользователь указывает ячейку, хранящую целевую функцию, значение которой нужно максимизировать, ячейки с переменными поиска (в начале оптимизации они либо пусты, либо хранят значения первого приближения к максимуму) и ограничения.

Алгоритм оптимизации с помощью Решателя Excel можно назвать «ленивым»: пользователь формирует таблицу расчета и говорит: «По щучьему велению, по моему хотению сделай так, чтобы»... целевая функция приняла максимальное (минимальное, определенное) значение, но при этом были выполнены все ограничения». Для этого пользователю достаточно нажать кнопку Выполнить. Решатель Excel выдал нам старый результат – 16 больших и 2 маленьких барабана. Но сдаваться не хотелось.

Есть хорошее правило – проверять решение задачи не только другими методами, но и другими программными средствами. Кроме того, не следует забывать о KISS-принципе программирования. С поцелуями он ничего общего не имеет, хотя хорошее отношение к решаемой задаче и к компьютеру в нем просматривается. KISS – это аббревиатура английской фразы: «Keep It Simple, Stupid! – Делай это проще, дурачок!» Она призывает решать поставленную задачу наипростейшими способами и прибегать к изощренным алгоритмам и методикам только тогда, когда простые способы не годятся из-за длительности времени счета или из-за нерационального использования других ресурсов человека и/или компьютера[19].



Простейший способ решить на компьютере поставленную задачу – это перебрать

все варианты и остановиться на оптимальном. Благо вариантов не так уж много – 1088: на отпущенные 14 миллионов можно было взять не более 63 маленьких барабанов с краской или не более 16 больших [20]. Перебор можно назвать «компьютерно-рабоче-крестьянским» методом решения. Но помимо прочего он может дать стопроцентную уверенность не только в правильности, но и в единственности

найденного решения и даже показать, что таких решений несколько. А такая ситуация нередка в задачах целочисленного

линейного программирования.

Итак, перебор. Следуя вышеописанному правилу, новый метод решения задачи необходимо совместить с новым программным средством для его реализации. Это, конечно, можно было сделать и в среде Excel, составив таблицу всех решений и/или написав программу перебора на языке Visual Basic for Applications (VBA), встроенном в Excel. Но у Оли на компьютере был установлен еще и Mathcad (феномен рояля в кустах). Он довольно успешно решает задачи самого разного плана (включая и экономические) без обращения к чистому программированию (BASIC, C, Pascal и др.). Кроме того, в то время я работал над книгой, которую читатель держит в руках. Пример с краской эту книгу только украсит (нечаянный каламбур).


Содержание раздела