《第四章目标规划及图解法运筹学精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章目标规划及图解法运筹学精选文档.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章目标规划及图解法运筹学本讲稿第一页，共二十九页例例1 1 产品资源A B限量1车间2车间 2 1.5 1 2 50 40单位利润 80 100求利润最大的生产方案求利润最大的生产方案利润利润 max z=80 xmax z=80 x1 1+100 x+100 x2 2约束约束条件条件2x2x1 1+1.5x+1.5x2 2 5050 x x1 1+2x+2x2 2 40 40 x x1 1，x x2 2 0 0本讲稿第二页，共二十九页例例2 2由于各种原因，对例由于各种原因，对例1 1的提出一些要求：的提出一些要求：1 1、B B产品不超过产品不超过1010单位单位 2 2、利润不低于、
2、利润不低于16001600元元 3 3、充分利用、充分利用2 2车间的生产能力，尽量不加班。车间的生产能力，尽量不加班。本讲稿第三页，共二十九页目标的含义目标的含义本题三个目标依次表示为：本题三个目标依次表示为：1 1、B B产品不超过产品不超过1010单位单位 x x2 2=10=1600=1600 3 3、充分利用、充分利用2 2车间的生产能力，尽量不加班。车间的生产能力，尽量不加班。x x1 1+2+2x x2 2 =40=40?本讲稿第四页，共二十九页问题分析问题分析1 1）问题中有些限制是必须满足的，不能有丝毫妥协余地）问题中有些限制是必须满足的，不能有丝毫妥协余地的，如对资源的约束
3、：的，如对资源的约束：2x2x1 1+1.5x+1.5x2 2 50 (1)50 (1)x x1 1+2x+2x2 2 40 (2)40 (2)这些约束条件是一种刚性约束，称之为这些约束条件是一种刚性约束，称之为 系统约束or绝对约束本讲稿第五页，共二十九页问题分析问题分析2 2）除了前面提到的刚性约束外，例）除了前面提到的刚性约束外，例2 2中还提出一些的希中还提出一些的希望达到的目标。这些要求实际上也是约束条件，当然望达到的目标。这些要求实际上也是约束条件，当然这些目标能到达最好，实在无法达到也是可以接受的，这些目标能到达最好，实在无法达到也是可以接受的，我们称之为我们称之为目标约束如：如
4、：1 1、B B产品不超过产品不超过1010单位单位 2 2、利润不低于、利润不低于16001600元元 3 3、充分利用、充分利用2 2车间的生产能力，尽量不加班。车间的生产能力，尽量不加班。本讲稿第六页，共二十九页问题分析问题分析3 3）目标约束的目标一定要明确，给出确切的量值，）目标约束的目标一定要明确，给出确切的量值，即即目标期望值n B B产品不超过产品不超过1010单位单位n 利润不低于利润不低于16001600元元n 充分利用充分利用2 2车间的生产能力，尽量不加班车间的生产能力，尽量不加班如：如：本讲稿第七页，共二十九页问题分析问题分析4 4）目标约束不是刚性的，而是弹性的，允
5、许在一定范）目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，围内有偏差，这更接近于实际。为表达这种灵活性，便引入了便引入了偏差变量的概念，偏差变量有的概念，偏差变量有正负之分，表示为：正负之分，表示为：d d+和和d d-，d d+表示超过目标值的部表示超过目标值的部分；分；d d-表示不足目标值的部分表示不足目标值的部分.显然有显然有d d-d d+=0=0本讲稿第八页，共二十九页问题分析问题分析本题三个目标约束依次表示为：本题三个目标约束依次表示为：1 1、B B产品不超过产品不超过1010单位单位 x x2 2+d d1 1-d d1 1+=10
6、=10 2 2、利润不低于、利润不低于16001600元元 8080 x x1 1+100+100 x x2 2+d d2 2-d d2 2+=1600=1600 3 3、充分利用、充分利用2 2车间的生产能力，尽量不加班。车间的生产能力，尽量不加班。x x1 1+2+2x x2 2 +d d3 3-d d3 3+=40=40本讲稿第九页，共二十九页问题分析问题分析4 4）目标的重要程度不同，因此目标的满足有先）目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为有后，即有优先级别。设最重要的为P1P1级，级，次之者为次之者为P2P2级级优先因子优先因子 P P看成实数看成实
7、数 P1P2P1P2本讲稿第十页，共二十九页问题分析问题分析5 5）有时同级别的目标中，其重要程度又有时同级别的目标中，其重要程度又 有差有差别，则设置不同的别，则设置不同的权重权重（系数（系数W W）。6)6)x x1 1+2x+2x2 2 40 (40 (系统约束系统约束)x x1 1+2+2x x2 2 +d d3 3-d d3 3+=40 =40(目标约束目标约束)当对某个资源约束既是系统约束，又是目标约当对某个资源约束既是系统约束，又是目标约束时，则不再表示为系统约束束时，则不再表示为系统约束本讲稿第十一页，共二十九页问题分析问题分析1 1、B B产品不超过产品不超过1010单位单位
8、 d d1 1+越小越好越小越好 0 0最佳最佳2 2、利润不低于、利润不低于16001600元元 d d2 2-越小越好越小越好 0 0最好最好 3 3、充分利用、充分利用2 2车间的生产能力，尽量不加班车间的生产能力，尽量不加班 d d3 3-和和 d d3 3+越小越好越小越好 7）目标规划的目标）目标规划的目标本讲稿第十二页，共二十九页问题分析问题分析7）目标规划的目标函数：）目标规划的目标函数：目标规划有多个目标，我们已经把它转化为目标约目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值束，整个问题的目标就是使得实施结果与目标期望值的偏差最小的
9、偏差最小 于是本题目标函数表示为：于是本题目标函数表示为：minZ=P1d1+,P2d2-,P3(d3-+d3+)本讲稿第十三页，共二十九页问题分析问题分析 2x 2x1 1+1.5x+1.5x2 2 50 50 x x2 2+d+d1 1-d-d1 1+=10=1080 x80 x1 1+100 x+100 x2 2+d+d2 2-d-d2 2+=1600 =1600 x x1 1+2x+2x2 2+d+d3 3-d-d3 3+=40 =40 x x1 1 ，x x2 2 ，d di i-，d di i+0,i=1,2,30,i=1,2,3综上所述，本题的数学模型为：综上所述，本题的数学模型
10、为：目标函数：目标函数：min Z=P1d1+,P2d2-,P3(d3-+d3+)约束约束条件条件本讲稿第十四页，共二十九页目标规划的概念及数学模型目标规划的概念及数学模型数学模型为：数学模型为：目标函数目标函数min Z=Pl(k(Wlk-dk-+Wlk+dk+)，l=1,2,L约束约束条件条件jckjxj+dk-dk+=bk,k=1,2,K jaijxj(=)bi,i=1,2,m xj，dk-，dk+0,j=1,n;k=1,2,K目标约束目标约束系统约束系统约束本讲稿第十五页，共二十九页目标规划的图解法目标规划的图解法例例2 2x 2x1 1+1.5x+1.5x2 2 50 50 x x2
11、 2+d+d1 1-d-d1 1+=10=1080 x80 x1 1+100 x+100 x2 2+d+d2 2-d-d2 2+=1600 =1600 x x1 1+2x+2x2 2+d+d3 3-d-d3 3+=40 =40 x x1 1 ，x x2 2 ，d di i-，d di i+0,i=1,2,30,i=1,2,3目标函数目标函数 min Z=P1 d1min Z=P1 d1+,P2 d2,P2 d2-,P3(d3P3(d3-+d3+d3+)约约束束条条件件30102030 4010 2040Ox1x2d1-d1+图解法图解法d2+d2-d3+d3-本讲稿第十六页，共二十九页4.3
12、解目标规划的单纯形法解目标规划的单纯形法本讲稿第十七页，共二十九页4.3 解目标规划的单纯形法解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构没有本质目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别，所以可用单纯形法进行求解。但要考虑目标规划数学的区别，所以可用单纯形法进行求解。但要考虑目标规划数学模型的一些特点：模型的一些特点：(1)因目标规划问题的目标函数都是求最小化，所以检验数的最优因目标规划问题的目标函数都是求最小化，所以检验数的最优准则与我们前面讲到的线性规划检验准则是相反的，即以所有的准则与我们前面讲到的线性规划检验准则是相反的，即以所有的j0为最优
13、准则；为最优准则；(2)因为非基变量的检验数中含有不同等级的优先因子，且因为非基变量的检验数中含有不同等级的优先因子，且 Pi Pi+1，i=1,2,L-1.所以在判断各检验数大小时得小心；所以在判断各检验数大小时得小心；本讲稿第十八页，共二十九页解目标规划的单纯形法计算步骤解目标规划的单纯形法计算步骤 (1)建立初始单纯形表，在表中将检验数行按优先因子个数分建立初始单纯形表，在表中将检验数行按优先因子个数分别列成别列成L行，置行，置k=1。(2)检查该行中是否存在负数，且对应的前检查该行中是否存在负数，且对应的前k-1行的系数行的系数是是0。若有，则取其中最小者对应的变量为换入变量，转。若有
14、，则取其中最小者对应的变量为换入变量，转(3)；否则，转；否则，转(5)。(3)按最小比值规则确定换出变量，当存在两个或两个按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高优先级别的变量为换以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。出变量。(4)按单纯形法进行基变换运算，建立新的单纯形表。按单纯形法进行基变换运算，建立新的单纯形表。(5)当当k=L时，计算结束，表中解即为满意解。否则置时，计算结束，表中解即为满意解。否则置k=k+1，返回返回(2)。本讲稿第十九页，共二十九页例例5 用单纯形法来解例用单纯形法来解例2 引入松弛变量引入松弛变量x3
15、，将例，将例2的目标规划中约束条件转的目标规划中约束条件转换成线性规划标准形式，如下：换成线性规划标准形式，如下：Min P1d1-，P2 d2+，P3 d3-s.t.5x1+10 x2+x3 =60 x1-2x2 +d1-d1+=0 4x1+4x2 +d2-d2+=36 6x1+8x2 +d3-d3+=48 x1,x2,x3,di-,di+0 ,i=1,2,3.本讲稿第二十页，共二十九页 Min z=P1d1-+P2 d2+P3 d3-s.t.5x1+10 x2+x3 =60 x1-2x2 +d1-d1+=0 4x1+4x2 +d2-d2+=36 6x1+8x2 +d3-d3+=48 x1,
16、x2,x3,di-,di+0 ,i=1,2,3.该目标规划和下面线性规划问题等价该目标规划和下面线性规划问题等价本讲稿第二十一页，共二十九页C 0 0 0 P1 0 0 P2 P3 0CB XBb x1 x2 x3 d1 d1+d2 d2+d3 d3+0P10 P3x3d1d2d36003648 5 10 1 0 0 0 0 0 0 1 2 0 1 1 0 0 0 0 4 4 0 0 0 1 1 0 0 6 8 0 0 0 0 0 1 1P1P2P3 1 2 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 6 8 0 0 0 0 0 0 1建立初始单纯形表建立初始单纯形表本讲稿
17、第二十二页，共二十九页C 0 0 0 P1 0 0 P2 P3 0CB XBb x1 x2 x3 d1 d1+d2 d2+d3 d3+000 0 x3x1d2x21224/536/512/5 0 0 1 1 1 0 0 1 1 1 0 0 2/5 2/5 0 0 1/10 1/10 0 0 0 2/5 2/5 1 1 3/5 3/5 0 1 0 3/10 3/10 0 0 1/20 1/20P1P2P3 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0最终单纯形表最终单纯形表最优解最优解 X1=（24/5，12/5）本讲稿第二十三页，共
18、二十九页C 0 0 0 P1 0 0 P2 P3 0CB XBb x1 x2 x3 d1 d1+d2 d2+d3 d3+000 0 x3x1d2d1+20848 0 10/3 1 0 0 0 0 5/6 5/6 1 4/3 0 0 0 0 0 1/6 1/6 0 4/3 0 0 0 1 1 2/3 2/3 0 10/3 0 1 1 0 0 1/6 1/6P1P2P3 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0n C 0 0 0 P1 0 0 P2 P3 0CB XBb x1 x2 x3 d1 d1+d2 d2+d3 d3+000
19、0d3+x1d2x212603 0 0 1 1 1 0 0 1 1 1 0 1/10 1/2 1/2 0 0 0 0 0 0 3/5 1 1 1 1 0 0 0 1 1/20 1/4 1/4 0 0 0 0P1P2P3 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0n 本讲稿第二十四页，共二十九页C 0 0 0 P1 0 0 P2 P3 0CB XBb x1 x2 x3 d1 d1+d2 d2+d3 d3+000 0d3+x1d1+x369915 0 2 0 0 0 3/2 3/2 1 1 1 1 0 0 0 1/4 1/4 0 0
20、0 3 0 1 1 1/4 1/4 0 0 0 5 1 0 0 5/4 5/4 0 0P1P2P3 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0n n 分别得到剩下的三个最优解：分别得到剩下的三个最优解：X2=（8，0）；）；X3=（6，3）；）；X4=（9，0）本讲稿第二十五页，共二十九页X X1 1X X2 2X X3 3X X4 4本讲稿第二十六页，共二十九页目标规划应用举例之一目标规划应用举例之一 A B C工时限制工时/件 5 8 12 120利润/件 100 140 252要求：要求：P1:P1:充分利用工时充分利用工时
21、 P2P2：A A、B B、C C分别达到分别达到5 5、5 5、8 8件，并按件，并按 工时利润确定权重工时利润确定权重 P3P3：加班时间不要超过加班时间不要超过1616小时小时 P4P4：A A、B B、C C月销售量月销售量1010、1212、1010件件 P5P5：尽量减少加班时间尽量减少加班时间例例1.1.本讲稿第二十七页，共二十九页目标规划应用举例之一目标规划应用举例之一min Z=P1d1-+P2(40d2-+35d3-+42d4-)+P3 d5+P4(d6-+d7-+d8-)+P5 d1+5x1+8x2+12x3+d1-d1+=120 x1+d2-d2+=5 x2+d3-d3+=5 x3+d4-d4+=8 5x1+8x2+12x3+d5-d5+=120+16 x1+d6-d6+=10 x2+d7-d7+=12 x3+d8-d8+=10 xj,di-,di+0,j=1,2,3 i=1,2,5本讲稿第二十八页，共二十九页4.5 目标规划应用举例目标规划应用举例例例8 P117本讲稿第二十九页，共二十九页