第一章线性规划第一章1.1线性规划问题及其数学模型.ppt

第一章、、线性规划问题的提出——利用有限资源某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台数及A、B两种原材料的消耗量,见表1-1。该工厂每生产一件产品Ⅰ可获利润2元,每生产一件产品Ⅱ可获利润3元,问应如何安排生产计划使该工厂获得的利润最大?生产计划问题产品资源ⅠⅡ资源限量设备(台时)128原材料A(g)4016000原材料B(g)0412000如何制定生产计划,使两种产品总利润最大?利用有限资源:某鸡厂共饲养1万只鸡,用大豆和谷物混合喂养,已知鸡消耗饲料1kg/天,鸡至少需要蛋白质、、,每公斤大豆含蛋白质、钙为50%、%,每公斤谷物含蛋白质、钙为10%、%,、。饲料成分大豆谷物营养/%10%≥%%≥:每只鸡需要大豆x1公斤,谷物x2公斤,=³≥++=2,1,..≥++=121xx=³≥++=2,1,×10000..≥+×+=1000021xx设:养鸡场每天需要大豆x1公斤,谷物x2公斤二、线性规划的定义和数学描述(模型):对于求取一组变量xj(j=1,2,......,n),使之既满足线性约束条件,又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题,简称线性规划(LP)。:用一组未知变量表示要求的方案,这组未知变量称为决策变量;存在一定的限制条件,且为线性表达式;有一个目标要求(最大化,当然也可以是最小化),目标表示为未知变量的线性表达式,称之为目标函数;对决策变量有非负要求。(数学模型):(1)一般形式+++=…)(2211nnxcxcxcZMinMax或≥=+++≥=+++≥=++0,,,),(),(),(..21221122222**********nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≤≤≤≥(2)紧缩形式=≥=≥==∑==njxmibxatsxcZMinMaxjnjijijnjjj,2,10,2,1),(..)(11或≤∑……(3)矩阵形式其中:),,(…=T=),,(21nxxxX…Tmbbbb),,,(21…==mnmmnnaaaaaaaaaA…………………212222111211