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

第一章第一章 线性规划及单纯形法线性规划及单纯形法1．线性规划介绍2．线性规划数学模型3．线性规划标准形式4．线性规划的图解法5．线性规划基本概念6．单纯形法7．应用举例第一章1．线性规划介绍．线性规划介绍Ø历史悠久，理论成熟，应用广泛Ø运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的Ø解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大第一章线性规划理论的发展线性规划理论的发展：1939年前苏联康托洛维奇（年前苏联康托洛维奇（KOHTOPOBUZ）） 《《生产组织与计划中的生产组织与计划中的 数学方法数学方法》》提出提出 “解乘数法解乘数法”1．线性规划介绍．线性规划介绍列奥尼德列奥尼德·康托罗维奇，前苏联人，由于在康托罗维奇，前苏联人，由于在1939年创年创立了享誉全球的线形规划要点，对资源最优分配理论立了享誉全球的线形规划要点，对资源最优分配理论做出了贡献，而获得诺贝尔经济学奖做出了贡献，而获得诺贝尔经济学奖第一章美国科学院院士美国科学院院士DANTZIG（（丹齐克），丹齐克），1948年在年在研究美国空军资源的优化配置时提出线性规划及其通用研究美国空军资源的优化配置时提出线性规划及其通用解法解法 “单纯形法单纯形法”。

被称为线性规划之父被称为线性规划之父1．线性规划介绍．线性规划介绍 线性规划之父的Dantzig (丹齐克)据说，一次上课，Dantzig迟到 了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头苦做几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是 惭愧几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了Dantzig很不解 , 后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法这个方法是上个世纪前十位的算法 第一章1．线性规划介绍．线性规划介绍 1960 1960年，年，““最佳资源利用的经济计算最佳资源利用的经济计算” ” 康托洛维奇康托洛维奇和库伯曼斯和库伯曼斯( (KoopmansKoopmans) ) 两人两人因对资源最优分配理论的因对资源最优分配理论的贡献而获贡献而获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设备和调试工序每天可用于这两种家电的能力、各售出设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表一件时的获利情况如表I—l所示问该公司应制造所示问该公司应制造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 1用数学语言描述用数学语言描述2．线性规划数学模型．线性规划数学模型第一章解：设变量xij表示捷运公司在第i(i＝1．…，4)个月初签订的租借期为j〔j＝1，…，4)个月的仓库面积的合同(单位为100m2)约束条件目标函数例例2 2月份月份1 12 23 34 4所需所需仓库面积仓库面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租费合同期内的租费280028004500450060006000730073002．线性规划数学模型．线性规划数学模型第一章 A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50求：最大利润的生产计划。

练习练习1 生产计划问题生产计划问题2．线性规划数学模型．线性规划数学模型第一章max Z= 40x1 +50x2解:设产品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．线性规划数学模型．线性规划数学模型第一章max(min)Z=c1x1+ c2x2+…+cnxnn个变量个变量价值系价值系数数第第i 种资种资源的拥有源的拥有量量技术系数或技术系数或工艺系数工艺系数a11x1+ a12x2+…+ a1nxn (=, )b1a21x1+ a22x2+…+ a2nxn (=, )b2 … … … am1x1+ am2x2+…+ amnxn (=, )bmxj 0(j=1,…,n)s.t.线性规划的一般式线性规划的一般式2．线性规划数学模型．线性规划数学模型19第一章线性规划的简写式线性规划的简写式2．线性规划数学模型．线性规划数学模型第一章线性规划的向量表示式线性规划的向量表示式2．线性规划数学模型．线性规划数学模型第一章线性规划的矩阵表示式线性规划的矩阵表示式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   50x21+x22+x23   30x31+x32+x33   10x11 +x21+x31 = 40x12 +x22+x32 = 15x13 +x23+x33 = 35 xij   0st.2．线性规划数学模型．线性规划数学模型第一章练习练习4 4 连续投资连续投资1010万元万元A A：：从第从第1 1年到第年到第4 4年每年初投资，次年末回收本利年每年初投资，次年末回收本利1.1.1515；；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=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  0s.t.2．线性规划数学模型．线性规划数学模型第一章线性规划问题应用线性规划问题应用Ø市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)Ø生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)Ø库存管理(合理物资库存量，停车场大小，设备容量)Ø运输问题Ø财政、会计(预算，贷款，成本分析，投资，证券管理)Ø人事(人员分配，人才评价，工资和奖金的确定)Ø设备管理(维修计划，设备更新)Ø城市管理(供水，污水管理，服务系统设计、运用)2．线性规划数学模型．线性规划数学模型第一章线性规划的适用情况线性规划的适用情况Ø要解决的问题的目标可以用数值指标反映Ø对于要实现的目标有多种方案可选择Ø有影响决策的若干约束条件2．线性规划数学模型．线性规划数学模型第一章线性规划模型的结构目标函数 ：max，min约束条件：≥,=,≤变量符号：：≥0, ≤0线性规划的标准形式目标函数：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 bm…C=(C1 C2 …Cn )标准型的矩阵型标准型的矩阵型maxZ=Cx Ax=b x  0 b0 b 0 0 3．线性规划标准形式．线性规划标准形式第一章 x1Ax=(P1 P2 …Pn ) x2 = b xn …P1 x1+ P2 x2 + … +Pn xn=b标准型的向量型标准型的向量型3．线性规划标准形式．线性规划标准形式第一章线性规划问题化标准型：线性规划问题化标准型：(1)、约束条件(2)、变量(3)、目标函数(4)、右端常数3．线性规划标准形式．线性规划标准形式第一章(1)、约束条件、约束条件x3为松弛变量x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。

当约束条件为“  ”时：当约束条件为“ ”时：3．线性规划标准形式．线性规划标准形式第一章3．线性规划标准形式．线性规划标准形式 X1 +2X2 +X3 =30 s.t. 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 , …, X5  0 0 转化为：转化为：maxZ=40X1+ 50X2+0·X3 +0·X4+0·X5 x1 + 2x2   30 3x1 + 2x2   60s.t. 2x2   24 x1，，x2   0 例：例：max Z= 40x1 +50x2松弛变量松弛变量第一章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 x20令x1= x1'- x1 "2、x取值无约束的情况。

令x’＝- x令x= x'- x"3 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  10x20-6+6  x1+6  10+6 令x1' = x1 +6 0  x1' 163．线性规划标准形式．线性规划标准形式第一章(3)、目标函数、目标函数xoZ-Z令Z ' = - Z 3．线性规划标准形式．线性规划标准形式第一章(4)、右端常数、右端常数右端项b＜0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零3．线性规划标准形式．线性规划标准形式第一章例3：将 min Z = -x1+2x2 -3x3x1+x2 +x3 7x1 -x2 +x3 2x1，x20，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，x20，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 = 10x1 , x2 无约束 s.t.3．线性规划标准形式．线性规划标准形式第一章作业作业: 课本课本P44 1．．23．线性规划标准形式．线性规划标准形式第一章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=40x1+ 50x2 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 =24203010x14．线性规划的图解法．线性规划的图解法第一章(2)、求最优解最优解：x* = (15,7.5) Zmax =975Z=40x1+50x20=40x1+50x2 (0,0)， (10,-8)x20102030203010x1DABCC点： x1+2x2 =30 3x1+2x2 =604．线性规划的图解法．线性规划的图解法第一章Z= 40 x1 + 80x2 =0 x1 + 2x2 =30DABCx20x1解: 最优解：BC线段B点 C点x(1)=(6,12) x(2)=(15,7.5)x= x(1)+(1-) x(2) (0   1)例5、 maxZ=40x1+ 80x2 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=28246x240x14．线性规划的图解法．线性规划的图解法第一章例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 x0A m×n 满秩 x = (x1… xn)T 一、线性规划问题的解的概念一、线性规划问题的解的概念5．线性规划基本概念．线性规划基本概念第一章定义定义1：：基基(基阵基阵) ——设A为约束方程组的m×n阶系数矩阵设(n>m)，其秩为m，B是矩阵A中的一个m×m阶的满秩子矩阵，称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 xN…B中的每一个列向量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若xN＝0 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 b0，称基解为基本可行解，也称基可行解 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/2∴x=(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, 点 xD，若找不到两个不同的点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 则 xC，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因为 x＝1/2 x(1) + 1/2 x(2)所以 x不是可行域的顶点5．线性规划基本概念．线性规划基本概念第一章证明：( ) 不是顶点，不是基可行解设x为可行解xj >0 j =1, … ,kxj =0 j =k+1, … ,n若x不是顶点，则有x(1) ＝ x(2) C，使得： x = x(1) +(1-  ) x(2) (0 < < 1) xj = xj (1) +(1-  ) xj (2) (j =1, … ,k)0= xj (1) +(1-  ) xj (2) (j =k+1, … ,n)5．线性规划基本概念．线性规划基本概念83第一章因为 >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系数矩阵的增广矩阵系数矩阵的增广矩阵二、基可行解的转换二、基可行解的转换6.1 单纯形法迭代原理单纯形法迭代原理第一章Pj= aij Pimi=1Pj－ aij Pi＝0 m i=1两边乘上一个正数θ>0，得θ (Pj－ aij Pi）=0 m i=1同 相加整理得： Pixi0 =bmi=1所以得到另一个点x(1) ,使 Pi xi(1) =bni=1可行解?基解?6.1 单纯形法迭代原理单纯形法迭代原理第一章所以x(1)是可行解令存在：6.1 单纯形法迭代原理单纯形法迭代原理第一章重新排列后不含非基向量的增广矩阵：因alj＞0，故上述矩阵元素组成的行列式不为零，P1,P2,…Pl-1,Pj,Pl+1,…,Pm 是一个基所以， x(1) ，是基可行解0 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 ？6.1 单纯形法迭代原理单纯形法迭代原理第一章将基本可行解x（0）和x（1）分别代入目标函数得：三、最优性检验和解的判别三、最优性检验和解的判别6.1 单纯形法迭代原理单纯形法迭代原理第一章是对线性规划问题的解进行最优性检验的标志Ø当所有的σi<=0时，现有顶点为最优解Ø当所有的σi<=0时，又对某个非基变量xj,有Cj-Zj=0，且可找到 θ ＞0，则有无穷多最优解Ø当存在某个σj>0，又Pj<=0,则有无界解通常简写为6.1 单纯形法迭代原理单纯形法迭代原理第一章1) 找出初始基可行解，建立单纯形表6.2 单纯形法计算步骤单纯形法计算步骤Cjc1…cm…cj…cnCBxBbx1…xm…xj…xnc1x1b110…a1j…a1nc2x2b200…a2j…a2n…………….……………cmxmbm01…amj…amn σj=cj-zj0…0……第一章6.2 单纯形法计算步骤单纯形法计算步骤 5） 以a’l,k为主元素进行旋转运算， 转2 ）。

第一章例例10 用单纯形法求解线性规划问题用单纯形法求解线性规划问题max Z= 2x1 +x25x2  156x1 + 2x2  24x1 + x3  5x1 , x2  0s.t.6.2 单纯形法计算步骤单纯形法计算步骤第一章解： 1、先将上述问题化成标准形式有 5x2 +x3 =15 s.t. 6x1 +2x2 +x4 =24 x1 + x2 +x5 =5 x1 , …, x5 0 maxZ=2x1+ x2+0·x3 +0·x4+0·x56.2 单纯形法计算步骤单纯形法计算步骤找到一个初始基可行解 x=(0,0,15,24,5)第一章2、列初始单纯形表：因为σ1 ＞σ2 ，确定x1为换入变量因为θ＝min{-，24/6，5/}＝4所以6为主元素，x4为换出变量Cj21000θCBxBbx1x2x3x4x50x315051000x424620100x5511001 σj=cj-zj6.2 单纯形法计算步骤单纯形法计算步骤第一章3、列新单纯形表：因为σ2 ＞0 ，确定x2为换入变量。

因为θ＝min{15/5，4/2/6，1/4/6}＝3/2所以4/6为主元素，x5为换出元素Cj21000θCBxBbx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61 σj=cj-zj6.2 单纯形法计算步骤单纯形法计算步骤第一章4、列新单纯形表：因为Cj-Zj＜0，所以达到最优解最优解为：x=(7/2,3/2,15/2,0,0)目标函数值为 Z＝2×7/2+1×3/2+0×15/2+0+0=8.5Cj21000θCBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2000-1/42/3 σj=cj-zj6.2 单纯形法计算步骤单纯形法计算步骤第一章练习题练习题解：原问题化为标准型6.2 单纯形法计算步骤单纯形法计算步骤第一章Cj3501000θCBxBbx1x2x3x4x5x6x70x5351110100350x612510-1010120x7500-11001－ σj=cj-zj3501000列初始单纯形表156.2 单纯形法计算步骤单纯形法计算步骤第一章Cj3501000θCBxBbx1x2x3x4x5x6x70x523-40111-10235x212510-1010－0x7500-110015 σj=cj-zj-220060-5016列新单纯形表6.2 单纯形法计算步骤单纯形法计算步骤第一章Cj3501000θCBxBbx1x2x3x4x5x6x70x518-40201-1-195x21751-10011－1x4500-11001－ σj=cj-zj-220600-5－626列新单纯形表6.2 单纯形法计算步骤单纯形法计算步骤第一章Cj3501000θCBxBbx1x2x3x4x5x6x70x39-20100.5-0.5-0.55x22631000.50.50.51x414-20010.5-0.50.5 σj=cj-zj-10000-3-2-36.2 单纯形法计算步骤单纯形法计算步骤第一章6.3 人工变量法人工变量法当化为标准形后的约束条件的系数矩阵中不存在单位矩阵时，可以人为地增加变量，在最优解中人工变量取值必须为零。

为此，令目标函数中人工变量的系数为任意大的负值－M亦称大M法第一章例1：maxZ= 6x1 +4x2 2x1 +3x2  1004x1 +2x2  120 x1 =14 x2  22x1 x2 06.3 人工变量法人工变量法第一章maxZ=6x1+4x22x1 +3x2 +x3 =1004x1 +2x2 +x4 =120 x1 =14 x2 - x5 = 22x1 … x5 0解：化成标准型6.3 人工变量法人工变量法第一章maxZ=6x1+4x2-Mx6 -Mx72x1 +3x2 +x3 =1004x1 +2x2 +x4 =120 x1 +x6 =14 x2 - x5 +x7 = 22x1 … x7 0加人工变量6.3 人工变量法人工变量法第一章Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x310023100000x41204201000-Mx6141000010-Mx7220100-101 σj=cj-zj列初始单纯形表6.3 人工变量法人工变量法第一章Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x31002310000500x4120420100030-Mx614100001014-Mx7220100-101 σj=cj-zjM＋6M+400-M000x37203100-200x46402010-406x1141000010-Mx7220100-101 σj=cj-zj0M+400-M6-M06.3 人工变量法人工变量法第一章Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x3600103-2-30x42000012-4-26x11410000104x2220100-101 σj=cj-zj000046-M4-M0x52001/301-2/3-10x41600-2/310-8/306x11410000104x224011/300-2/3-2 σj=cj-zj00-4/300-M-10/3-M6.3 人工变量法人工变量法第一章6.4 两阶段法两阶段法为了克服大M法的困难，对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。

￿解题思路：第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数(一般取1)，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解显然在第一阶段中，当人工变量取值为0时，目标函数值也为0这时候的最优解就是原线性规划问题的一个基可原线性规划问题的一个基可行解行解第一章作辅助问题minW= yi i=1mxj ， yi  0j=1naij xj + yi =bi ( i=1,2, …,m)原问题 maxZ= Cj xj j=1nxj  0j=1naij xj =bi ( i=1,2, …,m)6.4 两阶段法两阶段法第一章解题过程：解题过程：第第1 1阶段阶段：解辅助问题当进行到最优表时，①、若W=0, 则得到原问题的一个基本可行解，转入第2阶段 ②、若W>0, 则判定原问题无可行解第第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-1θCBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010x530100100 σ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、退化、退化 ： （非退化 θ 值唯一 ） 在下一次迭代中有一个或几个基变量为0，从而出现退化解。

可能可能会导致循环，永远达不到最优解1 1、目标函数极小化时解的最优性判别、目标函数极小化时解的最优性判别 以σi 0作为判别表中解是否最优的标志第一章 则xk进基1）若有两个以上检验数如何解决退化问题？ Dantzig 规则：6.5 计算中的几个问题计算中的几个问题第一章6.5 计算中的几个问题计算中的几个问题 1951 年 Hoffman 给出反例 （ 3个方程，11个变量 ）1955 年 E.M.L.Beale 3 个方程，7个变量 6次迭代后，出现循环 按照 Dantzig规则 ： （5，6，7） （1，6，7） （1，2，7） （3，2，7） （3，4，7） （5，4，7） （5，6，7）第一章Bland 原则 （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-MθCBxBbx1x2x3x4x50x3211100-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根原料 解之得 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项投资的资金额据题意可得： 约束条件：7．． 应用举例应用举例第一章 舱位重量定额（T）占地定额（m3）前 850.0中 1270.0后 730.0 货物重量（T）体积（m3/T）利润（元/T）1145.01002117.01303186.0115494.090 假定这些可乘运其任何一部分目标是要确定每种货物应当装运多少，并且放在哪个舱位才能使这次飞行的总利润最大？例3：一架货运飞机有三个装货舱：前舱.中舱及后舱这些舱对于重量与占地，都有如下所示的定额限制如左表所示此外，在各舱中货物的重量必须跟该舱的重量定额有同样的比例，以便保持飞机的平衡在即将到来的一次飞行中，有下列四种货物要装运，如右表7．． 应用举例应用举例第一章解：设xij表示第i种货物放到第j个舱位的重量约束条件：7．． 应用举例应用举例第一章7．． 应用举例应用举例第一章二、课本二、课本P45 1.7（（1））用大用大M法法 1.7（（2）用两阶段法）用两阶段法作作 业业一、用单纯形法求解下列线性规划：X1=3.75 X2=0.75X1=2X2=6X3=2。