您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 09运筹学-整数规划介绍(还有点目标规划)
Page:1QSC浙江工商大学信息学院运筹学运筹学目标规划Page:2QSC浙江工商大学信息学院运筹学多目标决策问题实际问题决策经常面临的问题:方案优劣并不以单一准则为目标,而是以多重准则为目标约束条件并不完全符合严格的刚性条件,具有一定的弹性可能的弹性约束:最好等于最好不大于最好不小于Page:3QSC浙江工商大学信息学院运筹学弹性约束的处理方法实际量+d--d+=目标值负偏差变量正偏差变量ddMin最好等于:dMin最好不大于:dMin最好不小于:Page:4QSC浙江工商大学信息学院运筹学顾客访问策略老顾客新顾客正常可用访问时间访问每一顾客所需时间23640小时平均可获销售利润250125目标:•访问时间最好不超过680小时;•访问时间最好不少于600小时;•销售收入尽量不少于70,000;•访问老顾客数最好不少于200个;•访问新顾客数最好不少于120个Page:5QSC浙江工商大学信息学院运筹学模型-顾客访问策略0120200000,7012525060032680325524413321222111215544332211所有变量ddxddxddxxddxxddxxStdPdPdPdPdPZMinPage:6QSC浙江工商大学信息学院运筹学目标规划解的几何分析X100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d(4)4d4d(5)5d5dPage:7QSC浙江工商大学信息学院运筹学0120200000,7012525060032680325524413321222111215544332211所有变量ddxddxddxxddxxddxxStdPdPdPdPdPZMin目标规划的求解---序贯算法Page:8QSC浙江工商大学信息学院运筹学06803211211所有变量ddxxStdZMin0680320211所有变量xxd第一级目标X100300200600500400X21002003004005001(1)1d1dPage:9QSC浙江工商大学信息学院运筹学060032680322221212所有变量ddxxxxStdZMin第二级目标06003268032021212所有变量xxxxdX100300200600500400X21002003004005001(1)1d1d(2)2d2dPage:10QSC浙江工商大学信息学院运筹学第三级目标0000,70125250600326803202121213所有变量xxxxxxdX100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d0000,701252506003268032332121213所有变量ddxxxxxxStdZMinPage:11QSC浙江工商大学信息学院运筹学X100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d(4)4d4d0200000,7012525060032680324412121214所有变量ddxxxxxxxStdZMin第四级目标0200000,701252506003268032012121214所有变量xxxxxxxdPage:12QSC浙江工商大学信息学院运筹学X100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d(4)4d4d(5)5d5d第五级目标…………Page:13QSC浙江工商大学信息学院运筹学目标规划的求解---多阶段算法0120200000,7012525060032680325524413321222111215544332211所有变量ddxddxddxxddxxddxxStdPdPdPdPdPZMinPage:14QSC浙江工商大学信息学院运筹学初始单纯形表000P1P20P30P40P50x1x2d1-d1+d2-d2+d3-d3+d4-d4+d5-d5+RHS比值0231-100000000680680/3P223001-1000000600600/3P325012500001-100007000070000/125P4100000001-100200-P501000000001-1120120/1P1000100000000P2-2-30001000000P3-250-1250000010000P4-100000000100P50-10000000001d3-d1-d2-d4-d5-检验数Page:15QSC浙江工商大学信息学院运筹学单纯形表运算000P1P20P30P40P50x1x2d1-d1+d2-d2+d3-d3+d4-d4+d5-d5+RHS比值0201-1000000-33320320/3P220001-10000-33240240/3P3250000001-100-1251255500055000/125P4100000001-100200-001000000001-1120-P1000100000000P2-20000100003-3P3-250000000100125-125P4-100000000100P5000000000010d3-d1-d2-d4-x2检验数Page:16QSC浙江工商大学信息学院运筹学单纯形表运算000P1P20P30P40P50x1x2d1-d1+d2-d2+d3-d3+d4-d4+d5-d5+RHS比值0001-1-1100000080-02/30001/3-1/30000-118080/(2/3)P3500/3000-125/3-125/31-100004500045000/(500/3)P4100000001-100200200/102/31001/3-1/3000000200200/(2/3)P1000100000000P2000011000000P3-500/3000125/3125/3010000P4-100000000100P5000000000010d3-d1-d5+d4-x2检验数…Page:17QSC浙江工商大学信息学院运筹学运筹学整数线性规划Page:18QSC浙江工商大学信息学院运筹学整数线性规划问题的一般形式max(min)zcxcxcxnn1122njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn,,1,0).().().(..22112222212111212111中部分或全部取整数nxx,1Page:19QSC浙江工商大学信息学院运筹学整数线性规划问题的分类全整数线性规划混合整数线性规划0-1整数线性规划Page:20QSC浙江工商大学信息学院运筹学整数规划与其松弛问题当放弃整数约束时得到的线性规划称为整数规划的松弛问题。整数规划的可行域是松弛问题的可行域,反之不成立。Page:21QSC浙江工商大学信息学院运筹学全整数规划的求解---Gomory割平面方法为整数x,x0x,x5x2x104x5x3x23x..x3xzmax212121212121ts132X2X122.5154整数点松弛问题最优解Page:22QSC浙江工商大学信息学院运筹学松弛问题的最优解3-1000x1x2x3x4x5RHS3101/702/713/7-101-2/703/79/7000-3/7122/731/700-5/70-3/7x4x1x2检验数Page:23QSC浙江工商大学信息学院运筹学Gomory定理000,ijjiibxax在松弛问题的最优单纯形表中,假如有一常数项不是整数,且对应的方程为:0ib000000,,iiijijijifNbfNa分解和成最大整数与正分数之和:jia,00ibPage:24QSC浙江工商大学信息学院运筹学000,ijjiibxax00000)(,,iijjijiifNxfNxjjiiijjiixffNxNx,,000000,00jjiixff则包含了整数规划的所有整数可行解,但不包括松弛问题的最优解Page:25QSC浙江工商大学信息学院运筹学例题求解选择第一个方程:7137271531xxx分解为:5317271761xxxPage:26QSC浙江工商大学信息学院运筹学072717653xx在原松弛问题中加入约束:767271653xxx即形成松弛问题2Page:27QSC浙江工商大学信息学院运筹学3-10000x1x2x3x4x5x6RHS3101/702/7013/7-101-2/703/709/7000-3/7122/7031/7000-1/70-2/71-6/700-5/70-3/70x4x1x2检验数x63-10000x1x2x3x4x5x6RHS31000011-1010-1/40-5/45/40001-1/20-11/25/200001/41-3/47/4000-1/40-17/4x3x1x2检验数x5Page:28QSC浙江工商大学信息学院运筹学132X2X122.5154整数点松弛问题2的最优解010727176153xxx或:割平面Page:29QSC浙江工商大学信息学院运筹学选择第四个方程(具有最大分数部分):474341645xxx分解为:64654141431xxxxPage:30QSC浙江工商大学信息学院运筹学在松弛问题2中加入约束:即形成松弛问题3041414364xx434141764xxxPage:31QSC浙江工商大学信息学院运筹学3-100000x1x2x3x4x5x6x7RHS310000101-1010-1/40-5/405/40001-1/20-11/205/200001/41-3/407/40000-1/40-1/41-3/4000-1/40-17/40x3x1x2检验数x5x73-100000x1x2x3x4x5x6x7RHS310000101-101000-1-12000100-5-24000001-1110000101-4300000-40x3x1x2检验数x5x7得到最优解Page:32QSC浙江工商大学信息学院运筹学割平面:46356123124125113444126777323541025xxxxxxxxxxxxxx321xx132X2X122.5154松弛问题3的最优解松弛问题2的最优解Page:33QSC浙江工商大学信息学院运筹学如果选择第二个方程:454541642xxx分解为:6464243434112xxxxxPage:34QSC浙江工商大学信息学院运筹学在松弛问题2中加入约束:即形成松弛问题3043434164xx414343764xxxPage:35QSC浙江工商大学信息学院运筹学3-100000x1x2x3x4x5x6x7RHS310000101-1010-1/4
本文标题:09运筹学-整数规划介绍(还有点目标规划)
链接地址:https://www.777doc.com/doc-1356222 .html