close

Вход

Забыли?

вход по аккаунту

?

Laba 4(5)

код для вставкиСкачать
 Белорусский государственный университет информатики и радиоэлектроники
Отчёт
по лабораторной работе №4
"Решение задач оптимизации на основе метода динамического программирования"
Выполнила:
Студент гр. 020601
Проверила:
Минск 2012
Постановка задачи и принцип работы метода динамического программирования
Метод динамического программирования предназначен для задач, решение которых может быть представлено как некоторая многошаговая операция, т.е. последовательность однотипных шагов. Решение на каждом шаге принимается с учетом результатов предыдущих шагов, а также с учетом последствий принимаемого решения для последующих шагов.
К числу задач, для которых может применяться метод динамического программирования, относится большинство задач планирования на несколько периодов времени (например, на несколько лет). Шагом в таких задачах является один плановый период (например, один год). Метод динамического программирования применяется также для многих задач, в которых имеется возможность искусственно представить процесс принятия как последовательность из нескольких однотипных шагов.
Общая постановка задачи, решаемой методом динамического программирования, следующая. Имеется некоторая операция, находящаяся в начальном состоянии S0. Операция реализуется за N шагов. На каждом шаге принимается некоторое решение Uk, где k - номер шага (k=1,...,N). Выбор каждого решения Uk вызывает переход операции из состояния Sk-1 в новое состояние Sk, а также обеспечивает некоторое значение критерия эффективности Zk. Требуется определить последовательность решений U1, U2, ...,Uk, обеспечивающих экстремальное (максимальное или минимальное) значение общего критерия эффективности E, зависящего от значений критерия эффективности на отдельных шагах Z1, Z2,...,Zk.
Основной принцип решения задач на основе метода динамического программирования (принцип оптимальности, или принцип Беллмана) состоит в следующем: решение на каждом шаге выбирается таким образом, чтобы обеспечить максимальную эффективность на данном шаге и на всех последующих шагах.
Задача, представленная в виде многошаговой операции, может быть решена методом динамического программирования, если она удовлетворяет следующим свойствам:
- отсутствие последействия: состояние операции по окончании каждого шага (Sk) и критерий эффективности на каждом шаге (Zk) зависят только от решения, принятого на данном шаге (Uk), и от состояния операции в начале данного шага (Sk-1), и не зависят от того, каким образом операция перешла в состояние Sk-1;
- аддитивность или мультипликативность критерия эффективности: общий критерий эффективности представляет собой сумму критериев эффективности на отдельных шагах (E = Z1+Z2+...+ZN) или их произведение (E = Z1·Z2·...·ZN ).
Решение задач динамического программирования обычно включает два цикла: сначала - от последнего шага к первому (обратная прогонка, или условная оптимизация), затем - от первого шага к последнему (прямая прогонка, или безусловная оптимизация).
В цикле условной оптимизации для каждого шага находится множество возможных состояний операции в начале данного шага. Для каждого из этих состояний находится условно оптимальное решение, т.е. решение, оптимальное для данного состояния. Поиск условно оптимальных решений начинается с последнего (N-го) шага, так как на этом шаге имеется возможность выбирать решение только с учетом эффективности на данном шаге (последующих шагов нет). Затем на других шагах (N-1-м, N-2-м,...,первом) условно оптимальные решения выбираются согласно принципу оптимальности, т.е. с учетом эффективности на данном шаге и на последующих шагах. На всех шагах от N-го до второго определяется несколько условно оптимальных решений - по одному для каждого возможного состояния. Для первого шага начальное состояние (S0) обычно известно точно, поэтому для этого шага находится только одно (безусловно оптимальное) решение . В цикле безусловной оптимизации для каждого шага находится безусловно оптимальное решение. Поиск безусловно оптимальных решений начинается с первого шага, так как для него известно начальное состояние S0, поэтому можно определить единственное (безусловно оптимальное) решение . Определяется состояние S1, в которое переходит операция из состояния S0 в результате решения , т.е. состояние в начале второго шага. Для него в цикле условной оптимизации уже найдено оптимальное решение . Определяется состояние операции в начале третьего шага - состояние S2, в которое операция переходит в результате решения . Для этого состояния в цикле условной оптимизации также найдено оптимальное решение . Аналогично определяются безусловно оптимальные решения для последующих шагов.
Важно отметить, что для метода динамического программирования не существует вычислительной процедуры, одинаковой для всех задач (в отличие, например, от симплекс-метода). Это означает, что правила вычислений, составления таблиц и т.д. полностью зависят от конкретной задачи. Общими являются лишь основные принципы решения: принцип оптимальности, решение задачи с использованием условной и безусловной оптимизации.
Условие задачи:
Требуется распределить между четырьмя предприятиями денежную сумму в размере 60 млн д.е. Средство могут выделяться в размерах, каратных 10 млн д.е. Для каждого предприятия известна прибыль, которую оно получит, если ему будет выделена конкретная сумма:
Таблица 1
Вложенные средства, млн. д.е.Предприятие12340
10
20
30
40
50
600
8
12
22
27
32
460
10
17
20
24
28
350
15
17
25
32
35
420
12
20
24
27
30
32 Требуется распределить средства между предприятиями таким образом, чтобы суммарная прибыль, полученная всеми предприятиями, была максимальной.
В задаче в качестве шагов будем рассматривать выделение средств предприятиям: первый шаг - выделение средств предприятию П1, второй - П2, и т.д. (всего 4 шага). Таким образом, распределение средств между предприятиями можно рассматривать как многошаговую операцию. В качестве состояния этой операции будем использовать величину имеющихся средств, которые требуется распределить. Начальное состояние S0=60. Решение на каждом шаге - это денежные средства, выделяемые предприятию (Uk, k=1,...,4). Критерий эффективности для каждого шага - прибыль, полученная предприятием (Zk, k=1,...,4). Общий критерий эффективности - это прибыль фирмы, т.е. сумма прибылей всех предприятий: E = Z1+Z2+Z3+Z4.
Задача удовлетворяет свойству отсутствия последействия. Состояние по окончании каждого шага (т.е. имеющаяся сумма средств, подлежащая распределению, Sk) зависит только от суммы, имевшейся в начале шага (Sk-1) и от решения, принятого на данном шаге (т.е. от выделенной на данном шаге денежной суммы Uk): Sk=Sk-1-Uk. Критерий эффективности на каждом шаге (т.е. прибыль предприятия Zk) зависит только от решения на данном шаге, т.е. от выделенной предприятию суммы Uk, и не зависит от того, сколько средств выделено другим предприятиям.
Задача удовлетворяет также свойству аддитивности критерия эффективности: общий критерий эффективности (прибыль фирмы) равен сумме критериев эффективности на отдельных шагах (прибылей предприятий).
Задача решается в два цикла.
I.Цикл условной оптимизации
Шаг 4 (выделение средств предприятию П4) Определяются все возможные состояния S3 к началу шага 4 (или к концу шага 3), т.е. все возможные значения остатка денежных средств после их выделения предприятиям П1, П2 и П3. Этот остаток может составлять 0 ден.ед. (если все средства выделяются предприятиям П1, П2 и П3), 10 млн ден.ед. (если предприятиям П1, П2, П3 выделяется 50 млн ден.ед.), 40 млн ден.ед. (если предприятиям П1, П2, П3 выделяется 20 млн ден.ед.), 30 млн ден.ед. (если предприятиям П1, П2, П3 выделяется 30 млн ден.ед.), 20 млн ден.ед. (если предприятиям П1, П2, П3 выделяется 40 млн ден.ед.), 10 млн ден.ед. (если предприятиям П1, П2, П3 выделяется 50 млн ден.ед.) или 60 млн ден.ед. (если предприятиям П1, П2, П3 средства вообще не выделяются). Для каждого из возможных состояний определяется условно оптимальное решение, т.е. решение, оптимальное при условии, что остаток денежных средств равен S3. Так как предприятие П4 - последнее (предполагается, что другим предприятиям средства уже выделены), оптимальное решение состоит в выделении предприятию П4 всех оставшихся средств.
Возможные состояния в начале четвертого шага S3, соответствующие им условно оптимальные решения и значения критерия эффективности (прибыль предприятия П4) (берётся из таблицы 1) приведены в табл.2. Таблица 2
S3U4*E4*0
10
20
30
40
50
600
10
20
30
40
50
600
12
20
24
27
30
32 По результатам четвертого шага не выяснено, сколько средств требуется выделять предприятию П4. Это пока невозможно, так как неизвестно начальное состояние четвертого шага S3. Поэтому найдены условно оптимальные решения для всех возможных состояний.
Шаг 3 (выделение средств предприятиям П3 и П4) Все расчеты для шага 3 приведены в табл.3. В таблице использованы следующие обозначения: S2 - возможные суммы денежных средств, распределяемые между предприятиями П3 и П4 (т.е. оставшиеся после выделения средств предприятиям П1 и П2); U3 - возможные варианты выделения средств предприятию П3; Z3 - прибыль предприятия П3 от выделения средств в размере U3; S3 - остаток денежных средств после их выделения предприятиям П1, П2 и П3 (т.е. средства, выделяемые предприятию П4); - прибыль предприятия П4 от выделенных ему средств в размере S3; E3 - суммарная прибыль предприятий П3 и П4 (сумма величин из столбцов Z3 и ); - условно оптимальное решение для состояния S2 (денежные средства, которые следует выделить предприятию П3 при наличии суммы S2); - условно оптимальный критерий эффективности для предприятий П3 и П4, т.е. прибыль, получаемая этими предприятиями в результате решения .
Таблица 3
S2U3Z3S3E4*E3U3*E3*00000000100
100
1510
012
012
151015200
10
200
15
1720
10
020
12
020
27
171027300
10
20
300
15
17
2530
20
10
024
20
12
024
35
29
251035400
10
20
30
400
15
17
25
3240
30
20
10
027
24
20
12
027
39
37
37
321039500
10
20
30
40
500
15
17
25
32
3550
40
30
20
10
030
27
24
20
12
030
42
41
45
44
353045600
10
20
30
40
50
600
15
17
25
32
35
4260
50
40
30
20
10
032
30
27
24
20
12
032
45
44
49
52
47
424052 Рассмотрим порядок решения для шага 3.
Определяются все возможные состояния S2 к началу шага 3 (или к концу шага 2), т.е. все возможные значения денежных средств, распределяемых между предприятиями П3 и П4. Этот остаток может составлять 0 ден.ед. (если все средства выделяются предприятиям П1 и П2), 10 млн ден.ед. (если предприятиям П1 и П2 выделено 50 млн ден.ед.), 20 млн ден.ед. (если предприятиям П1 и П2 выделено 40 млн ден.ед.), 30 млн ден.ед. (если предприятиям П1 и П2 выделено 30 млн ден.ед.), 40 млн ден.ед. (если предприятиям П1 и П2 выделено 20 млн ден.ед.), 50 млн ден.ед. (если предприятиям П1 и П2 выделено 10 млн ден.ед.) или 60 млн ден.ед. (если предприятиям П1 и П2 средства вообще не выделяются). Для каждого из возможных состояний определяется условно оптимальное решение, т.е. решение, оптимальное при условии, что остаток денежных средств равен S2. Средства для предприятия П3 должны выделяться таким образом, чтобы обеспечить максимальную суммарную прибыль предприятий П3 и П4.
Предположим, что денежные средства, распределяемые между предприятиями П3 и П4, составляют 20 млн ден.ед. (S2=20). Эти средства можно оставить для предприятия П4 (тогда предприятию П3 средства не выделяются, U3=0) или выделить только часть этих средств, т е 10 ден.ед., тогда на предприятие П4 остаётся 10 ден.ед., или выделить все средства предприятию П3 (U3=20). Если U3=0, то предприятие П3 не получит прибыли (Z3=0). В этом случае остаток средств (состояние) в конце третьего шага составит S3=20 млн ден.ед. Эти средства будут выделены предприятию П4, и его прибыль составит =20 млн ден.ед. Суммарная прибыль предприятий П3 и П4 составит E3=0+20=20 млн ден.ед. Если U3=10, то предприятие П3 получит прибыль Z3=15 млн ден.ед. Остаток средств (состояние) в конце третьего шага составит S3=10. Предприятию П4 будет выделено 10 млн ден.ед., и оно получит прибыль =12. Суммарная прибыль предприятий П3 и П4 составит E3=15+12=27 млн ден.ед. Если U3=20, то предприятие П3 получит прибыль Z3=17 млн ден.ед. Остаток средств (состояние) в конце третьего шага составит S3=0. Предприятию П4 не будет выделено средств и оно не получит прибыли (=0). Суммарная прибыль предприятий П3 и П4 составит E3=17+0=17 млн ден.ед. Таким образом, если между предприятиями П3 и П4 распределяется сумма в размере 20 млн ден.ед., то следует выделять предприятию П3 10 млн ден ед. и П4 также 10 млн ден. ед., так как общая прибыль в этом случае будет максимальной. Другими словами, для состояния S2=20 условно оптимальное решение =10, условно оптимальный критерий эффективности =27.
Аналогично можно определить, что при распределении между предприятиями П3 и П4 средств в размере 10 млн ден.ед. предприятию П3 следует выделить 10 млн ден.ед.( оптимальный критерий эффективности =15 млн ден.ед.); при распределении между предприятиями П3 и П4 средств в размере 30 млн ден.ед. предприятию П3 следует выделить 10 млн ден.ед.( оптимальный критерий эффективности =35 млн ден.ед.); при распределении между предприятиями П3 и П4 средств в размере 40 млн ден.ед. предприятию П3 следует выделить 10 млн ден.ед.( оптимальный критерий эффективности =39 млн ден.ед.); при распределении между предприятиями П3 и П4 средств в размере 50 млн ден.ед. предприятию П3 следует выделить 30 млн ден.ед.( оптимальный критерий эффективности =45 млн ден.ед.); при распределении между предприятиями П3 и П4 всех средств в размере (60 млн ден.ед.) предприятию П3 следует выделить 40 млн ден.ед.( оптимальный критерий эффективности =52 млн ден.ед.)
Шаг 2 (выделение средств предприятиям П2, П3 и П4) Все расчеты для шага 2 приведены в табл.4. Обозначения в таблице: S1 - возможные суммы денежных средств, распределяемые между предприятиями П2, П3 и П4 (т.е. оставшиеся после выделения средств предприятию П1); U2 - возможные варианты выделения средств предприятию П2; Z2 - прибыль предприятия П2 от выделения средств в размере U2; S2 - остаток денежных средств после их выделения предприятиям П1 и П2 (т.е. средства, выделяемые предприятиям П3 и П4); - максимальная суммарная прибыль предприятий П3 и П4 от выделенных им средств в размере S2 (определяется из табл.1); E2 - суммарная прибыль предприятий П2, П3 и П4 (сумма величин из столбцов Z2 и ); - условно оптимальное решение для состояния S1 (денежные средства, которые следует выделить предприятию П2 при наличии суммы S1); - условно оптимальный критерий эффективности для предприятий П2, П3 и П4, т.е. прибыль, получаемая этими предприятиями в результате решения .
Таблица 4
S1U2Z2S2E3*E2U2*E2*00000000100
100
1010
015
015
10015200
10
200
10
1720
10
027
15
027
25
17027300
10
20
300
10
17
2030
20
10
035
27
15
035
37
32
201037400
10
20
30
400
10
11
20
2440
30
20
10
039
35
27
15
039
45
44
35
241045500
10
20
30
40
500
10
17
20
24
2850
40
30
20
10
045
39
35
27
15
045
49
52
47
39
282052600
10
20
30
40
50
600
10
17
20
24
28
3560
50
40
30
20
10
052
45
39
35
27
15
052
55
56
55
51
43
352056 Шаг 1 (выделение средств предприятиям П1, П2, П3 и П4) Все расчеты для шага 1 приведены в табл.5. Обозначения в таблице: S0 - начальная сумма денежных средств, распределяемых между всеми предприятиями; U1 - возможные варианты выделения средств предприятию П1; Z1 - прибыль предприятия П1 от выделения средств в размере U1; S1 - остаток денежных средств после их выделения предприятию П1 (т.е. средства, выделяемые предприятиям П2, П3 и П4); - максимальная суммарная прибыль предприятий П2, П3 и П4 от выделенных им средств в размере S1 (определяется из табл.7.4); E1 - суммарная прибыль предприятий П1, П2, П3 и П4, т.е всех предприятий (сумма величин из столбцов Z2 и ); - безусловно оптимальное решение для состояния S0 (денежные средства, которые следует выделить предприятию П1 при наличии суммы S0); - условно оптимальный критерий эффективности для предприятий П1, П2, П3 и П4, т.е. прибыль, получаемая всеми предприятиями в результате решения .
Таблица 5
S0U1Z1S1E2*E1U1*E1*600
10
20
30
40
50
600
8
12
22
27
32
4660
50
40
30
20
10
056
52
45
37
27
15
056
60
57
59
54
47
461060 II.Цикл безусловной оптимизации
В цикле безусловной оптимизации для каждого шага находится безусловно оптимальное решение. Поиск безусловно оптимальных решений начинается с первого шага, так как для него известно начальное состояние S0, поэтому можно определить единственное (безусловно оптимальное) решение U1*.
Для первого шага (выделение средств предприятию П1) получено безусловно оптимальное решение: =10 млн ден.ед.. Для предприятий П2, П3 и П4 остается 50 млн ден.ед. Таким образом, состояние в начале второго шага S1=50. Из таблицы 4 для этого состояния определяется оптимальное решение: =20 (предприятию П2 выделяется 20 млн ден.ед.). Для предприятий П3 и П4 остается 30 млн ден.ед. (состояние в начале третьего второго шага S2=30). Из таблицы 3 для этого состояния определяется оптимальное решение: =10 млн ден.ед. (предприятию П3 выделяется 10 млн ден.ед.). Для предприятия П4 остается 20 млн ден.ед. (S3=20). Поэтому =20.
Выводы:
Оптимальное решение задачи следующее. Предприятию П1 следует выделить 10 млн ден.ед, предприятию П2 - 20 млн ден.ед., предприятию П3 - 10 млн ден.ед, предприятию П4 - выделить 20 млн ден.ед. Общая прибыль составит 60 млн ден.ед., в том числе прибыль предприятия П1 - 8 млн ден.ед., П2 - 17 млн ден.ед., П3 - 15 млн ден.ед., П4 - 20 млн ден.ед.
Документ
Категория
Рефераты
Просмотров
20
Размер файла
170 Кб
Теги
laba
1/--страниц
Пожаловаться на содержимое документа