数学建模整数规划.pdf

整数规划模型整数规划模型 实际问题中实际问题中 xxxxfzMaxMin T n ?),(),()( 1 =或 的优化模型的优化模型 mixgts i ?, 2 , 1, 0)(. .= x决策变量决策变量f(x)目标函数目标函数 gi(x) 0约束条件约束条件 多元函数多元函数 决策变量个数决策变量个数n和和 约束条件个数约束条件个数m较大较大 数数 学学 线性规划线性规划 多元函数多元函数 条件极值条件极值 约束条件个数约束条件个数m较大较大 最优最优解解在可行域在可行域 学学 规规 划划 非线性规划非线性规划 整数规划整数规划 解解 的边界上取得的边界上取得 划划 整数规划整数规划 +Integer Programming+Integer Programming 所有变量都取整数，称为纯整数规划；有一部所有变量都取整数，称为纯整数规划；有一部 分取整数，称为混合整数规划；限制取分取整数，称为混合整数规划；限制取0，1称称 为为0 1型整数规划型整数规划为为01型整数规划型整数规划。 整数线性规划整数线性规划+整数线性规划整数线性规划 max(min) n jj zc x= 1 jj j n = 1 s.t. ( , ) 1,2, ijji j a xbim = = = ? 12 ,0 () n x xx ?且为整数 或部分为整数 +例：假设有例：假设有m种不同的物品要装入航天飞机，种不同的物品要装入航天飞机， 它们的重量和体积分别为它们的重量和体积分别为和和价值为价值为它们的重量和体积分别为它们的重量和体积分别为wj 和和 vj，价值为价值为cj， 航天飞机的载重量和体积限制分别为 ， 航天飞机的载重量和体积限制分别为W和和V， 如何装载使价值最大化？如何装载使价值最大化？ m 1被装载 1 max jj j c y = 1 0 j j y j = 被装载 没被装载 s.t. m jj v yV 0 j 没被装载 1j m W = 1 jj j w yW = 0 or 1 1,2, j yjm=? 美国芝加哥(Chi)大学的LiS h教授于1980年美国芝加哥(Chicago)大学的Linus Schrage教授于1980年 前后开发, 后来成立 LINDO系统公司（LINDO Systems I）网址htt /li dInc.）， 网址： LINDO: Linear Interactive and Discrete Optimizer(V6 1)LINDO: Linear Interactive and Discrete Optimizer (V6.1) LINGO: Linear Interactive General Optimizer (V8.0) LINDO解决线性规划LPLinear Programming，整数规划IP Integer Programming问题。 LINGO解决线性规划LPLinear Programming，非线性规划 NLPNonlinear Programming，整数规划IPInteger Programminggg整划ggg 问题。 1.“”（或“（或“=”（或“（或“=”）功能相）功能相 同同 2.变量与系数间可有空格变量与系数间可有空格(甚至甚至回回车车), 但但无运无运算算变量与系数间可有空格变量与系数间可有空格(甚至车甚至车), 但算但算 符符 3.变量名变量名以以字母开头字母开头，不能超过不能超过8个字符个字符3.变量名字母开头变量名字母开头，不能超过不能超过8个字符个字符 4.变量名不区分大小写（包括变量名不区分大小写（包括LINDO中的关键中的关键 字字）字字） 5.目标函数所在行是第一行，第二行起为约束目标函数所在行是第一行，第二行起为约束 条件条件 6.行号行号(行名行名)自动产生或人为定义自动产生或人为定义。行名以行名以6.行号行号(行名行名)自动产生或人为定义自动产生或人为定义。行名以行名以 “）”结束“）”结束 7.变量不能出现在变量不能出现在一一个约束条件的右端个约束条件的右端7. 变量不能出现在个约束条件的右端变量不能出现在个约束条件的右端 8. 表达式中不接受括号“表达式中不接受括号“( )”和逗号“和逗号“,”等任何等任何 符号符号 例例: 400(X1+X2)需写为需写为400X1+400X2符号符号, 例例: 400(X1+X2)需写为需写为400X1+400X2 9.表达式应化简，如表达式应化简，如2X1+3X2 4X1应写成应写成 2X1 3X22X1+3X2 10.缺省假定所有变量非负；可在模型的“缺省假定所有变量非负；可在模型的“END” 语句后用“语句后用“FREE name”将变量将变量name的非负 假定取消 的非负 假定取消 11. “END”后对后对01变量说明：变量说明：INT n 或或 INT name 12 “END”后对整数变量说明后对整数变量说明GIN n 或或 GIN12. “END”后对整数变量说明后对整数变量说明：GIN n 或或 GIN name 汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢 材材劳动时间的需求劳动时间的需求利润及工厂每月的现有量利润及工厂每月的现有量。材材、劳动时间的需求劳动时间的需求，利润及工厂每月的现有量利润及工厂每月的现有量。 小型中型大型现有量小型中型大型现有量 钢材（吨）钢材（吨）1.5 3 5 600 劳动时间（小时）劳动时间（小时）280 250 400 60000 利润（万元）利润（万元）2 3 4 制订制订月生产计划月生产计划使工厂的利润最大使工厂的利润最大 如果生产某一类型汽车，则至少要生产80辆，如果生产某一类型汽车，则至少要生产80辆， 制订制订月生产计划月生产计划，使工厂的利润最大使工厂的利润最大。 那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？ 汽车厂汽车厂生生产计划产计划汽车厂产计划汽车厂产计划 模模型型建建立立小型小型中中型大型现有量型大型现有量 设每月生产小、中、大型设每月生产小、中、大型 模建模建中中 钢材钢材1.5 3 5 600 时间时间28025040060000 汽车的数量分别为汽车的数量分别为x1, x2, x3 时间时间280 250 400 60000 利润利润2 3 4 321 432xxxzMax+= 6005351+t 线线性性 600535 . 1. 321 +xxxts 60000400250280 321 +xxx 线线 规划 模型 规划 模型 321 0, 321 xxx (LP) 模型模型 OBJECTIVE FUNCTION VALUE 模型模型 求解求解 1)632.2581 VARIABLEVALUEREDUCED COST X164.5161290.000000X164.5161290.000000 X2167.7419280.000000 X30.0000000.946237 ROWSLACK OR SURPLUSDUAL PRICES 结果为小数，结果为小数， ROWSLACK OR SURPLUSDUAL PRICES 2)0.0000000.731183 3)0.0000000.003226 怎么办？怎么办？ 1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与 LP最优值最优值632.2581相差不大。相差不大。 2）试探：如取）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数 值 等，计算函数 值z，通过比较可能得到更优的，通过比较可能得到更优的解解。 3） 模型中增加条件模型中增加条件：x1, x2, x3均为整数均为整数，重新求解重新求解。 但必须检验它们是否满足约束条件。但必须检验它们是否满足约束条件。 3） 模型中增加条件模型中增加条件：x1, x2, x3均为整数均为整数，重新求解重新求解。 整数规划(整数规划(Integer Programming, ,简简记记IP) ) 模型求解模型求解 IP可用可用LINDO直接求解直接求解 max 2x1+3x2+4x3 321 432xxxzMax+= 模型求解模型求解 max 2x1+3x2+4x3 st 1.5x1+3x2+5x3600 600535 . 1. 321 +xxxts 60000400250280 321 +xxx 1.5x1+3x2+5x3600 280 x1+250 x2+400 x30 y=1 Max 4.8x11+4.8x21+5.6x12+5.6x2210 x18x26x3 st st x11+x12x0 0.4x120.6x220 xx1x2x3=0 x1500y10 x1 500y10 x2500y20 end int y1y int y2 int y3 01线性规划模型，可用线性规划模型，可用LINDO求解求解 OBJECTIVE FUNCTION VALUE 1)5000.000 VARIABLEVALUEREDUCED COSTVARIABLEVALUEREDUCED COST Y11.0000000.000000 Y21.0000002200.000000 Y31.0000001200.000000 X110 0000000 800000X110.0000000.800000 X210.0000000.800000 X121500.0000000.000000 X221000.0000000.000000 X1500.0000000.000000 X2500.0000000.000000 X30.0000000.400000 X1000 0000000 000000X 1000.0000000.000000 购买购买1000吨原油吨原油A，与，与库库存的存的500吨原油吨原油A和和1000吨原油吨原油B 一起，生产一起，生产2500吨汽油乙，利润为吨汽油乙，利润为5,000千元 。千元 。 分派问题分派问题分派问题分派问题 若干项任务分给一些候选人来完成，每人的专长不同，若干项任务分给一些候选人来完成，每人的专长不同， 完成每项任务取得的效益或需要的资源就不同，如何分完成每项任务取得的效益或需要的资源就不同，如何分 派任务使获得的总效益最大派任务使获得的总效益最大，或付出的总资源最少或付出的总资源最少。派任务使获得的总效益最大派任务使获得的总效益最大，或付出的总资源最少或付出的总资源最少。 选择问题选择问题 若干种策略供选择，不同的策略得到的收益或付出的若干种策略供选择，不同的策略得到的收益或付出的 成本不同成本不同各个策略之间有相互制约关系各个策略之间有相互制约关系如何在满如何在满成本不同成本不同，各个策略之间有相互制约关系各个策略之间有相互制约关系，如何在满如何在满 足一定条件下作出决择，使得收益最大或成本最小。足一定条件下作出决择，使得收益最大或成本最小。 5名候选人的百米成绩名候选人的百米成绩 甲甲乙乙丙丙丁丁戊戊 蝶泳蝶泳106”857”2118”110”107”4 仰泳仰泳115”6106”107”8114”2111” 蛙泳蛙泳127”106”4124”6109”6123”8 如何选拔队员组成如何选拔队员组成4 100米混合泳接力队米混合泳接力队? ? 自由泳自由泳58”653”59”457”2102”4 丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进 如何选拔队员组成如何选拔队员组成4 100米混合泳接力队米混合泳接力队? ? 步到步到57”5, 组成接力队的方案是否应该调整？组成接力队的方案是否应该调整？ 穷举法穷举法组成接力队的方案共有组成接力队的方案共有5! 120种种穷举法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种。 cij( (秒秒) )队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩cij( (秒秒) ) 队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩 ciji=1i=2i=3i=4i=5 j 166 857 2787067 4j=166.857.2787067.4 j=275.66667.874.271 j=38766 484 669 683 8 若选择队员若选择队员i参加泳姿参加泳姿j 的比赛的比赛记记x =1否则记否则记x =0 j=38766.484.669.683.8 j=458.65359.457.262.4 目标目标 若选择队员若选择队员i参加泳姿参加泳姿j 的比赛的比赛，记记xij=1, , 否则记否则记xij=0 45 xcZMin 函数函数 约束约束 每人最多入选泳姿之一每人最多入选泳姿之一 = = 11ji ijij xcZMin 每种泳姿有且只有每种泳姿有且只有1 1人人 约束约束 条件条件 每人最多入选泳姿之一每人最多入选泳姿之一每种泳姿有且只有每种泳姿有且只有1 1人人 511 4 ?= ix411 5 ?= jx5, 1, 1 1 ?= = ix j ij 4, 1, 1 1 = = jx i ij 模型求解模型求解 输输入入LINDO求解求解 模型求解模型求解 输输求解求解 MIN 66.8x11+75.6x12+87x13+58.6x14+57.2x21+66x22 +66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70 x41 +74.2x42+69.6x43+57.2x44+67.4x51+71x52+83.8x53+62.4x54 SUBJECT TO x11+x12+x13+x14 =1 x21+x22+x23+x24 =1 x31+x32+x33+x34 =1 x41+x42+x43+x44 =1 x51+x52+x53+x54 =1x51 x52 x53 x54 1 x11+x21+x31+x41+x51 =1 x12+x22+x32+x42+x52 =1 x13+x23+x33+x43+x53 =1x13+x23+x33+x43+x53 1 x14+x24+x34+x44+x54 =1 END INT 20INT 20 OBJECTIVE FUNCTION VALUE 1) 253.2000 最优解最优解： VARIABLE VALUE REDUCED COST X11 0.000000 66.800003 X12 0.000000 75.599998 最优解最优解 x14= x21= x32= x43= 1, X13 0.000000 87.000000 X141.00000058.599998 X211.00000057.200001 X220 00000066 000000 其它变量为其它变量为0; X22 0.000000 66.000000 X23 0.000000 66.400002 X24 0.000000 53.000000 X310 00000078 000000 成绩为成绩为253.2(秒)(秒)=413”2 X31 0.000000 78.000000 X32 1.00000067.800003 X33 0.000000 84.599998 X340 00000059 400002 甲甲 自由泳自由泳 X34 0.000000 59.400002 X41 0.000000 70.000000 X42 0.000000 74.199997 X431.00000069.599998 乙乙 蝶泳蝶泳 X431.000000 69.599998 X44 0.000000 57.200001 X51 0.000000 67.400002 X52 0.000000 71.000000 丙丙 仰泳仰泳 丁丁 蛙泳蛙泳 50 000000000000 X53 0.000000 83.800003 X54 0.000000 62.400002 丁丁 蛙泳蛙泳 甲甲乙乙丙丙丁丁戊戊 蝶泳蝶泳106”857”2118”110”107”4 仰泳仰泳115”6106”107”8114”2111” 蛙泳蛙泳127”106”4124”6109”6123”8 自由泳自由泳58”653”59”457”2102”4 讨论讨论 丁蛙泳丁蛙泳69 675 2戊自由泳戊自由泳62 4 讨论讨论 丁蛙泳丁蛙泳c43= =69.675.2，戊自由泳戊自由泳c54= =62.4 57.5, 方案是否调整？敏感性分析？, 方案是否调整？敏感性分析？ IP规划般没有与规划般没有与LP规划相类似的理论规划相类似的理论LINDO输出输出IP规划规划一一般没有与般没有与LP规划相类似的理论规划相类似的理论，LINDO输出输出 的敏感性分析结果通常是没有意义的。的敏感性分析结果通常是没有意义的。 cc的新数据重新输入模型的新数据重新输入模型用用LINDO求解求解c43, c54的新数据重新输入模型的新数据重新输入模型，用用LINDO求解求解 模型求解模型求解 输输入入LINDO求解求解 模型求解模型求解 输输求解求解 MIN 66.8x11+75.6x12+87x13+58.6x14+57.2x21+66x22 +66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70 x41 +74.2x42+75.2x43+57.2x44+67.4x51+71x52+83.8x53+57.5x54 SUBJECT TO x11+x12+x13+x14 =1 x21+x22+x23+x24 =1 x31+x32+x33+x34 =1 x41+x42+x43+x44 3 x4+x6+x7+x92 2x3x1x20 VARIABLE VALUE REDUCED COST X1 1.000000 1.000000 X21 0000001 000000 x4x70 2x5x1x20 x6x70 X2 1.000000 1.000000 X3 1.000000 1.000000 X4 0.000000 1.000000 X50.0000001.000000 x8x53 OBJECTIVE FUNCTION VALUE 1) 22.00000 x3 x5 x6 x8 x93 x4+x6+x7+x92 2x3x1x20 x4x70 VARIABLE VALUE REDUCED COST X1 1.000000 5.000000 X2 1.000000 4.000000 2x5x1x20 x6x70 x8x53 x4+x6+x7+x92 2x3x1x20 x4x70 2x5x1x20 OBJECTIVE FUNCTION VALUE x6x70 x8x50 2x9x1x20 d OBJECTIVE FUNCTION VALUE 1) 2.800000 end int 9 VARIABLE VALUE REDUCED COST X1 1.000000 0.800000 X2 1.000000 0.500000 X3 1.000000 0.500000 X4 1.000000 0.200000 X5 1.000000 0.500000 X6 1.000000 0.200000 X7 1.000000 0.100000 X8 0.000000 0.100000 X91 0000000 200000X9 1.000000 0.200000 多目标规划多目标规划 WZYMin 21 =1,0, 1 2121 =+ 多目标规划多目标规划 WZYMin 21 1,0, 1 2121 + 54321 43445xxxxxW+= = 9 i xZ 9876 3223xxxx+ =1i i 原料下料问题原料下料问题 生产中通过切割生产中通过切割剪裁剪裁冲压等冲压等 原料下料问题原料下料问题 生产中通过切割生产中通过切割、剪裁剪裁、冲压等冲压等 手段，将原材料加工成所需大小手段，将原材料加工成所需大小 按照工艺要求，确定下料方案，按照工艺要求，确定下料方案， 使所用材料最省，或利润最大使所用材料最省，或利润最大 原料钢管原料钢管: :每根每根19米米原料钢管原料钢管: :每根每根19米米 客户需求客户需求 4米米50根根6米米20根根 8米米15根根 问题问题1. 如何下料最节省如何下料最节省 ? 节省的标准是什么？节省的标准是什么？ 问题问题2. 客户增加需求：客户增加需求：5米米10根根 由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本， 规定切割模式不能超过规定切割模式不能超过3种种如何下料最节省如何下料最节省？规定切割模式不能超过规定切割模式不能超过3种种。如何下料最节省如何下料最节省？ 钢管下料钢管下料 按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。 钢管下料钢管下料 余料余料 米米米米米米米米余料余料1 1米米4米米1根根6米米1根根8米米1根根 余料余料3米米4米米1根根6米米1根根6米米1根根 余料余料3米米8米米1根根 8米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸 余料余料3米米8米米1根根 米米 根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸 钢管下钢管下料料问题1 问题1 模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米) 14003 23101 32013 41203 51111 60301 为满客户需要为满客户需要照些种式照些种式每种式每种式 60301 70023 为满为满足足客户需要客户需要，按，按照照哪哪些种些种合理模合理模式式，每种每种模模式式 切割切割多多少根原少根原料料钢管，最钢管，最为节为节省？省？ 两种两种 标准标准 1. 原料钢管剩余总余量最小原料钢管剩余总余量最小 2. 所用原料钢管总根数最少所用原料钢管总根数最少 标准标准 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i 1 27) ) 决策决策 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,7) ) 变量变量 目标目标1（总余量总余量） 76543211 3333xxxxxxxZMin+= 约束约束满足需求满足需求 目标目标 （总余量总余量） 76543211 模 式 模 式 4米 根数 米 根数 6米 根数 米 根数 8米 根数 米 根数 余 料 余 料 50234 54321 +xxxxx 2032 6542 +xxxx 152 14003 23101 152 753 +xxx32013 41203 51111 整整数数约束约束： xi为整为整数数 51111 60301 70023 最优解：最优解：x2=12, x5=15, 其余为其余为0 整约束整约束 i 为整 为整 70023 需 求 需 求 502015 其余为其余为0； 最优值： ； 最优值：27。 按模式按模式2切割切割12根,按模式根,按模式5切割切割15根，余料根，余料27米米 钢管下钢管下料料问题1 问题1 76543212 xxxxxxxZMin+=目标目标2（总根数）（总根数） 约束条约束条 件不变件不变 最优解：最优解：x2=15, x5=5, x7=5, 50234 54321 +xxxxx 2032 6542 +xxxx 件不变件不变 5 , 7 , 其余为其余为0； 最优值最优值25 2032 6542 +xxxx 152 753 +xxx 为整数 最优值最优值：25。 xi 为整数 按模式按模式2切切割割15根，根， 与与目标目标1的结果的结果“共切割共切割 割割 按模式按模式5切割切割5根，根， 按模式按模式7切割切割5根根 与与目标目标1的结果的结果共切割共切割 27根，余料根，余料27米” 相比米” 相比 按模式按模式7切割切割5根根， 共 ， 共25根，余料根，余料35米 虽余料增加 米 虽余料增加8米，但减少了米，但减少了2根根 当余料没有用处时，通常以总根数最少为目标当余料没有用处时，通常以总根数最少为目标 钢管下料问题钢管下料问题2 增加一种需求：增加一种需求：5米米10根；切割模式不超过根；切割模式不超过3种。种。 现有现有4种需求：种需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米 15根根用枚举法确定合理切割模式用枚举法确定合理切割模式过于复杂过于复杂 对大规模问题对大规模问题，用模型的约束条件界定合用模型的约束条件界定合理理模式模式 15根根，用枚举法确定合理切割模式用枚举法确定合理切割模式，过于复杂过于复杂。 对大规模问题对大规模问题，用模型的约束条件界定合模式用模型的约束条件界定合模式 决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数(种模式切割的原料钢管根数(i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管 生产生产4米米、5米米、6米和米和8米长的钢管的数量米长的钢管的数量生产生产4米米、5米米、6米和米和8米长的钢管的数量米长的钢管的数量 钢管下钢管下料料问题问题2 目标函数（总根数）目标函数（总根数） 321 xxxMin+ 满足需求满足需求 模式合理：每根模式合理：每根 余料不超过余料不超过3米米 约束约束 条件条件 满足需求满足需求 50 313212111 +xrxrxr 余料不超过余料不超过3米米 19865416 41312111 +rrrr 条件条件 50 313212111 +xrxrxr 10 323222121 +xrxrxr 41312111 19865416 42322212 +rrrr 20 333232131 +xrxrxr 15+ 19865416 43332313 +rrrr 整数约束整数约束： xi,r1i, r2i, 15 343242141 +xrxrxr 整数线划型整数线划型 整数约束整数约束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3)为整数)为整数 整数整数非非线线性规性规划划模模型型 增加约