第一章线性规划及单纯形法

第一章第一章 线性规划及单纯形法线性规划及单纯形法1线性规划介绍2线性规划数学模型3线性规划标准形式4线性规划的图解法5线性规划基本概念6单纯形法7应用举例第一章1线性规划介绍线性规划介绍历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。第一章线性规划理论的发展线性规划理论的发展：1939年前苏联康托洛维奇（年前苏联康托洛维奇（KOHTOPOBUZ）生产组织与计划中的生产组织与计划中的 数学方法数学方法提出提出 “解乘数法解乘数法”。1线性规划介绍线性规划介绍列奥尼德列奥尼德康托罗维奇，前苏联人，由于在康托罗维奇，前苏联人，由于在1939年创立年创立了享誉全球的线形规划要点，对资源最优分配理论做了享誉全球的线形规划要点，对资源最优分配理论做出了贡献，而获得诺贝尔经济学奖。出了贡献，而获得诺贝尔经济学奖。第一章美国科学院院士美国科学院院士DANTZIG（丹齐克），（丹齐克），1948年在年在研究美国空军资源的优化配置时提出线性规划及其通用研究美国空军资源的优化配置时提出线性规划及其通用解法解法“单纯形法单纯形法”。被称为线性规划之父。被称为线性规划之父。1线性规划介绍线性规划介绍 线性规划之父的Dantzig(丹齐克)。据说，一次上课，Dantzig迟到 了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是 惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。第一章1线性规划介绍线性规划介绍 1960 1960年，年，“最佳资源利用的经济计算最佳资源利用的经济计算”康托洛维奇康托洛维奇和库伯曼斯和库伯曼斯(Koopmans(Koopmans)。两人。两人因对资源最优分配理论的因对资源最优分配理论的贡献而获贡献而获19751975年诺贝尔经济学奖年诺贝尔经济学奖 佳林佳林库普曼斯，美国人，他将数理统计学成功运用库普曼斯，美国人，他将数理统计学成功运用于经济计量学，对资源最优分配理论做出了贡献。于经济计量学，对资源最优分配理论做出了贡献。第一章1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题。计算机 50约束 100变量 30000约束 3000000变量1线性规划介绍线性规划介绍第一章从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。1线性规划介绍线性规划介绍保罗-萨缪尔逊（PAUL A SAMUELSON）,他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILY LEONTIEF），美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J-阿罗（KENNETH J.ARROW）,美国人，因与约翰-希克斯（JOHN R.HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTON M.MILLER）,1923-2000,美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。第一章1线性规划介绍线性规划介绍线性规划研究的主要问题：有一定的人力、财力、资源条件下，如何合理安排使用，效益最高?某项任务确定后，如何安排人、财、物，使之最省?第一章 例例1 美佳公司计划制造美佳公司计划制造I，II两种家电产品。已知各两种家电产品。已知各制造一件时分别占用的设备制造一件时分别占用的设备A、B的台时、调试时间及的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表一件时的获利情况如表Il所示。问该公司应制造所示。问该公司应制造A、B两两种家电各多少件，使获取的利润为最大？种家电各多少件，使获取的利润为最大？项目项目I IIIII每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 12线性规划数学模型线性规划数学模型第一章例例2 捷运公司拟在下一年度的捷运公司拟在下一年度的1-4月的月的4个月内需租用仓库堆个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合同每月初都可办理，每份台同具体现定租用面积数和期限。因此同每月初都可办理，每份台同具体现定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借台同。每次办理时可该厂可根据需要，在任何一个月初办理租借台同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。该公司签订租借合同的最优决策，目的是使所付租借费用最小。月份月份1 12 23 34 4所需仓库面积所需仓库面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租费合同期内的租费280028004500450060006000730073002线性规划数学模型线性规划数学模型第一章目标函数目标函数约束条件约束条件解：用变量解：用变量x1x1和和x2x2分别表示美佳公司制造家电分别表示美佳公司制造家电I I和和IIII的数量。的数量。项目项目I IIIII每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序（调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 1例例1 1212maxxxz0,52426155.2121212xxxxxxxts用数学语言描述用数学语言描述2线性规划数学模型线性规划数学模型第一章解：设变量xij表示捷运公司在第i(i1，4)个月初签订的租借期为jj1，4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例例2 2月份月份1 12 23 34 4所需仓库面积所需仓库面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租费合同期内的租费28002800450045006000600073007300142313322212413121117300)(6000)(4500)(2800minxxxxxxxxxxz)4.1;4.1(012201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxtsij2线性规划数学模型线性规划数学模型第一章 A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50求：最大利润的生产计划。练习练习1 生产计划问题生产计划问题2线性规划数学模型线性规划数学模型第一章max Z=40 x1+50 x2解:设产品A,B产量分别为变量x1，x2x1+2x2 30 3x1+2x2 602x2 24x1，x2 0s.t.2线性规划数学模型线性规划数学模型第一章求：最低成本的原料混合方案？求：最低成本的原料混合方案？原料原料 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 素最低含量素最低含量练习练习2 混合配料问题混合配料问题2线性规划数学模型线性规划数学模型第一章解：设每单位添加剂中原料解：设每单位添加剂中原料i的用量为的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)s.t.2线性规划数学模型线性规划数学模型第一章 决策变量：向量(x1 xn)T 决策人要考虑和控制的因素。非负 约束条件：线性等式或不等式 目标函数：Z=(x1 xn)线性式，求Z极大或极小线性规划模型特点2线性规划数学模型线性规划数学模型第一章如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型线性规划的数学模型。实际问题中线性的含义：一是严格的比例性二是可叠加性关于线性的界定关于线性的界定2线性规划数学模型线性规划数学模型第一章19max(min)Z=c1x1+c2x2+cnxnn个变量个变量价值系价值系数数第第i 种资种资源的拥有源的拥有量量技术系数或技术系数或工艺系数工艺系数a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2 am1x1+am2x2+amnxn(=,)bmxj 0(j=1,n)s.t.线性规划的一般式线性规划的一般式2线性规划数学模型线性规划数学模型第一章njjjxcz1max(min),2,1(0),2,1(.1njxmibxastjinjjij线性规划的简写式线性规划的简写式2线性规划数学模型线性规划数学模型第一章CXz max(min)0),(.1Xbxpstnjjj),.,(21ncccC nxxxX21mjjjjaaaP21mbbbb21线性规划的向量表示式线性规划的向量表示式2线性规划数学模型线性规划数学模型第一章CXz max(min)0),(.XbAXstmnmmnnaaaaaaaaaA.212222111211线性规划的矩阵表示式线性规划的矩阵表示式2线性规划数学模型线性规划数学模型第一章比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij,bi,ci为确定值。隐含的假设隐含的假设2线性规划数学模型线性规划数学模型第一章仓库工厂 1 2 3 库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35练习练习3 运输问题运输问题工厂需要的原棉存放在三个仓库中，现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如表所示。问使总运费最小的运输方案？2线性规划数学模型线性规划数学模型第一章解：设解：设xij为为i 仓库运到仓库运到 j工厂的原棉数量工厂的原棉数量(i=1,2,3 j=1,2,3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31 +4x32+2x33x11+x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11+x21+x31=40 x12+x22+x32=15x13+x23+x33=35 xij 0st.2线性规划数学模型线性规划数学模型第一章练习练习4 4 连续投资连续投资1010万元万元A A：从第：从第1 1年到第年到第4 4年每年初投资，次年末回收本利年每年初投资，次年末回收本利1.151.15；B B：第：第3 3年初投资年初投资，到第，到第5 5年末年末回收回收本利本利1.251.25，最大投资，最大投资4 4万元；万元；C C：第：第2 2年初投资年初投资，到第，到第5 5年末年末回收回收本利本利1.401.40，最大投资，最大投资3 3万元；万元；D D：每：每年初投资年初投资，每年每年末末回收回收本利本利1.111.11。求：使求：使5 5年末总资本最大的投资方案。年末总资本最大的投资方案。分析：分析：1 2 3 4 5A x1A x2A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D 2线性规划数学模型线性规划数学模型第一章解解：xik(i=1,2,5;k=A,B,C,D)为第为第i年初投资到第年初投资到第k个项个项目的资金数。目的资金数。MaxZ=1.15x4A+1.40 x2C+1.25x3B+1.11x5Dx1A+x1D=10 x2A+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 0s.t.2线性规划数学模型线性规划数学模型第一章线性规划问题应用线性规划问题应用 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)2线性规划数学模型线性规划数学模型第一章线性规划的适用情况线性规划的适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件2线性规划数学模型线性规划数学模型第一章线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,00)(),(.max(min)XbAXt sXCzT0.maxXbAXtsXCzT线性规划的标准形式目标函数：max约束条件：=变量符号：03线性规划标准形式线性规划标准形式第一章标准型的一般型标准型的一般型maxZ=c1x1+c2x2+cnxn其中 bi 0(i=1,2,m)a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bmxj 0(j=1,2,n)s.t.3线性规划标准形式线性规划标准形式第一章 P1 P2 Pn a11 a12 a1n其中 A=a21 a22 a2n am1 am2 amn x1 x=x2 xn b1 b=b2 bmC=(C1 C2 Cn)标准型的矩阵型标准型的矩阵型maxZ=Cx Ax=b x 0 b0 b 0 0 3线性规划标准形式线性规划标准形式第一章 x1Ax=(P1 P2 Pn)x2 =b xn CXZ max01XbxpnjjjP1 x1+P2 x2+Pn xn=b标准型的向量型标准型的向量型3线性规划标准形式线性规划标准形式第一章线性规划问题化标准型：线性规划问题化标准型：(1)、约束条件(2)、变量(3)、目标函数(4)、右端常数3线性规划标准形式线性规划标准形式第一章(1)、约束条件、约束条件x3为松弛变量x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。242621xx：如2426321xxx18121021xx：如181210321xxx当约束条件为“”时：当约束条件为“”时：3线性规划标准形式线性规划标准形式第一章3线性规划标准形式线性规划标准形式 X1+2X2+X3 =30 s.t.3X1+2X2 +X4 =60 2X2 +X5=24 X1,X5 0 0 转化为：转化为：maxZ=40X1+50X2+0X3+0X4+0X5 x1+2x2 30 3x1+2x2 60s.t.2x2 24 x1，x2 0 例：例：max Z=40 x1+50 x2松弛变量松弛变量第一章3线性规划标准形式线性规划标准形式例：例：4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)4X1+6X2+X3+2X4-X5 =12 X1+X2+7X3+5X4 -X6 =14 2X2+X3+3X4 -X7=8 X1,X7 0 0 剩余变量剩余变量第一章(2)、变量、变量3 x1-3 x1 +2x2 8 x1-x1 -4x2 14x1,x1,x2 01、x 0的情况，3x1+2x2 8 x1-4x2 14 x20令x1=x1-x1 2、x取值无约束的情况。令x-x。令x=x-x3 x1-3 x1 +2x2+x3=8 x1-x1 -4x2+x 4=14x1,x1,x2,x3,x4 03线性规划标准形式线性规划标准形式第一章x1+x2 11x1 16x1,x2 0（3 3）、）、x两边有约束的情况。两边有约束的情况。x1+x2 5-6 x1 10 x20-6+6 x1+6 10+6 令x1=x1+6 0 x1 163线性规划标准形式线性规划标准形式第一章(3)、目标函数、目标函数xoZ-Z令Z =-Z njjjxcZ1minnjjjxcZ1min3线性规划标准形式线性规划标准形式第一章(4)、右端常数、右端常数右端项b0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。3线性规划标准形式线性规划标准形式第一章例3：将 min Z=-x1+2x2-3x3x1+x2+x3 7x1-x2+x3 2x1，x20，x3无限制化为标准型3线性规划标准形式线性规划标准形式第一章解：令x3=x4-x5 加松弛变量x6加剩余变量x7 令Z=-ZmaxZ=x1-2x2+3x4-3x5 x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,x2,x4,x7 0min Z=-x1+2x2-3x3x1+x2+x3 7x1-x2+x3 2x1，x20，x3无限制3线性规划标准形式线性规划标准形式第一章(1)min Z=2x1-x2+2x3练习练习5 将下列线性规划问题化成标准型：将下列线性规划问题化成标准型：-x1+x2+x3=4-x1+x2-x3 6x1 0，x2 0,x3 无约束 s.t.(2)max Z=2x1+x2+3x3+x4x1+x2+x3+x3 7 2x1-3x2+x3=-8x1-2x3+2x4 1x1,x3 0,x2 0，x4 无约束 s.t.3线性规划标准形式线性规划标准形式第一章(3)min Z=2x1+3x2+5x3x1+x2-x3 -5-6x1+7x2-9 x3=15|19x1-7x2+5x3|13x1,x2 0,x3 无约束 s.t.(4)max Z=x1-3x2-x1+2x2 -5 x1+3x2=10 x1,x2 无约束 s.t.3线性规划标准形式线性规划标准形式第一章作业作业:课本课本P44 123线性规划标准形式线性规划标准形式第一章Ax=b (1)x 0 (2)maxZ=Cx (3)定义1：满足约束(1)、(2)的x=(x1 xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为LP问题的最优解线性规划的标准型线性规划的标准型4线性规划的图解法线性规划的图解法第一章图解法求解的目的：一是判别线性规划问题的求解结局；二是在存在最优解的条件下，把问题的最优解找出来。4线性规划的图解法线性规划的图解法第一章图解法的步骤：1、在平面上建立直角坐标系；2、图示约束条件，找出可行域；3、图示目标函数和寻找最优解。4线性规划的图解法线性规划的图解法第一章例4 maxZ=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 04线性规划的图解法线性规划的图解法第一章解：(1)、确定可行域 x1 0 x1=0(纵)x2 0 x2=0(横)x1+2x2 30 x1+2x2=30 (0,15)(30,0)x20102030DABC3x1+2x2=60(0,30)(20,0)2x2=24203010 x14线性规划的图解法线性规划的图解法第一章(2)、求最优解最优解：x*=(15,7.5)Zmax=975Z=40 x1+50 x20=40 x1+50 x2 (0,0)，(10,-8)x20102030203010 x1DABCC点：x1+2x2=30 3x1+2x2=604线性规划的图解法线性规划的图解法第一章Z=40 x1+80 x2=0 x1+2x2=30DABCx20 x1解:最优解：BC线段B点 C点x(1)=(6,12)x(2)=(15,7.5)x=x(1)+(1-)x(2)(0 1)例5、maxZ=40 x1+80 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 04线性规划的图解法线性规划的图解法第一章4线性规划的图解法线性规划的图解法X1=6 +(1-)15X2=12 +(1-)7.5X1=15-9 X2=7.5+4.5 (0 1)X=+(1-)maxZ=1200 X1 6 15 X2 12 7.5第一章无界解无有限最优解例6、maxZ=2x1+4x2 2x1+x2 8-2x1+x2 2x1,x2 0Z=02x1+x2=8-2x1+x2=28246x240 x14线性规划的图解法线性规划的图解法第一章例7、maxZ=3x1+2x2-x1-x2 1x1,x2 0无解无可行解-1x1-1x204线性规划的图解法线性规划的图解法第一章唯一解无穷多解 无有限最优解 无可行解有解无解当目标函数的直线族与某约束条件平行，且该问题有解时。约束条件无公共区域。有解但可行域可伸展到无穷时总总 结结4线性规划的图解法线性规划的图解法第一章由图解法得到的启示由图解法得到的启示(1)、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。(2)、若线性规划可行域存在，则可行域是一个凸集。(3)、若有最优解，定可在可行域的顶点得到。(4)、解题思路是找出凸集的各顶点的最大目标函数值。4线性规划的图解法线性规划的图解法第一章作业：作业：用图解法解以下问题：max Z=5x1+6x2x1-2x2 2 -2x1+3x2 2x1,x2 无约束 s.t.4线性规划的图解法线性规划的图解法第一章maxZ=Cx Ax=b x0A mn 满秩 x=(x1 xn)T 一、线性规划问题的解的概念一、线性规划问题的解的概念5线性规划基本概念线性规划基本概念第一章定义定义1：基基(基阵基阵)设A为约束方程组的mn阶系数矩阵设(nm)，其秩为m，B是矩阵A中的一个mm阶的满秩子矩阵，称B是线性规划问题的一个基。P1 P2 Pm Pn a11 a12 a1m a1n A=a21 a22 a2m a2n am1 am2 amm amnB5线性规划基本概念线性规划基本概念第一章A=(P1 Pm Pm+1 Pn)=(BN)基向量 非基向量x=(x1 xm xm+1 xn)T=(xB xN)T 基变量 非基变量 xB xNB中的每一个列向量Pj称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。5线性规划基本概念线性规划基本概念第一章Ax=b的求解的求解xB xN(BN)=bBxB+NxN=bBxB=b-NxNxB=B-1 b-B-1N xNA=(BN)x=(xB xN)T若B为单位矩阵 xB=b-N xN若xN0 xB=B-1 b5线性规划基本概念线性规划基本概念第一章定义2：可行解满足方程约束条件的解x（x1，x2，xn)T,称为线性规划问题的可行解。全部可行解的集合称为可行域。定义3：最优解使目标函数达到最大值的可行解，称为最优解。5线性规划基本概念线性规划基本概念第一章定义4：基本解对应于基B，x=为Ax=b的一个解，则x为线性规划问题的基本解，也称基解。B-1 b 0定义5：基本可行解基B，基本解x=若B-1 b0，称基解为基本可行解，也称基可行解。B-1 b 0 基本解中最多有m个非零分量。基本解的数目不超过Cnm=个。n!m!(n-m)!定义6：可行基对应于基可行解的基称为可行基。5线性规划基本概念线性规划基本概念第一章例8 x1+2x2+x3=30 3x1+2x2 +x4=60 2x2 +x5=24 x1 x5 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=5线性规划基本概念线性规划基本概念第一章x1x2x3x4x5x=b=306024B=(P3 P4 P5)=I 是满秩子矩阵 非基 N=(P1 P2)x3=30-(x1+2 x2)x4=60-(3x1+2 x2)x5=24 -2 x25线性规划基本概念线性规划基本概念第一章令x1=x2=0,x3=30,x4=60,x5=24x=xN 0 xB B-1 b003060245线性规划基本概念线性规划基本概念第一章例9：给定约束条件 -x3+x4=0 x2+x3+x4=3 -x1+x2+x3+x4=2 xj 0(j=1,2,3,4)求出基变量是x1,x3,x4的基本解，是不是可行解？5线性规划基本概念线性规划基本概念第一章 0 -1 1解：B=(P1 P3 P4)=0 1 1 -1 1 1 0 1 -1 0B-1=-1/2 1/2 0 3 1/2 1/2 0 2b=5线性规划基本概念线性规划基本概念第一章 x1 x3 =B-1 b x4 xB=0 1 -1 0 1 =-1/2 1/2 0 3 =3/2 1/2 1/2 0 2 3/2x=(1,0,3/2,3/2)T 是 5线性规划基本概念线性规划基本概念第一章凸集D是n维空间的一个集合，x(1),x(2)D,若对任何x(1),x(2)，有x=x(1)+(1-)x(2)D(0 1)，则D为凸集。定义定义1：凸集如果集合D中任意两个点，其连线上的所有点也都是集合D中的点，则称D为凸集。二、凸集及其顶点二、凸集及其顶点5线性规划基本概念线性规划基本概念第一章x(1)x(2)凸多边形凸多边形凹多边形凹多边形x(1)x(2)5线性规划基本概念线性规划基本概念第一章第一章 x(1),x(2),x(k)是n维欧氏空间中的k个点，若有一组数 1,2,k 满足 0 i 1(i=1,k)定义定义2 i=1ki=1有点 x=1 x(1)+k x(k)则称点x为 x(1),x(2),x(k)的凸组合。凸组合5线性规划基本概念线性规划基本概念第一章 凸集D,点 xD，若找不到两个不同的点x(1),x(2)D 使得 x=x(1)+(1-)x(2)(0 1)则称x为 D的顶点。定义定义3顶点顶点5线性规划基本概念线性规划基本概念第一章证明：设LP问题的可行解域为集合CC=x|Ax=b x 0 任取x(1),x(2)C,则 x=x(1)+(1-)x(2)0 (0 1)又因为 A x(1)=b，A x(2)=b所以 Ax=A x(1)+(1-)x(2)=b+(1-)b=b 则 xC，C为凸集定理定理1：LP问题的可行解域一定是凸集。问题的可行解域一定是凸集。三、几个基本定理的证明三、几个基本定理的证明5线性规划基本概念线性规划基本概念第一章只须证明：D的k个顶点x(1),x(k)，有 预理预理1 D为有界凸多面集，为有界凸多面集，x D，x必可表必可表 为为D的顶的顶点的凸组合点的凸组合。0 i 1，使 x=1 x(1)+k x(k)i=1ki=15线性规划基本概念线性规划基本概念第一章证明可用归纳法（略）x(1)x(2)x(3)x xx在边界上x在内部 x(1)(1-)x(2)(1-)x(3)x=+x x +(1-)x(2)(0 1)x x(1)+(1-)x(3)(0 1)5线性规划基本概念线性规划基本概念第一章证明：设x(1),x(k)为可行域顶点，若x*不是顶点，但 maxZ=C x*定理定理2：可行域有界，最优值必可在顶点得到：可行域有界，最优值必可在顶点得到Cx*=iC x(i)ki=1 i Cx(m)ki=1=Cx(m)设 Cx(m)Max(C x(i)1 i k i x(i)ki=1 i=1ki=10 i 1x*=5线性规划基本概念线性规划基本概念第一章引理引理2：LP问题的可行解x是基本可行解x的非0分量对应的系数列向量线性无关证明：（1）必要性。由基可行解的定义显然。（2）充分性。若向量P1，P2,Pk线性独立，则必有k m。当k=m时，它们恰好构成一个基，从而x=(x1,x2,xm,0,0)为相应的基可行解。当k0 j=1,kxj=0 j=k+1,n由引理2知，p1,pk 线性相关必有不全为0的1,k使 1 p1+k pk=0做 (1,k ,0 ,0)T则有 A 1 p1+k pk=0可行域C中点x是顶点x是基本可行解定理3：5线性规划基本概念线性规划基本概念第一章选任一不为零的数令 x(1)=x+0 x(2)=x 0又Ax(1)=Ax+A b Ax(2)=Ax A=b 所以x(1)Cx(2)C因为 x1/2 x(1)+1/2 x(2)所以 x不是可行域的顶点5线性规划基本概念线性规划基本概念第一章83证明：()不是顶点，不是基可行解设x为可行解xj 0 j=1,kxj=0 j=k+1,n若x不是顶点，则有x(1)x(2)C，使得：x=x(1)+(1-)x(2)(0 0，1-0，xj(1)0，xj(2)0 所以 xj(1)xj(2)0(j=k+1,n)因为 Ax(1)=b Ax(2)=b p j xj(1)=bnj=1 p j xj(2)=bnj=1即 p1 x1(1)+pk xk(1)=b (a)p1 x1(2)+pk xk(2)=b (b)5线性规划基本概念线性规划基本概念第一章由(a)(b)得(x1(1)x1(2)p1+(xk(1)xk(2)pk=0即x不是基可行解所以 p1,pk 线性相关定理定理4 若线性规划问题有最优解，一定存在一个基若线性规划问题有最优解，一定存在一个基可行解是最优解。可行解是最优解。5线性规划基本概念线性规划基本概念第一章 (LP)问题的基本可行解 可行域的顶点。若(LP)问题有最优解，必可以在基本可行解(顶点)达到。若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。5线性规划基本概念线性规划基本概念LP问题解的性质问题解的性质第一章6单纯形法单纯形法 6.1、单纯形法迭代原理 6.2、单纯形法计算步骤 6.3、人工变量法 6.4、两阶段法 6.5、计算中的几个问题第一章6.1 单纯形法迭代原理单纯形法迭代原理一、确定初始基可行解二、从一个基可行解转换为相邻基可行解三、最优性检验和解的判别第一章A中总存在一个单位矩阵（P1,P2,Pm)。一、确定初始基可行解一、确定初始基可行解当约束条件为时，加上松驰变量的系数矩阵即为单位矩阵。当约束条件为或时，可以构造人工基，人为产生一个单位矩阵。基向量、基变量、非基向量、非基变量可得初始基可行解:x=(x1,xm,xm+1,xn)T=(b1,bm,0,0)T6.1 单纯形法迭代原理单纯形法迭代原理第一章两个基可行解相邻指的是它们之间变换且仅变换一个基变量。设x(0)=(x10,x20,xm0,0,0)T，有Pi xi0=bmi=1系数矩阵的增广矩阵系数矩阵的增广矩阵mnmjmmmnjmnjmnjmmbaaabaaabaaabPPPPPP,1,2,2,21,21,1,11,1121.1.00.0.10.0.01.二、基可行解的转换二、基可行解的转换6.1 单纯形法迭代原理单纯形法迭代原理第一章Pj=aij Pimi=1Pj aij Pi0 m i=1两边乘上一个正数0，得(Pj aij Pi）=0 m i=1同 相加整理得：Pixi0=bmi=1所以得到另一个点x(1),使bPPaxjmiiiji10)(TmjmjaxaxX)0,.,.,0,.,(0101)1(Pi xi(1)=bni=1可行解?基解?6.1 单纯形法迭代原理单纯形法迭代原理bPPPPPPaxPaxPaxnjjmmmmjmjj0.0.00)(.)()(121022021101第一章所以x(1)是可行解令ljlijijiaxaax000minTmjmjaxaxX)0,.,.,0,.,(0101)1(存在：00ijiax)(0)(00liliaxiji6.1 单纯形法迭代原理单纯形法迭代原理第一章mjmljlljlljljjmljlbababababababPPPPPP1.00.00.0.10.000.00.000.01.00.0.00.100.00.01.,1,1,1,12,21,11121重新排列后不含非基向量的增广矩阵：因alj0，故上述矩阵元素组成的行列式不为零，P1,P2,Pl-1,Pj,Pl+1,Pm 是一个基。所以，x(1)，是基可行解。lja/ja10 0 0 1 0 0 6.1 单纯形法迭代原理单纯形法迭代原理第一章进行初等变换：b=(b1-a1j,bl-1-al-1,j,bl+1-al+1,j,bm-amj)T由此x(1)是x(0)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。x(1)=(b1-a1j,bl-1-al-1,j,bl+1-al+1,j,bm-amj)T？Tmjmjlljlljababababx)0,.,.,0,.,0,.,(,11,1111)1(6.1 单纯形法迭代原理单纯形法迭代原理10)1(ijmiiaxx第一章将基本可行解x（0）和x（1）分别代入目标函数得：miiixcz10)0(jijmiiicaxcz10)1(110miijijmiiiaccxc1)0(miijijaccz三、最优性检验和解的判别三、最优性检验和解的判别6.1 单纯形法迭代原理单纯形法迭代原理第一章是对线性规划问题的解进行最优性检验的标志。当所有的i=0时，现有顶点为最优解。当所有的i0，又Pj0,则判定原问题无可行解。第第2 2阶段阶段：去除人工变量，求解原问题。第一阶段的最优解为原问题的初始基可行解。6.4 两阶段法两阶段法第一章例2：maxZ=-x1+2x2 x1+x2 2-x1+x2 1 x2 3x1 x2 0解：第(1)阶段：minW=x6+x7 x1+x2-x3 +x6 =2-x1+x2 -x4 +x7=1 x2 +x5 =3x1 x7 06.4 两阶段法两阶段法第一章列初始单纯形表Cj00000-1-1CBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010 x530100100 j=cj-zj第二阶段：去除人工变量，列新单纯形表求解。6.4 两阶段法两阶段法第一章 0 0 0 0 0 1 1 x1 x2 x3 x4 x5 x6 x7CB xB 3 0 -2 1 1 0 0 01 x6 2 1 1 -1 0 0 1 0 1 x7 1 -1 (1)0 -1 0 0 1 0 x5 3 0 1 0 0 1 0 0 CB xB 1 -2 0 1 -1 0 0 2 x6 1 (2)0 -1 1 0 1 -1 x2 1 -1 1 0 -1 0 0 1 x5 2 1 0 0 1 1 0 -1 xB 0 0 0 0 0 0 1 1 x1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 x2 3/2 0 1 -1/2 -1/2 0 1/2 1/2 x5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 6.4 两阶段法两阶段法第一章 -1 2 0 0 0 x1 x2 x3 x4 x5CB xB 3/2 0 0 1/2 3/2 0-1 x1 1/2 1 0 -1/2 (1/2)0 2 x2 3/2 0 1 -1/2 -1/2 0 0 x5 3/2 0 0 1/2 1/2 1 xB 4 -3 0 2 0 0 x4 1 2 0 -1 1 0 x2 2 1 1 -1 0 0 x5 1 -1 0 (1)0 1 xB 6 1 0 0 0 -2 x4 2 1 0 0 1 1 x2 3 0 1 0 0 1 x3 1 -1 0 1 0 16.4 两阶段法两阶段法第一章6.5 计算中的几个问题计算中的几个问题2 2、退化、退化：（非退化 值唯一）kllkllkllkikiittabababaab,1,.)0min(221 在下一次迭代中有一个或几个基变量为0，从而出现退化解。可能可能会导致循环，永远达不到最优解。1 1、目标函数极小化时解的最优性判别、目标函数极小化时解的最优性判别 以i 0作为判别表中解是否最优的标志第一章tkllkllkllkikiilllabababaabtt.)0min()221,1,221且若离基。为主元素。则11,lklxa 则xk进基kjj)0(max0j1）若有两个以上检验数如何解决退化问题？Dantzig 规则：6.5 计算中的几个问题计算中的几个问题第一章6.5 计算中的几个问题计算中的几个问题 1951 年 Hoffman 给出反例。（3个方程，11个变量）1955 年 E.M.L.Beale 3 个方程，7个变量。6次迭代后，出现循环。7,.,2,101035019021092516041650115043min7364321543214321ixxxxxxxxxxxxxxxxxzi 按照 Dantzig规则：（5，6，7）（1，6，7）（1，2，7）（3，2，7）（3，4，7）（5，4，7）（5，6，7）第一章进基则若kixki 0min.1离基。中下标最小者的基变量选)0min(.2,kikiiaabBland 原则 （1976 年 第9届国际数学规划大会）6.5 计算中的几个问题计算中的几个问题第一章3 3、无可行解的判别、无可行解的判别 当线性规划问题中添加人工变量后，无论用人工变量法或两阶段法，初始单纯形表中的解因含非零人工变量，故实质上是非可行解。当求解结果出现所有i 0 0时，如基变量中仍含有非零的人工变量(两阶段法求解时第一阶段目标函数值不等于零)，表明问题无可行解。6.5 计算中的几个问题计算中的几个问题第一章6.5 计算中的几个问题计算中的几个问题例7 用单纯形法求解线性规划问题 maxZ=2x1+x2 x1+x2 22x1+2x2 6 x1 x2 0第一章6.5 计算中的几个问题计算中的几个问题解：添加松弛变量和人工变量，原模型化为标准型。maxZ=2x1+x2-M x5 x1+x2+x3=22x1+2x2 x4+x5=6 x1-5 0以X3，X5为基变量列初始单纯形表，进行计算。第一章6.5 计算中的几个问题计算中的几个问题Cj2100-MCBxBbx1x2x3x4x50 x3211100-Mx56220-11 j=cj-zj2+2M1+2M0-M02x1211100-Mx5200-2-11 j=cj-zj0-1-2-2M-M0第一章6.6单纯形法小结单纯形法小结第一章6.6单纯形法小结单纯形法小结第一章7 应用举例应用举例例1：用长7.4m的钢材做100套钢架，每套钢架需长2.9m,2.1m,1.5m 的料各一根。问如何下料，使用的原料最省？分析：可行的下料方案有：2.9000011122.1012301201.543203101合计66.67.26.37.46.57.17.3余料1.40.80.21.100.90.30.1第一章 解：设第i种方案用xi根原料。Zxxxxxxxxxxxxxxxxxxxxzii01003231002210021.03.09.02.08.0min643215421654365421 解之得 x3=30 x5 =50 x6 =10思考：1）目标函数可否改为 z=x1+x2+x3+x4+x5+x6 2）若每套钢架需长2.9m一根，2.1m二根，1.5m五根。问如何求解。7 应用举例应用举例第一章例 2 连续投资问题李勇拟定在三年后购买一套房子，准备在今后的三年中作一些投资，现有下面四个 投资机会：1：在三年内，投资人在每年年初投资，每年有20%的收益。2：在三年内，投资人在第一年年初投资，两年后有50%的收益。这种投资最多不得超过40000元。3：在三年内，投资人在第二年年初投资，两年后有60%的收益。这种投资最多不得 超过30000元。4：在三年内，投资人在第三年年初投资，一年内有40%的收益。这种投资最多不得超过10000元。现有资金100000元，且每年年末有20000元的固定收入。问李勇应怎样决定投资计划，才能在第三年末获得最高收益？7 应用举例应用举例第一章解：解：设xij为第i年把资金作第j项投资的资金额。据题意可得：3431232112114.02.06.02.05.02.0maxxxxxxxz目标函数：1000001211 xx1123212.120000 xxx211234312.15.140000 xxxx4000012x3000023x1000034x4,3,2,13,2,10jixij 约束条件：7 应用举例应用举例第一章 舱位重量定额（T）占地定额（m3）前 850.0中 1270.0后 730.0 货物重量（T）体积（m3/T）利润（元/T）1145.01002117.01303186.0115494.090 假定这些可乘运其任何一部分。目标是要确定每种货物应当装运多少，并且放在哪个舱位才能使这次飞行的总利润最大？例3：一架货运飞机有三个装货舱：前舱.中舱及后舱。这些舱对于重量与占地，都有如下所示的定额限制如左表所示。此外，在各舱中货物的重量必须跟该舱的重量定额有同样的比例，以便保持飞机的平衡。在即将到来的一次飞行中，有下列四种货物要装运，如右表。7 应用举例应用举例第一章解：设xij表示第i种货物放到第j个舱位的重量。)(90)(115)(130)(100max434241333231232221131211xxxxxxxxxxxxz目标函数：30467543332313xxxx50467541312111xxxx70467542322212xxxx841312111xxxx7:8:12:8:43332313413121114232221241312111xxxxxxxxxxxxxxxx14131211xxx11232221xxx18333231xxx9434241xxx3,2,14,3,2,10jixij约束条件：7 应用举例应用举例第一章29703/19,3/4,3/4,0,0,23/2,3/17,3/14,0,5,0*434241333231232221131211zxxxxxxxxxxxx最优值最优解：7 应用举例应用举例第一章二、课本二、课本P45 1.7（1）用大）用大M法法 1.7（2）用两阶段法）用两阶段法作作 业业一、用单纯形法求解下列线性规划：0,24261553.22max)1(21212121xxxxxxtsxxz0,18231224.53max)1(21212121xxxxxxtsxxzX1=3.75 X2=0.75X1=2X2=6X3=2