运筹(第一章线性规划)

2023/2/41运筹学

OPERATIONSRESEARCH

2023/2/42第一章线性规划及单纯形法

(LinearProgramming,LP)线性规划模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论数据包络分析2023/2/43§1一般线性规划问题的数学模型

1.1引例

例1生产计划问题

Ⅰ

Ⅱ能力设备A2212设备B4

016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?2023/2/44注意模型特点解:设产品Ⅰ,Ⅱ产量分别为变量。2023/2/45线性规划模型特点决策变量：向量决策人要考虑和控制的因素，非负。约束条件：关于的线性等式或不等式。目标函数：为关于

的线性函数，求Z极大或极小2023/2/461.2线性规划问题的数学模型线性规划模型的三个组成要素：1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。2023/2/47一般线性规划问题的数学模型：目标函数：约束条件：2023/2/48简写形式：2023/2/49矩阵形式表示为：其中：2023/2/4101.3线性规划问题的标准形式标准形式：2023/2/411标准形式特点：4.决策变量取值非负。1.目标函数为求极大值；2.约束条件全为等式；3.约束条件右端常数项全为非负；2023/2/412一般线性规划问题如何化为标准型：1.目标函数求极小值：令：，即化为：2023/2/4132.约束条件为不等式：（1）当约束条件为“≤”时如：可令：，显然（2）当约束条件为“≥”时如：可令：，显然称为松弛变量。

称为剩余变量。2023/2/414松弛变量和剩余变量统称为松弛变量。（3）目标函数中松弛变量的系数由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。2023/2/4153.取值无约束的变量其中：令4.变量xj≤0，显然如果变量

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

的取值可能是正也可能是负，这时可令：2023/2/416例.将下述线性规划模型化为标准型2023/2/417解：令得标准形式为：2023/2/418求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。1.4线性规划问题的解的概念2023/2/419

可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。最优解：使目标函数达到最大值的可行解。

基：约束方程组的系数矩阵中的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。

说明：基通常不唯一。2023/2/420

基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。基可行解：满足变量非负的基解称为基可行解。可行基：对应于基可行解的基称为可行基。2023/2/421例：考察下述线性规划问题：2023/2/422（1）可行解，如或满足约束条件，所以是可行解。（2）基系数矩阵其中

或

都构成基。而不构成基。2023/2/423（3）基向量、基变量是对应于基的三个基向量，而是对应于这三个基向量的基变量。（4）基解、基可行解、可行基是对应于基的基解、基可行解。是对应于基的基解、基可行解。均是可行基。练习：P14，例42023/2/424

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

目标函数等值线有无数条，且平行。（观察规律)2023/2/427解的几种情况：(2)无穷多最优解：若目标函数改为(1)唯一最优解约束条件不变，则:目标函数等值线此时，线段上所有点都是最优值点。2023/2/428(4)无界解(3)无可行解：当可行域为空集时，无可行解。若目标函数不变，将约束条件1和3去掉，则可行域及解的情况见下图。目标函数等值线此时，目标函数等值线可以向上无穷远处平移，Z值无界。2023/2/429几点说明：1、图解法只能用来求解含有两个决策变量的线性规划问题。2、若最优解存在，则必在可行域的某个顶点处取得。3、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。2023/2/430§3．单纯形法原理上图中（1）（2）是凸集，（3）（4）不是凸集3.1预备知识

凸集：如果集合

中任意两个点，其连线上的所有点也都是集合

中的点。顶点：如果对于凸集中的点

，不存在

中的任意其它两个不同的点，使得在它们的连线上，这时称为凸集的顶点。2023/2/4313.2线性规划问题基本定理定理1:若线性规划问题存在可行解，则问题的可行域是凸集。证明:设是线性规划的任意两个可行解，则于是对于任意的，，则

所以也是问题的可行解，即可行域是凸集。

2023/2/432引理:

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

2023/2/433

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

线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。证明:问题即是要证明:X是基可行解X是可行域顶点，也即要证明其逆否命题：X不是基可行解X不是可行域顶点。（1）X不是基可行解X不是可行域顶点。假设X是可行解，但不是基可行解，X的前k个分量为正,其余分量为0，则有又X不是基可行解，所以由引理知，正分量对应列向量线性相关。即存在一组不全为零的数，使得用非零常数乘以上式得：2023/2/4352023/2/436（1）+（3）得：（1）-（3）得：令选择合适的，使得所有的于是均是可行解，并且，所以X不是可行域顶点。2023/2/437（2）X不是可行域顶点X不是基可行解。设不是可行域的顶点，因而可以找到可行域内另两个不同的点，使得用分量表示即为：

易知，当，时，必有2023/2/438所以所以于是（1）-（2）得而不全为零，于是知线性相关，X不是基可行解。证毕。2023/2/439定理3:

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

有界

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

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

设有初始基可行解，并可设前m个分量非零，即于是2023/2/446

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

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

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

设有线性规划问题：2023/2/454(1)找到初始可行基，建立初始单纯形表.(4)重复二、三两步，直至找到最优解。单纯形法的计算步骤

(2)进行最优性检验。计算检验数，若所有≤0则得最优解，结束.否则转下步.若某≥0而≤0，则最优解无界，结束.否则转下步.(3)从一个可行解转换到另一个目标函数值更大的基可行解。由最大增加原则确定进基变量；由最小比值原则选择出基变量；以为主元素进行换基迭代。2023/2/455……(1)找到初始可行基，建立初始单纯形表.00…………………是初始基。2023/2/456(2)进行最优性检验计算检验数，若所有≤0则得最优解，结束.否则转下步.若某≥0而≤0，则最优解无界，结束.否则转下步.检验数的计算方法：基变量的检验数一定为0。判断是否达到最优时，只要考虑非基变量检验数。2023/2/457(3)从一个可行解转换到另一个目标函数值更大的基可行解。进基变量由最大增加原则确定进基变量：当某些非基变量的检验数时，为使目标函数值增加地更快，一般选择正检验数中最大者对应的非基变量进基

，成为新的基变量。

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

所在的系数列变为单位列向量，而变为1。这样原来基矩阵中的就不再是单位向量，取而代之的是，这样就找到了一组新的基。(4)重复二、三两步，直至找到最优解。2023/2/459说明：若目标函数是求最小，可以不必将其转变为求最大，但在使用单纯形法求解时，确定进基变量，应找负检验数中最小者，并应以检验数全部为正作为判别最优的条件。2023/2/460解将模型标准化例1求解下面的线性规划问题检验数最大比值最小列单纯形表，进行迭代计算612023/2/4检验数最大比值最小622023/2/4所有检验数均已非正，已得到最优解，最优解即为632023/2/42023/2/464解将模型标准化例2求解下面的线性规划问题检验数最大比值最小列单纯形表，进行迭代计算652023/2/4检验数最大比值最小列单纯形表，进行迭代计算662023/2/4列单纯形表，进行迭代计算672023/2/4所有检验数均已非正，已得到最优解，最优解即为2023/2/468特殊情况：（1）出现两个或两个以上相同的最大，此时可任选一个所对应的变量作为进基变量。

（2）利用规则决定出基变量时，出现两个或两个以上的最小比值，则迭代后，会出现一个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。出现退化现象时，可考虑采用“勃兰特”规则决定进基变量和出基变量的选择。2023/2/4695.1人工变量用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。采用人造基的办法：添加人工变量，构造单位矩阵.§5单纯形法的进一步讨论2023/2/470

人工单位矩阵的构造方法（1）在“”的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是-1，所以再加入一个人工变量，其系数是+1，因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。（2）在原本就是“=”的约束中可直接添加一个人工变量，以便得到初始基矩阵。注意：人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。2023/2/4715.2大M法

没有单位矩阵，不符合构造初始基的条件，需加入人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为（-M）。求最小值问题中，人工变量系数取MM为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。2023/2/472例3解线性规划解化为标准型此时无单位矩阵作为初始基。2023/2/473添加人工变量，构造初始基：（求最小值问题中，人工变量系数需取M）2023/2/474初始单纯形表：2023/2/4752023/2/476此时人工变量全部出基，并已达最优条件。最优解为，最优值为注意：计算机上使用大M法时，需要用机器最大字长的数字代替M，但当某些系数与之较接近时，还是可能会出错。另外一种求解带人工变量的线性规划问题的方法不会出现这种问题-------两阶段法。2023/2/477例解线性规划解按大M法构造人造基，引入人工变量的辅助问题如下：列单纯形表，进行迭代计算782023/2/4列单纯形表，进行迭代计算792023/2/4所有检验数均已非正，且人工变量都已出基，已得到最优解，最优解即为2023/2/4805.3两阶段法

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

解（1）化标准型、并添加人工变量得：

例：目标函数：

约束条件：

2023/2/482（2）构造第一阶段问题：

说明：原问题目标函数无论是求MAX还是求MIN，构造的第一阶段问题目标函数都是求最小MIN。2023/2/483求解第一阶段问题：2023/2/484此时所得可行解目标函数值为0，故原规划问题有基可行解。转入第二步。2023/2/485（3）去掉人工变量，得到第二阶段的单纯形表，在此基础上继续求解。最优解为：2023/2/4865.4关于解的不同情况的判别

1、无穷多最优解例：解：将问题化为标准型：2023/2/4872023/2/488从上表中可知，已达最优解，为，而，若将选为进基变量迭代后，可得另一最优解。上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。判别无穷多最优解的方法：单纯形表的检验数行已达最有性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。2023/2/489

2、无可行解例

用单纯形表求解下列线性规划问题解化为标准型：2023/2/490单纯形表求解线性规划问题2023/2/491所有检验数均为非正，但单纯形法的最终表里有人工变量大于零，则此线性规划无可行解。2023/2/492

3、无界解例

用单纯形表求解下面线性规划问题。解2023/2/493单纯形表求解线性规划问题此时的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以取得无限大。2023/2/494练习：用大M法求解下列线性规划问题1、2023/2/495解1：将模型化为标准型得：建立单纯形表并计算如下2023/2/496显然，检验数已全部非正，已达最优解，但非基变量X2的检验数为0，故知此问题有无穷多最优解。2023/2/497练习：用大M法求解下列线性规划问题2、2023/2/498解2：将模型化为标准型得：建立单纯形表并计算如下2023/2/4992023/2/4100最优解为（4，4）2023/2/4101小结表格单纯形表的使用（1）化线性规划模型为标准型，建立初始单纯形表。（2）根据单纯形表按照最大增加原则选择进基变量；（3）按照最小比值原则选择换出变量；（4）实施矩阵的初等变换进行换基迭代；（5）建立新的单纯形表；（6）重复上述过程直到求得最优表格为止。2023/2/4102例连续投资问题。现有资金10万元，在其后3年预对四个项目进行投资。A：从第1年到第3年每年初可投资，年末回收本利111%；B：第2年初投资，到第3年末回收本利125%，最大投资3万元；C：第3年初投资，到年末回收本利120%，最大投资4万元；D：每年初投资，次年末回收本利的115%。求：第3年末总资本最大的投资方案。§6线性规划应用举例

2023/2/4103解：假设

表示第i年初投资于第j个项目的资金，i=1,2,3;j=A,B,C,D。则2023/2/4104例.混合配料问题

某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大，试建立该问题的线性规划数学模型。2023/2/41052023/2/4106解：用i=1,2,3分别代表原料A、B、C，用j=1,2,3分别代表甲、乙、丙三种糖果。设xij

为生产第j

种糖果使用的第i

种原料的质量，则问题的数学模型可归结为：目标函数2023/2/4107约束条件为2023/2/4108例.投资项目的组合问题

兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资：三年内的每年年初均可投入，每年获利为投资额的20%，其本利可一起用于下一年的投资；2.只允许第一年初投入，于第二年年末收回，本利合计为投资额的150%，但此类投资限额15万以内；3.允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元以内；4.允许于第三年初投入，年末收回，可获利40%，但限额为10万元以内；试为该公司确定一个使第三年末本利总和为最大的投资组合方案。2023/2/4109解：用xij表示第i年初投放到j

项目的资金数，则可投资的变量表如下2023/2/4110由于第三年末收回的本利只包含第三年初项目一的投资、第二年初项目三的投资和第三年初项目四的投资，因此目标函数为：第一年初投资总额为30万，因此有：第二年初的投资额与第一年末收回的本利总额相同：第三年初投资额与第二年末收回的本利总额相同：2023/2/4111再考虑各项目的投资限额，得到该问题的线性规划模型如下：2023/2/4112例.生产、库存与设备维修综合计划红光厂有2台车床、1台钻床、1台磨床，承担4种产品的生产任务。已知各种产品所需设备工时及单位产品的售价如表1所示。对产品今后3个月的市场最大需求（小于最大需求时可全部售出）及各产品今后3个月的成本分别如表2、