|
Курсовая: Линейное и динамическое программирование |
Находим новые потенциалы. Новые оценки:
D12= -2; D13= -4; D15= -1; D23= -2;
D24= -1; D25= -2; D31= -2; D32=0.
Поскольку все Dij£0 решение является оптимальным:
33 0 0 7
Xоpt1 = 15 30 0 0
0 0 29 33
Однако, так как оценка клетки D32=0, делаем вывод о наличие другого
возможного оптимального решения. Для его нахождения строим цикл пересчета
клетки 32: 32-22-21-11-14-34, производим перераспределение:
Таблица 3
Потребл Произв | b1=48 | b2=30 | b3=29 | b4=40 | b5=8 | | a1=40 | 33 | 6 | 4 | 373 | 0 | p1=0 | a2=45 | 45 2 | 3 | 1 | 3 | 0 | p2=-1 | a3=70 | 6 | 305 | 291 | 34 | 80 | 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(ξ-z2j), 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 | 53 | 70 | 90 | 106 | 120 | 133 | x2 | 0 | 0 | 100 | 100 | 100 | 200 | 300 | 300 |
Таблица 2
х3 | ξ-х2 | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | F3(ξ-x3) f3(x3) | 0 | 28 | 53 | 70 | 90 | 106 | 120 | 133 | 0 | 0 | 0 | 28 | 53 | 70 | 90 | 106 | 120 | 133 | 100 | 15 | 15 | 43 | 68 | 85 | 105 | 121 | 135 | | 200 | 25 | 25 | 53 | 78 | 95 | 115 | 131 | | | 300 | 40 | 40 | 68 | 93 | 110 | 130 | | | | 400 | 56 | 56 | 84 | 109 | 125 | | | | | 500 | 62 | 62 | 90 | 115 | | | | | | 600 | 73 | 73 | 101 | | | | | | | 700 | 82 | 82 | | | | | | | |
Жирным цветом обозначен максимальный суммарный эффект от выделения
соответствующего размера инвестиций по 3-м предприятиям.
ξ | 0 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | F2 | 0 | 28 | 53 | 70 | 90 | 106 | 121 | 135 | x2 | 0 | 0 | 0 | 0 | 0 | 0 | 100 | 100 |
Страницы: 1, 2, 3, 4
|
|
|
© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент. |
|
|