第一章线性规划与单纯形法
一、本章考情分析：常考题型：选择填空判断计算 分值：必考知识点，30分以上,非常重要！
二、本章基本内容：１）掌握线性规划的数学模型的标准型； ２）掌握线性规划的图解法及几何意义； ３）了解单纯形法原理； ４）熟练掌握单纯形法的求解步骤；
５）能运用大Ｍ法与两阶段法求解线性规划问题； ６）熟练掌握线性规划几种解的性质及判定定理．
三、本章重难点：
重点：１）单纯形法求解线性规划问题； ２）解的性质； ３）线性规划问题建模．
难点：１）单纯形法原理的理解； ２）线性规划问题建模．
四、本章要点精讲：·要点 １ 化标准型 ·要点 ２ 图解法 ·要点 ３ 单纯形法的原理 ·要点 ４ 单纯形法的计算步骤 ·要点 ５ 单纯形法的进一步讨论
1）要点 １ 化标准型
线性规划的数学模型：Z=CX （C：价值系数） Ax=b （a：工艺或技术系数 b：资源限制）
复习思路提示：化标准型按“目标函数—资源限量—约束条件—决策变量”的顺序进行。
2）要点 ２ 图解法
线性规划解的情况有：唯一最优解、无穷多最优解、无界解、无可行解；
3）要点 ３ 单纯形法原理
解的概念与关系:基：设A是约束方程组的m*n阶系数矩阵（设n>m），其秩为m，B是A中的一个m*m阶的满秩子矩阵（B≠0的非奇异子矩阵），称 B是线性规划问题的一个基．设除基变量以外的变量称为非基变量。 基解：在约束方程组中，令所有的非基变量=0，可以求出唯一解X。 基可行解：变量非负约束条件的基解． 可行基：基可行解的基．
几个定理：１线性规划问题的可行解为基可行解的充要条件是 Ｘ的正分量所对应的系数列向量是线性独立的． ２线性规划问题的基可行解 Ｘ对应线性规划问题可行域（凸集）的顶点． ３若线性规划问题有最优解，一定存在一个基可行解是最优解．
最优解唯一时，最优解也是基最优解；当最优解不唯一时，最优解不一定是基最优解．
第3章09人工变量法之两阶段法同学们大家好，今天我们继续来学习，人工变量法这一小节。现在我们再来看第二个方法——两阶段法。大M法和两阶段法实际上各有优缺点，大M法的原理很清晰，但是在用计算机求解时，对M只能输入一个很大字长的数字，而模型的参数与M有可能比较接近，从而可能会在计算过程中发生一些错误。而两阶段法不需要设定大M，不会发生这个问题，所以，计算机程序中一般都采用两阶段法。两阶段法，顾名思义，就是把求解过程分成两个阶段进行。第一个阶段，在原模型中，引入人工变量，使约束矩阵中有一个单位阵，同时，目标函数是求人工变量的和的最小值。求解完之后，如果人工变量不取零，那么能证明原模型一定无可行解，反之，如果人工变量是都取零的，那么这个时候实际上也找到了原模型的一个可行基，然后再进一步求出原模型的解。下面我们通过例3-7进行介绍。例3-7用两阶段法求解线性规划问题
3,2,1,093124st.3max
3232132131
ixxxxxxxxxxxz
i对于这个问题，首先把它化成下面的标准型131234123523max3421st.390,1,2,,5izxxxxxxxxxxxxxi它的约束矩阵中显然没有单位阵，所以，我们下面用两阶段法进行求解。第一阶段，引入人工变量x6和x7，使得约束矩阵中有单位阵，同时，目标函数是求人工变量的和的最小值，也就是，先求解下面的线性规划模型。67123412356237max421st.390,1,2,,7jxxxxxxxxxxxxxxxj
用单纯形表法对上面的模型进行求解，先写出A，b，C，111100021101100310001A，419b，0000011C
选取初始基B=（P4，P6，P7）=E，基变量为XB=（x4，x6，x7）T，CB=（0，-1，-1），
大M法
原模型：
max
..0zCXAXbstX
112211112211112212 max ..............,,...,0nnnnmmmnnmnzcxcxcxaxaxaxbstaxaxaxbxxx
其中000000121(,,...,,,....,)mmnXxxxxx
人工模型：
max
..0aazCXLMXAXIXbstX
111112211112211112212max .........
........
,,...,,,...,0mmmnnaannammmnnamnaazcxcxcxMxMxaxaxaxxbstaxaxaxxbxxxxx
其中(1,1,...,1)mL, aX为人工向量且12,,...,aaaamXxxx，M是一个很大的数.
大M法的思想：
1． 如果原模型有最优解，那么由人工模型可得到其最优解
2． 如果原模型无解，那么由人工模型判定其无解。
3． 事实上，当原模型有最优解时，人工模型的最优解“就是”原模型的最优解，且二者最优目标函数值相同。
实施方法：
1． 如果人工模型的最优目标值不为无穷小，那么原模型和人工模型具有“同样”的最优解，而且最优目标函数值相同。
2． 如果人工模型的最优目标值为无穷小，那么原模型无解。
下面证明：
定理1 如果人工模型的最优目标值为，那么就可判定原模型无解。
证明 用反证法证明。
设原问题有可行解，那么也存在基本可行解，设为000000121(,,...,,,....,)mmnXxxxxx，那么必有0CX。
显然100000121(,,...,,,....,,0,...,0)mmnmXxxxxx个也是人工模型的一个基本可行解，那么有
1 §4.2 两阶段法与大M法————初始可行基的求法
求解线性规划的步骤是：
1） 已知一个初始基本可行解
2） 从初始基本可行解出发，写出单纯型表，求出进基离基变量，做主元消去法，求出一个新的基本可行解且使目标函数值得到改善。
3） 判断当前基本可行解是否是最优解
那末，当观察不出来初始基本可行解时，怎么办？下面介绍的方法是几种求初始基本可行解的方法
4.2.1 两 阶 段 法
min cx
ts. bAx
x≥0
其中A是nm矩阵，b≥0。若A中有m阶单位矩阵，则初始基本可行解立即得到。比如，NIAm,，那么
0bxxxNB
就是一个基本可行解。若A中不包含m阶单位矩阵，就需要用某种方法求出一个基本可行解。
介绍两阶段法之前，先引入人工变量的概念。
设A中不包含m阶单位矩阵，为使约束方程的系数矩阵中含有m阶单位矩阵，把每个方程增加一个非负变量，令
bxAxa （4.2.2） 2 x≥0 ，ax≥0
即
bxxIAam),( （4.2.3）
x≥0 ，ax≥0
显然， bxxa0
是4:2:3的一个基本可行解.
向量x®¸0是人为引入的，它的每个分量成为人工变量。人变量与前面介绍过的松弛变量是两个不同的概念。松弛变量的作用是把不等式约束改写成等式约束，改写前后的两个问题是等价的。因此，松弛变量是“合法”的变量。而人工变量的引入，改变了原来的约束条件从这个意义上讲，它们是“不合法”的变量。
第一阶段是用单纯形方法消去人工变量（如果可能的话）：
min aTxe
s:t Ax+x®=b (4:2:1)
