《运筹学》教案。
本教案适用于32课时的班级）
第一章线性规划与单纯形法。
1、教学计划。
第 1 次课 2 学时。
第 2 次课 2 学时。
第 3 次课 2 学时。
2、课件。1.1线性规划问题及其数学模型。
线性规划模型的建立就是将现实问题用数学的语言表达出来。
例1：某工厂要安排生产ⅰ、ⅱ两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？
解：设生产产品ⅰ、ⅱ的数量分别为和。
首先，我们的目标是要获得最大利润，即。
其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即。
原材料约束：生产所用的两种原材料a、b不得超过所用有的原材料总数，即。
非负约束：生产的产品数必然为非负的，即。
由此可得该问题的数学规划模型：
总结：线性规划的一般建模步骤如下：
1）确定决策变量。
确定决策变量就是将问题中的未知量用变量来表示，如例1中的和。确定决策变量是建立数学规划模型的关键所在。
2）确定目标函数。
确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。
3）确定约束条件。
将现实的约束用数学公式表示出来。
线性规划数学模型的特点。
1）有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最小化。
2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。
3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函数最大或最小），从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是最优化问题。
1.2 线性规划问题的标准形式。
根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是“”或“”的不等式，也可以是“=”虽然决策变量一般是非负的，但也可是无约束的，即，可以在取值。为了分析问题的简化，一般规定如下的标准形式：
非标准形式转化为标准形式：
1）若目标函数要求实现最小化，则可令，可将原问题的目标函数转化为即可。
2）若约束方程为“”，则可在“”的左边加上非负的松弛变量；若约束方程为“”，则可在“”的左边减去非负的剩余变量。
3）若存在取值无约束的变量，则可令，其中，。
例：将如下问题转化为标准形式：
解：首先，用替换，其中，；
其次，在第一个约束条件的左端加上非负的松弛变量；
再次，在第二个约束条件的左端减去非负的剩余变量；
最后，令，将求改为求。由此，可得标准形如下：
1.3线性规划问题的解。
首先，将线性问题的标准形式用矩阵和向量形式表示如下：
其中，；，1、可行解和最优解。
满足约束条件的所有解成为线性规划问题的可行解，其中，使目标函数达到最大的可行解成为最优解。
2、基和基解。
设为约束方程组的维矩阵，其秩为。设为矩阵中的阶非奇异子矩阵（），则称为线性规划的一个基。
不妨设前个变量的系数矩阵为线性规划的一个基，则为对应于这个基的基变量。用高斯消去法可求得一个解。
该解得非零分量的数目不大于方程个数，称为基解。
3、基可行解。
若基解满足非负约束，则称其为基可行解。
4、可行基。
对应于基可行解的基，成为可行基。
1.4 单纯形法。
一、单纯形表。
考察一种最简单的形式：目标函数最大化、所有约束条件均为“”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得。
将其与目标函数的变换形式组成个变量、个方程的方程组。若将看成不参与基变换的基变量，它与的系数构成一个基，利用初等变换将变为零，则可得。
据此，可设计如下的数表。
列表示基变量，在这里为；
列为基变量对应的价值系数；
列为约束方程的右端项；
行为所有变量的价值系数；
列的数字是在确定换入变量后，按规则计算后填入；
最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。
例，求解 首先将其转换为标准形式，构造初始单纯形表如下：
由上表可得初始基可行解。
由于和的检验数大于零，表明上述解不是最优解，由于的检验数更大，所以，先以为换入变量。根据规则，可确定为换出变量，计算得新表如下：
可得新解，目标函数取值。
的检验数为2，换入。根据规则，可确定为换出变量，计算得新表如下：
得新解，目标函数取值。
的检验数为1/4，换入。根据规则，可确定为换出变量，计算得：
得解，目标函数取值。由于所有的检验都小于零，达到最优。
ps：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。
1.5单纯形法的进一步讨论及小结。
一、人工变量法。
如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和初始基可行解，此时必须要构造人工变量。
在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有解；反之，则表示无可行解。
例：在第一个约束条件中加入松弛变量；在第二个约束条件中加入剩余变量和人工变量；在第三个约束条件中加入人工变量。
1）大m法：
在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数值不产生影响，可假定人工变量在目标函数中的系数为（-m）（m为很大的正数），这样在目标函数要实现最大化时，必须将人工变量从基变量中换出，否则目标函数不会实现最大化。
对上例求解，加入人工变量后，规划问题变成。
然后，利用单纯形法求解，详见p33。
2）两阶段法。
第一阶段：不考虑原问题是否有基可行解；给原线性规划问题加上人工变量后，构造仅含人工变量的目标函数和要求实现最小化；然后用单纯形法求解，若得到该规划的最优解为零，说明原问题存在基可行解，否则原问题无可行解，停止计算。
第二阶段：将第一阶段的最重计算表出去人工变量，换回原目标函数的系数作为第二阶段计算的初始表，利用单纯形法求解。
前一个例子的两阶段法求解如下：
构造出第一阶段的数学模型如下：
得最优解。由于人工变量，说明是原问题的基可行解，可进行第二阶段运算。利用单纯形法，从下表开始：
二、解的退化。
所有的检验数均。
1、基变量中有非零的人工变量，无可行解；
2、某非基变量的检验数为零，有无穷多解；
对于任一检验数，若对应的系数向量，则有无界解。
单纯形法小结。
第三章运输问题。
1、教学计划。
第 4 次课 2 学时。
2、课件。
运筹学教案
第一章绪论。运筹学 operational research 直译为 运作研究。运筹学是应用分析 试验 量化的方法，对经济管理系统中的人力 物力 财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学的产生和发展。举例 丁谓修皇宫 田忌赛马 二战大西洋潜艇战，交通线战争 滇...
运筹学教案
第 1 次课 2 学时。注 本页为每次课教案首页。绪论。运筹学 operations research 是用数学方法研究各类系统最优化问题的学科。运筹学通过建立系统的数学模型并求解，为决策者制定最优决策提供科学依据。一 运筹学简史。二 运筹学的主要分支。1.线性规划 linear programmi...
运筹学教案
学习运筹学要结合实际的应用，不要被一些概念 理论的困难吓倒。学习运筹学要把注意力放在 结合实际问题建立运筹学模型 和 解决问题的方案或模型的解 两头，中间的计算过程尽可能让计算机软件去完成。本书附有运筹学教学软件，使用方法很简单。学员必须尽快学会使用这个运筹学教学软件，并借助它来学好本课程。学习运筹...