资源描述:
《数学建模优化课件》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第一章线性优化及其应用§1线性优化问题及其数学模型(一)引例1(生产计划的问题)某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品,已知生产单位产品所需的设备台时,A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多?ⅠⅡ资源限量设备128(台时)原材料A4016(kg)原材料B0412(kg)单位产品利润(元)23该问题可用一句话来描述,即在有限资源的条件下,求使利润最大的生产计划方案。解:设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制,所以有:机器设备的限制条件:x1+2x2≤8
2、原材料A的限制条件:4x1≤16(称为资源约束条件)原材料B的限制条件:4x2≤12同时,产品Ⅰ、Ⅱ的产量不能是负数,所以有x1≥0,x2≥0(称为变量的非负约束)显然,在满足上述约束条件下的变量取值,均能构成可行方案,且有许许多多。而工厂的目标是在不超过所有资源限量的条件下,如何确定产量x1,x2以得到最大的利润,即使目标函数Z=2x1+3x2的值达到最大。综上所述,该生产计划安排问题可用以下数学模型表示:maxz=2x1+3x2引例2.(营养配餐问题)假定一个成年人每天需要从食物中获取3000卡路里热量,55克蛋白质和800毫
3、克钙。如果市场上只有四种食品可供选择,它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小?序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设xj(j=1,2,3,4)为第j种食品每天的购买量,则配餐问题数学模型为minz=10x16x23x32x4(二)线性优化问题的模型上述两例所提出的问题,可归结为在变量满足线性约束条件下,求使线性目标函数值最大或最小的问题。它们具
4、有共同的特征。(1)每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案,其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点,可对变量的取值加以约束,如非负约束。(2)存在一组线性等式或不等式的约束条件。(3)都有一个用决策变量的线性函数作为决策目标(即目标函数),按问题的不同,要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为LP的数学模型,其一般形式为:max(或min)z=c1x1+c2x2+…+cnxn(1.1)(1.3)(1.2)或紧缩形式max(或min)z=(1.4)或矩阵形式max
5、(或min)z=cx(1.5)或向量形式:max(或min)z=cx(1.6)其中C=(c1,c2,…,cn),称为价值系数向量;称为技术系数矩阵(并称消耗系数矩阵)=(p1,p2,…,pn)称资源限制向量X=(x1,x2,…,xn)T称为决策变量向量。(三)线性优化问题的标准型1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便,必须把LP问题的一般形式化为统一的标准型:maxz=cxmaxz=;或maxz=cx或标准型的特点:①目标函数是最大化类型②约束条件均由等式组成③决策变量均为非负④bi(i=1,2,…,n)2.
6、化一般形式为标准型①minz®max(-z)=-cx②“£”®左边+松驰变量;“³”®左边-“松驰变量”③变量xj£0®-xj³0变量xj无限制®令xj=xj¢-xj²④bi<0®等式两边同乘以(-1)。3.模型隐含的假设①比例性假定:决策变量变化的改变量与引起目标函数的改变量成比例;决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数,对资源的消耗也是一个常数。②可加性假定:每个决策变量对目标函数和约束方程的影响是独立于其它变量的。③连续性假定:决策变量应取连续值。④确定性假
7、定:所有的参数(aij,bi,cj)均为确定,所以LP问题是确定型问题,不含随机因素。以上4个假定均由于线性函数所致。在现实生活中,完全满足这4个假定的例子并不多见,因此在使用LP时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时,应考虑使用其它模型和方法。如非线性规划,整数规划或不确定型分析方法。对LP标准型,我们还假定r(A)=m8、行解。所有可行解构成可行解集,即可行域。而使目标函数达到最大值的可行解称为最优解,对应的目标函数值称为最优值。求解LP问题就是求其最优解和最优值,但从代数的角度去求是困难的。2.从LP角度看:基:设A为mxn矩阵,r(A)=m,B是A中的mxm阶非