数学建模 线性规划模型.doc

数学建模教案－线性规划模型 　　　　　　　　　　　　　　 一、问题的提出 在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财 力等资源，以便得到最好的经济效果。 例1　　　 若需在长为4000mm的圆钢上 ，截出长为698mm和518mm两种毛坯，问怎样 截取才能使残料最少？ 初步分析 可以先考虑两种“极端”的情况： （1）全部截出长为698mm的甲件，一共可截出 EQ F(4000,698) ?5件，残料长为510mm。 （2）全部截出长为518mm的乙件，一共可截出 EQ F(4000,518) ?7件，残料长为374mm。 由此可以想到，若将 x个甲件和y 个乙件搭配起来下料，是否可能使残料减少？把截 取条件数学化地表示出来就是： 　　　　　　　　　　 698 x + 518y ￡ 4000 　　　　　　　　　　 x ，y都是非负整数 　　　 目标是使：z = EQ F(698x + 518y,4000) （材料利用率）尽可能地接近或等于1。（尽可能地大） 　　　 该问题可用数学模型表示为： 　　　 目标函数　　：　 max z = EQ F(698x + 518y,4000) 　　　 满足约束条件：　　698 x + 518y ￡ 4000 ， (1) 　　　　　　　　　　 　　　　　x ，y都是非负整数 .　 (2) 例2　 某工厂在计划期内要安排生产I 、II两种产品，已知生产单位产品所需的设备台 数及A、B两种原料的消耗，如下表所示。 　　　 　　　 I 　　　 　　　 II 设备 　　　 　　　 1 　　　 　　　 2 　　　 　 　　8台数 原材料A 　　　 　　　 4 　　　 　　　 0 　　　 　　　 16kg 原材料B 　　　 　　　 0 　　　 　　　 4 　　　 　　 12kg 　 该工厂每生产一件产品I可获利 2 元，每生产一件产品II可获利 3 元，问应如何安排生产计划使工厂获利最多？ 这问题可以用以下的数学模型来描述：设 x 1, x 2分别表示在计划期内产品I、II的产量。因为设备的有效台数为8 ，这是一个限制产量的条件，所以在确定I 、II的产量时，要考虑不超过设备的有效台数，即可用不等式表示为： 　　　　　　　　　　　　　　　　　　　　　　　　　　　 x 1 + 2x 2 ￡ 8 . 同理，因原材料A 、B的限量，可以得到以下不等式： 　　　　　　　　　　　　　 4 x 1 　　　　￡ 16 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　 4 x 2 ￡ 12. 　　　 该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x 1、x 2以得到最大的利润。若用 z 表示利润，这时z = 2x 1 + 3 x 2 。综上所述，该计划问题可用数学模型表示为： 　　　 目标函数　 ：　　 max z = 2x 1 + 3 x 2 　　　 满足约束条件：　　 x 1 + 2x 2 ￡ 8 　　　　　　　　　　　 4 x 1 　　　　￡ 16 　　　　　　　　　　　　　　　　　　　　 　 　　　 　　　4 x 2 ￡ 12. 　　　　　　　　　　　　　 x 1 ，x 2 3 0 　　　 该模型的特征是： （1）有一组决策变量（x 1 ,x 2 ,…,x n)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。 （2）存在一定的约束条件，这些约束条件可用一组线性等式（不等式）来表示。 （3）有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求实现目标函数最大化或最小化。 满足以上三个条件的数学模型称为线性规划模型。其一般形式为： 目标函数 　： 　max(min) z = c 1x 1 + c 2x 2 + …+ c nx n 　　　　　　　 a11x 1 + a12x 2 +….+ a13x n ￡ (= , 3) b 1 　　　　　　　a21x 1 + a22x 2 +…. + a23x n ￡ (= , 3) b2 满足约束条件：　 … …　 　　　　　　　a m1x 1 + a m2x 2 +….+ a m3x n ￡ (= , 3) b m 　　　　　　　　　　　　　x 1 ,x 2 ,…, x n 3 0 二、　　　　　　 穷举法 以例1为例介绍穷举法。 先根据（1）求出x 所有可能的取值为：0、1、2、3、4、5，再由（1）把相应y 的最 大值求出，对应为7、6、5、3、2、0，依此计算住z值如下表： x 　 0 　 1 　 2 　 3 　 4 　 5 y 　 7 　 6 　 5 　 3 　 2 　 0 z 90.65% 95.15% 99.