第五讲 运输问题续.ppt

《第五讲 运输问题续.ppt》由会员分享，可在线阅读，更多相关《第五讲 运输问题续.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五讲l运输问题（续）l目标规划2021/9/241表4-3 运输问题数据表1.1.运输问题模型及有关概念运输问题模型及有关概念 销地产地B1 B2 Bn产量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmns1 s2 sm销量d1 d2 dn 设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个运输问题的要求，可以建立运输变量表（表 4-4）。2021/9/242表4-4 运输问题变量表1.1.运输问题模型及有关概念运输问题模型及有关概念 销地产地B1 B2 Bn产量A1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xm

2、ns1 s2 sm销量d1 d2 dn2021/9/243 m nMin f=cij xij （4-1）i=1 j=1 n s.t.xij si i=1,2,m （4-2）j=1 m xij(=,)dj j=1,2,n （4-3）i=1 xij 0(i=1,2,m;j=1,2,n)（4-4）1.1.运输问题模型及有关概念运输问题模型及有关概念 于是得到下列一般运输问题的模型：在模型（4-1）（4-4）中，式（4-2）为 m 个产地的产量约束；式（4-3）为 n 个销地的销量约束。2021/9/244 m n Min f=cij xij i=1 j=1 n s.t.xij =si i=1,2,m

3、 (4-5)j=1m xij =dj j=1,2,n (4-6)i=1 xij 0 (i=1,2,m;j=1,2,n)1.1.运输问题模型及有关概念运输问题模型及有关概念 对于产销平衡问题，可得到下列运输问题的模型：2021/9/2451.1.运输问题模型及有关概念运输问题模型及有关概念基本可行解是否最优解结束换基是否图4-1 运输问题的求解思路表上作业法2021/9/2461.1.运输问题模型及有关概念运输问题模型及有关概念 销地产地B1B2Bn产量A1 c11 x11c12 x12c1n x1na1 A2 c21 x21c22 x22c2n x2na2 Amcm1 xm1cm2 xm2cm

4、n xmnam销量b1b2bn2021/9/247 A的秩为 m+n-1，基变量共有 m+n-1 个。运输问题的 m+n-1 个变量构成基变量的充分必要条件是不含闭回路。特点 运输问题基变量的1.1.运输问题模型及有关概念运输问题模型及有关概念2021/9/2482.2.运输问题求解运输问题求解 表上作业法表上作业法 一、初始基本可行解的确定一、初始基本可行解的确定 西北角法：西北角法：最小元素法：最小元素法：2021/9/249求检验数的方法求检验数的方法:闭回路法闭回路法 位势法位势法 二、基本可行解的最优性检验二、基本可行解的最优性检验 2.2.运输问题求解运输问题求解 表上作业法表上作

5、业法 2021/9/2410表4-10 以非基变量 x22 为起始顶点的闭回路销地产地B1B2B3B4产量3 11 3 410 371 39 2 18 47 4 610 5 39销量365620(产销平衡)A1A2A39 2+3 10+5 4 1,总的运费增加 1 个单位2021/9/2411 销地产地B1B2B3B4产量A13 111 23 410 37A21 39 12 18-14A37 104 610125 39销量365620(产销平衡)表表4-11 4-11 初始基本可行解及检验数初始基本可行解及检验数2021/9/24122.2.运输问题求解运输问题求解 表上作业法表上作业法位势法

6、位势法2021/9/2413 2.2.位势法位势法 位位势势：设设对对应应基基变变量量xij的的 m m+n n-1-1 个个 ij ，存存在在ui,vj 满足满足 ui+vj=cij ，i=1,2,m;j=1,2,n.称这些称这些 ui,vj 为该基本可行解对应的为该基本可行解对应的位势位势。注注.由于有由于有m m+n n 个变量（个变量（ui,vj ），），m m+n n-1 -1 个方程（基变量个数），个方程（基变量个数），故有一个自由变量，位势不唯一。故有一个自由变量，位势不唯一。利用位势求检验数：利用位势求检验数：ij=cij-ui-vji=1,m;j=1,n2.2.运输问题求解运

7、输问题求解 表上作业法表上作业法 2021/9/2414前例，位势法求检验数：前例，位势法求检验数：step 1step 1 从任意基变量对应的从任意基变量对应的 cij 开开始始,任取任取 ui 或或 vj ，然后利用公式，然后利用公式 cij=ui+vj 依次找出依次找出 m m+n n 个个 ui,vj从从c14=10 开始开始 step 2step 2 计算非基变量的检验数计算非基变量的检验数 ij=cij-ui-vj；填入圆圈内；填入圆圈内2.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/24152.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9

8、/2416 当当非非基基变变量量的的检检验验数数出出现现负负值值时时，则则表表明明当当前前的的基基本本可可行行解解不不是是最最优优解解。在在这这种种情情况况下下，应应该该对对基基本本可可行行解解进进行行调调整整，即即找找到到一一个个新新的的基基本本可可行行解解使使目目标标函函数数值值下下降降，这这一一过过程程通通常常称称为为换换基基(或或主主元元变变换换)过程。过程。2.2.运输问题求解运输问题求解 表上作业法表上作业法 三、求新的基本可行解三、求新的基本可行解2021/9/2417 （1 1）选负检验数中最小者选负检验数中最小者 rk，那，那么么xrk为主元，作为进基变量（上页图为主元，作为

9、进基变量（上页图中中x24）;（2 2）以以 xrk为起点找一条闭回路，为起点找一条闭回路，除除xrk外其余外其余顶点必须为基变量格（上顶点必须为基变量格（上页图中的回路）页图中的回路）;2.2.运输问题求解运输问题求解 表上作业法表上作业法 在运输问题的表上作业法中，换基的过在运输问题的表上作业法中，换基的过程是如下进行：程是如下进行：2021/9/2418 （3 3）为闭回路的每一个顶点标号，为闭回路的每一个顶点标号，x xrkrk 为为 1 1，沿一个方向（顺时针或逆时，沿一个方向（顺时针或逆时针）依次给各顶点标号；针）依次给各顶点标号；（4 4）求求 =Minxij xij对应闭回路上

10、对应闭回路上的偶数标号格的偶数标号格=xpq 那么确定那么确定xpq为出为出基变量，基变量，为调整量；为调整量；2.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/2419 （5 5）对闭回路的各奇标号顶点调对闭回路的各奇标号顶点调整为：整为：xij+，对各偶标号顶点，对各偶标号顶点调整调整为：为：xij-，特别，特别 xpq-=0，xpq变为变为非非基变量。基变量。重复重复(2)(2)、(3)(3)步，直到所有检验步，直到所有检验数均非负，得到最优解。数均非负，得到最优解。2.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/24202.2.表上作业法表上作

11、业法 ij0，得到，得到最优解最优解x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余其余xij=0;最优值最优值：f*=35+102+13+81+46+53=852021/9/2421作业：作业：2021/9/2422 四、产销不平衡问题的处理 在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型 m nMin f=cij xij （4-1）i=1 j=1 n s.t.xij si i=1,2,m （4-2）j=1 m xij(=,)dj j=1,2,n(4-3）i=1 xij 0(i=1,2,m;j=1,2,n)（4-4）2.2.运输问题求解运输问

12、题求解 表上作业法表上作业法 2021/9/2423 我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。1.产量大于销量的情况 m n 考虑 si dj 的运输问题，得到的数学模 i=1 j=1型为2.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/24242.2.运输问题求解运输问题求解 表上作业法表上作业法 m n Min f=cij xij i=1 j=1 n s.t.xij si i=1,2,m j=1 m xij=dj j=1,2,n i=1 xij0(i=1,2,m;j=1,2,n)2021/9/2425 只要在

13、模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xin+1 i=1,2,m 即可，变为：n xij+xin+1=si i=1,2,，mj=1然后，需设一个销地B n+1,它的销量为：m n bn+1=si-d dj j i=1 j=12.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/2426 这里，松弛变量 x i n+1 可以视为从产地 A i 运往销地 B n+1 的运输量，由于实际并不运送，它们的运费为 c i n+1=0 i=1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。2.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/2

14、427 例4.2:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？2.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/2428 解：增加一个虚设的销地运输费用为02.2.运输问题求解运输问题求解 表上作业法表上作业法 2021/9/2429 2.2.销量大于产量的情况销量大于产量的情况 m nm n 考虑考虑 s si i Pi+1，i=1,2,L-1.2021/9/2463目标规划模型目标规划模型目标规划模型目标规划模型2.目标规划模型的基本概念目标规划模型

15、的基本概念（续）（续）即在计算过程中即在计算过程中,首先保证首先保证P1级目标的实现，级目标的实现，这时可不考虑次级目标；而这时可不考虑次级目标；而P2级目标是在实现级目标是在实现P1级目标的基础上考虑的，以此类推。当需要级目标的基础上考虑的，以此类推。当需要区别具有相同优先因子的若干个目标的差别时，区别具有相同优先因子的若干个目标的差别时，可分别赋于它们不同的权系数可分别赋于它们不同的权系数wj。优先因子及优先因子及权系数的值，均由决策者按具体情况来确定权系数的值，均由决策者按具体情况来确定（4）目标规划的目标函效）目标规划的目标函效目标规划的目标函数是通过各目标约目标规划的目标函数是通过各

16、目标约束的正、负偏差变量和赋于相应的优先等束的正、负偏差变量和赋于相应的优先等级来构造的级来构造的2021/9/2464目标规划模型目标规划模型2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）决决策策者者的的要要求求是是尽尽可可能能从从某某个个方方向向缩缩小小偏偏离离目目标标的的数数值值。于于是是，目目标标规规划划的的目目标标函函数数应该是求极小：应该是求极小：minf f（d+，d-)其基本形式有三种其基本形式有三种：（1）要求恰好达到目标值，即使相要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可应目标约束的正、负偏差变量都要尽可能地小。这时取能地小。这时取min（d

17、+d-)；（2）要求不超过目标值，即使相应要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。目标约束的正偏差变量要尽可能地小。这时取这时取min（d+)；2021/9/2465目标规划模型目标规划模型目标规划模型目标规划模型2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）（3）要求不低于目标值，即使相应目标约要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取束的负偏差变量要尽可能地小。这时取min（d-)；对于例对于例7.1,我们根据决策者的考虑知我们根据决策者的考虑知第一优先级要求第一优先级要求min（d1+d2+)；第二优先级要求第二优先级要求min（

18、d3+)；第三优先级要求第三优先级要求min（d4-)；第四优先级要求第四优先级要求min（d1-+2d2-)，这里这里,当不当不能满足市场需求时能满足市场需求时,市场认为市场认为B产品的重要性是产品的重要性是A产品的产品的2倍即减少倍即减少B产品的影响是产品的影响是A产品的产品的2倍，倍，因此我们引入了因此我们引入了2:1的权系数。的权系数。2021/9/2466目标规划模型目标规划模型目标规划模型目标规划模型2.目标规划模型的基本概念目标规划模型的基本概念（续）（续）综合上述分析，我们可得到下列目标规划模型综合上述分析，我们可得到下列目标规划模型 Minf=P1（d1+d2+)+P2 d3

19、+P3 d4-+P4（d1-+2d2-)s.t.x1+d1-d1+=9 x2+d2-d2+=8 4x1+6x2+d3-d3+=60(7.1.5)12x1+18x2+d4-d4+=252 x1,x2,di-,di+0,i=1,2,3,4.2021/9/2467目标规划模型目标规划模型3.目标规划模型的一般形式目标规划模型的一般形式根据上面讨论根据上面讨论,我们可以得到目标规划的一我们可以得到目标规划的一般形式如下般形式如下（LGP）中的第二行是中的第二行是K个目标约束，第三行是个目标约束，第三行是m个绝对约束，个绝对约束，ckj和和gk是目标参数。是目标参数。2021/9/2468目标规划的几何

20、意义及图解法目标规划的几何意义及图解法对只具有两个决策变量的目标对只具有两个决策变量的目标规划的数学模型，我们可以用图解规划的数学模型，我们可以用图解法来分析求解通过图解示例，可法来分析求解通过图解示例，可以看到目标规划中优先因子，正、以看到目标规划中优先因子，正、负偏差变量及权系数等的几何意义。负偏差变量及权系数等的几何意义。2021/9/2469目标规划的几何意义及图解法目标规划的几何意义及图解法下面用图解法来求解例下面用图解法来求解例7-1。我们先在平面直角坐标系的第一象我们先在平面直角坐标系的第一象限内，作出与各约束条件对应的直线，限内，作出与各约束条件对应的直线，然后在这些直线旁分别

21、标上然后在这些直线旁分别标上G-i，i=1，2，3，4。图中图中x，y分别表示问题（分别表示问题（7-5）的）的x1和和x2；各直线移动使之函数值变各直线移动使之函数值变大、变小的方向用大、变小的方向用+、-表示表示di+,di-（如如图图7-1所示）所示）2021/9/2470目标规划的几何意义及图解法目标规划的几何意义及图解法0 5 10 15 20 y x2015105+-G-1+-G-2+-G-4+-G-3图7-12021/9/2471目标规划的几何意义及图解法目标规划的几何意义及图解法下面我们根据目标函数的优先因子来分析下面我们根据目标函数的优先因子来分析求解首先考虑第一级具有求解首

22、先考虑第一级具有P1优先因子的目优先因子的目标的实现，在目标函数中要求实现标的实现，在目标函数中要求实现min（d1+d2+),取取d1+=d2+=0.图图72中阴影部分即表示中阴影部分即表示出该最优解集合的所有点。出该最优解集合的所有点。我们在第一级目标的最优解集合中找满足我们在第一级目标的最优解集合中找满足第二优先级要求第二优先级要求min（d3+)的最优解的最优解.取取d3+=0,可得到图可得到图73中阴影部分即是满足第一、第中阴影部分即是满足第一、第二优先级要求的最优解集合。二优先级要求的最优解集合。2021/9/2472目标规划的几何意义及图解法目标规划的几何意义及图解法图7-20

23、5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)2021/9/2473目标规划的几何意义及图解法目标规划的几何意义及图解法图7 3 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)2021/9/2474目标规划的几何意义及图解法目标规划的几何意义及图解法第第三三优优先先级级要要求求min（d4-)，根根据据图图示示可可知知，d4-不不可可能能取取0值值，我我们们取取使使d4-最最小小的的值值72得得到到图图74中中两两阴阴影影部部分分的的交交线线(黑黑色色粗粗线线)，其其表表示示满满足足第第一一、第第二

24、二及及第第三三优优先先级级要要求求的的最最优解集合。优解集合。最后，考虑第四优先级要求最后，考虑第四优先级要求min（d1-+2d2-)，即要在黑色粗线段中找出最优解。由于即要在黑色粗线段中找出最优解。由于d1-的权因子小于的权因子小于d2-，因此在这里可以考虑取因此在这里可以考虑取d2-=0。于是解得于是解得d1-=6，最优解为最优解为A点点x=3，y=8。2021/9/2475目标规划的几何意义及图解法目标规划的几何意义及图解法图7 4 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)2021/9/24763.求解目标规划的单纯形方法求解目标

25、规划的单纯形方法目标规划的数学模型目标规划的数学模型,特别是约束的结构与特别是约束的结构与线性规划模型没有本质的区别，只是它的目标线性规划模型没有本质的区别，只是它的目标不止是一个不止是一个,虽然其利用优先因子和权系数把虽然其利用优先因子和权系数把目标写成一个函数的形式目标写成一个函数的形式,但在计算中无法按但在计算中无法按单目标处理单目标处理,所以可用单纯形法进行适当改进所以可用单纯形法进行适当改进后求解。在组织、构造算法时，我们要考虑目后求解。在组织、构造算法时，我们要考虑目标规划的数学模型一些特点，作以下规定：标规划的数学模型一些特点，作以下规定：(1)因为目标规划问题的目标函数都是求最

26、因为目标规划问题的目标函数都是求最小化，所以检验数的最优准则与线性规划是相小化，所以检验数的最优准则与线性规划是相同的；同的；2021/9/24773.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)(2)因为非基变量的检验数中含有不同等级的因为非基变量的检验数中含有不同等级的优先因子，优先因子，Pi Pi+1，i=1,2,L-1.于是从每个于是从每个检验数的整体来看：检验数的整体来看：Pi+1（i=1,2,L-1）优先级优先级第第k个检验数的正、负首先决定于个检验数的正、负首先决定于P1，P2，Pi优先级第优先级第k个检验数的正、负。若个检验数的正、负。若P1级第级第k个检个检验数为

27、验数为0，则此检验数的正、负取决于，则此检验数的正、负取决于P2级第级第k个个检验数；若检验数；若P2级第级第k个检验数仍为个检验数仍为0，则此检验数，则此检验数的正、负取决于的正、负取决于P3级第级第k个检验数，依次类推。个检验数，依次类推。换一句话说，当某换一句话说，当某Pi 级第级第k个检验数为负数时，个检验数为负数时，计算中不必再考察计算中不必再考察Pj（j i）级第级第k个检验数的个检验数的正、负情况；正、负情况；2021/9/24783.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)（3）根根据据（LGP）模模型型特特征征，当当不不含含绝绝对对约约束束时时，di-（i=1

28、,2,K）构构成成了了一一组组基基本本可可行行解解。在在寻寻找找单单纯纯形形法法初初始始可可行行点点时时，这这个个特特点是很有用的。点是很有用的。解目标规划问题的单纯形法的计算步骤解目标规划问题的单纯形法的计算步骤：(1)建立初始单纯形表在表中将检验数行建立初始单纯形表在表中将检验数行按优先因子个数分别列成按优先因子个数分别列成K行。初始的检验数行。初始的检验数需根据初始可行解计算出来，方法同基本单纯需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时，形法。当不含绝对约束时，di-（i=1,2,K）构成了一组基本可行解，这时只需利用相应单构成了一组基本可行解，这时只需利用相应单位向

29、量把各级目标行中对应位向量把各级目标行中对应di-（i=1,2,K）的量消成的量消成0即可得到初始单纯形表。置即可得到初始单纯形表。置k 1；2021/9/24793.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)(2)检检查查当当前前第第k行行中中是是否否存存在在大大于于0，且且对对应应的的前前k-1行行的的同同列列检检验验数数为为零零的的检检验验数数。若若有有取取其其中中最最大大者者对对应应的的变变量量为为换换入入变变量量，转转(3)。若无这样的检验数，则转若无这样的检验数，则转(5)；(3)按单纯形法中的最小比值规则确定换出按单纯形法中的最小比值规则确定换出变量，当存在两个和两

30、个以上相同的最小比值变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，时，选取具有较高优先级别的变量为换出变量，转（转（4）；）；2021/9/24803.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)(4)按按单单纯纯形形法法进进行行基基变变换换运运算算，建建立立新新的的单单纯纯形形表表，（注注意意：要要对对所所有有的的行行进进行行转转轴运算）返回轴运算）返回(2)；(5)当当k K 时，计算结束。表中的解即时，计算结束。表中的解即为满意解。否则置为满意解。否则置k=k+1，返回（返回（2）。）。2021/9/24813.求解目标规划的单纯形方法求解

31、目标规划的单纯形方法(续续)例例7.2试试用用单单纯纯形形法法来来求求解解例例7-1的的目目标标规规划模型划模型(7-5)Minf=P1（d1+d2+)+P2 d3+P3 d4-+P4（d1-+2d2-)s.t.x1+d1-d1+=9 x2+d2-d2+=8 4x1+6x2+d3-d3+=60 12x1+18x2+d4-d4+=252 x1,x2,di-,di+0,i=1,2,3,4.2021/9/2482求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)解解:首首先先处处理理初初始始基基本本可可行行解解对对应应的的各各级级检验数。检验数。由由于于P1,P2优优先先级级对对应应的的目目标

32、标函函数数中中不不含含di-,所所以以其其检检验验数数只只需需取取系系数数负负值值。分分别别为为(0，0，0，-1，0，-1，0，0，0，0；0)和和(0，0，0，0，0，0，0，-1，0，0；0)2021/9/2483x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000P20000000-1000P300000000-100P400-10-2000000d1-101-10000009d2-01001-100008d3-4600001-10060d4-12180000001-12522021/9/2484x1x2d1-d1+d2-d2+d3-d3+d4

33、-d4+RHS P1000-10-100000P20000000-1000P312180000000-1252P400-10-2000000d1-101-10000009d2-0*1001-100008d3-4600001-10060d4-12180000001-12522021/9/24853.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)P3优优先先级级对对应应的的目目标标函函数数中中含含d4-,所所以以其其检检验验数数需需要要把把第第四四个个约约束束行行加加到到取取负负值值的的这这一一行上，得到行上，得到(12，18，0，0，0，0，0，0，0，-1；252)T P4优优先先级

34、级对对应应的的目目标标函函数数中中含含（d1-+2d2-)，所所以以其其检检验验数数需需要要把把第第一一个个约约束束行行与与第第二二个个约约束束行行的的2倍倍加加到到取取系系数数负负值值的的这这一一行行上上，得到得到(1，2，0，-1，0，-2，0，0，0，0；25)。列目标规划的初始单纯形表列目标规划的初始单纯形表 2021/9/2486x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000P20000000-1000P312180000000-1252P4120-10-2000025d1-101-10000009d2-0*1001-1000088d3

35、-4600001-1006010d4-12180000001-1252142021/9/24873.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)（1）k=1，在初始单纯形表中基变量为在初始单纯形表中基变量为（d1-,d2-,d3-,d4-)T=（9，8,60，252)T；（2）因因为为P1与与P2优优先先级级的的检检验验数数均均已已经经为为非非正正，所所以以这这个个单单纯纯形形表表对对P1与与P2优优先先级级是是最最优单纯形表；优单纯形表；（3）下面考虑）下面考虑P3优先级，第二列的检验数优先级，第二列的检验数为为18，此为进基变量，计算相应的比值，此为进基变量，计算相应的比值bi

36、/aij写在写在 列。通过比较，得到列。通过比较，得到d2-对应的比值最对应的比值最小，于是取小，于是取a22（标为标为*号）为转轴元进行矩号）为转轴元进行矩阵行变换得到新的单纯形表；阵行变换得到新的单纯形表；2021/9/2488x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000P20000000-1000P312000-1818000-1108P4100-1-2000009d1-101-100000099x201001-100008d3-*4000-661-100123d4-12000-1818001-110892021/9/24893.求解目标

37、规划的单纯形方法求解目标规划的单纯形方法(续续)（4）下面继续考虑）下面继续考虑P3优先级，第一优先级，第一列的检验数为列的检验数为18，此为进基变量，计算，此为进基变量，计算相应的比值相应的比值bi/aij写在写在 列。通过比较，列。通过比较，得到得到d3-对应的比值最小，于是取对应的比值最小，于是取a31（标为标为*号）为转轴元进行矩阵行变换号）为转轴元进行矩阵行变换得到新的单纯形表；得到新的单纯形表；2021/9/2490 x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHS P1000-10-100000P20000000-1000P3000000-330-172P4000-1-0.5-1.5-.25.25006d1-001-11.5-1.5-.25.25006x201001-100008x11000-1.51.5.25-.25003d4-000000-331-1722021/9/24913.求解目标规划的单纯形方法求解目标规划的单纯形方法(续续)（5）当前的单纯形表各优先级的检验）当前的单纯形表各优先级的检验数均满足了上述条件数均满足了上述条件,故为最优单纯形表。故为最优单纯形表。我们得到最优解我们得到最优解x1=3，x2=8。2021/9/2492