运筹学-怎样把事情做到最好培训教材(编辑修改稿)

运筹学-怎样把事情做到最好培训教材(编辑修改稿)内容摘要：

基的概念 ：如前所述 LP标准型 和式： maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n 矩阵式： maxZ=CX AX=b X ≥0 约束方程的系数矩阵 A的秩为 m，且 mn。 设A=B+N ， B是 A中 mm阶非奇异子矩阵，则称B是 LP的一个 基 ，即： B是 A中 m个线性无关向量组。 n j=1 n j=1 OR1 33 基解的概念 不失一般性 ,设 B是 A的前 m列 ,即B=(p1,p2,…,p m） ,其相对应的变量XB=(x1,x2,…,x m)T,称为基变量；其余变量XN=(Xm+1,… ,Xn)T称为非基变量。 令所有非基变量等于零 ,则 X=（ x1,x2,… xm,0,… ,0)T称为基解。 OR1 34 基可行解的概念  基可行解： 基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为 基可行解。  退化的基可行解 ： 若某个基变量取值为零，则称之为退化的基可行解。  基解的数目：最多 Cmn=n!/m!(nm)! OR1 35 例题 6 基可行解说明 maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj≥0 j=1,2,…,5 这里 m=3,n=5。 Cmn=10 OR1 36 例题 6 基可行解说明  基（ p3,p4,p5） ，令非基变量 x1,x2=0，则基变量 x3=360, x4=200, x5=300, 可行解  基（ p2,p4,p5） ,令非基变量 x1=0,x3=0基变量x2=90,x4=－ 250,x5=－ 600. 非可行解  基（ p2,p3,p4 ），令非基变量 x1,x5=0，则基变量 x2=30, x3=240, x4=50,可行解 （ P21图） OR1 37  从系数矩阵中找到一个可行基 B，不妨设 B由 A的前 m列组成，即 B=(P1,P2,……Pm)。 进行等价变换－－约束方程两端分别左乘 B－ 1 得 X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 …………………………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m 令非基变量为 0，得基可行解 X(0)=(b1’， b2’， ……b m， 0， ……0 ） T z0=∑cibi’ OR1 38  ： LP经过若干步迭代，成为如下形式： X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1 ∑ a’1jxj x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2 ∑a’2jxj …………………………….. …………….. xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m ∑a’mjxj OR1 39 单纯形法 一般性表示 ： xi=b’i ∑a’ijxj i=1,2,…m 将 xi代入目标函数得 ： Z= ∑ cjxj = ∑ cixi+ ∑ cjxj = ∑ci（ b’i ∑a’ijxj ） + ∑ cjxj = ∑cibi’+ ∑(cj ∑ cia’ij)xj 令： σj= cj ∑ cia’ij z0=∑cibi’ 则 Z=z0+ ∑ σj xj σj判别准则 ： σj ≤0 时 ,达到最优解 OR1 40 单纯形法  若存在 σj ≥ 0，则取 max{σj } = σK ，相应之非基变量 XK若取非零，将使 Z增加 ,故令 XK 进基。 令 XK≠0 ，其余非基变量保持为零。 XK 原是非基变量，取零值， 若 XK ≠0 将迫使某个原基变量为零，当 XK取值超过任意 b’i / a’ik 时 ,将破坏非负性条件 ,于是令 θ = min {b’i / a’ik a’ik 0 } =b’L/ a’Lk。 这时原基变量 XL=0，由基变量变成非基变量， a’Lk处在变量转换的交叉点上，称之为枢轴元素 σj ≥0OR1 41 单纯形法解题举例 单纯形表的格式： Cj C1 C2 … C n θi CB XB b x1 x2 …. xn C1 C2 … Cm x1 x2…xm b 1 b2 … bm a11 a12 … a 1n a21 a22 … a 2n … … … am1 am2… a mn θ1 θ2 … θm σj σ1 σ2 … σ n OR1 42 Cj C1 C2 … C n CB XB b X1 X2 X3 X4 X5 θj 0 0 0 X3 X4 X5 360 200 300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 90 40 30 σj 0 70 120 0 0 0 0 0 120 X3 X4 X2 240 50 30 0 1 0 0 0 1 1 0 0 20。