《线性规划及其单纯形求解方法.pptx》由会员分享，可在线阅读，更多相关《线性规划及其单纯形求解方法.pptx（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划的数学模型线性规划的数学模型线性规划的标准形式及方法线性规划的标准形式及方法线性规划的解及其性质线性规划的解及其性质线性规划问题的求解方法线性规划问题的求解方法单纯形法单纯形法应用实例应用实例:农场种植计划模型农场种植计划模型 第第1 1节节 线性规划及其单线性规划及其单纯形求解方法纯形求解方法第1页/共42页n n （一）线性规划模型之实例（一）线性规划模型之实例（一）线性规划模型之实例（一）线性规划模型之实例n n 线性规划研究的两类问题：线性规划研究的两类问题：n n 某项任务确定后，如何统筹安排，以最少某项任务确定后，
2、如何统筹安排，以最少的人力、物力和财力去完成该项任务；的人力、物力和财力去完成该项任务；n n 面对一定数量的人力、物力和财力资源，面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。它们都属如何安排使用，使得完成的任务最多。它们都属于最优规划的范畴。于最优规划的范畴。n n 以下为一些实例。以下为一些实例。一、线性规划的数学一、线性规划的数学模型模型 第2页/共42页n运输问题运输问题假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，m），第j销地的需求量为bj(j=1,2，n)，它们满足产销平衡条件。如果产地i到销地j的单位物资
3、的运费为Cij，要使总运费达到最小，可这样安排物资的调运计划：第3页/共42页 设设设设x xij ij表示由产地表示由产地表示由产地表示由产地i i供给销地供给销地供给销地供给销地j j 的物资数量，则的物资数量，则的物资数量，则的物资数量，则上述问题可以表述为：上述问题可以表述为：上述问题可以表述为：上述问题可以表述为：求一组实值变量求一组实值变量求一组实值变量求一组实值变量x xij ij(i i=1=1，2 2，mm；j j=1=1，2 2，n n)，使其满足，使其满足，使其满足，使其满足n n 而且使而且使 第4页/共42页n n资源利用问题资源利用问题资源利用问题资源利用问题 n
4、n 假假设设某某地地区区拥拥有有m m种种资资源源，其其中中，第第i i种种资资源源在在规规划划期期内内的的限限额额为为b bi i(i i=1=1，2 2，m m)。这这m m种种资资源源可可用用来来生生产产n n种种产产品品，其其中中，生生产产单单位位数数量量的的第第j j种种产产品品需需要要消消耗耗的的第第i i种种资资源源的的数数量量为为a aij ij(i i=1=1，2 2，m m；j j=1,2,=1,2,n n)，第第j j种种产产品品的的单单价价为为c cj j(j j=1=1，2 2，n n)。试试问问如如何何安安排排这这几几种种产产品品的的生生产产计计划划，才才能能使使规
5、规划划期期内内资资源源利利用用的总产值达到最大的总产值达到最大?第5页/共42页 设第设第设第设第j j种产品的生产数量为种产品的生产数量为种产品的生产数量为种产品的生产数量为x xj j(j j=1=1，2 2，n n)，则上述资源问题就是：，则上述资源问题就是：，则上述资源问题就是：，则上述资源问题就是：n n 求一组实数变量求一组实数变量x xj j(j=1(j=1，2 2，n n)，使，使其满足其满足第6页/共42页n n合理下料问题合理下料问题合理下料问题合理下料问题 n n 用某种原材料切割零件用某种原材料切割零件A A1 1，A A2 2,A Amm的的毛坯，现已设计出在一块原材
6、料上有毛坯，现已设计出在一块原材料上有B B1 1，B B2 2，B Bn n种不同的下料方式，如用种不同的下料方式，如用B Bj j下料方式可下料方式可得得A Ai i种零件种零件a aij ij个，设个，设A Ai i种零件的需要量为种零件的需要量为b bi i个。个。试问应该怎样组织下料活动，才能使得既满足试问应该怎样组织下料活动，才能使得既满足需要，又节约原材料？需要，又节约原材料？第7页/共42页 设采用设采用设采用设采用B Bj j方式下料的原材料数为方式下料的原材料数为方式下料的原材料数为方式下料的原材料数为x xj j，则上述，则上述，则上述，则上述问题可表示为：问题可表示为：
7、问题可表示为：问题可表示为：n n求一组整数变量求一组整数变量x xj j(j=1(j=1，2 2，n)n)，使得，使得第8页/共42页 （二）线性规划的数学模型（二）线性规划的数学模型（二）线性规划的数学模型（二）线性规划的数学模型 n n以上例子表明，线性规划问题具有以下特征：以上例子表明，线性规划问题具有以下特征：n n 每每一一个个问问题题都都用用一一组组未未知知变变量量（x x1 1，x x2 2，x xn n）表表示示某某一一规规划划方方案案，其其一一组组定定值值代代表表一一个个具具体体的的方案，而且通常要求这些未知变量的取值是非负的。方案，而且通常要求这些未知变量的取值是非负的。
8、n n 每每一一个个问问题题的的组组成成部部分分：一一是是目目标标函函数数，按按照照研研究究问问题题的的不不同同，常常常常要要求求目目标标函函数数取取最最大大或或最最小小值值；二二是是约约束束条条件件，它它定定义义了了一一种种求求解解范范围围，使使问问题题的的解解必须在这一范围之内。必须在这一范围之内。n n每一个问题的目标函数和约束条件都是线性的。每一个问题的目标函数和约束条件都是线性的。第9页/共42页由此可以抽象出线性规划问题的数学模型，一般形式为：在线性约束条件以及非负约束条件xj0（j=1，2，n）下，求一组未知变量xj(j=1，2，n)的值，使第10页/共42页采用矩阵形式可描述为
9、：在约束条件 AX(，)b X0下，求未知向量，使得Z=CXmax(min)其中第11页/共42页 二、线性规划的标准形式及方法二、线性规划的标准形式及方法二、线性规划的标准形式及方法二、线性规划的标准形式及方法 n n (一）线性规划的标准形一）线性规划的标准形式式 n n 在在讨讨论论与与计计算算时时，需需要要将将线线性性规规划划问问题题的的数数学学模模型转化为标准形式，即在约束条件型转化为标准形式，即在约束条件xj0（j=1，2，n）下，求一组未知变量xj（j=1，2，n）的值，使第12页/共42页其缩写形式为：在约束条件 x0（j=1，2，n）下，求一组未知变量（j=1，2，n）的值，
10、使得 常记为如下更为紧凑的形式 或第13页/共42页（二）化为标准形式的方法（二）化为标准形式的方法（二）化为标准形式的方法（二）化为标准形式的方法 n n具体的线性规划问题，需要对目标函数或具体的线性规划问题，需要对目标函数或约束条件进行转换，化为标准形式。约束条件进行转换，化为标准形式。n n目标函数化为标准形式的方法目标函数化为标准形式的方法目标函数化为标准形式的方法目标函数化为标准形式的方法 n n如果其线性规划问题的目标函数为如果其线性规划问题的目标函数为n n minminZ Z =CX=CX n n显然有显然有minminZ Z=maxmax(-(-Z Z)=)=maxmax Z
11、 Z n n则目标函数的标准形式为则目标函数的标准形式为maxmax Z Z=-=-CXCX第14页/共42页n约束方程化为标准形式的方法约束方程化为标准形式的方法 若第k个约束方程为不等式，即 引入松弛变量 ,K个方程改写为 则目标函数标准形式为第15页/共42页三、线性规划的解及其性质三、线性规划的解及其性质三、线性规划的解及其性质三、线性规划的解及其性质 n n (一一)线性规划的解线性规划的解 n n可行解与最优解可行解与最优解n n 满满足足约约束束条条件件（即即满满足足线线性性约约束束和和非非负负约约束束）的的一一组组变变量量为为可可行行解解。所所有有可可行行解组成的集合称为可行域
12、。解组成的集合称为可行域。n n 使使目目标标函函数数最最大大或或最最小小化化的的可可行行解解称称为最优解。为最优解。第16页/共42页n n基本解与基本可行解基本解与基本可行解 n n 在在线线性性规规划划问问题题中中，将将约约束束方方程程组组的的m m n n阶阶矩矩阵阵A A写写成成由由n n个个列列向向量量组组成成的的分分块块矩阵矩阵第17页/共42页如果B是A中的一个阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设则称 为基向量，与基向量相对应的向量 为基变量，而其余的变量 为非基变量。第18页/共42页如果是方程组的解,则就是方程组的一个解，它称之为对应于基B的基
13、本解，简称基解。满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。第19页/共42页 线性规划问题的以上几个解的关系，可用下图来描述：第20页/共42页 (二二二二)线性规划解的性质线性规划解的性质线性规划解的性质线性规划解的性质 n n凸集和顶点凸集和顶点n 凸集凸集凸集凸集：若连接：若连接n n维点集维点集S S中的任意两点中的任意两点X X(1)(1)和和X X(2)(2)之间的线段仍在之间的线段仍在S S中，则中，则S S为凸集。为凸集。n n 顶点顶点顶点顶点：若凸集：若凸集S S中的点中的点X X(0)(0)不能成为不能成为S S中任中任何线段的内点，则称
14、何线段的内点，则称X X(0)(0)为为S S的顶点或极点。的顶点或极点。第21页/共42页n线性规划解的性质线性规划解的性质 线性规划问题的可行解集（可行域）为凸集。可行解集S中的点X是顶点的充要条件是基本可行解。若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到。因此线性规划的最优解只需从其可行解集的有限个顶点中去寻找。第22页/共42页四、线性规划问题的求解方法四、线性规划问题的求解方法单纯形法单纯形法 （一）单纯形表（一）单纯形表 根据以上讨论，令 则 基变量 ，非基变量 ，则有 变形得第23页/共42页n n相应地，记相应地，记n n目标函数记为目标函数记为n n则对应于基
15、则对应于基B B的基本解为的基本解为第24页/共42页n最优解的判定最优解的判定当时，则由目标函数式可看出：对应于B的基本可行解为最优解，这时，B也被称为最优基。由于与等价，故可得。n最优解的判定定理最优解的判定定理对于基B，若，且,则对应于基B的基本解为最优解，B为最优基。第25页/共42页在上式中，称系数矩阵 为对应于基B的单纯形表，记为T(B)。或对目标函数与约束不等式运用矩阵变形得第26页/共42页如果记以及则第27页/共42页(二二二二)单纯形法的计算步骤单纯形法的计算步骤单纯形法的计算步骤单纯形法的计算步骤 n n 第第第第1 1步步步步，找找出出初初始始可可行行基基，建建立立初初
16、始始单单纯纯形表。形表。n n 第第第第2 2 2 2步步步步，判别检验所有的检验系数，判别检验所有的检验系数 n n （1 1）如果所有的检验系数）如果所有的检验系数 ,则由最优性判定定理知，已获最优解，即则由最优性判定定理知，已获最优解，即此时的基本可行解就是最优解。此时的基本可行解就是最优解。n n （2 2）若检验系数中，有些为正数，但其中若检验系数中，有些为正数，但其中某一正的检验系数所对应的列向量的各分量均非某一正的检验系数所对应的列向量的各分量均非正，则线性规划问题无解。正，则线性规划问题无解。（3 3）若检验系数中，有些为正数，且它们所若检验系数中，有些为正数，且它们所对应的列
17、向量中有正的分量，则需要换基、进行对应的列向量中有正的分量，则需要换基、进行迭代运算。迭代运算。第28页/共42页 第第3 3步步，选主元。在所有大于零的检验数中选取最大的一个b0s，对应的非基变量为xs，对应的列向量为若则确定brs为主元项。第第4 4步步，在基B中调进Ps，换出Pjr，得到一个新的基 第第5 5步步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。第第6 6步步，转入上述第2步。第29页/共42页例例1：用单纯形方法求解线性规划问题 解解：首先引入松弛变量 ，把原问题化为标准形式 第30页/共42页 具体步骤如下：第1步，确定初始单纯形表5.1.
18、1。x1x2x3x4-z02300 x3121310 x492101第2步，判别。在初始单纯形表中b01=2,b02=3，所以B1不是最优基，进行换基迭代。第3步，选主元。根据选主元法则，确定主元项 。第4步，换基，得一新基 。表5.1.1第31页/共42页 第5步，进行初等行变换，得B2下的新单纯形表x1x2x3x4-z-1210-10 x241/311/30 x455/30-1/31 第6步，因检验系数有正数b01=1，重复以上步骤可得对应于 B3=p2,p3的单纯形表，检验各检验数可知得最优解X1=3,X2=3,X3=0,X4=0:目标函数最大值为 Z=15。x1x2x3x4-z-150
19、0-4/5-3/5x23012/5-1/5x1 310-1/53/5表5.1.2表5.1.3第32页/共42页 五、应用实例五、应用实例五、应用实例五、应用实例:农场种植计划模型农场种植计划模型农场种植计划模型农场种植计划模型 n n某农场某农场I I、II II、IIIIII等耕地的面积分别为等耕地的面积分别为100hm100hm2 2、300hm300hm2 2和和200hm200hm2 2，计划种植水稻、大豆和玉米，要，计划种植水稻、大豆和玉米，要求求3 3种作物的最低收获量分别为种作物的最低收获量分别为190000kg190000kg、130000130000kgkg和和350000k
20、g350000kg。I I、II II、IIIIII等耕地种植等耕地种植3 3种作物的单产种作物的单产如表如表5.1.45.1.4所示。若所示。若3 3种作物的售价分别为水稻种作物的售价分别为水稻1.201.20元元/kg/kg，大豆，大豆1.501.50元元/kg/kg，玉米，玉米0.800.80元元/kg/kg。那么，（。那么，（1 1）如）如何制订种植计划，才能使总产量最大？（何制订种植计划，才能使总产量最大？（2 2）如何制）如何制订种植计划，才能使总产值最大？订种植计划，才能使总产值最大？第33页/共42页表5.1.4不同等级耕地种植不同作物的单产(单位:kg/hm2)I等耕地II等
21、耕地III等耕地水稻11 0009 5009 000大豆8 0006 8006 000玉米14 00012 00010 000表5.1.4第34页/共42页对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。根据题意，决策变量设置如表5.1.5所示,表中Xij表示在第j等级的耕地上种植第i种作物的面积。3种作物的产量可以用表5.1.6表示。第35页/共42页作物种类总产量水稻大豆玉米表5.1.5 作物计划种植面积（单位:hm2)表5.1.6 3种作物的总产量（单位:kg）I等耕地II等耕地III等耕地水稻大豆玉米第36页/共42页n根据题意，约束方程如下根据题意，约束方程如下,耕地面积
22、约束耕地面积约束n最低收获量约束最低收获量约束 n非负约束非负约束 第37页/共42页 （1）追求最大总产量的目标函数为 调用Matlab软件系统优化工具箱中的linprog函数，进行求解运算，可以得到一个最优解（如表5.1.7所示）。在该方案下，最优值，即最大总产量为6 892 200 kg。从表中可以看出，如果以追求总产量最大为种植计划目标，那么，玉米的种植面积在I、II、III等耕地上都占绝对优势。第38页/共42页表5.1.7 追求总产量最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻0021.1111大豆0021.6667玉米100300157.2222第39页/共42页 (2)追求最大总产值的目标函数为 进行求解运算，可以得到一个最优解（如表5.1.8所示）。在该方案下，最优值，即最大总产值为6 830 500元。从表中可以看出，如果以追求总产值最大为种植计划目标，那么，水稻的种植面积在I、II、III等耕地上都占绝对优势。第40页/共42页表5.1.8 追求总产值最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻58.75 300 200大豆16.25 00玉米2500第41页/共42页