运筹学课件-第四章目标规划.ppt

1、第四章 目标规划,一、目标规划问题及其数学模型 二、目标规划的图解法 三、解目标规划的单纯形法 四、应用举例,一、目标规划问题及其数学模型,例1：,LP： maxZ=6X1 + 8X2,解得：最优生产计划为： x1=8件， x2=2件， max z=64元。,线性规划中的问题,从计划人员的立场上看： 1、这是一个单目标最优化问题。但一个计划问题要满足多方面的要求。财务、物资、销售、计划 2、线性规划有最优解的必要条件是其可行解集非空。但实际问题有时不能满足这样的要求。 3、线性规划解的可行性和最优性具有十分明确的意义，但那是针对特定数学模型而言的。实际问题中往往还会作某种调整和修改。 目标规划

2、在处理实际决策问题时，承认各项决策的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。,目标规划的数学模型,例2 假设在例1的基础上，计划人员还被要求考虑如下的意见： (1)由于产品II销售疲软，故希望产品II的产量不超过产品I的一半； (2)原材料严重短缺，生产中应避免过量消耗； (3)最好能节约4小时设备工时； (4)计划利润不少于48元。 最后达成了一致意见：（目标） (1)原材料使用限额不得突破； (2)产品II产量要求必须优先考虑； (3)设备工时问题其次考虑（节约4个）； (4)最后考虑计划利润的要求。,1、偏差变量 对每一个决策目标，引入正、负偏差变量d+和d- 。 d

3、+ : 决策值超过目标值的部分。 d- ：决策值未达到目标值的部分。 d+ 0和d- 0 d+d- 0 2绝对约束和目标约束 绝对约束：必须严格满足的等式或不等式约束。 目标约束：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负的偏差。 绝对约束是硬约束。目标约束是一种软约束，目标约束中决策值和目标值之间的差异用偏差变量表示。必为等式。,目标规划数学模型涉及到基本概念,3优先因子和权系数 不同目标的主次轻重有两种差别。 一种差别是绝对的，可用优先因子Pt来表示。优先因子间的关系为PtPt+1，即Pt对应的目标比Pt+1对应的目标有绝对的优先性。 另一种差别是相

4、对的，这些目标具有相同的优先因子，它们的重要程度可用权系数的不同来表示。,目标规划数学模型涉及到基本概念,4目标规划的目标函数 目标规划的目标函数(又称为准则函数或达成函数)由各目标约束的偏差变量及相应的优先因子和权系数构成。其目标函数只能是极小化。 有三种基本表达式： (1)要求恰好达到目标值。 minf(d+d- ) (2)要求不超过目标值，但允许不足目标值。 minf(d+ ) (3)要求不低于目标值，但允许超过目标值。 minf(d- ),目标规划数学模型涉及到基本概念,其他 minf(d+d- ) minf(d-d+ ),例2的数学模型,(1)原材料使用限额不得突破； (2)产品II

5、产量要求必须优先考虑； (3)设备工时问题其次考虑（节约4个）； (4)最后考虑计划利润的要求。（不少于48）,5X1+10X2 60 X1 -2X2 +d1- -d1+=0 4X1 +4X2 +d2- -d2+=36 6X1 +8X2 +d3- -d3+=48 X1 , X2 , di- , di+ 0 di- . di+ =0 i=1,2,3,minP1d1- , P2(d2+), P3(d3-),目标规划的数学模型,例1、,LP： maxZ=100X1 + 80X2,X* =(50,100) Z* =13000,目标：去年总收益9000，增长要求11.1% 即：今年希望总收益不低于100

6、00,引入 d+：决策超过目标值部分(正偏差变量) d-：决策不足目标值部分(负偏差变量),目标约束： 100X1+80X2 -d+d- =10000 d+d- =0 d+,d- 0,例2,(1)、原材料价格上涨，超计划要高价购买，所以要严格控制。 (2)、市场情况，产品销售量下降，产品的产量不大于产品的产量。 (3)、充分利用设备，不希望加班。 (4)、尽可能达到并超过利润计划指标56千元。,建模：,(1)、设定约束条件。(目标约束、绝对约束),(2)、规定目标约束优先级。,(3)、建立模型,2X1+X2 11 X1 -X2 +d1- -d1+=0 X1 +2X2 +d2- -d2+=10

7、8X1 +10X2 +d3- -d3+=56 X1 , X2 , di- , di+ 0 di- . di+ =0,d1- : X1产量不足X2 部分 d1+ : X1产量超过X2 部分 d2- : 设备使用不足10 部分 d2+ :设备使用超过10 部分 d3- : 利润不足56 部分 d3+ :利润超过56 部分,设X1 ，X2为产品，产品产量。,目标函数 minZ1 = d1+ minZ2 = d2- +d2+ minZ3 = d3-,或 minZ=P1d1+P2(d2-+d2+)+P3(d3-) minP1d1+ , P2(d2-+d2+), P3(d3-),例3、电视机厂装配25寸和

8、21寸两种彩电，每台电视机需装备时间1小时，每周装配线计划开动40小时，预计每周25寸彩电销售24台，每台可获利80元，每周21寸彩电销售30台，每台可获利40元。,该厂目标： 1、充分利用装配线，避免开工不足。 2、允许装配线加班，但尽量不超过10小时。 3、尽量满足市场需求。,解：设X1 , X2 分别表示25寸，21寸彩电产量,minZ=P1d1-+P2d2+P3(2d3-+d4-),X1+X2 +d1- -d1+=40 X1 +X2+d2- -d2+=50 X1+d3- -d3+=24 X2 +d4- -d4+=30 X1 , X2 , di- , di+ 0 (i=1,2,3,4),

9、小结：,1、约束条件： 硬约束(绝对约束) 软约束 (目标约束)，引入d-, d+,2、目标优先级： P1 P2 PL 同一级中可以有若干个目标：P21 , P22 ,P23 其重要程度用权重系数W21 ,W22 ,W23 表示,3、目标函数： (1)、恰好达到目标： minZ= f (d -+d+) (2)、超过目标： minZ= f (d -) (3)、不超过目标： minZ= f (d+),一般模型：,4、目标规划：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。, Z=0：各级目标均已达到 Z0：部分目标未达到。, 目标函数中只有偏差变量。, 目标函数总是求偏差变量最小。,二、

10、目标规划的图解法,例1、,E,(1)、绝对约束可行域OBEC (2)、目标约束满意域CBE (3)、多个可行满意解： (60,50),10000; (70,50),11000; E(50,100),13000。 (4)、Zmin =0,例2：用图解法求解。,X2,4,3,X1,问题的解为：线段DE,例3、,解： 可行域OAB 目标1： OBC 目标2：ED线段 目标3：GD线段, Zmin =0,例4、,解：,(1)、满足目标、的满意域为ABCD,(2)、先考虑的满意域为ABEF 再考虑，无公共满意域。,(4)、Zmin =d4- =30 - X2 + d4+=30-26=40,应用案例：,红

11、星制药厂生产A、B两种药品，有关数据如下：,（1）求最优生产计划 （2）电力可多供应20（百度），利润能否达240（万元）？ （3）若（2）达不到，改为以下目标规划 目标1：保证利润不低于240万元 目标2：耗电量、耗煤量应尽量少地超过120,解：,(1)、,用单纯形法求解，得解为： X1 =20， X2=20 ，Zmax =200(万元),(2)、用灵敏度分析，可得： X1 =15， X2=30 ，Zmax =210,(3)、建立目标规划模型,分析：满足P1，部分满足P2的点有A,B,C,D (如果不考虑A，B产品均需生产) 由解方程可得：A(40，0)， B(60，0) C(24，24)，

12、 D(0，60),比较与目标的偏差,A点：ZA = P1d1- + P2d2+ P2d3+ = 0+0+ P2d3+ = (4X1+ 2X2 + d3- - 120) P2 = (440 -120） P2=40P2,B点：ZB = 120P2 C点：ZC = 24P2 D点：ZD = 60P2,结论：取C点,方案：A24 B24 利润240 电力未超，煤超用24(百吨),为实施此项方案，需要进行技术改造，降低单位耗煤量,按照120/144的比例 原来：A4 B2 现在：A4120/144=4 5/63.33 B25/6=1.66 可在原资源条件下实施计划,三、解目标规划的单纯形法,计算步骤：

13、1）建立初始单纯形表。在表尾将检验数行按优先因子个数分别列成k行，置k=1 2）检验该行中是否存在负数且对应的前k-1行的系数为0。若有取其中最小者对应的变量为换入变量，转3）。若无负数，转5）。 3）按最小比值规则确定换出变量，当存在两个及两个以上相同的最小比值时，选取具有较高级别的变量为换出变量。 4）按单纯形法进行基变换运算，建立新计算表，返2）。 5）当k=K时，计算结束。其中的解即为满意解。 否则置k=K+1,返2）。,课本例5,minP1d1- , P2d2+, P3d3-,解：化标准形。 列初始单纯形表,上面例3用单纯形法求解。,相当G x=(2 , 4) 利润为56,说明： 1

14、，还可以再做一步，d3+ d1-,可得 X=(10/3，10/3)，对应于D点 2，初始表中检验数行：要注意化为非基变 量表示式再填入,例：用单纯形法求解,解：列初始单纯形表,所以，原问题的解为：X124，X226。 d4- 4，所以市场需求没有满足，每周21寸彩电只生产26台。,1、友谊农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。各种作物每亩需施化肥分别为012吨、020吨、015吨。预计秋后玉米每亩可收获500千克，售价为024元千克，大豆每亩可收获200千克，售价为120元千克，小麦每亩可收获350千克，售价为0.70元千克。农场年初规划时考虑如下几个方面： p1：年终收益不低于

15、350万元； p2：总产量不低于125万吨； p3：小麦产量以05万吨为宜； p4：大豆产量不少于02万吨； p5：玉米产量不超过06万吨； p6：农场现能提供5000吨化肥；若不够，可在市场高价购买，但希望高价采购量愈少愈好。 试就该农场生产计划建立数学模型。,四、 应用举例,解：设种植玉米x1亩，大豆x2亩，小麦x3亩，则该问题的数学模型为:,2、 某彩色电视机组装工厂，生产A，B，C三种规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月

16、销量预计为12台、10台、6台。该厂经营目标如下： p1：利润指标定为每月1.6万元； p2：充分利用生产能力； p3：加班时间不超过24小时； p4：产量以预计销量为标准； 为确定生产计划，试建立该问题的目标规划模型。,解：设生产电视机A型为x1台，B型为x2台，C型为x3台，该问题的目标规划模型为：,3： 某电子公司生产录音机和收音机两种产品，它们均需经过两个工厂加工，每一台录音机在第一个工厂加工2小时，然后送到第二个工厂装配试验25小时才变为成品；每一台收音机需在第一个工厂加工4小时，在第二个工厂装配试验15小时才变为成品。 录音机与收音机每台厂内的每月储存成本分别为8元和15元。 第一

17、个工厂有12部制造机器，每部每天工作8小时，每月正常工作天数为25天，第二个工厂有7部装配试验设备，每部每天工作16小时，每月正常工作天数仍为25天。每部机器每小时的运转成本是：第一个工厂为18元，第二个工厂为15元。每台录音机的销售利润为20元，收音机为23元。依市场预测，次月的录音机与收音机的销售量估计分别为1500台和1000台。,该公司依下列次序为目标优先次序，以实现下月的生产与销 售目标。 P1：厂内的储存成本不超过23000元。 P2：录音机销售量必须完成1500台。 P3：第一、二工厂的生产设备应全力运转，避免有空闲时间。 两厂的运转成本当作它们间的权系数。 P4：第一个工厂的超

18、时作业时间全月份不宜超出30小时。 P5：收音机销售量必须完成l000台。 P6；两个工厂的超时工作时间总和应予限制，其限制的比率依各厂每小时运转成本为准。 试建立这个问题的目标规划模型。,该公司依下列次序为目标优先次序，以实现下月的生产与销 售目标。 P1：厂内的储存成本不超过23000元。 P2：录音机销售量必须完成1500台。 P3：第一、二工厂的生产设备应全力运转，避免有空闲时间。 两厂的运转成本当作它们间的权系数。 P4：第一个工厂的超时作业时间全月份不宜超出30小时。 P5：收音机销售量必须完成l000台。 P6；两个工厂的超时工作时间总和应予限制，其限制的比率依各厂每小时运转成本

19、为准。 试建立这个问题的目标规划模型。,3： 某电子公司生产录音机和收音机两种产品，它们均需经过两个工厂加工，每一台录音机在第一个工厂加工2小时，然后送到第二个工厂装配试验25小时才变为成品；每一台收音机需在第一个工厂加工4小时，在第二个工厂装配试验15小时才变为成品。 录音机与收音机每台厂内的每月储存成本分别为8元和15元。 第一个工厂有12部制造机器，每部每天工作8小时，每月正常工作天数为25天，第二个工厂有7部装配试验设备，每部每天工作16小时，每月正常工作天数仍为25天。每部机器每小时的运转成本是：第一个工厂为18元，第二个工厂为15元。每台录音机的销售利润为20元，收音机为23元。依

20、市场预测，次月的录音机与收音机的销售量估计分别为1500台和1000台。,设备能力约束： 储存成本约束： 销售目标约束： 超时作业约束：,minZ=P1d1+P2d2- +P3(6d3-+5d4-) +P4d11+ +P5d5- + P6(6d3+5d4+),例2：一个公司需要从两个仓库调拨同一种零部件给下属三个工厂，每个仓库的供应能力，每个工厂的需求数量以及从每个仓库到每个工厂之间的单位运费如表所示(表中方格内的数字为单位运费)。,这是一个需求大于供应的物资调运问题，公司提出的目标要求是： P1：尽量满足工厂3的全部需求。 P2：其他两个工厂的需求至少满足75。 P3：总运费要求最少。 P4

21、：仓库2给工厂1的供应量至少为1000单位。 P5：工厂l和工厂2的需求量满足程度尽可能平衡 试建立这个问题的目标规划模型。,这是一个需求大于供应的物资调运问题，公司提出目标要求： P1：尽量满足工厂3的全部需求。 P2：其他两个工厂的需求至少满足75。 P3：总运费要求最少。 P4：仓库2给工厂1的供应量至少为1000单位。 P5：工厂l和工厂2的需求量满足程度尽可能平衡 试建立这个问题的目标规划模型。,例2：一个公司需要从两个仓库调拨同一种零部件给下属三个工厂，每个仓库的供应能力，每个工厂的需求数量以及从每个仓库到每个工厂之间的单位运费如表所示(表中方格内的数字为单位运费)。,解 设xij(i1，2；j1，2，3)表示仓库i调运结工厂j的零部件数量。,例3：某唱片商店聘用5位全日工售货员和4位半日工售货员，他们的工作、工资情况如表：,已知每售出一张唱片可获利1.5元。,要求确定满足以下目标的服务计划：,P3：维持全体售货员充分就业，但对全日工要加倍照顾。 P4：尽量减少加班时间，但全日工、半日工有