книги / Типовые задачи оперативного управления непрерывным производством

календарного планирования; nkt+x — вектор двойственных

В задачу для Æ-го шага (6-16) — (6-17) входят значе­ ния pît и qjf для всех шагов от первого до (к—1)-го включительно, которые уже определены до начала рас­ четов /г-го шага. После перехода от одного шага к дру­ гому появляются новые рц и q-Y т. е. размерность ре­ шаемых задач возрастает.

Для задачи SPY необходимо знать вектор я \ +1. Ре­

шение задач SPhi, ..., SPhT на каждом к-ы шаге осуще­ ствляется от последнего 7’-го интервала к первому. В первой задаче SPkr член jtr+iBr отсутствует, в ре-

наибольшее число основных переменных на интервале, М — общее число переменных в задаче по всем интерва­ лам (включая дополнительные переменные), М — общее число строк в задаче, Я —процент ненулевого заполне­

в виде двух вариаций (метод 1 и метод 2), отличающих­

Данные таблицы показывают, что симплекс-метод требует больше оперативной памяти, чем предлагаемый метод, однако обладает большим быстродействием. Из таблицы также видно, что метод 2 расходует меньше оперативной памяти, чем метод 1, но ведет к увеличе­ нию времени счета.

Предполагается, что программа работает с внешним накопителем, причем в оперативной памяти в каждый текущий момент времени хранится лишь та часть про­ граммы и данных, которые находятся в работе. Объем этих рабочих данных в оперативной памяти ЭВМ и при­ веден в третьем столбце табл. 6-2.

6-3. Метод упрощенной декомпозиции детализированной задачи

Рассмотренные выше общие методы декомпозиции требуют создания довольно сложных и больших про­ грамм, рассчитанных на ЭВМ с высоким быстродейст­ вием и развитой памятью. При применении их в про­ мышленных условиях возникают существенные трудно­ сти, так как промышленные организации, решающие по­ добные задачи, обычно имеют вычислительные средства средней и малой мощности с небольшой библиотекой стандартных программ (обычно включающей лишь не­ которые стандартные процедуры симплекс-метода реше­ ния задачи линейного программирования). Поэтому актуальна задача разработки таких процедур решения, в которых использование существенных особенностей структуры представленных задач позволило бы умень­ шить размерность детализированной задачи и эффек­ тивно применять стандартные программы линейного программирования. Одна из таких процедур [99] и рас­ сматривается в настоящем параграфе.

Для упрощения изложения будем в дальнейшем счи­ тать, что вся готовая продукция сразу отгружается по­ требителям, и как в задаче (6-8), так и в задаче (6-15) можно не учитывать ограничений, связанных с наличием выходных емкостей. Описанная далее процедура может быть применена и для решения с учетом этих огра­

ничений.

Предварительно рассмотрим следующее свойство исходной (6-8) и детализированной (6-15) задач.

Предположим, что детализированная задача решена и получено значение целевой функции F*, затем решена соответствующая задача технико-экономического плани­ рования и получено значение F*a.

Можно показать, что

f. ë. оптимальное значение целевой функций задачи (6-8) является верхней оценкой значения целевой функ­ ции детализированной задачи.

Действительно, если в задаче технико-экономиче- ското планирования сделать подстановку

г

t= \

то эта задача превратится в детализированную задачу, в которой отсутствуют ограничения (6-13) и из всей си­ стемы ограничений (6-11) присутствуют только ограни­ чения, относящиеся к Г-му интервалу времени.

Таким образом, если детализированная задача имеет решение, то множество ее допустимых решений будет принадлежать множеству допустимых решений задачи технико-экономического планирования с указанной под­ становкой. В этом случае справедливо неравенство

(6-20).

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

исходных компонентов 4?fr’ J= l, .... л, которые могут

быть и нулевыми, и некоторые значения суммарного вы­ пуска готовой продукции УsTt s= l, ..., m. Согласно введенным выше ограничениям

2 y s t , ~ 5 = 1 ,...,/л. t=i

Будем называть их конечными условиями 7Vo времен­ ного интервала. Конечные условия для (Т — 1)-го интер­

Следует отметить, что существует, вообще говоря, бесчисленное множество конечных условий для (Т—1)- го интервала, из которых путем распределения потоков на Г-м интервале можно перейти в заданные конечные условия для Т-го интервала. Будем полагать, что это распределение потоков при заданных конечных условиях проводится оптимально, т. е. при максимизации крите­ рия (6-14). Аналогичным образом рассмотрим множест­

во конечных условий интервала (Т—2), из которых мо* жет быть достигнуто каждое из допустимых конечных условий (Т—1)-го интервала и т. д. Последовательно проводя подобные рассмотрения, можно, наконец, дой­ ти до начала первого временного интервала.

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

(2Т, У,)

Рис. 6-5. Дерево решений детализи­ рованной задачи.

мальное распределение потоков, соответствующее вы­ бранным конечным условиям, — прямоугольником, то задачу можно представить в виде дерева решений с бес­ конечным числом ветвей, часть которого изображена на рис. 6-5. Условия в начале первого интервала можно рассматривать как конечные условия специально введен­ ного нулевого интервала.

Цель процедуры получения оптимального детализи­ рованного плана состоит в нахождении таких ветвей этого дерева, которые ведут из заданных конечных усло­ вий нулевого интервала в заданные конечные условия Г-го интервала и при этом достигается максимум значе­ ния критерия (6-14).

Для нахождения такого оптимального решения мо­ жет быть использована процедура динамического про-