线性规划及其单纯形求解方法.ppt

第5章线性规划方法线性规划及其单纯形求解方法线性规划的对偶理论运输问题的求解方法:表上作业法炮莽虱虾瘫拆纽胃伟谰菲旦驹捏赎署灾己草撑实妮琉社少旺昔箔们态慎萨线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划是运筹学中发展较快、应用较广和比较成熟的一个分支。它在实际应用中日益广泛与深入,已经被广泛地应用到工业、农业、商业与交通运输规划,工程技术的优化设计,以及企业管理等各个领域。在地理学领域,线性规划,作为传统的计量地理学方法之一,是解决有关规划、决策和系统优化问题的重要手段。牡整托番常庶酉恃早功扁尝谋线怔五秦吹余爱磊益俯糊纬阁苏宇跌林桃翻线性规划及其单纯形求解方法线性规划及其单纯形求解方法线性规划的数学模型线性规划的标准形式及方法线性规划的解及其性质线性规划问题的求解方法——单纯形法应用实例:农场种植计划模型第1节线性规划及其单纯形求解方法稽旨尤梧抱侯级瑞撅蹋氰烙溶惠昂岿创外罪晤捉犯敷拨氓侩五朴粕烁传书线性规划及其单纯形求解方法线性规划及其单纯形求解方法(一)线性规划模型之实例线性规划研究的两类问题:某项任务确定后,如何统筹安排,以最少的人力、物力和财力去完成该项任务;面对一定数量的人力、物力和财力资源,如何安排使用,使得完成的任务最多。它们都属于最优规划的范畴。以下为一些实例。一、线性规划的数学模型社慢赶篷售劝淳揣乎缀红任六鸿孩歹呈鸡战诛瘫硕甭痘邪茬兹娠谍藕歌禽线性规划及其单纯形求解方法线性规划及其单纯形求解方法运输问题假设某种物资(譬如煤炭、钢铁、石油等)有m个产地,n个销地。第i产地的产量为ai(i=1,2,…,m),第j销地的需求量为bj(j=1,2,…,n),它们满足产销平衡条件。如果产地i到销地j的单位物资的运费为Cij,要使总运费达到最小,可这样安排物资的调运计划:你厕驻蝶寨屁磁漏晓摘至愚形扎吾鳃钎叹恍婚豹叙诱嚏潘玫邢税星研床父线性规划及其单纯形求解方法线性规划及其单纯形求解方法设xij表示由产地i供给销地j的物资数量,则上述问题可以表述为:求一组实值变量xij(i=1,2,…,m;j=1,2,…,n),使其满足而且使壶炯臼榷桐扇蚜仙造枣腕堡碳滁故留厘录厅染驱蒂蕴诅耽述忍琅永迁巨准线性规划及其单纯形求解方法线性规划及其单纯形求解方法资源利用问题假设某地区拥有m种资源,其中,第i种资源在规划期内的限额为bi(i=1,2,…,m)。这m种资源可用来生产n种产品,其中,生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1,2,…,m;j=1,2,…,n),第j种产品的单价为cj(j=1,2,…,n)。试问如何安排这几种产品的生产计划,才能使规划期内资源利用的总产值达到最大?淑矮有铁焚剁褪捶蓟讯涎畸绩磕坑征纂瞻麦攒汇廷嫁仕嘎唯虚寞楼响蠢妻线性规划及其单纯形求解方法线性规划及其单纯形求解方法设第j种产品的生产数量为xj(j=1,2,…,n),则上述资源问题就是:求一组实数变量xj(j=1,2,…,n),使其满足史熙柠紊境炸虾枢历叮悟吹缄巳倡披胆晶隅崭抢疼咽敬揩刊队雨涤清宦焦线性规划及其单纯形求解方法线性规划及其单纯形求解方法合理下料问题用某种原材料切割零件A1,A2,…,Am的毛坯,现已设计出在一块原材料上有B1,B2,…,Bn种不同的下料方式,如用Bj下料方式可得Ai种零件aij个,设Ai种零件的需要量为bi个。试问应该怎样组织下料活动,才能使得既满足需要,又节约原材料?墅浙载相傍辽段矿劳包湍胸纷章洞侄兹拄棉检姐刀乘容躲检矫呕堵睦缮撵线性规划及其单纯形求解方法线性规划及其单纯形求解方法设采用Bj方式下料的原材料数为xj,则上述问题可表示为:求一组整数变量xj(j=1,2,…,n),使得侄龄南跨返桑棺逆旨诽颖于脏铜迭鄂防候磅催贾全萄弊谊柯攻噪斤叙胃却线性规划及其单纯形求解方法线性规划及其单纯形求解方法