1、什么是线性规化？
线性规划（Linear programming,简称LP），是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。
线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。关键在于选定适当的决策变量。
2、线性规化简介
数学模型：
（1）列出约束条件及目标函数
（2）画出约束条件所表示的可行域
（3）在可行域内求目标函数的最优解及最优值
3、模型建立
从实际问题中建立数学模型一般有以下三个步骤；
1.根据影响所要达到目的的因素找到决策变量；
2.由决策变量和所在达到目的之间的函数关系确定目标函数；
3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
接下来让我们通过几个具体实例来体会“线性规划”在建模方面的实际应用
运输问题
例：
某商品有m个产地，n个销地，各产地的产量分别为a1，…，am，各销地的需求量分别为b1，…，bm。若该商品由i产地运到j销地的单位运价为c（ij），问应该如何调运才能使总运费最省？
01、产销平衡
存在产销平衡问题（当有也有生产与销售量不平衡的情况），实际上不平衡的运输问题可以转换成平衡型的问题。通过虚设一个产地或销售地并令运输成本为0。
02、解
当产量等于销售量的时候有可行解且必有最优解。并且若产量与销售量均为整数时，必存在决策变量均是整数的解。
03、表上作业法
其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法）。
指派问题
例：
拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费C(ij)单位时间，问应如何分配工作才能使工人花费的总时间最少？
01、矩阵表示法
指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为 0；问题中的变量只能取 0 或1，从而是一个0-1 规划问题。一般的0-1 规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为±1），其非负可行解的分量只能取 0或 1，故约束xijxij = 0或1可改写为xijxij≥ 0而不改变其解。此时，指派问题被转化为一个特殊的运输问题。
02、费药类
由于指派问题的特殊性，又存在着由匈牙利数学家 Konig 提出的更为简便的解法—匈牙利算法。算法主要依据:
如果系数矩阵 C=(cij)C=(cij)一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵BB，则以C或B为系数矩阵的指派问题具有相同的最优指派。
对偶理论与灵敏度分析
对偶问题的基本性质：
01、对称性
对偶问题的对偶是原问题。
02、无界性
若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
03、对偶定理
若原问题有最优解，那么对偶问题也有最优解；且目标函数值相同。
03、互补松弛性
若xˆ,yˆx^,y^分别是原问题和对偶问题的最优解，则
本期的建模算法之线性规划小知识到此告一段落啦。如果你对该算法有兴趣，可以自己动一动手去查找资料更深入了解一下。以下书籍供参考。
愿你在建模道路上越走越远！
最终满载而归！
【竞赛报名/项目咨询请加微信：mollywei007】
