Реферат: Линейное и динамическое программирование
Таблица 3
|
Произв | b1 =48 | b2 =30 | b3 =29 | b4 =40 | b5 =8 | |
a1 =40 | 3 3 | 6 | 4 | 37 3 | 0 | p1 =0 |
| a2 =45 | 45 2 | 3 | 1 | 3 | 0 | p2 =-1 |
| a3 =70 |
6 | 30 5 | 29 1 | 3 4 | 8 0 | p3 =1 |
| q1 =3 | q2 =4 | q3 =0 | q4 =3 | q5 = -1 |
ПотреблНаходим новые потенциалы. Получаем рi и qj соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого Dmax =D32 , однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение:
3 0 0 37
Xо pt2 = 45 0 0 0
0 30 29 3
Оптимальное распределение инвестиций
Данная задача с n переменными представляется, как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только по одной переменной.
Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере ξ (сотен тыс. рублей) выражается функцией fi (xi ). Приходим к задаче fl (xl )+f2 (x2 )+f3 (x3 )+f4 (x4 )-max , где xi - пока еще неизвестный размер х1 +х2 +х3 +х4 ≤7; х1 ,х2 ,х3 .х4 ≥0 инвестиций i-й фирме. Эта задача решается методом динамического программирования: последовательно ищется оптимальное распределение для k=2,3 и 4 фирм.
Пусть первым двум фирмам выделено ξ инвестиций. обозначим z2 (ξ) величину инвестиций 2-й фирме, при которой сумма f2 (z2 j )+fl (ξ-z2 j ), 0≤j≤ ξ максимальна, саму эту максимальную величину обозначим F2 (ξ). Далее действуем также: находим функции z3 и F3 и т.д. На k-ом шаге для нахождения Fk (ξ) используем основное рекуррентное соотношение: Fk (ξ)=max{fkj (хk )+F( k -1) ( ξ-хk ); 0 ≤ хk ≤ ξ
| xj | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
| f1 | 0 | 28 | 45 | 65 | 78 | 90 | 102 | 113 |
| f2 | 0 | 25 | 41 | 55 | 65 | 75 | 80 | 85 |
| f3 | 0 | 15 | 25 | 40 | 56 | 62 | 73 | 82 |
| f4 | 0 | 20 | 33 | 42 | 48 | 53 | 56 | 58 |
Таблица 1
|
x2 | ξ-х2 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
|
F1 (ξ-x2 ) f2 (x2 ) | 0 | 28 | 45 | 65 | 78 | 90 | 102 | 113 | |
| 0 | 0 | 0 | 28 | 45 | 65 | 78 | 90 | 102 | 113 |
| 100 | 25 | 25 | 53 | 70 | 90 | 103 | 115 | 127 | |
| 200 | 41 | 41 | 69 | 86 | 106 | 119 | 131 | ||
| 300 | 55 | 55 | 83 | 100 | 120 | 133 | |||
| 400 | 65 | 65 | 93 | 110 | 130 | ||||
| 500 | 75 | 75 | 103 | 120 | |||||
| 600 | 80 | 80 | 108 | ||||||
| 700 | 85 | 85 |
Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 2-м предприятиям.
| ξ | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 |
| F2 | 0 | 28 |