运筹帷幄之中

1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线线 性性 规规 划划Linear ProgrammingLinear Programming运运 筹筹 学学 课课 件件第第2页页线线 性性 规规 划划|线性规划问题线性规划问题|可行区域与基本可行解可行区域与基本可行解|单纯形算法单纯形算法|初始可行解初始可行解|对偶理论对偶理论|灵敏度分析灵敏度分析|计算软件计算软件|案例分析案例分析第第3页页线线 性性 规规 划划 问问 题题|线性规划实例线性规划实例 生产计划问题生产计划问题 运输问题运输问题|线性规划模型线性规划模型 一般形式一般形式 规范形式规范形式 标

2、准形式标准形式 形式转换形式转换 概念概念 第第4页页某工厂用三种原料生产三种产品，已知的条件如表某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划所示，试制订总利润最大的生产计划单位产品所需原单位产品所需原料数量（公斤）料数量（公斤）产品产品Q1产品产品Q2产品产品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000单位产品的利润单位产品的利润（千元）（千元）354生生 产产 计计 划划 问问 题题第第5页页问问 题题 分分 析析可控因素：可控因素：每天生产三种产品的数量，分别设为每天生

3、产三种产品的数量，分别设为321,xxx 目标：目标：每天的生产利润最大每天的生产利润最大 利润函数利润函数321453xxx 受制条件：受制条件： 每天原料的需求量不超过可用量：每天原料的需求量不超过可用量： 原料原料1P：15003221 xx 原料原料2P：8004232 xx 原料原料3P：2000523321 xxx 蕴含约束：蕴含约束：产量为非负数产量为非负数 0,321 xxx 第第6页页模模 型型321453maxxxx 15003221 xx s.t. 8004232 xx 2000523321 xxx 0,321 xxx 第第7页页计计 算算 结结 果果 OBJECTIVE

4、 FUNCTION VALUE 2675.000 VARIABLE VALUE REDUCED COST X1 375.000000 0.000000 X2 250.000000 0.000000 X3 75.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 1) 0.000000 1.050000 2) 0.000000 0.625000 3) 0.000000 0.300000 第第8页页运运 输输 问问 题题一一个个制制造造厂厂要要把把若若干干单单位位的的产产品品从从两两个个仓仓库库2 , 1; iAi 发发送送到到零零售售点点4 , 3

5、, 2 , 1; jBj，仓仓库库iA能能供供应应的的产产品品数数量量为为 2 , 1; iai，零零售售点点 jB所所需需的的产产品品的的数数量量为为4 , 3 , 2 , 1; jbj。 假假设设供供给给总总量量和和需需求求总总量量相相等等，且且已已知知从从仓仓库库iA运运一一个个单单 位位产产品品往往jB的的运运价价为为ijc。问问应应如如何何组组织织运运输输才才能能使使总总运运费费 最最iA小小？ 第第9页页问问 题题 分分 析析可控因素可控因素：从仓库：从仓库iA运往运往jB的产品数量的产品数量 设为设为4 , 3 , 2 , 1, 2 , 1; jixij 目标目标：总运费最小：总

6、运费最小 费用函数费用函数 2141ijijijxc 受控条件受控条件： 从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。 由于总供给量等于总需求量，所以都是等号。即由于总供给量等于总需求量，所以都是等号。即 2 , 1;4321 iaxxxxiiiii 4 , 3 , 2 , 1;21 jbxxjjj 蕴含约束蕴含约束：数量非负：数量非负4 , 3 , 2 , 1, 2 , 1; 0 jixij 第第10页页模模 型型min 2141ijijijxc 2 , 1;4321 iaxxxxiiiii s.t. 4 , 3 ,

7、 2 , 1;21 jbxxjjj 4 , 3 , 2 , 1, 2 , 1; 0 jixij 第第11页页一一 般般 形形 式式 qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn,.,2 , 1;,.,2 , 1; 0,.,1;,.,2 , 1;.min221122112211无无限限制制 目标函数目标函数约束条件约束条件第第12页页注注 释释njxj,.,2 , 1; 为待定的为待定的决策变量决策变量， ),(21ncccc 为为价值向量价值向量， njcj,.,2 , 1; 为为价值系数价值系数， ),.,(21mbbbb 为为右端向量

8、右端向量， 矩阵矩阵 为为系数矩阵系数矩阵。 mnmmnnaaaaaaaaaA212222111211第第13页页规规 范范 形形 式式 0.min xbAxtsxc 第第14页页标标 准准 形形 式式 0.min xbAxtsxc 第第15页页概概 念念可行解（或可行点） ：可行解（或可行点） ：满足所有约束条件的向量满足所有约束条件的向量 ),(21nxxxx 可行集（或可行域）可行集（或可行域） ：所有的可行解的全体：所有的可行解的全体 0, xbAxxD 最优解：最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为

9、最优解集合称为最优解集合 DyycxcDxO , 最优值：最优值：最优解的目标函数值最优解的目标函数值 Oxxcv , 第第16页页模模 型型 转转 换换v约束转换约束转换v实例实例令令自自由由变变量量 jjjxxx，其其中中 jjxx ,为为非非负负变变量量 求最大可以等价成求负的最小求最大可以等价成求负的最小 xcxc minmax v目标转换目标转换v变量转换变量转换第第17页页约约 束束 转转 换换v不等式变等式不等式变等式v不等式变不等式不等式变不等式ininiibxaxaxa 2211 ininiibxaxaxa 2211 ininiibxaxaxa 2211 v等式变不等式等式变

10、不等式第第18页页不不 等等 式式 变变 等等 式式ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 或或 ininiibxaxaxa 2211 0,2211 iiininiisbsxaxaxa 松弛变量松弛变量剩余变量剩余变量第第19页页不等式变不等式不等式变不等式ininiibxaxaxa 2211 ininiibxaxaxa 2211 或或 ininiibxaxaxa 2211 ininiibxaxaxa 2211 第第20页页 例例2.1.3 把问题转化为标准形式把问题转化为标准形式 052222.21max1212121xxxxxxxtsxxz

11、7 , 6 , 5 , 4 , 3 , 1; 05)(2)(22)(2.)(min743164315431431ixxxxxxxxxxxxxtsxxxzi 第第21页页可行区域与基本可行解可行区域与基本可行解 | 图解法图解法 |可行域的几何结构可行域的几何结构| 基本可行解与基本定理基本可行解与基本定理第第22页页图图 解解 法法对于只有两个变量的线性规划问题可以用图解法求解：对于只有两个变量的线性规划问题可以用图解法求解： 变量用直角坐标系中的点表示变量用直角坐标系中的点表示 约束条件用坐标系中的半空间或直线的交表示约束条件用坐标系中的半空间或直线的交表示 可行区域是一个凸多面体可行区域是

12、一个凸多面体 目标函数用一组等值线表示，沿着增加或减少的方向目标函数用一组等值线表示，沿着增加或减少的方向 移动，与可行域最后的交点就是最优解。移动，与可行域最后的交点就是最优解。 第第23页页例例2.2.1 解线性规划解线性规划 2221 xx 2221 xx 521 xx 最优解（最优解（1，4） 052222.max121212121xxxxxxxtsxxz第第24页页当当目目标标函函数数该该边边后后，等等值值线线的的方方向向会会发发生生改改变变， 如如果果等等值值线线与与某某个个约约束束对对应应的的函函数数直直线线平平行行， 则则该该函函数数值值线线上上的的所所有有可可行行解解都都是是

13、最最优优解解 2221 xx 2221 xx 最最优优解解（1，4） 521 xx第第25页页注注 释释可能出现的情况可能出现的情况：| 可行域是空集可行域是空集| 可行域无界无最优解可行域无界无最优解| 最优解存在且唯一，则一定在顶点上达到最优解存在且唯一，则一定在顶点上达到| 最优解存在且不唯一，一定存在顶点是最优解最优解存在且不唯一，一定存在顶点是最优解第第26页页可行域的几何结构可行域的几何结构|基本假设基本假设|凸集凸集|可行域的凸性可行域的凸性第第27页页基基 本本 假假 设设考虑虑线线性性规规划划的的标标准准形形式式 其其中中nmmnRARbRcx ,，并并且且假假定定可可行行域

14、域 0, xbAxRxDn不不空空，系系数数矩矩阵阵A是是行行 满满秩秩的的，mAr )(，否否则则的的话话可可以以去去掉掉多多余余约约束束。 0.minxbAxtsxc第第28页页凸凸 集集定义定义 2.2.1：设：设nRS 是是n维欧氏空间的点集，若对任意维欧氏空间的点集，若对任意 SySx ,的和任意的和任意1 , 0 都有都有 就称就称S是一个是一个凸集凸集。 定理定理 2.2.1 线性规划的可行域线性规划的可行域0, xbAxxD是凸集是凸集 定理定理 2.2.2 任意多个凸集的交还是凸集任意多个凸集的交还是凸集 Syx )1( 第第29页页可可 行行 域域 的的 凸凸 性性超平面超

15、平面 bxaRxHn 半空间半空间 bxaRxHn ；bxaRxHn 多面凸集多面凸集 ,.,2, 1;,.,2 , 1;qpppibxapibxaRxSiiiin 定义定义 2.2.2：设：设S为凸集为凸集Sx ，如果对任意，如果对任意Szy ,和和10 ， 都有都有zyx)1( ,则称则称 x 为为 S 的的顶点顶点。 第第30页页问问 题题1.可可行行域域顶顶点点的的个个数数是是否否有有限限？ 2.最最优优解解是是否否一一定定在在可可行行域域顶顶点点上上达达到到？ 3.如如何何找找到到顶顶点点？ 4.如如何何从从一一个个顶顶点点转转移移到到另另一一个个顶顶点点? 第第31页页基基 本本

16、可可 行行 解解 与与 基基 本本 定定 理理|定义定义|基本定理基本定理|问题问题第第32页页基基 本本 可可 行行 解解 定定 义义令令),(NBA ， x=(Bx,Nx)。 bAx 分块分块 bNxBxNB 左乘左乘1 B bBNxBxNB11 即即 NBNxBbBx11 Nx=0 01bBx 第第33页页定义定义2.2.2： 设设B是秩为是秩为m的约束矩阵的约束矩阵A的一个的一个 m阶满秩阶满秩子方阵，则称子方阵，则称B为一个为一个基基；B中中 m个线性无关的列向量称个线性无关的列向量称为为基向量基向量，变量，变量 x中与之对应的中与之对应的 m个分量称为个分量称为基变量基变量，其，其

17、余的变量为余的变量为非基变量非基变量， 令所有的非基变量取值为， 令所有的非基变量取值为 0， 得到的解， 得到的解 01bBx称为相应于称为相应于B的的基本解基本解。当当01 bB则称基本解为则称基本解为基本可行解基本可行解，这时对应的基阵，这时对应的基阵B为为可行基可行基。 如果如果01 bB则称该则称该基可行解为非退化的基可行解为非退化的，如果一个线，如果一个线性规划的所有基可行解都是非退化的则称该性规划的所有基可行解都是非退化的则称该规划为非退化规划为非退化的的。 第第34页页例例 考虑问题：考虑问题： 5 , 4 , 3 , 2 , 1; 052222.min52142132121j

18、xxxxxxxxxxtsxxzj 系数矩阵系数矩阵 100110102100112A 基阵为基阵为 1000100011B 1010110022B 对应的基解分别为对应的基解分别为 )5 , 2 , 2 , 0 , 0(1x 和和 )6 , 3 , 0 , 0 , 1(2x，其中，其中 x1 为基本可行解，为基本可行解， x2 不是基本可行解。不是基本可行解。 第第35页页基基 本本 定定 理理定定理理2.2.3 可可行行解解 x是是基基本本可可行行解解的的充充要要条条件件是是它它的的正正分分量量所所对对应应的的矩矩阵阵A中中列列向向量量线线性性无无关关。 定定理理 2.2.4 x是是基基本本

19、可可行行解解的的充充要要条条件件是是 x是是可可行行域域 D的的顶顶点点。 定定理理 2.2.5 一一个个标标准准的的 LP 问问题题如如果果有有可可行行解解， 则则至至少少有有一一个个基基本本可可行行解解 定定理理 2.2.6 一一个个标标准准的的 LP 问问题题如如果果有有有有限限的的最最优优值值， 则则一一定定存存在在一一个个基基本本可可行行解解是是最最优优解解。 第第36页页问问 题题1 基本可行解不一定都是最优解，基本可行解不一定都是最优解， 最优解也不一定都是基本解最优解也不一定都是基本解 2 如果有两个基本可行解是最优解，如果有两个基本可行解是最优解， 则两解的凸组合也都是最优解

20、。则两解的凸组合也都是最优解。 3 如果最优解不唯一，如果最优解不唯一， 则会有多个基本可行解是最优解，它们必然在同一个面上。则会有多个基本可行解是最优解，它们必然在同一个面上。 4行解个数有限，可以在基可行解中寻找最优解。行解个数有限，可以在基可行解中寻找最优解。 剩余的问题是如何判断一个基可行解是最优解，剩余的问题是如何判断一个基可行解是最优解， 如果不是则如何从一个基可行解转到另一个基可行解。如果不是则如何从一个基可行解转到另一个基可行解。 第第37页页单单 纯纯 形形 算算 法法|理论方法理论方法|算法步骤算法步骤|单纯形表单纯形表|算例算例第第38页页理理 论论 方方 法法定定理理

21、2.3.1（最最优优性性准准则则）如如果果0 ，则则基基可可行行解解x为为原原问问题题的的最最优优解解。 定定理理 2.3.2 如如果果向向量量 的的第第k个个分分量量0 k ，而而向向量量01 kAB，则则原原问问题题无无界界。 定定理理 2.3.3 对对于于非非退退化化的的基基本本可可行行解解x， 若若向向量量 的的第第k个个分分量量0 k ，而而向向量量.1kAB 至至少少有有一一个个正正分分量量，则则可可以以找找到到一一个个新新的的基基本本可可行行解解x 使使得得xcxc 。 第第39页页定理定理2.3.1 给定一个非退化的基可行解给定一个非退化的基可行解 x，对应的可行基为，对应的可

22、行基为 B，则等式约束变为：，则等式约束变为： bBNxBxNB11 典式典式 NBNxBbBx11 目标函数目标函数NNBBxcxcxc NNNBxcNxBbBc )(11 NNBBxcNBcbBc)(11 令令 NBNcNBc1 ，0 B ，则则xbBcxcB 1 规划等价于规划等价于 0.min111xbBNxBxtsxbBcNBB 第第40页页定定 理理 2.3.2令令 )0 , 0 , 1 , 0 , 0 ,(1kkABb其基变量取值为其基变量取值为。非基变量中第非基变量中第 k 个个 非基变量取值为非基变量取值为 1，其它为，其它为 0。令令kkbxxx ，其中，其中0 kx。由于

23、由于0 x， 可知对任意可知对任意0 kx，0 x，且满足，且满足bBNxBxNB11 和和xcxc 。 当当 x时，时， kkxxcxc 。 第第41页页定定 理理 2.3.3 令令 )0 , 0 , 1 , 0 , 0 ,(1kkABb其其基基变变量量取取值值为为。非非基基变变量量中中第第 k 个个 非非基基变变量量取取值值为为 1，其其它它为为 0。令令kkbxxx ，其其中中0 kx。为为了了保保证证 0 kkbxxx，即即要要求求对对于于.1kAB 的的正正分分量量0)(1 ikikABa，满满足足 0 kikixab，其其中中iibBb)(1 。因因而而kikixab /， 令令,

24、.,2 , 1, 0/minmiaabikiki ，令令kbxx 则则显显然然 x是是个个可可行行解解。 在在原原基基阵阵中中以以第第 k 列列替替代代第第 i 列列，则则显显然然所所得得子子阵阵可可逆逆，所所以以 x是是个个基基可可 行行解解。其其对对应应的的目目标标函函数数值值xcxcxck 。 第第42页页算算 法法 步步 骤骤step1 找找一一个个初初始始可可行行基基 step2 求求出出典典式式和和检检验验数数 step3 求求,.,2 , 1maxnjjk step4 如如果果0 k 则则该该基基可可行行解解就就是是最最优优解解停停止止；否否则则转转 step5； step5 如

25、如果果01 kAB，则则问问题题无无最最优优解解，停停止止；否否则则转转 step6 step6 求求rkrikikiabmiaab/,.,2 , 1, 0/min step7 以以kA替替代代rA得得到到一一个个新新的的基基，转转 step2； 第第43页页单单 纯纯 形形 表表一般假设当前的基一般假设当前的基),.,(21mAAAB 对应的单纯形表为对应的单纯形表为 1x rx mx 1mx kx nx 1 11 ma ka1 na1 1 1rma rka rna 1 1mma mka mna 1b rb mb 第第44页页如如果果kx为为入入基基变变量量，rx为为出出基基变变量量，则则经

26、经过过变变换换单单纯纯形形表表为为 1x rx mx 1mx kx nx 1 ra1 11ma 0 na1 1/rka 1rma 1 rna mra 1 1mma 0 mna 1b rb mb 其其中中rkikrjijijaaaaa/ kjrimi ,.,2 , 1;rkrjrjaaa/ ， rkrrabb/ ，rkiikiiababb/ 。 第第45页页目目标标函函数数NNBBxcNBcbBcz)(11 等等价价于于 bBcxcNBczBNNB11)( 由由于于0 B ， NBNcNBc1 ，所所以以bBcxzB1 。把把 Z 看看成成变变量量在在 单单纯纯形形表表中中加加上上一一列列，同同

27、时时加加上上一一行行描描述述方方程程bBcxzB1 ，则则可可以以 得得到到新新的的单单纯纯形形表表： Z 1x rx mx 1mx kx nx 1 0 0 0 1m k n bBcB1 1 11 ma ka1 na1 1 1rma rka rna 1 1mma mka mna 1b rb mb 第第46页页当当进进行行转转换换时时只只需需要要把把k 转转换换成成 0 对对应应其其它它位位置置等等价价变变换换即即可可。 z 1x rx mx 1mx kx nx 1 0 -k/rka 0 1m 0 n bBcB1 1 ra1 11ma 0 na1 1/rka 1rma 1 rna mra 1 1

28、mma 0 mna 1b rb mb 其其中中rkjrjjjaa/ ；rkkrBBabbBcbBc/11 。 第第47页页算算 例例例例 2.3.1 求解问题求解问题 5,.,2 , 1; 021322.2min53243232132jxxxxxxxxxxtsxxzj 第第48页页初初 始始 单单 纯纯 形形 表表以以1x、4x和和5x为基变量就可以得到初始基可行解为基变量就可以得到初始基可行解 )2 , 1 , 0 , 0 , 2(， 其对应的单纯形表为其对应的单纯形表为 1x 2x 3x 4x 5x 1 -2 1 -2 1 1 -3 1 1 -1 1 2 1 2 第第49页页迭迭 代代 1

29、由于由于012 ，所以该基可行解不是最优解，同时系数矩阵该列有大于，所以该基可行解不是最优解，同时系数矩阵该列有大于 0的元素，所以取的元素，所以取2x为入基变量。计算为入基变量。计算1,min1211 ，所以取第二个约束，所以取第二个约束对应的基变量对应的基变量4x为出基变量，就可以得到一个新的基可行解，在上表中为出基变量，就可以得到一个新的基可行解，在上表中把把2x对应的列变成单位向量， 系数矩阵第对应的列变成单位向量， 系数矩阵第 2 行对应的元素为行对应的元素为 1， 则可以得， 则可以得到该基可行解的单纯形表到该基可行解的单纯形表 1x 2x 3x 4x 5x 0 1 -1 -1 1

30、 0 -5 2 1 -3 1 0 2 -1 1 4 1 1 第第50页页迭迭 代代 2由由于于013 ，所所以以该该基基可可行行解解不不是是最最优优解解，同同时时系系数数矩矩阵阵该该列列有有大大于于 0的的元元素素，所所以以取取3x为为入入基基变变量量。计计算算21 ，所所以以取取第第 3 个个约约束束对对应应的的基基变变量量5x为为出出基基变变量量，就就可可以以得得到到一一个个新新的的基基可可行行解解，在在上上表表中中把把3x对对应应的的列列变变成成单单位位向向量量，系系数数矩矩阵阵第第 3 行行对对应应的的元元素素为为 1，则则可可以以得得到到该该基基可可行行解解的的单单纯纯形形表表： 1

31、x 2x 3x 4x 5x 0 0 -1/2 -1/2 -3/2 1 0 -5 -1/2 5/2 1 0 -1/2 3/2 0 1 -1/2 1/2 13/2 5/2 1/2 第第51页页由于检验数都小于等于由于检验数都小于等于 0，所以该基可行解就是最优解，所以该基可行解就是最优解， 对应的最优解为对应的最优解为)0 , 0 , 2/1 , 2/5 , 2/13(，最优值为，最优值为-3/2。 注：注： 1. 该算法在实际应用中非常有效，被广泛采用，该算法在实际应用中非常有效，被广泛采用， 但在理论上不是多项式时间算法。但在理论上不是多项式时间算法。 2. 现在还有待解决的问题是如何给出初始

32、基可行现在还有待解决的问题是如何给出初始基可行 解以及出现退化的时候如何处理。解以及出现退化的时候如何处理。 第第52页页初初 始始 解解|两阶段法两阶段法|大大M法法|说明说明第第53页页两两 阶阶 段段 法法|基本思想基本思想 第一阶段第一阶段：通过求解辅助问题的最优基可行通过求解辅助问题的最优基可行 解得到原问题的初始基可行解。解得到原问题的初始基可行解。 第二阶段第二阶段：求原问题的最优解求原问题的最优解|算例算例第第54页页辅辅 助助 问问 题题设设原原问问题题为为 ( 2.4.1) 0.minxbAxtsxc 不不妨妨假假设设0 b，如如果果某某一一个个元元素素小小于于 0，该该方

33、方程程两两边边乘乘于于-1 后后则则可可以以使使右右端端数数变变成成正正数数。考考虑虑如如下下问问题题 （2.4.2） 0, 0.min1aamnniixxbxAxtsxg 其其中中 ),.,(21mnnnaxxxx 第第55页页原原 辅辅 助助 题题 问问 与与 题题 的的 关关 系系1. 显然如果原问题显然如果原问题( 2.4.1)有可行解，则规划有可行解，则规划( 2.4.2)的最优值为的最优值为 0，反之亦然。，反之亦然。 2由于由于0 b，所以以，所以以 ),.,(21mnnnaxxxx为基变量，就可以得到规划（为基变量，就可以得到规划（2.4.2）的初始基可行解的初始基可行解 ),

34、 0(b。 3规划（规划（2.4.2）有可行解）有可行解 ), 0(b，同时，同时0 ax，所以，所以01 mnniix。即问题的目标函数有下界，即问题的目标函数有下界，所所以该问题一定有最优解。以该问题一定有最优解。 4因此我们可以首先求规划因此我们可以首先求规划( 2.4.2)的最优基可行解的最优基可行解),(axx，如果最优值为，如果最优值为 0，则，则0 ax，所以，所以x是问题是问题( 2.4.1)的可行解。的可行解。由于由于),(axx是规划（是规划（2.4.2）的基可行解，所以）的基可行解，所以其非零分量对应系数矩阵的列向量线性无关。其非零分量对应系数矩阵的列向量线性无关。所以所

35、以x的非零分量对应的系数矩阵的列的非零分量对应的系数矩阵的列向量也线性无关，所以向量也线性无关，所以x是问题是问题( 2.4.1)的基可行解。的基可行解。在规划在规划（2.4.2） ，我们称） ，我们称ax为人工变为人工变量。量。 第第56页页求求 辅辅 助助 问问 题题 的的 三三 种种 情情 况况101 mnniix且且ax为为非非基基变变量量，则则此此时时x是是问问题题( 2.4.1)的的基基可可行行解解， 且且基基变变量量不不变变。在在最最优优基基可可行行解解的的单单纯纯形形表表里里删删除除 ax对对应应的的列列， 同同时时计计算算出出检检验验数数就就可可以以得得到到原原问问题题的的单

36、单纯纯形形表表。 201 mnniix且且ax中中有有部部分分变变量量为为基基变变量量，此此时时x是是问问题题( 2.4.1)的的基基 可可行行解解，不不同同的的是是基基变变量量会会有有些些改改变变。 301 mnniix，则则原原问问题题没没有有可可行行解解。 第第57页页算算 例例例例 2.4.1 求解求解 如果以如果以4x、5x为基变量，则可以得到该问题的基解为基变量，则可以得到该问题的基解 )1, 2, 0 , 0 , 0(， 不是可行解，而其第一个基可行解不能直接给出，下面用两阶段法求解。不是可行解，而其第一个基可行解不能直接给出，下面用两阶段法求解。 5 , 4 , 3 , 2 ,

37、 1;1226.215min5321432131jxxxxxxxxxtsxxzj第第58页页第第 1 阶阶 段段首先引入人工变量，考虑问题首先引入人工变量，考虑问题 以以6x和和7x为基变量可得其第一个基可行解为基变量可得其第一个基可行解 )1 , 2 , 0 , 0 , 0 , 0 , 0(， 其对应的单纯形表为其对应的单纯形表为 7 , 6 , 5 , 4 , 3 , 2 , 1;1226.min753216432176jxxxxxxxxxxxtsxxzj第第59页页第第 1 阶阶 段段 1x 2x 3x 4x 5x 6x 7x -5 -21 0 2 8 -1 -1 3 1 -1 6 -1

38、 1 1 1 2 -1 1 2 1 由于由于083 ，所以该基可行解不是最优解，同时系数矩阵该列有大于，所以该基可行解不是最优解，同时系数矩阵该列有大于 0 的的元素，所以取元素，所以取3x为入基变量。为入基变量。计算计算622162,min ，所以取第，所以取第 1 个约束对应个约束对应的基变量的基变量6x为出基变量， 就可以得到一个新的基可行解， 在上表中把为出基变量， 就可以得到一个新的基可行解， 在上表中把3x对应对应的列变成单位向量，系数矩阵第的列变成单位向量，系数矩阵第 1 行对应的元素为行对应的元素为 1， 则可以得到该基可行解的单纯形表则可以得到该基可行解的单纯形表 第第60页

39、页第第 1 阶阶 段段1x 2x 3x 4x 5x 6x 7x -3/2 -7/2 -7/2 21/6 7 2/3 4/3 1/3 -1 -4/3 1/3 1/6 -1/6 1 -1/6 1/6 2/3 4/3 1/3 -1 -1/3 1 1/3 1/3 由于由于03/42 ，所以该基可行解不是最优解，同时系数矩阵该，所以该基可行解不是最优解，同时系数矩阵该 列有大于列有大于 0 的元素，所以取的元素，所以取 x2为入基变量。为入基变量。计算计算3431/ ，所以，所以 取第取第 2 个约束对应的基变量个约束对应的基变量7x为出基变量，就可以得到一个新的为出基变量，就可以得到一个新的 基可行解

40、，在上表中把基可行解，在上表中把 x2对应的列变成单位向量，系数矩阵第对应的列变成单位向量，系数矩阵第 2 行对应的元素为行对应的元素为 1， 则可以得到该基可行解的单纯形表则可以得到该基可行解的单纯形表 第第61页页第第 1 阶阶 段段1x 2x 3x 4x 5x 6x 7x 1/4 -21/8 -21/8 21/8 21/8 63/8 -1 -1 0 1/4 1 -1/8 -1/8 1/8 1/8 1/2 1 1/4 -3/4 -1/4 3/4 3/8 1/4 由于检验数都小于等于由于检验数都小于等于 0，所以对应的基可行解就是辅助问题，所以对应的基可行解就是辅助问题 的最优解，最优值为的

41、最优解，最优值为 0，且人工变量都是非基变量，所以得到，且人工变量都是非基变量，所以得到 原问题的基可行解，对应的基变量为原问题的基可行解，对应的基变量为 x2和和 x3， 对应的单纯形表为对应的单纯形表为 第第62页页第第 1 阶阶 段段 1x 2x 3x 4x 5x 1/4 -21/8 -21/8 63/8 1/4 1 -1/8 -1/8 1/2 1 1/4 -3/4 3/8 1/4 第第63页页第第 2 阶阶 段段由于由于04/11 ，所以该基可行解不是原问题最优解，同时，所以该基可行解不是原问题最优解，同时 系数矩阵该列有大于系数矩阵该列有大于 0 的元素，所以取的元素，所以取 x1为

42、入基变量。计算为入基变量。计算 214121414183/,/min ，所以取第，所以取第 2 个约束对应的基变量个约束对应的基变量 x2为为 出基变量，就可以得到一个新的基可行解，在上表中把出基变量，就可以得到一个新的基可行解，在上表中把 x1对对 应的列变成单位向量，系数矩阵第应的列变成单位向量，系数矩阵第 2 行对应的元素为行对应的元素为 1，则，则 可以得到该基可行解的单纯形表可以得到该基可行解的单纯形表 1x 2x 3x 4x 5x -1/2 -11/4 -9/4 31/4 -1/2 1 -1/4 1/4 1 2 1/2 -3/2 1/4 1/2 由于检验数都小于等于由于检验数都小于

43、等于 0，所以对应的基可行解就是原问，所以对应的基可行解就是原问 题的最优解，最优值为题的最优解，最优值为 31/4，对应的最优解为，对应的最优解为 ) 0 , 0 , 4/ 1 , 0 , 2/ 1 (。 第第64页页大大 M 法法求解辅助问题求解辅助问题 当当 M 为足够大的正数时其最优解对应的人工变量为足够大的正数时其最优解对应的人工变量0 ax，从从 而最优解对应于原问题的可行解，且目标函数值相等；而最优解对应于原问题的可行解，且目标函数值相等；同时同时 原问题的任意可行解原问题的任意可行解 x 对应于辅助问题的可行解对应于辅助问题的可行解 )0 ,(x，且目且目 标函数值相等。标函数

44、值相等。所以两个规划最优值相等，且辅助问题所以两个规划最优值相等，且辅助问题的最的最 优解优解 )0 ,(x对应可得原问题的最优解对应可得原问题的最优解 x。因此只需求解辅因此只需求解辅助问助问 题题就可求得原问题的最优解。就可求得原问题的最优解。 0, 0.min1aamnniixxbxAxtsxMxcz第第65页页说说 明明(1) 退化问题的处理退化问题的处理 摄动方法、字典序方法和摄动方法、字典序方法和 Bland 反循环方法反循环方法 (2) 修正的单纯形算法修正的单纯形算法 (3) 特殊问题的处理特殊问题的处理 运输问题、变量有界线性规划问题等运输问题、变量有界线性规划问题等 第第6

45、6页页对对 偶偶 理理 论论|对偶规划对偶规划|对偶理论对偶理论|对偶单纯形算法对偶单纯形算法第第67页页对对 偶偶 规规 划划|标准形式线性规划的对偶规划标准形式线性规划的对偶规划|规范形式线性规划的对偶规划规范形式线性规划的对偶规划|一般形式线性规划的对偶规划一般形式线性规划的对偶规划|实例实例第第68页页标准形式的对偶规划标准形式的对偶规划考考虑虑线线性性规规划划的的标标准准形形式式 ( () ) 其其中中nmmnRARbRcx ,。 根根据据单单纯纯形形理理论论，若若x是是最最优优基基可可行行解解， 其其对对应应的的基基阵阵为为 B 则则其其检检验验数数为为01 BBBcBBc ， 0

46、1 NBNcNBc ，同同时时bBxB1 ，0 Nx，最最优优 值值为为bBcxcB1 。如如果果令令1 BcB ，则则有有 0 cA xcb 0.minxbAxtsxc第第69页页同同时时 是是下下列列规规划划的的可可行行解解 ( () ) 对对于于规规划划( () )的的任任意意可可行行解解x x和和规规划划( () ) 的的任任意意可可行行解解 ，由由于于0 x所所以以有有 由由此此可可知知 是是规规划划( () )的的最最优优解解，反反之之亦亦然然。 两两个个规规划划的的最最有有解解之之间间存存在在着着密密切切的的关关系系，通通过过 一一个个规规划划可可以以得得到到另另一一个个规规划划

47、的的最最优优解解。同同时时从从 形形式式上上两两者者之之间间也也有有本本质质的的相相似似，给给定定),(cbA两两 个个规规划划相相伴伴而而存存在在，因因而而称称两两个个规规划划互互为为对对偶偶规规 划划。 cAtsb .maxxcAxb 第第70页页规规 范范 形形 式式 的的 对对 偶偶 规规 划划规规范范形形式式的的线线性性规规划划 0.minxbAxtsxc 0,.minyxbIyAxtsxc 其其对对偶偶规规划划为为 )0 ,(),(.max cIAtsb 0.max cAtsb 第第71页页一般形式的对偶规划一般形式的对偶规划对于一般形式的线性规划对于一般形式的线性规划 通过把其转

48、化为标准形式同样可以得到其对偶规划为通过把其转化为标准形式同样可以得到其对偶规划为： qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn,.,2 , 1;,.,2 , 1; 0,.,1;,.,2 , 1;.min221122112211无无限限制制 mpiqjcAnqjcAtsbijjjj,.,1; 0,.,2 , 1;,.,1;.max 第第72页页实实 例例例例 2.5.1 写出下列规划的对偶规划写出下列规划的对偶规划 5,.,2 , 1;1226.215min5321432131jxxxxxxxxxtsxxj 其对偶规划为其对偶规划为 0

49、0212605.2max2121212121 ts 00212605.2max2121212121 ts 3 , 2 , 1;1226.215min32132131jxxxxxxxtsxxj 第第73页页对对 偶偶 理理 论论定定理理 2.5.1 若若x和和 分分别别是是原原规规划划和和对对偶偶规规划划的的可可行行解解，则则 x和和 分分别别是是原原规规划划和和对对偶偶规规划划的的最最优优解解的的充充要要条条件件是是bxc 。 定定理理 2.5.2 线线性性规规划划的的对对偶偶规规划划的的对对偶偶规规划划是是原原始始规规划划。 定定理理 2.5.3 如如果果一一个个线线性性规规划划有有最最优优

50、解解，则则其其对对偶偶规规划划也也有有最最优优 解解，且且它它们们的的最最优优值值相相等等。 定定理理 2.5.4 给给定定一一个个原原规规划划和和对对偶偶规规划划，则则下下面面三三种种情情况况必必有有其其一一： 1.都都有有最最优优解解 2.都都无无可可行行解解 3.一一个个有有可可行行解解另另一一个个无无界界 定定理理 2.5.5 若若x和和 分分别别是是原原规规划划和和对对偶偶规规划划的的可可行行解解，则则 x和和 分分别别是是原原规规划划和和对对偶偶规规划划的的最最优优解解的的充充要要条条件件是是， mibxaiii,.,2 , 1; 0)( njxAcjj,.,2 , 1; 0)(

51、第第74页页定定 理理 2.5.1对对于于规规划划( () )的的任任意意可可行行解解x和和规规划划( () )的的任任意意可可行行解解 ， 由由于于0 x所所以以有有 如如果果bxc 则则显显然然x和和 分分别别是是原原规规划划和和对对偶偶规规划划的的最最 优优解解。反反之之x是是原原规规划划的的最最优优解解，则则存存在在最最优优基基可可行行解解x， 使使得得 令令1 BcB ，则则有有 所所以以 是是对对偶偶规规划划的的最最优优解解，所所以以 由由此此可可知知 xcAxb xcxc 0 cA xcb bb bxc 第第75页页定定 理理 2.5.2 cAtsb .max 0,.min cy

52、AAtsbb )0 ,(),(.maxbbIAAxtscx 0.maxxbAxbAxtsxc 0.maxxbAxbAxtsxc 0.minxbAxtsxc 第第76页页定定 理理 2.5.5x和和 分别是原规划和对偶规划的最优解的分别是原规划和对偶规划的最优解的充要条件充要条件是是bxc . x和和 分别是原规划和对偶规划的可行解，则分别是原规划和对偶规划的可行解，则 所以所以 xcAxb njxAcjj,.,2 , 1; 0)( bxc mibxaiii,.,2 , 1; 0)( 第第77页页对偶单纯形算法对偶单纯形算法|基本思想基本思想|算法过程算法过程|算例算例第第78页页基基 本本 思

53、思 想想NB1 I0 N 0 B BxNxbBcB101 bB第第79页页单单 纯纯 形形 算算 法法从满足从满足01 bB的基解入手，在保持的基解入手，在保持01 bB 的条件下的条件下寻找满足寻找满足01 cABcB的基解。的基解。 BxNB1 IN 0 B bBcB1 01 bBNx第第80页页对对 偶偶 单单 纯纯 形形同样可以从满足同样可以从满足01 cABcB的基解出发，在保持的基解出发，在保持 01 cABcB的条件下寻找满足的条件下寻找满足01 bB的基解。的基解。 我们称满足我们称满足01 cABcB的基解为的基解为正则解正则解。对偶对偶 单纯形算法单纯形算法就是从正则解出发

54、，从一个正则解调就是从正则解出发，从一个正则解调 整到另一个正则解，直至找到可行的正则解。整到另一个正则解，直至找到可行的正则解。 NB1I0N0BbBcB1bB1BxNx第第81页页正正 则则 解解01 cABcB0 cA 1 BcB 正则解正则解对偶可行解对偶可行解第第82页页正则解的单纯性表正则解的单纯性表nmjjrjrrxabx11xnx2x1mxmx0111mabBcB101m00110nna11mmamna1bmbrx011rmarna0rb第第83页页 nmjjrjrrxabx10:1 rjanjm0 rx规划无可行解规划无可行解;0:100 rjanjm0,/00rrjrjxa

55、bx保持正则性保持正则性第第84页页00/rjjrjjjaa 0/00 rjjra 0 rja0 j 0 rja00/rjjrjjaa 0/min/ rjrjjrkkaaa kx入基变量入基变量第第85页页1xnx2x1mxmx0111 mabBcB1 01 m 00110 n na11 mmamna1bmbrx011 rmarna0 rbkx0 k ka1rkamka第第86页页否否算算 法法 过过 程程初始正则解初始正则解检查可行检查可行是则停止是则停止得最优解得最优解选出基变量选出基变量检查检查是否无可是否无可行解行解是则停止是则停止否否无最优解无最优解选入基变量选入基变量计算典式检验数

56、计算典式检验数第第87页页算算 例例例例：解下列规划解下列规划 首先化为标准形式首先化为标准形式 0,2413.min321321321321xxxxxxxxxtsxxx 0,2413.min5432153214321321xxxxxxxxxxxxxtsxxx第第88页页迭迭 代代1x2x3x4x5x111000311100211411第第89页页迭迭 代代1x2x3x4x5x1110003111002141141411413043121414504304121第第90页页迭迭 代代1x2x3x4x5x0214141411413043121414504304121第第91页页1x2x3x4x5

57、x02141414111013313413213145043041211135139013601320134131133137第第92页页1x2x3x4x5x101331341321311135139013601320134131133137第第93页页灵灵 敏敏 度度 分分 析析|概况概况|改变价值向量改变价值向量|改变右端向量改变右端向量第第94页页概概 况况|信息的不确定性信息的不确定性 信息的变化：信息的变化： 价值向量价值向量市场变化市场变化 右端向量右端向量资源变化资源变化 系数矩阵系数矩阵技术进步技术进步 认知的误差认知的误差|分析方法分析方法 静态分析静态分析- 比较静态分析比

58、较静态分析-动态分析动态分析第第95页页改变价值向量改变价值向量v 一般改变情况一般改变情况 v改变非基变量的价值向量改变非基变量的价值向量 v改变基变量的价值向量改变基变量的价值向量 v算例算例第第96页页一一 般般 改改 变变 Bx Nx RHS Z Bx 0 NBcNBc1 bBcB1 I NB1 bB1 当价值向量改变时在单纯形表里后影响的只是检验数当价值向量改变时在单纯形表里后影响的只是检验数 和目标函数值，其它没有改变，因而只需计算新的检和目标函数值，其它没有改变，因而只需计算新的检 验数和目标函数值验数和目标函数值 和和 如果检验数非正，则原最优解依然是最优解；否如果检验数非正，

59、则原最优解依然是最优解；否则是则是 基可行解。以此为初始基可行解进行迭代就可以求出基可行解。以此为初始基可行解进行迭代就可以求出 新问题的解。新问题的解。 NBNcNBc1 bBcxcB1 第第97页页非非 基基 变变 量量改改变变非非基基变变量量kx的的价价值值向向量量kckc ： kBkcNBc 1 kkkkcc 为为了了使使原原最最优优解解还还是是最最优优解解则则要要求求 0 kkkkcc ，即即kkkcc 第第98页页基基 变变 量量改改变变基基变变量量kx的的价价值值向向量量kc kc ，基基变变量量kx 对对应应的的约约束束为为第第l个个 NkkBcNBccNBc11)0 , 0

60、, 0 , 0( )(1)(lkkTNNBcc lkkBBBbccbcbcbBc)(1 NBNcNBc1 第第99页页算算 例例例例 2.6.1 问题问题 的目标函数中变量的目标函数中变量2x的系数由的系数由 0 变成变成 1. 5 , 4 , 3 , 2 , 1;1226.215min5321432131jxxxxxxxxxtsxxzj第第100页页1x 2x 3x 4x 5x -1/2 -11/4 -9/4 31/4 -1/2 1 -1/4 1/4 1 2 1/2 -3/2 1/4 1/2 由由于于2x为为非非基基变变量量，所所以以系系数数的的改改变变只只影影响响2x的的检检验验数数， 新