ch线性规划与单纯形法

1、第一章 线性规划与单纯形法1在生产管理和经营活动中经常提出以下两类问题：1.如何利用有限的人力、物力、财力等资源安排生产，使产值最大或利润最高。2.对给定的任务，如何统筹安排，以便用最少的人力、物力、财力等资源消耗去完成任务。2对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究，构成了运筹学的一个重要分支数学规划论。 3 第一节 线性规划问题及其数学模型 第二节 线性规划问题的图解法 第三节 线性规划问题的标准型 第四节 线性规划问题的解 第五节 线性规划问题的几何意义 第六节 单纯形法的基本原理 第七节 单纯形法的应用 第八节 线性规划在管理方面的应用 第九节 数据包络

2、分析4第一节 线性规划问题及其数学模型 一、问题的提出 例1 某工厂在计划内要生产I、II两种产品，已知生产单位产品所需的设备台时数、原材料A的消耗量、原材料B的消耗量，具体数据如表所示。设 备原材料A原材料BI140II2048台时16kg12kg5又知道，每生产一件产品 I 可获利2元，每生产一件产品 II 可获得3元，问应如何安排生产计划才能够使得工厂获利最多？解：生产计划就是要确定生产产品 I 和 II 各多少件。故问题的决策变量为需要生产产品I的数量、生产产品II的数量。设需要生产产品I的数量：x1设需要生产产品II的数量：x26对生产计划（即产品 I 和 II 的生产数量）造成影响

3、的制约因素有三个，分别为：（1）设备台时数限制： x1 + 2x2 8（2）原材料A的数量限制：4x1 16（3）原材料B的数量限制： 4x2 12问题的目标是使得创造的利润达到最大，用 z 表示所创造的利润值，则可表示为：max z = 2x1 + 3x2 7综上所述，建立问题的数学模型为：目标函数： max z = 2x1 + 3x2约束条件：目标为变量的线性函数变量的线性等式或不等式8 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定

4、条件限制下，求使目标函数 z 达到最大的x1 ,x2 的取值。9例2 河流旁建有两个化工厂，两条河流的流量分别为500万立方米/天、200万立方米/天。500 万立方米 / 天200 万立方米 / 天 工厂 I 工厂 II工厂 I 排污：2 万立方米/天。工厂 II 排污：1.4万立方米/天。10根据环保要求，河流中污水含量不应大于0.2%。为了达到环保要求，需要进行污水处理。处理方式有两种：（1）河流自然净化：工厂1排出的污水流到工厂2时，20%得到自然净化。（2）工厂自己进行污水处理： 工厂I 污水处理成本：1000 元/万立方米 工厂II 污水处理成本：800 元/万立方米问如何制定污水

5、处理计划才能使工厂总污水处理成本最小。11解：污水处理计划就是要确定工厂 I 和工厂 II 各处理污水多少。故问题的决策变量为工厂 I 处理的污水、工厂 II 处理的污水。设工厂I 需处理的污水：x1 万立方米设工厂II 需处理的污水：x2 万立方米12对污水处理计划（即工厂I和II的污水处理量）造成影响的制约因素有四个，分别为：（1）工厂I 污水处理量的上限：x1 2（2）工厂II 污水处理量的上限：x2 1.4（3）工厂I和II之间河流污水含量的0.2%限制：（2-x1 ）/ 500 0.002x1 1 13问题的目标是使得污水处理成本最小，用 z 表示污水处理成本，则可表示为：min z

6、 = 1000 x1 + 800 x2 （4）工厂II之后河流污水含量的0.2%限制：0.8（2-x1）+（1.4 - x2） / 700 0.0020.8x1 + x2 1.6 14综上所述，建立问题的数学模型为：目标函数： min z = 1000 x1 + 800 x2约束条件：15二、线性规划问题的特征 从以上两个例子可以看出，它们都属于一类优化问题，它们的共同特征为： 每个问题都用一组决策变量（x1,x2,xn）表示某一方案。这组决策变量的值代表一个具体方案，这些变量一般取值都是非负的。16存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。都有一个要求表达的目标，

7、它可用决策变量的线性函数来表示（称为目标函数），按问题的不同，要求目标函数实现最大化或最小化。 17三、线性规划问题的数学模型 满足以上三个条件的数学模型称为线性规划的数学模型： 目标函数 max(min) z=c1x1 + c2x2 + cnxn约束条件 a11x1 + a12x2 + a1nxn (=,) b1 a21x1 + a22x2 + a2nxn (=,) b2 am1x1 + am2x2 + amnxn (=,) bm x1, x2, , xn 018四、线性规划问题数学模型的特点 1. 决策变量正负不限。2. 约束条件可以为=，即约束条件为决策变量的线性等式或不等式。3. 每一

8、约束条件右端的常数可为正、负。4. 目标函数可以要求极大，也可以极小。5. 目标函数为决策变量的线性函数。 19第二节 线性规划问题的图解法 一、图解法的步骤 对于两个或三个变量的线性规划问题可以用图解法来求解。 在直角坐标系中画出由所有约束条件不等式所组成的公共取值范围。20该公共取值范围中的每一点都满足所有约束条件，称为线性规划的可行域。可行域边界上改变方向的点称为可行域的顶点。可行域中的每一点都满足所有约束条件，称可行域中的每一点为线性规划的可行解。可行域中使目标函数极大或极小的那个可行解称为最优解。最优解必然在可行域的顶点上取得。 定 义21如目标函数为最大化：则把目标函数在直角坐标系

9、中所代表的直线沿法线方向向右上方或左上方平移，直到同图中可行域（公共取值范围）的边界点相交为止，停止平移；22如目标函数为最小化：则把目标函数在直角坐标系中所代表的直线沿法线方向向右下方或左下方，直到同图中可行域（公共取值范围）的边界点相交为止，停止平移。 定义：位于同一条目标函数所代表的直线上的点具有相同的目标函数值，因而称它为“等值线”。23求出目标函数直线同可行域相交的边界点坐标值。该边界值即为问题的最优解，并代入目标函数，求出问题的最优解。 24例：目标函数： max z = 2x1 + 3x2约束条件：25解：（1）绘制公共取值范围： x1 + 2x2 8：直线 x1+ 2x2 =

10、8 的左下方 4x1 16：直线 4x1 = 16 的左方 4x2 12：直线 4x2 = 12 的下方 x10、x20：第1象限x1x24x2 =12x1 + 2x2=84x1 =1626（2）绘制等值线、并向右上方平移。x1x24x2 =12x1 + 2x2=84x1 =162x1 + 3x2=zQ27（3）求出交点坐标 Q（4,2）。（4）最优解为：x1=4，x2=2。 最优值为：z = 1428确定约束条件围成的区域；求出该区域边界点，列表求出目标函数的最优值。 二、图解法的改进步骤 依据线性规划问题的最优解在其可行域的顶点上取得。29x1x24x2 =12x1 + 2x2=84x1

11、=162x1 + 3x2=z0Q1Q2Q3Q4解：0=(0,0) ；Q1=(4,0)； Q2=(4,2)； Q3=(2,3)；Q4=(0,3)边界点坐标0=(0,0)Q1=(4,0)Q2*=(4,2)Q3=(2,3)Q4=(0,3)目标函数值z0814*13930三、求解结果分析 最优解是唯一的。无穷多最优解：目标函数直线同某一约束条件直线平行。无界解：可行域无界。无可行解：无可行域。 31最优解是唯一的。目标函数： max z = 2x1 + 3x2约束条件：32目标函数： max z = 2x1 + 4x2约束条件：无穷多最优解：目标函数直线同某一约束条件直线平行。33x1x24x2 =1

12、2x1 + 2x2=84x1 =162x1 + 4x2=zQ3Q2位于线段 Q2Q3 上任意一点都使目标函数 z 取得相同的最大值。分析：目标函数直线和约束条件x1+2x28的边界线平行。34目标函数： max z = 2x1 + 3x2约束条件：无界解：可行域无界。35x1x24x2 =124x1 =16x1 + 2x2=8可行域无界，故最优解无界。注：可行域无界，可能无最优解，也可能存在最优解，但此时最优解一定在顶点上取得。36无可行解：无可行域。 目标函数： max z = 2x1 + 3x2约束条件：37x1x24x2 =12x1 + 2x2164x1 =16(4,3)无可行域，所以无

13、可行解。38分 析：当求解结果出现3、4两种情况时，一般说明线性规划问题的数学模型有错误。情况 3 可能是因为建模时缺少了某些必要的约束条件。情况 4 可能是因为建模时出现了矛盾的约束条件。图解法虽然直观、简便，但当变量数多于 3 个以上时，它就无能为力了。需要借助于后面章节所介绍的一种代数法单纯形法。 39第三节 线性规划问题的标准型 鉴于线性规划问题模型形式的多样性，为了便于求解和讨论，对于一般线性规划问题总是先将它化为标准形式的线性规划问题，然后再予以分析或求解。 40一、线性规划问题的标准型 具有 m 个约束条件和 n 个决策变量的线性规划问题的标准型定义为： max z=c1x1 +

14、 c2x2 + cnxns.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm其中：x1, x2, , xn 0，b1,b2,bm0形式一（完整形式）41形式二（简化形式）42形式三（向量形式）Max z = CXs.t. AX=b X0其中：C = (c1,cn) A = ( aij )m n,，i =1, m，j =1, n X= (x1, xn) T b= (b1, bm) T43目标函数为极大化。所有约束条件为等式。所有决策变量限于非负值。每一约束条件右端的常数为非负值。

15、实际碰到的各种线性规划问题的数学模型都应变换为标准型后才求解。 二、线性规划问题标准型的四大特点 44三、线性规划问题的非标准型转化为标准型 1、目标函数为极小化：将目标函数乘以 -1 即可化为等价的极大化问题。 Min z = c x Max z = -c x 45min z = - 2x1 - 3x2max z = 2x1+ 3x2解：线性规划模型的标准型为：462、约束条件为不等式：（1）约束条件为：在不等式左端加上一个非负的新变量即可化为等式。新增的非负变量称为松弛变量。（2）约束条件为：在不等式左端减去一个非负的新变量即可化为等式。新增的非负变量称为剩余变量。 47max z = 2

16、x1 + 3x2max z = 2x1+ 3x2解：引入松弛变量 x3和 x4，剩余变量 x5。从而线性规划模型的标准型为：483、决策变量不是非负值：（1）决策变量有非正约束：用一新变量（该变量为决策变量的相反数）来代替。xj 0引入新变量 xj 0 ，令 xj = -xj； 将 xj 表达式代入线性规划模型，用 xj 替代 xj 。49max z = 2x1 + 3x2max z = 2x1 - 3x2解：引入新变量 x2 0，令 x2 = -x2 。从而线性规划模型的标准型为：50（2）决策变量符号不受限制（为自由变量）：用两个非负新变量来代替。xj 正负不限引入新变量 xj 0 和 x

17、j 0 ，令 xj = xj- xj ； 将 xj 表达式代入线性规划模型，用 xj 、 xj替代 xj 。51max z = 2x1 + 3x2max z = 2x1 + 3x2 3x2”解：引入新变量 x2 0， x2” 0 ，令 x2 = x2 x2”。从而线性规划模型的标准型为：52（3）决策变量有上、下界：引进新变量使其等于原变量减去下限值，并用新变量替换模型中原变量；将新变量的上限约束转化为新的约束条件，并化为等式。a xj b引入新变量xj，令 xj= xj -a，0 xj b-a；将 xj 表达式（xj = xj+ a）代入线性规划模型，用 xj 替换 xj ；将 xj b-a

18、 转为约束，再化为等式。 53max z = 2x1 + 3x2解：引入新变量 x2 ，令 x2 =x2 2， x2 2将 x2 = x2 + 2代入模型，用 x2 替代 x2 ：将 x2 2 转化为约束54max z = 2x1 3 ( x2 + 2 )55max z = 2x1 3 x2 + 956max z = 2x1 3 x2 + 9574、约束条件右端的常数为负：约束两端乘以 -1。 max z = 2x1 + 3x2解：将第三个约束两端分别乘以 - 1。从而线性规划模型的标准型为：max z = 2x1 + 3x258第四节 线性规划问题的解 在讨论线性规划问题的求解之前，先要了解

19、线性规划问题的解的概念。 （1）（2）（3）59一、基本定义 可行解满足约束条件（2）和（3）的解X=( x1 , xn) T 称为线性规划问题的可行解。可行域所有可行解的集合称为可行域。最优解使目标函数（1）达到最优（最大化问题是使目标函数值最大，最小化问题是使目标函数最小）的可行解称为最优解。 60二、约束方程组系数矩阵 A 的讨论 Max z = C Xs.t. A X = b X 0其中：C = (c1,cn) A = ( aij )m n,，i =1, m，j =1, n X= (x1, xn) T b= (b1, bm) T611. 几个概念 （1）向量 由数 a1, a2, ,

20、an 组成的有序数组，称为 n 维向量。 a = ( a1, a2, , an ) n 维行向量 n 维列向量62 （2）矩阵的列向量 (m, n) 矩阵 A 的每一列由竖直排列的 m 个变量组成，把它叫做矩阵 A 的一个列向量。 63（3）线性相关 给定向量组 A =(P1, P2, , Pn)则称向量组 A 是线性相关的。使 k1P1+ k2P2 + + knPn =0如果存在 n 个不全为零的数 k1, k2, , kn64（4）线性无关 给定向量组 A =(P1, P2, , Pn)则称向量组 A 是线性无关的。使 k1P1+ k2P2 + + knPn =0如果不存在 n 个不全为零

21、的数 k1, k2, , kn65 设向量 (, P1, P2, , Pn) 则称可由向量 (P1, P2, , Pn) 线性表示。如果存在 一组数 k1, k2, , kn使 =k1P1+ k2P2 + + knPn （5）向量的线性表示66定 理： 设向量组 (P1, P2, , Pn) 线性无关 设向量组 (, P1, P2, , Pn) 线性相关 则可由 (P1, P2, , Pn) 线性表示且表达式唯一。67（6）矩阵的秩从 (m, n) 矩阵 A 中选取 r 个行 r 个列，这 r 个行 r 个列相关处的元素构成一个 r 阶方阵，它的行列式叫做A 的 r 阶子式。当 A 的各 r

22、阶子式中至少有一个不为 0，而 r + 1 阶子式全为0，就说矩阵 A 的秩为 r ，记为 r(A)。显然 r(A) min m, n。 68（7）矩阵秩和向量线性无关若矩阵 A 的秩等于 r ，则在列向量（或行向量）中必然有 r 个列向量（或行向量）构成线性无关组，而任意 r+1 个列向量（或行向量）都是线性相关的。r(A) = A 中最大线性无关列数 = A 中最大线性无关行数692. 约束条件方程组系数矩阵 A 的讨论70约定：(1) m n，即约束条件数少于决策变量数。(2) r(A) = m，约束条件系数矩阵的秩等于约束方程数。71下面来论证上述两条约定：(1) m n，即约束条件数

23、少于决策变量数。(2) r(A) = m，约束条件系数矩阵的秩等于约束方程数。72m n 的论证如果m n，约束条件变为了由 m 个相互独立的方程组成的线性方程组，从而可直接求出。故在线性规划问题模型中，约定 m n 。73r(A)= m 的论证因为r(A) minm, n = m，所以存在两种情况： r(A) m r(A) = m 74下面来论证 r(A) m 是不正确的。若 r(A) m，则线性无关的约束条件只有 r(A) 个，其余的 m - r(A) 个约束必然可以由这 r(A) 个线性无关的约束线性表示，所以这 m - r(A)个约束方程为多余的，它们根本起不到约束作用，不应当作为问题

24、的约束条件而存在于模型中，故应将其删去。75综上所述，对于线性规划问题，均约定：约束条件数 决策变量数（ m n ）所有约束条件之间必须线性无关，即约束条件系数矩阵的秩 = 约束条件数（ r ( A ) = m ）76三、引申定义 设 ( A )m n 是线性规划问题的约束条件系数矩阵，r(A) = m。将 A 表示成列向量的形式，即 A = (P1, P2, ,Pn)，则约束方程可写成： 77又因为 r(A) = m，故 ( P1,P2, Pn) 中有 m 个列向量线性无关，设 B=(P1,P2,Pm) 为 A 中 m 个线性无关的列向量。 1、基由 ( P1, P2, Pm) 此 m 个线

25、性无关的列向量所构成的矩阵称为线性规划问题的一个基。 基的个数最多为 Cnm 个78例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x3, x4 0、 解：系统矩阵中存在的基有：不构成基79基变量 基( P1,P2,Pm) 所对应的 m 个变量 (x1, x2, xm ) 称为基变量。3. 非基变量 其余 n-m 个变量称为非基变量。80例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1

26、, x2, x3, x4 0解：x1 和 x2x3 和 x4选择基基变量非基变量81x1 和 x3x2 和 x4选择基基变量非基变量x3 和 x4x1 和 x2不构成基不是基变量不是非基变量82由此可知基变量所对应的系数列向量必须线性无关834. 基解 令 (n-m) 个非基变量等于0，并对余下的 m 个基变量求解，所得的解称为基解。 基解中非零分量的数目 m 基解的个数最多为 Cnm 个84例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x3, x4 0、 解：基变量：x1 和 x

27、2非基变量：x3 和 x4令 x3= x4=0（非基变量），求得： x =（ 19/8，7/8，0，0）为基解。 85基变量：x1 和 x3非基变量：x2 和 x4令 x2= x4=0（非基变量），求得： x =（ -2，0，7，0）为基解，但不是一个可行解。 86令 x3= x4=1（非基变量），求得： x =（ 23/16，11/16，1，1）不为基解，但它是一个可行解。 基变量：x1 和 x2非基变量：x3 和 x487令 x3=-1， x4=0（非基变量），求得： x =（ 3，1，-1，0）不为基解，它也不是一个可行解。 基变量：x1 和 x2非基变量：x3 和 x4885. 基可行

28、解 若基解满足非负约束，称其为基可行解。6. 可行基 对应于基可行解的基。89例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x3, x4 0、 解：选择 x1 和 x2 为基变量令 x3= x4=0（非基变量），求得： x =（ 19/8，7/8，0，0）为基解，同时也是可行解，所以是基可行解。 可行基 90选择 x1 和 x3为基变量令 x2= x4=0（非基变量），求得： x =（ -2，0，7，0）为基解，但不是可行解，所以不是基可行解。 不是可行基 917. 退化解 若基可

29、行解中有基变量等于0，则该基可行解称为退化解。 92例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 16/3 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x3, x4 0、 基变量：x1 和 x2非基变量：x3 和 x4令 x3= x4=0（非基变量），求得： x =( 8/3，0，0，0 ) 为基可行解，同时也是一个退化解。 解：93可行解非可行解基解基解中的可行解基解中的不可行解（基可行解）94不可行解可行解95不可行解可行解基解96不可行解可行解基解中的不可行解基可行解97第五节 线性规划问题的几何意义 一、基本概念 凸集 设

30、 K 是 n 维欧氏空间的一个点集，若存在任意两点 X(1)K，X(2)K 的连线上的一切点：则称 K 为凸集。98注：X(1)X(2)X1 -99实心圆、实心球体、实心立方体等都是凸集。凸集没有凹入部分，其内部没有空间。两个凸集的交集是凸集。100凸组合 设 X(1)，X(2)，X(k) 是 n 维欧氏空间 En 中的 k 个点，若存在 u1，u2，uk ，且 0 ui 1 ，i = 1, 2, , k ； ，使 X = u1 X(1)+ u2 X(2)+ uk X(k)则称 X 为 X(1)，X(2)，X(k) 的凸组合。 101顶点 设 K 是凸集，XK；若 X 不能用不同的两点 X(1

31、)K 和 X(2)K 的凸组合表示为： X=uX(1)+ (1-u) X(2)（0u1） 则称 X 为 K 的一个顶点（或极点）。102凸集 K 中满足下述条件的点 X 称为顶点：如果 K 中不存在任何两个不同点 X(1)、X(2)，使 X 成为这两个连线上的一个点。 103二、基本定理 定理 1若线性规划问题存在可行域，则可行域是凸集证明：可行域 K 内存在两个不同的点 X(1) 和 X(2) ：104则：105点 X(1) 和 X(2) 连线上的点 X 可表述为：针对 X 中的每一份量，有：下面来证明 X K ，也即证明：106证 毕。107引 理线性规划问题的可行解 X = ( x1 ,

32、 x2 , , xn ) T 为基可行解的充要条件是 X 的正分量所对应的系数列向量线性无关。可行解 X = ( x1 , x2 , , xn ) T 为基可行解可行解 X = ( x1 , x2 , , xn ) T 的正分量所对应的系数列向量线性无关。108证：（1）必要性可行解 X = ( x1 , x2 , , xn ) T 为基可行解X = ( x1 , x2 , , xn ) T 中正分量的系数列向量线性无关。 （基解 令 (n-m) 个非基变量等于0，并对余下的 m 个基变量求解，所得的解称为基解。 基变量所对应的系数列向量是线性无关的。） 由基可行解定义可知，必要性成立。109

33、（2）充分性可行解 X = ( x1 , x2 , , xn ) T 为基可行解可行解 X = ( x1 , x2 , , xn ) T 中正分量的系数列向量线性无关。110因为 X = ( x1 , x2 , , xn ) T 为可行解，所以 ( x1 , x2 , , xn ) 中只有正分量和零分量。设可行解 X = ( x1 , x2 , , xn ) T 中正分量数为 k , 则 X 可表述成：X = ( x1 , x2 , , xk , 0 , , 0 ) T111（注：m 个约束条件和 n 个决策变量组成的线性规划问题的约束条件系数矩阵的秩为 m ，最大线性无关列向量数为m，多于

34、m 个列向量必然线性相关。）因为 X = ( x1 , x2 , , xk ,0 , , 0 ) T 中正分量所对应的系数列向量线性无关，所以 k m 。112k = m ：由定义可知， X = ( x1 , x2 , , xm , 0 , , 0 ) T 为基可行解 。X = ( x1 , x2 , , xm ,0 , ,0 ) T113k 0，且较大）：由此可知，存在两个可行解： - （ 0，且较大）：120X (1)、X (2) 和 X 之间存在如下关系：由顶点定义：X 不是可行域 K 的顶点。121（2）若可行解 X 不是可行域 K 的顶点，则它一定不是基可行解。 证：因为 X 为可行

35、解，则 X 中只有正分量和 0 分量。 X = ( x1 , x2 , , xk , 0 , ,0 ) T设可行解 X = ( x1 , x2 , , xn ) T 中正分量数为 k , 则 X 可表述成：122因为可行解 X 不是可行域 K 的顶点，则在 K 内可以找到两个不同点 X (1) 和 X (2) ，使 X 位于其连线上（由顶点定义可知）。 123124125 - ：因为 X (1) X (2)不全为 0所以所以 ( P1 , P2 , , Pk ) 线性相关。进而由引理可知，X 不是基可行解。126引 理若 K 是有界凸集，则任何一点 X K 可表示为 K 的顶点的凸组合。 X(

36、1)X(2)X(3)XX 127证： 将 带入 ：128129定理 3若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。 证：设 X ( 0 ) 不是顶点，且目标函数在 X ( 0 )处达到最优 z = C X (0) 由引理可知：X ( 0 ) 可由可行域的顶点的凸组合表示：130131因为目标函数在 X ( 0 )处达到最优，故从而目标函数在 X ( m )处也达到最优，而 X(m) 正是可行域的一个顶点。132命题目标函数可能在多个顶点处达到最大值，这时在这些顶点的凸组合上也达到最大值，称这种线性规划问题有无限多个最优解。 证：设 X ( 1 )， X ( 2 )，

37、 X ( k )是目标函数达到最优值的顶点。133134若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到，根据以上讨论，可以得到以下结论： 线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点。若线性规划问题有最优解，必在某顶点上得到。可行域的顶点数目是有限的，最多不大于Cnm个。135基本可行解最多不大于 Cmn 个，若采用“枚举法”找所有基本可行解，然后一一比较，最终可能找到最优解。但当 n 和 m 的数较大时，这种办法就行不通的，所以要继续讨论，如何有效地找到最优解的方法，这里介绍的是单纯形法。

38、 136结论： 因此，求解线性规划标准型最优解，我们只需找到可行基（极点），然后在极点范围内求解最优解就可以了，无需考虑其它！单纯形法就是基于这种思路求解的！切记之！137 利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法（ 1947年美国数学家G.B.Dantzig提出）的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。单 纯 形 法138 由上面的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可

39、行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示（求检验数过程） 。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加（基变换过程），而其他非基变量的值都保持0不变。139初始基本可行解是否最优解或无限最优解?结束沿边界找新的基本可行解NY单纯形法的基本过程 核心是：变量迭代找一个初始可行基单位矩阵或由单位矩阵各列向量组成140考虑标准形式的线性规划问题：Max z = c1x1 + c2x2 + + cnxn s.t. a11 x1 + a12 x2 + + a1n xn

40、= b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . am1 x1 + am2 x2 + + amn xn = bm x1 , x2 , , xn 0 x1 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx= . CT= . b= . A= . . . . . . . . xn cn bm am1 am2.amn 141这里，矩阵A表示为：A = ( p1 ，p2 ，pn ) ，其中 pj = ( a1j ，a2j ，amj )T Rm。若找到一个可行基，无妨设B = ( p1 ，p2 ，pm ) ，则m个基变量为 x1 , x2

41、, , xm，n-m个非基变量为 xm+1 ，xm+2 ，xn 。通过运算，所有的基变量都可以用非基变量来表示：142 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）( 2-11 ) . . . xm=bm-（amm+1xm+1+amm+2xm+2+amnxn） 把它们代入目标函数，得 z = z+m+1xm+1+m+2xm+2+nxn ( 2-12 )其中 j=cj - c1a1j + c2a2j + + cm amj） 我们把基变量由非基变量线性表示的（LP）称为与基B相应的典式。通常把目标函数中非基变

42、量前面的系数j叫“检验数”。143单纯形法的基本步骤可描述如下：（1）寻找一个初始的可行基和相应基本可行解（极点），确定基变量、非基变量以及基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示； 144 （2）在用非基变量表示的目标函数表达 z = z+m+1xm+1+m+2xm+2+nxn中，我们称非基变量xj的系数为检验数记为 j 。若 j 0，那么相应的非基变量xj的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有 j 非正（小于等于0），则当前的基本可

43、行解就是最优解，计算结束；这是最优性判别定理！145 注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的（即检验数最大的）先换入等。146（3）在用非基变量表示的基变量的表达式 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn） xm=bm-（amm+1xm+1+amm+2xm+2+amnxn）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr ，满足，=minbi /aij aij 0 = br /arj这个基变量xr称为“出基变量”。（最小比值原

44、则）当进基变量的值增加到 时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（极点），转（4）。147如果进基变量的值增加时，所有基变量的值都不减少，即所有aij 非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；（4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。148例：用单纯形法的基本思路解如下的线性规划问题（用代数方法求解LP） Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 =

45、65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0149第一次迭代：（1）取初始可行基B10= (p3 , p4 , p5)，那么x3 ，x4 ，x5为基变量，x1 ，x2为非基变量。将基变量和目标函数用非基变量线性的表示： z=1500 x1+2500 x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=65，x4=40，x5= 75，z = 0，得到当前的基本可行解：x=(0,0,65,40,

46、75)T，z = 0 。这个解对应于平面图2-7的D、E交点。（投影）150151 （2）选择进基变量。在目标函数z = 1500 x1 + 2500 x2中，非基变量x1，x2的系数都是正数，因此 x1 ，x2进基都可以使目标函数z增大，但x2的系数为2500，绝对值比x1的系数1500大，因此把x2作为进基变量可以使目标函数z增加更快。选择x2为进基变量，使x2的值从0开始增加，另一个非基变量x1保持零值不变。152 （3）确定出基变量。在约束条件 x3 = 65 (3 x1 +2 x2 ) x4 = 40 (2 x1 + x2 ) x5 = 75 (0 x1 +3 x2 )中，由于进基变

47、量x2在3个约束条件中的系数都是正数，当x2的值从0开始增加时，基变量x3 、x4 、x5的值分别从当前的值65、40和75开始减少，当x2增加到25时，x5首先下降为0成为非基变量（应用最小比值原则确定）。这时，新的基变量为x3 、x4 、x2 ，新的非基变量为x1 、x5 ，当前的基本可行解和目标函数值为：x = (0，25，15，15，0)T，z = 62500。这个解对应于图中的C、D交点。153154第二次迭代： （1）当前的可行基为B7 = (p2 , p3 , p4)，那么x2 ，x3 ，x4为基变量，x1 ，x5为非基变量。在原标准型中将基变量和目标函数用非基变量表示： z =

48、 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 155 （2）选择进基变量。在目标函数z = 62500 + 1500 x1 (2500/3) x5 中，非基变量x1的系数是正数，因此 x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0开始增加, 另一个非基变量x5保持零值不变。 (3)确定出基变量。在约束条件 x2 = 25 0 x1 +(1/3) x5x3 = 15 3 x1 - (2/3) x5 x4 = 15 2 x1 - (1/

49、3) x5156中，由于进基变量x1在两个约束条件中的系数都是正数，当x1的值从0开始增加时，基变量x3 、x4的值分别从当前的值15、15开始减少，当x1增加到5时，x3首先下降为0成为非基变量（应用最小比值原则确定） 。这时，新的基变量为x1 、x2 、x4 ，新的非基变量为x3 、x5 ，当前的基本可行解和目标函数值为：x = (5，25，0，5，0)T，z = 70000。这个解对应于图中的A,C交点。157158第三次迭代： （1）当前的可行基为B2 = (p1 , p2 , p4 )，那么x1 ，x2 ，x4为基变量，x3 ，x5为非基变量。在原标准型中将将基变量和目标函数用非基变

50、量表示： z = 70000 500 x3 - 500 x5x1 = 5 (1/3) x3 - (2/9)x5 x2 = 25 0 x3 + (1/3) x5x4 = 5 - -(2/3) x3 + (1/9) x5 159 （2）选择进基变量。在目标函数z = 70000 500 x3 500 x5 中，非基变量x3 、x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x* = (5，25，0，5，0)T，最优目标值为z* = 70000。这个解对应于图中的A,C交点。我们也称相应的基B2 = (p1 , p2 , p4)为最优基。计算结束。160161表格单纯形法考虑

51、： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0162加入松弛变量化为标准型（就是典式的另外一种表达方式）：典式的矩阵表达式（复习） ：163代数单纯形法求解时典式的表达式（复习）： 对于典式表达式（1），为了方便求解大规模(LP)问题，我们构建如下表格形式的单纯形表164显然，xj = 0 j = 1, , n ; xn+i

52、 = bi i = 1 , , m 是基本可行解 对应的基是单位矩阵。以下是初始单纯形表： m m其中：f = - cn+i bi j = cj - cn+i aij 为检验数 cn+i = 0 i= 1,m i = 1 i = 1 ai,n+i = 1 , aj,n+i = 0 ( ji ) i , j = 1, , m i=bi /aij 165Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 最优解 x1 = 5 x

53、2 = 25 x4 = 5（松弛标量，表示B设备有5个机时的剩余） 最优值 z* = 70000 166用表格单纯形法求解167引入非负的松弛变量x4,x5, 将该LP化为标准型168 CB XB Cj b xj 2 3 3 0 0 x1 x2 x3 x4 x5 j 0 0 X4 X5 3 9 1 1 1 1 0 1 4 7 0 13/19/4 j 2 3 3 0 0 0 3 X4 X2 3/4 9/4 3/4 0 -3/4 1 -1/4 1/4 1 7/4 0 1/4 1 9 j 1/4 0 -9/4 0 -3/4 2 3 X1 X2 1 2 1 0 -1 4/3 -1/3 0 1 2 -1

54、/3 1/3 j 0 0 -1 -5/3 -1/3169从最优表可知:该LP的 最优解是X*=(1,2,0,0,0)T 相应的目标函数最优值是Zmax=8170注意：单纯形法中， (1)每一步运算只能用矩阵初等行变换； (2)表中第3列的数总应保持非负（ 0）（最小比值原则可保证）； (3)当所有检验数均非正（ 0）时，得到最优单纯形表。 （4）当最优单纯形表存在非基变量对应的检验数为零时，存在无穷多最优解； （5）如果某大于0的检验数所对应的所有aij 非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束。171第八节 线性规划在经济管理方

55、面的应用 一、合理利用线料问题 例 1现要做100套钢架，每套钢架用长2.9m、2.1m和1.5m的元钢各一根。已知原料长7.4m，问如何下料，使用原料最省。172解：简单的套裁方法：在每一根7.4m的原料上分别截取2.9m、2.1m和1.5m三种不同规格的元钢各一根，组成一套钢架。上述套裁方法的结果：每根原料均有0.9m（7.4 - 2.9 - 2.1 - 1.5 = 0.9）的料头被浪费。做100套钢架，需要原料100根，共有90m料头被浪费。173方 案IIIIIIIVV2.9001212.1120021.532310合计6.67.27.47.37.1料头0.80.200.10.3上述五

56、种套裁方案料头均小于0.9m。选择更好的套裁方法（比如每根原料上只截取两种不同规格的元钢）。套裁方案如下：174方 案IIIIIIIVV2.9120102.1002211.531203合计7.47.37.27.16.6料头00.10.20.30.8把这 5 套套裁方案按浪费料头数量从低到高的顺序重新排列：175设按方案 I 下料的原料数量为 x1 根； 按方案 II 下料的原料数量为 x2 根； 按方案 III 下料的原料数量为 x3 根； 按方案 IV 下料的原料数量为 x4 根； 按方案 V 下料的原料数量为 x5 根。从而建立问题模型如下：176177二、配料问题 例 1某工厂要用三种原

57、材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表。该厂应如何安排生产，使利润收入为最大？178产品名称规格要求单价（元/kg）A原材料 C 不少于 50%50原材料 P 不超过 25%B原材料 C 不少于 25%35原材料 P 不超过 50%D不限25原材料名称每天最多供应量（kg）单价（元/kg）C10065P10025H6035表 1表 2179 DC ：D 中 C 的数量。 DP ：D 中 P 的数量。 DH ：D 中 H 的数量。 AC ：A 中 C 的数量。 AP ：A 中 P 的数量。 AH ：A 中

58、H 的数量。 BC ：B 中 C 的数量。 BP ：B 中 P 的数量。 BH ：B 中 H 的数量。 解：180由表 1 中规格要求：181由表 2 中供应量限制：182由表 1中的产品价格：由表 2中的原材料价格：产品 A产品 B产品 D原材料 C原材料 P原材料 H183设： x1=AC x2=AP x3=AH x4=BC x5=BP x6=BH x7=DC x8=DP x9=DH184185三、生产与库存的优化安排 某工厂生产五种产品（ i = 1,5 ），已知：单件产品的售价： Si 元单件产品的生产工时： ai 单件产品的成本：正常时间内为 Ci 元，加班时间内为C i 元；上半年

59、市场需求量：dij（i=1,5; j=1,6）上半年生产工时：正常时间内为rj ，加班时间内为 rj( j = 1,6 ) ；186每月生产的各种产品如当月销售不完，可以库存，费用为每件产品每月 Hi 元。假设1月初所有产品的库存为0，要求6月底各产品库存量分别为 ki 件。现要求为该工厂制定一个生产计划，在尽可能利用生产能力的条件下，获取最大利润。187解：设 xij ：第 i 种产品第 j 个月正常时间的生产量； xij：第 i 种产品第 j 个月加班时间的生产量； yij ：第 i 种产品第 j 个月的销售量； wij ：第 i 种产品第 j 个月末的库存量。（1）正常时间工时限制：18

60、8（2）加班时间的生产工时限制：（3）每月销量不能超过市场需求量：（4）上月末库存+本月产量-本月销量 = 本月末库存189（5）各变量的非负约束（6）总销售利润（7）总库存成本190s.t.191四、连续投资问题 某部门在今后五年内考虑给下列项目投资，已知：项目A：从第 1 年第 4 年，每年年初需要投资，并于次年末回收本利115%； 项目B：第 3 年初需要投资，第 5 年末回收本利125%，但规定最大投资额不超过 4 万元；项目C：第 2 年初需要投资，到第 5 年末回收本利140%，但规定最大投资额不超过 3 万元；192项目D：5 年内，每年年初可投资，于当年末归还，并加利息6%。该