线性规划的数学模型和基本性质-PPT课件.pptx

线性性规划划及及单纯形法形法1线性规划介绍2线性规划数学模型3线性规划标准形式4线性规划的图解法5线性规划基本概念6单纯形法7应用举例11线性性规划介划介绍历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。2线性性规划理划理论的的发展展：1939年前年前苏联康托洛康托洛维奇（奇（KOHTOPOBUZ）生生产组织与与计划中的划中的 数学方法数学方法提出提出 “解乘数法解乘数法”。1线性性规划介划介绍列奥尼德列奥尼德康托康托罗维奇，前奇，前苏联人，由于在人，由于在1939年年创立立了享誉全球的了享誉全球的线形形规划要点，划要点，对资源最源最优分配理分配理论做做出了出了贡献，而献，而获得得诺贝尔经济学学奖。3美国科学院院士美国科学院院士DANTZIG（丹（丹齐克），克），1948年在年在研究美国空研究美国空军资源的源的优化配置化配置时提出提出线性性规划及其通用划及其通用解法解法“单纯形法形法”。被称。被称为线性性规划之父。划之父。1线性性规划介划介绍 线性规划之父的Dantzig(丹齐克)。据说，一次上课，Dantzig迟到 了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是 惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解,后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。41线性性规划介划介绍 1960 1960年，年，“最佳最佳资源利用的源利用的经济计算算”康托洛康托洛维奇和奇和库伯曼斯伯曼斯(Koopmans)(Koopmans)。两人。两人因因对资源最源最优分配理分配理论的的贡献而献而获19751975年年诺贝尔经济学学奖 佳林佳林库普曼斯，美国人，他将数理普曼斯，美国人，他将数理统计学成功运用学成功运用于于经济计量学，量学，对资源最源最优分配理分配理论做出了做出了贡献。献。51961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题。计算机 50约束 100变量 30000约束 3000000变量1线性性规划介划介绍6从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年获得诺贝尔经济奖。71线性性规划介划介绍线性规划研究的主要问题：有一定的人力、财力、资源条件下，如何合理安排使用，效益最高?某项任务确定后，如何安排人、财、物，使之最省?8 例例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线性性规划数学模型划数学模型9例例2 捷运公司捷运公司拟在下一年度的在下一年度的1-4月的月的4个月内需租用个月内需租用仓库堆堆放物放物资。已知各月份所需。已知各月份所需仓库面面积数列数列见下表。下表。仓库租借租借费用随用随合同期定，期限越合同期定，期限越长折扣越大，具体数字折扣越大，具体数字见下表。租借下表。租借仓库的合的合同每月初都可同每月初都可办理，每份台同具体理，每份台同具体现定租用面定租用面积数和期限。因此数和期限。因此该厂可根据需要，在任何一个月初厂可根据需要，在任何一个月初办理租借台同。每次理租借台同。每次办理理时可可签一份，也可一份，也可签若干份租用面若干份租用面积和租借期限不同的合同，和租借期限不同的合同，试确定确定该公司公司签订租借合同的最租借合同的最优决策，目的是使所付租借决策，目的是使所付租借费用最小。用最小。月份月份1 12 23 34 4所需所需仓库面面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租合同期内的租费280028004500450060006000730073002线性性规划数学模型划数学模型10目目标函数函数约束条件束条件解：用解：用变量量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 1用数学用数学语言描述言描述2线性性规划数学模型划数学模型11解：设变量xij表示捷运公司在第i(i1，4)个月初签订的租借期为jj1，4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例例2 2月份月份1 12 23 34 4所需所需仓库面面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租合同期内的租费280028004500450060006000730073002线性性规划数学模型划数学模型12 A B 备用用资源源 煤煤 1 2 30 劳动日日 3 2 60 仓库 0 2 24 利利润 40 50求：最大利润的生产计划。练习1 生生产计划划问题2线性性规划数学模型划数学模型13max Z=40 x1+50 x2解:设产品A,B产量分别为变量x1，x2x1+2x2 30 3x1+2x2 602x2 24x1，x2 0s.t.2线性性规划数学模型划数学模型14求：最低成本的原料混合方案？求：最低成本的原料混合方案？原料原料 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线性性规划数学模型划数学模型15解：解：设每每单位添加位添加剂中原料中原料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线性性规划数学模型划数学模型16决策变量：向量(x1 xn)T 决策人要考虑和控制的因素。非负约束条件：线性等式或不等式目标函数：Z=(x1 xn)线性式，求Z极大或极小线性规划模型特点2线性性规划数学模型划数学模型17如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性性规划的数学模型划的数学模型。实际问题中线性的含义：一是严格的比例性二是可叠加性关于关于线性的界定性的界定2线性性规划数学模型划数学模型1819max(min)Z=c1x1+c2x2+cnxnn个个变量量价价值系系数数第第i 种种资源的源的拥有有量量技技术系数或系数或工工艺系数系数a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2 am1x1+am2x2+amnxn(=,)bmxj 0(j=1,n)s.t.线性性规划的一般式划的一般式2线性性规划数学模型划数学模型线性性规划的划的简写式写式2线性性规划数学模型划数学模型20线性性规划的向量表示式划的向量表示式2线性性规划数学模型划数学模型21线性性规划的矩划的矩阵表示式表示式2线性性规划数学模型划数学模型22比例性：决策变量变化引起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij,bi,ci为确定值。隐含的假含的假设2线性性规划数学模型划数学模型23仓库工厂 1 2 3 库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35练习3 运运输问题工厂需要的原棉存放在三个仓库中，现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如表所示。问使总运费最小的运输方案？2线性性规划数学模型划数学模型24解：解：设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线性性规划数学模型划数学模型25练习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线性性规划数学模型划数学模型26解解：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线性性规划数学模型划数学模型27线性性规划划问题应用用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)2线性性规划数学模型划数学模型28线性性规划的适用情况划的适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件2线性性规划数学模型划数学模型29线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,0线性规划的标准形式目标函数：max约束条件：=变量符号：03线性性规划划标准形式准形式30标准型的一般型准型的一般型min z=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线性性规划划标准形式准形式31 P1 P2 Pn a11 a12 a1n其中 A=a21 a22 a2n am1 am2 amn x1 x=x2 xn b1 b=b2 bmC=(C1 C2 Cn)标准型的矩准型的矩阵型型min Z=Ax=b x 0 b0 b 0 0 3线性性规划划标准形式准形式32 x1Ax=(P1 P2 Pn)x2 =b xn P1 x1+P2 x2+Pn xn=b标准型的向量型准型的向量型3线性性规划划标准形式准形式33线性性规划划问题化化标准型：准型：(1)、约束条件(2)、变量(3)、目标函数(4)、右端常数3线性性规划划标准形式准形式34(1)、约束条件束条件x3为松弛变量x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当约束条件为“”时：当约束条件为“”时：3线性性规划划标准形式准形式353线性性规划划标准形式准形式 x1+2x2+x3 =30 s.t.3x1+2x2 +x4 =60 2x2 +x5=24 x1,x5 0 0 转化化为：min Z=40 x1+50 x2+0-x3+0 x4+0 x5 x1+2x2 30 3x1+2x2 60s.t.2x2 24 x1，x2 0 例：例：min Z=40 x1+50 x2松弛松弛变量量363线性性规划划标准形式准形式例：例：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 剩余剩余变量量37(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线性性规划划标准形式准形式38x1+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线性性规划划标准形式准形式39(3)、目、目标函数函数xo-ZZ令Z =-Z 3线性性规划划标准形式准形式40(4)、右端常数、右端常数右端项b0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。3线性性规划划标准形式准形式41例3：将 max Z=-x1+2x2-3x3x1+x2+x3 7x1-x2+x3 2x1，x20，x3无限制化为标准型3线性性规划划标准形式准形式42解：令x3=x4-x5 加松弛变量x6加剩余变量x7 令Z=-Zmin Z=x1-2x2+3x4-3x5 x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,x2,x4,x7 0max Z=-x1+2x2-3x3x1+x2+x3 7x1-x2+x3 2x1，x20，x3无限制3线性性规划划标准形式准形式43(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线性性规划划标准形式准形式44(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线性性规划划标准形式准形式45Ax=b (1)x 0 (2)maxZ=(3)定义1：满足约束(1)、(2)的x=(x1 xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为LP问题的最优解线性性规划的划的标准型准型4线性性规划的划的图解法解法46图解法求解的目的：一是判别线性规划问题的求解结局；二是在存在最优解的条件下，把问题的最优解找出来。4线性性规划的划的图解法解法47图解法的步骤：1、在平面上建立直角坐标系；2、图示约束条件，找出可行域；3、图示目标函数和寻找最优解。4线性性规划的划的图解法解法48例4 max Z=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 04线性性规划的划的图解法解法49解：(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线性性规划的划的图解法解法50(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线性性规划的划的图解法解法51Z=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线性性规划的划的图解法解法524线性性规划的划的图解法解法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.553无界解无有限最优解例6、maxZ=2x1+4x2 2x1+x2 8-2x1+x2 2x1,x2 0Z=02x1+x2=8-2x1+x2=28246x240 x14线性性规划的划的图解法解法54例7、maxZ=3x1+2x2-x1-x2 1x1,x2 0无解无可行解-1x1-1x204线性性规划的划的图解法解法55唯一解无穷多解 无有限最优解 无可行解有解无解当目标函数的直线族与某约束条件平行，且该问题有解时。约束条件无公共区域。有解但可行域可伸展到无穷时总 结4线性性规划的划的图解法解法56由由图解法得到的启示解法得到的启示(1)、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。(2)、若线性规划可行域存在，则可行域是一个凸集。(3)、若有最优解，定可在可行域的顶点得到。(4)、解题思路是找出凸集的各顶点的最大目标函数值。4线性性规划的划的图解法解法57min Z=Ax=b x0A mn 满秩 x=(x1 xn)T 一、一、线性性规划划问题的解的概念的解的概念5线性性规划基本概念划基本概念58定定义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线性性规划基本概念划基本概念59A=(P1 Pm Pm+1 Pn)=(BN)基向量 非基向量x=(x1 xm xm+1 xn)T=(xB xN)T 基变量 非基变量 xB xNB中的每一个列向量Pj称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。5线性性规划基本概念划基本概念60Ax=b的求解的求解xB xN(B N)=bBxB+NxN=bBxB=b-NxNxB=B-1 b-B-1N xNA=(B N)x=(xB xN)T若B为单位矩阵 xB=b-N xN若xN0 xB=B-1 b5线性性规划基本概念划基本概念61定义2：可行解满足方程约束条件的解x（x1，x2，xn)T,称为线性规划问题的可行解。全部可行解的集合称为可行域。定义3：最优解使目标函数达到最大值的可行解，称为最优解。5线性性规划基本概念划基本概念62定义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线性性规划基本概念划基本概念63例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线性性规划基本概念划基本概念64x1x2x3x4x5x=b=306024B=(P3 P4 P5)=I 是满秩子矩阵 非基 N=(P1 P2)x3=30-(x1+2 x2)x4=60-(3x1+2 x2)x5=24 -2 x25线性性规划基本概念划基本概念65令x1=x2=0,x3=30,x4=60,x5=24x=xN 0 xB B-1 b003060245线性性规划基本概念划基本概念66例9：给定约束条件 -x3+x4=0 x2+x3+x4=3 -x1+x2+x3+x4=2 xj 0(j=1,2,3,4)求出基变量是x1,x3,x4的基本解，是不是可行解？5线性性规划基本概念划基本概念67 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线性性规划基本概念划基本概念68 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线性性规划基本概念划基本概念69凸集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线性性规划基本概念划基本概念70 x(1)x(2)凸多凸多边形形凹多凹多边形形x(1)x(2)5线性性规划基本概念划基本概念第一章71 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线性性规划基本概念划基本概念72 凸集D,点 xD，若找不到两个不同的点x(1),x(2)D 使得 x=x(1)+(1-)x(2)(0 1)则称x为 D的顶点。定定义3顶点点5线性性规划基本概念划基本概念73证明：设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线性性规划基本概念划基本概念74只须证明：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线性性规划基本概念划基本概念75证明可用归纳法（略）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线性性规划基本概念划基本概念76证明：设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线性性规划基本概念划基本概念77引理引理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线性性规划基本概念划基本概念79选任一不为零的数令 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线性性规划基本概念划基本概念8081证明：()不是顶点，不是基可行解设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线性性规划基本概念划基本概念82由(a)(b)得(x1(1)x1(2)p1+(xk(1)xk(2)pk=0即x不是基可行解所以 p1,pk 线性相关定理定理4 若若线性性规划划问题有最有最优解，一定存在一个基解，一定存在一个基可行解是最可行解是最优解。解。5线性性规划基本概念划基本概念83 (LP)问题的基本可行解 可行域的顶点。若(LP)问题有最优解，必可以在基本可行解(顶点)达到。若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。5线性性规划基本概念划基本概念LP问题解的性解的性质84