《纯形法的灵敏度分析与对偶.ppt》由会员分享，可在线阅读，更多相关《纯形法的灵敏度分析与对偶.ppt（45页珍藏版）》请在金锄头文库上搜索。
1、管管 理理 运运 筹筹 学学第六章第六章 单纯形法的灵敏度分析与对偶单纯形法的灵敏度分析与对偶1 1单纯形表的灵敏度分析单纯形表的灵敏度分析2 2线性规划的对偶问题线性规划的对偶问题3 3对偶规划的基本性质对偶规划的基本性质4 4对偶单纯形法对偶单纯形法1管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析一、目标函数中变量系数ck灵敏度分析2管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析3管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析例： 目标函数：max z=50x1+100x2 约束条件：x1+x2300 2x
2、1+x2400 x2250 x1，x20最优单纯形表如下迭代次数基变量cBx1 x2 s1 s2 s3b50 100 0 0 02x1501 0 1 0 -150 s200 0 -2 1 150 x21000 1 0 0 1250 zj50 100 50 0 5027500cj -zj0 0 -50 0 -504管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 我们先对非基变量S1的目标函数的系数c3进行灵敏度分析。 这里3=-50，所以当c3的增量c350，最优解不变。 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a11,a12,a13,a14,a15中，
3、除了知道a11和 a13大于0， a15小于0，可知 ，有 。同样有 。这样可以知道当-50c150时，也就是x1的目标函数c1在0c1100时最优解不变。 在最终的单纯形表中，用c1代替原来的c1=50,计算得表5管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析迭代次数基变量cBx1 x2 S1 S2 S3b50 100 0 0 02x1c11 0 1 0 -150 S200 0 -2 1 150 x21000 1 0 0 1250 zjc1 100 c1 0 -c1+100cj -zj0 0 - c1 0 c1-1006 从30，得到-c10,即c10，并且从50
4、，得到c1100。 那么如果c1取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中S2 =50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增加利润的， A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为0。7迭代次数基变量cBx1 x2 S1 S2 S3b50 100 0 0 02x1501 0 1 0 -150 S200 0 -2 1 150 x21
5、000 1 0 0 1250 zj50 100 50 0 5027500cj -zj0 0 -50 0 -50管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数中从0变到z3=50时，也就是只要当余下一台时数设备从不能获利变成获利50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产、产品而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是z3=50元。同样我们也可以知道原料B的对偶价格为z5 =50元 对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对偶价格就和这个剩余
6、变量的 有关了。这将使得最优目标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 值的相反数- 。 对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的 值。 8管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析9下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。 从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值，当对偶价格为负时它将“恶化”目标函数值。 下面我们研究当右端项bj发生变化时，在什么范围内其对偶价格不变。由于bj的变化并不影响系数矩阵的迭代，故其最终单
7、纯形表中的系数矩阵没有变化。由此可见当bj变化时，要使原来的基不变得到的基本可行解仍然是可行解，也就是所求的基变量的值一定要大于0。所谓使其对偶价格不变的bj的变化范围，也就是使其最优解的所有基变量（最优基）不变，且所得的最优解仍然是可行的bj的变化范围。约束条件对偶价格的取值 等于这个约束条件对应的松弛变量的 值 等于这个约束条件对应的剩余变量的 值的相反数 =等于这个约束条件对应的人工变量的 值管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析10 在求目标函数最大值的线性规划中，对偶价格等于影子价格；而在求目标函数最小值的线性规划中，影子价格为对偶价格的相反数下表
8、给出了一个对偶价格的取值。 约束条件对偶价格的取值 等于这个约束条件对应的松弛变量的 值,即为 的相反数 等于这个约束条件对应的剩余变量的 值,即为 的相反数 =等于这个约束条件对应的人工变量的 值,即为 的相反数 管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 当bj中的第k项bK 变成 时，也就是原来的初始单纯形表中的b向量变成了b向量11管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 这样在最终单纯形表中基变量xB的解就变成了 如要使xB 成为可行解，只要使上述等式的右边0，就可求出 的取值范围，也就是使得第k个约束条件的对偶价格不
9、变的bk的变化范围。 12管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。最终单纯形表如下所示：迭代次数基变量cBx1 x2 S1 S2 S3b50 100 0 0 02x1501 0 1 0 -150 S200 0 -2 1 150 x21000 1 0 0 1250 zj50 100 50 0 5027500cj -zj0 0 -50 0 -5013管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1, 实际意义可以
10、描述为：当设备台时数在250与325之间变化时，该约束条件即设备台时数的对偶价格不变，都为每设备台时50元。14管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析三、约束方程系数矩阵A灵敏度分析下面分两种情况讨论 1.在初始单纯形表上的变量xk的系数列pk改变为pk经过迭代后，在最终单纯形表上xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，pk变成pk仅仅影响最终单纯形表上第k列数据，包括xk的系数列、zk以及 k，这时最终单纯形表上的xk的系数列就变成了B-1pk,而zk就变成 cBB-1pk，新的检验数 若 ，则原最优解仍然为最优解。若 0 ，则继续
11、进行迭代以求出最优。 例例 以第二章例1为基础，设该厂除了生产，种产品外，现在试制成一个新产品，已知生产产品,每件需要设备2台时，并消耗A原料0.5公斤。B原料1.5公斤，获利150元，问该厂应该生产该产品和生产多少？ 解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量x3在初始表上的系数列的问题，15管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析接上页迭代次数基变量cBx1 x2 S1 S2 S3 x3 b50 100 0 0 0 150x1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 x21000 1 0 0 1 1.52
12、50 zj50 100 50 0 50 17527500cj -zj0 0 -50 0 -50 -2516管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要使用1.5台设备 ，消耗原料A为2千克，原料B为1千克，每件产品的利润为160元，问该厂的生产计划是否要修改。 解：首先求出x3在最终表上的系数列 17迭代次数基变量cBx1 x2 S1 S2 S3 x3 b50 100 0 0 0 1602x1501 0 1 0 -1 0.55050/0.5 S200 0 -2 1 1 050 x21000 1 0 0 1
13、 1250250/1 zj50 100 50 0 50 12527500cj -zj0 0 -50 0 -50 35管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析接下来又可以有新的迭代S3进基，迭代次数基变量cBx1 x2 S1 S2 S3 x3 b50 100 0 0 0 1603x31602 0 2 0 -2 1100- S200 0 -2 1 1 05050/1 x2100-2 1 -2 0 3 0150150/3 zj120 100 120 0 -20 16031000cj -zj-70 0 -120 0 20 018管管 理理 运运 筹筹 学学1 1单纯形
14、表的灵敏度分析单纯形表的灵敏度分析接上页 可知此规模的最优解x1=0, x2=0, S1=0, S2=0, S3=50, x3=200,此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，生产产品200件, 可获得最大利润32000元。迭代次数基变量cBx1 x2 S1 S2 S3 x3 b50 100 0 0 0 1604x31602 0 -2 2 0 1200 S300 0 -2 1 1 050 x2100-2 1 4 -3 0 00 zj120 100 80 20 0 16032000cj -zj-70 0 -80 -20 0 019管管 理理 运运 筹筹 学学
15、1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 2.在初始表上的变量xK的系数pK改变为pK，经过迭代后，在最终表上xK是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表，而是重新计算。20管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析21 在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。 下面仍以第二章例1为例来加以说明。 例：假如该工厂除了在设备台时，原材料
16、A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电30度。试分析此时该厂获得最大利润的生产计划？管管 理理 运运 筹筹 学学迭代迭代次数次数基变量基变量b b比比值值50501001000 00 00 00 050501 10 01 10 0-1-10 050500 00 00 0-2-21 11 10 050501001000 01 10 00 01 10 02502500 0101030300 00 00 01 150005000505010010050500 050500 027500275000 00 0-
17、50-500 0-50-500 01 1单纯形表的灵敏度分析单纯形表的灵敏度分析 22解：先将原问题的最优解=50=50，=250代入用电量的约束条件得：1050+30250=500+75005000,所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量S4后得：把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：管管 理理 运运 筹筹 学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析 23在上表中的x1，x2不是单位向量，故进行行的线性变换，得迭代迭代次数次数基变量基变量c cB Bx x1 1x x2 2s s1 1s s2 2s s3 3s s4 4b b比
18、值比值50501001000 00 00 00 0x x1 150501 10 01 10 0-1-10 05050s s2 20 00 00 0-2-21 11 10 05050x x2 21001000 01 10 00 01 10 0250250s s4 40 00 00 0-10-100 0-20-201 1-3000-3000z zj j505010010050500 050500 027500275000 00 0-50-500 0-50-500 0把上表中的S4行的约束可以写为：上式两边乘以（-1），再加上人工变量a1得：用上式替换上表中的S4行，得下表：管管 理理 运运 筹筹
19、学学1 1单纯形表的灵敏度分析单纯形表的灵敏度分析24迭代迭代次数次数基基变变量量x x1 1x x2 2s s1 1s s2 2s s3 3s s4 4a a1 1b b比比值值50501001000 00 00 00 0-M-Mx x1 150501 10 01 10 0-1-10 00 05050s s2 20 00 00 0-2-21 1(1)(1)0 00 05050x x2 21001000 01 10 00 01 10 00 0250250a a1 1-M-M0 00 010100 02020-1-11 130003000z zj j505010010050-10M50-10M0
20、 050-20M50-20MM M-M-M0 00 010M-5010M-500 020M-5020M-50-M-M0 0x x1 150501 10 0-1-11 10 00 00 0100100s s3 30 00 00 0-2-21 11 10 00 05050x x2 21001000 01 12 2-1-10 00 00 0200200s s4 4-M-M0 00 0（5050）-20-200 0-1-11 120002000z zj j5050100100150-50M150-50M20M-5020M-500 0M M-M-M0 050M-15050M-15050-20M50-20
21、M0 0-M-M0 0x x1 150501 10 00 03/53/50 0-1/50-1/501/501/50140140s s3 30 00 00 00 01/51/51 1-2/50-2/502/502/50130130x x2 21001000 01 10 0-1/5-1/50 02/502/50-2/50-2/50120120s s4 40 00 00 01 1-2/5-2/50 0-1/50-1/501/501/504040z zj j50501001000 010100 03 3-3-30 00 00 0-10-100 0-3-3-M+3-M+3管管 理理 运运 筹筹 学学1
22、1单纯形表的灵敏度分析单纯形表的灵敏度分析 25由上表可知，最优解为： 即该工厂在添加了用电限量以后的最优生产计划为产品生产140件，产品生产120件。管管 理理 运运 筹筹 学学26 每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。例题例题1 1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、c台时如表所示 该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？解：设 为产品 的计划产量， 为产品的计划产量，则有目标函数： Max z z=50 + 100约束
23、条件： 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学27 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、c，那么该厂的厂长应该如何来确定合理的租金呢？ 设 分别为设备A、B、c的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，生产单位 产品所需各设备的台时各总租金不应低于原利润50元，即 ，否则就不出租还是用于生产 产品以获利50元；同样生产一单位 产品 所需各设备的台时的总租金也不应当低于原利润100元， 即 ，否则这些设备台时就不出租，还是用于生产 产品以获利100元。但对于租用者来说，他要求在满足
24、上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们得到了该问题的数学模型： 目标函数： 约束条件： 这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题原问题，而另外一个叫对偶问题对偶问题。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学28 如果我们把求目标函数最大值的线性规划问题看成原问题，则把求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。 1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条
25、件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。 3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于对偶问题的目标函数中的第i个变量的系数。 4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置 。 设 A=则 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学29如
26、果我们用矩阵形式来表示，则有原问题： 其中A是 矩阵mn，该问题有m个约束条件n个变量， , , 对偶问题： 其中 是A的转置， 是b的转置, 是c的转置, y= 现在我们用单纯形法求对偶问题的解。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学30 加上剩余变量 和人工变量 ，把此问题化成标准型如下：把上述数据填入单纯形表计算。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学31迭代变量基变量 b-300-400-25000-M 1-M1 0 -1 0 15050/2-250 1 1 1 0 -1 0 100100/1-M-250-2M-250
27、-250M250-M-50M-25000M-502M-1500-M-25002-4001/210-1/201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+502 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学 由上表，最优解： =50， -f 的最大值为-27500，即目标函数f的最小值为f=27500元。 从上面可知租金：A设备为50元，B设备为0
28、元，c设备为50元。这样把工厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目 标函数的最小值。 通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。 322 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学33 下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的
29、线性规划为例，写出它的对偶问题。 s.t. 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学34 这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于等于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以 -1，使不等号方向改变即可，得 这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有 显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以-1，得 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹
30、筹 学学35 通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题： s.t. 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学36 这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题： s.t.2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学37 这里 和 一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为 。 因为在该对偶问题中 和 的系数只相差一个符号，我们可以把上面的对偶问题化为： s.t.2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学38
31、进一步，我们可以令 ，这时当 时， ，当 时， 。这也就是说，尽管 但 的取值可以为正，可以为0，可以为负，即 没有非负限制。 这样我们把原规划的对偶问题化为 s.t. 没有非负限制。 对照原线性规划问题，我们可以知道： 当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。 如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用 进行替换，这里 ， ，用类似的方法知道其对偶问题中第 i个约束条件取等号。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学39 另外，用大于等于0的两个决策变量之差来代替无非负限制的决策变量也是求
32、解含有无非负限制的决策变量的线性规划问题的一种方法。 原线性规划问题为： s.t. 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学40首先在写对偶问题之前，我们先把第二个约束条件两边乘以-1得 然后按照上面的规则，我们可以得到其对偶问题为 s.t. 2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学3 3对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质1对称性对称性。即对偶问题的对偶是原问题。2弱对偶性弱对偶性。即对于原问题和对偶问题的可行解 ， 都有 。 由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其
33、对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：此性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。41管管 理理 运运 筹筹 学学3 3对偶规划的基本性质对偶规划的基本性质3最优性最优性。如果 是原问题的可行解， 是对偶问题的可行解，并且 ，则 和
34、 分别为原问题和对偶问题的最优解。4强对偶性强对偶性。即若原问题及其对偶问题都有可行解，则两者都有最优解，且它们的最优解的目标函数都相等。5互补松弛性互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即 若yi*0,则有 若 ，则有yi*=042管管 理理 运运 筹筹 学学4 4对偶单纯形法对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于等于零的情况下，通过迭代使得所有的约束都大于等于零，最后求得最优解。 简化计算是对偶单纯形
35、法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解使得其所有检验数都小于等于零。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。 上节分析中已知当250b1325时第一个约束条件的对偶价格不变，现在b1=300变成b1=350，请问这时第一个约束方程的对偶价格应为多少呢？ 解：求出在第二次迭代表上的常数列 43管管 理理 运运 筹筹 学学4 4对偶单纯形法对偶单纯形法迭代次数基变量cBx1 x2 S1 S2 S3b50 100 0 0 02x1501 0 1 0 -1100S200 0 -2 1 1-50 x21000 1 0 0 1250 zj50 100 50 0 50cj -zj0 0 -50 0 -50441.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行的基变量为出基变量管管 理理 运运 筹筹 学学4 4对偶单纯形法对偶单纯形法 4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复1-4步。迭代次数基变量cBx1 x2 S1 S2 S3b50 100 0 0 02x1501 0 0 1/2 -1/275 S100 0 1 -1/2 -1/225 x21000 1 0 0 1250 zj50 100 0 25 7528750cj -zj0 0 0 -25 -7545
