《线性规划模型的建立与应用重点.pptx》由会员分享，可在线阅读，更多相关《线性规划模型的建立与应用重点.pptx（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1线性规划模型的建立与应用重点线性规划模型的建立与应用重点第七章第七章第七章第七章 线性规划模型的建立与应用线性规划模型的建立与应用线性规划模型的建立与应用线性规划模型的建立与应用一、线性规划的概念一、线性规划的概念二、线性规划三要素二、线性规划三要素三、技术经济研究中运用线性规划方法的特点三、技术经济研究中运用线性规划方法的特点及局限性及局限性四、线性规划模型的基本结构四、线性规划模型的基本结构五、线性规划模型的一般形式五、线性规划模型的一般形式六、线性规划模型的基本假设六、线性规划模型的基本假设 第一节线性规划模型的基本原理第1页/共73页 线性规划是指如何最有效或最佳地谋划线性规划
2、是指如何最有效或最佳地谋划经济活动。它所研究的问题有两类：经济活动。它所研究的问题有两类：一类是指一定资源的条件下，达到最高一类是指一定资源的条件下，达到最高产量、最高产值、最大利润；产量、最高产值、最大利润；一类是，任务量一定，如何统筹安排，一类是，任务量一定，如何统筹安排，以最小的消耗取完成这项任务。如最低成本以最小的消耗取完成这项任务。如最低成本问题、最小投资、最短时间、最短距离等问问题、最小投资、最短时间、最短距离等问题。前者是求极大值问题，后者是求极小值题。前者是求极大值问题，后者是求极小值问题。总之，线性规划是一定限制条件下，问题。总之，线性规划是一定限制条件下，求目标函数极值的问
3、题。求目标函数极值的问题。第一节线性规划模型的基本原理一、线性规划的概念一、线性规划的概念一、线性规划的概念一、线性规划的概念第2页/共73页 经济大词典定义线性规划：一种具有确定目标，而实现目标的手段又有一定限制，且目标和手段之间的函数关系是线性的条件下，从所有可供选择的方案中求解出最优方案的数学方法。第一节线性规划模型的基本原理一、线性规划的概念一、线性规划的概念一、线性规划的概念一、线性规划的概念第3页/共73页二、线性规划三要素二、线性规划三要素二、线性规划三要素二、线性规划三要素1.目标函数最优化单一目标 多重目标问题如何处理？2.实现目标的多种方法 若实现目标只有一种方法不存在规划
4、问题。3.生产条件的约束资源是有限的 资源无限不存在规划问题。第一节线性规划模型的基本原理第4页/共73页三、技术经济研究中运用线性规划方法三、技术经济研究中运用线性规划方法三、技术经济研究中运用线性规划方法三、技术经济研究中运用线性规划方法的特点及局限性的特点及局限性的特点及局限性的特点及局限性 第一节线性规划模型的基本原理特点：1.可以使研究对象具体化、数量化。可以对所研究的技术经济问题做出明确的结论；2.线性3.允许出现生产要素的剩余量4.有一套完整的运算程序第5页/共73页三、技术经济研究中运用线性规划方法三、技术经济研究中运用线性规划方法三、技术经济研究中运用线性规划方法三、技术经济
5、研究中运用线性规划方法的特点及局限性的特点及局限性的特点及局限性的特点及局限性 第一节线性规划模型的基本原理局限性：1.线性规划它是以价格不变和技术不变为前提条件的，不能处理涉及到时间因素的问题。因此，线性规划只能以短期计划为基础。2.在生产活动中，投入产出的关系不完全是线性关系，由于在一定的技术条件下，报酬递减规律起作用，所以要满足线性假定是不可能的。在线性规划解题中，常常把投入产出的非线性关系转化为线性关系来处理，以满足线性的假定性，客观上产生误差。3.线性规划本身只是一组方程式，并不提供经济概念，它不能代替人们对现实经济问题的判断。第6页/共73页四、线性规划模型的基本结构四、线性规划模
6、型的基本结构四、线性规划模型的基本结构四、线性规划模型的基本结构1.1.决决策策变变量量 未未知知数数。它它是是通通过过模模型型计计算算来来确确定定的的决决策策因因素素。又又分分为为实实际际变变量量求求解解的的变变量量和和计计算算变变量量，计计算算变变量量又又分分松松弛弛变变量量（上限）和人工变量（下限）。（上限）和人工变量（下限）。2.2.目目标标函函数数经经济济目目标标的的数数学学表表达达式式。目目标标函函数数是是求求变变量量的的线线性性函函数数的的极极大大值值和和极极小小值值这这样一个极值问题。样一个极值问题。3.3.约束条件约束条件实现经济目标的制约因素。它实现经济目标的制约因素。它包
7、括：生产资源的限制（客观约束条件）、包括：生产资源的限制（客观约束条件）、生产数量、质量要求的限制（主观约束条件）生产数量、质量要求的限制（主观约束条件）、特定技术要求和非负限制。、特定技术要求和非负限制。第一节线性规划模型的基本原理第7页/共73页四、线性规划模型的基本结构四、线性规划模型的基本结构四、线性规划模型的基本结构四、线性规划模型的基本结构 Min Z=10 x1+20 x2 s.t.x1+x210 3x1+x215 x1+6x215 x10,x20 约束条件目标函数第一节线性规划模型的基本原理第8页/共73页五、线性规划模型的一般形式五、线性规划模型的一般形式五、线性规划模型的一
8、般形式五、线性规划模型的一般形式Max Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn b1 (1)a21x1+a22x2+a2nxn b2 (2)am1x1+am2x2+amnxn bm (m)x1，x2，xn0第一节线性规划模型的基本原理极大值模型第9页/共73页其简缩形式为其简缩形式为 第一节线性规划模型的基本原理极大值模型第10页/共73页五、线性规划模型的一般形式五、线性规划模型的一般形式五、线性规划模型的一般形式五、线性规划模型的一般形式Min Min Z Z=c=c1 1x x1 1+c+c2 2x x2 2+c+c3 3x x3 3+c+cn n
9、x xn n a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n b b1 1 (1)(1)a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n b b2 2 (2)(2)a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n b bm m (m)(m)x x1 1，x x2 2，x xn n00第一节线性规划模型的基本原理极小值模型第11页/共73页其简缩形式为其简缩形式为 第一节线性规划模型的基本原理极小值模型第12页/共73页其简缩形式为其简缩形式为 第一节线性规划模型的基本原理极大值模型可用向量表
10、示：C=(c1,c2,cn)第13页/共73页六、线性规划模型的基本假设六、线性规划模型的基本假设六、线性规划模型的基本假设六、线性规划模型的基本假设1.1.线性线性线性线性 目标函数和约束条件目标函数和约束条件目标函数和约束条件目标函数和约束条件2.2.可分性可分性可分性可分性 活动对资源的可分性活动对资源的可分性活动对资源的可分性活动对资源的可分性3.3.可可可可加加加加性性性性 活活活活动动动动所所所所耗耗耗耗资资资资源源源源的的的的可可可可加加加加性性性性，资资资资源源源源总总总总需需需需要要要要量量量量为为为为多多多多种种种种活活活活动动动动所所所所需需需需资资资资源源源源数量的总和
11、。数量的总和。数量的总和。数量的总和。4.4.明确性明确性明确性明确性 目标的明确性目标的明确性目标的明确性目标的明确性5.5.单一性单一性单一性单一性 期望值的单一性期望值的单一性期望值的单一性期望值的单一性6.6.独独独独立立立立性性性性 变变变变量量量量是是是是独独独独立立立立的的的的表表表表示示示示各各各各种种种种作作作作业业业业对对对对资资资资源源源源都都都都是是是是互互互互竟竟竟竟关关关关系系系系，没没没没有有有有互互互互助助助助关系关系关系关系7.7.非负性非负性非负性非负性第14页/共73页第二节第二节 线性规划模型的建立与线性规划模型的建立与图解法求解图解法求解一、建模二、线
12、性规划的求解图解法第15页/共73页一、建模一、建模一、建模一、建模 例例例例11某饲料公司用甲、乙两种原料配制饲料，甲乙两种某饲料公司用甲、乙两种原料配制饲料，甲乙两种原料的营养成份及配合饲料中所含各营养成份最低原料的营养成份及配合饲料中所含各营养成份最低量由表量由表1 1给出。已知单位甲、乙原料的价格分别为给出。已知单位甲、乙原料的价格分别为1010元和元和2020元，求满足营养需要的饲料最小成本配方。元，求满足营养需要的饲料最小成本配方。第16页/共73页一、建模一、建模一、建模一、建模 设设配配合合饲饲料料中中，用用甲甲x1x1单单位位，用用乙乙x2x2单单位位，则则配配合合饲饲料料的
13、的原原料料成成本本函函数数，即即决决策策的的目目标标函函数数为为Z=10 x1+20 x2Z=10 x1+20 x2。考考虑虑三三种种营营养养含含量量限限制制条条件件后后，可可得得这这一一问问题题的的线线性性规规划划模模型型如如下：下：Min Z=10 xMin Z=10 x1 1+20 x+20 x2 2 x x1 1+x+x2 21010 3x 3x1 1+x+x2 21515 x x1 1+6x+6x2 21515 x x1 10,x0,x2 200第17页/共73页一、建模一、建模一、建模一、建模例例2某农户计划用12公顷耕地生产玉米，大豆和地瓜，可投入48个劳动日，资金360元。生产
14、玉米1公顷，需6个劳动日，资金36元，可获净收入200元；生产1公顷大豆，需6个劳动日，资金24元，可获净收入150元；生产1公顷地瓜需2个劳动日，资金18元，可获净收入1200元，问怎样安排才能使总的净收入最高。设种玉米，大豆和地瓜的数量分别为x1、x2和x3公顷，根据问题建立线性规划问题模型如下：第18页/共73页一、建模一、建模一、建模一、建模Max Z=200 x1+150 x2+100 x3 x1+x2+x312(1)6x1+6x2+2x348(2)36x1+24x2+18x3360(3)x10，x20，x30 第19页/共73页一、建模一、建模一、建模一、建模 例例33某农户有耕地
15、20公顷，可采用甲乙两种种植方式。甲种植方式每公顷需投资280元，每公顷投工6个，可获收入1000元，乙方式每公顷需投资150元，劳动15个工日，可获收入1200元，该户共有可用资金4200元、240个劳动工日。问如何安排甲乙两种方式的生产，可使总收入最大?解：设甲方式种x1公顷，乙方式种x2公顷，总收入为Z，则有：第20页/共73页一、建模一、建模一、建模一、建模Max Z=1000 x1+1200 x2 280 x1+150 x24200 6x1+15x2240 x1+x220 x10,x20 第21页/共73页二、线性规划的求解二、线性规划的求解二、线性规划的求解二、线性规划的求解图解法
16、图解法图解法图解法（一）可行解（二）可行域（三）最优解（四）最优性定理（五）最大化问题的图解法（六）最小化问题的图解法 第22页/共73页二、线性规划的求解二、线性规划的求解二、线性规划的求解二、线性规划的求解图解法图解法图解法图解法 （一）可行解（一）可行解 线性规划问题的可行解是指，满足规划线性规划问题的可行解是指，满足规划中所有约束条件及非负约束的决策变量的一组取值，中所有约束条件及非负约束的决策变量的一组取值，其仅与约束条件有关而与目标函数值的大小无关。其仅与约束条件有关而与目标函数值的大小无关。（二）可行域（二）可行域 可行域是由所有可行解构成的集合。可行域是由所有可行解构成的集合。
17、根据线性规划的基本理论，任一个线性规划问题的根据线性规划的基本理论，任一个线性规划问题的可行域，都是一个有限或无限的凸多边形，凸多边可行域，都是一个有限或无限的凸多边形，凸多边形的每个角，称为可行域的极点。形的每个角，称为可行域的极点。（三）最优解（三）最优解 线性规划的最优解是指，使目标函数线性规划的最优解是指，使目标函数值达到最优值达到最优(最大或最小最大或最小)的可行解。一个线性规划问的可行解。一个线性规划问题可以是有解的，也可能是无解的，最优解的个数题可以是有解的，也可能是无解的，最优解的个数可能是惟一的，也可能是有无穷多个，即决策变量可能是惟一的，也可能是有无穷多个，即决策变量有许多
18、组不同的取值，都使目标函数达到同一个最有许多组不同的取值，都使目标函数达到同一个最优值。优值。第23页/共73页二、线性规划的求解二、线性规划的求解二、线性规划的求解二、线性规划的求解图解法图解法图解法图解法 （四）最优性定理 若一个线性规划问题有最优解，则最优解一定可以在可行域的某个极点上找到一个最优解。同时仍有可能有其他最优解存在，但它们也只可能存在于可行域的其他极点或是边界上。如果我们的目的是找出一个最优解而不是全部最优解，这一定理实际上是把寻找的范围，从可行域中的无穷多个可行点，缩小到可行域的有限几个极点上。第24页/共73页二、线性规划的求解二、线性规划的求解二、线性规划的求解二、线
19、性规划的求解图解法图解法图解法图解法 （五）最大化问题的图解法第一步，找出问题的可行域第二步，在可行域中寻求最优解，方法有两种：A.查点法 B.图解法第25页/共73页二、线性规划的求解二、线性规划的求解二、线性规划的求解二、线性规划的求解图解法图解法图解法图解法 O 20 40 x120ABCD280 x1+150 x2=42006x1+15x2=240 x1+x2=20 x2Z=1000 x1+1200 x2A(0,16)B(6.7,13.3)C(9.2,10.8)D(15,0)ZA=19200ZB=22660ZC=22160ZD=15000第26页/共73页二、线性规划的求解二、线性规划
20、的求解二、线性规划的求解二、线性规划的求解图解法图解法图解法图解法 （五）最小化问题的图解法n n例：Min Z=10 x1+20 x2n ns.t.x1+x210n n 3x1+x215n n x1+6x215n n x10,x20第27页/共73页1515105105OABCDx2x1x1+6x2=15可行域3x1+x2=15x1+x2=1010 x1+20 x20A(0,15)B(2.5,7.5)C(9,1)D(15,0)ZA=300ZB=175ZC=110ZD=150第28页/共73页第三节第三节第三节第三节 单纯形法单纯形法单纯形法单纯形法 单纯形方法是一种较为完善的、步骤化的线性规
21、划问题求解方法。它的原理涉及到较多的数学理论上的推导和证明，我们在此仅介绍这种方法的具体操作步骤及每一步的经济上的含义。为更好地说明问题，我们仍结合实例介绍这种方法 第29页/共73页第三节第三节第三节第三节 单纯形法单纯形法单纯形法单纯形法一、线性规划的标准型二、线性规划问题的解三、单纯形法 四、单纯型表第30页/共73页第三节 单纯形法一线性规划的标准型LP目标函数有的要求实现最大化，有的要求实现最小化，约束条件可以是“=”、“”，这种多样性给讨论问题带来不便。为了便于讨论，我们规定线性规划问题的标准形式为：Max Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1n
22、xn=b1 (1)a21x1+a22x2+a2nxn=b2 (2)am1x1+am2x2+amnxn=bm (m)x1，x2，xn0 第31页/共73页第三节 单纯形法其简缩形式为 一线性规划的标准型用向量表示 其中 C=(c1,c2,cn)向量Pj是其对应变量xj 的系数向量。第32页/共73页第三节 单纯形法一线性规划的标准型用矩阵描述 第33页/共73页第三节 单纯形法二线性规划问题的解可行解可行解最优解最优解 基基 设A为约束方程组的mn阶系数矩阵，其秩为m。B是矩阵A中mm阶非奇异子矩阵（）,则称B是线性规划问题的一个基。不失一般性可设 称Pj为基向量，与基变量Pj相对应的变量为基变
23、量。否则为非基变量。第34页/共73页n n为了进一步讨论线性规划问题的解，我们来研究约束方程组求解的问题。假设方程组系数矩阵Z的秩为m，因m小于n故它有无穷多个解。假设前m个变量的系数列向量是线性独立的，这时线性规划模型可写成:二线性规划问题的解第35页/共73页或 设非基变量用高斯消去法，可求出一个解称X为基本解基本解基本可行解基本可行解 满足非负条件的基本解二线性规划问题的解第36页/共73页n n例例3某工厂在计划期内安排生产x1 x2两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定，产品x1和产品x2在各设备上加工的台时数见下表。已知各设备在计划期内有效台时
24、数分别是12、8、16和12。（一台设备工作一小时称为一台时）该工厂每生产一件产品x1可得利润2元，每生产一件产品x2可得利润3元，问如何安排生产计划，才能得到利润最多？三单纯形法第37页/共73页 设备产品ABCDx12140 x22204三单纯形法第38页/共73页n n（一）求解过程 n n（二）求解过程小结三单纯形法第39页/共73页Max Z=2x1+3 x2 2x1+2x212 x1+2x28 4x1 16 4x2 12 x10，x20 引入松弛变量x3 A设备闲置台时数x4 B设备闲置台时数x5 C设备闲置台时数x6D设备闲置台时数将线性规划化为标准型.（8.1）三单纯形法求解过
25、程第40页/共73页Max Z=2x1+3 x2+x3+x4+x5+x6 2x1+2x2+x3 =12 x1+2x2 +x4 =8 4x1 +x5 =16 4x2 +x6=12 x x1 100，x x2 20,0,x x3 300，x x4 400,x,x5 500，x x6 60 0（8.2）三单纯形法求解过程第41页/共73页 x3,x4,x5,x6的系数列向量p3,p4,p5,p6是线性独立的，这些列向量构成一个基 系数矩阵 三单纯形法求解过程第42页/共73页x3 =122x12x2 x4 =8x12x2 x5 =164x1 x6 =124x2 把上式带入目标函数得到 Z=0+2x1
26、+3 x2 （8.4）当非基变量x1=x2=0,便得z=0，这时得到一个基本可行解X(0)对应于B的变量x3,x4,x5,x6为基变量，从标准型我们可以得到：（8.3）三单纯形法求解过程第43页/共73页这个基本可行解表示：工厂没有安排生产产品；设备的有效台时数没有被利用，所以构成的利润为0。从分析目标函数的表达式可以看到，非基变量x1,x2系数都是正数，若将非基变量换成基变量，目标函数就会增加。所以，只要在目标函数的表达式中还存在正系数的非基变量，这表示目标函数还有增加的可能，就需要将非基变量换成基变量。一般选择正系数最大的那个非基变量。可按以下方法来确定换出变量。三单纯形法求解过程第44页
27、/共73页 现分析（现分析（8.48.4），将），将x x2 2定为换入变量后，必须从定为换入变量后，必须从x x3 3,x,x4 4,x,x5 5,x,x6 6中换出一个，并保证其余的都是非负，中换出一个，并保证其余的都是非负，即即x x3 3,x,x4 4,x,x5 5,x,x6 60 0 当当x x1 10 0，由（，由（8.38.3）式得到）式得到 x x3 3 =12 =122 2x x2 2 0 0 x x4 4 =8 =82 2x x2 20 0 （8.58.5）x x5 5 =16 =1600 x x6 6 =12 =124 4x x2 2 0 0 从（从（8.58.5）式中可
28、以看出，只有选择）式中可以看出，只有选择 Z=0+2x1+3 x2 （8.4）时，才能使（8.5）式成立。因当x2=3时，基变量x6=0这就决定用x2去替换x6。三单纯形法求解过程第45页/共73页为了求得以为了求得以x x3 3,x,x4 4,x,x5 5,x,x2 2为基变量的一个基本可行为基变量的一个基本可行解和进一步分析问题，需将（解和进一步分析问题，需将（8.58.5）中的）中的x x2 2位位置与置与x x6 6的位置兑换。得到的位置兑换。得到x x3 3 2 2x x2 2 =1 =12 22 2x x1 1 x x4 4 2 2x x2 2 =8 =8x x1 1 （8.68.
29、6）x x5 5 =16 =164 4x x1 1 4 4x x2 2 =12 =12 x x6 6 用高斯消去法，将（用高斯消去法，将（8.68.6）式中的）式中的x x2 2的系数列向的系数列向量变为单位列向量。量变为单位列向量。x x3 3 =6 =62 2x x1 1+1/2+1/2x x6 6 x x4 4 =2 =2x x1 1+1/2+1/2x x6 6 （8.78.7）x x5 5 =16 =164 4x x1 1 x x2 2 =3 =31/4x1/4x6 6三单纯形法求解过程第46页/共73页n n再将（8.7）代入（8.1）目标函数得到：n nZ=9+2x1-3/4 x6
30、 （8.8）n n当非基变量x1=x6=0，得到Z=9，并得到另一个基本可行解三单纯形法求解过程第47页/共73页 从目标函数的表达式（从目标函数的表达式（8.88.8）中可看到，非基）中可看到，非基变量变量x x1 1的系数是正的，说明目标函数值还可以的系数是正的，说明目标函数值还可以增大，增大，X X(1)(1)不一定是最优解。于是用上述方法，不一定是最优解。于是用上述方法，确定换入换出变量，继续迭代，再得到另一个确定换入换出变量，继续迭代，再得到另一个基本可行解基本可行解X X(2)(2)再经过一次迭代，又得到一个基本可行解再经过一次迭代，又得到一个基本可行解 这时得到的目标函数的表达式
31、是：这时得到的目标函数的表达式是：Z Z=14-1.5=14-1.5x x4 4-0.125 x-0.125 x5 5 目标函数值达到最大，目标函数值达到最大，X X(3)(3)是线性规划的最是线性规划的最优解。优解。三单纯形法求解过程第48页/共73页n n1.人造基、初始基本可行解 n n2.最优性检验 三单纯形法求解过程小结第49页/共73页n n1.1.人造基、初始基本可行解人造基、初始基本可行解 n n1.11.1若从线性规划问题的若从线性规划问题的 PjPj中能直接观察到存在中能直接观察到存在mm个线性独立的单位个线性独立的单位向量，经过重新安排次序便得到一个可行基向量，经过重新安
32、排次序便得到一个可行基三单纯形法求解过程小结第50页/共73页n n1.1.人造基、初始基本可行解人造基、初始基本可行解 n n1.2“”1.2“”标准化的方法，引入非负的松弛变量重标准化的方法，引入非负的松弛变量重新对新对x xj j及及a aij ij编号，经整理则可得到下列方程编号，经整理则可得到下列方程 Max Max Z Z=c=c1 1x x1 1+c+c2 2x x2 2+c+c3 3x x3 3+c+cn nx xn n x x1 1 +a+a1m+11m+1x xm+1m+1+a+a1m+21m+2x xm+2m+2+a+a1n1nx xn n =b=b1 1 x x2 2
33、+a+a2m+12m+1x x m+1m+1+a+a2m+22m+2x x m+2m+2+a+a2n2nx xn n=b=b2 2 （8.98.9）x xmm +a+amm+1mm+1x x m+1m+1+a+amm+2mm+2x x m+2m+2+a+amnmnx xn n=b=bmm x x1 1 ，x x2 2 ，x xn n00显然得到一个单位阵显然得到一个单位阵 三单纯形法求解过程小结第51页/共73页我们就将我们就将B B作为可行基。将（作为可行基。将（8.98.9）每个等式进）每个等式进行移项得行移项得 x x1 1 =b=b1 1 -a-a1m+11m+1x xm+1m+1-a
34、-a1m+21m+2x xm+2m+2-a-a1n1nx xn n x x2 2 =b=b2 2-a-a2m+12m+1x x m+1m+1-a-a2m+22m+2x x m+2m+2-a-a2n2nx xn n （8.108.10）x xm m =b=bm m -a-amm+1mm+1x x m+1m+1-a-amm+2mm+2x x m+2 m+2-a-amnmnx xn n x x1 1 ，x x2 2 ，x xn n00令令x x m+m+1 1 =x x m+2m+2 =x x n n=0,=0,由（由（8.108.10）可得）可得x xi i=b=bi i(I I=1,2,m)=1
35、,2,m)得到一个初始基本可行解得到一个初始基本可行解三单纯形法求解过程小结第52页/共73页2.2.最优性检验最优性检验n n得到初始可行解后，要检验一下是否是最优得到初始可行解后，要检验一下是否是最优解，如果是，则停止迭代，如果不是，则继解，如果是，则停止迭代，如果不是，则继续迭代续迭代。但每次迭代后都要检验一下是。但每次迭代后都要检验一下是否是最优解，为此需要建立一个判别准则。否是最优解，为此需要建立一个判别准则。n n一般情况下，经过迭代后式变成一般情况下，经过迭代后式变成n n （i=1,2,3,mi=1,2,3,m）n n将上式代入目标函数，整理后得将上式代入目标函数，整理后得三单
36、纯形法求解过程小结第53页/共73页j=m+1,n 三单纯形法求解过程小结第54页/共73页n n2.12.1最优解判别定理：最优解判别定理：n n若若 为对应于为对应于B B的基的基本可行解，且对于一切本可行解，且对于一切j=m+1,nj=m+1,n有有 ，则，则X X（0 0）为最优解。为最优解。n n无有限最优解判别定理：无有限最优解判别定理：n n若若 为对应于为对应于B B的基的基本可行解，有一个本可行解，有一个 并且对于一切并且对于一切i=1,2,3,mi=1,2,3,m有，有，那么该线性规那么该线性规划没有有限最优解。划没有有限最优解。n n2.22.2换入变量的确定换入变量的确
37、定n n2.32.3换出变量的确定换出变量的确定 ，n n 为换入变量。为换入变量。三单纯形法求解过程小结第55页/共73页三单纯形表例1第56页/共73页例1第57页/共73页例1第58页/共73页例1第59页/共73页例2第60页/共73页例2第61页/共73页例2第62页/共73页n n目标函数系数灵敏度分析n n右边值灵敏度分析第四节第四节 灵敏度分析灵敏度分析第63页/共73页目标函数系数灵敏度分析目标函数系数灵敏度分析目标函数系数灵敏度分析目标函数系数灵敏度分析n n最优解不变的条件下，允许最优解不变的条件下，允许C C的变化范围，最优的变化范围，最优解不变的前提是解不变的前提是j
38、 0n n假设玉米价值系数假设玉米价值系数C C1 1发生了变化，其变化量为发生了变化，其变化量为1 1-50 1 1001 -501 1001 100 -50-1 0 -50+0.51 0 -25-0.251 0第64页/共73页目标函数系数灵敏度分析目标函数系数灵敏度分析目标函数系数灵敏度分析目标函数系数灵敏度分析n n假设大豆价值系数假设大豆价值系数C C2 2发生了变化，其变化量为发生了变化，其变化量为2 2 -50-502 0第65页/共73页目标函数系数灵敏度分析目标函数系数灵敏度分析目标函数系数灵敏度分析目标函数系数灵敏度分析n n假设地瓜价值系数假设地瓜价值系数C C3 3发生
39、了变化，其变化量为发生了变化，其变化量为3 3-100/3 3 1003 -100/33 100 -50-1.53 0-250.253 0第66页/共73页表8-3 目标系数的允许变动范围活动目标系数当前值可减上限 可增上限 可变范围玉米种植x120050100150300大豆种植x2150无穷大50-200地瓜种植x3100100/3100200/3200 当仅有一种目标系数在允许范围内变动时，最优方案不会变动，但最优目标值会随之变化。第67页/共73页右边值敏感性分析右边值敏感性分析n n由线性规划的原理可知，影子价格不变的条件是最优解的松弛变量矩阵与右边值矩阵的乘积大于和等于0，即：当右
40、边值发生变化时，如耕地变化，此时，影子价格不变的条件是 第68页/共73页右边值敏感性分析右边值敏感性分析耕地耕地得到 6+3/210 6-1/210 -414 36-910因此耕地影子价格不变的耕地数量范围为：8，16第69页/共73页右边值敏感性分析右边值敏感性分析劳动力劳动力得到 61/420 6+1/420 -2428 36-9/220因此劳动力影子价格不变的劳动力数量范围为：24，56第70页/共73页右边值敏感性分析右边值敏感性分析资金资金得到 60 60 3 36 3630因此资金影子价格不变的资金数量范围为：324，第71页/共73页表8-4 常数项的允许变动范围资源现有数量可减上限可增上限可变范围影子价格耕地124481650劳动48248245625资金36036+324+0常数项的允许变动范围这一结果也还有另外一种意义，即它给出了资源影子价格（边际产出率）的有效范围。对耕地而言，当投入使用的数量在8-16公顷之间变化时，其边际产出率都是50元，即每增加或减少1公顷耕地，农户将增加或减少50元净收入。第72页/共73页