Skip to content

数学规划

约 2396 个字 预计阅读时间 8 分钟

运筹学(Operations Research)

运筹学与最优化

运筹学的研究对象是人类对各种资源的运用及筹划活动，它的研究目的在于了解和发现这种运用及筹划活动的基本规律，以便发挥有限资源的最大效益，来达到总体、最优的目标

最优化(Optimization)使在一定约束之下如何选取某些因素的值使某项(或某些)指标达到最优的一门学科。运筹学中所处理的问题绝大部分都是最优化问题

  • 数学规划（Mathematical Programming）
    • 线性规划（Linear Programming）
    • 非线性规划（Nonlinear Programming）
    • 整数规划（Integer Programming）
    • 多目标规划（Multiobjective Programming）
  • 组合优化（Combinatorial Optimization）
  • 随机运筹
    • 排队论（Queuing Theory）
    • 库存论（Inventory theory）
    • 可靠性理论（Reliability Theory）
  • 博弈论（Game Theory）与决策理论（Decision Theory）

数学规划

定义

若干个变量在满足一些等式或不等式限制条件下，使目标函数取得最大值或最小值

本地路径

数学规划分类

按函数性质

  • 线性规划（linear programming）
    • 目标函数为线性函数，约束条件为线性等式或不等式

      \(min\ \mathbf{cx}\)

      \(s.t.\ \mathbf{Ax=b}\)

      \(\mathbf{x\geq 0}\)

  • 非线性规划（nonlinear programming）
    • 目标函数为非线性函数，或至少有一个约束条件为非线性等式或不等式
      • 二次规划（Quadratic Programming, QP）：目标函数为二次函数，约束条件为线性等式或不等式

        \(min\ \mathbf{x^T Ax}\)

        \(s.t.\ \mathbf{Ax=b}\)

        \(\mathbf{x\geq 0}\)

      • 带二次约束的二次规划（Quadratically Constrained Quadratic Program， QCQP）：目标函数为二次函数，约束条件为线性或二次等式或不等式
      • 线性分式规划（linear fractional programming）：目标函数为两个线性函数的商，约束条件为线性等式或不等式

        \(min\ \mathbf{\frac{cx+d}{ux+v}}\)

        \(s.t.\ \mathbf{Ax=b}\)

        \(\mathbf{x\geq 0}\)

按变量性质

整数规划（integer programming）：至少有一个决策变量限定取整数值

  • 整数决策变量意义
    • 用于表示只能取离散值的对象的数量
    • 用于表示约束条件之间的逻辑关系或复杂的函数形式
    • 用于表示非数值的优化或可行性问题
  • 特殊整数规划
    • 部分决策变量取整数值的数学规划特称为混合整数规划（Mixed Integer Programming, MIP）
    • 0-1规划：决策变量仅取值0或1的数学规划

按约束条件

  • 无约束优化
  • 约束优化

数学规划建模的基本要求

  • 数学规划模型是问题要求和限制的真实反映
    • 数学规划模型的最优解（可行解）与问题最优解（可行解）是否一致或对应
    • 是否遗漏问题的隐含约束、决策变量的必然要求、多组决策变量间的联系等约束条件
  • 数学规划模型应符合数学规划的内容规范和形式要求
    • 要素完整、变量指标运用准确。逻辑关系、集合运算等一般不在数学规划中出现
  • 问题可能存在多个数学规划描述，需根据实际情况进行选择和不断完善
    • 复杂目标函数和约束条件的简化， 0-1变量的灵活运用
    • 可行域约简、数学规划的重构、分解与松弛

食谱问题(diet problem)

  • \(n\)种不同的食品，第\(j\)种食品的单位售价为个\(c_j\)
  • 人体正常生命活动过程需要\(m\)种基本营养成分，一个人每天至少需要摄入第\(i\)种营养成分\(b_i\)个单位
  • 每单位第\(j\)种食物包含第\(i\)种营养成分\(a_{ij}\)个单位
  • 在满足人体营养需求的前提下，寻找最经济的配食方案数学规划建模
  • 决策变量:食谱中第\(j\)种食物的数量为\(x_j\)个单位
  • 目标函数:所有食物费用之和\(c_1x_1+c_2x_2+\dots+c_nx_n\)
  • 约束条件：
    • 满足人体营养需求\(a_{i1}x_1+\dots +a_{ij}x_j+\dots +a_{in}x_n\geq b_i\ ,\ i=1,\dots,m\)，其中\(a_{ij}x_j\)是从第\(j\)种食物种摄入的第\(i\)种营养成分数量
    • 摄入食物量非负\(x_j\geq 0\)

      \(min\ \Sigma_{j=1}^nc_jx_j\)

      \(s.t.\ \Sigma_{j=1}^na_{ij}x_j\geq b_i,\ i=1,\dots,m\)

      \(x_j\geq 0,\ j=1,\dots,n\)

运输问题(Transportation Problem)

  • 某货物有\(m\)个产地，产地\(i\)的产量为\(q\)，\(i=1,\dots,m\)，\(n\)个销地，销地\(j\)的销量为\(b_j,\ j=1,\dots,n\)
    • 产销平衡：\(\Sigma_{i=1}^ma_i=\Sigma_{j=1}^nb_j\)
  • 由产地\(i\)到销地\(j\)的运输单价为\(c_{ij},i=1,\dots,m,j=1,\dots,n\)
  • 如何调运货物从产地到销地，可使总运输费用最小
  • 决策变量\(x_{ij}\): 产地\(i\)调运到销地\(j\)的货物数量
  • 约束条件：
    • 每个产地的货物全部运出：\(\Sigma_{j=1}^nx_{ij}=a_i,i=1,\dots,m\)
    • 每个销地的货物全部运入\(\Sigma_{j=1}^mx_{ij}=b_j,j=1,\dots,n\)
    • 调运货物量非负\(x_{ij}\geq 0\)

      \(min\ \Sigma_{i=1}^m\Sigma_{j=1}^nc_{ij}x_{ij}\)

      \(s.t.\ \Sigma_{j=1}^nx_{ij}=a_i,\ i=1,\dots,m\)

      \(\quad\quad\Sigma_{i=1}^mx_{ij}=b_i,\ i=1,\dots,n\)

      \(\quad\quad x_{ij}\geq 0,\ i=1,\dots,m,\ j=1,\dots,n\)

      \(\mathbf{x}=(x_{11},x_{12},\dots,x_{1n},x_{21},\dots,x_{2n},\dots,x_{mm})^T\)

数独

  • 决策变量：\(\begin{equation} p_{ij}=\left\{ \begin{aligned} 1 & , 第i行第j列所填数字为k \\ 0 & , 其他 \end{aligned} \right. \end{equation}\)
  • 约束条件
    • 每个格子填入的数字唯一
      • 对任意\(i,j\)，\(x_{ij1},x_{ij2},x_{ij3},x_{ij4},x_{ij5},x_{ij6},x_{ij7},x_{ij8},x_{ij9}\)恰有一个取值1
      • \(\Sigma_{k=1}^9x_{ijk}=1,i,j=1,\dots,9\)
    • 每一行填入的数字各不相同
      • 对任意\(k,k=1,\dots,9\)，第\(i\)行各列中只有一个数字为\(k\)
      • 对任意\(k,k=1,\dots,9\)，\(x_{i1k},\dots,x_{i9k}\)中恰有一个取值为1
      • \(\Sigma_{j=1}^9=1,\ i,k=1,\dots,9\)
    • 关于约束条件 \(\begin{equation} p_{ij}=\left\{ \begin{aligned} 1 & , 第i行第j列所填数字为k \\ 0 & , 其他 \end{aligned} \right. \end{equation}\)

下料问题

问题背景

现有 \(W\) 米长的钢管若干。生产某产品需长为 \(w_i\) 米的短管 \(b_i\) 根，\(i=1,2,\cdots,n\)。如何截取能使材料最省？

  • 决策变量
    • \(x_{ji}\) 表示第 \(j\) 根钢管截取第 \(i\) 种短管的数量，\(i=1,2,\cdots,k\)，\(j=1,2,\cdots,n\)（\(n=\sum\limits_{i=1}^k b_{i}\)）
  • 约束条件
    • 每根钢管截取的短管总长度不超过钢管长度 \(W\)，即 \(\sum\limits_{i=1}^n w_ix_{ji}\leq W\)，\(j=1,2,\cdots,n\)
    • 每种短管截取的数量不低于需求量，即 \(\sum\limits_{j=1}^n x_{ji}\geq b_i\)，\(i=1,2,\cdots,k\)

选址问题

问题背景

平面上有 \(n\) 个点，求一个面积最小的圆，使得这 \(n\) 个点都在圆内。

记第 \(j\) 个点的坐标为 \((x_j,y_j)\)，\(j=1,2,\cdots,n\)。我们给出一个带二次约束的二次规划模型：

决策变量：圆心坐标 \((x_0,y_0)\)，圆半径 \(r\)

目标函数：\(\min r^2\)

约束条件：\((x_j-x_0)^2+(y_j-y_0)^2\leq r^2\)，\(j=1,2,\cdots,n\)

约束为二次时，比较难写，我们可以将其转化成更简单的形式：

决策变量改为 \(\lambda=r^2-(x_0^2+y_0^2)\)

目标函数改为 \(\min\lambda+(x_0^2+y_0^2)\)

约束条件改为 \(\lambda+2x_0x_j+2y_0y_j\geq x_j^2+y_j^2\)，\(j=1,2,\cdots,n\)

数学规划建模基本要求

  • 是问题和要求和限制的真实反馈
    • 数学规划最优解（可行解）与问题最优解（可行解）有对应的关系
    • 是否遗漏问题的隐含约束，决策变量的必然要求，多组决策变量的联系等约束条件
  • 要符合数学规范的内容规范和形式要求
    • 要素完整，变量指标运用准确，逻辑运算和集合运算一般不在数学规划中出现
  • 可能存在多个数学规划描述
    • 复杂目标函数和约束条件的简化，0-1变量灵活运用
    • 可行域约简，数学规划重构，分解与松弛
  • 适用范围
    • 有更简单方法时不需要数学规划
    • 最优解不具有必要性，或求解时间高于精度要求，不必要用数学规划

时间分配问题

问题背景

有 \(T\) 天时间可用于安排复习 \(n\) 门课程，每天只能复习一门课程，每门课程至少复习一天。用 \(t\) 天时间复习第 \(j\) 门课程可使该门课程提高 \(p_{jt}\) 分。如何制定复习计划可使所有课程提高的总分尽可能大？

决策变量：\(x_{jt}\) 表示第 \(j\) 门课程是否复习 \(t\) 天，\(j=1,2,\cdots,n\)，\(t=1,2,\cdots,T\)

\[x_{jt}=\left\{\begin{array}{ll}1,&\text{第 $j$ 门课程复习 $t$ 天}\\0,&\text{其他}\end{array}\right.\]

目标函数：\(\max\sum\limits_{j=1}^n\sum\limits_{t=1}^Tp_{jt}x_{jt}\)

约束条件：\(\sum\limits_{t=1}^Tx_{jt}=1\)；\(\sum\limits_{j=1}^n\sum\limits_{t=1}^Ttx_{jt}\leq T\)

案例一：赛程编制

  • Symmetry and separation(对称性和分离性)
  • Breaks(出现连续的客场或主场比赛--这是我们不愿看到的)
  • The carry-over effect(是否连续打弱队等等)

breaks数

懒得写了，看杰哥的吧——赛程编制

支持向量机

问题背景

将一数据集 \(S\) 分为 \(C_1,C_2\) 两类，每个数据有 \(n\) 个特征。我们应该如何通过训练集来找出一个超平面，使得它判别效果最好？