什么是整數線性規劃(Integer Linear Programming)？
當試圖求解線性系統時，當指定所有未知變量必須是整數時，就會出現整數線性規劃問題，或整數。線性系統是描述程序員試圖找到解決方案的情況的一組方程組。它們通常由一個必須最大化或最小化的方程和一個或多個限制未知變量...
當試圖求解線性系統時，當指定所有未知變量必須是整數時，就會出現整數線性規劃問題，或整數。線性系統是描述程序員試圖找到解決方案的情況的一組方程組。它們通常由一個必須最大化或最小化的方程和一個或多個限制未知變量的限制方程組成。要使系統是線性的，每個限制必須是線性方程，也就是說，它不能包含指數大于1的未知變量的實例。
常規線性系統可以使用計算機很容易地解決。程序可以通過找到導數并將其設置為零。然后，它可以通過檢查函數上的緊鄰來驗證該點是最大值還是最小值。只要在函數的每個點上定義了導數，計算機就只能檢查有限數量的可能解。
線性規劃通過增加整數限制變成整數線性規劃。這意味著問題保持不變，但答案必須由未知值的整數值組成：它們必須是整數。有時，這意味著與分數相比，解將是次優的是允許的；但是，它反映了現實世界，在現實世界中，項目通常以離散的、不可分割的單位出現。這使得整數線性規劃對于商業應用很重要，由于企業希望利潤最大化，但不能選擇銷售一小部分產品。
一旦整數限制到位，求解線性系統的問題就是NP完全問題這意味著計算機求解系統所需的時間是不確定的。在整數限制下，計算機不能使用導數工具，因為不能保證導數的零點落在整數上。解將是在所有的整數，因此計算機必須檢查所有整數，這是一個需要花費無限時間的過程。
程序員開發了啟發式方法，或解決問題的方法，來處理這些問題的復雜性。解決整數線性規劃問題的一種方法是分枝定界算法，計算機解決與原始問題有關的一系列問題，將可用值的范圍縮小到一個解決方案。然而，對于復雜的問題，這可能需要很長時間。
常規線性系統可以使用計算機很容易地解決。程序可以通過找到導數并將其設置為零。然后，它可以通過檢查函數上的緊鄰來驗證該點是最大值還是最小值。只要在函數的每個點上定義了導數，計算機就只能檢查有限數量的可能解。線性規劃通過增加整數限制變成整數線性規劃。這意味著問題保持不變，但答案必須由未知值的整數值組成：它們必須是整數。有時，這意味著與分數相比，解將是次優的是允許的；但是，它反映了現實世界，在現實世界中，項目通常以離散的、不可分割的單位出現。這使得整數線性規劃對于商業應用很重要，由于企業希望利潤最大化，但不能選擇銷售一小部分產品。
一旦整數限制到位，求解線性系統的問題就是NP完全問題這意味著計算機求解系統所需的時間是不確定的。在整數限制下，計算機不能使用導數工具，因為不能保證導數的零點落在整數上。解將是在所有的整數，因此計算機必須檢查所有整數，這是一個需要花費無限時間的過程。
程序員開發了啟發式方法，或解決問題的方法，來處理這些問題的復雜性。解決整數線性規劃問題的一種方法是分枝定界算法，計算機解決與原始問題有關的一系列問題，將可用值的范圍縮小到一個解決方案。然而，對于復雜的問題，這可能需要很長時間。
- 發表于 2020-07-10 16:57
- 閱讀 ( 2271 )
- 分類：電腦網絡
admin
0 篇文章
作家榜 ?
-
xiaonan123
189 文章
-
湯依妹兒
97 文章
-
luogf229
46 文章
-
jy02406749
45 文章
-
小凡
34 文章
-
Daisy萌
32 文章
-
我的QQ3117863681
24 文章
-
華志健
23 文章