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

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

Рис. 3.6

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

Таблица 3.10

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

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

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

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

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