《6线性规划实用教案》由会员分享，可在线阅读，更多相关《6线性规划实用教案（69页珍藏版）》请在金锄头文库上搜索。
1、美国空军为了保证士兵的营养，规定每餐的食品中，美国空军为了保证士兵的营养，规定每餐的食品中，要保证一定的营养成份，例如蛋白质、脂肪、维生素要保证一定的营养成份，例如蛋白质、脂肪、维生素等等，都有定量的规定。当然这些营养成份可以由各等等，都有定量的规定。当然这些营养成份可以由各种不同的食物来提供，例如牛奶提供蛋白质和维生素，种不同的食物来提供，例如牛奶提供蛋白质和维生素，黄油提供蛋白质和脂肪，胡萝卜提供维生素，等等。黄油提供蛋白质和脂肪，胡萝卜提供维生素，等等。由於战争条件的限制，食品种类有限，又要尽量降低由於战争条件的限制，食品种类有限，又要尽量降低成本，於是在一盒套餐中，如何决定各种食品的数
2、量，成本，於是在一盒套餐中，如何决定各种食品的数量，使得既能满足营养成份的需要，又可以降低成本？使得既能满足营养成份的需要，又可以降低成本？现代管理问题现代管理问题(wnt)虽然千变万化，但大致上总是虽然千变万化，但大致上总是要利用有限的资源，去追求最大的利润或最小的成本，要利用有限的资源，去追求最大的利润或最小的成本，如何解决这些问题如何解决这些问题(wnt)？解决问题的方法(fngf)：线性规划第1页/共68页第一页，共69页。在在波波斯斯湾湾战战争争期期间间，美美国国军军方方利利用用线线性性规规划划，有有效效地地解解决决了了部部队队给给养养和和武武器器调调运运问问题题，对对促促进进战战争
3、争的的胜胜利利，起起了了关关键键的的作作用用(zuyng)。甚甚至至有有这这样样的的说说法法：因因为为使使用用炸炸药药，第第一一次次世世界界大大战战可可说说是是化化学学的的战战争争；因因为为使使用用原原子子弹弹，第第二二次次世世界界大大战战可可说说是是物理的战争；因为使用线性规划，波斯湾战争可称为数学的战争。物理的战争；因为使用线性规划，波斯湾战争可称为数学的战争。在在历历史史上上，没没有有哪哪种种数数学学方方法法，可可以以像像线线性性规规划划那那样样，直直接接为为人人类类创创造造如如此此巨巨额额的的财财富，并对历史的进程发生如此直接的影响。富，并对历史的进程发生如此直接的影响。2第2页/共6
4、8页第二页，共69页。实验(shyn)八线性函数极值求解3例1、生产(shngchn)计划问题：问：A, B各生产(shngchn)多少, 可获最大利润? A B 备用资源 煤 1 2 30劳动日 3 2 60 仓库 0 2 24 利润 40 50一、引例某企业生产A，B两 种产品，成本和利润指标如下：第3页/共68页第三页，共69页。 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24， x1，x2 0；max Z= 40x1 +50x2解:设产品A, B的产量(chnling)分别为变量x1 ， x2，则：s.t. A B 备用资源 煤 1 2 30劳动日 3 2 60 仓
5、库 0 2 24 利润 40 504第4页/共68页第四页，共69页。5例2：(资源配置问题(wnt) 现有四种原料，其单位成本和所含维生素A，B，C成分如下：求：最低成本(chngbn)的原料混合方案。 A B 每单位成本 原料(yunlio)1 4 1 0 2 原料(yunlio)2 6 1 2 5 原料(yunlio)3 1 7 1 6 原料(yunlio)4 2 5 3 8每单位添加剂中维生素最低含量 12 14 8第5页/共68页第五页，共69页。6解：minZ= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12，x1 + x2 +7x3+5x4 14，
6、 2x2 + x3+3x4 8， xi 0 (i =1,4)；设每单位(dnwi)添加剂中原料i的用量为xi(i =1,2,3,4)，则：s.t. A B 每单位成本 原料1 4 1 0 2 原料2 6 1 2 5 原料3 1 7 1 6 原料4 2 5 3 8每单位添加剂中维生素最低含量12 14 8第6页/共68页第六页，共69页。 有一批长度为7.4m的钢筋若干根。现有5中下料方案，分别(fnbi)作成2.9m， 2.1m，1.5m的钢筋架子各100根。每种下料方案及剩余料头如下表所示：例3、 (资源配置(z yun pi zh)问题)问：如何(rh)下料使得剩余料头最少？ 2.9m 1
7、 2 0 1 02.1m 0 0 2 2 11.5m 3 1 2 0 3合计 7.4 7.3 7.2 7.1 6.6料头 0 0.1 0.2 0.3 0.87第7页/共68页第七页，共69页。解：设按第i种方案(fng n)下料的原材料为xi根，则：minZ= 0.1x2 + 0.2x3+0.3x4+0.8x5 x1 + 2x2 + x4 =100， 2x3 +2x4+ x5=100，3x1+ x2+2x3 +3x5=100， xi 0 (i =1,5)，且为整数；s.t. 2.9m 1 2 0 1 02.1m 0 0 2 2 11.5m 3 1 2 0 3合计 7.4 7.3 7.2 7.1
8、 6.6料头 0 0.1 0.2 0.3 0.88第8页/共68页第八页，共69页。例4、(运输(ynsh)问题) 1 2 3 库存容量 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35仓库车间某棉纺厂的原棉需从仓库运送到各车间(chjin)。各车间(chjin)原棉需求量，单位产品从各仓库运往各车间(chjin)的运输费以及各仓库的库存容量如下表所列：问：如何(rh)安排运输任务使得总运费最小？9第9页/共68页第九页，共69页。设xij为i 仓库运到 j车间(chjin)的原棉数量(i 1,2,3; j 1,2,3)。则minZ= 2x11 + x1
9、2+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33解：x11 +x12+x13 50，x21+x22+x23 30，x31+x32+x33 10，x11 +x21+x31 = 40，x12 +x22+x32 =15，x13 +x23+x33 =35， xij 0， i 1,2,3; j 1,2,3;s.t. 1 2 3 库存容量 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10需求 40 15 35仓库车间10第10页/共68页第十页，共69页。例5、连续投资10万元于4个项目。各项目投资时间(shjin)和本利情况如下：项目A：从第1年 到第4
10、年每年初要投资，次年末(nin m) 回收本利1.15倍。项目B：第3年初(ninch)投资，到第5年末回收本利1.25倍， 最大投资4万元。项目C：第2年初投资，到第5年末回收本利1.40倍， 最大投资3万元。项目D：每年初投资，每年末回收本利1.11倍。求：如何分配投资资金使得5年末总资本最大？11第11页/共68页第十一页，共69页。解： 1 2 3 4 5A x1A x2A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D 项目年份设xik( i =1,2,3,4,5; k =A,B,C,D)表示第i年初投资(tu z)第k项目的资金数。12第12页/共6
11、8页第十二页，共69页。xik( i =1,2,5; k =A,B,C,D)为第i年初(ninch)投k项目的资金数.则：maxZ= 1.15x4A +1.40 x2C+1.25x3B+1.11x5Dx1A+x1D=10x2A+x2C+x2D= 1.11 x1Dx2C 3x3A +x3B+x3D =1.15 x1A+ 1.11 x2Dx3B 4x4A +x4D =1.15 x2A+ 1.11 x3Dx5D =1.15 x3A+ 1.11 x4D xik 0, i =1,2,5; k =A,B,C,D;s.t.13第13页/共68页第十三页，共69页。1以上以上(yshng)(yshng)问题问
12、题的特点的特点: :2.某项任务确定(qudng)后，如何安排人力、财力、物力，使之最省.1.在人力、财力、资源(zyun)给定条件下，如何合理安排任务，使得效益最高.即以上问题都是在一定条件下，求线性函数的最大值或最小值问题。这类问题称为线性规划LP (Linear Programming) 问题。第14页/共68页第十四页，共69页。1线性规划问题的一般(ybn)形式max(min)Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn (=, )b1,a21x1+ a22x2+ a2nxn (=, )b2, am1x1+ am2x2+ amnxn (=, )bm,xj
13、0(j=1,n);s.t.或第15页/共68页第十五页，共69页。三、线性规划三、线性规划(xinxnuhu)问题的求解方法问题的求解方法二元线性规划(xin xn u hu)问题的图解法线性规划(xin xn u hu)问题的理论解法线性规划问题的MATLAB软件解法第16页/共68页第十六页，共69页。x=linprog(f, A, b): 求解(qi ji) min z = fx,Ax b求解线性规划(xin xn u hu)的MATLAB命令 若没有(mi yu)不等式约束,可用 替代A和b, 若没有(mi yu)等式约束,可用 替代Aeq和beq, 若某个xi下无界或上无界,可设定-
14、inf或 inf；用x, Fval代替上述命令行中的x，可得最优解处的函数值Fval。x=linprog(f, A, b, Aeq, beq): 求解： min z = fx, Ax b, Aeqx = beq；x=linprog(f, A, b, Aeq, beq, lb, ub): 指定lb x ub;7第17页/共68页第十七页，共69页。 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24，min Z= -40x1 -50x2s.t.例1、解：程序(chngx)如下c=-40,-50;a=1,2;3,2;0,2;b=30;60;24;x=linprog (c,a,b)
15、z=c*x18第18页/共68页第十八页，共69页。x1+x2 5,-6 x1 10, -1 x2 4;例2:min Z= 4x1 +3x2s.t.解： % lp2.m %c=4,3;a=1,1;b=5;vlb=-6;-1; %lower bound of vector x %vub=10;4; % upper bound of vector x % x=linprog(c,a,b,vlb,vub)z=c*x19第19页/共68页第十九页，共69页。x1+x2 +x3 7,-x1 +x2 -x3 -2,x1 , x2 ,x3 0;例3:min Z = -x1+2x2 3x3s.t.20解：%
16、lp3.m %c=-1,2,-3;a=1,1,1;-1,1,-1; b=7;-2;vlb=0;0;0; % lower bound of vector x %vub=; % upper bound of vector x % x=linprg(c,a,b,vlb,vub)z=c*x第20页/共68页第二十页，共69页。minZ= 2x1 + x2+3x3+2x4 +2x5 +4x6 +3x7 +4x8 +2x9x1 +x4 +x7 = 40， x2 +x5 +x8 =15， x3 +x6 +x9 =35，x1 +x2+x3 50， x4+x5+x6 30， x7+x8+x9 10， xi 0，
17、 i 1,2,9;s.t.例4:21第21页/共68页第二十一页，共69页。% lp4.m %c=2,1,3,2,2,4,3,4,2;b=40;15;35;beq=50;30;10;a(1,:)=1,0,0,1,0,0,1,0,0;a(2,:)=0,1,0,0,1,0,0,1,0;a(3,:)=0,0,1,0,0,1,0,0,1;aeq(1,:)=1,1,1,0,0,0,0,0,0;aeq(2,:)=0,0,0,1,1,1,0,0,0;aeq(3,:)=0,0,0,0,0,0,1,1,1;vlb=zeros(9,1); % lower bound of vector x %vub=; % up
18、per bound of vector x % x=linprog(c,a,b,aeq,beq,vlb,vub)z=c*x解：22第22页/共68页第二十二页，共69页。综合(zngh)实例 投资的收益和风险市场上有n种资产Si(i=1,2,n)可以选择，现用数额为M的相当大的资金作一个时期的投资。财务人员分析估算出这一时期内购买Si的平均收益率为ri,风险损失率为qi,投资越分散，总的风险越小，总体风险可用投资的Si中最大的一个风险来度量。购买Si时要付交易费，费率pi(不买无须付费).当购买额不超过给定值ui时，交易费按购买ui计算.另外，假定同期银行存款利率(ll)是r0,既无交易费又无
19、风险。(r0=5%)已知n=4时的相关数据如下:第23页/共68页第二十三页，共69页。SiriqipiuiS1282.51103S2211.52198S3235.54.552S4252.66.540 试给该公司设计一种投资组合方案，即用给定达到资金M,M,有选择地购买若干种资产或存银行(ynhng)(ynhng)生息，使净收益尽可能大，使总体风险尽可能小。第24页/共68页第二十四页，共69页。基本(jbn)假设1.1.投资数额M M相当大, ,为了便于计算，假设(jish)M=1;(jish)M=1;2.2.投资越分散，总的风险越小；3.3.总体风险Si Si 用投资项目中最大的一个风险来
20、度量；4.n4.n种资产 Si Si 之间是相互独立的；5.5.在投资的这一时期内,ri , pi , qi , r0,ri , pi , qi , r0为定值，不受意外因素影响；6.6.净收益和总体风险只受ri , pi , qiri , pi , qi影响，不受其他因素干扰。第25页/共68页第二十五页，共69页。符号(fho)规定Si第i种投资项目，如股票，债券ri,pi,qi分别为Si的平均收益率,风险损失率，交易费率uiSi的交易定额(dng),r0同期银行利率xi投资项目Si的资金,a投资风险度Q总体收益,Q总体收益的增量第26页/共68页第二十六页，共69页。模型的建立(jinl
21、)与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即maxqixi|i=1，2,n2购买Si所付交易费是一个分段函数,即pixixiui交易费=piuixiui而题目所给定的定值ui(单位:元)相对(xingdu)总投资M很小,piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi第27页/共68页第二十七页，共69页。模型(mxng)的建立与分析净收益(shuy)尽可能大建立(jinl)模型总体风险尽可能小多目标规划问题第28页/共68页第二十八页，共69页。模型(mxng)转化方法一:固定风险水平，优化收益在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限(
22、 jixin)a，使最大的一个风险qixi/Ma，可找到相应的投资方案。 模型(mxng)一线性规划模型(mxng)第29页/共68页第二十九页，共69页。模型(mxng)转化方法二:固定(gdng)盈利水平，极小化风险若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。 模型(mxng)二线性规划模型(mxng)第30页/共68页第三十页，共69页。模型转化(zhunhu)-(zhunhu)-方法3 3线性加权投资者在权衡资产风险(fngxin)和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险(fngxin)、收益赋予权重s（0s1)，s称为投资偏好系
23、数. 模型(mxng)三线性规划模型(mxng)第31页/共68页第三十一页，共69页。模型(mxng)一的求解将具体(jt)数据代入,模型一如下: 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环(xnhun)搜索，编制程序如下：第32页/共68页第三十二页，共69页。a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0
24、0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)第33页/共68页第三十三页，共69页。计算结果：第34页/共68页第三十四页，共69页。模型(mxng)一结果分析1.1.风险大，收益也大。2.2.当投资越分散时，投资者承担的风险越小，这与题意(t y)(t y)一致。即: : 冒险的投资者会出
25、现集中投资的情况，保守的投资者则尽量分散投资。3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。第35页/共68页第三十五页，共69页。4.4.在a=0.006a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有(mi yu)(mi yu)特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合， 大约是a*=0.6%a*=0.6%，Q*=20% Q*=20% ，此时风险度为 0.0060 0.0060 收益为 0.201
26、9, 0.2019,所对应投资方案为: : x0 x1 x2 x3 x4 x0 x1 x2 x3 x4 0 0.2400 0.4000 0.1091 0.2212 0 0.2400 0.4000 0.1091 0.2212第36页/共68页第三十六页，共69页。线性规划线性规划(xinxnuhu)问题的图解法问题的图解法Ax=b (1)x 0 (2)maxZ=cx (3)定义1：满足约束(1)、(2)的x=(x1 , , xn)T称为LP问题(wnt)的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为(chn wi)LP问题的最优解.231、两个概念第37页/共68页第三十七
27、页，共69页。 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24， x1，x2 0；max Z= 40x1 +50x2例1:s.t.24、二元线性规划(xin xn u hu)问题的图解法第38页/共68页第三十八页，共69页。x2=0 (横) (0,30), (20,0) 2x2 =24(1)、确定(qudng)可行域解：x1 0;x1 =0 (纵)x2 0;x1+2x2 30x1+2x2 =30 (0,15) (30,0)与坐标轴交点:3x1+2x2 =602x2 243x1+2x2 600x2102030DABC3x1+2x2 = 60x1+2x2 = 302x2 =2
28、43010x120第39页/共68页第三十九页，共69页。(2)、求最优解x* = (15,7.5)Z=40x1+50x20=40x1+50x2 x1+2x2 =30 3x1+2x2 =60C点:0102030x2DABC3x1+2x2 = 60x1+2x2 = 302x2 = 24203010x1Z=975Z=0Zmax =97534第40页/共68页第四十页，共69页。(0 1)maxZ=40x1+ 80x2 x1+2x2 30,3x1+2x2 60, 2x2 24, x1 , x2 0;例2: 求解(qi ji)s.t.最优解：BC线段(xindun)B点 : x(1)=(6,12) C
29、点: x(2)=(15,7.5) BC线段(xindun):maxZ=1200 350102030x2DABC3x1+2x2 = 60x1+2x2 = 302x2 = 24203010x1Z=1200Z=0第41页/共68页第四十一页，共69页。例、 max Z=3x1+2x2 -x1 -x2 1,x1 , x2 0;即无可行(kxng)解.x2x1-1-1037s.t.可行(kxng)域无解.-x1 -x2 =1第42页/共68页第四十二页，共69页。线性规划问题(wnt)的理论解法 A称为(chn wi)约束矩阵.21、 线性规划问题(wnt)的标准形式第43页/共68页第四十三页，共69
30、页。化一般(ybn)线性规划问题为标准形（1）约束条件的转换(zhunhun)：称为松弛变量(binling)或剩余变量(binling)22第44页/共68页第四十四页，共69页。 x1 +2x2 +x3 =30， 3x1 +2x2 +x4 =60， 2x2 + +x5 =24， x1 , , x5 0 ； maxZ=40x1+ 50x2+0x3 +0x4+0x5 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24， x1，x2 0；max Z= 40x1 +50x2例1:s.t.其中x3 , x4, x5 为松弛(sn ch)变量 。s.t.25第45页/共68页第四十五页
31、，共69页。minZ= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12，x1 + x2 +7x3+5x4 14， 2x2 + x3+3x4 8， xi 0 (i =1,4)；例2：minZ= 2x1 + 5x2 +6x3+8x4 +0x5 +0x6 +0x74x1 + 6x2 + x3+2x4 -x5 =12，x1 + x2 +7x3+5x4 -x6 =14， 2x2 + x3+3x4 x7= 8， xi 0 (i =1,2,7)；其中x5 , x6, x7 为剩余(shngy)变量 。s.t.s.t.26第46页/共68页第四十六页，共69页。(2)、变量(b
32、inling)例3:令: x1= x1- x1 3x1+2x2 8, x1 4x2 14,x20, x1 为自由变量;(1)(1)3 x1 3 x1 +2x2 8, x1 x1 4x2 14,x1 , x1 , x2 0;(2)27第47页/共68页第四十七页，共69页。（2）变量(binling)转换：23第48页/共68页第四十八页，共69页。令: x1 = x1 +6, 则 0 x1 16x1+x2 5,-6 x1 10,x20;(3)-6+6 x1+6 10+6易知:例4:(3)x1 +x2 11,x1 16,x1 , x2 0;(4)28第49页/共68页第四十九页，共69页。(3)
33、、目标函数(hnsh)的转换ZZ 令Z = -ZxoZ24第50页/共68页第五十页，共69页。将以下线性规划(xin xn u hu)问题x1+x2 +x3 7,x1 -x2 +x3 2,x1 , x2 0， x3为自由变量;化为标准型。例5:min Z = -x1+2x2 3x3s.t.29第51页/共68页第五十一页，共69页。 令x3 =x4 - x5 加松弛(sn ch)变量x6加剩余(shngy)变量x7 令 Z= -Zmax Z= x1 2x2 +3x4 3x5 解：min Z = -x1+2x2 3x3x1+x2 +x3 7,x1 -x2 +x3 2,x1 , x2 0；s.t
34、.x1 +x2 +x4 -x5 +x6 =7,x1 -x2 +x4 -x5 -x7 =2,x1 , x2 , x4 , x5 , x6 , x7 0;s.t.30第52页/共68页第五十二页，共69页。、线性规划(xin xn u hu)问题的理论解法:凸集：定义(dngy)1：Ax=b (1)x 0 (2)maxZ=cx (3)设D是n维欧氏空间(kngjin)的一个集合。任意点x(1), x(2)D,若任一满足 x= x(1)+(1-) x(2) (0 1)的点xD。则D称为凸集。38.x(2)x(1).x设线性规划的标准型设线性规划的标准型第53页/共68页第五十三页，共69页。B P1
35、 PmN =Pm+1 Pna11 a1ma21 a2mam1 ammP1 Pma1m+1 a1na2m+1 a2namm+1 amnPm+1 PnA，定义2：基(基阵) 若A中一个子矩阵方阵(fn zhn)B可逆，则矩阵B称为LP问题的一个基(基阵) 。基向量:P1 Pm;非基向量:Pm+1 Pn;基变量:x1 xmxB =;非基变量:xN =xm+1 xn;设x=x1 xmxm+1 xn=xB xN，39第54页/共68页第五十四页，共69页。xB = B-1 b - B-1N xNA=BNx=xB xNAx=b记:BxB +NxN=bBxB =b -NxN定义(dngy)3：基本解称为Ax
36、=b的一个(y )基本解, 最多有m个非零分量。B-1 b 0x=则称基B为基本(jbn)可行基。称为Ax=b的一个基本可行解。B-1 b 0x=对应于基B，若B-1 b0，40最多第55页/共68页第五十五页，共69页。x1+2x2 +x3 =30,3x1+2x2 +x4 =60, 2x2 +x5=24,x1 x5 0;41例1、b=306024取B=P3 P4 P5=I 可逆, 基阵。1 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=,N=P1 P2非基阵.非基向量xN=x1x2,xB=x3x4x5,基向量x=xN xB解向量第56页/共68页第五十六页
37、，共69页。42xB = B-1 b - B-1N xNAx=b令=00xN=x1x2则基本(jbn)解 0 0306024x=xN xB=因为(yn wi)x 0，是基本可行解。第57页/共68页第五十七页，共69页。43又由det(B1) =60, 知B1可逆,可以充当(chngdng)基矩阵.1 2 13 2 0 0 2 0=若取B1 =(P1 P2 P3 )相应(xingyng)的非基阵N1 =P4 P5xB1=x1x2x3,基变量x4x5xN1=.非基变量得基本(jbn)解令1212-6 0 0xB1 xN1x=(B1 ) -1 b 0=.x4x5xN1=00,非基本可行解第58页/
38、共68页第五十八页，共69页。 -x3+x4 =0, x2 +x3 +x4 =3, -x1 +x2 +x3+x4 =2,xj 0 ( j=1,2,3,4 );求出基变量是x1 , x3 , x4的基本(jbn)解，是不是可行解？44例2、给定(i dn)约束条件解：0 -1 10 1 1-1 1 1B=(P1 P3 P4)= 0 1 -1 -1/2 1/2 0 1/2 1/2 0B-1= ,b=032 .第59页/共68页第五十九页，共69页。45 xB = x1 x3x4 = B-1 b 0 1 -1 -1/2 1/2 0 1/2 1/2 0=03213/23/2=是可行(kxng)解.所以
39、(suy)x =x1x2x3x4 1 03/23/2 =,第60页/共68页第六十页，共69页。设x(1),x(2),x(k)是n维欧氏空间(kngjin)中的k个点，若有一组数1,2,k满足0i1(i=1,k)定义(dngy)4 i =1ki=1使得(sh de) x= 1 x(1) + + k x(k)则称点x为 x(1) , x(2) , ,x(k) 的凸组合。凸组合:46第61页/共68页第六十一页，共69页。凸集D,点xD，若找不到两个不同的点x(1),x(2)D使得(shde)x=x(1)+(1-)x(2)(01)则称x为D的顶点。定义(dngy)5顶点(dngdin):47第62
40、页/共68页第六十二页，共69页。LP问题(wnt)解的性质:若(LP)问题(wnt)有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。(LP)问题的基本可行解 可行域的顶点。 若(LP)问题有最优解，必可以在基本可行解(顶点)达到。48第63页/共68页第六十三页，共69页。LP问题理论解法的一般(ybn)步骤:将LP问题模型标准化，找出所有(suyu)基矩阵；49对找出的每个基矩阵(j zhn)求得一个基本解；在所有的基本解中找出基本可行解；在所有的基本可行解中找出最优解；算出最优解处目标函数的最优值.第64页/共68页第六十四页，共69页。图解法可以解决图解法可
41、以解决(jiju)二元线性规划问题，形象直观地观察解的性态。二元线性规划问题，形象直观地观察解的性态。理论法可以解决理论法可以解决(jiju)决策变量少，约束条件少的线性规划问题，理论上可行。决策变量少，约束条件少的线性规划问题，理论上可行。软件解法可解决软件解法可解决(jiju)复杂线性规划问题，但解的性态信息不多。复杂线性规划问题，但解的性态信息不多。总结(zngji)55第65页/共68页第六十五页，共69页。选题及组队1.每三个学生组成(z chn)一队，共同协作完成一份实验报告。 2.题目自选 根据题目难度系数及完成质量给分。1第66页/共68页第六十六页，共69页。数学(shxu)
42、实验报告要求:1.实验问题2.问题分析(fnx):包括解决问题的理论依据，建立的数学模型以及求解问题的思路和方法。3.程序设计流程图。4.结果分析(fnx)和结论。5.总结和体会。2第67页/共68页第六十七页，共69页。谢谢您的观看(gunkn)！第68页/共68页第六十八页，共69页。内容(nirng)总结美国空军为了保证士兵的营养，规定每餐的食品中，要保证一定的营养成份，例如蛋白质、脂肪、维生素等等，都有定量(dngling)的规定。因为使用线性规划，波斯湾战争可称为数学的战争。项目D：每年初投资，每年末回收本利1.11倍。3.总体风险Si 用投资项目中最大的一个风险来度量。ui Si的交易定额,。r0 同期银行利率。xi 投资项目Si的资金,。a 投资风险度。Q总体收益,。Q总体收益的增量。谢谢您的观看第六十九页，共69页。
