單純性算法

其基本原理及主要步驟是：首先設法找到一個（初始）基可行解，然後再根據最優性理論判斷這個基可行解是否最優解。若是最優解，則輸出結果，計算停止。

概述

單純形法是一種疊代算法

原理

若不是最優解，則設法由當前的基可行解產生一個目標值更優的新的基可行解，再利用最優性理論對所得的新基可行解進行判斷，看其是否最優解，這樣就構成一個疊代算法。由於基可行解只有有限個，而每次目標值都有所改進，因而必可在有限步內終止。如果原問題確有最優解，必可在有限步內達到，且計算量大大少於窮舉法；若原問題無最優解，也可根據最優性理論及時發現，停止計算，避免錯誤及無效運算。
是20世紀十大經典算法之一