线性规划33.ppt

Max S= c1x1 + c2x2 + …+ cnxn
a11x1 + a12x2 + …+ a1nxn = b1
a21x1 + a22x2 + …+ a2nxn = b2
.
.
.
am1x1 + am2x2 + …+ amnxn = bm

x1 ,x2 ,…,xn ≥ 0
第三节线性规划问题数学模型的标准形式
目标应最大化
约束应为等式
决策变量均非负
右端项均非负
例
1
:
设目标函数为
Min S= c1x1 + c2x2 + …+ cnxn
则可以令z = -S ,该极小化问题与下面的极大化问题有相同的最优解,即
Max z = -c1x1 - c2x2 - …- cnxn
2
2、约束条件不是等式的问题:
如:设约束条件为
ai1 x1+ai2 x2+ …+ain xn ≤bi
可以引进一个松弛变量s (s≥0),使得
ai1 x1+ai2 x2+ …+ain xn+s = bi

又如:约束条件为
ai1 x1+ai2 x2+ …+ain xn ≥ bi
可以引进一个松弛变量s (s≥0),使得
ai1 x1+ai2 x2+ …+ain xn-s = bi
3
:
在标准形式中,要求右端项必须每一个分量非负。当某一个右端项系数为负时,如 bi<0,即
ai1 x1+ai2 x2+ …+ain xn = bi
则把该等式约束两端同时乘以-1,得到:
-ai1 x1-ai2 x2- …-ain xn = -bi
4
4. 变量无符号限制的问题:
在标准形式中,必须每一个变量均有非负约束。
可以令 xj = xj′- xj〃
当某一个变量 xj 没有非负约束时,
其中 xj′≥0, xj〃≥0
5
例1:将以下线性规划问题转化为标准形式 
Min S = 3x1 - 5x2 + x3
2x1 + 5x2 - x3 ≤15
4x1 + 3x3 ≥8
x1 - x2 - x3 =-38
x1 , x2 , x3 ≥ 0
解
6
其次,考虑约束,有2个不等式约束,引进松弛变量x4,x5 ≥0。
2x1+5x2-6x3+x4= 15
4x1+3x3-x5= 8
首先,将目标函数转换成极大化:
令 z= -S = -3x1+5x2-x3
第三,由于第3个约束右端项系数为-38,于是把该式两端乘以-1 。
-x1+x2+x3= 38
原题
解:
7
于是,我们可以得到以下标准形式的线性规划问题:
Max z = - 3x1 + 5 x2 - x3
2x1+5x2-6x3+x4= 15
4x1+3x3-x5= 8
-x1+x2+x3= 38
x1 ,x2 ,x3 ,x4 ,x5 ≥ 0
原题
8
练****将以下线性规划问题转化为标准形式
Min S= x1 -3x2
x1 -x2 ≥5
x1 ≤2
x2 ≤-3
xi ≥ 0, (i=1,2)
解:其标准形式为
Max Z= -x1 + 3x2
x1 -x2–x3=5
x1 +x4=2
-x2-x5=3
xi ≥ 0, (i=1,2,3,4,5)
9
例2:将以下线性规划问题转化为标准形式
Max f= -3 x1 + 5 x2
2x1 -3 x2≤28
x1≥0
解:其标准形式为
Max f= -3x1+5(x2′-x2″)
2x1–3(x2′-x2″)+x3= 28
x1 ,x2′,x2″,x3 ≥ 0
提示:
令 x2=x2′-x2″,
x2′≥0,x2″≥0 ;
10