运筹学第1章-线性规划

1、7/25/2022第1章 线性规划1 CONTENTS目录7/25/20221.1 线性规划建模1.2 线性规划的解1.3 线性规划的图解法1.4 线性规划的基本定理1.5 单纯形法1.6 单纯形法的进一步讨论1.7 应用举例21.1 线性规划建模例1.1 生产计划问题问产品A, B各生产多少, 可获最大利润?生产经营中经常提出的一个问题是：如何合理地利用人、财、物，以降低成本，获取效益，这就是规划问题。7/25/20221.1.1 线性规划引例 A B 备用资源 钢材（吨） 1 2 30 劳动力（工时） 3 2 60特种设备（台时） 0 2 24 利润（元/件） 40 504 x1 + 2x

2、2 30 3x1 + 2x2 60 2x2 24 x1，x2 0max z = 40 x1 +50 x2解: 设产品A, B的产量分别为变量 x1, x2s.t.7/25/20221.1.1 线性规划引例5例1.2 混合配料问题请设计一个既保证维生素摄入量，又最经济的配食方案。 饲料 A B C 每单位成本 饲料1 4 1 0 2 饲料2 6 1 2 5 饲料3 1 7 1 6 饲料4 2 5 3 8 每天维生素 12 14 8 的最低需求维生素/mg7/25/20221.1.1 线性规划引例6解：设每天给每头奶牛喂食饲料 i 的单位用量为 xi (i =1,2,3,4)min z = 2x1

3、 + 5x2 +6x3+8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)7/25/20221.1.1 线性规划引例s.t.7线性规划问题的特征要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件线性规划模型的要素决策变量：向量 (x1 , , xn)T ，即决策人要考虑和控制的因素（通常非负）约束条件：线性等式或不等式目标函数：z = f (x1 , , xn) 线性式，求 z 极大或极小7/25/20221.1.1 线性规划引例8max (min) z

4、= c1x1 + c2x2 + + cnxna11x1+ a12x2+ a1nxn (=, ) b1a21x1+ a22x2+ a2nxn (=, ) b2 am1x1+ am2x2+ amnxn (=, ) bmxj ( ) 0, j = 1,2,n7/25/20221.1.2 线性规划模型的一般形式9a11x1+ a12x2+ a1nxn = b1a21x1+ a22x2+ a2nxn = b2 am1x1+ am2x2+ amxn = bmxj 0 ( j = 1,2,n)max z = c1x1 + c2x2 + + cnxn其中 bi 0 ( i=1,2,m)7/25/20221.1

5、.3 线性规划模型的标准形式10max z = cTxs.t. Ax = b x 0 a11 a12 a1n其中 A = a21 a22 a2n am1 am2 amn x1 x = x2 xn b1 b = b2 bm c1 c = c2 cn标准形式的矩阵表示：7/25/20221.1.3 线性规划模型的标准形式11(1) 目标函数(2) 约束条件(3) 决策变量非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式12(1) 目标函数xoz-z令 z = z非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式13(2) 约束条件例1. max z = 40

6、x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式14(2) 约束条件 x1 +2x2 +x3 = 30 3x1 +2x2 +x4 = 60 2x2 + +x5 = 24 x1 , , x5 0 x3, x4, x5 称为松弛变量 (slack variables)例1. max z = 40 x1+ 50 x2+0 x3 +0 x4+0 x5非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式154x1+6x2+ x3 +2x4 12 x1+ x2+7x3+5x4 1

7、4 2x2+ x3+3x4 8 x1 , , x4 0 例2. min z = 2x1+ 5x2+6x3 +8x4(2) 约束条件非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式16(2) 约束条件4x1+6x2+ x3 +2x4 - x5 = 12 x1+ x2+7x3+5x4 - x6 = 14 2x2+ x3+3x4 - x7 = 8 x1 , , x7 0 x5, x6, x7 剩余变量 (surplus variables)例2. min z = 2x1+ 5x2+6x3 +8x4非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式17(3) 决策

8、变量3 x1 -3 x1 +2x2 8 x1 - x1 4x2 14 x1 , x1 , x2 03x1+2x2 8 x1 4x2 14 x2 0令 x1= x1- x1 非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式18(3) 决策变量 x1 +x2 11 x1 16 x1 , x2 0 x1+x2 5-6 x1 10 x2 0-6+6 x1+6 10+6 令 x1 = x1 +6 0 x1 16非标准型 标准型7/25/20221.1.3 线性规划模型的标准形式197/25/20221.1.3 线性规划模型的标准形式变换的方法目标函数为 min型，价值系数一律反号，即

9、令 f (x) = - f (x) = - cTx第 i 个约束的 bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向第 i 个约束为 型，在不等式左边增加一个非负的变量 xn+i，称为松弛变量；同时令 cn+i = 0第 i 个约束为 型，在不等式左边减去一个非负的变量 xn+i，称为剩余变量；同时令 cn+i = 0若 xj 0，令 xj = - xj ，代入非标准型，则有 xj 0若 xj 正负不限，令 xj= xj - xj，xj 0，xj 0，代入非标准型201.2 线性规划的解max z = cTxs.t. Ax= b (1) x 0 (2)定义1：满足约束(1)，(2)

10、的x = (x1 , , xn)T 称为LP问题的可行解，全部可行解的集合称为可行域。定义2：使目标函数达到最大值的的可行解称为LP问题的最优解。(LP)7/25/20221.2 线性规划的解22BN(m n) rank(A)=m 至少有一个m阶子式不为0Amn 满秩mm 满秩子矩阵a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amn P1 Pm Pm+1 PnAmn=max z = cTxs.t. Ax= b x 0 x = ( x1 , , xn )T7/25/20221.2 线性规划的解23定义3：基 (基阵) 若 A 中一个 mm 子

11、矩阵 B 是可逆矩阵，则称方阵 B 为 LP 问题的一个基。A = (P1 Pm Pm+1 Pn ) = (B N) 基向量 非基向量 B N X = (x1 xm xm+1 xn )T = (XB XN)T 基变量 非基变量 XB XN7/25/20221.2 线性规划的解24AX = b 的求解A=(B N) X=(XB XN )T XB XN(B N) = bBXB +NXN = bBXB = b-NXNXB = B-1 b - B-1N XN7/25/20221.2 线性规划的解25定义4：基本解 对应于基 B，X = 为 AX = b 的一个解。B-1 b 0定义5：基本可行解 基

12、B，基本解 X = B-1 b 0若 B-1 b 0，称基 B 为可行基。若其基本解是最优解，成为最优基本解，相应的基为最优基。 基本解中最多有m个非零分量; 基本解的数目7/25/20221.2 线性规划的解26约束方程的解空间基本解可行解非可行解基本可行解7/25/20221.2 线性规划的解271.3 线性规划的图解法非负约束The non-negative constraintsx2x1最简单、直观的方法但只适用有两个决策变量的情况7/25/20221.3.1 图解法的步骤290 1 2 3 4 5 6 7 8可行域x2非可行域x1+2x2 843214x1 16x1最优解点x1=4，

13、 x2 =2z= 2 x1+3 x2即x2 = -2 x1/3+z/3z取不同值时是一束斜率为-2/3平行线，z最大值出现在最高的一条线上。 4x2 127/25/20221.3.1 图解法的步骤已知某线性规划模型归结为：目标函数 max z= 2 x1+3 x2约束条件 x1+2 x2 8 4 x1 16 s.t. 4 x2 12 x1, x2 0307/25/20221.3.1 图解法的步骤max z = x1+3x2 s.t. x1+ x2 6-x1+2x2 8 x1 0, x2 0可行域目标函数等值线最优解64-860 x1x231例1.1 max z = 40 x1+ 50 x2 x

14、1+2x2 303x1+2x2 60 2x2 24 x1 , x2 07/25/20221.3.2 线性规划解的几种可能性32DABC解：(1) 确定可行域 x1 0 x1 =0 (纵) x2 0 x2 =0 (横) x1+2x2 30 (0,15) (30,0)0102030 x23x1+2x2 60 (0,30) (20,0) 2x2 24 (0,12) 203010 x17/25/20221.3.2 线性规划解的几种可能性33(2) 求最优解解：x* = (15,7.5) zmax =975z=40 x1+50 x20=40 x1+50 x2 (0,0), (10,-8)C点： x1+2

15、x2 =30 3x1+2x2 =60DABC0102030 x2203010 x17/25/20221.3.2 线性规划解的几种可能性34例： max z = 40 x1+ 80 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 07/25/20221.3.2 线性规划解的几种可能性无穷多个最优解35最优解： BC线段B点 x(1)=(6,12) C点 x(2)=(15,7.5)x * = x(1)+(1-) x(2) (0 1)求解DABC0102030 x2203010 x1Z= 40 x1 + 80 x2 =0 1.3.2 线性规划解的几种可能性036无界无有限

16、最优解例： max z = 2x1+ 4x2 2x1+x2 8-2x1+x2 2x1 , x2 0Z=02x1+ x2=8-2x1+ x2=28246x240 x17/25/20221.3.2 线性规划解的几种可能性无界解37例： max z = 2x1+x2 x1 + x2 22x1 +2x2 6 x1 , x2 0无解无可行解7/25/20221.3.2 线性规划解的几种可能性无可行解x1+ x2=22x1+ 2x2=64123x220 x13387/25/20221.3.2 线性规划解的几种可能性 线性规划的可行域及最优解的可能结果图示：(a)可行域封闭，唯一最优解(b)可行域封闭，多个

17、最优解(d)可行域开放，多个最优解(e)可行域开放，目标函数无界(f) 可行域为空集(c)可行域开放，唯一最优解39 唯一解 无穷多个最优解 无有限最优解 无可行解有解无解总结:7/25/20221.3.2 线性规划解的几种可能性40可行域为凸多边形若有最优解，一定在可行域的顶点达到X(1)X(2)凸多边形凹多边形X(1)X(2)7/25/20221.3.3 图解法的启示41凸集及其性质定义1：凸集 D 是 n 维欧氏空间上的一个集合 X(1), X(2)D, 对任一个满足 X= X(1)+(1-) X(2) (0 1) 有 XD凸集中任意两点的连线仍然属于该集合。7/25/20221.3.3

18、 图解法的启示42凸集及其性质定义2：凸组合 X(1) , X(2) , , X(k) 是 n 维欧氏空间中 的 k 个点, 若有一组数 1 , 2 , , k 满足 0 i 1 ( i=1, ,k ) i = 1 ki=1有点 X = 1 X(1) + + k X(k)则称点 X 为 X(1) , X(2) , ,X(k) 的凸组合。7/25/20221.3.3 图解法的启示437/25/20221.3.3 图解法的启示 凸集 D, 点 XD，若找不到两个不 同的点 X(1) , X(2) D 使得 X= X(1) + (1- ) X(2) (0 1) 则称 X 为 D 的顶点。凸集及其性质

19、定义3：顶点凸多边形也称为极点extreme point44几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基本解可行域的极点基本可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解1.3.3 图解法的启示0451.4 线性规划的基本定理 若(LP)问题有可行解，则可行解集（可行域）是凸集（可能有界，也可能无界），有有限个顶点。 (LP)问题的基本可行解 可行域的顶点。 若(LP)问题有最优解，必定可以在基本可行解（顶点）达到。7/25/20221.4 线性规划的基本原理47若(LP)问题有可行解

20、，则可行解集（可行域）是凸集（可能有界，也可能无界），有有限个顶点。即证满足约束条件的所有点组成的图形是凸集。or7/25/20221.4 线性规划的基本原理48 (LP)问题的基本可行解 可行域的顶点。引理：线性规划问题的可行解 X = (x1, , xn) 为基本可行解的充要条件是 X 的正分量所对应的系数列向量是线性独立的。证明： 由基本可行解定义显然成立； 若向量 P1, P2, , Pk 线性独立，则必有k m；（1）“k = m” 恰好构成一个基；（2）“k m” 一定可以从其余列向量中找出 (m-k) 个与 P1, P2, , Pk 构成一个基，其对应的解恰为 X。7/25/20

21、221.4 线性规划的基本原理49 (LP)问题的基本可行解 可行域的顶点。反证法（1）X 不是基本可行解 X 不是可行域的顶点假设 X 的前 m 个 分量为正：由引理，P1, P2, , Pm 线性相关，即7/25/20221.4 线性规划的基本原理50反证法（2）X 不是可行域的顶点 X 不是基本可行解可以找到可行域内另外两个不同点Y 和 Z：X=aY + (1-a)Z (0a0 007/25/20221.5.1 迭代原理58单纯形法的基本思路：从一个初始的基本可行解出发，经过判断，如果是最优解，则结束，否则经过基变换得到另一个改善的基本可行解，如此一直进行下去，直到找到最优解。第1步：求

22、初始基可行解，列出初始单纯形表。第2步：最优性检验。第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。第4步：重复第2、3步，一直到计算结束为止。7/25/20221.5.2 迭代步骤59非标准形的LP问题标准的LP问题设法使约束方程的系数矩阵中包含一个单位阵以此作为基求出问题的一个初始基可行解为了书写规范和便于计算，对单纯形的计算有一种专门的表格，称为单纯形表。 含初始基可行解的单纯形表 初始单纯形表 含最优解的单纯形表 最终单纯形表第1步 - 求初始基可行解，列出初始单纯形表7/25/20221.5.2 迭代步骤60 cj c1 cm cj cnCB 基 b x

23、1 xm xj xn c1 x1 b1 c2 x2 b2 ： ： ： ： ： ： cm xm bm 1 0 a1j a1n 0 0 a2j a2n ： ： ： ： ： ： ： ： 0 1 amj amn cj - zj 0 0 基变量基变量的取值检验数j第1步 - 求初始基可行解，列出初始单纯形表7/25/20221.5.2 迭代步骤61 cj c1 cm cj cnCB 基 b x1 xm xj xn c1 x1 b1 c2 x2 b2 ： ： ： ： ： ： cm xm bm 1 0 a1j a1n 0 0 a2j a2n ： ： ： ： ： ： ： ： 0 1 amj amn cj -

24、zj 0 0 所有检验数0，且基变量中不含人工变量时，即为最优解。 当表中存在 cj zj 0时，如有 Pj 0，则问题为无界解。 如果都不是，下一步第2步 最优性检验1.5.2 迭代步骤062确定换入变量和换出变量第3步 换基，使目标函数值更大换入变量 = 进基变量 = Entering Variable根据 ，确定 xk 为换入变量换出变量 = 出基变量 = Leaving Variable按 规则计算，可确定 xl 为换出变量7/25/20221.5.2 迭代步骤637/25/20221.5.2 迭代步骤以 alk 为主元素 (pivot number) 进行迭代，得到新的单纯形表。第3

25、步 换基，使目标函数值更大旋转运算 Pivoting64 cj c1 cl cm cj ck CB 基 b x1 xl xm xj xk c1 x1 b1 ： ： ： ck xk ： ： ： cm xm bm 1 0 0 ： ： ： ： ： 0 0 1 ： ： ： ： ： 0 1 0 cj - zj 0 0 0 1.5.2 迭代步骤第3步 换基，使目标函数值更大旋转运算 Pivoting065例1.4 用单纯形法求解线性规划问题max z= 40 x1 + 50 x2 x1 +2x2 30 3x1 +2x2 60 2x2 24 x1 , x2 0s.t.第4步 重复2、3步，直到计算结束7/2

26、5/20221.5.2 迭代步骤66解：首先将上述问题化为标准型：1.5.2 迭代步骤7/25/202267单纯法求解cBxBbx1x2x3x4x54050000 x3x4x500030602413022210001000104050000-z 153012初始单纯形表重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算06850122x2501121/2036-106-11.5.2 迭代步骤cBxBbx1x2x3x4x54050000 x3x4001201010-1-11/2400-25-z 0612-第2单纯形表00336101x25060-840计算非基变量检验数为检验数判别

27、06904061x14011018-32000-4015第3单纯形表-400701.5.2 迭代步骤cBxBbx1x2x3x4x54050000 x3x4012110-11/20-z 第3单纯形表00 x25060-840检验数判别0700 x1401018-32000-4015-400700 x59-3/211/2015-1/211/2015/23/4-1/4-35/2-15/20-975检验数全非正, 已经取得最优解, 最优解为: X* = (15,15/2,0,0,9)T Z* = 975最终单纯形表Final Simplex tableau1.5.2 迭代步骤1.6 单纯形法的进一步讨

28、论 前面的例子中，化为标准形式后约束条件的系数矩阵都含有单位矩阵，可以作为初始可行基。 如果化为标准形式的约束条件的系数矩阵中不存在单位矩阵呢？ 如何建立初始单纯形表？ 例1.5: max z = x1 + 2x2 + x3 x1+ 4x2 - 2x3 120 x1+ x2 + x3 =60 x1 , x2 , x3 0s.t.7/25/20221.6 单纯形法的进一步讨论72max z = x1 + 2x2 + x3x1+ 4x2 - 2x3 - x4 = 120 x1+ x2 + x3 = 60 x1 , x2 , x3 , x4 0s.t.可以添加两列单位向量P5 ，P6，构成单位矩阵。

29、max z = x1 + 2x2 + x3 -M x5 -M x6 x1+ 4x2 - 2x3 - x4 + x5 = 120 x1+ x2 + x3 + x6 = 60 x1 , x2 , x3 , x4 , x5 , x6 0s.t.人工变量-M 罚因子7/25/20221.6.1 人工变量法 大M法73 1 2 1 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 2 x2 60 1 1 1 0 0 1 0 x4 120 3 0 6 1 -1 4 -1 0 -1 0 0 -2-M最终单纯形表:7/25/20221.6.1 人工变量法 大M法747/25/20221.6.

30、1 人工变量法两阶段法大M是一个很大的数,但计算机处理时取多大呢?两阶段法不用确定M具体值，可用于计算机求解。第一阶段：先求解一个目标函数中只包含人工变量的 线性规划问题，判断其有否可行解： - 当人工变量取值为 0 时，这时的最优解就是原线性规划问题的 一个基可行解； - 如果最优解的基变量中含有非零的人工变量，则原线性规划问题 无可行解。第二阶段：有可行解时去掉人工变量再求解。757/25/20221.6.1 人工变量法两阶段法max z = x1 + 2x2 + x3x1+ 4x2 - 2x3 - x4 = 120 x1+ x2 + x3 = 60 x1 , x2 , x3 , x4 0

31、s.t. x1+ 4x2 - 2x3 - x4 + x5 = 120 x1+ x2 + x3 + x6 = 60 x1 , x2 , x3 , x4 , x5 , x6 0s.t.max z = x1 + 2x2 + x3 -M x5 -M x676第一阶段的线性规划问题：min z = x5 + x6x1+ 4x2 - 2x3 - x4 + x5 = 120 x1+ x2 + x3 + x6 = 60 x1 , x2 , x3 , x4 , x5 , x6 0s.t.第二阶段去除人工变量，目标函数回归到：max z = x1 + 2x2 + x3( max z = - x5 - x6 )ma

32、x z = x1 + 2x2 + x3 -M x5 -M x6从第一个阶段的最后一张单纯形表出发，继续用单纯形法计算。1.6.1 人工变量法两阶段法077例1.6: max z = 2x1 + x2 x1+ x2 2 2x1 + 2x2 6 x1 , x2 0s.t.max z = 2x1 + x2+ 0 x3+ 0 x4 - Mx5 x1+ x2 + x3 = 2 2x1 + 2x2 - x4 + x5 = 6 x1 , x2 , x3 , x4 , x5 0s.t.判定无解条件: 当进行到最优表时，仍有人工变量在基中，且0，则说明原问题无可行解。7/25/20221.6.2 无可行解78

33、2 1 0 0 -MCB XB b x1 x2 x3 x4 x5 0 x3 2 1 1 1 0 0-M x5 6 2 2 0 -1 1 cj - zj 2+2M 1+2M 0 -M 02 x1 2 1 1 1 0 0-M x5 2 0 0 -2 -1 1 cj - zj 0 -1 -2-2M -M 07/25/20221.6.2 无可行解79例1.7：max z = 4x1 +x2 -x1+ x2 2 x1 4x2 4 x1 2x2 8x1 , x2 0-x1+x2+ x3 = 2x1 4x2 + x4 = 4x1 2x2 + x5 = 8x1, , x5 0 当表中存在 cj zj 0 时有

34、 Pj0，则问题为无界解。7/25/20220801.6.3 无界解7/25/202280 4 1 0 0 0 CB XB b x1 x2 x3 x4 x50 x3 2 -1 1 1 0 00 x4 4 1 -4 0 1 00 x5 8 1 -2 0 0 1 0 4 1 0 0 07/25/20220811.6.3 无界解7/25/202281 4 1 0 0 0 CB XB b x1 x2 x3 x4 x50 x3 6 0 -3 1 1 04 x1 4 1 -4 0 1 00 x5 4 0 2 0 -1 1 16 0 17 0 -4 00 x3 12 0 0 1 -1/2 3/24 x1 1

35、2 1 0 0 -1 21 x2 2 0 1 0 -1/2 1/2 50 0 0 0 9/2 -17/21.6.3 无界解082本问题无界。x1x2OZ=00831.6.3 无界解 当所有检验数 时，对某个非基变量 xj 有 cj - zj=0，且可以找到 。 这表明可以找到另一个顶点（基可行解），其目标函数值也到达最大。 由于可行域为凸集，所以该两点连线上的点也属于可行域，且目标函数值相等。即有无穷多解。 如果所有非基变量的 ，则LP问题唯一解。7/25/20221.6.4 无穷多最优解84例1.8: max z = 40 x1 +80 x2 x1+2x2 30 3x1+2x2 60 2x2

36、 24 x1 , x2 0 x1+2x2 +x3 = 303x1+2x2 +x4 = 60 2x2 +x5 = 24 x1 x5 07/25/20221.6.4 无穷多最优解85 40 80 0 0 0 CB XB b x1 x2 x3 x4 x50 x3 30 1 2 1 0 00 x4 60 3 2 0 1 00 x5 24 0 2 0 0 1 0 40 80 0 0 00 x3 6 1 0 1 0 -1 0 x4 36 3 0 0 1 -1 80 x2 12 0 1 0 0 1/2 (接下表) 40 0 0 0 -400861.6.4 无穷多最优解 40 80 0 0 0 CB XB b

37、 x1 x2 x3 x4 x5 40 x1 6 1 0 1 0 -10 x4 18 0 0 -3 1 280 x2 12 0 1 0 0 1/2 1200 0 0 -40 0 040 x1 15 1 0 -1/2 1/2 0 0 x5 9 0 0 -3/2 1/2 180 x2 15/2 0 1 3/4 -1/4 0 1200 0 0 -40 0 00871.6.4 无穷多最优解X(1)= (6,12) Z(1)=1200 X(2)= (15,15/2) Z(2)=1200无穷多解全部解：X= + (1-) (0 1) 6 15 12 15/27/25/20221.6.4 无穷多最优解88退化

38、解： 有时存在两个以上相同的最小值，从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。 7/25/20221.6.5 退化和循环89例: max z = 10 x1 + 12x23x1+4x2 64x1+ x2 23x1 +2x2 3x1 , x2 03x1+4x2+ x3 = 64x1+ x2 + x4 = 23x1 +2x2 + x5 = 3x1 x5 07/25/20221.6.5 退化和循环90 10 12 0 0 0 XB b x1 x2 x3 x4 x5 i 0 x3 6 3 4 1 0 0 3/20 x4 2 4 1 0 1 0 2/10 x5 3 3 2 0 0 1

39、 3/2 0 10 12 0 0 0 12 x2 3/2 3/4 1 1/4 0 0 20 x4 1/2 13/4 0 -1/4 1 0 2/130 x5 0 3/2 0 -1/2 0 1 0 18 1 0 -3 0 0 12 x2 3/2 0 1 1/2 0 -1/20 x4 1/2 0 0 5/6 1 -13/6 10 x1 0 1 0 -1/3 0 2/3 18 0 0 -8/3 0 -2/3 ( )( )1.6.5 退化和循环退化解zmax=18x* = (0, 3/2, 0, 1/2, 0)T但是，退化解情形有可能出现迭代计算的死循环！7/25/20221.6.5 退化和循环92死循

40、环的例子：1.6.5 退化和循环093和初始基可行解相同1.6.5 退化和循环094 为避免出现计算循环，可采用Bland(1974)准则: (1) 当存在多个 时，始终选取下标值为最小的变量作为换入变量； (2) 当计算 值出现两个或以上相同的最小比值时，始终选取下标值为最小的变量作为换出变量； 7/25/20221.6.5 退化和循环95前例中，在第5张表时我们运用Bland法则，得：7/25/20221.6.5 退化和循环961.7 应用举例7/25/20221.7 应用举例 (1) 要求解问题的目标能用数值指标来表示，并且目标函数 z = f (x) 为线性函数； (2) 存在着多种可

41、选方案； (3) 要达到的目标是在一定约束条件下实现的,这些约束条件可用线性等式或不等式来描述。一般来讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划的模型。下面举例说明线性规划在经济管理等方面的应用。987/25/20221.7.1 风险控制问题997/25/20221.7.1 风险控制问题该问题可以表述为如下的线性规划模型：1007/25/20221.7.1 风险控制问题目标函数是带有绝对值的特殊线性规划问题，如何将其转换成一般的线性规划模型呢？101例1.11 某工厂生产三种不同型号的润滑油A，B和C，表1.28是工厂刚刚接到的一季度生产订单。已知每月生产三种润滑油的单位成本如表

42、1.29所示，生产单位润滑油所需的工时分别为1，0.8和1.5（小时/吨）。该工厂每个月的最大生产能力均为900（小时）。若生产出来的润滑油当月不交货，每吨库存1个月的存储费分别为220，200和160元。请为该厂设计一个既保证完成订单，又使一季度生产和库存总成本最低的生产计划。7/25/20221.7.2 生产库存问题102表1.28 一季度生产订单（单位：吨）7/25/20221.7.2 生产库存问题表1.29 一季度单位生产成本（单位：元/吨）103目标函数：总成本由生产成本和库存成本两部分构成：7/25/20221.7.2 生产库存问题104约束条件：工时约束各个月生产工时均不超过最大

43、生产能力：交货要求各个月足以完成订单需求即每月库存量不小于0，于是有：非负约束决策变量为生产产品的数量，因此是非负的，即7/25/20221.7.2 生产库存问题105某工厂生产一型号的机床，每台机床上分别需用 2.9、2.1、1.5米长的轴 1根、2根和1根，这些轴需用同一种圆钢制作，圆钢的长度为7.4米。如需要生产100台机床，问应如何安排下料，才能使用料最省？试建立其线性规划模型。B1B2B3B4B5B6B7B8需要量2.9m2.1m1.5m余料10302010.10220.21200.30130.81110.90301.10041.4100200100最少7/25/20221.7.3 合理下料问题106解：设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： min x