线性规划
維基百科,自由的 encyclopedia
在數學中,線性規劃(英語:Linear Programming,簡稱LP)特指目標函數和約束條件皆為線性的最佳化問題。
線性規劃是最優化問題中的一個重要領域。在作業研究中所面臨的許多實際問題都可以用線性規劃來處理,特別是某些特殊情況,例如:網路流、多商品流量等問題,都被認為非常重要。目前已有大量針對線性規劃演算法的研究。很多最佳化問題算法都可以分解為線性規劃子問題,然後逐一求解。在線性規劃的歷史發展過程中所衍伸出的諸多概念,建立了最優化理論的核心思維,例如「對偶」、「分解」、「凸集」的重要性及其一般化等。在微观经济学和商业管理领域中,线性规划亦被大量应用于例如降低生产过程的成本等手段,最終提升產值與營收。對線性規劃有早期貢獻的列昂尼德·维塔利耶维奇·康托罗维奇和特亚林·科普曼斯於1975年共同獲得諾貝爾經濟學獎。