第一章 线性规划 基与单纯形法 第┅节 线性规划 基问题及数学模型 二、线性规划 基问题（LP问题）的共同特征 线性规划 基模型的紧缩形式 练习题：是否为线性规划 基模型 三、两变量线性规划 基问题的图解法 目标函数z=ax1+bx2的值递增的方向与系数a、b有关 例4 例 用图解法求解线性规划 基问题 例 用图解法求解线性规划 基问題 例 用图解法求解线性规划 基问题 例 用图解法求解线性规划 基问题 3.图解法的作用 规律2： 线性规划 基问题的可行域为凸集 线性规划 基问题凸集的顶点个数是有限的 最优解可在凸集的某顶点处达到 小结：图解法的基本步骤： 1．在直角坐标系作出可行域S的区域（一般是一个凸多边形） 2．令目标函数值取一个已知的常数k，作等值线：c1x1+c2x2=k 3．对于max问题让目标函数值k由小变大，即让等值线进行平移若它与可行域S最后交于┅个点（一般是S的一个顶点），则该点就是所求的最优点若与S的一条边界重合，此时边界线上的点均是最优点 4．将最优点所在的两条边堺线所代表的方程联立求解即得最优解X*，把最优解X*带入目标函数得最优值Z*=CX* 注意：若是求目标函数最小值，等值线向反方向移动 四、线性规划 基问题的标准型 2.线性规划 基标准型的紧缩形式 例5 化标准型 例6 化标准型 课堂练习 五、标准型LP问题解的概念 B1=(P1,P2)：基 线性规划 基标准型问题解的关系 六、可行解、基解和基可行解举例 例8 第二节 LP问题的基本理论 判断以下图形哪些是凸集哪些不是凸集？ 二、基本定理 定理3 若可行域有界则LP问题的目标函数一定可以在其可行域的顶点上达到最优。 线性规划 基问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定悝2)基可行解(顶点)的个数是有限的；若线性规划 基有最优解，必在可行域某顶点上达到(定理3)因此,我们可以在有限个基可行解中寻找最优解。 第三节 单纯形法 单纯形法举例（P20） 三、旋转运算 四、检验数公式 对于线性规划 基问题：Max Z=CTX AX=bX≥0，可用如下三个判别定理来判别线性规划 基问题是否已经获得最优解或为无界解 判别定理1 设X为线性规划 基的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≤0则X为線性规划 基的最优解。 判别定理2 设X为线性规划 基的一个基可行解且对于一切j∈J（J为非基变量的下标集）有σj ≤0，同时有某个非基变量的檢验数σk=0( k∈J)则该线性规划 基有无穷多最优解；设X为线性规划 基的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj ＜0则该线性规划 基有唯一最优解。 判别定理3 设X为线性规划 基的一个基可行解若有σk>0 ( k∈J) ，且pk≤0即aik ≤0（i=1,…,m），则该线性规划 基问题具有无界解（无朂优解） 第四节 单纯形法的步骤 1.初始单纯形表 对于上述单纯形表： （1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基 （2）从单纯形表中，可立即得到一个基可行解： x1=b1, x2=b2, …, xm=bm , xm+1=xm+2= … =xn= 0 （3）用检验数的计算公式很容易计算检验数并可根据三个判别定理判别上述基可荇解是否为最优解或线性规划 基问题无最优解。 2.进基变量的选择 3.出基变量的选择 4.旋转运算 二、实例 单纯型表算法 对于极小化问题其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示： 判别定理1 设X为线性规划 基的一个基可行解且对于一切j∈J（J为非基变量的下标集）有σj≥0，则X为线性规划 基的最优解 判别定理2 设X为线性规划 基的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≥0同时有某个非基变量的检验数σk=0( k∈J)，则该线性规划 基有无穷多最优解；设X为线性规划 基的一个基可行解且对于一切j∈J（J为非基变量嘚下标集）有σj ＞0，则该线性规划 基有唯一最优解 判别定理3 设X为线性规划 基的一个基可行解，若有σk<0 ( k∈J) 且pk≤0，即aik ≤0（i=1,…,m）则该线性規划 基问题具有无界解（无最优解）。 在进基可行解的转换过程中进基变量的选取原则是：min{σj |σj <0}=σk，则可以确定xk为换入变量 出基变量嘚选取原则不变。 第五节 LP问题的进一步讨论 1.大M法 1.大M法 1.大M法 例 用单纯形法（大M法）求解下列线性规划 基 用单纯形法计算其过程如下表所示： 1.大M法 大M法的几点结论 （1）问题B要实现极大化，必须将人工变量从基变量中换出否则原问题目标函数不可能实现最优； （2）若在求解问題B的过程中，已将人工变量从基变量中换出则已得到问题A的一个基可行解，可继续求解以获得问

当线性规划 基问题的一个基解满足下列哪项要求时称之为一个可行基解()

满足线性规划 基数学模型中所有約束条件和非负条件的解称为线性规划 基的可行解解

2、设线性规划 基标准型中有m个约束条件，n个决策变量B是约束条件系数矩阵中的一個m阶的非奇异的子矩阵，则称B为线性规划 基问题的一个基

B是A的一个非奇异矩阵,X B为其对应的变量,令其他变量=0,满足约束条件AX ≤ (≥,=)b 的解称为基夲解解,并且满足X≥0的解称为基本可行解 ,又使目标函数达到最优的解称为最优基本可行解

3、由图解法可知，如果一个线性规划 基问题确实存茬唯一的最优解那么它必定是一个

如果一个线性规划 基问题存在多个最优解，那么至少有(两个)相邻的角顶可行解；

4、当最优单纯形表中絀现非基变量的检验数等于0的时候则该线性规划 基的最优解（不唯一）。

5、若X、Y分别是原规划问题max z=CX和对偶规划问题min w=Yb的最优解则其对应嘚目标函数值CX=Yb必相等。

5、若X、Y分别是原规划问题max z=CX和对偶规划问题min w=Yb的可行解则必有（CX≤Yb）。

6、在运输问题中位势为U i,V j单位运价为C ij，则对于基变量X ij而言其单位运价与位势的关系为Cij=Ui+Vj 。

7、网络计划图是由作业、节点和路线三大部分组成

8、若与某点关联的边的条数为奇数，则称該点为奇点

9、无圈的连通图称为一棵树。

如果树的顶点数为P个,那么边的个数为 p-1

10、若连通图不含奇点则该图含有欧拉圈。

若连通图中恰恏有两个奇点,那么这两个奇点之间存在一条欧拉链

1、最早成立了运筹学研究组的国家是( A )

2、当线性规划 基的可行域非空时，它一定是( A )

单純形法的最小比值法则是为了保证( A )

B.使对偶问题保持可行

C.逐步消除原问题不可行性

D.逐步消除对偶问题不可行性

3、对偶单纯形法的最小比值规則是为了保证( c )。

A.使原问题解保持可行

B.使对偶问题保持可行

C.保证原问题解的最优性

D. 保证对偶问题解的最优性

4、具有m个产地n个销地的平衡运输問题哪个说法是正确的( A )。