第一讲 线性规划与非线性规划

1线性规划与非线性规划主讲：黄厚辉电话：[phone]邮箱：[e-mail]2三个问题1.什么是线性规划问题？2.如何求解线性规划问题？3.求解线性规划问题的注意事项。3一、什么是线性规划问题？线性规划是研究在一组线性约束条件下，某一个线性函数的最大值或最小值问题。一般线性规划问题数学模型为：112211112211211222221122min(max)..()()()0(1,2,,)nnnnnnmmmnnmizfxfxfxstaxaxaxbaxaxaxbaxaxaxbxin或或，或或，或或，或4例一生产决策问题某厂生产甲乙两种产品，已知制成一吨产品甲需要用资源A3吨，资源B4m3;制成一吨产品乙需要用资源A2吨，资源B6m3，C资源7个单位。若一吨甲和一吨乙的经济价值分别为7万元和5万元，三中资源分别为90吨、200m3和210个单位，试决定应生产这两种产品各多少吨才能创造总经济价值最高？5（1）假定自变量（决策变量）：生产产品甲的数量（吨）：生产产品乙的数量（吨）（2）分析并表达限制条件（约束条件）资源A限制：资源B限制：资源C限制：非负条件：1x2x123290xx1246200xx27210x120,0xx61x（3）分析目标以Z表示生产甲和乙两种产品各为和（吨）时产生的经济价值，则有：综上可得：1275zxx2x121212212max7532904620072100,0zxxxxxxxxx7例二投资问题某单位有一批资金用于四个工程项目的投资，用于各个工程项目时所得之净收益（投入资金的百分比）如下表所示：工程项目ABCD收益(%)15108128考虑到问题的目标及本身的限制条件可得数学模型：123412342341234max0.150.10.080.120010,1,2,3,4jzxxxxxxxxxxxxxxxxj9例三工件加工任务分配问题某车间有两台机床甲和乙，可用于加工三种工件。假定这两台机床的可用台时数分别为700和800，三种工件的数量分别为300、500和400，且已知用不同机床加工单位数量的不同工件所需的台时数和加工费用（见表一），问怎样分配机床的加工任务才能既满足加工工件的要求，又使总加工费用最低？10表一机床类型单位工件所需加工台时单位工件的加工费用可用台时数工件1工件2工件3工件1工件2工件3甲乙0.40.51.11.21.01.3131191210870080011考虑到问题的目标及本身的限制条件可得数学模型：123456142536123456max13910111283005004000.41.17000.51.21.38000,1,2,,6jzxxxxxxxxxxxxxxxxxxxj12小结1.用未知自变量表示某种重要的可变因素，变量的一组数据表示一种解决方案，通常要求这些变量取非负值。2.存在一定的限定条件（例如材料、人力、设备、时间、费用等的限制），它们可以用自变量的线性不等式和等式来表达。3.都有一个要达到的目标，它是自变量的线性函数，往往需要这个函数取得最大或是最小。13二、如何求解线性规划问题？结论：线性规划问题实质是求解：由给定条件限定的定义域内的多元线性函数的最值。14几个概念1.松弛变量2.凸集3.基4.基解5.基可行解6.超平面7.顶点15几条定理1.定理一：线性规划的可行解是凸集2.定理二：线性规划的基可行解对应于其可行域的顶点。3.定理三：若线性规划问题有可行解，则必有基可行解。4.定理四：线性规划问题若有最优解，则一定可在期可行域的顶点上达到；如果在几个顶点上都出现最优解，则在这些顶点的每个凸组合上也达到最优。16单纯形法略17MATLAB求解线性规划问题112211112211211222221122min(max)..()()()0(1,2,,)nnnnnnmmmnnmizfxfxfxstaxaxaxbaxaxaxbaxaxaxbxin或或，或或，或或，或min(max)..TzfxstAxbAeqxbeqlbxub或12(,,,)Tnffff线性规划问题写成矩阵形式其中：12(,,,)Tnxxxx,AAeq是矩阵,,,bbeqlbub是列向量18MATLAB里面只能解形如下式的线性规划问题：min..TzfxstAxbAeqxbeqlbxub19转化成等价形式（1）目标函数：1122maxnnzfxfxfx'zz令1122max'nnzfxfxfx1122min'nnzfxfxfx20（2）约束条件：1122iiinniaxaxaxb1122iiinniaxaxaxb（3）非负约束条件：jx为自由变量(0,0)jksksxxxxx=21例子123123123123123max23..72325,0zxxxstxxxxxxxxxxxx不限制12451245124512451245max23)..()7()232()5,,,0zxxxxstxxxxxxxxxxxxxxxx（x3=x4-x5x4，x5非负12451245124512451245min233..723225,,,0zxxxxstxxxxxxxxxxxxxxxx22MATLAB命令（helplinprog）x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)[x,fval]=linprog(...)[x,lambda,exitflag]=linprog(...)[x,lambda,exitflag,output]=linprog(...)[x,fval,exitflag,output,lambda]=linprog(...)23求解例一121212212max7532904620072100,0zxxxxxxxxx121212212min7532904620072100,0zxxxxxxxxx(7,5)Tf其中：min..TzfxstAxbAeqxbeqlbxub12(,)Txxx(0,0)Tlb(inf,inf)Tub324607A90200210bAeqbeq24f=[-7-5];A=[32;46;07];b=[90;200;210];x=linprog(f,A,b)X=(14,24)Tz=218万元25求解例二123412342341234max0.150.10.080.120010,1,2,3,4jzxxxxxxxxxxxxxxxxj123412342341234min0.150.10.080.120010,1,2,3,4jzxxxxxxxxxxxxxxxxj(0.15,0.1,0.08,0.12)Tf1beq11110111A(0,0)Tb1234(,,,)Txxxxx0000lb1111Aeqinfinfinfinfub26f=[-0.15-0.1-0.08-0.12];A=[1-1-1-1;0-1-11];b=[0;0];Aeq=[1111];beq=[1];lb=[0;0;0;0];ub=[inf;inf;inf;inf];x=linprog(f,A,b,Aeq,beq,lb,ub)x=(0.50.250.00.25)z=0.1327求解例三123456142536123456max13910111283005004000.41.17000.51.21.38000,1,2,,6jzxxxxxxxxxxxxxxxxxxxj123456142536123456min13910111283005004000.41.17000.51.21.38000,1,2,,6jzxxxxxxxxxxxxxxxxxxxj(13,9,10,11,12,8)Tf(0.15,0.1,0.08,0.12)Tf(0.15,0.1,0.08,0.12)Tf(300,500,400)Tbeq100100010010001001Aeq(0.15,0.1,0.08,0.12)Tf0.41.110000000.51.21.3A(700,800)Tb(0.15,0.1,0.08,0.12)Tf(0.15,0.1,0.08,0.12)Tf28f=[-13-9-10-11-12-8];A=[0.41.11000;0000.51.21.3];b=[700;800];Aeq=[100100;010010;001001];beq=[300;500;400];lb=[000000];ub=[infinfinfinfinfinf];x=linprog(f,A,b,Aeq,beq,lb,ub)X=300.00.0400.00.0500.00.0z=1389929练习一连续投资问题某部门在今后五年内考虑给下列项目投资，已知：项目A：从第一年到第四年初需投资，并于次年末回收本利115％；项目B：从第三年初需投资，到第五年末回收本利125％，但规定投资额不超过4万元；项目C：从第二年初需投资，到第五年末回收本利140％，但规定投资额不超过3万元；项目D：五年内每年初可购买公债，于当年末归还，并加利息6％。该部门现有资金10万元，问它应如何确定给这些项目每年得资额，使到第五年末拥有资金得本利总额最大？30解:(1)确定变量。用j=1,2,3,4,5分别代表第1至5年，用i=1,2,3,4分别代表项目A、B、C、D。设xij为生产单位第j年初用第i种项目的投资额，如下表所示：31(2)年投资额＝年资金总额第1年X11+x41=100000第2年X12+x32+x42=(1+6%)x41第3年X13+x23+x43=115%x11+(1+6%)x42第4年X14+x44=115%x12+(1+6%)x43第5年x45=115%x13+(1+6%)x44投资额限制x23≤40000，x32≤3000032(3)目标函数maxz=115%x14+125%x23+140%x32+(1+6%)x4533(4)数学模型Maxz=115%x14+125%x23+140%x32+(1+6%)x45X11+x41=100000X12+x32+x42=(1+6%)x41X13+x23+x43=115%x11+(1+6%)x42X14+x44=115%x12+(1+6%)x43x45=115%x13+(1+6%)x44x23≤40000x32≤300