第四章--目标规划及图解法--运筹学

《第四章--目标规划及图解法--运筹学》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、清华大学出版社《运筹学教程》（第三版）运筹学基础胡运权主编教材第四章目标规划例1产品资源AB限量1车间2车间21.5125040单位利润80100求利润最大的生产方案利润maxz=80x1+100x2约束条件2x1+1.5x2≤50x1+2x2≤40x1，x2≥0例2由于各种原因，对例1的提出一些要求：1、B产品不超过10单位2、利润不低于1600元3、充分利用2车间的生产能力，尽量不加班。目标的含义本题三个目标依次表示为：1、B产品不超过10单位x2<=102、利润不低于1600元80x1+100x2>=16003、充分利用2车间的生产能力，尽量不加班。x1+2x2=40?问题分析

2、1）问题中有些限制是必须满足的，不能有丝毫妥协余地的，如对资源的约束：2x1+1.5x2≤50(1)x1+2x2≤40(2)这些约束条件是一种刚性约束，称之为系统约束or绝对约束问题分析2）除了前面提到的刚性约束外，例2中还提出一些的希望达到的目标。这些要求实际上也是约束条件，当然这些目标能到达最好，实在无法达到也是可以接受的，我们称之为目标约束如：1、B产品不超过10单位2、利润不低于1600元3、充分利用2车间的生产能力，尽量不加班。问题分析3）目标约束的目标一定要明确，给出确切的量值，即目标期望值B产品不超过10单位利润不低于1600元充分利用2车间的生产能力，尽量不加班如：问

3、题分析4）目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入了偏差变量的概念，偏差变量有正负之分，表示为：d+和d-，d+表示超过目标值的部分；d-表示不足目标值的部分.显然有d-·d+=0问题分析本题三个目标约束依次表示为：1、B产品不超过10单位x2+d1--d1+=102、利润不低于1600元80x1+100x2+d2--d2+=16003、充分利用2车间的生产能力，尽量不加班。x1+2x2+d3--d3+=40问题分析4）目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为P1级，次之者为P2级——优先因子P看成

4、实数P1>>P2问题分析5）有时同级别的目标中，其重要程度又有差别，则设置不同的权重（系数W）。6)x1+2x2≤40(系统约束)x1+2x2+d3--d3+=40(目标约束)当对某个资源约束既是系统约束，又是目标约束时，则不再表示为系统约束问题分析1、B产品不超过10单位d1+越小越好0最佳2、利润不低于1600元d2-越小越好0最好3、充分利用2车间的生产能力，尽量不加班d3-和d3+越小越好7）目标规划的目标问题分析7）目标规划的目标函数：目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值的偏差最小于是本题目标函数表示为：minZ={P1

5、d1+,P2d2-,P3(d3-+d3+)}问题分析2x1+1.5x2≤50x2+d1--d1+=1080x1+100x2+d2--d2+=1600x1+2x2+d3--d3+=40x1，x2，di-，di+≥0,i=1,2,3综上所述，本题的数学模型为：目标函数：minZ={P1d1+,P2d2-,P3(d3-+d3+)}约束条件目标规划的概念及数学模型数学模型为：目标函数minZ={Pl(∑k(Wlk-•dk-+Wlk+•dk+))，l=1,2,…,L}约束条件∑jckjxj+dk--dk+=bk,k=1,2,…,K∑jaijxj≤(=≥)bi,i=1,2,…,mxj，dk-，d

6、k+≥0,j=1,…n;k=1,2,…,K目标约束系统约束目标规划的图解法例22x1+1.5x2≤50x2+d1--d1+=1080x1+100x2+d2--d2+=1600x1+2x2+d3--d3+=40x1，x2，di-，di+≥0,i=1,2,3目标函数minZ={P1d1+,P2d2-,P3(d3-+d3+)约束条件3010203040102040Ox1x2d1-d1+图解法d2+d2-d3+d3-§4.3解目标规划的单纯形法§4.3解目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别，所以可用单纯形法进行求解。但要考虑目标规划数学模型的一些特点

7、：(1)因目标规划问题的目标函数都是求最小化，所以检验数的最优准则与我们前面讲到的线性规划检验准则是相反的，即以所有的σj≥0为最优准则；(2)因为非基变量的检验数中含有不同等级的优先因子，且Pi>>Pi+1，i=1,2,,L-1.所以在判断各检验数大小时得小心；解目标规划的单纯形法计算步骤(1)建立初始单纯形表，在表中将检验数行按优先因子个数分别列成L行，置k=1。(2)检查该行中是否存在负数，且对应的前k-1行的系数是0。若有，则取其中最小者对应的变