【文章內容簡介】 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 X=(0 0 8 16 12),Z=0 Max Z=2X1+3X2+0X3+0X4+0X5 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 X1,X2 ,X3 ,X4 ,X5 ≥0 X3 8 1 2 1 0 0 X4 16 4 0 0 1 0 X5 12 0 4 0 0 1 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 用表表示： 36 當 X2=min(8/2,,12/4)=3時 , X5=0, ∴X 5出基。 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 8/2 12/4 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 基 變 換 37 X1 +X3 X5 /2 =2 ① ’=① 2*③ ’ 4X1 +X4 =16 ② ’=② X2 +X5 /4 =3 ③ ’=③ /4 解基變量并保持右端常數是其值的形式 ,對系數作如下變換： X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 ① ’=① 2*③ ’： X1+2X2 +X3 =8 2（ X2 +X5 /4 =3） = X1+X3 X5 /2 =2 2 0 4 0 0 1 X3 2 1 0 1 0 1/2 X4 16 4 0 0 1 0 X2 3 0 1 0 0 1/4 用表表示： X2 X5 38 X3 8 1 2 1 0 0 X4 16 4 0 0 1 0 X5 12 0 4 0 0 1 X3 2 1 0 1 0 1/2 X4 16 4 0 0 1 0 X2 3 0 1 0 0 1/4 X1 +X3 X5 /2 =2 4X1 +X4 =16 X2 +X5 /4 =3 X1+2X2 +X3 =8 4X1 +X4 =16 4X2 +X5 =12 令 X1,X5=0,得 X=(0 3 2 16 0),將 X X2代入目標函數 ，并寫成只含非基變量形式 得： Z=2X1+3(3X5 /4)=9+2X13X5 /4。 ∵ X1 系數 C1=20, ∴ 此解非最優(yōu) , 選 X1進基。 和前一步對比： 39 當 X1=min(2/1,16/4,)=2時 , X3=0, ∴ X3出基。 X1 +X3 X5 /2 =2 4X1 +X4 =16 X2 +X5 /4 =3 2/1 16/4 X1 +X3 X5 /2 =2 4X1 +X4 =16 X2 +X5 /4 =3 X1 +X3 X5 /2 =2 4X1 +X4 =16 X2 +X5 /4 =3 X1 +X3 X5 /2 =2 4X1 +X4 =16 X2 +X5 /4 =3 基 變 換 40 解基變量并保持右端常數是其值的形式 ,對系數作如下變換： ② ’= ② 4*① ： 4X1 +X4 =16 4（ X1+X3X5 /2 =2 ) = 4X3+X4+2X5 =8 1 4 0 1 0 0 X1 2 1 0 1 0 1/2 X4 8 0 0 4 1 2 X2 3 0 1 0 0 1/4 用表表示： X1 +X3 X5 /2 =2 ① 4X1 +X4 =16 ② X2 +X5 /4 =3 ③ X1 X3 X1 +X3 X5 /2 =2 ① ’=① 4X3+X4+2X5 =8 ② ’=② 4*① X2 X5 /4 =3 ③ ’=③ 41 令 X3,X5=0,得 X=(2 3 0 8 0),將 X X2代入目標函數 ，并寫成只含非基變量形式 得： Z=2(2X3+X5/2)+3(3X5/4)=132X3+X5/4 。 ∵ X5 系數 C5=1/40, ∴ 此解非最優(yōu) , 選 X5進基。 和前一步對比： X1 +X3 X5 /2 =2 4X3+X4+2X5 =8 X2 +X5 /4 =3 X1 2 1 0 1 0 1/2 X4 8 0 0 4 1 2 X2 3 0 1 0 0 1/4 X3 2 1 0 1 0 1/2 X4 16 4 0 0 1 0 X2 3 0 1 0 0 1/4 X1 +X3 X5 /2 =2 4X1 +X4 =16 X2 +X5 /4 =3 42 當 X5=min(,8/2,3*4)=4時 , X4=0, ∴ X4出基。 8/2 3*4 基 變 換 X1 +X3 X5 /2 =2 4X3+X4+2X5 =8 X2 +X5 /4 =3 X1 +X3 X5 /2 =2 4X3+X4+2X5 =8 X2 +X5 /4 =3 X1 +X3 X5 /2 =2 4X3+X4+2X5 =8 X2 +X5 /4 =3 X1 +X3 X5 /2 =2 4X3+X4+2X5 =8 X2 +X5 /4 =3 43 解基變量并保持右端常數是其值的形式 ,對系數作如下變換： ① ’=① + ② ’/2： X1 +X3 X5 /2 =2 + (2X3+X4/2 +X5 =4 )/2 = X1+X4 /4 =4 1/2 2 1/4 0 1 0 X1 4 1 0 0 1/4 0 X5 4 0 0 2 1/2 1 X2 2 0 1 1/2 1/8 0 用表表示： X5 X4 X1 +X3 X5 /2 =2 ① 4X3+X4+2X5 =8 ② X2 +X5 /4 =3 ③ X1+X4 /4 =4 ① ’=① + ② ’/2 2X3+X4/2 +X5 =4 ② ’= ② /2 X2 +X3 /2X4/8 =2 ③ ’=③ ② ’/4 ③ ’=③ ② ’/4 ： X2 +X5 /4 =3 (2X3+X4/2 +X5 =4 )/4 = X2+X3/2X4 /8 =2 44 令 X3,X4=0,得 X=(4 2 0 0 4),將 X X2代入目標函數 ，并寫成只含非基變量形式 得： Z=2(4X4/4)+3(2X3/2+X4/8)=143X3/2X4/8 。 和前一步對比： X1+X4 /4 =4 2X3+X4/2 +X5 =4 X2 +X3 /2X4/8 =2 X1 4 1 0 0 1/4 0 X5 4 0 0 2 1/2 1 X2 2 0 1 1/2 1/8 0 X1 +X3 X5 /2 =2 4X3+X4+2X5 =8 X2 +X5 /4 =3 X1 2 1 0 1 0 1/2 X4 8 0 0 4 1 2 X2 3 0 1 0 0 1/4 45 ∵ 目標函數中所有變量的系數均 或 =0, ∴ 得最優(yōu)解： X*=(4 2 0 0 4),Z*=14 答：該廠生產 I產品 4件， II產品 2件，可獲最大利潤 14元。 將上述方程組求解過程，用列表形式表達，即為線性規(guī)劃單純形法。 Z=2(4X4/4)+3(2X3/2+X4/8)=143X3/2X4/8 。 46 x3 x4 x2 ← 表 13 表 14 2 1 0 1 0 1/2 3 0 1 0 0 1/4 檢驗行 ?j 2 0 0 0 3/4 2/1=2 16/4=4 ↓ ↓ ← 8/2=4 12/4=3 16 4 0 0 1 0 0 0 3 47 表 15 2 1 0 1 0 1/2 8 0 0 4 1 2 3 0