4线性规划的基本理论

线性规划及其理论基础
线性规划是求解数量模型的一种方法，其基本理论是将实际问题表述为一个约束条件的线性规划模型，并利用线性规划的优化原理对模型进行求解，以获得最优解。

线性规划的基本理论包括：
1. 模型及线性表示：线性规划模型是通过将目标函数和约束条件用线性方程组表示的。

2. 目标函数和约束条件：线性规划模型中，目标函数和约束条件必须都是线性的。

3. 最优解：线性规划模型中的最优解是满足所有约束条件下目标函数值最大（或最小）的解。

4. 数学优化原理：线性规划模型的最优解可以通过数学优化原理进行求解，即利用图论、单纯形理论等数学优化方法。

第二章线性规划线性规划（linear programming，简称LP）是运筹学的一个重要分支，研究得比较早，尤其自1947年丹捷格（G.B.Dantzig）提出了单纯形法之后，线性规划在理论上趋向成熟．线性规划研究的对象大体可分为两大类：一类是在现有的人、财、物等资源的条件下，研究如何合理地计划、安排，可使得某一目标达到最大，如产量、利润目标等；另一类是在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使生产成本、费用最小等．这两类问题从本质上说是相同的，即都在一组约束条件下，去实现某一个目标的最优（最大或最小）．线性规划研究的问题要求目标与约束条件函数均是线性的，而目标函数只能是一个．在经济管理问题中，大量的问题是线性的，有的可以转化为线性的，从而使线性规划有极大的应用价值．据美国《财富》杂志对全美500家大公司的调查，线性规划的应用名列前茅，有85%左右的公司频繁地使用线性规划．第一节线性规划问题及其数学模型一、线性规划问题的数学模型在生产实践和日常生活中，经常会遇到如何合理地使用有限资源（如资金、劳力、材料、机器、仪器设备、时间等），以获得最大效益的问题．例2-1 某制药厂在计划期内要安排生产Ⅰ、Ⅱ两种药品，这些药品分别需要在D、、四种不同的设备上加工．按工艺规定，每千克药品Ⅰ和Ⅱ在各BCA、台设备上所需要的加工台时数如表2-1．已知各设备在计划期内有效台时数（1台设备工作1小时称为1台时）分别是12、8、16和12．该制药厂每生产1千克药品Ⅰ可得利润200元，每生产1千克药品Ⅱ可得利润300元．问应如何安排生产计划，才能使制药厂利润最大？A、两种药品每千克在各台设备上所需的加工台时数表2-1 B药品A B C DⅠ 2 1 4 0Ⅱ 2 2 0 4这是一个资源有限，但需利润最大的线性规划问题．解 设1x ，2x 分别表示在计划期内药品Ⅰ和Ⅱ的产量（千克），Z 表示这个期间的制药厂利润．则计划期内生产Ⅰ、Ⅱ两种药品的利润总额为21300200x x Z +=（元）．但是生产Ⅰ、Ⅱ两种药品在A 设备上的加工台时数必须满足122221≤+x x ；在B 设备上的加工台时数必须满足8221≤+x x ；在C 设备上的加工台时数必须满足1641≤x ；在D 设备上的加工台时数必须满足1242≤x ；生产Ⅰ、Ⅱ两种药品的数量应是非负的数，即0,21≥x x ．于是上述的问题归结为：目标函数 21300200Max x x Z += 122221≤+x x8221≤+x x约束条件 1641≤ x1242≤x0,21≥x x同样，在经济生活和生产活动中也遇到另一类问题，即为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分等，以使消耗（人力、设备台时、资金、原材料等）为最少．例2-2 用3种原料321B B B 、、配制某种食品，要求该食品中蛋白质、脂肪、糖、维生素的含量不低于15、20、25、30单位．以上3种原料的单价及每单位原料所含各种成分的数量，如下表2-2所示．问应如何配制该食品，使所需成本最低？表2-2 3种原料所含成分营养成分 原料 食品中营养成分的最低需要量（单位） 1B 2B3B蛋白质（单位/千克）5 6 8 15 脂肪（单位/千克）3 4 6 20 糖（单位/千克）8 5 4 25 维生素（单位/千克）10 12 8 30 原料单价（元/千克）20 25 30这个问题是在食品的营养要求得到满足的前提下，如何通过适当的原料配比，使食品的成本最低．解 设321x x x 、、分别表示原料321B B B 、、的用量（千克），Z 表示食品的成本（元），则这一食品配制问题变为：目标函数 321302520Min x x x Z ++= 15865321≥++x x x20643321≥++x x x约束条件 25458321≥++x x x3081210321≥++x x x0,,321≥x x x例2-3 某医院每天至少需要下列数量的护士（见表2-3）．表2-3 某医院每天至少需要的护士数班次 时间 护士数1 上午6时－上午10时 602 上午10时－下午2时 703 下午2时－下午6时 604 下午6时－晚10时 505 晚10时－凌晨2时 206 凌晨2时－上午6时 30每班的护士在值班开始时向病房报到，连续工作8小时．试问：为满足每班所需要的护士数，医院最少应雇用多少护士？请列出线性规划问题的数学模型．解 设1x 表示第1班次向病房报到的护士数；2x 表示第2班次向病房报到的护士数；3x 表示第3班次向病房报到的护士数；4x 表示第4班次向病房报到的护士数；5x 表示第5班次向病房报到的护士数；6x 表示第6班次向病房报到的护士数．则有目标函数 ∑==61Min Z j j x 6016≥+x x7021≥+x x6032≥+x x约束条件 5043≥+x x2054≥+x x3065≥+x x0≥j x 且为整数 6,,2,1Λ=j例2-4 某一卫生所配有1名医生和1名护士．医生每天工作8小时，护士每天工作9小时．服务的项目是接生和做小手术．一次接生，医生要花0.5小时，护士同样要花0.5小时；一次小手术，医生要花1小时，护士要花1.5小时．这是一所小规模的卫生所，每天容纳的手术数和接生数合计不能超过12次．假定一次手术的收入为200元，一次接生的收入为80元．问怎样合理安排接生和手术的数量，使医生和护士一天工作能收入最多？解 设每天手术数为1x ，每天接生数为2x ，则目标函数 2180200Max x x Z +=82121≤+x x 9212321≤+x x 12 21≤+x x0,21≥x x 且为整数二、线性规划问题的结构特征从上面4个例子可见，线性规划的数学模型（model of LP ）有如下特征：1．都有一组未知变量（n x x x ,,,21Λ）代表某一方案，它们取不同的非负值，代表不同的具体方案；2．都有一个目标要求，实现极大或极小．目标函数要用未知变量的线性函数表示；3．未知变量受到一组约束条件的限制，这些约束条件用一组线性等式或不等式表示．正是由于目标函数和约束条件都是未知变量的线性函数，所以我们把这类问题称为线性规划问题．线性规划问题的一般形式：目标函数 n n x c x c x c Z +++=Λ2211 (Min)Max11212111),(b x a x a x a n n ≥=≤+++Λ22222121),(b x a x a x a n n ≥=≤+++Λ约束条件 …………………………m n mn m m b x a x a x a ),(2211≥=≤+++Λ0,,,21≥n x x x Λ这里，n n x c x c x c +++Λ2211称为目标函数，记为Z ，其中，j c （n j ,,2,1Λ=）称为成本或利润系数；ij a （m i ,,2,1Λ=；n j ,,2,1Λ=）称为约束条件中未知变量的系数；i b （m i ,,2,1Λ=）称为限定系数．约束条件三、线性规划问题的标准形式建立线性规划的标准形式有助于我们研究它的求解方法，至于其他各种形式的线性规划问题，我们可以先将非标准形式变成标准形式，然后再用标准形式的求解方法求解．（一）线性规划问题的标准形式线性规划的标准形式（standard form of LP ）为：目标函数 n n x c x c x c Z +++=Λ2211Max 11212111b x a x a x a n n =+++Λ22222121b x a x a x a n n =+++Λ…………………………m n mn m m b x a x a x a =+++Λ22110,,21≥n x x x Λ0≥i b (m i ,,2,1Λ=)式中，jc （n j ,,2,1Λ=）称为成本或利润系数；ij a （m i ,,2,1Λ=；n j ,,2,1Λ=）称为未知变量的系数；i b （m i ,,2,1Λ=）称为限定系数．标准形式的主要特点是：①目标函数最大化；②所有的约束条件由等式表示；③所有的变量和每一约束条件右端的常数项均为非负值．（二）书写形式为书写简便，我们可以将上述线性规划问题的标准形式写成如下两种形式，其中..t s 代表约束条件．1．简缩形式∑==nj j j x c Z 1Max∑==nj i j ij b x a 1 m i ,,2,1Λ=..t s 0≥j x n j ,,2,1Λ=约束条件0≥i b m i ,,2,1Λ=2．矩阵形式CX Z =Max b AX = ..t s 0≥X0≥b其中， ),,,(21n c c c C Λ=mn m m n n a a a a a a a a a A ΛΛΛΛΛΛΛ212222111211= n x x x X Λ21= m b b b b Λ21 = 000 0Λ= 这里C 为成本或利润向量，X 为决策向量，A 为系数矩阵（或称约束矩阵），b 为限定向量（或称右端向量），条件0≥X 称为非负约束． （三）标准形式的转化当给出的线性规划为非标准形式时，可以按照下述的方法化为标准形式．1．目标函数的转换 若给出的线性规划要求目标函数极小化，即 ∑==nj j j x c Z 1Min ，因)(Max Min Z Z --=，所以只须令Z Z '=-，即有j nj j x c Z Z ∑=-=-='1)(Max )(Max Max这就是标准形式的目标函数了．2．约束条件的转换 由于标准形式要求所有的约束条件是等式，必须把不等式的约束条件化为等式．须引入新的变量，代表每个不等式左右端之间的差额．这些新的变量称为松弛变量或剩余变量．这里有2种情况：一种是约束条件为“≤”形式的不等式，则可在“≤”的左端加入非负的松弛变量，把原“≤”形式的不等式变为等式；另一种是约束条件为“≥”形式的不等式，则可在“≥”号的左端减去一个非负的剩余变量（也可称松弛变量），把不等式改为等式．例如前面例2-1中线性规划问题的标准形式可写为：目标函数 21300200Max x x Z += 12 22321＝x x x ++8 2421＝x x x ++..t s 16 451＝x x + 12 4 62＝x x +0,,,621≥x x x Λ式中6543x x x x 、、、为松弛变量．例2-2中线性规划的标准形式可写成：321302520Max x x x Z ---='15 86 5 4321=-++x x x x20 64 3 5321=-++x x x x..t s 25 45 8 6321=-++x x x x30 812107321=-++x x x x0,,,721≥x x x Λ式中Z Z '-=，74~x x 为剩余变量（也可称松弛变量）．要注意的是松弛变量或剩余变量都是非负值，它们的实际意义是未被利用的资源或额外的提供量．由于松弛变量或剩余变量都不会影响目标函数的增加或减少，所以在目标函数中它们的系数都应当为零．3．变量的非负转换 若存在无非负要求的变量，即变量k x 取正值或负值都可以，在物理、经济意义上都是合理的，这时为了满足标准形式对变量的非负要求，可令k x ＝k x '－k x ''，其中，0≥'k x ，0≥''k x ．由于k x '可能大于k x ''，k x '也可能小于k x ''，故k x 可为正值也可为负值．以上讨论说明，任何形式的线性规划问题都可化成标准形式．第二节 线性规划问题的图解法讨论两变量的线性规划问题的图解法（graphical solution of LP problems ），是为了更直观地了解线性规划问题及其解的基本概念，从而了解求解线性规划问题的一般方法——单纯形法的基本原理．一、线性规划问题解的基本概念设线性规划问题的标准形式为：⎪⎪⎩⎪⎪⎨⎧=≥=≥===∑∑==mi b n j x m i b x a t s x c Z ij nj i j j i nj jj ,,2,10,,2,10,,2,1..11ΛΛΛMax 1．可行解 满足约束条件的解T n x x x X ),,,(21Λ=，称为线性规划问题的可行解．所有可行解的集合称为可行域．2．最优解 满足目标函数式的可行解，称为线性规划问题的最优解．3．最优值 对应于最优解的目标函数之值，称为最优值．二、两个变量的线性规划问题的图解法例2-5 以上一节例2-1为例:⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≤+≤++=0,124164821222..3002002121212121x x x x x x x x t s x x Z Max由于此问题是两变量的线性规划问题，因而可用图解法求解．求解过程是先求出满足约束条件的可行解区域；然后从可行解区域中找出最优解．具体步骤如下：第1步 建立平面直角坐标系，取1x 为横轴，2x 为纵轴．第2步 求满足约束条件的可行解区域．本例中作直线①：122221=+x x ,第一个约束不等式的解由直线122221=+x x 及其左下方半平面表示；作直线②：8221=+x x ，第二个约束不等式的解由直线8221=+x x 及其左下方半平面表示；作直线③：1641=x ，第三个约束不等式的解由直线1641=x 及其左方半平面表示；作直线④：1242=x ，第四个约束不等式的解由直线1242=x 及其下方半平面表示；1x 和2x 变量非负条件的区域为第1象限．满足所有约束条件的可行解区域（也称可行域）是由上述5个区域的公共部分表示，即图2-1中OABCD 的区域（包括边界）．在这个区域里的每一点(包括边界上的点)都是可行解．从图上我们可以看到这个可行域是一个凸多边形，我们把它称为凸集（如果在形体中任意取两点连接一根直线，若线段上所有的点都在这个形体中，则称该形体为凸集）．第3步 作目标函数的等值线簇，确定目标函数值增加方向．本例中，由目标函数21300200 x x Z +=可知，当Z 值取不同的数值时，在图上可得到一簇以Z 为参数的平行线．位于同一直线上的点，具有相同的目标函数值，因而称每条直线为“等值线”．对于直线21300200 x x Z +=来说，当Z 值由小变大时，直线3003212Z x x +-=向右上方平行移动．作直线600300200 21=+x x （Z ＝600），在这条直线上的所有点其Z 值均为600．第4步 从可行解区域内找满足目标函数的最优解．从图2-1中可以看到，当等值线600300200 21=+x x 向右上方平移到距原点最远且仍与可行域有一交点时，那个交点便是使Z 值取值最大的可行解，即最优解．在本例中C 点是最优解，此时1x ＝4，2x ＝2，Z ＝1400． 简单表示为：X *＝()T24，Z *=1400．例2-6 用图解法解线性规划： 212Max x x Z +=10221≤+x x 1 21≥+x x..t s 0 1≥x 0 2≥x 4 2≤x解 按照例2-5的步骤作出图2-2，求出凸五边形ABCDE 所围成的可行区域，并作目标函数的等值线)2(2221==+Z x x ，随着Z 值的逐渐增大，等值线不断向右上方平行移动，最后与可行域的边AB 重叠．所以线段AB 上的每一点所对应的（21 ,x x ）都为最优解，即该线性规划问题有无穷多个最优解，不过最优值是唯一的，10*=Z ．例2-7 解下列线性规划：⎩⎨⎧≥≤-+=0,80810..123212121x x x x t s x x Z Max 解 从图2-3可看出，规划的可行域是无界的，并且无最优解（最优解无限大）．这个例子中出现的情况在实际问题中并不存在，因为资源是有限的，所以不可能取得无限大的收益．出现这种情况往往是由于建立数学模型时考虑不周，忽略了某些约束条件而造成．三、线性规划问题解的特点由上面的图解法可以直观地看出线性规划问题的解具有如下几个特点：1．可行域总是凸多边形；2．如果一个线性规划问题确实存在唯一的最优解，那么它必定可在其可行域的一个顶点上达到；3．如果一个线性规划问题存在多重最优解，那么至少在其可行域有两个相邻的顶点所对应的目标函数值相等，且达到最大值（或最小值）；4．如果可行域中一个顶点的目标函数值比其相邻顶点的目标函数值要好的话，那么它就比其他所有顶点的目标函数值都要好，或者说它就是一个最优解．有时在求解线性规划时，会发现线性规划的约束条件矛盾，无法找到可行域，这时线性规划无解；有时也会遇到可行域无界且无最优解，这时称为无界解．第三节单纯形法在实际问题中，我们常常遇到的线性规划问题不是仅涉及两个变量，而是两个以上的多变量线性规划问题．对两个以上的多变量线性规划问题无法用图解法求解，必须使用简便有效的求解方法——单纯形法（simplex method）．一、单纯形法的基本原理（一）典型方程组一般线性规划问题标准形式的约束条件如下式（2-1），是一个有n个未知数、m个方程的线性方程组．如果这m个方程是独立的（即其中任一方程均不能由其它方程代替），则通过初等变换，必能使式（2-1）化成式（2-2）形式的同解方程组：∑==njijijbxa1mi,,2,1Λ=（2-1）1x ' +11221111b x a x a x a n n m m m m '=''+⋅⋅⋅+''+''++++ 2x ' +22222112b x a x a x a n n m m m m '=''+⋅⋅⋅+''+''++++ （2-2）…………………………………………………………mx '+m n mn m mm m mm b x a x a x a '=''+⋅⋅⋅+''+''++++2211 式中n x x x '⋅⋅⋅'',,,21是重新排序后的变量．式（2-2）被称为典型方程组．即如果在一个线性方程组中的每一个方程中都有系数为1，并且不再出现在其它方程的一个未知量，则此方程组称为典型方程组．（二）基本变量如果变量j x 在某一方程中系数为1，而在其它一切方程中的系数为零，则称j x 为该方程中的基本变量．否则为非基本变量．如式（2-2）中的m x x x '⋅⋅⋅'',,,21为基本变量，n m mx x x '⋅⋅⋅''++,,,21为非基本变量．基本变量的个数为线性无关的方程的个数．事实上，n 个变量中任意m 个都可能作为基本变量，因此由排列组合知识可知，基本变量的组数为mn c 个，n 为未知变量的个数，m 为线性无关的方程的个数．（三）基本解在典型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解．基本解的个数为m n c 个．（四）基本可行解基本变量为非负的一组基本解称为基本可行解，基本可行解的个数最多不超过m n c 个．例如，对方程组32 4321=+-+x x x x ① 13 2421=+x x x － ②施行初等变换[①×（－2）＋②],可以得到：32 4321=+-+x x x x ① 572 432-=-+-x x x ③ [③×(－1)] : 32 4321=+-+x x x x ① 572432=+-x x x ④ [④×（－1）＋①]: 25431-=-+x x x ⑤ 572432=+-x x x ④式⑤和④为典型方程组，基本变量是1x 和2x ，非基本变量为3x 和4x ．设非基本变量3x 和4x 为零，则1x 和2x 分别等于-2和5，即对应于典型方程组⑤和④，基本解为：X =()T0052-．因基本变量中1x 为负值，所以此解不是基本可行解．根据方程组①和②有4个未知变量，因此通过初等变换可得到24c 组（即6组）典型方程组和基本解．若令2x 和4x 为基本变量，通过初等变换，方程组①和②可变换为： [①×（－1）＋②]: 32 4321=+-+x x x x ① 25 431－=-+x x x ③ [③×（－1/5）]: 324321=+-+x x x x ① 4.0202.0431=+--x x . x ④ [④×（－2）＋①] : 2.2604.1321=-+ x . x x ⑤ 4.0202.0431=--x x . x ＋ ④此时，典型方程组的基本变量为2x 和4x ，非基本变量为1x 和3x ．基本解为：T X ）（0.4 0 2.2 0 =，因为基本变量为非负值，所以此基本解也为基本可行解．（五）单纯形法的原理理论上已经证明，线性规划的基本可行解与可行域的顶点是一对一的．这就决定了线性规划可行域的顶点个数最多也不超过m n c 个．上面讨论线性规划问题解的特点时已指出，如果线性规划有最优解，一定可以在可行域的某个顶点处达到．因此，单纯形法的基本思路是：根据问题的标准形式，从可行域中的一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解．在用单纯形法求解线性规划问题时，应考虑的问题：1．建立初始基本可行解 在用单纯形法求解时，首先应将线性规划问题以标准形式表达、约束条件以右端常数非负的典型方程组表示，确定初始基本可行解．在前面的阐述中，已讨论了如何将一般线性规划问题转化为标准形式的线性规划问题，如何将约束条件通过初等变换以典型方程组形式表示，以及如何得出基本可行解（最初得到的基本可行解也称初始基本可行解），此处不再赘述．经过变换，典型方程组和初始基本可行解可用式（2-3）表示：1x +11221111b x a x a x a n n m m m m '='+⋅⋅⋅+'+'++++ 2x +22222112b x a x a x a n n m m m m '='+⋅⋅⋅+'+'++++ （2-3）………………………………………………………m x +m n mn m mm m mmb x a x a x a '='+⋅⋅⋅+'+'++++2211 初始基本可行解：T mb b X )00(10ΛΛ''=． 2．最优性检验 得到一个基本可行解后，我们要判断它是不是最优解．一般情况下，经过迭代后式（2-3）变为∑+='-'=nm j jiji i xa b x 1（m i ,,2,1Λ=） （2-4）将式（2-4）代入目标函数式，整理后得∑∑∑+==='-+'=n m j mi j iji jmi i i x a c c b c Z 111)( （2-5）令∑='=mi i i b c Z 10 , ∑='=mi iji j a c Z 1, n m m j ,,2 ,1Λ++= 于是∑+=-+=nm j j j jx Z cZ Z 10)( （2-6）由于当m j ,,2 ,1Λ=时，j mi ij i j c a c Z ='=∑=1，即0=-j j Z c （m j ,,2 ,1Λ=），所以式（2-6）也可写作∑∑∑=+=+=-+-+=-+=mj j j j nm j nm j j j jj j jx Z c x Z cZ x Z cZ Z 11100)()()(∑=-+=nj j j j x Z c Z Z 10)( n j ,,2 ,1Λ=再令j j j Z c C -= n j ,,2 ,1Λ=j C 为变量j x 的检验数．则∑=+=nj j j x C Z Z 10 （2-7）（1）最优解判别 若)0(X ＝T m b b b )00(21⋅⋅⋅'⋅⋅⋅''为基本可行解，且对一切n j ,,2 ,1Λ=,有0≤j C ，则)0(X 为最优解．（2）无有限最优解判别 若)0(X ＝T m b b b )00(21⋅⋅⋅'⋅⋅⋅''为一基本可行解，有一个k C >0，且对一切m i ,,2,1Λ=有0≤ik β（ik β为约束条件方程中的系数，n k ,,2,1Λ=），那么该线性规划问题无有限最优解（或称有无界解或无最优解）． 事实上，应用向量的乘法，可以将检验数的求法表示得简明一些．令j c 表示目标函数中变量j x 的系数，B C 表示基本变量在目标函数中的系数行向量，j P 表示变量j x 在典型方程中的系数列向量，则⎪⎪⎪⎪⎪⎭⎫⎝⎛⋅-=⋅-=-=mj j j B j j B j j j j a a a C c P C c Z c C Λ21 n j ,,2 ,1Λ= （2-8）基本变量的检验数总等于0．目标函数值b C Z B ⋅=.3．基本可行解的改进 若初始基本可行解)0(X 不是最优解及不能判别无最优解时，需找一个新的基本可行解．具体方法是：首先确定进基变量，再确定出基变量．进基变量的确定：由式（2-7）可知，检验数j C 对线性规划问题的实际意义是：j C 表示当变量j x 增加1个单位时，目标函数的增加量；其经济意义表示相对利润．当0>j C 时，说明非基本变量j x 增加1个单位，目标函数可以增加，即现在的函数值不是最优，还能增加．这时要将某个非基本变量换到基本变量中去（称为进基变量）．为了使目标函数值增长最快，所以应选择j C 值最大的一项所对应的非基本变量进基,k C =>)0j C (max . 则对应的k x 为进基变量．进基变量所在的列（k ）称为枢列．出基变量的确定：当进基变量确定后（假设i x 是进基变量），出基变量的选定是应用“最小比值规则”．即用此时的各约束方程右端的常数项i b （非负数）与相应方程中k x 的正系数ik β相比，并选取最小商值的基本变量l x 为出基变量（将由基本变量变为非基本变量）．{}lkl ik ik i i bb βββθ=⎭⎬⎫⎩⎨⎧>=0min min出基变量所在的行（l ）称为枢行．枢行与枢列交点处的元素（lk β）称为枢元．然后通过初等变换，将约束条件转为关于新的基本变量的典型方程组，并求得新的基本可行解．对于新的基本可行解可再进行上述的最优性检验．二、单纯形解法上面介绍的单纯形法原理看似复杂，但如用表格形式计算，则比较容易操作．单纯形法的计算步骤：第1步：找出初始基本可行解，建立初始单纯形表．第2步：检验对应于非基本变量的检验数j C ，若对所有的0≤j C（n j ,,2 ,1Λ=），则已得到最优解，计算最优值∑==mi i i b c Z 1，即可结束．否则，转入下一步．第3步：在所有0>j C 中，若有一个k C 对应k x 的系数列向量，即对m i ,,2,1Λ=均有0≤ik β，则此问题无有限最优解（或称有无界解或无最优解），停止计算．否则转入下一步．第4步：根据()0max >j C ＝k C ，确定k x 为进基变量，再依据“最小比值规则”（{}lk l ik ik i i b b βββθ=⎭⎬⎫⎩⎨⎧>=0min min ）确定l x 为出基变量． 第5步：实施以枢元素为中心的初等变换，使约束方程组变为关于新的基本变量的典型方程组，得到新的单纯形表，重复第二步…，一直到没有新的非基本变量可以改善目标函数为止．若线性规划模型为：CX Z =Min ..t s b AX = 0≥X上述单纯形法的计算步骤仍有效，只是其中的第二步改为：若对所有的0≥j C （n j ,,2,1Λ=），则已得到最优解；第三步改为在所有0<j C 中，若有一个k C 对应k x 的系数列向量，即对m i ,,2,1Λ=均有0≤ik β，则此问题无有限最优解（或称有无界解或无最优解）；第四步改为)0min(<j C ＝k C ，确定k x 为进基变量．例2-8 现以例2-1来说明单纯形法的表上解法．⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤≤+≤++=0,124164821222..3002002121212121x x x x x x x x t s x x Z Max解 首先将线性规划问题标准化，即在约束条件中引入松弛变量3x 、4x 、5x 、6x ，则标准化后的线性规划模型为：21300200Max x x Z +=12 22321＝x x x ++ 8 2421＝x x x ++..t s 16 451＝x x + 12 462＝x x + 0,,,621≥x x x Λ此时约束方程组已为典型方程组，根据上述线性规划模型可以列出初始单纯形表（表2-4）：表2-4 单纯形法求解例2-1（1）表2-4中：10040010004001021000122 为典型方程组中变量的系数，j x 为规划中出现的变量，j c 为变量j x 在目标函数中的系数，B X 为基本变量，B C 为基本变量在目标函数中的系数，b 为典型方程组右端常数项（非负值），θ为确定出基变量的商值，ikii b βθ=（0>ik β），j C 为变量j x 的检验数，j P C c C B j j ⋅-=，Z为此时目标函数值，b C Z B ⋅=． 根据初始单纯形表可以看出：初始基本可行解是01=x ，02=x ，123=x ，84=x ，165=x ，126=x此时目标函数值()⎪⎪⎪⎪⎪⎭⎫⎝⎛⋅=12168120000Z ＝0检验数111P C c C B ⋅-=＝200－()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅04120000＝200222P C c C B ⋅-=＝300－()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅40220000＝3003C =4C =5C ＝6C ＝0（基本变量的检验数总等于零）由于01>C ，02>C ，所以初始基本可行解非最优解．又由于12C C >，所以确定2x 为进基变量．进一步求最小θ值：{}{}33,4,6min 412,28,212min 0min min ==⎭⎬⎫⎩⎨⎧=⎭⎬⎫⎩⎨⎧>=ik ik i i b ββθ即从第4个方程中算出的商值最小，而第4个方程中的基本变量是6x ，于是6x 为出基变量．表中给第4个约束方程中2x 的系数4加上方括号以突出其为枢元．接下去的工作是将2x 取代6x ，表2-4中的约束方程化为以3x 、4x 、5x 和2x 为基本变量，1x 和6x 为非基本变量的典型方程，以便求出新的基本可行解．从表2-4中可以看到，只需对方程组实行初等变换，使枢元位置变成1，而枢列中的其它元素变为零（即以枢元为中心的初等变换）就可以了．此处可先将第4个方程除以4，使枢元位置变成1；然后用新得到的第4个方程乘以（-2）后分别加到第1个和第2个方程上，使枢列中的第1个和第二个方程所在位变为零．这样我们可以得到新的单纯形表（表2-5）．表2-5给出的新的基本可行解是1x ＝0，2x ＝3，3x ＝6，4x ＝2，5x ＝16，6x ＝0此时目标函数值()⎪⎪⎪⎪⎪⎭⎫⎝⎛⋅=31626300000Z ＝900检验数111P C c C B ⋅-=＝200-()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅0412300000＝200666P C c C B ⋅-=＝0-()⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--⋅4102121300000＝75-2C ＝3C =4C =5C ＝0（基本变量的检验数总等于零）表2-5 单纯形法求解例2-1（2）由于01>C ，所以此时基本可行解非最优解，确定1x 为进基变量． 进一步计算最小θ值：{}{}24,2,3min 416,12,26min 0min min ==⎭⎬⎫⎩⎨⎧=⎭⎬⎫⎩⎨⎧>=ik ik i i b ββθ即从第2个方程中算出的商值最小，而第2个方程中的基本变量是4x ，于是4x 为出基变量．接着进行第二次迭代，将1x 取代4x ，表2-5中的约束方程化为以3x 、1x 、5x 和2x 为基本变量，4x 和6x 为非基本变量的典型方程，以便求出新的单纯形表．重复单纯形法计算第2 步～第5步，一直到没有新的非基本变量可以改善目标函数为止（见表2-6和表2-7）．表2-6 单纯形法求解例2-1（3）表2-7 单纯形法求解例2-1（4）表2-7中：目标函数值()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅=244030002000Z =1400检验数444P C c C B ⋅-==0-()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--⋅2120130002000=-150555P C c C B ⋅-==0-()⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--⋅8121414130002000=225- 1C =2C =3C =6C =0（基本变量的检验数总等于零）由于0≤j C ，6,,2,1Λ=j ，所以此基本可行解41=x ，22=x ，03=x ，04=x ，05=x ，46=x ，即为最优解，最优值为Z *＝1400．与前面图解法求解结果一致．为了加深对单纯形法基本思想的理解，不妨将表2-4、表2-5、表2-6、表2-7和图2-1进行对照，可以发现表2-4给出的基本可行解对应于图中可行域顶点0，表2-5给出的基本可行解对应于顶点A ，表2-6给出的基本可行解对应于顶点B ，表2-7给出的最优解对应于顶点C ．线性规划问题有无穷多个可行解，应用单纯形法可以高效率地求解此类问题．例2-9 用单纯形法求解下列规划问题43213Min x x x x Z +++=4 22321=++-x x x..t s 6 3421=++x x x0,,,4321≥x x x x解 令Z Z -='，于是原线性规划问题变为标准形式：43213Max x x x x Z ----='4 22321=++-x x x..t s 6 3421=++x x x 0,,,4321≥x x x x由于约束方程组已是典型方程组，所以可直接用单纯形表求解，见表2-8．表2-8 单纯形法求解例2-9表2-8计算得最优解是1x ＝0，2x ＝2，3x ＝0，4x ＝4，最优值为Z *＝-Z '*=6． 实际上，此线性规划问题也可根据单纯形法求解的基本思想，按照前面单纯形法计算步骤中提到的改变检验数判断方法，直接用单纯形表求解极小化问题，见表2-9．若对所有的0≥j C （n j ,,2,1Λ=），则已得到最优解；所有0<j C 中，若有一个k C 对应k x 的系数列向量，即对m i ,,2,1Λ=均有0≤ik β，则此问题无有。

毕业论文文献综述信息与计算科学线性规划理论及其应用一、前言部分[1] [2]线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大化或最小化的问题，最大化问题是要在一个集合上使一个函数达到最大，最小化问题是要在一个集合上使一个函数达到最小。

统称为线性规划问题。

满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。

决策变量、约束条件、目标函数是线性规划的三要素。

随着计算机技术的发展和普及，线性规划的应用越来越广泛。

它已成为人们为合理利用有限资源制定最佳决策的有力工具。

二、主题部分2.1线性规划理论发展过程及方向2.1.1线性规划发展过程[3][4]法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。

1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。

1947年美国数学家G.B.丹奇克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。

1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。

1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。

50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。

例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。

运筹学判断题一、第1章 线性规划的基本理论及其应用 1、线性规划问题的可行解集不一定是凸集。

（×） 2、若线性规划无最优解则其可行域无界。

（×）3、线性规划具有惟一的最优解是指最优表中非基变量检验数全部非零。

（√）4、线性规划问题的每一个基本可行解对应可行域的一个顶点。

（√）5、若线性规划模型的可行域非空有界，则其顶点中必存在最优解。

（√）6、线性规划问题的大M 法中，M 是负无穷大。

（×）7、单纯形法计算中，若不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量为负。

（√）8、对于线性规划问题的基本可行解，若大于零的基变量数小于约束条件数，则解是退化的。

（√）。

9、一旦一个人工变量在迭代过程中变为非基变量后，则该变量及相应列的数字可以从单纯性表中删除，且这样做不影响计算结果。

（√）10、线性规划的目标函数中系数最大的变量在最优解中总是取正值。

（×）11、对一个有n 个变量，m 个约束的标准型的线性规划问题，其可行域的顶点恰好为个m n C 。

（×）12、线性规划解的退化问题就是表明有多个最优解。

（×）13、如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。

（√） 14、单纯型法解线性规划问题时值为0的变量未必是非基变量。

（√） 15、任何线性规划问题度存在并具有唯一的对偶问题。

（√） 16、对偶问题的对偶问题一定是原问题。

（√）17、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题为无界解。

（×）18、若原问题有可行解，则其对偶问题也一定有可行解。

（×） 19、若原问题无可行解，其对偶问题也一定无可行解。

（×） 20、若原问题有最优解，其对偶问题也一定有最优解。

（√） 21、已知*i y 为线性规划的对偶问题的最优解，若*0i y >，说明在最优生产计划中，第i 种资源一定有剩余。

第四章 线性规划本章主要内容：线性规划的基本理论 线性规划的单纯形法 线性规划的对偶理论 线性规划的对偶单纯形法教学目的及要求：理解线性规划的基本理论；掌握线性规划的单纯形法；理解线性规划的对偶理论；掌握线性规划的对偶单纯形法。

教学重点：线性规划的单纯形法． 教学难点：线性规划的对偶单纯形法． 教学方法：启发式．教学手段：多媒体演示、演讲与板书相结合． 教学时间：6学时． 教学内容：§4.1 线性规划的基本理论考虑线性规划问题11min ;,1,2,,,0,1,2,,.nj j j n ij j i j j c x a x b i m x j n ==⎧⎪⎪⎪==⎨⎪⎪≥=⎪⎩∑∑s.t. (LP)或min ;,0.T c x Ax b x ⎧⎪=⎨⎪≥⎩s.t. 其中 121212(,,,),(,,,),(,,,),(),T T T n n m ij m n x x x x c c c c b b b b A a ⨯====A 称为约束矩阵，Ax b =称为约束方程组，0x ≥称为非负约束．假定：rank()A m =．定义 在（LP ）中，满足约束方程组及非负约束的向量x 称为可行解或可行点；所有可行解的全体称为可行解集或可行域，记作K ，即{,0}K Ax b x ==≥．使目标函数在K 上取到最小值的可行解称为最优解；最优解对应的目标函数值称为最优值．定义 在（LP ）中，约束矩阵A 的任意一个m 阶满秩子方阵B 称为基，B 中m 个线性无关的列向量称为基向量，x 中与B 的列对应的分量称为关于B 的基变量，其余的变量称为关于B 的非基变量．任取（LP ）的一个基12(,,,)m j j j B p p p =，记12(,,,)m T B j j j x x x x =，若令关于B 的非基变量都取0，则约束方程Ax b =变为B Bx b =．由于B 是满秩方阵，因此B Bx b =有唯一解1B x B b -=．记121(,,,)m T j j j B b x x x -=，则由12,1,2,,,0,{1,2,,}{,,,}k k j j j m x x k m x j n j j j ===∀∈-所构成的n 维向量x 是Ax b =的一个解，称之为（LP ）的关于B 的基本解．基本解满足约束方程组，但不一定满足非负约束，所以不一定是可行解．若10B b -≥，即基本解x 也是可行解，则称x 为（LP ）的关于基B 的基本可行解，相应的基B 称为（LP ）的可行基；当10B b ->时，称此基本可行解x 是非退化的，否则，称之为退化的．若一个（LP ）的所有基本可行解都是非退化的，则称该（LP ）是非退化的，否则，称它是退化的．例1 求下列线性规划问题的所有基本可行解．12123124min 44;4,2,0,1,2,3,4.j x x x x x x x x x j -⎧⎪-+=⎪⎨-++=⎪⎪≥=⎩s.t. 解 约束矩阵的4个列向量依次为12341110,,,1101p p p p -⎛⎫⎛⎫⎛⎫⎛⎫==== ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭⎝⎭．全部基为113214323424534(,),(,),(,),(,),(,),B p p B p p B p p B p p B p p =====对于1B ，1x 和3x 为基变量，2x 和4x 为非基变量．令2x =4x =0，有1314,2,x x x +=⎧⎨-=⎩ 得到关于1B 的基本解(1)(2,0,6,0)T x =-，它不是可行解．对于2B ，1x 和4x 为基变量，2x 和3x 为非基变量．令2x =3x =0，有1144,2,x x x =⎧⎨-+=⎩ 得到关于2B 的基本解(2)(4,0,0,6)T x =，它是一个非退化的基本可行解．同理，可求得关于345,,B B B 的基本解分别为(3)(4)(5)(0,2,6,0),(0,4,0,6),(0,0,4,2)T T T x x x ==-=，显然，(3)x 和(5)x 均是非退化的基本可行解，而(4)x 不是可行解．因此，该问题的所有基本可行解为(2)(3)(5),,x x x ．此外，因为这些基本可行解都是非退化的，所以该问题是非退化的．定理1 设x 为（LP ）的可行解，则x 为（LP ）的基本可行解的充要条件是它的非零分量所对应的列向量线性无关．证明 不妨设x 的前r 个分量为正分量，即12(,,,,0,,0),0(1,2,,).T r j x x x x x j r =>=若x 是基本可行解，则取正值的变量12,,,r x x x 必定是基变量，而这些基变量对应的列向量12,,,r p p p 是基向量．故必定线性相关．反之，若12,,,r p p p 线性无关，则必有0r m ≤≤．当r m =时，12(,,,)r B p p p =就是一个基；当r m <时，一定可以从约束矩阵A 的后n r -个列向量中选出m r -个，不妨设为12,,,r r m p p p ++，使121(,,,,,,)r r m B p p p p p +=成为一个基．由于x 是可行解，因此1rj j j x p b ==∑，从而必有1mj j j x p b ==∑．由此可知x 是关于B 的基本可行解．定理2 x 是（LP ）的基本可行解的充要条件是x 为（LP ）的可行域的极点． 证明 由定理4.1.1和定理2.2.2知结论成立． 例2 求下列线性规划问题的可行域的极点．1212314min ;22,2,0,1,2,3,4.j x x x x x x x x j -⎧⎪++=⎪⎨+=⎪⎪≥=⎩s.t. 解 因为约束矩阵的4个列向量依次为12341210,,,1001p p p p ⎛⎫⎛⎫⎛⎫⎛⎫==== ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭．全部基为112213314424534(,),(,),(,),(,),(,),B p p B p p B p p B p p B p p =====求得关于基12345,,,,B B B B B 的基本解分别为(1)(2)(3)(4)(5)(2,0,0,0),(2,0,0,0),(2,0,0,0),(0,1,0,2),(0,0,2,2)T T T T Tx x x x x =====显然，(1)(2)(3),,x x x 均为退化的基本可行解，(4)(5),x x 是非退化的基本可行解．可行域有三个极点：(2,0,0,0)T ，(0,1,0,2)T ，(0,0,2,2)T ．定理3 若（LP ）有可行解，则它必有基本可行解． 证明 由定理2.2.1及定理4.1.2知结论成立．定理4 若（LP ）的可行域K 非空有界，则（LP ）必存在最优解，且其中至少有一个基本可行解为最优解．证明 根据推论2.2.6，（LP ）的任一可行解x 都可表示为（LP ）的全部基本可行解12,,,k x x x 的凸组合，即1,ki i i x x x K λ==∀∈∑，其中10(1,2,,),1ki i i i k λλ=≥==∑．设s x 是使（LP ）中目标函数值达到最小的基本可行解，即 1min T T s i i kc x c x ≤≤=，则11,kkTTT T i i i s s i i c x c x c x c x x K λλ===≥=∀∈∑∑．这表明，基本可行解s x 为（LP ）的最优解．定理5 设（LP ）的可行域K 无界，则（LP ）存在最优解的充要条件是对K 的任一极方向d ，均有0T c d ≥．证明 根据定理2.2.10，（LP ）的任一可行解x 都可写成11kli i j j i j x x d λμ===+∑∑，其中12,,,k x x x 为（LP ）的全部基本可行解，12,,,l d d d 为K 的全部极方向，且10(1,2,,),1,0(1,2,,)ki i j i i k j l λλμ=≥==≥=∑．于是，（LP ）等价于下面以0(1,2,,)0(1,2,,)i j i k j l λμ≥=≥=和为决策变量的线性规划问题111min ()();1,0,1,2,,,0,1,2,,.k lT T i i j j i j k i i i j c x c d i k j l λμλλμ===⎧+⎪⎪⎪⎪=⎨⎪⎪≥=⎪≥=⎪⎩∑∑∑s.t. 由于j μ可以任意大，因此若存在某个j d ，使0T j c d <，则上述问题的目标函数无下界，从而不存在最优解，从而（LP ）不存在最优解．若1,2,,j l ∀=，均有0T j c d ≥，设1min T T s i i kc x c x ≤≤=，则11()(),k lTTT T i i j j s i j c x c x c d c x x K λμ===+≥∀∈∑∑．所以基本可行解s x 是（LP ）的最优解．推论6 若（LP ）的可行域K 无界，且（LP ）存在最优解，则至少存在一个基本可行解为最优解．证明 由定理4.1.5的证明过程可知结论成立． 定理7 设在（LP ）的全部基本可行解12,,,k x x x 中，使目标函数值最小者为12,,,s i i i x x x ；在K 的全部极方向12,,,l d d d 中，满足0T j c d =者为12,,,t j j j d d d ．若（LP ）存在最优解，则x 为（LP ）的最优解的充要条件是存在10(1,2,,),1,0(1,2,,)pp q si i j p p s q t λλμ=≥==≥=∑使11p p q q sti i j j p q x x d λμ===+∑∑． （*）证明 因为（LP ）存在最优解，所以由定理4.1.4和推论4.1.6及其证明知，基本可行解12,,,s i i i x x x 是（LP ）的最优解．设x 具有（*）式的形式，则由推论2.2.6和定理2.2.10知，x 为（LP ）的可行解，从而由（*）式知，111p p q q stTTT T i i j j i p q c x c x c d c x λμ===+=∑∑因此，x 为（LP ）的最优解．反之，设x 为（LP ）的任一最优解，则x 为可行解，于是由推论2.2.6和定理2.2.10知，存在 10(1,2,,),1,0(1,2,,)ki i j i i k j l λλμ=≥==≥=∑，使 11kli i j j i j x x d λμ===+∑∑． （**）根据定理1.1.5，有 0,1,2,,T j c d j l ≥=， 且由1i x 为最优解知1,1,2,,T T i i c x c x i k ≥=．从而由上述两式容易用反证法证明：若（**）式中某个0i λ>，则i x 必为（LP ）的最优解；若（**）式中某个0j μ>，则必有0T j c d =。