【正文】 的系數(shù)取為“ M” 對最小化的 LP問題，人工變量在目標函數(shù)中的系數(shù)取為“ M” 然后再用單純形法求解。 若最優(yōu)解的基變量中仍含有人工變量，則 LP問題為無可行解。 廣東工業(yè)大學(xué)管理學(xué)院 100 p30 例 6 給定 LP問題 ????????????????????0,93124..3m a x3213232132131xxxxxxxxxxxtsxxz化成標準形式后為 ??????????????????????0,93124..3m a x54321325321432131xxxxxxxxxxxxxxxtsxxz不存在前面那種初始基變量，因此要添加人工變量 廣東工業(yè)大學(xué)管理學(xué)院 101 添加人工變量，并用大 M法處理人工變量，模型變?yōu)? ??????????????????????????0,93124..3m a x717326532143217631xxxxxxxxxxxxxxtsMxMxxxz?然后用單純形法求解該問題 廣東工業(yè)大學(xué)管理學(xué)院 102 3 0 1 0 0 M M Cb Xb b x1 x2 x3 x4 x5 x6 x7 0 M M x4 x6 x7 4 1 9 1 1 1 1 0 0 0 2 1 1 0 1 1 0 0 3 1 0 0 0 1 σj 2M3 4M 1 0 M 0 0 0 0 M x4 x2 x7 3 1 6 3 0 2 1 1 1 0 2 1 1 0 1 1 0 6 0 4 0 3 3 1 σj 6M3 0 4M+1 0 3M 4M 0 廣東工業(yè)大學(xué)管理學(xué)院 103 3 0 1 0 0 M M Cb Xb b x1 x2 x3 x4 x5 x6 x7 0 0 3 x4 x2 x1 0 3 1 0 0 0 1 1/2 1/2 1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 1/2 1/6 σj 0 0 3 0 3/2 M3/2 M+1/2 0 0 1 x4 x2 x3 0 5/2 3/2 0 0 0 1 1/2 1/2 1/2 1/2 1 0 0 1/4 1/4 1/4 3/2 0 1 0 3/4 3/4 1/4 σj 9/2 0 0 0 3/4 M+3/4 M1/4 最優(yōu)解為 0,23,25,0 7654321 ??????? xxxxxxx最優(yōu)目標函數(shù)值為 23* ?z廣東工業(yè)大學(xué)管理學(xué)院 104 兩階段法 大 M法的不足。 兩階段法： 添加了人工變量后，分兩個階段來求解 LP問題。 第一階段： 求解輔助的 LP問題。輔助的 LP問題構(gòu)造如下： 約束條件就是原來的（添加了人工變量后）條件，目標函數(shù)是所有人工變量之和，對這樣的目標函數(shù)求最小值。 若第一階段的目標函數(shù)的最優(yōu)值不等于零，則原 LP問題無可行解， 否則進入第二階段。 廣東工業(yè)大學(xué)管理學(xué)院 105 第二階段： 將第一階段的最終單純形表中的人工變量去掉，并將目標函數(shù)系數(shù)換成原LP問題的目標函數(shù)系數(shù)，然后以這樣得到的單純形表為初始單純形表，用單純形法求解原 LP問題。 若無須添加人工變量，則 LP問題一定存在可行解。 廣東工業(yè)大學(xué)管理學(xué)院 106 仍然考慮 p30 例 6 首先寫出輔助的 LP問題 ???????????????????????0,93124..m i n7173265321432176xxxxxxxxxxxxxxtsxxz?現(xiàn)在用單純形法求解該輔助 LP問題，注意它為最小化問題。既可直接求解，也可轉(zhuǎn)化為最大化問題求解。 廣東工業(yè)大學(xué)管理學(xué)院 107 0 0 0 0 0 1 1 Cb Xb b x1 x2 x3 x4 x5 x6 x7 0 1 1 x4 x6 x7 4 1 9 1 1 1 1 0 0 0 2 1 1 0 1 1 0 0 3 1 0 0 0 1 2 4 0 0 1 0 0 0 0 1 x4 x2 x7 3 1 6 3 0 2 1 1 1 0 2 1 1 0 1 1 0 6 0 4 0 3 3 1 6 0 4 0 3 4 0 0 0 0 x4 x2 x1 0 3 1 0 0 0 1 1/2 1/2 1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 1/2 1/6 0 0 0 0 0 1 1 0 廣東工業(yè)大學(xué)管理學(xué)院 108 第二階段 3 0 1 0 0 Cb Xb b x1 x2 x3 x4 x5 0 0 3 x4 x2 x1 0 3 1 0 0 0 1 1/2 0 1 1/3 0 0 1 0 2/3 0 1/2 σj 0 0 3 0 3/2 0 0 1 x4 x2 x3 0 5/2 3/2 0 0 0 1 1/2 1/2 1 0 0 1/4 3/2 0 1 0 3/4 σj 9/2 0 0 0 3/4 最優(yōu)解為 0,2/3,2/5,054321 ????? xxxxx最優(yōu)目標函數(shù)值為 2/3* ?z廣東工業(yè)大學(xué)管理學(xué)院 109 無可行解的判別 若無須添加人工變量，則 LP問題一定存在可行解。 若需要添加人工變量，則 當(dāng)用大 M法求解時， 若最優(yōu)解的基變量中仍含有人工變量，則 LP問題為無可行解。 當(dāng)用兩階段法求解時， 若第一階段的目標函數(shù)的最優(yōu)值不等于零，則原 LP問題無可行解。 廣東工業(yè)大學(xué)管理學(xué)院 110 退化 退化 是指當(dāng)確定換出變量時， b列的數(shù)除以換入變量列對應(yīng)系數(shù)出現(xiàn)多個最小值。 這將導(dǎo)致基變量取零值的情況，從幾何上看這意味著多個基可行解對應(yīng)同一個頂點。 如果出現(xiàn)退化，有可能導(dǎo)致單純形法的迭代陷入循環(huán)。 避免循環(huán)的 Bland規(guī)則 （ 1）始終選擇最左邊的正檢驗數(shù)對應(yīng)的變量為換入變量；（ 2）當(dāng)存在多個變量可作為換出變量時，始終選擇最上邊的變量。 廣東工業(yè)大學(xué)管理學(xué)院 111 線性規(guī)劃模型 化為標準形式 0?jx 不變 0?jx 令jjxx ??39。，則 039。?jx 變量 jx 取值無約束 令39。jjjxxx ?? ，其中 0,039。??jjxx 0?ib 不變 右端項 0?ib 約束條件兩端乘“ 1 ” injjijbxa ??? 1 isinjjijbxxa ???? 1 injjijbxa ??? 1 iaisinjjijbxxxa ????? 1，其中aix 為人工變量（下同） 約束條件 形式 injjijbxa ??? 1 iainjjijbxxa ???? 1 ???njjjxcz1m ax 不變 極大或極小 ???njjjxcz1min 令 zz ??39。 ，化為求????njjjxcz139。m ax 松弛變量或剩余變量 在目標函數(shù)中的系數(shù)為零 目標函數(shù) 變量前的系數(shù) 人工變量 對極大化問題，人工變量的系數(shù)為 M 對極小化問題，人工變量的系數(shù)為 M 廣東工業(yè)大學(xué)管理學(xué)院 112 找出初始基可行解 列出初始單純形表 計算檢驗數(shù)j? 所有0?j? 基變量中含非零的人工變量 存在非基變量檢驗數(shù)為零 唯一最優(yōu)解 無可行 解 無窮多最優(yōu)解 對某個0?j? 有0?jP 無界 解 }{m a xjjk?? ? kx為換入變量 設(shè)lkiikikiabaab????????? 0m i n? 則lka為主元素，jx為換出變 量 旋轉(zhuǎn)運算： 經(jīng)矩陣的初等行運算，使主元變?yōu)?1 ，主元列的其它數(shù)變?yōu)榱?，得到新的單純形?