跳至主要內容

数学建模

LincZero大约 4 分钟

数学建模

目录

整数规划模型（IP）

简概

基本原理

  • 整数规划模型

    • 数学规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。
    • 目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划
    • IP是整数规划，LP是线性规划，ILP是整数线性规划

  • 整数规划特点

    • 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况
      1. 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致
      2. 整数规划无可行解
      3. 有可行解（当然就存在最优解)，但最优解值变差
    • 整数规划最优解不能按照实数最优解简单取整而获得

案例

  • 情形举例一

    • 问题（合理下料问题）

      设用某型号的圆钢下零件A1,A2,⋯ ,AmA_1,A_2,\cdots,A_m的毛坯。在一根圆钢上下料的方式有B1,B2,⋯ ,BnB_1,B_2,\cdots,B_n种

      每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量如表所示

      问怎样安排下料方式，使得即满足需要，所用的原材料又最少?

    • 模型——问题假设

      设xjx_j表示用BjB_j种方式下料根数，模型：（竖着看）

      下零件，右方式，右下零件个数B1⋯Bn\begin{matrix}B_1&\cdots &B_n\end{matrix}零件毛坯数至少需求量
      A1⋮Am\begin{matrix}A_1\\\vdots\\A_m\end{matrix}a11⋯a1n⋮⋮am1⋯amn\begin{matrix}a_{11}&\cdots&a_{1n}\\\vdots&&\vdots\\a_{m1}&\cdots&a_{mn}\end{matrix}b1⋮bm\begin{matrix}b_1\\\vdots\\b_m\end{matrix}

    • 模型——整数目标规划

      min⁡Z=∑j=1nxj s.t.{∑j=1naijxj≥bi（i=1,2,⋯ ,m）xj≥0且为整数（j=1,2,⋯ ,m） \min Z=\sum_{j=1}^nx_j\\~\\ s.t.\left\{\begin{aligned} &\sum_{j=1}^n a_{ij}x_j\geq b_i&&（i=1,2,\cdots,m）\\ &x_j\geq0且为整数&&（j=1,2,\cdots,m） \end{aligned}\right.

  • 情形举例二

    • 问题（建厂问题）

      某公司计划在mm个地点建厂，可供选择的地点有A1,A2,⋯ ,AmA_1,A_2,\cdots,A_m，他们的生产能力分别是a1,a2,⋯ ,ama_1,a_2,\cdots,a_m（假设生产同一产品），第ii个工厂的建设费用为fi（i=1,2,⋯ ,m）f_i（i=1,2,\cdots,m）

      又有n个地点B1,B2,⋯ ,BnB_1,B_2,\cdots,B_n需要销售这种产品，其销量分别为b1,b2,⋯ ,bnb_1,b_2,\cdots,b_n，从工厂运往销地的单位运费为CijC_{ij}

      试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？

      下产地，右销地B1⋯Bn\begin{matrix}B_1&\cdots &B_n\end{matrix}生产能力建设费用
      A1⋮Am\begin{matrix}A_1\\\vdots\\A_m\end{matrix}c11⋯c1n⋮⋮cm1⋯cmn\begin{matrix}c_{11}&\cdots&c_{1n}\\\vdots&&\vdots\\c_{m1}&\cdots&c_{mn}\end{matrix}a1⋮am\begin{matrix}a_1\\\vdots\\a_m\end{matrix}f1⋮fm\begin{matrix}f_1\\\vdots\\f_m\end{matrix}
      销量b1⋯bn\begin{matrix}b_1&\cdots &b_n\end{matrix}————

    • 模型——问题假设

      设xijx_{ij}表示从工厂往销地的运量

      又设Yi={1在Ai建厂0不在Ai建厂 （i=1,2,⋯ ,m）Y_i=\left\{\begin{aligned}1&&在A_i建厂\\0&&不在A_i建厂\end{aligned}\right.~（i=1,2,\cdots,m）

    • 模型——整数目标规划

      min⁡Z=∑∑cijxij+∑i=1mfiyi s.t.{∑j=1nxij≤aiyi（i=1,2,⋯ ,m）∑i=1mxij≥bj（j=1,2,⋯ ,n）xij≥0，yi=0或1（i=1,2,⋯ ,m、j=1,2,⋯ ,n） \min Z=\sum\sum c_{ij}x_{ij}+\sum^m_{i=1}f_iy_i\\~\\ s.t.\left\{\begin{aligned} &\sum^n_{j=1}x_{ij}\leq a_iy_i&&（i=1,2,\cdots,m）\\ &\sum^m_{i=1}x_{ij}\geq b_j&&（j=1,2,\cdots,n）\\ &x_{ij}\geq0，y_i=0或1&&（i=1,2,\cdots,m、j=1,2,\cdots,n） \end{aligned}\right.

求解

标准形式

  • 一般形式

    max⁡(min⁡)z=∑j=1ncjxj s.t.{∑j=1naijxj≤(=,≥)bi（i=1,2,⋯ ,m）xj≥0，xj为整数（j=1,2,⋯ ,m） \max(\min)z=\sum^n_{j=1}c_jx_j\\~\\ s.t.\left\{\begin{aligned} &\sum^n_{j=1}a_{ij}x_j\leq(=,\geq)b_i&&（i=1,2,\cdots,m）\\ &x_j\geq0，x_j为整数&&（j=1,2,\cdots,m） \end{aligned}\right.

分类

  • 整数规划分类

    • 纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）
    • 全整数规划：除了所有决策变量要求取非负整数外，系数aija_{ij}和常数bib_i也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）
    • 混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数
    • 0-1整数规划：所有决策变量只能取0或1两个整数（一般是用于工作的安排分配）

  • 概念补充

    • 松弛变量：比如a+b<=x，可以加入松弛变量c>=0，使得a+b+c=x。不等式约束转换为等式约束
    • 剩余变量：比如a+b>=x，可以加入剩余变量c<=0，使得a+b+c=x。不等式约束转换为等式约束

  • 松弛线性规划

    • 整数规划

      max⁡cTx s.t.{Ax=bx≥0，x为整数 \max c^Tx\\~\\ s.t.\left\{\begin{aligned} Ax&=b\\ x&\geq0，x为整数 \end{aligned}\right.

    • 松弛的线性规划

      max⁡cTx s.t.{Ax=bx≥0 \max c^Tx\\~\\ s.t.\left\{\begin{aligned} Ax&=b\\ x&\geq0 \end{aligned}\right.

    • 关系

      整数规划可行解是松弛问题可行域中的整数格点

      松弛问题无可行解则整数规划也无可行解

      LIP最优值小于或等于松弛问题的最优解

      松弛问题最优解满足整数要求，则该最优解为整数规划最优解

Matlab求

算法

分支定界算法

分支定界算法求解整数规划基本原理

割平面算法

割平面算法求解整数规划基本原理

匈牙利算法

匈牙利算法求解整数规划基本原理