# 线性规划求解
这里主要介绍谷歌的优化工具包(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()
```
