第 2 次课 2学时。
本次课教学重点：
线型规划模型有关概念、**法求解线型规划模型。
本次课教学难点：
线型规划模型有关概念、各种解的情况分析。
本次课教学内容：
第二章线性规划的**法。
第一节问题的提出。
一、引例。例1. 某工厂在计划期内要安排ⅰ、ⅱ两种产品的生产，已知生产单位产品所需的设备台时及a、b两种原材料的消耗、资源的限制，如下表：
问题：工厂应分别生产多少单位ⅰ、ⅱ产品才能使工厂获利最多？
解：分析问题后可得数学模型：
目标函数：
约束条件：
这是一个线性规划模型，因为：目标函数是线性函数，约束条件是一些线性的等式或不等式。若目标函数是非线性函数，或约束条件中有非线性的等式或不等式，则这样的问题称为非线性规划。
二、 一般建模过程。
1.理解要解决的问题，了解解题的目标和条件；
2.定义决策变量，每一组值表示一个方案；
3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；
4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。
三、 线性规划模型的一般形式。
目标函数：
约束条件。第二节**法。
对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法。
一、 有关概念。
1、 可行解：满足约束条件的解。
2、 可行域：全体可行解的集合。
3、 最优解：使得目标函数值达到最优的可行解。
4、 凸集。
5、 松弛变量。
二、 **法求解线性规划。
例1. 目标函数：
约束条件：
解：1)分别取决策变量为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。
2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。
3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。
4）目标函数，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到b点时，z在可行域内实现了最大化。a，b，c，d，e是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。
综上得到最优解：
最优目标值
三、线性规划问题解的情况。
1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；
2、无穷多个最优解。
若将例1 中的目标函数变为，则线段bc 上的所有点都代表了最优解；
3、 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。
一般来说，这说明模型有错，忽略了一些必要的约束条件；
4、 无可行解。
若在例1 的数学模型中再增加一个约束条件，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。
例2． 某公司由于生产需要，共需要a，b两种原料至少350吨（a，b两种材料有一定替代性），其中a原料至少购进125吨。但由于a，b两种原料的规格不同，各自所需的加工时间。
也是不同的，加工每吨a原料需要2个小时，加工每吨b原料需要1小时，而公司总共有600个加工小时。又知道每吨a原料的**为2万元，每吨b原料的**为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买a，b两种。
原料，使得购进成本最低？
解： 目标函数：
约束条件：
采用**法。如下图：
得q点坐标（250，100）为最优解。
教学组织。1、课堂讲授。
2、多**图形演示。
作业布置：
1、p23.2（1，2）
第 3 次课 2学时。
本次课教学重点：
化标准型、灵敏度分析。
本次课教学难点：
灵敏度分析。
本次课教学内容：
第三节**法的灵敏度分析。
一、线性规划模型的标准形式。
目标函数：
约束条件。标准形式四个特点：
1．目标最大化； 2．约束为等式； 3．决策变量均非负； 4．右端项非负。
二、线性规划模型标准化。
1.极小化目标函数的问题：
设目标函数为
(可以)令 z ＝ f ， 则该极小化问题与下面的极大化问题有相同的最优解，即。
但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即。
min f ＝ max z
2、约束条件不是等式的问题：
（1）设约束条件为。
可以引进一个新的变量，使它等于约束右边与左边之差。
显然， 也具有非负约束，即，这时新的约束条件成为。
（2）当约束条件为。
时，类似地令。
显然， 也具有非负约束，即，这时新的约束条件成为。
3.右端项有负值的问题：
在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如，则把该等式约束两端同时乘以-1，得到：
为了使约束由不等式成为等式而引进的变量，当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。
例：将以下线性规划问题转化为标准形式。
约束条件：
x1 , x2 , x3 ≥ 0
解：首先，将目标函数转换成极大化： 令
次考虑约束，有2个不等式约束，引进松弛变量。
三个约束条件的右端值为负，在等式两边同时乘-1。
通过以上变换，可以得到以下标准形式的线性规划问题：
约束条件：
4. 变量无符号限制的问题。
在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj = xj’- xj” 其中xj’≥0，xj”≥0
即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。
三、 灵敏度分析。
灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）变化时，对最优解产生的影响。
1．目标函数中的系数的灵敏度分析。
的变化只影响目标函数等值线的斜率，不影响可行域。
考虑例1的情况，目标函数
在 (斜率为0 ) 到 (斜率为)之间时，原最优解仍是最优解。
一般情况：；写成斜截式
目标函数等值线的斜率为 ， 当时，原最优解仍是最优解。
假设产品ⅱ的利润100元不变，即，代到式（*）并整理得。
假设产品ⅰ的利润 50 元不变，即，代到式（*）并整理得。
运筹学第二章答案
1 某人根据医嘱，每天需补充a b c三种营养，a不少于80单位，b不少于150单位，c不少于180单位 此人准备每天从六种食物中摄取这三种营养成分 已知六种食物每百克的营养成分含量及食物 如表2 22所示 1 试建立此人在满足健康需要的基础上花费最少的数学模型 2 假定有一个厂商计划生产一中药丸，...
运筹学第二章课后题
习题2.1 某厂利用a b两种原料生产甲 乙 丙三种产品，已知单位产品所需的原料 利润及有关数据如表2 3所示。表2 3两种原料生产三种产品的有关数据。请分别回答下列问题 1 求使该厂获利最大的生产计划。2 若产品乙 丙的单位利润不变，当产品甲的单位利润在什么范围内变化时，最优解不变？3 若原料a市...
第二章习题运筹学汇总
第二章习题。12 对于下面的线性规划问题，以为基写出相对应的典式。解 由题可以知 取一个基，即 且。在matlab中可以计算得到 由可得典式的目标函数 由可得 由此与题中线性规划问题相对应的典式为 14 用单纯形法求解线面的线性规划问题，并在平面上画出迭代点走过的路线。解 由题先将题中线性规划问题化...