下载文档原格式
第一章 线性规划【教学内容】线性规划模型，图解法，可行区域的几何结构，基本可行解及线性规划的基本定理，单 纯形方法，单纯形表，两阶段法，关于单纯形方法的几点说明，对偶线性规划，对偶理论， 对偶单纯形法，求解线性规划问题的几个常用软件。
【教学要求】要求学生理解线性规划的标准形式，能熟练的将一般的线性规划问题化为标准形式；掌 握图解法，能用单纯形法求解线性规划问题；掌握灵敏度分析方法，能够建立线性规划模型 及用常用软件求解线性规划问题。
【教学重点】线性规划模型，图解法，单纯形方法，单纯形表，两阶段法，对偶线性规划，对偶单纯 形法，灵敏度分析。
【教学难点】基本可行解及线性规划的基本定理，单纯形方法，对偶线性规划，对偶理论，对偶单纯 形法。
第一节 线性规划模型线性规划(Linear Programming ， 简记为 LP )问题研究的是在一组线性约束条件下一个线 性函数最优问题。
§1．1 线性规划问题举例例 1.1.1 某工厂用 3 种原料 3 2 1 , , P P P 生产 3 种产品 3 2 1 , , Q Q Q 。
已知单位产品所需原 料数量如表 1.1.1 所示，试制订出利润最大的生产计划。
453 单位产品的利润（千元）20005 2 800 4 2 0 P 2 1500 0 3 2 P 1 原料可用量Q 3Q 2 Q 1 单位产品所需产品原料数量(kg)原料3P 3表 1.1.1分析 设产品 j Q 的产量为 j x 个单位， 3 , 2 , 1 = j ，它们受到一些条件的限制。
首先， 它们不能取负值，即必须有 3 , 2 , 1 , 0 = ³ j x j ；其次，根据题设，三种原料的消耗量分别不 能超过它们的可用量，即它们又必须满足：1223 123 231500 24800 3252000 x x x x x x x +£ ì ï+£ í ï ++£ î我们希望在以上约束条件下，求出 3 2 1 , , x x x ，使总利润 3 2 1 4 5 3 x x x z + + = 达到最大， 故求解该问题的数学模型为：123 12 23 123 max 354 231500 24800 .. 3252000 0,1,2,3j z x x x x x x x s t x x x x j =++ +£ ì ï +£ ï í++£ ï ï ³= î 类似这样的问题非常多。
线性规划原问题与对偶问题的转化及其应用摘要线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解.关键词：线性规划；原问题；对偶问题；转化LinearProgrammingistheOriginalProblemandtheTransformationoftheDualProblemandApplicationsAbstract:Linearprogramminginoperationalresearchisresearchearlier,rapiddevelopmentandw ideapplication,themethodisanimportantbranchofmature,itisoneofthescientificmanagementofa uxiliarypeoplemathematicalmethod.Canfromdifferentanglestolinearprogrammingdualproble mforpolicymakerstoprovidemorescientifictheorybasis.Thisarticlemainlyprobesintothelinearp rogrammingproblemandtherelationshipbetweenthedualproblem,linearprogrammingproblem andthetransformationofthedualproblem,theapplicationoflinearprogrammingdualproblem.Thi sarticleisthecomplexoftheoriginalproblemintoitsdualproblemtobesolved,simplifiesthelinearp rogrammingproblem,enablesustorapidlyfindtheoptimalsolutionoflinearprogrammingproble m.Keywords:linearprogramming;theoriginalproblem;thedualproblem;conversion目录4.4非对称型原问题转化为对偶问题 (10)1引言线性规划问题是运筹学里的一个重要的分支，它的应用比较广泛，因而是辅助人们进行现代科学管理的一种数学方法.随着线性规划理论的逐步深入，人们发现线性规划问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对，密切联系，反之亦然.我们把线性规划的这个特性称为对偶性.于是，我们将其中的一个问题称为原问题，另一个问题则称为它的对偶问题.对偶性不仅仅是数学上的理论问题，而且也是线性规划中实际问题的内在经济联系的必然反映.我们通过对对偶问题的深入研究，发现对偶问题能从不同角度对生产计划进行分析，从而使管理者能够间接地获得更多比较有用的信息.2文献综述2.1国内外研究现状在所查阅到的国内外参考文献[1-15]中，有不少文章是探讨了原问题转化为对偶问题的方法以及对偶性质的证明，并在对偶理论的应用方面有所研究.如郝英奇，胡运权在[1]、[10]中主要介绍了线性规划中原问题与对偶问题中的一些基本概念，探究了实际问题中的数学模型以及解.孙君曼，冯巧玲，孙慧君，李淑君等在[2]中探讨了对偶理论中互补松弛定理在各种情况下的使用方法,使学生更好地掌握互补松弛定理的含义和应用方法.胡运权，郭耀煌，殷志祥等在[3]、[5]中系统的介绍了线性规划中原始问题与对偶问题的两种形式.郭鹏，徐玖平等在[6]、[8]中用不同例子来说明了原问题转化为对偶问题的必要性.崔永新等在[9]、[15]中探讨了对偶问题的相关定理以及对偶问题的可行解和最优解之间的若干性质.李师正，王德胜在[11]中探讨了如何用计算机计算对偶问题的最优解.岳宏志，蔺小林，孙文喻等在[12]、[14]中探讨了对偶理论的证明过程，并用常见的例子来说明对偶理论的基本思想和解题方法.曾波，叶宗文在[13]中主要从经济管理的实际问题中阐述了线性规划的基本概念，基本原理，对偶理论，灵敏度分析等.2.2国内外研究现状评价文献[1-15]分别探讨了线性规划问题中原问题转化为对偶问题的理论依据以及如何利用对偶理论去解决实际生产问题.文献中主要探讨了对称型的原问题转化为对偶问题的方法.没有全面介绍非对称型的原问题与对偶问题之间转化的具体步骤，而且文献中对原问题转化为对偶问题的步骤提及甚少，大都一带而过，对应用中存在的问题也未给出详细深入的说明.2.3提出问题在线性规划问题中,根据实际生产中具体情况的需要,我们常常要把原问题与它的对偶问题进行转换,以解决一些复杂的线性规划问题,因而对偶问题的应用较为广泛.但大部分书籍都只介绍了线性规划问题的基础知识，并没有给出原问题与对偶问题转换的具体步骤.因此本文主要探讨了线性规划原问题与对偶问题之间转化的具体步骤，体会不同类型原问题的转化过程.3预备知识首先我先简单的介绍一些关于线性规划问题中的原问题和对偶问题的一些基本的知识.3.1对称形式的原问题我们将满足下列条件的线性规划问题称之为具有对称形式的线性规划问题.这类问题的变量都具有非负约束，当目标函数求极大值时，它的约束条件都取“≤”号，当目标函数求极小值时它的约束条件均取“≥”号.因而，这类数学模型的特点是：（1）所有的决策变量都是非负的；（2）所有的约束条件都是“≤”型；（3）目标函数是最大化类型.一般形式为：线性规划原问题的对称形式的]1[⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤+++≤+++≤+++),,2,1(0.22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n ΛΛMΛΛ(3.1) 3.2非对称形式的原问题不是所有的线性规划问题都具有对称的形式，我们将没有对称形式的线性规划问题称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件；，或是无限制的随意的组合.例如： ⎪⎪⎩⎪⎪⎨⎧≤≥≤++=++≤++无约束321333323213123232221211313212111,0,0.x x x b x a x a x a b x a x a x a b x a x a x a t s (3.2) 3.3对偶问题的定义在运筹学中，关于对线性规划的对偶规划给出的]2[定义如下.设给定的线性规划为：⎩⎨⎧≥≤0.X b AX t s (3.2) 其中()T n x x x X ,,,21Λ=，()nm ij a A ⨯=，()T m b b b b ,,,21Λ=，()n c c c C ,,,21Λ= 因此，定义它的对偶问题为：⎩⎨⎧≥≥0.Y C YA t s (3.4) 其中()m y y y Y ,,,21Λ=是行向量.(3.4)是对偶问题，(3.3)是原问题，(3.3)与(3.4)合在一起我们就称为是一对对称形式的对偶规划问题.3.4原问题转化为对偶问题的理论依据表所示：我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下]3[1表14原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面，是从两个角度对同一个研究对象提出的极值问题，两类极值的问题都具有相同的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易，为决策者提供更多的科学理论依据，因此我们常常需要把原问题转化为对偶问题.4.1原问题与对偶问题的关系一对对偶的线性规划问题具有相互对应的关系：（1）原问题中的目标函数值是max，约束条件是“≤”的形式；对偶问题的约束条件是“≥的形式.min目标函数值为，”（2）原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价值系数对应.（3）原问题的变量和对偶问题的约束条件对应，即，原问题中有个n变量，那么对偶问题就有个m变量.m约束条件，那么对偶问题就有个n约束条件；原问题有个（4）对偶问题的系数矩阵就是原问题的系数矩阵的转置.用矩阵表示，原问题为：则对偶问题为：需要注意的是，我们所讨论的对偶问题一定是指一对问题，而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题.4.2对称型原问题转化为对偶问题当线性规划问题为一般形式（3.1）时，我们将根据下面的四条规则转换为它的对偶问题：（1）原问题和它的对偶问题之间的系数矩阵互为转置.（2）原问题中变量的个数等于它的对偶问题的约束条件的个数.（3）原问题的右端常数就是对偶问题的目标函数的系数.（4）原问题的目标函数求极大时，约束条件是“≤”类型，而它的对偶问题的目标函数求极小，约束条件则为“≥”类型.形式：因此，它的对偶问题可以转变为如下的]4[例1生产计划问题云南一公司加工生产甲，乙两种产品，它的市场前景非常的好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供应.已知制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表2所示.问题：云南的这家公司应该怎样制定每天的生产计划，才能使它的产量得到最大？表2分析：为了建立此问题的数学模型，第一，要选定决策变量.第二，要确定问题的目标，即用来评价不同方案优劣的标准，这种目标总是决策变量的函数，称为目标函数.第三，我们把要确定达到目标时所受的限制条件，称之为约束条件.这里要决策的问题是，在现有人力、设备、矿石的限制下，如何确定产量使得产值自大？设1x 和2x 分别表示该公司A ，B 产品的数量，用z 表示产值，则每天的产值表示为2115090x x z +=，使其最大化，即2115090m ax x x z +=，称为目标函数.将制约因素表达出来，即有：人力不超过320工时，为3206821≤+x x ；设备不超过260台时有，2608621≤+x x ；原材料不超过300公斤有，30010421≤+x x 。
第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。
应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。
例：某家具厂木器车间生产木门与木窗；两种产品。
加工木门收入为56元/扇，加工木窗收入为30元/扇。
生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。
问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。
他想利用该木器车间的木工与油漆工来加工完成他的订单。
他就要考虑付给该车间每个工时的价格。
他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。
解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。
运筹学对偶问题的直观描述
运筹学中的对偶问题是指原始线性规划问题和对应的对偶线性规划问题之间的关系。
直观描述对偶问题可以从几个方面来理解。
首先，可以从成本和效益的角度来理解。
原始线性规划问题通常涉及最小化成本或者最大化利润，而对偶线性规划问题则涉及最大化成本或者最小化利润。
这种对偶关系可以被解释为在资源有限的情况下，通过最小化成本来实现最大化效益，或者通过最大化效益来实现最小化成本。
其次，可以从约束条件的角度来理解。
原始线性规划问题的约束条件对应着对偶线性规划问题的变量，而对偶线性规划问题的约束条件对应着原始线性规划问题的变量。
这种对偶关系可以被理解为在资源分配和利用的过程中，对约束条件和变量之间的转换和对应关系。
另外，可以从几何图形的角度来理解。
原始线性规划问题的最优解和对偶线性规划问题的最优解之间存在着一种对偶关系，即原始问题的最优解和对偶问题的最优解分别对应着凸集的两个相对的极值点，它们之间的距离可以被理解为对偶问题的最优值和原始问
题的最优值之间的关系。
总的来说，对偶问题在运筹学中具有重要的意义，它不仅可以帮助我们理解原始问题和对偶问题之间的关系，还可以为我们寻找最优解提供了一种新的视角和方法。
通过对偶问题的研究和理解，我们可以更好地解决实际生产和管理中的复杂问题。
第三章 线性规划及其对偶问题线性规划是最优化问题的一种特殊情形，也是运筹学的一个重要分支，它的实质是从多个变量中选取一组适当的变量作为解，使这组变量满足一组确定的线性式，而且使一个线性目标函数达到最优（最大或最小）．线性规划的应用极为广泛，自1949年美国数学家G. B. Dantzing 提出一般线性规划问题求解的方法——单纯形法之后，线性规划无论在理论上、计算方法和开拓新的应用领域中，都获得了长足的进步，线性规划从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都有广泛的发展和应用．本章主要从线性规划的基本概念、数学模型、单纯形法、对偶理论、灵敏度分析等方面进行介绍．§3.1 线性规划数学模型基本原理一、线性规划的数学模型满足以下三个条件的数学模型称为线性规划的数学模型：（1）每一个问题都用一组决策变量T n x x x ][21，，， 表示某一方案；每一组值就代表一个具体方案．（2）有一个目标函数，可用决策变量的线性函数来表示，按问题的不同，要求目标函数实现最大化或最小化．（3）有一组约束条件，可用一组线性等式或不等式来表示． 线性规划问题的一般形式为1211221111221121122222112212max(min)()()()..()0n n n n n n n m m mn n m n f x x x c x c x c x a x a x a x b a x a x a x b s t a x a x a x b x x x =++++++≤=≥⎧⎪+++≤=≥⎪⎪⎨⎪+++≤=≥⎪⎪≥⎩，，，，，，，，，，，，，．这里，目标函数中的系数n c c c ，，， 21叫做目标函数系数或价值系数，约束条件中的常数m b b b ，，， 21叫做资源系数，约束条件中的系数；，，，m i a ij 21(= )21n j ，，， =叫做约束系数或技术系数．二、线性规划问题的标准形式所谓线性规划问题的标准形式，是指目标函数要求min ，所有约束条件都是等式约束，且所有决策定量都是非负的，即1211221111221121122222112212min ()..0n n n n n n n m m mn n mn f x x x c x c x c x a x a x a x b a x a x a x b s t a x a x a x b x x x =++++++=⎧⎪+++=⎪⎪⎨⎪+++=⎪⎪≥⎩，，，，，，，，，，，或简写为11min ()12..012nj j j nij ji j jf X c x a x b i m s t x j n ===⎧==⎪⎨⎪≥=⎩∑∑，，，，，，，，，，． 可以规定各约束条件中的资源系数0(12)i b i n ≥=，，，，否则等式两端乘以“1-”．线性规划问题的矩阵表示为min ()..0f X CX AX b s t X ==⎧⎨≥⎩，，，其中12[]n C c c c =，，，，12[]T n X x x x =，，，，11121212221212n n n m m mn a a a a a a A P P P a a a ⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦［，，，］，12[]T n b b b b =，，，． 任意的线性规划模型都可以转化为标准形式：（1）若目标函数是求最大值的问题，这时只需将所有目标函数系数乘以“－1”，求最大值的问题就变成了求最小值的问题，即)](min[)(max X f X f --=．求其最优解后，把最优目标函数值反号即得原问题的目标函数值．（2）若约束条件为不等式，这里有两种情况：一种是“≤”不等式，则可在“≤”不等式的左端加入一个非负的新变量（叫松驰变量），把不等式变为等式；另一种是“≥”不等式，则可在“≥”不等式的左端减去一个非负松驰变量（也叫剩余变量），把不等式变为等式．松驰变量在目标函数中对应的系数为零．（3）若存在取值无约束的变量k x ，可令k k k x x x ''-'=，其中k x '，0≥''k x ． 例3.1 将下列线性规划问题化为标准形式123123123123123max ()2372.3250f X x x x x x x x x x s t x x x x x x =-+++≤⎧⎪-+≥⎪⎨-++=⎪⎪≥⎩，，，，，，为无约束． 解 将目标函数变为)](min[X f -，令543x x x -=，其中450x x ≥，，在第一个约束不等式中加入松驰变量6x ，在第二个约束不等式中减去剩余变量7x ，则可得标准形式12456712456124571245124567min[()]23()00()7()2.32()5,,,,,0f X x x x x x x x x x x x x x x x x s t x x x x x x x x x x -=-+--++++-+=⎧⎪-+--=⎪⎨-++-=⎪⎪≥⎩，，，，．三、线性规划的解的概念和基本定理 考虑线性规划标准形式的约束条件0AX b X =≥，，其中A 为n m ⨯矩阵，m n >，b 是m 维向量．假定增广矩阵,A b ［］的秩=矩阵A 的秩m =，把矩阵A 的列进行可能的重新排列，使,A B N =［］．这里B 为m m ⨯矩阵，且有逆矩阵存在，即0||≠B ，称B 为该线性规划问题的一个基．不失一般性，设111211212,,,m m m m mm a a a B PP P a a a ⎡⎤⎢⎥==⎢⎥⎢⎥⎣⎦［］， 称(12)j P j m =，，，为基向量，与基向量对应的变量(12)j x j m =，，，称为基变量，记为12T B m X x x x =［，，，］，其余的变量称为非基变量，记为12T N m m n X x x x ++=［，，，］．令m n -个非基变量均为0，并用高斯消元法，可得一个解12[][00]T T T T B N m X X X x x x ==，，，，，，，，称X 为该约束方程组的基解，其中b B X B 1-=．满足非负约束条件0≥X （基解的非零分量都0≥）的基解称为基可行解．对应于基可行解的基称为可行基．基可行解的非零分量个数小于m 时，称为退化解．线性规划的解的基本定理：引理3.1 线性规划问题的可行解12[]T n X x x x =，，，为基可行解的充要条件是X 的正分量所对应的系数列向量是线性无关的．证 必要性由基可行解的定义可知．下证充分性若向量组k P P P ，，，21线性无关，则必有m k ≤；当m k =时，它们恰构成一个基，从而12[00]T k X x x x =，，，，，，为相应的基可行解．当m k <时，则一定可以从其余的列向量中取出k m -个与k P P P ，，，21构成最大的线性无关向量组，其对应的解恰为X ，所以它是基可行解． 定理3.1 线性规划问题的基可行解X 对应于可行域D 的顶点． 证 不失一般性，假设基可行解X 的前m 个分量为正，故∑==mj jj b xP 1．（3.1）现在分两步来讨论，分别用反证法．（1）若X 不是基可行解，则它一定不是可行域D 的顶点．根据引理3.1，若X 不是基可行解，则其正分量所对应的系数列向量m P P P ，，， 21线性相关，即存在一组不全为零的数12i i m α=，，，，，使得02211=+++m m P P P ααα （3.2）用一个0>μ的数乘式（3.2），再分别与式（3.1）相加和相减，得到111222()()()m m m x P x P x P b μαμαμα-+-++-=，111222()()()m m m x P x P x P b μαμαμα++++++=．现取11122[()()()00]T m m X x x x μαμαμα=---，，，，，，，21122[()()()00]T m m X x x x μαμαμα=+++，，，，，，，由21X X ，可得121122X X X =+，即X 是21X X ，连线的中点．另一方面，当μ充分小时，可保证012i i x i m μα±≥=，，，，，即21X X ，是可行解，这证明了X 不是可行域D 的顶点．（2）若X 不是可行域D 的顶点，则它一定不是基可行解．因为X 不是可行域D 的顶点，故在可行域D 中可找到不同的两点，(1)(1)(1)112[]T nX x x x =，，，，T nx x x X ][)2()2(2)2(12，，， =，使12(1)01X X X ααα=+-<<，．设X 是基可行解，对应向量组m P P P ，，， 21线性无关，当m j >时，有0)2()1(===j j j x x x ，由于21X X ，是可行域的两点，应满足∑∑====mj mj jj j j b xP b x P 11)2()1(,．将这两式相减，即得∑==-mj j j jx xP 1)2()1(0)(．因21X X ≠，所以上式系数)()2()1(j j x x -不全为零，故向量组m P P P ，，， 21线性相关，与假设矛盾，即X 不是基可行解．定理3.2 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优．证 设k X X X ，，， 21是可行域的顶点，若0X 不是顶点，且目标函数在0X 处达到最优*0()f X CX =（标准形式是*()min ()f X f X =）．因0X 不是顶点，所以它可以用D 的顶点线性表示为01101kki i i i i i X X ααα===≥=∑∑，，．因此011k ki i i i i i CX C X CX αα====∑∑．（3.3）在所有的顶点中必然能找到某一个顶点m X ，使m CX 是所有i CX 中最小者，并且将m X 代替式（3.3）中的所有i X ，得到∑∑===≥ki ki m m i ii CX CX CX11αα，由此得到m CX CX ≥0．根据假设，0CX 是最小值，所以只能有m CX CX =0，即目标函数在顶点m X 处也达到最小值．§3.2 线性规划迭代算法单纯形法是求解线性规划问题的迭代算法．一、单纯形法的计算步骤单纯形法的基本思路是：从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），直到目标函数达到最优时，基可行解即为最优解．单纯形法的基本过程如图3.1所示．为计算方便，通常借助于单纯形表来计算，从初始单纯形表3.1开始，每迭代一步构造一个新单纯形表．单纯型表中B X 列中填入基变量m x x x ，，， 21；B C 列中填入基变量的价值系数m c c c ，，， 21；b 列中填入约束方程组右端的常数；j θ列的数字是在确定换入变量后，按θ规则计算填入；最后一行称为检验数行，对应各非基变量j x 的检验数是∑=-=-=mi j j ij i j j z c a c c 1σ，1j m n =+，，（这里令∑==mi ijj j ac z 1）．（1）找出初始可行基，确定初始基可行解，建立初始单纯形表． （2）检验各非基变量j x 的检验数∑=-=-=mi j j iji j j z c ac c 1σ（1j m n =+，，）．若所有0≥j σ，则已得到最优解，停止计算．否则转入下一步．（3）在0(1)j j m n σ<=+，，，中，若所有0≤jk a ，则此问题无最优解，停止计算．否则转入下一步．（4）根据min{|0}j j k σσσ<=，确定k x 为换入变量．按θ规则计算min 0i l ik ik lkb ba a a θ⎧⎫=>=⎨⎬⎩⎭， 可确定l x 为换出变量，转入下一步．（5）以lk a 为主元素进行迭代（用高斯消元法），把k x 所对应的列向量120010k k k lk mk a a P l a a ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=−−−→⎢⎥⎢⎥←⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦变换成第行， 将B X 列中的l x 换为k x ，得到新的单纯形表，重复步骤（2）—步骤（5），直到终止．单纯形法的流程图如图3.2所示．若目标函数要求实现最大化，一方面可将最大化转换为最小化，另一方面也可在上述计算步骤中将判定最优解的0≥j σ改为0≤j σ，将换入变量的条件min{|0}j j k σσσ<=改为max{|0}j j k σσσ>=．二、初始可行基的确定 （1） 若线性规划问题是11min ()12..012nj j j nij ji j jf X c x a x b i m s t x j n ===⎧==⎪⎨⎪≥=⎩∑∑，，，，，，，，，，， 则从(12)j P j n =，，，中一般能直接观察到存在一个初始可行基12100010[,,,]001m B P P P ⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦．（2）对所有约束条件是“≤”形式的不等式，可以利用化标准形式的方法，在每个约束条件的左端加入一个松驰变量，经过整理重新对j x 及ij a 进行编号，可得下列方程组．，，m n mn m m m m n n m m n n m m b x a x a x b x a x a x b x a x a x =+++=+++=+++++++++ 11,2211,221111,11显然得到一个m m ⨯单位矩阵B 可作为初始可行基12100010[,,,]001m B P P P ⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦． （3）对所有约束条件是“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人工变量，即对不等式约束减去一个非负的剩余变量后，再加入一个非负的人工变量；对等式约束再加入一个非负的人工变量，总可得到一个单位矩阵作为初始可行基．例3.2 求解线性规划问题12121212max ()2328416..4120f X x x x x x s t x x x =++≤⎧⎪≤⎪⎨≤⎪⎪≥⎩，，，，，． 解：将线性规划问题化为标准形式12345123142512345min[()]2300028416..4120f X x x x x x x x x x x s t x x x x x x x -=--+++++=⎧⎪+=⎪⎨+=⎪⎪≥⎩，，，，，，，，．作初始单纯形表，按单纯形法计算步骤进行迭代，结果如下（表3.2）．表3.2最后一行的检验数均为正，这表示目标函数值已不可能再减小，于是得到最优解*42004T X =［，，，，］，目标函数值14)(*=X f ．三、单纯形法的有关说明对线性规划问题min ()..0f X CX AX b s t X ==⎧⎨≥⎩，，，（3.5） 若系数矩阵中不含单位矩阵，没有明显的基可行解时，常采用引入非负人工变量的方法来求初始基可行解．下面分别介绍常用的“大M 法”和“两阶段法”．（一）大M 法在约束条件式（3.5）中加入人工变量，人工变量在目标函数中的价值系数为M ，M 为一个很大的正数．在迭代过程中，将人工变量从基变量中逐个换出，如果在最终表中当所有检验数0≥j σ时，基变量中不再含有非零的人工变量，这表示原问题有解，否则无可行解．例3.3 求解线性规划问题12312312313123min ()3211423..210f X x x x x x x x x x s t x x x x x =-++-+≤⎧⎪-++≥⎪⎨-+=⎪⎪≥⎩，，，，，，． 解：将原问题化为标准形式并引入人工变量，得12345671234123561371234567min ()300211423..210f X x x x x x Mx Mx x x x x x x x x x s t x x x x x x x x x x =-++++++-++=⎧⎪-++-+=⎪⎨-++=⎪⎪≥⎩，，，，，，，，，，．用单纯形法计算，得表3.3．根据表 3.3的最后一行的检验数均0≥，得最优解*4190000T X =［，，，，，，］，最优值2)(*-=X f ，由于人工变量的值均为零，故得原问题的最优解*419T X =［，，］，最优值为2)(*-=X f ．（二）两阶段法两阶段法是把线性规划问题的求解过程分为两个阶段：第一阶段，给原问题加入人工变量，构造仅含价值系数为1的人工变量的目标函数且要求实现最小化，其约束条件与原问题相同，即11111111211221112min ()00..0n n m n n n n nn n n m mn n n m m n m g X x x x x a x a x x b a x a x x b s t a x a x x b x x x ++++++=++++++++=⎧⎪+++=⎪⎪⎨⎪+++=⎪⎪≥⎩，，，，，，，． 然后用单纯形法求解上述问题，若得到0)(=X g ，这说明原问题存在基可行解，可进入第二阶段计算，否则原问题无可行解，停止计算．第二阶段，将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换为原问题的目标函数系数，作为第二阶段计算的初始单纯形表进行计算．例3.4 用两阶段法求解线性规划问题12312312313123min ()3211423.210f X x x x x x x x x x s t x x x x x =-++-+≤⎧⎪-++≥⎪⎨-+=⎪⎪≥⎩，，，，，，． 解 第一阶段，标准化并引入人工变量，得如下的线性规划=)(min X g 76x x +，1234123561371234567211423.210x x x x x x x x x s t x x x x x x x x x x -++=⎧⎪-++-+=⎪⎨-++=⎪⎪≥⎩，，，，，，，，，． 用单纯形法计算该线性规划（见表 3.4），最优解为*[011120000]T X =，，，，，，，，最优值0)(*=X g ．表3.4由于人工变量076==X X ，所以得原问题的基可行解为[011120]T X =，，，，．于是进入第二阶段计算（见表3.5），最优解为*[41900]T X =，，，，，最优值2)(*-=X f ，于是原问题的最优解为*[419]T X =，，，最优值为2)(*-=X f ．§3.3 对偶问题的基本原理一、对偶问题的提出对偶性是线性规划的重要内容之一，每一个线性规划问题必然有与之相伴而生的另一个线性规划问题，我们称一个叫原问题，另一个叫对偶问题，这两个问题有着非常密切的关系，让我们先分析一个实际的线性规划模型与其对偶线性规划问题的经济意义．例3.5 某工厂计划在下一生产周期生产3种产品1A ，2A ，3A ，这些产品都要在甲、乙、丙、丁4种设备上加工，根据设备性能和以往的生产情况知道单位产品的加工工时，各种设备的最大加工工时限制，以及每种产品的单位利润（单位：千元），如表3.6所示，问如何安排生产计划，才能使工厂得到最大利润？解 设321x x x ，，分别为产品321A A A ，，的产量，构造此问题的线性规划模型为1231231231312123max ()8102237042280..3152250,,0f X x x x x x x x x x s t x x x x x x x =++++≤⎧⎪++≤⎪⎪+≤⎨⎪+≤⎪⎪≥⎩，，，，，．现在从另一个角度来讨论该问题．假设工厂考虑不安排生产，而准备将所有设备出租，收取租费．于是，需要为每种设备的台时进行估价．设4321y y y y ，，，分别表示甲、乙、丙、丁4种设备的台时估价．由表3.6可知，生产一件产品1A 需用各设备台时分别为h h h h 2342，，，，如果将h h h h 2342，，，不用于生产产品1A ，而是用于出租，那么将得到租费43212342y y y y +++．当然，工厂为了不至于蚀本，在为设备定价时，保证用于生产产品1A 的各设备台时得到的租费，不能低于产品1A 的单位利润8千元，即823424321≥+++y y y y ．按照同样分析，用于生产一件产品2A 的各设备台时h 1，h 2，0，h 2所得的租费，不能低于产品2A 的单位利润10千元，即1022421≥++y y y ．同理，还有223321≥++y y y ．另外，价格显然不能为负值，所以01234iy i ≥=，，，，． 企业现在设备的总以时数为70h ，80h ，15h ，50h ，如果将这些台时都用于出租，企业的总收入为422150158070)(y y y y Y g +++=．企业为了能够得到租用设备的用户，使出租设备的计划成交，在价格满足上述约束的条件下，应将设备价值定得尽可能低，因此取)(Y g 的最小值，综合上述分析，可得到一个与例3.5相对应的线性规划，即123412341231231234min ()70801550243282210..3220g Y y y y y y y y y y y y s t y y y y y y y =++++++≥⎧⎪++≥⎪⎨++≥⎪⎪≥⎩，，，，，，，．称后一个规划问题为前一个规划问题的对偶问题，反之，也称前一个规划问题是后一个规划问题的对偶问题．二、原问题与对偶问题的表达形式和关系在线性规划的对偶理论中，把如下线性规划形式称为原问题的标准形式11221111221121122222112212min ()..0n n n n n n m m mn n mn f X c x c x c x a x a x a x b a x a x a x b s t a x a x a x b x x x =++++++≥⎧⎪+++≥⎪⎪⎨⎪+++≥⎪⎪≥⎩，，，，，，，． 而把如下线性规划形式称为对偶问题的标准形式11221111221121122222112212max ()..0n n m m m m n n mn m nm g Y b y b y b y a y a y a y c a y a y a y c s t a y a y a y c y y y =++++++≥⎧⎪+++≥⎪⎪⎨⎪+++≥⎪⎪≥⎩，，，，，，，． 若用矩阵形式表示，则原问题和对偶问题分别可写成如下形式：原问题min ()..0f X CX AX b s t X =≥⎧⎨≥⎩，，．（3.6）对偶问题max ()..0g Y Yb YA C s t Y =≤⎧⎨≥⎩，，．（3.7）原问题与对偶问题的关系见表3.7．例3.6 求下面线性规划问题的对偶问题123412341342341234min ()23535224..600f X x x x x x x x x x x x s t x x x x x x x =+-++-+≥⎧⎪+-≤⎪⎨++=⎪⎪≤≥⎩，，，，，，，无约束． 解：根据表3.7可直接写出上述问题的对偶问题12312131********max ()546223..325100g Y y y y y y y y s t y y y y y y y y y =+++≥⎧⎪+≤⎪⎪-++≤-⎨⎪-+=⎪⎪≥≤⎩，，，，，，，无约束． 三、对偶理论定理3.3（弱对偶定理） 对偶问题（max ）的任何可行解︒Y ，其目标函数值总是不大于原问题（min ）任何可行解︒X 的目标函数值．证 由定理所设及问题（3.6）和问题（3.7）容易看出︒︒︒︒≤≤CX AX Y b Y ．定理3.4（对偶定理） 假如原问题或对偶问题之一具有有限的最优解，则另一问题也具有有限的最优解，且两者相应的目标函数值相等．假如一个问题的目标函数值是无界的，则另一问题没有可行解．证明从略．定理3.5（互补松驰定理） 假如︒X 和︒Y 分别是原问题（3.6）和对偶问题（3.7）的可行解，︒U 是原问题剩余变量的值，︒V 是对偶问题松驰变量的值，则︒X 、︒Y 分别是原问题和对偶问题最优解的充要条件是0=+︒︒︒︒X V U Y ．证 由定理所设，可知有0AX U b X U ︒︒︒-=︒≥，，，（3.8） 0Y A V C Y V ︒︒︒︒︒+=≥，，．（3.9）分别以︒Y 左乘式（3.8），以︒X 右乘式（3.9），两式相减，得b Y CX X U U Y ︒︒︒︒︒︒-=+．若0=+︒︒︒︒X V U Y ，根据弱对偶定理知CX b Y CX Yb ≤=≤︒︒．这说明︒X ，︒Y 分别是原问题和对偶问题最优解，反之亦然．根据互补松驰定理和决策变量满足非负条件可知，在最优解时，︒︒U Y 和︒︒X V 同时等于0，所以有)21(000n j x v j j ，，， ==， )21(000m i u y i i ，，， ==． 于是，互补松驰定理也可以这样叙述：最优化时，假如一个问题的某个变量取正数，则相应的另一个问题的约束条件必取等式；或者一个问题中的约束条件不取等式，则相应于另一问题中的变量必为零．例3.7 已知线性规划问题123451234512445min ()23523234.2330125jf X x x x x x x x x x x s t x x x x x x j =++++⎧++++≥⎪-+++≥⎨⎪≥=⎩，，，，，，，．已知其对偶问题的最优解为5)(5/35/4**2*1===Y g y y ，，，试用对偶理论找出原问题的最优解．解：先写出它的对偶问题12121212121212max ()4322(1)3(2)235(3)..2(4)33(5)0g Y y y y y y y y y s t y y y y y y =++≤⎧⎪-≤⎪⎪+≤⎪⎨+≤⎪⎪+≤⎪≥⎪⎩，，，，，，，．将*2*1y y ，的值代入约束条件，得（2），（3），（4）为严格不等式，由互补松驰定理得***2340x x x ===，因021≥y y ，，原问题的两个约束条件应取等式，故有**1534x x +=， **1523x x +=．求解后得到**1511x x ==，，故原问题的最优解为 **10001()5TX f X ==［，，，，］，．四、对偶问题的迭代算法对偶单纯形法是对偶问题的迭代算法，其基本思想是：从原问题的一个基本解出发，此基本解不一定是可行解，但它对应着对偶问题的一个可行解；然后检验原问题的基本解是否可行，即是否有负的分量．如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解．如果得到的基本解的分量皆非负，则该基本解为最优解．也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行解，使原问题的基本解由不可行逐步变为可行．当同时得到对偶问题与原问题的可行解时，便得到原问题的最优解．对线性规划问题的标准形式min ()..0f X CX AX b s t X =≥⎧⎨≥⎩，，．对偶单纯形法的计算步骤如下：(1)找出原问题的一个基，构成初始对偶基可行解，使所有检验数0≥j σ，构成初始对偶单纯形表．(2)若所有0≥i b ，则当前的解是最优解，停止计算，否则计算min{|0}l i i b b b =<，则l 行为主行，该行对应的基变量为换出变量．(3)若所有0≥lj a ，则对偶问题无界，原问题无解，停止计算，否则计算min |0j k lj lj lka a a σσθ⎧⎫⎪⎪=<=⎨⎬--⎪⎪⎩⎭，则k 列为主列，该列对应的基变量为换入变量．(4)以lk a 为主元素进行迭代，然后转回步骤(2)． 对偶单纯形法的流程图如图3.3所示．例3.8 用对偶单纯形法求解下述线性规划问题123123123123min ()23423..2340f X x x x x x x s t x x x x x x =++++≥⎧⎪-+≥⎨⎪≥⎩，，，，，．解：首先将“≥”约束条件两边反号，再加入松驰变量，可得原问题的一个基123451234123512345min ()2340023..2340f X x x x x x x x x x s t x x x x x x x x x =++++---+=-⎧⎪-+-+=-⎨⎪≥⎩，，，，，，，．图3.3从表3.8看出，所有检验数0≥j σ，则对应对偶问题的解是可行的，因b 列数字为负，需进行迭代，计算min 344--=-｛，｝．所以5x 为换出变量．又因为24min 123θ⎧⎫=-=⎨⎬⎩⎭，，，所以1x 为换入变量，以换入、换出变量所在行列交叉处元素“－2”为主元素，按单纯形法计算步骤进行迭代，得表3.9．由表3.9的最后一行看出，所有检验数0≥j σ，故原问题的最优解为*[11/52/50]T X =，，．若对应两个约束条件对偶变量为1y ，2y ，则可得对偶问题的最优解为*[8/51/5]T Y =，．§3.4 线性规划问题灵敏度在建立实际的线性规划模型时，所收集到的数据不是很精确；另一方面在实际应用中，各种信息瞬息万变，已形成的数学模型中的某些数据需要随之而变．因此，对于一个线性规划问题，研究当数据发生变动时解的变化情况是很重要的．下面仅介绍两种数据变化而导致解的变化的情况，这就是灵敏度分析问题．一、价值系数的变化假设只有一个系数k C 变化，其它系数保持不变 ，k C 的变化只影响检验解而不影响解的非负定性，下面分别就k C 是非基变量系数和基变量系数两种情况进行讨论．（1）k C 是非基变量的系数由于B C 不变，因而j Z 对任何j 都不变．这时非基变量的系数k C 的变化只影响与k C 有关的一个检验数k σ的变化，而对其它j σ没有影响，设系数从k C 变化到k C '，这时检验数k k k Z C -=σ被k k kZ C -'='σ所代替，在当前解是原问题的最优解时，有0≥-=k k k Z C σ，假如()(k k k k k k C Z C Z C σ'''=-=-+)0k C -<，则k X 必须引进基，单纯形法继续进行，否则原解仍是k C 变化后的新问题的最优解，最优解不变相当于k C '变化的界限为)(k k k kZ C C C --≥'． （2）k C 为基变量的系数当k C 被k C '所代替时，j Z 变成j Z '，j j Z C '-可计算为kj k kj j j j a C C Z C Z C )(-'--='-． （3.10）特别是当k j =时，0=-k k Z C ，且1=kk a ，因此k k k k C C Z C -'='-，仍为零．由式（3.10）知，基变量k x 的价值系数k C 的变化会引起整个价值系数行的变化，变化值为)(k k C C -'-乘以最终表相应该基变量k x 所在的k 行的数值kj a ．k 列本身则调整为0='-'k k Z C ．由式（3.10）可看出，当对某个非基变量j x ，式（3.10）为负时会引起基的变化，若要保持最优解不变，分析变化值)(k k C C -'且大于或小于零以及kj a 值是正或负的情况，得出会保持最优解不变的k C '的变化界限为max 0min 0j j j j k kj k k kj j jkj kj C Z C Z C a C C a a a ⎧⎫⎧⎫--⎪⎪⎪⎪'+<≤≤+>⎨⎬⎨⎬⎪⎪⎪⎪⎩⎭⎩⎭．例3.8 以例3.2的最终表为例，设基变量2x 的系数2C 变化2C ∆，在原最优解不变条件下，确定2C ∆的变化范围．解 此时例3.2的最终表便成为表3.10为了保持原最优解不变，则2x 的检验数应当为零，进行行初等变换，得表3.11．从表（3.11）可得02232≥∆-C 且08812≥∆+C ． 由此可得2C ∆的变化范围为312≤∆≤-C ，即2x 的价值系数2C 可以在[0，4]之间变化，而不影响原最优解．二、资源系数的变化假设资源系数k b 变化为k b '，k b 的变化将会影响解的可行性，但不会引起检验数的符号变化．根据基可行解的矩阵表示可知，b B X B 1-=，所以只要k b 变化必定会导致最优解的数值发生变化，最优解的变化分为两类：一类是保持01≥-b B ，最优基B 不变；另一类是b B 1-中出现负分量，这将使最优基B 变化，若最优基不变，则只需将变化后的k b 代入B X 的表达式重新计算即可；若b B 1-中出现负分量，则要通过迭代求解新的最优基和最优解．设系数k b 变化到k k k b b b ∆+='，而其它系数都不变，这样使最终表中原问题的解相应变化为11111100k B k k k k m mk m b a b X B b b B b B b b b a b ---⎡⎤⎡⎤⎢⎥⎢⎥'⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥'=+∆=+∆=+∆⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥'⎢⎥⎣⎦⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦， 其中B X 为原最优解，i b '为B X 的第i 个分量，ik a 为1-B 的第i 行第k 列元素，为了保持最优基不变，应使0≥'B X ，即110k k m mk a b b b a '⎡⎤⎡⎤⎢⎥⎢⎥+∆≥⎢⎥⎢⎥⎢⎥⎢⎥'⎣⎦⎣⎦． 由此可得到保持最优基不变时，资源系数的变化界限为max 0min 0i i k ik k k ik ik ik b b b a b b a a a ⎧⎫⎧⎫''--⎪⎪⎪⎪'+>≤≤+<⎨⎬⎨⎬⎪⎪⎪⎪⎩⎭⎩⎭．例3.9 若例3.2的第二个约束条件中2b 变化为22b b ∆+，在最优解不变的条件下，求2b ∆的变化范围．解 计算⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡≥∆⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-+⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∆+--000812141244002211b b B b B可得2224/(1/4)164/(1/2)82/(1/8)16b b b ∆≥-=-∆≥-=-∆≤--=，，．所以2b ∆的变化范围是（－8，16）．显然2b 的变化范围是（8，32）．。
