單純形法的原理如下:
首先設法找到壹個(初始)基可行解,然後再根據最優性理論判斷這個基可行解是否最優解。若是最優解,則輸出結果,計算停止。
若不是最優解,則設法由當前的基可行解產生壹個目標值更優的新的基可行解,再利用最優性理論對所得的新基可行解進行判斷,看其是否最優解,這樣就構成壹個叠代算法。
由於基可行解只有有限個,而每次目標值都有所改進,因而必可在有限步內終止。如果原問題確有最優解,必可在有限步內達到,且計算量大大少於窮舉法;若原問題無最優解,也可根據最優性理論及時發現,停止計算,避免錯誤及無效運算。"
單純形法是求解線性規劃問題最常用、最有效的算法之壹。單純形法最早由 George Dantzig於1947年提出,近70年來,雖有許多變形體已經開發,但卻保持著同樣的基本觀念。如果線性規劃問題的最優解存在,則壹定可以在其可行區域的頂點中找到。
基於此,單純形法的基本思路是:先找出可行域的壹個頂點,據壹定規則判斷其是否最優;若否,則轉換到與之相鄰的另壹頂點,並使目標函數值更優;如此下去,直到找到某最優解為止 。