Теория вероятностей

Размещено на http://www.allbest.ru

1. Сведения из теории вероятностей:

1) три типа событий,

2) комбинации событий,

3) классическая вероятностная модель,

4) статистический подход к оценке вероятности,

5) закон распределения дискретной случайной величины,

6) математическое ожидание случайной величины.

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

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

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

Произведением двух событий А и В называется событие, обозначаемое символом АВ_, заключающееся в одновременном появлении и события А, и события В.

Действия над событиями иллюстрируют рис. 9.2, 9.3, которые можно интерпретировать следующим образом. Если события А и В -- попадание в соответствующие мишени А и В, то события А+В (рис. 9.2, 9.4) и АВ (рис. 9.3) -- попадания в заштрихованные области.

События А и В могут быть совместными, если они могут происходить одновременно (рис. 9.2, 9.3) или несовместными (непересекающимися) (рис. 9.4), если они не могут произойти одновременно. Для несовместных событий А В --Ш.

3. Рассмотрим так называемую классическую вероятностную модель. Пусть проведен эксперимент, все исходы которого можно перечислить, и, кроме того, все исходы:

· равновозможны;

· попарно несовместны (в результате однократного проведения эксперимента может произойти только один из исходов);

· образуют полную группу событий (никакие другие исходы, кроме перечисленных, не могут произойти).

Примером подобного эксперимента может служить бросание игральной кости. Все возможные исходы такого эксперимента -- так называемое пространство элементарных событий -- {1, 2, 3, 4, 5, 6}. Случайным событием будет любое подмножество, состоящее из элементарных исходов данного пространства элементарных событий. Например, случайное событие А -- выпадение четной цифры: А = {2,4,6}; случайное событие В -- выпадение цифры, меньшей трех: В= {1,2}

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

Р(А) = (9.1)

где Р(А) -- вероятность события А; т_A -- число элементарных исходов, благоприятствующих событию А; n -- общее число элементарных исходов.

Для рассмотренного выше примера с игральной костью на основе (9.1) легко подсчитать:

• вероятность выпадения четной цифры Р(А)= =0,5;

• вероятность выпадения цифры, меньшей трех, Р(В)=

Из (9.1) следует, что вероятность любого события А заключена в диапазоне от нуля до единицы:

0?Р(А)?1. (9.2)

Причем, если Р(А)= 1, то А -- достоверное событие, если Р(А) = О, то А -- невозможное событие.

4. Для оценки вероятности событий существует и другой, так называемый статистический подход. Он основан на определении относительной частоты появления события А в п экспериментах, которые могут быть воспроизведены неограниченное число раз при одном и том же комплексе условий. Если в этих условиях событие А появилось т_А раз, то

Р(А)= (9.3)

Формула означает, что если эксперимент повторяется бесконечно много раз (п->?), то вероятностью события А будет предельное значение дроби .

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

• Например, если из тысячи проданных холодильников 20 оказались неисправными, то вероятность брака при покупке холодильника можно оценить как P_брака? 0,02.

• Если на основании статистики последнего месяца из 500 человек, ежедневно посещающих магазин, в среднем 450 совершают покупки, то вероятность того, что посетитель уйдет из магазина с покупкой можно оценить как Р ? =0,9.

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

5. Описание случайной величины, связывающее все ее возможные значения с вероятностями этих значений, называют законом (рядом) распределения дискретной, случайной величины. Как правило, ряд распределения задают таблицей, в которой в первой строке перечисляют все возможные значения х₁, х₂, х₃...x_n случайной величины, а во второй -- соответствующие им вероятности p_i = Р(Х = x_i) (табл. 9.2).

Таблица 9.2

X	x1	x2	...	xn
Р	Р1	Р2	...	Рn

Для любого ряда распределения должно выполняться условие

,

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

6. Закон распределения случайной величины дает исчерпывающую информацию о случайной величине, позволяя, в частности, вычислять вероятности любых событий, связанных со случайной величиной. Однако законы распределения не всегда удобны для анализа, особенно при сравнении нескольких случайных величин между собой. Кроме того, в различных бизнес-приложениях часто возникает необходимость в оценке типового, ожидаемого, среднего значения случайной величины. Бизнес постоянно оперирует такими понятиями, как средняя выручка, средняя ставка арендной платы, средняя зарплата, средний объем продаж и т.д. Для случайной величины таким средним является величина, называемая математическим ожиданием:

М(Х) =Е(Х) = х₁р₁ +х₂р₂ +...+ х_п р_n = р,. (9.9)

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

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



2. Критерии для принятия решений в условиях неопределенности

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

Тогда для рассматриваемого примера вероятность каждого из состояний внешней среды будет равна Р = 0,5. Рассчитаем и поместим в табл. 9.5 ожидаемые доходы для каждого решения, вычисляя их как математические ожидания случайной величины (платежа):

Е_l = 200 *0_,5+(-180)*0,5 = 10,

Е₂ = 100*0,5+(-20) *0,5 = 40,

Е₃ = 0*0,5+0*0,5 = 0.

Как видно (табл. 9.5), максимальный ожидаемый доход (платеж) по критерию Лапласа обеспечивает решение 2 -- «закупить малую партию товара».

Таблица 9.5

Платежная матрица
	Состояние природы
Решение	Благоприятный рынок	Неблагоприятный рынок	Критерий безразличия Лапласа
	Р = 0,5	Р = 0,5
1. Закупить большую партию товара	200	-180	10
2. Закупить малую партию	100	-20	40
3. Ничего не закупать	0	0	0



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

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

Платежная матрица
	Состояние природы	Критерий Max (max)
Решение	Благоприятный рынок	Неблагоприятный рынок
1, Закупить большую партию товара	200	-180	200
2. Закупить малую партию	100	-20	100
3. Ничего не закупать	0	0	0

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

По максимаксному критерию оптимальным для рассматриваемого примера будет решение 1 -- «закупить большую партию товара».



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

Таблица 9.7

Платежная матрица
	Состояние природы	Критерий
Решение	Благоприятный рынок	Неблагоприятный рынок	Max (min)
1. Закупить большую партию товара	200	-180	-180
2. Закупить малую партию	100	-20	-20
3. Ничего не закупать	0	0	0

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

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

Для ситуации «Благоприятный рынок», как следует из таблицы платежей, самым выгодным будет решение 1 -- «Закупить большую партию товара». В этом случае выигрыш составит 200 тыс. у .д.е. Тогда принятие этого решения не принесет потерь:

Потери = 200 - 200 = 0.

Если же для этого состояния внешней среды будет принято решение 2 -- «Закупить малую партию» с доходом 100 тыс. у.д.е„ то потери от принятия не наилучшего решения (решения 1), обеспечивавшего доход, равный 200 тыс. ул.е., составят:

Потери = 200 - 100= 100.

Аналогично, для решения 3 потери по сравнению с наилучшим решением составят:

Потери = 200 - 0 = 200.

Результаты и алгоритм пересчета платежей в потери для состояния внешней среды «Благоприятный рынок» показаны в табл. 9.8.

Таблица 9.8

Решение	Благоприятный рынок
	Исходная таблица	->	Новая таблица
	Платежи	Вычисление потерь	Потери
1. Закупить большую партию	200	200 - 200 = 0	0
товара
2. Закупить малую партию	100	200- 100 = 100	100
3. Ничего не закупать	0	200 - 0 = 200	200

Для состояния внешней среды «Неблагоприятный рынок» наилучшим» с точки зрения дохода (минимального убытка), является решение «Ничего не закупать». Алгоритм пересчета исходной матрицы платежей в новую матрицу (таблицу) потерь, показан в табл. 9.9. Объединяя полученные результаты, получаем новую табл. 9.10 -- матрицу потерь. Для каждого решения выбираем максимальное значение потерь и записываем его в правом столбце. В качестве оптимального решения выбирается решение, обеспечивающее минимальное значение максимально возможных потерь. Для рассматриваемого примера таким решением будет решение 2 -- «Закупить малую партию».

Таблица 9.9

Решение	Неблагоприятный рынок
	Исходная таблица	=>	Новая таблица
	Платежи	Вычисление потерь	Потери
1. Закупить большую	-180		0 - (-180) = 180	180
партию товара
2. Закупить малую	-20		0 - (-20) = 20	20
партию
3. Ничего не закупать	0		0-0 = 0	0

Таблица 9.10

Матрица потерь
	Состояние природы	Критерий Min (max)
Решение	Благоприятный рынок	Неблагоприятный рынок
1. Закупить большую партию товара	0	180	180
2. Закупить малую партию	100	20	100
3. Ничего не закупать	200	0	200

Таким образом, применение различных критериев в одной и той же ситуации принятия решения в условиях неопределенности дает различные «оптимальные» решения (табл. 9,11). Это связано с тем, что, во-первых, перечисленные критерии зависят от предпочтений лица, принимающего решения, и его взгляда на ситуацию -- оптимистического, пессимистического, безразличного, взвешенного.

Таблица 9.11

Решение	Состояние природы	Критерии для принятия решения
	Благоприятный рынок	Неблагоприятный рынок	Критерий безразличия	Критерий Мах (max)	Критерий Мах (min)	Критерий Min (max)
1.Закупить большую партию товара	200	-180	10	200	-180	180
2. Закупить малую партию	100	-20	40	100	-20	100
3, Ничего не закупать	0	0	0	0	0	200

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

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



3. Решение задач линейного программирования графоаналитическим методом

В линейном программировании существует 2 метода:

· графоаналитический;

· симплекс-метод

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

Пусть задана система ограничений:

5x1+9x2<=45

3x1+3x2<=19

2x1+x2<=10

f(x1,x2)=2x1+x2=max

Переход к каноническому виду означает переход от системы неравенств к системе равенств. При этом строку с равенством не меняем. Знак <= заменяем добавлением к выражению нек. слагаемого, а >= - вычитанием. Поскольку придется менять все неравенства, то возникнет три новых переменных: x3,x4,x5. Но они будут носить чисто формальный характер!! ! и фактически будут нулями. Получим

5x1+9x2+x3=45

3x1+3x2+x4=19

2x1+x2+x5=10

Это есть канонический вид. Стоит также иметь в виду, что все переменные >=0!

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

Благо в нашем случае этого делать не надо: в матрице сразу видна единичная.

Справедливо, очевидно:

x3=45-5x1-9x2

x4=19-3x1-3x2 (**)

x5=10-2x1-x2

Вспоминая, что x3,x4,x5 - фактически нули, то получаем уравнения прямых на плоскости Ox1x2 (либо x2 выражаем через x1, либо наоборот) . Проводим все эти три прямые. Теперь ищем общую область. Для этого проверим для каждой прямой, какую область та ограничивает (сверху или снизу) . Для этого выберем точку (x1,x2)=(0,0) и подставим в (**). Если x3 (аналогично с x4, x5) положительно, то область лежит ниже прямой, отрицательна - выше.

Находите общую область пересечения (опять же учитываем, что x1,x2>=0!).

Осталось рассмотреть целевую функцию/ Допускают f(x1,x2)=0, т. е x2=-2x1.

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

Осталось только найти координату этой точки и подставить полученные x1,x2 в исходную целевую функцию.

4. Теория графов и оптимизация

Теория графов и оптимизация

Один из разделов дискретной математики, часто используемый при принятии решений - теория графов (см., например, учебное пособие [8]). Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами. Примеры графов приведены на рис.5.

Рис.5. Примеры графов.

На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.6.

Рис.6. Примеры ориентированных графов.



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

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

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

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

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

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

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

Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

Рис.7. Исходные данные к задаче о кратчайшем пути.

Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.8).

Табл.8. Исходные данные к задаче о кратчайшем пути.

Начало дуги	Конец дуги	Время в пути
1	2	7
1	3	1
2	4	4
2	6	1
3	2	5
3	5	2
3	6	3
5	2	2
5	4	5
6	5	3

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

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

Для исходных данных, представленных на рис.7 и в табл.6, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1. Кроме того, очевидно, что С(1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С(4) = min {С(2) + 4 ; С(5) + 5}.

Таким образом, проведена реструктуризация задачи - нахождение С(4) сведено к нахождению С(2) и С(5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С(5) = min {С(3) + 2 ; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому

С(5) = min {3 ; С(6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С(2) = min {С(1) + 7 ; С(3) + 5 ; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому

С(2) = min {0 + 7 ; 1 + 5 ; 3 + 2} = 5.

Теперь мы можем найти С(4):

С(4) = min {С(2) + 4 ; С(5) + 5} = min {5 + 4 ; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 > 3 > 5 > 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.6) полностью решена.

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

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

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

Рис.8. Исходные данные к задаче о максимальном потоке

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.8, можно также задать таблицей (табл.9).

Табл.9. Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность
0	1	2
0	2	3
0	3	1
1	2	4
1	3	1
1	4	3
2	3	1
2	4	2
3	4	2

Решение задачи о максимальном потоке может быть получено из следующих соображений.

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

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде таблицы (табл.10)

Табл.10. Решение задачи о максимальном потоке

Пункт отправления	Пункт назначения	План перевозок	Пропускная способность
0	1	2	2
0	2	3	3
0	3	1	1
1	2	0	4
1	3	0	1
1	4	2	3
2	3	1	1
2	4	2	2
3	4	2	2

Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х_KM - объем перевозок из пункта К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х_{KM ,} а именно, Х_{01 ,} Х_{02 ,} Х_{03 ,} Х_{12 ,} Х_{13 ,} Х_{14 ,} Х_{23 ,} Х_{24 ,} Х₃₄ . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F > max ,

Х₀₁ + Х₀₂ + Х₀₃ = F (0)

- Х₀₁ + Х₁₂ + Х₁₃ + Х₁₄ = 0 (1)

- Х₀₂ - Х₁₂ + Х₂₃ + Х₂₄ = 0 (2)

- Х₀₃ - Х₁₃ - Х₂₃ + Х₃₄ = 0 (3)

- Х₁₄ - Х₂₄ - Х₃₄ = - F (4)

Х₀₁ ? 2

Х₀₂ ? 3

Х₀₃ ? 1

Х₁₂ ? 4

Х₁₃ ? 1

Х₁₄ ? 3

Х₂₃ ? 1

Х₂₄ ? 2

Х₃₄ ? 2

Х_КМ ? 0 , К, М = 0, 1, 2, 3, 4

F ? 0 .

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней. Условие (4) - это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").

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

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

5. Расчет параметров сетевой модели

Расчет параметров сетевой модели ведется в следующей последовательности:

1 Расчет ранних сроков свершения событий. Для исходного события ранний срок совершения принимается равным 0, а для последующих рассчитывается путем добавления к раннему сроку предшествующего события продолжительности работы:

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

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

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

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

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

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

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

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

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

6. Отличие динамического программирования от других видов программирования

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

Размещено на Allbest.ru

...