哈尔滨工程大学：《运筹学基础》课程教学资源（PPT课件讲稿）第四章 整数规划

第4章整数规划- 第四章整数规判 / nteger Programming整数规划 A/// nteger Programming全整数规划 Mixed Programming混合整数规划 2006/3

2006/3 --第4章 整数规划-- --2-- Integer Programming 整数规划 All Integer Programming 全整数规划 Mixed Programming 混合整数规划 第四章 整数规划

第4章整数规划- 41一般整数规划问题的特点及分枝定界法 引例 某厂拟用集装箱托运甲、乙两种货物,每箱的体 积、重量、可获利润及托运时所受的限制如下表所示, 问如何托运能使总收益最大? 货物体积(米3/箱)重量(吨/箱)利润(千元/箱) 甲 托运限制14米3 9吨 2006/3

2006/3 --第4章 整数规划-- --3-- 4.1 一般整数规划问题的特点及分枝定界法 一、引例 某厂拟用集装箱托运甲、乙两种货物，每箱的体 积、重量、可获利润及托运时所受的限制如下表所示， 问如何托运能使总收益最大？ 货物 体积(米3/箱) 重量(吨/箱) 利润(千元/箱) 甲 乙 2 2 3 3 1 2 14 米3 托运限制 9 吨

第4章整数规划- 建模: 解:设托运甲货物x箱,乙货物x2箱 Max z3 x,+2 X st.2x1+3x,≤14 2x1+X29 X1≥0,X2≥0,且为整数 2006/3

2006/3 --第4章 整数规划-- --4-- 建模： 解：设 托运甲货物x1箱，乙货物x2箱 Max z=3 x1 +2 x2 st . 2 x1+3 x214 2 x1 + x29 x10，x20，且为整数

第4章整数规划- 2x1+x2=9 4 (3.25,25) 2x1+3x2=14 米 6 XI 3x1+2x2=6 2006/3

2006/3 --第4章 整数规划-- --5-- 2 4 6 2 4 (3.25, 2.5) x1 x2 2x1+3x2=14 2x1+x2=9 3x1+2x2=6

第4章整数规划- 2x1+x2=9 4 25,3) (352) 2x1+3x2=14 米 6 XI 3x1+2x2=6 2006/3

2006/3 --第4章 整数规划-- --6-- 2 4 6 2 4 (3.5, 2) x1 x2 2x1+3x2=14 2x1+x2=9 3x1+2x2=6 (2.5, 3)

第4章整数规划- 2x1+x,=9 4 25,3) (3,2 2x1+3x2=14 4,1) 6 XI 3x1+2x2=6 2006/3

2006/3 --第4章 整数规划-- --7-- 2 4 6 2 4 (4, 1) x1 x2 2x1+3x2=14 2x1+x2=9 3x1+2x2=6 (2.5, 3) (3, 2)

第4章整数规划- 分枝定界法 z0=14.75 325,x2=2.5 1:z1=14.5 L2:z2=13.5 3.5,X2=2 2.5,x2=3 4 Z3=13 :z=14 =4 2006/3

2006/3 --第4章 整数规划-- --8-- 分枝定界法: L0：z0=14.75 x1=3.25，x2=2.5 L1：z1=14.5 L2：z2=13.5 L3：z3=13 L4：z4=14 x1=3.5，x2=2 x1=2.5，x2=3 x1=3，x2=2 x1=4，x2=1 −

第4章整数规划- LINDO软件及 EXCEL求解: LINDO程序软件:同求解LP模型时的输入及编辑修改过 程,在使用‘GOˆ命令求解之前,对整数变量给予说明 命令格式:GIN EXCEL求解 2006/3

2006/3 --第4章 整数规划-- --9-- LINDO软件及EXCEL求解： LINDO程序软件：同求解LP模型时的输入及编辑修改过 程，在使用‘ GO ’命令求解之前，对整数变量给予说明。 命令格式：GIN 。 EXCEL求解：

第4章整数规划- 420-1规划问题及模型 、0-1规划问题的概念 在整数规划问题中,若变量取值为0或者1,则为0-1 规划问题。 ·0-1变量通常用来表示逻辑性选择的决策。 2006/3

2006/3 --第4章 整数规划-- --10-- 4.2 0-1规划问题及模型 一、0-1规划问题的概念 • 在整数规划问题中，若变量取值为0或者1，则为0-1 规划问题。 • 0-1变量通常用来表示逻辑性选择的决策

第4章整数规划- 、0-1变量的应用 、表示选择性决策 例1:某油田在10个有油气构造处要选择若干个钻探 采油,设第个构造开采时需投资a元,投产后预计年收 益为c元,若该油田投资的总限额为b元,问:应选择哪 几个构造开采最为有利? -选择开采第j个构造 设X10 不选择开采第j个构造 10 maxz=∑cX 年总收益 10 a.x. s b 投资额限制 x=0或1(=12-10) 2006/3

2006/3 --第4章 整数规划-- --11-- 二、0-1变量的应用 例1：某油田在10个有油气构造处要选择若干个钻探 采油，设第j个构造开采时需投资aj元，投产后预计年收 益为cj元，若该油田投资的总限额为b元，问：应选择哪 几个构造开采最为有利？ 设 xj= 1 0 --- 选择开采第j个构造 ---不选择开采第j个构造 max z=Σcjxj j=1 10 ∑ajxj b xj ＝0或1 (j=1,2,---,10) j=1 10 -----年总收益 ----投资额限制 1、表示选择性决策