运筹学基础及应用

1、1,运筹学,2,第一章 线性规划及单纯形法 (Linear Programming, LP),线性规划模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论 数据包络分析,3,1 一般线性规划问题的数学模型1.1 引例,，各生产多少, 可获最大利润?,2020/10/20,4,2x1+2x2 12 4x1 16 5x2 15 x1，x2 0 注意模型特点,max Z= 2x1 +3x2,解:设产品, 产量分别为变量x1 ， x2,2020/10/20,5,线性规划模型特点,决策变量：向量X=(x1 xn)T 决策人要考虑和控制的因素，非负 约束条件：关于X的线性等式或不等式 目标函

2、数：Z=(x1 xn) 为关于X 的线性函数，求Z极大或极小,2020/10/20,6,1.2 线性规划问题的数学模型,三个组成要素：,1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。,2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。,3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,2020/10/20,7,一般线性规划问题的数学模型：,目标函数：,约束条件：,2020/10/20,8,简写形式：,2020/10/20,9,矩阵形式表示为：,其中：,2020/10/20,10,1.3 线性规划问题的标准形式,标

3、准形式：,标准形式特点：,4. 决策变量取值非负。,1. 目标函数为求极大值；,2. 约束条件全为等式；,3. 约束条件右端常数项全为非负；,2020/10/20,11,一般线性规划问题如何化为标准型：,1. 目标函数求极小值：,令： ，即化为：,2020/10/20,12,2. 约束条件为不等式：,（2）当约束条件为“”时,如：,可令： ， 显然,称为松弛变量。,称为剩余变量。,2020/10/20,13,松弛变量和剩余变量统称为松弛变量,（3）目标函数中松弛变量的系数,由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。,202

4、0/10/20,14,3. 取值无约束的变量,如果变量 x 代表某产品当年计划数与上一年计划数之差，显然 x 的取值可能是正也可能是负，这时可令：,其中：,2020/10/20,15,例. 将下述线性规划模型化为标准型,2020/10/20,16,解：令,得标准形式为：,2020/10/20,17,求解线性规划问题： 就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。,1.4 线性规划问题的解的概念,2020/10/20,18,可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。,2020/10/20,19,例：考察下述线性规划问题：,2020/10/20

5、,20,（2） 基,系数矩阵A：,其中,或,2020/10/20,21,（3）基向量、基变量,（4）基解、基可行解、可行基,是对应于基,的一个基解、基可行解。,是对应于基,的一个基解、基可行解。,均是可行基 。,练习：P14， 例4,2020/10/20,22,为了便于建立 n 维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。,求解下述线性规划问题：,2 线性规划问题的图解法,2020/10/20,23,画出线性规划问题的可行域：,2020/10/20,24,1、可行域：约束条件所围成的区域。,2、基可行解：对应可行域的顶点。,3、目标函数等值线：,4、

6、目标函数最优值: 最大截距所对应的 。,目标函数等值线有无数条，且平行。（观察规律),2020/10/20,25,解的几种情况：,(2) 无穷多最优解,(1) 唯一最优解,若目标函数改为：,约束条件不变，则:,2020/10/20,26,解的几种情况：,(4) 无界解,(3) 无可行解：当可行域为空集时，无可行解。,若目标函数不变，将约束条件1和3去掉，则可行域及解的情况见下图。,目标函数等值线,此时，目标函数等值线可以向上无穷远处平移，Z值无界。,2020/10/20,27,几点说明： 1、图解法只能用来求解含有两个决策变量的线性规划问 题。 2、若最优解存在，则必在可行域的某个顶点处取得。

7、 3、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。,2020/10/20,28,3单纯形法原理,凸集：如果集合 C 中任意两个点 ，其连线上的所有点也都是集合C 中的点。,上图中（1）（2）是凸集，（3）（4）不是凸集,顶点：如果对于凸集 C 中的点 X ，不存在C 中的任意其它两个不同的点 ，使得 X 在它们的连线上，这时称 X 为凸集的顶点。,3.1 预备知识,2020/10/20,29,3.2 线性规划问题基本定理,定理1:若线性规划问题存在可行解，则问题的可行域是凸集。,证明:设 是线性规划的任意两个可行解，则,于是对于任意的 ，设 ，则,所以 也是问题的可行解

8、，即可行域是凸集。,2020/10/20,30,引理: 线性规划问题的可行解 X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。,证明:设 （1） 必要性显然。 （2） 设 A 的秩为m。可行解 X 的前 k 个分量为正，且它们对应的系数列向量 线性无关，则 。 当 时， 恰好构成一组基，而 就是这组基对应的基可行解。,当 时，在 基础上从其余列向量中可以找出 个线性无关的向量，恰好构成一组基，而 X 就是这组基对应的基可行解。,2020/10/20,31,定理2: 线性规划问题的基可行解 X 对应线性规划问题可行 域（凸集）的顶点。,证明:问题即是要证明: X是基可行解 X是可行

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

10、 使得 ， 用分量表示即为：,易知，当 时，必有 所以,所以,于是（1）-（2）得,而 不全为零，于是知 线性相关，X不是基可行解。,2020/10/20,34,定理3: 若线性规划问题有最优解，一定存在一个基可行解是 最优解。,引理： 有界 凸集中的任何一点均可表示成顶点的凸组合。,证明:假设 是可行域顶点， 不是可行域顶点 ，且目标函数在 处达到最优，即 。,由引理知： 可表示为 的凸组合，即,因此,假设 是所有 中最大者，则,2020/10/20,35,而 是目标函数的最大值，所以 也是最大值， 也即，目标函数在可行域的某个顶点达到了最优。,从上述三个定理可以看出，要求线性规划问题的最优

11、解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。,单纯形方法的基本思路 自从1947年丹齐格（G.B Dantzig）提出单纯形方法以来，迄今为止仍是求解线性规划问题的最有效的方法。在介绍这种方法之前，先通过一个例子介绍单纯形方法的基本思想。,例 用消元法解线性规划问题.,(1.3.1),解 求解线性规划问题（1.2.4），实际上是求线性方程组,(1.3.2),安徽省十一五规划教材,(1.3.3),安徽省十一五规划教材,(1.3.4),安徽省十一五规划教材,2020/10/20,43,3.3 确定初始基可行解,寻求最优解的思路：线性规划问题的最优解一定会在

12、基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，并使得目标函数值不断增大，直到找到最优解为止。,设给定线性规划问题：,2020/10/20,44,因此约束方程组的系数矩阵为：,添加松弛变量得其标准形为：,2020/10/20,45,由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：,说明：如果约束条件不全是 形式，如含所有 形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。,称其为初始基可行解。,2020/10/20,46,3.4 从初始基可行解转换为另一个基 可行解,思路：对初始基可行解的系数矩阵进行初等行变

13、换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。,设有初始基可行解 ，并可设前m 个 分量非零，即 ，于是,2020/10/20,47,由构造初始可行基的方法知前m 个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为,由于任意系数列向量均可由基向量组线性表示，则非基向量中的 用基向量组线性表示为：,2020/10/20,48,设有 ，则,（1）+（2）得：,由此式可知，我们找到了满足约束方程组的另一个解 ，,要使其成为可行解，只要对所有i=1,2,m ，下式成立,要使其成为基可行解，上面m个式中至少有一个取零。 （基可行解中非零分量的个数不

14、超过m 个。）,（与 比较）,2020/10/20,49,只要取,于是前m个分量中的第l个变为零，其余非负，第j个分量为正，于是非零分量的个数 ，并可证得 线性无关，所以 是新的基可行解。,2020/10/20,50,3.4 最优性检验和解的判别,设有基可行解,比较两者对应的目标函数值，哪一个更优？,2020/10/20,51,2）若对所有的 ，则 ， 就是最优解。,1）当 时， ，目标函数值得到 了改进， 不是最优解，需要继续迭代。,易知,2020/10/20,52,当所有 时，现有顶点对应的基可行解即为最优解。 当所有 时，又对某个非基变量 有 则该线性规划问题有无穷多最优解。 3. 如果

15、存在某个 ，又 向量的所有分量 ，对任意 ，恒有 ，则存在无界解。,结论,2020/10/20,53,4 单纯形法的计算步骤,设有线性规划问题：,2020/10/20,54,(1)找到初始可行基，建立初始单纯形表.,(4) 重复二、三两步，直至找到最优解。,4 单纯形法的计算步骤,(2)进行最优性检验。 计算检验数，若所有 0 则得最优解，结束.否则转下步. 若某 0 而 0 ，则最优解无界，结束.否则转下步.,(3)从一个可行解转换到另一个目标函数值更大的基可行解。 由最大增加原则确定进基变量；由最小比值原则选择出基变量；以 为主元素进行换基迭代。,2020/10/20,55,(1)找到初始

16、可行基，建立初始单纯形表.,是初始基。,2020/10/20,56,(2)进行最优性检验 计算检验数，若所有 0 则得最优解，结束.否则转下步. 若某 0 而 0 ，则最优解无界，结束.否则转下步.,检验数的计算方法：,基变量的检验数一定为0。判断是否达到最优时，只要考虑非基变量检验数。,2020/10/20,57,(3)从一个可行解转换到另一个目标函数值更大的基可行解。,由最小比值原则选择出基变量；,进基变量,由最大增加原则确定进基变量： 当某些非基变量的检验数 时，为使目标函数值增加地更快，一般选择正检验数中最大者对应的非基变量进基 ，成为新的基变量。,为确保新的基可行解的非零分量非负，按

17、下述规则求得最小 比值 ，其所对应的原基变量中的 出基。,于是，新的一组基是：,2020/10/20,58,以 为主元素进行换基迭代： 即利用初等行变换将进基变量 所在的系数列变为单位列向量，而 变为1。这样原来基矩阵中的 就不再是单位向量，取而代之的是 ，这样就找到了一组新的基。,(4) 重复二、三两步，直至找到最优解。,说明：若目标函数是求最小，可以不必将其转变为求 最大，但在使用单纯形法求解时，确定进基变 量，应找负检验数中最小者，并应以检验数 全部为正作为判别最优的条件。,2020/10/20,59,maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 + x3 =8

18、2x2 + x4 =12 3x1 +4 x2 + x5 =36 x1 ，x2 ，x3 ，x4 ，x5 0,解 将模型标准化,例 maxZ=3x1 +5x2 x1 8 2x2 12 3x1+4x2 36 x1 ，x2 0,2020/10/20,60,作出单纯形表，进行迭代,检验数最大,比值最小,2020/10/20,61,2020/10/20,62,最优解 :X*=(4,6,4,0,0)T，Z*=42,2020/10/20,63,特殊情况： （1）出现两个或两个以上相同的最大 ，此时可任选一个 所对应的变量作为进基变量。 （2）利用 规则决定出基变量时，出现两个或两个以上的最小比值 ，则迭代后，

19、会出现一个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。 出现退化现象时，可考虑采用“勃兰特”规则决定进基变量和出基变量的选择。,单纯形法计算中用 规划确定换出变量时，有时存在两个 以上相同的最小比值，这样在下一次迭代中就有一个或 几个基变量等于零，这就出现了退化解，当出现退化时， 进行多次迭代，而基又返回到最初的情形 ，即出现计算 过程的循环，使永远达不到最优解。为解决这个问题我 们介绍勃兰特规则： （1）当存在两个或两个以上最大检验数时，选取 中下 标最小的非基变量 为换入变量； （2）当按 规则计算时，存在两个或两个以上最小比值 时，选

20、取下标最小的基变量为换出变量。,2020/10/20,65,5.1 人工变量,用单纯形法解题时，需要有一个单位阵作为初始基。 当约束条件都是“”时，加入松弛变量就形成了初始基。 但实际存在“”或“”型的约束，没有现成的单位矩阵。 采用人造基的办法：添加人工变量，构造单位矩阵,5 单纯形法的进一步讨论,2020/10/20,66,人工单位矩阵的构造方法 在“ ”的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（-1），所以再加入一个人工变量，其系数是（+1），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。 在原本就是“ = ”的约束中可直接添加一

21、个人工变量，以便得到初始基矩阵。 注意：人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。,求解带人工变量的线性规划有两种方法： 大M法 两阶段法,2020/10/20,67,5.2 大M法,没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。 人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为（-M）。 （求最小值问题中，人工变量系数取M） M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。 如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，

22、当然亦无最优解。,2020/10/20,68,例解线性规划,解化为标准型,此时无单位矩阵作为初始基。,2020/10/20,69,添加人工变量，构造初始基：,（求最小值问题中，人工变量系数取M）,2020/10/20,70,初始单纯形表：,2020/10/20,71,2020/10/20,72,此时人工变量全部出基，并已达最优条件。 最优解为,，最优值为,注意：计算机上使用大M法时，需要用机器最大字长的数字 代替M，但当某些系数与之较接近时，还是可能会出错。 另外一种求解带人工变量的线性规划问题的方法不会出现这种 问题-两阶段法。,2020/10/20,73,例解线性规划,maxZ= 3x1

23、- x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0,解按大M法构造人造基，引入人工变量x4 , x5 的辅助问题如下：,2020/10/20,74,作出单纯形表，进行迭代,2020/10/20,75,最优解 :X*=(3,0,1)T，Z*=7,2020/10/20,76,5.3 两阶段法,第一阶段：构造目标函数只含人工变量的线 性规划问题，求解后判断原线性 规划问题是否有基本可行解，若 有，则进行第二阶段 ； 第二阶段：将第一阶段的最终单纯形表所对 应的解

24、，去掉人工变量，作为第 二阶段的初始单纯形表的初始基 可行解，进行单纯形法的迭代。,2020/10/20,77,解（1）化标准型、并添加人工变量得： Min f = 2x1 + 3 x2 （此处未将目标变为MAX） s.t. x1 + x2 x3 +x6 = 350 x1 - x4 +x7 =125 2 x1 + x2 +x5 =600 x1 , x2 , x3, x4, x5 ,x6,x7 0,例：目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0,2020/10/20,78,（2）构造

25、第一阶段问题： Min z = x6 +x7 (Max z = -x6 -x7) s.t. x1 + x2 x3 +x6 = 350 x1 - x4 +x7 =125 2 x1 + x2 +x5 =600 x1 , x2 , x3, x4, x5 ,x6,x7 0,说明：原问题目标函数无论是求MAX还是求MIN，构造的 第一阶段问题目标函数都是求最小MIN。,2020/10/20,79,求解第一阶段问题：,2020/10/20,80,此时所得可行解目标函数值为0，故原规划问题有基可行 解。转入第二步。,2020/10/20,81,（3）去掉人工变量，得到第二阶段的单纯形表，在此 基础上继续求解

26、。,最优解为：,2020/10/20,82,5.4 关于解的不同情况的判别,1、无穷多最优解 例：,解：将问题化为标准型：,2020/10/20,83,2020/10/20,84,从上表中可知，已达最优解，为 ， 而 ，若将 选为进基变量迭代后，可得另一最优 解 。,上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。,判别无穷多最优解的方法：单纯形表的检验数行已达最有性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。,2020/10/20,85,2、无可行解 例 用单纯形表求解下列线性规划问题,解：化为标准型：,2020/10/20,86,

27、单纯形表求解线性规划问题,2020/10/20,87,单纯形法的最终表里有人工变量大于零，则此线性规划无可行解。,2020/10/20,88,3、无界解,例 用单纯形表求解下面线性规划问题。,解,2020/10/20,89,此时 的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以取得无限大。,2020/10/20,90,事实上，此从1次迭代的单纯形表中，得到约束方程：,移项可得：,由此可知，目标 函数可以任意大， 即无界。,2020/10/20,91,练习：用大M法求解下列线性规划问题,1、,2、,2020/10/20,92,解1：将模型化为标准型得：,建立单

28、纯形表并计算如下,2020/10/20,93,显然，检验数已全部非正，已达最优解，但非基变量X2的 检验数为0，故知此问题有无穷多最优解。,2020/10/20,94,解2：将模型化为标准型得：,建立单纯形表并计算如下,2020/10/20,95,2020/10/20,96,最优解为（4，4）,2020/10/20,97,小结 表格单纯形表的使用,（1）化线性规划模型为标准型，建立初始单纯形表。 （2）根据单纯形表按照最大增加原则选择进基变量； （3）按照最小比值原则选择换出变量； （4）实施矩阵的初等变换进行换基迭代； （5）建立新的单纯形表； （6）重复上述过程直到求得最优表格为止。,2020/10/20,98,例 连续投资问题。现有资金10万元，在其后3年预对四个项目进行投资。 A：从第1年到第3年每年初可投资，年末回收本利111%； B：第2年初投资，到第3年末回收本利125%，最大投资3万元； C：