第1章 运筹学基础及应用-第六版ppt课件

2020/5/7,.,1,管理运筹学OPERATIONSRESEARCHFORMANAGEMENTSCIENCE,2020/5/7,.,2,第一章线性规划及单纯形法(LinearProgramming都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。,2020/5/7,.,13,1.2线性规划问题的数学模型,三个组成要素：,1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。,2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。,3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,.,线性规划的数学模型由三个要素构成,决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints,其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个模型是线性规划模型？,2020/5/7,.,15,一般线性规划问题的数学模型：,目标函数：,约束条件：,.,线性规划模型的简写形式(求和符号),.,一般线性规划(LP)问题模型向量形式,其中：,.,一般线性规划(LP)问题模型矩阵形式,其中：,2020/5/7,.,19,1.3线性规划问题的标准形式,标准形式：,标准形式特点：,4.决策变量取值非负。,1.目标函数为求极大值；,2.约束条件全为等式；,3.约束条件右端常数项全为非负；,2020/5/7,.,20,一般线性规划问题如何化为标准型：,1.目标函数求极小值：,令：，即化为：,2020/5/7,.,21,2.约束条件为不等式：,（2）当约束条件为“”时,如：,可令：，显然,称为松弛变量。,称为剩余变量。,2020/5/7,.,22,松弛变量和剩余变量统称为松弛变量,（3）目标函数中松弛变量的系数,由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。,2020/5/7,.,23,3.取值无约束的变量,如果变量xj代表某产品当年计划数与上一年计划数之差，显然xj的取值可能是正也可能是负，这时可令：,其中：,2020/5/7,.,24,例3(教材15页)将下述LP模型化为标准型,2020/5/7,.,25,解：令,得标准形式为：,2020/5/7,.,26,.,线性规划问题及数学模型线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）,.,线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）,.,线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”,.,线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”,.,线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simplex）1963年Dantzig写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”,又称多项式时间算法,.,线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simplex）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,2020/5/7,.,33,求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。,1.4线性规划问题的解的概念,2020/5/7,.,34,可行解：满足所有约束条件的解称为可行解，所有可行解的集合称为可行域。,2020/5/7,.,35,例：考察下述线性规划问题：,2020/5/7,.,36,（2）基,系数矩阵A：,其中,或,2020/5/7,.,37,（3）基向量、基变量,（4）基解、基可行解、可行基,是对应于基,的一个基解、基可行解。,是对应于基,的一个基解、基可行解。,均是可行基。,练习：P14，例4,2020/5/7,.,38,为了便于建立n维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。,求解下述线性规划问题：,2线性规划问题的图解法,2020/5/7,.,39,画出线性规划问题的可行域：,2020/5/7,.,40,1、可行域：约束条件所围成的区域。,2、基可行解：对应可行域的顶点。,3、目标函数等值线：,4、目标函数最优值:最大截距所对应的。,目标函数等值线有无数条，且平行。（观察规律),2020/5/7,.,41,解的几种情况：,(2)无穷多最优解,(1)唯一最优解,若目标函数改为：,约束条件不变，则:,2020/5/7,.,42,解的几种情况：,(4)无界解,(3)无可行解：当可行域为空集时，无可行解。,若目标函数不变，将约束条件1和3去掉，则可行域及解的情况见下图。,目标函数等值线,此时，目标函数等值线可以向上无穷远处平移，Z值无界。,2020/5/7,.,43,几点说明：1、图解法只能用来求解含有两个决策变量的线性规划问题。2、若最优解存在，则必在可行域的某个顶点处取得。3、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。,2020/5/7,.,44,3单纯形法原理,凸集：如果集合C中任意两个点，其连线上的所有点也都是集合C中的点。,上图中（1）（2）是凸集，（3）（4）不是凸集,顶点：如果对于凸集C中的点X，不存在C中的任意其它两个不同的点，使得X在它们的连线上，这时称X为凸集的顶点。,3.1预备知识,2020/5/7,.,45,3.2线性规划问题基本定理,定理1:若线性规划问题存在可行解，则问题的可行域是凸集。,证明:设是线性规划的任意两个可行解，则,于是对于任意的，设，则,所以也是问题的可行解，即可行域是凸集。,2020/5/7,.,46,引理:线性规划问题的可行解X为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。,证明:设（1）必要性显然。（2）设A的秩为m。可行解X的前k个分量为正，且它们对应的系数列向量线性无关，则。当时，恰好构成一组基，而就是这组基对应的基可行解。,当时，在基础上从其余列向量中可以找出个线性无关的向量，恰好构成一组基，而X就是这组基对应的基可行解。,2020/5/7,.,47,定理2:线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。,证明:问题即是要证明:X是基可行解X是可行域顶点，也即要证明其逆否命题：X不是基可行解X不是可行域顶点。,（1）X不是基可行解X不是可行域顶点。,假设X是可行解，但不是基可行解，X的前k个分量为正,其余分量为0，则有又X不是基可行解，所以由引理知，正分量对应的列向量线性相关。即存在一组不全为零的数，使得,2020/5/7,.,48,用非零常数乘以上式得：（1）+（3）得：（1）-（3）得：令选择合适的，使得所有的于是均是可行解，并且，所以X不是可行域顶点。,2020/5/7,.,49,（2）X不是可行域顶点X不是基可行解。,设不是可行域的顶点，因而可以找到可行域内另两个不同的点，使得，用分量表示即为：,易知，当时，必有所以,所以,于是（1）-（2）得,而不全为零，于是知线性相关，X不是基可行解。,2020/5/7,.,50,定理3:若线性规划问题有最优解，一定存在一个基可行解是最优解。,引理：有界凸集中的任何一点均可表示成顶点的凸组合。,证明:假设是可行域顶点，不是可行域顶点，且目标函数在处达到最优，即。,由引理知：可表示为的凸组合，即,因此,假设是所有中最大者，则,2020/5/7,.,51,而是目标函数的最大值，所以也是最大值，也即，目标函数在可行域的某个顶点达到了最优。,从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。,2020/5/7,.,52,3.3确定初始基可行解,寻求最优解的思路：线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，并使得目标函数值不断增大，直到找到最优解为止。,设给定线性规划问题：,2020/5/7,.,53,因此约束方程组的系数矩阵为：,添加松弛变量得其标准形为：,2020/5/7,.,54,由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：,说明：如果约束条件不全是形式，如含所有形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。,称其为初始基可行解。,2020/5/7,.,55,3.4从初始基可行解转换为另一个基可行解,思路：对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。,设有初始基可行解，并可设前m个分量非零，即，于是,2020/5/7,.,56,由构造初始可行基的方法知前m个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为,由于任意系数列向量均可由基向量组线性表示，则非基向量中的用基向量组线性表示为：,2020/5/7,.,57,设有，则,（1）+（2）得：,由此式可知，我们找到了满足约束方程组的另一个解，,要使其成为可行解，只要对所有i=1,2,m，下式成立,要使其成为基可行解，上面m个式中至少有一个取零。（基可行解中非零分量的个数不超过m个。）,（与比较）,2020/5/7,.,58,只要取,于是前m个分量中的第l个变为零，其余非负，第j个分量为正，于是非零分量的个数，并可证得线性无关，所以是新的基可行解。,2020/5/7,.,59,3.4最优性检验和解的判别,设有基可行解,比较两者对应的目标函数值，哪一个更优？,2020/5/7,.,60,2）若对所有的，则，就是最优解。,1）当时，目标函数值得到了改进，不是最优解，需要继续迭代。,易知,2020/5/7,.,61,当所有时，现有顶点对应的基可行解即为最优解。当所有时，又对某个非基变量有则该线性规划问题有无穷多最优解。3.如果存在某个，又向量的所有分量，对任意，恒有，则存在无界解。,结论,2020/5/7,.,62,4单纯形法的计算步骤,设有线性规划问题：,2020/5/7,.,63,(1)找到初始可行基，建立初始单纯形表.,(4)重复二、三两步，直至找到最优解。,4单纯形法的计算步骤,(2)进行最优性检验。计算检验数，若所有0则得最优解，结束.否则转下步.若某0而0，则最优解无界，结束.否则转下步.,(3)从一个可行解转换到另一个目标函数值更大的基可行解。由最大增加原则确定进基变量；由最小比值原则选择出基变量；以为主元素进行换基迭代。,2020/5/7,.,64,(1)找到初始可行基，建立初始单纯形表.,是初始基。,2020/5/7,.,65,(2)进行最优性检验计算检验数，若所有0则得最优解，结束.否则转下步.若某0而0，则最优解无界，结束.否则转下步.,检验数的计算方法：,基变量的检验数一定为0。判断是否达到最优时，只要考虑非基变量检验数。,2020/5/7,.,66,(3)从一个可行解转换到另一个目标函数值更大的基可行解。,由最小比值原则选择出基变量；,进基变量,由最大增加原则确定进基变量：当某些非基变量的检验数时，为使目标函数值增加地更快，一般选择正检验数中最大者对应的非基变量进基，成为新的基变量。,为确保新的基可行解的非零分量非负，按下述规则求得最小比值，其所对应的原基变量中的出基。,于是，新的一组基是：,2020/5/7,.,67,以为主元素进行换基迭代：即利用初等行变换将进基变量所在的系数列变为单位列向量，而变为1。这样原来基矩阵中的就不再是单位向量，取而代之的是，这样就找到了一组新的基。,(4)重复二、三两步，直至找到最优解。,说明：若目标函数是求最小，可以不必将其转变为求最大，但在使用单纯形法求解时，确定进基变量，应找负检验数中最小者，并应以检验数全部为正作为判别最优的条件。,2020/5/7,.,68,解将模型标准化,附例,2020/5/7,.,69,作出初始单纯形表，进行迭代,检验数最大,比值最小,2020/5/7,.,70,2020/5/7,.,71,唯一最优解:X*=(4,6,4,0,0)T，Z*=42,2020/5/7,.,72,特殊情况：（1）出现两个或两个以上相同的最大，此时可任选一个所对应的变量作为进基变量。（2）利用规则决定出基变量时，出现两个或两个以上的最小比值，则迭代后，会出现一个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。出现退化现象时，可考虑采用“勃兰特”规则决定进基变量和出基变量的选择。,2020/5/7,.,73,5.1人工变量,用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。采用人造基的办法：添加人工变量，构造单位矩阵,5单纯形法的进一步讨论,2020/5/7,.,74,人工单位矩阵的构造方法在“”的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（-1），所以再加入一个人工变量，其系数是（+1），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。在原本就是“=”的约束中可直接添加一个人工变量，以便得到初始基矩阵。注意：人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。,求解带人工变量的线性规划有两种方法：大M法两阶段法,2020/5/7,.,75,5.2大M法,没有单位矩阵，不符合构造初始基的条件，需加入人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为（-M）。（求最小值问题中，人工变量系数取M）M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,2020/5/7,.,76,例解线性规划,解化为标准型,此时无单位矩阵作为初始基。,2020/5/7,.,77,添加人工变量，构造初始基：,注意：若求最小值问题，则目标函数中人工变量系数取M。,2020/5/7,.,78,初始单纯形表：,2020/5/7,.,79,2020/5/7,.,80,此时人工变量全部出基，并已达最优条件。最优解为,，最优值为,注意：计算机上使用大M法时，需要用机器最大字长的数字代替M，但当某些系数与之较接近时，还是可能会出错。另外一种求解带人工变量的线性规划问题的方法不会出现这种问题-两阶段法。,2020/5/7,.,81,例解线性规划,解按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：,2020/5/7,.,82,作出单纯形表，进行迭代,2020/5/7,.,83,最优解:X*=(3,0,1)T，Z*=7,2020/5/7,.,84,5.3两阶段法,第一阶段：构造目标函数只含人工变量的线性规划问题，求解后判断原线性规划问题是否有基本可行解，若有，则进行第二阶段；第二阶段：将第一阶段的最终单纯形表所对应的解，去掉人工变量，作为第二阶段的初始单纯形表的初始基可行解，进行单纯形法的迭代。,2020/5/7,.,85,解（1）化标准型、并添加人工变量得：（此处未将目标变为MAX）,例：,2020/5/7,.,86,（2）构造第一阶段问题：,说明：原问题目标函数无论是求MAX还是求MIN，构造的第一阶段问题目标函数都是求最小MIN。,2020/5/7,.,87,求解第一阶段问题：,2020/5/7,.,88,此时所得可行解目标函数值为0，故原规划问题有基可行解。转入第二步。,2020/5/7,.,89,（3）去掉人工变量，得到第二阶段的单纯形表，在此基础上继续求解。,最优解为：,2020/5/7,.,90,5.4关于解的不同情况的判别,1、无穷多最优解例：,解：将问题化为标准型：,2020/5/7,.,91,2020/5/7,.,92,从上表中可知，已达最优解，为，而，若将选为进基变量迭代后，可得另一最优解。,上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。,判别无穷多最优解的方法：单纯形表的检验数行已达最优性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。,2020/5/7,.,93,2、无可行解例用单纯形表求解下列线性规划问题,解：化为标准型：,2020/5/7,.,94,单纯形表求解线性规划问题,2020/5/7,.,95,单纯形法的最终表里有人工变量大于零，则此线性规划无可行解。,2020/5/7,.,96,3、无界解,例用单纯形表求解下面线性规划问题。,解,2020/5/7,.,97,此时的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以取得无限大。,2020/5/7,.,98,事实上，此从1次迭代的单纯形表中，得到约束方程：,移项可得：,由此可知，目标函数可以任意大，即无界。,2020/5/7,.,99,练习：用大M法求解下列线性规划问题,1、,2、,2020/5/7,.,100,解1：将模型化为标准型得：,建立单纯形表并计算如下,2020/5/7,.,101,显然，检验数已全部非正，已达最优解，但非基变量X2的检验数为0，故知此问题有无穷多最优解。,2020/5/7,.,102,解2：将模型化为标准型得：,建立单纯形表并计算如下,2020/5/7,.,103,2020/5/7,.,104,最优解为（4，4）,.,第一章线性规划及单纯形法,LinearProgramming（LP）,线性规划问题及其数学模型,线性规划的图解法,线性规划的单纯形法,线性规划问题的应用,线性规划问题的求解方法,.,单纯形法的求解思路,是,否,循环,.,以alk为主元素进行迭代，利用初等行变换将xk所在列化为单位向量，即alk化为1，其它元素化为0，得到改进的可行基，转入第步。,计算步骤总结（有可行解时）,将线性规划问题化成标准形式;找出一个m阶单位矩阵作初始可行基，得到初始基可行解;计算各非基变量xj的检验数j，若所有j0，则问题已得到最优解，停止计算，否则转入下步;若存在某个s0，且对应的所有系数ais0，则此问题是无界解，停止计算，否则转入下步;根据maxj|j0=k原则，确定xk为入基变量，再按=minbi/aik|aik0=bl/alk规则，确定xl为出基变量，得到改进的基可行解。,.,单纯形表,目标系数区,约束条件系数区,右端系数,检验系数区,基变量区,.,基变量的系数,目标函数中变量的系数,决策变量,约束方程组的系数矩阵,出基变量判断参数,方程右端常数项,各变量的检验数,基变量,单纯形表,.,由单纯形表判别解的类别,无可行解,唯一最优解,所有,无穷多最优解,无界解（无最优解）,最优解,所有非基变量的检验数*,.,由单纯形表判别解的类别,无可行解,唯一最优解,所有,无穷多最优解,无界解（无最优解）,最优解,所有非基变量的检验数*,.,保证当前的基可行解是最优解,至少有一个等于0，如,至少有一个大于0，如,0,存在，保证当xp入基时有xl出基,两个最优解连线上的所有点都是最优解,说明能得到另一个最优基可行解,.,无穷多最优解,示例：,s.t.,s.t.,.,.,此时所有检验数,得到最优解,最优值为,.,此时所有检验数,得另一最优解,最优值为,.,A,.,1,课后题：P481.8,0,0,2,4,-2,3,5,2,3,5,-3/2,.,练习题：求ag的值，并判断表中解是否最优解,单纯形法计算时某一步的表格,为松弛变量，表中解代入目标函数后得,2020/5/7,.,120,小结表格单纯形表的使用,（1）化线性规划模型为标准型，建立初始单纯形表。（2）根据单纯形表按照最大增加原则选择进基变量；（3）按照最小比值原则选择换出变量；（4）实施矩阵的初等变换进行换基迭代；（5）建立新的单纯形表；（6）重复上述过程直到求得最优表格为止。,.,121,一般地讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型。(1)要求解问题的目标函数能用数值指标来表示，且为线性函数；(2)存在着多种方案及有关数据；(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。,7线性规划应用举例,.,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线性规划应用举例,.,123,所有可能的裁截方案,表2-12-(a),.,124,建模分析,.,125,为了得到100套钢架，需要混合使用各种下料方案。设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5。根据表2-12-(a)的方案，可列出以下数学模型：,7线性规划应用举例,.,126,模型求解-首先标准化,.,127,两阶段法求解结果,2020/5/7,.,128,例连续投资问题。现有资金10万元，在其后3年预对四个项目进行投资。A：从第1年到第3