运筹学 --线性规划（02）.ppt

《运筹学 --线性规划（02）.ppt》由会员分享，可在线阅读，更多相关《运筹学 --线性规划（02）.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Max S =CX Max S =CX s.t.AX=b s.t.AX=b X X 0 0基，基解，基可行解，可行基。基，基解，基可行解，可行基。线性规划问题的可行域线性规划问题的可行域D是凸集。是凸集。顶点与基可行解相对应顶点与基可行解相对应线性规划问题的最优解，必定在线性规划问题的最优解，必定在D的顶点上达到。的顶点上达到。目标函数在多个顶点上达到最优值。这些顶点的目标函数在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）。凸组合也是最优值。（有无穷多最优解）。第三节第三节 线性规划线性规划-单纯形方法单纯形方法单纯形方法基本思路：单纯形方法基本思路：从可行域中某个基础

2、可行解（一个顶点）从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。开始（称为初始基础可行解）。线性规划（线性规划（2 2）-单纯形方法单纯形方法单纯形方法基本思路：单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），数值的另一个基础可行解（另一个顶点），以改进初始解。以改进初始解。线性规划（线性规划（2 2）-单纯形方法单纯形方法单纯形方法基本思路：单纯形方法基本思路：从可行

3、域中某个基础可行解（一个顶点）从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），数值的另一个基础可行解（另一个顶点），以改进初始解。以改进初始解。继续寻找更优的基础可行解，进一步改进继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。改善时，该解就是最优解。第三节第三节 线性规划线性规划-单纯形方法单纯形方法单纯形方法基本思路：单纯形方法基本思路：1.1.从可行域中

4、某个基础可行解（一个顶点）从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。开始（称为初始基础可行解）。2.2.如可能，从可行域中求出具有更优目标函数值如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进的另一个基础可行解（另一个顶点），以改进3.3.继续寻找更优的基础可行解，进一步改继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。再改善时，该解就是最优解。初始解。初始解。一、消去法一、消去法例例1-18：一个企业需要同一两种原：一个企业需要同一两种原材料生产甲乙两种产

5、品，它们的材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量单位产品所需要的原材料的数量及所耗费的加工时间各不相同，及所耗费的加工时间各不相同，从而获得的利润也不相同（如下从而获得的利润也不相同（如下表）。那么，该企业应如何安排表）。那么，该企业应如何安排生产计划，才能使获得的利润达生产计划，才能使获得的利润达到最大？到最大？解：数学模型解：数学模型 max S=2x1+3x2 s.t.x1+2x2 8 4x1 16 4x2 12 x1,x20解：引进松弛变量解：引进松弛变量x3,x4,x5=0数学模型标准形式：数学模型标准形式：max S=2x1+3x2 s.t.x1+2x2+x3 =

6、8 4x1 +x4=16 4x2 +x5=12 x1,x2,x3,x4,x5 0约束条件的增广矩阵为：约束条件的增广矩阵为：1 2 1 0 0 8（A b)=4 0 0 1 0 16 0 4 0 0 1 12显然显然 r(A)=r(Ab)=3=0 (1-19)a a11 11 a a1212 .a .a1n 1n b b1 1 A=a a21 21 a a2222 .a .a2n 2n b =b b2 2 a am1 m1 a am2m2 .a amnmn b bn n c c1 1 x x1 1 0 0 c c2 2 x x2 2 0 0C Ct t=X=0=X=0=.c cn n x xn

7、 n 0 0并且并且并且并且 r(A)=mn.r(A)=m=0,X=（B-1b,0)T=0X为基础可行解为基础可行解,B就是可行基。就是可行基。另外，若满足另外，若满足 CN-CB B-1N 0或或 CB B-1N-CN 0则对任意的则对任意的 x=0 有有 S=CX CB B-1b 即对应可行基即对应可行基B的可行解的可行解x为最优解。为最优解。定理（最优解判别准则）定理（最优解判别准则）对于可行基对于可行基B,若若 C-CB B-1A 0 则对应于基则对应于基B的基础可行解的基础可行解x就是就是基础最基础最优解，此时的可行基就是最优基。优解，此时的可行基就是最优基。=C-CB B-1A为检

8、验数。为检验数。基变量的检验数：基变量的检验数：CB-CB B-1B=0C-CB B-1A=（0，CN-CB B-1N）换入基变量中，得到基可行解换入基变量中，得到基可行解换入基变量中，得到基可行解换入基变量中，得到基可行解定理：若检验数全小于等于零，且某一个非基变量定理：若检验数全小于等于零，且某一个非基变量定理：若检验数全小于等于零，且某一个非基变量定理：若检验数全小于等于零，且某一个非基变量的检验数为的检验数为的检验数为的检验数为0 0，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。（无穷多最优解情况）（无穷

9、多最优解情况）（无穷多最优解情况）（无穷多最优解情况）证明：证明：证明：证明：某个非基变量某个非基变量某个非基变量某个非基变量为为为为最优解。故线性规划问题有无最优解。故线性规划问题有无最优解。故线性规划问题有无最优解。故线性规划问题有无穷多最优解。穷多最优解。穷多最优解。穷多最优解。为一基可行解，有一个变量为一基可行解，有一个变量为一基可行解，有一个变量为一基可行解，有一个变量X Xm+km+k对应对应对应对应因因因因为可行解。为可行解。为可行解。为可行解。定理：定理：若存在检验数大于零，但所对应的换入变量若存在检验数大于零，但所对应的换入变量若存在检验数大于零，但所对应的换入变量若存在检验

10、数大于零，但所对应的换入变量X Xm+km+k的系数向量的系数向量的系数向量的系数向量P Pm+km+k0,0,则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（无界解的情况）无界解的情况）无界解的情况）无界解的情况）证明：证明：证明：证明：构造一个新的解构造一个新的解构造一个新的解构造一个新的解 ，分量为，分量为，分量为，分量为定理定理：若非基变量检验数严格小于零，则线：若非基变量检验数严格小于零，则线性规划问题有唯一最优解。性规划问题有唯一最优解。定理定理定理定理：若检验数全小于等于零，且某一个非基变量：若检验数全小于等于零，且某一个非基变量：若检验数全小于等

11、于零，且某一个非基变量：若检验数全小于等于零，且某一个非基变量的检验数为的检验数为的检验数为的检验数为0 0，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。定理：定理：若某一个非基变量的检验数大于若某一个非基变量的检验数大于若某一个非基变量的检验数大于若某一个非基变量的检验数大于0 0，其系数列向，其系数列向，其系数列向，其系数列向量量量量P Pm+km+k0,0,则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（无界解的情况）无界解的情况）无界解的情况）无界解的情况）线性规划为求最大

12、化的标准型：线性规划为求最大化的标准型：线性规划为求最小化的标准型时，相应的结线性规划为求最小化的标准型时，相应的结果？果？单纯形表：单纯形表：T T（B B）=B=B-1-1b Bb B-1-1A A C CB B B B-1-1b C-Cb C-CB B B B-1-1A A =B =B-1-1b I Bb I B-1-1N N C CB B B B-1-1b 0 Cb 0 CN N-C-CB B B B-1-1N N注意：注意：A=（B，N）检验数检验数=C-CB B-1A=（0，CN-CB B-1N）非基变量检验数非基变量检验数=CN-CB B-1N时时,达到最优。达到最优。单纯形表格

13、：单纯形表格：单纯形解题步骤：单纯形解题步骤：（已知初始可行基）（已知初始可行基）求最大化时求最大化时一、作对应一、作对应B的单纯形表的单纯形表：T T（B B）=B=B-1-1b Bb B-1-1A A C CB B B B-1-1b C-Cb C-CB B B B-1-1A A =B =B-1-1b I Bb I B-1-1N N C CB B B B-1-1b 0 Cb 0 CN N-C-CB B B B-1-1N N单纯形解题步骤：单纯形解题步骤：二、判别二、判别若检验数全小于等于零，则基若检验数全小于等于零，则基B所对应所对应的基础可行解的基础可行解X就是最优解，终止。就是最优解，终

14、止。若存在检验数大于零，但所对应的换若存在检验数大于零，但所对应的换入变量入变量Xk的系数向量的系数向量Pk0,则原问题无则原问题无最优解，终止。最优解，终止。若存在检验数大于零，且对应的系数若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。列有大于零的分量，则需要换基迭代。三、换基迭代三、换基迭代确定换入变量确定换入变量Xk，其中其中max(j 0)=k,xk为换入变量为换入变量 j=1,2,m确定换出基变量确定换出基变量Xr,根据最小比值原则根据最小比值原则min(bi/aik,aik 0,1im)=bl/blkalk为主元素为主元素,Xl为为换出基变量。换出基变量。对单纯

15、形表对单纯形表T（B）进行初等行变换进行初等行变换（主元运算）得到新的单纯形表。（主元运算）得到新的单纯形表。经过上述有限次的换基迭代，就可得到经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。原问题的最优解，或判定无最优解。例例1-19 求线性规划问题：求线性规划问题：max S=2x1+3x2 s.t.x1+2x2=8 4x1 =16 4x2=0解：解：对目标函数标准化对目标函数标准化max S=2x1+3x2 s.t.x1+2x2+x3 =8 4x1 +x4=16 4x2 +x5=12 x1,x2,x3,x4,x5=0 1 2 1 0 0 A=4 0 0 1 0 0 4

16、0 0 1 （x1 x2 x3 x4 x5）=（N B ）解：解：1 0 0B=0 1 0 =I b=(8,16,12)T 0 0 1x3 x4,x5为基变量，为基变量，CB=（0，0,0）x1,x2为非基变量。为非基变量。有有B-1=I,B-1b=b,B-1A=A,单纯性表如下：单纯性表如下：初始单纯性表初始单纯性表TAB(1)为：为：x2换入换入,x5 换出换出；得；得TAB(2)为：为：x1换入换入,x3换出换出；得；得TAB(3)为：为：x5换入换入,x4 换出换出；得；得TAB(4)为：为：此时所有的检验数此时所有的检验数小于等于零小于等于零，此时，此时的基础可行解的基础可行解X=（

17、4，2，0，0,4）T就是最优解，对应的目标函数值：就是最优解，对应的目标函数值：S=14就是最优值，对应的就是最优值，对应的B4就是最优基。就是最优基。求最大化求最大化LP问题单纯形表解题步骤：问题单纯形表解题步骤：一一.LP问题化成标准型问题化成标准型,列初始单纯形表列初始单纯形表二二.判别判别1.若检验数全小于等于零，则基若检验数全小于等于零，则基B所对所对应的基础可行解应的基础可行解X就是最优解，终止。就是最优解，终止。2.若存在检验数大于零，但所对应的换若存在检验数大于零，但所对应的换入变量入变量Xk的系数向量的系数向量Pk0,则原问题无则原问题无最优解，终止。最优解，终止。3.若存

18、在检验数大于零，且对应的系数若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。列有大于零的分量，则需要换基迭代。三三.换基迭代换基迭代1.确定换入变量确定换入变量Xk，其中其中max(j 0)=k,xk为换入变量为换入变量 j=1,2,m2.确定换出基变量确定换出基变量Xr,根据最小比值原则根据最小比值原则min(bi/aik,aik 0,1im)=bl/blkalk为主元素为主元素,Xl为为换出基变量。换出基变量。对单纯形表对单纯形表T（B）进行初等行变换进行初等行变换（主元运算）得到新的单纯形表。（主元运算）得到新的单纯形表。经过上述有限次的换基迭代，就可得到经过上述有限次

19、的换基迭代，就可得到原问题的最优解，或判定无最优解。原问题的最优解，或判定无最优解。定理（求最小化的最优解判别准则）定理（求最小化的最优解判别准则）（1）若若若若=C-C=C-CB B B B-1-1A 0 A 0，则对应于基则对应于基则对应于基则对应于基B B的基础可的基础可的基础可的基础可行解行解行解行解x x就是就是就是就是基础最优解，此时的可行基就是最优基。基础最优解，此时的可行基就是最优基。基础最优解，此时的可行基就是最优基。基础最优解，此时的可行基就是最优基。（2）若检验数全大于等于零，且某一个非基变量的若检验数全大于等于零，且某一个非基变量的若检验数全大于等于零，且某一个非基变量

20、的若检验数全大于等于零，且某一个非基变量的检验数为检验数为检验数为检验数为0 0，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。，则线性规划问题有无穷多最优解。（无穷（无穷（无穷（无穷多最优解情况）多最优解情况）多最优解情况）多最优解情况）（3 3）若存在检验数小于零，但所对应的换入变量）若存在检验数小于零，但所对应的换入变量）若存在检验数小于零，但所对应的换入变量）若存在检验数小于零，但所对应的换入变量X Xm+km+k的系数向量的系数向量的系数向量的系数向量P Pm+km+k0,0,则原问题无最优解。（则原问题无最优解。（则原问题无最优解。（

21、则原问题无最优解。（无界解的情况）无界解的情况）无界解的情况）无界解的情况）确定换入变量时，找小于确定换入变量时，找小于0中的最小者。中的最小者。例例8 线性规划问题线性规划问题 一.大M法 当原问题求最大化时，假定人工变当原问题求最大化时，假定人工变量在目标函数中的系数为（量在目标函数中的系数为（-M）（）（M为为任意大正数），目标函数求最大化，必任意大正数），目标函数求最大化，必须把人工变量从基变量换出，否则，不须把人工变量从基变量换出，否则，不可能实现最大化。可能实现最大化。当原问题求最小化时，假定人工变量当原问题求最小化时，假定人工变量在目标函数中的系数为在目标函数中的系数为M（M为任

22、意大正为任意大正数），目标函数求最小化，必须把人工变数），目标函数求最小化，必须把人工变量从基变量换出，否则，不可能实现最小量从基变量换出，否则，不可能实现最小化。化。例例8 线性规划问题线性规划问题 -3 1 1 0 0 M M cj cj -3 1 1 0 0 M M 线性规划问题达到最优线性规划问题达到最优,最优解最优解及最优值为及最优值为:二.两阶段法 当用计算机求解含人工变量的线性规划问题当用计算机求解含人工变量的线性规划问题时，只能用很大的数代替时，只能用很大的数代替M M，否则，会造成计算否则，会造成计算机的错误。而两阶段法避免了这一错误。机的错误。而两阶段法避免了这一错误。第一

23、阶段：第一阶段：不考虑原问题是否存在基可行解；不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，构造目标给原线性规划问题加入人工变量，构造目标函数为人工变量的和，约束是原问题的约束。函数为人工变量的和，约束是原问题的约束。用单纯形法求解上述模型，若目标函数值为用单纯形法求解上述模型，若目标函数值为用单纯形法求解上述模型，若目标函数值为用单纯形法求解上述模型，若目标函数值为0 0，说明原问题有基可行解，进行第二阶段计算，否则，说明原问题有基可行解，进行第二阶段计算，否则，说明原问题有基可行解，进行第二阶段计算，否则，说明原问题有基可行解，进行第二阶段计算，否则，原问题无可行解。原问题无

24、可行解。原问题无可行解。原问题无可行解。第二阶段：第二阶段：将第一阶段计算得到的最终表，除将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数，换为原问去人工变量，将目标函数行的系数，换为原问题的目标函数系数，作为第二阶段计算的初始题的目标函数系数，作为第二阶段计算的初始表。表。例例9 线性规划问题线性规划问题 解：加入人工变量，给出第一阶段的线性规划解：加入人工变量，给出第一阶段的线性规划解：加入人工变量，给出第一阶段的线性规划解：加入人工变量，给出第一阶段的线性规划模型模型模型模型:人工变量已经换出，则=0，得到基可行解，将第一阶段的人工变量取消，填入原问题的目标函数的系数，进行第

25、二阶段运算。cj 0 0 0 0 0 1 1人工变量已经换出，则=0，得到基可行解，将第一阶段的人工变量取消，即上表中划去人工变量所在列，填入原问题的目标函数的系数，进行第二阶段运算。cj -31 1 0 0最优解为：x 1,=4,x 2,=1,x 3=9,最优值z=-2.应用举例应用举例例例例例1 1 配料问题配料问题配料问题配料问题 某工厂要用三种原材料某工厂要用三种原材料某工厂要用三种原材料某工厂要用三种原材料C C、P P、HH混合调配出三种不同规格混合调配出三种不同规格混合调配出三种不同规格混合调配出三种不同规格的产品的产品的产品的产品A A、B B、D D。已知产品的规格要求，产品

26、单价，每天能供已知产品的规格要求，产品单价，每天能供已知产品的规格要求，产品单价，每天能供已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价见下表。该厂应如何安排生产，应的原材料数量及原材料单价见下表。该厂应如何安排生产，应的原材料数量及原材料单价见下表。该厂应如何安排生产，应的原材料数量及原材料单价见下表。该厂应如何安排生产，使利润收入为最大？使利润收入为最大？使利润收入为最大？使利润收入为最大？产品名称 规格要求单价（元/kg)A 原材料C不少于50，原材料P不超过25 50 B原材料C不少于25，原材料P不超过50 35 D 不限 25原材料名称原材料名称原材料名称原材料名

27、称每天最多供应量（每天最多供应量（每天最多供应量（每天最多供应量（kg)kg)单价（元单价（元单价（元单价（元/kg)/kg)C C P P H H 100 100 100 100 60 60 65 65 25 25 35 35解：解：解：解：设设设设x xij ij为为为为产品产品产品产品A A、B B、D D中含中含中含中含C C、P P、HH的公斤数。列表如下：的公斤数。列表如下：的公斤数。列表如下：的公斤数。列表如下：原材料原材料原材料原材料 产品产品产品产品 C C P P H H A A x x1111 x x1212 x x1313 B B x x2121 x x2222 x x

28、2323 D D x x3131 x x3232 x x3333解：解：数学模型为：数学模型为：产品名称 规格要求单价（元/kg)A 原材料C不少于50，原材料P不超过25 50 B原材料C不少于25，原材料P不超过50 35 D 不限 25 原材料 产品 C P H A x11 x12 x13 B x21 x22 x23 D x31 x32 x33例例例例2 2 连续投资问题连续投资问题连续投资问题连续投资问题某部门有某部门有某部门有某部门有100100万元，在今后五年内考虑给下列项目进行投资万元，在今后五年内考虑给下列项目进行投资万元，在今后五年内考虑给下列项目进行投资万元，在今后五年内考

29、虑给下列项目进行投资项目项目项目项目A:A:从第一年到第四年每年年初需要投资，并于次年末回收从第一年到第四年每年年初需要投资，并于次年末回收从第一年到第四年每年年初需要投资，并于次年末回收从第一年到第四年每年年初需要投资，并于次年末回收 本利本利本利本利104104；项目项目项目项目B:B:从第三年初投资，到第五年末回收从第三年初投资，到第五年末回收从第三年初投资，到第五年末回收从第三年初投资，到第五年末回收 本利本利本利本利105105；但规定；但规定；但规定；但规定 最大投资额不超过最大投资额不超过最大投资额不超过最大投资额不超过4040万元；万元；万元；万元；项目项目项目项目C:C:从第

30、二年初投资，到第五年末回收从第二年初投资，到第五年末回收从第二年初投资，到第五年末回收从第二年初投资，到第五年末回收 本利本利本利本利108108；但规定；但规定；但规定；但规定 最大投资额不超过最大投资额不超过最大投资额不超过最大投资额不超过3030万元；万元；万元；万元；项目项目项目项目D:D:五年内每年可购买国债，于当年末归还，并加息五年内每年可购买国债，于当年末归还，并加息五年内每年可购买国债，于当年末归还，并加息五年内每年可购买国债，于当年末归还，并加息3 3；问该部门如何确定每年的投资计划，使五年末拥有的本金最大问该部门如何确定每年的投资计划，使五年末拥有的本金最大问该部门如何确定

31、每年的投资计划，使五年末拥有的本金最大问该部门如何确定每年的投资计划，使五年末拥有的本金最大？解：解：设设设设x xiAiA,x xiBiB,x xiCiC,x xiDiD,分别表示第分别表示第分别表示第分别表示第i i年年初给项目年年初给项目年年初给项目年年初给项目A A、B B、C C、D D的投资额。列表如下：的投资额。列表如下：的投资额。列表如下：的投资额。列表如下：年份年份年份年份项目项目项目项目 1 2 3 4 5 A B C D x x1A1A x x2A 2A x x3A 3A x x4A4A x x3B3B x x2C2Cx x1D 1D x x2D 2D x x3D 3D

32、x x4D 4D x x5D5D数学模型为：数学模型为：数学模型为：数学模型为：人力资源分配的问题人力资源分配的问题解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务班次时开始上班的司机和乘务人员数人员数,这样我们建立如下的数学模型。这样我们建立如下的数学模型。目标函目标函数：数：Min Z=xMin Z=x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5+x+x6 6 s.t.xs.t.x1 1+x+x6 6 60 60 x x1 1+x+x2 2 70 70 x x2 2+x+x3 3 60 60 x x3 3+x+x4 4 50 50 x x4 4+x

33、+x5 5 20 20 x x5 5+x+x6 6 30 30 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6 0 0 班次：班次：1 1 ，2 2 ，3 3，4 4，5 5，6 6 x x6 6+x+x1 1,x,x1 1+x+x2 2,x,x2 2+x+x3 3,x,x3 3+x+x4 4,x,x4 4+x+x5 5,x,x5 5+x+x6 6班次：班次：1 1 ，2 2 ，3 3，4 4，5 5，6 6 x x6 6+x+x1 1,x,x1 1+x+x2 2,x,x2 2+x+x3 3,x,x3 3+x+x4 4,x,x4 4+x+x5 5,x,x5

34、5+x+x6 6人力资源分配的问题人力资源分配的问题解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务人员数班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。这样我们建立如下的数学模型。目标函数：目标函数：Min Z=xMin Z=x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5+x+x6 6 s.t.xs.t.x6 6+x+x1 1 =60 60 x x1 1+x+x2 2 =70 70 x x2 2+x+x3 3 =60 60 x x1 1-x-x3 3 =1010 x x3 3+x+x4 4=50 =50 x x1 1+x+x4 4 =6

35、060 x x4 4+x+x5 5=20 =20 x x1 1-x-x5 5 =4=40 0 x x5 5+x+x6 6=30 =30 x x1 1+x+x6 6=7=70 0 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6 0 0 例例 求线性规划问题：求线性规划问题：max Z=2x1+x2 s.t.x1-x2-5 2x1-5 x2 10 x1,x2 0标准型为：标准型为：max Z=2x1+x2 s.t.-x1+x2+x3=5 2x1-5 x2+x4=10 x1,x2，x3，x4 0 max Z=2x1+x2 s.t.-x1+x2+x3=5 2x1-5

36、 x2+x4=10 x1,x2，x3，x4 0 20,P 2 0,无最优解。无最优解。例例例例 求线性规划问题：求线性规划问题：求线性规划问题：求线性规划问题：max Z=2xmax Z=2x1 1+4 x+4 x2 2 s.t.2x s.t.2x1 1+2x+2x2 2 1212 x x1 1+2x+2x2 2 8 8 4x 4x1 1 1616 4x 4x2 2 1212 x x1 1,x,x2 2 0 0标准型为：标准型为：标准型为：标准型为：max Z=2xmax Z=2x1 1+4 x+4 x2 2 s.t.2x s.t.2x1 1+2x+2x2 2+x+x3 3=12=12 x x1 1+2x+2x2 2+x+x4 4=8=8 4x 4x1 1+x x5 5=1616 4x 4x2 2+x x6 6=1212 x xi i 0,i=1,2,3,4,5,60,i=1,2,3,4,5,6最终表为：最终表为：最终表为：最终表为：x x6 6换入换入换入换入x x5 5换出换出换出换出