Шпаргалка по "Экономике"

 

Рис. 16.2. Транспортная сеть рассматриваемого примера.

 

Решение. 

Задача  может быть сформулирована следующим образом:

Максимизировать при ограничениях:

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

27. Экономическое содержание и алгоритм решения задачи о потоке минимальной стоимости.

 

К задачам такого типа сводятся транспортная задача, задача о назначениях и ряд других задач.

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

Формулировка задачи:

                                                             

                        

              

                                                                 

 

Пример 2

Рассматривается сеть, представленная на Рис. 16.3.

 

Рис. 16.3. Транспортная сеть примера.

 

Цифры в скобках обозначают: в случае узла 1 (источника) – количество имеющегося продукта, в случае узлов 4 и 5 – их потребности в продукте. Первые числа у стрелок означают удельную стоимость транспортировки продукта ( ), а вторые – пропускную способность дуги (например, магистрали). Индекс * у дуг (2,3) и (4,5) означает, что их пропускные способности могут считаться неограниченными (например, они значительно превосходят имеющиеся в наличии запасы продукта).

Требуется определить распределение потоков, при котором суммарная стоимость  доставки минимальна, а потребности узлов 4 и 5 удовлетворяются.

 

Решение.

Задача  сводится к минимизации функции

при ограничениях

Решение задачи дает минимальное значение стоимости потока:

    

при следующих интенсивностях дуговых  потоков

 

(1,2)	12	(2,4)	4	(3,5)	1
(1,3)	8	(2,5)	0	(5,3)	0
(2,3)	8	(3,4)	15	(4,5)	14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

28. Задача о кратчайшем маршруте

 

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

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

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

при ограничениях:

где

 

Пример 3. Для транспортной системы, представленной на Рис. 12.5, определить кратчайший маршрут между узлами 1 и 7.

 

 

 

 

 

 

 

 

 

 

Рис. 12.5. Схема транспортной системы примера.

 

Очевидно, задача сводится к определению минимума функции

 

   

при ограничениях

.

 

Смысл ограничений:

необходимо, чтобы из узла 1 (источник) перевозимый  продукт был отправлен ( );

в узел 7 (сток или приемник) продукт был доставлен ( );

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

 

Ответ:

 

и  кратчайшему расстоянию между пунктами 1 и 7 соответствует маршрут

(1-3–4-7).

 

29. Понятие о методе PERT. Определение вероятностных характеристик сетевого графика в условиях неопределенности составляющих его работ.

 

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

При планировании проектов с учетом фактора неопределенности предполагается, что плотность распределения  продолжительности работ обладает следующими свойствами:

• непрерывностью;
• наличием единственного максимума у плотности распределения;
• двумя точками пересечения кривой распределения с осью Ox.

 

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

Плотность вероятности b - распределения имеет вид:

 

где p, q – некоторые параметры, A – константа, определяемая из условия нормировки (интеграл от должен быть равен единице). Плотность b - распределения для представлена ниже.

 

Рис. 17.1. Плотность бета-распределения

 

Для определения математического  ожидания и дисперсии этого распределения на основании опроса экспертов определяют три временные оценки для каждой работы :

• оптимистическую оценку  , т.е. продолжительность работы при самых благоприятных условиях;
• пессимистическую оценку продолжительности при самых неблагоприятных условиях ;
• наиболее вероятную оценку - продолжительность работы при нормальных условиях.

 

При b - распределении продолжительностей работ справедливы следующие оценки математического ожидания:

 

и дисперсии

 

 

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

           

 

Зная вероятностные характеристики продолжительностей работ, можно оценить  временные параметры проекта.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

30. Расчет вероятности выполнения проекта в директивный срок с помощью метода PERT. Понятие о стохастических сетях.

 

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

В соответствии с ЦПТ можно утверждать, что общая продолжительность  пути L имеет нормальный закон распределения со средним значением , равным сумме средних значений продолжительностей составляющих его работ и дисперсией , равной сумме соответствующих дисперсий :

 

          

          

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

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

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

Полагая случайной величиной, имеющей нормальный закон распределения, получим

 

где - функция Лапласа, ,   а - среднее квадратическое отклонение продолжительности критического пути.

Если рассчитанные по (6) значения вероятности  выполнения проекта в срок окажутся малыми (меньше 0,3-0,5), необходимо принятие дополнительных мер (перераспределение материально-технических ресурсов по сети, пересмотр состава работ и т.п.). При значениях вероятности 0,8 и выше можно с достаточно высокой надежностью прогнозировать выполнение проекта в директивный срок.

Рассмотрим  методику использования  метода PERT на конкретном примере.

 

Пример

 

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

 

Работа	Содержание  работы	Непосредственно предшествующие работы	Оптимистическое время выполнения работы	Наиболее вероятное время выполнения	Пессимистическое время  выпол-нения	Ожидаемое время выполнения	Дисперсия
A	Подготовка конструкторского проекта	-	4	5	12	6	1,78
B	Разработка плана маркетинговых исследований	-	1	1,5	5	2	0,44
C	Подготовка маршрутных карт	A	2	3	4	3	0,11
D	Создание опытного образца	A	3	4	11	5	1,78
E	Выпуск рекламных брошюр	A	2	3	4	3	0,11
F	Подготовка оценок затрат	C	1,5	2	2,5	2	0,03
G	Проведение предварительного тестирования	D	1,5	3	4,5	3	0,25
H	Исследование рынка	B, E	2,5	3,5	7,5	4	0,69
I	Подготовка доклада  о ценах	H	1,5	2	2,5	2	0,03
J	Подготовка заключительного  доклада	F,G,I	1	2	3	2	0,11