文档介绍：第八章整数规划
§1 整数规划的图解法
§2整数规划的计算机求解
§3整数规划的应用
§4整数规划的分枝定界法
§1 整数规划的图解法
例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产,已知生产仪器设备
需要A、B两种材
料的消耗以及资
源的限制,如右
表。
问题:工厂应分
别生产多少件甲、乙种仪器设备才
能使工厂获利最多?
解、
目标函数: Max z = x1 + x2
约束条件: .
3 x1 + 2 x2 ≤ 10
2 x2 ≤ 5
x1,x2 ≥ 0 为整数
不考虑整数约束得到最优解:
x1 =, x2 = ;z =
考虑整数约束得到最优解:
x1 = 2, x2 = 2; z = 4
整数规划的最优目标值小于相应
线性规划的最优目标值(相当于附加一个约束)
§2整数规划的计算机求解
例2:
Max z = 15x1 + 10x2 + 7x3
.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0 为整数
例2:
Max z = 15x1 + 10x2 + 7x3
.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0
x3 为整数 x1 为0-1变量
用《管理运筹学》软件求解得:
x1 = 0 x2 = 3 x3 = 0
z = 30
用《管理运筹学》软件求解得:
x1 = 1 x2 = x3 = 0
z = 30
§3整数规划的应用(1)
一、投资场所的选择
例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有10个位置 Aj (j=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定:
在东区由A1 , A2 ,A3 三个点至多选择两个;
在西区由A4 , A5 两个点中至少选一个;
在南区由A6 , A7 两个点中至少选一个;
在北区由A8 , A9 , A10 三个点中至少选两个。
Aj 各点的设备投资及每
年可获利润由于地点不同都是
不一样的,预测情况见右表所
示(单位:万元)。但投资总额不能超过720万元,问应选择哪几个销售点,可使年利润为最大?
解:设:0--1变量 xi = 1 (Ai 点被选用)或 0 (Ai 点没被选用)。
这样我们可建立如下的数学模型:
Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
. 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
二、固定成本问题
、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机
器设备,制造一个容器所需的各种资源的数量如右
表所示。不考虑固定费用,每种容器售出一只所得
的利润分别为 4万元、5万元、6万元,可使用的金
属板有500吨,劳动力有300人月,机器有100台月,
此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是l00万元,中号为 150
万元,大号为200万元。现在要制定一个生产计划,使获得的利润为最大。
解:这是一个整数规划的问题。
设x1,x2, x3 分别为小号容器、中号容器和大号容器的生产数量。
各种容器的固定费用只有在生产该种容器时才投入,为了说明固定费用的这种性质,设
yi = 1(当生产第 i种容器, 即 xi > 0 时) 或0(当不生产第 i种容器即 xi = 0 时)
引入约束 xi ≤ M yi ,i =1,2,3,M充分大,以保证当 yi = 0 时,xi = 0 。
这样我们可建立如下的数学模型:
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3
. 2x1 + 4x2 + 8x3 ≤ 500
2x1 + 3x2 + 4x3 ≤ 300
x1 + 2x2 + 3x3 ≤ 100
xi ≤ M yi ,i =1,2,3,M充分大
xj ≥ 0 yj 为0--1变量,i = 1,2,3
§3整数规划的应用(2)
,要分别指派他们