数据模型与决策线性规划

1、第第2 2讲讲 优化问题：线性规划优化问题：线性规划线性规划的基本概念最大化问题的线性规划模型表2.1.1 上海电器厂月生产安排解 ：此问题可用表2.1.1表示表2.1.1 上海电器厂月生产安排决策变量此问题的决策变量是第一个月产品A与 产品B的产量。可设：X为第一个月产品A的产量（件）；Y为第一个月产品B的产量（件）。X、Y即为本问题的决策变量 。目标函数此问题的目标函数是总利润最大。由于产品A与 产品B每件利润分别为3元与8元，而其产量分别为X与Y,所以总利润可计算如下：总利润=3 X+8Y约束条件此问题共有四个约束条件。第一个约束是原材料1的约束。每件产品A与产品B对原材料1的消耗量分别

2、为6与2，而两种产品的产量分别为X与Y，所以该两种产品在第一个月对原材料1的总消耗量为6 X+2Y。由题意，原材料1的可提供量为1800。由此，可得第一个约束如下： 6X+2Y 1800第二个约束是原材料2的约束。由于只有产品B需消耗原材料2，而且单位产品B对原材料2的消耗量为1，产品B的产量为Y。由题意，原材料2的可提供量为350。由此可得第二个约束如下： Y 350第三个约束是劳动时间的约束。由于每单位产品A与产品B对劳动时间的需要量分别为2与4，而两种产品的产量分别为X与Y，所以两种产品在第一个月所需的总劳动时间为2X+4Y。由题意，劳动时间的可提供量为1600。由此可得第三个约束如下：

3、 2X+4Y 1600第四个约束是决策变量的非负约束。由于产量不可能为负值，所以有： X0 ，,Y 0 由上述分析可建立本问题的线性规划模型如下：o.b. max 3X+8Y s.t. 6X+2Y 1800 Y 350 2X+4Y 1600 X， , Y 0最小化问题的线性规划模型 例 贵州金属厂成本优化问题贵州金属厂从、两种矿石中提炼A、B两种金属。已知每吨矿石中金属A、B的含量和两种矿石的价格如表所示。据预测，金属B的需求量不少于420千克，而金属A由于销路问题，该厂决定，其产量不得超过600千克。此外，矿石由于库存积压，要求其使用量不得少于800吨，问应使用各种矿石多少吨，使得在满足要求

4、的前提下总费用最小？ 表 矿石成分与价格表解：根据题意可作如下分析：决策变量本问题的决策变量是两种矿石的使用量。可设：X为矿石的使用量（吨）；Y为矿石的使用量（吨）。目标函数本问题的目标函数是总费用最小。总费用可计算如下：总费用=45X+10Y（元）约束条件本问题共有四个约束。第一个约束是金属A的产量约束，第二个约束是金属B的需求约束，第三个约束是矿石的使用量约束，第四个约束是非负约束。0.40 X + 0.25 Y 6000.42 X + 0.15 Y 420 Y 800 X0, Y0由上述分析，可建立该最小化问题的线性规划模型如下：o.b. Min 45 X + 10 Ys.t. 0.40

5、 X + 0.25 Y 600 （金属A的产量约束） 0.42 X + 0.15 Y 420 （金属B的需求约束） Y 800 （矿石的使用量约束） X0, Y0 （非负约束）所谓的线性规划就是： (1)每一个问题都用一组决策变量（x1, x2, xn）表示某一方案；这组决策变量的值就代表一个方案。一般，这些变量取值是非负的。（2）存在一定的约束条件，这些约束条件是一组关于决策变量的线性等式或线性不等式。（3）都有一个要求达到的目标，目标函数是关于决策变量的线性函数。满足以上三个条件的数学模型称为线性规划的数学模型。它的一般形式为：目标函数 max(min) z=c1 x1+c2x2+cn x

6、n满足约束条件: a11x1+a12x2+a1nxn (,) b1 a21x1+a22x2+a2nxn (,) b2 . . am1x1+am2x2+amnxn (,) bm x1, x2, ,xn 0由此可知，线性规划模型有各种不同的形式，目标函数有的求max，有的求min，约束条件可以是“”，也可以是“ ”不等式，还可以是等式，决策变量一般是非负约束，在实际问题中有一定的意义,但也允许在（，）范围内取值。线性规划的图解法 问题的提出例：某工厂在计划期内要安排例：某工厂在计划期内要安排、两种产品的生产，已两种产品的生产，已知生产单位产品所需的设备台时及知生产单位产品所需的设备台时及A、B两种

7、原材料的两种原材料的消耗、资源的限制，如下表：消耗、资源的限制，如下表：问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能使工厂获产品才能使工厂获利最多？利最多？n线性规划模型：线性规划模型：n 目标函数：Max z = 50 x1 + 100 x2 n 约束条件：s.t. x1 + x2 300n 2 x1 + x2 400n x2 250n x1 , x2 0图解法适用范围图解法适用范围图解法求解过程图解法求解过程x2x1X20X2=0 x2x1X10X1=0100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1

8、+x2=400300200300400100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。图解法的灵敏度分析图解法的

9、灵敏度分析通常，假定系数aij，bi，cj都是常数，而实际上这些系数往往是估计值和预测值。如果市场条件一变， cj值就会变化；工艺条件发生变化会改变aij的值。同样，由于bi是根据资源投入后的经济效果决定的一种决策选择。灵敏度分析就是对系统或事物因周围条件变化显示出来的敏感性程度的分析。提出这样两个问题：当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解、目标值会有什么变化；或者这些系数在什么范围内变化时，线性规划线性规划问题的最优解、目标值不变。灵敏度分析的主要内容包括：（1）灵敏度分析是研究目标函数中的系数变化对最优解与目标值的影响，以及目标函数中的系数改变多少，方可使最优解发

10、生变化。（2）灵敏度分析是研究约束条件右边变化对目标值的影响。影子价格和对偶价格 约束条件右侧（即资源）改变1个单位时，目标函数（即利润）的变化量，它度量了约束条件对应的那种资源的价值，经济学上称为影子价格影子价格。对偶价格：对偶价格：约束条件的右侧值每增加一个单位导致最优解的增加量。对偶价格只适用于约束条件右侧值变化比较小的情况。当资源越来越多时，约束条件右侧的值也越来越大，其它的约束条件就有可能成为紧约束，限制目标函数值的变大。影子价格的主要特点：线性规划在工商管理中的应用线性规划在工商管理中的应用1 1人力资源分配的问题人力资源分配的问题2 2生产计划的问题2 2生产计划的问题3 3套裁

11、下料问题 设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 04 4配料问题 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33； 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求