四川大学运筹学课件线性规划

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线线 性性 规划规划Linear ProgrammingLinear Programming运运 筹筹 学学 课课 件件第第 1 章章 线线 性性 规规 划划|线性规划问题线性规划问题提出提出|可行区域与基本可行解可行区域与基本可行解|单纯形算法单纯形算法|单纯形法进一步讨论单纯形法进一步讨论1.1 线线 性性 规规 划划 问问 题提出题提出|线性规划例题线性规划例题 生产计划问题生产计划问题 |线性规划模型线性规划模型 一般形式一般形式 规范形式规范形式 标准形式标准形式 形式转换形式转换 概念概念 图解法图解法 1.1.1

2、 线性规划例题线性规划例题某工厂用三种原料生产三种产品，已知的条件如表某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划所示，试制订总利润最大的生产计划单位产品所需原单位产品所需原料数量（公斤）料数量（公斤）产品产品Q1产品产品Q2产品产品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000单位产品的利润单位产品的利润（千元）（千元）354 生生 产产 计计 划划 问问 题题问问 题题 分分 析析可控因素：可控因素：每天生产三种产品的数量，分别设为每天生产三种产品的数量，分别设为321,xxx 目标

3、：目标：每天的生产利润最大每天的生产利润最大 利润函数利润函数321453xxx 受制条件：受制条件： 每天原料的需求量不超过可用量：每天原料的需求量不超过可用量： 原料原料1P：15003221 xx 原料原料2P：8004232 xx 原料原料3P：2000523321 xxx 蕴含约束：蕴含约束：产量为非负数产量为非负数 0,321 xxx 模模 型型321453maxxxx 15003221 xx s.t. 8004232 xx 2000523321 xxx 0,321 xxx 1.1.2 )(0)(,),(.),(.),(.2122112222212111212111无限制 nmnm

4、nmmnnnnxxxbxaxaxabxaxaxabxaxaxatsnnxcxcxczMax 2211min)(或或 一一 般般 形形 式式注注 释释njxj,.,2 , 1; 为待定的为待定的决策变量决策变量， ),(21ncccc 为为价值向量价值向量， njcj,.,2 , 1; 为为价值系数价值系数， ),.,(21mbbbb 为为右端向量右端向量， 矩阵矩阵 为为系数矩阵系数矩阵。 mnmmnnaaaaaaaaaA212222111211 向向 量量 形形 式式 0),(),(max(min)1xbxPcxznjjj mnmmnnnmnaaaaaaaaaPPPbbbbbcccc2122

5、221112112121210,),(系系数数矩矩阵阵：资资源源向向量量：价价值值向向量量： 矩矩 阵阵 形形 式式 0),(),(max(min)xbAxcxz nmnmmnnmnPPPaaaaaaaaaAbbbbbcccc2121222211121121210,),( 系系数数矩矩阵阵：资资源源向向量量：价价值值向向量量：0,.min)(21211122221121112121112211 nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxczMax或 标标 准准 形形 式式 变一般形式为标准形式变一般形式为标准形式v约束转换约束转换v实例实例令令自自

6、由由变变量量 jjjxxx，其其中中 jjxx ,为为非非负负变变量量 求最大可以等价成求负的最小求最大可以等价成求负的最小 xcxc minmax v目标转换目标转换v变量转换变量转换不不 等等 式式 变变 等等 式式ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 或或 ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 松弛变量松弛变量剩余变量剩余变量几几 个个 概概 念念可行解（或可行点） ：可行解（或可行点） ：满足所有约束条件的向量满足所有约束条件的向量 ),(21nxxxx 可行集（或可行域）可行集（或可行

7、域） ：所有的可行解的全体：所有的可行解的全体 0, xbAxxD 最优解：最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合称为最优解集合 DyycxcDxO , 最优值：最优值：最优解的目标函数值最优解的目标函数值 Oxxcv , 图图 解解 法法例例 解线性规划解线性规划 注注 释释解可能出现的情况解可能出现的情况：| 可行域是空集可行域是空集| 可行域无界无最优解可行域无界无最优解| 最优解存在且唯一，则一定在顶点上达到最优解存在且唯一，则一定在顶点上达到| 最优解存在且不唯一，一定存在顶点是最优解最优

8、解存在且不唯一，一定存在顶点是最优解1.2 可行区域与基本可行解可行区域与基本可行解 |可行域的几何结构可行域的几何结构| 基本可行解与基本定理基本可行解与基本定理可行域的几何结构可行域的几何结构|基本假设基本假设|凸集凸集|可行域的凸性可行域的凸性基基 本本 假假 设设凸凸 集集 与与 顶顶 点点基基 本本 可可 行行 解解 与与 基基 本本 定定 理理|定义定义|基本定理基本定理|问题问题第第29页页例例:基本解不一定是可行解基本解不一定是可行解基基 本本 定定 理理证明：由基可行解的定义知，必要性显然成立。证明：由基可行解的定义知，必要性显然成立。充分性：若向量充分性：若向量kppp,2

9、1线性独立，则必有线性独立，则必有mk 当当mk 时，它们恰好构成一个基，从而为相应的时，它们恰好构成一个基，从而为相应的基可行解；当基可行解；当mk 时，则一定能从剩余的列向量时，则一定能从剩余的列向量中取出中取出m-k个与个与kppp,21构成最大的线性独立向量构成最大的线性独立向量组组其对应的解恰为其对应的解恰为x，所以，所以，x是基可行解。是基可行解。证明证明 (1) x不是基可行解，则不是基可行解，则x不是可行域的顶点。不是可行域的顶点。不失一般性，假设不失一般性，假设x的前的前m个分量为正，则有个分量为正，则有 miiibxP1由定理由定理2知，知，mPPP,21线性相关，即存在一

10、组线性相关，即存在一组不全为不全为0的数的数), 2 , 1(mii 使得有使得有02211 mmPPP 上式乘上一个不为上式乘上一个不为0的数的数 02211 mmPPP与与 miiibxP1相加、相减得相加、相减得bPxPxPxmmm )()()(222111bPxPxPxmmm )()()(222111令令TmmxxxX0 , 0),( ,),(),(2211)1( TmmxxxX0 , 0),( ,),(),(2211)2( 的选取保证，对所有的的选取保证，对所有的mi, 2 , 1 有有0 iix所以，所以，CXCX )2()1(,且且)2()1(2121XXX 所以，所以， x不是

11、可行域的顶点不是可行域的顶点(2) x不是可行域的顶点，则不是可行域的顶点，则x不是基可行解。不是基可行解。不失一般性，设不失一般性，设TrxxxX0 , 0 ,21 不是可行域的顶点，所以可以找到可行域内另外不是可行域的顶点，所以可以找到可行域内另外两个不同点两个不同点Y,Z，有，有X=AY+(1-a)Z（0a0,1-a0，故当，故当0 0时，必有时，必有jjjzyx 因为因为 njrjjjjjbxPxP11 njrjjjjjbyPyP11所以所以 njrjjjjjbzPzP11上面两式相减得上面两式相减得 rjjjjPzy10)(因为因为)(jjzy 不全为不全为0，故，故rPPP,21线

12、性相关，即线性相关，即x不是基本可行解。不是基本可行解。1.3 单单 纯纯 形形 算算 法法|算法的三个阶段算法的三个阶段|算法步骤算法步骤|单纯形表单纯形表|算例算例阶阶 段段 1：确定初始基可行解：确定初始基可行解0 .max: xbAxtscxzLP假设问题假设问题引入松弛变量引入松弛变量Tmnnnsxxxx),(21 0, .0max sssxxbIxAxtsxcxz得得则，可设则，可设IB 则，约束变为则，约束变为 则，初始基可行解为则，初始基可行解为 bBxAxBN bxB 则则 0bxxxNB阶阶 段段 2：由一个基可行解到另一个：由一个基可行解到另一个设初始基可行解设初始基可行

13、解Tnxxxx),(0001)0(2 又设前又设前m个坐标非个坐标非0，即，即Tmxxxx)0 , 0 , 0 ,(0001)0(2 因为是基可行解，所以因为是基可行解，所以 miiibxP10若我们总假定有方法使基矩阵是单位矩阵，则上式展若我们总假定有方法使基矩阵是单位矩阵，则上式展开为开为 mnmjmmmnjmnjmnjmmbbbaaaaaaaaabpppppp21,1,2,21,2, 1, 11, 1121100010001mppp,21因为因为 miiijjpap1是基，所以，其余向量可由它是基，所以，其余向量可由它线性表示线性表示01 miiijjpap对上式乘以正数对上式乘以正数

14、0)(1 miiijjpap miiibxP10上式与上式与相加得相加得bppaxmijiiji 10)( 从中可找到另一个满足约束的点从中可找到另一个满足约束的点)0 , 0 ,(0101)1( mjmjaxaxX 要使它成为基可行解，需要满足要使它成为基可行解，需要满足ljlijijiiaxaax000min 0, 00101 mjmjaxax ，且至少有一个取等号。，且至少有一个取等号。又因为，若又因为，若aij0，则条件自然满足，所以，只需取，则条件自然满足，所以，只需取即可。即可。阶阶 段段 3：最优性检验和解的判别：最优性检验和解的判别把基可行解把基可行解)1()0(, XX分别代

15、入目标分别代入目标)()(1)0(10)1(10)0( miijijjmiijiimiiiacczcaxczxcz )(1 miijijjacc 令令（1）当所有的）当所有的0 j 说明：现有顶点的目标函数值说明：现有顶点的目标函数值比相邻各顶点的目标函数值都大，现有顶点对应的基比相邻各顶点的目标函数值都大，现有顶点对应的基可行解即为唯一最优解。可行解即为唯一最优解。（2）当所有的）当所有的0 j 又对某个非基变量又对某个非基变量jx有有0 jjzc则，则，无穷多最优解。无穷多最优解。（3）若存在某个）若存在某个0 j 又又jp无界解。无界解。的所有分量的所有分量0 ija算算 法法 步步 骤

16、骤单纯形表例子单纯形表例子例：例： 0,825943.510max432142132121xxxxxxxxxxtsxxz解：0 x321/5014/51-3/510 x18/512/501/5cjzj010-25x23/2015/14-3/1410 x1110-1/7 2/7cjzj00-5/14-25/14cj10500cBxBbx1x2x3x40 x3934100 x485201cjzj105005858,39min 235258,514521min 2/3, 1, 021 xxj，达到最优解达到最优解 第第52页页单纯形法的矩阵描述单纯形法的矩阵描述0 .max: xbAxtscxzLP

17、考虑问题考虑问题引入松弛变量引入松弛变量Tmnnnsxxxx),(21 0, .0max sssxxbIxAxtsxcxz得得第第53页页设设B是一个是一个可行基可行基，若，若),(),(NBIA则对应于则对应于B的变量向量的变量向量TmBBBBxxxx),(21 则则 NBxxx同时将同时将C也分成两块也分成两块 NBCCC 所以所以,有有 bxxNBNB NNBBNBNBxCxCxxCC 第第54页页所以，所以，LP问题写成问题写成0, )2( . NBNBxxbNxBxts)1( maxNNBBxCxCz 将（将（2）移项后得）移项后得)3( - NBNxbBx 将（将（3）左乘）左乘1

18、 B)4( - 11NBNxBbBx 将（将（4）代入目标（）代入目标（1）得）得)5( )-( 1N1NBBxNBCCbBCz 第第55页页单纯形法进一步讨论单纯形法进一步讨论|两阶段法两阶段法|大大M法法|退化退化说明说明第第56页页为什么要做进一步讨论为什么要做进一步讨论?第第57页页两两 阶阶 段段 法法第一阶段第一阶段：不考虑原问题是否存在基可行解，给原问：不考虑原问题是否存在基可行解，给原问题加入人工变量，并构造只含人工变量的目标函数题加入人工变量，并构造只含人工变量的目标函数w，并要求实现最小化。若求解得并要求实现最小化。若求解得w=0，说明原问题存在基，说明原问题存在基可行解，

19、可进入第二阶段，否，原问题无可行解，停。可行解，可进入第二阶段，否，原问题无可行解，停。第二阶段第二阶段：将第一阶段计算得到的最终表，除去人工：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换成原问题的目标函数系变量，将目标函数行的系数换成原问题的目标函数系数，作为第二阶段的初始表。数，作为第二阶段的初始表。例例算算 例例解解:第一阶段第一阶段 cj0000011cBxBbx1x2x3x4x5x6x70 x4111-2110001x63-4120-1101x71-2010001 Cj-zj6-1-30100 cj00000110 x4103-20100-11x610100-11-

20、20 x31-2010001 Cj-zj0-1001030 x4123001-22-50 x210100-11-20 x31-2010001 Cj-zj0000011所以，所以，w=0第二阶段第二阶段 cj-31100cBxBbx1x2x3x4x50 x4123001-21x210100-11x31-20100 Cj-zj-10001-3x141001/3-2/31x210100-11x390012/3-4/3 Cj-zj0001/31/3大大 M 法法在一个在一个LP问题的约束条件中加入人工变量后，要求人问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量工变量对目标函数取值不受影响，为此假定人工变量在目标函数中的系数为（在目标函数中的系数为（M），这样目标要实现最大），这样目标要实现最大化时，必须把人工变量换出基，否则不能最大化。化时，必须把人工变量换出基，否则不能最大化。采用大采用大 M 法，引入人工变量，构造新的线性规划问题（法，引入人工变量，构造新的线性规划问题（LP）单纯形表如下单纯形表如下例：例：cj-31100MMcBxB