1.线性规划及单纯形法1ppt课件.ppt

第一章第一章线性规划及其单纯形法线性规划及其单纯形法第一章第一章 线性规划及单纯形法线性规划及单纯形法 第一节第一节 线性规划问题及数学模型线性规划问题及数学模型 Linear Programming , LP1939年年 苏苏 康托洛维奇和康托洛维奇和1941年年 美美 Hichook 在生产组织管理和制定交通运输方案方面研究和应用线性规划，求解方法在生产组织管理和制定交通运输方案方面研究和应用线性规划，求解方法——解乘数法解乘数法 1947年年 G. B. Dantzig 单纯形法单纯形法1979年年 苏苏 哈奇安多项式算法〔椭球算法）哈奇安多项式算法〔椭球算法）1984年年 Karmarkar算法算法多项式时间算法每次迭代不是从一个顶点出发求改进的顶点，而是使迭代点保持在某个单纯形多项式时间算法每次迭代不是从一个顶点出发求改进的顶点，而是使迭代点保持在某个单纯形的内部，因此是一种内点算法的内部，因此是一种内点算法 LPLP是数学规划的一个重要分支，数学规划着重解决资源的是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：优化配置，一般可以表达成以下两个问题中的一个：（（1 1〕当资源给定时，要求完成的任务最多；〕当资源给定时，要求完成的任务最多；（（2 2〕当任务给定时，要求为完成任务所消耗的资源最少。

〕当任务给定时，要求为完成任务所消耗的资源最少 若上述问题的目标若上述问题的目标﹑﹑约束都能表达成变量的线性关系，约束都能表达成变量的线性关系，则这类优化问题称则这类优化问题称LPLP问题LPLP是一种解决性约束条件下追求最大或最小的线性目是一种解决性约束条件下追求最大或最小的线性目标函数的方法标函数的方法一、实例一、实例例例1 生产计划问题生产计划问题 (书书P8，典型示例，典型示例)Step 1:Step 1:明确问题，设定决策变量明确问题，设定决策变量设设I I、、IIII两种产品的产量分别为两种产品的产量分别为x1, x2 x1, x2 Step 2: Step 2: 确定约束条件确定约束条件 3 2 利润利润 12公斤公斤 4 0 原料原料B 16公斤公斤 0 4 原料原料A 8台时台时 2 1 设设 备备资源限量资源限量 II I 产品产品阐明：阐明：OBJ OBJ 表示表示Objective;Objective; s.t. s.t. 表示表示Subject to Subject to Step 3: Step 3: 给出目标函数给出目标函数Step 4: Step 4: 整理数学模型整理数学模型例例2 污水处理问题污水处理问题 (书书P9)设设x1﹑x2x1﹑x2为为工工厂厂1﹑2 1﹑2 的的日日污污水水处处理理量量。

建建立立该该问问题题的的数数学学模模型型为：为： 500万m3200万m31.4万m3，800元/万m3 o工厂2 2万m3 ，1000元/万m3 o工厂1二、总结二、总结• 目标函数用决策变量的线性函数来表示按问题目标函数用决策变量的线性函数来表示按问题的不同，要求目标函数实现最大化和最小化的不同，要求目标函数实现最大化和最小化线性规划问题〔线性规划问题〔LP问题〕的共同特征：问题〕的共同特征：• 每一个问题变量都用一组决策变量〔每一个问题变量都用一组决策变量〔x1, x2, …, xn〕表〕表示某一方案，这组决策变量的值代表一个具体方案，这示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的且在某范围内连续取值些变量是非负的且在某范围内连续取值• 存在一定的约束条件，这些约束条件可以用一组存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示线性等式或线性不等式来表示三、线性规划问题的一般形式三、线性规划问题的一般形式四、两变量线性规划问题的图解法四、两变量线性规划问题的图解法1.线性不等式的几何意义线性不等式的几何意义— 半平面半平面•作出作出LP问题的可行域问题的可行域•作出目标函数的等值线作出目标函数的等值线•移动等值线到可行域边界移动等值线到可行域边界得到最优点得到最优点2.图解法步骤图解法步骤例例1 （典型示例）：（典型示例）：4x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0) Q2(4,2)Z=2x1+3x2 做目标函数做目标函数2x1+3x2的等值线，与阴影部分的的等值线，与阴影部分的边界相交于边界相交于Q(4,2)点，表明最优生产计划为：生产点，表明最优生产计划为：生产I产品产品4件，生产件，生产II产品产品2件。

件Q1(4,0)Q3(2,3)Q5(4,3)图解法意义不大，但可直观揭示有关概念图解法意义不大，但可直观揭示有关概念3.LP解的类型解的类型有有4类：类：（（1〕唯一最优解〕唯一最优解 如例如例1的的Q2点2〕无穷多最优解〔多重解）〕无穷多最优解〔多重解）（（3〕无界解〕无界解（（4〕无可行解〕无可行解0 4 8 12 x1 9 6 3 ①①③③②②可行域可行域Z=364, 6此线段上的点均为最优点x2当例当例1 的目标函数变为的目标函数变为 max Z =2x1+4x2 多重解示例多重解示例 8, 3x2可行域不闭合②②Z增大方向①①x1无界解示例无界解示例 产生原因：缺少约束条件产生原因：缺少约束条件 注注 意：可行域不闭合不一定就会出现无界意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质若目解，这要看目标函数的性质若目标函数是标函数是min，则有最优解无论，则有最优解。

无论有无最优解，一定有可行解有无最优解，一定有可行解 无可行解示例无可行解示例 ①①③③④④无公共区域(可行域)产生原因： 有相互矛盾的约束条件②②x2x14. 图解法的作用图解法的作用LPLP问题问题有可行解有可行解有最优解有最优解唯一解唯一解无穷多解无穷多解无最优解〔可行域为无界）无最优解〔可行域为无界）无可行解〔无解）无可行解〔无解）（（1〕规律：〕规律： 揭示了线性规划问题有关规律和结论揭示了线性规划问题有关规律和结论2〕结论：若〕结论：若LP问题有最优解，则要么最优解唯一〔对问题有最优解，则要么最优解唯一〔对应其中一个顶点），要么有无穷多最优解〔对应其中一个顶点），要么有无穷多最优解〔对应其中两个顶点连线上的所有点）应其中两个顶点连线上的所有点）五、五、 线性规划问题的标准型线性规划问题的标准型1. 标准型的构成要素标准型的构成要素（（1〕目标函数：〕目标函数：max（（2〕约束条件：等式〕约束条件：等式（（3〕变量约束：非负〕变量约束：非负 xj³0（（4〕资源限量：非负〕资源限量：非负bi ³02. 标准型的表示方法标准型的表示方法（（1〕解析式〕解析式简写的解析式简写的解析式亦可写成：亦可写成：其中：其中：（（2〕矩阵式〕矩阵式X—决策变量列向量。

决策变量列向量 b—约束条件右端常数〔资源〕列向量约束条件右端常数〔资源〕列向量C—目标函数价值系数行向量目标函数价值系数行向量 Am´n—约束条件左端系数矩阵约束条件左端系数矩阵（（3〕向量和矩阵符号式〕向量和矩阵符号式3. 非标准型的标准化非标准型的标准化（（1〕最小转换成最大〕最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*（（2〕不等式约束条件转换成等式约束条件〕不等式约束条件转换成等式约束条件（（3〕变量约束转换〕变量约束转换（（4〕把〕把bi<0转换成转换成bi>0例例1可化为可化为例例2 化标准型化标准型六、标准型六、标准型LPLP问题的解问题的解1. 基本概念基本概念4x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0) Q2(4,2)Q1(4,0)Q3(2,3)Q5(4,3)Q7 基解基解x2，，x3x5=12x4=－－16x1=8Q6 基解基解x1，，x3x5=－－4x4=16x2=4Q5 基解基解x4，，x5x3=－－2x2=3x1=4Q4 基可行解基可行解x1，，x5x4=16x3=2x2=3Q3 基可行解基可行解x3，，x5x4=8x2=3x1=2Q2 基可行解基可行解 最优解最优解x3，，x4x5=5x2=2x1=4Q1 基可行解基可行解x2，，x4x5=12x3=4x1=4K 可行解可行解x1=2, x2=2, x3=2, x4=8, x5=4O 基可行解基可行解x1，，x2x5=12x4=16x3=8图中的点及对应图中的点及对应的解的解非非 基基 变变 量量基变量基变量K•2. 可行解、基解和基可行解举例可行解、基解和基可行解举例 典型示例标准化后有典型示例标准化后有3个约束条件、个约束条件、5个决策变量，个决策变量，基的最大个数可达基的最大个数可达C53=10个，但实际上只有个，但实际上只有8个。

个约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解3. LP标准型问题解的关系标准型问题解的关系4. LP标准型问题解的结论标准型问题解的结论 根据根据LP的图解法及解的基本概念可知：的图解法及解的基本概念可知：基解对应约束条件的交点；基解对应约束条件的交点；基可行解对应可行域的顶点基可行解对应可行域的顶点某个基可行解一定是最优解，即一定在可行域的顶点上得到最优某个基可行解一定是最优解，即一定在可行域的顶点上得到最优解第二节第二节 单纯形法单纯形法 Simplex Method Simplex Method • 由线性代数知，对LP标准型问题，理论上可以求出所有基解〔枚举法），再通过观察找出其中基可行解，进而找出最优解但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法 • 为加快计算速度，算法必须具有两个功能，一是每得到一个基可行解，就能检验是否已经最优，若是，停顿。

二是若不是最优，要保证下一步得到的基可行解不劣于当前解基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法 一、基本思想一、基本思想化化LP问题为标准型，问题为标准型，确定一个初始基可行解确定一个初始基可行解检验解的检验解的最优性最优性终了终了Y旋转运算〔枢轴运算）旋转运算〔枢轴运算）确定另一个基可行解确定另一个基可行解N基本思路：化基本思路：化LP问题为标准型，从可行域问题为标准型，从可行域的某个基可行解〔一个顶点〕开场，转换到另一的某个基可行解〔一个顶点〕开场，转换到另一个基可行解〔另一个顶点），并使目标函数值得个基可行解〔另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解到改善，如此反复，从而求得问题的最优解其实质是逐步迭代〔逼近〕法其实质是逐步迭代〔逼近〕法二、基本原理举例二、基本原理举例1. 初始基可行解的确定初始基可行解的确定要得到一个初始基可行解，必须找到一个初始可行基要得到一个初始基可行解，必须找到一个初始可行基由于典型示例标准化后，由于典型示例标准化后，x3、、x4、、x5的系数列向量构成单的系数列向量构成单位矩阵，该矩阵位矩阵，该矩阵B0是一个基，并且是一个可行基〔可以证是一个基，并且是一个可行基〔可以证明，标准化后的单位矩阵一定是可行基）。

明，标准化后的单位矩阵一定是可行基） 令非基变量令非基变量x1＝＝0、、x2 ＝＝0，得到基可行解及相应的目标，得到基可行解及相应的目标函数值，函数值，X(0) ＝＝(0,0,8,16,12)T，， Z(0) ＝＝0结论：结论： （（1〕在标准化的〕在标准化的LP问题的约束系数矩阵中，只要存在单问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；位矩阵，就可求得初始基可行解； （（2〕基变量确定后，目标函数和基变量均可表示成非基〕基变量确定后，目标函数和基变量均可表示成非基变量的代数和形式〔如变量的代数和形式〔如(6)和和(5)），从而便于求出基可行解），从而便于求出基可行解及相应的目标函数值及相应的目标函数值2. 最优性检验最优性检验 考察变换后的目标函数考察变换后的目标函数(6)式，非基变量式，非基变量x1、、x2的系数都的系数都为正数，若让为正数，若让x1、、x2取正值，则目标函数值会增大因此，取正值，则目标函数值会增大因此，应将非基变量应将非基变量x1、、x2变换成基变量变换成基变量结论：结论： 在非基变量的代数和形式表示的目标函数中，若非基变在非基变量的代数和形式表示的目标函数中，若非基变量的系数〔称为检验数〕为正，则目标函数值还有增加的可量的系数〔称为检验数〕为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。

能，表明当前的基可行解不是最优解3. 确定新的基可行解〔基变换）确定新的基可行解〔基变换） 单纯形法在寻找新的可行基时，是以当前的可行基为基础的，单纯形法在寻找新的可行基时，是以当前的可行基为基础的，即把当前的可行基中某一列用非基向量替换，从而形成新的可即把当前的可行基中某一列用非基向量替换，从而形成新的可行基确定换入变量：一般选择正系数最大的非基变量为换入变量确定换入变量：一般选择正系数最大的非基变量为换入变量 本例为非基变量本例为非基变量x2确定换出变量：其依据是〔确定换出变量：其依据是〔a〕保证换出的变量取值为〕保证换出的变量取值为0，变，变 成非基量；（成非基量；（b〕其它的变量取值为非负〕其它的变量取值为非负 当确定当确定x2为换入变量后，为换入变量后， x1还是非基变量，故还是非基变量，故 x1＝＝0现在要保证在要保证x3、、x4、、x5³0，即，即(5)当当 x2 ＝＝min〔〔8/2，，—，，12/4）） =3 （最小比值规则）（最小比值规则）可保证可保证 x5 =0则则x5为换出变量。

为换出变量新的基变量为新的基变量为x3、、x4、、x2 ，新的可行基为，新的可行基为B1＝＝(P3, P4 , P2)4. 旋转迭代旋转迭代 基变量确定后，旋转迭代就是把目标函数和基变量均表基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量示成非基变量x1、、x5的代数和形式可用高斯消去法实现的代数和形式可用高斯消去法实现 令非基变量令非基变量x1＝＝0、、x5 ＝＝0，得到新的基可行解及相应的，得到新的基可行解及相应的目标函数值，目标函数值，X(1) ＝＝(0,3,2,16,0)T，， Z(1) ＝＝9返回至第二返回至第二步，直至求出最优解步，直至求出最优解 将上述方程组求解过程，用列表形式表达，即为线性规划将上述方程组求解过程，用列表形式表达，即为线性规划单纯形表单纯形表三、最优性检验及解的判别三、最优性检验及解的判别1. 检验数公式检验数公式 课堂作业课堂作业1：： 请给出公式〔请给出公式〔2〕的推导过程〕的推导过程2. 最优性检验与解的判别最优性检验与解的判别 设设X(0)=(b¢1, b¢2, …,b¢m,0, …,0)T为对应于基为对应于基B的一个基可行的一个基可行解。

解对于最大化问题，最优性检验与解的判别如下：对于最大化问题，最优性检验与解的判别如下：（（1〕唯一最优解〕唯一最优解 对于一切对于一切 j=m+1, …,n，有，有sj<0，则，则X(0)为唯一最优解为唯一最优解2〕无穷多最优解〕无穷多最优解 对于一切对于一切 j=m+1, …,n，有，有sj£0，且至少有一个，且至少有一个sm+k=0，则该，则该LP问题有无穷多最优解，问题有无穷多最优解，X(0)为其中之一为其中之一3〕无界解〕无界解 在在 j=m+1, …,n中，至少有一个中，至少有一个sm+k>0，且对，且对i=1, …,m，有，有a¢i,m+k£0，则该，则该LP问题具有无界解问题具有无界解四、基变换四、基变换1. 换入变量的确定换入变量的确定2. 换出变量的确定换出变量的确定则第则第l个约束方程对应的基变量个约束方程对应的基变量xl为换出变量为换出变量五、迭代运算五、迭代运算第三节第三节 单纯型法的步骤单纯型法的步骤1. 化化LP问题为标准型问题为标准型,建立初始单纯型表建立初始单纯型表;一、步骤一、步骤化为标准型化为标准型二、实例二、实例单纯型表算法单纯型表算法 X(0) ＝＝(0,0,8,16,12)T O点点以以[1]为主元素进行旋转运算，为主元素进行旋转运算，x1为换入变量，为换入变量， x3为换出变为换出变量量 0 qi 3 0 0 x5 x2 x3 x40 x4 x3XB b sj 0 x1CB 2 cj x1 cj x2 x3 x4 x5 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 2 3 0 0 0 b816 12 XB x3 x4 x5 CB CB 0 0 0以以[4]为主元素进行旋转运算，为主元素进行旋转运算，x2为换入变量，为换入变量，x5为换出变为换出变量量 sj 2 3 0 0 0 qi 8/2 — 12/4[4] x2 3主元列主元列主元行主元行 0 0 0 1/43 1 4 0 1 016 0 0 1 1 0 -1/22X(1) ＝＝(0,3,2,16,0)T Q4点点 2 0 0 -3/4 016/4 2/1 — [1]此时达到最优解。

此时达到最优解X*=(4,2), max Z=14 0 qi 3 0 0 x5 x2 x3 x40 x4 x23 XB b sj x1CB 2 cj 0 qi 3 0 0 x5 x2 x3 x4x23 x1XB b sj 2 x1CB 2 cj 0 0 0 1/43 10 -2 0 1/4 0 x1 2 0 1 1 0 -1/22 [2] 0-4 128 08/2 12 — x50 0 -2 1/2 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0X(3) ＝＝(4,2,0,0,4)T Q2点点X(2) ＝＝(2,3,0,8,0)T Q3点点以以[2]为主元素进行旋转运算，为主元素进行旋转运算，x5为换入变量，为换入变量，x4为换出变为换出变量量一、最小化问题最优解判别一、最小化问题最优解判别第四节第四节 LP问题的进一步讨论问题的进一步讨论 前面讨论的前面讨论的LP问题都是以最大化目标函数作为标准型的，问题都是以最大化目标函数作为标准型的，但也有用最小化目标函数作为但也有用最小化目标函数作为LP问题标准型的构成要素的情问题标准型的构成要素的情况。

二者的区别如下：况二者的区别如下：按最小比值规则按最小比值规则 max Z=CX AX=b，，X³0 min Z=CX AX=b，，X³0£0£0³0 ³0 min{sj| sj <0}max{sj| sj >0}换入变量换入变量xk换出变量换出变量xl最优解的最优解的sj标准型标准型 比较条目比较条目二、人工变量法二、人工变量法化为标准型化为标准型 化标准型时，若找不到单位矩阵，可人为添加非负变化标准型时，若找不到单位矩阵，可人为添加非负变量〔人工变量〕凑成单位矩阵量〔人工变量〕凑成单位矩阵 因人工变量是虚拟的变量，无任何物理意义，它们的因人工变量是虚拟的变量，无任何物理意义，它们的取值最终必须为零，才能保证约束方程不发生变化取值最终必须为零，才能保证约束方程不发生变化 为此，必须把人工变量从基变量中替换出去而变成非为此，必须把人工变量从基变量中替换出去而变成非基变量，则基变量，则LP问题有解；若最优解中含有人工变量，则问题有解；若最优解中含有人工变量，则LP问题无可行解这是问题无可行解这是LP问题无解的判别条件。

问题无解的判别条件加入松弛变量加入松弛变量x4;剩余变量剩余变量x5;人工人工变量变量x6,x7（（1）） 基本思路基本思路（（2〕目标函数的处理〕目标函数的处理（（3）） 计算计算1. 大大M法法(M为任意大的正数为任意大的正数)3M-10M001-M-1-100010-21x311-21-100101x6M--10010-2310x4000M01-3M1-M-3+6M1100010-21x7M3/201-1021-43x6M1100011-2111x40x7x6x5x4x3x2x1bXBCBMM0011-3cj结果得结果得: X*=(4,1,9,0,0) T Z*=-2M-2/3M-1/31/31/3000-7/34/3-4/32/31009x31-21-100101x21-5/32/3-2/31/30014x1-3M+1M-11000-1-100010-21x31--21-100101x214-52-2100312x40x7x6x5x4x3x2x1bXBCBMM0011-3cj（接上表）（接上表）将将LP问题分成两个阶段来考虑问题分成两个阶段来考虑 第第I 阶段阶段: 不考虑原问题是否存在可行解，给原不考虑原问题是否存在可行解，给原LP问题问题加入人工变量，并构造仅含人工变量的目标函数和要求最加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯型法求解，若得小化；然后用单纯型法求解，若得W=0，则进行第二阶段，则进行第二阶段计算，否则无可行解。

计算，否则无可行解 第第II 阶段：将第一阶段得到的最终表除去人工变量，将阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初目标函数行的系数换为原问题的系数，作为第二阶段的初始表2. 两阶段法两阶段法加入松弛变量加入松弛变量x4;剩余变量剩余变量x5;人工人工变量变量x6,x7用单纯形法求解第一阶段的结果得：用单纯形法求解第一阶段的结果得：1100000-000010-21x30--21-100101x204-52-2100312x4030100-10-100010-21x301-21-100101x61--10010-2310x400010-3-161100010-21x713/201-1021-43x611100011-2111x40x7x6x5x4x3x2x1bXBCB1100000cj此时，达到第一阶段的最优解，此时，达到第一阶段的最优解，W=01/31/3000-4/32/31009x31-100101x21-2/31/30014x1-31000-1-0010-21x31--100101x214-2100312x40x5x4x3x2x1bXBCB0011-3cj由于人工变量由于人工变量x6 =x7=0,所以〔所以〔0,1,1,12,0〕〕T是该线性规划问题的基可行解。

于是转入第二阶段运算：是该线性规划问题的基可行解于是转入第二阶段运算：此时达到该此时达到该LP问题的最优解：问题的最优解： X*=(4,1,9,0,0) T; 目标函数值目标函数值Z*=-2三、单纯型法中存在的问题三、单纯型法中存在的问题1. 存在两个以上的最大正检验数选择存在两个以上的最大正检验数选择任何变量〔对应最大正检验数〕作为换任何变量〔对应最大正检验数〕作为换入变量2. 最小比值相同最小比值相同LP问题出现退化现象，即基变量取值为问题出现退化现象，即基变量取值为0 000-61/2-203/4010001001x700103-1/2-121/20x600019-1-81/40x50x7x6x5x4x3x2x1bXBCB 3/4 -20 1/2 -6 0 0 0 cj00-3217/240010001001x70010-153/2400x6000436-4-3210x13/4x7x6x5x4x3x2x1bXBCB 3/4 -20 1/2 -6 0 0 0 cj选取选取x1为换入变量；按为换入变量；按Bland算法，算法，选取下标最小的选取下标最小的x5为换出变量，得下表：为换出变量，得下表：此时换出变量为此时换出变量为x1，换入变量为，换入变量为x4，迭代后，迭代后目标函数值不变，继而出现了循环现象，达目标函数值不变，继而出现了循环现象，达不到最优解。

不到最优解解决退化的方法有：解决退化的方法有：“摄动法摄动法”、、“辞典序法辞典序法”、、 Bland规规则等则等1974年年Bland提出提出Bland算法规则：算法规则：3. 最小比值原则失效最小比值原则失效-30011-12cj-Zj101-34x23110-26x30x4x3x2x1bXBCB0032cj经过一次迭代后可得右表经过一次迭代后可得右表4. 在最优表中出现某在最优表中出现某非基变量检验数为非基变量检验数为01/3-2/30014x13-10000-36cj-Zj01/20106x24-1/32/31004x30x5x4x3x2x1bXBCB-10000-36cj-Zj001018x131/40-3/4103x24-1/213/2006x40000430cj-Zj结论：若线性规划问题存在某非基变量检验数为结论：若线性规划问题存在某非基变量检验数为0,而其对而其对应列向量应列向量Pk≤0,仍可判断线性规划问题有无穷多最优解仍可判断线性规划问题有无穷多最优解式中的式中的X* 是否能全部由单纯形法求得？是否能全部由单纯形法求得？ 课堂作业课堂作业2 第五节第五节 应用举例应用举例应用应用1：下料问题〔书：下料问题〔书P38 例例10）） 现要做现要做100套钢架，每套需套钢架，每套需2.9米、米、2.1米米和和1.5米的圆钢各一根。

已知原料长米的圆钢各一根已知原料长7.4米，米，问如何下料，使用的原料最少〔余料最少或问如何下料，使用的原料最少〔余料最少或根数最少）？根数最少）？分析：分析： 最简单的做法是：每根最简单的做法是：每根7.4米长的原材料各截取三种规格米长的原材料各截取三种规格的元钢一根，则料头为的元钢一根，则料头为0.9米，米，100套则浪费材料套则浪费材料90米关键是米关键是要设计套裁方案，不能有遗漏要设计套裁方案，不能有遗漏解：设解：设 x1, x2 , x3, x4 , x5分别代表五种不同的原料用量方案分别代表五种不同的原料用量方案0.86.6310x50.37.1021x40.27.2220x30.17.3102x207.4301x1余料余料合计合计1.5米米2.1米米2.9米米方案方案余料最少的余料最少的LP模型：模型：根数最少的根数最少的LP模型：模型：料头最省料头最省根数最少根数最少＝＝解解1: x1=30, x2=10, x4=50; 料头料头Z=16, 根数根数90 可以做可以做100套钢架，无圆钢剩余套钢架，无圆钢剩余与解与解1相同相同≥≥解解2: x1=100, x3=50; 料头料头Z=10, 根数根数150。

可以做可以做100套钢架套钢架, 但余但余1.5m圆钢圆钢300根与解与解1相同相同应用应用2：配料问题〔书：配料问题〔书P38 例例11）） 某工厂要用三种原材料某工厂要用三种原材料C、、P、、H混合调混合调配出三种不同规格的产品配出三种不同规格的产品A、、B、、D已知产品的规格要求、单价和原材料的供应量、单品的规格要求、单价和原材料的供应量、单价该厂应如何安排生产使利润最大？价该厂应如何安排生产使利润最大？25不限不限D35原材料原材料C不少于不少于25%原材料原材料P不超过不超过50%B50原材料原材料C不少于不少于50%原材料原材料P不超过不超过25%A单价单价(元元/kg））规格要求规格要求产品名称产品名称3560H25100P65100C单价单价(元元/kg)每天最多供每天最多供应量应量(kg)原材料名称原材料名称解：根据题意，可将问题简化成如下表格形式：解：根据题意，可将问题简化成如下表格形式：60100100原料限量原料限量(kg））DBA35—/ x33—/ x23—/ x13H3525£50%/ x22£50%/ x22—/ x32³25%/x21³25%/x21—/ x3150产品单价产品单价(元元/kg））25£25%/ x12£25%/ x12P65³50%/x11³50%/x11C单价单价(元元/kg））规格要求规格要求/决策变量决策变量产品名称产品名称原料原料 用单纯型法计算得结果：每天只生产用单纯型法计算得结果：每天只生产A产品产品200kg。

分别需要原料：分别需要原料：C为为100kg；；P为为50kg；；H为为50kg 总利润收入总利润收入Z=500元元/天天.例例1：某企业拟用：某企业拟用m种资源种资源(i=1,2,…,m)生产生产n种产品种产品(j=1,2,…,n) 已知第i种资源的数种资源的数量为量为bi，其单价为，其单价为Pi；第；第j种单位产品的产值种单位产品的产值为为Vj，消耗第，消耗第i种资源的数量为种资源的数量为aij，合同量，合同量为为ej，最高需求为，最高需求为dj问企业应如何拟定生问企业应如何拟定生产计划？产计划？解：根据题意，设解：根据题意，设xj (j=1,2,…,n)为第为第j种产品的生产量种产品的生产量应用应用3：生产计划问题：生产计划问题例例2 （书（书P41 例例12））市场要求：市场要求： 1) 产品数量和品种；产品数量和品种； 2) 产品交货期不同产品交货期不同生产要求：生产要求： 1) 设备均衡且满负荷生产；设备均衡且满负荷生产； 2) 生产技术准备需要时间生产技术准备需要时间 以一月份内各种设备的生产能力总和为分母以一月份内各种设备的生产能力总和为分母,生产产品生产产品所需要的各类设备的总台时数为分子所需要的各类设备的总台时数为分子,可计算出一月份的平可计算出一月份的平均设备利用系数均设备利用系数Z,将将Z作为目标函数作为目标函数,可得下面的模型可得下面的模型:先考虑一月份的线性规划模型先考虑一月份的线性规划模型: 考虑二月份线性规划模型时考虑二月份线性规划模型时:(1)从从全年计划中减去一月份已生产的数量全年计划中减去一月份已生产的数量;(2)对批量小的产品对批量小的产品,如一月份已经安排如一月份已经安排较大产量的较大产量的,二月份将剩余部分安排生产二月份将剩余部分安排生产;(3)保证第保证第4种产品在月底前交货。

种产品在月底前交货这样这样,我们可以依次对我们可以依次对12个月列出线性规划模型个月列出线性规划模型并求解并求解,再根据具体情况再根据具体情况对计算结果进行必要调对计算结果进行必要调整应用应用4：连续投资问题〔书：连续投资问题〔书P42 例例13））x5Dx4Dx3Dx2Dx1DDx2CCx3BBx4Ax3Ax2Ax1AA54321 某部门在今后某部门在今后5年内连续给以下项目投资：年内连续给以下项目投资：项目项目A，第一年至第四年每年年初投资，次年末回收本利，第一年至第四年每年年初投资，次年末回收本利 115%；；项目项目B，第三年初投资，第五年末回收本利，第三年初投资，第五年末回收本利 125%，最大投资额不，最大投资额不超过超过4万元；万元； 项目项目C，第二年初投资，第五年末回收本利，第二年初投资，第五年末回收本利 140%，最大投资额不，最大投资额不超过超过3万元；万元； 项目项目D，五年内每年初可购买公债，当年末归还，并加利息，五年内每年初可购买公债，当年末归还，并加利息6% 该部门现有资金该部门现有资金 10万元，问该如何确定投资方案，使第五年末万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？拥有的资金本利和最大？应用应用5：食谱问题：食谱问题 有有n种食品种食品(j=1,2,…,n)，每种食品中含有，每种食品中含有m种营养成分种营养成分(i=1,2,…,m) 。

已知第已知第j种食品单价为种食品单价为cj，每天最大供应量为，每天最大供应量为dj，每单位第，每单位第j种食品中含第种食品中含第i种营养成分的数量为种营养成分的数量为aij设某种生物每天对第生物每天对第i种营养成分的需求量至少为种营养成分的需求量至少为bi，而每天的进食数，而每天的进食数量限定在量限定在[h1, h2]之间问该生物的食谱，使总成本为最小？之间问该生物的食谱，使总成本为最小？解：根据题意，设解：根据题意，设xj (j=1,2,…,n)表示每天食用第表示每天食用第j种食种食品的数量品的数量应用应用6：产品配套问题：产品配套问题 某厂生产一种产品，由两个某厂生产一种产品，由两个B1 零件和三零件和三个个B2零件配置组装而成该厂有零件配置组装而成该厂有A1、、A2、、A3三种机床可加工上述两种零件，每种机床三种机床可加工上述两种零件，每种机床的台数以及每台机床每个工作日全部用于加的台数以及每台机床每个工作日全部用于加工某一种零件的最大产量〔即生产率：件工某一种零件的最大产量〔即生产率：件/日〕见下表试求该产品产量最大的生产方日〕见下表试求该产品产量最大的生产方案。

案机床生产率〔件机床生产率〔件/日）日）机床数量机床数量机床类型机床类型零件零件B2零件零件B118104A3354520302A23A1难点：难点：1) 同一台机床加工零件同一台机床加工零件B1和和 B2的时间分配；的时间分配；2)零件零件B1和和 B2的配套问题，的配套问题，2:3构成一件产品构成一件产品解：解：（（1〕决策变量〕决策变量 根据题意，设每台根据题意，设每台Ai (i=1,2,3)机床每个工作日加工机床每个工作日加工Bj(j=1,2)零件的时间为零件的时间为xij(工作日工作日)；；Z为零件为零件B1和和 B2按按2:3比例配套的产比例配套的产品数量〔套品数量〔套/日）2〕约束条件〕约束条件 工时约束：工时约束： 机床机床A1：：x11+ x12=1 机床机床A2：：x21+ x22=1 机床机床A3：：x31+ x32=1 配套约束：配套约束： 零件零件B1的产量：的产量：3´20 x11＋＋2 ´35 x21 ＋＋4 ´10 x31 零件零件B2的产量：的产量：3´30 x12＋＋2 ´45 x22 ＋＋4 ´18 x32非负约束非负约束 xij ³0 (i=1,2,3；；j=1,2) （（3〕目标函数〕目标函数 max Z=f课堂作业课堂作业3 设每台设每台Ai每个工作日加工每个工作日加工Bj的数量为的数量为xij。

应用应用7：人力资源优化问题〔书：人力资源优化问题〔书P46 习题习题1.9）） 某公交线路每天各时段内所需司乘某公交线路每天各时段内所需司乘 人员数如下：人员数如下：302:00~6:0062022:00~2:0055018:00~22:0046014:00~18:0037010:00~14:002606:00~10:001所需人数所需人数时间时间班次班次 设所有的司乘人员分别在各时段的开始上班，并连续工设所有的司乘人员分别在各时段的开始上班，并连续工作作8小时，问该公交线路至少需配备多少司乘人员列出该小时，问该公交线路至少需配备多少司乘人员列出该问题的线性规划模型问题的线性规划模型第六节第六节 LP LP问题的基本理论问题的基本理论一、基本概念一、基本概念二、基本定理二、基本定理定理定理1 LP问题的可行域为一凸集问题的可行域为一凸集 引理：线性规划问题的可行解引理：线性规划问题的可行解X=(x1,x2,…,xn)T是基可行解的充要条件是是基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的的正分量所对应的系数列向量是线性独立的。

定理定理2 线性规划问题的基可行解对应线性规划问题的基可行解对应于可行域的顶点即：若于可行域的顶点即：若X是是LP问题问题的可行解，那么的可行解，那么“X是是LP问题的基可行问题的基可行解〞等价于解〞等价于“X是是LP问题可行域顶点问题可行域顶点”））定理定理3 若可行域有界，则若可行域有界，则LP问题的问题的目标函数一定可以在其可行域的顶点目标函数一定可以在其可行域的顶点上达到最优上达到最优课堂作业课堂作业4 化为标准型化为标准型第七节第七节 单纯形法的矩阵描述单纯形法的矩阵描述0I初始基变量初始基变量XSXNXBbNBCN0CB常数项常数项初始非基变量初始非基变量XSXN-CBB-1B-1非基变量非基变量B-1bB-1NICN-CBB-1N-CBB-1b0常数项常数项基变量基变量XBXSXN-CBB-1B-1非基变量非基变量B-1bB-1NICN-CBB-1N-CBB-1b0常数项常数项基变量基变量XB比较上述两张表，可得如下结论：比较上述两张表，可得如下结论： 1〕当新基〕当新基B确定后，表确定后，表2可由表可由表1直接求得；直接求得； 2〕表〕表2对应表对应表1单位矩阵单位矩阵I的位置为的位置为B-1。

表表1表表20I初始基变量初始基变量XSXNXBbNBCN0CB常数项常数项初始非基变量初始非基变量例例：：已已知知某某线线性性规规划划问问题题，，用用单单纯纯形形表表计计算算时时已已得得到到其其中两步计算表的部分信息如表中两步计算表的部分信息如表1、表、表2所示要求：所示要求： (1) 在两表的空白处填写正确的数字；在两表的空白处填写正确的数字； (2) 写出表写出表2的可行基Ｂ的可行基Ｂ表表1表表2 0 5 0 0 x5 x2 x3 x4 2 0 2 0 31218 x4 x5 x3XB b sj 14 x1CB 3 cj x5 x2 x3 x4 1/2 -1/3 0 1/3 -1/3 1/3 x2 x1 x3XB b sj x1CBcj1) 根据单纯形表构成规则填写相关数据；根据单纯形表构成规则填写相关数据；2) 确定表确定表2中的中的B-1，经计算，填写相关数据经计算，填写相关数据1 0 00 1 00 0 1 3 0 0 0 5 3 0 0 0 51 0 00 0 10 1 0-3/2-1 0 0 02 6 20 0 00 5 3课堂作业课堂作业5已已知知某某线线性性规规划划问问题题，，用用单单纯纯形形表表计计算算时时已已得得到到其其中中两两步计算表的部分信息如表步计算表的部分信息如表1、表、表2所示。

要求：所示要求： (1) 在两表的空白处填写正确的数字；在两表的空白处填写正确的数字； (2) 写出表写出表2的可行基Ｂ的可行基Ｂ表表1表表2 6 0 0 x2 x3 x4 -1/2 3 1/2 1/418 x4 x1XB b sj 15 x1CB 8 cj x2 x3 x4 1/3 -1/6 x2 x1XB b sj x1CBcj。