上海交通大学：《线性规划与非线性规划》教学资源_第4章 目标规划 第3节 解目标规划的单纯形法 第4节 灵敏度分析 第5节 应用举例

第3节解耳标规划的单纯形法 ·目标规划的数学模型结构与线性规划的 数学模型结构形式上没有本质的区别， 所以可用单纯形法求解

第3节 解目标规划的单纯形法 • 目标规划的数学模型结构与线性规划的 数学模型结构形式上没有本质的区别， 所以可用单纯形法求解

由目标规划数学模型的特点，规定 (1)因目标规划问题的目标函数都是求最小 化，所以以c-z≥0，j=1,2,n为最优准则 (2)因非基变量的检验数中含有不同等级的优 先因子，即 Cj-2j=∑Qg%j=1,2,…,n,k=1,2,…,K 因P>>P2>>.>>Px;从每个检验数的整体 来看：检验数的正、负首先决定于P,的系 数a的正、负。若a0, 这时此检验数 的正、负就决定于P2的系数a2的正、负， 下面可依此类推

由目标规划数学模型的特点，规定 (1)因目标规划问题的目标函数都是求最小 化，所以以 cj-zj ≥ 0 ，j=1,2, … ， n为最优准则 (2) 因非基变量的检验数中含有不同等级的优 先因子，即 因 P 1>>P 2>>…>>PK；从每个检验数的整体 来看：检验数的正、负首先决定于 P 1的系 数α1j的正、负。若α1j=0，这时此检验数 的正、负就决定于 P 2的系数α2j的正、负， 下面可依此类推 KknjPazc kkjjj =− ∑ = " = ",,2,1;,,2,1

解目标规划问题的单纯形法的计算步骤： (1)建立初始单纯形表，在表中将检验数行按优先因 子个数分别列成K行，置k=1。 (2)检查该行中是否存在负数，且对应的前k-1行的 系数是零。若有负数取其中最小者对应的变量为换 入变量，转(3)。若无负数，则转（⑤） (3)按最小比值规则确定换出变量，当存在两个和两 个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量。 (4)按单纯形法进行基变换运算，建立新的计算表， 返回(2) (⑤)当k=K时，计算结束。表中的解即为满意解。否 则置k=k+1,返回到(2)

解目标规划问题的单纯形法的计算步骤： (1) 建立初始单纯形表，在表中将检验数行按优先因 子个数分别列成K行，置k=1。 (2) 检查该行中是否存在负数，且对应的前k-1行的 系数是零。若有负数取其中最小者对应的变量为换 入变量，转(3)。若无负数，则转(5)。 (3) 按最小比值规则确定换出变量，当存在两个和两 个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量。 (4) 按单纯形法进行基变换运算，建立新的计算表， 返回(2)。 (5) 当k=K时，计算结束。表中的解即为满意解。否 则置k=k+1，返回到(2)

例4 试用单纯形法来求解例2。 将例2的数学模型化为标准型： min z Pd+P (d2 +d2)+Pd3 2x1+X2+X =11 七-x2+4-d1=0 s.t.3 七1+2x2+d-d=10 8x1+10x2+d-d=56 七1，x2,x,,≥0，i=1,2,3

例4 试用单纯形法来求解例2。 将例 2的数学模型化为标准型： 11 2 2 2 33 1 2 1 21 1 1 22 2 1 23 3 1 2 min ( ) 2 1 1 0 .. 2 10 8 10 56 , , , , 0, 1,2,3 s si i z Pd P d d Pd x xx x xd d st x x d d x xd d xx xd d i + −+ − − + − + − + − + = + ++ ⎧ ++ = ⎪ − +−= ⎪ ⎪ ⎨ + +−= ⎪ + +−= ⎪ ⎪ ⎩ ≥ =

①取×，d,d2,d3为初始基变量，列初始 单纯形表，见表4-1。 Ci P1 P2P2 P3 CB XB b X1 X2 Xs d1- d1+ d2- d2+ d3- d3+ 0 2 1 11/1 B 101086 118 11 1 -1 1 -1 10/2 1 -1 56/10 1 Cj-Zj a o a 8 品 2 1

① 取xs，d1-，d2-，d3-为初始基变量，列初始 单纯形表，见表4-1。 cj P1 P2 P2 P3 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ θ P2 P3 xs d1- d2- d3- 11 0 10 56 2 1 1 8 1 -1 [2] 10 1 1 -1 1 -1 1 -1 11/1 / 10/2 56/10 cj-zj P1 P2 P3 -1 -8 -2 -10 1 2 1

2 取k=1,检查P,行的检验数，因该行无负 检验数，故转（⑤）。 3 因k(=1)<K(=3),置k=k+1=2,返回到(2) 当k=2时，查出P,行检验数中有-1、-2； 取min(-1,-2)=-2。 它对应的变量x2为换入变量，转入(3)。 5 在表4-1上计算最小比值 1 10 0=min 1056 1,-210 2 它对应的变量d2为换出变量，转入(4)

② 取k=1，检查P 1行的检验数，因该行无负 检验数，故转(5)。 ③ 因k(=1)＜K(=3)，置k=k+1=2，返回到(2) ④ 当k=2 时 ,查出 P 2行检验数中有-1 、-2 ； 取min( -1, -2) = - 2 。 它对应的变量x2为换入变量，转入(3) 。 ⑤ 在表4-1上计算最小比值 它对应的变量 d 2 -为换出变量，转入(4) 11 10 56 10 min( , , , ) 1 2 10 2 θ = − =

6 进行基变换运算，计算结果见表4-2 Ci P1 P2 P2 P3 CB XB b X1 X2 Xs d1- d1+ d2- d2+ d3- d3+ 0 65 3/2 1 -1/2 1/2 4 30123 1 -1 1/2 -112 10/3 1 1 -1/2 10 P3 6 5 5 1 -1 6/3 P1 1 Cj-Zj 1 1 -3 5 -5 1

⑥ 进行基变换运算，计算结果见表4-2 cj P1 P2 P2 P 3 C B X B b x1 x 2 x s d 1- d 1+ d 2- d 2+ d 3- d 3 + θ P3 x s d 1 - x 2 d 3 - 6 5 5 6 3/2 3/2 1/2 [3] 1 1 1 -1 -1/2 1/2 1/2 -5 1/2 -1/2 -1/2 5 1 -1 4 10/3 10 6/3 cj-zj P1 P2 P3 -3 1 1 5 1 -5 1

返回到(2)。依此类推，直至得到最终表 为止。见表4-3。 表4-3 Ci P1 P2 P2 P3 Ce XB b X1 X2 Xs d1- d1+ d2- d2+ d3- d3+ 1 2 -2 -1/2 1/2 6 2 1 -1 3 -3 -1/2 112 4 42 1 413 -4/3 -1/6 116 24 1 -5/3 5/3 1/3 -1/3 P1 1 Cj-Zj P2 1 1 3 1 d+的检验数为0，这表示存在多重解

表4-3 cj P1 P2 P2 P3 返回到(2)。依此类推，直至得到最终表 为止。见表4-3。 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ θ xs d1- x2 x1 3 2 4 2 1 1 1 1 -1 2 3 4/3 -5/3 -2 -3 -4/3 5/3 -1/2 -1/2 -1/6 1/3 1/2 1/2 1/6 -1/3 6 4 24 cj-zj P1 P2 P3 1 1 1 1 d3+的检验数为0，这表示存在多重解

表4-3所示的解x1*=2,x2*=4为例2的满意解。 此解相当于G点 d di FE d 0 A ds ③ ②

表4-3所示的解x 1 *=2，x 2 *=4为例 2的满意解。 此解相当于 G 点

检查表4-3的检验数行，发现非基变量d,+的检验数为 0,这表示存在多重解。在表4-3中以非基变量d3+为换 入变量，d1为换出变量，经迭代得到表4-4。 Ci P1 P2 P2 P3 0 Ce Xe b 1 X2 Xs d1- d1+ d2- d2+ d3- d3+ Xs 1 1 -1 1 -1 1 4 2 -2 6 -6 -1 1 X2 10/3 1 -1/3 1/3 1/13 -1/3 X1 10/3 1 2/3 -2/3 1/3 -1/3 1 Cj-Zj 2 1 1 P3 1

检查表4-3的检验数行，发现非基变量d 3 +的检验数为 0，这表示存在多重解。在表4-3中以非基变量d 3 +为换 入变量，d 1 -为换出变量，经迭代得到表4-4。 cj P1 P 2 P2 P 3 C B X B b x 1 x 2 x s d 1- d 1+ d 2- d 2+ d 3- d 3 + θ x s d 3 + x 2 x 1 1 4 10/3 10/3 1 1 1 -1 2 -1/3 2/3 1 -2 1/3 -2/3 -1 6 1/3 1/3 1 -6 -1/3 -1/3 -1 1 cj-zj P1 P2 P3 1 1 1 1