|
Исследование операций и имитационное моделирование
|
Содержание
Затруднительно
дать определение исследованию операций - слишком велик арсенал используемых
им методов и широки применения. Для меня исследование операций начинается
там, где появляется линейное программирование. Т.е. исторически - брошюрой
Л.В. Канторовича,
а вернее - разработкой симплекс-метода Дж. Данцигом.
Но вы понимаете, что это весьма спорная точка зрения...
Пионерская работа Л.В. Канторовича была выполнена в нашей стране, но было
ли тогда в России место для исследования операций? Я присоединяюсь к тому
мнению, что собственно исследование операций фактически отсутствовало, а
развивались его математические методы. В этом вопросе я нахожусь под
впечатлением от книг Н.Н. Моисеева,
где приведены характерные примеры внедрения разработок
ВЦ РАН, и ряда других
научных авторитетов.
Будем надеяться, что с ростом экономической активности в нашем обществе будут
развиваться и приложения исследования операций, а последствия
приснопамятной борьбы с кибернетикой будут наконец-то изжиты!
Очень приятно, что мое намерение посвятить часть своей домашней страницы исследованию операций и связанному с ним имитационному
моделированию вызвала довольно горячий отклик среди ее посетилей - лишь их призыв к моей совести был способен привести к результату,
который вы сейчас наблюдаете перед собой... Хотя нужно заметить, что некоторые не стали ждать давно обещанного мной гипертекста и
получили нужные им программы посредством FTP. Слава этим безвестным энтузиастам исследования операций!
Вверх
В последние годы в сообществе исследователей операций все большую популярность приобретает пакет для
решения задач целочисленного и смешанного целочисленного линейного программирования lp_solve, разработанный
Михаелем Беркеларом из Технологического университета Эйндховена (Нидерланды).
Пакет распространяется в виде исходных текстов на Си по лицензии GNU, но это не единственное его достоинство. Еще - большая размерность
решаемых задач вследствие компактного представления разреженных матриц, развитый интерфейс прикладного
программирования, поддержка простого алгебраического формата представления задач и формата MPS, а
также хорошая переносимость, следствием которой и является предлагаемая вам версия 4.0.1.10 этой программы для DOS.
Она не требует использования дополнительных драйверов DPMI или менеджеров виртуальной памяти, как в других ее DOS-версиях, хотя
может быть именно по этой причине работает медленнее, чем откомпилированная Borland C, и не может использовать дисковую память, как версия,
полученная при помощи DJGPP. Для запуска задачи на решение (допустим, что она сохранена в файле PROBLEM.MPS, а ваш процессор
не хуже 386) в ответ на приглашение DOS достаточно набрать:
lp_solve -mps problem.mps >problem.res
Для получении подсказки запустите оптимизатор с опцией -h.
Последние версии пакета с документацией, исходными текстами и готовыми исполняемыми модулями для
Win32 находятся на сайте Yahoo!, а более
ранние вы сможете найти на FTP-сервере
Технологического университета Эйндховена.
В Сети вы также сможете найти результаты сравнительных испытаний lp_solve и ряда коммерческих пакетов, но самые острые
впечатления получите, запустив на решение задачи из набора тестов MIPLIB3, скажем, на Intel Pentium 4 3.06 GHz - опять окажется, что это все таки
не ASCI White или Cray XMP, и даже не SPARCstation ;-).
P.S. Если ваша целочисленная задача решается недопустимо долго и вы уже начинаете
подозревать ее в NP-сложности, попробуйте для нее опцию -c. Это может
радикально ускорить ее решение за счет изменения порядка ветвления
в методе ветвей и границ. ВНИМАНИЕ: С 4-ой версии возможности по управлению решением
существенно расширились - вам придется перепробовать несколько опций...
На всякий случай здесь предыдущая версия.
За последний год-полтора размер программы увеличился почти в два раза, и это «распухание» приводит к тому, что
более рання версия может на конкретной задаче показать лучшие результаты :(.
P.P.S. Иногда, когда lp_solve не может найти оптимального решения
вашей задачи вследствие потери устойчивости вычислительного алгоритма, стоит попробовать запустить его с
опцией -i . Последнее из полученных таким образом решений может оказаться весьма
близким к оптимальному, которое к тому же нельзя будет найти даже при помощи известных коммерческих пакетов...
Вверх
О роли электронных таблиц в исследовании операция можно сказать одно - сейчас
уже непонятно, как раньше обходились без них! Практически все методы исследования операций могут быть реализованы без выхода из электроной таблицы.
Современные встроенные оптимизаторы решают линейные и нелинейные задачи математического программирования, причем довольно большой размерности.
Но что делать, когда размерность задачи все же больше, чем возможности нашей любимой Lotus 123, Quattro Pro или (нелюбимой, но все же!) Excel?
Можно, конечно, купить усовершенствованную версию встроенного оптимизатора ;-), но лучше воспользоваться способностью вашей
электронной таблицы сохранять данные в текстовом файле. Т.е. вначале записать задачу в форматированном виде
(имена ограничений, коэффициенты и правые части, имена переменных, символы конца строки), затем сохратить ее
в текстовом файле *.LP, выйти из таблицы, запустить lp_solve, при успешном решении
загрузить таблицу снова и импортировать в нее текстовый файл с результатом решения. А простые пакетный файл и
макропрограмма разбора решения способны полностью автоматизировать ваш анализ!
При этом задача большой размерности не только записывается в привычном алгебраическом формате - в связи с этим в нее удобнее, чем во встроенных
оптимизаторах, вносить изменения. Сочетание электронной таблицы с доступным внешним оптимизатором существенно расширяют
наши возможности в исследовании операций.
P.S. Ради полноты картины вынужден заметить, что элегантность и прозрачность подхода Дж.Хо к применению электронных таблиц для оптимизации
до сих пор остаются непревзойденными (cм. Ho J.K. Linear and
dynamic programming with Lotus 1-2-3 Release 2. -Portland: MIS, 1987.-330 p.).
Вверх
В этом разделе предполагается поместить исходные коды из ряда книг (например,
Davies R.M., O'Keefe R.M. Simulation Modelling with Pascal.-N.Y.etc.: Prentice
Hall,1989.-302 p.), посвященного предмету, но для переговоров с издательствами времени пока не нашлось. Планируется "осветить" подобным образом
дискретно-событийный, процессный и 3-фазный подходы, а также возможности электронных таблиц на ряде примеров из научной периодики.
Вверх
Начнем с примечательных персональных сайтов:
Сетевые версии ведущих журналов:
Архивы задач, справочники и прочие полезные ресурсы:
P.S. Вы еще не член The Operational Research Society ? А на usenet.sci.op-research подписаны? Тогда порядок!
А если серьезно, то прошу сообщать
ссылки на отечественные ресурсы.
Вверх
Если у вас есть вопросы или предложения, шлите их письмом или
оставьте запись в гостевой книге.
Вернуться на главную страницу