第1-4章 线性规划及对偶理论2

夫运筹帷幄之中决胜于千里之外运筹学课件线性规划LinearProgramming本章内容线性规划问题的数学建模图解法单纯形法原理单纯形法的计算步骤WinQSB软件求解教学说明教学目标：掌握LP的建模方法，熟练地使用单纯形法求解模型，借助WinQSB软件求解问题重点与难点：重点是LP的建模与解法；难点是单纯形法的原理教学方法：配合课件和WinQSB软件，课堂讲授为主，案例研讨为辅思考题、讨论题、作业：教材第1-3章习题学时分配：8学时线性规划的产生与发展1939年苏联的经济学家康托洛维奇在《生产组织与计划中的数学方法》一书中，首次用线性规划方法解决了生产组织与运输问题。1947年美国数学家G.B.Dantzig提出了线性规划的数学模型，并给出了求解该模型的单纯形法（Simplexmethod)。这标志着线性规划这一运筹学的重要分支的诞生。计算机的发展促进了LP计算理论的发展，使其应用更加广泛和深入。线性规划的应用范围生产中的组织与计划问题运输问题合理下料问题配料问题生产布局问题特点：在现有条件下，统筹安排，使总的经济效益最好，或者是总成本最省。某工厂制造A、B两种产品，它们的原材料单位消耗、单位利润以及资源现有量如下表：问如何组织生产，使工厂获得最大利润？例1：生产组织与计划问题AB资源现有量（吨）钢材23600煤21400单位利润（万元）205产品资源资源消耗1－1线性规划的数学建模建立数学模型步骤1.假设决策变量：设A、B两种产品各生产个单位；2.建立目标函数：利润函数是，求它的最大值，即3.现有资源的限制条件：4.决策变量必须有非负限制：数学模型目标函数系统约束非负限制

注意：目标函数和约束条件中变量的次数都是一次的，这样的模型称为线性规划数学模型。生产计划安排问题的一般描述资源产品消耗资源现有量单位产品利润求解使工厂获得最大利润的生产方案。生产计划安排问题的一般数学模型解：设表示生产产品的单位数，则有如下的数学模型：设有某种物资从A、B、C三个产地调出，运往甲、乙、丙三个需求地，其调运量及运价如下表。求运费最省的调运方案。

甲乙丙调出量

A2457B1344C3239调入量686（20）调出调入运价例2：运输问题设表示从i地调往j地的调运量产销平衡运输问题的一般描述产量销量产地销地运价求解使运输总成本最低的方案。设表示从i地调往j地的调运量产销平衡运输问题的一般模型例3：合理配载问题某货船的前舱、中舱、后舱的载重分别为2000吨、3000吨、1000吨，容积分别为100000立方米、135000立方米、30000立方米；顾客托运的货物A、B、C的重量、体积、运费等资料已知。为了保持货船的稳定，要求三个货舱载货率必须平衡。问如何装载，使收入最大？例4：连续投资问题某地区今后三年内可以有A、B、C、D四个项目的投资选择，总资金量为3000万元。其中项目A在三年内每年年初投资，当年年底可回收本利和为120％；项目B第一年年初投资，第二年年底可回收本利和为150％，但投资额不超过2000万元；项目C第二年年初投资，第三年年底可回收本利和为160％，但投资额不超过1500万元；项目D第三年年初投资，当年年底可收回本利和为140％，投资额不超过1000万元。问如何安排投资，使第三年年底本利和的金额最大？思考题1：配料问题

某化工厂要用三种原料混合配置三种不同规格的产品，各产品的规格、单价见下表：产品规格单价（元/公斤）A原料Ⅰ不少于50%原料Ⅱ不超过25%50B原料Ⅰ不少于25%原料Ⅱ不超过50%35C不限25问如何安排生产使得生产利润最大？原料日最大供应量单价(元/公斤)Ⅰ10065Ⅱ10025Ⅲ6035原料的单价与每天最大供应量见下表：思考题2：人力资源分配问题某个中型百货商场对售货人员（周工资400元）的需求经统计如下表为了保证销售人员充分休息，销售人员每周连续工作5天，休息2天。问应如何安排销售人员的工作时间，使得人力总成本最小？星期一二三四五六日人数12151214161819思考题3：合理下料问题要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原材料长7.4m，应如何切割，使用原材料最节省，试建立线性规划模型并求解。课堂练习：三种产品要分别经过A,B两道工序。产品Ⅰ可在A,B的任何设备上加工；产品Ⅱ可在A的任何设备上加工后，只能在B1设备上加工；产品Ⅲ只能在A2和B2设备上加工。

试安排最优生产计划，使该厂获利最大。1－2线性规划问题解的性质⒈两个变量的线性规划问题的图解法几个基本概念：⑴满足所有约束条件的解称为LP问题的可行解；所有可行解的集合称为可行解集。⑵使目标函数达到最优的可行解称为LP问题的最优解。问题：线性规划是一个带有约束条件的极值问题，能否用微积分方法求解?例1：用图解法求解下面的LP问题目标函数等值线此点为LP的最优解maxSminS得到这个最优解：本问题有唯一最优解。例2：用图解法解下面的线性规划

目标函数等值线maxSminS得到LP的最优解及目标函数最优值：

除A、B两个最优解外，AB线段上的所有点都是LP的最优解。本问题有无穷多最优解。例3：用图解法解下面的线性规划无界的可行解集

此题有可行解，但无最优解maxSminS例4：用图解法解下面的线性规划无可行解

本题无可行解，更无最优解有唯一最优解，这个最优解一定在可行解集合的某一顶点上达到有无穷多最优解，最优解充满一个线段，可以用它的两个端点作为代表有可行解，但无最优解（无界解）无可行解小结：LP图解法有如下四种情况线性规划问题解的关系线性规划问题的解无可行解

有可行解唯一最优解无最优解有最优解无穷多最优解⒉线性规划问题的标准形式将一般的LP转化为LP标准形：规定:⑴求目标函数的最大值为标准形，即目标函数为maxS。如果问题是求

minS时，可令求

，相当于求minS

。规定:⑵以等式约束为标准形。设第k

个等式为(3)LP中所有的变量都有非负限制。如果实际问题中的LP里某个变量无非负限制，可如下处理:(4)若约束条件为等式，但右端项为负值，则在等式两边同时乘以-1即可规定:将下列线性规划模型化为标准形根据以上的规定，LP的标准形为：两种缩写形式：矩阵表示法：3.LP问题解的性质⑴几个概念①凸集：若连接n维点集S中任意两点的线段仍在S内，则称S为凸集。即凸集凸集不是凸集极点②极点：若凸集S中的点x，不能成为S中任何线段的内点，则称x为S的极点。③设为LP的一个可行解，若或的非零分量对应的A中列向量线性无关，则称它为基础可行解。由这些列向量组成的矩阵称为基矩阵，与这些列向量对应的变量称为基变量，其余的变量称为非基变量。使目标函数值达到最优值的可行解称为最优解；使目标函数达到最优值的基础可行解称为基础最优解。可行解集基础可行解最优解基础最优解线性规划解的关系目标函数约束条件行列式≠0基矩阵右边常数=⑵几个重要定理（单纯形法的理论依据）定理1

线性规划问题的可行解集为凸集，即连接线性规划问题任意两个可行解的线段上的点仍为可行解。定理2可行解集S中的点x是极点的充要条件是x为基础可行解（简单地说，凸多边形的顶点就是基础可行解）。定理3线性规划的目标函数的最优值，一定可在极点上达到。1－3单纯形方法(Simplexmethod)x1x2O单纯形法的解题思路：⒈用消去法解LP问题解：引入松弛变量将其化为标准形式2.单纯形方法理论推导设A是的矩阵，且R(A)=m（m<n），即A是行满秩的。于是，A中一定存在m列线性无关，这m行m列构成A的一个非奇异子矩阵，称为线性规划的一个基矩阵B（简称为一个基），基矩阵B各列对应的变量称为基变量。为方便起见，不妨设A的前m列线性无关。现将A，B，C，x按一定规则作成分块矩阵。对于标准型的LP问题目标函数约束条件行列式≠0基矩阵右边常数=类似地，为了用原题所给的数据做判优，下面证明：线性规划的有解判别定理：单纯形法的计算步骤单纯形法的思路找出一个初始基本可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）否核心是：变量迭代结束基础最优解是是否可转移无界解是否3.单纯形表S＝目标函数值基变量取值检验数单纯形表的形式单纯形法的计算步骤例1用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400cB基x1x2x3x40x34021100x4301301Z=03400单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ

，选最小的θ对应基变量作为换出变量。 单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。

5）重复3）、4）步直到计算结束为止。单纯形法的计算步骤cj3400θicB基变量x1x2x3x40x34021100x430130134000x34x23x14x2换入列bi/ai2，ai2>04010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以3/5后得到103/5－1/51801－1/5－2/5400－1－1Z=0Z=40Z=70单纯形法的计算步骤 学习要点： 1.线性规划解的概念以及3个基本定理 2.熟练掌握单纯形法的解题思路及求解步骤问题:表1中我们选取了入基,如果选取入基结果又如何呢?路径1路径2结论：1.每一个单纯形表对应一个极点，表一对应黄点；表二对应绿点；表三对应蓝点。2.一般来说，路径不同，迭代次数可能不同。(1)如果单纯形表中的基变量取值皆为正数，称这个基可行解为非退化解。若LP的所有基可行解都是非退化的，则LP经过有限次迭代可达到最优.(2)如果单纯形表中的基变量取值有的为零时，称为LP的退化解，此时称LP是退化的，理论上认为这种线性规划在迭代过程中可能产生循环，从而得不到最优解。为避免循环，常采用1976年R.G.Bland提出Bland法则：a.单纯形表中有若干个检验数时，取下标号小的非基变量入基；b.

用法则选取出基变量时，若比值相同，则选取下标号小的基变量出基。说明：(3)当所有的检验数全部小于等于零时，若有某个非基变量的检验数也是零，则该线性规划有无穷多组解，否则有唯一解。将这个检验数为零的变量入基，得到另一个基础最优解。（P31）(4)当某非基变量的检验数大于零时，但中对应列系数已无正数，则表示无论引入该非基变量多少，基变量不会向违反非负约束的方向发展，从而使目标函数可以无限制地增加，因此存在无界解（P32）说明：例2：解线性规划解：注意到对应A中的列向量恰好构成三阶单位方阵，可以作为第一个可行基。单纯形表C2-11-211-1-2201030201011100230013S’=-507000812-201000-210-3110020-301-3S’=200-700-6最优解为

最优值S=-203.第一个可行解的求法（大M法）以上各例的系数矩阵A中，都存在一个m阶单位阵，因此很容易用单纯行法求解。但是大多数LP问题并不是这样。例3：解：化为标准形填写单纯形表：C3-1-100-M-M0-M-M11311-211000-4120-110-2010001S’=-4M3-6M

M-13M-10-M00C3-1-100-M-M0-M-110113-20100-10100-11-2-2010001S’=-M-11

M-100-M0-3M+1C3-1-100-M-M0-1-112113001-22-50100-11-2-2010001S’=-21

000-1-M+1-M-1C3-1-100-M-M3-1-14191001/3-2/32/3-5/30100-11-20012/3-4/34/3-7/3S’=20

00-1/3-1/3-M+1/3-M+2/3终止表说明：关于大M法的几种情况（1）上表称为终止表。在终止表中，如果基变量里不含有人工变量，或者基变量里含有人工变量，但是人工变量取值为零，则LP一定有最优解；（2）在终止表中，如果基变量里含有人工变量，且人工变量取值大于零，则LP无最优解（P37）1-4WinQSB软件应用第2章线性规划的对偶理论对偶问题的提出原问题与对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析线性规划的对偶理论教学目的与要求：了解对偶问题产生的经济背景，熟练掌握对偶单纯形法和影子价格概念，熟练掌握灵敏度分析方法。重点与难点：重点同上，难点是对偶理论。教学方法：课堂讲授为主并配合课件和WinQSB软件。思考题、讨论题、作业：教材第4章习题参考资料：见绪论学时分配：8学时2－1对偶线性规划问题对偶问题的提出内容一致，而从相反的角度提出的一对问题，称为一对对偶问题。例1：某工厂在计划期内安排生产甲、乙两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。产品在各台设备上需要加工的台时数如下表：ABCD甲2140乙2204产品设备已知A、B、C、D设备的有效台时数分别是12、8、16、12。售出一单位甲产品获利2万元，一单位乙产品获利3万元。如何安排生产使工厂获利最大？从相反的角度提出问题：工厂决策者决定不生产甲、乙两种产品，而对设备的有效台时数进行出租，用租金的方法获得最大利润。应如何考虑？决策者要考虑给每一种设备出租一个台时的定价。在何种价格下，决策者接受出租设备呢？建立LP数学模型显然，当maxZ=minW时，对于决策者来说这两种方案都是最优的。2.对偶线性规划的模型对偶线性规划的特点：一个规划中的每一个约束，对应对偶规划中的一个决策变量；一个规划中目标函数系数恰为对偶规划约束条件右端常数项；一个规划求最小化，而对偶规划求最大化；目标函数求最小化搭配约束；目标函数求最大化搭配约束；两个规划都有非负限制。例1：写出下面原规划的对偶规划定理1如果线性规划中第k个约束条件是等式，则它的对偶规划中的第k个变量无非负限制，反之亦然。例2：写出下面原规划的对偶规划例3：写出下面原规划的对偶规划原规划与对偶规划的对应关系变量约束条件目标函数LP原问题LP对偶问题约束条件变量目标函数练习：写出下列LP问题的对偶问题模型3.对偶线性规划的性质定理2(弱对偶定理)对偶规划(1)，(2)有最优解的充分必要条件是它们同时有可行解。定理3(最优性定理)如果分别是(1)，(2)的可行解，且则分别是(1)，(2)的最优解。定理4如果对偶规划(1)，(2)中，有一个存在最优解，那么另一个也一定有最优解。并且两个规划的目标函数的最优值相等。注意：重点研究两个规划的最优解之间的关系分别化为标准形原问题的最优单纯形表C2100002115/27/23/20015/4-15/21001/4-1/2010-1/43/2S=17/2000-1/4-1/2对偶问题的最优单纯形表b-15-24-500-24-51/41/2-5/410-1/41/415/2011/2-3/2g’=-17/2-15/200-7/2-3/2重要结论：给出一对对偶线性规划，只需解其中一个线性规划得出最优解和目标函数最优值。它的对偶规划的目标函数最优值与原规划的目标函数值相同，而最优解可用原规划最优表中的松弛变量的检验数乘以“-1”得到。例：线性规划问题其对偶问题的最优解为求原问题的最优解。提示：运用对偶模型最优解之间的关系，分析松弛变量取值，决定对应变量的值。4.影子价格(Shadowprice)根据最优性定理，

是原规划约束条件右端项，它代表第i种资源的拥有量，对偶变量表示对一个单位第i种资源的估价。它不是该资源的市场价格，而是根据该资源在生产中做出的贡献而作的估价，称为影子价格。关于影子价格的几个重要结论:（1）影子价格的求法：对偶问题的最优解，即为原问题约束条件右端常数项的影子价格。

具体做法：将原规划最优表中的松弛变量的检验数乘以-1，就得到了对应于原规划约束条件右端常数项（即资源限制量）的影子价格。（2）影子价格是一种边际价格（Boundaryprice）在上式中，对求偏导数，得这说明，的值相当于在给定的生产条件下，每增加一个单位时，目标函数S的增加量，即总收入的变化率（总收入增加一个影子价格值）。（3）影子价格是一种机会成本（Opportunitycost）在纯市场经济条件下，当某种资源的市场价格低于影子价格时，可以买进这种资源扩大生产；相反当市场价格高于影子价格，可卖出这种资源获取更大的利润。注意：由于影子价格可为决策者提供决策依据，因此各种资源的影子价格应当保密。（4）影子价格大于零时，对应的松弛变量为非基变量，其取值为零，则该约束条件为等式，这说明此种资源已被充分利用。影子价格等于零时，对应的松弛变量为基变量，一般地说，其取值大于零，则该约束条件不等式是成立的（“<”关系）。这说明此资源是过剩资源，没有被充分利用。影子价格等于零，不是说该资源没有价格，而是表明该资源是过剩资源，再买进此资源不会增加总收入。检验数的含义：4.对偶单纯形法定义1：将线性规划模型转化为标准形式后，对某一确定的基矩阵B，令非基变量等于零，根据系统约束条件解出基变量，则这组解称为基矩阵B的基解。满足非负约束条件的基解，称为基可行解。试找出下列线性规划模型的基解，并判断是否可行？是否最优？定义2：设是线性规划的一组基变量，其对应的基矩阵是B，对应的基解为，如果这组基对应的检验数全部小于等于零，即，则称这组基为该线性规划的一组正则基。为正则解。线性规划的对偶单纯形法是从第一个正则解开始迭代的。对偶单纯形法的迭代步骤:（1）从一个正则解开始，列出对偶单纯形表；（2）如基变量的取值全部大于等于零，则线性规划已取得最优解，计算结束；否则转（3）；（3）在基变量中，挑选取负值中最小的一个，作为出基变量（若最小负值相同，可由Bland法则确定）；（4）在出基变量行中，如果非基变量的约束系数全部非负，则原问题不存在可行解；否则转（5）；（5）在出基变量行中，如果有些非基变量的约束系数为负，则分别计算这些变量的检验数与出基变量行中负系数的比值，比值最小者对应的非基变量为入基变量（若比值相同，由Bland法则确定）；（6）出、入基交叉点上的元素为主元素，用方框框起来，将其变为1，用矩阵初等行变换将其所在列的其余元素变为0，得到一张新表，转（2）。对偶单纯形法的迭代步骤:例1：利用对偶单纯形法解下边的线性规划解：首先将LP化为标准形再变形为对偶单纯形表C-2-1000000-3-6-2-3-1100-4-3010-1-2001-S=0-2-10000-10-122-5/301-1/304/310-1/305/300-2/31-S=-2-2/300-1/30对偶单纯形表C-2-10000-10-122-5/301-1/304/310-1/305/300-2/31-S=-2-2-1000-2-103/56/5110-3/51/50014/5-3/50001-11-S=-12/500-2/5-1/505.灵敏度分析灵敏度分析的主要内容1）目标函数系数变化的灵敏度分析；2）约束条件右端常数项变化的灵敏度分析；3）系统约束系数的灵敏度分析；4）增加一个新决策变量的灵敏度分析；5）增加一个新约束条件的灵敏度分析例：某工厂用甲、乙两种原料生产A,B,C,D四种产品，每种产品消耗的原料定额如下表，现有甲原料18吨，乙原料3吨。而每单位产品A,B,C,D的利润分别是9万元、8万元、50万元和19万元。问如何组织生产才能使总利润最大。ABCD甲乙321040021/2单位消耗最优表为C9850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3进行灵敏度分析:1）目标函数系数变化的灵敏度分析C9+

850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3（1）是非基变量的系数1cD1cD（2）是基变量的系数C9850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3+检验数解不等式组即当C产品的利润在（47.5,52）之间时，最优解不变。有关灵敏度分析的例题综合例题：考虑下列线性规划求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。目标函数系数c3变为1C2-140004005/47/411/43/41/211/4001/41/20-1/4101/4-3/20-1/401Z=5-1-30-100最优单纯形表：c3的系数已超出允许变化范围，在上表中替换相应的数，用单纯形法求解。115/4-3/2带入后的单纯形表：目标函数系数c2变为2最优单纯形表：因为c2未超过允许值，所以最优解保持不变。C2-140004005/47/411/43/41/211/4001/41/20-1/4101/4-3/20-1/401Z=5-1-30-100简便方法（对于目标函数极大化的情况）：（1）非基变量的目标函数系数变化时，利用该非基变量的原检验数加系数变化的量，并列为小于等于零的不等式。（2）基变量的目标函数系数变化时，会影响所有非基变量的检验数，以原检验数加上系数变化的基变量对应的消耗系数的相反数与系数变化量的乘积，并列为小于等于零的不等式组。2）约束条件右端常数项变化的灵敏度分析最优单纯形表C9850190019502124/3012/3-10/3-1/2-1/310-1/64/3S=88-4-2/300-13/3-10/3初始单纯形表C985019000018332104100021/201S’=098501900最优基B可行基最优基例如，第一种资源限制量发生变化即当时，最优基不变。简便方法：基变量的取值加上该资源的松弛变量所在列的系数为的系数，并列为大于等于零的不等式。有关灵敏度分析的例题综合例题：考虑下列线性规划求出最优解后，当右边常数项变化时，求出变化后的最优解。2042最优单纯形表：基本解不可行，最优基已变化，用对偶单纯形法求最优解。带入参数后的对偶单纯形表：C2-140004005/47/411/43/41/211/4001/41/20-1/4101/4-3/20-1/401Z=5-1-30-100-20C2-140004005-1-33/41/211/4001/41/20-1/4101/4-3/20-1/401Z=20-18-30-10040-14-225/6011/601/31/300-1/311/3-1/6101/60-2/3Z=14-3/200-1/20-240-136110101/21/2-1001-3-101001/2-1/2Z=11-2000-3/2-5/2当为基变量的系数，其变化一定影响最优解当为非基变量的系数，其变化仅影响该非基变量的检验数。分析不改变最优解基变量及其取值情况下，求非基变量系数的变动范围处理方法：3）的灵敏度分析98501900C-4-2/300-13/3-10/3S=8824/3012/3-10/3-1/2-1/310-1/64/3211950分析的灵敏度范围非基变量对应的消耗系数的灵敏度范围简便方法：令该非基变量对应的检验数加上消耗系数资源对应的松弛变量的检验数与变化值的乘积小于等于零，求得灵敏度区间例：某工厂用甲、乙两种原料生产A,B,C,D四种产品，每种产品