Черненко В.Д. Высшая математика в примерах и задачах (том 3)

Подождите немного. Документ загружается.

150 Г пава 24

Если на /-том шаге в производство вложены средства

Х^

то они

дают доход li(^) и уменьшаются до (р^(Х).

Требуется рационально распределить средства, имеющие-

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

максимальным.

Считаем, что резервные средства вложены в какое-то II

фиктивное предприятие, где они

не

тратятся, но и не дают доход

ЯД)

0; Wi(y)

y (i

\.2....,m).

В данном случае задача решается так же, как задача рас-

пределения ресурсов по неоднородным этапам.

Рассмотрим частный случай резервирования средств, ког-

да (р^(Х)

О,

т. е. когда средства тратятся целиком.

Поставленная задача сводится к отысканию максимума

функции m аргументов Хр Х2, ..., Х^,

где X. неотрицательны и удовлетворяют условию

/=1

Простейшие задачи резервирования ресурсов допускают

элементарное решение

без метода динамического программи-

рования. Например, когда функция дохода на всех этапах одна

и та же

[,(Х)=[,(Х)=...=их)=!(Х),

а средства расходуются полностью

(p,(X)

= ... =

(i>JX)

Максимум дохода достигается тогда, когда средства рас-

пределяются между этапами равномерно:

_ _ _ ^^

Х|

—

... —Х^ —

ПИНЕЙНОЕ И аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

151

6.5.

Задача распределения ресурсов мелсду тремя и бо-

лее предприятиями. Пусть ресурсы распределяются между не-

сколькими предприятиями связи I,

II,...,

{п), причем для каж-

дого предприятия заданы: функция дохода

fl^^(X),

выража-

ющая доход, приносимый средствами X, вложенными в /-м

году в7-е предприятие и функция траты (р\^-(Х)

X, показы-

вающая, насколько убывают средства X на /-м году в j-u

предприятии.

Для трех предприятий фазовое пространство имеет вид (рис.

24.15).

Для случая более чем трех предприятий состояние систе-

мы будет определяться уже/2 числами ^^^\ Х^^\ ..., ^'^''^, обо-

значающими вложения в каждое из предприятий. Распределение

средств производится от конца

началу (условная оптимизация),

а затем от начала до конца.

Рис. 24.15

Управление на /-м шаге будет состоять в вьщелении средств

п предприятиям

Х^^>,

Xj". ....

Xi''^=K-f^Xl'\

i=l

причем здесь следует находить максимум функции нескольких

переменных.

6.6. Распределение ресурсов с

влоэюением

доходов в произ-

водство. 1. Доход вкладывается в производство полностью,

максимизируется сумма всех средств после т-го этапа.

152 Гпава

Рассмотрим

два

предприятия. Выигрыш

представляет

сумму всех средств, сохранившихся в обоих предприятиях плюс

доход на последнем этапе

Поскольку все средства (основные и доход) вкладываются

в производство, то для

-го предприятия функция дохода

на

/-м

шаге обозначим

F.(X),

для

— соответственно G-(Y).

Выигрыш на последнем шаге выражается формулой

^JK,XJ = FJXJ +

GJK-XJ,

где К — средства, с которыми мы подошли к последнему шагу.

Основное функциональное уравнение динамического про-

граммирования будет

W,(K)

m^x{w,^,{F,{X,)^{K-X.S)],

где К — средства, с которыми мы подошли

г-му шагу.

На последнем шаге условный оптимальный выигрыш равен

WJK)

mzx{F^{X^)^G^{K-X^)}.

Далее по основному функциональному уравнению получа-

ем,

начиная

последнего,

все

условные оптимальные выигры-

ши и условные оптимальные управления.

Доход вкладывается

производство полностью на

всех

эта-

пах,

кроме

последнего;

максимизируется доход на последнем шаге.

Задача отличается от предыдущей

тем,

что максимизирует-

ся не сумма оставшихся средств «+» доход на последнем шаге,

только один доход на последнем шаге.

Чтобы отделить сумму оставшихся средств

от

дохода,

для

последнего шага зададим

по

отдельности функции дохода

/тГ^Л

ёт(^) и

функции траты (pJX),

ij/JY).

Полагаем

на

ПИНЕЙНОЕ и аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 153

последнем шаге FJX)

fJX) и GJY)

gJY). Задача сво-

дится к предыдущей задаче.

Доход вкладывается в производство не полностью, а ка-

кая-то часть его отчисляется; максимизируется полный отчис-

ленный доход на всех этапах «+» остаток средств после т-го

этапа.

Для решения задачи зададим функции дохода /

^(Х),

g- (Y)

h2,.,.,m) и функции траты (р^(Х),

y/^fY)

\,2,...,m).

Зададим дополнительную функцию отчислений

r-(D)<D

l,2,.,.,m), которая показывает, какая часть дохода D не

вкладывается, начиная с /+1 шага, а отчисляется.

Состояние системы перед /-м шагом характеризуется коли-

чеством средств К . Выигрыш на /-м шаге

Управление Х- переводит систему из состояния К в состоя-

ние К'

Основное функциональное уравнение будет

W/K)

max{r,(f,(XJ

g,(K-XJ) +

+%j9i(XiH¥i(K-X,)+l(X,)+g,(K-X,)^-

+na^(X,)+g,(K-XJ))}.

Условный оптимальный выигрыш на т-м шаге

WJK)^m^,{!JXJ + gJK-XJ+(pJXJ+iifJK-XJ}.

В остальном схема динамического программирования ос-

тается такой же.

6.7. Задачи динамического

программирования,

не связанные

со

временем.

Пусть имеется группа предприятий Яр

Я2,...,

П^,

которые выполняют одну и ту же операцию. В нашем распоря-

154 Гпава 24

жении

/CQ

средств, которые мы можем вложить, чтобы произве-

сти продукцию сверх плана.

Каждое предприятие может освоить только ограниченное

количество средств

^Р ^2—От-

вели в предприятие П. вложены средства X., оно даст

(Pi(X) единиц дополнительной продукции. Требуется так рас-

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

объем дополнительной продукции был бы максимальным. То

есть сумма всех вложенных средств была бы меньше имею-

щихся

гп

/=1

а выигрыш был бы

^w. =max.

i=\

где w. —дополнительная продукция/-ГО предприятия.

Оптимальное управление на последнем шаге состоит в том,

чтобы т-му предприятию выделить все К средств <

/С^

, т. е.

\К при К<К

XJK)

\ ^

приК>К^

Максимальный доход на последнем шаге будет

WJK)

wJK)

cpJxJK)).

Доход на предпоследнем шаге будет

Основное функциональное уравнение динамического про-

граммирования

ПИНЕЙНОЕ

аИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

155

^:да=тах{(р,гх,;+^,/л:-;^,;}

И ВСЯ

процедура решения не отличается от задачи распределения

ресурсов

неоднородными этапами.

6.8. Задачи динамического программирования

мультипли-

кативным критерием.

До сих пор мы

рассматривали задачи,

когда выигрыш складывался

из

суммы выигрышей

Иногда возникают задачи, когда выигрыш представляет

собой не сумму,

произведение

/=1

где

ш. -

выигрыш

на /-м

шаге.

Такой показатель

называется

мультипликативнъш.

Основное функциональное уравнение примет вид

W/S)

max{w,(S,U,)-W,J(p/S.U,))},

а условие оптимальности последнего шага будет

WJS)

m^{wJS,Uj}.

Рассмотрим,

примеру, задачу распределения средств

по-

вышения надежности технического устройства. Пусть устрой-

ство состоит

из т

элементов. Надежность всей машины равна

произведению надежностей всех элементов

где

р.

— надежность /-го элемента.

Количество средств

вложенных в приспособление, повы-

шает надежность до значения

р.

=[.(Х). Требуется определить

156 Г пава 24

оптимальное распределение средств по элементам. Выигрыш на

/-М шаге pi =fi(X.), X. — количество средств, вложенных в

/-Й

элемент.

Основное функциональное уравнение

P/K)

max{f,(XJ-P,JK-X,)}.

Поскольку средства расходуются до конца, управление на

последнем шаге состоит в том, чтобы выделить на этот шаг все

оставшиеся средства

При

ЭТОМ

достигается условный оптимальный выигрыш

pJf<)

L(K).

Отсюда находим последовательные условные оптимальные

управления х^_^(К),х^_^(К), ... ^x^fK) и условные опти-

мальные выигрыши

р^_^(К),

Рт-2(^)>

••• ^Pli^)

•

Первый шаг определяется исходным количеством средств

Px(^J

=^^^{fi(^i)'P2(f^o-^i)}

управления X,

=x,(KJ.

Далее оптимальное управление стрится по обычной схеме.

Глава 25

ЭЛЕМЕНТЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ.

СЛУЧАЙНЫЕ СОБЫТИЯ

25.1.

Основные понятия теории

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

1°.

Всякий результат или исход испытания называется со-

бытием

и обозначается прописными буквами латинского алфа-

вита ^,Д С...

События называются

несовместными,

если в условиях ис-

пытания каждый раз возможно появление только одного из них.

События называются совместными, если в данных условиях

появление одного из этих событий не исключает возможности

появления других при том же испытании.

События Am А (не А) называются

противополож:ными,

если

данных условиях они несовместны, являясь единственны-

ми его исходами, т. е. появление одного из них исключает появ-

ление другого.

Статистическое определение вероятности. Под вероят-

ностью появления события понимается постоянная величина,

около которой группируются наблюдаемые значения частости

158 Гпава 25

т/п, где т — число проявлений события А при п независимых

испьгганиях.

Классическое определение

вероятности.

Под вероятностью

наступления события понимается отношение числа исходов, бла-

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

всех несовместных и равновозможных

исходов.

Вероятность по-

тп

явления события А обозначается Р{А) - —, где т — число ис-

ходов, благоприятствующих появлению события А,п — число

всех исходов.

Геометрические

вероятности.

Пусть g

—

мера длины, пло-

щади, объема представляет часть области

Вероятность попа-

дания брошеной точки в область

пропорциональна мере этой

области и не зависит ни от от формы области G, ни от ее распо-

ложения относительно

Тогда вероятность попадания точки в

область определяется равенством

мера G

Событие называется

достоверным,

если оно является един-

ственно возможным исходом испытания. Вероятность достовер-

ного события равна единице Р{А)

\. Если событие А заведомо

не может произойти, то оно называется

невозможным.

Вероят-

ность невозможного события равна нулю.

Если событие А при реализации некоторого комплекса ус-

ловий может произойти, а может

не произойти, то оно называ-

ется

случайным.

Вероятность случайного события удовлетворяет

двойному неравенству

< Р(^) < 1.

2°.

Основные понятия теории соединений. Перестановка-

ми из п различных элементов называются всевозможные соеди-

нения из этих п элементов, отличающиеся только порядком их

расположения

Р^

= п!.

ЭПЕМЕНТЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ 159

Размещениями из различных п элементов по т элементов

называются соединения, которые отличаются либо составом,

либо порядком своих элементов

Сочетаниями из п элементов по т элементов называются

соединения, которые различаются только составом своих эле-

ментов

А:

п!

С" =

Р т!(п

—

т)!

3°.

Правило

суммы.

Если некоторый элемент А может быть

выбран из совокупности элементов т способами, а другой эле-

мент В- п способами, то выбрать либо А, либо В можно

та

+ п

способами.

Правило

произведения.

Если элемент А можно выбрать из

совокупности элементов т способами и после этого элемент В

можно выбрать п способами, то оба элемента (А, В) в указан-

ном порядке могут быть выбраны тп способами.

1.1. В партии из 120 изделий отдел технического контроля

обнаружил 6 нестандартных. Чему равна относительная часто-

та появления нестандартного изделия?

Решение. Относительная частота появления нестандартно-

го изделия равна отношению числа испытаний, в которых это

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

W = — = 0,05.

120

1.2. В урне 4 черных, 3 красных и 5 белых шаров. Найти

вероятность

того,

что вынутый шар

окажется:

а) черным;

б)

крас-

ным; в) синим; г) белым.