资源描述：
《数学建模-第五章整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章整数规划运筹学OperationsResearch第五章整数规划在LP问题的讨论中，有些最优解是小数.但对于某些具体问题常有要求最优解是整数(即整数解).如决策变量为机器的台数、人数、车辆数etc.如果在问题中所有决策变量有整数限制，称为纯整数规划(PureIP)或全整数规划(AllIP)；如果在问题中仅部分决策变量有整数限制，称为混合整数规划(MixedIP)；如果在问题中决策变量仅取0、1，称为0-1(整数)规划.IntegerProgramming第五章整数规划§1整数规划问题及其数学模型§2整数规划的解法§3整数规
2、划的应用举例§1整数规划问题及其数学模型§1整数规划问题及其数学模型货物每箱体积（m3）每箱重量（kg）每箱利润（百元）甲5220乙4510托运限制2413Example1（装载问题）某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运限制如表，问两种货物各托运几箱，可获利润最大？Solution:设x1、x2分别为甲、乙两种货物托运箱数.则这是一个PureIP问题.第五章整数规划Example2（工厂选址问题）现准备从A1、A2、A3三个地点中选择两个开设工厂，工厂建成后它每月的产量ai(i=1,2,3)、三个客
3、户B1、B2、B3每月的需求量bj(j=1,2,3)及Ai至客户Bj的单位运价cij见表.BjAiB1B2B3aiA145370A223480A364590bj406045已知三工厂每月的经营费用di(与产量无关)分别为100、90、120.问如何选址使每月经营和运输费用最低.Solution:因为只有三个厂址选两个，，所以简单的方法是任取两个厂用运输问题求解，再加上每月的经营费用比较即可.设选地点Ai开设工厂否则i=1,2,3；xij为Ai开设工厂时，从Ai至Bj的运量显然如果Ai处开设工厂，则运量满足：不开设呢？客户端需求满
4、足：目标（每月的费用）：这是一个MixedIP问题.可用于设计分配系统、新生活小区的设置etc.§1整数规划问题及其数学模型在Ex.2中，引进0－1变量给出了在n件任务中,选择j项的约束又用来刻画不设第i项任务，则xijj=1~n都不起作用，为零.可应用于选择性约束条件中某工厂生产第j种产品的数量为xj(j=1,2,3)其使用的材料在甲、乙中选择一种，其消耗约束分别为：其他资源约束条件未列出引进0－1变量y选择材料甲选择材料乙M为充分大的正数一般地，假定要在p个约束条件中至少要选择q个约束条件得到满足，可引进0-1变量y第五章整
5、数规划Example3（背包问题）假设有人要出发旅行，考虑带七种物品，每件物品的重量与价值如表.现在假设他最多带35kg物品，问该带哪几件物品使总价值最大？物品重量aj价值cj1312241233943155159061326716112Solution:如果带第j件物品否则j=1~7这是一个0-1规划问题.一般整数规划中的变量x,也可用0-1变量替代，如0≤x≤15，x=x020+x121+x222+x323其中x0,x1,x2,x3为0-1变量.§1整数规划问题及其数学模型参见Ex.1,去掉整数约束，得舍入化整o12345x
6、14321x2由图解法得最优解为：x1=4.8,x2=0Zmax=96显然，x1不是整数.是否可以根据化整的原问题的解？x1=5、x2=0不是可行解，x1=4、x2=0Z=80.但是x1=4、x2=1也可行且Z=90.所以，“舍入化整”的结果：1、化整后未必可行；2、即使是可行解，也未必是最优解；3、用这个方法即使能得到最优解，但如果有n个变量，则取舍方案有2n种，计算量也是很大的.Goback第五章整数规划o12345x14321x2§2整数规划的解法有人在研究在建立模型中，什么条件下LP问题的解一定是整数解？如：运输问题从E
7、x.1的讨论，可得到一些启迪1、是否能在LP的约束区域中,切去n块不含整数解的可行域使整数解作为顶点，则LP的最优解即为整数解；如增加约束x1≤4,则LP问题的解即为整数解;2、在LP的可行域中，整数点不多，（12个）是否可以用穷举法.§2整数规划的解法一、割平面法1959年由R.E.Gomory首先提出，从此使IP逐渐形成为一个独立的运筹学分支.割平面法的实质是用解LP问题的方法求解IP问题；割平面法的基本思想是通过对LP问题的求解，如果最优解是整数解，则就是IP的解；否则设法对LP问题增加约束(割平面)，把LP问题的可行域中
8、去掉一部分不含整数解的，再求LP问题，反复进行.割平面法的关键在于如何寻找适当的切割约束条件.用割平面法求解IP问题常常会计算量大、收敛速度慢的情况，但在理论上是重要的，被认为是IP的核心.第五章整数规划二、分支定界法分支与定界法的基本思想是对有约束条件的最优化
