哈尔滨工程大学：《运筹学基础》课程教学资源（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)