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

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

Рис. 2.2

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

Таблица 2.2

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

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

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

Особенность таких задач – большая размерность.

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

2.9 Теория графов

Наглядность геометрии широко используют при анализе больших технических и организационных систем.

Граф – универсальное средство наглядного представления достаточно разнообразных задач – совокупность вершин и ребер. Разнообразные сочетания различных ребер и вершин представляют многообразие возможных графов и их применения.

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

Каждую вершину сети нумеруют порядковым номером. Начальную вершину называют «источником», конечную - «стоком» в описании движения потоков.

Дугу сети обозначают двойной индексацией 1-2; 3-4 (рис. 8.8) и т. д. (по номерам вершин, на которые дуга опирается). В общем случае дугу обозначают«i-j», где i - номер вершины, из которой исходит дуга; j - номер вершины, в которую входит дуга. Каждая дуга имеет свои характеристики: t_ij - продолжительность движения по дуге i-j; с_ij - стоимость перемещения; d_ij – пропускная способность дуги и т. д. (рис. 8.9).

Рисунок 2.3

Зная топологию сети и ее параметры, можно решать разнообразные задачи оптимизации.

Сетевой график (сеть) состоит из дуг и узлов (обозначается стрелкой); вершине – событие, то есть состояние перед работой (обозначается кружком).

Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает последовательность работ и продолжительность выполнения каждой работы (табл. 2.3).

Табл.2.3

Работа	Содержание	Следует после работ	Продолжительность	Обозначение
	Закупка и доставка оборудования	-	1	1-2
	Разработка технологии	-	2	1-3
	Монтаж и наладка оборудования		3	2-3
	Обучение рабочих-операторов		4	2-4
	Пуск линии в эксплуатацию	,	5	3-4

Два события отметим особо: начальное – состояние, с которого начинается весь комплекс работ; конечное – состояние, которым завершается комплекс работ.

По исходным данным строится сетевой график (рис. 8.10).

Рисунок 2.4

Последовательность работ, в которой конец предыдущей работы совпадает по времени с началом последующей, называется путем. Путь, имеющий наибольшую продолжительность, называют критическим. Увеличение продолжительности работ критического пути приводит к более позднему наступлению конечного события. Работы, не лежащие на критическом пути, могут быть позже начаты или позже окончены, или иметь большую продолжительность без изменения срока окончания всех работ. Величину, на которую можно увеличить продолжительность выполнения такой работы без увеличения времени наступления конечного события, называют резервом.

Если руководитель следит за выполнением всех работ в срок, то он должен четко знать и особо контролировать работы критического пути.

Перейдем к формализации. В нашем примере время наступления каждого события может быть найдено по зависимостям

; .

Так как третье событие может наступить после выполнения работ 2-3 и 1-3, запишем:

, значит Т₃=5.

Аналогично найдем время наступления последнего события:

, значит Т₄=11.

Окончательно время наступления событий будет равно:

; ; ; .

Резерв работы 1-3, который будем обозначать =5-2=3. Значит, работа 1-3 может быть начата не в первый момент времени, а спустя 3 единицы времени, или продолжаться на 3 единицы больше, чем первоначально предполагалось, то есть может длиться 2+3=5 ед. без увеличения момента наступления конечного события «4» (рис. 8.11).

Рисунок 2.5

Аналогично = =11-(l+3)=7, то есть продолжительность работы 2-4 может быть увеличена на 7 единиц. Очевидно, что для работ критического пути резерв времени равен 0, т. е. .

Для третьего события можно записать .

Отсюда .

Выражение записано в скобках, чтобы было наглядно видно, что это интервал времени между двумя последовательными событиями. И этот интервал за вычетом резерва равен продолжительности работы 1-3. В этой зависимости нам задана продолжительность работы (правая часть уравнения), остальные величины – искомые переменные. Если их обозначить:

,

то можно записать: и получить линейное уравнение с тремя неизвестными.

Если записать аналогичные зависимости для всех событий и работ, входящих в нашу сеть, то получим систему:

Эта система описывает топологию (структуру) нашей сети.

Если вместо подставить их известные (заданные) значения получим:

Описание структуры сети содержит пять линейных уравнений с девятью неизвестными. Они имеют бесчисленное множество решений. Чтобы решить эту систему уравнений, надо добавить граничные условия и целевую функцию. При этом возможны две постановки задач оптимизации. Первая постановка: задаемся временем начала работ, то есть значением Т₁, например, Т₁=0, и стремимся закончить комплекс работ как можно раньше:

Вторая постановка: задан срок завершения всех работ, например, Т₄=15, и нас интересует как можно позже начать работы, но чтобы непременно уложиться в срок:

В общем виде топология сети запишется:

(*)

Если обозначить S – число событий; R – число работ, то как видно из (*), система, описывающая сеть, будет включать п переменных, где n=S+R, так как каждому i-му событию соответствует неизвестная T_i, а каждой i, j-й работе – неизвестная . А число ограничений m=R, то есть каждой работе соответствует ограничение.

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

Тогда общие постановки запишутся:

,

где , - заданные плановые сроки начала и окончания работ сети.

Например, для графика из 11 событий и 20 работ (рис.8.12.) первая постановка при Т₁=0 будет иметь вид:

Рисунок 2.6