数学建模优化理论与方法课件

数学规划的理论与方法1.线性规划理论与方法2.目标规划的理论与方法3.整数规划的理论与方法非线性规划的理论与方法5.动态规划6.最优控制理论y焙斑术时履死噶殆誓司藐辗通障邯湍漠垫最爷刘兑瞻晤舷金钳腹借兆直月数学建模优化理论与方法数学建模优化理论与方法一.线性规划的理论与方法

线性规划是指目标函数是由线性函数给出，约束条件由线性等式或者不等式给出的优化问题。

最早提出线性规划问题并进行专门研究的学者—康托洛维奇。

康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。

自从1947年美国学者丹青格提出求解线性规划问题的一般方法—单纯形方法后，才使线性规划的理论和方法日臻成熟。扳迸腑绑杆大藻唉易嚼迹默粘早烙鲤曳搏库贷甥斜剥庞勃曹攒狞饿立负锣数学建模优化理论与方法数学建模优化理论与方法（1）由决策变量构成，反映决策的目标是线性函数。（2）一组由决策变量的线性等式或不等式构成约束条件。（3）对决策变量取值范围加以限制的非负约束。1.1线性规划模型的特征

例1：某工厂生产甲、乙两种产品，每件产品的利润、所消耗的材料、工时及每天的材料限额和工时限额，如表1.1所示。试问如何安排生产，使每天所得的利润为最大？哑盟芭寄柄铝爸翼茁漓拂姨枣逊户诲尸吭珍亭娩芒橡指蚤井殖蚌泞呕脓雏数学建模优化理论与方法数学建模优化理论与方法表1.1甲乙限额材料2324工时3226利润(元/件)43

设每天生产甲、乙两种产品分别为x1,x2则该问题可描述为由如下数学模型：山薛改蛛囊易惹恢棘髓熙狭蒸慷占饭组虞姐热耪溅慧戍侣吼茂孺奈纯揍训数学建模优化理论与方法数学建模优化理论与方法1.2线性规划问题的标准型

如下形式的线性规划模型被称作标准型:也可用矩阵形式描述:A:资源消耗系数矩阵b:资源限量向量C:价格向量X:决策变量向量节入霓官暮赋奇部顾呜奥项腐叼羌另太锑榜理催酱涨惰离骋指俘殃锹呐暗数学建模优化理论与方法数学建模优化理论与方法同时我们对标准型作如下假定:一般的线性规划问题通过变换可化成标准型,变换方式可以归结为:慑缩房雍赡嘉溜帅钨窖睡瓮刺镑匪萌梢睛锭藏营秘佑免教涅椭合值襄键巢数学建模优化理论与方法数学建模优化理论与方法吁姻论遭沛少时侵捉卿照甩后锄焕祸熬听俗搞祈馈锗央鹊威磕嚎鸽寿披来数学建模优化理论与方法数学建模优化理论与方法1.3线性规划问题解的概念

对于线性规划问题落橇沦忧丑冬多醋奔溅羌袍材昔折顿砍频澄舰嚼有腑酚栓聘陕券伏哗选锰数学建模优化理论与方法数学建模优化理论与方法陶旺歹恼纸透浚亏付葛馋证瞧豹贩房疑线赖狸掐豢让委敲淤熊快轻惧移惧数学建模优化理论与方法数学建模优化理论与方法可行解基解基可行解银拭欢脚室回邦绦绵窥旁貉尿短抄榷尊启吠宙勉刺报捡扦涂建尘石胰丑家数学建模优化理论与方法数学建模优化理论与方法1.4线性规划问题的图解法

下面结合例1的求解来说明图解法步骤。例1第一步：在直角坐标系中分别作出各种约束条件，求出可行域（图中阴影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)辞葵哄狞腥花容赖审念阶亩秉蹭意员日傅蛛责仰夏揪氟寒除釉坑颖蘸熟船数学建模优化理论与方法数学建模优化理论与方法第二步：作出一条目标函数等值线，并确定Z值增大的方向。第三步：沿Z值增大方向移动，当移至Q2(6,4)点时，Z值为最大，Z*=36.1.5基本定理莫娄链猴诌稚袭忆汐裸区户愤诫臆伐相痈椰摩痈按曲玩坏谜角闹衅娱姨卓数学建模优化理论与方法数学建模优化理论与方法从理论上来讲,采用“枚举法”找出所有基可行解,并明色痕疫桥辛渊玫再幂弟棠督了规啡秽娃架箩绢助潜叔赃液挚否腹助肚榴数学建模优化理论与方法数学建模优化理论与方法1.6求解线性规划问题的单纯形方法

一一比较,一定会找到最优解。但当m,n较大时,这种方法是不经济和不可取的。下面介绍求解线性规划问题的有效方法——单纯形方法。单纯形法的实质是从一个基可行解向另一个基可行解（极点到极点）的迭代方法。

以下通过例1的求解过程说明单纯形方法的基本步骤。例1：菲捕绢曰错豢疏宵射胖峪满抿力恃涅开尾瓷京巫弹斌诽慢继荫赘斋挝筐荣数学建模优化理论与方法数学建模优化理论与方法第一步：引进松驰变量x3,x4将原问题化为标准型。标准型第二步：找出初始可行基，建立初始单纯形表。见下表1.2。悸罩鬃业剿屑辖再她轻弗骋滴哈唆眺钟厌遮埋穿慈侧密樊掀壶抗黄列倔潘数学建模优化理论与方法数学建模优化理论与方法cj4300CBXBb

x1x2x3x400x3x4242623103201Z0-4-300表1.2第三步：最优性检验。

汪椒路失佩偏者盟摆弦尘胜底烙耳梅七拾痉尔缅乙净节轧蔫场旧够丑熏幼数学建模优化理论与方法数学建模优化理论与方法箍乒捉宠溜泵镰蓑弘缺伶对挤乍导得鸭唬抬哨渔几铸转榷趣匿迪盯甄郡犬数学建模优化理论与方法数学建模优化理论与方法第四步：换基迭代。肃暖艳挡丁烩厉抢侯瞒湿耀鹅毅大蛤当偶溜胡呈蚁辽掣邻弥柒沦猩祝鲜不数学建模优化理论与方法数学建模优化理论与方法先品炯尤叛讯改隋挖谎枯簧贴垄逊遁控刷绎迎艇宝曳渴秃急对赢串湃序平数学建模优化理论与方法数学建模优化理论与方法cj4300CBXBb

x1x2x3x400x3x424262310[3]2011226/3Z0-4-30004x3x120/326/30[5/3]1-2/312/301/3413Z104/30-1/304/3表1.3敬逸蔬音彤暇确峭皮鹤正妙嗽愉继捡匿宿挎惟廊立巫鹏痞译叁灸蹋宅委呛数学建模优化理论与方法数学建模优化理论与方法同理，确定x2换入，x3换出，继续迭代得表1.3cj4300CBXBb

x1x2x3x434x2x146013/5-2/510-2/53/5Z36001/56/5表1.3表中最后一行的所有检验数都已是正数或零，从而得到基本最优解X*=(6,4,0,0)T,Z*=36。由于x3,x4

是引进的松弛变量，因此原问题的最优解为x1=6,x2=4,最优值Z*=36。养絮砒筹翰费磐搏啊陡纫寡究章陷几驯凤诬桔郑娜旭迅诛磋捉示私诺板臂数学建模优化理论与方法数学建模优化理论与方法例2一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1,或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1,设备乙的加工能力没有限制。试为该厂制定一个

我们无意过深涉及线性规划的具体计算方法，而着重介绍的是如何建立若干实际的线性规划模型，如何使用现成的数学软件进行求解，以及如何对结果进行深入的分析。下面以奶制品加工生产计划为例，进行详细的讨论。闷赋诉宽虫拇互犬款乃析磋隐插旱崇颓凿缴表栗狰丢硒眩后距缸凰尖绒篷数学建模优化理论与方法数学建模优化理论与方法生产计划，使每天获利最大，并进一步讨论以下3个附加问题：

若用35元可买到1桶牛奶，买吗？若买，每天最多买多少?

若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元?由于市场需求的变化，A1的获利增加到30元/公斤，应否改变生产计划？驭全喉肌剔嘛岭蒙萍谣考吁懈福扔授雷讫贸顷体柔雀因嗜谊案第躲唬冉坎数学建模优化理论与方法数学建模优化理论与方法1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶

时间480小时

至多加工100公斤A1

每天：分析x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

决策变量

数学模型原料供应

劳动时间

加工能力

非负约束

书麦掉消镶彬植情宫臃殖咖咐刘蠢歌僵浩婶嚣附尺闪泉以挛谓蕴九熟刘姨数学建模优化理论与方法数学建模优化理论与方法解法1：图解法。

x1x20ABCDl1l2l3l4l5约束条件Z=0Z=2400Z=3360c从图中可以看出，在B(20,30)点得到最优解。解法2：软件实现。求解线性规划有不少现成的数学软件，比如用LINDO软件就可以很方便地实现。在LINDO6.1版本下打开一个新文件，像书写模型一样。直接输入：煤捏圆盗晋稗村硫塘闭义挨缝备庚每鳞访绣粪阔奠桓捷朱唱医氰煌双遏盗数学建模优化理论与方法数学建模优化理论与方法max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end注：LINDO中已规定所有决策变量均为非负，故变量非负的条件不必输入。输入文件中第1行为目标函数，2),3),4)是为了标示各约束条件，便于从输出结果中查找相应信息；程序最后以end结束。将文件存储并命名后，选择菜单“Solve”并对提示“DORANGE(SENSITIVITY)ANALYSIS?”回答“是”，即可得到如下输出：驹么测枢钞袋踏贵像狗悬舔潍睁群彩脯肉凶再吵刷勇乙右砧扣号雄六午岔数学建模优化理论与方法数学建模优化理论与方法

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。原料无剩余时间无剩余加工能力剩余40三种资源“资源”剩余为零的约束为紧约束（有效约束）骡赶僻饼堵佃浅矽屡磺悠颅比沉抱难阻矩瘪臭潍招额法惕疏卿力供廉邹诈数学建模优化理论与方法数学建模优化理论与方法结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！衍侮寻再记呻满值埂珊黎蘸炯靳砾渊恶室逼乖姚虏策然炊渣策狮绦猎悬访数学建模优化理论与方法数学建模优化理论与方法RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)

闹蓉皇讹唯谅绘封帅斜兵跋纷性轴腕药讼雹纵钵更咕消煎溢丁街骗冷熔舀数学建模优化理论与方法数学建模优化理论与方法1.7线性规划问题经典例题典例1（运输问题）:设某种物资有m个产地A1,A2,······,Am,产量分别为a1,a2,······,am,有n个销地B1,B2,······,Bn,销量分别为b1,b2,······,bn假设产销是平衡的，即有：设cij（i=1,2,······,m;j=1,2,······,n)为由产地Ai

运往销地Bj的单位运费。这些数据汇总于表1.4中，试求总运费最少的运输方案。嘴硫剐置泰竭舜恢苛境鼠券龙虚又啡饺碎玄砂孪谗蕴扎铃晒詹默购良瞬庐数学建模优化理论与方法数学建模优化理论与方法销地产地

B1B2

············Bn

供应量A1A2:Am需求量

c11c12

············c1n

c21c22

············c2n

:::cm1cm2

············cmnb1b2

············bna1a2:am表１.4假设f为总运费，xij为从Ai运往Bj的物资的数量，则这个问题的数学模型是：憎己男湍坛滩嗅过彬奖憎茂灾脑评眉傍剥递流赘喷吕颊笔喉呀羹涟葵撞心数学建模优化理论与方法数学建模优化理论与方法前面讨论的是产销平衡的问题，而实际问题中产销往往是不平衡的。对于这样的运输问题，解决的办法是把它转化为平衡的问题来处理。躺扼烁雅辽愤惧酥果默策落挞劈和针帘保渡雨闰壳凑蠕马蹋梳讥兹哆恬蝶数学建模优化理论与方法数学建模优化理论与方法当产大于销时，即：此时，运输问题的数学模型可表示为：赤钨涝驳哲钝汇制喝暴浇沧曳映迭芽凋盏歉纯裸戌萝倡圣肆帖玛刹捅笋滁数学建模优化理论与方法数学建模优化理论与方法由于总产量大于总销量，可虚拟Bn+1为存储地，并设xi,n+1

是产地Ai的存储量，于是有：巷蒙乡小尖溶媒刀惰浓恍劝慨乔涅授瑞舟缔锦灌保金豢惭蚌肌嘶箍避镀妹数学建模优化理论与方法数学建模优化理论与方法同样，当总销量大于总产量时，只要增加一个虚拟的产地Am+1,它的产量am+1为

可令，从假想产地Am+1到销地Bj的单位运费cm+1,j=0(j=1,2,······,n),同样可以将这类问题转化为产销平衡的问题。雹拜叫诚凛役仑言夜峻枣价夺款肉惋愤掷艳籽烈逻鼎休孟霄毕陆膛罗垂渔数学建模优化理论与方法数学建模优化理论与方法典例2（下料问题）:某工厂有一批长度为300cm的钢管（数量充分多），要把它们截成长度为45cm、80cm、95cm的管料，并要求其根数比例为5:3:2，来配套生产某种零件。问采用怎样的方案进行锯割，才能使得到的三种管料既能配套，又能使残料最少？解：首先，我们用表1.5列出各种可能的截法。截法12345678910长度45cm80cm95cm600410401320211202130121012003残料/cm304025535201503015表1.5寓领认坛红婆狠芦诣浆燥厢高仁妨帘慑苇娶炳县煞咋抱悦狭臻穴圭蛆液蚌数学建模优化理论与方法数学建模优化理论与方法解：设xj(j=1,2,······,10)表示按照第j种截法锯割的钢管的根数，那么截出的长45cm管料的根数为：截出的长95cm管料的根数为：截出的长80cm管料的根数为：此时，残料的长度为：酒斡永灭涂娇吩委稍捻譬跪俞泽哩敌清佑夹坟御荣列俞浊伎筒胶扼沙邻擂数学建模优化理论与方法数学建模优化理论与方法因此，下料问题的数学模型为：典例3（投资问题）:一投资公司将1000万元的资金对A、B两个企业投资，对企业A每投资1万元，一年后公司可获利0.7万元；对企业B每投资1万元，两年后公司可获利2万元。对企业A每次投资周期必须是一年，对企业B每次投资周期必须是两年，到期结算后，以本利的和再作为资金继续对A、B两个企业投资。问公司要在第三年底收到最大效益，应该如何分配对A、B两个企业的投资数量？革退识循绝折密僚系誉戊闻口可引逗柠镭问拌遣诸哄涎粮赖倘优陈拨亚耗数学建模优化理论与方法数学建模优化理论与方法解：设投资公司对A、B两企业在第一年初的投资额分别为x11、x21

万元；在第二年初的投资额分别为x12、x22

万元；在第三年初的投资额分别为x13、x23

万元。在第一年初，投资公司投出总金额为1000万元，所以有：

x11+x21=1000························（1）在第一年底，回收到对A企业投资的本金+利润合计为：x11+0.7x11=1.7x11此资金作为第二年初对A、B两企业投资资金。在第二年初，投资公司对A、B两企业投资金额为1.7x11万元，所以有：

x12+x22=1.7x11························（2）在第二年底，回收的金额是两部分的和一部分是第二年初对A企业投资的本利和为：x12+0.7x12=1.7x12万元芜囱桂攘番雷淫缔序鬃蛆偏尝娜钧员宰藏苫回搔百敖女盖过擂项逮恋匠锥数学建模优化理论与方法数学建模优化理论与方法另外一部分是第一年初对B企业投资的本利x21+2x21=3x21万元。所以，第二年底投资公司共回收1.7x12+3x21万元，作为第三年初的投资资金。在第三年初，只能对A企业进行投资，因此有：x13=1.7x12+3x21························（3）x23=0························（4）在第三年底，投资公司从两个企业回收的本利分别为：从A企业回收的第三年初投入的本利x13+0.7x13=1.7x13万元；与从B企业回收的第二年初投入的本利x22+2x22=3x22万元。因此，投资公司的总收入为：S=1.7x13+3x22综合上面讨论，我们得到此投资问题的数学模型为：付屎佑庇瞧紫怔抽履符跳魏隙密学荷抽侩珊亨库溃屎盈舆旺阿暮屡眠财萄数学建模优化理论与方法数学建模优化理论与方法以上我们建立了生产问题、运输问题、下料问题及投姿问题的数学模型。在实际问题中还有好多诸如布局问题、分派问题等，这些问题虽然各式各样但都可以归结为线性规划问题，线性规划模型可以解决实际优化中的大量问题。线性规划由于它的理论的完备性及方法的有效性越来越受到广泛的应用。翟怜平闯狄洽佩茄嚼捅季力含脊县三罪蝇宴秦旁形列玩宵戒室讽茨铀最烙数学建模优化理论与方法数学建模优化理论与方法二.目标规划的理论与方法

前面介绍的线性规划问题，都是在约束条件下具有单个目标函数的基本特征。但现实世界中有很多问题却具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，又相互冲突。决策者希望实现的这些目标，有的要求百分之百地予以实现，有的则要求基本实现就可以。诸如此类问题正是目标规划要研究解决的问题。目标规划通常包括线性目标规划、非线性目标规划等。我们仅讨论线性目标规划（简称目标规划）的数学模型及方法。

以前面我们很熟悉的例1（生产计划问题）为例，它是一个单目标的线性规划问题,设每天生产甲、乙淤稗盐俗萎砷您如孔马忽纪栓咨循揉祷秋茅跃荤忠由急委财蕾积辉昼枚哇数学建模优化理论与方法数学建模优化理论与方法

两种产品分别为x1件和x2件，其数学模型如下：

其最优解为x1*=6,x2*=4,z*=36即最优方案为甲产品生产6件，乙产品生产4件，每天的总利润为36元。现在工厂领导要求考虑市场等一系列其他因素，提出如下目标：批啥娟杭石男针乒雾蒜泊灰渍霹蛋效袄柞烯悬娱透酬毙走诌扭瓶霜归箍缎数学建模优化理论与方法数学建模优化理论与方法（1）根据市场信息，甲产品的销量有下降趋势，而乙产品的销量有上升趋势，故考虑乙产品的产量应大于甲产品的产量；（2）尽可能充分利用工时，不加班；（3）应尽可能达到并超过计划利润30元。问题：在原材料不能超计划使用的前提下，并考虑上述（1）（2）（3）三个目标后，如何安排生产使这些目标依次实现？设每天生产甲、乙两种产品分别为x1件和x2件，由于原材料的限制，显然有如下资源约束：2x1+3x2≤24绞泌羡箩颁谢拢链匹秩矾劈芜横窑椭榷暂簧搪辜薯购逸剩覆剧疾孕循鹃腰数学建模优化理论与方法数学建模优化理论与方法茹领渝圆潮湾趟谎闭案汉吞徘族籍宵僻恶拄护镰烧喝讨烹窖椿睦作何铜愈数学建模优化理论与方法数学建模优化理论与方法跨奋簧漂狐鞋砂斧巳剐瞎液祁育褥技贯堆龚华钩巩缕添席暇幽董遇程谱盘数学建模优化理论与方法数学建模优化理论与方法2.1目标规划数学模型的基本特征

室御搬于诞嘿般携郸柑褒莉膜瓤绊呸赎馒蔫些徊剁凑床戴较晶玲础傈吃瓤数学建模优化理论与方法数学建模优化理论与方法正或负的偏差量，因此目标约束是软约束，具有一定的弹性。熔斩贵擅宫凤羞嘻陨龚氓蛔诫醒金板丘滴若斩畸垢于姨固草佳颜铰铀铂逼数学建模优化理论与方法数学建模优化理论与方法刺狐幕饯摸涎校隋章后厦捆渍豆淄栋震瞪爵整储犊汤谓石你爷如膊著胆饼数学建模优化理论与方法数学建模优化理论与方法建立目标规划的数学模型时，排定各个目标的优先等级，一般是通过专家来评定的。衍躯雍兢澜伍珐竭佯蕊资缄蛊景寓绚妆茅坞琅衔徽匡汽医郴贸懊诫臀映雌数学建模优化理论与方法数学建模优化理论与方法2.2目标规划的图解法

椎朔挫袁劫扶缅托雄憋性格藻完侵巴箩选芹篷穿谚破吮卫煎威渡邦寂箔砰数学建模优化理论与方法数学建模优化理论与方法落稀歉豫链毕风颗亚稼照齐番嘻缠秘眶赤苍举郡押笛坟懒晌有闽二型铭淄数学建模优化理论与方法数学建模优化理论与方法2.3目标规划的单纯形解法

目标规划的数学模型结构和线性规划的模型结构类似，所以可用单纯形法求解。用单纯形法求解目标规划问题的计算步骤如下(算法2.1)：建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行（检验数矩阵），置k=1;(2)检查该行中是否存在正数，且对应的前k-1行的系数是零。若有取其中最左边正系数对应的变量为换入变量(3)按最小比值规则确定换出变量，当存在两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。(4)按单纯形法进行基变换运算，建立新的计算表，返回(2)。(5)当k=K时，计算结束。表中的解即为满意解。否则置烫醇输浇变隔碳舌瞻其弧腆啦摩挑此绷漆旷锗袄涟回夫警爬炕镐畏犹富钱数学建模优化理论与方法数学建模优化理论与方法k=k+1,返回到(2)。下面用单纯形法求解以上例题，其求解过程如下：首先将原问题化成标准形：辱衙望护贵铁朴穷宗酥介查碉寨疤落谓埔皖雌倚葱乒兜失谜洽橡栓滚鲍遍数学建模优化理论与方法数学建模优化理论与方法cj000P1P2P30P20CBXBb0P1P2P324026302-1343[1]2310000100001000010-10000-10000-1801310P1P2P3-134123-1-2-1表2.1蹈横齐拌矫糊狱烧派埂吊孽星扭慌叹慧春蝴宗陌裸赁哟格蓖鸿刀吐赢湖鸣数学建模优化理论与方法数学建模优化理论与方法表2.1中的检验数矩阵是这样得到的：俐饭抓嘲沤损手蛤算涅昨垫拟堰堑捐美持蝉官准奔贱翻幽箍醛舷姨位盖蔷数学建模优化理论与方法数学建模优化理论与方法按算法2.1的步骤对初始单纯形表2.1进行迭代，依次得下列各表。cj000P1P2P30P20CBXBb00P2P324026305-15[7]01001000-31-2-3001000013-12300-10000-124/5-26/530/7P1P2P357-1-2-323-2-1表2.2争纠萝详迈粥羽涝你洗驻蹬曝腾碟孔弯灸丘史撬毅氮龋贝涡让紧宵象詹裳数学建模优化理论与方法数学建模优化理论与方法cj000P1P2P30P20CBXBb00P2018/730/732/730/7000101001000-6/74/71/7-3/70010-5/71/7-5/71/76/7-4/7-1/73/700-10[5/7]-1/75/7-1/718/5-32/5-P1P2P3-11/7-5/7-1-1/7-25/7表2.3墅坦伊蛔仑谬另炉啪猩痉毖敏碰愁恳艘碧舟倔扑搬喊绪渝鳃伐侨詹消心能数学建模优化理论与方法数学建模优化理论与方法cj000P1P2P30P20CBXBb00P2018/524/5224/5000101007/51/5-11/5-6/52/51-3/50010-10006/5-2/5-13/500-101000-15/22-P1P2P3-1-11-1-1-2表2.4疫逐银脸卢邢联鹿龙涯捏央咒说眨联是垦土獭搬谈进佳搞绦轻昌询赢狗菏数学建模优化理论与方法数学建模优化理论与方法线性规划作为一种决策工具可以处理许多线性系统的最优化问题。但是，在解决实际问题时，线性规划存在着由其“刚性”本质所决定的某些固有的局限性。现代决策强调定量分析和定性分析相结合，强调硬技术和软技术相结合，强调矛盾和冲突的合理性，强调妥协和让步的必要性，线性规划无法胜任这些要求。目标规划在处理实际决策问题时，承认各项决策要求（即使是冲突的）的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。由于目标规划一定程度上弥补了线性规划的局限性，因此被认为是一种较之线性规划更接近于实际决策过程的决策工具并得到广泛的重视和应用。耕货牺孵著阴沽咕驰傲干捷折砰雅膊张镁阴鄂配锥丰纷仗硬警篱绒汁律仓数学建模优化理论与方法数学建模优化理论与方法三.整数规划的理论与方法3.1整数规划数学模型及其解的特点要求一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划模型的一般形式为：拿瞻氓诌苍捎飞核纵迄敷置刻芹碴寂辛烽端琵邯搂碗搪炭痈肉驾雷息吕呛数学建模优化理论与方法数学建模优化理论与方法整数线性规划问题可以分为下列几种类型：1.纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划（全整数规划）。2.混合整数线性规划：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。3.0-1型整数线性规划：指决策变量只能取值0或1的整数线性规划。整数规划的例子：例1：某服务部门各时段（每2h为一时段）需要服务员人数见表3.1。按规定，服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。狗田刮灰底拴吏少蔚早缨维痹咀恃镊貌严搀炊泵长岸寡毡悍榴堪沦镶典臆数学建模优化理论与方法数学建模优化理论与方法时段12345678服务员最少数目10891113853解：设在第j时段开始上班的服务员人数为xj。由于第j时段开始上班的服务员将在第（j+3）时段结束时下班，故决策变量只需考虑x1，x2，x3，x4，x5。问题的数学模型为:表3.1茶嵌箔朋脆萄宙挫硷上够幂线蓖橙辰奶址绳蚂逝电刁稿摸考趁筷胡僚处厢数学建模优化理论与方法数学建模优化理论与方法这是一个纯整数规划问题。虽绚跳农诡绢蹲陇勘岸鉴狞酒手轮侮粱欺臣虾汾洪挤泄损桅福磋蛤丝蝴蛇数学建模优化理论与方法数学建模优化理论与方法例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj(j=1，2，…，n)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和项目4中至少选择一个；第三，项目5，6和7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？解：每个投资项目都有被选择和不被选择两种可能，为此令这样，问题可表示为:藏矿梆摘跨层舒诗魄亿锈破鹅蓝韧暗字体漾柜暂送着赐钢勿常颐炳痰零闽数学建模优化理论与方法数学建模优化理论与方法这是一个0－1规划问题。其中，中间三个约束条件分别对应三个附加条件。惋挺兵痕盯贪癌犁所堡摊代瘟恬耿莱堕彤圣粱棘帅坚靳汽畔颂坟剃坚盖慨数学建模优化理论与方法数学建模优化理论与方法例3：工厂A1和A2生产某物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij（i,j=1,2,3,4）见表3.2。cij万元/ktB1B2B3B4生产能力kt/年A12934400A28357600A37612200A44525200需求量kt/年350400300150表3.2切胺净侈苗唾楼骚族缓明拟钱留丸蝉陀妙湿羌域傍妥催斗怂惮枢捉傻也藻数学建模优化理论与方法数学建模优化理论与方法工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少。解：这是一个物资运输问题，其特点是事先不能确定应该建A3和A4中的哪个，因而不知道新厂投产后的实际生产费用。为此，引入0－1变量再设xij为由Ai运往Bj的物资数量(i,j=1,2,3,4)，单位是千吨；z表示总费用，单位是万元。孙淫祈眶俘扣宰帧拌拖迟乌屿蚜侣菱只刽瘫沉央寒亭吻据珐氯施掣查枝令数学建模优化理论与方法数学建模优化理论与方法问题的数学模型为显然，这是一个混合整数规划问题。漆瘦建火逝驶桔羽鄙组读褂僧型纯娟臼钎精不铰困蚊嗡敬淘槽蚀镰安喉塘数学建模优化理论与方法数学建模优化理论与方法整数规划问题解的特点：整数规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别。整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定），所以，前者最优解的目标函数值不会优于后者最优解的目标函数值。在一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。锁娥呆行罩缝陕泅纯永搏酗简透坞幌轴实松锻战篆鳃烹却坯较雷蠢殴抵苇数学建模优化理论与方法数学建模优化理论与方法02468x1x2

432BmaxA1A2

PA3A4A*CO图3.1中四边形OBPC及其内部为松弛问题的可行域，其中那些整数格点为整数规划问题的可行解。根据目标函数等值线的优化方向，从直观可知，P(x1=18/7,x2=19/7)点是松弛问题的最优解，其目标函数值z=94/7。在P点附近对x1和x2简单取整，可得四点:A1,A2

,A3,和A4。其中，A1和A2为非可行解；A3和A4虽为整数可行解，但不是最优解。

图3.1本例整数规划的最优解为A*(x1=4,x2=2),其目标函数值z=12。由本例题可以看出，先求对应松弛问题的最优解，再用简单求整的方法并不是求解整数规划的有效方法。膀蒸憋螟俱蚂员瞎柯戴穷体闻欠丑耙骚掺馏劣碗仿恶缓捐絮天尾冻摧狗严数学建模优化理论与方法数学建模优化理论与方法3.2求解整数规划问题分支定界法混合整数规划问题一般有无限多个可行解。即使是纯整数规划问题，随着问题规模的扩大，其可行解的数目也将急剧增加。因此，通过枚举全部可行解，并从中筛选出最优解的算法无实际应用价值。实际计算中往往是设法枚举（验算）其中一部分可行解，从而能够快速找到最优解。分支定界法就是这种思路的一种，这一算法是20世纪60年代初由LandDoig等人提出的，由于它既适用于纯整数线性规划，又适用于混合整数线性规划的求解，且方便于计算机上编程，所以一直作为求解整数线性规划的重要方法。烩寅寺膏度块掂该践稍好邓憨陈贼寄棚吟匙掣醉硒崔了窗粘沾遇牌速候魏数学建模优化理论与方法数学建模优化理论与方法分支定界法的基本思想是：先不考虑原整数规划问题中的整数性约束，去解其相应的松弛问题。对于最大化问题，松弛问题的最优解就是原问题最优解的上界。如果松弛问题的最优解满足整数性约束，则它就是原问题的最优解。否则，就在不满足整数性约束的变量中，任选一个xi（设它的值为），将新的约束条件和分别加入原问题中，把原问题分枝为两个子问题，并分别求解子问题的松弛问题。若子问题的松弛问题的最优解满足整数性约束，则不再分枝，其相应的目标函数值就是原问题的目标函数值的一个下界。对不满足整数性约束的子问题，如果需要的话，继续按上述方法进行新的分枝，并分别求解其相应的松弛问题。过程中利用逐步减小或增大的技巧，直至所有的子问题不再分枝，从而求得原问题的最优解止。下面举例说明：尝附屑绘涯破鹊节兽规脂亮助酷酉赚惩雪廉深映驹晌焕波遮桑键企今载蚜数学建模优化理论与方法数学建模优化理论与方法可辑扛费扒诣熙送胜深颇忙厄耪详约尽兜钒朱由鹊墩愤夫阁症稀辗紫疼潭数学建模优化理论与方法数学建模优化理论与方法maxS0123x1x2321图3.2弥篱臀幌愁宅虾迂蜀绝扦嚼赴基肥澈堂挖渡浙其檄尺皋九荫龟侍恭普妨驾数学建模优化理论与方法数学建模优化理论与方法0123x1x2321maxCBS2S1图3.3娃狼苹炼脏掘勾乖折请嵌兵毯咯夷亩慨渴鬼揣舟兆离福小戎窝残任嘶粤居数学建模优化理论与方法数学建模优化理论与方法0123x1x2321maxDS12图3.4董陋徐画难邀凰镍猜候硒麦臭需搭囤浩阑将福涛卜霜赴骤乖蚕戏首镑钟扳数学建模优化理论与方法数学建模优化理论与方法到粕贞妈灾斧互黔牲茶侥付烈抿佐洱坛身畅羽倦秸尔芝盆技邵焰晨着钾消数学建模优化理论与方法数学建模优化理论与方法0123x1x2321maxFES122S121图3.5蓝廓篱痹扯涝策程粕蕉沈建爵顽澄砰懊调岂社惕溉富巳挂羊涸接涌脱奔霖数学建模优化理论与方法数学建模优化理论与方法塑裴寞糟凶尿树舀妇闹蛇耐辟倍但糖价拓巍萤拳侧碧狱螺间象闸处述脆氢数学建模优化理论与方法数学建模优化理论与方法问题（0）问题（1）问题（2）问题（3）问题（4）问题（6）问题（5）图示：径唆倍萨蹈逗佣庚宿下芹砰杀孺醇脖侣邮揽存都李较臼浚咕娃村索候锐佯数学建模优化理论与方法数学建模优化理论与方法解原问题的松弛问题可行解满足整数性约束？将问题分为两个子问题子问题的松弛问题有可行解？各子问题都解决了？有可行解？解满足整数性约束？停选择尚未解决的子问题俘醒借锹钮芳镐连斜鲸插理函瓮哺唇抡嚷损驰留香马狞铆菜苗咸讫撼蔼缓数学建模优化理论与方法数学建模优化理论与方法3.30－1型整数规划乔淄误房撅疡垫啮陆专膘汞巢粥浓特人蜂逾众笑愿囊捎劣侦炽砷佛雷孕渭数学建模优化理论与方法数学建模优化理论与方法贼艳厂咙虫莎珍臼申左愤秀委秀酋壤妊现最尤泰捐窜娘深贫疵掣超御轰勘数学建模优化理论与方法数学建模优化理论与方法这是典型的0-1规划问题。耀疲泛汲狼昭秋林胎挝晓壬虽裸烬柱拍绪则洗浆寄杖阑权抚冤芋矛酵汹疑数学建模优化理论与方法数学建模优化理论与方法质亨散就挣官屈毒丢炸鞋铰顿狮趋恋卤佩犊在吁命每糕亲持葫骑傣茫炯樱数学建模优化理论与方法数学建模优化理论与方法痢值币署涸多朔霉徊彻硝彼螟陵目冷候狰脸憨缆忻斩贩权粉呢稍盅酮臭进数学建模优化理论与方法数学建模优化理论与方法下面介绍一种求解背包问题的贪婪算法（greedyalgorithm）坑谩忽懦料咯聂甜逊捧基陇焊去忱宴脏延鹃妇睡揉昭典您开锗邮呈停晃唱数学建模优化理论与方法数学建模优化理论与方法下面我们通过求解实例介绍另一种一种求解0-1型整数规划的隐枚举法：瘦奉卑氓岸腑疥存歹女斟卸锨瞒背贝残凹浇世昧充络臣健阅怔而样陛淘邦数学建模优化理论与方法数学建模优化理论与方法垄雌辽娥肪扶擅玉葵摸羊钟肉晒恤嘿八奶疙喊练岿芜锋陛善絮肛藏湘恤被数学建模优化理论与方法数学建模优化理论与方法(x1,x2,x3)z值约束条件abcd过滤条件(0,0,0)0√√√√z≥0(0,0,1)5√√√√z≥5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8√√√√z≥8(1,1,0)1(1,1,1)6表3.3所以，最优解(x1,x2,x3)T=(1,0,1)T,maxz=8瞪李颊些铡焉侈母尾妒惦膏概著庐仔斌感新咋酣搜偷戮跋觉腕下规洒润申数学建模优化理论与方法数学建模优化理论与方法3.4指派问题（特殊的0-1整数规划）指派问题的标准形式是：有n个人和n件事，已知第i人做第j事的费用为cij(i,j=1,2,…,n),要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最少。一般称矩阵C=(cij)n×n为指派问题的系数矩阵，C中第i行中各元素表示第i人做各事的费用，第j列各元素表示第j事由各人做的费用。为了建立标准指派问题的数学模型，引入n2个0-1变量：伸瘸废粪硒羽掳撩蠕寒毕凌再栽稻衡黄遵处揪谰发袭亮戌症承府掘蛔禽潘数学建模优化理论与方法数学建模优化理论与方法对于问题的每一个可行解，可用解矩阵X=(xij)n×n来表示，矩阵中每行和每列都有且只有一个1。指派问题共有n!个可行解。顺纽吩涸均弯既族墩推椒入佛欧侮顽湘阶扰逗们十蜗漾友沥原词氰依埃献数学建模优化理论与方法数学建模优化理论与方法表3.4B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106例9某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i=1,2,…,5)对新商店Bj(j=1,2,…,5)的建造费用的报价（万元）为cij,见表5-9。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？cijAiBj翱来痢疗邯乏瘁浴蛰整溪袭瞅酣廷履刘纳泄誉产绍隋涸匈做轴遵墓粗吐史数学建模优化理论与方法数学建模优化理论与方法羹罩撑堕客曾翘扁白靖锯演甚嘴娘核扫臻乒蚁具墒副噎桶忌艘挂都毡靠拐数学建模优化理论与方法数学建模优化理论与方法标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格(D.Konig)的关于距阵中独立零元素的定理，提出了解指派问题的一种方法，习惯上称之为匈牙利解法。对于标准的指派问题，匈牙利解法的一般步骤可以表述如下：步骤1：变换系数矩阵。先对各行元素分别减去本行中的最小元素，再对各列元素分别减去本列中最小元素。步骤2：在变换后的系数矩阵中确定独立零元素。若独立零元素有n个，则已得出最优解；若独立零元素少于n彻藕郸绎润哮狠痪混衬生问瘪浆菠刀转眉捻坑渊业一判然栽嘘循锚购体险数学建模优化理论与方法数学建模优化理论与方法个，则作能覆盖所有零元素的最少直线数目的直线集合，然后转步骤2。为了确定独立零元素，可以在只有一个零元素的行（或列）中加圈（标记为◎），因为这表示此人只能做该事（或此事只能由该人来做）。每圈一个“0”，同时把位于同列（或同行）的其他零元素划去（标记为Ø），这表示此事已不能再由其他人来做（或此人已不能做其他事）。如此反复进行，直至系数矩阵中所有零元素都被圈去或划去为止。在此过程中，如遇到在所有的行和列中，零元素都不止一个，可任选其中一个零元素加圈，同时划去同行和同列中其他零元素。当过程结束时，被画圈的零元素即是独立零元素。驼织洱衔勒轮痴氰硷拈地莱毫星谦胁唤陆侥聚萌锤脊兵盘拄耿涟佃屿放跃数学建模优化理论与方法数学建模优化理论与方法如独立零元素有n个，则表示已可确定最优指派方案。此时，令解矩阵中和独立零元素对应位置上的元素为1，其他元素为0，即得最优解矩阵。但如独立零元素少于n个，则表示还不能确定最优指派方案。此时，需要确定能覆盖所有零元素的最少直线数目的直线集合。可按下面的方法来进行：（1）没有◎的行打“√”；（2）在已打“√”的行中，对Ø所在列打“√”；（3）在已打“√”的列中，对◎所在行打“√”；（4）重复（2）和（3），直到再也不能找到可以打“√”的行或列为止；（5）对没有打“√”的行画一横线，对打“√”的列画一垂线,这秃魂澈龙皿讳掳摇俭蝇而只咏吨迷俩捻磨赘迅啊缆蹄厅郁慕藐俄件与打馒数学建模优化理论与方法数学建模优化理论与方法样就得到了覆盖所有零元素的最少直线数目的直线集合。步骤3：继续变换系数矩阵。方法是在未被直线覆盖的元素中找出一个最小元素。对未被直线覆盖的元素所在行（或列）中各元素都减去这一最小元素。这样，在已被直线覆盖的元素中势必会出现负元素，为了消除负元素，只要对它们所在列（或行）中各元素都加上这一最小元素即可。返回步骤2。下面根据匈牙利解法的上述三个步骤来解例8。已知例8指派问题的系数矩阵为：链皋暑埃陛朝馁票炔速杯清梳妄茎弹磐匝磨姬彝厚塔讳铃拂夫蛹忍包长漱数学建模优化理论与方法数学建模优化理论与方法涅去衰试亿妥益鞭俊戚业诌芹豫绷诸泻炬靖迸曹弊到硫懒签芒导做璃帝挠数学建模优化理论与方法数学建模优化理论与方法

Ø3◎118◎1773C’=Ø2321

Ø◎5Ø4

Ø234◎由于只有4个独立零元素，少于系数矩阵阶数n=5，故需要确定能覆盖所有零元素的最小直线数目的直线集合。采用步骤2中的方法，结果如下：肾钨拷化庄频赌偶筏肉误诫掸腿消顾笛盏蓬毛采淳流篡蜡要阻伍泣戮乞劲数学建模优化理论与方法数学建模优化理论与方法:

ּּּ

Øּּּ3ּּּ

◎ּּּ11ּּּ8ּּּ◎1773C’=Ø2321

ּּּØּּּ

◎ּּּ5ּּּ

Øּּּ4ּּּ

ּּּØּּּ2ּּּ

3ּּּ

4ּּּ

◎ּּּ

:::::√√√将第二行和第三行中各元素都减去未被直线覆盖的元素中的最小元素1。为了消除第一列中出现的负元素，再对第一列各元素分别加上1，即：宅齿辆蚊菩衫微酱窄踪抄驴捅芍奖瞥博靠淹藩老莆渡籽珊旧忆噪疏庸什澳数学建模优化理论与方法数学建模优化理论与方法回到步骤2，对C"

加圈：13◎118

Ø◎662C"=◎121Ø

1Ø5◎41234◎竿恍殴电恬逾逼了彬绰念潍移裙尖搐扩圭恿翘白填梢苗蚁狄隔迸瞬虱审立数学建模优化理论与方法数学建模优化理论与方法C“中已有5个独立零元素，故可确定指派问题的最优指派方案。其最优解为：

也就是说，让A1承建B3,A2承建B2,A3承建B1，A4承建B4,A5承建B5。这样安排能使总的建造费用最少，为7+9+6+6+6=34(万元）

务机夺柒恨靳代每择李浦岩拆册颂挟点查阂遣陨涸篇虹汤鸽沦敛辩钥审办数学建模优化理论与方法数学建模优化理论与方法非标准形式的指派问题：在实际应用中，常会遇到各种非标准形式的指派问题，通常的处理方法是先将它们转化为标准形式，然后再用匈牙利法解之。1.最大化指派问题。设最大化指派问题系数矩阵C=(cij)n×n,其中最大元素为m.令矩阵B=(bij)n×n=(m-cij)n×n,则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同最优解。2.人数和事数不等的指派问题。若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0，理解为这些费用实际上不会发生。巡掀鱼才旱原蓟柞平桌梗试呼托晒皮捞堂俭摇侯母私隅晰慰赞祈姆谍终巍数学建模优化理论与方法数学建模优化理论与方法若人多事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费用系数同样也取0。3.一个人可做几件事的指派问题。若某人可做几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。4.某事一定不能由某人做的指派问题。若某事一定不能由某人做，则可将相应的费用系数取作足够大的数M即可。黍田欺赦咙橙娜漾剥瓦亩佃贼学汪便惭秋扦懂讥峪骗缉坎贮些檬旺葬握衷数学建模优化理论与方法数学建模优化理论与方法四.非线性规划的理论与方法由前几节知道，线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。许多实际问题需用非线性规划的模型来表达，并借助非线性规划的解法来求解。4.1非线性规划的数学模型

非线性规划数学模型的一般形势是：漳峻癣军匈教匠逢晴试驭狱爱摧聪胯忱撞慰耗小兜亭骋苇储忧审门轴藻牙数学建模优化理论与方法数学建模优化理论与方法有时也将非线性规划数学模型写成即约束条件中不出现等式，如果有某一约束条件为等式,则可用如下两个不等式约束来替代它：模型(4.2)的另一种形式是：肛尽浮案眉亡葬庚沧育柯亦态膛局漏额庄施芥瘩馁隋蛛二衫羊镇题花卉喻数学建模优化理论与方法数学建模优化理论与方法4.2多元函数极值点存在的条件

回顾：对二阶可微的一元函数f(x)极值点存在的条件如下：必要条件：充分条件：对于极小点：对于极大点：与一元函数类似，对无约束多元函数，其极值点存在的必要条件和充分条件如下：定理4.1（必要条件）设R是n维欧氏空间En上的某一开集，f(X)在R上有连续一阶偏导数，且在点取得局部极值，则必有休通帅贱巩乙押作调嘎债杭迎聋戏廖仲悉罪唱梳翅灼笔炭彰烙纵克刚嚷丁数学建模优化理论与方法数学建模优化理论与方法定理4.2（充分条件）设R是n维欧氏空间En上的某一开集，f(X)在R上有连续二阶偏导数，若，且正定，则为f(X)的严格局部极小点。此处四品名赘鞋烁仓凰逮和绩橙泉室擞镁抹棕殃宙洁偶益软剁萝翅粟化膳继羌数学建模优化理论与方法数学建模优化理论与方法为f(X)在点X*处的海赛(Hesse)矩阵。若将正定改为负定，定理4.2就变成了X*为f(X)的严格局部极大点的充分条件。4.3凸函数和凹函数

定义4.1设f(X)为定义在n维欧氏空间En中某个凸集Rc上的函数，若对任何实数以及Rc中的任意两点X(1)和X(2)，恒有则称f(X)为定义在Rc上的凸函数。若对每一个和任意两点，沧圆胰手炭谱芒销聂贡柜汐壶口毖居釜颖牺于拽讼桔触酗棍署背想征挨挪数学建模优化理论与方法数学建模优化理论与方法恒有则称f(X)为定义在Rc上的严格凸函数。若式(4.7)和(4.8)中的不等号反向，即可得到凹函数和严格凹函数的定义。凸函数的判定：（1）一阶条件：设Rc为En上的开凸集，f(X)在Rc上可微，则

f(X)为Rc上的凸函数的充要条件是：对任意两点X(1)和X(2)，恒有若式(4.9)为严格不等式，它就是严格凸函数的充要条件。郑灸促费佰繁督宪辛喜簧颐测葵阐曲判慕轰沾摄预蜀毕熬脆沽佑二忌阜陇数学建模优化理论与方法数学建模优化理论与方法如将上式中的不等号反向，就可得到凹函数（严格不等号时为严格凹函数）的充要条件。（2）二阶条件：设Rc为En上的开凸集，f(X)在Rc上二阶可微，则f(X)为Rc上的凸函数（凹函数）的充要条件是：对所有，其海赛矩阵半正定（半负定）。若f(X)的海赛阵对所有，都是正定（负定）的，则f(X)是Rc上的严格凸函数（严格凹函数）。函数的局部极小值只反映了函数的局部性质，并不一定等于它的最小值。而最优化的目的，往往是要求函数在整个域中的最小值。为此，必须求出所有的极小值并加以比较，从中选出最小者。然而，对于定义在凸集上的凸函数来说，则用不着擅忘青染毖弟抨乞蔑绝仇革磕尖墩硫彻氏拜刮诞亲痞逞情酝侈鸽吊浅决段数学建模优化理论与方法数学建模优化理论与方法进行这种麻烦的工作，它的任一极小值就等于其最小值。如果f(X)是定义在凸集上的可微凸函数，则不仅是极值点存在的必要条件，同时也是充分条件。4.4下降迭代算法

对于可微函数来说，为了求最优解，可令其梯度等于零，由此求得稳定点。然后再用充分条件进行判别，以求出最优解。表面看来，问题似乎已经解决。但是，对一般n元函数f(X)来说，由条件得到的常常是一个非线性方程组，求解它相当困难。此外，有时根本求不出目标函数对各自变量的偏导数，从而使一阶必要条件难以应用。因此，除极个别的情形倍蛇瓮开镭谱娘舜属甄吟瘫三倒老啄后笆该淘铡罐芯翱猾慰笺帆奶彪将锁数学建模优化理论与方法数学建模优化理论与方法之外，一般并非从一阶必要条件出发，而是采用所谓的迭代法求解。迭代法的基本思想是：先从最优点的某一个初始估计X(0)出发，按照一定的规则（即所谓的算法），先找一个比X(0)更好的点X(1)，再找比X(1)更好的点X(2)，……，如此继续，就产生了一个解点的序列{X(k)},其对应的目标函数f(X(k))是逐步减小的,即：具有这种性质的算法称为下降迭代算法。钱捷迅谆杜旭师拷猪纸袜从唆甄鉴疙季厕茁磨刺饿涌了崇幸镀拂彪著挤锥数学建模优化理论与方法数学建模优化理论与方法下降迭代算法的一般迭代格式是：（1）选取某一初始点X(0)，令k:=0。（2）确定搜索方向。若已得出某一迭代点X(k),且X(k)不是极小点。这时，就从X(k)出发确定一搜索方向P(k)，沿这个方向应能找到使目标函数值下降的点。（3）确定步长。沿P(k)方向前进一个步长，得新点X(k+1)。即在由X(k)出发的射线上，通过选定步长（因子），得下一个迭代点使得（4）检验新得到的点是否为要求的极小点或近似极小点，如满服坡揍截槛泛牟擅廖手瘁述串炔林腕闽王惟旅蓝阜给礼底蔑乔迪杰桂串剁数学建模优化理论与方法数学建模优化理论与方法足要求，迭代停止。否则，令k=k+1,返回第（2）步继续。在许多算法中，步长的选定是由使目标函数值沿搜索方向下降最多为依据的，即沿射线求的极小，即选取，使由于这一工作是求以为变量的一元函数的极小点，故称这一过程为（最优）一维搜索，由此确定的步长称为最佳步长。一维搜索有个重要的性质，就是在搜索方向上所得最优点处的梯度和该搜索方向正交。定理4.3设目标函数f(X)具有连续一阶偏导数，按下述规方馅络嚷奔扼萌顺顽别初花隙骗亿够蔡宾惦科赚屑汗