《算法图解》11.10-11.11读书笔记
线性规划，是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，是辅助人们进行科学管理的一种数学方法，是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。
线性规划是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。
一.数学模型
（1）列出约束条件及目标函数
线性规划步骤
（2）画出约束条件所表示的可行域
（3）在可行域内求目标函数的最优解及最优值
二.标准型
描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：
一个需要极大化的线性函数：
以下形式的问题约束：
和非负变量：
其它类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。
模型建立
从实际问题中建立数学模型一般有以下三个步骤；
1.根据影响所要达到目的的因素找到决策变量；
2.由决策变量和所在达到目的之间的函数关系确定目标函数；
3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
三.线性规划难题解法
所建立的数学模型具有以下特点：
1、每个模型都有若干个决策变量（x1，x2，x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。
2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。
3、约束条件也是决策变量的线性函数。
当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。
例：
生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示，表中右边一列是每日设备能力及原材料供应的限量，该工厂生产一单位产品Ⅰ可获利2元，生产一单位产品Ⅱ可获利3元，问应如何安排生产，使其获利最多？
解：
1、确定决策变量：设x1、x2分别为产品Ⅰ、Ⅱ的生产数量；
2、明确目标函数：获利最大，即求2x1+3x2最大值；
3、所满足的约束条件：
设备限制：x1+2x2≤8
原材料A限制：4x1≤16
原材料B限制：4x2≤12
基本要求：x1，x2≥0
用max代替最大值，s.t.（subject to 的简写）代替约束条件，则该模型可记为：
max z=2x1+3x2
s.t. x1+2x2≤8
4x1≤16
4x2≤12
x1，x2≥0
解法
求解线性规划问题的基本方法是单纯形法，已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。
对于一般线性规划问题：Min z=CX
图解法解线性规划问题
S.T.
AX =b
X>=0
其中A为一个m*n矩阵。
若A行满秩
则可以找到基矩阵B，并寻找初始基解。
用N表示对应于B的非基矩阵。则规划问题1可化为：
规划问题2：
Min z=CB XB+CNXN
S.T.B XB+N XN = b (1)
线性规划法解题
XB >= 0, XN >= 0 (2)
(1)两边同乘B-1，得
XB + B-1 N XN = B-1 b
同时，由上式得XB = B-1 b - B-1 N XN，也代入目标函数，问题可以继续化为：
规划问题3：
Min z=CB B-1 b + ( CN - CB B-1 N ) XN
S.T.
XB+B-1N XN = B-1 b (1)
XB >= 0, XN >= 0 (2)
令N:=B-1N，b:= B-1 b，ζ= CB B-1b，σ= CN - CB B-1 N，则上述问题化为规划问题形式4：
Min z= ζ + σ XN
S.T.
XB+ N XN = b (1)
XB >= 0, XN >= 0 (2)
在上述变换中，若能找到规划问题形式4，使得b>=0，称该形式为初始基解形式。
上述的变换相当于对整个扩展矩阵（包含C及A） 乘以增广矩阵 。所以重在选择B，从而找出对应的CB。
若存在初始基解
若σ>= 0
则z >=ζ。同时，令XN = 0，XB = b，这是一个可行解，且此时z=ζ，即达到最优值。所以，此时可以得到最优解。
若σ >= 0不成立
可以采用单纯形表变换。
σ中存在分量<0。这些负分量对应的决策变量编号中，最小的为j。N中与j对应的列向量为Pj。
若Pj <=0不成立
则Pj至少存在一个分量ai，j为正。在规划问题4的约束条件（1）的两边乘以矩阵T。
T=
则变换后，决策变量xj成为基变量，替换掉原来的那个基变量。为使得T b >= 0，且T Pj=ei（其中，ei表示第i个单位向量），需要：
l ai，j>0。
l βq+βi*(-aq,j/ai,j)>=0，其中q!=i。即βq>=βi/ ai,j * aq,j。
n 若aq,j<=0，上式一定成立。
n 若aq,j>0，则需要βq / aq,j >=βi/ ai,j。因此，要选择i使得βi/ ai,j最小。
如果这种方法确定了多个下标，选择下标最小的一个。
转换后得到规划问题4的形式，继续对σ进行判断。由于基解是有限个，因此，一定可以在有限步跳出该循环。
若对于每一个i，ai,j<=0
最优值无解。
若不能寻找到初始基解
无解。
若A不是行满秩
化简直到A行满秩，转到若A行满秩。
