線性規(guī)劃初始可行基的選擇

1、高文鋒12數(shù)基班 126160031單純形法1.概念2.基本思想3.求解步驟 單純形法是在高斯消去法的基礎(chǔ)上,發(fā)展為求解變量數(shù)多于方程數(shù),并且使目標函數(shù)值優(yōu)化的方法.返回 單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進行。因基本可行解的個數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。 返回 單純形法的一般解題步驟可歸納如下：把線性規(guī)劃問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。若基本可行解不存在，即約束條件有矛盾，則問題無解。若基本可行解存在，從初始基本可

2、行解作為起點，根據(jù)最優(yōu)性條件和可行性條件， 引入非基變量取代某一基變量，找出目標函數(shù)值更優(yōu)的另一基本可行解。按步驟3進行迭代,直到對應(yīng)檢驗數(shù)滿足最優(yōu)性條件（這時目標函數(shù)值不能再改善），即得到問題的最優(yōu)解。若迭代過程中發(fā)現(xiàn)問題的目標函數(shù)值無界，則終止迭代。 返回加人工變量大M法: 在一個線性規(guī)劃問題的約束條件中加入人工變量后,要求人工變量對目標函數(shù)取值不受影響,為此假定人工變量在目標函數(shù)中的系數(shù)(M)(M為任意大的正數(shù)),這樣目標函數(shù)要實現(xiàn)最小化時,必須把人工變量從基變量換出兩階段法: 第一階段:不考慮原問題是否存在基可行解;給原線性規(guī)劃問題加入人工變量,并構(gòu)造僅含人工變量的目標函數(shù)和要求實現(xiàn)最

3、小化. 第二階段:將第一階段計算得到的最終表,除去人工變量.將目標函數(shù)行的系數(shù),換回原問題的目標函數(shù)系數(shù),作為第二階段的計算初始表初始表-31100MM3-4120-1103/2M1-20100011-3+6M1-M1 -3M0M00 最終表-341001/3-2/32/3-5/3110100-11-2 190012/3-4/34/3-7/3 0001/31/3M-1/3M-2/3 不加人工變量 利用這種確定初始可行基的方法求解線性規(guī)劃問題時，首先，對線性規(guī)劃模型(1)的系數(shù)增廣矩陣進行上述的初等行變換而得到rxr階的初始可行基(rm)，接著將所得初始可行基安排入單純形表，然后，進行單純形表的表上作業(yè)程序-31100b0123001-24110100-1 11-20100 -10001 -341001/3-2/3 110100-1 190012/3-4/3 0001/31/3 不加人工變量方法的優(yōu)勢在于思路清晰，方法簡明在運用單純形法時不需要判斷選擇兩階段法或大M法等，只要借助于線性代數(shù)的初等行變換及在以單位陣為初始基的單純形法就可以順利地求解任何線性規(guī)劃模型。對于線性規(guī)