线性规划问题总结

线性规划
如何建立线性规划的数学模型; 线性规划的标准形有哪些要求?如何把一般的线性规划化为标 准形式? 如何用图解法求解两个变量的线性规划问题?由图解法总结出 线性规划问题的解有哪些性质? 如何用单纯形方法求解线性规划问题? 如何确定初始可行基或如何求初始基本可行解?(两阶段方法) 如何写出一个线性规划问题的对偶问题?如果已知原问题的最 优解如何求解对偶问题的最优解? (对偶的性质, 互补松紧条件) 对偶单纯形方法适合解决什么样的问题?如何求解? 对于已经求解的一个线性规划问题如果改变价值向量和右端向 量原最优解/基是否仍是最优解/基?如果不是,如何进一步求 解?

1、建立线性规划的数学模型:
特点: (1)每个行动方案可用一组变量(x1,…,xn)的值表示,这些 变量一般取非负值; (2)变量的变化要受某些限制,这些限制条件用一些线性等式 或不等式表示; (3)有一个需要优化的目标,它也是变量的线性函数。 2、线性规划的标准形有哪些限制?如何把一般的线性规划化为

标准形式?
目标求极小;约束为等式;变量为非负。
min z ? CT X ? AX ? b ? ?X ? 0

例:把下列线性规划化为标准形式:

max

z ? 2 x1 ? 3 x2

? x1 ? 2 x2 ? 8 ? ? ? x1 ? x2 ? 1 ? ?2 ? x1 ? x ? 0, x ?? 0 ? 1 2
解:令 x1 ? ? x3 , x2 ? x4 ? x5 , 标准型为:

min

z , ? ?{?2 x3 ? 3( x4 ? x5 )}

? ? x3 ? 2( x4 ? x5 ) ? x6 ? 8 ? ? ? x 3 ? ( x4 ? x 5 ) ? x 7 ? 1 ? +x8 ? 2 ? ? x3 ? x ? 0, i ? 3, 4, 5, 6, 7, 8 ? i

3、如何用图解法求解两个变量的线性规划问题?由图解法总结 出线性规划问题的解有哪些性质?
(唯一最优解、无穷多最优解、无界解、无解) 线性规划解的性质: (基、基本解、基本可行解、凸集、顶点) 定理 1 定理 2 点。 定理 3 线性规划如果有可行解, 则一定有基可行解; 如果有最优解, 则一定有基可行解是最优解。 4、如何用单纯形方法求解线性规划问题?(单纯形表) 单纯形法的基本法则 法则 1 最优性判定法则(检验数全部小于等于零时最优) 法则 2 换入变量确定法则(谁最正谁进基) 法则 3 换出变量确定法则(最小比值原则) 法则 4 换基迭代运算法则 线性规划的可行域是凸集。

X 是线性规划基本可行解的充分必要条件是 X 是可行域的顶

min

z ? ?2 x1 ? 5 x2 ?8 ? x1 ? 2 x2 ? x3 ? ? x4 ? 20 ? 5 x1 ? 2 x2 ? 4 x2 ? x5 ? 12 ? ?x , x , x , x , x ? 0 ? 1 2 3 4 5

x1

x2

x3

x4

x5

RHS

z x3 x4 x5 z x3 x4 x2 z x1 x4 x2

2 1 5 0 2 [1] 5 0 0 1 0 0

5 2 2 [4] 0 0 0 1 0 0 0 1

0 1 0 0 0 1 0 0 -2 1 -5 0

0 0 1 0 0 0 1 0 0 0 1 0

0 0 0 1 -5/4 -1/2 -1/2 1/4 -1/4 -1/2 2 1/4

0 8 20 12 -15 2 14 3 -19 2 4 3

最优解 X*=(2,3,0,4,0)T,z*=-2×2-5×3=-19。 5、如何确定初始可行基或如何求初始基本可行解?(两阶段方

法)
例求下列 LP 问题的最优解

min

z ? 3 x1 ? x2 ? x3 ? x1 ? 2 x2 ? x3 ? 11 ? ? ?4 x1 ? x2 ? 2 x3 ? 3 ? ? x3 ? 1 ? ?2 x1 ?x , x , x ? 0 ? 1 2 3

用两阶段法来求解

它的第一阶段是先解辅助问题:

min

g ? x6 ? x7 ? 11 ? x1 ? 2 x2 ? x3 ? x4 ? ? x5 ? x6 ?3 ? ?4 x1 ? x2 ? 2 x3 ? ? x3 ? x7 ? 1 ? ?2 x1 ? x ,? , x ? 0 ? 1 7

x1 g x4 x6 x7 g x4 x6 x7 g x4 x6 x3 g x4 x2 x3 0 1 -4 -2 -6 1 -4 -2 0 3 0 -2 0 3 0 -2

x2 0 -2 1 0 1 -2 1 0 1 -2 [1] 0 0 0 1 0

x3 0 1 2 1 3 1 2 [1] 0 0 0 1 0 0 0 1

x4 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0

x5 0 0 -1 0 -1 0 -1 0 -1 0 -1 0 0 -2 -1 0

x6 -1 0 1 0 0 0 1 0 0 0 1 0 -1 2 1 0

x7 -1 0 0 1 0 0 0 1 -3 -1 -2 1 -1 -5 -2 1

RHS 0 11 3 1 4 11 3 1 1 10 1 1 0 12 1 1

第二阶段:

x1 z x4 x2 x3 z x4 x2 x3 -3 3 0 -2 -1 3 0 -2

x2 1 0 1 0 0 0 1 0

x3 1 0 0 1 0 0 0 1

x4 0 1 0 0 0 1 0 0

x5 0 -2 -1 0 1 -2 -1 0

RHS 0 12 1 1 -2 12 1 1

原问题无界。 6、如何写出原问题的对偶问题?如果已知原问题的最优解,如

何求解对偶问题的最优解?

min cT x s .t . aiT x ? bi aiT x ? bi xj ? 0 x j ?? 0 i ? 1,? , p i ? p ? 1,? , m j ? 1,? , q j ? q ? 1,? , n

max bT w s .t . wi ?? 0 wi ? 0 AT w ? c j j AT w ? c j j

例写出下面线性规划问题的对偶问题

min z ? 2 x1 ? 3 x2 ? 5 x3 ? x4 ? x1 ? x2 ? 3 x3 ? x4 ? 5 ? ? 2 x 3 ? 4 x4 ? 4 ? 2 x1 ? x 2 ? x 3 ? x4 ? 6 ? ? x , x , ? 0 , x ?? 0 4 ? 1 2 x3

解:原问题的对偶问题为:

max

y ? 5 w1 ? 4 w2 ? 6 w 3

?2 ? w1 ? 2 w2 ? w ? w3 ? 3 1 ? ? ? ?3 w1 ? 2 w2 ? w3 ? ?5 ? w ? 4w ? w ? 1 1 2 3 ? ? w1 , w2 ? 0, w3 ?? 0 ? 7、对偶单纯形方法适合解决什么样的问题?如何求解?
例:

min

z ? 15 x1 ? 24 x2 ? 5 x3

6 x2 ? x3 ? x4 ?2 ? ? ? x5 ? 1 ? 5x1 ? 2 x2 ? x3 ?x , x , x , x , x ? 0 ? 1 2 3 4 5
对偶单纯形法的基本法则 法则 1 最优性判定法则(检验数全部小于等于零时最优) 法则 2 换出变量确定法则(谁最负谁出基) 法则 3 换入变量确定法则(最小比值原则) 法则 4 换基迭代运算法则

x1 z x4 x5 z -15 0 -5 -15

x2 -24 [-6] -2 0

x3 -5 -1 -1 -1

x4 0 1 0 -4

x5 0 0 1 0

RHS 0 -2 -1 8

x2 x5 z x2 x3

0 -5 -15/2 -5/4 15/2

1 0 0 1 0

1/6 [-2/3] 0 0 1

-1/6 -1/3 -7/2 -1/4 1/2

0 1 -3/2 1/4 -3/2

1/3 -1/3 17/2 1/4 1/2

写出对偶问题并求解?(利用互补松紧条件) 8、对于已经求解的一个线性规划问题如果改变价值向量和右端

向量原最优解/基是否仍是最优解/基?如果不是,如何进一步求 解?
例:线性规划

max

z ? 5 x1 ? 4 x2

? x1 ? 3 x2 ? 90 ? ? 2 x1 ? x2 ? 80 ? ? x1 ? x2 ? 45 ?x , x ? 0 ? 1 2
已知最优表:

x1 z x3 x1 x2 0 0 1 0

x2 0 0 0 1

x3 0 1 0 0

x4 -1 2 1 -1

x5 -3 -5 -1 2

RHS -215 25 35 10

(1)确定 x2 的系数 c2 的变化范围,使原最优解保持最优;

(2)若 c2=6,求新的最优计划。 解 (1)将上表中的第 0 行重新计算检验数,得到:

x1 z x3 x1 x2 z x3 x1 x2 5 0 1 0 0 0 1 0

x2
c2

x3 0 1 0 0 0 1 0 0

x4 0 2 1 -1
c2-5

x5 0 -5 -1 2
5-2c2

RHS 0 25 35 10 -175-10c2 25 35 10

0 0 1 0 0 0 1

2 1 -1

-5 -1 2

令 c2-5≤0,5-2c2≤0,解得 5/2≤c2≤5,即当 c2 在区间[5/2,5] 中变化时,最优解 X*=(35,10,25,0,0)T 保持不变。 (2)当 c2=6 时,c2-5=1>0,原最优解失去最优性,在表中修 改第 0 行后,用单纯形法容易求得新的最优表如下:

x1 z x3 x1 x2 z x4 0 0 1 0 0 0

x2 0 0 0 1 0 0

x3 0 1 0 0 -1/2 1/2

x4 1 [2] 1 -1 0 1

x5 -7 -5 -1 2 -9/2 -5/2

RHS -235 25 35 10 -495/2 25/2

x1 x2

1 0

0 1

-1/2 1/2

0 0

3/2 -1/2

45/2 45/2

故新的最优解为 x1*=45/2,x2*=45/2,x4*=25/2,x3*= x5*=0,最优 值 z*=495/2, 例 对于上例中的线性规划作下列分析:

(1)b3 在什么范围内变化,原最优基不变? (2)若 b3=55,求出新的最优解。 解原最优基为 B=(P3,P1,P2) ,由表 2-6 可得:
?1 B =?0 ? ?0 ?
-1

2 1 -1 -5 ? ? ? 1? 2 ? ?

-5 ? ? ? 1? 2 ? ?
? 90 ? ? 250-5b 3 ? ? ? ? ? ? 80 ? = ? 80 ? b 3 ? ≥0 ? b ? ? ?80 ? 2b ? ? 3? ? 3?

(1)由 B

-1

? 90 ? ? 1 ? ? ? ? 80 ? = ? 0 ?b ? ?0 ? 3? ?

2 1 -1

解得 40≤b3≤50,即当 b3∈[40,50]时,最优基 B 不变,最优解为:
* ? x 3 ? ? 250-5b 3 ? ? *? ? ? * x* * (80-b3)+4× (-80+2b3) ? x1 ? = ? 80 ? b 3 ? , 4 =x5 =0,z =5× ? * ? ? ?80 ? 2b ? 3? ? x2 ? ?

=80+3b3 (2)当 b3=55 时,
? 250-5b 3 ? ? ?25 ? ? ? ? ? ? 80 ? b 3 ? = ? 25 ? ,以它代替表的 b 列,用对偶单纯形法继续求 ? ?80 ? 2b ? ? 30 ? ? ? 3? ?

解。

x1 z 0

x2 0

x3 0

x4 -1

x5 -3

RHS -245

x3 x1 x2 z x5 x1 x2

0 1 0 0 0 1 0

0 0 1 0 0 0 1

1 0 0 -3/5 -1/5 -1/5 2/5

2 1 -1 -11/5 -2/5 3/5 -1/5

[-5] -1 2 0 1 0 0

-25 25 30 -230 5 30 20

故新的最优解为 x1*=30,2*=20,5*=5,3*= x4*=0, x x x 最优值 z*=230。

整数线性规划 0-1 规划
如何建立整数线性规划的数学模型? 如何用图解法求解两个变量的整数线性规划问题? 割平面方法的基本思想?如何用割平面方法求解整数线性规划 问题? 分支定界方法的基本思想?如何用分支定界方法求解整数线性 规划问题? 如何建立 0-1 规划问题的数学模型? 如何用隐枚举法求解 0-1 规划和匈牙利法求解指派问题?

1、 如何建立整数线性规划的数学模型? 2、 如何用图解法求解两个变量的整数线性规划问题? 3、 割平面方法的基本思想?如何用割平面方法求解整数线性 规划问题?
例考虑纯整数规划问题

max z ? x1 ? x2
? 2 x1 ? x 2 ? 6 ? ? 4 x1 ? 5 x 2 ? 20 ? x ? 0, x ? 0 且为整数 ? 1 2
解先不考虑整数条件,求得其松弛问题的最优单纯形表为:

x1 z x1 x2 0 1 0

x2 0 0 1
1 3

x3 -1/6 5/6 -2/3
1

x4 -1/6 -1/6 1/3
2 3 2

RHS -13/3 5/3 8/3

由第二行可以生成割平面:
1

x3+ x4>=
3 1

引入松弛变量 s1 后得:- x3- x4+s1=- 3 3 3 将此约束条件加到表中继续求解如下:

x1 z x1 x2 0 1 0

x2 0 0 1

x3 -1/6 5/6 -2/3

x4 -1/6 -1/6 1/3

s1 0 0 0

RHS -13/3 5/3 8/3

s1 z x1 x2 x3

0 0 1 0 0

0 0 0 1 0

[-1/3] 0 0 0 1

-1/3 0 -1 1 1

1 -1/2 5/2 -2 -3

-2/3 -4 0 4 2

所以原问题的最优解为:x1*=0,x2*=4,最优值 z*=4。

4、 分支定界方法的基本思想?如何用分支定界方法求解整数 线性规划问题?
例 求解下面整数规划

max z ? 3 x1 ? 2 x2
? 2 x1 ? x 2 ? 9 ? ? 2 x1 ? 3 x 2 ? 14 ? x ? 0, x ? 0 且为整数值 ? 1 2
(P0)

x1=3.25 x2=2.5 z(0)=14.755
X2<=2
(P1)

X2>=3
(P2)

x1=3.5 x2=2 z(1)=14.5

x1=2.5 x2=3 z(2)=13.5

X1<=3
(P3)

X1>=4
(P4)

x1=3 x2=2 z(3)=13
×

x1=4 x2=1 z(4)=14 *

5、如何建立 0-1 规划问题的数学模型? 6、如何用隐枚举法求解 0-1 规划和匈牙利法求解指派问题?
例 max z ? 5 x1 ? 4 x2 ? 3 x3

? x1 ? 3 x2 ? 2 x3 ? 5 ? ? 2 x1 ? 7 x2 ? 3 x3 ? 5 ? 2 x2 ? x3 ? 2 ? ?5 x ? 3 x ? 2 x ? 7 2 3 ? 1 ? x j ? 0 或 1 ? j= 1, , 3 ? 2 ?
满 (x1,x2,x3) (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) √ √ √ √ √ √ √ √ √ × ◎ × × ①

① ② ③ 5 x1 ? 4 x2 ? 3 x3 ? 4 ④





条 ②

件 ? ③ ④

满足所有 条件? × × √

z值

4

√ × √ √

× × √ √ √ √ √ √ × 8 9


相关文档

线性规划所有类型总结(很全的)
第1章:线性规划总结
第二章线性规划总结
第2章 线性规划 (1)总结
简单线性规划复习总结
第二章线性规划基本内容总结
简单的线性规划题型总结
简单的线性规划常见题型总结
最全线性规划题型总结
5线性规划总结
电脑版