线性规划求解第一的MindOpt如何使用Python语言的API建模及优化

简介: MindOpt是一款高效的优化算法软件包,求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP),可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章,讲述各个语言如何使用 MindOpt 来求解数学规划问题

本篇文章是系列文章的开篇,下文会分享小编个人线性规划的定义,然后举个一例题,最后将讲述使用 MindOpt Python 语言的 API 来建模以及求解 线性规划问题示例 中的问题以及求解的结果。


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

image.png


在上文的例子,是一个简单的线性规划问题,只有两个决策变量,而线性规划问题示例中的问题涉及到四个决策变量,人工去求最优解呢,需要先把线性规划问题转换为标准形式,然后制表、入基、出基、换基,最后迭代得出最优解,过程比较复杂。


那么我们可以使用商用求解器 MindOpt ,让计算机来帮助我们求解。


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

image.png

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


进阶算例-实际例子算

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


线性规划问题示例:

image.png


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


相关文章
|
人工智能 自然语言处理 测试技术
Apipost智能搜索:只需用业务语言描述需求,就能精准定位目标接口,API 搜索的下一代形态!
在大型项目中,API 数量庞大、命名不一,导致“找接口”耗时费力。传统工具依赖关键词搜索,难以应对语义模糊或命名不规范的场景。Apipost AI 智能搜索功能,支持自然语言查询,如“和用户登录有关的接口”,系统可理解语义并精准匹配目标接口。无论是新人上手、模糊查找还是批量定位,都能大幅提升检索效率,降低协作成本。从关键词到语义理解,智能搜索让开发者少花时间找接口,多专注核心开发,真正实现高效协作。
|
缓存 监控 前端开发
顺企网 API 开发实战:搜索 / 详情接口从 0 到 1 落地(附 Elasticsearch 优化 + 错误速查)
企业API开发常陷参数、缓存、错误处理三大坑?本指南拆解顺企网双接口全流程,涵盖搜索优化、签名验证、限流应对,附可复用代码与错误速查表,助你2小时高效搞定开发,提升响应速度与稳定性。
|
Java 测试技术 API
Java Stream API:被低估的性能陷阱与优化技巧
Java Stream API:被低估的性能陷阱与优化技巧
701 114
|
存储 JavaScript Java
(Python基础)新时代语言!一起学习Python吧!(四):dict字典和set类型;切片类型、列表生成式;map和reduce迭代器;filter过滤函数、sorted排序函数;lambda函数
dict字典 Python内置了字典:dict的支持,dict全称dictionary,在其他语言中也称为map,使用键-值(key-value)存储,具有极快的查找速度。 我们可以通过声明JS对象一样的方式声明dict
701 2
|
算法 Java Docker
(Python基础)新时代语言!一起学习Python吧!(三):IF条件判断和match匹配;Python中的循环:for...in、while循环;循环操作关键字;Python函数使用方法
IF 条件判断 使用if语句,对条件进行判断 true则执行代码块缩进语句 false则不执行代码块缩进语句,如果有else 或 elif 则进入相应的规则中执行
1869 1
|
存储 Java 索引
(Python基础)新时代语言!一起学习Python吧!(二):字符编码由来;Python字符串、字符串格式化;list集合和tuple元组区别
字符编码 我们要清楚,计算机最开始的表达都是由二进制而来 我们要想通过二进制来表示我们熟知的字符看看以下的变化 例如: 1 的二进制编码为 0000 0001 我们通过A这个字符,让其在计算机内部存储(现如今,A 字符在地址通常表示为65) 现在拿A举例: 在计算机内部 A字符,它本身表示为 65这个数,在计算机底层会转为二进制码 也意味着A字符在底层表示为 1000001 通过这样的字符表示进行转换,逐步发展为拥有127个字符的编码存储到计算机中,这个编码表也被称为ASCII编码。 但随时代变迁,ASCII编码逐渐暴露短板,全球有上百种语言,光是ASCII编码并不能够满足需求
515 4
|
JSON 监控 API
Shopee:对接海外仓API实现本地发货,优化物流时效
Shopee卖家可通过对接海外仓API实现本地发货,将物流时效从10-15天缩短至3-5天,显著提升买家体验与店铺转化率。本文详解API对接原理、步骤及代码示例,助力优化跨境物流效率。
|
JSON 监控 API
亚马逊:调用跨境物流API追踪国际包裹清关状态,优化时效
在亚马逊跨境运营中,清关不确定性常导致物流延误。通过调用跨境物流API(如Amazon SP-API),可自动化获取包裹清关状态与预计交付时间,提升响应效率。本文详解API调用步骤,提供Python代码示例,并分享实时监控、预警机制与数据优化策略,助力卖家缩短处理时间、提升客户满意度,实现高效智能的国际物流管理。
|
并行计算 算法 调度
【微电网优化】基于吸血水蛭优化器(BSLO)的微电网优化研究(Matlab代码实现)
【微电网优化】基于吸血水蛭优化器(BSLO)的微电网优化研究(Matlab代码实现)
316 3

热门文章

最新文章

推荐镜像

更多