运筹学1.doc

运筹学
沈轶
华中科技大学控制科学与工程系
目录
第一章 线性规划的单纯形法 1
§ 线性规划的基本概念 1
§ 线性规划的基本定理 5
§ 线性规划的图解法（变量2个） 9
§ 单纯形法 12
§ 线性规划的大M法与两阶段法 19
§ 单纯形法的评述 25
§ 单纯形法的矩阵描述 28
第二章 线性规划的对偶理论 31
§ 问题 31
§ 线性规划的对偶理论 33
§ 对偶问题的经济解释——影子价格 36
§ 对偶单纯形法 38
§ 灵敏度分析 41
第三章 运输问题 49
§ 运输问题的数学模型 49
§ 运输问题的基本性质 51
§ 表上作业法 54
§ 产销不平衡的运输问题 64
第四章 整数规划 65
§ 数学模型 65
§ 割平面法 68
§ 分枝定界法 77
§ 0-1变量的作用 80
133
第一章 线性规划的单纯形法
§ 线性规划的基本概念
1. 问题的提出
产品
Ⅰ
Ⅱ
设备
1
2
8台时
原料A
4
0
16kg
原料B
0
4
12kg
利润
2元/件
3元/件
建立数学模型：设,分别是生产Ⅰ，Ⅱ的件数，则有：
这里称为决策变量。目标函数与约束条件关于决策变量是线性的称为线性规划。
线性规划的一般形式：
2. 线性规划的标准形
特点：目标函数求极大；等式约束；变量非负。
令
则线性规划标准形的矩阵表达式为：
约定：
如何化标准形：
（I） 目标函数实现极大化，即，令，则；
（II）约束条件为不等式
约束条件为“” 不等式，则在约束条件的左端加上一个非负的松弛变量；
约束条件为“” 不等式，则在约束条件的左端减去一个非负的松弛变量。
（III）若存在无约束的变量，可令，其中
将线性规划
化为标准形。
3. 基本概念
（I）可行域，可行解，最优解
对线性规划的标准形
称为线性规划的可行域。
任意为线性规划的可行解，若存在，使，有

则称为线性规划的最优解，为最优值。
（II）基，基向量，基变量，非基变量，基本解，退化的基本解
令。因秩，故中存在个线性无关的列，不妨设的前个列线性无关，则称为线性规划的一个基，而称为线性规划的基向量，对应的变量称为基变量，对应的变量成为非基变量。
若令，令，则等价于。
故有。由此，得到的一个解。
这里非零分量的数目不大于，称为线性规划的基本解，
若中至少有一个为零，则称为线性规划的退化的基本解。
（III）基可行解，可行基，最优基可行解
若一个基本解又是可行解，则称为线性规划的基可行解，其对应的基称为可行基。
设是线性规划的一个基可行解，若对任意可行解，都有
则称是线性规划的一个最优基可行解。
（IV）凸集与凸线性组合
设，若有
则称为凸集。
设,则称
是的凸线性组合。
设是凸集，，若不能表示为中不同两点的凸线性组合，则称是凸集的顶点。
§ 线性规划的基本定理
定理1. 线性规划的可行域是凸集。
定理2. 设是线性规划的可行解，则是基可行解的充要条件是的正分量所对应的系数列向量线性无关。
证明： 必要性
由基可行解的定义可知。
充分性
若向量线性无关，则有。当时，它恰好构成线性规划的一个基，从而为相应的基可行解；当时，则一定可以从其余的列向量中取定个与构成其最大线性无关组，其对应的解恰为，且是基可行解。
定理3. 线性规划的基可行解对应于可行域的顶点。
证明：必要性。设是基可行解，要证明是可行域的顶点。若不是可行域的顶点，则必存在可行域中不同的两点与及，使

因是基可行解，不妨设的前个分量是正，而其余的为零，这里，因此有

且，由，与，，，必可推出
于是有

上面两式相减，有

而，因此有线性相关，这与线性无关矛盾。
充分性。设是可行域的顶点，要证明是基可行解。因是可行域的顶点，不妨设，而0，。若不是基可行解，则由定理1知：线性相关。因此存在不全为0的数，使：
而
因此有

因，取充分小，必可使。令
故有