第八章运筹学 目标规划 案例.doc

第八章 目标规划8.1请将下列目标规划问题数学模型的一般形式转换为各优先级的数学模型。 1、min P1（dl-）P2（d2-）P2（d2+）P3（d3-）P3（ d3+）P4（d4-）约束条件：4 xl 680 4x2 600 2 xl3x2d1+ +d1-12 xlx2d2+d2-0 2 xl2x2d3+d3-12xl2x2d4+d4-8 xl，x2，d1+，d1-，d2+，d2-，d3+，d3-，d4+，d4-0。 解： 这是一个四级目标规划问题：第一级：min dl- S.T. 4 xl 680 4x2 600 2 xl3x2d1+ +d1-12xl，x2，d1+，d1-0 第二级： min d2- d2+ S.T. 4 xl 680 4x2 600 2 xl3x2d1+ +d1-12xlx2d2+d2-0d1-第一级的最优结果xl，x2，d1+，d1-，d2+，d2-0第三级： min d3- d3+ S.T. 4 xl 680 4x2 600 2 xl3x2d1+ +d1-12xlx2d2+d2-02 xl2x2d3+d3-12d1-第一级的最优结果d2+，d2-第二级的最优结果xl，x2，d1+，d1-，d2+，d2-，d3+，d3-0 第四级： min d4- S.T. 4 xl 680 4x2 600 2 xl3x2d1+ +d1-12xlx2d2+d2-02 xl2x2d3+d3-12xl2x2d4+d4-8d1-第一级的最优结果 d2+，d2-第二级的最优结果 d3+，d3-第三级的最优结果xl，x2，d1+，d1-，d2+，d2-，d3+，d3-，d4+，d4-0 2、 min P1（dl-）P2（d2-）P2（d2+）P3（d3-）约束条件：12 xl9x215x3d1+ +d1-125 5xl3x24x3d2+ +d2-40 5 xl7x28x3d3+ +d3-55 xl，x2，x3，d1+，d1-，d2+，d2-，d3+，d3-0。解：这是一个三级目标规划问题：第一级： min dl-S.T. 12 xl9x215x3d1+ +d1-125 xl，x2，x3，d1+，d1-0第二级： min d2-d2+S.T. 12 xl9x215x3d1+ +d1-125 5xl3x24x3d2+ +d2-40 dl-第一级的最优结果 xl，x2，x3，d1+，d1-，d2+，d2-0第三级： min d3-S.T. 12 xl9x215x3d1+ +d1-125 5xl3x24x3d2+ +d2-40 5 xl7x28x3d3+ +d3-55 dl-第一级的最优结果d2+ ，d2-第二级的最优结果 xl，x2，x3，d1+，d1-，d2+，d2-，d3+，d3-08.2某企业生产A、B、C、三种不同规格的电子产品，三种产品的装配工作在同一生产线上完成，各种产品装配时消耗的工时分别为5、9和12小时，生产线每月正常台时为1500小时；三种产品销售出去后，每台可获得利润分别为450、550和700元；三种产品每月销售量预计分别为300、80和90台。该厂经营目标如下：P1-利润目标为每月150000元，争取超额完成。P2-充分利用现有生产能力。P3-可以适当加班，但加班时间不要超过100小时。P4-产量以预计销量为标准。试建立该问题的目标规划数学模型，并求解最合适的生产方案。解：本问题的目标规划数学模型：min P1（d1-）P2（d2-）P3（d3+）P4（d4-d4+d5-d5+d6-d6+） S.T. 450xl550x2700x3d1+ +d1-1500005xl9x212x3d2+ +d2-15005xl9x212x3d3+ +d3-1600 xld4+ +d4-300 x2d5+ +d5-80x3d6+ +d6-90xi0 (i=1,2,3)di+ 、di- 0 (i=1,2,3,4,5,6) 这是一个四级目标规划问题： 第一级： min d1- S.T. 450xl550x2700x3d1+ +d1-150000xi0 (i=1,2,3)d1+ 、d1- 0 即：最优解：（0，0，214.29）,最优值：min d1-0第二级： min d2- S.T. 450xl550x2700x3d1+ +d1-1500005xl9x212x3d2+ +d2-1500 d1-0xi0 (i=1,2,3)di+ 、di- 0 (i=1,2)即：最优解：（333.33，0，0）,最优值：min d1-0，min d2-0第三级： min d3+ S.T. 450xl550x2700x3d1+ +d1-1500005xl9x212x3d2+ +d2-15005xl9x212x3d3+ +d3-1600d1-0 d2-0xi0 (i=1,2,3)di+ 、di- 0 (i=1,2，3)即：最优解：（333.33，0，0）,最优值：min d1-0，min d2-0，min d3-66.667第四级： min d4-d4+d5-d5+d6-d6+ S.T. 450xl550x2700x3d1+ +d1-1500005xl9x212x3d2+ +d2-15005xl9x212x3d3+ +d3-1600xld4+ +d4-300 x2d5+ +d5-80x3d6+ +d6-90d1-0 d2-0d3+66.667xi0 (i=1,2,3)di+ 、di- 0 (i=1,2,3,4,5,6)即：最优解：（333.33，0.0001，0）,最优值：min d1-0，min d2-0，min d3-66.667, min d4-0, min d4+33.33 min d5-80, min d5+0min d4-90, min d4+0即安排生产的方案： 生产产品A33.33件，产品B和产品C不生产最合适。若再加上产品是整数的特殊要求：第一级： min d1- S.T. 450xl550x2700x3d1+ +d1-150000xi0 (i=1,2,3)d1+ 、d1- 0得最优解：（0，0，215）最优值：d1-0第二级： min d2- S.T. 450xl550x2700x3d1+ +d1-1500005xl9x212x3d2+ +d2-1500 d1-0xi0 (i=1,2,3)di+ 、di- 0 (i=1,2)得最优解：（334，0，0）最优值：d1-0，d2-0第三级： min d3+ S.T. 450xl550x2700x3d1+ +d1-1500005xl9x212x3d2+ +d2-15005xl9x212x3d3+ +d3-1600d1-0 d2-0xi0 (i=1,2,3)di+ 、di- 0 (i=1,2，3)得最优解：（334，0，0）最优值：d1-0，d2-0，d3-70第四级： min d4-d4+d5-d5+d6-d6+ S.T. 450xl550x2700x3d1+ +d1-1500005xl9x212x3d2+ +d2-15005xl9x212x3d3+ +d3-1600xld4+ +d4-300 x2d5+ +d5-80x3d6+ +d6-90d1-0 d2-0d3+70xi0 (i=1,2,3)di+ 、di- 0 (i=1,2,3,4,5,6)得最优解：（334，0，0）最优值：d1-0，d2-0，d3-70 min d4-0, min d4+34 min d5-80, min d5+0min d4-90, min d4+08.3现有一个四个产地、三个销地的运输问题，其供需数量及单位运费如下表所示：销地产地B1B2B3供应量A147512A26485A336106A454811需求量121618经营决策中要求所有产地的产量都必须全部运出，希望达到目标以及优先等级如下：P1-销地B1、B2至少得到它需求量的50%。P2-必须满足销地B3全部需求量。P3-由于客观原因，要尽量减少A4到B2的货运量。P4-若期望运费132元，并尽可能减少运输费用。解：本问题的目标规划数学模型：min P1（d1-d2-）P2（d3-）P3（d4+）P4（d5+） S.T. xlx4x7d1+ +d1-6 x2x5x8d2+ +d2-8 x3x6x9d3+ +d3-18x11d4+ +d4-04xl7x25x36x44x58x63x76x810x95x104x118x12 d5+ +d5-132 xi0 (i=1,2.12)di+ 、di- 0 (i=1,2,3,4,5) 这是一个四个优先及的目标规划问题：第一级： min d1-d2- S.T. xlx4x7d1+ +d1-6 x2x5x8d2+ +d2-8xi0 (i=1,2.12)di+ 、di- 0 (i=1,2) 得结果：最优解（6，8，0，0，0，0，0，0，0，0，0，0） 最优值d1-0，d2-0第二级： min d3- S.T. xlx4x7d1+ +d1-6 x2x5x8d2+ +d2-8x3x6x9d3+ +d3-18d1-0d2-0xi0 (i=1,2.12)di+ 、di- 0 (i=1,2，3) 得结果：最优解（6，8，18，0，0，0，0，0，0，0，0，0） 最优值d1-0，d2-0，d3-0第三级： min d4+ S.T. xlx4x7d1+ +d1-6 x2x5x8d2+ +d2-8x3x6x9d3+ +d3-18x11d4+ +d4-0d1-0d2-0d3-0xi0 (i=1,2.12)di+ 、di- 0 (i=1,2，3，4) 得结果：最优解（6，8，18，0，0，0，0，0，0，0，0，0） 最优值d1-0，d2-0，d3-0，d4+0第四级：min d5+ S.T. xlx4x7d1+ +d1-6 x2x5x8d2+ +d2-8 x3x6x9d3+ +d3-18x11d4+ +d4-04xl7x25x36x44x58x63x76x810x95x104x118x12 d5+ +d5-132 d1-d2-d3-d4+xi0 (i=1,2.12)di+ 、di- 0 (i=1,2,3,4,5)得结果：最优解（0，0，18，0，0，0，0，0，0，0，0，0） 最优值d1-0，d2-0，d3-0，d4+0，d5+8即A1到B3运8件最合适。8.4 某公司准备投产三种产品，三种产品的单位利润、需要劳动力资源及投入成本情况如下表：产品利润（元/件）需要工人（人/万件）投入成本（元/件）产品11566产品21048产品312510现在的重要工作是确定三种产品的生产计划，并且要求在计划中最好能体现完成以下三个目标：P1-希望总利润不低于130万元。P2-现有工人45名，要充分利用现有员工，但尽可能不要安排加班。P3-希望总投资不要超过60万元。1、 用优先级目标规划确定满意的投产计划。2、 若将三个目标赋予偏离目标的罚数权重为低于总利润目标为5；低于现有工人利用目标为4；超过现有工人人数目标为2；超过投资额目标为3。用加权目标规划确定满意的投产计划。解： 分别设三种产品的产量为x、x2、x3件。1、min P1（d1-）P2（d2-+d2+）P4（d3+） S.T. 15xl10x212x3d1+ +d1-130 6x14x25x3d2+ +d2-45 6x18x210x3d3+ +d3-60xi0 (i=1,2,3)di+ 、di- 0 (i=1,2,3) 这是一个三个优先级的目标规划问题：第一级： min d1-S.T. 15xl10x212x3d1+ +d1-130xi0 (i=1,2,3)d1+ 、d1- 0 得最优解：（8.667，0，0），最优值：min d1-0第二级： min d2-+d2+S.T. 15xl10x212x3d1+ +d1-1306x14x25x3d2+ +d2-45d1-0xi0 (i=1,2,3)di+ 、di- 0 (i=1,2) 得最优解：（8.667，0，0），最优值：min d1-0，min d2-0，min d2+7第三级： min d3+S.T. 15xl10x212x3d1+ +d1-1306x14x25x3d2+ +d2-456x18x210x3d3+ +d3-60d1-0d2-0d2+7xi0 (i=1,2,3)di+ 、di- 0 (i=1,2,3) 得最优解：（7.333，2，0），最优值：min d1-0，min d2-0，min d2+7，min d3+0 即产品1安排生产7.333件，产品2安排2件最合适。 若考虑产品应该是整数可得： 第一级：得最优解：（9，0，0），最优值：min d1-0 第二级：得最优解：（8，1，0），最优值：min d1-0 ，min d2-0 ，min d2+7第三级：得最优解：（8，1，0），最优值：min d1-0 ，min d2-0 ，min d2+7，min d3+0即产品1安排生产8件，产品1安排1件最合适。 2、min 5d1-4d2-+2d2+3d3+ S.T. 15xl10x212x3d1+ +d1-130 6x14x25x3d2+ +d2-45 6x18x210x3d3+ +d3-60xi0 (i=1,2,3)di+ 、di- 0 (i=1,2,3) 得最优解：（7.333，2，0），最优值：min 5d1-4d2-+2d2+3d3+14 即产品1安排生产7.333件，产品2安排2件最合适。8.5某公司准备从两个不同仓库向三个居民点提供某种产品。在计划其内该产品供不应求，公司决定重点保证某些居民点的需要，同时又要保证总的运费要最省。已知仓库的库存量、各居民点的需求量及仓库到各居民点的单位运费如下表： 运价单位：元/单位产品居民点1居民点2居民点3库存量（单位产品）仓库1125103200仓库2101244500需求量（单位产品）250018005000公司要求在制定运输方案时考虑以下六个有序目标：P1-完全满足居民点3的需求。P2-至少满足所有居民点需求的75%。P3-使总的运费为最小。P4-从仓库2向居民点3的最小货运量为1200单位。P5-从仓库1到居民点3和从仓库2到居民点1的公路不好，希望尽可能减少运货量。P6-平衡居民点1和居民点2之间的供货量最满意水平。试求满意的运输方案。解：这是一个运输问题，但由于库存量（3200+4500=8700单位）不能完全满足3个居民点的需求（2500+1800+5000=9300单位），所以是一个产销不平衡的运输问题，我们先不考虑六个目标的附加条件，先求出无条件产销不平衡的最佳运输方案。居民点1居民点2居民点3库存量（单位产品）仓库190018005003200仓库2 45004500需求量（单位产品）250018005000最小运输费用：42800元下面考虑公司设有的6个有序目标，可利用优先目标规划模型来求解。各级的目标规划数学模型一级：满足居民点3的需求。 所以 min d1- S.T. xlx2x33200x4x5x64500 x1x42500x2x51800x3x65000x3x6d1+ +d1-5000 xi0 (i=1,2.6)di+ 、di- 0 (i=1) 得最优解：居民点1居民点2居民点3库存量（单位产品）仓库125002005003200仓库2 45004500需求量（单位产品）250018005000最优值：min d1-0二级： 至少满足所有居民点需求的75%。 所以 min d2-+ d3-+d4- （计算时需求修改求解模型！） S.T. xlx2x33200x4x5x64500 x1x42500x2x51800x3x65000 x3x6d1+ +d1-5000x1x4d2+ +d2-1875x2x5d3+ +d3-1350x3x6d4+ +d4-3750d1-0xi0 (i=1,2.6)di+ 、di- 0 (i=1,24) 得最优解：居民点1居民点2居民点3库存量（单位产品）仓库1135013505003200仓库2 45004500需求量（单位产品）250018005000最优值：min d1-0，min d2-525，min d3-0，min d4-0三级： 使总的运费为最小。 所以 min P1（d5+） S.T. xlx2x33200x4x5x64500 x1x42500x2x51800x3x65000 x3x6d1+ +d1-5000x1x4d2+ +d2-1875x2x5d3+ +d3-1350x3x6d4+ +d4-3750d1-0 12xl5x210x3 10x412x54x6d5+ +d5-0 （也可以取42800） d2-525d3-0d4-0xi0 (i=1,2.6)di+ 、di- 0 (i=1,25) 得最优解：居民点1居民点2居民点3库存量（单位产品）仓库1135013505003200仓库2 45004500需求量（单位产品）250018005000最优值：min d1-0，min d2-525，min d3-0，min d4-0，min d5+45950四级： 从仓库2向居民点3的最小货运量为1200单位。 所以 min P1（d6-） S.T. xlx2x33200x4x5x64500 x1x42500x2x51800x3x65000 x3x6d1+ +d1-5000x1x4d2+ +d2-1875x2x5d3+ +d3-1350x3x6d4+ +d4-3750d1-0 12xl5x210x3 10x412x54x6d5+ +d5-0 （也可以取42800） d2-525d3-0d4-0 x6d6+ +d6-1200 d5+45950xi0 (i=1,2.6)di+ 、di- 0 (i=1,26)得最优解：居民点1居民点2居民点3库存量（单位产品）仓库1135013505003200仓库2 45004500需求量（单位产品）250018005000最优值：min d1-0，min d2-525，min d3-0，min d4-0，min d5+45950min d6-0五级： 从仓库1给居民点3和从仓库2给居民点1的公路不好，希望尽可能减少运货量。 所以 min P1（d7+d8+） S.T. xlx2x33200x4x5x64500 x1x42500x2x51800x3x65000 x3x6d1+ +d1-5000x3x6d1+ +d1-5000x1x4d2+ +d2-1875x2x5d3+ +d3-1350x3x6d4+ +d4-3750d1-0 12xl5x210x3 10x412x54x6d5+ +d5-0 （也可以取42800） d2-525d3-0d4-0 x6d6+ +d6-1200 d5+45950x3d7+ +d7-0x4d8+ +d8-0d6-0xi0 (i=1,2.6)di+ 、di- 0 (i=1,28)得最优解：居民点1居民点2居民点3库存量（单位产品）仓库1135013505003200仓库2 45004500需求量（单位产品）250018005000最优值：min d1-0，min d2-525，min d3-0，min d4-0，min d5+45950min d6-0 ，min d7+500，min d8+0六级： 平衡居民点1和居民点2之间的供货时满意水平。即两个居民点人平均得到产品数量要一样。 所以 min P1（d9+d9-） S.T. xlx2x33200x4x5x64500 x1x42500x2x51800x3x65000 x3x6d1+ +d1-5000x3x6d1+ +d1-5000x1x4d2+ +d2-1875x2x5d3+ +d3-1350x3x6d4+ +d4-3750d1-0 12xl5x210x3 10x412x54x6d5+ +d5-0 （也可以取42800） d2-525d3-0d4-0 x6d6+ +d6-1200 d5+45950x3d7+ +d7-0x4d8+ +d8-0d6-0（x1x4）/2500（x2x5）/1800d9+ +d9-0d7+500d8+0xi0 (i=1,2.6)di+ 、di- 0 (i=1,29)得最优解：居民点1居民点2居民点3库存量（单位产品）仓库1135013505003200仓库2 45004500需求量（单位产品）250018005000最优值：min d1-0，min d2-525，min d3-0，min d4-0，min d5+45950min d6-0 ，min d7+500，min d8+0，min d9+1.296，min d9-0即：本问题按上表所示的运输方案执行最合适，部分目标能完全实现，但也有少数目标不能实现。8.6 一家大公司有两分公司G1和G2。该公司的业务是向零售商供应石油和酒精。为对各分公司进行业务考核，要求将零售商分给两个分公司，由分公司给只属于它的零售商供货。这种划分要尽可能使G1占有45%的市场份额，G2占有55%的市场份额。零售商共有25家，记作S1-S25。按地域又将零售商划分为三个区，S1-S8在一区，S9-S18在二区，S19-S25在三区，并将发展前景好零售商为A类，其余的归为B类。各零售商目前估计占有的销售量及各供货点的情况如下表：区域零售商石油销量（吨）供货点数（个）酒精销量（吨）分类一区S181032AS21236410AS3134280BS41623150BS510106AS61924180BS7122515AS82050200B二区S9818100AS10105220BS11162053AS12181002AS131788AS141816100BS152132110AS162398112AS173552500BS18422010A三区S1951052BS20152030AS21141570AS22241065BS23382028AS24361630AS25291842B公司的计划中要求，两个分公司在下列7个方面的比例都要接近于45/55。P1-货点总数。P2-酒精市场占有份额。P3-一区的石油市场占有份额。P4-二区的石油市场占有份额。P5-三区的石油市场占有份额。P6-A类零售商数。P7-B类零售商数。解：本问题的目标规划数学模型：min P1（d1-d1+）P2（d2-d2+）P3（d3-d3+）P4（d4-d4+）P5（d5-d5+）P6（d6-d6+）P7（d7-d7+）S.T. 10xl36x242x323x410x524x625x750x818x952x1020x11100x12 8x1316x1432x1598x1652x1720x1810x1920x2015x2110x2220x2316x2418x25d1+ +d1-33532xl410x280x3150x46x5180x615x7200x8100x920x1053x112x12 8x13100x14110x15112x16500x1710x1852x1930x2070x2165x2228x2330x2442x25d2+ +d2-1082 8xl12x213x316x410x519x612x720x8d3+ +d3-548x910x1016x1118x12 17x1318x1421x1523x1635x1742x18d4+ +d4-945 x1915x2014x2124x2238x2336x2429x25d5+ +d5-72x1x2x5x7x9x11x12x13x15x16x18x20x21x22x24d6+ +d6-7 x3x4x6x8x10x14x17x19x23x25d7+ +d7-5xi0 (i=1,2.25)di+ 、di- 0 (i=1,2.7) 由于本问题是0-1整数的目标规划问题，所以只能用EXCEL求解模型来求解。并且每一级的计算时间都可能在5分钟以上。模型求解：第一级： min d1-d1+10xl36x242x323x410x524x625x750x818x952x1020x11100x12 8x1316x1432x1598x1652x1720x1810x1920x2015x2110x2220x2316x2418x25d1+ +d1-335xi0 (i=1,2.25)d1+ 、d1- 0最优解：（1，0，0，0，0，0，0，0，0，1，0，1，1，0，0，1，1，0，0，0，1，0，0，0，0）最优值： d1-0，d1+0第二级： min d2-d2+10xl36x242x323x410x524x625x750x818x952x1020x11100x12 8x1316x1432x1598x1652x1720x1810x1920x2015x2110x2220x2316x2418x25d1+ +d1-33532xl410x280x3150x46x5180x615x7200x8100x920x1053x112x12 8x13100x14110x15112x16500x1710x1852x1930x2070x2165x2228x2330x2442x25d2+ +d2-1082 d1-0 d1+0 xi0 (i=1,2.25)di+ 、di- 0 (i=1,2) 即：最优解：（0，1，1，1，0，1，1，1，1，0，0，0，0，0，1，0，1，1，0，0，1，0，0，0，0）最优值： d1-0，d1+0 d2-0，d2+0第三级： min d3-d3+10xl36x242x323x410x524x625x750x818x952x1020x11100x12 8x1316x1432x1598x1652x1720x1810x1920x2015x2110x2220x2316x2418x25d1+ +d1-33532xl410x280x3150x46x5180x615x7200x8100x920x1053x112x12 8x13100x14110x15112x16500x1710x1852x1930x2070x2165x2228x2330x2442x25d2+ +d2-1082 8xl12x213x316x410x519x612x720x8d3+ +d3-54d1-0 d1+0 d2-0 d2+0 xi0 (i=1,2.25)di+ 、di- 0 (i=1,2，3)最优解：（1，1，0，1，0，0，0，1，1，0，1，0，0，0，1，0，1，0，1，1，0，1，1，1，1）最优值： d1-0，d1+0 d2-0，d2+0d3-0，d3+2第四级： min d4-d4+10xl36x242x323x410x524x625x750x818x952x1020x11100x12 8x1316x1432x1598x1652x1720x1810x1920x2015x2110x2220x2316x2418x25d1+ +d1-33532xl410x280x3150x46x5180x615x7200x8100x920x1053x112x12 8x13100x14110x15112x16500x1710x1852x1930x2070x2165x2228x2330x2442x25d2+ +d2-1082 8xl12x213x316x410x519x612x720x8d3+ +d3-548x910x1016x1118x12 17x1318x1421x1523x1635x1742x18d4+ +d4-94d1-0 d1+0 d2-0 d2+0 d3-0 d3+2 xi0 (i=1,2.25)di+ 、di- 0 (i=1,2，3，4)最优解：（1，1，0，1，0，0，0，1，1，0，1，0，0，0，1，0，1，0，1，1，0，1，1，1，1）最优值： d1-0，d1+0 d2-0，d2+0d3-0，d3+2d4-14，d4+0第五级： min d5-d5+10xl36x242x323x410x524x625x750x818x952x1020x11100x12 8x1316x1432x1598x1652x1720x1810x1920x2015x2110x2220x2316x2418x25d1+ +d1-33532xl410x280x3150x46x5180x615x7200x8100x920x1053x112x12 8x13100x14110x15112x16500x1710x1852x1930x2070x2165x2228x2330x2442x25d2+ +d2-1082 8xl12x213x316x410x519x612x720x8d3+ +d3-548x910x1016x1118x12 17x1318x1421x1523x1635x1742x18d4+ +d4-945 x1915x2014x2124x2238x2336x2429x25d5+ +d5-72d1-0 d1+0 d2-0 d2+0 d3-0 d3+2 d4-14 d4+0xi0 (i=1,2.25)di+ 、di- 0 (i=1,2，3，4，5)最优解：（1，1，0，1，0，0，0，1，1，0，1，0，0，0，1，0，1，0，1，1，0，1，1，1，1）最优值： d1-0，d1+0 d2-0，d2+0d3-0，d3+2d4-14，d4+0d5-0，d5+75第六级： min d6-d6+10xl36x242x323x410x524x625x750x818x952x1020x11100x12 8x1316x1432x1598x1652x1720x1810x1920x2015x2110x2220x2316x241