《运筹学》第一章至第节.docVIP

线性规划与单纯形法 §1 线性规划问题及其数学模型 [例] 利用现有机器台时及原料A、B生产两种产品，已知如下： 产品一 产品二 台时及原料的拥有量 生产单位产品所需设备台时（单位：台时） 1 2 8 生产单位产品消耗原料A（单位：kg） 4 0 16 生产单位产品消耗原料B（单位：kg） 0 4 12 单位产品利润（单位：元） 2 3 求达最大利润的生产方案。 解：设生产产品一、二的数量分别为x1, x2 相应线性规划问题为： 线性规划问题的特点： 一组控制变量表示某一方案 关于控制变量线性的约束条件（等式或不等式） 关于控制变量线性的目标函数 线性规划问题的一般形式： 两个变量的线性规划问题的图解法 [例1] 唯一最优解（4，2），最优值=14 [例2] 无穷多最优解（4，2），（2，3）及其中间点，最优值=16 [例3] 无界解， [例4] 无可行解，约束矛盾，可行域 由两个变量的线性规划问题的图解法得出的直观结论： 可行域D及相应最优解与最优值的可能情况： ：无可行解 且D有界：有有限的最优值（有唯一最优解或无穷多最优解） 且D无界： 有有限的最优值（有唯一最优解或无穷多最优解） 无界解(或) 若,则可行域D为有界凸多边形或无界凸区域 若有最优解，必可以在可行域D的某个顶点达到 若在两个顶点同时达到最优值，则其连线之间任一点都是最优解，即为无穷多最优解情形。 线性规划问题的标准形式 矩阵形式： 其中： 为价值向量 为约束条件的系数矩阵， 为决策变量向量， 为资源向量，且满足 将一般线性规划问题化为标准型的方法 若目标函数为，令， 若某一约束，将此约束化为： 若某一约束为，加非负松弛变量化为等式： 若某一约束为，减非负松弛变量化为等式： 若某一决策变量，令，则 若某一决策变量无约束，令，则 [例] 将如下线性规划问题化为标准型 其标准形式为： 其中，， 线性规划问题解的概念 对标准型： （） [定义] 可行域： 可行解： 最优解： 最优值： 基B：B 为系数矩阵A的m阶非奇异子矩阵 基变量： 与基B的列对应的决策变量，常记为向量 非基变量：与A中除基B外的列对应的决策变量，常记为向量 基解：对某一基B，令非基变量后，求出基变量的值，为与此基B对应的基解，若基变量中有分量为零，则为退化的基解。 基可行解：若某基B对应的基解满足，则称为基可行解 可行基：与基可行解对应的基称为可行基 [例] 对线性规划模型: 讨论其基、基解、基可行解等有关基本概念。 解：首先化为标准型： 系数矩阵 可能的基 基 相应基解 基可行解 几何点 z值 1 √ （4，3，-2，0，0） × A (4,3) 2 √ （2，3，0，8，0） √ B (2,3) 13 3 √ （4，2，0，0，4） √ C (4,2) (最优解) 14 (最优值) 4 × 5 √ （4，0，4，0，12） √ D (4,0) 8 6 √ （8，0，0，-16，12） × E (8,0) 7 √ （0，3，2，16，0） √ F (0,3) 9 8 × 9 √ （0，4，0，16，-4） × G (0,4) 10 √ （0，0，8，16，12） √ O (0,0) 0 下图中标出了基解与基可行解对应的几何点A，B，C，D，E，F，G，O，其中基可行解对应可行域的顶点。 [例] 退化的基解的情形： 修正上例的第二个约束，考虑如下线性规划问题： 其标准型为： 系数矩阵 基对应的基解为：，其中为非基变量，为退化的基变量。 基对应的基解为：，其中为非基变量，为退化的基变量。 基对应的基解为：，其中为非基变量，为退化的基变量。 这里是与不同基对应的退化的基解，它们是同一个解，对应可行域的同一个顶点 §2 线性规划问题的几何意义 几何上的几个基本概念 凸集：，总有，则称K为凸集 凸组合：，则称的凸组合 凸集的顶点： 设K为凸集，，若不能用K中不同的两点的线性组合表示为：，则称为K的一个顶点 线性规划问题的基本定理 [定理1] 线性规划问题的可行域为凸集 [定理2] 线性规划问题的基可行解对应于可行域的顶点 [定