运筹学 (第三版) 第4章 目标规划 《运筹学》教材编写组 第3节 解目标规划 的单纯形法 第4节 灵敏度分析 第5节 应用举例 钱颂迪制作 清华大学出版社
第4章 目标规划 第3节 解目标规划 的单纯形法 第4节 灵敏度分析 第5节 应用举例 钱颂迪制作 运筹学 （第三版） 《运筹学》教材编写组 清华大学出版社
第3节解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模 型结构形式上没有本质的区别,所以可用单纯形法 求解。但要考虑目标规划的数学模型一些特点,作 以下规定: (1)因目标规划问题的目标函数都是求最小化,所以 以cz≥0,j=1,2灬,n为最优准则 (2)因非基变量的检验数中含有不同等级的优先因子, -;=SW"k=1,2…,K
第3节 解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模 型结构形式上没有本质的区别，所以可用单纯形法 求解。但要考虑目标规划的数学模型一些特点，作 以下规定： • (1) 因目标规划问题的目标函数都是求最小化，所以 以cj -zj≥0，j=1,2,…，n为最优准则。 • (2) 因非基变量的检验数中含有不同等级的优先因子， 即 cj − zj = ak jPk j =1,2,,n; k =1,2,,K
因P→>P,>>…>>P;从每个检验数的 整体来看:检验数的正、负首先决定于 P1的系数a1的正、负。若a1=0,这时 此检验数的正、负就决定于P2的系数a2 的正、负,下面可依此类推
• 因P1>>P2>>…>>PK；从每个检验数的 整体来看：检验数的正、负首先决定于 P1的系数α1j的正、负。若α1j=0，这时 此检验数的正、负就决定于P2的系数α2j 的正、负，下面可依此类推
解目标规划问题的单纯形法的计算步骤: (1)建立初始单纯形表,在表中将检验数行按优先 因子个数分别列成K行,置k=1。 (2)检査该行中是否存在负数,且对应的前k-1行 的系数是零。若有负数取其中最小者对应的变量为 换入变量,转(3)。若无负数,则转(5)。 ·(3)按最小比值规则确定换出变量,当存在两个和 两个以上相同的最小比值时,选取具有较高优先级 别的变量为换出变量 (4)按单纯形法进行基变换运算,建立新的计算表, 返回(2) (5)当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的数学模型化为标准型: 日标函数:minz=P+P2(dl2+a)+P3d3 2x1+x2+x x,+d1-a+=0 满足约束条件:{x+2x2+d2-=10 8x1+10x2+d2-d=56 x1,x2,x,d1,d+20,i=1,2,3
例4 试用单纯形法来求解例2。 将例2的数学模型化为标准型： = + + − = + + − = − + − = + + = = + + + − + − + − + − + + − + − , , , , 0, 1,2,3 8 10 56 2 10 0 2 11 min ( ) 1 2 1 2 3 3 1 2 2 2 1 2 1 1 1 2 1 1 2 2 2 3 3 x x x d d i x x d d x x d d x x d d x x x z Pd P d d P d s i i s 满足约束条件： 目标函数：
①取x,d;,d2,d3为初始基变量,列初始 单纯形表,见表4-1 C CgXB bx, dd+d-d+ ds- d3+0 xddd 0 10/2 561810 1|-1|56/10 CiZ P3-8|-10
① 取xs，d1 -，d2 -，d3 -为初始基变量，列初始 单纯形表，见表4-1。 cj P1 P2 P3 P4 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,检查P1行的检验数,因该行无负检验数, 故转(5)。 ③因k(=1)<K(=3),置k=k+1=2,返回到(2)。 ④当k2时,查出P行检验数中有-1、-2 取min(-1,-2)= 它对应的变量x2为换入变量,转入(3) 在表4-1上计算最小比值 11105610 =mi(,0 对应的变量d2为换出变量,转入(4)
② 取k=1，检查P1行的检验数，因该行无负检验数， 故转(5)。 ③ 因k(=1)＜K(=3)，置k=k+1=2，返回到(2)。 ④ 当k=2时,查出P2行检验数中有-1、-2； 取min(-1,-2)=-2。 它对应的变量x2为换入变量，转入(3)。 ⑤ 在表4-1上计算最小比值 它对应的变量d2 -为换出变量，转入(4) 2 10 ) 10 56 , 2 10 ,0. 1 11 = min( =
⑥即进行基变换运算,计算结果见表4-2 C Ⅹ Ⅹ d1-d1+|d2-|d2+|d3-|d+ 3/2 1/21/2 4 d1-|5|3/2 10 xd 51/21 [3] 551-16/3 CiZ 6PPP 8|-10
⑥ 即进行基变换运算，计算结果见表4-2 cj P1 P2 P3 P4 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ θ P3 xs d1- x2- d3- 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 -1 -8 -2 -10 1 1 5 1 -5 1
返回到(2)。依此类推,直至得到最终表 为止。见表4-3 表4-3 4 cB XB b xX2xs dr dI+ d2- d2+d3-d3+|0 2-2-121/26 d1-|2 1-13-3-1/2|1/24 43|-43-1/6|1624 -5/3531/3|-1/3 P3|-8 10
表4-3 返回到(2)。依此类推，直至得到最终表 为止。见表4-3。 cj P1 P2 P3 P4 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 -8 -2 -10 1 1 1 1
表4-3所示的解x*=2,x*=4为例1的满意解。 此解相当于图4-1的G点 x2B FE
表4-3所示的解x1 *=2，x2 *=4为例1的满意解。 此解相当于图4-1的G点