运筹学
沈轶
华中科技大学控制科学与工程系
目录
第一章 线性规划的单纯形法 ....................................................................................................... 1 §1.1 线性规划的基本概念 ............................................................................................................ 1 §1.2 线性规划的基本定理 ............................................................................................................ 4 §1.3 线性规划的图解法（变量?2个） ..................................................................................... 7 §1.4 单纯形法 ................................................................................................................................ 9 §1.5 线性规划的大M法与两阶段法 ........................................................................................ 14 §1.6 单纯形法的评述 .................................................................................................................. 19 §1.7 单纯形法的矩阵描述 .......................................................................................................... 20 第二章 线性规划的对偶理论 ..................................................................................................... 22 §2.1 问题...................................................................................................................................... 22 §2.2 线性规划的对偶理论 .......................................................................................................... 24 §2.3 对偶问题的经济解释——影子价格 .................................................................................. 27 §2.4 对偶单纯形法 ...................................................................................................................... 29 §2.5 灵敏度分析 .......................................................................................................................... 31 第三章 运输问题 ......................................................................................................................... 39 §3.1 运输问题的数学模型 .......................................................................................................... 39 §3.2 运输问题的基本性质 .......................................................................................................... 40 §3.3 表上作业法 .......................................................................................................................... 42 §3.4 产销不平衡的运输问题 ...................................................................................................... 50 第四章 整数规划 ......................................................................................................................... 51 §4.1 数学模型 .............................................................................................................................. 51 §4.2 割平面法 .............................................................................................................................. 53 §4.3 分枝定界法 .......................................................................................................................... 62 §4.4 0-1变量的作用 ................................................................................................................... 65 ........................................................................................................................ 错误！未定义书签。
第一章 线性规划的单纯形法
§1.1 线性规划的基本概念
1. 问题的提出
产品 设备 原料A 原料B 利润 Ⅰ 1 4 0 2元/件 Ⅱ 2 0 4 3元/件 8台时 16kg 12kg 建立数学模型：设x1,x2分别是生产Ⅰ，Ⅱ的件数，则有：
maxz?2x1?3x2?x1?2x2?8?4x?16?1?4x2?12???x1,x2?0
这里x1,x2称为决策变量。目标函数与约束条件关于决策变量是线性的称为线性规划。
线性规划的一般形式：
max(min)z?c1x1?c2x2?...?cnxn?a11x1?a12x2?...?a1nxn?(?,?)b1??a21x1?a22x2?...?a2nxn?(?,?)b2? ...??ax?ax?...?ax?(?,?)bm22mnnm?m11??x1,x2,..,xn?(?)0或无约束2. 线性规划的标准形
1
maxz?c1x1?c2x2?...?cnxn?a11x1?a12x2?...?a1nxn?b1?ax?ax?...?ax?b2112222nn2??...??ax?ax?...?ax?bmnnm?m11m22??x1?0,x2?0,...,xn?0特点：目标函数求极大；等式约束；变量非负。
令c?(c1,c2,...,cn),x?(x1,x2,...,xn)T,A?(aij)m?n，b?(b1,b2,...,bm)T 则线性规划标准形的矩阵表达式为：
maxz?cxAx?b
x?0约定：b?0,m?n,秩A?m.
如何化标准形：
（I） 目标函数实现极大化，即minz?cx，令w??z，则maxw??cx； （II）约束条件为不等式
约束条件为“?” 不等式，则在约束条件的左端加上一个非负的松弛变量； 约束条件为“?” 不等式，则在约束条件的左端减去一个非负的松弛变量。
''''''（III）若存在无约束的变量xk，可令xk?xk，其中xk?xk?0,xk?0.
例1． 将线性规划
minz??x1?2x2?x1?x2?x3?2 ?x?x?x?1?123?x?0,x?0,x无约束23?1化为标准形。
3. 基本概念
（I）可行域，可行解，最优解 对线性规划的标准形
maxz?cxAx?b x?0 2
称???x?Rn|Ax?b,x?0?为线性规划的可行域。
任意x??为线性规划的可行解，若存在x*??，使?x??，有
cx?cx*
则称x*为线性规划的最优解，cx*为最优值。
（II）基，基向量，基变量，非基变量，基本解，退化的基本解
令A?(p1,p2,...,pm,pm?1,...,pn)。因秩A?m，故A中存在m个线性无关的列，不妨设A的前m个列线性无关，则称B?(p1,p2,..,pm)为线性规划的一个基，而
p1,p2,...,pm称为线性规划的基向量，p1,p2,...,pm对应的变量x1,x2,...,xm称为基变量，pm?1,...,pn对应的变量xm?1,...,xn成为非基变量。
若令xB?(x1,x2,...,xm)T，令xm?1?...?xn?0，则Ax?b等价于BxB?b。
?1?Bb??1x?Ax?b故有xB?Bb。由此，得到的一个解??。
0???B?1b?这里非零分量的数目不大于m，称x???为线性规划的基本解，
?0??B?1b?若Bb中至少有一个为零，则称x???为线性规划的退化的基本解。
0???1（III）基可行解，可行基，最优基可行解
若一个基本解又是可行解，则称为线性规划的基可行解，其对应的基称为可行基。
设x*是线性规划的一个基可行解，若对任意可行解x，都有
cx?cx*
则称x*是线性规划的一个最优基可行解。 （IV）凸集与凸线性组合
设K?Rn，若?x(1),x(2)?K,t??0,1?有
tx(1)?(1?t)x(2)?K
则称K为凸集。
3