Mathematical modeling
6
(1) 原线性规划有最优解，当自变量限制为 整数后，其整数规划解出现下述情况： a原线性规划最优解全是整数，则整数规 划最优解与线性规划最优解一致。 b原线性规划最优解不全是整数，则整数 规划最优解小于原线性规划最优解（max） 或整数规划最优解大于原线性规划最优解 （min）。
Mathematical modeling
23
1 分派第i工人完成第j工作 解：设 xij 0 其他 i, j 1, 2, ,5
min z 5 x11 6 x12 8 x13 4 x14 5 x15 3 x21 4 x22 6 x23 6 x24 1x25 5 x31 5 x32 7 x33 9 x34 8 x35 s.t. 6 x41 7 x42 5 x43 7 x44 6 x45 7 x51 4 x52 6 x53 2 x54 8 x55 5 xij 1 j 1, 2, , 5 i 1 5 xij 1 i 1, 2, , 5 j 1 x 0或1 i, j 1, 2, , 5 ij
15
Mathematical modeling
· 0-1整数规划
1.什么是0-1整数规划？ 0-1 整数规划是一种特殊形式的整数规划， 这时的决策变量xi 只取两个值0或1，一般的解 法为隐枚举法。
2.什么时候采用0-1整数规划法？ 正如计算机只懂得0,1两个数，1代表是，0代 表否。同样的，在0-1整数规划中的0和1并不是 真真意义上的数，而是一个衡量事件是否发生 的标准。一般来说，我们在从多个事物中选出 其中一部分，在一定的条件下求解最优情况时 可以采用0-1整数规划法。 Mathematical modeling
Mathematical modeling
24
Mathematical modeling
Mathematical modeling
整数规划是什么?
规划中的变量（部分或全部）限制为整数时，称为整数规 划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。目前所流行的求解整数规划的方法，往往只适 用于整数线性规划。目前还没有一种方法能有效地求解一 切整数规划。
Mathematical modeling
Mathematical modeling
8
解: 设每周生产Ⅰ、Ⅱ号杯各 x1 , x2 百箱,则有如下
数学模型
max z 500 x1 450 x2 6 x1 5 x2 60 10 x 20 x 150 1 2 x1 8 x1 , x2 0且为整数
Mathematical modeling
11
· 分支定界法
对有约束条件的最优化问题（其可行解为有限数） 的所有可行解空间恰当地进行系 统搜索，这就是分枝与定界内容。通常，把全部可 行解空间反复地分割为越来越小的子 集，称为分枝；并且对每个子集内的解集计算一个 目标下界（对于最小值问题），这称 为定界。在每次分枝后，凡是界限超出已知可行解 集目标值的那些子集不再进一步分枝，这样，许多 子集可不予考虑，这称剪枝。这就是分枝定界法的 主要思路。
Mathematical modeling
21
解：对于0-1 规划问题，由于每个变量只取0，1两个值，一 般会用穷举法来解，即将所有的0，1 组合找出，使目标函数 达到极值要求就可求得最优解。
Mathematical modeling
22
例7(指派问题) 有5个工人，要分派他们分别完 成5项工作，每人做各项工作所消耗的时间如下 表，问应如何安排工作，可使总的消耗时间最 小？
16
例5一个旅行者要到某地作两周的带包旅行,装背包时,他发 现除了已装的必需物件外,他还能再装5公斤重的东西.他打 算从下列4种东西中选取,使增加的重量不超过5公斤又能使 使用价值最大.这4种东西的重量和使用价值(这里用打分数 的办法表示价值)如下表所示,问旅行者应该选取哪些物件为 好？
Mathematical modeling
Mathematical modeling
12
例4 用分支定界法求以下整数规划
max z 5 x1 8 x2 x1 x2 6 5 x1 9 x2 45 x , x 0且为整数 x 2
Mathematical modeling
13
x2
x1
Mathematical modeling
Mathematical modeling货物的装运和获利情况如下表所示，问：甲乙两 货物各托运多少箱，可使获得利润最大？
Mathematical modeling
5
解：设 x1 , x2 为甲乙两货物各托运箱数
max z 20 x1 10 x2 5 x1 4 x2 24 2 x1 5 x2 13 x , x 0且为整数 1 2
Mathematical modeling
20
例6 求解下列0-1规划问题
max Z 3 x1 2 x2 5 x3 x1 2 x2 x3 2 (1) x1 4 x2 x3 4 (2) s.t. x1 x2 3 (3) 4 x2 x3 6 (4) x1 , x2 , x3 0或1
返回
Mathematical modeling
9
· 完全枚举法 例3：设整数规划问题如下
max z x1 x2 14 x1 9 x2 51 6 x1 3 x2 1 x , x 0且为整数 1 2
Mathematical modeling
10
现求整数解（最优 解）：如用“舍入取整法” 可得到4个点即(1，3) (2，3)(1，4)(2，4)。显 然，它们都不可能是整数 规划的最优解。 故按整数规划约束条 件，其可行解肯定在线性 规划问题的可行域内且为 整数点。故整数规划问题 的可行解集是一个有限 集，如图所示。 求得（2，2）（3，1）点为最大值，。 在求解整数规划问题时，可将集合内的整数点一一找 出，其最大目标函数的值为最优解，此法为完全枚举法。 返回
19
由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) 但此法 太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加 入一定的条件，就能较快的求得最优解： 找到x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论， 如下表。
2
整数规划的分类
变量全限制为整数时，称纯（完全）整数规划。 变量部分限制为整数的，称混合整数规划。 变量只能取0或1时，称之为0-1整数规划。
Mathematical modeling
3
· 整数规划模型的建立 · 整数规划模型的求解
· 完全枚举法 · 分支定界法 · 割平面法
· 0-1数规划模整型
14
开始 V0 X1=2.25,X2=3.75;Z0=41.25 X2≤3 X2≥4 V1 X1=3,X2=3,Z2=39 V2 X1=1.8,X2=4,Z1=41 X1≥2 X1≤1 V3 X1=1,X2=4.44, Z4=40.56 V4 不可行
X2≤4
V5 X1=1,X2=4,Z5=37
X2≥5 V6 X1=0,X2=5,Z6=40
17
解：建立模型为
max Z=6x1 7 x2 3 x3 9 x4 2 x1 3x2 x3 4 x4 5 s.t. xi 0,1 i 1, 2,3, 4
Mathematical modeling
18
Mathematical modeling
Mathematical modeling
7
例2 今有一台机器将一周生产的两种型号的冷饮杯 存储在150立方米的储藏室 里,并同时进行出售.已 知这台机器能在6小时内生产一百箱Ⅰ号杯,5小时内 生产一百箱Ⅱ号杯,生产以百箱为单位计算,预计每 周生产60小时.如果Ⅰ号杯每百箱占体积10立方米, 每百箱可获利润500元,每周售出数量不会超过800 箱;Ⅱ号杯每百箱占体积20立方米, 每百箱可获利润 450元,每周售出数量不受限制.为保证总收益为最大 ,每周应安排生产Ⅰ、Ⅱ号杯各多少百箱？