（第五章 整数规划.ppt

第五章 整数规划 §1　整数规划的数学模型及其特征 §2　整数规划的应用 §3 * 整数规划的分枝定界法 §1　整数规划的数学模型 一、整数规划问题的提出 1.整数规划的含义 所谓整数规划，就是决策变量有整数要求的数学规划问题。 2.整数规划的分类 线性整数规划：又叫整数线性规划（ILP） 非线性整数规划 整数线性规划又分为两类： （1）纯整数线性规划：所有决策变量均取整数。 （2）混合整数线性规划：只有部分决策变量取整数值。 二、整数规划的一般模型 1.引例——整数规划的图解法 §1　整数规划的数学模型 例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 §1　整数规划的数学模型 解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： s.t. 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1，x2 ≥ 0 为整数。 如果去掉最后一个约束，就是一个线性规划问题。利用图解法，得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。 §1　整数规划的数学模型 §1　整数规划的数学模型 结论： （1）整数线性规划问题的求解不可以由相应的线性规划的最优解进行四舍五入法或去尾法或进一法取整而得出。 （2）整数线性规划问题的求解有自己特有的方法。 （3）整数线性规划具有如下性质： 任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。 §1　整数规划的数学模型 2.整数线性规划的一般模型 目标函数： 约束条件： §2　整数规划的应用 一、投资场所的选择 例2、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大? §2　整数规划的应用 解：设：0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 且xj 为0--1变量，i = 1,2,3,……,10 §2　整数规划的应用 二、固定成本问题 例3．高压容器公司制造小、中、