建模教程线性规划.ppt

《建模教程线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、静态最优化问题30-Jul-21线性规划模型与求解线性规划LinearProgramming运筹学中应用最广泛的方法之一运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大研究对象有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之最省线性规划的数学模型某家具厂木器车间生产木门与木窗两种产品。加工木门收入为56元／扇、加工木窗收入为30元／扇。生产一扇木门需要木工4小时、油漆工2小时；生产一扇木窗需要木工3小时、油漆工1小时。该车间每日可用木

2、工总工时为120小时，油漆工总工时为50小时。问该车间应如何安排生产才能使每日收入最大。设该车间每日安排生产木门x1扇、木窗x2扇。Model:Maxz=56x1+30x2s.t4x1+3x21202x1+x250x1,x20解得：X*=(15,20)T,z*=1440假若另有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要事先考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图从而愿意为他加工这批订单、又使自己所付的工时费用总数最少。设w1,w2分别为付给木工和油漆工每个工时的价格。

3、则该个体经营者的目标函数为每日所付工时总费用最小。Minf=120w1+50w2该个体经营者所付的价格不能太低，至少不能低于该车间生产木门、木窗时所得到的收入，否则该车间觉得无利可图就不会替他加工这批订单。因此，需满足4w1+2w2563w1+w230w1,w20解得：W*＝（2，24），f*=1440Maxz=56x1+30x2Minf=120w1+50w2s.t4x1+3x2120s.t.4w1+2w2562x1+x2503w1+w230x1,x20w1,w20上面两个线性规划模型称为一对对偶的线性规划模型。任一线性规划问题都有一对偶问题。线性规划模型特点决策变量

4、：向量(x1…xn)T决策人要考虑和控制的因素，一般非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小一般式max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn(=,)b2………am1X1+am2X2+…+amnXn(=,)bmXj0(j=1,…,n)11隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值线性

5、规划模型线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,unr,≤0线性规划的标准形式目标函数：min约束条件：=变量符号：≥0线性规划的图解法maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点LP问题的特性2维n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点凸集——D是n维欧氏空间的一个集合X(1),X(2)∈D,若任一个满足X=X(1)+(1-)X(2)(01)有X∈D定义1：凸集及其顶点X

6、(1),X(2),…,X(k)是n维欧氏空间中的k个点，若有一组数µ1,µ2,…,µk满足0µi1(i=1,…,k)定义2µi=1ki=1有点x=µ1X(1)+…+µkX(k)则称点X为X(1),X(2),…,X(k)的凸组合。凸组合凸集D,点XD，若找不到两个不同的点X(1),X(2)D使得X=X(1)+(1-)X(2)(0<<1)则称X为D的顶点。定义3顶点定理2：LP有最优解，必定可以在可行域(凸多面集)的顶点得到。定理1：LP问题的可行域一定是凸集(凸多面集)LP问题的解的性质凸集凸集不是凸集LP问题解的性质maxZ=CXAX=bX0Am×n满秩X=(x1…x

7、n)Ta11…a1ma1m+1…a1na21…a2ma2m+1…a2n………………………am1…ammamm+1…amnP1…PmPm+1…PnBN(m