文档介绍：Chapter4整数规划 (IntegerProgramming)整数规划的特点及应用分配问题与匈牙利法分支定界法割平面法本章主要内容:这样的问题称为整数线性规划(integerlinearprogramming),,但对于某些问题,常要求解必须是整数(称为整数解)。例如,所求解是机器的台数、完成工作的人数或装货的车数等。整数规划的特点及应用整数规划的特点及应用整数规划(简称:IP) 要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为整数规划的松弛问题。若松弛问题是一个线性规划,则称整数规划为整数线性规划。整数规划的特点及应用整数线性规划的一般形式:整数规划的特点及应用整数线性规划问题的种类:纯整数线性规划:指全部决策变量都必须取整数值的整数线性规划。整数规划的特点及应用整数线性规划问题的种类:0-1型整数线性规划:决策变量只能取值0或1的整数线性规划。整数规划的特点及应用整数线性规划问题的种类:混合整数线性规划:决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划。。由于该种物资供不应求,故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij,见下表:B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量350400300150工厂A3或A4开工后,每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4,才能使今后每年的总费用最少。整数规划的特点及应用解:这是一个物资运输问题,特点是事先不能确定应该建A3还是A4中哪一个,因而不知道新厂投产后的实际生产物资。再设xij为由Ai运往Bj的物资数量,单位为千吨;z表示总费用,单位万元。则该规划问题的数学模型可以表示为:为此,引入0-1变量:整数规划的特点及应用混合整数规划问题