一．非标准形式化为标准
例1：下列线性规划问题化为标准型。(10分)
''''1、 minZ??x1+5x2-2x3 max(-z)=x1?5x2?2(x3?x3)
x1?x2?x3?62x1?x2?3x3?5x1?x2?10
满足
x1?0,x2?0,x3符号不限
二．用单纯形法求解线性规划的最优解
例1：1、某工厂拥有A,B,C三种类型的设备，生产甲、乙两种产品，每件产品在生产中需要使用的机时数，每件产品可以获得的利润，以及三种设备可利用的机时数见下表：
求：（1）线性规划模型；（5分） （2）利用单纯形法求最优解；（15分）
maxz?1500x1?2500x2答案：1. 解：（1）
3x1?2x2?65
满足 （2）
cB2x1?x2?40
x1,x2?0
xB3x2?75 b '1500 2500 x10 x30 x40 x5 ? x2 0 0 0 ?z x3x4x5 65 40 75 0 3 2 0 2 1 [3] 1 0 0 0 0 1 0 0 0 0 1 0 32.5 40 25 1500 2500 1
0 0 x3x4 15 15 [3] 2 0 0 0 1 0 0 0 1 0 1 0 0 0 1/3 -2/3 0 0 1 0 0 0 1 0 -2/3 -1/3 1/3 -2500/3 -2/9 1/9 1/3 -500 5 7.5 _ - _ _ _ 2500 x2 25 ?z -62500 1500 1 0 0 0 1500 x1 5 0 2500 ?z x4x2 5 25 -70000 T-500 0
最优解
x?(5,25,0,5,0)* 最优目标值 = 70000元
三．线性规划原问题如下，请写出对应的对偶模型
Smax?2x1?5x2
?x1?4??x2?3 ?x?x?82?1?x,x?0?12
Smin = 4y1＋3y2+4y3
y1+y3≥2
y2+y3≥5
y1, y2, y3≥0
例2：写出下列问题的对偶问题 (10分)
minZ?4x1?2x2+3x3
4x1+5x2?6x3=7满足
答案：
8x1?9x2?10x3?1112x1?13x2?14x1?0,x2无约束，x3?0
maxW=7y1?11y2?14y3
2
四．灵敏度分析
?maxz?3x1?3x2?x1?x2?4???x1?x2?2??6x?2x?1812?x1?0,x2?0??
例1：:用单纯形法求解
；并对以下情况作灵敏度分析：（1）求c2?5?的变化范围；（2）若右边常数向量变为b??2?，分析最优解的变化。
???20?
1、解：
加入人工变量，化问题为标准型式如下：
maxz?3x1?3x2?0x3?0x4?0x5?x1?x2?x3?4???x1?x2?x4?2s.t??6x1?2x2?x5?18?x,x,x,x,x?0?12345 (3分)
下面用单纯形表进行计算得终表为：
3 c j3 x2 0 x3 0 x4 0 x5CB 基 x3 x4 x1 cj?zj b x1 0 0 3 1 5 3 0 0 1 0 2/3 4/3 1/3 0 1 0 0 0 0 1 0 0 -1/6 1/6 1/6 -1/2 （5分） 所以原最优解为 X*?(3,0,1,5,0)T （2分）
3
（1）设c2变化?，将c2得变化带入最终单纯形表得c2的变化范围为c2?1；
（5分）
?5?（2）若右边常数向量变为b??2?，将变化带入最终单纯形表得：最优基解不
???20?变，最优解的值由（3，0）T变为（10/3，0）T。 （5分）
例2：考虑如下线性规划问题（24分） Max z=-5x1+5x2+13x3 s.t. -x1+x2+3x3≤20
12x1+4x2+10x3≤90 x1，x2， x3≥0
回答以下问题： 1）求最优解
2）求对偶问题的最优解
3）当b1由20变为45，最优解是否发生变化。
4）求新解增加一个变量x6，c6=10，a16=3，a26=5，对最优解是否有影响 5）c2有5变为6，是否影响最优解。 答：最优解为 1) Cj CB 0 0 Cj-Zj 13 0 Cj-Zj 13 5 X3 X5 X3 X2 20/3 70/3 185/33 35/11 XB X4 X5 b 20 90 -5 X1 -1 12 -5 -1/3 46/3 5 X2 1 4 5 1/3 22/3 13 X3 3 10 13 1 0 0 1 0 0 0 X4 1 0 0 1/3 -10/3 -13/3 2/11 -5/11 -1/11 0 X5 0 1 0 0 1 0 -1/22 3/22 -1/11 θ 20/3 9 20 70/22 -2/3 2/3 -34/33 0 23/11 1 -68/33 0 最优解为X1=185/33, X3=35/11 2)对偶问题最优解为
Y＝（1/22,1/11,68/33,0,0）T 3)
当b1=45时 X= 45/11 -11/90 由于X2的值小于0，所以最优解将发生变化 4）P6’=(3/11,-3/4)T σ6=217/20>0
所以对最优解有影响。 5）当C2=6
4