Задача о краске
Протокол «контрольного взвешивания» краски в среде Mathcad приведен на рис. 3.11. Комментарии поясняют, что происходит в формулах. Во-первых, функция Maximize, как и ожидалось, дала дробный ответ (см. пункт 2) – маленьких банок можно не брать, если можно брать дробное количество больших. Пришлось, вспомнив эпиграф и название этюда, перейти к перебору вариантов. В Mathcad-документе формируются две матрицы с именами Об (пункт 3.2) и Ст (пункт 3.3), элементы которых (их 1088 – у матриц 17 столбцов и 64 строки) хранят значения объема (Об) и стоимости (Ст) краски в зависимости от комбинаций расфасовки. Далее (пункт 3.4) некоторым элементам матрицы Об присваиваются нулевые значения, если данные комбинации расфасовки не проходят по стоимости. Остальное – ловкость рук и никакой математики: в пункте 3.5 определяется номер строки (переменная N_15) и номер столбца (N_55) матрицы Об, на пересечении которых находится элемент с максимальным значением. Ответ (6 маленьких барабанов и 15 больших) неприятно удивил Олю. Она невольно обманывала меня на 5 литров краски и на 139 тыс. руб.
Метод поиска координат точки максимума, реализованный на рис. 3.11 (двойная сумма), имеет существенное ограничение: в анализируемой матрице (у нас это Об) должен быть только один максимальный элемент. Если их несколько, то ответ будет неверен: в переменные N_15 и N_55 будут записаны суммы координат точек с максимальным элементом. Мы это наблюдали в пункте 2 на рис 3.9.
Так Mathcad сэкономил мне почти полторы сотни тысяч рублей. Деньги не такие уж большие, но если присовокупить к ним новый компьютерный этюд в книгу, новую тему лекции и новую лабораторную работу по информатике, а также гонорар за эту книгу, то игра стоила свеч.
Вернувшись из Тамбова домой в Москву, я в спокойной обстановке у своего родного компьютера еще раз проанализировал задачу. И вот что получилось.
Во-первых, заставить Решатель Excel правильно «разъяснять» задачу о краске можно было, изменив начальные установки Решателя. А для этого нужно было не полениться и нажать на кнопку Параметры... в диалоговом окне Поиск решения. В новом диалоговом окне Параметры поиска решения достаточно было допустимое отклонение уменьшить с 5 до 1%. После этого правильное решение (15 больших и 6 маленьких барабанов) было бы найдено. Честно говоря, в Excel плох не Решатель, а его начальные установки. Очень мало пользователей Excel, прибегающих к услугам Решателя, нажимают кнопку Параметры... Тот же, кто разбирается в сути установок оптимизации, как правило, с Excel не работает. Отсюда и недоразумения.
Во-вторых, и Оля, и Excel, и Mathcad в разной степени меня немножко обманули[21]: 910 литров краски можно было отгрузить и другим вариантом – 13 маленьких и столько же больших барабанов[22]. В этом случае осталось бы «сдачи» всего 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-литровый барабан можно взять в ремонтируемую аудиторию и там полностью использовать.
Неверное решение задачи получается не только из-за плохих методик или дефектных программных средств, но и из-за того, что пользователь сам толком не знает, чего он хочет. Все программы решения задачи линейного программирования требуют четкого формулирования одной единственной целевой функции[23]. При решении учебных задач цель ясна. А что является целью в жизни? Но это уже не математика, а философия...
У метода перебора, реализованного на рис. 3.11, есть три собственных ограничения:
1) число переменных не может быть больше двух, так как в среде Mathcad есть векторы и матрицы, но нет тензоров (трех- и более мерных матриц);
2) при чрезмерном размере матрицы компьютер отказывается иметь с ней дело, выдавая протестующее сообщение типа «не хватает памяти»;
3) счет (если перебор можно назвать счетом) может длиться нестерпимо долго.
Первые два ограничения снимаются при переходе от метода формирования матрицы (рис. 3.11) к методу перебора вариантов с запоминанием только оптимального плана, который можно реализовать средствами программирования, что мы и сделаем в этюде 6 (см. рис. 6.31 и 6.32).
Метод перебора оказывается незаменимым (то есть опять же бывает не таким уж извращенным), когда задача, оставаясь целочисленной, теряет свою линейность[24]. В этом случае традиционные методы (например, симплекс-метод) часто оказываются бессильными.
Тем не менее реализация метода перебора в среде Mathcad всегда будет извращением чистой воды. Mathcad – это программа интерпретирующего типа с низкой скоростью выполнения исходного текста. Для перебора нужны не просто компиляторы, а компиляторы, оптимизирующие время выполнения программы.
