运筹学 CH4整数规划.ppt

《运筹学 CH4整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter4整数规划(IntegerProgramming)整数规划问题整数规划的数学模型整数规划的Excel解法应用举例本章主要内容：教学要求【教学目的与要求】了解一般整数规划问题基本概念；熟悉整数规划的数学模型；了解MicrosoftExcel求解整数规划问题的方法。【教学重难点】整数规划问题概念及模型结构整数规划问题整数规划（简称：IP）要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为

2、整数线性规划。整数线性规划数学模型的一般形式：整数规划问题整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。一、纯整数规划产品资源甲乙现有量A219B5735单台利润65例4.1：某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台产品的获利能力如下表所示：问如何安排甲、乙两产品的产量，使利润为最大。解：设x1为甲产品的台数，x2为乙产品的台数。ma

3、xZ=6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数整数规划问题二、0-1规划登山队员可携带最大重量为25公斤。问都带哪些物品的重要性最大。解：对于每一种物品无非有两种状态，带或者不带，不妨设序号1234567物品食品氧气冰镐绳索帐篷相机设备重量55261224重要性系数2015181484100-1规划的模型：整数规划问题例4.2第一节整数规划问题三、混合整数规划例4.3：某产品有n个区域市场，各区域市场的需求量为bj吨/月；现拟在m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选i地建厂

4、，生产能力为ai吨/月，其运营固定费用为Fi元/月；已知址i至j区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？解：选址建厂与否是个0-1型决策变量，假设yi=1，选择第i址建厂，yi=0，不选择第i址建厂；计划从i址至区域市场j的运输运量xij为实数型决策变量。整数规划的特点及应用整数规划问题解的特征：整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不

5、会优于后者最优解的目标函数值。整数规划的Excel解法和线性规划相同，仅在“规划求解”时，在约束条件处，多添加一项约束：可变单元格“int”“整数”（纯整数规划）或可变单元格“bin”“二进制”（0-1规划）