第二章-整数规划

数学模型电子教案重庆邮电大学数理学院虞继敏第二章规划论模型1.线性规划2.整数规划3.非线性规划4.动态规划

1.整数规划问题的提出2.分枝定界法3.0-1型整数规划4.指派问题第二节整数规划

1.整数规划问题的提出

在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数规划(IntegerProgramming)或简称IP。

例1某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：

货物集装箱体积(米3)重量(百斤)利润(百元) 甲5220乙 4510托运限制24 13 问两种货物各装运多少箱，可使获得利润最大？

是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？

设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下：Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)x1,x2≥0(4)x1,x2为整数(5)它和线性规划问题的区别在于条件(5)。此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。因此要专门研究整数规划的解法。

分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。2.分枝定界法

设有最大化的整数规划问题R，与它相应的线性规划问题为R0，分枝定界法的做法是：

(1)用观察法求R的一个可行解，其目标值便是R的最优目标值z*的一个下界z。(2)求解R0，得R0的最优解x(0)和最优值z0。若x(0)符合R的整数条件，则显然x(0)也是R的最优解，结束；否则，以R0作为一个分枝标明求解的结果，z0是问题R的最优目标值z*的一个上界z。(3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选一不符合整数条件的变量xj，其值为bj，构造两个约束条件xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs，得两个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。(4)定界。在各分枝中找出目标函数值最大者作为新的上界z；从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界z。(5)比较与剪枝。各分枝的最优目标函数值中如果有小于z者，则剪掉这一枝（用打×表示），即以后不再考虑了。若已没有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。例求解问题Maxz=40x1+90x29x1+7x2≤

567x1+20x2≤70x1,x2≥0,整数问题R0为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0R0:z0=356x1=4.81x2=1.82问题R1为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x1,x2≥0问题R2为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≥5x1,x2≥

0x1≤4x1≥5R1:z1=349x1=4.00x2=2.10R1:z1=349x1=4.00x2=2.10问题R11为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≤2x1,x2≥0问题R12为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≥3x1,x2≥

0x2≤2x2≥3R1:z1=349x1=4.00x2=2.10R12:z12=327x1=1.42x2=3.00x2≥3R11:z11=340x1=4.00x2=2.00R21:z21=308x1=5.44x2=1.00R22:无可行解x1≤1x1≥2x2≤2R2:z2=341x1=5.00x2=1.57R0:z0=356x1=4.81x2=1.82x1≤4x1≥50-韵1型毙整数态规划奏是整迎数规慕划的火一种乏特殊象形式挽，它拍的变陶量xj仅取敢值0穷或1般。这筒种只厨能取河0或城1的捞变量扎称为扮0-穷1变构量或第二进惠制变归量。例:化某牧公司封拟在妈市东换、西薪、南盘三区沈建立减门市眨部。海拟议碗中有越7个嗓位置关Ai（i涛=1燃,2案,切…,辫7）气可供坝选择翁。规槐定：兄(1挣)在椒东区满A1、A2、A3三个怜点中宇至多图选两竞个；器(2划)在离西区逮A4、A5两个举点中初至少它选一锤个；奖(3冤)在减南区辨A6、A7两个慈点中型至少亭选一或个。如选竞用Ai点，游设备片投资递估计百为bi元，插每年轰可获茂利润凝估计玩为ci元，熊但投叔资总陷额不吹超过复B元鸣。问晴应选针择哪罩几个碰点可倚使年挺利润承为最肉大？3.叮0-贱1型飘整数册规划引入0-1变量xi（i=1,2,…,7）,令xi=1,当Ai点被选用,xi=0,当Ai点没被选用。（i=1,2,…,7)Ma呀x岔z=扇c1x1+c2x2+…微+c7x7b1x1+b2x2+…亭+b7x7≤Bx1+x2+x3≤2x4+x5≥1x6+x7≥1xi=0或1同,恋i=呈1,晒2,快…,窑7于是返建立狠下列茅模型鼓:例某求解潮0-池1型日整数服规划晚问题Ma慎xz=捡8x1+2观x2-4围x3-7晒x4-5恢x53x1+3屋x2+x3+2枪x4+3菠x5≤45x1+3膛x2-2狐x3-x4+炼x5≤4xj=0善或1阳，j圾=1俱,2钟,…危,5变成导标准饲型，去要求喂如下升：⑴泪目标膜函数舞求极似大化植。俱对于喷目标锐函数蚊为M芦inz的极窑小化质问题债，令z′=-z，使肆其变叠为目熟标函陕数为恶Ma济xz′的极困大化饺问题羡。⑵典目标欺函数困中所轰有变引量的言系数员都为形正数爸。如表果目扁标函柴数中甘变量xj的系慌数为痛负数陵，令xj′=锣1-吓xj，把后模型灶中的xj用xj′代换楚。⑶讲变量赚的排觉列顺循序按辆变量挖在目失标函闯数中修的系影数值逮从小庭到大宇排列简。求解插0-陪1型鸦整数裕规划评，可斤使用浆分枝衫定界碑法。亩下面降用实啄例说毫明：过滤鞋隐枚援举法览举例欲分析例3打：找出饱一个咽可行绍解求出唐其目警标函参数值2.炼由于垒该问骑题是逃求最乎大值脉，故且目标秆值小疲于3撤的解租可以橡不考电虑，增加科约束霞条件，此条鲁件称呼为过骄滤条疤件。例有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指派哪个人完成哪项工作，使所需的总时间最少？一般地，有n项任务、n个完成人，第i人完成第j项任务的代价为cij（i,j＝1,2,…,n）。为了求得总代价最小的指派方案，引入0-1型变量xij，并令1指派第i人去完成第j项任务

xij＝

0不指派第i人去完成第j项任务4.沾指派留问题指派辽问题液的求粮解，叛最简纵便易睡行的割方法底是匈钓牙利喇法。可见书指派袍问题天是0渡-1地型整舍数规杨划的解特例碍。不住难发蹄现，岭指派那问题化也是滑运输仆问题冈的特通例，船其产征地和制销地某数都犹为n轿，各旦产地上的产寸量和杰各销脏地的均销量童都为燥1。数学模型为Minz＝∑∑cijxij

n∑xij＝1j=1,2,…,n

i=1

n∑xij＝1i=1,2,…,n

j=1xij＝0或1匈牙利法基于下面的效率矩阵：c11c12…c1n（cij）=c21c22…c2n……………….cn1cn2…cnn匈牙齿利法尊基于白这样粘一个附明显炎的事率实：贡如果辣系数维矩阵浅的所骡有元木素满道足cij≥0他，而艺其中马有n粱个位挺于不而同行鹊不同常列的沿一组年0元饶素，翼则只公要令懂对应识于这肺些0雀元素具位置闭的xij＝1胃，其柔余的颠xij＝0权，就初得到象最优杠解。匈牙蹲利法伍求解挤指派征问题捕的步巡寿骤如税下：

0420

例如：（cij）=207831500603第一养步：榆变换掩系数掘矩阵妥，使胆每行度每列旷都出本现0秃元素描。(绕1)们系数暮矩阵罢的各与行分搏别减报去各肾行中号的最肺小元露素；弱(2捏)所扯得系储数矩溪阵的坐各列隶再分窜别减妻去各株列中嘉的最携小元快素。第二谢步：阻试求剃最优傲解。(1找)给胸只有矩一个穷0元您素（间不含渐划去钱的0巡寿）的花行中倾的“泳0”梦画○透，划命去与榨◎同箩列的胶其它虫“0北”；(2涝)给哨只有怨一个佩0元疼素（奖不含旱划去葵的0凤）的述列中沸的“漫0”锯画○茅，划供去与页◎同嗓行的他其它绵“0贵”；(3天)重颠复(站1)蛾、(跑2)迹，直度到无珠新的口◎画岗出。软若系穷数矩摔阵中仙已无面未画矛○也剪未划睛去的油“0崭”，划则已娃得到奖最多性的◎软，转耻(5达)；炒否则炭，便紫出现币了0兔元素转的闭乌回路恳，转透(4荷)。(4乏)从街0元曾素的韵闭回问路上誓任选红一个伐“0虎”画伸○，凶划去热其同糟行同根列的岩其它滨“0侄”，次转(考1)却。(5信)显蛇然，凶按上冒述步岔骤得圈到的曲◎是蜓位于劳不同缎行不躬同列吵的。银若◎穴已达级n个橡，则视指派控问题乞的最除优解潜已得类到，纷结束定计算伞；否勺则，猪转第笛三步坡。第三窜步：陡用最替少的菜直线身覆盖扑所有商0元窄素。(1缓)给帜无◎沟的行研打“纠√”德；(2慌)给惊打√愧行中菠含有愈0元间素的控列打些“√子”；(3零)给栏打√董列中横含有激◎元竟素的饮行打么“√造”；(4觉)重造复(慎2)馅、(壮3)昆，直佣到无傅新的腹“√励”打课出。(5慢)给晶没有躁打√廊的行卷画横啦线，笼给打烈√的输列画居纵线切。第四贩步：塌变换箩系数脚矩阵设，增蹦加0六元素干。在胀未被没画线愉覆盖行的其纳它元堵素中牲找出王最小贯元素毅，各炼打“转√”矩行减西去最倘小元条素，颜各打码“√潜”列溪加上最最小氧元素区，转挥第二击步。

例求下列指派问题的最小解。解：12撕7劲9痛7啊98姻9柜6走6徒67粪17醉1艳2保14仙915轰1根4可6谅6杜104残10祸7扰10扑95欣0池2舰0麻22册3史0合0序00付10赶5样7直29诸8欢0杀0暗40代6稿3既6讲5√√√7立0挽2容0劳24茶3句0便0确00不8打3留5撒011辽8路0塔0赞40炉4妨1厅4瞒3于是辈此问惹题的许最优秀解为输:甲昏—B穿,乙覆—C化,丙千—E锋,测丁—坡D,述戊驴—A所需球的总名费用青为：供Mi岁n安z=竹7+怠6+卧9+佳6+犬4=爸32第三辫节毛非线刚性规概划模简型一、之非线圆性规贸划问脱题线性第规划找和整彩数规扒划它巧们的浙目标价函数豆和约掠束条型件都柿是自变僚量的伪线性叨函数爪，在驼实际口中还僚有大撤量的霉问题肾，其目德标函笋数或余约束剥条件藏很难剃用线榨性函撤数来拾表示楚。如果钓目标添函数耀或约木束条响件中糟含有庸非线劳性函谋数，则称享这种州规划土问题基为非柄线性伶规划挨问题旦。先扣看两摊个实幻玉例。问题垮1眠容究器设矿计问介题问题征提出衣某公寻司生罗产贮泻藏用胶容器夹，订殊货合盏同要克求该糖公司讨制造一种印敞口证的长筑方体邮容器还，容锣积为崖12殿立方任米，诸该容顺器的掠底为爸正方老形，容器质总重窄量不裕超过枪68准公斤撒。已跑知用蚊作容仇器四涉壁的肠材料洽为每平低方米如10圣元，你重3钱公斤百；用迁作容边器底思的材降料每通平方渗米2屑0元野，重2牙公斤粘。试伶问制慨造该坐容器秀所需昆的最更小费对用是道多少瘦？模型泊建立青设该痰容器狱的底啊边长良和高絮分别独为则问膛题的扫数学塘模型泻为三、领非线懒性规臣划问湖题解太法概文述1、欢非线叔性规望划问米题的刻图解冒法当非缎线性泻规划屈问题嫌只有欧两个染自变用量时处，也渗可像鹿线性语规划河那样用图厚解法肾求解演。考拢虑非言线性斗规划s．麦t．5、镰计算俯结果Ma膨tl卫ab刺优化外工具绸箱简绒介1.潮MA球TL换AB垦求解应优化叠问题则的主塘要函湿数2.扇优吩化函击数的滥输入版变量使用兵优化采函数染或优壳化工碗具箱践中其龙它优躬化函疏数时陵,宰输入贱变量铅见下喜表:3.切优钩化函技数的近输出光变量雪下表程:4．借控制朱参数谢op痰ti母on秆s的蜜设置(3耐)Ma逆xI偶te恼r:千允许我进行轮迭代究的最购大次替数,惭取值撕为正叠整数半.Op善ti建on锦s中鹅常用姑的几液个参唯数的拢名称负、含既义、爱取值尾如下导:(1掩)Di运sp终la匆y:稿显示售水平誓.取轿值为璃’o贸ff既’时促,不察显示些输出灯;拥取值贡为’茫it殊er遭’时械,显格示每舌次迭讽代的宜信息露;取荒值为跃’f享in跨al冷’时肠,显缸示最悦终结副果.笛默认县值为视’f签in置al全’.(2兼)Ma造xF黎un毁Ev桃al匠s:锈允许符进行英函数门评价钻的最黎大次效数,帝取值模为正仁整数帝.例：蛇op醉ts绕=o玻pt层im谷se玻t(杜‘D僵is劈燕pl挠ay额’,祖’i租te议r’布,’预To测lF探un券’,耳1e岸-8妇)该语软句创密建一佛个称斩为o僵pt辱s的右优化华选项沟结构暂,其分中显努示参视数设遗为’手it龟er平’,导T另ol形Fu剂n参掉数设甘为1翠e-画8.控制耐参数震op员ti勇on抛s可恨以通他过函秋数o占pt松im售se猛t创傅建或储修改石。命叼令的童格式穷如下脖：(1誓)op皮ti乳on绘s=僚op吗ti授ms井et适(‘幸op扬ti津mf他un怨’)创建总一个侮含有撒所有楚参数卸名,落并与船优化航函数坟op和ti菜mf槽un帆相关丈的默肠认值肾的选兽项结乱构o止pt低io爷ns羞.（2冻）op知ti既on殿s=钞op估ti免ms默et梨(‘躬pa谎ra代m1逼’,息va简lu绝e1缎,’亚pa醋ra误m2扶’,戏va稀lu机e2耍,.叫..漏)创建言一个困名称场为o袍pt命io种ns敌的优训化选性项参持数,丛其中他指定薄的参农数具吵有指港定值滑,所尿有未声指定变的参止数取瞧默认虏值.(3怀)op罪ti掀on点s=厘op祝ti矮ms革et宫(o膨ld技op饼s,鼓‘p查ar胁am掠1’陵,v归al更ue宰1,档’p隶ar剑am当2’馋,va资lu久e2蜡,.岗..蹲)创建绳名称塔为o如ld臣op传s的盏参数缘瑞的拷速贝,杀用指屠定的叨参数酒值修拖改o胁ld北op振s中设相应撇的参滥数.返回用M区AT糖LA慢B优严化工芒具箱押解线装性规章划minz=cX

1、模型：命令驰：x=蔑li禾np淡ro厘g（演c，室A，绑b）2、模型：minz=cX

命令行：x=翼li河np继ro尸g（致c，据A，姨b，诸Ae侍q,蚊be悄q）注意：若没有不等式：存在，则令A=[]，b=[].3、模型：minz=cX

VLB≤X≤VUB命令症：[1奶]x=细li菜np柜ro裕g（骡c，宵A，姿b，刘Ae敲q,蒸be倾q,筝V多LB樱，V筐UB杠）[2押]x=柜li份np银ro爱g（啊c，涝A，浸b，督Ae防q,狸be远q,芹V楼LB吵，V潮UB炕,者X0）注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点4、丢命令歉：[x培,f验va扰l]闷=l垄in拢pr两og桨(…则)返回品最优狡解ｘ识及ｘ榆处的撤目标蛮函数盼值f羽va撤l.解辈编写电M文政件x矮xg能h1赴.m吹如下祸：c=族[-予0.豪4政-0种.2尤8携-0蚀.3蛛2球-0考.7胖2浙-0狐.6晚4言-0校.6验];A=贸[0屠.0末1善0.宵01付0胖.0腿1府0.层03钉0方.0单3居0.锤03坝;0肤.0己2某0东0蒙0.请05血0荡0披;0墨0免.0仓2兰0透0落0.溜05缎0匀;0胆0肆0悼.0站3溉0返0犯0.知08巷];b=高[8逝50调;7恳00柜;1共00耕;9膨00袋];Ae需q=每[]搜;拦be峰q=仇[]痕;vl疼b=社[0饿;0蚂;0川;0哄;0删;0际];胶v惕ub基=[站];[x材,f页va巨l]薯=l绞in彩pr雾og烧(c旷,A弱,b域,A州eq愧,b预eq饿,v哀lb半,v谷ub桌)To启M鹅at吊la潮b伶(x隐xg糖h1画)解:膝编写唤M文滴件x想xg荷h2亲.m剩如下内：c=仔[6桑3功4暖];A=阿[0繁1集0布];b=看[5裕0]渐;Ae吐q=漏[1坊1讲1纸];be弟q=垂[1早20北];vl扭b=丽[3皇0,骨0,眯20烤];vu研b=好[]凯;[x猪,f骗va莫l]悠=l他in票pr缎og速(c政,A皱,b厕,A剂eq聪,b耻eq字,v柏lb象,v邀ub捆)To霞Ma搏tl呜ab捎(蔑xx五gh碰2)S.t.改写为：例3问题孤一的抄解答问题编写叔M文拖件x抢xg畜h3要.m絮如下俱:f接=钱[1员3匆9场10差1眼1美12厦8敲];A仙=美[仙0.畜4薯1.洁1气1拒0寄0段00填0滚0零0.绍5织1.爽2泻1.批3]抄;b奶=虚[8遇00络;割90调0]惯;Ae拢q=坡[1蒜0镇0括1炭0束00钓1赢0柄0崖1浙00仪0诸1扰0圾0乌1]里;be以q=穿[4四00鉴6卸00腐5望00挺];vl斜b遗=振ze看ro旋s(势6,部1)揉;vu头b=桂[]妙;[x怕,f工va味l]饼=睬l巨in借pr窗og伤(f陈,A艺,b绘,A浆eq健,b市eq路,v案lb煎,v网ub衰)To签Ma是tl条ab蜓(广xx慨gh东3)结果包:x撇=0.掠00圾0060蝴0.楚00慨000.踢00比0040绞0.追00棉000.发00绞0050渡0.济00谢00fv浩al伸=鼓1.网38割00森e+截00剪4即在部甲机绞床上遥加工割60槐0个耽工件愚2,冒在乙块机床场上加盈工4廊00床个工铜件1叉、5蜻00紫个工堆件3云，可凡在满烂足条娘件的四情况财下使滥总加杀工费咳最小搭为1岁38柜00扣。例2腰问题朋二的争解答问题改写为：编写丙M文散件x刑xg障h4笛.m抓如下墓：c治=沃[4斗0;庭36僚];A=或[-鼓5吩-3桶];b=宰[-副45鲜];Ae荷q=舞[]傲;be摸q=骆[]联;vl躲b湿=研ze参ro皆s(端2,处1)车;vu惑b=量[9殿;1发5]煎;%调狠用l昆in橡pr盗og江函数宵：[x蛇,f迫va信l]亏=搬l灿in笔pr惰og蹈(c孟,A警,b唤,A肆eq辣,b巾eq温,v以lb停,v荣ub笛)To谣Ma号tl竖ab砌(鼻xx尽gh胸4)用M饰at占la肉b解保无约竿束优石化问筹题其中尚（3斗）、说（4四）、搏（5奏）的株等式撒右边少可选砌用（弹1）且或（肥2）惹的等梯式右夺边。函数软fm纳in档bn奶d的习算法搭基于锡黄金聚分割升法和范二次盐插值纳法，团它要骗求目哗标函年数必往须是势连续脑函数叶，并岁可能霞只给躬出局回部最狡优解祖。常用溜格式宾如下骗：（1巧）x扁=泪fm埋in伐bn夫d容(fu捎n,勤x1,x2)（2距）x水=博fm警in贷bn超d狸(fu艰n,踪蝶x1,x2，o衡pt她io概ns富)（3创）[弹x，谊fv肾al滥]=螺f燃mi揭nb拘nd居（.泉..妨）（4幅）[仗x，效fv犹al趋，e旧xi扯tf键la左g]跪=钞fm相in琴bn抚d（钞..炊.）（5仙）[添x，闻fv骂al快，e宵xi缓tf滴la眉g，穴ou咱tp捷ut忠]=僵f期mi坦nb絮nd转（.窝..豆）To孙M窃at刻la超b(仍wl甩it更i1个)主程呆序为牙wl往it盾i1茎.m备:f=双'2浮*e歉xp圈(-邻x)鸟.*堵si幸n(夫x)亚';fp抢lo虽t(特f,净[0知,8闯])货;赴%作裂图语打句[x所mi故n,阀ym乏in拢]=赌fm益in府bn快d猾(f借,基0,定8)f1乘='插-2加*e插xp晋(-小x)扔.*坛si驶n(债x)刊';[x敬ma愧x,妙ym递ax算]=批fm植in结bn洒d客(f徐1,朴0欲,8惩)例2对边刻长为唯3米需的正越方形药铁板厕，在粮四个篇角剪扭去相泛等的诸正方员形以得制成蛙方形迹无盖挎水槽遮，问松如何佛剪法拉使水析槽的蝴容积奸最大邪？解先编椅写M仍文件凭fu赌n0杠.m拐如下制:fu伐nc尺ti春on林f挂=f岁un馆0(资x)f=奏-(期3-侨2*吃x)参.^道2*侄x;主程携序为线wl百it息i2旷.m府:[x订,f浓va瞎l]心=f锣mi惊nb府nd扶('关fu庭n0咱',畅0,卧1.疮5)符;xm旅ax衔=xfm候ax失=-遣fv半al运算腊结果考为:xm终ax冷=铁0薪.5棕00商0,剥fm峡ax无=姨2.凡00戚00仅.即掘剪掉挂的正托方形常的边腰长为乌0.如5米伟时水阴槽的疑容积框最大巩,最醋大容打积为栏2立羡方米农.To核M钥at廊la谦b(泉wl相it红i2金)命令照格式洁为:（1敬）x=宴f仇mi踏nu省nc图（fu舞n,慎X0）；叶或x毅=f舞mi盘ns侄ea孩rc温h（fu伟n,婶X0）（2占）x=饥f渐mi立nu埋nc直（fu猛n,岂X0，o献pt雨io柿ns茎）；或x向=f半mi萄ns仍ea蒸rc纱h（fu许n,宽X0，o潜pt津io宰ns戏）（3胡）[x滔，f石va久l]主=堆fm秧in添un浇c（遥..挡.）消；或[映x，夸fv受al尾]=杨f订mi神ns担ea建rc奥h（葵..搂.）（4旧）[x胸，f睡va戒l，锄ex毕it腊fl轻ag刘]=康f逮mi效nu晨nc啊（.樱..部）；或[虽x，叶fv芦al县，e幸xi勒tf雨la乐g]瓶=贯fm捉in漫se披ar尝ch（5坡）[x娘，f岂va伞l，啄ex克it死fl递ag扯，o语ut竭pu行t]尊=监fm即in致un正c（芦..浅.）肯；或[扩x，猎fv谦al各，e车xi疼tf亚la碧g，欠ou晕tp阅ut窑]=尾f温mi蔽ns钞ea痛rc构h（鸟..甜.）2、印多元损函数扛无约恢束优薯化问奋题标准圆型为：mi毕n膝F(浙X)[3采]股fm勒in弯un太c为扛中型琴优化拜算法沈的步虏长一碰维搜听索提梳供了里两种姐算法奇，由o贵pt凯io躬ns哈中参氏数L跪in摇eS趣ea扇rc俱hT讽yp虑e控胜制：Li智ne嘉Se蝇ar师ch膀Ty聋pe翅=’膀qu艇ad或cu客bi洲c’异(缺邮省值德)，怒混合饿的二爪次和汪三次多穿项式瓶插值蕉；Li喜ne临Se膜ar切ch然Ty拍pe粥=’木cu阵bi荐cp祸ol届y’胖，三健次多重项式者插使用fm早in级un景c和fm那in巾se绞ar望ch可能可会得枯到局恨部最授优解.说明渗:fm饭in适se礼ar远ch是用巧单纯即形法蛙寻优.fm某in天un波c的算壳法见久以下亲几点冻说明林：[1邪]裤fm蝴in齿un霜c为西无约万束优港化提陵供了址大型膛优化亩和中剃型优款化算兽法。贝由o适pt易io垂ns侦中的务参数费La天rg旨eS闪ca悠le咽控制筋：La哈rg先eS抛ca许le兽=’揪on曾’(艇默认抖值)从,使加用大杯型算奶法La客rg糕eS校ca司le减=’盟of抛f’住(默激认值目),告使用崖中型侍算法[2恼]寺fm摆in讽un滚c为孙中型着优化对算法斤的搜痒索方皆向提让供了素4种姿算法昼，由op岂ti粗on演s中忆的参览数H冬es安sU摇pd内at冲e控赢制：He诱ss策Up必da浸te火=’垦bf善gs境’（挪默认听值）毙，拟脆牛顿岸法的仗BF巩GS每公式桌；He剑ss鼓Up滨da遍te增=’版df洒p’寺，拟颤牛顿蹄法的敢DF饿P公卸式；He级ss犁Up械da醋te守=’则st伴ee坦pd层es颜c’集，最醉速下直降法例3mi幅n倚f(扎x)歉=(仪4x12+2茫x22+4彼x1x2+2隙x2+1槐)*驳ex音p(叫x1)To泛M广at飘la吓b(寸wl圣it坟i3梯)1、歪编写订M-即文件翼f勇un乌1.鼻m:fu事nc解ti喂on践f壮=业f闻un木1拾(x岩)f季=挑ex采p(帆x(序1)蝴)*处(4谋*x岗(1窑)^仰2+惧2*默x(予2)址^2拆+4滥*x冠(1莫)*互x(丈2)鼓+2自*x勒(2拐)+箭1)璃;2、胞输入绵M文倚件w弦li蔑ti续3.鲜m如批下:x0=术[-惭1,董1顺];x=姓fm悔in静un熊c(局‘f常un承1’衡,x0);y=歼fu梅n1跨(x堤)3、初运行章结果相:x=交0炎.5烈00全0味-1商.0幻玉00揉0y蚕=肌1.当30情29蒙e-趴10To眉Ma说tl雾ab诊(斑wl蛛it肢i3址1)To蛙Ma僻tl巷ab疯(烫wl游it柴i3虫2)3.辣用f摊mi蔬ns镇ea以rc幸h函牙数求宿解To恢Ma挥tl林ab疗(w恭li澡ti醒41欲)输入肺命令抄:f=脂'1懒00想*(坏x(看2)题-x尾(1划)^滴2)块^2央+(贤1-芝x(其1)师)^僻2'繁;[x翼,f灰va姑l,宪ex冈it垫fl汗ag析,o佳ut活pu肚t]帐=f帮mi贡ns记ea皂rc飘h(毙f,谨[站-1旦.2帖2删])运行胸结果楚:x封=1卸.0兽00踩0肠1瞎.0茂00除0fv与al修=母1.断91侧51谱e-衣01隔0ex锋it掠fl拨ag璃=妙1ou渐tp翠ut拥=it珠er估at魂io精ns军:形10料8fu蔬nc艇Co旋un滔t:遍2朝02al仔go昂ri绘th机m:厉'需Ne站ld威er狂-M第ea碗d归si漂mp滔le圣x茫di妨re帽ct树s狱ea僻rc魄h'用M吨AT服LA仿B软赏件求切解,跌其输氏入格杜式如届下:1.企x敞=q童ua怨dp妹ro瘦g(亮H,钞C,耽A,副b)恳;2.排x辽=q招ua置dp型ro烈g(仇H,刮C,姥A,唇b,幕Ae夜q,奋be雕q)朴;3.净x耀=q嗽ua泥dp璃ro烧g(钩H,狠C,绵A,攀b,稿Ae震q,娘be长q,继VL替B,派VU菌B)帖;4.张x稠=q透ua标dp奋ro没g(吹H,梦C,腹A,转b,厚A炸eq访,b过eq涨,说VL搁B,溜VU火B,看X0);5.份x时=q故ua徒dp唱ro用g(撑H,制C,恳A,叠b,唯A奸eq来,b乔eq织,饭VL筋B,勉VU转B,潜X0,o咬pt耍io如ns独);6.罗[匪x,勾fv怨al典]=郑qu甚ap情ro粘g(块..晋.)把;7.果[鞋x,裁fv泥al挺,e共xi打tf悼la绪g]杯=q丙ua蛛pr捡og弊(.婚..榨);8.荒[眠x,背fv把al阶,e胁xi它tf免la阅g,猫ou镇tp缸ut康]=么qu胀ap鱼ro俘g(昂..触.)掌;1、凝二次团规划例1mi带n鬼f(凑x1,x2)=雹-2链x1-6缠x2+x12-2脸x1x2+2母x22s.命t.妥x1+x2≤2-x1+2兄x2≤2x1≥0供,怠x2≥0MA迷TL蒙AB暂（y迎ou适h1撇）1、写成松标准构形式：2、输入粪命令：H=俘[1首-俯1;竹-耗1浪2]响;c=类[-需2愉;-讨6]缝;A护=[企1边1;闸-双1阀2]译;b妙=[晕2;天2]辰;Ae秀q=期[]员;b在eq里=[界];拼V扮LB干=[炸0;蚊0]灵;V中UB算=[抬];[x环,z傻]=薪qu许ad述pr绣og喘(H险,c任,A塔,b班,A铸eq键,b荣eq显,V分LB茎,V县UB皆)3、运算觉结果为：x乏=0败.6们66版7戏1她.3约33朝3消z属=艘-8委.2淋22欲2s.t.1.首先淘建立列M文棚件fu征n.根m,定义晒目标询函数套F（嫩X）忆:fu召nc巨ti阳on谎f用=f康un秘(X眯);f=捕F(搏X)铁;2、城一般鹅非线验性规输划其中X为n维变每元向葵量，G(朗X)与Ce无q(载X)均为户非线捧性函加数组帽成的粉向量篇，其趋它变要量的扣含义康与线是性规匆划、览二次玻规划床中相充同.延用M依at欧la启b求厉解上驱述问眯题，乖基本月步骤豆分三扯步：3.推建隙立主宜程序造.非旷线性然规划肃求解顾的函果数是指fm递in萌co柔n,立命令千的基僚本格暗式如掩下：(1答)x=fm恢in惊co努n(‘侦fu揪n’再,X0,A畏,b永)(2顽)x=fm鸽in划co灰n(‘细fu吴n’匀,X0,A肉,b把,A触eq构,b做eq栗)(3杰)x=fm叶in巷co窝n(‘捉fu昨n’草,X0,A喉,b多,本Ae腾q,灶be蚁q,皂VL右B,着VU颂B)(4悼)x=fm衰in笛co姓n(‘么fu目n’掘,X0,A锋,b肆,A蜻eq累,b瞒eq鼠,V传LB振,V柱UB肿,’虫no铃nl惕co蔬n’驼)(5扬)x=fm姐in滩co卫n(‘行fu话n’沾,X0,A坡,b牙,A嘉eq梦,b喝eq栏,V供LB院,V断UB悼,’粉no挣nl差co膨n’劫,o含pt渐io侍ns震)(6岔)[x丑,f劝va俱l]串=fm终in逼co馋n(最..解.)(7宋)[x伙,f成va茎l,脚ex幸it哗fl忙ag春]=fm甚in病co庸n(阅..芒.)(8遥)[赔x,欲fv树al意,e衰xi尚tf音la遮g,章ou邻tp杯ut坛]=fm兆in先co托n(遵..穷.)输出脆极值排点M文件迭代拦的初冈值参数侮说明变量鹅上下角限注意逮：[1衬]央fm晴in淋co肤n函男数提屿供了马大型辱优化躲算法驳和中壮型优梦化算早法。牢默认渗时，台若在封fu肃n函浇数中车提供厚了梯法度（进op匆ti应on茧s参敞数的监Gr增ad健Ob舌j设绳置为胀’o剥n’芹），西并且渔只有婚上下斑界存月在或带只有差等式寨约束挥，f办mi节nc滋on筑函数嘱将选舍择大自型算否法。衡当既搞有等震式约验束又速有梯烤度约写束时量，使味用中居型算资法。[2杜]即fm绑in醒co杯n函牢数的帐中型辆算法茄使用甜的是钢序列随二次惠规划押法。吨在每鹅一步榆迭代乌中求叉解二糖次规缺划子极问题皂，并望用B研FG意S法雀更新领拉格踩朗日妹He忠ss抖ia挖n矩遮阵。[3源]霉fm孙in躁co杆n函录数可崭能会泉给出漫局部絮最优篮解，初这与吃初值X0的选河取有房诚关。1、写成标准形式：

s.t.

2x1+3x26s.tx1+4x25x1,x20例22、先建现立M痛-文千件太fu鱼n3塑.m床:fu肠nc喝ti惕on伸f侨=f轮un粪3(耀x)搅;f=己-x布(1闹)-裹2*济x(稻2)冤+(乞1/左2)慨*x窜(1围)^贞2+赵(1还/2捎)*竿x(趟2)扰^2MA抢TL浅AB屡(y模ou扣h2设)3、舱再建青立主阳程序猪yo尊uh爹2.西m：x0古=[汪1;特1]享;A=别[2套3角;消1野4]泊;喊b=脊[6漠;5回];Ae瓜q=畅[]泛;b言eq鸟=[轮];VL振B=阀[0剪;0去];茄V需UB卸=[蝴];[x界,f驾va挪l]货=f咸mi嫁nc狠on兄('嫌fu阁n3湖',扁x0运,A堪,b妹,A店eq摆,b宽eq渗,V线LB泰,V申UB令)4、运算增结果爸为：x反=香0.券76纹47锋1粱.0凉58快8fv撤al锦=口-柔2.诵02墨941．先建搁立M煎文件今f堆un沈4.歉m,定义搭目标鱼函数和:fu姨nc刻ti掠on略f森=f篇un袖4(宵x)叮;f=森ex冒p(僻x(嘉1)摊)*(埋4*喊x(根1)赞^2欲+2茶*x己(2今)^仆2+乡丰4*满x(眼1)羊*x掏(2滩)+锤2*兴x(矛2)协+1疾);x1+x2=0s.t.1.5+x1x2-x1-x20-x1x2–10

0例32．钥再建研立M祥文件奋my督co少n.蔽m定突义非浑线性戏约束件：fu愿nc降ti丝式on久[联g,敞ce俭q]庄=m横yc和on宪(x愉)g=赢[x歼(1抛)+栽x(堵2)市;1盟.5词+x眉(1切)*驳x(罩2)迎-x临(1劣)-陈x(菌2)裤;-尚x(霸1)倒*x兆(2层)-邻10歪];3．今主程叉序y赖ou镜h3乓.m少为:x0济=[携-1垂;1拼];A=枪[]垒;b辜=[连];Ae狮q=伪[1俭1洪];骗be光q=柴[0饱];vl旧b=本[]铲;v贵ub攀=[事];[x仪,f分va办l]清=f蕉mi锈nc由on腥('赞fu市n4侦',成x0张,A搅,b平,A锦eq慕,b哭eq杯,v断lb蜓,v慌ub搁,'穿my奥co蓝n'摸)MA迫TL坊AB赠(y睁ou抵h3厨)3.运算廊结果惕为：x稀=踢-1沟.2晚25妥0高1歪.2辈25为0fv诱al牺=嚷1肾.8命95率1例41．唯先建皱立M伏-文砖件f旅un吗.m择定义葬目标落函数棍:fu候nc傻ti衡on筑f仓=f犹un清(x峰);f=帽-2夸*x欣(1耻)-宏x(勇2)锈;2．柔再建忙立M鼻文件林my苍2.坝m定输义非扫线性怜约束问：fu信nc钩ti呈on仔[恶g,傍ce狗q]帖=m声yc恶on悦2(庄x)g=加[x境(1营)^顷2+丢x(贺2)误^2席-2慕5;掀x(探1)纷^2戒-x鲁(2拖)^恐2-弹7]锦;3.晚主圾程序榆fx玻x.笛m为牵:x0姓=[作3;源2.悼5]醉;VL港B=张[0必0旨];笋VU丘B=欣[5咽1肝0]背;[x寇,f座va鼓l,伍ex兰it彻fl渠ag者]=f钓mi际nc艰on挺('评fu筒n'浴,x苍0,愚[]亭,[羡],险[]鹊,[宗],元VL骆B,墨VU期B,理'm专y2江')MA露TL念AB酿(f经xx猫(f盒un柔))4.尸运滑算结港果为贞:x随=4.漠00捧003.葛00文00fv悼al赢=贤-1恒1.里00厨00ex捷it醒fl惜ag罪=柜1ou佳tp为ut荐=it世er子at恩io涨ns嫁:察4fu求nc名Co全un鸣t:馅1晴7st轰ep沾si稳ze尖:负1al百go亡ri政th匙m:悼[艇1x投44旱c肠ha倘r]fi孔rs巡寿to河rd私er磨op喘t:乱[谨]cg锐it投er探at轿io零ns监:献[]返回动盏态纺规焰划(D夕yn灰am妄ic之pr接og限ra访mm疯in及g)动态目规划凳的基胞本思椅想最短所路径买问题投资旋分配乓问题背包企问题动态夫规划崭是用米来解表决多访阶段护决策油过程战最优屈化的值一种佣数量投方法者。其的特点浇在于班，它剩可以届把一星个n烛维才决策职问题效变换术为几定个一佳维最帐优化能问题鬼，从森而一板个一从个地挥去解呼决。需指劳出：团动态泽规划担是求除解某带类问潜题的抛一种明方法巧，是卧考察拉问题助的一态种途牙径，僚而不广是一辨种算次法。鼠必须权对具枪体问列题进膨行具路体分妹析，奏运用辱动态中规划识的原菠理和项方法早，建宪立相粗应的核模型怒，然抵后再猜用动款态规喘划方清法去英求解苹。即在肠系统嘱发展输的不只同时宗刻（址或阶怜段）铸根据析系统帆所处叫的状植态，趋不断毁地做约出决芳策；每个风阶段辣都要吊进行决策,目撇的是庆使整头个过栏程的祖决策姥达到逆最优俊效果届。动态惊决策塘问题纲的特筹点：系统继所处智的状已态和寸时刻绪是进雾行决岩策的挖重要撑因素徐；找到棍不同挥时刻沟的最袍优决从策以门及整懒个过骂程的昆最优燥策略蹈。多阶淋段决规策问像题：是动最态决菌策问佛题的金一种搏特殊轮形式渐；在多药阶段斩决策盼过程歇中,壁系统监的动迁态过柳程可粥以按事照时休间进或程分阅为状态相互联系而又止相互区别的各世个阶段；多阶医段决职策问阴题的册典型锣例子酸：1蚁.生产票决策考问题：企顷业在姨生产纺过程谋中，旨由于态需求欠是随地时间吸变化配的，桌因此竟企业如为了邪获得引全年害的最泄佳生仓产效随益，外就要健在整黄个生仇产过芽程中自逐月寇或逐脂季度杠地根据集库存兰和需颂求决寨定生木产计毯划。2.机器或负荷预分配颠问题：某庸种机四器可蛛以在亏高低鸣两种巷不同需的负警荷下把进行斜生产嘱。在副高负会荷下节进行萍生产矛时，足产品纳的年迷产量g和投互入生两产的肢机器寸数量u1的关槐系为g=g(u1)12n状态决策状态决策状态状态决策这时居，机角器的候年完培好率犁为a，即本如果纯年初旋完好淋机器馅的数此量为u，到税年终软完好舰的机继器就盾为au,毕0<a<1冤。在低吃负荷廉下生葛产时阁，产问品的牙年产岂量h和投滚入生熄产的爪机器盖数量u2的关稳系为h=h(u2)假定罢开始腾生产视时完赴好的韵机器磁数量到为s1。要你求制智定一碰个五画年计糕划，舰在每邻年开牲始时收，决戏定如它何重机新分吴配完絮好的件机器敏在两倚种不喊同的晴负荷僚下生刚产的竞数量报，使柴在五短年内拴产品肌的总瞒产量贿达到扯最高朵。相应后的机坐器年杜完好欠率b,哨0<b<1同。3.杯航天鞠飞机富飞行心控制狮问题芒：由击于航愚天飞含机的待运动栋的环绍境是艘不断尚变化夸的，相因此餐就要响根据爱航天爬飞机撇飞行彻在不胞同环位境中柿的情凶况，铅不断够地决凡定航冲天飞息机的骑飞行队方向模和速矩度（变状态附），走使之仗能最劫省燃断料和思实现丘目的偶（如谨软着患落问誉题）森。不包固含时触间因基素的声静态登决策垃问题菜（本裤质上葡是一猫次决梯策问乱题）割也可弊以适括当地鲁引入始阶段虫的概堤念，梦作为杆多阶焦段的闭决策撞问题曲用动怖态规弟划方慎法来颤解决纹。4.线性垃规划膝、非盲线性搞规划评等静穗态的苏规划策问题钟也可屈以通苦过适你当地劳引入甜阶段垂的概寒念，恶应用扭动态忌规划朝方法绝加以龙解决该。5.最短句路问摇题：给熔定一您个交崭通网稳络图塞如下扣，其促中两饮点之影间的件数字涌表示营距离坛（或吼花费央），给试求薄从A点到G点的冻最短州距离威（总凯费用添最小肺）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643（一泡）、斗基本喷概念1、障阶段初：把一竹个问留题的映过程日，恰记当地潜分为必若干申个相暴互联科系的阶段，以米便于廊按一穴定的屡次序故去求技解。描述烫阶段赏的变脑量称广为阶段纷变量。阶挽段的支划分闲，一持般是泡根据独时间滑和空针间的葱自然虑特征傲来进嫁行的也，但领要便迷于问漏题转冒化为渣多阶续段决坝策。2、弓状态事：表歼示每夹个阶兔段开学始所笼处的自然即状况酱或客参观条辛件。通苏常一啄个阶炼段有星若干滑个状随态，非描述巧过程圈状态挡的变低量称庙为状态辅变量。年、月、路段一个稠数、捏一组羊数、来一个分向量状态拔变量侮的取完值有改一定裙的允衣许集莫合或服范围怠，此查集合影称为状态坚允许旧集合。一、肺动态房诚规划舍的基养本思呈想3、竿决策岁：表缓示当长过程际处于渗某一恭阶段舟的某午个状长态时句，可集以作斤出不咽同的李决定衔，从讯而确城定下笼一阶湾段的览状态，这种徐决定畏称为决策。描述呆决策奔的变已量，拣称为决策丧变量。决荷策变邪量是搁状态恢变量曾的函吨数。秒可用耕一个挑数、冶一组哗数或绒一向堆量（张多维擦情形飞）来吴描述宗。在实抖际问焦题中家决策具变量宣的取纺值往