如果您是工科學生或工程師，您就知道優化系統以獲得最佳結果意味著什麼。
優化解決方案是從構建橋樑到製作軟件的一切成功的關鍵。
基本可行解的想法就在此時產生了。
這是線性規劃中的一個基本思想，可以讓您找出一組可能的解決方案中的哪一個是最好的。
但為什麼它如此重要？在本文中，我將討論基本可行的解決方案以及如何使用它們來解決現實世界中的工程問題。
我將討論如何找到它們、它們由什麼製成以及它們為何重要。
因此，無論您是經驗豐富的工程師還是剛起步的學生，都請與我們一起深入了解基本可行解的世界，並向您展示如何使用線性規劃的強大功能。
了解基本可行的解決方案
正式定義：
所有變量均為非負的線性規劃模型的基本解。
基本可行解 (BFS) 是線性規劃中的一個關鍵思想，可幫助找到最佳解。
BFS 是具有盡可能少的非零變量的解決方案。
它是可行解多面體的一個角。
換句話說，BFS 是滿足非負約束並且在可行域或問題域中的基本解。
尋找最優的基本可行解
為了找到最好的 BFS，我們需要做以下事情：
- 以標準形式為線性序列編寫程序。
- 將不等式系統變成增廣矩陣。
- 弄清楚哪些變量是基本的，哪些不是。
- 根據其他變量找出基本變量是什麼。
- 將這些表達式放入目標函數中以獲得僅包含非基本變量的函數。
- 找到一個可以在不破壞任何約束的情況下增加的非基本變量，這將使目標函數更好。
該變量現在是基本變量，其他基本變量之一不再是基本變量。
如果存在最佳解決方案，則它必須位於可能存在解決方案的區域的末端或頂點之一。
因此，如果 LP 有最優解，則它在可行集的極值點處有最優解。
此外，如果存在最優解，則始終存在最優 BFS。
使用單純形法尋找最佳 BFS
單純形法是一種用於解決線性規劃問題的算法。
它通過使用樞軸過程從一個 BFS 移動到“相鄰”BFS。
在主元過程中，選擇一個非基本變量成為基本變量，然後使用當前 BFS 求解新的基本變量。
當不能改變非基本變量以使目標函數更好時，算法就完成了。
為什麼基本可行的解決方案對於解決複雜的工程問題至關重要
還是很難理解？讓我稍微改變一下觀點：
無論如何，誰需要簡單、可行的答案？把一切都放在一起，希望最好的。
畢竟，當混亂如此有趣時，誰還需要優化呢？歡迎來到非負變量的世界，這裡的一切都只是建議，幾乎可以肯定會失敗。
或者是嗎？
讓我們探討為什麼基本可行解決方案看似基本的概念根本不是基本概念，以及為什麼它們可能只是解決最複雜工程問題的關鍵。
好吧，那隻是一個看起來像電視廣告的笑話。
現在讓我們回到解釋。
尋找基本可行的解決方案
基本可行解 (BFS) 是線性優化問題的解，它滿足所有約束並且具有最少數量的非零變量。
從幾何角度看，每個 BFS 都是可行解多面體的一個角。
如果有最佳解決方案，則還必須有最佳第一步。
在本文中，我們將討論如何找到初始基本可行解、如何找到所有基本可行解以及如何找到沒有鬆弛變量的基本可行解。
尋找初步的基本可行方案
我們可以根據問題的設置方式使用不同的方法來找到適用於線性優化問題的初始基本解決方案。
一種方法是將鬆弛變量添加到不等式的約束中，並將所有其他變量設置為零。
鬆弛變量成為基本變量，其餘為非基本變量。
兩相單純形法是解決該問題的另一種方法。
該方法涉及解決額外的線性規劃問題以找到可行的初始基本解決方案。
一旦找到初始的基本可行解，就可以使用單純形法從一個基本可行解移動到下一個，然後移動到最佳解決方案。
尋找所有基本可行的解決方案
可以有不止一種適用於線性程序的基本解決方案。
我們可以通過添加鬆弛變量來改變系統，然後使用新系統來尋找線性規劃的所有基本可行解。
然後，利用這些基本可行解來尋找原問題的基本可行解。
尋找沒有鬆弛變量的基本可行解
我們需要使用鬆弛變量來擺脫小於約束，這樣我們就可以找到一個沒有鬆弛變量的基本解決方案。
鬆弛變量只是約束右側和左側之間的差異。
例如，對於第一個約束，我們定義一個鬆弛變量 x4 = 14 - 2x1 - x2 - x3。就這個新變量而言，第一個約束簡單地等同於 x4 ≥ 0，這是 x4 的正約束。
當我們添加這些鬆弛變量時，我們得到一個與原始程序相同的線性程序，除了所有約束都是方程式或表示某些內容為正的約束。
在基本解中具有非零值的基本變量集稱為基礎。
在基本解中值為零的變量不是基本變量。
為了找到最佳解決方案，我們需要找到滿足所有規則並獲得目標的最大或最小值的向量 x。
但是找到最佳解決方案比僅僅找到一個有效且沒有鬆弛變量的解決方案需要更多的步驟。
並非總能找到沒有鬆弛變量的基本解決方案，尤其是對於小於約束的問題。
要找到基本可行解，需要使用單純形法或其他線性規划算法來尋找滿足所有約束且具有最少非零變量的解。
基本可行解的性質及意義
基本可行解的性質
一個基本可行解最多有 m 個非零變量，至少有 nm 個變量為零，其中 n 是決策變量的數量，m 是約束的數量。
BFS 是可能解多面體的一個角，每個 BFS 都有 n 個線性獨立的活動約束。
如果有最佳解決方案，則還必須有最佳第一步。
基本可行解最重要的是它們是線性規劃問題凸解集的末端。
為了找到最佳答案，單純形算法會經過一系列 BFS。
Simplex Algorithm 以有組織的方式搜索所有基本可能的解決方案，以找到最佳解決方案。
基本可行解的意義
找到可能的基本解決方案很重要，因為它有助於找到線性規劃問題的最佳答案。
它還為複雜算法提供了一個起點，並可用於確定線性程序是否可能。
要找到線性規劃的所有基本可行解，您可以通過添加鬆弛變量來更改系統，然後使用更改後的系統找到所有基本可行解。
然後，利用這些基本可行解來尋找原問題的基本可行解。
視頻：基本可行的解決方案
提示：如果需要，請打開字幕按鈕。如果您不熟悉口語，請在設置按鈕中選擇“自動翻譯”。在您最喜歡的語言可供翻譯之前，您可能需要先點擊視頻的語言。
用例
| 用於： | 描述： |
|---|---|
| 資源分配： | BFS可以用來將有限的資源分配到幾個項目中，做到事半功倍。這種方法可以用於許多不同的領域，如交通、農業和金融。 |
| 網絡優化： | BFS 可用於使通信、運輸和物流網絡更好地工作。BFS 可以幫助找到貨物和服務的最佳路線，減少運輸時間和金錢，並加快和更準確地交付。 |
| 生產計劃： | BFS 可用於計劃生產，以便以最佳方式使用勞動力、原材料和設備等資源，以充分利用它們。BFS 可以幫助降低生產成本、減少浪費並提高效率。 |
| 金融計劃： | 在財務規劃中，BFS 可用於優化投資組合、降低風險並獲得最大的回報。BFS 可以幫助找到最好的資產分配方式，降低交易成本，賺更多的錢。 |
| 供應鏈管理： | 作為供應鏈管理的一部分，BFS 可用於改善從供應商到客戶的商品和服務流。BFS 可以幫助確定手頭的最佳庫存量、縮短交貨時間並改善客戶服務。 |
結論
隨著對基本可行解決方案的了解接近尾聲，很明顯它們是任何工程師或工程專業學生的重要工具。
從找出構建複雜系統的最佳方法到充分利用可用資源，基本可行的解決方案為獲得最佳結果提供了一個框架。
但不僅僅是有用，它們還展示了數學是多麼優雅和美麗。
令人驚奇的是，您可以將復雜的問題歸結為一組簡單的方程式，然後使用這些方程式來解決現實世界中的問題。
這是一個很好的提醒，工程就是解決問題，並且通過使用數學的力量，我們可以找到曾經被認為不可能的答案。
因此，隨著您對工程學的了解越來越多，請牢記您所了解的簡單有效解決方案，並使用它們讓世界變得更美好、更高效。
鏈接和參考
圖書：
- 線性規劃：基礎和擴展
- 線性規劃：理論與應用
分享…
