• 运筹系列86：MIP问题的建模tips

    1. Either-or constraint

    添加辅助变量y。
    比如
    Either 3 x 1 + 2 x 2 ≤ 18 3x_1+2x_2 \le 18 3x1​+2x2​≤18
    or x 1 + 4 x 2 ≤ 16 x_1+4x_2 \le 16 x1​+4x2​≤16

    可以用

    3 x 1 + 2 x 2 ≤ 18 + M y 3x_1+2x_2 \le 18+My 3x1​+2x2​≤18+My
    x 1 + 4 x 2 ≤ 16 + M ( 1 − y ) x_1+4x_2 \le 16+M(1-y) x1​+4x2​≤16+M(1−y)
    来代替。

    2. k out of N constraints must hold

    类似上面，添加辅助变量 y 1 y_1 y1​～ y N y_N yN​
    从
    f 1 ( . . . ) ≤ d 1 f_1(...)\le d_1 f1​(...)≤d1​
    …
    f N ( . . . ) ≤ d N f_N(...)\le d_N fN​(...)≤dN​

    变为

    f 1 ( . . . ) ≤ d 1 + M y 1 f_1(...)\le d_1+My_1 f1​(...)≤d1​+My1​
    …
    f N ( . . . ) ≤ d N + M y N f_N(...)\le d_N+My_N fN​(...)≤dN​+MyN​
    Σ 1 N y i = N − k , y i \Sigma_1^N y_i=N-k, y_i Σ1N​yi​=N−k,yi​ binary.

    3. functions with N possible values

    f ( x ) ∈ ( d 1 , . . . , d N ) f(x)\in (d_1,...,d_N) f(x)∈(d1​,...,dN​)

    添加辅助变量 y 1 y_1 y1​～ y N y_N yN​
    f ( x ) = Σ d i y i f(x)=\Sigma d_iy_i f(x)=Σdi​yi​
    Σ y i = 1 \Sigma y_i=1 Σyi​=1 (mutally exclusive alternatives)

    4. fixed-charge problem

    f ( x ) = { k + c x , x > 0 0 , x = 0 f(x)=\begin {equation}

    {k+cx,x>00,x=0" role="presentation" style="position: relative;">{k+cx,x>00,x=0
    \end {equation} f(x)={k+cx,x>00,x=0​​​
    可以变为
    f ( x ) = c x + k y f(x)=cx+ky f(x)=cx+ky
    x ≤ M y x\le My x≤My
    y y y binary.

    5. 综合例子

    在这里插入图片描述
    在这里插入图片描述

    如果没有题目中的两个restriction，那么模型为：
    在这里插入图片描述
    接下来我们看约束1，要求 x 1 , x 2 , x 3 x_1,x_2,x_3 x1​,x2​,x3​最多只能有2个，因此添加 y 1 + y 2 + y 3 ≤ 2 y_1+y_2+y_3\le 2 y1​+y2​+y3​≤2的约束。
    然后是约束2，要求两座工厂二选一，因此添加Either-or变量 y 4 y_4 y4​，最终模型为：
    在这里插入图片描述

  • 相关阅读:
    一幅长文细学Vue（三）——组件基础（上）
    SparkSQL DataFrame的介绍及创建
    Tiktok沙箱环境文档
    1.Gin 介绍
    Redis系列2：数据持久化提高可用性
    c++11高级用法（建议收藏）
    通用后台管理系统前端界面Ⅵ——首页、登录页、404页面
    R语言将向量数据按照行方式转化为矩阵数据（设置参数byrow为TRUE）
    RabbitMQ——入门介绍
    使用 bitnami/postgresql-repmgr 镜像快速设置 PostgreSQL HA
  • 原文地址：https://blog.csdn.net/kittyzc/article/details/133925589