机理模型优质课件

§3.3机理模型

优化问题与规划模型§3.3机理模型

优化问题与规划模型1优化问题与规划模型

优化问题：与最大、最小、最长、最短等等有关的问题。解决最优化问题的数学方法：运筹学

运筹学主要分支：

线性规划、非线性规划、整数规划；动态规划、多目标规划、分层规划；存贮论、排队伦、对策论、决策论；图与网络分析。优化问题与规划模型优化问题：2线性规划1.问题例1家具生产的安排一.家具公司生产桌子和椅子，每张桌子要用15个工时，0.2立方木材，售价80元每张椅子要用10个工时，0.05立方木材，售价45元用于生产的劳力共计450个工时，木材共有4立方米问为达到最大的收益，应如何安排生产？线性规划3分析：

1.求什么？生产多少桌子？生产多少椅子？2.优化什么？收益最大3.限制条件？原料总量劳力总数x1x2Maxf=80x1+45x20.2x1+0.05x2

≤415x1+10x2≤450分析：x14模型I：以产值为目标取得最大收益.设：生产桌子x1张,椅子x2张,(决策变量)将目标优化为：maxf=80x1+45x2对决策变量的约束：0.2x1+0.05x2≤420x1+5x2≤40015x1+10x2≤450,x1≥0,x2≥0,

0.2x1+0.05x2≤4模型I：以产值为目标取得最大收益.0.2x1+0.05x25规划问题：在约束条件下求目标函数的最优值点。规划问题包含3个组成要素:

决策变量、目标函数、约束条件。1.规划问题分类：当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,

否则称为非线性规划问题。规划问题：在约束条件下求目标函数的最优值点。62.线性规划问题求解方法称满足约束条件的向量为可行解,

称可行解的集合为可行域,称使目标函数达最优值的可行解为最优解.图解法：(解两个变量的线性规划问题)

在平面上画出可行域（凸多边形），计算目标函数在各极点(多边形顶点)处的值比较后，取最值点为最优解。2.线性规划问题求解方法7命题1

线性规划问题的可行解集是凸集

可行解集：线性不等式组的解

0.2x1+0.05x2=415x1+10x2=450命题1线性规划问题的可行解集是凸集0.2x1+0.8命题2

线性规划问题的目标函数(关于不同的目标值)是一族平行直线,目标值的大小描述了直线离原点的远近命题2线性规划问题的目标函数(关于不同的目标值)是一9命题3

线性规划问题的最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).

机理模型优质课件10求解可得生产计划x1=14,x2=24净收益

f=80x1+45x2=2200（元）共用木材0.2x1+0.05x2=4（立方）共需劳力15x1+10x2=450（工时）,求解可得11单纯形法:使用线性代数的方法求解线性规划问题

通过确定约束方程组的基本解,并计算相应目标函数值,在可行解集的极点中搜寻最优模型的标准化

正则模型:

决策变量:x1,x2,…,xn.目标函数:Z=c1x1+c2x2+…+cnxn.约束条件:a11x1+…+a1nxn≤b1,……am1x1+…+amnxn≤bm,单纯形法:12模型的标准化过程10.引入松弛变量将不等式约束变为等式约束若有ai1x1+…+ainxn≤bi,则引入xn+i≥0,使得ai1x1+…+ainxn+xn+i=bi若有aj1x1+…+ajnxn≥bj,则引入xn+j≥0,使得aj1x1+…+ajnxn-xn+j=bj.

且有Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.

模型的标准化过程1320.将目标函数的优化变为目标函数的极大化.若求minZ,令Z’=–Z,则问题变为maxZ’.30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,则可使得问题的全部变量均非负.

20.将目标函数的优化变为目标函数的极大化.14标准化模型

求变量x1,x2,…,xn,maxZ=c1x1+…+cnxn,s.t.a11x1+…+a1nxn=b1,……am1x1+…+amnxn=bm,x1≥0,…,xn≥0,标准化模型15讨论模型I模型可以标准化为求变量：x1,x2,x3,x4maxf=80x1+45x2s.t.20x1+5x2+x3=40015x1+10x2+x4=450x1≥0，x2≥0,x3≥0,x4≥0讨论模型I16令x3=x4=0关于x1,x2求解方程(4),(5)可得x1=14，x2=24代入目标函数（3）得到f=80×14+45×24=2200令x2=x3=0关于x1,x4求解方程(4),(5)可得x1=20，x4=150f=80×20+45×0=1600令x3=x4=0关于x1,x2求解方程(4),(5)可17令x1=x4=0关于x2,x3求解方程(4),(5)可得

x2=45，x3=170f=80×0+45×45=2025令x1=x2=0关于x3,x4求解方程(4),(5)可得

x3=400，x4=4500f=80×0+45×0=0令x1=x4=0关于x2,x3求解方程(4),(5)可18令x1=x3=0关于x2,x4求解方程(4),(5)可得

x2=80，x4=－350非可行解令x2=x4=0关于x1,x3求解方程(4),(5)可得

x1=30，x3=－400非可行解最优解为x1=14，x2=24，目标函数值f=80×14+45×24=2200令x1=x3=0关于x2,x4求解方程(4),(5)可19

定义:若代数方程AX=B的解向量有n-m个分量为零,其余m个分量对应A的m个线性无关列,则称该解向量为方程组的一个基本解.在一个线性规划问题中,如果一个可行解也是约束方程组的基本解,则称之为基本可行解命题4

一个向量x是线性规划问题可行解集的一个极点,

当且仅当它是约束方程的一个基本可行解.

定义:若代数方程AX=B的解向量有n-m个分量为零,20一般线性规划的数学模型及解法：minf=cTxs.t.AxbA1x=b1LBxUBMatlab求解程序[x,f]=linprog(c,A,b,A1,b1,LB,UB)一般线性规划的数学模型及解法：21练习1：农作物种植安排一个农场计划种蔬菜,棉花和水稻.预计每亩产值（利润）分别为110元,75元,60元.农场有50亩土地,20个劳动力,种植这三种农作物每亩地分别需要劳动力1/21/31/4,如何规划经营使经济效益最大.

练习1：农作物种植安排22设决策变量：种植蔬菜x1亩,棉花x2亩,水稻x3亩，求目标函数f=110x1+75x2+60x3在约束条件x1+x2+x3≤501/2x1+1/3x2+1/4x3≤20x1，x2，x3≥0下的最大值设决策变量：23练习2资源分配生产甲肥1吨,需要磷酸盐0.4吨,硝酸盐1.8吨,利润1万元;生产乙肥1吨,需要磷酸盐0.1吨,硝酸盐1.5吨,利润0.5万元.现有磷酸盐10吨,硝酸盐66吨,问甲、乙肥各生产多少吨获利最大？练习2资源分配24设决策变量：生产甲肥x1吨,乙肥x2吨，求目标函数f=1x1+0.5x2在约束条件0.4x1+0.1x2≤101.8x1+1.5x2≤66x1，x2≥0下的最大值。设决策变量：25模型II.在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。

设每立方木材和每个工时投入“成本”分别为y1y2(决策变量)则目标函数为：g=4y1+450y2对决策变量的约束

0.2y1+15y2

≥

800.05y1+10y2≥

45y1≥0,y2≥0

模型II.在不降低当前生产水平的前提下评估资源的贡献，26求解可得

y1=100（元/m3），y2=4（元/工时）总成本

g=4y1+450y2=2200（元）产品成本（资源的贡献）

0.2y1+15y2

=800.05y1+10y2

=45求解可得273.对偶问题(DualProblem)：

A是mn矩阵，

c是n1向量（价格），b是m1向量（原料）

x是n1向量（产出）,y是m1向量（成本）问题maxf=cTxs.t.Ax

bxi0,i=1,2,,n.

对偶问题minf=bTys.t.ATy

cyi0,i=1,2,,m.3.对偶问题(DualProblem)：

28对偶定理:互为对偶的两个线性规划问题,若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.若两者之一有无界的最优解,则另一个没有可行解模型I给出了生产中产品的最优方案模型II给出了生产中资源的最低估价.这种估价涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中的贡献确定的估价.

我们称之为影子价格(shadowprice)对偶定理:互为对偶的两个线性规划问题,29例2.生产5种产品P1,P2,P3,P4,P5

单价为550,600,350,400,200.三道工序:研磨、钻孔、装配。每种产品所需工时P1P2P3P4P5I122002515II1081600III2020202020各工序的生产能力（工时数）288192384如何安排生产，收入最大。例2.生产5种产品P1,P2,P3,P30模型：设xi生产Pi的件数。则maxZ=550x1+600x2+350x3+400x4+200x5。s.t.12x1+20x2+0x3+25x4+15x5≤28810x1+8x2+16x3+0x4+0x5≤19220x1+20x2+20x3+20x4+20x5≤384xi

≥0有解x1=12，x2=7.2，x3=x4=x5=0Z=10920模型：设xi生产Pi的件数。31分析：1.

约束条件（生产能力）限制的情况12x1+20x2=288≤288

10x1+8x2=177.6＜19220x1+20x2=384≤384三个工序的生产能力不平衡如果改变三个工序的生产能力，每个工序的单位增长会带来多少贡献？分析：322.产品价格的影响x1x2x3x4x5

550600350400200结果表明与P1,P2相比P3,P4,P5，定价低了.在当前的生产能力下，产品的定价不平衡价格如何改变,生产才能达到平衡?2.产品价格的影响33对偶问题有解:工序的成本（贡献）：w1=6.25,w2=0,w3=23.75Zopt=6.25×288+0×192+23.75×384=10920

约束条件(影子价格）的情况X1：12×6.25+10×0+20×23.75=550≥550X2：20×6.25+8×0+20×23.75=600≥600X3：0×6.25+16×0+20×23.75=475.00>350X4：25×6.25+0×0+20×23.75=631.25>400X5：15×6.25+0×0+20×23.75=568.75>200对偶问题有解:344.灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时,最优解是否会随之变化?通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题,被称为参数线性规划(参见线性规划书籍).例如,当农作物的价格发生变化时,生产计划是否应马上随之改变?可以稍微改变价格，观察最优解的变化，讨论参数的灵敏性。4.灵敏度分析35练习3营养配餐甲种食品每10克含5个单位的蛋白,10个单位的铁,单价3元;乙种食品每10克含7个单位的蛋白,4个单位的铁,单价2元.现需要一份食品,含有35个单位的蛋白,40个单位的铁,问如何配餐最省钱?练习3营养配餐36思考1一家大建筑公司正在三个地点开掘。同时又在其他四个地点建筑，这里需要土方的填充。在1、2、3处挖掘产生的土方分别为每天150，400，325立方码。建筑地点A、B、C、D处需要的填充土方分别为175，125，225，450立方码。也可以从地点4用每立方码5美元的价格获得额外的填充土方。填充土方运输的费用约为一货车容量每英里20美元。一辆货车可以搬运10立方码的土方，每立方码土方每英里运输费2美元。下表给出了各地点间距离的英里数。求使公司花费最少的运输计划。思考1一家大建筑公司正在三个地点开掘。同时又在其他四个地点建37

挖掘与建筑地点间的距离（英里）接收填充土方的地点挖掘地点ABCD1526102457537644491062机理模型优质课件38农作物问题某农户有100英亩土地合5000美元可供投资。每年冬季家庭成员可以贡献3500小时的劳动时间，而夏季为4000小时。如果这些劳动时间有富裕，家庭成员可以去附近农场打工，冬季每小时4.8美元，夏季每小时5.1美元。现金收入来源于3种农作物（大豆、玉米、燕麦）以及2种家禽（奶牛、母鸡）。农作物不需要投资，但每头奶牛需要400美元初始投资，每只母鸡需要3美元初始投资。思考2农作物问题思考239每头奶牛需要1.5英亩土地，冬季需要付出100小时劳动时间，夏季50小时，每年净收益为450美元；相应地，每只母鸡不占用土地，冬季0.6小时，夏季0.3小时，年净收益为3.5美元。养鸡房最多容纳3000只母鸡，栅拦最多能容纳32头奶牛。种植一英亩的大豆、玉米、燕麦分别需要冬季劳动时间20、35、10小时，夏季劳动时间30、75、40小时，年景收益分别为175、300、120美元。建立数学模型，帮助该农户确定养殖计划，使得年净收入最多。每头奶牛需要1.5英亩土地，冬季需要付出100小时劳动时间，40思考题*：有4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不许插队（即在任何阶段4位同学的顺序是一样的）。由于4位置同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下所示：思考题*：有4名同学到一家公司参加三个阶段的面试，公司要求每41

秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这4位同学约定他们面试完后一起离开公司，假定现在是早上8：00，问他们最早何时能离开公司。秘书初试主管复试经理面试42§3.3机理模型优化问题与规划模型§3.3机理模型43课堂讨论总结参加组数：19组，人数57人参加评分：41＋1包饺子模型：10组，洗衣服9组课堂讨论总结参加组数：19组，人数57人44优胜组包饺子五组刘达通胡勤王威马锡豫张郑李直杨雅婷洗衣服刘轶群文豪封达道孙鹏举帅清

优胜组包饺子五组洗衣服454.非线性规划当目标函数和约束条件中包含有决策变量的非线性函数时，

称为非线性规划问题。

4.非线性规划46例3.某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）建两个日储量为e=20吨的料场，需要确定料场位置(xj,yj)和运量cij

，使总吨公里数最小。例3.某公司有6个建筑工地，位置坐标为(ai,bi)(单47假设：1.只考虑两点间的直线距离2.各工地的需求稳定令cij为料场j向工地i运送的水泥量假设：48

minz=f(z)s.t.A1x≤b1,A2x=b2,c1(x)≤0,c2(x)=0LB≤x≤UBMATLAB程序[x,z]=fmincon(fun,x0,A1,b1,A2,b2,LB,UB,nonlcon）minz=f(z)49用随机搜索算法确定初始点：在可行域[0.5,8.75][0.75,7.75]内简单地选取n个随机的的点，计算目标函数在这些点的值，选择其中最小的点即可。然后，可采用Matlab求最值点程序求出精确的最小值点:求函数fun在x0点附近的最小值点用随机搜索算法确定初始点：505.0-1规划

如果要求决策变量只取0或1的线性规划问题,称为整数规划.0-1约束不一定是由变量的性质决定的,更多地是由于逻辑关系引进问题的

5.0-1规划51例4背包问题一个旅行者的背包最多只能装6kg物品.现有4件物品重量为2kg,3kg,3kg,4kg,价值为100元,120元,90元,115元.应携带那些物品使得携带物品的价值最大?建模:记xj：旅行者携带第j件物品的件数,xj={0,1}.约束条件2x1+3x2+3x3+4x4

6求xj使目标函数f=x1+1.2x2+0.9x3+1.15x4最大.例4背包问题52用Lingo软件求解0-1规划LinearInteractiveandGeneralOptimizerModel:Max=x1+1.2*x2+0.9*x3+1.15*x4;2*x1+3*x2+3*x3+4*x4<=6;@bin(x1);@bin(x2);@bin(x3);@bin(x4);end用Lingo软件求解0-1规划53例5供货问题一家公司生产某种商品.现有n个客户,第j个客户需要货物量至少为bj,可在m各不同地点设厂供货.在地区i设厂的费用为di,供货能力为hi

,向第j个客户供应单位数量的货物费用为cij.如何设厂与供货使总费用最小.例5供货问题54模型：记xij为在地区i向第j个客户供货数量,记yi=1,在地区i设厂，记yi=0不在地区i设厂，求设厂和供货分配方案yi，xij使得目标函数f=yi(jcijxij+

di)在约束条件i

yi

xij

bj,j=1,…,n

jxij–hi0,I=1,…,mxij0,yi={0,1}下达到最小模型：记xij为在地区i向第j个客户供货数556.整数规划如果要求决策变量取整数,或部分取整数的线性规划问题,称为整数规划.

机理模型优质课件56例6.飞船装载问题设有n种不同类型的科学仪器希望装在登月飞船上,令cj>0表示每件第j类仪器的科学价值;aj>0表示每件第j类仪器的重量.每类仪器件数不限,但装载件数只能是整数.飞船总载荷不得超过数b.设计一种方案,使得被装载仪器的科学价值之和最大.例6.飞船装载问题57建模记xj为第j类仪器的装载数.求各种仪器的装载数量xj（整数）在约束条件jajxj

b下,

使得目标函数f=jcjxj达到最大值.建模记xj为第j类仪器的装载数.587.用Lindo软件求解整数规划

LinearInteractiveandDiscreteoptimizermax3x1+2x2st2x1+3x2<=142x1+x2<=9endginx1ginx2(或者用gin2)求整数x1,x2MaxZ=3x1+2x2s.t.2x1+3x2≤142x1+x2≤97.用Lindo软件求解整数规划

LinearInter598.规划问题的建模艺术将实际问题归结为线性规划模型是一个探索创造的过程。

8.规划问题的建模艺术60例7钢材截短有一批钢材,每根长7.3米.现需做100套短钢材.每套包括长2.9米,2.1米,1.5米的各一根.至少用掉多少根钢材才能满足需要,并使得用料最省.

例7钢材截短61解:可能的截法和余料第1种7.3-(2.9×2+1.5×1)=0第2种7.3-(2.9×1+2.1×2)=0.2第3种7.3-(2.9×1+1.5×2)=1.4第4种7.3-(2.9×1+2.1×1+1.5×1)=0.8第5种7.3-(2.1×2+1.5×2)=0.1第6种7.3-(2.1×3)=1第7种7.3-(2.1×1+1.5×3)=0.7第8种7.3-(1.5×4)=1.3解:可能的截法和余料62设按第i种方法截xi根钢材(决策变量).目标函数minf=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8约束条件2x1+x2+x3+x4

1002x2+x4+2x5+3x6+x7

100x1+2x3+x4+2x5+3x7+4x8

100xi

0,i=1,…,8

设按第i种方法截xi根钢材(决策变量).63用Matlab程序解得x1=40x2=20x5=30,f=7（实际上应要求xi为正整数。这是一个整数规划问题）。用Matlab程序解得64例8存储问题有5种药品S={1,2,3,4,5}要存放,有些药品不能存放在一起,能存放在一起存放的药品为={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}不同的组合所需的存放费用不同其中第i种组合的存储费用为ci,求这五种药品费用最低的储存方案。例8存储问题65

令xi为存储组合i的决策变量:xi=1时存储第i个组合,否则xi=0求存储方案x

=(x1,x2,x3,x4,x5,x6)’在约束条件x1+x2

+x51

x1+x3

1x2

+x4

1x3+x61

x2

+x3+x61xi{0，1}，i=1,2,,6,下使得目标函数f=cixi最小.

66习题

一资源的最优配置策略某工厂有1000台机器,生产两种产品A,B,若投入y台机器生产A产品,则纯收入为5y.若投入y台机器生产B产品,则纯收入为4y.又知,生产A种产品机器的年折损率为20%,,生产B种产品机器的年折损率为10%,问在5年内如何安排各年度的生产计划,才能使总收入最高.习题一资源的最优配置策略67习题二混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。如何根据4位运动员的4种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩。

蛙泳蝶泳自由泳仰泳

甲99605973

乙79659387

丙67936381

丁56798676习题二混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。如何根据68习题三在大约1000m高空的某边长为160km的正方形区域内有若干架飞机作水平飞行。区域内每架飞机的位置和速度向量均有计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域的边缘时记录其数据后要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机的飞行的方向角，以避免碰撞。习题三69先假定条件如下：1）不碰撞的标准为任意两架飞机的距离大于8km2）飞机飞行方向角调整的幅度不超过3003）所有飞机飞行速度均为每小时800km4）进入该区域的飞机到达区域的边界时，与区域内的飞机的距离应在60km以上5）最多考虑6架飞机6）不必考虑飞机离开次区域后的状况先假定条件如下：70请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算（方向角误差不超过0.010）。要求飞机飞行方向角调整的幅度尽量小设该区域四个顶点的坐标为(0,0),(160,0),(160,160),(0,160)请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，71记录数据为飞机编号横坐标x纵坐标y方向角(0)1150140243285852363150155220.54145501595130150230

新进入0052注：方向角指飞行方向与x轴正向的夹角记录数据为飞机编号横坐标x纵坐标y方向角(0)172

73§3.3机理模型

优化问题与规划模型§3.3机理模型

优化问题与规划模型74优化问题与规划模型

优化问题：与最大、最小、最长、最短等等有关的问题。解决最优化问题的数学方法：运筹学

运筹学主要分支：

线性规划、非线性规划、整数规划；动态规划、多目标规划、分层规划；存贮论、排队伦、对策论、决策论；图与网络分析。优化问题与规划模型优化问题：75线性规划1.问题例1家具生产的安排一.家具公司生产桌子和椅子，每张桌子要用15个工时，0.2立方木材，售价80元每张椅子要用10个工时，0.05立方木材，售价45元用于生产的劳力共计450个工时，木材共有4立方米问为达到最大的收益，应如何安排生产？线性规划76分析：

1.求什么？生产多少桌子？生产多少椅子？2.优化什么？收益最大3.限制条件？原料总量劳力总数x1x2Maxf=80x1+45x20.2x1+0.05x2

≤415x1+10x2≤450分析：x177模型I：以产值为目标取得最大收益.设：生产桌子x1张,椅子x2张,(决策变量)将目标优化为：maxf=80x1+45x2对决策变量的约束：0.2x1+0.05x2≤420x1+5x2≤40015x1+10x2≤450,x1≥0,x2≥0,

0.2x1+0.05x2≤4模型I：以产值为目标取得最大收益.0.2x1+0.05x278规划问题：在约束条件下求目标函数的最优值点。规划问题包含3个组成要素:

决策变量、目标函数、约束条件。1.规划问题分类：当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,

否则称为非线性规划问题。规划问题：在约束条件下求目标函数的最优值点。792.线性规划问题求解方法称满足约束条件的向量为可行解,

称可行解的集合为可行域,称使目标函数达最优值的可行解为最优解.图解法：(解两个变量的线性规划问题)

在平面上画出可行域（凸多边形），计算目标函数在各极点(多边形顶点)处的值比较后，取最值点为最优解。2.线性规划问题求解方法80命题1

线性规划问题的可行解集是凸集

可行解集：线性不等式组的解

0.2x1+0.05x2=415x1+10x2=450命题1线性规划问题的可行解集是凸集0.2x1+0.81命题2

线性规划问题的目标函数(关于不同的目标值)是一族平行直线,目标值的大小描述了直线离原点的远近命题2线性规划问题的目标函数(关于不同的目标值)是一82命题3

线性规划问题的最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).

机理模型优质课件83求解可得生产计划x1=14,x2=24净收益

f=80x1+45x2=2200（元）共用木材0.2x1+0.05x2=4（立方）共需劳力15x1+10x2=450（工时）,求解可得84单纯形法:使用线性代数的方法求解线性规划问题

通过确定约束方程组的基本解,并计算相应目标函数值,在可行解集的极点中搜寻最优模型的标准化

正则模型:

决策变量:x1,x2,…,xn.目标函数:Z=c1x1+c2x2+…+cnxn.约束条件:a11x1+…+a1nxn≤b1,……am1x1+…+amnxn≤bm,单纯形法:85模型的标准化过程10.引入松弛变量将不等式约束变为等式约束若有ai1x1+…+ainxn≤bi,则引入xn+i≥0,使得ai1x1+…+ainxn+xn+i=bi若有aj1x1+…+ajnxn≥bj,则引入xn+j≥0,使得aj1x1+…+ajnxn-xn+j=bj.

且有Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.

模型的标准化过程8620.将目标函数的优化变为目标函数的极大化.若求minZ,令Z’=–Z,则问题变为maxZ’.30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,则可使得问题的全部变量均非负.

20.将目标函数的优化变为目标函数的极大化.87标准化模型

求变量x1,x2,…,xn,maxZ=c1x1+…+cnxn,s.t.a11x1+…+a1nxn=b1,……am1x1+…+amnxn=bm,x1≥0,…,xn≥0,标准化模型88讨论模型I模型可以标准化为求变量：x1,x2,x3,x4maxf=80x1+45x2s.t.20x1+5x2+x3=40015x1+10x2+x4=450x1≥0，x2≥0,x3≥0,x4≥0讨论模型I89令x3=x4=0关于x1,x2求解方程(4),(5)可得x1=14，x2=24代入目标函数（3）得到f=80×14+45×24=2200令x2=x3=0关于x1,x4求解方程(4),(5)可得x1=20，x4=150f=80×20+45×0=1600令x3=x4=0关于x1,x2求解方程(4),(5)可90令x1=x4=0关于x2,x3求解方程(4),(5)可得

x2=45，x3=170f=80×0+45×45=2025令x1=x2=0关于x3,x4求解方程(4),(5)可得

x3=400，x4=4500f=80×0+45×0=0令x1=x4=0关于x2,x3求解方程(4),(5)可91令x1=x3=0关于x2,x4求解方程(4),(5)可得

x2=80，x4=－350非可行解令x2=x4=0关于x1,x3求解方程(4),(5)可得

x1=30，x3=－400非可行解最优解为x1=14，x2=24，目标函数值f=80×14+45×24=2200令x1=x3=0关于x2,x4求解方程(4),(5)可92

定义:若代数方程AX=B的解向量有n-m个分量为零,其余m个分量对应A的m个线性无关列,则称该解向量为方程组的一个基本解.在一个线性规划问题中,如果一个可行解也是约束方程组的基本解,则称之为基本可行解命题4

一个向量x是线性规划问题可行解集的一个极点,

当且仅当它是约束方程的一个基本可行解.

定义:若代数方程AX=B的解向量有n-m个分量为零,93一般线性规划的数学模型及解法：minf=cTxs.t.AxbA1x=b1LBxUBMatlab求解程序[x,f]=linprog(c,A,b,A1,b1,LB,UB)一般线性规划的数学模型及解法：94练习1：农作物种植安排一个农场计划种蔬菜,棉花和水稻.预计每亩产值（利润）分别为110元,75元,60元.农场有50亩土地,20个劳动力,种植这三种农作物每亩地分别需要劳动力1/21/31/4,如何规划经营使经济效益最大.

练习1：农作物种植安排95设决策变量：种植蔬菜x1亩,棉花x2亩,水稻x3亩，求目标函数f=110x1+75x2+60x3在约束条件x1+x2+x3≤501/2x1+1/3x2+1/4x3≤20x1，x2，x3≥0下的最大值设决策变量：96练习2资源分配生产甲肥1吨,需要磷酸盐0.4吨,硝酸盐1.8吨,利润1万元;生产乙肥1吨,需要磷酸盐0.1吨,硝酸盐1.5吨,利润0.5万元.现有磷酸盐10吨,硝酸盐66吨,问甲、乙肥各生产多少吨获利最大？练习2资源分配97设决策变量：生产甲肥x1吨,乙肥x2吨，求目标函数f=1x1+0.5x2在约束条件0.4x1+0.1x2≤101.8x1+1.5x2≤66x1，x2≥0下的最大值。设决策变量：98模型II.在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。

设每立方木材和每个工时投入“成本”分别为y1y2(决策变量)则目标函数为：g=4y1+450y2对决策变量的约束

0.2y1+15y2

≥

800.05y1+10y2≥

45y1≥0,y2≥0

模型II.在不降低当前生产水平的前提下评估资源的贡献，99求解可得

y1=100（元/m3），y2=4（元/工时）总成本

g=4y1+450y2=2200（元）产品成本（资源的贡献）

0.2y1+15y2

=800.05y1+10y2

=45求解可得1003.对偶问题(DualProblem)：

A是mn矩阵，

c是n1向量（价格），b是m1向量（原料）

x是n1向量（产出）,y是m1向量（成本）问题maxf=cTxs.t.Ax

bxi0,i=1,2,,n.

对偶问题minf=bTys.t.ATy

cyi0,i=1,2,,m.3.对偶问题(DualProblem)：

101对偶定理:互为对偶的两个线性规划问题,若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.若两者之一有无界的最优解,则另一个没有可行解模型I给出了生产中产品的最优方案模型II给出了生产中资源的最低估价.这种估价涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中的贡献确定的估价.

我们称之为影子价格(shadowprice)对偶定理:互为对偶的两个线性规划问题,102例2.生产5种产品P1,P2,P3,P4,P5

单价为550,600,350,400,200.三道工序:研磨、钻孔、装配。每种产品所需工时P1P2P3P4P5I122002515II1081600III2020202020各工序的生产能力（工时数）288192384如何安排生产，收入最大。例2.生产5种产品P1,P2,P3,P103模型：设xi生产Pi的件数。则maxZ=550x1+600x2+350x3+400x4+200x5。s.t.12x1+20x2+0x3+25x4+15x5≤28810x1+8x2+16x3+0x4+0x5≤19220x1+20x2+20x3+20x4+20x5≤384xi

≥0有解x1=12，x2=7.2，x3=x4=x5=0Z=10920模型：设xi生产Pi的件数。104分析：1.

约束条件（生产能力）限制的情况12x1+20x2=288≤288

10x1+8x2=177.6＜19220x1+20x2=384≤384三个工序的生产能力不平衡如果改变三个工序的生产能力，每个工序的单位增长会带来多少贡献？分析：1052.产品价格的影响x1x2x3x4x5

550600350400200结果表明与P1,P2相比P3,P4,P5，定价低了.在当前的生产能力下，产品的定价不平衡价格如何改变,生产才能达到平衡?2.产品价格的影响106对偶问题有解:工序的成本（贡献）：w1=6.25,w2=0,w3=23.75Zopt=6.25×288+0×192+23.75×384=10920

约束条件(影子价格）的情况X1：12×6.25+10×0+20×23.75=550≥550X2：20×6.25+8×0+20×23.75=600≥600X3：0×6.25+16×0+20×23.75=475.00>350X4：25×6.25+0×0+20×23.75=631.25>400X5：15×6.25+0×0+20×23.75=568.75>200对偶问题有解:1074.灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时,最优解是否会随之变化?通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题,被称为参数线性规划(参见线性规划书籍).例如,当农作物的价格发生变化时,生产计划是否应马上随之改变?可以稍微改变价格，观察最优解的变化，讨论参数的灵敏性。4.灵敏度分析108练习3营养配餐甲种食品每10克含5个单位的蛋白,10个单位的铁,单价3元;乙种食品每10克含7个单位的蛋白,4个单位的铁,单价2元.现需要一份食品,含有35个单位的蛋白,40个单位的铁,问如何配餐最省钱?练习3营养配餐109思考1一家大建筑公司正在三个地点开掘。同时又在其他四个地点建筑，这里需要土方的填充。在1、2、3处挖掘产生的土方分别为每天150，400，325立方码。建筑地点A、B、C、D处需要的填充土方分别为175，125，225，450立方码。也可以从地点4用每立方码5美元的价格获得额外的填充土方。填充土方运输的费用约为一货车容量每英里20美元。一辆货车可以搬运10立方码的土方，每立方码土方每英里运输费2美元。下表给出了各地点间距离的英里数。求使公司花费最少的运输计划。思考1一家大建筑公司正在三个地点开掘。同时又在其他四个地点建110

挖掘与建筑地点间的距离（英里）接收填充土方的地点挖掘地点ABCD1526102457537644491062机理模型优质课件111农作物问题某农户有100英亩土地合5000美元可供投资。每年冬季家庭成员可以贡献3500小时的劳动时间，而夏季为4000小时。如果这些劳动时间有富裕，家庭成员可以去附近农场打工，冬季每小时4.8美元，夏季每小时5.1美元。现金收入来源于3种农作物（大豆、玉米、燕麦）以及2种家禽（奶牛、母鸡）。农作物不需要投资，但每头奶牛需要400美元初始投资，每只母鸡需要3美元初始投资。思考2农作物问题思考2112每头奶牛需要1.5英亩土地，冬季需要付出100小时劳动时间，夏季50小时，每年净收益为450美元；相应地，每只母鸡不占用土地，冬季0.6小时，夏季0.3小时，年净收益为3.5美元。养鸡房最多容纳3000只母鸡，栅拦最多能容纳32头奶牛。种植一英亩的大豆、玉米、燕麦分别需要冬季劳动时间20、35、10小时，夏季劳动时间30、75、40小时，年景收益分别为175、300、120美元。建立数学模型，帮助该农户确定养殖计划，使得年净收入最多。每头奶牛需要1.5英亩土地，冬季需要付出100小时劳动时间，113思考题*：有4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不许插队（即在任何阶段4位同学的顺序是一样的）。由于4位置同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下所示：思考题*：有4名同学到一家公司参加三个阶段的面试，公司要求每114

秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这4位同学约定他们面试完后一起离开公司，假定现在是早上8：00，问他们最早何时能离开公司。秘书初试主管复试经理面试115§3.3机理模型优化问题与规划模型§3.3机理模型116课堂讨论总结参加组数：19组，人数57人参加评分：41＋1包饺子模型：10组，洗衣服9组课堂讨论总结参加组数：19组，人数57人117优胜组包饺子五组刘达通胡勤王威马锡豫张郑李直杨雅婷洗衣服刘轶群文豪封达道孙鹏举帅清

优胜组包饺子五组洗衣服1184.非线性规划当目标函数和约束条件中包含有决策变量的非线性函数时，

称为非线性规划问题。

4.非线性规划119例3.某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）建两个日储量为e=20吨的料场，需要确定料场位置(xj,yj)和运量cij

，使总吨公里数最小。例3.某公司有6个建筑工地，位置坐标为(ai,bi)(单120假设：1.只考虑两点间的直线距离2.各工地的需求稳定令cij为料场j向工地i运送的水泥量假设：121

minz=f(z)s.t.A1x≤b1,A2x=b2,c1(x)≤0,c2(x)=0LB≤x≤UBMATLAB程序[x,z]=fmincon(fun,x0,A1,b1,A2,b2,LB,UB,nonlcon）minz=f(z)122用随机搜索算法确定初始点：在可行域[0.5,8.75][0.75,7.75]内简单地选取n个随机的的点，计算目标函数在这些点的值，选择其中最小的点即可。然后，可采用Matlab求最值点程序求出精确的最小值点:求函数fun在x0点附近的最小值点用随机搜索算法确定初始点：1235.0-1规划

如果要求决策变量只取0或1的线性规划问题,称为整数规划.0-1约束不一定是由变量的性质决定的,更多地是由于逻辑关系引进问题的

5.0-1规划124例4背包问题一个旅行者的背包最多只能装6kg物品.现有4件物品重量为2kg,3kg,3kg,4kg,价值为100元,120元,90元,115元.应携带那些物品使得携带物品的价值最大?建模:记xj：旅行者携带第j件物品的件数,xj={0,1}.约束条件2x1+3x2+3x3+4x4

6求xj使目标函数f=x1+1.2x2+0.9x3+1.15x4最大.例4背包问题125用Lingo软件求解0-1规划LinearInteractiveandGeneralOptimizerModel:Max=x1+1.2*x2+0.9*x3+1.15*x4;2*x1+3*x2+3*x3+4*x4<=6;@bin(x1);@bin(x2);@bin(x3);@bin(x4);end用Lingo软件求解0-1规划126例5供货问题一家公司生产某种商品.现有n个客户,第j个客户需要货物量至少为bj,可在m各不同地点设厂供货.在地区i设厂的费用为di,供货能力为hi

,向第j个客户供应单位数量的货物费用为cij.如何设厂与供货使总费用最小.例5供货问题127模型：记xij为在地区i向第j个客户供货数量,记yi=1,在地区i设厂，记yi=0不在地区i设厂，求设厂和供货分配方案yi，xij使得目标函数f=yi(jcijxij+

di)在约束条件i

yi

xij

bj,j=1,…,n

jxij–hi0,I=1,…,mxij0,yi={0,1}下达到最小模型：记xij为在地区i向第j个客户供货数1286.整数规划如果要求决策变量取整数,或部分取整数的线性规划问题,称为整数规划.

机理模型优质课件129例6.飞船装载问题设有n种不同类型的科学仪器希望装在登月飞船上,令cj>0表示每件第j类仪器的科学价值;aj>0表示每件第j类仪器的重量.每类仪器件数不限,但装载件数只能是整数.飞船总载荷不得超过数b.设计一种方案,使得被装载仪器的科学价值之和最大.例6.飞船装载问题130建模记xj为第j类仪器的装载数.求各种仪器的装载数量xj（整数）在约束条件jajxj

b下,

使得目标函数f=jcjxj达到最大值.建模记xj为第j类仪器的装载数.1317.用Lindo软件求解整数规划

LinearInteractiveandDiscreteoptimizermax3x1+2x2st2x1+3x2<=142x1+x2<=9endginx1ginx2(或者用gin2)求整数x1,x2MaxZ=3x1+2x2s.t.2x1+3x2≤14