下载文档原格式
〈运筹学〉补充例题例题 1.1 某工厂可以生产产品A和产品B两种产品。
生产单位产品A和B所需要的机时、人工工时的数量以及可利用资源总量由下表给出。
这两种产品在市场上是畅销产品。
该工厂经理要制订季度的生产计划，其目标是使工厂的销售额最大。
产品A 产品B 资源总量机器（时） 6 8 120人工（时） 10 5 100产品售价（元） 800 300MAX 800X1 +300X2ST6X1 +8X2 <= 12010X1 +5X2 <= 100X1, X2 >=0例题 1.2该工厂根据产品A和产品B的销售和竞争对手的策略，调整了两种产品的售价。
产品A和B的价格调整为600元和400元。
假设其它条件不变，请你帮助该工厂经理制订季度的生产计划，其目标仍然是使工厂的销售额最大。
X 600X1 +400X2ST6X1 +8X2 <= 12010X1 +5X2 <= 100X1, X2 >=0例题 1.3由于某些原因，该工厂面临产品原料供应的问题。
因此，工厂要全面考虑各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价等因素。
有关信息在下表中给出。
产品A 产品B 资源总量机器（时） 6 8 120人工（时） 10 5 100原材料(公斤) 11 8 130产品售价（元） 600 400MAX 600X1 +400X2ST6X1 +8X2 <= 12010X1 +5X2 <= 10011X1 +8X2 <= 130X1, X2 >=0例题 1.４随着企业改革的不断深化，该企业的经理的管理思想产生了变化，由原来的追求销售额变为注重销售利润，因此，要考虑资源的成本。
工厂的各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价和各种资源的价格等因素。
有关信息在下表中给出。
产品A 产品B 资源总量资源价格（元／单位）机器（时） 6 8 120 ５人工（时） 10 5 100 20原材料(公斤) 11 8 130 1产品售价（元） 600 400设： J为所用机器资源数量（小时）；R为所用人力资源数量（小时）；L为所用原材料数量（公斤）MAX 600X1 +400X2 -CST6X1 +8X2 - J = 010X1 +5X2 - R = 011X1 +8X2 - L = 0J <= 120R <= 100L <= 1305J +20R +1L - C = 0x1, x2, J,R,L>=0例题 1.5 学习了管理课程后，该企业的经理明白了产品的成本包括变动成本和固定成本。
运筹学难点辅导材料 整数规划补例
1、 对( IP) 整数规划问题12
12121212max 14951631..0,0,z x x x x x x s t x x x x =++≤⎧⎪
-+≤⎪⎨
≥≥⎪⎪⎩为整数, 问用先解相应的线性规划然后凑
整的办法能否求到最优整数解? 再用分支定界法求解。
解 先不考虑整数约束, 得到线性规划问题( 一般称为松弛问题LP)
12
12121
2max 14951..6310,0
z x x x x s t x x x x =++≤⎧⎪
-+≤⎨⎪≥≥⎩用图解法求出最优解12310
,23x x ==且296z =。
如用”舍入取整法”凑整可得到四个点, 即( 1, 3) 、
( 2, 3) 、 ( 1, 4) 、 ( 2, 4) 。
代入约束条件发现她们都不是可行解。
可将可行域内的所有整数点一一列举( 完全枚举法) , 本例中( 2, 2) 、 ( 3, 1) 点为最大值4z =。
令()
0310,23T
X
⎛⎫= ⎪⎝⎭
及最优值()0
296z =。
可行域记为D, 显然()0X 不是整数解。
定界: 取()0296z z ==
, 再用视察法找一个整数可行解()0,0T
X '=及0z '=, 取0z z '==, 即*2906
z ≤≤ 分支: ( 关键点, 在B 的最优解中任选一个不符合整数条件的变量j x , 其值为
j b , 构造两个约束条件1,j j j j x b x b ⎡⎤⎡⎤≥+≤⎣⎦⎣⎦, 这里用了取整函数呵! ) 任取最
优解中一个不为整数的变量值, 例如132x =
, 根据312⎡⎤
=⎢⎥⎣⎦
, 构造两个约束条件,
形成下面两个子问题( IP1) 12121211212max 14951631..10,0,z x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≤⎨⎪≥≥⎪⎪⎩为整数和( IP2) 12
121221212max 14951631..20,0,z x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≥⎨⎪≥≥⎪⎪⎩为整数 解( IP1) 和( IP2) , 得最优解分别为()
()11
7101,,33T
X z ⎛⎫==
⎪⎝⎭
和()
()22
23412,,99T
X
z ⎛⎫== ⎪⎝⎭
, 这两个都不是符合整数条件的可行解。
修改上下界: 根据个分支的最优解, 可取新的上界()(){}
1241
min ,9
z z z =
=, *4109
z ≤≤
再分支: 由于()()12z z <, 故先对( IP2) 进行分支, 取2239x =
, 根据2329⎡⎤
=⎢⎥⎣⎦
, 构造两个约束条件, 形成下面两个子问题( IP3) 12
121
2121212max 14951631
2
..2
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≥⎪⎨
≤⎪⎪≥≥⎪⎪⎩为整数和( IP4) 12
121
2121212max 14951
631
2..3
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≥⎪⎨
≥⎪⎪≥≥⎪⎪⎩为整数。
解相应的松弛问题( IP3) 和( IP4) , 得( IP4) 无可行解, ( IP3) 的最优解为
(
)
()33
3361,2,1414T
X z ⎛⎫== ⎪⎝⎭。
在考虑( IP1) , 由( IP1) 的最优解, 取273x =
, 根据723⎡⎤
=⎢⎥⎣⎦
, 构造两个约束条件, 形成下面两个子问题( IP5) 12
121
2121212max 14951
631
1..2
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≤⎪⎨
≤⎪⎪≥≥⎪⎪⎩为整数和( IP6) 12
121
2121212max 14951
631
1..3
0,0,z x x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≤⎪⎨
≥⎪⎪≥≥⎪⎪⎩为整数, 得( IP6) 无可行解, ( IP5) 的最优解为()()()551,2,3T
X z ==。
在修改上下界: 根据上述两个最优解的情况, 有*61
314
z ≤≤ 再分支: 由( IP3) 的最优解()
333,214T
X
⎛⎫
= ⎪⎝⎭
, 取13314x =, 根据33214⎡⎤=⎢⎥⎣⎦, 构造
两个约束条件, 形成下面两个子问题( IP7) 12
1212121
1212max 149516312
..220,0,z x x x x x x x s t x x x x x x =++≤⎧⎪
-+≤⎪⎪≥⎪
≤⎨⎪≤⎪⎪≥≥⎪
⎩为整数
和( IP8)
121212121
1212max 149516312
..230,0,z x x x x x x x s t x x x x x x =++≤⎧⎪
-+≤⎪⎪≥⎪
≤⎨⎪≥⎪⎪≥≥⎪
⎩为整数
, 得( IP7) 的最优解为()()()772,2,4T
X z ==, ( IP8) 的最优解为
()()()883,1,4T
X z ==。
重新定界: 由于的最优解为()()78
,X X 为整数解, 且()()784z z ==, 故
()**3,1,4T
X z ==
2、 对整数规划问题12
12121212max 32231429..0,0,z x x x x x x s t x x x x =++≤⎧⎪
+≤⎪⎨
≥≥⎪⎪⎩为整数, 问用先解相应的线性规划然后凑整的办
法能否求到最优整数解?
解 用单纯形法解对应的LP 问题, 求到最优解1213559
,,max 424
x x z =
==
当凑为()()12,3,2T
T
x x =时, 为可行解, 13z =; 当凑为()()12,3,3T
T
x x =时, 为非可行解;
当凑为()()12,4,2T
T
x x =时, 为非可行解; 当凑为()()12,4,3T
T
x x =时, 为非可行解;
下面用分支定界法来解整数规划问题。
令594
z =, 显然()()12,0,0T T
x x =为可行解, 从而*5904
z ≤≤。
将原问题分解为下面两个子问题( 用222,3x x ≤≥分支, 复杂些, 不妨去试试! )
( IP1) 121212112max 32231429..30,0z x x x x x x s t x x x =++≤⎧⎪+≤⎪⎨≤⎪⎪≥≥⎩和( IP2) 12
1212112max 322314
29..40,0z x x x x x x s t x x x =++≤⎧⎪+≤⎪⎨
≥⎪⎪≥≥⎩
( IP1) 的最优解为
()
12343,3,,max 83T
T
x x z ⎛⎫
== ⎪⎝⎭
和( IP2) 的为()
()12,4,1,max 14T
T
x x z ==
因为4314,3z z ==, 因此*43
143
z ≤≤, 且*z 为整数, 则*1214,4,1z x x ===为最优解。
3、 用割平面法求解12
1212121212max 3323
5410..25,0,,z x x x x x x s t x x x x x x =--≤⎧⎪
+≥⎪⎨
+≤⎪⎪≥⎩为整数
解 引入松弛变量345,,x x x 和人工变量6x 及一个充分大的数0M >, 先解一个大
M 问题:
126
1231246
1251234567max 3323
5410
..25,,,,,,0z x x Mx x x x x x x x s t x x x x x x x x x x =---+=⎧⎪+-+=⎪⎨
++=⎪⎪≥⎩ 作初始单纯形表, 并进行迭代运算。
