线性代数第7章.ppt

第七章线性规划线性规划研究的主要问题一类是已有一定数量的资源(人力、物质、时间等),研究如何充分合理地使用它们,才能使完成的任务量为最大。——实际上,上述两类问题是一个问题的两个不同的方面,都是求问题的最优解(maxf或minf)。另一类是当一项任务确定以后,研究如何统筹安排,才能使完成任务所耗费的资源量为最少。1939年,前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题1947年,美国数学家丹茨格(Dantzig)提出求解线性规划的单纯形法1950-1956年,主要研究线性规划的对偶理论1958年,发表整数规划的割平面法1960年,Dantzig和Wolfe研究成功分解算法,奠定了大规模线性规划问题理论和算法的基础。1979年,Khachiyan,1984年,Karmarkaa研究成功线性规划的多项式算法。,下表给出了单位产品所需资源及单位产品利润问:应如何安排生产计划,才能使总利润最大?§、问题的提出解::设产品I、II的产量分别为x1、:设总利润为z,则有:maxz=2x1+:x1+2x2≤84x1≤164x2≤12x1,x2≥,这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量要求:生产A种药物至少160单位;B种药物恰好200单位,C种药物不超过180单位,且使原料总成本最小。解::设四种原料的使用量分别为:x1、x2、x3、:设总成本为z,则有:minz=5x1+6x2+7x3+:x1+2x2+x3+x4≥1602x1+4x3+2x4=1603x1+x2+x3+2x4≤180x1、x2、x3、x4≥0药物原料ABC单位成本(元/吨)甲1235乙2016丙1417丁1228模型特点1都用一组决策变量X=(x1,x2,…,xn)T表示某一方案,且决策变量取值非负;———满足以上三个条件的数学模型称为线性规划2都有一个要达到的目标,并且目标要求可以表示成决策变量的线性函数;3都有一组约束条件,这些约束条件可以用决策变量的线性等式或线性不等式来表示。:目标最小化、约束为等式、变量均非负、右端约束常数非负。,要求右端项必须每一个分量非负,当某一个右端项系数为负时,则把该等式约束两端同时乘以-1,得到:(1)设约束条件为:可以引进一个新的变量使得:显然,也具有非负约束,即≥0(2)当约束条件为:如果原问题中有若干个非等式约束,则将其转化为标准形式时,必须对各个约束引进不同的松弛变量。可以引进一个新的变量使得:显然,也具有非负约束,即≥0为了使约束由不等式成为等式而引进的变量,称为“松弛变量”。