运筹学第01章课件

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

线性规划及单纯形法线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤（必考）单纯形法进一步讨论数据包络分析其他应用例子§1线性规划问题问题的提出线性规划问题的数学模型线性规划概念和模型1

问题的提出例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。表1-1数学模型(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max:maximize的缩写，“最大化”，s.t.

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

捷运公司在下一年度的1~4月的4个月内拟租用仓库堆放物资。该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表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，“最小化”2

概念和模型定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。max（或min）

一、一般形式：max（或min）

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

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

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

2

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

2

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

称为决策变量向量

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

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

2

概念和模型标准形式四、标准型的主要特征：①目标最大；②约束等式；③变量非负；④右端非负。标准化把一般的LP化成标准型的过程称为线性规划问题的标准化方法：1目标标准化

minZ

等价于max(-Z)maxZ’=-∑cjxj2化约束为等式加松弛变量、减剩余变量3变量非负化做变换或4右端非负标准化标准化举例（例3）：3

课堂练习1.课堂讨论3

课堂练习2.习题1.2（2）答案课堂练习§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单纯形法原理线性规划问题的解的概念凸集及其顶点几个基本定理1

解

的

概

念可行解：变量满足所有约束条件的一组值。最优解：

使得目标函数达到最优的可行解。线性规划问题1

解的概念先研究AX=b设系数矩阵A是m×n矩阵，秩为m，B是A中m×m阶非奇异子矩阵（即|B|≠0），则称B是线性规划问题的一个基。B是由m个线性独立的列向量组成。基向量

基变量非基变量：其余变量1

解的概念基可行解：满足非负约束条件的基解称为基可行解可行基：对应于基可行解的基练习1.3（2），找出基可行解和最优解。2

凸

集

及

其

顶

点1、基本概念：

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

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

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

凸

集

的

概

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

K，X（2）

K使

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

凸

集

的

概

念凸集凸集不是凸集顶点3

基

本

定

理若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解。定理1引理定理2定理3若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。线性规划问题的可行解x＝(x1,x2,…,xn)为基可行解的充要条件是x的正分量所对应的系数列向量是线性独立的。线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点3

解的几何意义猜想1线性规划的可行域是凸集；猜想2最优解若存在，则可以在可行域的顶点上得到；猜想3可行域的顶点的个数是有限的；猜想4若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个3

求解思路

求一个初始基可行解

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

不是

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

是否存在？如何得到？是否唯一？如何判断？如何改善？4

单纯形方法引例单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。4

单纯形方法引例用单纯形法的思想求解线性规划问题：第一步：标准化4

单纯形方法引例第一步：标准化基本解（0，0，0，3，9）也是可行的

第二步：初始基可行解4

单纯形方法引例例1:理解换入、换出变量初始基本可行解X(0)=（0，0，0，3，9）含义：不生产任何产品，工时剩余为3，材料剩余为9，利润为Z(0)=0初始基本可行解是否最优解?是否可以生产某种产品使目标提高？当x1（或x2,x3）增加一个单位时，会使目标增加2（或3）单位。

4

单纯形方法引例例1初始基本可行解X(0)=（0，0，0，3，9）当x1（或x2,x3）增加一个单位时，会使目标增加2（或3）单位考虑将x2（或x1,x3）变为非零变量，是由于x2价值系数较大，将x2变为基变量——引入变量。也称为进基变量思考：为什么换x2不换x1呢？4

单纯形方法引例例1初始基本可行解X(0)=（0，0，0，3，9）当x2作为转入变量，为使新解X(1)仍为基可行解，必须使且使x4或x5中有一个等于零——退出变量（1-1）4

单纯形方法引例例1由(1-1)第四、第五式，得为使新解X(1)为基可行解，取交集，即此时，变为零，x5为退出变量新的基可行解为X(1)=(0,9/4,0,3/4,0)目标函数值Z(1)=27/4>Z(0)也称为离基变量4

单纯形方法引例例2理解检验数系数列向量此时，基变量进一步分析引入x1或x3是否会更好？引入哪一个更好？4

单纯形方法引例首先考虑引入x1，由于计算增加单位x1所创增的净经济价值同理，可计算增加单位x3所创增的净经济价值检验数4

单纯形方法引例例基本可行解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)此时非基变量检验数均为负，解最优。5

单纯形法一般步骤1.初始基本可行解的确定（观察法）；5

单纯形法一般步骤1.初始基本可行解的确定（观察法）；基基本可行解5

单纯形法一般步骤2.从约束中解出基变量；5

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

j；！思考：为什么基变量的检验数为0？5

单纯形法一般步骤4.判断最优；最优性判别定理：若是对应于B的基本可行解，j是用非基变量表示目标函数的表达式中非基变量xj的检验数，若对于一切非基变量，均有j≤0则当前基本可行解为最优解。对于任意可行解X，对于基本可行解X0，5

单纯形法一般步骤5.没有有限最优解的判断；无最优解判别定理：若是对应于B的基本可行解.非基变量xk的检验数k>0,且对于i=1,2,……,m均有aik≤0,则问题没有有限最优解。4

单纯形方法引例考虑引入x3，由于计算增加单位x3所创增的净经济价值：检验数5

单纯形法一般步骤6.改进目标

若k>0，则选xk进基变量（换入变量）;用最小比值法确定xk的最大值θ（换出变量）

即xl换出，换出过程；若θ不存在,则Z→∞，没有有限最优解。5

单纯形法一般步骤7.主元变换（枢变换或旋转变换）xk进基，xl出基，解出新的基变量表格单纯形法基变量检验数最小比值列基变量系数右端常数1、练习快速绘制单纯形表0cj-zj00x5x4x3x2x1b00012

cj

XbCB3*5矩阵j=画一个包含7条横线的框，中间一条竖线隔开基变量和系数矩阵。2、快速填写初始单纯形表000x5x4x3x2x1b00012

cj

XbCBjx3x4x51524505100620101100121000CB基

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

cj

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

cj

XbCB表1-9表1-9中所有j<=0,且基变量中不含人工变量，最优解X=(7/2,3/2,15/2,0,0);最优值Z=17/2单纯形表变换通常变换方法：1.将一行同乘以一个不为零的数；2.将一行加减到另一行；3.将一行同乘以一个不为零的数，然后加减到另一行。注意：资源系数一定随着行的变化而变化。价值系数不变。变换的最终结果：将换入变量的列，变换成换出变量列的形式。使得换入变量和其他基变量的系数列向量构成新基。解的判别1.无界解：存在非基变量的检验数j

>0

,且对于Pj≤0。所有的j

≤0，且非基变量的检验数都不为0，有唯一的最优解。所有的j

≤0，其中有非基变量的检验数为0，有无穷多最优解。练习1：求解线性规划用图解法求解可得：无界解练习1：求解线性规划

cj1200CBXBbx1x2x3x40x3

01-2100x4

31001Cj-Zj12００练习1：求解线性规划

cj1200CBXBbx1x2x3x40x3

-30-21-11x1

31001Cj-Zj02０-1

作业1：分别用图解法和单纯形法求解算法思路

求一个初始基本可行解

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

不是

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

是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？例6大M法-M0-10x500010x6-M00-11-21x6-M0014M-2M-3cj-zj101309x7-M011114x40x7x4x3x2x1b-M010-3cjXBCB表1-10罚因子0x400011-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§5单

纯

形

法

进

一

步

讨

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

纯

形

法

进

一

步

讨

论第二阶段以第一阶段最优基作为初始基本可行解,继续迭代。两阶段法第一阶段例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几点注意事项检验数的计算；换入变量的选取：若有不止一个变量可以进基时,只取一个；换出变量选取：若有不止一个最小比值时，只能选取其中之一行对应的基变量出基；最优解是否唯一：最优表中非基变量检验数等于零时,最优解不唯一。作

业作业2用大M法和两阶段法求解下列问题。作

业作业3习题1.13：只列模型不求解作

业