文档介绍:其中,线性规划是形成最早也是最成熟的一个分支。到目前为止,它的应用也最广泛,是数学规划及运筹学其他分支的基础。线性规划整数规划动态规划零一规划非线性规划目标规划2理论分支理论分支康脱络维奇——论文“生产组织与计划中的数学方法”,1939年。1947年,丹捷格提出了单纯形法第一节线性规划对于一个实际问题,如果采用线性规划去求解,应做两方面的工作,一是把求解问题抽象成能用线性规划来解的数学模型,这就是数学建模。二是对这个线性规划进行求解。(1)引例某军工厂准备用三种原料来制造两种产品,有关数据如下表所示。问如何安排生产,以使总利润达到最大化。单位产品产品消耗量原料(公斤)III原料总量A94360B45200C310300单位产品利润(元)7122线性规划问题的数学模型确定目标:求出生产两种产品的数量各为公斤,以使总利润达到最大。建立数学模型:设I产品生产x1公斤,II产品生产x2公斤MAX总利润Z=7x1+12x2目标是9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2,,x3≥0建立数学模型:设I产品生产x1公斤,II产品生产x2公斤MAX总利润Z=7x1+12x2目标是9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2,,x3≥0以上问题属于线性规划问题,这类问题从数学上讲所具有的共同特征是:1)决策变量。每一个问题都用一组未知数(……xn)表示某一方案,这组未知数的一组定值代表一个具体的规划方案。通常要求这些未知数取值是非负。以后我们称这组未知数为决策变量。2)约束条件。3)目标函数。线性规划问题都有一个目标要求,并且这个目标可以表示为一组未知数的线性函数,称之为目标函数,按研究问题的实际情况目标函数可以是求最小值也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化,而对于成本、费用、支出等指标则希望达到最小化。(2)线性规划问题的共同特征综合上述这三点,这类问题都可以用如下数学语言来描述。 目标函数:max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn≥(=,≤)b1a21x1+a22x2+…a2nxn≥(=,≤)b2……am1x1+am2x2+…amnxn≥(=,≤)bmx1,x2,…xn≥03线性规划问题的标准形式(1)线性规划的标准形式是: 目标函数:maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1,x2,…xn≥0线性规划的标准形式是: maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1,x2,…xn≥0maxZ=xj≥0用求和符号表示标准形式,则标准形式可简写为: