4.3 用单纯形法求解目标规划课件

第三节用单纯形法求解目标规划4.3用单纯形法求解目标规划本节内容的安排目标规划单纯形法的求解步骤例*题4.3用单纯形法求解目标规划目标规划求解问题过程明确问题，列出(或修改)目标的优先级和权系数构造目标规划的模型求出满意解满意否？分析各项目表完成情况据此制定出决策方案是否4.3用单纯形法求解目标规划

由目标规划数学模型的标准型可看出，它实质上是最小化的线性规划，所以可用单纯形法求解．这时，我们应该把目标优先等级系数Pi（i=1,2,…,k）理解为一种特殊的正常数，且注意到各等级系数之间的关系：P1»P2»…»Pk．而检验数就是各优先因子P1,P2,…,Pk的线性组合。当所有检验数都满足最优性条件（）时，从最终表上即可得出目标规划的解．ci-zj=∑αkjPk,j=1,2,…,n;k=1,2,…,KPk是指不同数量的很大的数d-是松弛变量d+是剩余变量Pk>>MPk+1(M是任意大的正数）4.3用单纯形法求解目标规划例:

用单纯形法求解下面目标规划问题:

解：引入松驰变量x3,将它们化为标准型：4.3用单纯形法求解目标规划cj000P100P2P30CBXBbx1x2x30x3605101000000P10[1]-201-10000036440001-100P34868000001-1P1-120010000P2000000100P3-6-800000010x3600201-5500000x101-201-100000360120-441-100P3480[20]0-66001-1P1000100000P2000000100P30-2006-60001

单纯形表14.3用单纯形法求解目标规划cj000P100P2P30CBXBbx1x2x30x3600201-5500000x101-201-100000360120-441-100P3480[20]0-66001-1P1000100000P2000000100P30-2006-600010x3120011-100-110x124/51002/5-2/5001/10-1/10036/5000-2/52/51-1-3/53/50x212/5010-3/103/10001/20-1/20P1000100000P2000000100P3000000010单纯形表1全部检验数非负，计算结束。4.3用单纯形法求解目标规划2．最优性检验

目标规划的最优性检验是分优先级进行的，从P1级开始依次到Pk级为止，具体检验Pi级目标时，可能有下述三种情况．

（1）若检验数矩阵的Pi

行系数均≥0，则Pi

级目标已达最优，应转入对Pi+1

级目标的寻优，直到i=k，计算结束。

1、建立初始单纯形表。

一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部，得检验数矩阵。单纯形法的计算步骤：4.3用单纯形法求解目标规划（2）若检验数矩阵的Pi中有负系数，且负系数所在列的前i-1行优先因子的系数全为0(例如-P2+223P3<0)

，可判定该检验数为负，则选该系数（若此类负系数有多个，则可选绝对值最大者）所在列对应的非基变量为入基变量，继续进行基变换．

（3）若检验数矩阵的Pi行中有负系数，但负系数所在列的前i-1行优先因子的系数有0，也有正数，（例如P2-3P3>0），即整个检验数的值可判为正（因Pi-1»Pi），故也应转入对Pi+1级目标的寻优，否则会使高优先级别的目标函数值劣化．4.3用单纯形法求解目标规划

3．基变换

①入基变量的确定：在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。4.3用单纯形法求解目标规划②出基变量的确定：按最小非负比值规则确定出基变量，当存在两个或两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。③主元素的确定：出基变量与入基变量在系数矩阵中对应的交叉点上的元素即为主元素．④迭代变换：同线性规划的单纯形法．得到新的单纯形表，获得一组新解⑤对求得的解进行分析：若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第1步。4.3用单纯形法求解目标规划4．从表中找到基本可行解和相应于各优先级的目标函数值每个单纯形表中常数列b，即为各基变量的相应取值．本题最后一个单纯形表已为最优，它对应的基本可行解：x1=24/5,x2=12/5,x3=12,d2-=36/5，即为最优解．这与图解法得到结果一致．

注意：在最优单纯形表中非基变量d1+和d3+的检验数都是零，故知本题有多个最优解．如以d1+为入基变量继续迭代，可得单纯形表2，如以d3+为入基变量继续迭代，可得单纯形表3．4.3用单纯形法求解目标规划cj000P100P2P30CBXBbx1x2x30x3600201-5500000x101-201-100000360120-441-100P3480[20]0-66001-1P1000100000P2000000100P30-2006-600010x3120011-100-110x124/51002/5-2/5001/10-1/10036/5000-2/52/51-1-3/53/50x212/5010-3/103/10001/20-1/20P1000100000P2000000100P3000000010单纯形表14.3用单纯形法求解目标规划cj000P100P2P30CBXBbx1x2x30x320010/310000

-5/65/60x181

4/3000001/6-1/6040

-4/30001-1

-2/32/30

8010/30-11001/6-1/6P1000100000P2000000100P3000000010表2续单纯形表14.3用单纯形法求解目标规划cj000P100P2P30CBXBbx1x2x30

120011-100-110x16101/101/2-1/200000000-3/5-111-1000x23011/20-1/41/40000P1000100000P2000000100P3000000010表3续单纯形表14.3用单纯形法求解目标规划例：用单纯形法求解下列目标规划问题4.3用单纯形法求解目标规划Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

-10－1－20002000P3

-56－8－1000000104.3用单纯形法求解目标规划Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

053/201－11/2-1/20000x251/21001/2-1/2000P3

63000-551－100

x3

63/2000-1/21/2001σkjP1

0000100000P2

0000011000P3

-6－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,故为换出变量。4.3用单纯形法求解目标规划Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300

x3

300002-2-1/21/21σkjP1

0000100000P2

0000011000P3

0000000100

最优解为x1＝2，x2＝4。但非基变量的检验数为零，故此题有无穷多最优解。θ=min｛4,24,－,6｝=4,故为换出变量。4.3用单纯形法求解目标规划Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000

x3

100-1－1-11001σkjP1

0000100000P2

0000011000P3

000000100

最优解为x1＝10/3,，x2=10/3。则这两个解得凸组合都是本例的满意解。4.3用单纯形法求解目标规划例:

用单纯形法求解下述目标规划问题：解:

第一步：列出初始单纯形表第二步：确定换入变量第三步：确定换出变量4.3用单纯形法求解目标规划第四步：用换入变量替换基变量中的换出变量4.3用单纯形法求解目标规划4.3用单纯形法求解目标规划

例、已知一个生产计划的线性规划模型为

其中目标函数为总利润，x1,x2

为产品A、B产量。现有下列目标：

1、要求总利润必须超过2500元；

2、考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；

3、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用单纯形法求解。4.3用单纯形法求解目标规划1、要求总利润必须超过2500元；

2、考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；

3、由于甲资源供应比较紧张，不要超过现有量140。4.3用单纯形法求解目标规划Cj00P100P302.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

-2500－30－1201000000P2

000000002.501P3

00000010000θ=min｛2500/30,140/2,60/1｝=60,故为换出变量。4.3用单纯形法求解目标规划Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σkjP1

－7000－12010030－3000P2

000000002.501P3

00000010000θ=min｛700/30,20/2,－,－｝=10,故为换出变量。4.3用单纯形法求解目标规划Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min｛400/15,－,－,－｝=10,故为换出变量。4.3用单纯形法求解目标规划Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75,故为换出变量。4.3用单纯形法求解目标规划Cj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000