研目标规划ppt课件

1、目 标 规 划(Goal programming)目的规划的数学模型目的规划的图解法目的规划的单纯形法目的规划概述导入案例产品组合问题产品I产品II设备A设备B设备C240205121615单位利润23现添加如下思索：1力求使利润目的不低于15元；2据市场预测，I、II两种产品需求量的比例大致是1:2；3A为贵重设备，严厉制止超时运用；4设备C可以适当加班，但要控制；设备B既要求充分利用，又尽能够不加班，在重要性上设备B是C的3倍。综合思索上述要素，企业应如何决策？这里本章所要讨论的问题。最优解：x1=3x2=3z=15假设仅思索利润目的，其LP模型为： 目的规划经过引入目的值和偏向变量，可以

2、将目的函数转化为目的约束。 目的值：是指预先给定的某个目的的一个期望值。 实现值或决策值：是指当决策变量xj 选定以后，目的函数的对应值。 偏向变量事先无法确定的未知数：是指实现值和目的值之间的差别,记为 d 。 正偏向变量：表示实现值超越目的值的部分，记为 d。 负偏向变量：表示实现值未到达目的值的部分，记为 d。1、目的值和偏向变量 当完成或超额完成规定的目的那么表示：d0, d0 当未完成规定的目的那么表示： d0, d0 当恰好完成目的时那么表示： d0, d0 d d 0 成立。 引入了目的值和正、负偏向变量后，就对某一问题有了新的限制，既目的约束。 目的约束即可对原目的函数起作用，

3、也可对原约束起作用。目的约束是目的规划中特有的，是软约束。在一次决策中，实现值不能够既超越目的值又未到达目的值，故有 d d 0,并规定d0, d02、目的约束和绝对约束绝对约束系统约束是指必需严厉满足的等式或不等式约束。如线性规划中的一切约束条件都是绝对约束，否那么无可行解。所以，绝对约束是硬约束。目的规划处置问题的方法是将多目的转化为多个目的约束。如目的利润的约束：甲产品单位利润2元，乙产品单位利润3元，目的要求利润不小于15元，即有目的约束不等式： 添加正负偏向变量，将其变为等式：当 时，阐明 ，到达了目的；当 时，阐明 ，未到达目的，此种情况一但发生，希望越小越好，即目的要求为：同理有

4、其他目的约束：产品比例设备B利用与加班设备C的加班 达成函数是一个使总偏向量为最小的目的函数，记为 minZ = fd、d。 普通说来，有以下三种情况，但只能出现其中之一： .要求恰好到达规定的目的值，即正、负偏向变量要尽能够小，那么minZ = fd d。 .要求不超越目的值，即允许达不到目的值，也就是正偏向变量尽能够小，那么minZ = fd。 .要求超越目的值，即超越量不限，但不低于目的值，也就是负偏向变量尽能够小，那么minZ = fd。 对于由绝对约束转化而来的目的函数，也照上述处置即可。3、达成函数即目的规划中的目的函数 优先因子Pk 是将决策目的按其重要程度排序并表示出来。P1P

5、2PkPk+1PK ，k=1.2K。 权系数k 区别具有一样优先因子的两个目的的差别，决策者可视详细情况而定。 对于这种解来说，前面的目的可以保证明现或部分实现，而后面的目的就不一定能保证明现或部分实现，有些能够就不能实现。4、优先因子优先等级与优先权系数 5、称心解具有层次意义的解导入案例产品组合问题产品I产品II设备A设备B设备C240205121615单位利润23现添加如下思索：1力求使利润目的不低于15元；2据市场预测，I、II两种产品需求量的比例大致是1:2；3A为贵重设备，严厉制止超时运用；4设备C可以适当加班，但要控制；设备B既要求充分利用，又尽能够不加班，在重要性上设备B是C的

6、3倍。综合思索上述要素，企业应如何决策？这里本章所要讨论的问题。最优解：x1=3x2=3z=15假设仅思索利润目的，其LP模型为：将上述目的规划的目的约束、目的函数再加上系统约束和变量非负约束，即构成了引例中的目的规划数学模型如下： 目的规划是在线性规划的根底上，为顺应经济管理中多目的决策的需求而逐渐开展起来的一个分支。 2、线性规划求最优解；目的规划是找到一个称心解。 1、线性规划只讨论一个线性目的函数在一组线性约束条件下的极值问题；而目的规划是多个目的决策，可求得更切合实践的解。目的规划概述一、目的规划与线性规划的比较 4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力

7、才干得到；实践过程中，只需求得称心解，就能满足需求或更能满足需求。 3、线性规划中的约束条件是同等重要的，是硬约束；而目的规划中有轻重缓急和主次之分，即有优先权。目前，曾经在经济方案、消费管理、运营管理、市场分析、财务管理等方面得到了广泛的运用。目的规划的数学模型目的规划数学模型的普通方式： 优先因子正偏向权系数负偏向权系数目的约束系统约束变量非负建模的步骤 1、根据要研讨的问题所提出的各目的与条件，确定目的值，列出目的约束与绝对约束； 4、对同一优先等级中的各偏向变量，假设需求可按其重要程度的不同，赋予相应的权系数 。 3、给各目的赋予相应的优先因子 Pkk=1.2K。 2、可根据决策者的需

8、求，将某些或全部绝对约束转化为目的约束。这时只需求给绝对约束加上负偏向变量和减去正偏向变量即可。 5、根据决策者的要求，按以下情况之一构造 优先因子和权系数相对应的偏向变量组成的，要务虚现极小化的目的函数，即达成函数。.恰好到达目的值，取 。.允许超越目的值，取 。.不允许超越目的值，取 。 例、某厂方案在下一个消费周期内消费甲、乙两种产品，知资料如表所示。试制定消费方案，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽能够少消费；乙的销路较好，可以扩展消费。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲 单位 产品资源

9、 耗费 另外提出以下要求： 1、完成或超额完成利润目的 50000元； 2、产品甲不超越 200件，产品乙不低于 250件； 3、现有钢材 3600吨必需用完。试建立目的规划模型。 分析：标题有三个目的层次，包含四个目的值。 第一目的： 第二目的：有两个要求即甲 ，乙 ，但两个具有一样的优先因子，因此需求确定权系数。此题可用单件利润比作为权系数即 70 :120，化简为7:12。第三目的：目的规划模型为： 某厂消费、两种产品，有关数据如表所示。试求获利最大的消费方案？拥有量原材料2111设备(台时)1210单件利润810 在此根底上思索： 1、产品的产量不低于产品的产量； 2、充分利用设备有效

10、台时，不加班； 3、利润不小于 56 元。解: 分析 第一目的： 即产品的产量不大于的产量。 第二目的：例三：第三目的：规划模型：三、小结线性规划LP目标规划GP目标函数min , max系数可正负min , 偏差变量系数0变量xi, xs xa xi xs xa d约束条件系统约束（绝对约束）目标约束系统约束解最优最满意 图解法同样适用两个变量的目的规划问题，但其操作简单，原理一目了然。同时，也有助于了解普通目的规划的求解原理和过程。 图解法解题步骤如下： 1、确定各约束条件的可行域，即将一切约束条件包括目的约束和绝对约束，暂不思索正负偏向变量在坐标平面上表示出来； 2、在目的约束所代表的边

11、境限上，用箭头标出正、负偏向变量值增大的方向；三、目的规划的图解法 3、求满足最高优先等级目的的解； 4、转到下一个优先等级的目的，在不破坏一切较高优先等级目的的前提下，求出该优先等级目的的解； 5、反复4，直到一切优先等级的目的都已审查终了为止； 6、确定最优解和称心解。例一、用图解法求解目的规划问题01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1BC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上的一切点均是该问题的解无穷多最优解。图解法x1x2o662x1+2x2=122x1+3x2=157.552x1-x2=04x1=16

12、5x2=151绘出直角坐标2图示系统约束，确定可行域3按优先级高低，依次图示目的约束，减少称心解范围。 例二、知一个消费方案的线性规划模型为 其中目的函数为总利润，x1,x2 为产品A、B产量。现有以下目的： 1、要求总利润必需超越 2500 元； 2、思索产品受市场影响，为防止积压，A、B的消费量不超越 60 件和 100 件； 3、由于甲资源供应比较紧张，不要超越现有量140。试建立目的规划模型，并用图解法求解。 解：以产品 A、B 的单件利润比 2.5 ：1 为权系数，模型如下：0 x2 0 x11401201008060402020 40 60 80 100ABCD 结论：C(60 ,

13、58.3)为所求的称心解。作图： 检验：将上述结果带入模型，因 0； 0； 0， 存在； 0， 存在。所以，有下式： minZ=P3 将 x160， x2 58.3 带入约束条件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 0。阐明第k个优先等级的目的尚未到达,必需检查Pk这一的检验数kj(j=1.2n+2m).假设Pk这一行某些负检验数的同列上面较高优先等级没有正检验数，阐明未得到称心解，应继续改良，转到第3步；假设Pk这一行全部负检验数的同列上面较高优先等级都有正检验数，阐明目的虽没到达，但已不能改良，故得称心解，转到第6

14、步。 3、确定进基变量。 在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是进基变量。假设Pk行中有几个一样的绝对值最大者，那么依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假设仍无法确定，那么选最左边的变量变量下标小者为进基变量。 4、确定出基变量 其方法同线性规划，即根据最小比值法那么故确定xr为出基变量，ers为主元素。假设有几个一样的行可供选择时，选最上面那一行所对应得变量为xr 。 5、旋转变换变量迭代。 以为主元素进展变换，得到新的单纯形表，获得一组新解，前往到第2步。 6、对求得的解进展分析 假设计算结果称心，停顿运

15、算；假设不称心，需修正模型，即调整目的优先等级和权系数，或者改动目的值，重新进展第1步。单纯形法步骤：第1步 列出初始单纯形表1由于目的函数均为负值，为方便起见，不转换为极大；2以系统约束的松驰变量、人工变量、目的约束的负偏向变量为初始基变量；3检验数行按优先因子分别列出。第2步 计算检验数，确定换入变量1从第一级优级开场，假设检验数存在负数，最小检验数所对应的变量为换入变量。当高级优先级得到优化，转向下一级；2在第k优先级优化过程中，假设破坏了上级优化结果，那么迭代停顿，k-1以上级目的得到优化，k级以下未得到优化，所得结果为称心解；3假设一切检验数均非负，一切目的均得到优化，所得结果可称为

16、最优解。第3步 用最小比值原那么确定换出变量第4步 用换入变量交换换出变量，用行初等变换方法列出新的单纯形表，前往第2步。用单纯形法求目的规划称心解称心解例一、用单纯形法求解以下目的规划问题Cj00P1000000000000002.5P20P200000P30000CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 -2500301201000000P2 000000002.501P3 00000010000= min2500/30,140/2,60/1=60 ,故 为换出变量。Cj 00P100P

17、302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 00000010000= min700/30,20/2, =10 ,故 为换出变量。Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2 -

18、250-5/400-5/45/45/2001P3 00000010000= min400/15, =10 ,故 为换出变量。Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/15100000= min,350/6,1250/6,100/1=75 ,故 为换出变量。Cj

19、 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/12101/2-1/200表中P3115/30，阐明P3 优先等级目的没有实现，但已无法改良，得到称心解 x1 60， x2 175/3， 115/3， 125/3。 结果分析：计算结果阐明，工厂应消费A产品60件，B产品175/3件

20、，2500元的利润目的刚好到达。 125/3，阐明产品比最高限额少125/3件，满足要求。 115/3 阐明甲资源超越库存115/3公斤，该目的没有到达。 从表中还可以看到，P3 的检验数还有负数，但其高等级的检验数却是正数，要保证 P1目的实现，P3等级目的那么无法实现。所以，按现有耗费程度和资源库存量，无法实现2500元的利润目的。 可思索如下措施：降低A、B产品对甲资源的耗费量，以满足现有甲资源库存量的目的；或改动P3等级目的的目的值，添加甲资源115/3公斤。 假设很难实现上述措施，那么需改动现有目的的优先等级，以获得可行的称心解果。练习：用单纯形法求解以下目的规划问题Cj 000P1

21、 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 0000100000P2 10120002000P3 568100000010= min,10/2,56/10,11/1= 5,故 为换出变量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 023/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001kjP1 0000100000P2 0000011000P3 6300

22、05-5010= min10/3,10,6/3,12/3= 2,故 为换出变量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21kjP1 0000100000P2 0000011000P3 0000000100 最优解为x12， x2 4。 但非基变量 的检验数为零，故此题有无穷多最优解。= min4 , 24 , 6= 4,故 为换出变量。Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04

23、002-26-6-1100 x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001kjP1 0000100000P2 0000011000P3 0000000100 最优解为x110/3,，x2 =10/3。 1、某厂消费A、B、C三种产品，装配任务在同一消费线上完成，三种产品时的工时耗费分别为6、8、10小时，消费线每月正常任务时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量估计为12、10和6台。 该厂运营目的如下：1、利润目的为每月16000元，争取超额完成；2、充分利用现有消费才干；3、可以适当加班，但加班时间不得超越24小时；4、产量以估计销售量为准。试建立目的规划模型。 作业：2、用图解法求解以下目的规划问题：称心解为由x1 =3， 3, x2 =3.5，1.5 所连线段。 3、用图解法解以下目的规划模