基本思路：基于線性規劃問題的標準形，先確定一初始基可行解X0,并由此開始在保證目標函數值不下降的情況下逐次施行從一個基可行解到另一個基可行解的轉換。如此進行下去，直到取得最優解或判明問題無最優解為止。4）基本步驟:（1） 對一般線性規劃問題標準化；（2） 確定一初始基可行解X0;（3） 若所有檢驗數ajV0（aj為的第］個分量），則X0是線性規劃問題的最優解，停止計算；否則較4）（4） 若存在atv0所對應的系數列向量pt<O,則線性規劃問題無最優解，停止計算；否則轉（5）。（5）按最大檢驗數規則：jj0}jj0}kj確定進基變量xk和主列pk；再按最小比值規則:min{^^|a0} -i-

ia.ik a確定出基變量xl和主元alk。（6）以主元alk進行換基迭代得一新的基可行解xl,將xl記為x0返回到（3）。對偶關系對應表原問題（或對偶問題）對偶問題（或原問題）原問題（或對偶問題）對偶問題（或原問題）目標函數maxZ目標函數maxZ目標函數minW約束條件>0條件約束條件>0條件<0無限制m個變<量>n個約束約束條件右邊常數項目標函數變量系數約束條件右邊常數項目標函數變量系數目標函數變量系數約束條件右邊常數項目標函數變量系數約束條件右邊常數項表上作業法是單純形法在求解運輸問題時的一種簡化方法，其本質是單純形法。2）表上作業法的基本步驟：（1） 找一初始的調運方案（初始基可行解）；（必須滿足：①產銷平衡，②數字格（基變量）的個數為:產地數+銷地數-1；常用最小元素法尋找）（2） 判斷：計算表（產銷平衡表）上空格（非基變量）的檢驗數，判斷該方案是否為最優方案（最優解），若是最優方案，則停止計算;否則轉（3）。（因運輸問題為極小化問題，故最優性條件為：檢驗數a>0；常用位勢法或閉合回路法計算檢驗數）（3） 調整：確定某個空格和某個數字格的轉換，找出新的調運方案基可行解)轉(2)常用閉合回路法進行調整(2)判斷用位勢法計算空格(非基變量)檢驗數：應用Cij=Ui+Vj計算數字格(基變量)的位勢Ui、Vj，并令：U1=0；應用aij=Cij-(Ui+V計算空格非基變量)的檢驗數aij;若所有空格(非基變量)的檢驗數akl>0,則停止計算，輸出最優方案；否則轉(2。具體結果見下表3.6-5:(3)調整：(用閉合回路法)從某個檢驗數akl<0的空格(非基變量)出發；根據“遇見空格直行”的原則做閉合回路1;在閉合回路1的奇拐點中找出最小運量，記為a;將閉合回路L的每個奇拐點的運量都減去a,每個偶拐點的運量都加上a;得一新的調運方案；轉⑵匈牙利算法1)適用范圍：指派問題的標準型問題。指派問題的標準型問題必須滿足以下3個條件：目標要求為極小化(min)；效益矩陣(目標系數矩陣)A=(aij)xn為方陣；A中所有元素均為非負常數(a>0,i,j=1,?凱n)基本步驟：效益矩陣的初始變換一一零元素的獲取行變換：效益矩陣A0的每行減去該行的最小元素得新父攵益矩陣A1;列變換：對A1的每列減去該列的最小元素得新效益矩陣A2；（2） 最優性檢驗：用最少的直線覆蓋A2所有的0元素，記其直線數為K,若k=n，則轉（4）；否則轉（3）。（3） 調整：在覆蓋有直線的A2中，對線外的所有元素減去這些元素中的最小a；對線上交叉的元素加上a，得一新的效益矩陣，仍記為A2；轉（2）。（4） 輸出最優解：確定位于不同行不同列的0元素；將確定的位于不同行不同列的0元素對應的決策變量取1，其余決策變量取0，得最優解（方案）。三、分支定界法1、 適用范圍：一般整數規劃問題2、 基本思想：先求不含整數約束的規劃問題（整數規劃松弛問題）的最優解X。若X為整數解，則X*=X 為原整數規劃問題的最優解。否則，若X中的xk=bk不是整數，則將原整數規劃問題分別添加xk<[bk和