cj→
CB
XB
31
x1
0
x4
0
x5
-z
b
30 280 120 -930
31 22 0 0 0
ห้องสมุดไป่ตู้
x1
x2
x3
x4
x5
1 1/3 1/6 0 0
约束条件:≥,=,≤
∑aijxj ≤(=, ≥) bi (i=1,2, …n)
变量符号:≥0,unr,≤0 xj ≥0
(j=1,2, …n)
线性规划的标准形式 目标函数:max 约束条件 := 变量符号 :≥0
max z=∑cjxj ∑aijxj = bi (i=1,2, …n) xj ≥0 (j=1,2, …n)
x2
50
当z的值增加时,目
标函数与约束条件:
40
4x1+3x2 120
30
重合,Q1与Q2之间都
是最优解。
20
Q2(15,20)
可行域
10
Q1(25,0)
10
20
30
40
x1
解的讨论:
无界解:
例:max z=x1+x2 s.t. -2x1+x2 40 x1-x2 20 x1,x2 0
取目标函数最大正系数对应的非基变量为入基变量;取最小比值所对应 方程的基变量为出基变量。本例中,取 x1为入基变量, x3为出基变量。
x1+ 1/3x2 +1/6x3 26/3x2 -2/3x3 +x4 4x2 -1/2x3 +x5
= 30 =280 =120
令 非 基 变 量 x2=x3=0,z(1)=930, 相 应 的 基 可 行 解 为 x(1)=(30,0,0,280,120)T