Файл: Алексеев, А. М. Сетевые модели в перспективном планировании развития производства.pdf

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

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

Значения неизвестных и двойственные оценки за исключением последней компоненты у обеих задач совпадают, тогда, одно из

(у* — двойственная переменная к ограничению Z= 1). Предположим, что по каждому £_задано выпуклое множество

ctg возможных вариантов развития (а£, ^g), соответственно век­ тор р — один из эквивалентных вариантов спроса pGSS, тогда усло­ вия (1—6) оптимальности решения X, Y должны выполняться для всех (щ, Тб) ecxg и рбЗЗ.

шах (Yocg — уЕ) < 0 , I = 1, 2,

В противном случае план может быть улучшен введением векторснособа р°, для которого

решение может быть улучшено4.

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

Вернемся к исходной отраслевой задаче. Вектор-столбцы (ctg, v*-)T представляют собой технологические способы функционирова­

ния предприятий, вектор [3 — спрос в определенной номенклатуре

на продукцию отрасли, Y — объективно обусловленные оценки продукции и ресурсов. В этом случае, возможность улучшения по­ лученного плана развития (условия (I—8), (I—9)) может быть истолкована следующим образом.

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

Сетевые графики впервые начали применяться в практике управления. В 1956 г. при разработке космической. программы «Поларис» была использована система PERT. Эффективность отыскания «узких мест» и сосредоточенного контроля за крити­ ческими участками производства вызвали широкий интерес и спо­ собствовали быстрому распространению этой системы.

чительно расширилась (Обзор исследований..., 1968)- Сейчас се­ тевые методы широко используются в строительстве, планирова­ нии производства и сбыта продукции, проектировании и разработ­ ке годовых народнохозяйственных планов республики. Универ­ сальность системы PERT вызвана простотой отображения процес­ са производства отдельными этапами с установленной очередно:- стью и временной оценкой выполнения каждой работы.

Небольшое количество параметров сети (работа, событие, вре­ мя выполнения) и простота расчетов резервов времени работ обес­ печивают оперативный анализ и эффективность руководства при выполнении сложных производственных заданий. Однако непо­

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

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

Оптимизация на сети предполагает выбор наилучшего сочета­ ния вариантов выполнения оаботКритериями оптимизации могут быть простота технологии производства, эффективность капитало­ вложений, затраты ресурсов, стоимость. Последний критерий на­ иболее универсален: при сравнении вариантов в стоимостной фор­ ме могут быть отражены сложность выполнения работ, продук­ тивность, дефицитность используемых ресурсов. Например, ис­ пользование дефицитных трудовых ресурсов можно связать с ка­ питаловложениями в жилищное строительство или затратами на привлечение и обустройство рабочих. Подходя с этой точки зрения к вопросу оптимизации5, необходимо затронуть вопрос о предпо­ чтении вариантов на основе стоимости.

В терминах сетевых моделей каждой работе (г, /) сети должно соответствовать несколько вариантов выполнения. Естественно, что технологическими условиями может быть определено раз­ личное число вариантов (в том числе и единственный). Вариан­ ты задаются двумя параметрами: продолжительностью, выполне­ ния (ту) и стоимостью S{i(rii). Полагая, что все прочие факторы находят отражение в стоимости, из двух вариантов с одинаковой продолжительностью выполнения всегда будет предпочтителен бо­ лее дешевый. Если же варианты имеют одинаковые параметры, то, считая их идентичными, можно брать любой из них, а остав­ шиеся отбрасывать. Таким образом, теперь для любой пары ва­

зависимости ^ (т).

Одна из первых оптимизационных задач на сети в случае ли­

5 В специальной литературе модели оптимизации на сети по критери стоимости именуют PERT — cost. (Кофман, 1968).

20

нейной зависимости 8ц(т) решена Келли (Kelley, 1961). При за­ данном характере зависимости стоимости работ от их продолжи­ тельности из установленных сроков выполнения проекта необхо­ димо выбрать тот, при котором стоимость проекта (сумма стоимо­ стей всех работ).минимальна. Математически эта задача записыва­ ется следующим образом.

Пусть задан сетевой график Г с событиями i = 0, 1, .. .., п и ра­ ботами (г, /) е б . Продолжительность каждой работы ту по усло­ виям технологии имеет верхний и нижний предел:

Для времени наступления событий U должно выполняться усло­ вие

сти работы от ее продолжительности, то целью задачи является отыскание такого расписания работ {£,} , при котором достигается минимум суммарных расходов на выполнение всего проекта:

Алгоритм заключается в последовательном решении задачи параметрического программирования при значениях параметра Т от Ттах до Tmin. При Т — Ттах оптимальное расписание находится тривиально:

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

Рассматриваемый алгоритм приведен к форме, допускающей реализацию на ЭВМ. В блок-схеме алгоритма (см. схему 1) ис­ пользованы следующие обозначения:

лее сокращаться не может); /а — поток через дугу (г, j);

: — — знак присвоения кода; S г — г'-е событие графика;

г* или Sj — закодированное событие; i~ или 5 — — незакодированное событие.

21