线性规划问题在生活中一般会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题，下文我们也将讲述一个排产排程的例子，求最大经济效益问题，但我们今天要重点展示的是使用MindOpt C++ 语言的 API 来建模以及求解一个目标函数最小化的算例(比如风险最小化、资源利用)。
MindOpt Python、C、C++语言求解LP、MILP、QP问题系列
- Python: 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C++ : 线性规划LP问题(本篇)、混合整数线性规划MILP问题、二次规划QP问题
线性规划
线性规划问题我个人认为是在线性的目标和约束中，找出一个最优解(如最大利润或最低成本)。线性规划可以广泛的应用在我们的生活中，解决资源利用、人力调配、生产安排等问题。
线性规划问题可以用以下数学公式来描述：
公式参考自：https://solver.damo.alibaba.com/doc/html/model/lp/linear%20problem.html
入门案例
一位员工每天要负责处理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
进阶算例
在上文的例子，是一个简单的线性规划问题，只有两个决策变量，一个约束条件，而下文线性规划问题示例中的问题涉及到四个决策变量，两个约束条件，人工去求最优解呢，需要先把线性规划问题转换为标准形式，然后制表、入基、出基、换基，最后迭代得出最优解，过程比较复杂，那么我们可以使用商用求解器 MindOpt ，让计算机来帮助我们求解。
数学算例比较抽象，但要找到一个和线性规划问题示例中的问题相匹配的文字列题比较困难，所以我们在这里做一个假设，把它当成是一个人力调配的问题，求解的是一个目标函数的最小值，也就是花费最低成本去解决问题。
我们把上述的假设带入下文的数学算例，用MindOpt优化求解器进行求解。
线性规划问题示例：
MindOpt + C++语言的建模与优化
核心使用的几个APIs是：
MdoModel model; model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES); model.addCons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0"); model.addCons(1.0, 1.0, 1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], "c1"); model.solveProb(); model.displayResults();
下面是完整的例子，可复制存为MdoLoEx1.cpp文件。/**/里是小编的注释
/*引入头文件*/ using namespace mindopt; int main(void) { /*------------------------------------------------------------------*/ /* Step 1. 创建模型并更改参数。 */ /*------------------------------------------------------------------*/ /* 创建一个空模型。 */ MdoModel model; try { /*------------------------------------------------------------------*/ /* Step 2. 输入模型。 */ /*------------------------------------------------------------------*/ /* 通过 mindopt::MdoModel::setIntAttr() 将目标函数设置为 最小化 */ model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES); /* 调用 mindopt::MdoModel::addVar() 来添加四个优化变量， 定义其下界、上界、名称和类型 */ std::vector<MdoVar> x; x.push_back(model.addVar(0.0, 10.0, 1.0, "x0", MDO_NO)); x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x1", MDO_NO)); x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x2", MDO_NO)); x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x3", MDO_NO)); /* 调用 model.addCons() 来添加约束。 */ model.addCons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0"); model.addCons(1.0, 1.0, 1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], "c1"); /*------------------------------------------------------------------*/ /* Step 3. 解决问题并填充结果。 */ /*------------------------------------------------------------------*/ /* 调用 mindopt::MdoModel::solveProb() 求解优化问题， 并通过 mindopt::MdoModel::displayResults() 查看优化结果 */ model.solveProb(); model.displayResults(); } catch (MdoException & e) { std::cerr << "===================================" << std::endl; std::cerr << "Error : code <" << e.getResult() << ">" << std::endl; std::cerr << "Reason : " << model.explainResult(e.getResult()) << std::endl; std::cerr << "===================================" << std::endl; return static_cast<int>(e.getResult()); } return static_cast<int>(MDO_OKAY); }
如何编译及运行MdoLoEx1.cpp文件
linux和Mac系统直接在命令行输入以下代码
cd <MDOHOME>/<VERSION>/examples/CPP make -f Makefile all ./MdoLoEx1
windows系统本例是在Visual Studio上运行，版本为2019；c++和c的操作步骤大体是一致的只需要修改library文件和添加 .cpp 文件。
运行MdoLoEx1.cpp文件后，得到求解的结果如下所示，/**/号里面是小编的注释
Concurrent optimization started. /*并发优化*/ - Num. threads : 2 - Num. optimizers : 2 - Registered optimizers. + : Simplex method (1 thread, enabled output) + : Interior point method (1 thread, disabled output) 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.05s 2 4.00000e-01 0.0000e+00 0.0000e+00 0.06s Postsolver started. Simplex method terminated. Time : 0.036s Concurrent optimization terminated. Optimizer summary. - Optimizer used : Simplex method - Optimizer status : OPTIMAL - Total time : 0.085s Solution summary. Primal solution - Objective : 4.0000000000e-01 /*目标函数最优解*/
下载安装
用户可以点这里下载安装MindOpt优化求解器，找不到安装步骤点这里。
(官网https://opt.aliyun.com有更多信息等着您哟!)
联系我们
钉钉：damodi
邮箱地址：solver.damo@list.alibaba-inc.com
