Некрасова М.Г. Методы оптимизации - файл n1.doc

приобрести
Некрасова М.Г. Методы оптимизации
скачать (3013.5 kb.)
Доступные файлы (1):
n1.doc3014kb.22.08.2012 14:29скачать

n1.doc

1   ...   4   5   6   7   8   9   10   11   12

8.6. Дискретная динамическая модель оптимального распределения ресурсов

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

Рассмотрим дискретную динамическую модель на примере задачи распределения инвестиций. Требуется распределить имеющиеся В единиц средств среди n предприятий, доход gi(xi) от которых в зависимости от количества вложенных средств xi определяется матрицей , приведенной в табл. 21 так, чтобы суммарный доход со всех предприятий был бы максимальным.

Таблица 21

        gi

x       

g1

g2

. . .

gi

. . .

gn

x1

g1(x1)

g2(x1)



gi(x1)

 

gn(x1)

x2

g1(x2)

g2(x2)



gi(x2)

 

gn(x2)

xi







gi(xi)





xn

g1(xn)

g2(xn)



gi(xn)

 

gn(xn)

 

Запишем математическую модель задачи.

Определить  удовлетворяющий условиям

                                                               (32), (33)

и обеспечивающий максимум целевой функции

                                            (34)

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

С этой целью разобьем процесс оптимизации на n шагов и будем на каждом k-том шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом естественно считать, что в остальные предприятия (с первого по (k – 1)-е) тоже вкладываются средства, и поэтому на инвестирование предприятий с k-го по n-е остаются не все средства, а некоторая меньшая сумма Ck B. Эта величина и будет являться переменной состояния системы. Переменной управления на k-том шаге назовем величину xk средств, вкладываемых в k-тое предприятие. В качестве функции Беллмана Fk(Ck) на k-том шаге можно выбрать максимально возможный доход, который можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось Ck средств. Очевидно, что при вложении в k-е предприятие xk средств будет получена прибыль gk(xk), а система к (k + 1)-му шагу перейдет в состояние Sk+1 и, следовательно, на инвестирование предприятий с (k + 1)-го до n-го останется Ck+1=(Ck-xk) средств.

Таким образом, на первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств Cn, . Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е.



На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на k-м шаге для инвестирования предприятий с k-го по n-е осталось Ck средств (). Тогда после вложения в k-ое предприятие xk средств будет получена прибыль gkk), а на инвестирование остальных предприятий (с k-го по n-е) останется   средств. Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), будет равен:

                                 (30)

Максимум выражения (30) достигается на некотором значении , которое является оптимальным управлением на k-ом шаге для состояния системы Sk. Действуя таким образом, можно определить функцию Беллмана и оптимальные управления до шага k = 1.

Значение функции Беллмана F1(C1) представляет собой максимально возможный доход со всех предприятий, а значение , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина  и оптимальным управлением на k-м шаге является то значение xk, которое обеспечивает максимум дохода при соответствующем состоянии системы Sk.

Пример 73. На развитие трех предприятий выделено 5 млн. р. Известна эффективность капитальных вложений в каждое предприятие, заданная значением нелинейной функции gi(xi) представленной в табл. 22. Необходимо распределить выделенные средства между предприятиями таким образом, чтобы получить максимальный суммарный доход.

Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах xi = {0, 1, 2, 3, 4, 5} млн. р.

Таблица 22

x

g1

g2

g3

0

0

0

0

1

2.2

2

2.8

2

3

3.2

5.4

3

4.1

4.8

6.4

4

5.2

6.2

6.6

5

5.9

6.4

6.9

 

Решение. 1 этап. Условная оптимизация.

1-й шаг: k = 3. Предположим, что все средства в количестве x3 = 5 млн. р. отданы третьему предприятию. В этом случае максимальный доход, как это видно из табл. 23, составит g3(X3) = 6.9 тыс. р., следовательно:

F3(c3) = g3(x3).

Таблица 23

x3

c3

0

1

2

3

4

5

F3(c3)

x3*

0

0

-

-

-

-

-

0

0

1

-

2,8

-

-

-

-

2,8

1

2

-

-

5,4

-

-

-

5,4

2

3

-

-

-

6,4

-

-

6,4

3

4

-

-

-

-

6,6

-

6,6

4

5

-

-

-

-

-

6,9

6,9

5

 

2-й шаг: k = 2. Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим предприятиями. При этом соотношение Беллмана имеет вид



на основе которого составлена табл. 24:

Таблица 24

x2

c2

0

1

2

3

4

5

F2(c2)

x2*

0

0+0

-

-

-

-

-

0

0

1

0+2,8

2+0

-

-

-

-

2,8

0

2

0+5,4

2+2,8

3,2+0

-

-

-

5,4

0

3

0+6,4

2+5,4

3,2+2,8

4,8+0

-

-

7,4

1

4

0+6,6

2+6,4

3,2+5,4

4,8+2,8

6,2+0

-

8,6

2

5

0+6,9

2+6,6

3,2+6,4

4,8+5,4

6,2+2,8

6,4+0

10,2

3

 

3-й шаг: k = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими предприятиями, используя следующую формулу для расчета суммарного дохода:



на основе которого составлена табл. 25:

Таблица 25

x1

c1

0

1

2

3

4

5

F1(c1)

x1*

0

0+0

-

-

-

-

-

0

0

1

0+2,8

2,2+0

-

-

-

-

2,8

0

2

0+5,4

2,2+2,8

3+0

-

-

-

5,4

0

3

0+7,4

2,2+5,4

3+2,8

4,1+0

-

-

7,6

1

4

0+8,6

2,2+7,4

3+5,4

4,1+2,8

5,2+0

-

9,6

1

5

0+10,2

2,2+8,6

3+7,4

4,1+5,4

5,2+2,8

5,9

10,8

1

 

2 этап. Безусловная оптимизация.

Определяем компоненты оптимальной стратегии.

1-й шаг. По данным табл. 25 максимальный доход при распределении 5 млн. р. между тремя предприятиями составляет: с1 = 5, F1(5) = 10.8. При этом первому предприятию нужно выделить х1* = 1 млн. р.

2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий.

с2 = с1 – х1* = 5 – 1 = 4 млн. р.

По данным табл. 24 находим, что оптимальный вариант распределения денежных средств размером 4 млн. р. между вторым и третьим предприятиями составляет:          F2 (4) = 8.6 при выделении второму предприятию х2* = 2 млн. р.

3-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего предприятия:

с3 = с2 – х2* = 4 – 2 = 2 млн. р.

По данным табл. 25 находим:

F3(2)  = 5.4 и х3* = 2 млн. р.

Таким образом, оптимальный план инвестирования предприятий:

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

F(5) = g1(1) + g2(2) + g3(2) = 2.2 + 3.2 + 5.4 = 10.8 млн. р.

8.7. Выбор оптимальной стратегии обновления оборудования

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

Предположим, что планируется эксплуатация оборудования в течение некоторого периода времени продолжительностью n лет. Оборудование имеет тенденцию с течением времени стареть и приносить все меньший доход r(t) (t – возраст оборудования). При этом есть возможность в начале любого года продать устаревшее оборудование за цену S(t), которая также зависит от возраста t, и купить новое оборудование за цену P. Под возрастом оборудования понимается период эксплуатации оборудования после последней замены, определенный в годах. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарный доход за все n лет был максимальным, учитывая, что к началу эксплуатации возраст оборудования составлял t0 лет.

Исходными данными в задаче являются доход r(t) от эксплуатации в течение одного года оборудования возраста t лет,  остаточная стоимость S(t), цена нового оборудования P и начальный возраст оборудования t0.

Таблица 26

t

0

1



n

r

r(0)

r(1)



r(n)

S

S(0)

S(1)



S(n)

 

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

Выберем в качестве шага оптимизацию плана замены оборудования с k-го по n-й годы.

Очевидно, что доход от эксплуатации оборудования за эти годы будет зависеть от возраста оборудования к началу рассматриваемого шага, т. е. k-го года.

Поскольку процесс оптимизации ведется с последнего шага (k = n), то на k-м шаге неизвестно, в какие годы с первого по (k – 1)-й должна осуществляться замена и соответственно неизвестен возраст оборудования к началу k-го года. Возраст оборудования, который определяет состояние системы, обозначим t. На величину t накладывается следующее ограничение:

                                                              (*)

Выражение (*) свидетельствует о том, что t не может превышать возраст оборудования за (k – 1)-й год его эксплуатации с учетом возраста к началу первого года, который составляет t0 лет; и не может быть меньше единицы (этот возраст оборудование будет иметь к началу k-го года, если замена произошла в начале предыдущего (k – 1)-го года).

Таким образом, переменная t в данной задаче является переменной состояния системы на k-м шаге.

Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (C) или заменить (З) оборудование в начале k-го года:



Функцию Беллмана Fk(t) определяют как максимально возможный доход от эксплуатации оборудования за годы с k-го по n-й, если к началу k-го возраст оборудования составлял t лет. Применяя то или иное управление, система переходит в новое состояние. Так, например, если в начале k-го года оборудование сохраняется, то к началу (k + 1)-го года его возраст увеличится на единицу (состояние системы станет t+1), в случае замены старого оборудования новое достигнет к началу (k + 1)-го года возраста tI = 1 год.

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

Если в начале каждого года сохраняется оборудование, возраст которого t лет, то доход за этот год составит r(t). К началу (k + 1)-го года возраст оборудования достигнет (t + 1) и максимально возможный доход за оставшиеся годы (с (k + 1)-го по n-й) составит Fk+1(t+1). Если в начале k-го года принято решение о замене оборудования, то продается старое оборудование возраста t лет по цене S(t), приобретается новое за P единиц, а его эксплуатация в течение k-го года нового оборудования принесет прибыль r(0). К началу следующего года возраст оборудования составит 1 год и за все оставшиеся годы с (k + 1)-го по n-й максимально возможный доход будет Fk+1(1). Из двух возможных вариантов управления выбирается тот, который приносит максимальный доход. Таким образом, уравнение Беллмана на каждом шаге управления имеет вид

                                       (31)

Функция Fk(t) вычисляется на каждом шаге управления для всех . Управление, при котором достигается максимум дохода, является оптимальным.

Для первого шага условной оптимизации при k = n функция представляет собой доход за последний n-й год:

                                               (32)

Значения функции Fn(t), определяемые Fn-1(t), Fn-2(t) вплоть до F1(t). F1(t0) представляют собой возможные доходы за все годы. Максимум дохода достигается при некотором управлении, применяя которое на первом году, мы определяем возраст оборудования к началу второго года. Для данного возраста оборудования выбирается управление, при котором достигается максимум дохода за годы со второго по n-й и т. д. В результате на этапе безусловной оптимизации определяются годы, в начале которых следует произвести замену оборудования.

Пример 74. Найти оптимальную стратегию эксплуатации оборудования на период продолжительностью 6 лет, если годовой доход r(t) и остаточная стоимость S(t) в зависимости от возраста заданы табл. 27, стоимость нового оборудования равна          P = 13, а возраст оборудования к началу эксплуатационного периода составлял 1 год.

Таблица 27

t

0

1

2

3

4

5

6

r(t)

8

7

7

6

6

5

5

S(t)

12

10

8

8

7

6

4

 

Решение. 1 этап. Условная оптимизация.

1-й шаг. k = 6. Для первого шага возможные состояния системы t = 1, 2, …, 6. Функциональное управление имеет вид (31).













2-й шаг. k = 5. Для второго шага возможные состояния системы t = 1, 2, …, 5. Функциональное уравнение имеет вид













3-й шаг. k = 4.











4-й шаг. k = 3.









5-й шаг. k = 2.







6-й шаг. k = 1.





Результаты вычислений Беллмана Fk(t) приведены в следующей таблице, в которой k – год эксплуатации, t – возраст оборудования.

Таблица 28

t

k

1

2

3

4

5

6

1

37

 

 

 

 

 

2

31

30

 

 

 

 

3

26

24

23

 

 

 

4

20

19

17

16

 

 

5

14

13

12

11

10

 

6

7

7

6

6

5

5

 

В табл. 28 выделено серым значение функции, соответствующее состоянию (З) - замена оборудования.

2-й этап. Безусловная оптимизация.

Безусловная оптимизация начинается с шага при k = 1. Максимально возможный доход от эксплуатации оборудования за годы с 1-го по 6-й составляет F1(1) = 37. Этот оптимальный выигрыш достигается, если на первом году не производить замены оборудования. Тогда к началу второго года возраст оборудования увеличится на единицу и составит: t2 = t1 + 1 = 1 + 1 = 2. Безусловно, оптимальное управление при k=2, х2(2) = С, т. е. максимум дохода за годы со 2-го по 6-й достигается, если оборудование не заменяется.

К началу третьего года при k=3 возраст оборудования станет: t3 = t2 + 1 = 3. Безусловное оптимальное управление х3(3) = З, т. е. для получения максимума прибыли за оставшиеся годы необходимо провести замену оборудования.

К началу четвертого года при k=4 возраст оборудования станет равен t4=1. Безусловное оптимальное управление х4(1) = С.

Далее соответственно:



Таким образом, за 6 лет эксплуатации оборудования замену надо произвести один раз – в начале третьего года эксплуатации.

8.8. Выбор оптимального маршрута перевозки грузов

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













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

В задаче имеется ограничение – двигаться по изображенным на схеме маршрутам можно только слева направо, т.е. попав, например, в пункт 7, мы имеем право переместиться только в пункт 10 и не можем возвратиться обратно в 5-й или 6-й. Эта особенность транспортной сети дает право отнести каждый из десяти пунктов к одному из поясов. Будем считать, что пункт принадлежит k-му поясу, если из него можно попасть в конечный пункт ровно за k шагов, т. е. с заездом ровно в (k-1)-й промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 – ко второму, 2, 3, 4 – к третьему, 1 – к четвертому. Тогда на k-м шаге будем находить оптимальные маршруты перевозки груза из пунктов k-го пояса до конечного пункта. Оптимизацию будем производить с конца процесса, и потому, дойдя до k-го шага, неизвестно, в каком из пунктов k-го пояса окажется груз, перевозимый из первого пункта.

Введем обозначения:

k – номер шага (k = 1, 2, 3, 4);

i – пункт, из которого осуществляются перевозки (i = 1, 2, …, 9);

j – пункт, в который доставляется груз (j = 2, 3, …, 10);

cij – стоимость перевозки груза из пункта i  в пункт j.

Fk(i) – минимальные затраты на перевозку груза на k-м шаге решения задачи из пункта i до конечного пункта.

Очевидно, что минимум затрат на перевозку груза из пунктов k-го пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы оказались. Номер i пункта, принадлежащего k-му поясу, будет являться переменной состояния системы на k-м шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в некотором пункте i k-го пояса, принимается решение о перемещении груза в один из пунктов (k-1)-го пояса, а направление дальнейшего движения известно из предыдущих шагов. Номер j пункта (k-1)-го пояса будет переменной управления на k–м шаге.

Для первого шага управления (k=1) функция Беллмана представляет собой минимальные затраты на перевозку груза из пунктов 1-го пояса в конечный пункт, т. е. . Для последующих шагов затраты складываются из двух слагаемых – стоимости перевозки груза  Cij из пункта i k-го пояса в пункт j (k-1)-го пояса и минимально возможных затрат на перевозку из пункта j до конечного пункта, т.е. Fk1(j). Таким образом, функциональное уравнение Беллмана будет иметь вид



Минимум затрат достигается на некотором значении j*, которое является оптимальным направлением движения из пункта 1 в конечный пункт.

На четвертом шаге попадаем на 4-й пояс и состояние системы становится определенным i=1. Функция F4(1) представляет собой минимально возможные затраты по перемещению груза из 1-го пункта в 10-й. Оптимальный маршрут определяется в результате анализа всех шагов в обратном порядке, а выбор некоторого управления j на k-м шаге приводит к тому, что состояние системы на (k-1)-м шаге становится определенным.

Пример 75. Решим сформулированную выше задачу, исходные данные которой приведены на рис. 43.

Решение.1 этап. Условная оптимизация.

1-й шаг. k=1.

F1(i)=Ci10

На первом шаге в пункт 10 груз может быть доставлен из пунктов 7, 8 или 9.

Таблица 29

j

i

10

F1(i)

j*

7

7

7

10

8

9

9

10

9

11

11

10

 

2-й шаг. k=2.

Функциональное уравнение на втором шаге принимает вид



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

Таблица 30

j

i

7

8

9

F2(i)

j*

5

8+7

6+9

-

15

7; 8

6

5+7

-

4+11

12

7

 

3-й шаг. k=3.



Таблица 31

j

i

5

6

F3(i)

j*

2

4+15

-

19

5

3

-

3+12

15

6

4

-

9+12

21

6

 

4-й шаг. k=4.



Таблица 32

j

i

2

3

4

F3(i)

j*

1

7+19

5+15

6+21

20

3

 

2 этап. Безусловная оптимизация.

На этапе условной оптимизации получено, что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют F4(1)=20.  Данный результат достигается при движении груза из 1-го пункта в 3-й. По данным таблицы третьего шага необходимо двигаться в пункт 6, затем – в пункт 7 (см. таблицу второго шага) и из него – в конечный пункт (см. таблицу первого шага). Таким образом, оптимальный маршрут доставки груза: 1  3  6  7  10. На рис. 45 жирными стрелками показан оптимальный путь.














8.9. Построение оптимальной последовательности операций

в коммерческой деятельности

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

Из условия следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости XOY, на ограниченном прямыми прямоугольнике, который является областью допустимых состояний системы. Если по оси Х отложить число (n) разгруженных машин, а по оси Y – число (m) загруженных товаром машин, то можно построить на плоскости граф состояний процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.

Пример 76. Пусть n = 6, m = 4. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 46).













Точка So определяет начало процесса, а S1 – конечное состояние, соответствующее приему и отправке всех машин. Оптимизацию процесса будем производить с конечного состояния – S1. Весь процесс разобьем на шаги, их количество k = n + m = 6 + 4 =10. Каждый шаг представляет собой сечение графа состояний, проходящее через вершины (на рис. 46 сечения показаны косыми линиями).

1 этап. Условная оптимизация.













1-й шаг. k = 1. На первом шаге, с задаваемым сечением A1, B1,  из состояний A1 и В1 возможен только один вариант перехода в  конечное состояние S1. Поэтому в вершинах А1 и В1 записываем соответственно издержки 8 и 11. Ребра A1S1 и B1S1 обозначаем стрелкой, направленной в вершину S1,  как показано на рис. 47.

2-й шаг. k = 2. Второй шаг оптимизации задается сечением по вершинам A2, B2, C1. Из состояний A2 и С1 возможен единственный переход в вершины А1 и В1 соответственно, поэтому в вершинах А2 и С1 записываем суммарные издержки 17 и 22 на первых двух шагах перехода в конечное состояние S1.













Из вершины В2 возможны два варианта перехода: в вершину А1 или вершину В1. При переходе В2 А1 сумма издержек составляет 10+8=18, на переходе В2 В1 сумма составляет 13+11=24. Из двух вариантов суммарных издержек выбираем наименьшую (18) и обозначаем стрелкой условно оптимальный переход В2 А1, как показано на рис. 48.

3-й шаг. k = 3. На третьем шаге сечение проходит через вершины A3, B3, C2, D1. Из вершин A3 и D1 возможен единственный переход в вершины А2 и С1 соответственно. Суммарные издержки для состояния D1 равны 22+12=34. Из вершины B3 возможны два варианта перехода: в вершину А2 - издержки равны 17+8=25; в вершину В2 – 18+9=27.

Для вершины С2 возможен переход в вершину В2 (18+10=28) и в вершину С1 (22+12=34). Выбираем для вершин В3 и С2 наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход, как показано на рис. 49.













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

Минимально возможные суммарные издержки по обслуживанию всех 10 машин на оптовой базе составляют 88 усл. ед.

2-й этап. Безусловная оптимизация.

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













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













Минимальные издержки Fmin соответствуют следующему оптимальному пути на графе:



и равны: Fmin = 12+9+9+7+7+10+9+8+9+8=88 усл. ед.

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

Вопросы к главе 8

1.    Как формулируется задача динамического программирования?

2.    В чем заключаются особенности математической модели ДП?

3.    Что лежит в основе метода ДП?

4.    Сформулируйте задачу кратчайших расстояний по заданной сети. На сколько этапов разбивается задача? Сколько шагов содержится в каждом этапе и в чем суть этапа и шага?

5.    Что является переменной управления и переменной состояния в задаче выбора оптимальной стратегии обновления оборудования?

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

7.    Запишите математическую модель оптимального распределения инвестиций и рекуррентное соотношение Беллмана для ее реализации.

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ

РАСЧЕТНО-ГРАФИЧЕСКОГО ЗАДАНИЯ

При выполнении расчетно-графического задания следует строго придерживаться указанных ниже правил.

1.    Выбор варианта РГЗ осуществляется в соответствии с последними двумя цифрами учебного шифра студента. Если предпоследняя цифра шифра четная или ноль, то выбирается вариант с 1 по 10, соответствующий последней цифре (например, если цифры 41 или 01, то соответствует вариант 1). Если же предпоследняя цифра шифра нечетная, то выбирается вариант с 11 по 20, соответствующий последней цифре (например, если цифры 31 или 11, то соответствует вариант 11).

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

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

4.    Приступая к выполнению РГЗ, необходимо изучить теоретический материал и ознакомиться с практической частью пособия. Решения задач следует оформлять аккуратно, подробно объясняя ход решения. В конце работы необходимо привести список использованной литературы, указать дату выполнения работы и поставить свою подпись.

5.    После получения проверенной работы необходимо исправить в ней отмеченные рецензентом ошибки и недочеты. Работа над ошибками, как правило, делается в той же тетради, что РГЗ. При необходимости, работу над ошибками допускается выполнять в новой тетради, но при отсылке на рецензирование необходимо приложить первоначальный вариант РГЗ.

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 1

Задача 1. Найти точки локального экстремума функции и значения функции в них:

  1.  

a)

f(x) = -3(x – 10)5;

б)

f(x) = -10x2e-10x;

  1.  

a)

f(x) = -6(x + 1)5;

б)

f(x) = 4x2e9x;

  1.  

a)

f(x) = 3(x – 1)5;

б)

f(x) = -6x2e-6x;

  1.  

a)

f(x) = -4(x + 9)5;

б)

f(x) = -3x2e2x;

  1.  

a)

f(x) = 4(x + 7)5;

б)

f(x) = 4x2e-9x;

  1.  

a)

f(x) = -8(x + 8)5;

б)

f(x) = -10x2e5x;

  1.  

a)

f(x) = -8(x – 10)5;

б)

f(x) = -7x2e2x;

  1.  

a)

f(x) = -9(x – 2)5;

б)

f(x) = 2x2e8x;

  1.  

a)

f(x) = 6(x – 10)5;

б)

f(x) = 5x2e-6x;

  1.  

a)

f(x) = 9(x – 9)5;

б)

f(x) = -10x2e8x;

  1.  

a)

f(x) = -9(x – 4)5;

б)

f(x) = -9x2e6x;

  1.  

a)

f(x) = -9(x + 8)5;

б)

f(x) = 3x2ex;

  1.  

a)

f(x) = 5(x + 3)5;

б)

f(x) = 3x2ex;

  1.  

a)

f(x) = 5(x – 8)5;

б)

f(x) = -8x2e7x;

  1.  

a)

f(x) = -8(x + 7)5;

б)

f(x) = 2x2e4x;

  1.  

a)

f(x) = -7(x + 9)5;

б)

f(x) = -5x2e-10x;

  1.  

a)

f(x) = -2(x – 3)5;

б)

f(x) = 9x2e-6x;

  1.  

a)

f(x) = 5(x + 2)5;

б)

f(x) = -4x2e-10x;

  1.  

a)

f(x) = -9(x + 1)5;

б)

f(x) = 8x2e2x;

  1.  

a)

f(x) = -6(x – 5)5;

б)

f(x) = 2x2e-x.

Задача 2. Найти наибольшее и наименьшее значения функции f(x) на отрезке [a; б].

1.

f(x) = -10x3 +15x2 + 6,

[-0.1, 2];

2.

f(x) = 3x3 –4.5x2 +9,

[-0.1, 2.3];

3.

f(x) = -4x3 +6x2 + 1,

[-0.4, 2.5];

4.

f(x) = 7x3 + 10.5x2 + 7,

[-0.5, 2.6];

5.

f(x) = -6x3 + 9x2 + 8,

[-0.1, 2.4];

6.

f(x) =-7x3 +10.5x2 + 2,

[-0.3, 2];

7.

f(x) = -3x3 + 4.5x2 + 1,

[-0.5, 2.7];

8.

f(x) = -2x3 + 3x2 + 10,

[-0.6, 2.9];

9.

f(x) = 9x3 – 13.5x2 + 9,

[-0.5, 2.6];

10.

f(x) = -9x3 + 13.5x2 + 7,

[-0.6, 2.5];

11.

f(x) = 2x3 – 3x2 + 3,

[-0.4, 2.2];

12.

f(x) = 2x3 – 3x2 + 6,

[-0.3, 2.1];

13.

f(x) = -4x3 + 6x2 + 3,

[-0.4, 2.8];

14.

f(x) = 3x3 – 4.5x2 + 9,

[-0.3, 2.5];

15.

f(x) = 5x3 – 7.5x2 + 2,

[-0.4, 2.1];

16.

f(x) = -10x3 + 15x2 + 7,

[-0.4, 2.4];

17.

f(x) = -9x3 + 13.5x2 +5,

[-0.4, 2.8];

18.

f(x) = -10x3 + 15x2 + 1,

[-0.1, 2.3];

19.

f(x) = -10x3 + 15x2 + 4,

[-0.6, 2.9];

20.

f(x) = 8x3 – 12x2 + 8,

[-0.6, 2.9].

 

Задача 3. Найти точки перегиба, промежутки выпуклости и вогнутости графика функции f(x).

1.        f(x) = 6x3-6x2+2x+6;

2.        f(x) = -8x3-10x2+2x+9;

3.        f(x) = -3x3+8x2-6x+1;

4.        f(x) = 6x3+6x2-2x+7;

5.        f(x) = 2x3-2x2-10x+8;

6.        f(x) = 9x3+6x2-2x+2;

7.        f(x) = 6x3+4x2-10x+1;

8.        f(x) = 3x3+3x2+6x+10;

9.        f(x) = 4x3-7x2-9x+9;

10.    f(x) = -5x3-8x2+6x+7;

 

11.         f(x) = -7x3-4x2-9x+3;

12.         f(x) = -3x3+4x2+7x+6;

13.         f(x) = 3x3-8x2-4x+3;

14.         f(x) = -7x3-8x2+3x+9;

15.         f(x) = -7x3+9x2+7x+2;

16.         f(x) = 2x3+2x2-4x+7;

17.         f(x) = -10x3-5x2+7x+5;

18.         f(x) = 2x3-3x2+6x+1;

19.         f(x) = -3x3+4x2-2x+4;

20.         f(x) = 8x3-2x2+4x+8.

 

 

Задача 4. Для данной функции двух переменных z = f(x, y) найти градиент функции в точке М(х0, у0)  и найти производную в той же точке М по направлению вектора MN.

1.

z = x2 + y3 – 24x2y,

M(-2, 3),

N(-5, 5);

2.

z = x2 + y3 – 15x2y,

M(0, -4),

N(2, -9);

3.

z = x2 +y3 – 6x2y,

M(-5, 4),

N(-6, 5);

4.

z = x2 + y3 – 21x2y,

M(0, -3),

N(0, -4);

5.

z = x2 + y3 – 12x2y,

M(-4, 2),

N(-6, 2);

6.

z = x2 + y3 – 30x2y,

M(4, 3),

N(6, 3);

7.

z = x2 + y3 – 15x2y,

M(0, -3),

N(4, -1);

8.

z = x2 + y3 – 15x2y,

M(1, -4),

N(-2, 0);

9.

z = x2 + y3 – 21x2y,

M(1, 0),

N(-2, -1);

10.

z = x2 + y3 – 27x2y,

M(-2,0),

N(-6, 1);

11.

z = x2 + y3 – 15x2y,

M(-4, 3),

N(-6, 0);

12.

z = x2 + y3 – 24x2y,

M(-4, 2),

N(-8, 1);

13.

z = x2 + y3 – 9x2y,

M(-1, -3),

N(-6, -4);

14.

z = x2 + y3 – 9x2y,

M(3, 4),

N(2, 6);

15.

z = x2 + y3 –27x2y,

M(2, 0),

N(3, -5);

16.

z = x2 + y3 – 15x2y,

M(0, 4),

N(0, 8);

17.

z = x2 + y3 – 27x2y,

M(3, -5),

N(3, -8);

18.

z = x2 + y3 – 27x2y,

M(-1, -3),

N(-4, -7);

19.

z = x2 + y3 – 27x2y,

M(3, 0),

N(5, 3);

20.

z = x2 + y3 – 12x2y,

M(0, -4),

N(-4, -9).

 

Задача 5.Исследовать функцию двух переменных z = f(x, y) на локальный экстремум.

 
1.      z = x3 + y3 – 9xy;

2.      z = x3 + y3 –18xy;

3.      z = x3 + y3 – 27xy;

4.      z = x3 +y3 – 3xy;

5.      z = x3 + y3 – 21xy;

6.      z = x3 + y3 – 30xy;

7.      z = x3 + y3 – 6xy;

8.      z = x3 + y3 – 17xy;

9.      z = x3 + y3 – 5xy;

10.  z = x3 + y3 – 13xy;

11.  z = x3 + y3 – 25xy;

12.  z = x3 + y3 – 16xy;

13.  z = x3 + y3 – 19xy;

14.  z = x3 + y3 – 4xy;

15.  z = x3 + y3 – 7xy;

16.  z = x3 + y3 – 20xy;

17.  z = x3 + y3 – 2xy;

18.  z = x3 + y3 – 29xy;

19.  z = x3 + y3 – 11xy;

20.  z = x3 + y3 – 12xy.

ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАЧИ 1

Задача.  Найти точки локального экстремума функции и значения функции в них:



Решение. а) Находим производную:

Решим уравнение    х=11.

Функция f(x) определена и непрерывна на всей числовой оси. Поэтому точка х=11 является критической точкой. Других критических точек нет, так как  существует всюду.

Исследуем критическую точку, определяя знак первой производной, слева и справа от неё.

                              Таблица 33

x

0

11

20



+

0

+

f(x)

возрастает

 

возрастает

Так как на всей числовой оси функция возрастает, то она не имеет экстремумов.

б) Находим производную:

Решим уравнение



Функция f(x) определена и непрерывна на всей числовой оси. Поэтому точки х1=0 и х2=0,25  являются критическими точками. Других критических точек нет, так как f(x) существует всюду. Исследуем критические точки, определяя знак первой производной, слева и справа от каждой точки.

Таблица 34

x

-1

0

0.1

0.25

1



-

0

+

0

-

f (x)

убывает

 

возрастает

 

убывает

 

На интервале (0; 0,25) функция возрастает, а на интервалах  (-; 0) и (0,25; +) – убывает.

Значит, х1=0 – точка минимума, f(0)=0; х2=0,25 – точка максимума, f(0.25)0.0596.

ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАЧИ 2

Задача. Найти наибольшее и наименьшее значения функции на интервале [-0.9; 2.2].

Решение. Найдем критические точки функции f(x), лежащие внутри заданного отрезка: ,  при х1=0 и х2=-1/3. Эти точки лежат внутри рассматриваемого отрезка и являются критическими. Вычислим значения функции на концах отрезка и в критических точках:

f(-0.9)=9.732; f(-1/3) 12.1296; f(0)=12; f(2.2) 103.476.

Сравнивая все вычисленные значения функции во внутренних критических точках и на концах отрезка, заключаем: наибольшее значение функции f(x) на отрезке [-0.9; 2.2] равно 103,476 и достигается на правой границе отрезка х=2,2, а её наименьшее значение равно 9,732 и достигается на левой границе отрезка х=-0,9.

ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАЧИ 3

Задача. Найти  точки перегиба, промежутки выпуклости и вогнутости функции

Решение. Найдем последовательно первую и вторую производную функции f(x):



Решим уравнение

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

Таблица 35

х

-1

-4/9

0



-

0

+

f(x)

выпукла

перегиб

вогнута

Значит, на интервале (-; -4/9) график функции выпуклый, на интервале                (-4/9; +) график функции вогнутый, х=-4/9 – точка перегиба.

ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАЧИ 4

Задача. Найти градиент функции в точке М(1; -3) и найти производную в той же точке по направлению MN, если N(0; -5).

Решение. а) Находим частные производные:  и их значения в точке М(1; -3):



б) Найдем единичный вектор l, имеющий данное направление:



откуда

Вычислим частные производные функции в точке М(1; -3):



Получаем,

ПРИМЕР ВЫПОЛНЕНИЯ ЗАДАЧИ 5

Задача. Исследовать функцию  на локальный экстремум.

Решение. Найдем частные производные функции z и приравняем их к нулю:



Её решением являются пары (0; 0) и , т.е. на экстремум надо проверить точки М0(0; 0) и М1. Частные производные второго порядка имеют вид:



Вычислим D в точках М0 и М1:

 значит экстремума в точке М0 нет;



Так как в точке М1 коэффициенты D>0 и A>0, то точка М1 является точкой минимума.
1   ...   4   5   6   7   8   9   10   11   12


8.6. Дискретная динамическая модель оптимального распределения ресурсов
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации