数学建模：线性规划问题(超全)

《数学建模：线性规划问题(超全)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回第一节线性规划问题及其数学模型问题的提出例:生产计划问题产品I产品2如何安排生产使利润最大？决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足

2、约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步-确定决策变量设——I的产量——II的产量——利润第2步--定义目标函数MaxZ=x1+x2决策变量MaxZ=2x1+3x2系数第2步--定义目标函数对我们有何限制?第3步--表示约束条件x1+2x284x1164x212x1、x20该计划的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x2线性规划问题的共同特征一组决策变量X表示一个方案,一般X大于等于零。约束

3、条件是线性等式或不等式。目标函数是线性的。求目标函数最大化或最小化线性规划模型的一般形式ïïïîïïïíì³³=£+++³=£+++³=£++++++=0,...,,),(......................................................),(...),(......)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax线性规划问题的标准形式标准形式为:目标函数最大约束条件等式决策变量非负简写为用矩阵表示C—价值向量b—资源向量X—决策变量

4、向量minZ=CX等价于maxZ’=-CX“”约束：加入非负松驰变量一般线性规划问题的标准化例：目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20minZ=CX等价于maxZ’=-CX“”约束：加入非负松驰变量一般线性规划问题的标准形化例：“”约束：减去非负剩余变量；Max例：可正可负（即无约束）；解：标准形为线性规划模型举例(一)运输问题(二)布局问题(三)分派问题(四)生产计划问题(五)合理下料问题线性规划模型的条件（1）要求解问题的目标函数能用数值指标来反映，且为线性函数；（2）存在着多种方案；（3）要求达到的目标是在一定约束

5、条件下实现的，这些约束条件可用线性等式或不等式来描述。(一)运输问题设某种物资有m个产地，A1，A2，…，Am；联合供应n个销地：B1，B2，…，Bn。各产地产量（单位：吨），各销地销量（单位：吨），各产地至各销地单位运价（单位：元／吨）如下表所示。应如何调运，才使总运费最少？表中：ai表示产地Ai的产量(i=1，2，…，m)；bj表示产地Bj的产量(j=1，2，…，n)；cij表示AiBj间的单位运价（元／吨）(i=1，2，…，m;j=1，2，…，n)；单价（元／吨）销地产地产量（吨）B1B2…BnA1A2┇Am销量（吨）C11C12…C1nC21C22…C2n┇┇…┇Cm1Cm

6、2…Cmnb1b2…bna1a2┇am设xij表示由产地Ai运往销地Bj的物资数(i=1,2,…,m;j=1,2,…,n)。那么，上述运输问题的数学模型为：求一组变量xij(i=1,2,…,m;j=1,2,…,n)的值,使它满足即(一)运输问题(Ⅰ)产销平衡(Ⅰ)产销平衡(Ⅱ)产销不平衡约束条件产地Ai发到各销地的发量总和应等于Ai的产量各产地发到销地Bj的发量总和应等于Bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型约束条件产地Ai发到各销地的发量总和应等于Ai的产量各产地发到销地Bj的发量总和应等于Bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型(Ⅰ)产销平衡的模型()()()

7、njmixnjbxmiaxijijiijmijnj,,1;,,2,10,,2,1,,2,111LLLL==³====åå==约束条件()()()njmixnjbxmiaxijijiijmijnj,,1;,,2,10,,2,1,,2,111LLLL==³====åå==(Ⅰ)产销平衡的模型这一问题的数学模型应为：求一组变量的值,使它满足(Ⅱ)产销不平衡—产大于销(一)运输问题调运量不能为负数(Ⅱ)产销不平衡—产大于销的模型产地Ai发到各销地的发量总和不超过Ai的产量各产