第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