运筹学整理笔记1⼀下是本⼈对于运筹学的⼀点学习笔记以及⼼得，由于是刚刚接触所以有些地⽅可能理解不是很到位，只留做⼤家的⼀个参考。
有什么不合理的地⽅还请各位指正，谢谢第⼆章线性规划与单纯形法（待完善）所以线性规划问题的求解变得相当的重要，⾸先最为直观的为图解法，通过作图直观⽅便的求解相应解。
由于其直观的结果，可以轻易地看出三中情况：1、⽆穷多最优解2、⽆界解3、⽆可⾏解。
为了形式化求解办法我们将所有的线性规划问题化为标准形式。
区分四个概念：1、可⾏解：2、基：3、基可⾏解：4、可⾏基：由于图解法⾃⾝的弊端，即只能表⽰两个变量（最多三个）的规划问题，所以产⽣了单纯形法：其本质是对于图解法的拓展，所谓的单纯形其实就是指各个维度中的图形，只不过图解法是单纯形法在⼆维中的情况。
⽽单纯形的寻优其实就是对于单纯形的各个边界以及定点的寻优。
单纯形法的根基：单纯形法基于以下⼏个定理：⼏个概念1、凸集：K是n维空间的⼀点集，若任意的两点X(1)ϵK，X(2)ϵK的连线上的所有的点满⾜αX(1)+ (1-α)X(1)ϵK，（0≤α≤1）；则K为凸集。
2、凸组合：3、顶点：⼏个定理：1、若线性规划问题存在可⾏域，则其可⾏域是凸集2、线性规划问题的可⾏解X=(x1,x2,x3……xn)T为基可⾏解的充分必要条件是X的正分量所对应的系数列向量是线性独⽴的。
3、线性规划问题的基可⾏解X对应于可⾏域D的顶点。
4、若K是有界凸集，则任何⼀点X ϵK科表⽰为K的顶点的凸组合5、若可⾏域有界，线性规划问题的⽬标函数⼀定可以再起可⾏域的顶点上达到最优松弛变量与⼈⼯变量：为了使约束中的不等式变为等式的标准形式，我们将多余的部分表⽰成松弛变量就得到了标准形式，加⼊的松弛变量其实质是表明没有利⽤上的资源，⼈⼯变量其实就像是为了⽅便找初始基多引⼊的东西。
不过要说的是⼈⼯变量在⽬标函数中的系数的正负要注意。
其实⼀般来说 ≤ 的情况下要 “+松弛变量”；在 ≥ 的情况下要 “－松弛变量+⼈⼯变量”。
4 运输问题1、运输问题表上作业法的基本步骤。
答：表上作业法的基本步骤可参照单纯形法归纳如下：（1）找出初始基可行解：即要在阶产销平衡表上给出“”个数字格（基变量）；（2）求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；(3确定入基变量，若，那么选取为入基变量；(4确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量；（5）在表上用闭合回路法调整运输方案；（6）重复2、3、4、5步骤，直到得到最优解。
2、“最小元素法”和“伏格尔”法的基本思想及基本操作。
答：最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。
伏格尔法把费用增量定义为给定行或列次小元素与最小元素的差（如果存在两个或两个以上的最小元素费用增量定义为零）。
最大差对应的行或列中的最小元素确定了产品的供应关系，即优先避免最大的费用增量发生。
当产地或销地中的一方在数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤，即可得到一个初始的基可行解。
3、闭合回路的构成以及利用闭合回路法求检验数的基本操作。
答：判断基可行解的最优性，需计算空格（非基变量）的检验数。
闭合回路法即通过闭合回路求空格检验数的方法。
从给定的初始方案的任一空格出发寻找闭合回路，闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的“+”、“-”号表示运量的调整方向。
空格处单位运量调整所引起的运费增量就是空格的检验数。
仿照此步骤可以计算初始方案中所有空格的检验数。
4、利用位势法求检验数以及利用闭合回路进行方案调整的基本操作。
答：位势法求解非基变量检验数的基本步骤：第一步：把方案表中基变量格填入其相应的运价并令；让每一个基变量都有，可求得所有的位势；第二步：利用计算各非基变量的检验数方案的优化基本步骤：在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。
