管理运筹学第四章整数规划与指派问题PPT课件.ppt

管理运筹学第四章整数规划与指派问题•线性规划的决策变量取值可以是任意非负实数,但许多实际问题中,只有当决策变量的取值为整数时才有意义。例如,产品的件数、机器的台数、装货的车数、完成工作的人数等,分数或小数解显然是不合理的。•要求全部或部分决策变量的取值为整数的线性规划问题,称为整数线性规划,简称整数规划(IntegerProgramming)。第一节整数线性规划问题的数学模型第二节整数规划的求解方法*第三节指派问题及匈牙利解法本章内容的安排第一节整数线性规划问题的数学模型引例逻辑变量在整数规划建模中的作用整数规划问题的特征与性质整数规划模型的分类例1(装载问题)有一辆卡车的最大载重量为b吨,现有n种货物可供装载。设第j种货物每件重aj吨,每件的装载费用为cj元(j=1,…n)。问应该采用怎样的装载方案才能使卡车一次装载货物的收入最大?解:设xj为卡车装载第j种货物的件数(j=1,2,…,,n),z表示卡车一次装载的收入,则该问题的数学模型为maxz=c1x1+c2x2+…++a2x2+…+anxnbxj0且为整数(j=1,2,…,,n).(选址问题—相互排斥的计划)某公司准备投资100万元在甲、乙两座城市修建健身中心,经过多方考察,最后选定A1,A2,A3,A4和A5五个位置,并且决定在甲城市的A1、A2、A3三个位置中最多投建两个;在乙城市的A4、A5两个位置中最少投建一个。如果已知各点的投资金额和年利润如下表。问:健身中心投建在哪些位置才会使总的年利润最大?待定地址A1A2A3A4A5投资总额投资金额(万元)2030254045100年利润(万元)1025202530解:设则该问题的数学模型为例3工厂选址问题:某商品有n个销地,各销地的需求量为bj吨/天;现拟在m个地点中选址建生产厂,一个地点最多只能建一个工厂;若选i地建厂,生产能力为ai吨/天,固定费用为di元/天;已知i地至第j销地的单位运费为cij元/吨。问如何选址和安排调运,才能使总费用最小?设:yi=1,表示选择第i地建厂,yi=0,表示不选择第i地建厂;从厂址i至销地j运量为xij,总费用为z。该问题的数学模型为例4某公司制造小、中、大3种尺寸的金属容器,所用的资源为金属板、劳动力和机时。制造一只容器所需的各种资源数量如下表所示,不考虑固定费用,每售出一只小、中、大号容器所得的利润分别为4元、5元、6元,可使用的金属板有500张,劳动力有300个,机时有100小时,如果生产某种容器,不管生产数量多少,都要支付一笔固定费用,小、中、大号容器的固定费用分别为100元、150元、200元,现要制订一生产计划,使获得的利润最大。资源小号容器中号容器大号容器资源拥有量金属板(张)248500劳动力(个)234300机时(小时)123100利润456解:设x1,x2,x3分别表示小、中、大号容器的生产数量,M为很大的正数,z表示总利润引入逻辑变量若xj=0时,yj=0,若xj>0时,yj=1。