《线性规划新》PPT课件.ppt
《《线性规划新》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《线性规划新》PPT课件.ppt(41页珍藏版)》请在三一办公上搜索。
1、线性规划,线性规划简介,线性规划问题最早是前苏联学者康德洛维奇(L.V.Kantorovich)于1939年提出的,但他的工作当时并未广为人知。第二次世界大战中,美国空军的一个研究小组SCOOP(Scientific Computation of Optimum Programs)在研究战时稀缺资源的最优化分配这一问题时,提出了线性规划问题。并且由丹泽()于1947年提出了求解线性规划问题的单纯形法。50年代初,电子计算机研制成功,较大规模的线性规划问题的计算已经成为可能。因此,线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视,得到迅速发展,很快发展成一门完整的学科并得到广泛的应用。
2、1952年,美国国家标准局(NBS)在当时的SEAC电子计算机上首次实现单纯形算法。1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS,后来又发展成为更为完善的MPSX。这些软件的研制成功,为线性规划的实际应用提供了强有力的工具。,随着计算机硬件和软件技术的发展,目前用微型计算机就可以求解变量个数达106,约束个数达104的巨大规模的问题,并且计算时间也不太长。,线性规划问题,根据实际问题的要求,可以建立线性规划问题数学模型。线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。下面列举3种最常见的线性规划问题的类型。,生产计划问题,例1.1 某工厂拥有A、B、C三
3、种类型的设备,生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:,设变量xi为第i种产品的生产件数(i1,2,3,4),目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下,可以建立如下的线性规划模型:,这是一个典型的利润最大化的生产计划问题。其中max表示极大化(maximize),s.t.是subject to的缩写。求解这个线性规划,可以得到最优解为:x1=294.12x2=1500 x3=0 x4=58.82(件)最大利润为z=12737.06(元),背包问题,例1.2 一只
4、背包最大装载重量为50公斤。现有三种物品,每种物品数量无限。每种物品每件的重量、价值如下表所示:,要在背包中装入这三种物品各多少件,使背包中的物品价值最高。,设装入物品1,物品2和物品3各为x1,x2,x3件,由于物品的件数必须是整数,因此背包问题的线性规划模型是一个整数规划问题:,指派问题,例1.3 有n项任务由n个人去完成,每项任务交给一个人,每个人都有一项任务。由第i个人去做第j项任务的成本(或效益)为cij。求使总成本最小(或效益最大)的分配方案。,例如,有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程,每位教师教一门课程,每门课程由一位老师教。根据这四位教师以往教课的情
5、况,他们分别教这四门课程的平均成绩如下表:,四位教师每人只能教一门课,每一门课只能由一个教师来教。要确定哪一位教师上哪一门课,使四门课的平均成绩之和为最高。,设xij(i=1,2,3,4;j=1,2,3,4)为第i个教师是否教第j门课,xij只能取值0或1,其意义如下:,变量xij与教师 i 以及课程 j 的关系如下:,max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1(1)x21+x22+x23+x
6、24=1(2)x31+x32+x33+x34=1(3)x41+x42+x43+x44=1(4)x11+x21+x31+x41=1(5)x12+x22+x32+x42=1(6)x13+x23+x33+x43=1(7)x14+x24+x34+x44=1(8)xij=0,1,这个问题的变量只能取值0或1,这样的线性规划问题成为01规划。,一般的指派问题线性规划模型如下:设:,得到以下的线性规划模型:,由以上3个例子,我们可以归纳出线性规划问题的一般形式:,非线性规划简介,规划问题:在约束条件下求目标函数的最优值点。规划问题包含3个组成要素:决策变量(decision variable)目标函数(ob
7、jective function)约束条件(constraint)当目标函数和约束条件都是决策变量的线性函数时,称为线性规划问题,否则称为非线性规划问题。,3、用MATLAB软件求解线性规划问题,线性规划问题的求解方法包括图解法、单纯形法、矩阵法等.,但在决策变量个数较多,求解过程都比较复杂时,用MATLAB软件求解线性规划问题则比较简单.,MATLAB求解线性规划问题的命令,X=linprog(f,A,b),求解LP问题,命令格式,命令函数 linprog(),X,fval=linprog(f,A,b,Aeq,Beq,LB,UB),求解LP问题,X,fval,exitflag,output,
8、lambda=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options).,其功能是求解有初始值X0和用options指定优化参数进行优化的LP问题.,函数说明(1),f,A,X,b,线性规划的不等式约束条件,Aeq,Beq,线性规划的等式约束条件,目标函数取得极值的决策变量组成的列向量,矩阵,向量,矩阵,向量,目标函数的系数组成的向量,LB,X0,Options,fval,UB,变量的上界约束,变量的初始值,变量的下界约束,控制规划过程的参数系列,优化结束后得到的目标函数值,X,fval,exitflag,output,lambda,=linprog(f,A,b,Aeq,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划新 线性规划 PPT 课件
链接地址:https://www.31ppt.com/p-5589503.html