《运筹学(fuxi)》由会员分享，可在线阅读，更多相关《运筹学(fuxi)（118页珍藏版）》请在金锄头文库上搜索。
1、运 筹 学绪论 第一章 线性规划与单纯形法 第二章 线性规划的对偶理论与灵敏度分析 第三章 运输问题 第四章 目标规划 第五章 整数规划 第八章 图与网络分析第一章 线性规划与单纯形法三要素组成:1.变量:决策变量(x1 , x2 xn) 2.目标函数:决策变量的函数,系统要达到的目标 3.约束条件:对决策变量的限制若：决策变量的取值是连续的,且目标和约束条件 为决策变量的线性函数和线性等式或不等式,则该 类规划问题为线性规划问题。解决问题的共同点: 在现有各项资源条件限制下,如何确定方案,使预期 目标达到最优（1）线性规划问题的数学模型一般可表示为： max(min) z =c1x1+ c2
2、x2 + + cnxna11x1+ a12x2 + + a1nxn (或=，)b1a21x1+ a22x2 + + a2nxn (或=，)b2am1x1+ am2x2 + + amnxn (或=，)bmst.x1, x2 , , xn0设线性规划中有n个决策变量,用xj(j-=1,2,n);目标函数中 xj(j-=1,2,n)的系数为cj(j-=1,2,n);用bi表示第i(i=1,2,m) 种资源限制; aij表示决策变量xj取值为1个单位时消耗的第i种 资源量。（2）一般模型的简写形式max(min) z =c1x1+ c2x2 + + cnxna11x1+ a12x2 + + a1nxn
3、 (或=，)b1a21x1+ a22x2 + + a2nxn (或=，)b2am1x1+ am2x2 + + amnxn (或=，)bmst. x1, x2 , , xn0（3）数学模型的向量形式：max(min) z =c1x1+ c2x2 + + cnxna11x1+ a12x2 + + a1nxn (或=，)b1a21x1+ a22x2 + + a2nxn (或=，)b2am1x1+ am2x2 + + amnxn (或=，)bmst.x1, x2 , , xn0C = (c1, c2 , , cn) X= (x1, x2, , xn)TPj= (a1j, a2j, , amj)Tb=
4、(b1, b2, , bm)T（4）数学模型的矩阵形式：max(min) z = CXAX(或=, )bX 0st.am1 am2 amna11 a12 a1nA=a21 a22 a2nx1X=x2xnb=（b1 b1 bm）Tmax(min) z =c1x1+ c2x2 + + cnxna11x1+ a12x2 + + a1nxn (或=，)b1a21x1+ a22x2 + + a2nxn (或=，)b2am1x1+ am2x2 + + amnxn (或=，)bmst.x1, x2 , , xn0线性规划的应用条件1、要解决的问题的目标可以用数值指标反应 ；2、对于要实现的目标有多种方案可选
5、择；3、有影响决策的若干约束条件。规定线性规划问题的标准形式如下：规定线性规划问题的标准形式如下：（4） 变量无约束，或称为自由变量。对于自由变量，通 常引入两个新的非负变量，比如，令xj = xj xj ，其中， xj ， xj 0 （5） 如果 x 0，则令 x = - x，显然， x 0对不符合上述标准形式的线性规划问题，进行标准化处理标准化处理：（1）目标函数为求极小值。因为求min z 等价于求max(z), 所以，可以令z=-z， 求max z即可。（2）右端常数项小于零。只需将不等式或等式两边同乘1 。 （3）约束条件为不等式。 对于“”符号的不等式约束，左边 减去一个非负变量变
6、为等式约束，新变量称为剩余变量，或 松弛变量；对于“”符号的约束，左边加上一个非负变量变为 等式，新变量称为松弛变量。（1）min z = x1+2x2 +3x3 令Z=-Z min Z=min（-z ）=max z 则 min z = x1+2x2 +3x3则 max z = -x1-2x2 -3x3（2） 2 x1+x2 +x3 92 x1+x2 +x3 + x4 =9 3 x1+x2 +2x3 43 x1+x2 +2x3 x5 = 4min z = x1+2x2 +3x3st. 2 x1+x2 +x3 9 3 x1+x2 +2x3 44 x12x2 3x3 =6x1 0, x2 0, x
7、3 无约束。4 x12x2 3x3 =6-4 x1+2x2 + 3x3 =6（3）x1 0, x2 0, x3 无约束令x1 =- x1, x3 = x3 - x3” max z =x1-2x2 -3(x3 - x3” )st.2 x1+x2 +(x3 - x3” )+ x4 = 93 x1 +x2 +2 (x3 - x3” ) x5 = 4-4 x1 +2x2 +3 (x3 - x3” ) =6x1 0, x2 0, x3 0 x3” 0x4 0, x5 0解的概念(1)(1)可行解可行解:满足所有约束条件（1-2，1-3）的解称为线性规划 问题的可行解。 (2)(2)最优解最优解: :使目
8、标函数（1-1）达到最大值的可行解称为最优解 。 (3)基：满秩子矩阵 ( (4)4)基基 解解:在约束方程组中，令所有非基变量 xj (j = m+1 n)取 零值。因为 子矩阵B是满秩的，根据克莱姆法则,由m个约束方 程可以解出m个基变量xi(i = 1 m)的唯一解,X B=(x1, x2, xm)T 。我们把X = (x1, x2, xm，0，0)T 称为基解 (5)(5)基可行解基可行解: 满足非负性约束条件(1-3)的基解称为基可行解。 (6)(6)可行基可行基: 对应于基可行解的基称为可行基. (7)退化解 :如果基变量某些分量取零值，则称该解为退化解。max z = x1+2x
9、2 +3x3x1+x2 +x3 =3 3 x1+2x2 -4x3 =2x1 0, x2 01 1 1-3 2 -4A=1 1-3 2B1=x1=4/5 x2=11/5 1 1-3 -4B2=x1=14 x3=-111 12 -4B3=x2=7/3 x3=2/3图解法图解法的结局图解法的结局1）唯一最优解。2）无穷多最优解。3）无界解。可行域无界所致。说明建立数学模型时遗 漏了某些必要的资源约束。4）无可行解。无可行域,约束之间互相矛盾。图解法的启示图解法的启示 1）如果线性规划问题的可行域存在，则可行域是一个凸集 。 2 ）如果线性规划问题存在最优解，则最优解（或之一）在凸 集的顶点上达到。用
10、图解法求解线性规划时，各种求解结果与各种求解结果与 各种类型的可行域之间的对应关系各种类型的可行域之间的对应关系可以用下图加 以描述：定理定理1 1：若线性规划问题存在可行解，那么，问题的 可行域是凸集。引理引理1 ：线性规划问题的可行解 X = (x1, x2, xn )T 为 基可行解的充要条件是X 的正分量对应的系数列向量 是线性独立。定理定理2 2：线性规划问题的基可行解 X 对应于线性规划 问题可行域（凸集）的顶点。定理定理3 3：若线性规划问题有最优解，一定存在一个基 可行解是最优解。几个定理上述基本定理给出一条清晰的思路：线性规划问题的最优解在可行域的顶点上达到；线性规划问题的每
11、个基可行解对应可行域的一个 顶点；基可行解是基解与可行解的交集；基解的数目不超过组合数 所以，可以通过基解、顶点寻找线性规划问 题的最优解。可行域可行解基可行解基可行解基可行解基可行解基可行解几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集 ： 凸多边形满足一组不等式约束的解约束直线的交点基解可行域的顶点基可行解目标函数等值线 ： 一组平行线 目标函数值等于一个常 数的解将基可行解X（0）和 X（1）代入目标函数，得检验数检验数 ： 判别定理：（1）当所有的检验数都 j 0 时 ，新基可行解X（1）的目标函数值小于X（0）的 目标函数值，这说明，目前
12、的基可行解（顶 点）就是最优解。最优性检验和解的判断（2）当所有的检验数j 0 时，又有某一个 非基变量的检验数等于零，表明新基可行解与 原来的基可行解有相同的目标函数值，则问题 具有无穷多最优解。 （3）与之相应，如果所有非基变量的检验数 j0，则线性规划问题具有唯一最优解。 （ 4）如果某个非基变量的检验数 j 0， 而它所对应的系数列向量Pj 0，则线性规划 问题具有无界解。*注意，在X（1）的各个分量无限增大时，目标函数值无限增加，所以，线性规划问题具有无界解。由于Pj 0，对 任意的单纯形法计算步骤1.求初始基可行解，列出单纯形表 2. 最优性检验3. 基变换（从一个基转换到另一个基
13、）4. 重复步骤2和3，求出最优解备注：单纯形表中必须有备注：单纯形表中必须有m m个基变量，以及和它们对个基变量，以及和它们对 应的应的m m个单位列向量个单位列向量单位方阵。单位方阵。cj c1cj cm cn CB c1 c2cmXB x1 x2xmb b1 b2bmx1 100xm 0 01 xj a1j a2 jam j xn a1n a2namn(检验数）001 求初始基可行解，列出单纯形表从表中可以看出： （1）所有基变量对应的检验数都为零。 （2）所有非基变量的检验数都是按特定的公式计 算的，即对于求极大化问题， 如果所有的检验数0，则已获得最优解，计算 结束。 如果某个非基变量的检验数0，且它所对应 的系数列向量0，则问题 具有无界解，结束计算 。 其他情况下，转下一步骤。2 最优性检验3 基变换 （1）确定换入基的变量。 只要非基变量的检验数大于零，都可以作为换入变 量。但是，当有一个以上检验数大于零时，人们习惯习惯 选择检验数最大选择检验数最大的变量 xk 作为换入变量。（2）确定换出基的变量。
