整数规划问题.ppt

《整数规划问题.ppt》由会员分享，可在线阅读，更多相关《整数规划问题.ppt（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、整数规划问题现在学习的是第1页，共21页3.1 3.1 投资决策问题投资决策问题问问题题某市在“十五”计划期间有b亿元的资金可用于n个项目的投资。若对第i个项目投资，需资金 亿元，可获利税收入 亿元。试确定一个投资方案，使该方案下该市新增的利税收入最多。建立此问 题的数学模型。解：设该市获得的新增利税收入为z亿元，并令 1，若对第i个项目投资 =i=1,2,n 0，若不对第i个项目投资则上述问题的数学模型如下：现在学习的是第2页，共21页max z=s.t.b =0或1；i=1，2，n说说明明1.是本投资方案的总收益；是 本投资方案的总投入。2.这是个纯整数规划问题，也是一个0-1规划问题。由

2、于目标函数z是决策变量的线性函数，并且约束条件也是决策变量的线性不等式，所以这是个0-1整数线性规划问题。现在学习的是第3页，共21页3.2 3.2 背包问题背包问题问问题题 设有一个容积为b的背包，有n个体积 为 (i=1，2，n),使用价值分别为（i=1，2，n）的物品可以装入背包。问应选择哪几件物品装入背包，才能得到 最大的使用价值？试建立数学模型。解：1 将第i件物品装入背包 令 =0 不将第i件物品装入背包 (i=1,2,n)并设装入背包的总使用价值为z，则本背包 问题的数学模型为：现在学习的是第4页，共21页 max z=s.t.b =0或1；i=1，2，n说说明明1.为装入背包的

3、物品的总价值，希望其取 最大值。2.为装入背包的物品的总体积，它不能超 过背包的容量。3.本模型也是一个0-1整数线性模型。现在学习的是第5页，共21页3.3 3.3 合理下料问题合理下料问题问问题题假设要利用某类钢板下m种零件 ，的毛料。根据既省料又容易操作的原则，人们在一块钢板上，已经设计出n种不同的下料方案。设在第j种下料方案中，可下得第i种零件 的个数为 ，第i种零件的需要量为 ，i=1，2，m。问应如何下料，才能既满足需要，又使所用的钢板总数最少？现在学习的是第6页，共21页解：设采用第j种方案下料的钢板数为 ，所用钢 板的块数为y，则本问题的数学模型如下：min y=s.t.i=1

4、，2，m 0 I，j=1，2，n说说明明1.采用各种方案下料的钢板数 的总和，即为 所用的钢板数。2.完工后，第i种零件下料的数目不少于 。3.本模型是一个非0-1的整数规划模型。现在学习的是第7页，共21页3.4 3.4 生产组织与计划问题生产组织与计划问题问问题题某工厂用m台机床：，加工n种零件 ，。在一个生产周期内，已知第i台机床只能工作 个机时，i=1，2，m。该工厂必须完成加工零件 的数量为 个，j=1，2，n。机床 加工零件 一个所需的机时和成本分别为 （机时/个）和 （元/个）。问在这个生产周期，应如何安排各机床的生产任务，才能既完成生产任务，又使总的加工成本最小？解：设机床 在

5、一生产周期内加工零件 的个数为 ，i=1，2，m；j=1，2，n。又设总的加工 成本为y，则本问题的数学模型如下：现在学习的是第8页，共21页 min y=s.t.，i=1，2，m ，j=1，2，n 0，且 I，i=1，2，m；j=1，2，n 说说明明1.总加工成本应等于各机床 加工零件 的个数 乘以该机床加工零件 的单位成本 （元/个）的 总和。现在学习的是第9页，共21页2.因为按问题要求，机床 加工各零件的机时不能 超过该机床能工作的机时数 ，所以第一个约束 条件成立。3.因为按问题要求，各机床 加工零件 的数目不 能少于对 的需要量 ，所以第二个约束条件成 立。4.本模型是一个非0-1

6、的整数规划模型。现在学习的是第10页，共21页 3.5 3.5 工厂选址问题工厂选址问题问问题题设有n个需求点（如城市、仓库或商店等），有m个可供选择的建厂地址。每个地址至多可建一个工厂。在 i 地址建立工厂后的生产能力为 ，在 i 地址经营工厂，单位时间的固定成本为 （元），需求点 j需求量为 ，从厂址 i 到需求点 j 的单位运费为 （元/吨）。问应如何选择厂址和安排运输计划，才能得到经济上最少的方案？现在学习的是第11页，共21页解：设在单位时间内，从厂址 i 运到 需求点j的物资 数量为 （吨），并引入布尔变量 1，若在 i 地建厂 =0，若不在 i地建厂 又设单位时间的总花费为s（元

7、），则本问题的 数学模型为：现在学习的是第12页，共21页 min s=+s.t.，i=1，2，m ，j=1，2，n0，其中 =0 或 1，i=1，2，m j=1，2，n现在学习的是第13页，共21页说说明明1.是总运费，是总生产成本。2.是产地 i 运出的物资总量，是产地i 的生产总量。3.是所有产地运达需求点j的物资总量，4.是j地的需求量。5.本模型中的变量既有0-1变量，又有非0-1变 量，所以是一个混合型的整数规划模型。现在学习的是第14页，共21页3.6 3.6 设备购置和安装问题设备购置和安装问题问问题题某工厂需要m种设备 ，设 的单价为 元。该厂已有第i种设备 台，i=1，2，

8、m。今有资金 M 元，可用于购置这些设备。另知该厂有n处可安装这些设备，处最多能安装 台；将一台设备 安装在 处，经济效益为 。应如何购置和安装这些设备，才能使总的经济效益最高？现在学习的是第15页，共21页解：用 表示设备 安装在 处的台数，表示购置 的台数，z表示总的经济效益，则本问题的数学 模型为：max z=s.t.+，i=1，2，m j=1，2，nM ,0,且 ，I，i=1，2，mj=1，2，n现在学习的是第16页，共21页说说明明1.是第i种设备安装在第j处产生的效益；全 体各已安装的设备产生的效益的总和即为总的 经济效益。2.安装设备 到各处的总数目不会超过设备 的 拥有数。即新

9、购置的数目 与原有数目 之和。3.安装在j处的各种设备的总数目 不能超过j处 可安装的数目 。4.购置新设备的总花费 不能超过可用的资金 总量M。现在学习的是第17页，共21页 3.7 3.7 旅行商问题旅行商问题问问题题一个商人拟到n个城市去推销商品。已知每两个城市 和 之间的距离为 ，任何选择一条道路，使得商人每个城市走一遍回到起点，且所走的路径最短。本问题称为旅行商问题（记为TSP），也叫货郎担问题或邮路问题。是一种特殊的Hamilton（哈密尔顿回路问题。现在学习的是第18页，共21页解：令 1，商人选择的路线包含从 到 的边=0，否则 n-2,S 1,2,n0,1;i,j=1,2,n;i j现在学习的是第19页，共21页说说明明1.为在路径上出现的各条边的长度总 和，亦即该路径的长度。2.=1表示从 向外走一次且只走一次。3.=1表示从其他点走到 一次且仅一次。4.若路径不满足第三个约束条件，则该路径 中必然含有回路。现在学习的是第20页，共21页现在学习的是第21页，共21页