第1章运筹学基础与应用-第六版

第1章运筹学基础与应用-第六版第一页，共138页。2023/3/102第一章线性规划及单纯形法

(LinearProgramming&SimplexMethod)§1一般线性规划问题的数学模型§2图解法§3单纯形法原理§4单纯形法的计算步骤§5单纯形法的进一步讨论§6数据包络分析(DEA)§7应用举例第二页，共138页。例2(教材第9页)生产计划问题常山机器加工厂，利用A、B、C三种不同设备加工生产Ⅰ、Ⅱ两种产品。按工艺要求，每生产一个单位的Ⅰ产品，需要占用三种设备2、4、0小时；每生产一个单位的Ⅱ产品，需要占用三种设备2、0、5小时。已知三种设备加工能力分别为12、16、15小时。且每生产一个单位的Ⅰ产品可获取2单位的利润；每生产一个单位的Ⅱ产品可获取2单位的利润。问应当如何安排加工，可使获取的总利润最大？2023/3/103第三页，共138页。2023/3/104§1一般线性规划问题的数学模型

1.1引例例1、生产计划问题

Ⅰ

Ⅱ设备能力（小时）设备A2212设备B4

016设备C0515利润（元）23问：Ⅰ，Ⅱ两种产品各加工多少单位,可获最大利润?第四页，共138页。2023/3/105

2x1+2x2

12

s.t.

4x1

16

5x2

15

x1，x2

0注意模型特点

maxZ=2x1+3x2解:设产品Ⅰ,Ⅱ产量分别为变量x1，x2防灾科技学院第五页，共138页。附例

营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？第六页，共138页。各种食物的营养成分表每天需要300055800第七页，共138页。各种食物的营养成分表每天需要300055800x1x2x3x4第八页，共138页。解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：第九页，共138页。2023/3/1010线性规划模型的特点决策变量：向量X=(x1…xn)T决策人要考虑和控制的因素，非负约束条件：关于X的线性等式或不等式目标函数：Z=ƒ(x1

…xn)为关于X的线性函数，求Z极大或极小第十页，共138页。防灾科技学院11LP问题一般可整理为：决策变量及各类系数之间的对应关系第十一页，共138页。防灾科技学院12上述模型的共同特征：每一个线性规划问题都用一组决策变量表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。第十二页，共138页。2023/3/10131.2线性规划问题的数学模型三个组成要素：1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。第十三页，共138页。线性规划的数学模型由三个要素构成

决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。

怎样辨别一个模型是线性规划模型？

第十四页，共138页。2023/3/1015一般线性规划问题的数学模型：目标函数：约束条件：第十五页，共138页。线性规划模型的简写形式(求和符号)第十六页，共138页。一般线性规划(LP)问题模型向量形式其中：第十七页，共138页。一般线性规划(LP)问题模型矩阵形式其中：第十八页，共138页。2023/3/10191.3线性规划问题的标准形式标准形式：标准形式特点：4.决策变量取值非负。1.目标函数为求极大值；2.约束条件全为等式；3.约束条件右端常数项全为非负；第十九页，共138页。2023/3/1020一般线性规划问题如何化为标准型：1.目标函数求极小值：令：，即化为：第二十页，共138页。2023/3/10212.约束条件为不等式：（1）当约束条件为“≤”时如：可令：，显然（2）当约束条件为“≥”时如：可令：，显然称为松弛变量。称为剩余变量。第二十一页，共138页。2023/3/1022松弛变量和剩余变量统称为松弛变量（3）目标函数中松弛变量的系数由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。第二十二页，共138页。2023/3/10233.取值无约束的变量如果变量xj

代表某产品当年计划数与上一年计划数之差，显然xj

的取值可能是正也可能是负，这时可令：其中：令4.变量xj≤0，显然第二十三页，共138页。2023/3/1024例3(教材15页)

将下述LP模型化为标准型第二十四页，共138页。2023/3/1025解：令得标准形式为：第二十五页，共138页。2023/3/1026第二十六页，共138页。线性规划问题及数学模型线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）第二十七页，共138页。线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）第二十八页，共138页。线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”第二十九页，共138页。线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”第三十页，共138页。线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”,又称多项式时间算法

第三十一页，共138页。线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simplex）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”

线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。第三十二页，共138页。2023/3/1033求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。1.4线性规划问题的解的概念第三十三页，共138页。2023/3/1034可行解：满足所有约束条件的解称为可行解，所有可行解的集合称为可行域。最优解：使目标函数达到最大值的可行解。基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。基可行解：满足变量非负的基解称为基可行解可行基：对应于基可行解的基称为可行基第三十四页，共138页。2023/3/1035例：考察下述线性规划问题：第三十五页，共138页。2023/3/1036（1）可行解，如或满足约束条件，所以是可行解。（2）基系数矩阵A：其中或都构成基。而不构成基。第三十六页，共138页。2023/3/1037（3）基向量、基变量是对应于基的三个基向量，而是对应于这三个基向量的基变量。（4）基解、基可行解、可行基是对应于基的一个基解、基可行解。是对应于基的一个基解、基可行解。均是可行基。练习：P14，例4第三十七页，共138页。2023/3/1038

为了便于建立n维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。求解下述线性规划问题：§2线性规划问题的图解法第三十八页，共138页。2023/3/1039画出线性规划问题的可行域：目标函数等值线第三十九页，共138页。2023/3/10401、可行域：约束条件所围成的区域。2、基可行解：对应可行域的顶点。3、目标函数等值线：4、目标函数最优值:最大截距所对应的。

目标函数等值线有无数条，且平行。（观察规律)第四十页，共138页。2023/3/1041解的几种情况：(2)无穷多最优解(1)唯一最优解若目标函数改为：约束条件不变，则:目标函数等值线此时，线段上所有点都是最优值点。第四十一页，共138页。2023/3/1042解的几种情况：(4)无界解(3)无可行解：当可行域为空集时，无可行解。若目标函数不变，将约束条件1和3去掉，则可行域及解的情况见下图。目标函数等值线此时，目标函数等值线可以向上无穷远处平移，Z值无界。第四十二页，共138页。2023/3/1043几点说明：1、图解法只能用来求解含有两个决策变量的线性规划问题。2、若最优解存在，则必在可行域的某个顶点处取得。3、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。第四十三页，共138页。2023/3/1044§3．单纯形法原理凸集：如果集合C中任意两个点，其连线上的所有点也都是集合C中的点。上图中（1）（2）是凸集，（3）（4）不是凸集顶点：如果对于凸集C中的点X，不存在C中的任意其它两个不同的点，使得X在它们的连线上，这时称X为凸集的顶点。3.1预备知识第四十四页，共138页。2023/3/10453.2线性规划问题基本定理定理1:若线性规划问题存在可行解，则问题的可行域是凸集。证明:设是线性规划的任意两个可行解，则于是对于任意的，设，则所以也是问题的可行解，即可行域是凸集。

第四十五页，共138页。2023/3/1046引理:

线性规划问题的可行解X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。证明:设（1）必要性显然。（2）设A的秩为m。可行解X的前k个分量为正，且它们对应的系数列向量线性无关，则。当时，恰好构成一组基，而就是这组基对应的基可行解。

当时，在基础上从其余列向量中可以找出个线性无关的向量，恰好构成一组基，而X就是这组基对应的基可行解。第四十六页，共138页。2023/3/1047定理2:

线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。证明:问题即是要证明:X是基可行解X是可行域顶点，也即要证明其逆否命题：X不是基可行解X不是可行域顶点。（1）X不是基可行解X不是可行域顶点。假设X是可行解，但不是基可行解，

X的前k个分量为正,其余分量为0，则有又X不是基可行解，所以由引理知，正分量对应的列向量线性相关。即存在一组不全为零的数，使得第四十七页，共138页。2023/3/1048用非零常数乘以上式得：（1）+（3）得：（1）-（3）得：令选择合适的，使得所有的于是均是可行解，并且，所以X不是可行域顶点。第四十八页，共138页。2023/3/1049（2）X不是可行域顶点X不是基可行解。设不是可行域的顶点，因而可以找到可行域内另两个不同的点，使得，用分量表示即为：

易知，当时，必有所以所以于是（1）-（2）得而不全为零，于是知线性相关，X不是基可行解。第四十九页，共138页。2023/3/1050定理3:

若线性规划问题有最优解，一定存在一个基可行解是最优解。引理：

有界

凸集中的任何一点均可表示成顶点的凸组合。证明:假设是可行域顶点，不是可行域顶点，且目标函数在处达到最优，即。由引理知：可表示为的凸组合，即因此假设是所有中最大者，则第五十页，共138页。2023/3/1051而是目标函数的最大值，所以也是最大值，也即，目标函数在可行域的某个顶点达到了最优。从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。第五十一页，共138页。2023/3/10523.3确定初始基可行解寻求最优解的思路：线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，并使得目标函数值不断增大，直到找到最优解为止。设给定线性规划问题：第五十二页，共138页。2023/3/1053因此约束方程组的系数矩阵为：添加松弛变量得其标准形为：第五十三页，共138页。2023/3/1054由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：说明：如果约束条件不全是形式，如含所有形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。称其为初始基可行解。第五十四页，共138页。2023/3/10553.4从初始基可行解转换为另一个基可行解

思路：对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。

设有初始基可行解，并可设前m个分量非零，即，于是第五十五页，共138页。2023/3/1056

由构造初始可行基的方法知前m个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为由于任意系数列向量均可由基向量组线性表示，则非基向量中的用基向量组线性表示为：第五十六页，共138页。2023/3/1057设有，则（1）+（2）得：由此式可知，我们找到了满足约束方程组的另一个解，要使其成为可行解，只要对所有i=1,2,…m，下式成立要使其成为基可行解，上面m个式中至少有一个取零。（基可行解中非零分量的个数不超过m个。）（与比较）第五十七页，共138页。2023/3/1058只要取于是前m个分量中的第l个变为零，其余非负，第j个分量为正，于是非零分量的个数，并可证得线性无关，所以是新的基可行解。第五十八页，共138页。2023/3/10593.4最优性检验和解的判别设有基可行解比较两者对应的目标函数值，哪一个更优？第五十九页，共138页。2023/3/10602）若对所有的，则，

就是最优解。是判断是否达到最优解的标准，称为检验数。1）当时，，目标函数值得到了改进，

不是最优解，需要继续迭代。易知第六十页，共138页。2023/3/1061当所有时，现有顶点对应的基可行解即为最优解。当所有时，又对某个非基变量有则该线性规划问题有无穷多最优解。3.如果存在某个，又向量的所有分量，对任意，恒有，则存在无界解。结论第六十一页，共138页。2023/3/1062§4单纯形法的计算步骤

Max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj0(j=1,…,n)设有线性规划问题：第六十二页，共138页。2023/3/1063(1)找到初始可行基，建立初始单纯形表.(4)重复二、三两步，直至找到最优解。§4单纯形法的计算步骤

(2)进行最优性检验。计算检验数，若所有≤0

则得最优解，结束.否则转下步.若某≥0而≤0，则最优解无界，结束.否则转下步.(3)从一个可行解转换到另一个目标函数值更大的基可行解。由最大增加原则确定进基变量；由最小比值原则选择出基变量；以为主元素进行换基迭代。第六十三页，共138页。2023/3/1064……(1)找到初始可行基，建立初始单纯形表.00…………………是初始基。第六十四页，共138页。2023/3/1065(2)进行最优性检验计算检验数，若所有≤0

则得最优解，结束.否则转下步.若某≥0而≤0，则最优解无界，结束.否则转下步.检验数的计算方法：基变量的检验数一定为0。判断是否达到最优时，只要考虑非基变量检验数。第六十五页，共138页。2023/3/1066(3)从一个可行解转换到另一个目标函数值更大的基可行解。由最小比值原则选择出基变量；进基变量由最大增加原则确定进基变量：

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

，成为新的基变量。

为确保新的基可行解的非零分量非负，按下述规则求得最小比值，其所对应的原基变量中的出基。于是，新的一组基是：第六十六页，共138页。2023/3/1067以为主元素进行换基迭代：即利用初等行变换将进基变量

所在的系数列变为单位列向量，而变为1。这样原来基矩阵中的就不再是单位向量，取而代之的是，这样就找到了一组新的基。(4)重复二、三两步，直至找到最优解。说明：若目标函数是求最小，可以不必将其转变为求最大，但在使用单纯形法求解时，确定进基变量，应找负检验数中最小者，并应以检验数全部为正作为判别最优的条件。第六十七页，共138页。2023/3/1068解将模型标准化附例第六十八页，共138页。1202010Cj比值CBXBb检验数j2023/3/1069x1x2x3x4x5350008101003634001x3x4x5000035000-12/2=636/4=9作出初始单纯形表，进行迭代检验数最大比值最小第六十九页，共138页。12300-21810100检验数j2023/3/107060101/20x3x2x5050-30300-5/208-4Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9第七十页，共138页。2023/3/1071Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1唯一最优解:X*=(4,6,4,0,0)T，Z*=42第七十一页，共138页。2023/3/1072特殊情况：（1）出现两个或两个以上相同的最大，此时可任选一个所对应的变量作为进基变量。

（2）利用规则决定出基变量时，出现两个或两个以上的最小比值，则迭代后，会出现一个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。出现退化现象时，可考虑采用“勃兰特”规则决定进基变量和出基变量的选择。第七十二页，共138页。2023/3/10735.1人工变量

用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。采用人造基的办法：添加人工变量，构造单位矩阵§5单纯形法的进一步讨论

第七十三页，共138页。2023/3/1074

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

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

=”的约束中可直接添加一个人工变量，以便得到初始基矩阵。注意：人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。求解带人工变量的线性规划有两种方法：☆大M法☆两阶段法第七十四页，共138页。2023/3/10755.2大M法△没有单位矩阵，不符合构造初始基的条件，需加入人工变量。△人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为（-M）。（求最小值问题中，人工变量系数取M）△M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。△如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。第七十五页，共138页。2023/3/1076例解线性规划解化为标准型此时无单位矩阵作为初始基。第七十六页，共138页。2023/3/1077添加人工变量，构造初始基：注意：若求最小值问题，则目标函数中人工变量系数取M。第七十七页，共138页。2023/3/1078-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始单纯形表：CCBXBb0x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-3M0第七十八页，共138页。2023/3/1079-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-3/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/4第七十九页，共138页。2023/3/1080此时人工变量全部出基，并已达最优条件。最优解为，最优值为注意：计算机上使用大M法时，需要用机器最大字长的数字代替M，但当某些系数与之较接近时，还是可能会出错。另外一种求解带人工变量的线性规划问题的方法不会出现这种问题-------两阶段法。第八十页，共138页。2023/3/1081例解线性规划解按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：第八十一页，共138页。2023/3/1082作出单纯形表，进行迭代Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24检验数j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M第八十二页，共138页。2023/3/1083检验数j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1检验数j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2最优解:X*=(3,0,1)T，Z*=7第八十三页，共138页。2023/3/10845.3两阶段法

第一阶段：构造目标函数只含人工变量的线性规划问题，求解后判断原线性规划问题是否有基本可行解，若有，则进行第二阶段；第二阶段：将第一阶段的最终单纯形表所对应的解，去掉人工变量，作为第二阶段的初始单纯形表的初始基可行解，进行单纯形法的迭代。第八十四页，共138页。2023/3/1085解（1）化标准型、并添加人工变量得：

（此处未将目标变为MAX）例：

第八十五页，共138页。2023/3/1086（2）构造第一阶段问题：

说明：原问题目标函数无论是求MAX还是求MIN，构造的第一阶段问题目标函数都是求最小MIN。第八十六页，共138页。2023/3/1087求解第一阶段问题：第八十七页，共138页。2023/3/1088此时所得可行解目标函数值为0，故原规划问题有基可行解。转入第二步。第八十八页，共138页。2023/3/1089（3）去掉人工变量，得到第二阶段的单纯形表，在此基础上继续求解。最优解为：第八十九页，共138页。2023/3/10905.4关于解的不同情况的判别1、无穷多最优解例：解：将问题化为标准型：第九十页，共138页。2023/3/1091第九十一页，共138页。2023/3/1092从上表中可知，已达最优解，为，而，若将选为进基变量迭代后，可得另一最优解。上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。判别无穷多最优解的方法：单纯形表的检验数行已达最优性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。第九十二页，共138页。2023/3/1093

2、无可行解

例用单纯形表求解下列线性规划问题解：化为标准型：第九十三页，共138页。2023/3/1094基变量CB2030000-Mbx1x2s1s2s3

a1s1s2a100-M31010001001001100-11150304015—40cj-zj20+M30+M00-M0-40M单纯形表求解线性规划问题第九十四页，共138页。2023/3/10951x2s2a1300-M3/1011/100001001007/100-1/100-111530255030250/7cj-zj11+7/10M0-3-M/100-M02x2x1a13020-M011/10-3/100010010000-1/10-7/10-116304cj-zj00-3-M/10-11-7M/10-M0迭代次数基变量CBx1x2s1s2s3a1b比值2030000-M单纯形法的最终表里有人工变量大于零，则此线性规划无可行解。第九十五页，共138页。2023/3/1096

3、无界解例用单纯形表求解下面线性规划问题。解第九十六页，共138页。2023/3/1097

迭代次数基变量CBx1x2s1s2b比值11000s1s2001-110-3201161—cj-zj110001x1s2101-1100-13119cj-zj02-101此时的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以取得无限大。第九十七页，共138页。2023/3/1098

事实上，此从1次迭代的单纯形表中，得到约束方程：

移项可得：由此可知，目标函数可以任意大，即无界。第九十八页，共138页。2023/3/1099练习：用大M法求解下列线性规划问题1、2、第九十九页，共138页。2023/3/10100解1：将模型化为标准型得：建立单纯形表并计算如下第一百页，共138页。2023/3/10101显然，检验数已全部非正，已达最优解，但非基变量X2的检验数为0，故知此问题有无穷多最优解。第一百零一页，共138页。2023/3/10102解2：将模型化为标准型得：建立单纯形表并计算如下第一百零二页，共138页。2023/3/10103第一百零三页，共138页。2023/3/10104最优解为（4，4）第一百零四页，共138页。第一章线性规划及单纯形法LinearProgramming（LP）

线性规划问题及其数学模型

线性规划的图解法

线性规划的单纯形法

线性规划问题的应用

线性规划问题的求解方法第一百零五页，共138页。单纯形法的求解思路是否循环第一百零六页，共138页。⑥以alk为主元素进行迭代，利用初等行变换将xk所在列化为单位向量，即alk化为1，其它元素化为0，得到改进的可行基，转入第③步。计算步骤总结（有可行解时）①将线性规划问题化成标准形式;②找出一个m阶单位矩阵作初始可行基，得到初始基可行解;③计算各非基变量xj的检验数j，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步;④若存在某个s>0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步;⑤根据max{j|j＞0}=k原则，确定xk为入基变量，再按=min{bi/aik|aik＞0}=bl/alk规则，确定xl为出基变量，得到改进的基可行解。第一百零七页，共138页。单纯形表迭代次数基变量CBx1x2x3x4x5b比值ithZj目标系数区约束条件系数区右端系数检验系数区基变量区第一百零八页，共138页。基变量的系数目标函数中变量的系数决策变量约束方程组的系数矩阵出基变量判断参数方程右端常数项各变量的检验数基变量CB基bcj→cj－zj单纯形表第一百零九页，共138页。由单纯形表判别解的类别无可行解唯一最优解所有无穷多最优解无界解（无最优解）存在某个，且所对应的系数最优解所有非基变量的检验数*第一百一十页，共138页。由单纯形表判别解的类别无可行解唯一最优解所有无穷多最优解无界解（无最优解）存在某个，且所对应的系数最优解某非基变量至少一个且所有非基变量的检验数*第一百一十一页，共138页。≥0保证当前的基可行解是最优解

至少有一个等于0，如

至少有一个大于0，如

＞0

存在，保证当xp入基时有xl出基两个最优解连线上的所有点都是最优解≤0说明能得到另一个最优基可行解第一百一十二页，共138页。无穷多最优解示例：s.t.标准化s.t.第一百一十三页，共138页。第一百一十四页，共138页。此时所有检验数得到最优解最优值为第一百一十五页，共138页。此时所有检验数得另一最优解

最优值为第一百一十六页，共138页。A第一百一十七页，共138页。1课后题：P481.80024-235235-3/2第一百一十八页，共138页。练习题：求a～g的值，并判断表中解是否最优解单纯形法计算时某一步的表格

，约束形式为，已知目标函数为松弛变量，表中解代入目标函数后得第一百一十九页，共138页。2023/3/10120小结表格单纯形表的使用（1）化线性规划模型为标准型，建立初始单纯形表。（2）根据单纯形表按照最大增加原则选择进基变量；（3）按照最小比值原则选择换出变量；（4）实施矩阵的初等变换进行换基迭代；（5）建立新的单纯形表；（6）重复上述过程直到求得最优表格为止。第一百二十页，共138页。防灾科技学院121一般地讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型。

(1)要求解问题的目标函数能用数值指标来表示，且为线性函数；

(2)存在着多种方案及有关数据；

(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。§7线性规划应用举例

第一百二十一页，共138页。防灾科技学院122例合理利用线材问题。现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。【分析】最简单做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头。若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用。见表2-12。表§7线性规划应用举例

第一百二十二页，共138页。所有可能的裁截方案①②