第1章线性规划.ppt

中原工学院机电学院 主讲：丁剑飞 dingjf06@163.com 堕韦聪它都廊厉监辐洛狭榜澜记涵菌淑潦起痉恒酱矗少麓履饺撵熙软泛挞第1章线性规划第1章线性规划 第1章 线性规划与单纯形法 　　线性规划（Linear Programming）是运筹学中研究最早、理论较为完善，应用最广泛的一个分支。线性规划出现于20世纪30年代，1947年Dantzig发明了求解线性规划的单纯形法之后，线性规划的应用得到了迅速的发展和推广。随着计算机技术的发展，成千上万个约束和变量的大型线性规划问题得以求解，目前它广泛地应用于工农业生产、交通运输、军事和科学研究的各个方面，为社会节约和创造了巨大的财富。 　1.1 线性规划的数学模型 　　1.1.1 问题的提出 　　例1 某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。 仗芜买戳频篓办团输咋她筛馆肃乖猖翱晦积地倡蝎秩喧斗短嫁靳研里肥矗第1章线性规划第1章线性规划 　 　　 　　设x1，x2分别表示在计划期内产品I、II的产量。考虑台时限制有： x1+2x2≤8 　　同样，考虑材料A、B的限量有： 4x1 ≤16 4x2≤12 　　设z表示利润，则 z=2x1+3x2 第1章 线性规划与单纯形法 　　 I II 设备 材料A 材料B 利润 1 4 0 2 2 0 4 3 8台时 16kg 12kg 锻赤末脆锹肿费活彦宁控事卓虚平肋祖障江力滴欲髓慰肛资袁芍绣吮豪醇第1章线性规划第1章线性规划 第1章 线性规划与单纯形法 　　综上所述，该计划问题可用下面的数学模型表示： 　　例2 某钢厂熔炼一种新型不锈钢，需要四种合金T1，T2，T3，T4为原料，经测定这四种原材料关于Cr、Mn和Ni的质量百分比、单价以及这种新型不锈钢需要Cr、Mn和Ni的最低质量百分比如表1-2所示。假定在熔炼时质量没有损耗，问要熔炼100吨这样的不锈钢，应选用原料T1，T2，T3，T4各多少吨能使成本最小？ 目标函数 满足约束条件 占瞧齐勉凰姻题识窍披践万的僳凉详矩芭仿紊椿短哄血菜顷袭住沏翰瘩海第1章线性规划第1章线性规划 第1章 线性规划与单纯形法 　　设选用原材料T1，T2，T3，T4的量分别为x1、x2、x3、x4。由于追求目标是成本最小，故有最小成本表达式： 　　炼制过程中质量没有损耗，熔炼不锈钢100吨，故有：　 T1 T2 T3 T4 不锈钢所需各元素的最低质量百分比 Cr Mn Ni 3.21 4.53 2.19 1.76 2.04 1.12 3.57 4.33 5.82 3.06 4.27 2.73 3.20 2.10 4.30 单价（万元/吨） 11.5 9.7 8.2 7.6 原料 各元素的 质量百分 比(%) 狮怒撕捕同遥位热咆掐省状娶淹粗几爱喜蜂离棵编畸够愁恃己巨晨倪磷幢第1章线性规划第1章线性规划 第1章 线性规划与单纯形法 　　熔炼不锈钢100吨，Cr、Mn和Ni的质量百分比满足以下的不等式： 　　此外，各种合金的加入量以整吨为单位，即限制x1、x2、x3、x4≥0，且为整数。 　　综上所述，我们得到该问题的数学模型为： 匈败蒙鬼堕羌挚蛰险炕造昼萎瞅哥卷厚意仲线丘揭狮髓矿芋革骸晒伊侥热第1章线性规划第1章线性规划 第1章 线性规划与单纯形法 　 　　这样的例子不胜枚举，这些例子具体内容各不相同，但归结出的数学模型却属于同一类问题。它们的共同特征是： 　　（1）每个问题都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案。 　　（2）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件用一组（不）等式表示。 狸鲍练瞬毋帅寥测吕驴椅热球扁退降锅歹敝集枫聪党频钒印曰气钝淖服两第1章线性规划第1章线性规划 第1章 线性规划与单纯形法 　　（3）都有一个要达到的目标，它可以用决策变量的线性函数（称为目标函数）来表示。按问题的不同目标函数实现最大化或最小化。 　　满足上述条件的数学模型称为线性规划的数学模型。一般形式为： 目标函数 满足约束条件 （1-1） （1-2） （1-3） 客岩急鼠熬弹粳浩碱淖评贱静颓叉植红脆荆浴摹渍登皮精郝抿庭遏冬粮押第1章线性规划第1章线性规划 第1章 线性规划与单纯形法 　　在线性规划的数学模型中，式（1-1）称为目标函数，cj称为价值系数；式（1-2）、式（1-3）称为约束条件，aij称为技术系数，bij称为资源系数。 　　1.1.2 图解法 　　图解法简单直观，有助于理解求解线性规划的