第二章线性规划。
1 线性规划问题的基本模型。
一、 线性规划标准模型线性规划标准模型的一般表达式：
化一般型为标准型：
2 ≤→左边+松弛变量；≥→左边-剩余变量。
3 变量→；变量无限制→令。
4 →等式两边同乘以（-1）.
2**法。一、 线性规划几何解的有关概念。
考虑线性规划模型一般形式：
可行解：凡满足约束条件和非负条件的决策变量的取值称为线性规划可行解。
可行域：所有可行解的集合称为线性规划的可行域。
最优解：使目标函数达到最优值的可行解称为线性规划的最优解。
二、 **法基本步骤。
在明确线性规划可行解、可行域和最优解的基础上，介绍线性规划的**法。对于两个或三个变量的线性规划问题，可以通过平面图或立体图进行求解，是线性规划问题解的几何表示。**法的优点简单、直观，有助于理解线性规划问题求解的基本原理。
它的局限性在于只能对两个或三个变量的线性规划问题求解。
**法的基本步骤可以概括如下：
1）建立平面（空间）直角坐标系。取决策变量为坐标向量，标出坐标原点、坐标轴指向及单位长度。
2）确定线性规划解可行域。根据非负条件和约束条件画出解的可行域。只有在第一象限的点才满足线性规划非负条件，将以不等式表示的每个约束条件化为等式，在坐标系第一象限作出约束直线，每条约束直线将第一象限划分为两个半平面，通过判断确定不等式所决定的半平面。
所有约束直线可能形成或不能形成相交区域，若能形成相交区域，相交区域任意点所表示解称为此线性规划可行解，这些符合约束限制的点集合，称为可行集或可行域。转到第三步；否则该线性规划问题无可行解。
3）绘制目标函数等值线（面）。目标函数等值线（面）就是目标函数取值相同点的集合，通常是一条直线（二维平面）或一个平面（三维空间）。
4）寻找线性规划最优解。对于目标函数的任意等值线（面），确定该等值线（面）平移后值增加的方向，平移此目标函数的等值线（面），使其达到既与可行域相交又不可能使目标函数值再增加的位置。相交位置存在三种情况：
若有唯一交点时，目标函数等值线（面）与可行域相切，切点坐标就是线性规划的最优解；若相交于多个点，称线性规划有无穷多最优解；若相交于无穷远处，此时无有限最优解。
例】 运用**法求解线性规划问题。
三、线性规划问题几何解的讨论。
利用**法可以讨论线性规划解的四种情况。
1）唯一最优解。线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。
2）无穷多最优解。线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值达到最优的解。如果例的目标函数变为，目标函数的等值线正好和约束条件相平行。
在目标函数向右上方平移的过程中，与可行域相切于上的所有点，此时，该线性规划问题存在无穷多最优解。
3）无有限最优解（无界解）。线性规划问题的无有限最优解是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。考虑下述线性规划模型：
利用**法进行求解时，可行域是一个非封闭的无界区域，的取值可以无限增大，同时，目标函数值也可以增大到无穷，如下图所示。在这种情况下，称线性规划无有限最优解或无界解。原因在于建立线性规划模型时，遗漏了某种必要资源的约束。
4）无可行解。当线性规划问题中的约束条件不能同时满足时，将出现无可行域的情况，这时不存在可行解，即该线性规划问题无解。考虑下述线性规划模型。
利用**法进行求解时，在第一象限内，所有约束条件不能形成一个相交平面区域，如上图。线性规划问题不存在可行域，也就是说，问题没有可行解。其原因是线性规划模型自身的错误，约束条件之间自相矛盾，应根据实际情况进行调整。
针对线性规划几何解还有一些重要的性质，这里不加证明叙述如下：（1）线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无有限最优解、无可行解。
（2）若线性规划可行域非空，则可行域必定是一个凸集。（3）若线性规划可行域非空，则凸集至多有有限个极点。（4）若线性规划优解存在，则最优解或最优解之一肯定能够在可行域（凸集）的某个极点找到。
通过上述的讨论，求线性规划问题最优解，可以转化为在其可行域有限个极点上进行搜索的方法。基本思路是，先找出凸集任意一个极点，计算极点的目标函数值。比较与之相邻的目标函数值是否比该极点的目标函数值更优，如果为否，则该极点就是最优解，如果为是，转到比该点目标函数值更优的另一极点。
重复上述过程，直到找出使目标函数值达到最忧的极点为止。
3 单纯形法。
一、预备知识。
1、基。考虑线性规划标准模型
其中：系数矩阵为阶矩阵。
若的秩为，为中的任意阶子矩阵，且行列式，则称为线性规划模型式的一个基。为中其余阶子矩阵，称为线性规划模型式的一个非基矩阵。不失一般性，假设：
，则为基向量。与基向量相对应的变量称为基变量，与基的列向量相对应；其它个变量称为非基变量，与非基矩阵的列向量相对应。基于上述讨论，假设为线性规划的一个基，为线性规划的一个非基，则可以表示为：
，相应地、可以分为： 。线性规划标准模型可以表示为：
如非基变量取定值，由于，则有唯一的值与之对应：。特别地，当时，。关于此类特别解，可以得到线性规划基本解、基本可行解、可行基的概念。
线性规划问题基的数量等于约束不等式的数量（不含非负约束）
2、基本解、基本可行解、可行基。
设为线性规划的一个基，令非基变量，可求得。此时，有，称是线性规划与基对应的一个基本解。
如果，称是线性规划与基对应的一个基本可行解，相对应的基称为可行基。
二单纯形法的基本思路及原理。
1、如何寻找初始基本可行解？
2、最优性检验：判断初始基本可行解是否是最优解？
检验数：目标函数中处理成只含有非基变量，则目标函数中基变量的系数为0.记目标函数中变量的系数为。
判定定理：所有检验数大于等于0，则这个基本可行解是最优解。
3、基变化。
1）入基变量的确定：选择检验数为负且绝对值较大的非基变量入基。
2）出基变量的确定：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程常数项的值，把其中比值最小的约束方程中的原基变量确定为出基变量。
出基变量的确定：
令，，则，所以最大只能取3.
三、人工变量的引入。
例2】解：化为标准型。
显然不是典则形式。
现引入辅助问题。
四、几种特殊情况。
1、无可行解。
例3】, 2、无界解。例4】
3、无穷多最优解。例5】
作业：p51（4）
4 运输问题（the transportation problem）
一、 基本模型。
1、 数学描述：假设有m个产地，可以**某种物资，用表示，有n个销地，用表示，产地的产量和销地的销售量分别为和，从至单位运价为。
2、 应用举例。
3、 产销平衡的运输模型的线性规划模型。
4、 产销不平衡的运输问题。
例：销地、、需求量依次为吨，产地、产量为吨。由于需求大于供给，决定需求量可减少吨，区全部满足，需求量不少于1700吨，试求运费最小的分配方案。
二、 表上作业法。
运输问题变量多，运算量大；
必须化为产销平衡问题。
表上作业法的步骤：
找出初始基本可行解；②求各非基变量的检验数；③确定入基和出基变量；④重复②、③直至得到最优解。
1、 确定初始基本可行解。
1）西北角法。
2）最小元素法。
2、 最优解的判别。
1）闭回路法。
在已经给出的调运方案的运输表上，从一个代表非基变量的空格出发，沿水平或垂直方向前进，只要碰到代表基变量的填入数字才能向左或向右转90度（当然也可以不改变方向继续前进），这样继续下去，直到回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的毕回路。
例如，增加1t，运输费用增加5元，就得减少1t，运输费用减少3元，为了产量平衡，就得增加1t，运输费用增加6元，为了销量平衡，就得减少1t，运输费用减小3元，所以检验数为5.
我们把基数顶点运价之和减去偶数顶点运价之和即可得到非基变量的检验数。
2）位势法。
我们对运输表上的每一行赋予一个数值，对每一列赋予一个数值，它们的数值是由基变量的检验数所决定，则非基变量的检验数为。
3.改进运输方案的方法：闭回路调整法。
运筹学复习重点
考试日期 6月24号。答疑时间 6月23号。题型 判断 20分左右 选择 10分左右 填空 10分左右 其余 大题 第一章 线性规划问题及其数学模型。1 了解什么是线性规划。2 知道线性规划问题建模的三个步骤 确定决策变量 确定目标函数，通常要求实现该函数的最大或最小。确定约束条件。实现目标函数要受...
运筹学复习重点
3 不同目标下网络计划优化的方法。第10章排队论。1 排队系统基本性能指标的含义 关系。2 泊松流与负指数分布的关系，排队系统中基本参数和含义的多维解读。3 系统状态概率pn的含义 它在推导系统基本性能指标中的基础地位，推导它自身所依据的状态转移图。4 标准m m 1模型的系统状态概率 基本性能指标...
运筹学复习重点
第1章线性规划与单纯形法。1 化线形规划标准形的手法。2 线性规划解的概念 解的情形 解的判定。3 单纯形法的计算过程 迭代逻辑。4 熟练运用单纯形表求解问题 若给出单纯形表，要会解读，会基于单纯形法基本原理反推出表中一些参数。5 两阶段法 大m法。第2章对偶理论和灵敏度分析。1 会写对偶问题，掌握...