运筹学课件第一章线性规划及单纯形法详解.ppt

（二）线性规划问题的数学模型 2、线性规划数学模型的一般形式 3、规划类型 二、图 解 法 例4 练习1 四、单纯形法 （三）、单纯形法 其步骤总结如下： （四）、单纯形表 练习 五、单纯形法的进一步讨论 ⑴.大M法： ⑵.两阶段法： （二）、线性规划小结 练习 作业 六、线性规划模型的应用 例题1： 例题2： 例题3： 解：该题有两个限制条件：一个是产量，一个是需量。目标是总运费最省。 设：xij表示从第i个矿山运往第j个铁厂的矿物运量。这样得到以下两组线性方程组： （1）各矿山矿物的生产量与运出量平衡方程： （2）各铁厂矿物供应量与需要量平衡方程 （4）目标函数 （二）资源最优利用的数学模型 例2.3 某厂生产A、 B产品1kg需用资源数见表2-3 ，已知生产A1kg价值7千元，B1kg12千元。应该生产A和B产品各多少才能使总价值最大。 解：设A、B两产品的计划产量为x1、x2 则数学模型为： （三）机床负荷问题的数学模型 例2.4 设某车间需加工甲、乙两种零件。这两种零件可以在三种不同机床——铣床、六角车床、自动机床上进行加工。机床数及生产效率如表2-4。 （三）机床负荷问题的数学模型 此表说明，在一台铣床上一个工作日可以加工15件甲零件或20件乙零件，余类同。该车间共有3台铣床，3台六角车床，1台自动机床。问如何合理安排机床的加工任务，使得在产品配套比例条件下（设甲、乙零件1:1配套），使成套产品的数量达到最大。 解：设xij表示第i种机床用来生产第j种产品的台数，则数学模型为： （1）加工甲、乙产品机床台数平衡方程： （3）变量非负： （四）人员分配的数学模型 例2.5 有四件工作，分配给四人，每人能力不同，工作效率也不同如表2-5，规定每项工作由一个人担任和每个工人只分配一项工作。问应分配哪个人去完成哪项工作可使总效率达到最大。 解：设xij表示i个工人分配担任第j项工作的情况，并xij取1和0两个值， xij=1，表示第i个工人分配担任第j项工作； xij=0，表示i个工人不担任第j项工作。 数学模型： （1）每个工人只担任一项工作 （2）每项工作必由一个工人担任 （五）合理配料问题的数学模型 例2.6 某人每日需服A、B两种维生素，A最少服9个单位，B最少服19个单位，现有六种营养物每克含A、B维生素的单位数和每克价格如表2-6。问此人每天要服用这六种营养物各多少克，才既能获得每日最少所需维生素又使花费最省。 （五）合理配料问题的数学模型 设：六种营养物分别各服用x1g，x2g，x3g，x4g，x5g，x6g。则数学模型： （六）合理下料问题的数学模型 例2.7 某车间有一批长度为180cm的钢管，为着制造零件的需要，要将其截成三种不同长度的管料：70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问题是应如何下料能使消耗的钢管数量最少？ 解：设在180cm长的钢管上能够下出U个70cm的零件，V个52cm的零件和W个35cm的零件，则U、V、W个零件必须符合: 70U+52V+35W≤180 （六）合理下料问题的数学模型 经过试算，可得8种下料方式，见表： 设：x1、x2、x3、x4、x5、x6、x7、x8分别表示这八种下料方式钢管消耗的总根数，则数学模型： 0 1 0 0 x2 -4 -2/3 5/3 -10/3 x1 3 0 0 -Z - 1/3 -1/3 0 0 -2/3 2/3 -1/3 2/3 x2 -4 40 10 -1/3 1/3 1 0 5/3 -5/3 10/3 40/3 10/3 x8 0 4 -1/3 1/3 0 1 -1/3 1/3 -5/3 4/3 x7 -M x10 x9 x8 x7 x6 x5 x3 b xB cB -M 0 0 -M 5 -5 2 cj 4M-4 3 1 1 x2 -4 3-6M -2 1 -4 x1 3 0 -M 0 0 5-3M 3M-5 2-3M -Z 2/3 1 -1 0 0 -2 2 -1 2 x10 -M 14 \ 4 0 0 1 0 1 -1 3 14 \ 4 x8 0 2 0 0 0 1 -1 1 -2 2 x7 -M x10 x9 x8 x7 x6 x5 x3 b xB cB -M 0 0 -M 5 -5 2 cj 0 1 0 0 x2 -4 -31/2 -3/2 5/2 -15/2 x1 3 -M 0 -1/2 -M+9/2 0 0 -17/2 2\ 7 -Z 0 0 1/2 1/2 0 0 1/2 8\ 3 x2 -4 0 0 1/2 -1/2 1 -1 [5/2] 6\ 1 x6