Лекция: Блочное программирование

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

Рис. 3.6

Такой задаче специальной блочной структуры соответствует особая структура исходных данных (табл. 4.3).

Таблица 3.10

Применительно к матрице блочной структуры математическую постановку задачи можно переписать иначе, вводя двухиндексное обозначение переменной xpj, указывающей на принадлежность переменной xj к p-му локальному блоку:

где P – общее число локальных блоков; np – число переменных, входящих в p-й локальный блок; mp – число ограничений в p-м локальном блоке.

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

Особенность таких задач – большая размерность, затрудняющая формирование и отладку постановки и исходных данных.

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