课程：运筹学.docx

课程：运筹学
代课教师：***
学号.***
姓名：*** 日期：2014年1月3日
一、运筹学简介
运筹学概念
运筹学是一应用数学和形式科学的跨领域研究，利用统计学、数学模型和算 法等方法，去寻找复杂问题中的最佳或近似最佳令z，=-z,于是得到maxz，=-CX。这就同标准型的目 标函数的形式一致了。
约束方程为不等式。这里有两种情况：一种是约束方程为不等式， 则可在不等式的左端加入非负松弛变量，把原“京”不等式变为等式；另 一种是约束方程为“N”不等式，则可在“3”不等式的左端减去一个非负剩余 变量(也可称松弛变量)，把不等式约束条件变为等式约束条件。
标准型式中规定各约束条件的右端项bi > 0,否则等式两端乘以
①当xj为自由变量时，即xjG (-8, +8)时，取xj'、Xj"均30,令xj=xj' ~xj"；②当xj为有界变量，艮hjWxjWHj,对上述三端减去hj, OWxj-hjWHj-hj, 令 xj' =xj-hj,从而 xj' 30 , xj' WHj-hj；③xjWO 时，令 xj' =xj 即可。
线性规划解的基本概念
考虑 max Z=CX (1)
AX=b (2) -
X30 (3) 一
可行解：满足(2) (3)的X即可行解。
最优解：满足(2) (3)并使目标达到最大值的可行解。
基：A的一个满秩m个方程B,称一个基，基的个数不超过W个。
基向量：设 B= (Pjl, Pj2, •••Pjm)为一个基，则 Pjl, Pj2, -Pjm 关于 B的基向量。其余向量为非基向量。
C5)基变量：设B= (Pjl, Pj2, •,•Pjm)为 基，B对应的变量xjl, xj2,… xjm称为基变量。其余变量为非基变量。
基解：在约束方程(2)中，令非基变量等于0,求得的惟一解为基解，基 解不一定是可行解，可行解不一定是基解，不超过W个。
基可行解：满足(3)的基解，不超过W个。
可行基：对应于基可行解的基。
线性规划问题的几何意义
线性规划问题的基可行解对应于可行域的顶点。基可行解是顶点的充要条件。 基可行解携易若线性规划有多个最优解，则其凸组合也是最优解，即线性规划 的解不惟一，则必有无穷多个；若线性规划问题存在最优解，则最优解可在某顶 点达到。
单纯形法
1)初始基可行解的确定。
(1)当线性规划问题的约束条件为“正典式时”，显然有一个可行解X<0) = (bL b2,…bm, 0, •,•O) To
（2） 当所有约束条件为“W”时，引入松弛变量后，就成为一个正典式。
（3） 当某个约束条件为“3”或“=”但不为正典式，再引入人工变量，即为正 典式。
2）最优性检验与解的判别。
（1） 最优判别定理：设X（°）= （bl, b2, •••bm, 0, •••（））「为一个基可行解，若所
有（j=m+l,---n）贝UX（。）为最优解（刍称作检验数或判别数）。
（2） 无穷多最优解的判别定理：设X（o）= （bl, b2, •••bm, 0, •••（））'为一个基可
行解，若所有（j=m+l, •••!：）而且有某个am+k=Q且Pm+k有正分量，则有无 穷多个最优解。
（3）解无界判别定理：设X（o）= （bl, b2,…而，0, •••（））"为一个基可行解，若存 在某个am+k>Q且Pm+kWO,则线性规划问题解无界。
3） 迭代过程
（1） 给主元alk所在的行除以alk。
（2） 给主元所在行分别乘以适当的数字，将alk所在的列除主元以外，全化为 若O
4） 单纯形法的计算步骤。
（1） 把线性规划问题化为正典式，同时建立单纯形表。
（2） 检验判别数，若所有判别数勺京0则该解为最优解，停止迭代，否则转下一 止
Zp* o
（3）在判别数0.>0中有一个兴>0且PkWO,则解无界，停止迭代，否则转下
（4）根据max{o/ |（j/ >0}=crk确定xk为进基变量，根据0规则，{专J aik>0）=会确 定xl为出基变量，alk为主元。
alk
（5）以M为主元进行迭代，将M所在的列富］=alk 变换为
amk
（0,0, •••1, -0,0） T（其中第1行为1,其余全为0元素），得到一新单纯形表, 转入第二步，重复第二至第五步，直到满足要求。
单纯形法的进一步讨论。
1）判别数的几种形式。
判别准则
max Z=CX
AX=b
XNO
min Z=CX
AX=b
XNO
°i=ci ~ zi
WO
Oj30
°j=zj ~ cj
OjNO
(jjWO
2）人工变量法。
（1） 大M法：当目标为求最小值时，引入人工变量后，取M>0