ch1 数学模型及单纯形法

Chapter1 线性规划及单纯形法v 1.1 线性规划问题及数学模型v 1.2 图解法 v 1.3 单纯形法v 1.4 单纯形法的进一步讨论本章主要内容：本章主要内容：page11.1 线性规划问题及数学模型1.1.1 问题的提出v规划问题 Program生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。v线性 linear量与量之间按比例、成直线的关系，在数学上可以理解为一阶导数为常数的函数。page21.1 线性规划问题及数学模型v线性规划 Linear Programming 求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。通常解决下列两类问题：（ 1）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大。）（ 2）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、材料、人工、时间等）去完成确定的任务或目标。page31.1 线性规划问题及数学模型例 1 美佳公司计划制造 、 两种家电产品。已知各制造 1件时分别占用的设备 A， B的台时、调试工序时间及每天可用于这两种家电的能力、各售出 1件时的获利情况，如下表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。page41.1 线性规划问题及数学模型例 2 捷运公司在下一年度的 14月的 4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表 1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表 1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表 1-2 单位： 100m2表 1-3单位：元 /100m2page51.1 线性规划问题及数学模型1.1.2 线性规划问题的数学模型1）线性规划问题的数学定义：求取一组变量 xj (j=1,2,n) ， 使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。怎样辨别一个模型是线性规划模型？（ 1）问题的目标函数是多个决策变量的 线性 函数，通常是求最大值或最小值；（ 2）问题的约束条件是一组多个决策变量的 线性 不等式或等式。page61.1 线性规划问题及数学模型1.1.2 线性规划问题的数学模型2） 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成 例例 1 例例 2决策变量决策变量 Decision variables 目标函数目标函数 Objective function约束条件约束条件 Constraintspage7例 1page8(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max: maximize的缩写， “最大化 ”，s.t. subject to的缩写， “受限制于 ”例 1page9目标函数约束条件 s.t.min： minimize ， “最小化 ”1.1.2 线性规划问题的数学模型目标函数：目标函数：约束条件：约束条件：3）线性规划数学模型的一般形式）线性规划数学模型的一般形式简写为：page101.1.2 线性规划问题的数学模型向量形式：向量形式：其中：page111.1.2 线性规划问题的数学模型矩阵形式：矩阵形式：其中：page121.1 线性规划问题及数学模型v 课堂练习某企业有三个工厂甲、乙、丙生产某种产品销往四个销售点 A、 B、 C、 D。每个计划期内甲乙丙的供应量分别为 150、 200和 250件，销售点 A、 B、 C、 D的需求量分别是 120、 140、 160和 180件。各工厂运送至各销售点 的运价如表所示，试制定总运价最小的调运方案（建立该问题的线性规划模型）。销售点运价（元 /件）工厂A B C D甲 4 6 8 10乙 6 4 10 4丙 8 2 4 6page131.1 线性规划问题及数学模型v1.1.3 线性规划问题的标准形式线性规划问题的标准形式特点：(1) 目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项 bi都大于或等于零(3) 决策变量 xj为非负。page141.1.3 线性规划问题的标准形式如何化标准形式？如何化标准形式？目标函数的转换如果是求极小值即 ，则可将目标函数乘以 (-1)，可化为求极大值问题。也就是：令 ，可得到上式。即若存在取值无约束的变量 ，可令 其中：变量的变换page151.1.3 线性规划问题的标准形式约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量变量 的变换可令 ，显然page16例 3 将下述线性规划化为标准形式 page171.1.3 线性规划问题的标准形式课堂练习 将下列线性规划问题化为标准形式用 替换 ，且 解 :（）因为 x3无符号要求 ，即 x3取正值也可取负值，标准型中要求变量非负，所以page181.1.3 线性规划问题的标准形式(2) 第一个约束条件是 “”号，在 “”左端加入松驰变量 x4，x40,化为等式；(3) 第二个约束条件是 “”号，在 “”左端减去剩余变量 x5，x50；(4) 第 3个约束方程右端常数项为 -5，方程两边同乘以 (-1),将右端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令 z=-z,得到 max z=-z，即当 z达到最小值时 z达到最大值，反之亦然 ;page191.1.3 线性规划问题的标准形式标准形式如下：page20作业v 某药厂生产 A、 B、 C三种药品，有甲乙丙丁四种原料可供选择（原材料供应不限），四种原料成本分别为每公斤 4、 7、 9、 5元。每公斤不同原料提取的各种药品数量 g如下表所示：v 该厂要求每天生产药品 A恰好 115g， B至少 260g， C不超过 130g。使确定各种原料的每天需要量，使每天的总成本最小。试建立该问题的数学模型，并将模型化成标准型。原料每公斤提取药量（ g）药品甲 乙 丙 丁A 2 1 3 2B 6 6 2 5C 3 2 2 3page211.2 图解法v 线性规划问题的求解方法一 般 有两种方法图 解 法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式可行解： 满足所有约束条件的解。可行域： 所有可行解的集合。最优解： 使目标函数达到最大值的可行解。page221.2 图解法v 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。v 图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。其目的表现为：判别线性规划问题的求解结局；若存在最优解，将其找出。page231.2 图解法v图解法的步骤：1）建立平面直角坐标系，标出坐标原点 , 坐标轴的指向和单位长度。2）对约束条件加以图解，找出可行域。 3）画出目标函数等值线。4）结合目标函数的要求求出最优解。page241.2 图解法(1.5c)(1.5a)(1.5b)(1.5d)例 1 用图解法求解线性规划问题page251.2 图解法page261.2 图解法max Z = 2X 1 + X2 X1 + 1.9X2 3.8X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2X1 - 1.9X2 -3.8X1 ， X2 0例 用图解法求解线性规划问题page271.2 图解法x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （ 7.6， 2）Dmax Zmin Z此点是唯一最优解，且最优目标函数值max Z=17.2可行域max Z = 2X1 + X2page281.2 图解法max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（ 7.6， 2）DL0： 0=3X1+5.7X2 max Z（ 3.8， 4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但