В практике решения задач математического программирова ния встречаются такие, системы ограничений которых включа ют ограничения, содержащие все переменные (эти ограничения образуют блок-связку), и ограничения, содержащие некоторые части их (эти ограничения образуют блоки). Система ограниче ний таких задач с двумя блоками изображена на рисунке. В об щем случае число блоков может быть достаточно большим, а за дачи, имеющие блочную структуру, могут быть задачами как линейного, так и нелинейного программирования. Блок-связка Блок 1 Блок 2 Расчленение задачи проводится таким образом, чтобы выде лить подзадачу, которая может быть решена посредством доста точно эффективного алгоритма, применение которого для задачи в целом нерационально. В блочном программировании допуска ется применение как точных, так и приближенных методов реше ния подзадач и предусматривается реализация последовательнос ти итераций, при этом исследование на каждом последующем шаге осуществляется с учетом результатов предшествующих шагов, что помогает постепенно решить все выделяемые задачи. В этой связи указанные методы представляют интерес для систем с большой начальной неопределенностью. Начиная с 80-х гг. XX в. данные методы использовались в эко номико-математическом анализе как модели процессов планиро вания и функционирования в экономических системах. В частно сти, блочное программирование с успехом применяется в отраслевых задачах оптимизации, где естественна декомпозиция общей модели отрасли на блоки - модели предприятий либо на блоки, соответствующие последовательным стадиям переработки сырья. Для решения задач с блочной структурой могут быть исполь зованы: 1) методразлоэ1сен11я Даицыга-Вулфа (для задач линейного про граммирования); 1) метод планирования на двух уровнях Корнаи-Липтака. Оба метода представляют собой последовательные (итераци онные) пересчеты, увязывающие решение главной и локальных задач. Различие между ними состоит в том, что в первом итераци онный процесс основан на корректировке двойственных оценок ресурсов и продукции (такая корректировка делает для предприя тия выгодными планы, все более приближающиеся к оптимально му плану отрасли), а во втором - на корректировке лимитов обще отраслевых ресурсов, выделяемых предприятиям. При этом задача сводится к игре между центром, варьирующим допустимые рас пределения ресурсов, и предприятиями, варьирующими допусти мые двойственные оценки ресурсов. Ценой игры является сумма целевых функций предприятий. В обоих методах важную роль играют двойственные оценки, причем их оптимальный уровень определяется вместе с оптимальным распределением ресурсов. Так, метод Данцига-Вулфа как бы моделирует «распродажу» гло бальных ресурсов с учетом эффективности р^ использования /-го ресурса. Однако в конечном итоге планы локальных объектов ус танавливаются с учетом решения задачи центра. 79 Методы блочного программирования активно применялись в исследованиях декомпозиционного централизованного плани рования. При этом они, во-первых, предполагают распределение вычислительных функций между элементами системы и не тре буют концентрации информации и, во-вторых, могут включать моделирование элементов децентрализованного управления. Централизм методов блочного программирования находит вы ражение в том, что критерий оптимальности и правые части ог раничений локальных задач определяются алгоритмом решения исходной задачи. Они «предписываются» локальному объекту, представляя собой редукцию на локальный объект глобального критерия (как в методе Данцига-Вулфа) или глобальных ограни чений (как в методе Корнаи-Липтака), а не выявляются при его анализе как самоорганизующейся системы.
Ви переглядаєте статтю (реферат): «БЛОЧНОЕ ПРОГРАММИРОВАНИЕ» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
