运筹学A-第1章线性规划

第1章线性规划

与单纯形法5/17/20241编辑版ppt第1章线性规划内容提要第一节线性规划问题的数学模型第二节两个变量LP问题的图解法第三节LP问题数学模型的标准型第四节线性规划问题解的性质第五节单纯形法原理及求解步骤2024/5/172编辑版ppt第一节线性规划问题的数学模型

线性规划(LinearProgramming，LP)是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常研究资源的最优利用、设备最佳运行以及费用最低等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。2024/5/173编辑版ppt一、问题的提出（线性规划问题举例）3.26

例1-1(生产计划问题)

某厂在计划期内安排Ⅰ、Ⅱ生产两种产品，已知生产单位产品所需要的设备台数、A和B两种原材料的消耗量以及利润如表1-1所示，问如何安排生产使利润最大？（假设产品全部售出）

产品资源ⅠⅡ资源限量设备（台）原材料A（kg）原材料B（kg）单位产品利润

1402

204381612x1x1x1x2

x2x22024/5/174编辑版ppt(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受资源制约，不能突破有限供给量。设备约束条件的数学表达为：x1+2x2≤8原材料A约束条件数学表达为：4x1≤16原材料B约束条件数学表达为：4x2≤12(3)目标函数：目标函数反映企业利润最大化

maxZ=

2x1+3x2

(4)非负约束：两产品的产量为非负

x1≥0，x2≥0LP模型：s.t.(subjectto)使满足，使服从例1-2见教材第5页2024/5/175编辑版ppt例1-3.某工地租赁甲、乙两种机械安装A、B、C三种构件，这两种机械每天的安装能力、租赁费用以及工程任务如下表所示，问如何租赁甲、乙两机械才能使总的租赁费用最低？构件机械ABC租赁费(元/天)甲（根/天）乙（根/天）任务（根）

56250

8630010207002503502024/5/176编辑版ppt【解】设租赁机械甲x1天、机械乙x2天，则该线性规划问题的数学模型为：例1-4见教材第6页，例【1.2】人员分配问题构件机械ABC租赁费(元/天)甲（根/天）乙（根/天）任务（根）

56250

8630010207002503502024/5/177编辑版ppt某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用多少圆钢来生产这些轴？(切割损失不计)解：1、设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式2.9y1+2.1y2+1.5y3≤7.4表示，求这个不等式关于y1，y2，y3的非负整数解。例如：y1=2，y2=0，则y3只能为1，余料为0.1。像这样的非负整数解共有8组，也就是有8种下料方式，如表1.4所示。

2、建立线性规划数学模型。设xj(j=1,2…,8)为第j种下料方案所用圆钢的根数。思考题：（下料问题）2024/5/178编辑版ppt方案规格12345678需求量y1(2.9m)21110000100y2(2.1m)02103210100y3(1.5m)10130234100总长7.4m0.10.30.90.01.10.20.81.4余料minZ=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4

1002x2+x3+3x5+2x6+x7

100x1+x3+3x4+2x6+3x7+4x8

100xj

0,j=1,2,…,8

(x1=10,x2=50,x4=30,16m)2024/5/179编辑版ppt思考题：某糖果厂用原料A，B，C加工成三种不同牌号糖果甲、乙、丙。已知各种糖果的中A，B，C的含量，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果各多少kg，利润最大？甲乙丙原料成本(元/kg)每月限制用量(kg)A≥60%≥30%2.002000B1.502500C≤20%≤50%≤60%1.001200加工费(元/kg)0.500.400.30售价(元/kg)3.402.852.252024/5/1710编辑版ppt解：设xij为生产第j种糖果使用的第i种原料的公斤数，i=1,2,3；j=1,2,3，则该问题的数学模型可归结为：

最优解：即该厂每月应生产甲种牌号糖果906.67kg，乙种牌号糖果4793.33kg。2024/5/1711编辑版ppt思考题：（投资问题）

某投资公司在第一年初有100万元资金，每年都有如下的投资方案：假使第一年初投入一笔资金，第二年初又继续投入此资金的50%，那么到第三年初就可回收第一年初投入资金的两倍。问：该投资公司如何确定投资策略使第六年初所拥有的资金最多？解：设x1为第一年的投资，x2为第一年的保留资金，则：x1

+x2=100第二年：设x3为第二年新的投资，x4为第二年的保留资金，则：2024/5/1712编辑版ppt第三年：设x5为新的投资，x6为第三年的保留资金；第四年：设新的投资x7，第四年的保留资金x8

；第五年：设x9为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这笔投资要到第七年初才能收回。约束条件每年应满足如下的关系：追加投资金额+新投资金额+保留资金=可利用的资金总额

2024/5/1713编辑版pptX*＝(22.64,72.36,58.54,0,26.02,0,104.06,0,0)T，Z*＝208.12。到第六年初，实有资金总额为x9+2x7，整理后得到下列线性规划模型：maxZ=2x7+x9

第一年投资22.64元;第二年新投资58.54元;第三年新投资26.02元;第四年新投资104.06元;第六年初拥有资金208.12万元。2024/5/1714编辑版ppt思考题：某人有30万元资金，在今后的三年内有以下投资项目可供参考：

(1)三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资；

(2)只允许第一年年初投入，第二年末可收回，本利合计为投资额的150%，但此类投资额不超过15万元；

(3)第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，这类投资限额20万元；

(4)第三年初允许投资，一年回收，可获利40%，投资限额为10万元。试为该人确定一个使第三年末本利和为最大的投资计划？（假设有钱就用于投资）设xij为第i年初投入到j项目的资金额2024/5/1715编辑版ppt项目投资时间1234第1年初x11x12第2年初x21x23第3年初x31x34对于约束条件：第1年，可用于项目1和2投资：

x11+x12=300000第2年，可用于项目1和3投资，投资额为x11的本利和：x21+x23=1.2x11第3年，可用于项目1和4投资，投资额x21和x12有关：x31+x34=1.2x21+1.5x12投资限额：x12≤150000;x23≤200000;x34≤100000非负约束：xij

≥0(i=1,2,3;j=1,2,3,4)对于目标函数，只需考虑第3年末的收益：项目1：x31→1.2x31(本利和)；项目2：x22→0；项目3：x23→1.6x23

(本利和)；项目4：x34→1.4x34

(本利和)；maxZ=1.2x31+1.6x23+1.4x34

2024/5/1716编辑版ppt解：设xij为第i年初投入到j项目的资金额，其数学模型为：maxZ=1.2x31+1.6x23+1.4x34

注意本题条件：有钱就会用于投资，即：可利用的资金=投资金额，据此建立约束等式。x11+x12=300000x21+x23=1.2x11x31+x34=1.2x21+1.5x12x12≤150000x23≤200000x34≤100000xij≥0(i=1,2,3;j=1,2,3,4)2024/5/1717编辑版ppt二、线性规划问题的数学模型3.30线性规划问题的数学模型包括三大要素：（1）一组决策变量（x1,x2,…,xn），是模型中需要首确定的未知量。（2）一组约束条件，是模型中决策变量受到的约束限制，包括两个部分：不等式或等式；非负取值（实际问题）。（3）一个目标函数，是关于决策变量的最优函数，max或min。2024/5/1718编辑版ppt思考：为什么称以上问题为线性规划问题呢？其主要特征是：1.解决的问题是规划问题；2．解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；3．解决问题的约束条件是多个决策变量的线性不等式或等式。2024/5/1719编辑版ppt线性规划问题模型的一般形式可总结为：线性规划问题模型的一般形式用一组非负决策变量表示的一个决策问题；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的极值线性函数。为了书写方便，上式也可简写：2024/5/1720编辑版ppt一般地，xj≥0，但有时xj≤0或xj无符号限制。2024/5/1721编辑版ppt其中：cj为价值系数，C=(c1,c2,…,cn)为价值向量；aij为技术系数，A=(P1,P2,…,Pn)为技术矩阵，如：

P1=(a11,a21,…,am1)T，

P2=(a12,a22,…,am2)T，

……Pn=(a1n,a2n,…,amn)T；

bi为限制系数，b=(b1,b2,…,bm)T。2024/5/1722编辑版ppt线性规划模型矩阵形式，其中：X=(x1,x2,…,xn)T；

C=(c1,c2,…,cn)

；

b=(b1,b2,…,bm)T。技术系数矩阵：2024/5/1723编辑版ppt第二节用于两个变量线性规划问题的图解法1、概念：利用几何图形求解两个变量线性规划问题的方法。

3、求解步骤：

第一步：建立平面直角坐标系；

第三步：在可行域内平移目标函数等值线，确定最优解及最优目标函数值。

2、特点：简单、直观，但只适用于两个变量的LP问题。

第二步：根据约束条件画出可行域；2024/5/1724编辑版ppt可行解：满足约束条件的解；可行域：所有可行解的集合；最优解：使目标函数达到最优的可行解。

可行域：满足所有约束条件的解的集合，即所有约束条件共同围城的区域。maxZ=3x1+5x2

2x1≤162x2≤10

3x1+4x2≤32x1≥0,x2≥0s.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD2024/5/1725编辑版ppt2x1=162x2=10x1x28103583x1+4x2=320ABCD目标函数等值线目标函数Z=3x1+5x2

代表以Z

为参数的一族平行线。Z=25Z=37Z=15(4,5)2024/5/1726编辑版ppt例：用图解法求解线性规划问题？

①坐标系：横坐标x1

，纵坐标x2

Z=360(2,6)②先将约束不等式变为等式，画出各等式对应的直线，然后再根据不等式符号确定可行域*线性规划问题解的可能结论：该问题具有唯一最优解，X*=(2,6)T，Z*=360③向上平移目标函数等值线x2=-3x1/5+Z/50，确定最优解。2024/5/1727编辑版pptx1x2O1020304010203040(15,10)最优解X*=(15,10)T最优值Z*

=852024/5/1728编辑版ppt246x1x2246最优解X*

=(3,1)T最优值Z*

=5(3,1)minZ=x1+2x22024/5/1729编辑版ppt例：用图解法进行求解线性规划问题？

如果线性规划问题有两个最优解，则它一定有无穷多最优解（多重最优解）。2024/5/1730编辑版ppt例用图解法求线性规划问题？2024/5/1731编辑版ppt该线性规划问题具有无界解。可行域无上界，目标值可以无限增大(缺乏必要约束)2024/5/1732编辑版ppt例2024/5/1733编辑版ppt该线性规划问题无可行解，原因：线性规划问题的可行域是空集(约束条件相互矛盾)2024/5/1734编辑版pptx2x1O10203040102030405050无可行解即无最优解maxZ=10x1+4x22024/5/1735编辑版ppt

图解法的解题思路和几何上的直观表示，对求解线性规划问题的求解具有重要启示：

（1）LP问题的解一般有唯一解、无穷多最优解、无界解和无可行解四种情况。（2）LP问题的可行域一般为无界或有界凸多边形。（3）若LP问题的最优解存在，即有唯一最优解或无穷多最优解，则必在可行域的某个项点上找到最优解。（4）若LP问题有两个最优解，则在它们的连线上的任意一点都是最优解。

作业：教材第37页，1.3：(1)、(2)、(3)；1.42024/5/1736编辑版ppt一、线性规划数学模型的标准型第三节线性规划问题数学模型的标准形式1、标准型表达方式(1)代数式：

(2)向量式：

(3)矩阵式：

A：技术系数矩阵，简称系数矩阵；B：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。2024/5/1737编辑版ppt通常X记为：

，其中，Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，且r(Ａ)＝m。其中:2024/5/1738编辑版ppt2、一般型→标准型的转换方法(1)“决策变量非负”。若某决策变量xk为“取值无约束”(无符号限制)，令：xk=x’k–x”k，(x’k≥0,x”k≥0)。(2)“目标函数求最大值”。如果极小化原问题minZ=CX，则令Z’=–Z，转为求maxZ’=–CX。注意：求解后还原。(3)“约束条件为等式”。对于“≤”型约束，则在“≤”左端加上一个非负松弛变量(slackvariable)，使其为等式。对于“≥”型约束，则在“≥”左端减去一个非负剩余变量(Surplusvariable)，使其为等式。(4)“资源限量非负”。若某个bi<0，则将该约束两端同乘“–1”，以满足非负性的要求。2024/5/1739编辑版ppt【例】将下列线性规划化为标准型？【解】(1)因为x3无符号要求(取值无约束)，x3可以取正值也可取负值，但标准型中要求变量非负，所以可令：对于x1≤0

，可令：2024/5/1740编辑版ppt

(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0，x5也称松驰变量

(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0，化为等式；(4)第三个约束条件右端常数项为负数，因此在不等式两端乘以“－1”。

(5)目标函数是最小值，令Z′=－Z,得到maxZ′=max(－Z)，即当Z达到最小值时Z′达到最大值，反之亦然。(1)x3取值无约束，令x3=x3’－x3’’，x3’,x3’’≥0。同时2024/5/1741编辑版ppt标准型为：2024/5/1742编辑版ppt【练习】将下列线性规划化为标准型？【解】(1)因为x3无符号要求(取值无约束)，即x3取正值也可取负值，但标准型中要求变量非负，所以可令：2024/5/1743编辑版ppt

(3)第二个约束条件是“≥号”，在“≥号”左端减去剩余变量x5，x5≥0，x5也称松驰变量

(2)第一个约束条件是“≤号”，在“≤”左端加入松驰变量x4，x4≥0，化为等式；(4)第三个约束条件是“≤号”且常数项为负数，因此在“≤”左边加入松驰变量x6，x6≥0，同时不等式两端乘以“－1”。

(5)目标函数是最小值，令Z′=－Z,得到maxZ′=max(－Z)，即当Z达到最小值时Z′达到最大值，反之亦然。(1)x3取值无约束，令x3=x3’－x3’’，x3’,x3’’≥0。

作业：教材第38页，1.5：(1)、(2)、(3)2024/5/1744编辑版ppt【练习】将下列线性规划化为标准型？(教材第38页，1.5)【解】先将模型变换成一般形式：标准型：2024/5/1745编辑版ppt第四节线性规划问题解的一般性质

1、线性规划解的概念

基矩阵：一个非奇异的子矩阵（线性无关）。矩阵A中任意一个m列的线性无关子矩阵B

，称为一个基(矩阵)。组成基的列向量称为基向量，用Pj表示(i=1,2,…,m)。基变量：与基向量Pj相对应的变量xj称为基变量。其余的n–m个变量称为非基变量(基矩阵以外的列向量对应变量)。基(本)解：令所有非基变量等于零，得出的唯一解。2024/5/1746编辑版ppt重要概念

可行解：满足约束条件AX=b和X≥0的解。基(本)解：令所有非基变量等于零，得出的唯一解。基(本)可行解：满足X≥0的基解。可行基：基可行解对应的基矩阵。最优解：使目标函数最优的基可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。2024/5/1747编辑版ppt基的概念

假设线性规划问题模型系数矩阵为m行、n列，则系数矩阵中秩为m的m行m列子矩阵，称为基矩阵，简称为基。基中的列向量对应的变量称为基变量，决策变量中基变量以外的变量称为非基变量。2024/5/1748编辑版ppt基本解

对于某一确定的基，令所有非基变量为0，由约束方程组AX=b可解出m个基变量的唯一解，称为一个基本解。2024/5/1749编辑版ppt基本可行解

满足非负条件的基本解，称为基本可行解，基本可行解对应于凸多边形的项点。2024/5/1750编辑版ppt练习：已知线性规划问题4.2

问：中哪一个是基本可行解？2024/5/1751编辑版ppt二、线性规划问题解的性质1、凸集和极点(顶点)的概念由约束条件形成的可行域是凸多边形(凸集)凸集：对于某一集合内部任意两点连线上的点都属于这个集合，我们就称这个集合为凸集(直观理解)。abcd可行域具有有限个顶点。目标函数最优值一定在可行域的边界(顶点)达到，而不可能在其区域的内部。2024/5/1752编辑版ppt凸集的数学定义设K为n维欧氏空间的一个点集，若K中任意两个点X1和X2连线上的所有点都属于K，则称K为凸集。X2X1X设X(x1,x2,…,xn);X1(u1,u2,…,un);X2(v1,v2,…,vn)2024/5/1753编辑版ppt极点：设S为凸集，若S中的点x不能成为S中任何线段的内点，即“不能用S中两个不同的点线性表示”，则称x为S的极点。2024/5/1754编辑版ppt定理1.1

若线性规划问题的可行域非空，则S为凸集(有界或无界)。即连接任意两个可行解的线段上的点仍为可行解。定理1.2

线性规划问题的可行域S中的点X是极点的充要条件是X是基本可行解。即凸多边形的顶点就是基本可行解。定理1.3

若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。如果线性规划问题有最优解，则最优解一定在可行域S的某个极点上得到。

2024/5/1755编辑版ppt第五节单纯形法原理一、线性规划问题的解题思路⑴首先，找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。⑵如果是最优解，就得到这个线性规划问题的最优解；⑶如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解；⑷如果还不是，再接着进行下一个可行基变化，直至找到最优解。2024/5/1756编辑版ppt求解线性规划问题的思路﹣单纯形法确定初始基本可行解判断该可行解是否最优确定新的基本可行解结束是否2024/5/1757编辑版ppt一、用消化法求解线性规划问题（教材第20页例题）解：(一)标准化：(二)求初始基可行解2024/5/1758编辑版ppt令非基变量：x1=x2=0，

得到初始基可行解：

X(0)=(0,0,4,3,8)T此时，目标函数值：

Z(0)=2x1+5x2+0=0

目标函数用非基变量表示。(三)判优对于Z(0)=2x1+5x2，若x1或x2从0变为正数，则目标函数值会增加，因此可判断X(0)一定不是最优解。

(X(0)≠X*)2024/5/1759编辑版pptZ(0)=2x1+5x2(四)方案调整(换基)寻找一个新的基可行解，使目标函数值得到改善。

①选择入基变量

寻找使目标函数增加量最大的非基变量入基，即目标函数中系数最大的变量。(x2↓)

②选择出基变量

为什么要选择原基变量出基？要求决策变量非负，因此有：说明x2最大可以是3，且当x2=3时，x4=0，即x4出基

。(←

x4)

2024/5/1760编辑版ppt(五)求新的基可行解此时，基变量为x3、x2和x5，非基变量为x1和x4。

用非基变量表示基变量：

用x4表示x2，x2=3–x4，

用x4表示x5，x5=2–x1–2x4。

令非基变量x1=x4=0，则X(1)=(0,3,4,0,2)T。2024/5/1761编辑版ppt(六)判优(检验)

将式(4)代入目标函数，目的：用非基变量表示目标函数，得到新的目标函数值：

Z(1)=2x1+5x2=2x1+5(3–x4)

=2x1–5x4+15非基变量x1的系数为2，大于零，可见，如果x1能从非基变量变为基变量，即变为正数，则目标函数值会增加，因此X(1)=(0,3,4,0,2)T不是最优解。2024/5/1762编辑版pptZ(1)=2x1–5x4+15(七)换基当x1=2时，x5=0即：当x1入基，x5

出基。2024/5/1763编辑版ppt(八)求新的基可行解此时，基变量为x3、x2和x1，非基变量为x4和x5。

用非基变量表示基变量：

x1=2+2x4–x5，

x3=2–2x4+x5

。

令非基变量x4=x5=0，则

X(2)=(2,3,2,0,0)T。2024/5/1764编辑版ppt松弛变量x3=2说明第一项资源有剩余，资源相对宽松，这就是松驰变量的经济含义。(九)判优(检验)非基变量x4和x5的系数均为负值，如果x4和x5从非基变量变为基变量，即从零变为正数，则目标函数值会减少，因此X(2)=(2,3,2,0,0)T是最优解，目标函数最优值Z*=19。2024/5/1765编辑版ppt求解过程(换基迭代过程)初始基初始基可行解：X(0)=(0,0,4,3,8)TZ(0)=0新的基可行解：X(1)=(0,3,4,0,2)TZ(1)=15新的可行基最优基最优解：X*=(2,3,2,0,0)TZ*=192024/5/1766编辑版ppt单纯形法原理-矩阵推导(1)2024/5/1767编辑版ppt单纯形法原理-矩阵推导(2)非基变量检验数令非基变量等于0，则2024/5/1768编辑版pptCjCBCNCBXBbXBXN0XBbBNσjCBCNCBXBbXBXNCBXBB-1bIB-1Nσj0CN–CBB-1N单纯形法原理(单纯形表)2024/5/1769编辑版ppt

单纯形法求解线性规划问题的步骤：

(1)求出初始基本可行解(标准化、单位基)；

(2)最优性检验(非基变量检验数非正时停止，否则进入下一步)；

(3)换基(迭代)；①确定入基变量②确定出基变量③初等变换，求出新的基本可行解

(4)重复步骤(2)、(3)，直到求出最优解。2024/5/1770编辑版ppt单纯形法求解步骤举例

maxZ=2x1+5x2

+0x3

+0x4+0x5x1+x3

=4

x2+x4

=3x1+2x2+x5=8

xj≥0,j=1,2,…,5CjθiCBXBb检验数

jx1x2x3x4x525000410100301010812001x3x4x5000025000–3/1=38/2=42024/5/1771编辑版ppt4101003010102100-21x3x2x5050200-504–2CjθiCBXBb检验数

jx1x2x3x4x525000检验数

j2001221x3x2x1052000-1-2最优解:X*=(2,3,2,0,0)T，Z*=19思考:在最终单纯形表中，B-1=？4.82024/5/1772编辑版ppt单纯形法的管理启示x1=4x2=3x1+2x2

=8x1x2430ABC(2,3)DX(0)=(0,0,4,3,8)TX(1)=(0,3,4,0,2)TX(2)=(2,3,2,0,0)T在管理过程中，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求更优。2024/5/1773编辑版ppt解：引入松驰变量x3,x4,x5

，化为标准形式：2024/5/1774编辑版ppt

cj

25000

CB

XB

b

x1

x2

x3

x4x5

000

x3x4x5

438

101000101012001

σj

0

25000由于x1，x2的检验数均为非负，且x2的检验数σ2最大，选x2为入基变量；再按最小比值θl=min(-,3/1,8/2)=3，选x4为出基变量。

cj

25000

CB

XB

b

x1

x2

x3

x4x5

0

0

x3

x5

43

1010001010

σj

x252100-21200-50152024/5/1775编辑版ppt

cj

25000

CB

XB

b

x1

x2

x3

x4x5

050

x3x2x5

432

1010001010100-21

σj

15

200-50由于x1检验数为非负，选x1为入基变量；再按最小比值

θl

=min（4/1,-,2/1）=2，选x5为出基变量。

cj

25000

CB

XB

b

x1

x2

x3

x4x5

05

x3x2

32

01010100-21

σj

x122001

2-1000-1-2192024/5/1776编辑版ppt

初始基本可行解：X(0)=(0,0,4,3,8)T，Z(0)=0

新的基本可行解：X(1)=(0,3,4,0,2)T，Z(1)=15

新的基本可行解：X(2)=(2,3,2,0,0)T，Z(2)=19

判别定理1：在单纯形表中，若所有非基变量的检验数小于零，且B-1b均为非负，则线性规划问题具有唯一最优解。2024/5/1777编辑版ppt图解法与单纯形法求解结果对照：x1x1=4x2=3x1+2x2=8x2(2,3)x2=-(2/5)x1+Z/5

A

(0,0)A：X(0)=(0,0,4,3,8)T，Z(0)=0

B

(0,3)B：X(1)=(0,3,4,0,2)T，Z(1)=15

C

C：X*=(2,3,2,0,0)T，Z*=19

D(4,2)

E(4,0)2024/5/1778编辑版ppt课堂练习

求解下列线性规划问题解：引进松驰变量x3,x4,x5，化为标准形式：2024/5/1779编辑版ppt

cj

24000

CB

XB

b

x1

x2

x3

x4x5

000

x3x4x5

4102

-12100120101-1001

σj

0

24000

cj

24000

CB

XB

b

x1

x2

x3

x4x5

00

x4x5

σj

x242-1/21

1/200620-11041/201/20140-20082024/5/1780编辑版ppt

cj

24000

CB

XB

b

x1

x2

x3

x4x5

400

x2x4x5

264

-1/211/20020-1101/201/201

σj

8

40-200

cj

24000

CB

XB

b

x1

x2

x3

x4x5

4

0

x2

x5

σj

x12310-1/2

1/20011/41/407/2003/4-1/415/200-202002024/5/1781编辑版ppt

cj

24000

CB

XB

b

x1

x2

x3

x4x5

420

x2x1x5

7/235/2

011/41/4010-1/21/20003/4-1/41

σj

20

000-20

cj

24000

CB

XB

b

x1

x2

x3

x4x5

42

x2x1

σj

x3010/3001

-1/34/38/30101/3-1/314/31001/32/300-200202024/5/1782编辑版ppt

初始基本可行解：X(0)=(0,0,4,10,2)T，Z(0)=0

新的基本可行解：X(1)=(0,2,0,6,4)T，Z(1)=8

新的基本可行解：X(2)=(3,7/2,0,0,5/2)T，Z(2)=20

新的基本可行解：X(3)=(14/3,8/3,10/3,0,0)T，Z(3)=20

判别定理2：在单纯形表中，若所有非基变量的检验数小于等于零，且B-1b均为非负，其中某个检验数等于零，则线性规划问题具有无穷多最优解(多重最优解)。2024/5/1783编辑版ppt图解法求解结果：

A

(0,0)A：X(0)=(0,0,4,10,2)T，Z(0)=0

B

(0,2)B：X(1)=(0,2,0,6,4)T，Z(1)=8

C(3,7/2)C：XC*=(3,7/2,0,0,5/2)T，Z*=20D(14/3,8/3)E(2,0)D：XD*=(14/3,8/3,10/3,0,0)T，Z*=202024/5/1784编辑版ppt例

求解下列线性规划问题解：引进松驰变量x3,x4，标准化：2024/5/1785编辑版ppt

cj

-2300

CB

XB

b

x1

x2

x3

x4

00

x3x4

24

4-2102-301

σj

0

-2300不满足出基变量确定法则：虽然，不能确定x3和x4中哪个变量出基，但无论哪个变量出基，都必须满足：x3≥0，x4≥0。x2入基，则：x2>

0(x2≥0)。说明x2可以无限增大，所以目标函数值可以无限增大。2024/5/1786编辑版ppt图解法求解结果：判定定理3：在单纯形表中，若某个检验数σk大于零，且xk对应列向量的元素均为非正，导致出基变量无法确定，则线性规划问题具有无界解。2024/5/1787编辑版ppt练习

求解下列线性规划问题解：引进松驰变量x3,x4，化为标准形式：从标准形中可看出存在可行基B=(P3，P4)=I，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得：2024/5/1788编辑版pptcj

4300CBXBb

x1

x2

x3

x400x3x42426

23103201

0

4300

由于x1，x2的检验数均为非负，且x1的检验数绝对值最大，选取x1为进基变量；再按最小比值θ=min（24/2，26/3）=26/3，选取x4为出基变量，进行换基迭代。cj

4300CBXBb

x1

x2x3

x404x3x120/326/3

05/31-2/312/301/3

104/3

01/30-4/32024/5/1789编辑版pptcj

4300CBXBb

x1

x2

x3

x434x2x146

013/5-2/510-2/53/5

36

00-1/5-6/5表中最后一行的所有检验数均为非正，表明目标函数已达到最大值，上表为最优单纯形表。从表中可得到最优解为：X*=(x1,x2,x3,x4)T=(6,4,0,0)T，最优值为：Z*=36。作业：教材39页，1.8第(1),(4)题在最终单纯形表中，所有非基变量检验数均为负数，说明该线性规划问题具有唯一最优解：X=(6,4,0,0)T，Z*=36。2024/5/1790编辑版pptcj

2-11000CBXBb

x1

x2

x3

x4

x5

x6000x4x5x6601020

3111001-1201011-1001

-21-1000

练习：已知某线性规划用单纯形法求得的某两步迭代表如下，请将表中空白处填上适当的数字。

cj

000011CBXBb

x1

x2

x3

x4

x5

x602-1x4x1x2

1-1-201/21/20-1/21/2

cj

000011CBXBb

x1

x2

x3

x4

x5

x602-1x4x1x210155

0011-1-2

101/201/21/2

01-3/20-1/21/2

25

00-3/20-3/2-1/22024/5/1791编辑版ppt讨论：用单纯形法求解某极大化问题的单纯形表如下，问表中参数a1,a2,a3,d,

1,

2为何取值范围时，下列结论成立。

cj

000011

CB

XB

b

x1

x2

x3

x4

x5

x6

300

x3

x4

x6

d23

4a110a20-1-301-10

a3-500-41

j

1

200-30

(1)表中解为唯一最优解：(2)表中解为无穷多最优解：(3)该问题具有无界解：(4)表中解为退化的基解：(5)表中解为不可行解：(6)x1入基，x6出基：

1≤0,

2≤0,

1×

2=0,d

0

1<

0,

2<

0,d

0

2>0,a1

0,d

0d=0

d<0

1>0,a3

>0,d

>0,d/4>

3/a32024/5/1792编辑版ppt思考题：已知线性规划问题：其中b1,b2是常数，且已知此问题的最终单纯形表如下。试确定表中所有的参数及b1和b2的值？cj

52300CBXBb

x1

x2

x3

x4

x5

50x1x53010

1b2100c-8-11

150

0a-7d

e

e=0,d=–5,

b=5,c=–10,a=–23,b1=30,b2=402024/5/1793编辑版ppt思考题：已知线性规划问题的最优单纯形表如下，求初始单纯形表中参数C,A,b以及最优基B？cj

c1

c2c3c4c5

CB

XB

b

x1

x2

x3

x4

x5

c1c2

x1x2

62

10

41/61/1501-301/5

σj

00-1-2-32024/5/1794编辑版ppt解法(一)：矩阵初等行变换增广矩阵：求A和b：2024/5/1795编辑版ppt求cj：cj

c