第一章线性规划与单纯形法

1第一章

线性规划与单纯形法2第一节线性规划问题及其数学模型1.1问题的提出例1

某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如下表：问题：如何安排生产才能使工厂获利最多？3线性规划模型三个要素决策变量

目标函数约束条件4例2

靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20％可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2％。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米，第二化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。工厂1工厂2500万立方米200万立方米5例3：下料问题

某工厂要做100套钢架，每套有长2.9米、2.1米和1.5米的圆钢组成，已知原料长7.4米，问应如何下料使需用的原材料最省。方案1方案2方案3方案4方案5方案6方案7方案82.9m120101002.1m002211301.5m31203104合计7.47.37.27.16.66.56.36.0剩余料头00.10.20.30.80.91.11.46线性规划的一般模型技术系数价值系数资源系数例1

某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如下表：问题：如何安排生产才能使工厂获利最多？7价值系数技术系数资源系数34840x2x1A1.2线性规划的图解法1.画可行域2.画等值线3.找最优解步骤惟一最优解34840x2x1AB无穷多最优解（多重最优解）34840x2x1-2无可行解x1x2024无界解解的情况总结12有最优解无最优解惟一最优解无穷多最优解无可行解无界解图解法的局限与启示局限：只能求解两个变量的线性规划问题启示:通过图解法，能够直观的看到，如果线性规划问题有最优解，一定能够在其顶点上达到最优。131434840x2x1A惟一最优解1534840x2x1AB无穷多最优解（多重最优解）16171.3线性规划问题的标准形式我们规定的标准形式要求：目标函数求极大值所有约束为等式约束条件右端项都大于等于零所有变量都大于等于零18练习19一般形式简写形式向量形式矩阵形式201.4线性规划问题解的概念可行解：满足所有约束条件的解，称为线性规划问题的可行解。最优解：使目标函数值达到最优的可行解。基：设A是约束方程组的m×n维系数矩阵，其秩为m。B是矩阵中m阶非奇异子矩阵，则称B是线性规划问题的一个基。基变量：与基向量对应的变量。非基变量：与非基向量对应的变量。基解：令非基变量为零，求解方程组,得到一个基解。基可行解：满足非负条件的基解。可行基：对应于基可行解的基，为可行基。21例题思考非基变量取值是否为零？取值为零的变量是否一定为非基变量？大于零的变量是否是基变量？基变量的系数列向量是否一定线性无关？22解之间的关系23可行解基解非可行解基可行解例题2425第二节线性规划问题的几何意义2.1基本概念凸集：设K是n维欧式空间的一点集，若任意两点的连线上的一切点都属于K；则称K为凸集。凸集凸集不是凸集极点26两点连线上的点的数学表示方法27282.2几个定理例题2930特殊情况有时目标函数可能在多个顶点处达到最大值。这时在这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个（无穷多个）最优解。若可行域无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。31结论

线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。33第三节单纯形法

单纯形法的基本思路：根据问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数值达到最优时，问题就得到了最优解。343.1举例35(1)(2)36几何意义分析

37(1)38几何意义分析

无穷多最优解举例39无界解举例40入基，由方程组可知，可以无限增加，所以目标函数可以趋向于无穷大，此时为无界解。413.2初始可行基的确定1.直接观察2.对所有约束条件是“≤”的不等式，可在每个不等式左端引入一个松弛变量，变成标准型，从而得到一个初始基可行解。3.不存在单位阵时，采用人造基方法。423.3最优性检验与解的判别

（目标函数求极大）最优解判别定理：若非基变量的系数（检验数）都小于等于零，则为最优解。无穷多最优解判别准则：若非基变量的检验数都小于等于零，且其中至少有一个为零，则线性规划问题有无穷多个最优解。无界解（无最优解）判别定理：对于一个基可行解，若有一个检验数大于零，且该检验数对应的所有系数都小于等于零，则该线性规划问题具有无界解（无最优解）。433.4基变换（一个顶点变换到另一个顶点）换入变量确定：一般选择绝对值最大的，但也可以任选或按最小号码选。换出变量确定：最小比值原则。其原理是保证所有变量都为非负。443.5迭代（旋转运算）

利用系数的增广矩阵进行初等变换来实现。将主元素变为1。将入基变量所对应的列向量变为单位向量。45第四节单纯形法的计算步骤4.1单纯形表若线性规划问题目标函数为：约束条件为：增广矩阵为：46根据增广矩阵设计计算表473.1举例484.2计算步骤49例题50单纯形法的求解步骤目标函数求极大初始可行基（单位阵）解的判别所有非基变量检验数都小于零，得惟一最优解所有非基变量检验数都小于等于零，且至少有一个为零，得无穷多最优解。如果有一个非基变量的检验数大于零，而其在方程组中的系数都小于等于零，为无界解。迭代入基变量：检验数大于零出基变量：最小比值原则方程组求解（矩阵初等行变换）目标函数求极小初始可行基（单位阵）解的判别所有非基变量检验数都大于零，得惟一最优解所有非基变量检验数都大于等于零，且至少有一个为零，得无穷多最优解。如果有一个非基变量的检验数小于零，而其在方程组中的系数都小于等于零，为无界解。迭代入基变量：检验数小于零出基变量：最小比值原则方程组求解（矩阵初等行变换）5152例8第五节单纯形法的进一步讨论531.大M法在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值没有影响，为此假定人工变量在目标函数中的系数为（-M）（M为任意大的数），（若目标函数值为求最小值，则人工变量在目标函数中的系数为M）。这样目标函数要实现最大化时，必须把人工变量从基变量换出，否则目标函数不可能实现最大化。54例8原问题新问题552.两阶段法第一阶段：不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数，要求其实现最小化。用单纯形法求解此模型，若目标函数值等于零，说明原问题有基可行解，可以进行第二阶段计算，否则原问题无可行解，应停止计算。第二阶段：将第一阶段得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。

实质是：第一阶段为原问题找出了一个基可行解。56例9第一阶段原问题1.6第一阶段605.2退化

单纯形法计算中，用最小比值原则确定出基变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。当出现退化时，有时会出现计算过程的循环，永远达不到最优解。可由勃兰特规则求解。迭代六次后，出现循环615.3检验数的几种表示形式62第六节应用举例63某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D，数据如下表。问：该厂应如何安排生产，使利润收入为最大？例11：配料问题64

某部门在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，