运筹学 (第三版) 第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 满足约束条件： 目标函数：