管理运筹学 课件 02线性规划及单纯形法

第1章线性规划及单纯形法1.1一般线性规划问题的数学模型

第一化工厂每天排放污水2万m3，第二化工厂每天排放污水1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/万m3和800元/万m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？例1

靠近某河流有两个化工厂，流经一厂的河流流量为每天500万m3，工厂之间有一条流量为每天200万m3的支流。1.1.1问题提出

设工厂1和工厂2每天分别处理污水x1和x2万m3，则有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4x1,x2≥0

设备产品ABCD利润(元)

Ⅰ21402

Ⅱ22043

有效台时1281612

例2已知资料如表所示，问如何安排生产才能使利润最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12设：X1——产品Ⅰ产量X2——产品Ⅱ产量建模1.1.1问题提出1.用未知自变量(决策变量)表示可变因素，变量的一组数据代

表一种解决方案，通常情况下决策变量取非负值。2．都有一个要达到的目标，它也是自变量的线性函数，称为

目标函数。根据需要，要求目标函数极大化或极小化。3．存在限制条件，它们可用自变量的线性方程(等式)或线性不

等式来表示。这些条件称为约束条件。

以上例子的共同特征：1.1.1问题提出maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12设：X1——产品Ⅰ产量，X2——产品Ⅱ产量线性规划数学模型三要素1.1.1问题提出6其他典型问题：合理下料问题运输问题投资组合问题1.1.1问题提出1.1.2线性规划问题的数学模型的表示一般表示方式:

目标函数：约束条件：1.1一般线性规划问题的数学模型简写形式1.1一般线性规划问题的数学模型1.1.2线性规划问题的数学模型的表示向量形式1.1一般线性规划问题的数学模型1.1.2线性规划问题的数学模型的表示矩阵形式1.1一般线性规划问题的数学模型1.1.2线性规划问题的数学模型的表示练习1：某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划。1.1一般线性规划问题的数学模型1.1.3线性规划问题的标准形式maxz=c1x1+c2x2++cnxna11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2

am1x1+am2x2++amnxn=bmx1,x2,,xn≥0其中，bi≥0(i=1,2,,m)（一）定义及形式一般形式1.1一般线性规划问题的数学模型简写形式矩阵形式（一）定义及形式1.1.3线性规划问题的标准形式1.1一般线性规划问题的数学模型（二）如何将一般问题化为标准型1、目标函数为minz=c1x1+c2x2++cnxn令z=-z,变为maxz

=-c1x1-c2x2--cnxn2、约束条件为a11x1+a12x2++a1nxn≤b1加入非负变量xn+1，称为松弛变量，有

a11x1+a12x2++a1nxn+xn+1=b11.1一般线性规划问题的数学模型1.1.3线性规划问题的标准形式（二）如何将一般问题化为标准型令xj=xj-xj

，对模型中的进行变量代换。3、约束条件为a11x1+a12x2++a1nxn≥b1减去非负变量xn+1，称为剩余变量，有

a11x1+a12x2++a1nxn-xn+1=b14、变量xj无约束。1.1一般线性规划问题的数学模型1.1.3线性规划问题的标准形式（二）如何将一般问题化为标准型令xj=xj-xj

，对模型中的进行变量代换。3、约束条件为a11x1+a12x2++a1nxn≥b1减去非负变量xn+1，称为剩余变量，有

a11x1+a12x2++a1nxn-xn+1=b14、变量xj无约束。令xj

=-xj5、变量xj≤01.1一般线性规划问题的数学模型1.1.3线性规划问题的标准形式minz=x1+2x2

+3x3

s.t.-2x1+x2+x3≤9-3x1+x2+2x3≥43x1-2x2-3x3=-6x1≤0,x2≥0,x3取值无约束例3（二）如何将一般问题化为标准型1.1一般线性规划问题的数学模型1.1.3线性规划问题的标准形式解：令得标准形式为：1.1.3线性规划问题的标准形式1.1.4线性规划问题的解19一、线性规划问题的解求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。Maxz=CX（1）

s.t.AX=b（2）

X

0（3）（一）解、可行解、最优解1.满足约束条件（2）

的X，称为线性规划

问题的解。2.满足约束条件（2）与（3）的X，称为线性规划的问题可行解。3.满足目标函数（1）的可行解X，称为线性规划的问题最优解。1.1.4线性规划问题的解（二）基、基向量、基变量1.设r(A)=m,并且B是A的m

阶非奇异的子矩阵（det(B)

0),则称矩阵B为线性规划问题的一个基。1.1.4线性规划问题的解（二）基、基向量、基变量1.设r(A)=m,并且B是A的m

阶非奇异的子矩阵（det(B)

0),则称矩阵B为线性规划问题的一个基。1.1.4线性规划问题的解

maxZ=2x1+3x22x1

+2x2+x3

=12x1

+2x2+x4

=84x1

+

+x5

=164x2

+x6

=12x1

，x2，x3

，x4，x5，x6

02.矩阵B=（P1，P2….Pm)，其列向量Pj称为对应基B的基向量。3.与基向量Pj相对应的变量xj就称为基变量，其余的就称为非基变量。1.1.4线性规划问题的解

maxZ=2x1+3x2

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

0(1)可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。(2)最优解：使目标函数达到最大值的可行解。(3)基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。基本概念小结：1.1.4线性规划问题的解(4)基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。(5)基可行解：满足变量非负的基解称为基可行解(6)可行基：对应于基可行解的基称为可行基1.1.4线性规划问题的解1.1.5有关线性和线性规划模型的假设1比例性目标函数的值同决策变量的取值成严格的比例。2可叠加性决策变量间相互独立，决策变量的各自取值对目标函数

总的取值互不影响。3可分性决策变量允许取小数、分数或任一实数。4确定性线性规划模型中的参数必须是确定的常数1.2图解法1、建立直角坐标系，将约束条件

表示在图中。2、确定满足约束条件的解的范围。3、绘制目标函数的图形。4、确定最优解。一、图解法步骤1.2图解法二、举例⑴⑵⑶⑷一、图解法步骤012345678123456⑴⑵⑶⑷作图∴最优解：x1=4，x2=2有唯一最优解，Z=14x2

x1(42)⑴⑵⑶⑷

例二、

例三、⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2

x2

⑴⑵x1x2

无可行解例四、1.2图解法三、LP问题可行域和解的情况1、可行域封闭唯一最优解2、可行域封闭多个最优解3、可行域开放唯一最优解4、可行域开放多个最优解5、可行域开放目标函数无界6、无可行解1.2图解法四、启示：

图解法的解题思路和几何上的直观结论对求解一般的线性规划有什么启示?1、求解LP问题时，解的四种情况2、若LP问题的可行域存在，则可行域是凸集。3、若存在最优解，则最优解一定在可行域的顶点

（边界）找到4、解题思路：逐个比较凸集顶点的目标函数值。1.3单纯形法原理34凸集：如果集合C中任意两个点，其连线上的所有点也都是集合C中的点。集合C为凸集。顶点：如果对于凸集C中的点X，不存在C中的任意其它两个不同的点，使得X在它们的连线上，这时称X为凸集的顶点。1.3.1预备知识1.3单纯形法原理35定理2:

线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。定理3:

若线性规划问题有最优解，一定存在一个基可行解是最优解。定理1:若线性规划问题存在可行解，则问题的可行域是凸集。1.3.2基本定理maxz=2x1+3x2

（1）s.t.-2x1+3x2

6（2-1）

3x1-2x2

6（2-2）

x1+x2

4（2-3）

x1,x2

0

（3）（1）用图解法求解（2）化为标准形式。（3）找出问题的所有基解，

指出哪些是基可行解。已知下列线性规划问题：练习（1）：x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域本问题解的情况：基解：点（O，A，B，Q1，Q2，Q3，Q4）可行解：由点（O，Q1，Q2，Q3，Q4）围成的区域。基可行解：点（O，Q1，Q2，Q3，Q4）最优解：Q3练习（2）：minz=2x1+3x2s.t.2x1+2x2≤84x1≥12x2≥-16x1≤0,x2

取值无约束。

将下列线性规划问题化为标准形式：1.3单纯形法原理1.3.3单纯形法求解思路寻求最优解的思路：

设给定线性规划问题：（一）确定初始基可行解1.3单纯形法原理添加松弛变量得其标准形为：因此约束方程组的系数矩阵为：（一）确定初始基可行解1.3.3单纯形法求解思路1.3单纯形法原理由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：称其为初始基可行解。（一）确定初始基可行解1.3.3单纯形法求解思路1.3单纯形法原理⑴⑵⑶⑷例：（一）确定初始基可行解1.3.3单纯形法求解思路1.3单纯形法原理（二）从初始基可行解转换到另一个基可行解

思路：对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。1.3.3单纯形法求解思路1.3单纯形法原理（三）最优性检验和解的判别设有基可行解比较两者对应的目标函数值，哪一个更优？1.3.3单纯形法求解思路1.3单纯形法原理（三）最优性检验和解的判别1.3.3单纯形法求解思路1.3单纯形法原理46小结：1、确定初始基可行解2、最优性检验和解的判别3、从初始基可行解转换为另一个基可行解4、重复步骤2-3直至得到最优解设给定线性规划问题：解:标准化：

maxZ=2x1+3x2+0x3+0x4+0x5+0x6

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

01.4单纯形法计算步骤例

maxZ=2x1+3x22x1+2x2

12

x1+2x2

8

4x1

164x2

12x1

，x2

048(1)找到初始可行基，建立初始单纯形表.(2)进行最优性检验2024/6/1349入基变量由最大增加原则确定入基变量：(3)从一个基可行解转换到另一个目标函数值更大的基可行解

当某些非基变量的检验数时，为使目标函数值增加地更快，一般选择正检验数中最大者对应的非基变量入基

，成为新的基变量。

50由最小比值原则选择出基变量；为确保新的基可行解的非零分量非负，按下述规则求得最小比值，其所对应的原基变量中的出基。(3)从一个基可行解转换到另一个目标函数值更大的基可行解由最大增加原则确定入基变量：(3)从一个基可行解转换到另一个目标函数值更大的基可行解由最小比值原则选择出基变量；入基变量由最大增加原则确定入基变量：出基变量52(3)从一个基可行解转换到另一个目标函数值更大的基可行解由最小比值原则选择出基变量；入基变量由最大增加原则确定入基变量：于是，新的一组基是：出基变量以为主元素进行换基迭代：即利用初等行变换将入基变量

所在的系数列变为单位列向量，而变为1。这样原来基矩阵中的就不再是单位向量，取而代之的是，这样就找到了一组新的基。53(3)从一个基可行解转换到另一个目标函数值更大的基可行解由最小比值原则选择出基变量；入基变量由最大增加原则确定入基变量：于是，新的一组基是：出基变量以为主元素进行换基迭代：(4)重复二、三两步，直至找到最优解。54(1)找到初始可行基，建立初始单纯形表.561.4单纯形法计算步骤特殊情况：（1）出现两个或两个以上相同的最大，此时可任选一个所对应的变量作为进基变量。

（2）利用规则决定出基变量时，出现两个或两个以上的最小比值，则迭代后，会出现一个或几个基变量等于零的情况，称此为退化现象。1.4单纯形法计算步骤找出一个初始可行解是否最优转移到另一个基本可行解最优解是否循环核心是：变量迭代结束求解步骤1.4单纯形法计算步骤小结——单纯形法的要点（1）化线性规划模型为标准型，建立初始单纯形表。（2）根据单纯形表按照最大增加原则选择换入变量；（3）按照最小比值原则选择换出变量；（4）实施矩阵的初等变换进行换基迭代；（5）建立新的单纯形表；（6）重复上述过程直到求得最优表格为止。2024/6/1359当所有时，现有顶点对应的基可行解即为最优解。小结——解的情况2024/6/13601.当所有时，现有顶点对应的基可行解即为最优解。小结——解的情况2.当所有时，又对某个非基变量有则该线性规划问题有无穷多最优解。611.当所有时，现有顶点对应的基可行解即为最优解。小结——解的情况2.当所有时，又对某个非基变量有则该线性规划问题有无穷多最优解。3.如果存在某个，又向量的所有分量，对任

意，恒有，则存在无界解。单纯形法与图解法比较例

maxZ=50x1+30x2

4x1+3x2+x3=120(1)2x1+x2+x4=20(2)x1

，x2

040502530(0，0)(15，20)(1)(2)63用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。§1.5单纯形法的进一步讨论64

maxZ=2x1+3x2+0x3+0x4+0x5+0x6

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

0解:将模型标准化例3

maxZ=2x1+3x2

2x1+2x2

12x1+2x2

8

4x1

16

4x2

12x1

，x2

065但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。例maxZ=-3x1+x3

x1+x2+x3

4-2x1+x2

-x3

≥

13x2+x3

=9x1

，x2，x3

0采用人造基的办法：添加人工变量，构造单位矩阵§1.5单纯形法的进一步讨论66

人工单位矩阵的构造方法在“

”的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（-1），所以再加入一个人工变量，其系数是（+1），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。在原本就是“

=”的约束中可直接添加一个人工变量，以便得到初始基矩阵。注意：人工变量是在等式中人为加入的，只有它等于0时，约束条件才是它本来的意义。求解带人工变量的线性规划有两种方法：☆大M法☆两阶段法例解线性规划1.5.1

大M法

68添加人工变量，构造初始基：69-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始单纯形表：CCBXBb0x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-4M070-30100-M-M初始单纯形表：C30211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-4M0-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x1171-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x11-9/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/472此时人工变量全部出基，并已达最优条件。最优解为最优值为-9/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4731.5.2两阶段法

第一阶段：构造目标函数只含人工变量的线性规划问题，求解后判断原线性规划问题是否有基本可行解，若有，则进行第二阶段；第二阶段：将第一阶段的最终单纯形表所对应的解，去掉人工变量，作为第二阶段的初始单纯形表的初始基可行解，进行单纯形法的迭代。1.5.2两阶段法

(2)第二阶段先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即maxz′=-2x1-3x2+0x3，继续迭代：

781.5.3关于解的判别

一、唯一最优解当所有时，该基可行解即为最优解。791.5.3关于解的判别

二、无穷多最优解80二、无穷多最优解1.5.3关于解的判别

81三、无界解1.5.3关于解的判别

82四、无可行解1.5.3关于解的判别

1.5.4单纯形法小结：三要素决策变量约束条件目标函数两个三个以上xj≥0xj无约束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa标准化图解法、单纯形法单纯形法不处理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj′=-xj不处理约束条件两端同乘以-1加松弛变量xs加人工变量xa减去xs加入xa不处理令z′=-Z

0-M个数取值限制右端常数约束方向要求系数A,b,C停止1,3/2§1.6

改进单纯形法——矩阵描述一、矩阵形式的单纯形法若记：线性规划模型为：

maxz=CXAX=bX≥0基变量：XB非基变量：XN

基矩阵：B

非基矩阵：N基变量的价值系数：CB非基变量的价值系数：CN则有：maxz=CBXB+CNXNBXB+NXN=b①XB,XN

≥0为求XB，用B-1左乘①式两端，有：B-1BXB+B-1NXN=B-1b从而有：XB=B-1b−

B-1NXN令非基变量XN=0，则有：1）基变量：XB=B-1b3）目标函数值：z=CBXB=CBB-1b2）检验数：σN=CN−CBB-1N=CB(B-1b−B-1NXN)+CNXN

z=CBXB+CNXN=CBB-1b+(CN−CBB-1N)XN4）非基矩阵:B-1N将XB=B-1b−

B-1NXN代入目标函数：

运筹学的研究步骤ax提出问题建模求解解的检验及控制决策实施例1.7应用举例

设备产品ABCD利润(元)

Ⅰ21402

Ⅱ22043

有效台时1281612已知资料如表所示，问如何安排生产才能使利润最大？1.7应用举例问题可以归结为线性规划模型的条件（1）问题目标能用效益指标度量（2）为达到目标有多种方案（3）目标要在一定约束条件下实现，条件可用线性

等式或不等式描述

设备产品ABCD利润(元)

Ⅰ21402

Ⅱ22043

有效台时1281612已知资料如表所示，问如何安排生产才能使利润最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12设：X1——产品Ⅰ产量X2——产品Ⅱ产量建模1.7应用举例1.7应用举例

例11工业原材料的合理利用解：先看有多少种裁料方案，再进行组合和选择。ⅠⅡⅢⅣⅤⅥ3m4m5m201120210002011300总长/m1111101099料头/m001122某大楼改造工程用11m长角钢切割成钢窗用料。每扇窗含3m长2根、4m长3根，5m长2根，若需钢窗100扇，至少需要多少根角钢原材料？1.7应用举例