1、第八章 整数规划8.1 整数规划问题及其数学模型8.2 图解法8.3 整数规划的应用8.4 分支定界法8.5 指派问题与匈牙利算法一、整数规划问题的特征：变量取值范围是离散的，经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。二、整数规划问题的定义：n 规划中的变量（部分或全部）限制为整数时，称为整数规划 （ Integer Programming）。简称 IP。n 线性 规划中的变量（部分或全部）限制为整数时，称为 整数 线性 规划 。8.1 整数规划问题及其数学模型8.1 整数规划问题及其数学模型三、建模中常用的处理方法：1、资本预算问题：设有 n个投资方案， cj为第 j个投资
2、方案的收益。投资过程共分为 m个阶段，bi为第 i个阶段的投资总量， aij为第 i阶段第 j项投资方案所需要的资金。目标是在各阶段资金限制下使整个投资的总收益最大。2、指示变量：指示不同情况的出现例 .有 m个仓库，要决定动用哪些仓库，满足 n个顾客对货物的需要，并决定从各仓库分别向不同顾客运送多少货物？费用： fi:动用 i仓库的固定运营费（租金等）cij:从仓库 i到 j顾客运送单位货物运费约束条件： i)每个顾客的需要量 dj必须得到满足；ii)只能从动用的仓库运出货物。四、整数规划的数学模型纯整数规划 ：所有决策变量为非负整数；全整数规划 ：所有变量、系数和常数均为整数；混合整数规划
3、 ：只有一部分决策变量为非负整数，其余变量可为非负实数；0-1整数规划 ：所有决策变量只能取 0获 1两个整数。8.2 整数规划的图解法例 1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运 4件，问两种货物各托运多少件，可使获得利润最大。货物 每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制 1365 140 8.2 整数规划的图解法解： 设 x1 、 x2分别为甲、乙两种货物托运的件数，建立模型目标函数： Max z = 2x1 +3 x2 约束条件： s.t. 195 x1 +
4、273 x2 1365 4 x1 + 40 x2 140x1 4x1， x2 0 为整数。如果去掉最后一个约束，就是一个线性规划问题。8.2 整数规划的图解法由图解法得到线性规划的最优解为 x1=2.44, x2=3.26,目标函数值为 14.66。由图表可看出，整数规划的最优解为 x1=4, x2=2,目标函数值为 14。1 2 3 4123 2x1+3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =68.2 整数规划的图解法例 2：Max z = 3x1 + x2 + 3x3 s.t.-x1 + 2x2 + x3 44x2 -3x3 2x1 -3x2 + 2x3 3x1,x2,x3 0 为整数例 3：Max z = 3x1 + x2 + 3x3 s.t.-x1 + 2x2 + x3 44x2 -3x3 2x1 -3x2 + 2x3 3x3 1x1,x2,x3 0x1， x3 为整数 x3 为 0-1变量用 管理运筹学 软件求解得：x1 = 5 x2 = 2 x3 = 2 用 管理运筹学 软件求解得：x1 = 4 x2 = 1.25 x3 = 1
