运筹学案例02

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 , 2 , 1;

7、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等式变不等式等式变不等式第第18

10、页页不不 等等 式式 变变 等等 式式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 7 , 6 ,

11、 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 ,，并且假定可行域，并且假定可行域 0, x

14、bAxRxDn不空，系数矩阵不空，系数矩阵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.min52142132121jxxxxxxxxxxtsx

18、xzj 系数矩阵系数矩阵 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页页理理 论论 方方 法法定定理理 2.3.1（最最优优性性准

21、准则则）如如果果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，对应的可行基为，对应的可行基为 B，则等式约束变为

22、：，则等式约束变为： 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。由于由于0 x， 可知对任意可

23、知对任意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 /， 令令,.,2 , 1, 0/mi

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

25、问题题无无最最优优解解，停停止止；否否则则转转 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 1mma 0 mna 1b

28、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由由于于012 ，所所以以

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

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

31、x 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，该该方方程程两两边边乘乘于于-1 后后则则

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

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

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

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

37、432131jxxxxxxxxxtsxxzj第第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 1 1 1 2 -1 1 2 1 由

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

39、 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为出基变量，就可以得到一个新的为出基变量，就可以得到一个新的 基可行解，在上表中把基可行解，在上表中把 x2

40、对应的列变成单位向量，系数矩阵第对应的列变成单位向量，系数矩阵第 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，所以对应的基可行解就是辅助问题，所以对应的基可行解就是辅助问题 的最优解，最优值为的最优解，最优值为 0，且人工变量都是非

41、基变量，所以得到，且人工变量都是非基变量，所以得到 原问题的基可行解，对应的基变量为原问题的基可行解，对应的基变量为 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为入基变量。计算为入基变量。计算 214

42、121414183/,/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 由于检验数都小于等于由于检验数都小于等于 0，所以对应的基可行解就是原问，

43、所以对应的基可行解就是原问 题的最优解，最优值为题的最优解，最优值为 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) 特特殊殊问问题题的的处处理理 运运输输问问题题、变变量量有有界界线线性性规规划划问问题题等等 第第66页页对对 偶偶 理理 论论|对偶规划对偶

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

46、，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 其对偶规划为其对偶规划为 00212605.2max212121212

49、1 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)( 第第74页页定定 理理 2.5.1对对于于规规划划(

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

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

53、1 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,/00rrjrjxabx保持正则性保持正则性第第84页页00/rjjrjjjaa

55、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页页否否算算 法法 过过 程程初始正则解初始正则解检查可行检查可行是则停止是则停止得最优解得最优解选出基变量选出基变量检查检查是否无可是否无可行解行解是则停止是则停止否否无最优解无最优解选入基变量选入基变量计算典式检验数计算典式检验数第第87页页算算 例例例例：解解下下列列规规划划

56、 首首先先化化为为标标准准形形式式 0,2413.min321321321321xxxxxxxxxtsxxx 0,2413.min5432153214321321xxxxxxxxxxxxxtsxxx第第88页页迭迭 代代1x2x3x4x5x111000311100211411第第89页页迭迭 代代1x2x3x4x5x1110003111002141141411413043121414504304121第第90页页迭迭 代代1x2x3x4x5x0214141411413043121414504304121第第91页页1x2x3x4x5x021414141110133134132131450430

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

58、量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 , 0 , 0( )(1)(lkkTNNBcc lkkBBBbccbcbc

60、bBc)(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的的检检验验数数， 新新的的检检验验数数为为2/3102/12222 cc 。由由于于新新检检