7. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ. Методом сетевого моделирования решается следующая задача оптимизации

7. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Шаг 3 (распределение средств в третьем и четвертом кварталах)

Пусть в конце второго квартала между предприятиями распределяется сумма в размере S2. Пусть предприятию П1 выделяется сумма в размереU3, а предприятию П2 –S2–U3.Тогда выручка предприятий к концу третьего кварта-

ла составит 1,5 U3+1,8(S2–U3).Из этой суммы 20% будет выплачено акционерам, а 80% - распределено между предприятиями. Выплаты акционерам затретий и четвертый кварталы определяются следующим образом:

E3=Z3+E4*=0,2 (1,5U3+1,8(S2–U3))+E4*.

Выразим величину E3 черезU3 иS2. Как показано выше,E4*=0,34S3, где

S3 – сумма средств, распределяемых между предприятиями в начале четвертого квартала. Эта сумма составляет 80% от выручки предприятий в третьем кварта-

ле: S3=0,8 (1,5U3+1,8(S2–U3)).Таким образом,E4*=0,34 0,8 (1,5U3+1,8 (S2–

-U3))= 0,49S2–0,08U3.

Подставляя эту величину в уравнение для E3, получим:

E3= 0,2 (1,5U3+1,8(S2–U3))+ 0,49S2–0,08U3 = 0,85S2–0,14U3.

Видно, что максимальные выплаты акционерам обеспечиваются при ми-

нимальном значенииU3 (так как коэффициент приU3 отрицательный). Таким образом, условно оптимальное решение для третьего квартала состоит в том,

чтобы не выделять средства предприятию П1: U 3*=0. ПодставляяU3=0, получим выражение для условно оптимального значения критерия эффективности на третьем и четвертом шагах:E3*= 0,85S2.

Шаг 2 (распределение средств во втором - четвертом кварталах)

Пусть в конце первого квартала между предприятиями распределяется сумма в размере S1. Пусть предприятию П1 выделяется сумма в размереU2, а предприятию П2 – сумма в размереS1–U2.Тогда выручка предприятий к концу

второго квартала составит 1,5 U2+2,2(S1–U2).Из этой суммы 20% будет выплачено акционерам, а 80% - распределено между предприятиями. Выплаты акционерам за второй - четвертый кварталы определяются следующим образом:

E2=Z2+E3*=0,2 (1,5U2+2,2(S1–U2))+E3*.

Выполнив расчеты, аналогичные приведенным на шаге 3, выразим величину E2 черезU2 иS1:

E2 = 0,2 (1,5U2+2,2(S1–U2))+E3* = 0,2 (1,5U2+2,2(S1–U2))+ 0,85S2 =

=0,2 (1,5 U2+2,2(S1–U2))+ 0,85 0,8 (1,5U2+2,2(S1–U2))=

=1,94 S1 – 0,62U2.

studfiles.net

4.7. Сетевые модели в оптимизации управленческих решений

4.7.1. Задача поиска кратчайшего пути

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

В общем виде задача формулируется следующим образом. Имеется некоторое количество пунктов, соединенных определенным образом одно- или двунаправленными связями. Каждая связь имеет определенный вес – длину. Требуется найти кратчайший путь из пункта i в пункт j.

При составлении математической модели задачи необходимо учитывать, что маршрут должен быть непрерывным, а каждый промежуточный пункт на пути следования может быть посещен только один раз. Транспортная система в задаче является ориентированным графом – двухполюсной сетью, где N1 – вход, Nn – выход, весовые коэффициенты cij ребер δij являются длинами пути между пунктами i и j, требуется определить кратчайший путь из N1 в Nn. Сопоставим каждому ребру графа булеву переменную, т.е. . Если ребро входит в маршрут, то, иначе. Тогда целевая функция, которая минимизируется при поиске кратчайшего пути, имеет вид:

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

для перечисления всех k, входящих в i-ый пункт маршрута ребер :

, ;

для перечисления всех j, исходящих из i-го пункта ребер:

, .

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

В начальном пункте – , в конечном –

для всехi и j. От переменных δij достаточно потребовать только неотрицательности. Из-за указанных выше ограничений в решении могут быть получены только значения нуля либо единицы. Таким образом, получили обычную задачу линейного программирования, которую можно решить без наложения требований целочисленности.

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

Пусть требуется найти кратчайший маршрут из пункта А в пункт B, если схема движения и расстояния между объектами заданы рис. 4.32 [24].

4.7.2. Задача о распределении потоков в сетях

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

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

Пусть xij – поток в ребре графа, тогда для промежуточной вершины сети

, (4.6)

где k – перечисление всех входящих, j – всех исходящих ребер для вершины i.

Для потока в любом ребре требуется, чтобы

Для начальной и конечной вершины, очевидно, необходимо выполнение условия

ис. 4.32. Решение задачи на поиск кратчайшего маршрута

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

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

Возможны различные постановки задачи оптимизации – минимизации стоимости транспортировки и максимизации потока. Получаем соответственно две формулировки математической модели задачи.

Минимизация стоимости:

- минимизируемая целевая функция – общая стоимость транспортировки. Ограничения:

- поток не может накапливаться в промежуточных вершинах, т.е.

- по пропускной способности;

- сохранение непрерывности потока.

Максимизация потока:

- максимизируемая целевая функция – суммарный поток, входящий в конечный узел.

- суммарные затраты не должны превысить величины имеющихся средств Сs.

Ограничения:

- поток не может накапливаться в промежуточных вершинах, т.е.

- по пропускной способности;

- сохранение непрерывности потока.

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

Заданный граф частично ориентирован. Для того чтобы прийти к математической модели, необходимо преобразовать граф в ориентированную сеть. Это можно сделать, заменив каждое неориентированное ребро – дорогу с двусторонним движением двумя ориентированными – односторонними полосами движения, каждая с исходной пропускной способностью. Дороги x4 и x5 стали односторонними, так как возможность противоположного направления движения в данной задаче для них несущественна.

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

Рис. 4.33. Решение задачи на поиск максимального потока для

системы автодорог

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

studfiles.net

Об использовании принципов системного подхода

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

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

Вопросы для самопроверки

Что такое сложные системы?
Системный анализ как наука.
Основные понятия системного анализа: элемент, связи, система, подсистема, декомпозиция.
Классификация систем.
Принципы системного подхода и их использование.

Тема 3 Математические методы

И основные классы задач оптимизации

Общая постановка математической модели задач

Оптимизации

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

Пусть f(x) – функция, определённая на множестве V, а Ω - некоторое подмножество множества V.

Оптимизационная задача задается тройкой (V, F, Ω). При этом функция f(x) называется целевой функцией, а Ω – допустимым множеством (множеством допустимых значений) оптимизационной задачи.

Оптимизационные задачи бывают двух типов: задачи минимизации и задачи максимизации. Задача минимизации (максимизации) (V, F, Ω) состоит в отыскивании наименьшего (наибольшего) значения целевой функции f(x) на допустимом множестве Ω.

Для того, чтобы решить задачу минимизации (максимизации) (V, F, Ω), достаточно найти её оптимальное решение, т.е. указать x0Ω такое, что f(x0)f(x1…,xn)=f(x) (или f(x0)f(x)) при любом xΩ.

Оптимизационная задача называется неразрешимой, если она не имеет оптимального решения. В частности, задача минимизации (максимизации) (V, F, Ω) будет неразрешимой, если целевая функция f(x) не ограничена снизу (сверху) на допустимом множестве Ω.

Решить оптимизационную задачу – значит либо найти её оптимальное решение, либо установить неразрешимость этой задачи.

Любая задача максимизации (V, F, Ω) сводится к задаче минимизации (V, -F, Ω): эти задачи либо обе неразрешимы, либо имеют одно и тоже оптимальное решение.

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

Методы решения оптимизационных задач, в которых целевая функция является функцией n переменных, часто называют методами математического программирования. Термин "программирование" в данном случае обусловлен тем, что в задачах имеется некоторая программа действий, это не программирование на ЭВМ. В зависимости от вида целевой функции, которая может быть линейной или нелинейной, в математическом программировании выделяют основные разделы: линейное программирование и нелинейное (выпуклое программирование).

В общем виде математическая постановка задачи оптимизации состоит в определении наибольшего или наименьшего значения целевой функции f(x1…,xn) при условиях gi (x1…,xn)≤ bi (i=1,…,m), где f и gi - заданные функции, а bi - некоторые действительные числа. Если все f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования.

Пусть z=f(x1,x2,…,xn). Тогда мы можем записать:

zmax (min)

gi (x1…,xn) bi ,i=1,…,m.

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

z - оптимизационная цель экономической системы;

f(x1,…,xn) - соответствующая ей целевая функция;

x1,x2,…,xn - показатели степени использования средств достижения цели, могут характеризовать выпуск продукции разных видов, загрузку оборудования, использование ресурсов и т.п.

gi(x1…,xn)функция совокупных затрат средств i-й группы, используемых для достижения целей;

bi - лимиты, предельные границы совокупных затрат средств i-й группы, фиксируются ограничением на gi(x) сверху.

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

Среди этих предпосылок основными являются следующие:

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

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

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

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

Концепция ограниченности средств достижения целей в экономике обычно сводится к признанию ограниченности ("дефицитности") ресурсов в производственной и непроизводственной сфере.

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

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

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

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

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

Применительно к общей модели математического программирования функция gi(x) должна быть известна, то есть зависимость расхода или выпуска ресурса i-го вида от переменных должна быть известна. Величина bi есть наличие или возможность получения ресурса i-го вида и должна быть задана. В каждом из ограничений вида gi(x)bi может иметь место в принципе любой из знаков  Ограничение вида gi(x)bi может быть приведено к каноническому (классическому) виду следующим образом: -gi(x)-bi. Различные ограничения могут иметь различные знаки. Соотношение между числом неизвестных n и числом ограничений m может быть любым: m n; m  n; m n. Когда m 0, то ищется максимум или минимум целевой функции без ограничений, т. е. решается задача на нахождение безусловного экстремума.

На переменные могут дополнительно накладываться следующие ограничения:

а) некоторые или все переменные должны быть неотрицательными, то есть xj0 (j 1,2, …, n1), где n1n;

б) некоторые или все переменные могут принимать лишь дискретные (например, целочисленные) значения.

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

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

Ранее мы уже привели классификацию этих задач на линейные и нелинейные задачи.

Если принять, что

f(x1,x2,…,xn) (3.1)

gi (x1,x2,…,xn){  }bi , i=1,…,m. (3.2)

xj (i=1,2,…,n), (3.3)

где аij и cj – заданные величины, то получим общую задачу линейного программирования, которая формулируется следующим образом.

Необходимо найти n неотрицательных переменных xj, максимизирующих (или минимизирующих) линейную целевую функцию (3.1) и удовлетворяющих ограничениям (3.2), (3.3).

Для этих задач разработан целый ряд эффективных методов, алгоритмов и программ, основным из которых является симплекс-метод.

Все другие задачи, имеющие целевую функцию и ограничения, отличающиеся от (3.1), (3.2) и (3.3), кроме задач, в которых предполагается целочисленность переменных, принято считать нелинейными.

Вычислительные методы разработаны лишь для немногих типов задач нелинейного программирования, а именно для задач так называемого выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции с1x1 с2x2 …  сnxn +d11x12… d12x1x2… d1nx1xn… dnnxn2 при условии, что её переменные удовлетворяют либо некоторой системе линейных неравенств или линейных уравнений, либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения.

Отдельными классами задач математического программирования являются задачи целочисленного, параметрического и дробно-линейного программирования.

В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения.

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

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

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

Вопросы для самопроверки

Вид оптимизационной задачи.
Математическая постановка задач оптимизации и ее интерпретация к проблемам выбора наилучших вариантов экономического поведения.
Условия сведения экономической задачи к задаче оптимизации.
Классы задач математического программирования.

studfiles.net

2.4.3. Методы оптимизации сетевого графика

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

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

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

Критерии эффективности могут быть различны, подробно об этом моменте планирования (выборе и обосновании критерия) см. в [1]. Выделяются два основных подхода:

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

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

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

Приведение сетевого графика к заданному сроку.

Процедура приведения сетевого графика к заданному сроку не относится к классу оптимизационных задач. На основе анализа сетевого графика нам необходимо принять некоторое целенаправленное решение, а именно, обеспечить окончание комплекса работ к заданному (директивному) сроку. Обозначим его Тдир. Речь не идет о поиске наилучшего (по какому-нибудь критерию) решения, а лишь о целенаправленном решении.

Мы рассмотрим процедуру приведения сетевого графика к заданному сроку, которая осуществляется, как правило, при использовании метода РЕRТ или СРМ. Эта процедура не формализована, т.е. не является строгим алгоритмом, как, например, при расчете параметров сетевого графика. Приведение сетевого графика к заданному сроку осуществляется при творческом анализе информации, которую дает сетевой график, и конкретных производственных условий, не отраженных в сетевой модели, так называемых внемодельных факторов.

Вначале сравниваем критическое время комплекса работ (Тn0) с директивным. Если Тn0  Тдир, то сокращать ничего не нужно.

Если Тn0  Тдир, то критическое время необходимо сократить на величину = Тn0 – Тдир, причем прежде всего сокращению подлежат работы критического пути. Кроме того, необходимо проанализировать пути, содержащие работы, у которых Rпij  . Если эти пути содержат работы критического пути, уже сокращенные на общее количество дней, меньшее , или не содержат таких работ вообще, то и некоторые работы подобных (так называемых, подкритических) путей также необходимо сократить. В противном случае, после сокращения работ критического пути подкритический путь становится новым критическим путем.

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

Рассмотрим опять наш пример (рис 2.4.5).

Пусть Тдир =18, тогда  = 22 – 18 = 4. Значит, необходимо на 4 дня сократить длину критического пути. Также следует рассмотреть путь, содержащий работы (2,5) и (5,7), так как Rп25 = Rп57 =3  4. Этот путь имеет общие работы с критическим путем – (0,2) и (7,8). Если производственная ситуация позволяет сократить их продолжительность на 2 дня каждую, то критический путь и подкритический (0,2)-(2,5)-(5,7)-(7,8) сокращаются на 4 дня, что нам и требовалось.

studfiles.net

7.6. Решение сетевых задач методом линейного программирования

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

Модель сети связи, используемая для передачи информации, можно рассматривать как совокупность ветвей и узлов и представить в виде графа, вершины которого поставлены в соответствие узлам, а ребра – ветвям, как показано на рис.7.1 для примера с 5 пунктами передачи и ретрансляции.

Граф может быть неориентированным,

15(4) 15(3) если связь по всем ветвям двухсторонняя,

или ориентированным, если имеют место

односторонние (т.е. в одном направлении)

15(9) связи между отдельными узлами,

15(2) 10(6) 20(8) например 12 на рис.7.1.

В общем случае некоторые характе-

ристики ветвей могут не совпадать по раз-

10(8) 10(7) ным направлениям, например стоимость

передачи единицы информации в одном

Рис. 7.1направлении будет отличаться от стоимо-

сти в обратном направлении.

Каждая ветвь характеризуется двумя параметрами. Один параметр – это емкость или пропускная способность ij, которая ограничивает возможности передачи определенного объема информации между пунктамиiиj. На рис.7.1, например, пропускная способность односторонней ветви12= 15, а двухсторонних, совпадающая в обоих направлениях, -15=51= 15,34=43= 10,23=23= 20 и т.д.

Второй параметр каждой ветви зависит от выбранного критерия оптимизации. Это может быть и длина ветви lij, и стоимость передачи единицы информацииcijпо данной ветви, и другие параметры. Как отмечено выше, для двухсторонних ветвей эти параметры могут не совпадать, например на рис.7.1. Стоимость, указанная в скобках, для ветвис43 = 8, ас34= 7.

Для полной характеристики сети используются матрица пропускных способностей (емкостей) В и, например, матрица стоимостей С, соответствующие приведенной на рис.7.1 сети связи

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

ни один из узлов не встречается дважды. Так, если требования на потоки информации Ф задать в матричном виде

это будет означать, что требуется передать потоки с объемами информации 2-5= 16 и1-3= 15.

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

Рис.7.2

В качестве переменных хi целесообразно выбрать величины потоков информации, передаваемой поi-му пути. Число переменных будет определяться количеством путей входящих в построенные деревья путей.

Для составления математической модели задачи удобно использовать таблицу путей где каждому потоку Фсоответствует набор путей с количеством передаваемой информациихi.

Пути

Пропускные способности ветвей и стоимости

Стоимость пути

12

15=51

23=32

24=42

34

43

35=53

45=54

2-5

2-3-5

2-4-5

2-4-3-5

2-3-4-5

1-3

1-2-3

1-5-3

1-2-4-3

1-5-4-3

Стоимость пути складывается из стоимости передачи единицы информации по каждому из составляющих ветвей. Так стоимость первого пути с1=с23+ +с35 = 14.

Как видно, в таблице объединены двухсторонние ветви, имеющие в обоих направлениях одинаковые характеристики, и только выделены отдельно ветви 34и43, имеющие разную стоимость.

Математическая модель задачи имеет целевую функцию, соответствующую оптимизации-минимизации стоимости передачи информации:

(7.11)

В частности, из таблицы путей следует F= 14x1+ 8x2+ 23x3+ 14x4+ 8x5 + + 13x6+ 8x5+ 13x6 + 17x7+ 14x8min.

В качестве ограничений выступают следующие требования:

1.Суммарный поток информации между заданной парой узлов, представленный в виде суммы потоков по каждому из путей, должен быть равен требуемому потоку информации между этой парой узлов, т.е.

х1 + х2 + х3 + х4 = 25= 16,

х5 + х6 + х7 + х8 = 13= 15. (7.12)

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

х5 + х715,

х6 + х8 15,

х1 + х4 + х520,

х2 + х3 + х710,

х4 10, (7.13)

х3 + х7 + х810,

х1 + х3 + х615,

х2 + х4 + х815.

3.Потоки информации не могут принимать отрицательных значений, т.е.хi0.

Целевая функция (7.11 ) и система ограничений (7. 12) и (7.13 ) позволяют решать и исследовать задачу оптимизации сети связи методом линейного программирования.

studfiles.net

Экономико-математические модели и методы, используемые при решении комплекса задач сетевого планирования и управления

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

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

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

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

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

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

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

Методы СПУ позволяют формировать оптимальные по выбранным критериям планы и осуществлять оптимальное управление.

В данном учебнике углубляется теоретико-практический аспект применения аппарата экономико-математического моделирования на сетевых графах.

Данная глава содержит компактное изложение основных вопросов, относящихся к построению и анализу детерминированных сетевых моделей.

studfiles.net

4.7. Сетевые модели в оптимизации управленческих решений

4.7.1. Задача поиска кратчайшего пути

для перечисления всех k, входящих в i-ый пункт маршрута ребер :

, ;

для перечисления всех j, исходящих из i-го пункта ребер:

, .

В начальном пункте – , в конечном –идля всехi и j. От переменных δij достаточно потребовать только неотрицательности. Из-за указанных выше ограничений в решении могут быть получены только значения нуля либо единицы. Таким образом, получили обычную задачу линейного программирования, которую можно решить без наложения требований целочисленности.

4.7.2. Задача о распределении потоков в сетях

Пусть xij – поток в ребре графа, тогда для промежуточной вершины сети

, (4.6)

где k – перечисление всех входящих, j – всех исходящих ребер для вершины i.

Для потока в любом ребре требуется, чтобы

Для начальной и конечной вершины, очевидно, необходимо выполнение условия

Рис. 4.32. Решение задачи на поиск кратчайшего маршрута

Минимизация стоимости:

- минимизируемая целевая функция – общая стоимость транспортировки. Ограничения:

- поток не может накапливаться в промежуточных вершинах, т.е.

- по пропускной способности;

- сохранение непрерывности потока.

Максимизация потока:

- максимизируемая целевая функция – суммарный поток, входящий в конечный узел.

- суммарные затраты не должны превысить величины имеющихся средств Сs.

Ограничения:

- поток не может накапливаться в промежуточных вершинах, т.е.

- по пропускной способности;

- сохранение непрерывности потока.

Рис. 4.33. Решение задачи на поиск максимального потока для

системы автодорог

studfiles.net