下载文档原格式
线性规划教案一、教学目标通过本教案的学习，学生将能够：1. 理解线性规划的基本概念和原理；2. 掌握线性规划模型的建立和求解方法；3. 能够在实际问题中应用线性规划进行决策和优化。
二、教学重点1. 线性规划的基本概念和原理；2. 线性规划模型的建立和求解方法；3. 线性规划在实际问题中的应用。
三、教学难点线性规划模型的建立和求解方法。
四、教学过程1. 导入引入线性规划的概念和背景，与学生分享线性规划的应用案例，激发学生的学习兴趣。
2. 理论讲解（1）线性规划的基本概念- 线性规划的定义：线性规划是一种用于求解最优化问题的数学方法，其目标函数和约束条件都是线性的。
- 最优解的定义：线性规划的最优解是使目标函数达到最大（或最小）值的变量取值。
（2）线性规划模型的建立- 决策变量的定义：根据实际问题，确定需要优化的变量，表示为决策变量。
- 目标函数的定义：确定需要最大化（或最小化）的目标，在实际问题中通常是利润、成本等。
- 约束条件的定义：确定影响决策变量的限制条件，包括等式约束和不等式约束。
（3）线性规划模型的求解方法- 图形法：通过画出约束条件和目标函数所表示的直线或面，找到最优解所在的区域，从而确定最优解。
- 单纯形法：通过运用单纯形表格法，逐步迭代求解线性规划模型，直到得到最优解。
- 整数规划：当决策变量只能取整数值时，需要使用整数规划方法进行求解。
3. 实例演练选择一个简单的线性规划实例，带领学生一起完成模型的建立和求解过程，让学生通过实际操作，进一步理解线性规划的求解方法。
4. 拓展应用从实际生活或工作中的问题出发，引导学生运用线性规划进行决策和优化，培养学生的实际应用能力。
五、教学评价1. 在实例演练中，教师可以针对学生的解题过程和答案，进行实时评价，及时纠正错误。
2. 可以组织小组或个人探究性学习活动，让学生自主构建线性规划模型并求解，评价学生的表现和学习成果。
六、教学延伸可以引导学生进一步深入学习线性规划的应用方法、算法和模型扩展，培养学生在实际问题中的建模和求解能力。
应⽤运筹学基础：线性规划（4）-对偶与对偶单纯形法这⼀节课讲解了线性规划的对偶问题及其性质。
引⼊对偶问题考虑⼀个线性规划问题：$$\begin{matrix}\max\limits_x & 4x_1 + 3x_2 \\ \text{s.t.} & 2x_1 + 3x_2 \le 24 \\ & 5x_1 + 2x_2 \le 26 \\ & x \ge0\end{matrix}$$ 我们可以把这个问题看作⼀个⽣产模型：⼀份产品 A 可以获利 4 单位价格，⽣产⼀份需要 2 单位原料 C 和 5 单位原料 D；⼀份产品 B 可以获利 3 单位价格，⽣产⼀份需要 3 单位原料 C 和 2 单位原料 D。
现有 24 单位原料 C，26 单位原料 D，问如何分配⽣产⽅式才能让获利最⼤。
但假如现在我们不⽣产产品，⽽是要把原料都卖掉。
设 1 单位原料 C 的价格为 $y_1$，1 单位原料 D 的价格为 $y_2$，每种原料制定怎样的价格才合理呢？⾸先，原料的价格应该不低于产出的产品价格（不然还不如⾃⼰⽣产...），所以我们有如下限制：$$2y_1 + 5y_2 \ge 4 \\ 3y_1 + 2y_2 \ge3$$ 当然也不能漫天要价（也要保护消费者利益嘛- -），所以我们制定如下⽬标函数：$$\min_y \quad 24y_1 + 26y_2$$ 合起来就是下⾯这个线性规划问题：$$\begin{matrix} \min\limits_y & 24y_1 + 26y_2 \\ \text{s.t.} & 2y_1 + 5y_2 \ge 4 \\ & 3y_1 + 2y_2 \ge 3 \\ & y \ge 0\end{matrix}$$ 这个问题就是原问题的对偶问题。
对偶问题对于⼀个线性规划问题（称为原问题，primal，记为 P） $$\begin{matrix} \max\limits_x & c^Tx \\ \text{s.t.} & Ax \le b \\ & x \ge 0\end{matrix}$$ 我们定义它的对偶问题（dual，记为 D）为 $$\begin{matrix} \min\limits_x & b^Ty \\ \text{s.t.} & A^Ty \ge c \\ & y \ge 0\end{matrix}$$ 这⾥的对偶变量 $y$，可以看作是对原问题的每个限制，都⽤⼀个变量来表⽰。
线性规划教案一、教案简介本教案旨在引导学生了解线性规划的基本概念、模型建立和求解方法，培养学生运用线性规划解决实际问题的能力。
通过理论讲解、案例分析和实践操作，匡助学生掌握线性规划的基本原理和应用技巧。
二、教学目标1. 知识目标：- 掌握线性规划的基本概念和术语；- 理解线性规划模型的建立过程；- 熟悉线性规划的常用求解方法。
2. 能力目标：- 能够运用线性规划解决实际问题；- 能够利用线性规划模型进行决策分析；- 能够分析和评价线性规划解的合理性。
三、教学内容与方法1. 教学内容：- 线性规划的概念和特点；- 线性规划模型的建立；- 单纯形法和对偶理论的基本原理；- 整数规划和混合整数规划的简介；- 线性规划在实际问题中的应用。
2. 教学方法：- 讲授法：通过讲解线性规划的基本概念、模型建立和求解方法，匡助学生理解相关知识；- 案例分析法：选取实际问题案例，引导学生运用线性规划解决问题，培养解决实际问题的能力；- 实践操作法：通过使用线性规划软件，让学生亲自操作求解线性规划问题，提升实际操作能力。
四、教学步骤与时间安排1. 第一课时（40分钟）：- 线性规划的概念和特点（10分钟）：- 介绍线性规划的定义和基本特点；- 解释线性规划的目标函数、约束条件和决策变量。
- 线性规划模型的建立（20分钟）：- 介绍线性规划模型的基本步骤和要素；- 通过实例演示线性规划模型的建立过程。
- 单纯形法的基本原理（10分钟）：- 讲解单纯形表格和单纯形法的基本思想；- 通过实例演示单纯形法的求解过程。
2. 第二课时（40分钟）：- 对偶理论的基本原理（15分钟）：- 介绍线性规划的对偶模型和对偶理论的基本概念；- 解释对偶理论在线性规划中的应用。
- 整数规划和混合整数规划的简介（10分钟）：- 介绍整数规划和混合整数规划的概念和特点；- 解释整数规划和混合整数规划的求解方法。
- 线性规划在实际问题中的应用（15分钟）：- 选取实际问题案例，引导学生运用线性规划解决问题；- 分析案例中线性规划解的合理性和可行性。
线性规划教案一、引言线性规划是运筹学中的重要分支，它通过建立数学模型，解决实际问题中的最优化问题。
本教案旨在帮助学生理解线性规划的基本概念、模型建立和求解方法，以及应用于实际问题的能力。
二、教学目标1. 理解线性规划的基本概念，包括决策变量、目标函数、约束条件等。
2. 掌握线性规划模型的建立方法，能够将实际问题转化为线性规划模型。
3. 熟悉线性规划的求解方法，包括图形法、单纯形法等。
4. 能够应用线性规划解决实际问题，如生产计划、资源分配等。
三、教学内容1. 线性规划的基本概念线性规划是一种数学优化方法，其基本概念包括：- 决策变量：表示需要决策的量，通常用x1、x2、...、xn表示。
- 目标函数：表示需要最大化或最小化的目标，通常用Z表示。
- 约束条件：表示问题的限制条件，通常以不等式或等式形式给出。
2. 线性规划模型的建立方法线性规划模型的建立方法包括以下步骤：- 确定决策变量：根据实际问题确定需要决策的变量。
- 建立目标函数：根据问题要求确定需要最大化或最小化的目标函数。
- 确定约束条件：根据问题给出的限制条件，建立约束条件。
- 确定变量的取值范围：根据实际问题确定变量的取值范围。
3. 线性规划的求解方法线性规划有多种求解方法，常用的有图形法和单纯形法。
- 图形法：适用于二维线性规划问题，通过绘制目标函数和约束条件的图形，找到最优解。
- 单纯形法：适用于多维线性规划问题，通过迭代计算，找到最优解。
4. 线性规划的应用线性规划广泛应用于生产计划、资源分配、运输问题等实际情境中。
通过将实际问题转化为线性规划模型，可以帮助决策者做出最优决策。
五、教学方法本教案采用讲授与实践相结合的教学方法，包括讲解线性规划的基本概念、示范建立线性规划模型的方法，以及引导学生进行实际问题的求解练习。
六、教学步骤1. 引入线性规划的概念，介绍线性规划的应用领域和重要性。
2. 讲解线性规划的基本概念，包括决策变量、目标函数、约束条件等。
第四章 线性规划本章主要内容：线性规划的基本理论 线性规划的单纯形法 线性规划的对偶理论 线性规划的对偶单纯形法教学目的及要求：理解线性规划的基本理论；掌握线性规划的单纯形法；理解线性规划的对偶理论；掌握线性规划的对偶单纯形法。
教学重点：线性规划的单纯形法． 教学难点：线性规划的对偶单纯形法． 教学方法：启发式．教学手段：多媒体演示、演讲与板书相结合． 教学时间：6学时． 教学内容：§4.1 线性规划的基本理论考虑线性规划问题11min ;,1,2,,,0,1,2,,.nj j j n ij j i j j c x a x b i m x j n ==⎧⎪⎪⎪==⎨⎪⎪≥=⎪⎩∑∑s.t. (LP)或min ;,0.T c x Ax b x ⎧⎪=⎨⎪≥⎩s.t. 其中 121212(,,,),(,,,),(,,,),(),T T T n n m ij m n x x x x c c c c b b b b A a ⨯====A 称为约束矩阵，Ax b =称为约束方程组，0x ≥称为非负约束．假定：rank()A m =．定义 在（LP ）中，满足约束方程组及非负约束的向量x 称为可行解或可行点；所有可行解的全体称为可行解集或可行域，记作K ，即{,0}K Ax b x ==≥．使目标函数在K 上取到最小值的可行解称为最优解；最优解对应的目标函数值称为最优值．定义 在（LP ）中，约束矩阵A 的任意一个m 阶满秩子方阵B 称为基，B 中m 个线性无关的列向量称为基向量，x 中与B 的列对应的分量称为关于B 的基变量，其余的变量称为关于B 的非基变量．任取（LP ）的一个基12(,,,)m j j j B p p p =，记12(,,,)m T B j j j x x x x =，若令关于B 的非基变量都取0，则约束方程Ax b =变为B Bx b =．由于B 是满秩方阵，因此B Bx b =有唯一解1B x B b -=．记121(,,,)m T j j j B b x x x -=，则由12,1,2,,,0,{1,2,,}{,,,}k k j j j m x x k m x j n j j j ===∀∈-所构成的n 维向量x 是Ax b =的一个解，称之为（LP ）的关于B 的基本解．基本解满足约束方程组，但不一定满足非负约束，所以不一定是可行解．若10B b -≥，即基本解x 也是可行解，则称x 为（LP ）的关于基B 的基本可行解，相应的基B 称为（LP ）的可行基；当10B b ->时，称此基本可行解x 是非退化的，否则，称之为退化的．若一个（LP ）的所有基本可行解都是非退化的，则称该（LP ）是非退化的，否则，称它是退化的．例1 求下列线性规划问题的所有基本可行解．12123124min 44;4,2,0,1,2,3,4.j x x x x x x x x x j -⎧⎪-+=⎪⎨-++=⎪⎪≥=⎩s.t. 解 约束矩阵的4个列向量依次为12341110,,,1101p p p p -⎛⎫⎛⎫⎛⎫⎛⎫==== ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭⎝⎭．全部基为113214323424534(,),(,),(,),(,),(,),B p p B p p B p p B p p B p p =====对于1B ，1x 和3x 为基变量，2x 和4x 为非基变量．令2x =4x =0，有1314,2,x x x +=⎧⎨-=⎩ 得到关于1B 的基本解(1)(2,0,6,0)T x =-，它不是可行解．对于2B ，1x 和4x 为基变量，2x 和3x 为非基变量．令2x =3x =0，有1144,2,x x x =⎧⎨-+=⎩ 得到关于2B 的基本解(2)(4,0,0,6)T x =，它是一个非退化的基本可行解．同理，可求得关于345,,B B B 的基本解分别为(3)(4)(5)(0,2,6,0),(0,4,0,6),(0,0,4,2)T T T x x x ==-=，显然，(3)x 和(5)x 均是非退化的基本可行解，而(4)x 不是可行解．因此，该问题的所有基本可行解为(2)(3)(5),,x x x ．此外，因为这些基本可行解都是非退化的，所以该问题是非退化的．定理1 设x 为（LP ）的可行解，则x 为（LP ）的基本可行解的充要条件是它的非零分量所对应的列向量线性无关．证明 不妨设x 的前r 个分量为正分量，即12(,,,,0,,0),0(1,2,,).T r j x x x x x j r =>=若x 是基本可行解，则取正值的变量12,,,r x x x 必定是基变量，而这些基变量对应的列向量12,,,r p p p 是基向量．故必定线性相关．反之，若12,,,r p p p 线性无关，则必有0r m ≤≤．当r m =时，12(,,,)r B p p p =就是一个基；当r m <时，一定可以从约束矩阵A 的后n r -个列向量中选出m r -个，不妨设为12,,,r r m p p p ++，使121(,,,,,,)r r m B p p p p p +=成为一个基．由于x 是可行解，因此1rj j j x p b ==∑，从而必有1mj j j x p b ==∑．由此可知x 是关于B 的基本可行解．定理2 x 是（LP ）的基本可行解的充要条件是x 为（LP ）的可行域的极点． 证明 由定理4.1.1和定理2.2.2知结论成立． 例2 求下列线性规划问题的可行域的极点．1212314min ;22,2,0,1,2,3,4.j x x x x x x x x j -⎧⎪++=⎪⎨+=⎪⎪≥=⎩s.t. 解 因为约束矩阵的4个列向量依次为12341210,,,1001p p p p ⎛⎫⎛⎫⎛⎫⎛⎫==== ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭．全部基为112213314424534(,),(,),(,),(,),(,),B p p B p p B p p B p p B p p =====求得关于基12345,,,,B B B B B 的基本解分别为(1)(2)(3)(4)(5)(2,0,0,0),(2,0,0,0),(2,0,0,0),(0,1,0,2),(0,0,2,2)T T T T Tx x x x x =====显然，(1)(2)(3),,x x x 均为退化的基本可行解，(4)(5),x x 是非退化的基本可行解．可行域有三个极点：(2,0,0,0)T ，(0,1,0,2)T ，(0,0,2,2)T ．定理3 若（LP ）有可行解，则它必有基本可行解． 证明 由定理2.2.1及定理4.1.2知结论成立．定理4 若（LP ）的可行域K 非空有界，则（LP ）必存在最优解，且其中至少有一个基本可行解为最优解．证明 根据推论2.2.6，（LP ）的任一可行解x 都可表示为（LP ）的全部基本可行解12,,,k x x x 的凸组合，即1,ki i i x x x K λ==∀∈∑，其中10(1,2,,),1ki i i i k λλ=≥==∑．设s x 是使（LP ）中目标函数值达到最小的基本可行解，即 1min T T s i i kc x c x ≤≤=，则11,kkTTT T i i i s s i i c x c x c x c x x K λλ===≥=∀∈∑∑．这表明，基本可行解s x 为（LP ）的最优解．定理5 设（LP ）的可行域K 无界，则（LP ）存在最优解的充要条件是对K 的任一极方向d ，均有0T c d ≥．证明 根据定理2.2.10，（LP ）的任一可行解x 都可写成11kli i j j i j x x d λμ===+∑∑，其中12,,,k x x x 为（LP ）的全部基本可行解，12,,,l d d d 为K 的全部极方向，且10(1,2,,),1,0(1,2,,)ki i j i i k j l λλμ=≥==≥=∑．于是，（LP ）等价于下面以0(1,2,,)0(1,2,,)i j i k j l λμ≥=≥=和为决策变量的线性规划问题111min ()();1,0,1,2,,,0,1,2,,.k lT T i i j j i j k i i i j c x c d i k j l λμλλμ===⎧+⎪⎪⎪⎪=⎨⎪⎪≥=⎪≥=⎪⎩∑∑∑s.t. 由于j μ可以任意大，因此若存在某个j d ，使0T j c d <，则上述问题的目标函数无下界，从而不存在最优解，从而（LP ）不存在最优解．若1,2,,j l ∀=，均有0T j c d ≥，设1min T T s i i kc x c x ≤≤=，则11()(),k lTTT T i i j j s i j c x c x c d c x x K λμ===+≥∀∈∑∑．所以基本可行解s x 是（LP ）的最优解．推论6 若（LP ）的可行域K 无界，且（LP ）存在最优解，则至少存在一个基本可行解为最优解．证明 由定理4.1.5的证明过程可知结论成立． 定理7 设在（LP ）的全部基本可行解12,,,k x x x 中，使目标函数值最小者为12,,,s i i i x x x ；在K 的全部极方向12,,,l d d d 中，满足0T j c d =者为12,,,t j j j d d d ．若（LP ）存在最优解，则x 为（LP ）的最优解的充要条件是存在10(1,2,,),1,0(1,2,,)pp q si i j p p s q t λλμ=≥==≥=∑使11p p q q sti i j j p q x x d λμ===+∑∑． （*）证明 因为（LP ）存在最优解，所以由定理4.1.4和推论4.1.6及其证明知，基本可行解12,,,s i i i x x x 是（LP ）的最优解．设x 具有（*）式的形式，则由推论2.2.6和定理2.2.10知，x 为（LP ）的可行解，从而由（*）式知，111p p q q stTTT T i i j j i p q c x c x c d c x λμ===+=∑∑因此，x 为（LP ）的最优解．反之，设x 为（LP ）的任一最优解，则x 为可行解，于是由推论2.2.6和定理2.2.10知，存在 10(1,2,,),1,0(1,2,,)ki i j i i k j l λλμ=≥==≥=∑，使 11kli i j j i j x x d λμ===+∑∑． （**）根据定理1.1.5，有 0,1,2,,T j c d j l ≥=， 且由1i x 为最优解知1,1,2,,T T i i c x c x i k ≥=．从而由上述两式容易用反证法证明：若（**）式中某个0i λ>，则i x 必为（LP ）的最优解；若（**）式中某个0j μ>，则必有0T j c d =。
教案四线性规划的单纯形法教学内容第三节单纯形法1．单纯形法2．单纯形法的基本原理3．单纯形解法4．大M法教学学时9学时教学目标1．理解单纯形法的解题思想2．掌握单纯形法的基本原理3．掌握单纯形解法和大M法重点难点重点单纯形法的基本原理、单纯形解法和大M法，难点单纯形法的基本原理教学方法及手段教师讲解使用多媒体课件教学过程一、复习巩固1．线性规划图解法的步骤（见课件）2．线性规划数学模型解的几种情况（见课件）二、讲授新课1．单纯形法基本概念（见课件）典型方程组一般线性规划问题标准形式的约束条件如下式（2-1），是一个有n个未知数、m个方程的线性方程组．如果这m个方程是独立的（即其中任一方程均不能由其它方程代替），则通过初等变换，必能使式（2-1）化成式（2-2）形式的同解方程组：∑==njijijbxa1mi,,2,1=（2-1）1x ' +11221111b x a x a x a n n m m m m '=''+⋅⋅⋅+''+''++++ 2x ' +22222112b x a x a x a n n m m m m '=''+⋅⋅⋅+''+''++++ （2-2） …………………………………………………………mx '+m n mn m mm m mm b x a x a x a '=''+⋅⋅⋅+''+''++++2211 式中n x x x '⋅⋅⋅'',,,21是重新排序后的变量．式（2-2）被称为典型方程组．即如果在一个线性方程组中的每一个方程中都有系数为1，并且不再出现在其它方程的一个未知量，则此方程组称为典型方程组．基本变量如果变量j x 在某一方程中系数为1，而在其它一切方程中的系数为零，则称j x 为该方程中的基本变量．否则为非基本变量．如式（2-2）中的m x x x '⋅⋅⋅'',,,21为基本变量，n m m x x x '⋅⋅⋅''++,,,21为非基本变量．基本变量的个数为线性无关的方程的个数．事实上，n 个变量中任意m 个都可能作为基本变量，因此由排列组合知识可知，基本变量的组数为mn c 个，n 为未知变量的个数，m 为线性无关的方程的个数．基本解在典型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解．基本解的个数为mnc 个．基本可行解基本变量为非负的一组基本解称为基本可行解，基本可行解的个数最多不超过m n c 个．例如，对方程组32 4321=+-+x x x x ①13 2421=+x x x －② 施行初等变换[①×（－2）＋②],可以得到：32 4321=+-+x x x x ①572 432-=-+-x x x ③[③×(－1)] : 32 4321=+-+x x x x ① 572432=+-x x x ④ [④×（－1）＋①]: 25431-=-+x x x ⑤ 572432=+-x x x ④式⑤和④为典型方程组，基本变量是1x 和2x ，非基本变量为3x 和4x ．设非基本变量3x 和4x 为零，则1x 和2x 分别等于-2和5，即对应于典型方程组⑤和④，基本解为：X =()T0052-．因基本变量中1x 为负值，所以此解不是基本可行解．根据方程组①和②有4个未知变量，因此通过初等变换可得到24c 组（即6组）典型方程组和基本解．若令2x 和4x 为基本变量，通过初等变换，方程组①和②可变换为：[①×（－1）＋②]: 32 4321=+-+x x x x ① 25 431－=-+x x x ③ [③×（－1/5）]: 324321=+-+x x x x ① 4.0202.0431=+--x x . x ④ [④×（－2）＋①] : 2.2604.1321=-+ x . x x ⑤4.0202.0431=--x x .x ＋ ④ 此时，典型方程组的基本变量为2x 和4x ，非基本变量为1x 和3x ．基本解为：T X ）（0.4 0 2.2 0 =，因为基本变量为非负值，所以此基本解也为基本可行解．2．单纯形法的基本原理（见课件）理论上已经证明，线性规划的基本可行解与可行域的顶点是一对一的．这就决定了线性规划可行域的顶点个数最多也不超过m n c 个．上面讨论线性规划问题解的特点时已指出，如果线性规划有最优解，一定可以在可行域的某个顶点处达到．因此，单纯形法的基本思路是：根据问题的标准形式，从可行域中的一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解．在用单纯形法求解线性规划问题时，应考虑的问题：建立初始基本可行解 在用单纯形法求解时，首先应将线性规划问题以标准形式表达、约束条件以右端常数非负的典型方程组表示，确定初始基本可行解．在前面的阐述中，已讨论了如何将一般线性规划问题转化为标准形式的线性规划问题，如何将约束条件通过初等变换以典型方程组形式表示，以及如何得出基本可行解（最初得到的基本可行解也称初始基本可行解），此处不再赘述．经过变换，典型方程组和初始基本可行解可用式（2-3）表示：1x +11221111b x a x a x a n n m m m m '='+⋅⋅⋅+'+'++++ 2x +22222112b x a x a x a n n m m m m '='+⋅⋅⋅+'+'++++ （2-3） ………………………………………………………m x +m n mn m mm m mmb x a x a x a '='+⋅⋅⋅+'+'++++2211 初始基本可行解：T mb b X )00(10 ''=． 最优性检验 得到一个基本可行解后，我们要判断它是不是最优解．一般情况下，经过迭代后式（2-3）变为∑+='-'=nm j jiji i xa b x 1（m i ,,2,1 =） （2-4）将式（2-4）代入目标函数式，整理后得∑∑∑+==='-+'=n m j mi j iji jmi i i x a c c b c Z 111)( （2-5）令 ∑='=m i i i b c Z 10 , ∑='=mi iji j a c Z 1, n m m j ,,2 ,1 ++= 于是 ∑+=-+=nm j j j jx Z cZ Z 10)( （2-6）由于当m j ,,2 ,1 =时，j mi ij i j c a c Z ='=∑=1，即0=-j j Z c （m j ,,2 ,1 =），所以式（2-6）也可写作再令 j j j Z c C -= n j ,,2 ,1 =j C 为变量j x 的检验数．则 ∑=+=nj j j x C Z Z 10 （2-7）（1）最优解判别 若)0(X ＝T m b b b )00(21⋅⋅⋅'⋅⋅⋅''为基本可行解，且对一切n j ,,2 ,1 =,有0≤j C ，则)0(X 为最优解．（2）无有限最优解判别 若)0(X ＝T m b b b )00(21⋅⋅⋅'⋅⋅⋅''为一基本可行解，有一个k C >0，且对一切m i ,,2,1 =有0≤ik β（ik β为约束条件方程中的系数，n k ,,2,1 =），那么该线性规划问题无有限最优解（或称有无界解或无最优解）．事实上，应用向量的乘法，可以将检验数的求法表示得简明一些．令j c 表示目标函数中变量jx 的系数，B C 表示基本变量在目标函数中的系数行向量，j P 表示变量j x 在典型方程中的系数列向量，则⎪⎪⎪⎪⎪⎭⎫⎝⎛⋅-=⋅-=-=mj j j B j j B j j j j a a a C c P C c Z c C 21 n j ,,2 ,1 = （2-8）基本变量的检验数总等于0．目标函数值b C Z B ⋅=.基本可行解的改进 若初始基本可行解)0(X 不是最优解及不能判别无最优解时，需找一个新的基本可行解．具体方法是：首先确定进基变量，再确定出基变量．进基变量的确定：由式（2-7）可知，检验数j C 对线性规划问题的实际意义是：j C 表示当变量j x 增加1个单位时，目标函数的增加量；其经济意义表示相对利润．当0>j C 时，说明非基本变量j x 增加1个单位，目标函数可以增加，即现在的函数值不是最优，还能增加．这时要将某个非基本变量换到基本变量中去（称为进基变量）．为了使目标函数值增长最快，所以应选择j C 值最大的一项所对应的非基本变量进基,k C =>)0j C (max . 则对应的k x 为进基变量．进基变量所在的列（k ）称为枢列．出基变量的确定：当进基变量确定后（假设i x 是进基变量），出基变量的选定是应用“最小比值规则”．即用此时的各约束方程右端的常数项i b （非负数）与相应方程中k x 的正系数ik β相比，并选取最小商值的基本变量l x 为出基变量（将由基本变量变为非基本变量）．出基变量所在的行（l ）称为枢行．枢行与枢列交点处的元素（lk β）称为枢元．然后通过初等变换，将约束条件转为关于新的基本变量的典型方程组，并求得新的基本可行解．对于新的基本可行解可再进行上述的最优性检验．3． 单纯形解法（见课件）上面介绍的单纯形法原理看似复杂，但如用表格形式计算，则比较容易操作．单纯形法的计算步骤：第1步：找出初始基本可行解，建立初始单纯形表．第2步：检验对应于非基本变量的检验数j C ，若对所有的0≤j C ，则已得到最优解，计算最优值∑==mi i i b c Z 1，即可结束．否则，转入下一步．第3步：在所有0>j C 中，若有一个k C 对应k x 的系数列向量，即对m i ,,2,1 =均有0≤ik β，则此问题无有限最优解（或称有无界解或无最优解），停止计算．否则转入下一步．第4步：根据()0max >j C ＝k C ，确定k x 为进基变量，再依据“最小比值规则”（{}lkl ik ik i i b b βββθ=⎭⎬⎫⎩⎨⎧>=0min min ）确定l x 为出基变量．第5步：实施以枢元素为中心的初等变换，使约束方程组变为关于新的基本变量的典型方程组，得到新的单纯形表，重复第二步…，一直到没有新的非基本变量可以改善目标函数为止．若线性规划模型为：上述计算步骤仍有效，只是其中的第二步改为：若对所有的0≥j C （n j ,,2,1 =），则已得到最优解；第三步改为在所有0<j C 中，若有一个k C 对应k x 的系数列向量，即对m i ,,2,1 =均有0≤ik β，则此问题无有限最优解（或称有无界解或无最优解）；第四步改为)0min(<j C ＝k C ，确定k x 为进基变量．例2-8 现以例2-1来说明单纯形法的表上解法．解 首先将线性规划问题标准化，引入松弛变量3x 、4x 、5x 、6x ，则：此时约束方程组已为典型方程组，根据上述线性规划模型可以列出初始单纯形表（表2-4）：表2-4 单纯形法求解例2-1（1）表2-4中：1004001000400102100012 为典型方程组中变量的系数，j x 为规划中出现的变量，j c 为变量j x 在目标函数中的系数，B X 为基本变量，B C 为基本变量在目标函数中的系数，b 为典型方程组右端常数项（非负值），θ为确定出基变量的商值，ikii b βθ=（0>ik β），j C 为变量j x 的检验数，j P C c C B j j ⋅-=，Z 为此时目标函数值，b C Z B ⋅=．根据初始单纯形表可以看出：初始基本可行解是01=x ，02=x ，123=x ，84=x ，165=x ，126=x此时目标函数值()⎪⎪⎪⎪⎪⎭⎫⎝⎛⋅=12168120000Z ＝0检验数111P C c C B ⋅-=＝200－()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅04120000＝200222P C c C B ⋅-=＝300－()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅40220000＝3003C =4C =5C ＝6C ＝0（基本变量的检验数总等于零）由于01>C ，02>C ，所以初始基本可行解非最优解．又由于12C C >，所以确定2x 为进基变量．进一步求最小θ值：即从第4个方程中算出的商值最小，而第4个方程中的基本变量是6x ，于是6x 为出基变量．表中给第4个约束方程中2x 的系数4加上方括号以突出其为枢元．接下去是将2x 取代6x ，表2-4中的约束方程化为以3x 、4x 、5x 和2x 为基本变量，1x 和6x 为非基本变量的典型方程．从表2-4中可以看到，只需对方程组实行初等变换，使枢元位置变成1，而枢列中的其它元素变为零就可以了．此处可先将第4个方程除以4，使枢元位置变成1；然后用新得到的第4个方程乘以（-2）后分别加到第1个和第2个方程上，使枢列中的第1个和第二个方程所在位变为零．这样我们可以得到新的单纯形表（表2-5）．表2-5给出的新的基本可行解是1x ＝0，2x ＝3，3x ＝6，4x ＝2，5x ＝16，6x ＝0此时目标函数值()⎪⎪⎪⎪⎪⎭⎫⎝⎛⋅=31626300000Z ＝900检验数111P C c C B ⋅-=＝200-()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅0412300000＝200666P C c C B ⋅-=＝0-()⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--⋅4102121300000＝75-2C ＝3C =4C =5C ＝0（基本变量的检验数总等于零）表2-5 单纯形法求解例2-1（2）由于01>C ，所以此时基本可行解非最优解，确定1x 为进基变量． 进一步计算最小θ值：即从第2个方程中算出的商值最小，而第2个方程中的基本变量是4x ，于是4x 为出基变量．接着进行第二次迭代，将1x 取代4x ，表2-5中的约束方程化为以3x 、1x 、5x 和2x 为基本变量，4x 和6x 为非基本变量的典型方程，以便求出新的单纯形表．重复单纯形法计算第2 步～第5步，一直到没有新的非基本变量可以改善目标函数为止（见表2-6和表2-7）．表2-6 单纯形法求解例2-1（3）表2-7 单纯形法求解例2-1（4）表2-7中：目标函数值()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅=244030002000Z =1400检验数444P C c C B ⋅-==0-()⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--⋅2120130002000=-150555P C c C B ⋅-==0-()⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--⋅8121414130002000=225- 1C =2C =3C =6C =0（基本变量的检验数总等于零）由于0≤j C ，6,,2,1 =j ，所以此基本可行解41=x ，22=x ，03=x ，04=x ，05=x ，46=x ，即为最优解，最优值为Z *＝1400．与前面图解法求解结果一致．为了加深对单纯形法基本思想的理解，不妨将表2-4、表2-5、表2-6、表2-7和图2-1进行对照，可以发现表2-4给出的基本可行解对应于图中可行域顶点0，表2-5给出的基本可行解对应于顶点A ，表2-6给出的基本可行解对应于顶点B ，表2-7给出的最优解对应于顶点C ．线性规划问题有无穷多个可行解，应用单纯形法可以高效率地求解此类问题．例2-9 用单纯形法求解下列规划问题（解略，见课件）4． 大M 法（1）人工变量 （见课件）单纯形法求解的一个重要前提是：线性规划问题必须是标准形式，并且约束条件必须化为典型方程组．这样才能得到初始基本可行解，并制作出初始的单纯形表．但许多线性规划问题不是以标准形式出现，约束条件也未以典型方程组形式表示，因此我们往往先要把线性规划问题化为标准形式，然后再使约束方程变为典型方程组．如果给定的线性规划问题中，约束条件都是“∑=≤nj i j ij b x a 1”型的，那么将每一个约束条件的左边添加一个松弛变量后，不仅约束条件化为了标准形式，而且也得到了典型方程组，如下列所示．但是，大多数的线性规划中的约束条件为∑=≥nj j ij x a 1（或＝）i b 的形式，化为典型方程组就不那么容易．在这种情况下，比较简单的方法是先将约束不等式化为等式，然后对每一个约束方程再添加一个非负变量（如果约束方程没有明显的基本变量），使方程组成为典型方程组形式．这种外加的变量不同于松弛变量（或剩余变量），没有实际意义，只是一种形式的存在，本质上应当等于零，所以被称为人工变量．（2）大M 法求解（见课件）在一个线性规划问题的约束条件中加入人工变量，成为典型方程组后，即可用单纯形表求解．由于一开始人工变量是作为基本变量的，而它们本质上应当为零，所以必须设法尽快将它们从基本变量中剔除，成为非基本变量（基本可行解中，非基本变量的值为零）．为此，将人工变量记入目标函数中，并赋予一个极大的负系数．习惯上，这种系数记作M -，其中M 是极大的正数．由于标准形式的线性规划是极大化问题，目标函数中添加1个或1个以上以M -为系数的人工变量后，人工变量取任何非负值均不可能为最优解．从而，在应用单纯形法过程中，人工变量一定会尽快地变成非基本变量，而对原问题的最优解不产生丝毫影响．对于目标函数为极小化时，规定人工变量在目标函数中的系数为极大的正系数（M +）．这种方法称为大M 法．例2-10 用大M 法求解下列问题．解 先通过加入松弛变量3x 和4x 使此线性规划问题化为标准形式然后通过加入人工变量5x 使约束方程组变为典型方程组2153M a xx x Z +=-5Mx 用单纯形法解之，结果如下表2-11：最后计算得出最优解21=x ，62=x ，23=x ，04=x ，05=x ，最优值Z *=36． 例2-11 有一线性规划问题 试用大M 法求解．解 在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到这里M 是一个很大的正数． 大M 法计算见表2-12．最优解：1x ＝4，2x ＝1，3x ＝9，4x ＝5x ＝6x ＝7x ＝0；最优值：Z ＝-2．在用大M 法求解时，如果得到人工变量不为零的最优解，则说明原问题不可行，即原问题无解．另外，若极小比值相等，则人工变量先出基．在线性规划问题中，如果线性规划已化为标准形式而约束方程仍没有明显的基本变量，则除可用大M 法求解外，还可用二阶段法求解（可参阅其他运筹学书籍）．单纯形法是线性规划问题的通用解法．尽管求解效率较高，但由于在许多实际问题的应用过程中，往往有很多的决策变量和约束条件，人工计算费时且易出现计算错误．计算机技术的发展，使线性规划问题的求解可以通过有关计算机程序完成，极大地增强了线性规划方法解决实际问题的能力．本书第十三章就介绍了用Excel 以电子表格的形式建立与求解线性规划模型的方法．表2-12 大M 法计算例2-11三、课堂练习（见课件）四、本次课小结（见课件）五、作业（见课件）。
