运筹学基础及应用说课材料.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运 筹,学,(,Operations Research,),夫运筹策帷幄之中，决胜于千里之外,史记,高祖本纪,绪 论,（,1,）运筹学简述,（,2,）运筹学的主要内容,（,3,）本课程的主要学习内容,（,4,）运筹学的应用,（,5,）本课程的教材及参考书,（,6,）本课程授课方式与考核,本章主要内容：,一、古代朴素的运筹学思想,国外,英文原名,Operations Research,简称“,O.R.”,直译为：运用研究或作业研究,正式出现于,1938,年,7,月英国一份关于防空作战系统运行的研究报告中,中国古代运筹学案例,二、运筹学的起源,（一）运筹学简述,运作研究,(Operational Research),小组,”,:,二战期间解决复杂的战略和战术问题。例如：,如何合理运用雷达有效地对付德军空袭,对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；,在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。,二战后运筹学的发展经历了三个阶段,（,1,）,1945,年到,20,世纪,50,年代初,创建时期,（,2,）,20,世纪,50,年代初到,20,世纪,50,年代末,成长时期,（,3,）,20,世纪,60,年代以来,迅速发展和普及的时期,国内,1956,年成立第一个运筹学小组,1957,年从“夫运筹策帷幄之中，决胜于千里之外”中摘取“运筹”二字，将,O.R.,正式翻译为“运筹学”,三、运筹学的定义,研究工具：数学，计算机科学及其他相关科学,研究目的：对有限资源进行合理规划、使用，并提供,优化决策方案。,研究对象：复杂系统的组织和管理,参考,大英百科全书,、,辞海,、,中国企业管理百科全书,等。,四、运筹学研究的基本特点,系统的整体优化,多学科的配合,模型方法的应用,五、运筹学研究的基本步骤,分析与表述问题,建立数学模型,对问题求解,对模型和模型导出的解进行检验,建立对解的有效控制,方案的实施,（二）运筹学的主要内容,数学规划（,线性规划、整数规划、目标规划,、动态规划等）,图论,存贮论,排队论,对策论（博弈论）,决策论,（三）运筹学的应用,运筹学方法 应用例,线性规划 生产结构优化,非线性规划 投资组合优化,整数规划 选址问题,动态规划 资源分配问题,网络分析 工程计划优化,排队论 服务系统优化,存贮论 订货库存管理,决策分析 机会选择,运筹学的广泛实际背景促使其不断发展并 在经济管理和系统工程等多领域中发挥着令 人瞩目的重要作用。,诺贝尔经济学奖从,1969,年首发至今的,57,位获奖者中就有多位是运筹学家。,1975,年诺贝尔经济学奖授给了库普曼和康脱罗维 奇，以表彰首先将线性规划与经济问题相联系而 做出的贡献；,1994,年诺贝尔经济学奖授给了三位博弈论专家：纳什、泽尔腾、海萨尼。博弈论已经成为当代经 济学的基石。,2005,年以色列经济学家罗伯特,-,奥曼和美国经济 学家托马斯,-,斯切林，因“通过博弈论分析加强了 我们对冲突和合作的理解”所作出的贡献而获奖。,发表的部分获奖项目,组织,应用,效果,联合航空公司,在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排,每年节约成本,600,万美元,Citgo,石油公司,优化炼油程序及产品供应、配送和营销,每年节约成本,7000,万,AT&T,优化商业用户的电话销售中心选址,每年节约成本,4.06,亿美元，销售额大幅增加,标准品牌公司,控制成本库存（制定最优再定购点和定购量确保安全库存）,每年节约成本,380,万美元,法国国家铁路公司,制定最优铁路时刻表并调整铁路日运营量,每年节约成本,1500,万美元，年收入大幅增加。,Taco Bell,优化员工安排，以最低成本服务客户,每年节约成本,1300,万美元,Delta,航空公司,优化配置上千个国内航线航班来实现利润最大化,每年节约成本,1,亿美元,（四）本课程的教材及参考书,选用教材,运筹学基础及应用,胡运权主编（第五版）高等教育出版社,参考教材,运筹学教程,胡运权主编（第,4,版）清华出版社,管理运筹学,韩伯棠主编（第,2,版）高等教育出版社,运筹学,(,修订版,),钱颂迪主编 清华出版社,（五）本课程的主要学习内容,第一章 线性规划及单纯形法,第二章 线性规划的对偶理论,第三章 运输问题,第四章 整数规划与分配问题,（六）本课程授课方式与考核,学科总成绩,平时成绩,（,30,）,课堂考勤,（,12,）,平时作业,（,18,）,期末成绩,（,70,）,讲授为主，结合讨论、习题作业,第一章 线性规划及单纯形法,Linear Programming and Simplex Method,线性规划,-,发展简史,法国数学家,J.-B.-J.,傅里叶和,C.,瓦莱普森分别于,1832,和,1911,年独立地提出线性规划的想法，但未引起注意。,1939,年苏联数学家,.,.,康托罗维奇,在,生产组织与计划中的数学方法,一书中提出线性规划问题，也未引起重视。,1947,年美国数学家,G.B.,丹齐克,提出线性规划的一般数学模型和求解线性规划问题的通用方法,单纯形法,，为这门学科奠定了基础。,1947,年美国数学家,J.von,诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。,1951,年美国经济学家,T.C.,库普曼斯把线性规划应用到经济领域,，为此与康托罗维奇一起获,1975,年诺贝尔经济学奖。,50,年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，,1954,年,C.,莱姆基提出对偶单纯形法,，,1954,年,S.,加斯和,T.,萨迪等人解决了线性规划的灵敏度分析和参数规划问题，,1956,年,A.,塔克提出互补松弛定理，,1960,年,G.B.,丹齐克和,P.,沃尔夫提出分解算法,等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如,MPSX,，,OPHEIE,，,UMPIRE,等，可以很方便地求解几千个变量的线性规划问题,。,1979,年苏联数学家,.,.,哈奇扬提出解线性规划问题的椭球算法,，并证明它是多项式时间算法。,1984,年,美国贝尔电话实验室的印度数学家,N.,卡马卡提出解线性规划问题的新的多项式时间算法,-,内点算法,。用这种方法求解线性规划问题在变量个数为,5000,时只要单纯形法所用时间的,1/50,。现已形成线性规划多项式算法理论。,50,年代后线性规划的应用范围不断扩大。,1.,1939,年，前苏联科学家康托洛维奇,-,生产组织与管理中的数学方法,是线性规划应用于工业生产问题的开山之作,；,(LEONID VITALIYEVICH KANTOROV(1912-1986),2.1947,年，美国数学家乔治,伯纳德,丹齐格,-,单纯形法，被称为线性规划之父。,George Bernard Dantzig(19142005),丹齐格在,1946,年获伯克利大学的博士学位。,1947,年，,33,岁提出了解决一种最优化问题的单纯形法,该方法奠定了线性规划的基础，使得经济学、环境科学、统计学应用等学科获得了迅速发展。,Dantzig,也因而被誉为“线性规划之父”。,1952,年他在兰德公司任研究数学家，在公司电脑上实行线性规划。,1960,年他被母校聘任教授计算机科学，终于当上运筹学中心主任。,1966,年他在史丹福大学当类似职位，留在那里直到,1990,年代退休。,Dantzig,在运筹学建树极高，获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在,Linear programming andextensions,一书中研究了线性编程模型，为计算机语言的发展做出了不可磨灭的贡献。他除了线性规划和单纯形法的杰出工作，还推进很多领域的发展，有分解论、灵敏度分析、互补主元法、大系统最优化、非线性规划和不确定规划。,SIAM Journal on Optimization,1991,年创刊号是献给他的。,Mathematical Programming Society,为表彰丹齐格，设立丹齐格奖，,1982,年起每三年颁给一至两位在数学规划有突出贡献的人。,x,a,此为无约束的极值问题,1.1,一般线性规划问题的数学模型,1-1,问题的提出,例,1,用一块边长为,a,的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？,解：如图设四个角上减去的小正方形边长为,x,，则容器体积为：,时，容积最大,例,2,常山机器厂生产,I,、,II,两型产品。这两型产品都分别要在,A,、,B,、,C,三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：,单位产品消耗设备工时,I,II,设备工时限量（小时）,设备,A,设备,B,设备,C,2,4,0,2,0,5,12,16,15,单位利润（元）,2,3,如何安排生产才能使总的利润最大？,解：设计划期内两种产品的数量分别为,x,1,，,x,2,，则总利润为：,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,简记为：,s.t.,（约束于：）,z,=2,x,1,+3,x,2,在满足限制条件下求,z,的最大值。,此为有约束极值问题,1-2,线性规划问题的数学模型,原型,模型,数学模型,提炼,数学工具,1,、,原型,：现实世界中人们关心、研究的实际对象。,模型,：将某一部分信息简缩、提炼而构造的原型替代物。,数学模型,：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。,3,、规划问题数学模型的三要素,（,2,）,目标函数,：问题要达到的目标要求，表示为决策变量的函数。用,z,=,f,(,x,1,，,x,2,，,，,x,n,),表示。,（,1,）,决策变量,：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用,x,1,，,x,2,，,，,x,n,表示。,（,3,）,约束条件,：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,2,、规划问题,即求目标函数在若干约束条件下的最值。,4,、线性规划问题（,Linear Programming,）的数学模型,（,2,）,一般形式,：,（,1,）,条件,：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为“,L.P.”,max,(,或,min,)z=c,1,x,1,+c,2,x,2,+,+c,n,x,n,s.t.,a,11,x,1,+a,12,x,2,+a,1n,x,n,（,=,，,）,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,（,=,，,）,b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,（,=,，,）,b,m,x,1,x,2,x,n,0,（,3,）,其他形式,：,连加形式,向量形式,其中,称为,价值行向量,；,决策列向量,系数列向量,右端列向量,矩阵形式,其中,称为价值行向量；,决策列向量,右端列向量,约束矩阵或系数矩阵,1-3,线性规划问题的标准形式,1,、标准形式,或,2,、条件,目标函数求极大值,约束条件全是等式（线性方程组）,决策变量全非负,右端常数全非负,3,、标准化方法,（,1,）若目标函数求极小值，即,则令,转化为,（,2,）若约束条件为不等式，,则依次引入松弛变量或剩余变量（统称为松弛变量），,转化为等式约束条件。,注意,：松弛变量在目标函数中系数全为,0,。,约束为不等式，减去松弛变量，化为等式约束条件；,约束为不等式，加上松弛变量，化为等式约束条件。,多退少补,例：,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t.,标准化,（,3,）若决策变量,x,j,0,，则令,（,4,）若决策变量,x,j,取值无限制，则令,（,5,）若约束等式的右端常数,b,i,0,，则等式两边同时乘以“,-1,”,。,其中,（“一分为二”）,例：,将下列线性规划模型化为标准形式。,则问题化为标准形式：,并引入松弛变量,x,4,x,5,课堂练习：将下列线性规划问题化为标准形式,线性规划问题的数学模型,标准形式如下：,1-4,线性规划问题的解,已知线性规划的标准形式：,或,1,、,求解线性规划问题,：,从满足（,2,）、（,3,）的方程组中找出一个解使目标函数（,1,）达到最大值。,2,、,可行解,：,所有可行解的集合。,可行域,：,满足约束条件（,2,）、（,3,）的解。,记做,最优解,：,使目标函数达到最大值的可行解。,（,1,）,基,：设,A,为线性规划问题约束条件的,m,n,系数矩阵,（,m0,，,有如下结论：,(1),若对所有,j,m+1,，有,j,0,，则,z,（,1,）,z,（,0,）,，即,z,（,0,）,为最优函数值，,X,（,0,）,为,唯一最优解,；,(2),若对所有,j m+1,，,有,j,0,，且,存在某个非基变量的检验数,k,=,0,，则将,P,k,作为新的基向量得出新的基可行解,X,（,1,）,，满足,z,（,1,）,=,z,（,0,）,，故,z,（,1,）,也,为最优函数值，从而,X,（,1,）,也,为最优解，,X,（,0,）,、,X,（,1,）,连线上所有点均为最优解，因此该线性规划模型具有,无穷多最优解,；,(3),若存在某个,j,0,，但对应的第,j,列系数全非正，即,a,ij,0,，则当,+,时，有,z,（,1,）,+,，,该线性规划模型具有,无界解,。,1.4,单纯形法的计算步骤,1,、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。,不妨假设,A,中前,m,列对应的子矩阵是单位矩阵，取其为基,B,，得到初始基可行解,m+,3,行,n+,4,列,第,1,行：价值行,c,j,第,2,行：变量行,x,j,最后一,行：检验数行,j,第,1,列：基价值列,C,B,第,2,列,：基变量列,X,B,第,3,列,：基解列,b,最后一,列：,比值,列,主体：系数矩阵,A,m,n,2,、单纯形表的结构,3,、初始单纯形表：含初始基可行解的单纯形表,最优单纯形表：含最优解的单纯形表,4,、单纯形法（,Simplex Method,）：,利用单纯形表求解线性规划问题的方法。,5,、单纯形法的计算步骤,(1),化,L.P.,问题为标准形式,建立初始单纯形表；,(3),计算,以,a,lk,为主元素,(,简称主元，用,表示,),，进行线性方程组 的初等行变换，将主元列,P,k,化为单位向量得到新的单纯形表，转入,(2),。,（最大正检验数决定换入变量）,（最小比值,决定换出变量,）,例,1,：用单纯形法求解下列线性规划问题,.,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t.,解：先标准化,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0,4 0 0 1 0,0 5 0 0 1,再列初始单纯形表：,6,-,3,2 3 0 0 0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0 6,4 0 0 1 0 -,0 5 0 0 1 3,2 3 0 0 0,以,5,为主元进行初等行变换,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,3,X,2,6,16,3,2 0 1 0 -2/5 3,4 0 0 1 0 4,0 1 0 0 1/5 -,2 0 0 0 -3/5,x,1,为换入变量,下面开始单纯形法迭代：,x,5,为换出变量,x,2,为换入变量,以,2,为主元进行初等行变换,x,3,为换出变量,主元化为,1,，主元列的其他元素化为,0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,4,3,X,2,3,4,3,1 0,0 -1/5,0 0 -2 1 4/5,0 1 0 0 1/5,0 0 -1 0 -1/5,此时得到唯一最优解,X,*,=(3,3),T,Z,max,=15,。,例,2,用单纯形法求解下列线性规划问题,解：先标准化,2 1 0 0,5,4,x,3,x,4,0,0,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,24,15,3,5,1,0,6,2,0,1,0 0,x,3,x,1,0,2,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,4,3,0,1,4,1,0,1/3,-1/2,1/6,1/3,-1/3,3/4,12,0 0 -1/12 -7/24,x,2,x,1,1,2,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,15/4,3/4,0,1,1/4,-1/8,1,0,-1/12,5/24,唯一最优解,6,、单纯形法中存在的问题,（,1,）存在两个以上的最大正检验数。,任取一个最大正检验数对应的变量作为换入变量。,（,2,）,出现两个以上相同的最小值。,任取一个最小,对应的变量作为换出变量。,此时,L.P.,问题出现退化现象。,练习：,5-1,人工变量法（大,M,法）,1.5,单纯形法的进一步讨论,前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大,M,法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。,例,1,：用单纯形法求解下列线性规划问题。,解：先标准化为,系数矩阵,但是,A,中没有单位矩阵，在,A,中人为的增加两列,此时,对应的约束方程组为,：,该问题新增加了两个变量：,x,4,x,5,（称为人工变量）,A,有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。,为使,必须保证在可行解中人工变量,x,4,=x,5,=,0,，,故令,x,4,，,x,5,在目标函数中的系数为,M,（其中,M,表示任意大的正数），,这种添加人工变量求解,LP,的方法称为,人工变量法,计算过程中出现了,M,，这种方法也称为,大,M,法,。,等价于,于是，这个线性规划问题转化为：,以下可用单纯形法继续求解。,C,j,x,1,x,2,x,3,x,4,X,B,b,C,B,1 1 -1 1 0 1 2 0 0 1,-2 -3 0 -,M,-,M,34,x,4,x,5,-,M -M,c,j,-z,j,-2+2M,-3+3M,-M,0,3/1=3,4/2=2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x,4,x,2,12,c,j,-z,j,-1/2+M/2,0,-,M,0,3/2-3M/2,-,M-,3,24,1 0 -2 2 -1 0 1 1 -1 1,x,1,x,2,21,c,j,-z,j,0 0 -1 1-,M 1-M,-2-3,x,5,0,唯一最优解,故,z,min,=,7,注意：此时人工变量,x,4,=,x,5,=0,说明：,若表中所有,j,0,，但存在非,0,的人工变量，则该模型,无可行解,。,采用大,M,法求解线性规划模型时，如果模型中各个系数与,M,的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大,M,法失效。,在这种情况下，可采用下面的两阶段法进行计算。,5-2,两阶段法,(,将,L.P.,问题分成两个阶段来考虑,),第一阶段,:,判断原,L.P.,问题是否存在可行解。,给原,L.P.,问题加入人工变量，并构造仅含人工变量的目标函数,w,（,人工变量在,w,中的系数一般取为,1,）并求,w,的最小值；然后用单纯形法求解。若求得,w,min,=0,，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。,第二阶段：将第,一,阶段得到的最终表去掉人工变量，并将目标函数还原为原,L.P.,问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。,例：用两阶段法求解下列线性规划问题。,标准化,引入人工变量,z,(1),第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解这个问题，先标准化为；,C,j,x,1,x,2,x,3,x,4,X,B,b,C,B,1 1 -1 1 0 1 2 0 0 1,0 0 0 -,1,-,1,34,x,4,x,5,-,1 -1,c,j,-z,j,2,3,-1,0,3/1=3,4/2=2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x,4,x,2,12,c,j,-z,j,1/2,0,-1,0,-3/2,-1,0,24,1 0 -2 2 -1 0 1 1 -1 1,x,1,x,2,21,c,j,-z,j,0 0 0 -1,-1,0 0,x,5,0,最优解,本问题有可行解，进入第二阶段,(2),第二阶段,先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即,max z,=-2,x,1,-3,x,2,+0,x,3,，,继续迭代：,C,j,x,1,x,2,x,3,X,B,b,C,B,1 0 -2 0 1 1,-2 -3 0,21,x,1,x,2,-2,-3,c,j,-z,j,0,0,-1,唯一最优解,故,z,min,=,7,注意：两阶段法中不再出现大,M,，但需要解两个线性规划问题，要注意目标函数系数的变化。,5-3,关于解的判别,例,7,用单纯形法解下列线性规划,无穷多解,当所有的 ，但某一非基变量检验数 ，存在无穷多最优解的条件是,P,s,列向量中至少存在一个元素 ，且能找出最优解,.,例,8,用单纯形法解下列线性规划,无界解,若存在某个,j,0,，但对应的第,j,列系数全非正，即,a,ij,0,，则问题的解无界,.,例,9,用单纯形法解下列线性规划,无可行解,若表中所有,j,0,，但存在非,0,的人工变量，则该模型无可行解。,用最终单纯形表判断线性规划问题解的类型：,解的类型,最终表的特征,无可行解,有非,0,的人工变量,有,可,行,解,唯一最优解,无,非,0,的人,工变量，非基变量的检验数全为负数,无穷多最优解,无非,0,的人工,变量，非基变量的检验数全非正，且有某个非基变量的检验数为,0,无界解,无非,0,的,人工变量，有某个非基变量的检验数为正数，但该变量对应的系数全为非正数,已知线性规划问题形如：,5-4,单纯形法计算的向量、矩阵描述,引入松弛变量,x,s,记,X=,(,X,B,X,N,X,S,),T,其中，,X,S,为松弛变量，在初始表中是基变量；,X,B,为,最终表中基变量；,X,N,表示,既不是初始表的基变量又不是最终表的基变量。,注意：,X,S,和,X,B,允许有公共变量。,（,2,）,A=,(,B,N,I,),B,N,I,分别为,X,B,、,X,N,、,X,S,在初始表中,对应,的矩阵。,则（,1,）,C=,(C,B,C,N,0),C,B,C,N,0,分别为,X,B,、,X,N,、,X,S,在目标函数中的系数。,（,3,）,A,=,(,I,N,B,-1,),I,N,B,-1,分别为,X,B,、,X,N,、,X,S,在最终表中,对应,的矩阵。,约束方程组两端同时左乘,B,-1,，则可得如下表达式：,初始单纯形表,最终单纯形表,用单纯形表表示如下：,X,S,b,B N I,X,B,b,I N,B,-1,初始表,X,B,X,N,X,S,c,j,-z,j,0,0,N,S,=,（,-y,1,-y,2,-y,m,）,=-Y,T,最终表,X,B,X,N,X,S,c,j,-z,j,B,N,0,0,比较得：,b,=B,-1,b,N,=B,-1,N,或者,P,j,=B,-1,P,j,S,=-C,B,B,-1,=-Y,T,N,=C,N,-C,B,B,-1,N,=C,N,-Y,T,N,或者,j,=C,j,-C,B,B,-1,P,j,其中,B,-1,为初始表中基变量在最终表对应的系数矩阵，,B,为最终表中基变量在初始表对应的系数矩阵。,例：用单纯形法求解下列线性规划问题,.,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t.,解：先标准化,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0,4 0 0 1 0,0 5 0 0 1,得到初始单纯形表：,6,-,3,2 3 0 0 0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,4,3,X,2,3,4,3,1 0,0 -1/5,0 0 -2 1 4/5,0 1 0 0 1/5,0 0 -1 0 -1/5,最终单纯形表：,X,4,0,1,0,X,4,0,1,0,可以验证：,三要素,决策变量,约束条件,目标函数,两,个,三个,以上,x,j,0,x,j,无,约束,x,j,0,b,i,0,b,i,0,=,maxZ,minZ,x,s,x,a,标准化,图解法、,单纯形法,单纯形法,不,处,理,令,x,j,=,x,j,-,x,j,x,j,0,x,j,0,令,x,j,=-,x,j,不,处,理,约束条件两端同乘以,-1,加松弛变量,x,s,加人工变量,x,a,减,去,x,s,加入,x,a,不,处,理,令,z,=-,Z,0,-M,根据上表可以列出初始单纯形表,5-5,单纯形法小结,个数,取值限制,右端常数,约束方向,要求,系数,列初始表,1.7,应用举例,一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：,.,需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；,.,为达到这个目标存在多种方案；,.,要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。,（一）、混合配料问题,例：某糖果厂用原料,A,、,B,、,C,加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规划模型。,甲,乙,丙,原料成本（元,/kg,）,每月限制用量（,kg,）,A,B,C,60,20,30,50,60,2.00,1.50,1.00,2000,2500,1200,加工费（元,/kg,）,0.50,0.40,0.30,售价（元,/kg,）,3.40,2.85,2.25,解：,用,i,=1,2,3,表示原料,A,、,B,、,C,；,用,j,=1,2,3,表示糖果甲、乙、丙；,设,x,ij,为生产第,j,种糖果使用的第,i,种原料的质量，,则该问题的数学模型为：,s.t.,原料供应限制,含量要求条件,用单纯形法求得：,即每月生产甲糖果,kg,，乙糖果,kg,，不生产丙糖果，可获得最大利润为,5450,元。,（二）、投资项目组合问题,例：兴安公司有一笔,30,万元的资金，考虑今后三年内用于下列项目的投资：,1,、三年内每年年初均可投资，每年获利为投资额的,20%,，其本利可一起用于下一年投资；,2,、只允许第一年初投入，于第二年末收回，本利合计为投资额的,150%,但此类投资限额不超过,15,万元；,3,、允许于第二年初投入，于第三年末收回，本利合计为投资额的,160%,，但限额投资,20,万元；,4,、允许于第三年初投入，年末收回，可获利,40%,，但限额为,10,万元,.,试为该公司确立一个使第三年末本利和最大的投资组合方案，,请建立这个问题的线性规划模型。,解：用,x,ij,表示第,i,年初投放到第,j,个项目的资金数，则建立如下线性规划模型：,1,2,3,4,一,二,三,第,i,年初,投入第,j,个项目,1,2,3,4,一,166666.7,133333.3,二,0,200000,三,100000,100000,第三年末本利和,=580000,用单纯形法求得：,综上投资组合方案如下：,(,三）、人力资源分配问题,例,某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,班次,时间,所需人员,1,6:00,10:00,60,2,10:00,14:00,70,3,14:00,18:00,60,4,18:00,22:00,50,5,22:00,2:00,20,6,2:00,6:00,30,设司机和乘务人员分别在各时间段开始时上班，并连续工作,8,小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少,?,解：设,x,i,表示第,i,班次时开始上班的司机和乘务人员人数。,此问题最优解：,x,1,50,，,x,2,20,，,x,3,50,，,x,4,0,，,x,5,20,，,x,6,10,，一共需要司机和乘务员,150,人。,（四）、套裁下料问题,例：现有一批某种型号的圆钢长,8,米，需要截取,2.5,米长的毛坯,100,根，长,1.3,米的毛坯,200,根。问如何才能既满足需要，又能使总的用料最少？,解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出,4,种下料方案以供套裁用。,2.5m,3,2,1,0,1.3m,0,2,4,6,料头,0.5,0.4,0.3,0.2,设按方案,、,、,、,下料的原材料根数分别为,x,j,(j=1,，,2,3,4),，可列出下面的数学模型：,Lingo,软件,LINGO,软件是美国的,LINDO,系统公司（,Lindo System Inc,）开发的一套用于求解最优化问题的软件包,.LINGO,除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解,.LINGO,软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快,.LINGO,内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用,LINGO,高效的求解器可快速求解并分析结果，这里简单介绍,LINGO,的使用方法,.LINGO,可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等,.,LINGO,的语法规定：,（,1,）求目标函数的最大值或最小值分别用,MAX=,或,MIN=,来表示；,（,2,）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（,（,3,）变量名称必须以字母（,AZ,）开头，由字母、数字（,09,）和下划线所组成，长度不超过,32,个字符，不区分大小写；,（,4,）可以给语句加上标号，例如,MAX=200*X1+300*X2,；,（,5,）以惊叹号“！”开头，以分号“；”结束的语句是注释语句；,（,6,）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；,（,7,）,LINGO,模型以语句“,MODEL,：”开头，以“,END”,结束，对于比较简单的模型，这两个语句可以省略,在,LINGO,中的输入如下：,MAX=5*x1+8*X2;,X1+x2 6;,5*x1+,9*X2=45;!,说明：一个约束分成两行写也没有关系,;,END,例,用鼠标点击菜单中的求解命令（,SOLVE,）就可得到解答，结果窗口显示如下：,Global optimal solution found.,Objective value:41.25000,Total solver iterations:2,Variable Value Reduced Cost,X1 2.250000 0.000000,X2 3.750000 0.000000,Row Slack or Surplus Dual Price,1 41.25000 1.000000,2 0.000000 1.250000,3 0.000000 0.7500000,Global optimal solution found”,表示找到了全局最优解。,“,Objective value”,表示最优目标值（,41.25000,）,.,“Total solver iterations”,表示算法的迭代次数。,以下的“,Value”,给出最优解中各变量,(“Variable”),的值,:X1=2.250000,X2=3.750000.,Reduced Cost”,的含义是,(,对,max,型问题,),：基变量的,Reduced Cost,值为,0,；对于非基变量,相应的,Reduced Cost,值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量。本例中两个变量都是基变量，此值均为,0,。,Row Slack or Surplus Dual Price,1 41.25000 1.000000,2 0.000000 1.250000,3 0.000000 0.7500000,Slack or Surplus”,给出对应约束,(“Row”),的松驰（或剩余）变量的值，表示约束是否起作用约束,:,第,2,、,3,行松驰变量均为,0,说明对于最优解而言，两个约束（第,2,、,3,行）均是起作用约束（取等号）。注意：,LINGO,中将目标函数自动看作第,1,行，从第,2,行开始才是真正的约束行,.“Dual Price”,给出约束的影子价格（也称为对偶价格）的值,:,第,2,、,3,行（约束）对应的影子价格分别为,1.250000,，,0.750000,。,