 |
|
Линейное и динамическое программирование
производственная программа. Найдем h'=Q-1 b' 5/28 0 -1/7 219 30 (x3 -4/7 1 -1/7 96 = 0 (x6 -3/28 0 2/7 228 33 (x1 Теперь новая производственная программа имеет вид: X'оpt=(33;0;30;0). При этом второй ресурс был использован полностью. 219 При наличии ресурсов b' = 96 производство наиболее выгодно, так как 228 достигается max прибыль с использованием всех ресурсов. Также обратим внимание на то, что производство продукции 1–го вида при заказе дополнительных ресурсов необходимо будет уменьшить на 15 единиц, а производство продукции 3–го вида – увеличить на единицу. ?Lmax=(Y,t)=6?21=126, где Y=(6;0;5); t(21;0;0) L'max= ?Lmax+ Lmax=126+2328=2454. Этот результат можно проверить, подставив значения х1 и х3 в первоначальную целевую функцию: L'max=48xl+30x2+29x3+10x4=31?37+41?21=1147+861=2454. Транспортная задача Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в т пунктах производства (хранения) в количествах a1, а2,..., аm единиц, необходимо распределить между п пунктами потребления, которым необходимо соответственно b1, b2,,…, bn единиц. Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт назначения равна cij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными. Обозначим через xij количество груза, планируемого к перевозке от i-ro поставщика j-му потребителю. При наличии баланса производства и потребления [pic] математическая модель транспортной задачи будет выглядеть так: найти план перевозок X=(xij), xij(0, i(Nm, j(Nn минимизирующий общую стоимость всех перевозок [pic] при условии, что из любого пункта производства вывозится весь продукт [pic] , i(Nm и любому потребителю доставляется необходимое количество груза [pic] , j(Nn Для решения транспортной задачи чаще всего применяется метод потенциалов. Пусть исходные данные задачи имеют вид А(а1,а2,а3)=(40;45;70); В(b1,b2,b3)=(48;30;29;40); 3 6 4 3 С= 2 3 1 3 6 5 1 4 Общий объем производства (ai=40+45+70=155 больше, чем требуется всем потребителям (bj=48+30+29+40=147, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 155-147=8 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами. Первое базисное допустимое решение легко построить по правилу "северо- западного угла". Таблица 1 | |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | | |Потребл | | | | | | | |Произв | | | | | | | |a1=40 |40 |6 | |* | |p1=0 | | |3 | |4 |3 |0 | | |a2=45 |8 2|30 |7 1| | |p2=-1 | | | |3 | |3 |0 | | |a3=70 | | |22 |40 |8 0|p3=-1 | | |6 |5 |1 |4 | | | | |q1=3 |q2=4 |q3=2 |q4=5 |q5=1 | | Обозначим через ((p1, p2,…, pm, q1, q2,…, qn) вектор симплексных множителей или потенциалов. Тогда (ij=(Aij-cij , i(Nm, j(Nn, откуда следует (ij=pi+qj-cij , i(Nm, j(Nn Положим, что p1=0. Остальные потенциалы находим из условия, что для базисных клеток (ij=0. В данном случае получаем (11=0, p1+q1-c11=0, 0+q1-3=0, q1=3 (21=0, p2+q1-c21=0, p2+3-2=0, p2= -1 (23=0, p2+q3-c23=0, -1+q3-1=0, q3=2 аналогично, получим: q2=4, р3=-1, q4=5, q5=1. Затем вычисляем оценки всех свободных клеток: (12=p1+q2-c12=0+4-6= -2 (13=p1+q3-c13=0+2-4=-2 (14=2; (15=1; (24=1; (25=0; (31= -4; (32= -2 Находим наибольшую положительную оценку: mах((ij >0)=2=(14, Для найденной свободной клетки 14 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33- 23-21-11. Производим перераспределение поставок вдоль цикла пересчета: |40 | | |* | |40-( | | |( | |33 | | |7 | |8 |30 |7 | |( |8+( | |7-( | |( |15 |30 | | | | | |22 |40 | | | |22+( |40-( | | | |29 |33 | (max=7 Получаем второе базисное допустимое решение: Таблица 2 | |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | | |Потребл | | | | | | | |Произв | | | | | | | |a1=40 |33 |6 | |7 | |p1=0 | | |3 | |4 |3 |0 | | |a2=45 |15 |30 |1 | | |p2=-1 | | |2 |3 | |3 |0 | | |a3=70 | |* |29 |33 |8 0|p3=1 | | |6 |5 |1 |4 | | | | |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| | Находим новые потенциалы. Новые оценки: (12= -2; (13= -4; (15= -1; (23= -2; (24= -1; (25= -2; (31= -2; (32=0. Поскольку все (ij(0 решение является оптимальным: 33 0 0 7 Xоpt1 = 15 30 0 0 0 0 29 33 Однако, так как оценка клетки (32=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение: Таблица 3 | |b1=48 |b2=30 |b3=29 |b4=40 |b5=8 | | |Потребл | | | | | | | |Произв | | | | | | | |a1=40 |3 3|6 | |37 | |p1=0 | | | | |4 |3 |0 | | |a2=45 |45 |3 |1 | | |p2=-1 | | |2 | | |3 |0 | | |a3=70 | |30 |29 |3 4|8 0|p3=1 | | |6 |5 |1 | | | | | |q1=3 |q2=4 |q3=0 |q4=3 |q5= -1| | Находим новые потенциалы. Получаем рi и qj соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого (max=(32, однако элемент с индексом 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(z2j)+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 | |?-х2 |0 |100 |200 |300 |400 |500 |600 |700 | | | | | | | | | | | | |x2 | | | | | | | | | | | | |0 |28 |45 |65 |78 |90 |102 |113 | | |F1(?-x2)| | | | | | | | | | | | | | | | | | | | | |f2(x2) | | | | | | | | | |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 | |?-х2 |0 |100 |200 |300 |400 |500 |600 |700 | | | | | | | | | | | | |х3 | | | | | | | | | | | | |0 |28 |53 |70 |90 |106 |120 |133 | | |F3(?-x3)| | | | | | | | | | | | | | | | | | | | | |f3(x3) | | | | | | | | | |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 | Таблица 3 | |?-х4 |0 |100 |200 |300 |400 |500 |600 |700 | | | | | | | | | | | | |x4 | | | | | | | | | | | | |0 |28 |53 |70 |90 |106 |121 |135 | | |F4(?-x4)| | | | | | | | | | | | | | | | | | | | | |f4(x4) | | | | | | | | | |0 |0 | | | | | | | |135 | |100 |20 | | | | | | |141 | | |200 |33 | | | | | |139 | | | |300 |42 | | | | |132 | | | | |400 |48 | | | |118 | | | | | |500 |53 | | |106 | | | | | | |600 |56 | |84 | | | | | | | |700 |58 |58 | | | | | | | | Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 4-м предприятиям. Сведем результаты в 4 таблицы. Теперь F4(7)=141 показывает максимальный суммарный эффект по всем 4-м фирмам, a z4(7)=100 тыс. руб. - размер инвестиций в 4-ю фирму для достижения этого максимального эффекта. На долю остальных трех предприятий остается 600 тыс. руб. Третьему предприятию должно быть выделено х*3=Х3(700-х*4)=Х3(600)=100 тыс. руб. Продолжая обратный процесс, находим х*2=Х2(700-х*4-х*3)=Х2(500)=200 тыс. руб. На долю первого предприятия остается х*1=700-х*4-х*3-х*2=300 тыс. руб. Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям: х*1 =300; х*2 =200; х*3 = 100; х*4 = 100. Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 141 тыс. руб. Анализ доходности и риска финансовых операций Финансовой называется операция, начальное и конечное состояния которой имеют денежную оценку и цель проведения которой заключается в максимизации дохода - разности между конечной и начальной оценками. Почти всегда финансовые операции проводятся в условиях не
| |  скачать работу |
Линейное и динамическое программирование |
|
|
|
Погода в Алматы |
на 10 дней |
другой город |
|
