下文我们将讲述小编对线性规划的理解以及展示两个算例，和使用 MindOpt C 语言的 API 来建模以及求解 线性规划示例 中的问题。
(线性规划定义、算数例题都是与前文Python语言的线性规划问题是一致的，已经阅读了前文可以忽略，直接点击目录进阶算例阅读建模优化代码。)
MindOpt Python、C、C++语言求解LP、MILP、QP问题系列
- Python: 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C : 线性规划LP问题(本篇)、混合整数线性规划MILP问题、二次规划QP问题
- C++ : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
安装
用户可以点这里下载安装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
进阶算例
要找到一个和线性规划问题示例中的问题相匹配的文字列题比较困难，所以我们在这里做一个假设，把它当成是一个人力调配的问题，求解的是一个目标函数的最小值，也就是花费最低成本去解决问题。
接下来把上述的问题带入下文的数学算例，用MindOpt优化求解器进行求解。
线性规划问题示例：
MindOpt+c语言的建模与优化
核心使用的几个APIs是：
MDO_CHECK_CALL(Mdo_createMdl(&model)) MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES)) MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0")); MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0, 3, row2_idx, row2_val, "c1")); MDO_CHECK_CALL(Mdo_solveProb(model)); Mdo_displayResults(model);
#关于更多API的详细使用方式，请参考 C 接口函数
下面是完整的例子，可复制存为MdoLoEx1.c文件。
/*引入头文件*/ /* 检查返回码的宏 */ int main(void) { /* 变量 */ char str[1024] = { "\0" }; MdoMdl * model = NULL; MdoResult code = MDO_OKAY; MdoStatus status = MDO_UNKNOWN; const int row1_idx[] = { 0, 1, 2, 3 }; const double row1_val[] = { 1.0, 1.0, 2.0, 3.0 }; const int row2_idx[] = { 0, 2, 3 }; const double row2_val[] = { 1.0, -1.0, 6.0 }; /*------------------------------------------------------------------*/ /* Step 1. 创建模型并更改参数。 */ /*------------------------------------------------------------------*/ /* 创建一个空模型。 */ MDO_CHECK_CALL(Mdo_createMdl(&model)); /*------------------------------------------------------------------*/ /* Step 2. 输入模型。 */ /*------------------------------------------------------------------*/ /* 改成最小化问题。 */ /*通过 Mdo_setIntAttr() 将目标函数设置为 最小化*/ MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES)); /* 添加变量。 */ /*调用 Mdo_addCol() 来添加四个优化变量，定义其下界、上界、名称和类型*/ MDO_CHECK_CALL(Mdo_addCol(model, 0.0, 10.0, 1.0, 0, NULL, NULL, "x0", MDO_NO)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x1", MDO_NO)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x2", MDO_NO)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x3", MDO_NO)); /* 添加约束。 * 请注意，这里的非零元素是按行顺序输入的。 * 调用 Mdo_addRow() 将输入约束 */ MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0")); MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0, 3, row2_idx, row2_val, "c1")); /*------------------------------------------------------------------*/ /* Step 3. 解决问题并填充结果。 */ /*------------------------------------------------------------------*/ /* 解决问题。 */ /*调用 Mdo_solveProb() 求解优化问题，并通过 Mdo_displayResults() 查看优化结果*/ MDO_CHECK_CALL(Mdo_solveProb(model)); Mdo_displayResults(model); /*------------------------------------------------------------------*/ /* Step 4. 释放模型。 */ /*------------------------------------------------------------------*/ /* Free the model. */ Mdo_freeMdl(&model); return (int)code; }
MindOpt求解的结果
如何运行MdoLoEx1.c文件
windows系统本例是在Visual Studio上运行，版本为2019
#运行文件放在“源文件”下，图片被挡住了不好意思。
*linux和mac系统 在命令行输入 cd <MDOHOME>/<VERSION>/examples/C make -f Makefile all ./MdoLoEx1
运行MdoLoEx1.c文件后，得到求解的结果如下所示，/**/号里面是小编的注释
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.000s Simplex method started. /*使用单纯形法*/ Model fingerprint: ==gZ3B2djdXZ 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.00s Postsolver started. Simplex method terminated. Time : 0.002s Concurrent optimization terminated. /*求解器最终选择的优化方法以及求解消耗的时间*/ 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
