运筹基础课程 5

1Lecture7

GoalProgramming*SchoolofBusinessAdministrationHunanUniversityLecturer:E-mail:

2LectureOutlineWhat’sGoalProgramming？SolutionMethodofGPApplicationsofGP3这是一个典型的线性规划问题，但实际中往往存在多个目标，例如：为什么提出目标规划？采购部：最近原材料供应紧张，就只有那么多原材料，不能超过人事部：劳动力目前也很紧缺，就那么多了销售部：由于产品B销售疲软，希望产品B产量不超过产品A的一半维修部：好久没检修过了，最好能节约4个设备台时以便检修财务部：计划利润要是不少于480元就好了4几个基本概念绝对约束和目标约束偏差变量优先因子和权系数5绝对约束和目标约束绝对约束：必须严格满足的约束条件，也叫硬约束目标约束：尽量要满足的约束条件，又称软约束采购部：最近原材料供应紧张，就只有那么多原材料，不能超过人事部：劳动力目前也很紧缺，就那么多了销售部：由于产品B销售疲软，希望产品B产量不超过产品A的一半维修部：好久没检修过了，最好能节约4个设备台时以便检修财务部：计划利润要是不少于480元就好了如果采购部和人事部的要求必须满足，那么它们就是绝对约束。6偏差变量对每一个决策目标，引入正偏差变量d+：实际决策值超过目标值的部分负偏差变量d-：实际决策值不足目标值的部分注意：d+,

d-≥0,并且d+×d-＝0例：由于产品B销售疲软，希望产品B产量不超过产品A的一半x1-2x2+d--d+=0多目标决策问题中,决策者对每个目标都应有一个期望值,即目标值,但由于现实问题的矛盾性,并非每个目标都能一一满足,而只能尽量满足。偏差变量7若要求利润指标为bi=100万元，则：若gi(X)=110万元，则d+=10，同时d-=0若gi(X)=90万元，则d-=10，同时d+=08优先因子和权系数不同目标的轻重缓急或优先程度不同

只有高级目标已满足的基础上，才考虑低级目标

——优先因子来反映(Pi>>Pi+1)

优先因子相同，只是一个并另一个稍微优先考虑

——权系数来反映(W)9目标规划的目标函数目标函数由偏差变量，优先因子和权系数构成。由于目标规划追求的是尽可能接近各既定目标值，也即各有关偏差变量尽可能小，因此，目标函数都是求极小化。几种基本表达式：要求恰好达到目标值：min(d-+d+)要求不超过目标值，但允许不足：min(d+)要求不低于目标值，但允许超过：min(d-)例1:假设上述生产计划的例子中，三个软约束优先考虑销售部，其次考虑维修部，再其次考虑财务部，则其目标规划模型为：（生产计划问题）：某工厂在计划期内要安排A、B两种产品的生产，已知生产单位产品的利润与所需的劳力、设备台时及原材料消耗，如下：12070单位产品利润360工时200台时300公斤4510943劳动力设备原材料资源限额产品B产品A12070单位产品利润360工时200台时300公斤4510943劳动力设备原材料资源限额产品B产品A采购部：最近原材料供应紧张，就只有那么多原材料，不能超过人事部：劳动力目前也很紧缺，就那么多了销售部：由于产品B销售疲软，希望产品B产量不超过产品A的一半维修部：好久没检修过了，最好能节约4个设备台时以便检修财务部：计划利润要是不少于480元就好了11目标规划的一般数学模型12建模举例例2：某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求完成下列目标的周生产计划：（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标(不要加班)，并依A、B产量/小时的比例确定重要性。设A，B生产线每周工作时间为X1，X21.先确定决策变量2.确定约束条件生产量达到210件/周2x1+1.5x2≥2102x1+1.5x2+d1--d1+=210A生产线加班时间限制在15小时内x1≤60x1+d2--d2+=60充分利用工时指标x1+d3--d3+=45x1≤45x2+d4--d4+=45x2≤453。确定目标函数minz=P1d1-+P2d2++4

P3d3++3P3d4+P1:d1-P2:d2＋P3:4d3++3d4+最终模型结果minz=P1d1-+P2d2++4

P3d3-+3P3d4-2x1+1.5x2+d1--d1+=210x1+d2--d2+=60x1+d3--d3+=45x2+d4--d4+=45X1,x2,di-,di+≥0（i=1,2,3,4)15建模举例例3：某电子公司同一生产线制造A、B、C三种产品，每种产品单位耗时分别为5小时、8小时、12小时。生产线每月正常运转170小时。三种产品利润分别为A:100(千元),B:144(千元),C:252(千元)该公司确定的目标：P1:充分利用工时P2:为满足主要客户的需求，A、B、C的产量须分别达到5、5、8，并依单位工时的利润比例确定权数P3:生产线的加班时间每月不宜超过16小时P4:A、B、C的月销售指标分别定为10、12、10,并依单位工时的利润比例确定权数;P5:尽量减少生产线的加班时间。1.先确定决策变量设生产A、B、C三种产品的产量分别为x1,x2,x32.确定约束条件P1:充分利用工时5x1+8x2＋12x3≥1705x1+8x2＋12x3+d1--d1+=170P2:A、B、C的产量须分别达到5、5、8x1≥5x2≥5x3≥8x1+d2--d2+=5x2+d3--d3+=5x3+d4--d4+=8P3:生产线的加班时间每月不宜超过16小时5x1+8x2＋12x3≤1865x1+8x2＋12x3+d5--d5+=

186P4:A、B、C的月销售指标分别定为10、12、10x1≥10x2≥12x3≥10x1+d6--d6+=10x2+d7--d7+=12x3+d8--d8+=10P5:尽量减少生产线的加班时间5x1+8x2＋12x3≤1705x1+8x2＋12x3+d1--d1+=1703.确定目标函数P1:d1-P2:20d2-+18d3-+21

d4-P3:d5+P4:20d6-+18d7-+21d8-minz=P1(d1-)+P2(20d2-+18d3-+

21d4-)+P3(d5+)+P4(20d6-+18d7-+21

d8-)+P5(d1+)P5:d1+18建模举例例4.混合配方问题：某酒厂用三种等级的原料酒Ⅰ、Ⅱ、Ⅲ兑成制三种混合酒（A、B、C）。原料受到严格限制，每日供应量分别为1500千克、2000千克和1000千克，供应价分别为18元/千克、13.5元/千克和9元/千克。三种混合酒的配方及售价如表所示：混合酒兑制要求售价元/千克AⅢ不多于10%,Ⅰ不少于50%16.5BⅢ不多于70%,Ⅰ不少于20%15CⅢ不多于50%,Ⅰ不少于10%14.4目标如下P1:按规定比例兑制；P2:获利最大；P3:混合酒A每天至少生产2000千克。1.先确定决策变量设xij表示第i种原料在第j种酒中的含量2.确定约束条件按规定比例兑制x31≤0.1(x11+x21+x31)x11≥0.5(x11+x21+x31)x32≤0.7(x12+x22+x32)x12≥0.2(x12+x22+x32)x33≤0.5(x13+x23+x33)x13≥0.1(x13+x23+x33)原料供应量x11+x12+x13≤1500x21+x22+x23≤2000x31+x32+x33≤10000.1x11+0.1x21-0.9x31+d1--d1+=0-0.5x11+0.5x21+0.5x31+d2--d2+=00.7x12+0.7x22-0.3x32+d3--d3+=0-0.8x12+0.2x22+0.2x32+d4--d4+=00.5x13+0.5x23-0.5x33+d5--d5+=0-0.9x13+0.1x23+0.1x33+d6--d6+=0获利最大16.5(x11+x21+x31)＋15(x12+x22+x32)+14.4(x13+x23+x33)-18(x11+x12+x13)-13.5(x21+x22+x23)-9(x31+x32+x33)≥81000混合酒A每天至少生产2000千克x11+x21+x31≥2000为了使获利最大，这里的理想值取利润的上界（或一个很大的数）=>-1.5x11-3x12-3.6x13+3x21+1.5x22+0.9x23+7.5x31+6x32+5.4x33+d7--d7+=81000=>x11+x21+x31+d8--d8+=200021混合配方问题目标规划模型22建模举例例5.工资调整方案问题:某单位在考虑职工的升级调资方案时，依次遵循以下规定：（1）年工资总额不超过600,000万元；（2）每级的人数不超过定编人数；（3）2，3级的升级面尽可能达到现有人数的20%；3级编制不足的人数可录用新职工来补充，1级职工中有10%要退休。有关资料如表所示，如何拟定一个满意的方案？等级工资额(元/年)现有人数编制人数120,0001012215,0001215310,0001515合计37421.先确定决策变量设x1,x2,x3分别表示提升到1，2，3级的人数2.确定约束条件年工资总额不超过600,000万元20000（10-10×0.1+x1)+15000(12-x1+x2)+10000(15-x2+x3)+d1--d1+=600000每级的人数不超过定编人数10-10×0.1+x1+d2--d2+=1212-x1+x2+d3--d3+=1515-x2+x3+d4--d4+=152，3级的升级面尽可能达到现有人数的20%x1+d5--d5+=12×0.2x2+d6--d6+=15×0.23.确定目标函数minz=p1d1+p2(d2++d3++d4+)+p3(d5-+d6-)24工资调整方案问题目标规划模型minz=p1d1+p2(d2++d3++d4+)+p3(d5-+d6-)5000x1+5000x2+10000x3+d1--d1+=90000

-x1+x2+d3--d3+=3-x2+x3+d4--d4+=0x1+d5--d5+=2.4x2+d6--d6+=3xi≥0,(i=1,2,3);dj-,dj+≥0,(j=1,2,…,6)x1+d2--d2+=3s.t.25目标规划的图解法两个决策变量的目标规划可用图解法来求解例：2533.3x1x210d1+d1-2040d3+d3-1620d2+d2-10（17.5,10）OABCEFD26目标规划的单纯形法目标规划单纯形法的特点目标规划的单纯形法目标规划单纯形法的要点27目标规划单纯形法的特点目标函数只有偏差变量，且求它们的”和”最小目标函数中“价值系数”一般为优先级的权重，因此检验数不是一行，而是m行。在m行检验数中，从上到下，按优先级从高到低的顺序排列。求解时，首先满足优先级高的变量。目标规划的单纯形法28产品决策问题：某汽车工厂生产大轿车和载重汽车两种型号的汽车，已知生产每辆汽车所用的钢材都是2吨/辆，该工厂每年供应的钢材为1600吨；工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查，出售一辆大轿车可获利4千元，出售一辆载重汽车可获利3千元。工厂的生产目标如下：P1.希望总利润为2600千元；P2.为了不使产品滞销，大轿车的产量不要超过300辆；P3.保持正常生产，避免开工不足；P4.钢材的消耗量不要超过库存量。应如何安排生产才能使工厂获利最大？目标规划的单纯形法29产品决策数学模型s.t.30初始单纯形表00b2600431-10006503001000100300250052.50001050016002200001800430-2000100000052.500000220000031第一次迭代00b1400031-1-40046603001000100-100002.500-51040010000200-201500030-2-4000000-10002.500-5000200-20032第二次迭代00b200001-12001000300100010030004000100-20.40-20000002-0.81100000-22000000-1000000000000020033第三次迭代00b100000.5-0.51-0.60020010-0.50.500.600600011-101.60000-1100.4100-1-1000000.5-0.50-0.6000000-1000-1100.4034最优解由于非基变量的检验数全都小于零因此已获最优解只有第二个目标值没有完全满足，偏差为100，即大轿车只生产200辆。35例某电视机厂生产46厘米和51厘米两种电视机，平均生产能力1台/小时，正常每日两班，每周80小时。下周的最大销售量是46厘米70台，51厘米35台。已知每出售一台46厘米的获利250元，51厘米的150元，试决定最优生产计划。经理按重要程度确定以下目标：避免开工不足，保持职工就业稳定尽量少加班，每周加班不超过10小时努力达到预计的销售量36数学模型37初始单纯形表00530b80111000-1080570100100007033501001000-0100000011-1-110000-100000000-153000000000000-1038第一次迭代00530b10011-100-101007010010000033501001000350100000011-1-010-100-100000000-1030-50000000000-1039第二次迭代00530b010011-100-10-07010010000-32500-111010250100000011-11000-1000000000000-100-3-20030000000-1040第三次迭代00530b020011-1010-10701001000031500-111-101100000011-100-1000000000000-100-3-20-3030000010-141最优解写出上一步的检验数，发现已是最优解。最优解：因此加班10小时(未能少加班)，51厘米的彩电少生产了15台，未能满足预期销售目标。42目标规划单纯形法的要点约束方程中的负偏差为初始基变量。检验数在单纯形表中以矩阵形式表达，占有m行，且按优先级顺序排列。选择换入变量时，先在优先级最高的行中寻找正的检验数，当最高级的检验数相同时，比较次高级的检验数。在选择换出变量时，若有多于一个的最小正比值，则选择较高优先级的变量换出。只要各变量的检验数表达式中最高级权重的系数小于零，则已获最优解。43小结：求解目标规划的单纯形法目标规划的数学模型实际上是最小化的线性规划，可以用单纯形法求解。几点注意事项：偏差变量一律都看作决策变量由于是求最小化，故最优性条件是所有检验数都≤0判定检验数的大小时，必须注意P1>>P2>>P3>>…..例：一家生产某种产品的公司在生产周期内的正常生产时间为100小时。为了提供产量，该公司可加班生产、转包或雇临时工，具体数据如下表：小时/单位产品费用/小时平均优质水平正常生产2.010099%加班生产2.015098%转包2.58095%临时工3.08090%决策目标为：P1:尽量满足100单位产品的市场需求P2:优质品不