1、7/29/2022第第1 1章章 线性规划线性规划1 CONTENTS目录7/29/20221.1 线性规划建模1.2 线性规划的解1.3 线性规划的图解法1.4 线性规划的基本定理1.5 单纯形法1.6 单纯形法的进一步讨论1.7 应用举例21.1 线性规划建模例例1.1 生产计划问题生产计划问题问产品问产品A,B各生产多少各生产多少,可获最大利润可获最大利润?l生产经营中经常提出的一个问题是：如何合理地利用人、财、物，以降低成本，获取效益，这就是规划问题。7/29/20221.1.1 线性规划引例 A B 备用资源备用资源 钢材（吨）钢材（吨）1 2 30 劳动力（工时）劳动力（工时）3
2、2 60特种设备（台时）特种设备（台时）0 2 24 利润（元利润（元/件）件）40 504 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0max z=40 x1+50 x2解解:设产品设产品A,B的产量的产量分别为变量分别为变量 x1,x2s.t.7/29/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、 3 8 每天维生素每天维生素 12 14 8 的最低需求的最低需求维生素维生素/mg7/29/20221.1.1 线性规划引例6解：设解：设每天给每头奶牛喂食饲料每天给每头奶牛喂食饲料 i 的单位用量的单位用量为为 xi (i=1,2,3,4)min z=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)7/29/20221.1.1 线性规划引例s.t.7线性规划问题的特征线性规划问题的特征 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件线性规
4、划模型的要素线性规划模型的要素 决策变量：向量(x1,xn)T ，即决策人要考虑和控制的因素（通常非负）约束条件：线性等式或不等式 目标函数：z=f(x1,xn)线性式，求 z 极大或极小7/29/20221.1.1 线性规划引例8max(min)z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn (=,)b1a21x1+a22x2+a2nxn (=,)b2 am1x1+am2x2+amnxn (=,)bmxj ()0,j=1,2,n7/29/20221.1.2 线性规划模型的一般形式9a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 am1x1
5、+am2x2+amxn=bmxj 0(j=1,2,n)max z=c1x1+c2x2+cnxn其中其中 bi 0(i=1,2,m)7/29/20221.1.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 cnl标准形式的矩阵表示：7/29/20221.1.3 线性规划模型的标准形式11(1)目标函数(2)约束条件(3)决策变量l非标准型 标准型7/29/20221.1.3 线性规划模型的标准形式12(1)目标函数目标函数xoz
6、-z1min njjjzc x令令 z=z1max njjjzc x l非标准型 标准型7/29/20221.1.3 线性规划模型的标准形式13(2)约束条件约束条件例例1.max z=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0l非标准型 标准型7/29/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 x
7、3+0 x4+0 x5l非标准型 标准型7/29/20221.1.3 线性规划模型的标准形式154x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 x1,x4 0 例例2.min z=2x1+5x2+6x3+8x4(2)约束条件约束条件l非标准型 标准型7/29/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.mi
8、n z=2x1+5x2+6x3+8x4l非标准型 标准型7/29/20221.1.3 线性规划模型的标准形式17(3)决策变量决策变量3 x1-3 x1 +2x2 8 x1-x1 4x2 14 x1,x1,x2 03x1+2x2 8 x1 4x2 14 x2 0令令 x1=x1-x1 l非标准型 标准型7/29/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 16l非标准型 标准型7/29/20221.1.3 线性规划模型的标
9、准形式197/29/20221.1.3 线性规划模型的标准形式变换的方法变换的方法l目标函数为 min型，价值系数一律反号，即令 f(x)=-f(x)=-cTxl第 i 个约束的 bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向l第 i 个约束为 型，在不等式左边增加一个非负的变量 xn+i，称为松弛变量；同时令 cn+i=0l第 i 个约束为 型，在不等式左边减去一个非负的变量 xn+i，称为剩余变量；同时令 cn+i=0l若 xj 0，令 xj=-xj，代入非标准型，则有 xj 0l若 xj 正负不限，令 xj=xj-xj，xj 0，xj 0，代入非标准型201.2 线性规划的
10、解max z=cTxs.t.Ax=b (1)x 0 (2)定义定义1 1：满足约束：满足约束(1)，(2)的的x=(x1,xn)T 称为称为LP问题的问题的可行解可行解，全部可行解的集合称为，全部可行解的集合称为可行域可行域。定义定义2 2：使目标函数达到最大值的的可行解称为：使目标函数达到最大值的的可行解称为LP问题的问题的最优解最优解。(LP)7/29/20221.2 线性规划的解22BN(m n)rank(A)=m 至少有一个至少有一个m阶子式不为阶子式不为0Amn 满秩满秩mm 满秩子矩阵满秩子矩阵a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm a
11、mm+1 amn P1 Pm Pm+1 PnAmn=max z=cTxs.t.Ax=b x 0 x=(x1,xn)T7/29/20221.2 线性规划的解23定义定义3：基基(基阵基阵)若若 A 中一个中一个 mm 子矩阵子矩阵 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/29/20221.2 线性规划的解24AX=b 的求解的求解A=(B N)X=(XB XN)
12、T XB XN(B N)=bBXB+NXN=bBXB=b-NXNXB=B-1 b-B-1N XN7/29/20221.2 线性规划的解25定义定义4：基本解基本解 对应于基对应于基 B，X=为为 AX=b 的一个解。的一个解。B-1 b 0定义定义5：基本可行解基本可行解 基基 B，基本解，基本解 X=B-1 b 0若若 B-1 b 0，称基，称基 B 为为可行基可行基。若其基本解是最。若其基本解是最优解，成为优解，成为最优基本解最优基本解，相应的基为，相应的基为最优基最优基。基本解中最多有基本解中最多有m个非零分量个非零分量;mnC基本解的数目基本解的数目7/29/20221.2 线性规划的
13、解26约束方程的约束方程的解空间解空间基本解基本解可行解可行解非可行解非可行解基本基本可行解可行解7/29/20221.2 线性规划的解271.3 线性规划的图解法非负约束The non-negative constraintsx2x1l最简单、直观的方法l但只适用有两个决策变量的情况7/29/20221.3.1 图解法的步骤290 1 2 3 4 5 6 7 8可行域x2非可行域x1+2x2 843214x1 16x1最优解点最优解点x1=4，x2 22z=2 x1+3 x2即x2=-2 x1/3+z/3z取不同值时是一束斜率为-2/3平行线，z最大值出现在最高的一条线上。4x2 127/2
14、9/20221.3.1 图解法的步骤已知某线性规划模型归结为：已知某线性规划模型归结为：目标函数目标函数 max z=2 x1+3 x2约束条件约束条件 x1+2 x2 8 4 x1 16 s.t.4 x2 12 x1,x2 0307/29/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 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 07/29/20221.3.2 线性规划解的几种
15、可能性32DABC解：解：(1)确定可行域确定可行域 x1 0 0 x1=0=0(纵纵)x2 0 0 x2=0=0(横横)x1+2x2 30 (0,15)(30,0)0102030 x23x1+2x2 60 (0,30)(20,0)2x2 24 (0,12)203010 x17/29/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+2x2=30 3x1+2x2=60DABC0102030 x2203010 x17/29/20221.3
16、.2 线性规划解的几种可能性34例：例：max z=40 x1+80 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 07/29/20221.3.2 线性规划解的几种可能性l无穷多个最优解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无界无界无有限最优解无有限最优解例：例：max z=2x1+4x2 2x1+x2 8 8-2x1+x2 2x1,x2 0 0
17、Z=02x1+x2=8-2x1+x2=28246x240 x17/29/20221.3.2 线性规划解的几种可能性l无界解37例例：max z=2x1+x2 x1+x2 22x1+2x2 6 x1,x2 0无解无解无可行解无可行解7/29/20221.3.2 线性规划解的几种可能性l无可行解x1+x2=22x1+2x2=64123x220 x13387/29/20221.3.2 线性规划解的几种可能性 (a)可行域封闭，唯一最优解可行域封闭，唯一最优解(b)可行域封闭，多个最优解可行域封闭，多个最优解(d)可行域开放，多个最优解可行域开放，多个最优解(e)可行域开放，目标函数无界可行域开放，目
18、标函数无界(f)可行域为空集可行域为空集(c)可行域开放，唯一最优解可行域开放，唯一最优解39 唯一解唯一解 无穷无穷多个最优解多个最优解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解总结总结:7/29/20221.3.2 线性规划解的几种可能性40l可行域为凸多边形l若有最优解，一定在可行域的顶点达到X(1)X(2)凸多边形凸多边形凹多边形凹多边形X(1)X(2)7/29/20221.3.3 图解法的启示41凸集及其性质凸集及其性质定义定义1：凸集凸集 D 是是 n 维欧氏空间维欧氏空间上上的一个集合的一个集合 X(1),X(2)D,对任一个满足对任一个满足 X=X(1)+(1
19、-)X(2)(0 1)有有 XD凸集中任意两点的连线仍然属于该集合。凸集中任意两点的连线仍然属于该集合。7/29/20221.3.3 图解法的启示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/29/20221.3.3 图解法的启示437/29/20221.3.3 图解法的启示 凸集凸集 D,点点 X D，
20、若若找不到找不到两个不两个不 同的点同的点 X(1),X(2)D 使得使得 X=X(1)+(1-)X(2)(0 1)则称则称 X 为为 D 的顶点。的顶点。凸集及其性质凸集及其性质定义定义3：顶点顶点凸多边形凸多边形也称为极点extreme point44几何概念几何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交集：约束半平面的交集：凸多边形凸多边形满足一组不等式约束的解满足一组不等式约束的解约束直线的交点约束直线的交点基本解基本解可行域的极点可行域的极点基本可行解基本可行解目标函数等值
21、线：目标函数等值线：一组平行线一组平行线 目标函数值等于一个常数目标函数值等于一个常数的解的解1.3.3 图解法的启示0451.4 线性规划的基本定理 若若(LP)问题有可行解，则可行解集（可行域问题有可行解，则可行解集（可行域）是）是凸集（可能有界，也可能无界），有有限个顶点。凸集（可能有界，也可能无界），有有限个顶点。(LP)问题的基本可行解问题的基本可行解 可行域可行域的顶点。的顶点。若若(LP)问题有最优解，必定可以在基本可行解问题有最优解，必定可以在基本可行解（顶点）达到。（顶点）达到。7/29/20221.4 线性规划的基本原理47若若(LP)问题有可行解，则可行解集（可行域）是问
22、题有可行解，则可行解集（可行域）是凸集（可能有界，也可能无界），有有限个顶点凸集（可能有界，也可能无界），有有限个顶点。即证满足约束条件即证满足约束条件的所有点组成的图形是凸集。的所有点组成的图形是凸集。0Axbxor10 1,njjjjx Pbxjn7/29/20221.4 线性规划的基本原理48(LP)问题问题的基本可行解的基本可行解 可行域可行域的顶点。的顶点。引理：线性规划问题的可行解 X=(x1,xn)为基本可行解的充要条件是 X 的正分量所对应的系数列向量是线性独立的。证明证明：由基本可行解定义显然成立；由基本可行解定义显然成立；若向量若向量 P1,P2,Pk 线性独立，则必有线性
23、独立，则必有k m；（1）“k=m”恰好构成一个基；恰好构成一个基；（2）“k m”一定可以从其余列向量中找出一定可以从其余列向量中找出(m-k)个与个与 P1,P2,Pk 构成一个基，其对应的解恰为构成一个基，其对应的解恰为 X。7/29/20221.4 线性规划的基本原理49(LP)问题问题的基本可行解的基本可行解 可行域可行域的顶点。的顶点。反证法（1）X 不是基本可行解不是基本可行解 X 不是可行域的顶点不是可行域的顶点假设假设 X 的前的前 m 个个 分量为正：分量为正：由引理，由引理，P1,P2,Pm 线性相关，即线性相关，即1 1220mmPPPL111222mmmxPxPxPb
24、L111222mmmxPxPxPbL0iix 12,iiiiXxC XxC 121122XXX1mjjjx Pb7/29/20221.4 线性规划的基本原理50反证法（2）X 不是可行域的顶点不是可行域的顶点 X 不是基本可行解不是基本可行解可以找到可行域内另外两个不同点可以找到可行域内另外两个不同点Y 和和 Z：X=aY+(1-a)Z (0a01 or mjjjjiijiczcc a 007/29/20221.5.1 迭代原理58单纯形法的基本思路：单纯形法的基本思路：从一个初始的基本可行解初始的基本可行解出发，经过判断判断，如果是最优解，则结束，否则经过基变换基变换得到另一个改善的基本可行
25、解，如此一直进行下去，直到找到最优解。第1步：求初始基可行解，列出初始单纯形表。第2步：最优性检验。第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。第4步：重复第2、3步，一直到计算结束为止。7/29/20221.5.2 迭代步骤59非标准形的LP问题标准的LP问题设法使约束方程的系数矩阵中包含 一 个 单 位 阵以此作为基求出问题的一个初始基可行解为了书写规范和便于计算，对单纯形的计算有一种专门的表格，称为单纯形表。含初始基可行解的单纯形表含初始基可行解的单纯形表 初始单纯形表初始单纯形表 含最优解的单纯形表含最优解的单纯形表 最终单纯形表最终单纯形表第第1 1
26、步步 -求初始基可行解，列出初始单纯形表求初始基可行解，列出初始单纯形表7/29/20221.5.2 迭代步骤60 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-zj 0 0 1mjiijicc a1mniinicc a基变量基变量的取值检验数 j11221,jjjmjmjmnPa Pa Pa P第第1 1步步 -求初始基可行解，列出初始单纯形表求初始基可行解，列出初始单纯形表7/29/20221.5.2 迭代步骤61 cj c1 cm cj
27、 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-zj 0 0 1mniinicc a 所有检验数00，且基变量中不含人工变量时，即为最优解。当表中存在 cj zj 0时，如有 Pj 0，则问题为无界解。如果都不是，下一步1mjiijicc a第第2步步 最优性检验最优性检验1.5.2 迭代步骤062确定换入变量和换出变量第第3步步 换基，使目标函数值更大换基，使目标函数值更大换入变量换入变量 =进基变量进基变量 =Entering Variable根据根据 ，确定，
28、确定 xk 为换入变量为换入变量换出变量换出变量 =出基变量出基变量 =Leaving Variable按按 规则计算，可确定规则计算，可确定 xl 为换出变量为换出变量min0ilikiklkbbaaa max|0kjjj 7/29/20221.5.2 迭代步骤637/29/20221.5.2 迭代步骤120010kkklkmkaaPaaMMuuuuuuuuuuuu rMM变换为以 alk 为主元素(pivot number)进行迭代，得到新的单纯形表。第第3步步 换基，使目标函数值更大换基，使目标函数值更大旋转运算旋转运算 Pivoting64 cj c1 cl cm cj ck CB 基
29、 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 kklkczaljjjkklkaczcza1.5.2 迭代步骤11klkabamkmlkaballkba1klkaa1lkamklkaaljlkaa11ljjklkaaaaljmjmklkaaaa12kklkmkaaaa第第3步步 换基，使目标函数值更大换基，使目标函数值更大旋转运算旋转运算 Pivoting065例例1.41.4 用用单纯形法求解线性规划问题单纯形法求解线性规划问题max z=40 x1+50 x2 x1+2x2 30 3x1+2
30、x2 60 2x2 24 x1,x2 0s.t.第第4步步 重复重复2、3步，直到计算结束步，直到计算结束7/29/20221.5.2 迭代步骤66解：解：首先首先将上述问题化为标准型：将上述问题化为标准型：123451231242512345max 40500002 3032 60 s.t.2 24,0zxxxxxxxxxxxxxx x x x x1.5.2 迭代步骤7/29/202267单纯法求解单纯法求解cBxBbx1x2x3x4x54050000 x3x4x500030602413022210001000104050000-z 153012初始单纯形表重新计算检验数，结果如下页检验数判
31、别换基迭代非基变量检验数为miijijnjacc1,.,2,1,计算lklikikiabaab0min06850122x2501121/2036-106-11.5.2 迭代步骤cBxBbx1x2x3x4x54050000 x3x4001201010-1-11/2400-25-z 0612-第2单纯形表00336101x25060-840计算lklikikiabaab0min非基变量检验数为miijijnjacc1,.,2,1,miiibcCBz1检验数判别06904061x14011018-32000-4015第3单纯形表-400701.5.2 迭代步骤cBxBbx1x2x3x4x540500
32、00 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 单纯形法的进一步讨论 前面的例子中，化为标准形式后约束条件的系数矩阵都含有单位矩阵，可以作为初始可行基。如果化为标准形式的约束条件的系数矩阵中不存在单位矩阵呢？如何建立初始
33、单纯形表？例例1.5:max z=x1+2x2+x3 x1+4x2-2x3 120 x1+x2+x3 =60 x1,x2,x3 0s.t.7/29/20221.6 单纯形法的进一步讨论72max z=x1+2x2+x3x1+4x2-2x3-x4 =120 x1+x2+x3 =60 x1,x2,x3,x4 0s.t.可以添加两列单位可以添加两列单位向量向量P5，P6，构成构成单位矩阵。单位矩阵。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/29/
34、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/29/20221.6.1 人工变量法 大M法747/29/20221.6.1 人工变量法两阶段法l大M是一个很大的数,但计算机处理时取多大呢?l两阶段法不用确定M具体值，可用于计算机求解。l第一阶段：先求解一个目标函数中只包含人工变量的 线性规划问题，判断其有否可行解：-当人工变量取值为 0 时，这时的最优解就是原线性规划问题的 一个基可行
35、解；-如果最优解的基变量中含有非零的人工变量，则原线性规划问题 无可行解。l第二阶段：有可行解时去掉人工变量再求解。757/29/20221.6.1 人工变量法两阶段法max z=x1+2x2+x3x1+4x2-2x3-x4 =120 x1+x2+x3 =60 x1,x2,x3,x4 0s.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,
36、x2,x3,x4,x5,x6 0s.t.第二阶段去除人工变量，目标函数回归到：max z=x1+2x2+x3(max z=-x5 -x6)max 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，则说明原问题
37、无可行解。7/29/20221.6.2 无可行解78 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/29/20221.6.2 无可行解79例例1.71.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 当表中存在当表中存在
38、 cj zj 0 时时有有 Pj0，则问题为无界解，则问题为无界解。7/29/20220801.6.3 无界解7/29/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/29/20220811.6.3 无界解7/29/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
39、 0 0 1 -1/2 3/24 x1 12 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，且可以找到，且可以找到 。0j 0 这表明可以找到另一个顶点（基可行解），其目这表明可以找到另一个顶点（基可行解），其目标函数值也到达最大。标函数值也到达最大。由于可行域为凸集，所以该两点连线上的点也属由于可行域为凸集，所以该两点连线上的点也属于可行域，且目标函数值相等。
40、即有无穷多解。于可行域，且目标函数值相等。即有无穷多解。如果所有非基变量的如果所有非基变量的 ，则，则LP问题唯一解。问题唯一解。0j 7/29/20221.6.4 无穷多最优解84例例1.8:1.8:max z=40 x1+80 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1,x2 0 x1+2x2+x3 =303x1+2x2 +x4 =60 2x2 +x5=24 x1 x5 07/29/20221.6.4 无穷多最优解85 40 80 40 80 0 0 0 0 0 0 CB XB b x1 x2 x3 x4 x50 0 x3 30 30 1 1 2 2 1 0 01
41、0 00 0 x4 60 60 3 3 2 2 0 1 00 1 00 0 x5 24 24 0 0 2 0 0 12 0 0 1 0 0 40 80 0 40 80 0 0 00 00 0 x3 6 6 1 0 1 0 1 0 1 0 -1 -1 0 0 x4 36 36 3 3 0 0 0 1 0 1 -1 -1 80 80 x2 12 2 0 0 1 1 0 0 1/2 0 0 1/2 (接下表接下表)40 40 0 0 0 0 0 -40 0 -400861.6.4 无穷多最优解 40 80 40 80 0 0 0 0 0 0 CB XB b x1 x2 x3 x4 x5 40 40
42、x1 6 6 1 1 0 1 0 1 0 0 -1-10 0 x4 18 0 18 0 0 0 -3 -3 1 21 280 80 x2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 1200 1200 0 0 0 0 -40 -40 0 00 040 40 x1 15 1 15 1 0 0 -1/2 1/2 0 -1/2 1/2 0 0 0 x5 9 9 0 0 0 -0 -3 3/2 1/2 1/2 1/2 180 80 x2 15/215/2 0 0 1 1 3/4 -1/4 0 3/4 -1/4 0 1200 1200 0 0 0 0 -40 -40 0 0 0 0087
43、1.6.4 无穷多最优解X X(1)(1)=(6,12)Z Z(1)(1)=1200=1200 X X(2)(2)=(15,15/2)Z Z(2(2)=1200=1200无穷多解无穷多解全部全部解：解：X X=+(1-)(0 1)6 15 12 15/27/29/20221.6.4 无穷多最优解88退化解：退化解：有时存在两个以上相同的最小值，从而使下一个表的有时存在两个以上相同的最小值，从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。基可行解中出现一个或多个基变量等于零的退化解。min0iikiikbaa 7/29/20221.6.5 退化和循环89例例:max z=10 x1
44、+12x23x1+4x2 64x1+x2 23x1+2x2 3x1,x2 03x1+4x2+x3=64x1+x2+x4=23x1+2x2+x5=3x1 x5 07/29/20221.6.5 退化和循环90 10 12 0 0 010 12 0 0 0 XB b x1 x2 x3 x4 x5 i i 0 0 x3 6 3 4 1 0 0 3/2 6 3 4 1 0 0 3/20 0 x4 2 4 1 0 1 0 2/12 4 1 0 1 0 2/10 0 x5 3 3 2 0 0 1 3/2 3 3 2 0 0 1 3/2 0 10 12 0 0 0 0 10 12 0 0 0 12 12 x2
45、 3/2 3/4 1 1/4 0 0 23/2 3/4 1 1/4 0 0 20 0 x4 1/2 13/4 0 -1/4 1 0 2/131/2 13/4 0 -1/4 1 0 2/130 0 x5 0 0 3/2 0 -1/2 0 1 03/2 0 -1/2 0 1 0 18 1 0 -3 0 0 18 1 0 -3 0 0 12 12 x2 3/2 0 1 1/2 0 -1/23/2 0 1 1/2 0 -1/20 0 x4 1/2 0 0 5/6 1 -13/6 1/2 0 0 5/6 1 -13/6 10 10 x1 0 1 0 -1/3 0 2/30 1 0 -1/3 0 2/3
46、18 0 0 -8/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/29/20221.6.5 退化和循环921234123412343123431min150645011subject to60904251190302501,0zxxxxxxxxxxxxxx xxx死循环的例子：死循环的例子：1.6.5 退化和循环093和初始基可行解相同1.6.5 退化和循环094 为避免出现计算循环，可采用为避免出现计算循环，可采用Bland(1974)准则准
47、则:(1)当存在多个当存在多个 时，始终选取下标值为最小时，始终选取下标值为最小的变量作为换入变量；的变量作为换入变量；0j(2)当计算当计算 值出现两个或以上相同的最小比值时，值出现两个或以上相同的最小比值时，始终选取下标值为最小的变量作为换出变量；始终选取下标值为最小的变量作为换出变量；7/29/20221.6.5 退化和循环95前例中，在第前例中，在第5张表时我们运用张表时我们运用Bland法则，得：法则，得：7/29/20221.6.5 退化和循环961.7 应用举例7/29/20221.7 应用举例 (1)要求解问题的目标能用数值指标来表示，并且目标函数 z=f(x)为线性函数；(2
48、)存在着多种可选方案；(3)要达到的目标是在一定约束条件下实现的,这些约束条件可用线性等式或不等式来描述。一般来讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划的模型。下面举例说明线性规划在经济管理等方面的应用。987/29/20221.7.1 风险控制问题997/29/20221.7.1 风险控制问题该问题可以表述为如下的线性规划模型：该问题可以表述为如下的线性规划模型：1007/29/20221.7.1 风险控制问题目标函数是带有绝对值的特殊线性规划问题，如何将其转换成一般的线性规划模型呢？101例例1.11 某某工厂生产三种不同型号的润滑油工厂生产三种不同型号的润滑油A，B和和C
49、，表，表1.28是工厂刚刚接到的一季度生产订单。已知是工厂刚刚接到的一季度生产订单。已知每月生产三种润每月生产三种润滑油的单位成本如表滑油的单位成本如表1.29所示，生产单位润滑油所需的工所示，生产单位润滑油所需的工时分别为时分别为1，0.8和和1.5（小时（小时/吨）。该工厂每个月的最大生吨）。该工厂每个月的最大生产能力均为产能力均为900（小时）。若生产出来的润滑油当月不交货，（小时）。若生产出来的润滑油当月不交货，每吨库存每吨库存1个月的存储费分别为个月的存储费分别为220，200和和160元元。请为该厂设计一个既保证完成订单，又使一季度生产和库存总成本最低的生产计划。7/29/2022
50、1.7.2 生产库存问题102表表1.28 一季度生产订单（单位：吨）一季度生产订单（单位：吨）7/29/20221.7.2 生产库存问题表表1.29 一季度单位生产成本（单位：元一季度单位生产成本（单位：元/吨）吨）103目标函数目标函数：总总成本由生产成本和库存成本两部分成本由生产成本和库存成本两部分构成：构成：7/29/20221.7.2 生产库存问题104约束条件约束条件：工时工时约束约束各个月生产工时均不超过最大生产能力：各个月生产工时均不超过最大生产能力：交货要求交货要求各个月足以完成订单需求即每月库存量不小于各个月足以完成订单需求即每月库存量不小于0，于是于是有：有：非非负约束负
