第一章绪论线性规划与单纯形法

运筹学OperationsResearch夫运筹帷幄之中，决胜千里之外。“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。——《大英百科全书》运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”——《中国大百科全书》运筹学定义运筹学“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效地使用人力物力”——《辞海》运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理”。——《中国企业管理百科全书》运筹学定义运筹学所研究的，通常是在必须分配稀缺资源的条件下，科学地决定如何最佳地设计和运营人—机系统。对象：人—机系统条件：资源稀缺方法：模型化，定量化特点：最优化目的：决策支持运筹学定义运筹学简史起源：古代战争、娱乐、建设田忌赛马丁渭修皇宫学科产生：第二次世界大战问题：合理利用稀缺战争资源保护自己、消灭敌人1938年7月，波得塞雷达站的负责人罗伊用OperationalResearch命名防空作战系统运行的研究1940年9月英国成立了由物理学家布莱克特(Blackett)领导的第一个运筹学小组l942年美国和加拿大也都相继成立运筹学小组运筹学简史反潜艇战库普曼(Koopmans)——搜索论肖克莱(Shockley)对策论商船编队和舰队护航扩展：战后用于民用事业成型：各个分支成熟成熟：计算机、信息技术结合发展：学科结合、渗透应用广度和深度、方法和算法的完善运筹学模型特点：系统的整体观念多学科的综合模型方法的应用符号语言、便于交流事前分析、减少失误抽象反映实际、突出共性优点：确定目标，明确约束抓主要矛盾、舍次要矛盾选择模型、设定变量描述约束和目标、确定参数选择求解方法、求解问题灵敏度分析、评价汇总、解释结果、报告

运筹学方法论提出问题建立模型求解、优化测试、控制方案实施学科主要分支规划理论线性规划非线性规划运输问题整数规划动态规划目标规划图论与网络理论排队论存储论决策论对策论冲突分析可靠性理论计划协调技术图解协调技术国内教学中常用的求解运筹学模型的软件LINDOWinQSBExcel对于大型复杂的数学模型，通常先要使用一个建模系统有效表达数学模型并将其输入计算机AMPLMPLOPLGAMSLINGO运筹学算法与主要应用软件第一章线性规划及单纯形法线性规划及单纯形法线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子§1线性规划问题问题的提出线性规划问题的数学模型线性规划概念和模型问题的提出例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。数学模型例1中先用变量x1和x2分别表示美佳公司制造家电Ⅰ和Ⅱ的数量。这时该公司可获取的利润为(2x1+x2)元，令z=2x1+x2，因问题中要求获取的利润为最大，即maxz。z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件。由此例1的数学模型可表为：数学模型(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max:maximize的缩写，“最大化”，s.t.

subjectto的缩写，“受限制于……”问题的提出例2

捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表1-2单位：100m2表1-3单位：元/100m2数学模型例2中若用变量xij表示捷运公司在第i(i=1,…,4)个月初签订的租借期为j(j=1,…,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：目标函数约束条件s.t.min：minimize，“最小化”概念和模型定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。概念和模型一般形式：max（或min）

目标函数约束条件非负约束称为决策变量

称为价值系数或目标函数系数

称为资源常数或约束右端常数称为技术系数或约束系数

概念和模型紧缩形式：max（或min）

概念和模型矩阵形式：max（或min）

称为决策变量向量

称为价值系数向量或目标函数系数向量

称为资源常数向量或约束右端常数向量称为技术系数或约束系数矩阵

标准形式标准型的主要特征：①目标最大；②约束等式；③变量非负；④右端非负。标准型标准型的紧缩形式：标准型的矩阵形式：标准型标准型的向量形式：其中：标准化把一般的LP化成标准型的过程称为线性规划问题的标准化方法：1目标标准化

minZ

等价于max(-Z)maxZ’=-∑cjxj2化约束为等式加松弛变量、减剩余变量3变量非负化做变换或4右端非负标准化标准化举例（例3）：线性规划及单纯形法线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子§2图解法1．什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。图解法2.图解法(例1)运用图解法，以求出最优生产计划（最优解）。

(1.1c)(1.1a)(1.1b)(1.1d)图解法

由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。

1.建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。2.对约束条件加以图解，找出可行域。3.画出目标函数等值线。4.结合目标函数的要求求出最优解。图

解

法(1.1c)(1.1a)(1.1b)(1.1d)图解法 (a)可行域有界(b)可行域有界 (c)可行域无界 唯一最优解 多个最优解

唯一最优解(d)可行域无界

(e)可行域无界

(f)可行域为空集 多个最优解

目标函数无界

无可行解线性规划及单纯形法线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子§3单纯形法原理线性规划问题的解的概念凸集及其顶点几个基本定理解

的

概

念可行解：变量满足所有约束条件的一组值可行解集：所有可行解构成的集合可行域：可行解集构成n维空间的区域线性规划问题解的概念最优解：使得目标函数达到最优的可行解最优值：最优解对应的目标函数值目的：求最优解和最优值求解方法：单纯形法解的概念先研究AX=b设系数矩阵A是m×n矩阵，秩为m，B是A中m×m阶非奇异子矩阵（即|B|≠0），则称B是线性规划问题的一个基。B是由m个线性独立的列向量组成基向量基变量非基变量：其余变量解的概念AX=BXB+NXN=b令非基变量XN=0得BXB=b和特解XB=B-1b结合XN=0

称为对应于B的基本解；基本解个数=基的个数≤Cnm基可行解可行的基本解

XB≥0XN=0可行基：对应于基可行解的基A=（B|N）解的概念最优基：对应的基本可行解也是最优.基本可行解个数≤基的个数≤Cnm基本可行解的非零分量均为正分量，其正分量个数≤m。退化的基本可行解：基本可行解的非零分量个数小于m时，也就是在基本可行解中一个或多于一个的基变量取零值时凸

集

及

其

顶

点1、基本概念：

凸集——设K是n维欧氏空间的一个点集，若任意两点X（1）∈K，X（2）∈K的连线上的一切点：

αX（1）+（1-α）X（2）∈

K（0<α<1），则称K为凸集。凸

集

的

概

念顶点设K是凸集，XK；若K中不存在两个不同的点X（1）

K，X（2）

K使

X=αX（1）+（1-α）X（2）（0<α<1）则称X为K的一个顶点（也称为极点或角点）。凸

集

的

概

念凸集凸集不是凸集顶点基

本

定

理若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解。定理1引理定理2定理3若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。线性规划问题的可行解x＝(x1,x2,…,xn)为基可行解的充要条件是x的正分量所对应的系数列向量是线性独立的。线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点解的几何意义猜想1线性规划的可行域是凸集；猜想2最优解若存在，则可以在可行域的顶点上得到；猜想3可行域的顶点的个数是有限的；猜想4若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个猜想5

对于标准型的线性规划X是可行域顶点的充分必要条件是X是基本可行解。求解思路

求一个初始基本可行解

是

判断基本可行解是否最优结束

不是

求使目标得到改善的基本可行解

是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？线性规划及单纯形法线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子§4单纯形法迭代原理单纯形方法引例单纯形法的一般描述表格单纯形法一般问题的处理单纯形法矩阵描述几点注意事项单纯形方法引例用单纯形法的思想求解线性规划问题：单纯形方法引例基本解（0，0，0，3，9）也是可行的.

单纯形方法引例初始基本可行解X(0)=（0，0，0，3，9）含义：不生产任何产品，工时剩余为3，材料剩余为9，利润为Z(0)=0

初始基本可行解是否最优解?是否可以生产某种产品使目标提高？当x1（或x2,x3）增加一个单位时，会使目标增加2（或3）单位

单纯形方法引例初始基本可行解X(0)=（0，0，0，3，9）当x1（或x2,x3）增加一个单位时，会使目标增加2（或3）单位考虑将x1（或x2,x3）并为非零变量，x2,x3价值系数加大，将x2变为基变量——引入变量。单纯形方法引例初始基本可行解X(0)=（0，0，0，3，9）当x2作为引入变量，为使新解X(1)仍为基可行解，必须使且使x4或x5中有一个等于零——退出变量（1-1）单纯形方法引例由(1-1)第四、第五式，得为使新解X(1)为基可行解此时，变为零，x5为退出变量新的基可行解为X(1)=(0,9/4,0,3/4,0)目标函数值Z(1)=27/4>Z(0)单纯形方法引例系数列向量此时，进一步分析引入x1或x3是否会更好？引入哪一个更好？单纯形方法引例首先考虑引入x1，由于计算增加单位x1所创增的净经济价值同理，可计算增加单位x3所创增的净经济价值检验数单纯形方法引例基本可行解X(1)=(0,9/4,0,3/4,0)取x1进基，同样，此时，为x4退出变量。新的基可行解为X(2)=(1,2,0,0,0)目标函数Z(2)=2+6=8>27/4=Z(0)此时非基变量检验数均为负，解最优单纯形法一般步骤1.初始基本可行解的确定（观察法）；单纯形法一般步骤1.初始基本可行解的确定（观察法）；基基本可行解单纯形法一般步骤2.从约束中解出基变量；单纯形法一般步骤3.代入目标消去基变量，得到非基变量xj的检验数

j；单纯形法一般步骤3.代入目标消去基变量，得到非基变量xj的检验数

j；单纯形法一般步骤4.判断最优；最优性判别定理：若是对应于B的基本可行解，j是用非基变量表示目标函数的表达式中非基变量xj的检验数，若对于一切非基变量的角指数j均有j≤0则当前基本可行解为最优解。对于任意可行解X，对于基本可行解X0，单纯形法一般步骤5.没有有限最优解的判断；无最优解判别定理：若是对应于B的基本可行解，非基变量xk的检验数k>0,且对于i=1,2,……,m均有aik≤0,则问题没有有限最优解。单纯形法一般步骤6.改进目标若k>0，则选xk进基;用最小比值法确定xk的最大值θ，使基变量xl取0值，其它基变量非负；即xl出基，目标改善kθ，换基过程若θ不存在,则Z→∞，没有有限最优解。单纯形法一般步骤7.主元变换（枢变换或旋转变换）xk进基，xl出基，解出新的基变量表格单纯形法表格单纯形法表格单纯形法基变量检验数最小比值列基变量系数右端常数CB基

cj21000bx1x2x3x4x50x315051000x424620100x5511001cj-zj21000解：表1-701/602/614x120-1/301/30cj-zj1-1/604/601x500015015x30x5x4x3x2x1b00012

cj基CB表1-8-1/21/40017/2x12-1/2-1/4000cj-zj3/2-1/40103/2x21-15/25/410015/2x30x5x4x3x2x1b00012

cj基CB表1-9表1-9中所有j<=0,且基变量中不含人工变量，最优解X=(7/2,3/2,15/2,0,0);最优值Z=17/2.练习1：求解线性规划CB

XB

cj25000

xj

bx1x2x3x4x50x34111004/10x42-12010∞0x521-10012/1cj-zj０25０００表格单纯形法CB

XB

cj25000

xj

bx1x2x3x4x50x34111004/10x42-12010∞0x521-10012/1cj-zj0250002x121-1001∞0x320210-12/20x44010114/1cj-zj-40700-2向右迭代一步练习2：求解线性规划CB

XB

cj1200

xj

bx1x2x3x40x301-2100x431001－Ｚ０12００表格单纯形法没有有限最优解算法思路

求一个初始基本可行解

是

判断基本可行解是否最优

结束

不是

求使目标得到改善的基本可行解

是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？§5单

纯

形

法

进

一

步

讨

论处理方法一大Ｍ法人造基添加人工变量造成基去掉人工变量人工变量§5单

纯

形

法

进

一

步

讨

论原问题的可行解新问题的可行解目标值结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解例6大M法-M0-10x500010x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40x7x4x3x2x1b-M010-3cjXBCB表1-100x400011-1/2-1/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/2CBXBcj-30100-M-Mbx1x2x3x4x5x6x70x4331110000x21-21-10-110-Mx766310001cj-zj6M-304M+103M-4M00x400001-1/21/2-1/20x25/2-1/2100-1/41/41/4-3x33/23/20103/401/4cj-zj-2/9000-3/4-M+3/4-M-1/4最优解:X=(0,5/2,3/2,0,0,0,0)最优值：Z=3/2大M法举例CB

XB

cj1200-M

xj

bx1x2x3x4x50x4111010-Mx54-12-101cj-zj012000CB

XB

cj-1-200-M

xj

bx1x2x3x4x50x4111010-Mx54-12-101cj-zj012000-2x2111010-Mx52-30-1-21cj-zj210020CB

XB

cj-1-200-M

xj

bx1x2x3x4x5-2x2111010-Mx52-30-1-21－Ｚ210020M2-30-1-20所有检验数<0已经是最优解x5=2人工变量不为零,表示原问题无可行解参照图解法结果线性规划及单纯形法线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子单

纯

形

法

进

一

步

讨

论处理方法二两阶段法人造基添加人工变量造成基去掉人工变量人工变量两

阶

段

法如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。单

纯

形

法

进

一

步

讨

论第一阶段第一阶段最优解中:如果Z<0,则原问题没有基本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可行解.否则基本可行解退化,继续迭代就可以得到基本可行解.单

纯

形

法

进

一

步

讨

论第二阶段以第一阶段最优基作为初始基本可行解,继续迭代.第一阶段例6两阶段法第一阶段：-10-10x500010x6-100-11-21x6-10004-2cj-zj1013-19x7-1011114x40x7x4x3x2x1

b-10000

cj

XBCB表1-11请注意:第一阶段的最优解不是唯一的33-11x50-4-31-1x6-100-11-21x2000406cj-zj104066x7-1012033x40x7x4x3x2x1

b-10000

cj

XBCB表1-1101/20-1/2x50-1-1/201/2x6-11/301/3103x20-10000cj-zj1/602/3011x10-1/210000x40x7x4x3x2x1

b-10000

cj

XBCB3/20300cj-zj1/20-1/2x5001/3103x2002/3011x1-312000x40x4x3x2x1

b010-3

cj

XBCB表1-12第二阶段-3/43/4-1/4-1/2x50001-1/25/2x20000-9/2cj-zj0103/23/2x3110000x40x4x3x2x1

b0000

cj

XBCB几点注意事项检验数的计算；进基变量的选取；若有不止一个变量可以进基时,只取一个；最小比值；若有不止一个最小比值时，只能选取其中之一行对应的基变量出基；没有有限最优解的情况；最优解是否唯一；最优表中非基变量检验数等于零时,可能最优解不唯一。线性规划及单纯形法线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子数据包络分析(DataEnvelo