模型简介

实例与定义

某机床厂生产甲、乙两种机床，每台销售后的利润分别为 4000 元与 3000 元。生产甲机床需用 A、B 机器加工，加工时间分别为每台 2 小时和 1 小时；生产乙机床需用 A、B、C 三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为 A机器 10 小时、B 机器 8 小时和C 机器 7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

上述问题的数学模型：设该厂生产x₁台甲机床和 x₂ 乙机床时总利润最大，则应满足

$(目标函数)max\ z=4x_1+3x_2\\ s.t.(约束条件)\begin{cases} 2x_1+x_2≤10\\ x_1+x_2≤8\\ x_2≤7\\ x_1,x_2≥0 \end{cases}$

这里变量x₁，x₂ 称之为决策变量，还有目标函数，约束条件。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。

总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

数学标准型

$max\ z=\sum_{j=1}^nc_jx_j\\ s.t.\ \begin{cases} \sum_{j=1}^na_{ij}x_j=b_i & i=1,2,...,m\\ x_j≥0 & j=1,2,...,n \end{cases}$

例题分析

可以转化为线性规划的问题

$min\ |x_1|+|x_2|+...+|x_n|\\ s.t.\ Ax≤b$
其中 x = [ x₁ … x_n ]^T，A和b为相应维数的矩阵和列向量

对于任意的 x_i ，存在 u_i , v_i > 0 满足

$x_i = u_i-v_i,\ |x_i|=u_i+ v_i$

取

$u_i=\frac{x_i+|x_i|}{2},v_i=\frac{|x_i|-x_i}{2}$

得

$min\ \sum_{i=1}^n(u_i+v_i)\\ s.t.\ \begin{cases} A(u-v)≤b\\ u,v≥0 \end{cases}$

$min_{x_i}\{max_{y_i}|\varepsilon_i|\}\\ 其中 \varepsilon_i=x_i-y_i$

目前还没弄明白这个解法。。。先记录一下

$取x_0=max_{y_i}|\varepsilon_i|得\\ min\ x_0\\ s.t.\ x_1-y_1≤x_0,...,x_n-y_n≤x_0$

运输问题

某商品有m 个产地、n个销地，各产地的产量分别为 a₁ , …, a_m ，各销地的需求量分别为 b₁ , … , b_n 。若该商品由 i 产地运到 j 销地的单位运价为 c_ij ，问应该如何调运才能使总运费最省？

对于产销平衡的运输问题，有以下关系式存在：

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。

指派问题（匈牙利算法）

拟分配 n 人去干 n 项工作，每人干且仅干一项工作，若分配第 i 人去干第 j 项工作，需花费 c_ij 单位时间，问应如何分配工作才能使工人花费的总时间最少？

上述指派问题的可行解可以用一个矩阵表示，这个矩阵比较特殊，其每行每列均有且仅有一个元素为1，其余元素均为0

由于指派问题的特殊性，我们可以用匈牙利算法来解决这一问题

$如果系数矩阵C=(c_{ij})一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=(b_{ij})\\ 则以C或B为系数矩阵的指派问题具有相同的最优指派$

例题详见P6，懒得copy了

对偶理论与灵敏度分析

占坑，盲猜用不着

多目标规划模型：投资的收益和风险

例题见P10

最终得到的线性规划中有两个目标：使净收益尽可能大，总体风险尽可能小，是一个多目标规划模型

模型简化

固定风险水平，优化收益

给定风险一个界限a，使最大风险小于等于a，就将一个目标变成约束条件，可将多目标规划变成一个目标的线性规划

固定盈利水平，极小化风险

同上

赋予权重 s (投资偏好系数)

投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益分别赋予权重 s（ 0 ≤ s ≤ 1 ）和 ) （1 - s），s 称为投资偏好系数。