备案控制台
探索云世界
开发者社区 达摩院 MindOpt 优化 文章 正文

C语言如何使用MindOpt建模并求解线性规划问题

2022-12-07 415
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： MindOpt是达摩院决策智能实验室研究的一款优化求解器，能帮助做方案设计、生产方案优化、资源合理分配、辅助决策等。可以支持命令行、c、c++、java和python调用，目前求解算法实现了线性规划、混合整数线性规划、二次规划。

下文我们将讲述小编对线性规划的理解以及展示两个算例，和使用 MindOpt C 语言的 API 来建模以及求解 线性规划示例 中的问题。

(线性规划定义、算数例题都是与前文Python语言的线性规划问题是一致的，已经阅读了前文可以忽略，直接点击目录进阶算例阅读建模优化代码。)


MindOpt Python、C、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小时。

image.png

在上文的例子，是一个简单的线性规划问题，只有两个决策变量，而线性规划问题示例中的问题涉及到四个决策变量，人工去求最优解呢，需要先把线性规划问题转换为标准形式，然后制表、入基、出基、换基，最后迭代得出最优解，过程比较复杂，那么我们可以使用商用求解器 MindOpt ，让计算机来帮助我们求解。

线性规划问题可以用以下数学公式来描述：

image.png

公式参考自：https://solver.damo.alibaba.com/doc/html/model/lp/linear%20problem.html

进阶算例

要找到一个和线性规划问题示例中的问题相匹配的文字列题比较困难，所以我们在这里做一个假设，把它当成是一个人力调配的问题，求解的是一个目标函数的最小值，也就是花费最低成本去解决问题。

接下来把上述的问题带入下文的数学算例，用MindOpt优化求解器进行求解。

线性规划问题示例：

image.png

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文件。

#include <stdio.h>/*引入头文件*/#include "Mindopt.h"/* 检查返回码的宏 */#define MDO_CHECK_CALL(MDO_CALL)                                    \code = MDO_CALL;                                                \if (code != MDO_OKAY)                                           \{                                                               \Mdo_explainResult(model, code, str);                        \Mdo_freeMdl(&model);                                        \fprintf(stderr, "===================================\n");   \fprintf(stderr, "Error   : code <%d>\n", code);             \fprintf(stderr, "Reason  : %s\n", str);                     \fprintf(stderr, "===================================\n");   \return (int)code;                                           \}intmain(void)
{
/* 变量 */charstr[1024] = { "\0" };
MdoMdl*model=NULL;
MdoResultcode=MDO_OKAY;
MdoStatusstatus=MDO_UNKNOWN;
constintrow1_idx[] = { 0,   1,   2,   3   };
constdoublerow1_val[] = { 1.0, 1.0, 2.0, 3.0 };
constintrow2_idx[] = { 0,    2,   3   };
constdoublerow2_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/Cmake-fMakefileall./MdoLoEx1

运行MdoLoEx1.c文件后，得到求解的结果如下所示，/**/号里面是小编的注释

Concurrentoptimizationstarted. /*并发优化开始*/-Num. threads       : 2-Num. optimizers    : 2-Registeredoptimizers.
+                  : Simplexmethod (1thread, enabledoutput)
+                  : Interiorpointmethod (1thread, disabledoutput)
Modelsummary.
-Num. variables     : 4-Num. constraints   : 2-Num. nonzeros      : 7-Boundrange        : [1.0e+00,1.0e+01]  /*限制范围*/-Objectiverange    : [1.0e+00,1.0e+00]       /*目标范围*/-Matrixrange       : [1.0e+00,6.0e+00]       /*矩阵范围*/Presolverstarted.
Presolverterminated. Time : 0.000sSimplexmethodstarted.                     /*使用单纯形法*/Modelfingerprint: ==gZ3B2djdXZIterationObjectiveDualInf.     PrimalInf.     Time00.00000e+000.0000e+001.0000e+000.00s24.00000e-010.0000e+000.0000e+000.00sPostsolverstarted.
Simplexmethodterminated. Time : 0.002sConcurrentoptimizationterminated. /*求解器最终选择的优化方法以及求解消耗的时间*/Optimizersummary.
-Optimizerused     : Simplexmethod/*单纯形法*/-Optimizerstatus   : OPTIMAL-Totaltime         : 0.005sSolutionsummary.       Primalsolution/*目标函数最优解*/-Objective          : 4.0000000000e-01

联系我们

钉钉群号：32451444

邮箱地址：solver.damo@list.alibaba-inc.com

更多更新通知：https://solver.damo.alibaba.com

文章标签：
C++
C语言
Python
达摩院
API
关键词：
优化求解器建模
优化求解器线性规划
优化求解器建模线性规划
决策智能Lab_运营小编003
目录
相关文章
决策智能Lab_运营小编003
|
4月前
|
人工智能 自然语言处理 达摩院
MindOpt 云上建模求解平台：多求解器协同优化
数学规划是一种数学优化方法，主要是寻找变量的取值在特定的约束情况下，使我们的决策目标得到一个最大或者最小值的决策。
决策智能Lab_运营小编003
100 0
决策智能Lab_运营小编003
|
8月前
|
存储 达摩院
「达摩院MindOpt」线性规划用于排程排程问题（02）
排产排程、原料采购、仓储存放等是制造业降本增效的关键问题。
决策智能Lab_运营小编003
113 1
「达摩院MindOpt」线性规划用于排程排程问题（02）
决策智能Lab_运营小编003
|
7月前
|
存储 达摩院
「达摩院MindOpt」线性规划用于排程排程问题（03）
比上一篇问题02中，我们只考虑了一次性的采购和生产计划，实际中的排产排程问题要更加复杂和精细。例如，我们要考虑未来三个月内采购和排产排程计划。其中，原材料每个月的采买价格均有不同，并且原材料购买后的存储也需要成本开销。在本节中，我们将考虑这样一个相对复杂的排产排程的决策问题。
决策智能Lab_运营小编003
188 0
「达摩院MindOpt」线性规划用于排程排程问题（03）
决策智能Lab_运营小编003
|
3月前
MindOpt APL建模语言自定小义函数的重要性和示例
在编程和建模语言中，函数是一段独立的、可重复使用的代码块，用于执行特定任务。在MindOpt APL中，自定义函数的使用非常重要，因为它们提高了建模过程的效率、可读性和灵活性。
决策智能Lab_运营小编003
38 0
决策智能Lab_运营小编003
|
4月前
|
人工智能 算法 决策智能
MindOpt云上建模求解平台功能的简单介绍
MindOpt云上建模求解平台是阿里巴巴达摩院研发的一款“优化领域”的云平台。它结合了最新的算法研究和云技术，为用户提供了一个易于使用的界面和强大的后台计算能力。该平台支持广泛的优化问题，包括线性规划、整数规划、非线性规划和混合整数规划等。
决策智能Lab_运营小编003
104 0
决策智能Lab_运营小编003
|
9月前
|
达摩院 调度
使用达摩院MindOpt优化交通调度_最大化通行量—线性规划问题
在数学规划中，网络流问题是指一类基于网络模型的流量分配问题。网络流问题的目标是在网络中分配资源，使得网络的流量满足一定的限制条件，并且使得某些目标函数最小或最大化。网络流问题通常涉及一个有向图，图中每个节点表示一个资源，每条边表示资源之间的关系。边上有一个容量值，表示该边上最多可以流动的资源数量。流量从源节点开始流出，经过一系列中间节点，最终到达汇节点。在这个过程中，需要遵守一定的流量守恒和容量限制条件。
决策智能Lab_运营小编003
123 0
决策智能Lab_运营小编003
|
5月前
|
达摩院 数据格式 索引
「达摩院MindOpt APL 建模语言」语法说明 print 将结果写表格文件
不同的编程语言写入表格文件的方式均不相同，下面将展示MindOpt APL建模语言的方式。
决策智能Lab_运营小编003
54 1
决策智能Lab_运营小编003
|
5月前
|
API Python
MindOpt V1.0优化种植计划问题，新的建模方法
种植计划是指农业生产中针对不同农作物的种植时间、面积和种植方式等方面的规划安排。根据具体情况进行合理的规划和安排，以实现农作物的高产、优质和可持续发展。
决策智能Lab_运营小编003
68 0
MindOpt V1.0优化种植计划问题，新的建模方法
半颗糖也甜入人心
|
11月前
|
Python
MindOpt有关于Python的建模与优化
MindOpt有关于Python的建模与优化
半颗糖也甜入人心
58 0
决策智能Lab_运营小编003
|
3月前
|
达摩院 开发者 容器
「达摩院MindOpt」优化形状切割问题（MILP）
在制造业，高效地利用材料不仅是节约成本的重要环节，也是可持续发展的关键因素。无论是在金属加工、家具制造还是纺织品生产中，原材料的有效利用都直接影响了整体效率和环境影响。
决策智能Lab_运营小编003
79 0
「达摩院MindOpt」优化形状切割问题（MILP）

达摩院 MindOpt 优化

热门文章

最新文章

  • 1
    阿里达摩院MindOpt优化求解器-月刊（2024年3月）
  • 2
    MindOpt APL 最新版本功能介绍，并且开放下载使用了！
  • 3
    阿里达摩院MindOpt优化求解器-月刊（2024年2月）
  • 4
    SQL优化器原理 - Auto Hash Join
  • 5
    PostgreSQL 9.6 并行计算 优化器算法浅析
  • 6
    MySQL · 捉虫动态 · order by limit 造成优化器选择索引错误
  • 7
    浅析Oracle 10gR2中优化器对表关联的优化
  • 8
    使用智能优化器提高Oracle的性能极限
  • 9
    【CBO Optimizer优化器】IX_SEL索引选择率
  • 10
    PolarDB-X 面向 HTAP 的 CBO 优化器
  • 1
    阿里达摩院MindOpt优化求解器-月刊（2024年3月）
    61
  • 2
    MindOpt APL 最新版本功能介绍，并且开放下载使用了！
    29
  • 3
    了解MindOpt优化求解器的各种调用方式、方法
    38
  • 4
    阿里达摩院MindOpt优化求解器-月刊（2024年2月）
    94
  • 5
    阿里达摩院MindOpt优化求解器-月刊（2024年1月）
    88
  • 6
    如何通过阿里达摩院MindOpt获得MILP多个解
    100
  • 7
    阿里达摩院MindOpt求解器V1.1新增C#接口
    140
  • 8
    「达摩院MindOpt」优化形状切割问题（MILP）
    79
  • 9
    「达摩院MindOpt」优化FlowShop流水线作业排班问题
    53
  • 10
    MindOpt APL建模语言自定小义函数的重要性和示例
    38

    • 相关课程

    更多
  • C语言学习教程
  • 你的第一门C语言课
  • 【算法实战】15. 利用SVD来简化数据
  • 【算法实战】8. 集成方法-Adaboost
  • 【算法实战】5. Logistic回归算法
  • 【算法实战】9. 线性回归算法

    • 相关电子书

    更多
  • 阿里技术专家一挃：MongoDB 优化器 & 执行器介绍
  • 典型模型-卷积神经网络入门
  • 典型模型-卷积神经网络入门 从概念原理到应用实现

    • 相关实验场景

    更多
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）