本篇文章是系列文章的开篇，下文会分享小编个人线性规划的定义，然后举个一例题，最后将讲述使用 MindOpt Python 语言的 API 来建模以及求解 线性规划问题示例 中的问题以及求解的结果。
MindOpt Python、C、C++语言求解LP、MILP、QP问题系列
- Python: 线性规划LP问题(本篇)、混合整数线性规划MILP问题、二次规划QP问题
- C : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C++ : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
安装MindOpt
用户可以点这里下载安装MindOpt优化求解器，免费的。找不到安装步骤点这里。
(官网https://opt.aliyun.com有更多信息等着您哟!)
线性规划
我们先介绍一下线性规划，我个人认为是在线性的目标和约束中，找出一个最优解(如最大利润或最低成本)。线性规划可以广泛的应用在我们的生活中，解决资源利用、人力调配、生产安排等问题。
入门案例
一位员工每天要负责处理a任务(生成零部件) 和b任务(组装产品)。其参与a任务的报酬为100元/小时，b任务的报酬为150元/小时。工厂要求该员工每天在每个任务上花费至少 3 个小时。已知该员工每天工作8小时（因此在 6 小时之外，可以自行决定 2 小时如何工作），那么他该如何在两项任务上分配时间以得到尽可能多的报酬？
- 以上问题可以被称为任务分配问题，也可以被视为一个简单的排产排程问题，由于该员工要决策时间分配，我们引入决策变量 Xa和 Xb用于表示该工人投入在任务和任务中的时长。由问题描述可知，这些变量需要满足Xa+Xb=8 和 Xa>=3,Xb>=3。
- 此外，该工人的目标是获得尽可能多的报酬。在定义如上三要素后，我们可以建立如下的数学规划问题：
- 决策变量: Xa,Xb
- 目标函数: maxmize 100Xa + 150Xb
- 约束: s.t. Xa + Xb = 8
- Xa>=3 , Xb>=3
- 这个列题最后求出的最优解是每天参与a任务三小时、b任务5小时。
在上文的例子，是一个简单的线性规划问题，只有两个决策变量，而线性规划问题示例中的问题涉及到四个决策变量，人工去求最优解呢，需要先把线性规划问题转换为标准形式，然后制表、入基、出基、换基，最后迭代得出最优解，过程比较复杂。
那么我们可以使用商用求解器 MindOpt ，让计算机来帮助我们求解。
线性规划问题可以用以下数学公式来描述：
公式参考自：https://solver.damo.alibaba.com/doc/html/model/lp/linear%20problem.html
进阶算例-实际例子算
要找到一个和线性规划问题示例中的问题相匹配的文字列题比较困难，所以我们在这里做一个假设，把它当成是一个人力调配的问题，求解的是一个目标函数的最小值，也就是花费最低成本去解决问题。
线性规划问题示例：
Python+MindOpt代码实现
# 引入python包 from mindoptpy import * if __name__ == "__main__": MDO_INFINITY = MdoModel.get_infinity() # Step 1.创建模型并更改参数。 model = MdoModel() try: # Step 2. 输入模型。 # 改为最小化问题。 # 通过 mindoptpy.MdoModel.set_int_attr() 将目标函数设置为 最小化 model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1) # 添加变量。 # 通过mindoptpy.MdoModel.add_var() 来添加四个优化变量， # 定义其下界、上界、名称和类型。 x = [] x.append(model.add_var(0.0, 10.0, 1.0, None, "x0", False)) x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x1", False)) x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x2", False)) x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x3", False)) # 添加约束。 # 注意这里的非零元素是按行顺序输入的。 model.add_cons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0") model.add_cons(1.0, 1.0, 1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], "c1") # Step 3. 解决问题并填充结果。 # 调用 mindoptpy.MdoModel.solve_prob() 求解优化问题， # 并用 mindoptpy.MdoModel.display_results() 来查看优化结果 model.solve_prob() model.display_results() # 调用 mindoptpy.MdoModel.get_status() 来检查求解器的优化状态， # 并通过 mindoptpy.MdoModel.get_real_attr() 和 # mindoptpy.MdoVar.get_real_attr() 来获取目标值和最优解。 status_code, status_msg = model.get_status() if status_msg == "OPTIMAL": print("Optimizer terminated with an OPTIMAL status (code {0}).".format(status_code)) print("Primal objective : {0}".format(round(model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL), 2))) for curr_x in x: print(" - x[{0}] : {1}".format(curr_x.get_index(), round(curr_x.get_real_attr(MDO_REAL_ATTR.PRIMAL_SOLN), 2))) else: print("Optimizer terminated with a(n) {0} status (code {1}).".format(status_msg, status_code)) # 如果求解异常，在这里将会看见它的状态码和错误原因 except MdoError as e: print("Received Mindopt exception.") print(" - Code : {}".format(e.code)) print(" - Reason : {}".format(e.message)) except Exception as e: print("Received exception.") print(" - Reason : {}".format(e)) finally: # Step 4. 释放模型。 # 调用 mindoptpy.MdoModel.free_mdl() 来释放内存 # (多次运行部分脚本的时候有些变量已经被用，所以调用这个api进行清除) model.free_mdl()
MindOpt求解的结果
# 模型摘要 Model summary. - Num. variables : 4 - Num. constraints : 2 - Num. nonzeros : 7 - Bound range : [1.0e+00,1.0e+01] #限制范围 - Objective range : [1.0e+00,1.0e+00] #目标范围 - Matrix range : [1.0e+00,6.0e+00] #矩阵范围 Presolver started. Presolver terminated. Time : 0.001s Simplex method started. Iteration Objective Dual Inf. Primal Inf. Time 0 0.00000e+00 0.0000e+00 1.0000e+00 0.00s 2 4.00000e-01 0.0000e+00 0.0000e+00 0.01s Postsolver started. Simplex method terminated. Time : 0.004s # 决策变量的最佳取值 Optimizer terminated with an OPTIMAL status (code 1). Primal objective : 0.4 - x[0] : 0.0 - x[1] : 0.0 - x[2] : 0.2 - x[3] : 0.2 # 展示了使用的单纯形法，优化器的状态，优化使用的时间 Optimizer summary. - Optimizer used : Simplex method - Optimizer status : OPTIMAL - Total time : 0.005s # 目标函数的实现 Solution summary. Primal solution - Objective : 4.0000000000e-01
联系我们
钉钉：damodi
邮箱地址：solver.damo@list.alibaba-inc.com
