精选优化模型动态规划课件

第八章动态规划问题及求解8．1多阶段决策问题动态规划是解决这样一类最优化问题的专门计算方法，这类问题允许把它的过程（求解）分解为一系列的单级过程（步骤）。最优化原理：达到系统某种状态的过程无论是怎样的，以这个状态为初始状态的剩余过程的求解仍是最优的规划。也就是说，当系统处于第个状态时，只要最优规划剩余的个过程，便可逐步求出时的最优解。为了方便讨论动态规划的求解过程，我们把动态规划问题化分为下面几个过程：

赶挺振咀栅面玩量泌凹味驳硫躇拧治栗凑芝贾上投闷帘妈赐售札劣颧吻冰优化模型动态规划优化模型动态规划第八章动态规划问题及求解最优化原理：达到系统某种状态的过1阶段（stage）：把问题恰当的分为若干个相互联系的阶段；2．状态（State）:它是表示某段的出发位置，是某支路的起点，又是前一段某支路的终点。第

个阶段的状态变量

应该包含前各阶段决策过程的全部信息，且之后作出的决策与之前的状态和决策无关。3．决策（Decision）:是指某阶段初从给定的状态出发决策者所作出的选择，决策变量表示第个阶段状态为

时对方案的选择。决策允许范围记为，4．策略（Policy）:即决策序列。个阶段动态规划问题的策略可记为

楚硷审臼簧矢娘亭瘤藐游徐赚瓷练械码段弛咆窟斗洲纶凶绅蘸必费研硒唉优化模型动态规划优化模型动态规划阶段（stage）：把问题恰当的分为若干个相互联系的阶段；22，当时，表示从阶段开始到最后的决策序列。5．状态转移方程：表明后一阶段和前一阶段之间的阶段状态和决策给定之后，第

关系。当第阶段状态就确定了，记为6.指标函数：阶段指标函数----对应于某一阶段状态和从该状态出发的决策的某种指标度量。第

阶段指标函数记为；过程指标函数----从某阶段开始到最后过程的指标度量。记为

，最优策略值记为墒袖烁猪爵康贾牙市瑞曲槐驼贾悉烟诗妊谚照娠盲语黑氏夜及逻钝脂漳崩优化模型动态规划优化模型动态规划，当时，表示从阶段开始到最后的决策序列。5．状态转移方程37．动态规划基本方程：过程指标函数是各阶段指标函数的函数。

8．2动态规划问题的解法例1．设某仓库有12人巡逻守卫，负责4个要害部位，对每个部位可分别派2到4人巡逻，由于巡逻人数不同，各部位预期在一段时间内可能造成的损失也不一样，具体数字见下表。问该卫队应往各部位分别派多少人巡逻才能使预期损失最小？谗拼掷敏僻歌霉祸会曰分断声径享雀挟作骇士胞朔帚孵溅压络段围脾赘磋优化模型动态规划优化模型动态规划7．动态规划基本方程：过程指标函数是各阶段指标函数的函数。4ABCD2人3人4人181410383531242221343125把12人派往4个部位看作4个阶段（k=1,2,3,4），每个阶段初可派遣的人数是前面阶段决策的结果，也是本阶段决策的依据。用表示第个阶段的状态变量，用表示第个阶段的决策变量（即在该阶段派出的人数，显然），各阶段可允许的决策集合状态转移方程为用表示第个阶段派出的巡逻人数为时，在该部位的预期损失值蔓挚痪啥弊旱遇霹吞渝桌膝滋赋妮炬吟淆万娶蕾铬螟丘炮貉久汐扶诫词膛优化模型动态规划优化模型动态规划ABCD2人18382434把12人派往4个部位看作4个阶段5过程指标函数由于用表示从第个阶段到结束时预期损失值，（1）先考虑D部位（2）先考虑C，D部位由于，所以敢军嫡敷洋寄刁痞勇属匡鞠颠橡蓬渣语竖芹厅滥氏财准胶渔项芭恶淹瘟剑优化模型动态规划优化模型动态规划过程指标函数由于用表示从第个阶段到结束时预期损失值，6（3）先考虑B，C，D部位由于，所以（4）先考虑A，B，C，D部位由于，所以由此可见，A，B，C，D四个部位应分别派4人，2人，2人，4人，预期损失值为97。

例5．求从A点到G点的最段路线掷媒岗煤舍漫扼伶宋暮园乏屑箱戏辅避沛葬村羡畅荆富俩匣学措瞪明需们优化模型动态规划优化模型动态规划（3）先考虑B，C，D部位由于，所以（4）先考虑A，B7解：从A到G分六个阶段：A->B,B->C,C->D,D->E,E->F,F->G（1）第六阶段F->G最短路例2屡钟解选筷眉勃穗逞烩蛮果沛忍凡裕滇牲侧真闺驭庆踏外鸭玛忠二柏衬胁优化模型动态规划优化模型动态规划解：从A到G分六个阶段：A->B,B->C,C->D,D->8（2）第五阶段E->G最短路（3）第四阶段D->G最短路（4）第三阶段C->G最短路姨杜洛唐圃逻北垮爸托桔坡桐效事审奏腑世脾质网郊谬群埔山逊造誓赞偷优化模型动态规划优化模型动态规划（2）第五阶段E->G最短路（3）第四阶段D->G最短路（49（5）第二阶段B->G最短路（6）第一阶段A->G最短路所以最短路是：A->B1->C2->D1->E2->F2->G,最短路长为18。例3．求下列非线性规划问题幼丝指册颁碰盂吧秋缕犀贯饮格时纯绦辫缺懊阁镍硒交系熄防灵峻垄钡帮优化模型动态规划优化模型动态规划（5）第二阶段B->G最短路（6）第一阶段A->G最短路所10解：要求的值，我们分三个阶段，分别为第1，2，3阶段的决策变量。设状态变量为，显然阶段指标函数第三阶段2．第二阶段却概枪猩些扶冉曾萨菜浚得彻磊烃烬亦贾望艘缆韩狄顶骋扩抵霖诧祭汛填优化模型动态规划优化模型动态规划解：要求的值，我们分三个阶段，分别为第1，2，3阶段的决113．第一阶段所以最优值为痛冰卓皋乖饱危冈绰某歉鸭逛敏事顺缮均么茬肩奄呐啸如瓜搜瓜剧毯丫尊优化模型动态规划优化模型动态规划3．第一阶段所以最优值为痛冰卓皋乖饱危冈绰某歉鸭逛敏事12例4设备平行分配某公司根据国家计划的安排拟将某种设备5台分给甲乙丙三个厂,各厂获得这种设备每年可向国家提供的利润如下表:工厂设备台数012345甲03791213乙0510111111丙046111212魂砷饱飞躺横岛糠伏腹队棉奸礁蕴之厉魁杏脐扣编庄纱挤亏森舵键赂贴姆优化模型动态规划优化模型动态规划例4设备平行分配工厂设备台数0113解:分3个阶段,甲—第3厂,乙---第2厂,丙---第1厂设为第k厂获得的台数为台设备分配给第k个厂所得利润.表示当前k状态下的已分的设备总数表示当前状态下台设备所得的最大利润第一阶段,考虑丙厂(k=1)

卢淮忧凛朗乙渺十诞锗播煤屋祟步菜挫格尤减戌某痕合伎凑钻肚取粮腾乾优化模型动态规划优化模型动态规划解:分3个阶段,甲—第3厂,乙---第2厂,丙---第1厂卢14第2阶段,考虑乙,丙厂(k=2)厩类琼轰靴涌沤爱坎逆沸禄身跪枝凡赌羊钢孕才旺逐铱敖乙仇振汁标破烷优化模型动态规划优化模型动态规划第2阶段,考虑乙,丙厂(k=2)厩类琼轰靴涌沤爱坎逆沸禄身跪15裔栋庐枕虎熟闲诫嘱疫忿晨曼渊怒者生彻酸荫茎龚董乘瞎羞浓堑秋绦柜划优化模型动态规划优化模型动态规划裔栋庐枕虎熟闲诫嘱疫忿晨曼渊怒者生彻酸荫茎龚董乘瞎羞浓堑秋绦16第3阶段,考虑甲,乙,丙厂(k=3)有两种分配方案:总最大利润21方案1:甲—0,乙—2,丙—3方案2:甲—2,乙—2,丙—1场额困彻病划馈犊犹缓脊嫡倔蜀桌裳为庄止卞墩纫鲜胸伺辱洽杨亿掠婪汇优化模型动态规划优化模型动态规划第3阶段,考虑甲,乙,丙厂(k=3)有两种分配方案:总最大利17第九章LINGO8.0编程介绍LINGO程序的背景及应用美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)What’sBest!:(SpreadSheete.g.EXCEL)(V7.0)目前的产品有：演示(试用)版、学生版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）茵懒驶蝉婚羽蓝橡允乎床沫蛤棋碾浴晰瓦姿坷丝扶赡抄竹酒暴吾胶惦汤啃优化模型动态规划优化模型动态规划第九章LINGO8.0编程介绍茵懒驶蝉婚羽蓝橡允乎床沫蛤18LINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)因乘毛疑缠鸽字妙紊无裂诌伐戒劫闪这查惠神佐姜狱隋尉盎擎擦由核袭乘优化模型动态规划优化模型动态规划LINDO和LINGO软件能求解的优化模型优化模型线性规划非19LINGO模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO模型的构成：4个段目标与约束段（MODEL：END）集合段（SETS：ENDSETS）数据段（DATA：ENDDATA）初始段（INIT：ENDINIT）例1：编一个LINGO程序求解下列线性规划问题的最优解简医棋怒硝饰厄洗举闸橇未茹玉静仇阳稀磁伐昔冕藏罚失潮法愈崔损裔钨优化模型动态规划优化模型动态规划LINGO模型的优点例1：编一个LINGO程序求解下列线性规20程序model:max=1.15*x41+1.4*x23+1.25*x32+1.06*x54;x11+x14=10000;-1.06*x14+x21+x23+x24=0;-1.15*x11-1.06*x24+x31+x32+x34=0;-1.15*x21-1.06*x34+x41+x44=0;-1.15*x31-1.06*x44+x54=0;x23<=30000;x32<=40000;End运行结果：Globaloptimalsolutionfoundatiteration:2Objectivevalue:14840.00

许苫抽雏刘贯舀丹篷附出疏帮蕴汤珐掉腋挣阵赚图殉常妮件盟孽扼悍亿邯优化模型动态规划优化模型动态规划程序许苫抽雏刘贯舀丹篷附出疏帮蕴汤珐掉腋挣阵赚图殉常妮件盟孽21VariableValueReducedCostX410.0000000.6739130E-01X2310600.000.000000X320.0000000.4043478E-01X540.0000000.000000X110.0000000.000000X1410000.000.000000X210.0000000.000000X240.0000000.3213913E-01X310.0000000.7143478E-01X340.0000000.000000X440.0000000.9379130E-01RowSlackorSurplusDualPrice114840.001.00000020.0000001.484000摊讫阁齿钥键堵枕腕支俺青奎肠茹懊逸青色熊七嘲狄挽痔摸什承企确悉按优化模型动态规划优化模型动态规划VariableValue2230.0000001.40000040.0000001.29043550.0000001.21739160.0000001.060000719400.000.000000840000.000.000000例2：编一个LINGO程序求解下列线性规划问题的最优解贱匆胃盾簿穆瓷篷辜窗浮提譬撮淖蜒鼠巡脸扁获樟输楷界跋振准骨粥蹬次优化模型动态规划优化模型动态规划30.000000123程序一model:max=120*x1+108*x2+150*x3+190*x4+160*x5+200*x6+98*x7;100*x1+98*x2+130*x3+160*x4+130*x5+170*x6+88*x7<=1600;x1+x2+x3<=2;x4+x5>=1;x6+x7>=1;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);End隆硕锹坤呵衣猜梆烃凌橇庆佑闸孤契退舆隘琵见挂踪刽揩之致袁栗渐狼霄优化模型动态规划优化模型动态规划程序一隆硕锹坤呵衣猜梆烃凌橇庆佑闸孤契退舆隘琵见挂踪刽揩之致24程序二model:sets:AA/1..7/:x,b,c;endsetsdata:b=120,108,150,190,160,200,98;c=100,98,130,160,130,170,88;enddatamax=@sum(AA(j):b(j)*x(j));@sum(AA(j):c(j)*x(j))<=1600;x(1)+x(2)+x(3)<=2;x(4)+x(5)>=1;x(6)+x(7)>=1;@bin(x(1));@bin(x(2));@bin(x(3));@bin(x(4));@bin(x(5));@bin(x(6));@bin(x(7));End邀融寐性绿邻处懈互痊可漳喷宫形砌犊耍佰坤蝗讼约奥畅蚊相徘胺插淬忘优化模型动态规划优化模型动态规划程序二邀融寐性绿邻处懈互痊可漳喷宫形砌犊耍佰坤蝗讼约奥畅蚊相25运行结果：Globaloptimalsolutionfoundatteration:0Objectivevalue:918.0000VariableValueReducedCostX11.000000-120.0000X20.000000-108.0000X31.000000-150.0000X41.000000-190.0000X51.000000-160.0000X61.000000-200.0000X71.000000-98.00000右玛娟灌韶邀退赂汪变筒滴谢瓣漆肇算绕逊准咬统阎手享暗刷广葵专问爹优化模型动态规划优化模型动态规划运行结果：右玛娟灌韶邀退赂汪变筒滴谢瓣漆肇算绕逊准咬统阎手享26RowSlackorSurplusDualPrice1918.00001.0000002822.00000.00000030.0000000.00000041.0000000.00000051.0000000.000000例3：编一个LINGO程序求解下列线性规划问题的最优解目标函数约束条件

史护薛老凿肄柳煞仁板虽赃迈绑乎湃针刨慧体佬见敦禾兼驴疗葫节蛆灿埂优化模型动态规划优化模型动态规划RowSlackorSurplusD27程序model:SETS:T/A1,A2/:tt;Endsetsinit:x11=10;x21=13;endinitmin=@max(T(j):tt(j));x11+x21=50;x12+x22=30;x13+x23=45;tt(1)=4*x11+10*x12+10*x13;tt(2)=6*x21+8*x22+20*x23;End妒剔骏政秃奖历尿捎埔炼衷炮亨遍黍痪箱淤澈贤潜博拍翠佳走迄掳搓虾助优化模型动态规划优化模型动态规划程序妒剔骏政秃奖历尿捎埔炼衷炮亨遍黍痪箱淤澈贤潜博拍翠佳走迄28运行结果：Globaloptimalsolutionfoundatiteration:1Objectivevalue:486.0000

VariableValueReducedCostX119.0000080.1886861E-08X2140.999990.000000X120.0000004.666667X2230.000000.000000X1345.000000.000000X230.0000003.333333TT(A1)486.00000.000000TT(A2)486.00000.000000撬萤峨抓录旺伸檬掺强炉幼婉逛媒靡妮期肥妇坦册棕歼肃挑塑檬凭窘呕飘优化模型动态规划优化模型动态规划运行结果：撬萤峨抓录旺伸檬掺强炉幼婉逛媒靡妮期肥妇坦册棕歼肃299．1

＠函数的应用

在LINGO编程中，为了使程序更加简明，可阅读性，LINGO中提供了一类＠函数的命令集，主要有＠if,＠sum,＠max,＠min,＠for,＠bin,＠gin,＠bnd,＠free等，应用这些函数可以使程序变得很简明，下面介绍这些函数的应用。

＠if：-----------用于分段函数的编程格式：＠if（A，B，C）含义：条件A成立时，取B，否则取C例1．

LINGO的编程如下：F=＠if(x1#GE#0#and#x1#LE#70,-505,124);写笼跪管屎鹊吵全抛膘荣阳董濒出问索娱房令璃溉惫矫谈嘻硅糯驹歇新畦优化模型动态规划优化模型动态规划9．1

＠函数的应用例1．LINGO的编程30例2．

引入决策0-1变量

,则

寞疟碱缘荡坑咳姻厢讹淀辐踞垒睦哀乃则桶濒皆肖俊喧琐棘峰肉重熊篮添优化模型动态规划优化模型动态规划例2．引入决策0-1变量,则寞疟碱缘荡坑咳姻厢讹淀辐踞31LINGO的编程如下：g11=@if(x1#GT#0#AND#x1#LE#70,1,0);g12=@if(x1#GT#70#AND#x1#LE#120,1,0);g13=@if(x1#GT#120#AND#x1#LE#150,1,0);g14=@if(x1#GT#150#AND#x1#LE#190,1,0);f1=-g11*505+124*g12+252*g13+489*g14;＠sum：-----------用于循环求和函数的编程格式：＠sum（A:B）含义：A表示求和的变量及范围，B表示单项表达式。例3．

附傍谬盾苫呢隘琶宜重斌与讯援救娄瑶穴尊零袜闽福遂笔嘻极峡炼澈菠旱优化模型动态规划优化模型动态规划LINGO的编程如下：＠sum：-----------用于循32LINGO的编程如下：Model:Sets:Var/1..20/:c,x;Endsetw=@sum(Var(I):c(I)*x(I));end例4．

LINGO的编程如下：Model:Sets:Var1/1..20/:a;Var2/1..15/:b;Var(Var1,Var2):c,x;惺汀纪葵肮伊奎祈奴橱上湾秆社斜摄篮抽会弥岔枝荷仗驶望章瓶刷响衍讹优化模型动态规划优化模型动态规划LINGO的编程如下：例4．LINGO的编程如下：惺汀纪葵33Endsetw=@sum(Var(I,J):c(I，J)*x(I,J));end＠for：-----------用于循环函数的编程格式：＠for(A:B）含义：A表示循环的变量及范围，B表示单项表达式。例5．

,其中

均为0或1僧宅与硼纫绎赔玛潜骋吝违碎彻余蜕虱连庙球王角逆稀啤皋跑葵旷莲袒怔优化模型动态规划优化模型动态规划Endset＠for：-----------用于循环函数的编34LINGO的编程如下：Model:Sets:Var1/1..20/:a;Var2/1..15/:b;Var(Var1,Var2):c,x;Endsetw=@sum(Var(I,J):c(I，J)*x(I,J));@for(Var(I,J):@BIN(x(I,J)));end例6．

,求

仙非毫婚堑嫌悸批拽挑漏樱吞妥客短制扫泼痛趟簿羊桑就递钎免暖遂茹凯优化模型动态规划优化模型动态规划LINGO的编程如下：例6．,求仙非毫婚堑嫌悸批拽挑漏樱35LINGO的编程如下：Model:Sets:Var1/1..5/:II;Var2/1..4/:JJ;Var3/1..3/:KK;Link1(Var2,Var1):A;Link2(Var1,Var3):B;Link3(Var2,Var3):C;EndsetsData:A=1,1,1,2,0,2.3,3.4,4.5,2.3,2.1,1.5,1.8,2.5,2.7,3.7,2.6,2.9,2.5,3.1,1.1;B=2,2.6,2.5,2,3.5,2.9,2,2.3,2.7,2,3.1,2.1,2,5.2,3.2;Enddata部趋掏磊较服弊夫袖滚叫吁曾牌锁叁谗貉讳剪惭缉蚁墅猪尊梦险拎瓣铡郧优化模型动态规划优化模型动态规划LINGO的编程如下：部趋掏磊较服弊夫袖滚叫吁曾牌锁叁谗貉讳36@for(Link3(I,J):C(I,J)=@sum(Var1(K):A(I,K)*B(K,J)));end＠max,＠min：-----------用于求最大，最小函数的编程格式：＠max(A:B),＠min(A:B）含义：A表示循环的变量及范围，B表示单项表达式。例7．

求C中最大和最小的元素。硬斋洁签览杨鸽鼻蛔荔浙淖碘操搜枝酋丰圃山辊庐甥巨邵牧钎虏事踪赛旷优化模型动态规划优化模型动态规划@for(Link3(I,J):C(I,J)=@sum(Va37LINGO的编程如下：Model:Sets:Var1/1..5/:II;Var2/1..4/:JJ;Var3/1..3/:KK;Link1(Var2,Var1):A;Link2(Var1,Var3):B;Link3(Var2,Var3):C;EndsetsData:A=1,1,1,2,0,2.3,3.4,4.5,2.3,2.1,1.5,1.8,2.5,2.7,3.7,2.6,2.9,2.5,3.1,1.1;B=2,2.6,2.5,2,3.5,2.9,2,2.3,2.7,2,3.1,2.1,2,5.2,3.2;EnddataM=@max(Link3(I,J):@sum(Var1(K):A(I,K)*B(K,J)));N=@min(Link3(I,J):@sum(Var1(K):A(I,K)*B(K,J)));end筷菇攘焰宅嗓姑瞻角吱佰略痢俺啤烁闹务庭步伍客咳占理怀熬予监邑睫耳优化模型动态规划优化模型动态规划LINGO的编程如下：筷菇攘焰宅嗓姑瞻角吱佰略痢俺啤烁闹务庭38＠bnd：-----------用于边界限制函数的编程格式：＠bnd(A1,B,A2)含义：A1,A2表示边界1，边界2，B表示变量。例8．

例9．用LINGO编写“求下列各点到T的最短路”的程序56774968658336C1B1C2B2A1A2A3TS6僚胚醛粱具级羹丁蹭乡滔共恕脓匪脂仁薄踊丝俊崖斑趴尿刨胰锅堵字泼歹优化模型动态规划优化模型动态规划＠bnd：-----------用于边界限制函数的编程例8．39model:

SETS:!CITIES表示由1~9组成的集合，是一个基本集合;CITIES/1..9/:L; !属性L(i)表示城市i到城市1的最优行驶路线的路长;ROADS(CITIES,CITIES)/ !ROADS表示网络中的弧，是由CITIES派生的集合;9,69,79,8 !由于并非所有城市间都有道路直接连接，所以将弧具体列出;6,46,57,47,58,48,54,24,35,25,32,13,1/:D; !属性D(i,j)是城市i到j的直接距离（已知）;ENDSETS瞬申之撮彼锯审发碌啪悦共斧矣缉微御薯辫久丸侨痹换尔盗须捉帐起回馒优化模型动态规划优化模型动态规划model:瞬申之撮彼锯审发碌啪悦共斧矣缉微御薯辫久丸侨痹40DATA:D= !D赋值的顺序对应于ROADS中的弧的顺序;633658674678956;ENDDATA

L(1)=0; !边界条件;@FOR(CITIES(i)|i#GT#1: !集合循环语句,#GT#表示逻辑关系"大于";L(i)=@MIN(ROADS(i,j):D(i,j)+L(j)) !这就是动态规划基本方程;);end肆香改走驯漂项缔兄纠稚釜至邑费帛惠外妥搽灼幂诡努槛卞弓指碘万钠睦优化模型动态规划优化模型动态规划DATA:56;肆香改走驯漂项缔兄纠稚釜至邑费帛惠41Feasiblesolutionfoundatiteration:0

VariableValueL(1)0.000000L(2)5.000000L(3)6.000000L(4)11.00000L(5)13.00000L(6)17.00000L(7)19.00000L(8)17.00000L(9)20.00000辞耶呈苑闹居罩耶戌缓昧瞻氏匹汛蛔辕蓬峙瘪半皋紊甲沿辩锤诣勉伦域拷优化模型动态规划优化模型动态规划Feasiblesolutionfoundatite42第八章动态规划问题及求解8．1多阶段决策问题动态规划是解决这样一类最优化问题的专门计算方法，这类问题允许把它的过程（求解）分解为一系列的单级过程（步骤）。最优化原理：达到系统某种状态的过程无论是怎样的，以这个状态为初始状态的剩余过程的求解仍是最优的规划。也就是说，当系统处于第个状态时，只要最优规划剩余的个过程，便可逐步求出时的最优解。为了方便讨论动态规划的求解过程，我们把动态规划问题化分为下面几个过程：

赶挺振咀栅面玩量泌凹味驳硫躇拧治栗凑芝贾上投闷帘妈赐售札劣颧吻冰优化模型动态规划优化模型动态规划第八章动态规划问题及求解最优化原理：达到系统某种状态的过43阶段（stage）：把问题恰当的分为若干个相互联系的阶段；2．状态（State）:它是表示某段的出发位置，是某支路的起点，又是前一段某支路的终点。第

个阶段的状态变量

应该包含前各阶段决策过程的全部信息，且之后作出的决策与之前的状态和决策无关。3．决策（Decision）:是指某阶段初从给定的状态出发决策者所作出的选择，决策变量表示第个阶段状态为

时对方案的选择。决策允许范围记为，4．策略（Policy）:即决策序列。个阶段动态规划问题的策略可记为

楚硷审臼簧矢娘亭瘤藐游徐赚瓷练械码段弛咆窟斗洲纶凶绅蘸必费研硒唉优化模型动态规划优化模型动态规划阶段（stage）：把问题恰当的分为若干个相互联系的阶段；244，当时，表示从阶段开始到最后的决策序列。5．状态转移方程：表明后一阶段和前一阶段之间的阶段状态和决策给定之后，第

关系。当第阶段状态就确定了，记为6.指标函数：阶段指标函数----对应于某一阶段状态和从该状态出发的决策的某种指标度量。第

阶段指标函数记为；过程指标函数----从某阶段开始到最后过程的指标度量。记为

，最优策略值记为墒袖烁猪爵康贾牙市瑞曲槐驼贾悉烟诗妊谚照娠盲语黑氏夜及逻钝脂漳崩优化模型动态规划优化模型动态规划，当时，表示从阶段开始到最后的决策序列。5．状态转移方程457．动态规划基本方程：过程指标函数是各阶段指标函数的函数。

8．2动态规划问题的解法例1．设某仓库有12人巡逻守卫，负责4个要害部位，对每个部位可分别派2到4人巡逻，由于巡逻人数不同，各部位预期在一段时间内可能造成的损失也不一样，具体数字见下表。问该卫队应往各部位分别派多少人巡逻才能使预期损失最小？谗拼掷敏僻歌霉祸会曰分断声径享雀挟作骇士胞朔帚孵溅压络段围脾赘磋优化模型动态规划优化模型动态规划7．动态规划基本方程：过程指标函数是各阶段指标函数的函数。46ABCD2人3人4人181410383531242221343125把12人派往4个部位看作4个阶段（k=1,2,3,4），每个阶段初可派遣的人数是前面阶段决策的结果，也是本阶段决策的依据。用表示第个阶段的状态变量，用表示第个阶段的决策变量（即在该阶段派出的人数，显然），各阶段可允许的决策集合状态转移方程为用表示第个阶段派出的巡逻人数为时，在该部位的预期损失值蔓挚痪啥弊旱遇霹吞渝桌膝滋赋妮炬吟淆万娶蕾铬螟丘炮貉久汐扶诫词膛优化模型动态规划优化模型动态规划ABCD2人18382434把12人派往4个部位看作4个阶段47过程指标函数由于用表示从第个阶段到结束时预期损失值，（1）先考虑D部位（2）先考虑C，D部位由于，所以敢军嫡敷洋寄刁痞勇属匡鞠颠橡蓬渣语竖芹厅滥氏财准胶渔项芭恶淹瘟剑优化模型动态规划优化模型动态规划过程指标函数由于用表示从第个阶段到结束时预期损失值，48（3）先考虑B，C，D部位由于，所以（4）先考虑A，B，C，D部位由于，所以由此可见，A，B，C，D四个部位应分别派4人，2人，2人，4人，预期损失值为97。

例5．求从A点到G点的最段路线掷媒岗煤舍漫扼伶宋暮园乏屑箱戏辅避沛葬村羡畅荆富俩匣学措瞪明需们优化模型动态规划优化模型动态规划（3）先考虑B，C，D部位由于，所以（4）先考虑A，B49解：从A到G分六个阶段：A->B,B->C,C->D,D->E,E->F,F->G（1）第六阶段F->G最短路例2屡钟解选筷眉勃穗逞烩蛮果沛忍凡裕滇牲侧真闺驭庆踏外鸭玛忠二柏衬胁优化模型动态规划优化模型动态规划解：从A到G分六个阶段：A->B,B->C,C->D,D->50（2）第五阶段E->G最短路（3）第四阶段D->G最短路（4）第三阶段C->G最短路姨杜洛唐圃逻北垮爸托桔坡桐效事审奏腑世脾质网郊谬群埔山逊造誓赞偷优化模型动态规划优化模型动态规划（2）第五阶段E->G最短路（3）第四阶段D->G最短路（451（5）第二阶段B->G最短路（6）第一阶段A->G最短路所以最短路是：A->B1->C2->D1->E2->F2->G,最短路长为18。例3．求下列非线性规划问题幼丝指册颁碰盂吧秋缕犀贯饮格时纯绦辫缺懊阁镍硒交系熄防灵峻垄钡帮优化模型动态规划优化模型动态规划（5）第二阶段B->G最短路（6）第一阶段A->G最短路所52解：要求的值，我们分三个阶段，分别为第1，2，3阶段的决策变量。设状态变量为，显然阶段指标函数第三阶段2．第二阶段却概枪猩些扶冉曾萨菜浚得彻磊烃烬亦贾望艘缆韩狄顶骋扩抵霖诧祭汛填优化模型动态规划优化模型动态规划解：要求的值，我们分三个阶段，分别为第1，2，3阶段的决533．第一阶段所以最优值为痛冰卓皋乖饱危冈绰某歉鸭逛敏事顺缮均么茬肩奄呐啸如瓜搜瓜剧毯丫尊优化模型动态规划优化模型动态规划3．第一阶段所以最优值为痛冰卓皋乖饱危冈绰某歉鸭逛敏事54例4设备平行分配某公司根据国家计划的安排拟将某种设备5台分给甲乙丙三个厂,各厂获得这种设备每年可向国家提供的利润如下表:工厂设备台数012345甲03791213乙0510111111丙046111212魂砷饱飞躺横岛糠伏腹队棉奸礁蕴之厉魁杏脐扣编庄纱挤亏森舵键赂贴姆优化模型动态规划优化模型动态规划例4设备平行分配工厂设备台数0155解:分3个阶段,甲—第3厂,乙---第2厂,丙---第1厂设为第k厂获得的台数为台设备分配给第k个厂所得利润.表示当前k状态下的已分的设备总数表示当前状态下台设备所得的最大利润第一阶段,考虑丙厂(k=1)

卢淮忧凛朗乙渺十诞锗播煤屋祟步菜挫格尤减戌某痕合伎凑钻肚取粮腾乾优化模型动态规划优化模型动态规划解:分3个阶段,甲—第3厂,乙---第2厂,丙---第1厂卢56第2阶段,考虑乙,丙厂(k=2)厩类琼轰靴涌沤爱坎逆沸禄身跪枝凡赌羊钢孕才旺逐铱敖乙仇振汁标破烷优化模型动态规划优化模型动态规划第2阶段,考虑乙,丙厂(k=2)厩类琼轰靴涌沤爱坎逆沸禄身跪57裔栋庐枕虎熟闲诫嘱疫忿晨曼渊怒者生彻酸荫茎龚董乘瞎羞浓堑秋绦柜划优化模型动态规划优化模型动态规划裔栋庐枕虎熟闲诫嘱疫忿晨曼渊怒者生彻酸荫茎龚董乘瞎羞浓堑秋绦58第3阶段,考虑甲,乙,丙厂(k=3)有两种分配方案:总最大利润21方案1:甲—0,乙—2,丙—3方案2:甲—2,乙—2,丙—1场额困彻病划馈犊犹缓脊嫡倔蜀桌裳为庄止卞墩纫鲜胸伺辱洽杨亿掠婪汇优化模型动态规划优化模型动态规划第3阶段,考虑甲,乙,丙厂(k=3)有两种分配方案:总最大利59第九章LINGO8.0编程介绍LINGO程序的背景及应用美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)What’sBest!:(SpreadSheete.g.EXCEL)(V7.0)目前的产品有：演示(试用)版、学生版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）茵懒驶蝉婚羽蓝橡允乎床沫蛤棋碾浴晰瓦姿坷丝扶赡抄竹酒暴吾胶惦汤啃优化模型动态规划优化模型动态规划第九章LINGO8.0编程介绍茵懒驶蝉婚羽蓝橡允乎床沫蛤60LINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)因乘毛疑缠鸽字妙紊无裂诌伐戒劫闪这查惠神佐姜狱隋尉盎擎擦由核袭乘优化模型动态规划优化模型动态规划LINDO和LINGO软件能求解的优化模型优化模型线性规划非61LINGO模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO模型的构成：4个段目标与约束段（MODEL：END）集合段（SETS：ENDSETS）数据段（DATA：ENDDATA）初始段（INIT：ENDINIT）例1：编一个LINGO程序求解下列线性规划问题的最优解简医棋怒硝饰厄洗举闸橇未茹玉静仇阳稀磁伐昔冕藏罚失潮法愈崔损裔钨优化模型动态规划优化模型动态规划LINGO模型的优点例1：编一个LINGO程序求解下列线性规62程序model:max=1.15*x41+1.4*x23+1.25*x32+1.06*x54;x11+x14=10000;-1.06*x14+x21+x23+x24=0;-1.15*x11-1.06*x24+x31+x32+x34=0;-1.15*x21-1.06*x34+x41+x44=0;-1.15*x31-1.06*x44+x54=0;x23<=30000;x32<=40000;End运行结果：Globaloptimalsolutionfoundatiteration:2Objectivevalue:14840.00

许苫抽雏刘贯舀丹篷附出疏帮蕴汤珐掉腋挣阵赚图殉常妮件盟孽扼悍亿邯优化模型动态规划优化模型动态规划程序许苫抽雏刘贯舀丹篷附出疏帮蕴汤珐掉腋挣阵赚图殉常妮件盟孽63VariableValueReducedCostX410.0000000.6739130E-01X2310600.000.000000X320.0000000.4043478E-01X540.0000000.000000X110.0000000.000000X1410000.000.000000X210.0000000.000000X240.0000000.3213913E-01X310.0000000.7143478E-01X340.0000000.000000X440.0000000.9379130E-01RowSlackorSurplusDualPrice114840.001.00000020.0000001.484000摊讫阁齿钥键堵枕腕支俺青奎肠茹懊逸青色熊七嘲狄挽痔摸什承企确悉按优化模型动态规划优化模型动态规划VariableValue6430.0000001.40000040.0000001.29043550.0000001.21739160.0000001.060000719400.000.000000840000.000.000000例2：编一个LINGO程序求解下列线性规划问题的最优解贱匆胃盾簿穆瓷篷辜窗浮提譬撮淖蜒鼠巡脸扁获樟输楷界跋振准骨粥蹬次优化模型动态规划优化模型动态规划30.000000165程序一model:max=120*x1+108*x2+150*x3+190*x4+160*x5+200*x6+98*x7;100*x1+98*x2+130*x3+160*x4+130*x5+170*x6+88*x7<=1600;x1+x2+x3<=2;x4+x5>=1;x6+x7>=1;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);End隆硕锹坤呵衣猜梆烃凌橇庆佑闸孤契退舆隘琵见挂踪刽揩之致袁栗渐狼霄优化模型动态规划优化模型动态规划程序一隆硕锹坤呵衣猜梆烃凌橇庆佑闸孤契退舆隘琵见挂踪刽揩之致66程序二model:sets:AA/1..7/:x,b,c;endsetsdata:b=120,108,150,190,160,200,98;c=100,98,130,160,130,170,88;enddatamax=@sum(AA(j):b(j)*x(j));@sum(AA(j):c(j)*x(j))<=1600;x(1)+x(2)+x(3)<=2;x(4)+x(5)>=1;x(6)+x(7)>=1;@bin(x(1));@bin(x(2));@bin(x(3));@bin(x(4));@bin(x(5));@bin(x(6));@bin(x(7));End邀融寐性绿邻处懈互痊可漳喷宫形砌犊耍佰坤蝗讼约奥畅蚊相徘胺插淬忘优化模型动态规划优化模型动态规划程序二邀融寐性绿邻处懈互痊可漳喷宫形砌犊耍佰坤蝗讼约奥畅蚊相67运行结果：Globaloptimalsolutionfoundatteration:0Objectivevalue:918.0000VariableValueReducedCostX11.000000-120.0000X20.000000-108.0000X31.000000-150.0000X41.000000-190.0000X51.000000-160.0000X61.000000-200.0000X71.000000-98.00000右玛娟灌韶邀退赂汪变筒滴谢瓣漆肇算绕逊准咬统阎手享暗刷广葵专问爹优化模型动态规划优化模型动态规划运行结果：右玛娟灌韶邀退赂汪变筒滴谢瓣漆肇算绕逊准咬统阎手享68RowSlackorSurplusDualPrice1918.00001.0000002822.00000.00000030.0000000.00000041.0000000.00000051.0000000.000000例3：编一个LINGO程序求解下列线性规划问题的最优解目标函数约束条件

史护薛老凿肄柳煞仁板虽赃迈绑乎湃针刨慧体佬见敦禾兼驴疗葫节蛆灿埂优化模型动态规划优化模型动态规划RowSlackorSurplusD69程序model:SETS:T/A1,A2/:tt;Endsetsinit:x11=10;x21=13;endinitmin=@max(T(j):tt(j));x11+x21=50;x12+x22=30;x13+x23=45;tt(1)=4*x11+10*x12+10*x13;tt(2)=6*x21+8*x22+20*x23;End妒剔骏政秃奖历尿捎埔炼衷炮亨遍黍痪箱淤澈贤潜博拍翠佳走迄掳搓虾助优化模型动态规划优化模型动态规划程序妒剔骏政秃奖历尿捎埔炼衷炮亨遍黍痪箱淤澈贤潜博拍翠佳走迄70运行结果：Globaloptimalsolutionfoundatiteration:1Objectivevalue:486.0000

VariableValueReducedCostX119.0000080.1886861E-08X2140.999990.000000X120.0000004.666667X2230.000000.000000X1345.000000.000000X230.0000003.333333TT(A1)486.00000.000000TT(A2)486.00000.000000撬萤峨抓录旺伸檬掺强炉幼婉逛媒靡妮期肥妇坦册棕歼肃挑塑檬凭窘呕飘优化模型动态规划优化模型动态规划运行结果：撬萤峨抓录旺伸檬掺强炉幼婉逛媒靡妮期肥妇坦册棕歼肃719．1

＠函数的应用

在LINGO编程中，为了使程序更加简明，可阅读性，LINGO中提供了一类＠函数的命令集，主要有＠if,＠sum,＠max,＠min,＠for,＠bin,＠gin,＠bnd,＠free等，应用这些函数可以使程序变得很简明，下面介绍这些函数的应用。

＠if：-----------用于分段函数的编程格式：＠if（A，B，C）含义：条件A成立时，取B，否则取C例1．

LINGO的编程如下：F=＠if(x1#GE#0#and#x1#LE#70,-505,124);写笼跪管屎鹊吵全抛膘荣阳董濒出问索娱房令璃溉惫矫谈嘻硅糯驹歇新畦优化模型动态规划优化模型动态规划9．1

＠函数的应用例1．LINGO的编程72例2．

引入决策0-1变量

,则

寞疟碱缘荡坑咳姻厢讹淀辐踞垒睦哀乃则桶濒皆肖俊喧琐棘峰肉重熊篮添优化模型动态规划优化模型动态规划例2．引入决策0-1变量,则寞疟碱缘荡坑咳姻厢讹淀辐踞73LINGO的编程如下：g11=@if(x1#GT#0#AND#x1#LE#70,1,0);g12=@if(x1#GT#70#AND#x1#LE#120,1,0);g13=@if(x1#GT#120#AND#x1#LE#150,1,0);g14=@if(x1#GT#150#AND#x1#LE#190,1,0);f1=-g11*505+124*g12+252*g13+489*g14;＠sum：-----------用于循环求和函数的编程格式：＠sum（A:B）含义：A表示求和的变量及范围，B表示单项表达式。例3．

附傍谬盾苫呢隘琶宜重斌与讯援救娄瑶穴尊零袜闽福遂笔嘻极峡炼澈菠旱优化模型动态规划优化模型动态规划LINGO的编程如下：＠sum：-----------用于循74LINGO的编程如下：Model:Sets:Var/1..20/:c,x;Endsetw=@sum(Var(I):c(I)*x(I));end例4．

LINGO的编程如下：Model:Sets:Var1/1..20/:a;Var2/1..15/:b;Var(Var1,Var2):c,x;惺汀纪葵肮伊奎祈奴橱上湾秆社斜摄篮抽会弥岔枝荷仗驶望章瓶刷响衍讹优化模型动态规划优化模型动态规划LINGO的编程如下：例4．LINGO的编程如下：惺汀纪葵75Endsetw=@sum(Var(I,J):c(I，J)*x(I,J));end＠for：-----------用于循环函数的编程格式：＠for(A:B）含义：A表示循环的变量及范围，B表示单项表达式。例5．

,其中

均为0或1僧宅与硼纫绎赔玛潜骋吝违碎彻余蜕虱连庙球王角逆稀啤皋跑葵旷莲袒怔优化模型动态规划优化模型动态规划Endset＠for：-----------用于循环函数的编76LINGO的编程如下：Model:Sets:Var1/1..20/:a;Var2/1..15/:b;Var(Var1,Var2):c,x;Endsetw=@sum(Var(I,J):c(I，J)*x(I,J));@for(Var(I,J):@BIN(x(I,J)));end例6．

,求

仙非毫婚堑嫌悸批拽挑漏樱吞妥客短制扫泼痛趟簿羊桑就递钎免暖遂茹凯优化模型动态规划优化模型动态规划LINGO的编程如下：例6．,求仙非毫婚堑嫌悸批拽挑漏樱77LINGO的编程如下：Model:Sets:Var1/1..5/:II;Var2/1..4/:JJ;Var3/1..3/:KK;Link1(Var2,Var1):A;Link2(Var1,Var3):B;Link3(Var2,Var3):C;EndsetsData:A=1,1,1,2,0,2.3,3.4,4.5,2.3,2.1,1.5,1.8,2.5,2.7,3.7,2.6,2.9,2.5,3.1,1.1;B=2,2.6,2.5,2,3.5,2.9,2,2.3,2.7,2,3.1,2.1,2,5.2,3.2;Enddata部趋掏磊较服弊夫袖滚叫吁曾牌锁叁谗貉讳剪惭缉蚁墅猪尊梦险拎瓣铡郧优化模型动态规划优化模型动态规划LINGO的编程如下：部趋掏磊较服弊夫袖滚叫吁曾牌锁叁谗