Блочное программирование

Блочное программирование [block programming] – метод решения сложных задач линейного программирования путем разложения модели на блоки. Крупноразмерная модель (включающая много показателей в исходной таблице) сводится к нескольким моделям меньшей размерности. Получившиеся задачи ре­шаются вместе по специальным правилам согласования.

Необходимость такого под­хода обосновывается тем, что с ростом размерности трудоемкость, да и просто сложность решения задач растет невероятно быстро. «Прокля­тие размерности», по меткому выражению американского ма­тематика Р.Беллмана, характерно для большинства реальных задач математического программирования.

Широко применяется Б.п. в отраслевых задачах оптимизации, где естественно разложение, «декомпозиция» общей модели отрасли либо на блоки – модели предприятий, либо на блоки, соответствующие последовательным стадиям пе­реработки сырья (производст­венным переделам).

Среди теоретических схем Б.п. наиболее известны две: метод декомпозиции Данцига-Вульфа и метод планирования на двух уровнях Корнаи-Липтака (Дж. Данциг и П.Вульф – американские, Я.Корнаи и Т.Липтак – венгерские ученые). Обе они представляют собой последовательные (итеративные) пересчеты, взаимно увязывающие решения главной «отрас­левой» задачи и локальных задач предприятий. Различие же между ними состоит в том, что в первом случае итеративный процесс основан на корректировке двойственных оценок ресурсов и продукции (та­кая корректировка делает для «предприятия» выгодными пла­ны, все более приближающиеся к оптимальному плану отрасли), а во втором случае – на корректировке лимитов общеотраслевых ресурсов, выделяемых предприятиям. При этом задача сводится к игре между центром, варьирующим допустимые распределения ресурсов, и предприятиями (варьи­рующими допусти­мые двойственные оценки ресурсов); ценой игры является сумма целевых функций предприятий.

Иначе говоря, схема Данцига-Вульфа построена по принципу «централизованное определение цен – децентрализованное определение наилучших возможностей», а схема Корнаи-Липтака – по принципу «централизованное лимитирование возможностей – децентрализованное выявление эффекта от их использования»[1]. В обоих случаях важную роль играют двойственные оценки, причем их оптимальный уровень выявляется вместе с оптимальным распределением ресурсов, т.е. собственно планом (именно в этом состоит принцип оптимального планирования).