运筹学单纯形法的例题
《运筹学》单纯形法
2
《运筹学》单纯形法
2013-7-27
练习㈠用图解法和单纯形法求如 下线性规划问题的最优解: Max z =4 x1 + x2 x1 + 3x2 ≤ 7 s.t. 4x1 + 2x2 ≤ 9 x1 , x2 ≥ 0 7 2 x1+3x2=7经过点(__,0)与(1,__) 0.5 4x1+2x2=9经过点(2,___)与(0,___) 4.5
标准化为: M是一个大的正数 Max z =4 x1+x2+0x3+0x4-Mx5 x1 + 3x2 + x3 =7 s.t. 4x1 + 2x2 -x4+x5=9 x1 , x2 , x3 , x4 , x5≥ 0 这个“-”如何处 基是谁? 理? 再引进一个“人工变 量”x5
12 《运筹学》单纯形法 2013-7-27
练习㈡. 单纯形表
两行,几列? 少一列? 填入第一个约束的数据.
14 《运筹学》单纯形法 2013-7-27
练习㈡. 单纯形表
填入第二个约束的数据.基? 填目标函数系数,填基变量列, 填CB列,计算Zj,计算检验数σj,
15 《运筹学》单纯形法 2013-7-27
练习㈡. 单纯形表
7 9/4
查什么? 不是! 谁进基? 最优吗? 检验数最大的x1进基, 谁出基? x1的系数有正的吗? 求比值?
第五章(P.99-100): 预习第六章§2
线性规划的对偶问题
25 《运筹学》单纯形法 2013-7-27
作业
7a,b,c,d
练
0 6 0 0
习
0 0
6u 0 3 0 0 150
1
0 6 6
0 5-6u 0 -3 0 一个LP问题的单纯形表如上: 必须为____
1、试补齐中间的空格; ∴u=5/6 2、u取什么值时此问题有无穷多最优解? 26 2013-7-27
4 1 0 0 x3 0 1 3 1 0 7 7 x4 0 4 2 0 1 9 9/4 0 0 0 0 0 4 1 0 0 最优吗?查什么? 不是! 谁进基? 检验数最大的x1进基, 谁出基? 求比值? x1的系数有正的吗?
7 《运筹学》单纯形法 2013-7-27
练习㈠. 单纯形表
4 x3 0 1 x4 0 4 0 4 1 3 2 0 1 0 1 0 0 0 0 0 1 0 0
21 《运筹学》单纯形法 2013-7-27
解LP问题单纯形法
LP问题解的几种可能:
唯一解 有解 无穷多解
无有限最优解 无解
22
无可行解
《运筹学》单纯形法 2013-7-27
LP问题解的几种可能: Ax≤b s.t. x≥0
无需引入人工变量.一定有可 行解,从而一定有基可行解,但 还有可能有无穷最优解或无有 限最优解.
16 《运筹学》单纯形法 2013-7-27
练习㈡. 单纯形表:迭代
x1 x5 基变量列中___换为___, -M 4 改CB列,____换为___.
17 《运筹学》单纯形法 2013-7-27
Excel
练习㈢用图解法和单纯形法求 如下线性规划问题的最优解: Max z =4 x1 + x2 x1 + 3x2 ≥ 7 s.t. 4x1 + 2x2 ≥ 9 x1 , x 2 ≥ 0
x2
0 1 0 0 0
x3
0 0 1 0 0
x4
7 7 9 9/4 0
bi
比
CB
1
x3 0 x1 4 zj σj=Cj- zj
9
4 0 1 4 0
1 2.5 0.5 2 -1
《运筹学》单纯形法
0 0 1 -0.25 4.75 0 0.25 2.25 0 1 9 0 -1
2013-7-27
练习㈡用图解法和单纯形法求 如下线性规划问题的最优解: Max z =4 x1 + x2 x1 + 3x2 ≤ 7 s.t. 4x1 + 2x2 ≥ 9 x1 , x 2 ≥ 0
《运筹学》单纯形法
下 可行域在x1+3x2=7与4x1+2x2=9之__
3 《运筹学》单纯形法 2013-7-27
练习㈠用图解法
5
4
4x1+x2=9
3
2
1 (2.25,0) 0 1
4
2
3
4
5
《运筹学》单纯形法
2013-7-27
6
7
练ห้องสมุดไป่ตู้㈠. 单纯形表
1 4 3 1 2 0 0 1 7 9
填入第一个约束的数据. 填入第二个约束的数据.
20 《运筹学》单纯形法 2013-7-27
练习㈢.用单纯形法
Max z=4x1+x2+0x3+0x4 -Mx5 –Mx6 x1+3x2-x3 +x5 =7 s.t. 4x1+2x2 -x4 +x6=9 x1,x2,x3,x4 ,x5,x6 ≥0 基是谁? x5,x6 它们的检验数为0 请它们出基,逼它们取值为0. 不能全出基,就无可行解. Excel
5 《运筹学》单纯形法 2013-7-27
练习㈠. 单纯形表
4 x3 0 1 x4 0 4 0 4 1 3 2 0 1 0 1 0 0 0 0 0 1 0 0
7 9
基?
0
填目标函数系数,填基变量列, 填CB列,计算Zj,计算检验数σj,
6 《运筹学》单纯形法 2013-7-27
练习㈠. 单纯形表
下 可行域在直线 x1+3x2=7之__
上 可行域在直线4x1+2x2=9之__
10 《运筹学》单纯形法 2013-7-27
练习㈡用图解法
5 最优解是x1=7,x2=0,此时Max z=28
4
4x1+x2=28 3
2 (7,0) 1
0
11
1
2
3
4
5
《运筹学》单纯形法
2013-7-27
6
7
练习㈡.用单纯形法 (大M法)
23 《运筹学》单纯形法 2013-7-27
解LP问题单纯形法
一般要引入人工变量. 人工变量不能全出基则无可行解,更 无最优解. 不需人工变量或人工变量可以全部出 基则必有可行解.分:
LP问题解的几种可能:
解LP问题单纯形法
至少有一个非基变量的检验数为正,但它的系 数全为非正,则无有限最优解; 所有非基变量的检验数全为非正,已有最优解, 但若其中至少有一个的检验数为0,且它的系 数中有正的,则可能有无穷多个最优解。 24 2013-7-27 《运筹学》单纯形法
上 可行域在直线 x1+3x2=7之__
上 可行域在直线4x1+2x2=9之__
18 《运筹学》单纯形法
2013-7-27
5
练习㈢用图解法
有可行解,但无有限的最优解,z→+∞.
4
3
2
1
0
19
1
2
3
4
5
《运筹学》单纯形法
2013-7-27
6
7
练习㈢.用单纯形法(大M法)
标准化为: M是一个大的正数 Max z=4x1+x2+0x3+0x-Mx5 -Mx6 4 x1 + 3x2 - x3 +x5 =7 s.t. 4x1 + 2x2 -x4+x6=9 x1 ,x2 ,x3 ,x4,x5 ,x6≥0 这里“-”如何处 基是谁? 理? 引进两个“人工变量” x5 ,x6
7 9
7 9/4
0
x1 x4 基变量列中___换为___, 改CB列,___换为___. 0 4
8 《运筹学》单纯形法
Excel
2013-7-27
练习㈠用单纯形法
迭代 次数 基 变量
CB
x1
x2
x3
x4
bi
比
0
迭代 次数
zj σj=Cj- zj
基 变量
x3 x4
0 0
4 1 4 0 4
x1
1 3 2 0 1
练习㈡.用单纯形法
Max z =4x1+x2+0x3+0x4-Mx5 x1 + 3x2 + x3 =7 s.t. 4x1 + 2x2 -x4+x5 =9 x1, x2 , x3 , x4 , x5 ≥0 基是谁? x3,x5 x5的检验数为0
请它出基,逼它取值为0.
13 《运筹学》单纯形法 2013-7-27