# 線性規劃求解
這里主要介紹谷歌的優化工具包(Google Optimization Tools)在線性規劃問題上的求解。
## 安裝
Google官方有提供Python的pypi版本，所以我們可以通過pip很簡單的安裝。
首先，請確認你所使用的Python版本，根據文檔說明，暫僅支持(2.7+, 3.5, or 3.6)。
同時，也需確認所用pip版本高于9.01，可以通過`pip --version`來查看pip的版本號，在必要的情況下，可以通過如下命令行升級pip。
```powershell
python -m pip install pip --upgrade
```
然后就是通過pip安裝OR-Tools。
```powershell
pip install ortools
```
**PS**: 因為該工具包本身是通過C++編寫的，然后再通過SWIG封裝各語言的分發版本，所以在用`help()`函數查看對應類或函數時，會發現其明顯有些不一樣。
## 簡單的示例
在Google的官方文檔中，確實是有一個線性規劃問題求解的示例，但對應剛開始用的人來說有些復雜了，所以我在這邊會用一個更簡單的問題來演示如何使用該工具包。
首先，我們需要求解的問題如下：
![待補圖]()
求解代碼如下：
```python
# 導入OR-Tools
from ortools.linear_solver import pywraplp
# 創建一個線性規劃問題，并命名為'ls'
solver = pywraplp.Solver('ls', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
# 創建待優化的目標函數
objective = solver.Objective()
# 建立變量x1, x2, x3
# 參數分別代表，下線，上限，變量名稱
x1 = solver.NumVar(0, solver.infinity(), 'x1')
x2 = solver.NumVar(0, solver.infinity(), 'x2')
x3 = solver.NumVar(0, solver.infinity(), 'x3')
# 設置變量在目標函數中的參數
objective.SetCoefficient(x1, 2)
objective.SetCoefficient(x2, -1)
objective.SetCoefficient(x3, 1)
# 設置目標函數的優化目標，默認為最小值
# 這里將目標函數的優化目標改為最大值
objective.SetMaximization()
# 創建約束條件
# 參數分別代表， 下限，上限， 約束名稱
c1 = solver.Constraint(-solver.infinity(), 60, 'c1')
# 設置變量在約束中的參數
c1.SetCoefficient(x1, 3)
c1.SetCoefficient(x2, 1)
c1.SetCoefficient(x3, 1)
c2 = solver.Constraint(-solver.infinity(), 10, 'c2')
c2.SetCoefficient(x1, 1)
c2.SetCoefficient(x2, -1)
c2.SetCoefficient(x3, 2)
c3 = solver.Constraint(-solver.infinity(), 20, 'c3')
c3.SetCoefficient(x1, 1)
c3.SetCoefficient(x2, 1)
c3.SetCoefficient(x3, -1)
# 輸出模型
# 對于該模型的輸出結果如下
# \ Generated by MPModelProtoExporter
# \ Name : ls
# \ Format : Free
# \ Constraints : 3
# \ Variables : 3
# \ Binary : 0
# \ Integer : 0
# \ Continuous : 3
# Maximize
# Obj: +2.000000 V0 -1.000000 V1 +1.000000 V2
# Subject to
# C0: +3.000000 V0 +1.000000 V1 +1.000000 V2 <= 60.000000
# C1: +1.000000 V0 -1.000000 V1 +2.000000 V2 <= 10.000000
# C2: +1.000000 V0 +1.000000 V1 -1.000000 V2 <= 20.000000
# Bounds
# 0.000000 <= V0
# 0.000000 <= V1
# 0.000000 <= V2
# End
print(solver.ExportModelAsLpFormat(True))
# 計算該線性規范問題
status = solver.Solve()
# 判斷解的狀態
if status == solver.OPTIMAL:
print('得到最優解')
elif status == solver.FEASIBLE:
print('得到可行解')
else:
print('無可行解')
# 目標函數的值
objective.Value()
# 各變量的解
x1.solution_value()
x2.solution_value()
x3.solution_value()
```
