第四章目标规划(运筹学-重庆大学,熊中楷)

运筹学熊中楷教授目标规划（1）运筹学熊中楷教授复习上节课内容：产销不平衡运输问题上节课难点：产销不平衡运输问题建立模型，造假本节课内容：目标规划和图解法本节课难点三个难点1.建立模型中：目标函数偏差是正或者负难点2.图解法中：方向偏差是正或者负难点3.图解法中：判断解第四章：目标规划（1）运筹学熊中楷教授第四章：目标规划（1）Chapter4:objectiveprogramming(1)exampleandmodelofobjectiveprogramminggraphicmethodofobjectiveprogramming第四章：目标规划（1－3）目标规划（1）目标规划的引例与模型，图解法目标规划（2）目标规划的单纯形法，灵敏度分析目标规划（3）目标规划的应用运筹学熊中楷教授线性规划-------单目标决策：利润最大或成本最小第四章：目标规划及其图解法（1）事实上，企业面临的多目标决策我们人生面临的多目标决策运筹学熊中楷教授一个国有企业面临的多目标决策1稳定指标（完不成第1把手下岗）今年下岗不超过现有人数的1％员工参加法能功上北京人数=0（负数表示不仅自己没有去，还告密）2利税指标=253万3新产品开发任务=2项第四章：目标规划及其图解法（1）运筹学熊中楷教授目标函数：Min{多个目标的正负偏差}约束条件：第一目标稳定＋正负偏差＝下岗2％第二目标利润＋正负偏差＝5000万第三目标成本＋正负偏差＝3000万第四目标新产品开发费用＋正负偏差＝250万第四章：目标规划及其图解法（1）运筹学熊中楷教授产品A产品B拥有量原材料（公斤）2111设备（小时）1212利润（万元/件）810书上引例：某工厂生产A、B两种产品，有关数据如下,用线性规划求解：第四章：目标规划及其图解法（1）运筹学熊中楷教授求利润最大的决策是产品A生产4产品B生产3利用线性规划求出：总利润为62万元这时原材料用完设备剩余2小时实际中，决策时不只考虑利润最大，还要考虑市场等一系列条件，例如（1)根据市场信息，产品A的需求有下降的趋势，因此考虑产品A的产量不大于产品B的产量（2）超过计划供应的原材料时，需要用高价采购，使成本增加（3）尽可能利用设备，但不希望加班（4）尽可能达到并且超过利润指标56万元求：决策方案。第四章：目标规划及其图解法（1）运筹学熊中楷教授例1.线性规划模型相关目标规划模型利润最大MaxZ=8x1+10x28x1+10x2+d1--d1+=56决策目标不是利润最大，而是有多个，重要性有先后之分：假设：第一目标利润不小于56元(利润小于56----------d1-0)第二目标充分利用台时，不加班第三目标产品1产量不大于产品2产量目标偏差最小：Min{P1d1-+P2(d2--d2+)+P3d3+}第四章：目标规划及其图解法（1）原材料约束2x1+x2=112x1+x2=11设备约束x1+2x2=10x1+2x2+d2--d2+=10xi=0x1-x2+d3_－d3+=0xi=0,di-,d+I=0难点1.建立模型中：目标函数偏差是正或者负运筹学熊中楷教授知识要点1．概念（1）偏差变量：实际值与目标值之间差距的变量表示，通常以di-、di+表示，分别称为正偏差变量、负偏差变量、且有di-≥0,di+≥0。（2）优先级系数：又称优先级因子，描述问题中目标重要性程度的差别，一般用pi表示。通常，i值越小，代表的优先程度越高。（3）目标约束与系统约束：描述问题中两类不同性质的限制条件。一般目标约束用来描述允许对给定目标值有一定偏离程度的限制条件。而系统约束表示的意义同线性规划模型的约束条件。2．模型特点（1）引进正负偏差变量，对所有目标下的正负偏差变量，均有di-·di+=0；（2）模型中必顺存在目标约束，而系统约束可以不存在；（3）目标函数为偏差变量表述式；（4）以优先级系数描述目标的重要性程度。目标规划问题的满意解可是一个点，一条线段或者为一个区域。第四章：目标规划及其图解法（1）运筹学熊中楷教授d1-d1+X1-X2+1=0X1X2d1-=1X1-X2=0第四章：目标规划及其图解法（1）难点2.图解方法中：方向偏差是正或者负X1-X2=02X1-X2+1=0判断d1-方向判断d1+方向运筹学熊中楷教授d2+=1X1+2X2=10X1X2510X1+2X2-1=10第四章：目标规划及其图解法（1）d2+d1-运筹学熊中楷教授P104例3电视生产第四章：目标规划及其图解法（1）Minz=Min{P1d1-+P2d2++P3)(2d3-+d4-)}x1+x2+d1--d1+=40x1+x2+d2_－d2+=50x1+d3_－d3+=24x2+d4_－d4+=30xi=0,di-,d+I=0运筹学熊中楷教授d3-＝03024d4-＝？d4+P104例3电视生产d3＋d2+＝0d1-＝0彩电X1X2黑白5004040第四章：目标规划及其图解法（1）难点3.图解方法中：判断解Min{P1d1-+P2d2++P3)(2d3-+d4-)}运筹学熊中楷教授d3-＝0彩电X1X2黑白3024D4-＝？d4+P104例3优先权改变改为黑白优先D3＋d2+＝0d1-＝0第四章：目标规划及其图解法（1）Min{P1d1-+P2d2++P3d4-+P4d3-}运筹学熊中楷教授灵敏度分析目标规划问题的灵敏度分析，一般只对约束右端项的变化以及优先级系数的变化进行。【例1】判断下述说法是否正确?(a)线性规划模型是目标规划模型的一种特殊形式;(b)正偏差变量应取正值、负偏差变量应取负值；(c)目标规划模型中，若不含系统约束，则一定有解；(d)目标规划的数学模型应同时包括系统约束和目标约束。答：（a）正确。模型结构完全一致，可以将线性规划模型改写成单一目标形式的目标规划。（b）错误。正负变量都定义取非负的值。(c)正确。目标规划的解是一种相对满意的解。(d)错误。可以没有系统的束。第四章：目标规划及其图解法（1）运筹学熊中楷教授目标规划图解法：例2（p103）.2d1d1d2d3d3d01d002d02d3d0第四章：目标规划及其图解法（1）第2目标约束Min{P2(d2--d2+)}d2-=0，d2+=0第1目标约束Min{P1d1+}d1+=0第3目标约束Min{P3d3-}d3-=01dd1+=0运筹学熊中楷教授例3.（p104）1d1d2d2d3d3d3d4d4d04dMin4dMin0021dd第二目标约束第一目标约束绝对约束第四章：目标规划及其图解法（1）运筹学熊中楷教授总结本节课：目标规划难点三个难点1.建立模型中：目标函数偏差是正或者负难点2.图解方法中：方向偏差是正或者负难点3.图解方法中：判断解第四章：目标规划及其图解法（1）运筹学熊中楷教授目标规划（2）运筹学熊中楷教授本节课任务：目标规划单纯形法目标规划灵敏度第四章：目标规划单纯形法和灵敏度（2）复习上节课内容：目标规划和图解法上节课难点三个难点1.建立模型中：目标函数偏差是正或者负难点2.图解法中：方向偏差是正或者负难点3.图解法中：判断解本节课要点三个要点1初试单纯形表要点2检验数的计算要点3检验数正负的判别运筹学熊中楷教授P103例2目标规划单纯形法第四章：目标规划单纯形法和灵敏度（2）原材料严格限制目标1：产品2产量不低于产品1的产量目标2：充分利用设备台时，不加班目标3：利润不小于56万元求决策方案运筹学熊中楷教授Minz=p1d1++p2(d2-+d2+)+p3d3-2x1+x2+Xs=11x1－x2+d1--d1+=0x1+2x2+d2_－d2+=108x1+10x2+d3_－d3+=56xi=0,di-,d+I=0P106例目标规划单纯形法第四章：目标规划单纯形法和灵敏度（2）要点1初试单纯形表:有一个单位矩阵检验数运筹学熊中楷教授第四章：目标规划单纯形法和灵敏度（2）解目标规划的单纯形法(P106)0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1b0XS2111111/10d1-1-11-10P2d2-1转21-11010/2P3d3-8101-15656/10检验数P11P2－1－22P3－8－101根据目标函数C2-CBB-1P2=0－（00P2P3）(1–1210)T=-2P2-10P3单纯形法：降成本，负中取小相除后正中取小B-1=I直接找到单位矩阵转元所在列化为单位向量运筹学熊中楷教授第四章：目标规划单纯形法和灵敏度（2）0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1b0XS0d1-0X21/211/2-1/255/1.5P3d3-检验数P11P2－1－22P3－8－101把这一行所有数乘以（2P2+10P3）加到检验数这一行：（-P2-8P3）+(1/2)（2P2+10P3）=-3P3转元所在列化为单位向量要点2检验数的计算运筹学熊中楷教授第四章：目标规划单纯形法和灵敏度（2）0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1b0XS0d1-0X21/211/2-1/255/1.5P3d3-检验数P1P2P3-3把这一行所有数乘以（2P2+10P3）加到检验数这一行：（-P2-8P3）+(1/2)（2P2+10P3）=-3P3运筹学熊中楷教授第四章：目标规划单纯形法和灵敏度（2）解目标规划的单纯形法(P105)0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1b0XS3/21-1/21/266/1.50d1-3/21-11/2-1/250X21/211/2-1/255/1.5P3d3-转3-551-166/3检验数P11P211P3－35－51C7－CBB-1P7=P2－（000P3）(1/2–1/2–1/25)T=P2－5P3单纯形法：降成本，负中取小(注：d2+的检验数为正)相除后正中取小CB转元所在列化为单位向量运筹学熊中楷教授解目标规划的单纯形法(P107)0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1b0Xs12-2-1/21/230d1-1-13-3-1/21/220X214/3-4/3-1/61/64P3X11-5/35/31/3-1/32检验数P11P211P310非基变量检验数为零对应无数最优解单纯形法：最优解：X1＝2，X2＝4，Xs＝3，d1-＝2第四章：目标规划单纯形法和灵敏度（2）运筹学熊中楷教授第四章：目标规划单纯形法和灵敏度（2）解目标规划的单纯形法(P107)0000P1P2P2P30CBX1X2Xsd1-d1+d2-d2+d3-d3+B-1b0Xs1-1-1110d3+126-6-1140X21-1/31/3-1/310/3P3X11-2/31/3-1/310/3检验数P101P211P31单纯形法：最优解X1＝10/3，X2＝10/3，Xs＝1，d3+＝4非基变量检验数为零对应无数最优解d1-d3+对换运筹学熊中楷教授解目标规划的单纯形法(P105)0NXbB100bB1NX0321PPP953832100NBCCBNN1bB1NX0321PPP953832100已达到最优解0第四章：目标规划单纯形法和灵敏度（2）?bB10bB10检验数2P2-3P3为正检验数-3P2+5P3为负检验数P1-8P2-9P3为正运筹学熊中楷教授要点3检验数正负的判别检验数中优先权大的系数符号为准检验数-3P2+5P3为负检验数2P2-3P3为正检验数P1-8P2-9P3为正第四章：目标规划单纯形法和灵敏度（2）运筹学熊中楷教授灵敏度分析----优先级改变(107)：优先彩电优先黑白NX01bB321PPPNBCCBNN1第四章：目标规划单纯形法和灵敏度（2）优先级改变目标函数改变，C改变C