1 线性规划与单纯形法。
第1节线性规划问题及其数学模型。
1．1 问题的提出。
1.1.1 引例。
例1．可取为教学参考书p8例1，或随堂构造一个相当的例子。
通过例1，得出线性规划模型的构成，并引出线性规划模型的一般形式。
1.1.2 数学模型一般形式。
其中：⑴为目标函数；⑵和⑶为约束条件；opt=max或min。
1.1.3 数学模型特征。
线性规划数学模型特征为：
解向量描述方案；
所有式子均为线性式子；
目标函数追求极大化或极小化。
1．2 **法。
1.2.1 相关概念。
1.2.1.1 函数梯度。
函数梯度方向是函数值增长最快的方向，这里以行向量描述梯度。
目标函数的梯度记为c=(c1,c2,,…cn)。
1.2.1.2 线性式子的几何意义。
线性等式代表一个超平面（二维时为一条直线）；
线性不等式代表一个半空间（二维时为一个半平面）。
1.2.1.3 一些解的概念。
以数学模型一般形式为基准，介绍一些相关概念。
解：的一个值称为一个解。
可行解：满足约束条件的解。
可行域：可行解的集合。
最优解：满足⑴的可行解。
最优值：与最优解对应的目标函数值。
1.2.2 **法的步骤
1.2.2.1 确定可行域。
可行域为各约束式子对应的区域的交。
如果可行域为空集，问题无可行解，否则，问题有可行解。
1.2.2.2 确定最优方向p
1.2.2.3 确定最优解。
据p和可行域的情况，可以确定解的情况：
如果目标函数值可以趋向无穷大，则问题无有限最优解，否则可以在可行域边界上取得最优解。
1.2.3 解的情况。
讨论可行域和解（求解结果）的可能组合。
1.2.3.1 可行域为空集。
此时无可行解。
1.2.3.2可行域非空有界。
唯一最优解。
无穷多最优解。
1.2.3.3可行域非空无界。
唯一最优解。
无穷多最优解。
无有限最优解。
1.3 标准型。
1.3.1 标准型。
标准型为：标准型也可写为向量形式：
式中：；；标准型也可写为矩阵形式：
式中：。1.3.2 化标准型。
将不符合标准型要求的数学模型化为标准型。
设已得： 变换1
xj无约束——>以取代，，
xj≤0——>以取代， 。
经变换1，得如下形式的数学模型：
变换2松弛变量， 。
剩余变量， 。
经变换2，得标准型。
变换3必要时，变更变量的文字符号。
1.4 解的概念。
以标准型为基础，讨论解的概念。
基向量：构成b的系数列向量。
非基向量：a中除基向量外的系数列向量。
基变量：与基向量对应的变量。
非基变量：与非基向量对应的变量。
通过例4引出一些相关的概念。
3）顶点。设d为凸集，，且，若不能用，表示，则称为d的顶点。
定理3.若线性规划问题有可行域，则必有基本可行解。
定理4.若线性规划问题有最优解，则可以在可行域顶点上达到。
最优。定理5.最优解的凸组合仍然是最优解。
2．3 枚举法。
如果问题有最优解，则找出所有的可行基，比较对应的。
目标函数值，得最优基本可行解，作它们的凸组合得最优解。
得表达式。如果可行域非空有界，一定可以用枚举法取得最优解。
如果可行域非空无界，不一定可以用枚举法取得最优解。
第3节单纯形法。
单纯形法是求解线性规划问题的一种基本方法。
3．1 求解原理。
原理（有最优解）：确定一个可行域顶点，如果尚未求得所有的。
最优顶点，则在目标函数值不劣化的前提下，寻找新顶点，直至。
求得所有的最优顶点为止。
最优顶点的凸组合代表了更多的最优解。
由于解的情况不只是有最优解一种，这样我们求解时必须。
解决下述几个问题：
假设原来的问题为，求解时的问题为（符合标准型的要求），则。
一定有可行解；
确定初始顶点的方法；
对顶点进行解的检验，要求可以判别出：
无可行解的情形；
无有限最优解的情形；
如果有最优解，则当前顶点是否最优顶点以及是否取得了。
所有的最优顶点的判别方法。
单纯形法中，对每个顶点进行解的检验，如果出现无有限最优解的特征，退出运算；当前顶点为最优顶点时，需判别是否无可行解，如果没有无可行解的特征，应判别是否取得了所有的最优顶点。
为便于对顶点的判别，应制定对应的模型格式。
顶点变换（从当前顶点出发，在目标函数值不劣化的前提下，确定新顶点）；
最优顶点的凸组合。
这里只需解决问题⑴－⑷
3．2 规范型和规范标准型。
规范型和规范标准型是便于解的判别的模型格式。设为：
又设， (t=0,1,…)为第t+1个基，则关于的规范型为：
+∑t式中，为方便，也可记为，和也可采取类似记法。
下的基本解为：,0, 。
称∑t＝或∑t＝为下的检验数向量，
称称为xj的检验数，或称为xtj的检验数。
易知基变量的检验数为零。
若为可行基，则称为关于的规范标准型。
3．3 确定初始顶点。
3．3．1 确定。
设已得： 式中：。
可以在建模后，经由化标准型的一些步骤取得。
做下述变换：
1）对松弛变量， 。
2）对人工变量，。
3）对剩余变量， ，人工变量，。
可得（符合标准型的要求）：
3．3．2 确定。
依次（依i的次序）取中的和为基向量：“≤型约束中的系数列向量，“≥型约束和“＝”型约束中的系数列向量。这些向量排成一个单位矩阵，取这个矩阵为初始单位基。
如果没有引入人工变量，则=0,与相同。
令下的非基变量为零，得初始基本可行解，对应于初始顶点。
3．4 解的检验。
称∑t＝或∑t＝为下的检验数，其中。
易知，基变量的检验数为零。
定理6.对，若∑t ≤ 0,则为最优解。
证明：设对，有∑t ≤ 0,若不是最优解，则设最优解为，对应的≤=，矛盾。
定理7.若》0且，则无有限最优解。
证明：对，有。
和 （2）取》0，乘以（2）式两边并移项得：
将（3）加入（1）左端并整理得：
由（4）可知为：
i=1,2,…,m
ti=k0i=m+1,m+2,…,n且tik
易知为可行解，。
当，，故无有限最优解。
定理8.设为最优解，若存在非基变量，有＝0且0，则。
有无穷多最优解。（注：这里）
证明：设为最优解，若存在非基变量，有＝0且0，仿照定理7构造：
i=1,2,…,m
ti=k0i=m+1,m+2,…,n且tik
为使可行，取，并且只需考虑对i=1,2,…,m,有。这时有下述情形：
1），则；2）>0，若取，则。
则为基本可行解，，从而也是最优解，进而也是最优解，定理得证。
定理9.设中有人工变量，若为最优解且其中人工变量不全为零，则无可行解。
证明：设中有人工变量、为最优解且其中人工变量不全为零。
设有可行解，为中与之对应的可行解，，由于中人工变量一定取零值，因此优于，矛盾。
运筹学讲解
实验二运输问题模型的建立及求解。1.实验目的和要求。理解运输问题模型的基本思想，模型的建立方法及使用运筹学软件对运输问题进行求解。2.实验前准备。复习教材第七章相关内容。3.实验条件。每名同学使用一台计算机。小组同学相邻，方便讨论。4.实验内容。1 练习教材第七章例4 例9中的一个例子，使用运筹学软...
运筹学试卷 物流运筹学
2012 2013学年第一学期。运筹学 试卷。试卷 自拟送卷人 唐文广打印 校对 唐文广。一 6分 已知线性规划模型。写出该问题的对偶问题。二 15分 用单纯形法求解下面线性规划问题 作1张表即可 三 10分 求解下面标准指派问题，其中效率矩阵为。四 15分 某项工程由a b i j k等11项工序...
运筹学试题与案例集 运筹学
20xx年运筹学试题与案例集 天津。全国运筹学精品课程建设与题库案例交流研讨会运筹学试题与案例集 内部交流资料 中国运筹学会教育普及工作委员会 天津运筹学会 天津工业大学 20xx年5月 全国运筹学精品课程建设与题库案例交流研讨会 2010.05 目录 第一部分运筹学试题4 试题 1 北京工商大学4...