线性规划的标准型和基本概念.ppt

1线性规划的标准型和基本概念?线性规划问题及其数学模型?线性规划的图解法?线性规划的标准形式?标准型线性规划的解的概念?线性规划的基本理论?问题的提出:在生产管理的经营活动中,通常需要对“有限的资源”寻求“最佳”的利用或分配方式。?有限资源:劳动力、原材料、设备或资金等?最佳:有一个标准或目标,使利润达到最大或成本达到最小。有限资源的合理配置有两类问题?如何合理的使用有限的资源,使生产经营的效益达到最大;?在生产或经营的任务确定的条件下,合理的组织生产,安排经营活动,使所消耗的资源数最少。?线性规划问题及其数学模型例1,某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每周可提供的资源总量如下表所示:1515设备(台班)1602030维生素(公斤)乙甲每周资源总量每吨产品的消耗已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果,甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大?定义x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数。.(subject to) (such that) 1 21 21 211 2maxZ=5x +2x30x 20x 1605x x 15x 4x 0, x 0? ???? ??????? ??1515设备(台班)25单位利润(万元)1602030维生素(公斤)乙甲每周资源总量每吨产品的消耗5?例2靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天500万m3,在两个工厂之间有一条流量为200万m3的支流。。从第一化工厂排出的工业污水流到第二化工厂以前,有20%可以自然净化。%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下,每厂各应处理多少工业污水,使这两个工厂处理工业污水的费用最小工厂1工厂2200万m3500万m36决策变量:x1、x2——分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数:min z=1000x1+800x2约束条件:第一段河流(工厂1——工厂2之间):(2-x1)/500 ≤%第二段河流:[ (2-x1) +(-x2)]/700≤%此外有:x1≤2;x2≤:min z=1000x1+800x2 x1≥1 + x2≥ x1≤2 x2≤ x1、x2≥0称之为上述问题的数学模型。例3,某铁器加工厂要制作100套钢架,,。,问应如何下料,可使材料最省??分析:在长度确定的原料上截取三种不同规格的圆钢,可以归纳出8种不同的下料方案:0301Ⅰ(米)ⅦⅦⅥⅤⅣⅢⅡ圆钢(米)问题归纳为如何混合使用这8种不同的下料方案,来制造100套钢架,且要使剩余的料头总长为最短。设xj表示用第j种下料方案下料的原料根数,j=1,2…8,.?这是一个下料问题,是在生产任务确定的条件下,合理的组织生产,使所消耗的资源数最少的数学规划问题。?满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最小值。1 2 3 4 5 6 7 81 2 4 63 4 5 6 7 1 2 3 5 6 8jminZ=x +x +x +x +x +x +x +xx 2x x x 100 2x 2x x x 3x 1003x x 2x 3x x 4x 100 x 0 j 1,2 8 ,? ? ????? ??????? ???????? ???,0301Ⅰ(米)