运筹第四章整数规划与分配问题

《运筹第四章整数规划与分配问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章整数规划与分配问题2011年4月北京物资学院运筹学课件IntegerProgrammingandAssignmentProblem•线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。•要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(IntegerProgramming)。第一节整数线性规划问题第二节分配问题第三节分枝定界法*第四节割平面法*本章内容的安排第一节整数线性规划问题问题的提出整数规划问题的特征与性质整数规

2、划模型的分类例1（装载问题）有一辆卡车的最大载重量为b吨,现有n种货物可供装载。设第j种货物每件重aj吨,每件的装载费用为cj元(j=1,…n)。问应该采用怎样的装载方案才能使卡车一次装载货物的收入最大?解:设xj为卡车装载第j种货物的件数(j=1,2,…,,n),z表示卡车一次装载的收入,则该问题的数学模型为maxz=c1x1+c2x2+…+cnxns.t.a1x1+a2x2+…+anxnbxj0且为整数(j=1,2,…,,n)1.问题的提出例2.（选址问题—相互排斥的计划）某公司准备投资100万元在甲、乙两座城市修建健身中心，经过多方考察，最后选定A1,A2,A3,A4和A5五个

3、位置，并且决定在甲城市的A1、A2、A3三个位置中最多投建两个；在乙城市的A4、A5两个位置中最少投建一个。如果已知各点的投资金额和年利润如下表。问：健身中心投建在哪些位置才会使总的年利润最大？待定地址A1A2A3A4A5投资总额投资金额（万元）2030254045100年利润（万元）1025202530解：设则该问题的数学模型为例3工厂选址问题：某商品有n个销地，各销地的需求量为bj吨/天；现拟在m个地点中选址建生产厂，一个地点最多只能建一个工厂；若选i地建厂，生产能力为ai吨/天，固定费用为di元/天；已知i地至第j销地的单位运费为cij元/吨。问如何选址和安排调运，才能使总费用最小

4、？设：yi=1，表示选择第i地建厂，yi=0，表示不选择第i地建厂；从厂址i至销地j运量为xij，总费用为z。该问题的数学模型为例4某公司制造小、中、大3种尺寸的金属容器，所用的资源为金属板、劳动力和机时。制造一只容器所需的各种资源数量如下表所示，不考虑固定费用，每售出一只小、中、大号容器所得的利润分别为4元、5元、6元，可使用的金属板有500张，劳动力有300个，机时有100小时，如果生产某种容器，不管生产数量多少，都要支付一笔固定费用，小、中、大号容器的固定费用分别为100元、150元、200元，现要制订一生产计划，使获得的利润最大。资源小号容器中号容器大号容器资源拥有量金属板（张）

5、248500劳动力（个）234300机时（小时）123100利润456解：设x1,x2,x3分别表示小、中、大号容器的生产数量，M为很大的正数，z表示总利润引入逻辑变量若xj=0时，yj=0,若xj>0时，yj=1。逻辑变量在整数规划建模中的作用1、m个约束条件中只有k个起作用。定义则上述条件可以表示成2、约束条件的右端可能是r个值中的某一个定义则上述条件可以表示成3、两组条件中满足其中的一组定义i=1,2则问题可以表示为4用以表示含固定费用的函数总费用目标函数是总费用最小定义则目标函数可以表示成2.整数规划问题的特征与性质特征—变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质—

6、可行域是离散集合3.整数规划的分类纯整数规划要求全部决策变量的取值都为整数,则称为纯整数规划(AllIP)；混合整数规划仅要求部分决策变量的取值为整数，则称为混合整数规划(MixedIP)；0-1整数规划要求决策变量只能取0或1值，则称为0-1规划(0-1Programming)。第二节分配问题（AssignmentProblem）问题的提出及数学模型分配问题的匈牙利解法两点说明分配问题的求解软件1.问题的提出及数学模型例1：设某工程有B1,B2,B3,B4四项任务，需由四个工人A1,A2,A3,A4去完成，由于任务性质和每个工人的技术水平不相同，他们完成各项任务所需的时间也不一样（见下

7、表）。问应当如何分配，即哪个人去完成哪项任务，才能使完成四项任务的总时间最少？任务人员B1B2B3B4A1215134A21041415A39141613A478119设该问题的解为：用矩阵形式表示为:解矩阵设有n项任务，需有n个人去完成，每个人只能完成一项任务，每项任务只能由一个人去完成，设第i人完成第j项任务需要的时间是aij,问如何分配才能使完成任务的总时间最少？设一般分配问题分配问题是一种特殊的运输问题，特殊在哪里？高度退化