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

第四章目标规划及图解法运筹学第一页，共二十九页，编辑于2023年，星期五例1

产品资源AB限量1车间2车间21.5125040单位利润80100求利润最大的生产方案利润maxz=80x1+100x2约束条件2x1+1.5x2

≤

50x1+2x2

≤

40x1，x2

≥0第二页，共二十九页，编辑于2023年，星期五例2由于各种原因，对例1的提出一些要求：

1、B产品不超过10单位

2、利润不低于1600元

3、充分利用2车间的生产能力，尽量不加班。第三页，共二十九页，编辑于2023年，星期五目标的含义本题三个目标依次表示为：

1、B产品不超过10单位

x2<=102、利润不低于1600元

80x1+100x2>=16003、充分利用2车间的生产能力，尽量不加班。

x1+2x2=40?第四页，共二十九页，编辑于2023年，星期五问题分析1）问题中有些限制是必须满足的，不能有丝毫妥协余地的，如对资源的约束：

2x1+1.5x2≤50(1)x1+2x2≤40(2)

这些约束条件是一种刚性约束，称之为

系统约束or绝对约束第五页，共二十九页，编辑于2023年，星期五问题分析2）除了前面提到的刚性约束外，例2中还提出一些的希望达到的目标。这些要求实际上也是约束条件，当然这些目标能到达最好，实在无法达到也是可以接受的，我们称之为目标约束如：1、B产品不超过10单位

2、利润不低于1600元

3、充分利用2车间的生产能力，尽量不加班。第六页，共二十九页，编辑于2023年，星期五问题分析3）目标约束的目标一定要明确，给出确切的量值，即目标期望值B产品不超过10单位利润不低于1600元

充分利用2车间的生产能力，尽量不加班如：第七页，共二十九页，编辑于2023年，星期五问题分析4）目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入了偏差变量的概念，偏差变量有正负之分，表示为：d+和d-，d+表示超过目标值的部分；

d-表示不足目标值的部分.显然有d-·d+=0第八页，共二十九页，编辑于2023年，星期五问题分析本题三个目标约束依次表示为：

1、B产品不超过10单位

x2+d1-

-d1+=102、利润不低于1600元

80x1+100x2+d2--d2+

=16003、充分利用2车间的生产能力，尽量不加班。

x1+2x2+d3--d3+=40第九页，共二十九页，编辑于2023年，星期五问题分析4）目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为P1级，次之者为P2级——优先因子

P看成实数P1>>P2第十页，共二十九页，编辑于2023年，星期五问题分析5）有时同级别的目标中，其重要程度又有差别，则设置不同的权重（系数W）

。6)x1+2x2

≤

40(系统约束)x1+2x2+d3--d3+=40(目标约束)

当对某个资源约束既是系统约束，又是目标约束时，则不再表示为系统约束第十一页，共二十九页，编辑于2023年，星期五问题分析1、B产品不超过10单位d1+越小越好

0最佳2、利润不低于1600元 d2-越小越好0最好

3、充分利用2车间的生产能力，尽量不加班

d3-

和d3+越小越好7）目标规划的目标第十二页，共二十九页，编辑于2023年，星期五问题分析7）目标规划的目标函数：目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值的偏差最小于是本题目标函数表示为：

minZ={P1d1+,P2d2-

,P3(d3-+d3+)}第十三页，共二十九页，编辑于2023年，星期五问题分析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+)}约束条件第十四页，共二十九页，编辑于2023年，星期五目标规划的概念及数学模型数学模型为：目标函数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-，dk+

≥0,j=1,…n;k=1,2,…,K目标约束系统约束第十五页，共二十九页，编辑于2023年，星期五目标规划的图解法例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-第十六页，共二十九页，编辑于2023年，星期五§4.3解目标规划的单纯形法第十七页，共二十九页，编辑于2023年，星期五§4.3解目标规划的单纯形法

目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别，所以可用单纯形法进行求解。但要考虑目标规划数学模型的一些特点：(1)因目标规划问题的目标函数都是求最小化，所以检验数的最优准则与我们前面讲到的线性规划检验准则是相反的，即以所有的σj≥0为最优准则；(2)因为非基变量的检验数中含有不同等级的优先因子，且Pi>>Pi+1，i=1,2,,L-1.所以在判断各检验数大小时得小心；第十八页，共二十九页，编辑于2023年，星期五解目标规划的单纯形法计算步骤

(1)建立初始单纯形表，在表中将检验数行按优先因子个数分别列成L行，置k=1。(2)检查该行中是否存在负数，且对应的前k-1行的系数是0。若有，则取其中最小者对应的变量为换入变量，转(3)；否则，转(5)。(3)按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。(4)按单纯形法进行基变换运算，建立新的单纯形表。(5)当k=L时，计算结束，表中解即为满意解。否则置k=k+1，返回(2)。第十九页，共二十九页，编辑于2023年，星期五例5用单纯形法来解例2

引入松弛变量x3，将例2的目标规划中约束条件转换成线性规划标准形式，如下：

Min{P1d1-，P2d2+，P3d3-}

s.t.5x1

+10x2+

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.

第二十页，共二十九页，编辑于2023年，星期五

Minz=P1d1-+P2d2++P3d3-

s.t.5x1

+10x2+

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.

该目标规划和下面线性规划问题等价第二十一页，共二十九页，编辑于2023年，星期五C

00

0

P1

0

0

P2

P3

0CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0P10

P3x3d1－d2－d3－60036485101000000

[

1]－201－10000440001－10068000001－1σP1P2P3

－120010000000000100－6－80000001建立初始单纯形表第二十二页，共二十九页，编辑于2023年，星期五C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000x3x1d2－x21224/536/512/50011－100－111002/5－2/5001/10－1/10000－2/52/51－1－3/53/5010－3/103/10001/20－1/20σP1P2P3000100000000000100000000010最终单纯形表最优解X1=（24/5，12/5）第二十三页，共二十九页，编辑于2023年，星期五C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000x3x1d2－d1+20848010/310000－5/65/614/3000001/6－1/60－4/30001－1－2/32/3010/30－11001/6－1/6σP1P2P3000100000000000100000000010

C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000d3+x1d2－x2126030011－100－11101/101/2－1/2000000－3/5－111－100011/20－1/41/40000σP1P2P3000100000000000100000000010

第二十四页，共二十九页，编辑于2023年，星期五C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000d3+x1d1+x3699150－20003/2－3/2－11110001/4－1/400030－111/4－1/40005100－5/45/400σP1P2P30001000000000001