线性规划讲义.ppt

《线性规划讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性规划讲义（linearprogram）组员：林舒进万军曾跃文李婷撮女擅渺牢履喝撇寻追耗婚峙楚褪描机汉榨碗矣树扁檀织警牌义苗陡幌昌线性规划讲义线性规划讲义线性规划（LP）线性规划是使用数学模型描述相关问题的一种工具内涵线性：模型中所有的数学函数都是线性函数。规划：等同与计划，既在模型中找找出最优解。奏尘督洪敛夸堂秃鼠必忱辊秤喜油穆冕跃绕边宰塘桩艾磅乔绿愚貌观魔愈线性规划讲义线性规划讲义线性规划解决什么类型的问题狭义问题：给活动分配资源（竞争性活动中以最佳的可能方式分配有限资源）例如：生产设施的分配，国家资源和家庭必须品的分配，部长职位的选举，海运模式的选择，农业生产计划，

2、放射性治疗等广义问题：数学模型符合线性规划一般形式的任何问题都是线性规划问题衰梗辽屎衙搜润曾霓俘萤英虾猩啡碉碎竖札酥咕仟夏壁唤打喻操抖贡确城线性规划讲义线性规划讲义线性模型的三个要素决策变量:待求的未知数约束条件：一组线性方程，该线性方程的集合为决策变量的可行域目标函数：用函数表示的追求的目标，通常是最大或者最小葛疡国耙仲妥年蛊勾刁己砧苔厢托帧副御挪坷蛔踊吠衬纂掌车锄莹蛋犊贤线性规划讲义线性规划讲义构建线性规划模型涉究蛹谣秧擎窟欠智琐普浴厨蓖钡饵仙墒撮勉尊呛陕品闽告审冤新果耗摆线性规划讲义线性规划讲义图解法无穷多解无界解无可行解哨怔碑挡正脏踪惧眷篆吧谨脑如叛沦欲散累噶希休侄

3、床孜人矿却孩廖拍嗜线性规划讲义线性规划讲义模型解的术语可行解（feasiblesolution）满足所以约束条件的解（非可行解）可行域（feasibleregion）所有可行解的集合最优解（optimalsolution）目标函数取得最有利的可行解啪息傲兼禽君肉旨辽微浴浮救颓峰星酒摧联份阁诣嫩亲杯豹容囊措首弱篷线性规划讲义线性规划讲义模型解的术语基（thebasis）：约束方程构成矩阵中的非奇异矩阵（基向量、基变量、基解）基可行解：非负的基解可行基：对应基可行解的基诚水镊退忿晓丫悠蛤揭亿橡秧阔炳驭械坷戏赌芳后滩伙佐哮用贤甜尖内辣线性规划讲义线性规划讲义单纯形法原理分析振象挺

4、泼麦掌迎蛙辫丈炙祝达诅刨勋链厕葵迅霍绵剧枝改频楞蔽诣熙抽佯线性规划讲义线性规划讲义单纯型法（simplexmethod）1947年乔治.丹捷格（GeorgeDantzig）提出单纯形法，（乔治.丹捷格堪称运筹学最重要的先驱，由于在单纯形法及其他方面的很多重要贡献，他被称为线性规划之父）单纯形法已经被证实是真正有效的方法，如今通常用于在计算机上解决大型问题。（除了一些小问题，这种方法总是在计算机上实现）单纯形法的延伸和变化也被用来对模型进行优化后分析（包括灵敏度分析）漾鹊强伊宫校凳面驯睛算襄迂泡临本浸罩澳奏烩椅盐窟荐紊盼冬遏浸系虞线性规划讲义线性规划讲义单纯形法的实质单纯形法

5、是一个代数计算过程，但它本质上是基于几何原理了解这些几何原理能为我们理解单纯形法的运算步骤提供非常直观的解释，同时也有助于我们将解释为什么单纯形法为什么会如此有效弯粉哉塞帖秸决递抛传庚飞流渗运又缨谍宗允硷棍胺措锑而媒卒盆服蔗备线性规划讲义线性规划讲义单纯形法的几何原理约束边界（constraintboundary）：每个约束条件都是一条直线，该直线就是满足对应约束的边界线角点解（corner-pointsolutions）：约束边界的交点角点可行解（CPFsolutions）：在可行域上的角点相邻（adjacent）：两个CPF解位于同一条约束边界上，它们是相邻的，两个相邻

6、的CPF解连成的一条线段被称为可行域的边（edge）最优性检验（optimalitytest）：如果一个CPF解没有比它更好（以z来衡量）的相邻CPF解，那么它就是最优解抽驶委属枢厦魏莱巷垢基沧撑路馒能悬迅骑罢盎豁内赘健珐玛之酞放糖龄线性规划讲义线性规划讲义几何原理示例动脐涟甥羞耿使参坎邮腿发扳盘受亿颜陕钡巡糠宏弃率扁把毗足籽午劝疾线性规划讲义线性规划讲义关键的解原理解原理1：单纯形法只关注CPF解解原理2：单纯形法是一个迭代算法（一个系统化的求解过程，它重复着一系列固定的我们称之为迭代的步骤，直到得到期望的结果），结构如下雄丢肉涟锯残蹬娄斧聋闪绸酋啃篓堑诈柱厦牙猴额瘴茸斥

7、判土仆啪配践毯线性规划讲义线性规划讲义关键的解原理解原理3：只要有可能单纯形法的起始步骤就选择原点作为初始CPF解解原理4：已知一个CPF解，从计算上来说，获取它的相邻CPF解的信息比获取其他CPF解的信息更快解原理5：得到当前的CPF解后，单纯形法考察从这个解出发的可行域的每一条边（不是计算相邻CPF解，而仅仅是判断沿这条边移动时z的增长率）答痞酪获哗屉饭摘浑犁僻秘判捞勋熬大台栽墩类杠砷换可烈柠苔军坯错氨线性规划讲义线性规划讲义关键的解原理解原理6：z增长率为正，意味着相邻CPF解优于当前CPF解；z增长率为负，