【正文】 3 (2) 型機床的臺數(shù)種零件表示生產(chǎn)設(shè)變量 ijij ABx323122211211 372330554030 xxxxxxZ ??????m a x????????????????).,..( 213210204040323122211211jixxxxxxxij且為整數(shù)x1 x2 1 2 3 (1) （一）、基本思想 將模型的一般形式變成標準形式，再根據(jù)標準型模型，從可行域中找一個基本可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個基本可行解，當目標函數(shù)達到最大時，得到最優(yōu)解。 （二）、線性規(guī)劃模型的標準形式 ?????????????? )n 2 1(j 0 m) 2 1(i ??jijijjjxbxaxcZm a x標準形式 四、單純形法 特征： ⑴ .目標函數(shù)為求極大值，也可以用求極小值； ⑵ .所有約束條件（非負條件除外）都是等式，右端常數(shù)項為非負； ⑶ .變量為非負。 轉(zhuǎn)換方式： ⑴ .目標函數(shù)的轉(zhuǎn)換 如果是求極小值即 ，則可將目標函數(shù)乘以（－ 1），可化為求極大值問題。 ?? jj xcZm in?????? jj xcZZm a x也就是：令 ，可得到上式。 ZZ ???即 ⑵ .約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式。 ? ? ijij bxa0??????iniinjijxbxxa 稱為松弛變量 ? ? ijij bxa0??????iniinjijxbxxa 稱為剩余變量 ⑶ .變量的變換 若存在取值無約束的變量 ，可令 其中： jx jjj xxx ?????0, ???? jj xx例 一、將下列線性規(guī)劃問題化為標準形式 ??????????????????????? ,0,52324 7 532m i n321321321321321xxxxxxxxxxxxxxxZ為無約束（無非負限制） 解 : 用 替換 ，且 ， 54 xx ? 3x 0, 54 ?xx將第 3個約束方程兩邊乘以 （－ 1） 將極小值問題反號，變?yōu)榍髽O大值 標準形式如下： ???????????????????????????? 0,,5 )(252 )( 7 )(500)(32m a x76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76 , xx引入變量 例二、將線性規(guī)劃問題化為標準型 ????????????? ,043 5832m a x21212121xxxxxxxxZ為無約束 解： ????????????????? 0, 4 )(3 5 )(83)(2m i n6543164315431431xxxxxxxxxxxxxxxxZ（三）、單純形法 例一、 ?????????????????? 0,124 16 482122232m a x2121212121xxxxxxxxxxZ變成標準型 ?????????????????????????? 0,, 12 4 16 4 8 2 21 22000032m a x6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ約束方程的系數(shù)矩陣 ? ?654321100040010004001021000122ppppppA ??????????????? ? IppppB ???????????????100001000010000165436543 xxxx ,?21 xx ,為基變量 為非基變量 I 為單位矩陣且線性獨立 令： 12x 16x 8x 12x 0654321?????? xx則： ∴ 基本可行解為 （ 0 0 12 8 16 12） 此時， Z = 0 然后，找另一個基本可行解。即將非基變量換入基變量中，但保證其余的非負。如此循環(huán)下去，直到找到最優(yōu)解為止。 注意：為盡快找到最優(yōu)解，在換入變量時有一定的要求。如將目標系數(shù)大的先換入等。 找出一個初始可行解 是否最優(yōu) 轉(zhuǎn)移到另一個目標函數(shù) （找更大的基本可行解） 最優(yōu)解 是 否 循 環(huán) 直到找出為止，核心是：變量迭代 結(jié)束 其步驟總結(jié)如下： 當 時， 為換入變量 01 ?x 2x0 4120 160 2 802122652423???????????xxxxxxx 確定換出變量 3)412 28 212m i n ( 2 ??x?6x?為換出變量 接下來有下式： ? ?? ?? ?? ?4 124 3 416 2 82 1 212 2 6215124123xxxxxxxxxx?????????? 用高斯法，將 的系數(shù)列向量換為單位列向量，其步驟是： 2x( 3 ))(3,)(422)()(2,)(42( 1 ))(1 ,4 )4()4( ????????????結(jié)果是： 621561461341 3 416 21 2 2126 xxxxxxxxxx?????????????1? ??2???3? ??4? ?? ?? ?? ?4 12 4 3 416 2 8 2 1 212 2 6215124123xxxxxxxxxx??????????代入目標函數(shù)： 6161 43294392 xxxxZ ?????? 有正系數(shù)表明：還有潛力可挖，沒有達到最大值； 此時：令 得到另一個基本可行解 （ 0， 3， 6， 2， 16， 0） 1x 有負系數(shù)表明：若要剩余資源發(fā)揮作用，就必須支付附加費用。當 時，即不再利用這些資源。 6x06 ?x9 ,061 ??? Zxx如此循環(huán)進行，直到找到最優(yōu)為止。 本例最優(yōu)解為： （ 4， 2， 0， 0， 0， 4） 14m a x Z 812314 54 ???? xxzjc nmm cccc ???? 11 ?Bc BX bmcc?? 1mxx?? 1mbb?? 1nmm xxxx ???? 11 ?i?m???? 1mnmmnmaaaa????????????????1,11,11001??Z? iibc?? 0 0 ?? ??? ijijj acc?)m i n ( 0?? kjkji aab?（四）、單純形表 判定標準： 0 0:m i n0 0:m a xz j??????????? ?jjjjjjjjijijjjczzcczzcaczc?若求 或 ?????????????????????????? 0,, 12 4 16 4 8 2 21 22000032m a x6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例 題： cj 2 3 0 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 0 0 0 x3 x4 x5 x6 12 8 16 12 2 2 1 0