山东大学《管理系统工程》教案14线性规划问题

1、周 次 第 十 周 章 节 名 称 第十四章 线性规划问题（一） 授 课 方 式 课堂讲授 教 学 时 数 3 授 课 要 点 第十四章 线性规划问题 教学目的： 通过这一章的教学，要求学生熟悉 线性规划问题的数学模型，解的概念，解的性质，线性规划的对偶理论、影子价格。掌握线性规划问题的图解法、单纯形法、对偶单纯形法以及常用的灵敏度分析方法。学会对一些简单的管理优化问题进行分析，建立模型并求解。 第一节 系统模型技术概述 模型在系统工程中占有很重要的地位。我们首先要了解什么是模型，模型的作用以及模型的分类，这对于构造和使用模型是十分重要的。 一、模型的定义及特征 模型可以认为是实际系统的代替物

2、。模型应反映出系统的主要组成部分和各部分的相互作用以及在运行条件下因果的作用和反作用的相互关系。根据模型，我们可以用较少的风险、时间和费用来对实际系统做研究和实验，更好地观察系统的行为。开发一个模型是科学和艺术的结合，因此，模型是实际系统理想化的抽象或简化表示。它描绘了现实世界的某些主要特点。它 是为了客观地研究系统而发展起来的。 模型有三个特征： 1.它是实现世界一部分的抽象或模仿； 2.它是由那些与分析的问题有关的因素构成； 3.它表明了有关因察之间的相互关系。 模型是对现实世界的一个抽象。因此，模型必须反映实际，同时由于它的抽象性，又要高于实际。在构造模型时，要兼顾到它的现实性和易处理性

3、。考虑到现实性，模型必须包括现实系统中的 主要因素；考虑到易处理性，模型要采取一些理想化的办法，即 去掉一些外在的影响，并对一些过程作合理的简化。 二、模型的种类 三、模型的作用和用途 模型的作用和用途有以下几个方面； 1模型比现实容易操作，尤其是一些参数值的改变在模型中操作比在现实中操作要容易； 2有时在现实上很难或不能作试验，通过建立模型就可以解决这些困难，而且模型比现实更容易理解； 3有些变量在现实情况中要很长时间才能看出其变化情况，但用模型研究时可以很快看出变化规律，从而最迅速地抓住其本质特征； 4用模型研究变量(可控的和不可控的)之间的关系，通过用可控变量得出一定的结果； 5通过灵敏

4、度分析，可看出哪些因素对系统影响更大。 四、建立模型的一般要求 1有足够的精确度。 2简单。 3数据要准确，依据要充分。 4. 尽量借鉴标准形式。 5. 模型中所表示的系统要能够操纵和控制，否则建立的模型就毫无意义； 6. 模型要有一定的适应性和可靠性。 五、构造模型的一般原则 1建立方框图。 2考虑信息相关性。 3考虑准确性。 4考虑结集性。 六、 构模的基本步骤 对于构模，很难给出一个严格的步骤。构模主要取决于对问题的理解、洞察力、训练和技巧。构模的基本步骤可归纳为： 1. 明确构模的目的和要求，以使模型满足实际需要，不致产生太大的偏差； 2对系统进行一般语言描述，这是进一步确定模型结构的

5、基础； 3. 弄清楚系统中的主要因素及其相互关系以使模型准确表示现实系统； 4确定模型的结构，这一步决定了模型定量方面的内容； 5估计模型中的参数，用数量表示系统中的因果关系； 6对模型进行实验研究； 7根据实验结果，对模型作必要的修改。 七、 模型的简化和近似 由于实际情况的复杂和变化多样，往往不能简单地套用现有的模型，甚至对一些具有简单结构的模型也是如此。这时只有改用其它形式的模型，有时通过模型的构造才发现必须拥有哪些数据，或者模型该往哪个方向修正。还有的时候，虽然复杂的模型已构造出来，但是作试验和求解太困难，就改用较为简单的近似模型。 另外，有些实际问题建立数学模型很困难，甚至不可能，还

6、有些问题即使建立起模型来也很复杂，求解也很困难，在这种情况下，我们就要用另外一种手段仿真技术。一种是物理仿真方法，另一种是电子计算机仿真方法，而后者最常用也最有效。 第二节 线性规划问题的数学模型 线性规划是运筹学的一个重要分支。它所研究的问题：一是在资源（如钢材、电力）受限制的前提下，研究如何合理使用这些资源，以完成更多的任务；二是在任务一定的前提下，研究如何合理安排，用最少的资源来完成给定的任务。实际上，它们是一个问题的两个方面，前者是扩大生产，增加利润，后者是减少消耗，降低成本。以数学的形式来表示的话，线性规划就是求具有线性约束条件的线性目标函数的极值问题。 一、问题的提出 二、线性规划

7、问题的数学模型 1. 一般线性规划问题的数学模型： 一般线性规划问题是具有下述形式的数学模型： 求决策变量：x1 ，x2 ，xn 满足约束条件： 这就是线性规划问题的数学模型。 2. 线性规划数学模型的标准形式 在线性规划问题的数学模型中，对不同的问题，约束条件可以是线性方程组，也可以是线性不等式组，目标函数可以是求最大值，也可以是求最小值，这种形式上的不同，给讨论线性规划问题的求解带来不便。为了讨论方便起见，规定线性规划问题的数学模型的标准形式为： 求： x1 ，x 2 ，xn 满足 3.将一般形式的线性规划数学模型转化为标准形式 三、线性规划问题数学模型的向量表达式与矩阵表达式 用向量来描

8、述线性规划问题的数学模型的标准形式为：教 学 重 点 与 难 点 重点： 线性规划的数学模型及其标准形式。在数学模型中，要求熟悉矩阵形式，为后面打下基础。要求学生掌握非标准形式的几种具体情形及其相应的标准化方法。 难点： 建立实际问题的线性规划数学模型，将线性规划数学模型的一般形式转化为标准形式。 课 堂 讨 论 与 练 习 习题： 教材 P199 1 ， 2 ， 3 ， 4 ， 5 参 考 资 料 运筹学 运筹学编写组 清华大学出版社 外 语 词 汇 Linear programming, model, Standard form 周 次 第 十一 周 章 节 名 称 第十四章 线性规划问题

9、（二） 授 课 方 式 课堂讲授 教 学 时 数 3 授 课 要 点 第三节 线性规划问题的图解法 图解法是用作图的方法来求线性规划问题的解，它适用于仅含两个决策变量的线性规划问题的数学模型。虽然这种方法的应用范围受到很大的限制，但这种方法简单、直观，而且有助于理解线性规划问题求解的基本原理。 第四节 线性规划问题的基本理论 一、 线性规划问题的解 对于线性规划问题 6 退化解：非零分量的个数小于 m 的基本可行解，称为退化解。 二、凸集 三、线性规划问题的基本定理 第五节 单纯形法 一、单纯形法原理 单纯形法的基本思路是：从一个基本可行解出发，转移到另一个基本可行解，每一次转移都使目标函数值

10、得到改善，这在数学上称为从一个基本可行解到另一个基本可行解的迭代。因为基本可行解反映在几何上就是可行域的一个顶点，而可行域的顶点个数是有限的，因此，经过有限次迭代后，就可取得最优解，先用一个例子来说明上述基本思路。 教 学 重 点 与 难 点 重点： 线性规划模型的矩阵表达式，图解法，解的基本概念，基、基本可行解、凸集的概念，定理 1 ， 3 ， 5 。单纯形法，解的判别定理。 难点： 线性规划模型的矩阵表达式，基的概念，基本可行解的概念，单纯形法原理，各种解的经济解释。课 堂 讨 论 与 练 习 习题： P199200 6 ， 7 ， 参 考 资 料 运筹学 运筹学编写组 清华大学出版社 外

11、 语 词 汇 Basic ； Basic variables ； Nonbasic variables ； Matrix form ； Basic feasible solution ； Optimal solution ； Convex set ； Simplex method 周 次 第 十二 周 章 节 名 称 第十四章 线性规划问题（三） 授 课 方 式 课堂讲授 教 学 时 数 3 授 课 要 点 一、单纯形法原理 用单纯形表计算 二、大 M 法与两阶段法 在前面的讨论中，约束方程组系数矩阵明显地含有 m 阶单位矩阵，因此很快地找到初始可行基与初始基本可行解。但是，一般来讲，约束方程

12、组的系数矩阵中所含的单位响亮的个数往往不足 m 个。这时，就要引进人工变量，以人工变量对应的系数列向量作为单位列向量，构成一个初始可行基，进而应用单纯形法求解。 （一） 大 M 法 设线性规划问题 （ 2 13 ） 如果约束方程组的系数矩阵中不含 m 阶单位矩阵，则分别给每一个约束方程加一个新的非负变量 xn+1 ， xn+2 ， xn+m ，使（ 2 13 ）式扩充为（ 2 14 ） 称新的变量 xn+1 ， xn+2 ， xn+m 为人工变量。因为（ 2 14 ）的系数矩阵中含有 m 阶单位矩阵，作为初始可行基，则 xn+1 ， xn+2 ， xn+m 为基变量，相应的基本可行解为： 但是

13、，我们不能用新的约束条件（ 2 14 ）简单地代替原来的约束条件，因为人工变量是虚拟的变量，没有任何实际意义。然而，它的引进却扩大了原问题的范围，也就是将 n 维空间的问题扩充为 m+n 维空间的问题了。为了使（ 2 13 ）与（ 2 14 ）在最优解方面互相提供信息，应考虑修改目标函数。由于原问题的最优解中不能有人工变量出现，即限定人工变量的取值必须为零，为此引入新的 n+m 维目标函数 其中 M 是很大的正数。对此应用单纯形法在改善（即增大）目标函数值的过程中，如果原问题有最优解，则必然要在迭代中尽快地将人工变量从基变量替换称非基变量，或使其值为零。否则，目标函数将是一个负的很大的值，这就

14、不可能实现最大值。从中可以看出引入大 M 的作用，所以称为大 M 法，也称为惩罚法。 在用大 M 法解线性规划问题，当其全部检验数 时，出现两种可能： 1 在基变量中已不包含人工变量时，则原问题有最优解； 2 在基变量中仍含有取正值的人工变量时，则原问题无可行解。 对于第 2 种可能，如果作为基变量的人工变量其值为零（即出现退化解），则原问题仍有最优解。 两阶段法是处理人工变量的另一种方法。这种方法是把增加人工变量后的线性规划问题分成两个阶段来求解。 第一阶段：求原线性规划问题的一个基本可行解。为此，构造一个辅助线性规划问题，它以所有人工变量之和求最小值为目标函数，即 用单纯形法求解，若第一阶

15、段问题的最终单纯形表中出现 W0 ，这说明至少有一个人工变量仍为基变量，其值大于零，于是原问题无可行解，计算停止；若得到 W=0 ，则必有 xn+i=0 （ i=1 ， 2 ， m ），即所有人工变量都变换成非基变量，这表明原线性规划问题得到一个基本可行解，且它对应的极为一个 m 阶单位矩阵，然后转入第二阶段。 第二阶段：建立原线性规划问题的初始单纯形表，并求其最优解：将第一阶段最终表中的目标函数系数换成原问题的目标函数的系数，然后划去人工变量所在的列，就得到原问题的初始单纯形表，以此为起点，继续用单纯形法进行迭代，求出最优解。 三、单纯形法的计算步骤 对给定的线性规划问题首先是将它化为标准形

16、式，选取或构造一个单位矩阵作为基，求出初始基本可行解，并列出初始单纯形表，具体计算步骤见框图（图 14 4 ）。 四、单纯形法的矩阵形式 设线性规划问题的数学模型 引进松弛变量 化为标准形式 其中 I 为 m 阶单位矩阵。 设 B 是一个可行基，于是可将线性规划问题数学模型中的 A 、 X 、 C 分别用分块矩阵表示为其中 N 为非基变量对应的系数列向量组成的矩阵； XB ， XN 分别为基变量与非基变量组成的向量； CB ， CN 分别为基变量与非基变量的价值系数组成的行向量。因此，线性规划问题的标准形式可改写成（ 14 15 ）（ 14 16 ） 因为 B 为基，所以 ，从而 存在，以 左

17、乘（ 2 16 ）式，得 （ 14 17 ） （ 14 17 ）式就是非基变量 XN ， Xs 表示基变量 XB 的矩阵形式。将（ 14 17 ）式代入（ 14 15 ）式，就得到用非基变量表示目标函数的矩阵形式 （ 14 18 ） 在（ 14 17 ）中，令非基变量 XN =0 ， Xs =0 ，得 当 时，得到对应于可行基 B 的基本可行解。相应的目标函数值 把（ 14 18 ）再改写成 从上式可以看出，系数 分别是基变量 XB ，非基变量 XN 与 Xs 的检验数。它们还可统一用矩阵形式表示为 将上述讨论纳入单纯形表，则初始单纯形表为（表 14 15 ）。 表 14 15 经过基变换后的

18、新单纯形表为（表 14 16 ）。14 16 第六节 线性规划问题的对偶问题 一、对偶问题的一般形式 定义 具有下列特征的线性规划称为对称形式的线性规划： （ 1 ）对求目标函数最大值的线性规划数学模型，其约束条件全部为“ ”不等式，对求目标函数最小值的线性规划数学模型，其约束条件全部为“ ”不等式。 （ 2 ）全部决策变量为负。定义： 称线性规划问题 与为对称形式的对偶线性规划问题。若称前者为线性规划的原问题，则称后者为原问题的对偶问题， y1 ， y2 ， ym 为对偶变量。 用矩阵来表示原问题为：则对偶问题为 其中： A 是原问题的系数矩阵； b 是原问题的常数列向量； C 是原问题目标

19、函数的系数行向量； X 是原问题的决策变量列向量； Y 是对偶问题的决策变量行向量。 非对称形式的对偶线性规划写法见下表：教 学 重 点 与 难 点 重点： 大 M 法、两阶段法与解的判别，一般对偶模型的写法。 难点： 对偶问题的经济解释，原问题与对偶问题解的对应关系。 课 堂 讨 论 与 练 习 习题： P200 8，9，10，11，12 参 考 资 料 运筹学 运筹学编写组 清华大学出版社 外 语 词 汇 dual problem 周 次 第 十三 周 章 节 名 称 第十四章 线性规划问题（四） 授 课 方 式 课堂讲授 教 学 时 数 3 授 课 要 点 二、对偶问题的基本性质 1 对

20、称性 对偶问题的对偶问题是原问题。 2 弱对偶性 若 与 分别是原问题（ 14 19 ）与对偶问题（ 14 20 ）的可行解，则 。 3 最优性准则 设0与Y0分别为原问题（ 14 19 ）与对偶问题（ 14 20 ）的可行解，且 CX0 =Y0b ，则 X0,Y0 分别是原问题（ 14 19 ）与对偶问题（ 14 20 ）的最优解。 4 对偶定理 若原问题（ 14 19 ）有最优解，则对偶问题（ 14 20 ）也有最优解，且目标函数值相等。 5 互补松弛定理 设 X0，Y0，分别为原问题（ 14 19 ）与对偶问题（ 14 20 ）的可行解， Xs为原问题（ 14 19 ）中约束条件的松弛变

21、量，Ys为对偶问题（ 14 20 ）中约束条件的剩余变量，则 X ，Y 分别为原问题（ 14 19 ）和对偶问题（ 14 20 ）的最优解的充分必要条件是 YXs=0 ， YsX=0 6 原问题（ 14 19 ）检验数的相反数是对偶问题（ 14 20 ）的一个基本解。 三、对偶单纯形法 单纯形法的整个迭代过程是原问题由一个基本可行解转换到另一个基本可行解的过程，直到使所有的检验数都变为非正为止。换句话说，就是在迭代过程中，始终在保持原问题解的可行性（ ）的基础上，直到满足解的最优性（所有检验数 ）为止。根据 2 的性质 6 ，因此，原问题检验数变为非正的过程也可解释为：由原问题的对偶问题的一个

22、基本解出发，经过换基迭代，逐步使基本解转换为基本可行解的过程，从而得到原问题的最优解，与此同时，也得到对偶问题的最优解。 根据对偶问题的对称性，把求解原问题的迭代过程建立在保持对偶问题解的可行性（所有 ）的基础上，从原问题的一个基本解出发，经过迭代，逐步使它转变成基本可行解（ ），从而在得到对偶问题的最优解的同时，也得到原问题的最优解。这就是对偶单纯形法的基本思路。 四、对偶问题的经济解释影子价格 由对偶定理知，当 X ， Y 分别表示原问题与对偶问题的最优解时，它们对应的目标函数值相等。式中 bi 是线性规划原问题约束条件的常数项，它代表第 I 中资源的拥有量； yi 是对偶问题的决策变量，

23、它代表对一个单位第 I 中资源的估价。这种估价不是资源的市场价格，这是针对具体企业具体产品而存在的一种特殊价格，它随着企业生产任务、产品结构、工艺条件等情况的改变而变化。为区别起见，称这种估价为影子价格。 教 学 重 点 与 难 点 重点：，对偶问题的基本定理，原问题与对偶问题解的对应关系，对偶单纯形法，影子价格的概念和计算，线性规划的灵敏度分析。 难点： 影子价格的经济解释灵敏度分析的计算。 课 堂 讨 论 与 练 习 习题： P201 13 ， 14 ， 参 考 资 料 运筹学 运筹学编写组 清华大学出版社 外 语 词 汇 shadow price 周 次 第 十四 周 章 节 名 称 第

24、十四章 线性规划问题（五） 授 课 方 式 课堂讲授 教 学 时 数 3 授 课 要 点 第七节 灵敏度分析 求解一个线性规划问题，是在其数学模型中的价值系数 cj ，资源限制常数 bi ，工艺系数 aij 确定的基础上进行的，而事实上这些数据往往是统计、预测和估计的数字，程度不同地存在着误差。同时，由于市场的变化，原材料供应上的变动，工艺技术条件的改进等因素的影响，使这些数据也不断地跟着变化。因此，当这些参数中一个或几个发生变化时，就要解答两个问题： 1 参数在什么范围内变动，使原来求出的最优解保持不变 2 参数超出上述范围时，如何用最简便的方法，调整出新的最优解。 这就是灵敏度分析研究的内容，所以灵敏度分析就是线性规划数学模型中某些参数的变化对最优解的影响及程度的分析。由于这项工作是在有了最优解以后进行的，因而也称为优化后分析。 解决上面两个问题，可以用单纯形法重新进行计算，但是这样，既麻烦也不必要，我们可以利用表 14 15 、表 14 16 中的关系式： 将参数的变化直接反映到最终单纯形表上，修改原来最终单纯形表上的某些数字。在修正后的最终单纯形表中，对所得到的基本解，检验其是否满足： 1 可行性： 2 最优性： 如果可行性要求与最优性要求都得到满足，则所得解为最优解；如果可行性要求被满足，而最优性要求