运筹与决策之2线性规划-课件.ppt

1、运筹与决策之2线性规划1Question线性规划的概念和建模线性规划的概念和建模线性规划的图解法线性规划的图解法单纯形法基本步骤单纯形法基本步骤计算机软件求解计算机软件求解LP问题（下料优化）问题（下料优化）Case 2:灵敏度分析灵敏度分析(运筹与决策之2线性规划21绪论绪论 Introduction2线性规划线性规划 Linear Programming3运输问题运输问题 Transportation Models 4整数规划整数规划 Integer Programming5网络模型网络模型 Network Models6项目计划项目计划 PERT&CPM7排队论排队论 Queueing

2、Models8 模拟模拟 Simulation 9决策分析决策分析 Decision Theory10多目标决策多目标决策 Multi-objective Decision运筹与决策之2线性规划3l线性规划问题的导出线性规划问题的导出lOR在企业管理的具体应用在企业管理的具体应用例例1、家具厂生产计划问题、家具厂生产计划问题例例3、合理下料问题、合理下料问题l线性规划概念和模型线性规划概念和模型运筹与决策之2线性规划4 产品产品 A B可用资源可用资源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬运工搬运工 0 2 24 利润利润(￥)40 50例例1、家具厂生产计划问题、家具厂生产

3、计划问题A,B 各生产多少各生产多少,可获最大利润可获最大利润?如何建模？如何建模？运筹与决策之2线性规划5产品消耗系数、利润、可用资源产品消耗系数、利润、可用资源A,B 各生产多少各生产多少最大利润最大利润运筹与决策之2线性规划6x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0max Z=40 x1+50 x2解解:设产品设产品A,B产量分别为变量产量分别为变量x1，x2运筹与决策之2线性规划7例例2 2 营养配餐营养配餐求：最低成本的原料混合方案求：最低成本的原料混合方案 原料原料i A B 每单位成本每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1

4、 6 4 2 5 3 8 每单位添每单位添 加剂中维生加剂中维生 12 14 8 素最低含量素最低含量如何建模？如何建模？运筹与决策之2线性规划8解：设每单位添加剂中原料解：设每单位添加剂中原料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)运筹与决策之2线性规划9定义：定义：对于求取一组变量对于求取一组变量 xj(j=1,2,.,n)，使之既，使之既满足线性约束条件，又使具有线性的目满足线性约束条件，又使具有线性的目标函数取得极值的一类

5、最优化问题称为标函数取得极值的一类最优化问题称为线性规划问题。线性规划问题。运筹与决策之2线性规划10l要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数值指标反映l对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择l有影响决策的若干约束条件有影响决策的若干约束条件运筹与决策之2线性规划11l线性规划很容易而有效率地被求解线性规划很容易而有效率地被求解l如果存在最优解，则必能够找到如果存在最优解，则必能够找到l功能强大的敏感性分析（功能强大的敏感性分析（sensitivity analysis）l许多实际问题本质上是线性的许多实际问题本质上是线性的运筹与决策之2线性规

6、划12l决策变量决策变量：向量：向量(x1 xn)T 决策人要决策人要考虑和控制的因素非负考虑和控制的因素非负l约束条件约束条件：线性等式或不等式：线性等式或不等式l目标函数目标函数：Z=(x1 xn)线性式，求线性式，求Z极大或极小极大或极小运筹与决策之2线性规划13一般式一般式max(min)Z=C1X1+C2X2+CnXna11X1+a12X2+a1nXn (=,(=,)b)b1 1a21X1+a22X2+a2nXn (=,(=,)b)b2 2 am1X1+am2X2+amnXn (=,(=,)b)bm mXj j 0(0(j=1,n)运筹与决策之2线性规划14njjjXCZ1max(m

7、in),2,1(0),2,1(1njXmibXajinjjij运筹与决策之2线性规划15l比例性比例性：决策变量变化引起目标的改变：决策变量变化引起目标的改变量与决策变量改变量成正比量与决策变量改变量成正比l可加性可加性：每个决策变量对目标和约束的：每个决策变量对目标和约束的影响独立于其它变量影响独立于其它变量l连续性连续性：每个决策变量取连续值：每个决策变量取连续值l确定性确定性：线性规划中的参数：线性规划中的参数aij,bi,ci为为确定值确定值 运筹与决策之2线性规划16某钢筋架需要某钢筋架需要 长度长度1.5m、2.1m和和 2.9m各各100段段，每根标准钢筋长度为，每根标准钢筋长度

8、为7.4m，问如何，问如何合理下料所需标准钢筋数目最少？合理下料所需标准钢筋数目最少？2.9m 1 2 0 1 0 2.9m 1 2 0 1 0 2.1m 0 0 2 2 1 2.1m 0 0 2 2 1 1.5m 3 1 2 0 3 1.5m 3 1 2 0 3 合计合计 7.4 7.3 7.2 7.1 6.67.4 7.3 7.2 7.1 6.6 料头料头 0 0.1 0.2 0.3 0.80 0.1 0.2 0.3 0.8例例3 3、合理下料问题、合理下料问题运筹与决策之2线性规划17解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根min Z=0.1x2+0.2x3

9、+0.3x4+0.8x5 x1+2x2 +x4 =100 2x3+2x4+x5=100 3x1+x2+2x3 +3x5=100 xi 0(i=1,5)如何正确建模？如何正确建模？运筹与决策之2线性规划18l决策变量缺少整数变量约束决策变量缺少整数变量约束l约束条件为等式约束条件为等式l用余料作为目标函数用余料作为目标函数l下料方式不全（少下料方式不全（少3种下料方式）种下料方式）运筹与决策之2线性规划19解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根min Z=x1+x2+x3+x4+x5+x6+x7+x8 2x1+x2+x3+x4 100 2x2+x3 +3x5+2x

10、6+x7 100 x1+x3+3x4 +2x6+3x7 +4x8 100 xi 0(i=1,8)，且为整数且为整数如何建模？如何建模？运筹与决策之2线性规划20例例4 4、运输问题、运输问题某公司有三个分厂分别供应三个市场，某公司有三个分厂分别供应三个市场，具体生产能力和需求量如下表：具体生产能力和需求量如下表：如何建模？如何建模？市场市场1 市场市场2 市场市场3 产量产量工厂工厂1 2 1 3 50工厂工厂2 2 2 4 30工厂工厂3 3 4 2 10 需求需求 40 15 35运筹与决策之2线性规划21设设xij为为i 工厂运到工厂运到 j市场的产品数量市场的产品数量(i 1，2，3，

11、j 1，2，3)min Z=2x11+x12+3x13+2x21+2x22+4x23+3x31 +4x32+2x33x11+x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11+x21+x31=40 x12+x22+x32=15x13+x23+x33=35 xij 0运筹与决策之2线性规划22例例5 5、连续投资、连续投资1010万元万元lA：从第：从第1年年 到第到第4年每年初要投资，次年末年每年初要投资，次年末回收本利回收本利1.15lB：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大，最大投资投资4万元万元lC：第第2年初投资，到第

12、年初投资，到第5年末回收年末回收1.40，最大，最大投资投资3万元万元lD：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5 5年末总资本最大年末总资本最大如何建模？如何建模？运筹与决策之2线性规划23分析分析 1 2 3 4 5A x1A x2A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D Xik(i=1,2,5;k=A,B,C,D)第第i年初投年初投k项目的资金数项目的资金数max Z=1.15x4A+1.40 x2C+1.25x3B+1.11x5Dx1A+x1D 10 x2A+x2C+x2D=1.11 x1Dx2C 3x3A+x3B+x

13、3D=1.15 x1A+1.11 x2Dx3B 4x4A+x4D=1.15 x2A+1.11 x3Dx5D=1.15 x3A+1.11 x4D xik 0运筹与决策之2线性规划25AX=b (1)X 0 (2)max Z=CX (3)定义定义1 1:满足约束满足约束(1)、(2)的的X=(X1 Xn)T称为称为LP问题的问题的可行解可行解，全部可行解集合称为，全部可行解集合称为可行域。可行域。定义定义2 2:满足满足(3)的可行解称为的可行解称为LP问题的问题的最优解。最优解。运筹与决策之2线性规划26 产品产品 A B 备用资源备用资源 木工木工 1 2 30 油漆工油漆工 3 2 60 搬

14、运工搬运工 0 2 24 利润利润 40 50例例1、家具厂生产计划问题、家具厂生产计划问题A,B 各生产多少各生产多少,可获最大利润可获最大利润?运筹与决策之2线性规划27建立模型建立模型max Z=40X1+50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 ,X2 0 0建模后如何计算？建模后如何计算？运筹与决策之2线性规划28解：解：(1)、确定可行域、确定可行域 X1 0 0 X1=0=0(横轴横轴)X2 0 0 X2=0=0(纵轴纵轴)X1+2X2 30X1+2X2=30两点两点(0,15)、(30,0)2030100102030X2DABC3X1+2X2=60(

15、0,30)(20,0)2X2=24X1运筹与决策之2线性规划29(2)、求最优解、求最优解解：解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2 (0,0)，(10,-8)0203010102030X1X2DABCDABCC点：点：X1+2X2=30 3X1+2X2=60运筹与决策之2线性规划30几何概念几何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交集：约束半平面的交集：凸多边形凸多边形满足一组不等式约束的解满足一组不等式约束的解约束直线的交点约束

16、直线的交点基本解基本解可行域的极点可行域的极点基本可行解基本可行解目标函数等值线：目标函数等值线：一组平行线一组平行线 目标函数值等于一个常目标函数值等于一个常数的解数的解如何对应？如何对应？运筹与决策之2线性规划31（1）用字母表示可行域；）用字母表示可行域；（2）画出目标函数的平行线；）画出目标函数的平行线；（3）注意目标函数的斜率；注意目标函数的斜率；（4）适当的说明语句（包括可行域、最优）适当的说明语句（包括可行域、最优解、目标函数值等）解、目标函数值等）运筹与决策之2线性规划32例例2、图解法、图解法 max Z=40X1+80X2 X1+2X2 30 3X1+2X2 60 2X2

17、24 X1,X2 0 0运筹与决策之2线性规划330Z=40 X1+80X2=0 X1+2X2=30DABCX2X1X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(0 1)求解求解最优解：最优解：BCBC线段线段B B点点C C点点无穷多解无穷多解运筹与决策之2线性规划34X1=6+(1-)15X2=12+(1-)7.5X1=15-9 X2=7.5+4.5 (0 1)X=+(1-)max Z=1200 X1 6 15 X2 12 7.5运筹与决策之2线性规划35无界无界无有限最优解无有限最优解例例3、max Z=2X1+4X2 2X1+X2 8 8-2X1+X2

18、 2X1,X2 0 0Z=0-2X1+X2=28246X22X1+X2=840X1运筹与决策之2线性规划36例例4、maxZ=3X1+2X2-X1-X2 1 1X1,X2 0 0无解无解无可行解无可行解-1X2-1X10运筹与决策之2线性规划37 唯一解唯一解 无穷多解无穷多解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解运筹与决策之2线性规划38AX=b (1)X 0 (2)maxZ=CX (3)概念：概念：1 1 可行解可行解?2 2 可行域可行域?3 3 最优解最优解?运筹与决策之2线性规划39运筹与决策之2线性规划40运筹与决策之2线性规划41运筹与决策之2线性规划42运

19、筹与决策之2线性规划43vEXCEL规划求解规划求解solver的功能：可以解决的功能：可以解决线性规划、线性规划、01规划以及整数线性规划等规划以及整数线性规划等问题。问题。vEXCEL中安装好中安装好“规划求解规划求解”？v（菜单（菜单工具工具加载宏）加载宏）v线性问题、非线性问题，变量限制线性问题、非线性问题，变量限制200个，个，约束条件最多可达约束条件最多可达100个。个。运筹与决策之2线性规划44运筹与决策之2线性规划451 在约束中使用的在约束中使用的运算符运算符有下列有下列5个：个：=大于等于大于等于;int 整数整数;bin 二进制（二进制（0或或1）2 求解中用到下列概念：

20、求解中用到下列概念：目标单元格最大值（最小值）：指满足可变单元格约目标单元格最大值（最小值）：指满足可变单元格约束条件后，单元格可取的最大值（最小值）。束条件后，单元格可取的最大值（最小值）。3 可变单元格可变单元格（目标函数、变量和约束条件）（目标函数、变量和约束条件）例如，问题中例如，问题中B1、D6、D7格由公式构成，分别对应格由公式构成，分别对应模型中的目标函数（如：模型中的目标函数（如：B1=B3*B5+C3*C5）和约）和约束条件；束条件；B5、C5为为“可变单元格可变单元格”，分别对应模型，分别对应模型中的变量。中的变量。4 求解过程（见求解过程（见Excel）运筹与决策之2线性

21、规划46运筹与决策之2线性规划47软件求解下料优化问题软件求解下料优化问题运筹与决策之2线性规划48运筹与决策之2线性规划49lLet S=fraction of the Security Systems project funded by HVClM=fraction of the Market Analysis project funded by HVC 运筹与决策之2线性规划50 运筹与决策之2线性规划51 运筹与决策之2线性规划52运筹与决策之2线性规划53l图解法灵敏度分析图解法灵敏度分析l灵敏度分析：计算机求解灵敏度分析：计算机求解l多于两个变量的情况多于两个变量的情况运筹与决策之

22、2线性规划54l如果在计划实施前或实施中有些因素已发如果在计划实施前或实施中有些因素已发生了改变，则决策者所关心的是目前所执生了改变，则决策者所关心的是目前所执行的计划还行的计划还是不是最优是不是最优？企业应当作出什？企业应当作出什么样的反应，运用灵敏度分析而么样的反应，运用灵敏度分析而不需建立不需建立新的模型。新的模型。l模型中模型中目标函数系数目标函数系数哪个更能影响最优解哪个更能影响最优解。l约束条件的约束条件的右端值变化右端值变化对最优解的影响。对最优解的影响。运筹与决策之2线性规划55l模型参数是粗略的模型参数是粗略的估计值估计值 l获取所需数据必须付出许多的获取所需数据必须付出许多

23、的时间与精力时间与精力l有些因素只有在研究完成后才能精确测量有些因素只有在研究完成后才能精确测量lwhat-ifwhat-if分析表明改变这些决策对结果的分析表明改变这些决策对结果的影响，从而有效指导管理者作出影响，从而有效指导管理者作出最终决策最终决策运筹与决策之2线性规划56A（原材料消耗）（原材料消耗）代表企业的技术状况；代表企业的技术状况；b（资源供应量）（资源供应量）代表企业的资源状况；代表企业的资源状况；C（价值系数）（价值系数）代表企业产品的市场状况；代表企业产品的市场状况；在这些因素（原材料消耗系数、资源供应量、在这些因素（原材料消耗系数、资源供应量、价值系数）不变的情况下企业

24、的最优生产计价值系数）不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值划和最大利润由线性规划的最优解和最优值决定。决定。在生产计划问题的一般形式在生产计划问题的一般形式中，中，A，b，C各代表什么各代表什么标准型标准型 max Z=CX AX=b X 0如何回答？如何回答？运筹与决策之2线性规划57l模型参数是粗略的估计值模型参数是粗略的估计值 l获取所需数据必须付出许多的时间与精力获取所需数据必须付出许多的时间与精力l有些因素只有在研究完成后才能精确测量有些因素只有在研究完成后才能精确测量lwhat-ifwhat-if分析表明改变这些决策对结果的分析表明改变这些决策对结果的

25、影响，从而有效指导管理者作出最终决策影响，从而有效指导管理者作出最终决策运筹与决策之2线性规划581.C(价格系数价格系数)变化的分析变化的分析:最优条件最优条件 CBB-1A C 0.2.增加一个新变量增加一个新变量(例如新产品投产例如新产品投产)的分析的分析:如果最优条件如果最优条件CBB-1Pj-Cj 0满足，不生产满足，不生产;如果满足如果满足CBB-1Pj-Cj 0，新产品生产，新产品生产.3.b(资源量资源量)变化的分析变化的分析:最优条件最优条件B-1b0.4.增加一个新的约束条件的分析：增加一个新的约束条件的分析：最优解满足约束条件，则不变；最优解满足约束条件，则不变；最优解不

26、满足约束条件，则用对偶单纯形法，最优解不满足约束条件，则用对偶单纯形法，目标值变差。目标值变差。运筹与决策之2线性规划59标准型标准型 max Z=CX AX=b X 0(1)、参数、参数A，b，C在什么范围内变动，对当在什么范围内变动，对当前方案无影响？前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对变动，对当前方案影响？当前方案影响？(3)、如果最优方案改变，如何用简便方法求、如果最优方案改变，如何用简便方法求新方案？新方案？运筹与决策之2线性规划60l递减成本（递减成本（CBB-1Pj -Cj）表示使目标函数中表示使目标函数中变量的值为正数时相应目标函数系数

27、的改变变量的值为正数时相应目标函数系数的改变量（最大化问题是增加；最小化问题是减小）量（最大化问题是增加；最小化问题是减小）l当某个变量对应的当某个变量对应的递减成本递减成本0，表示含义？，表示含义？l见见P70 例例3.4.1中图中图3-6的的D产品的递减成本为产品的递减成本为1.15003，表明，表明D的利润应增加的利润应增加1.15003元，元，D才能变为正值。才能变为正值。运筹与决策之2线性规划61经济解释：经济解释：W=yb=(y1 ym)b1bm=b1 y1+b2 y2+bm ymbi：第第 i 种资源的数量种资源的数量yi：对偶价格：对偶价格bi增加增加 bi,其它资源数量不变时

28、其它资源数量不变时,目标函数目标函数的增量的增量 Z=bi yiyi：反映：反映bi 的边际效益的边际效益(边际成本边际成本)运筹与决策之2线性规划62l假设目标为假设目标为maxl对偶价格对偶价格y（dual price）：）：b 的单位改变量的单位改变量所引起的目标函数改变量。所引起的目标函数改变量。l如果如果y的大小与系统内资源对目标的贡献有的大小与系统内资源对目标的贡献有关，是资源的一种估价，关，是资源的一种估价，又称为影子价格又称为影子价格。运筹与决策之2线性规划63对偶价格的准确经济意义与建模有关。对偶价格的准确经济意义与建模有关。情况情况 模型中，目标函数系数模型中，目标函数系数

29、Ci 表示利润时，表示利润时，yi 不是真正的影子价格，只表示资源不是真正的影子价格，只表示资源bi 增加增加1 1单单位时，企业目标增加的净利润。位时，企业目标增加的净利润。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示成本时，表示成本时，yi 是真正的影子价格。是真正的影子价格。运筹与决策之2线性规划64胜利家具厂生产桌子和椅子两种家具。桌子售价胜利家具厂生产桌子和椅子两种家具。桌子售价50元个，椅子售元个，椅子售价价30元个，生产桌子和椅子需要木工和油漆工两种工种。生产一元个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工个桌子需要木工4小时，油漆工小时，油漆

30、工2小时。生产一个椅子需要木工小时。生产一个椅子需要木工3小小时，油漆工时，油漆工1小时。该厂每月可用木工工时为小时。该厂每月可用木工工时为120小时，油漆工工时小时，油漆工工时为为50小时。问该厂如何组织生产才能使每月的销售收入最大？小时。问该厂如何组织生产才能使每月的销售收入最大？资源资源 单耗单耗 产品产品桌子桌子 椅子椅子资源限量资源限量 木工木工 4 3120小时小时 油漆工油漆工 2 1 50小时小时售价售价(元个元个)50 30 运筹与决策之2线性规划65l模型模型1 1：产品：产品A(A(桌子桌子)，B(B(椅子椅子)销售价格发生销售价格发生变化，最优解是否改变？变化，最优解是

31、否改变？l模型模型3 3：如果家具厂木工资源可能发生变化，：如果家具厂木工资源可能发生变化，要使生产计划不变，问木工工时要使生产计划不变，问木工工时b1b1变化范围变化范围如何如何?l模型模型2 2：设计一种新产品柜子：设计一种新产品柜子,售价售价100100元元,单耗木工单耗木工9 9工时、油漆工工时、油漆工3 3工时问是否投产工时问是否投产?l模型模型4 4：若增加约束：若增加约束:每月可用木材量是每月可用木材量是1010立立方米方米,桌子单耗桌子单耗0.40.4立方米立方米,椅子单耗椅子单耗0.30.3立方立方米。如何安排生产米。如何安排生产?l模型模型5 5：如果桌子价格降价：如果桌子

32、价格降价1010，而椅子价格，而椅子价格上涨上涨1010，该问题的最优解是否发生变化？，该问题的最优解是否发生变化？运筹与决策之2线性规划66l对所有变化的目标函数系数，对所有变化的目标函数系数，允许的增允许的增量和允许的减量百分比之和未达到量和允许的减量百分比之和未达到100%100%，最优解就不会改变。最优解就不会改变。l模型模型5 5：如果桌子价格：如果桌子价格降价降价1010，而椅子而椅子价格价格上涨上涨1010，如何？如何？目标式目标式系数系数允许的允许的增量增量允许的允许的减量减量5010101010307.57.55 5运筹与决策之2线性规划67l图解法灵敏度分析图解法灵敏度分析

33、（参见教材（参见教材P57P57）l应用应用ExcelExcel的灵敏度分析的灵敏度分析l应用应用MS6.0MS6.0的灵敏度分析的灵敏度分析运筹与决策之2线性规划68运筹与决策之2线性规划69分析：找出原问题的对偶解，分析：找出原问题的对偶解，利用机会成本利用机会成本C CB BB B 1 1Pj j。从最优表中可知：。从最优表中可知：Y=CY=CB BB B 1 1=(5,15)(5,15)。销售价格销售价格85元元机会成本机会成本,新产品不应生产新产品不应生产!机会成本机会成本C CB BB B 1 1Pj j=5=59 915153 39090若柜子售价为若柜子售价为100元，情况是否

34、有变化元，情况是否有变化?运筹与决策之2线性规划70运筹与决策之2线性规划71 MIN 6000X11+11400X12+15675X13+20160X14+6000X21+11400X22+15675X23+6000X31+11400X32+6000X41+2000Y1+2000Y2+2000Y3+2000Y4 S.T.1)1X11+1X12+1X13+1X14+1Y1=10 2)1X12+1X13+1X14+1X21+1X22+1X23+1Y2=12 3)1X13+1X14+1X22+1X23+1X31+1X32+1Y3=14 4)1X14+1X23+1X32+1X41+1Y4=8 5)1

35、Y11 6)1Y22 7)1Y33 8)1Y4 0 0，Pk全全 0，停，停，没有有限最优解；没有有限最优解；否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全全 0。若是，停，得到最优解；若是，停，得到最优解；若否，转若否，转(3)。运筹与决策之2线性规划85=min aim+k 0 =0 =biaim+kbrarm+k定定X Xr为换出变量，为换出变量，a arm+k为为主元。主元。由最小由最小比值法求：比值法求：maxmax j=m+kXm+k 换入变量换入变量 j00(4)、运筹与决策之2线性规划86转转(2)(2)m+k 0 a1m+k 0arm+k 1amm+k 0初等行变换初等行变换Pm+k=(5)、以、以a arm+k为中心，换基迭代为中心，换基迭代运筹与决策之2线性规划87运筹与决策之2线性规划883 运输问题运输问题