数据模型——线性规划

《数据模型——线性规划》由会员分享，可在线阅读，更多相关《数据模型——线性规划（86页珍藏版）》请在金锄头文库上搜索。

1、线性规划线性 规划 及单 纯形 法v线性规划问题及数学模型 v图解法 v单纯形法原理 v单纯形法计算步骤 v单纯形法进一步讨论 v其他应用例子线性规划问题 问题的提出 线性规划问题的数学模型 线性规划概念和模型问题的提出例1 美佳公司计划制造、两种家电 产品。已知各制造一件时分别占用的设 备A，B的台时、调试工序时间及每天可 用于这两种家电的能力、各售出一件时 的获利情况，如表1-1所示。问该公司 应制造两种家电各多少件，使获取的利 润为最大。表1-1数 学 模 型例1中先用变量x1和x2分别表示美佳 公司制造家电和的数量。这时 该公司可获取的利润为(2x1+x2)元 ，令z=2x1+x2，因

2、问题中要求获取 的利润为最大，即max z。 z是该公司能获取的利润的目标值， 它是变量x1，x2的函数，称为目标 函数。 x1，x2的取值受到设备A、B和调试工 序能力的限制，用于描述限制条件 的数学表达式称为约束条件。 由此例1的数学模型可表为：数学模型(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max: maximize的缩写， “最大化”， s.t. subject to的缩写， “受限制于”问 题 的 提 出例2 捷运公司在下一年度的14月的4个月内 拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期 而定，期限越长，折扣越大，具体数字见

3、表1-3。租借仓库的合同每月初都可办理， 每份合同具体规定租用面积和期限。因此 该厂可根据需要，在任何一个月初办理租 借合同。每次办理时可签一份合同，也可 签若干份租用面积和租借期限不同的合同 ，试确定该公司签订租借合同的最优决策 ，目的是使所付租借费用最小。表1-2单位：100m2表1-3 单位：元/100m2数 学 模 型例2中若用变量xij表示捷运公司在第i(i=1,4)个月初签订的 租借期为j(j=1,4)个月的仓库面积的合同。因5月份起该公 司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。 该公司希望总的租借费用为最小，故有如下数学模型：目标函数约束条件 s

4、.t.min：minimize ， “最小化”概 念 和 模 型定义：对于求取一组变量xj(j=1,2,n) ，使之既满足线性约束条件，又使 具有线性的目标函数取得极值的一 类最优化问题称为线性规划问题。max（或min） 概 念 和 模 型一般形式：max（或min） 目标函数约束条件非负约束 称为决策变量 称为价值系数或目标函数系数 称为资源常数或约束右端常数 称为技术系数或约束系数 概 念 和 模 型紧缩形式：max（或min） 概 念 和 模 型矩阵形式：max（或min） 称为决策变量向量 称为价值系数向量或目标函数系数向量 称为资源常数向量或 约束右端常数向量 称为技术系数或约束系

5、数矩阵 标 准 形 式标准型的主要特征： 目标最大； 约束等式； 变量非负； 右端非负。标 准 型标准型的紧缩形式：标准型的矩阵形式：标 准 型标准型的向量形式：其中：标准化 把一般的LP化成标准型的过程称为线性规划问题的 标准化 方法：1 目标标准化min Z 等价于 max ( - Z )max Z=-cjxj2 化约束为等式加松弛变量、减剩余变量3 变量非负化做变换或4 右端非负标 准 化标准化举例： 线性 规划 及单 纯形 法v线性规划问题及数学模型 v图解法 v单纯形法原理 v单纯形法计算步骤 v单纯形法进一步讨论 v其他应用例子图 解 法线性规划的图解法就是用几何作图的方法分析并求

6、出其最优解的 过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解 的集合（即可行域），然后结合目 标函数的要求从可行域中找出最优 解。图 解 法例1运用图解法，以求出最优最优生产计划 （最优解最优解）。 (1.1c)(1.1a)(1.1b)(1.1d)图 解 法由于线性规划模型中只有两个决策 变量，因此只需建立平面直角坐标系就 可以进行图解了。1.1.建立平面直角坐标系，标出坐标原点坐标原点, 坐标轴的指向坐标轴的指向和单位长度单位长度。 2.2.对约束条件加以图解，找出可行域。 3.3.画出目标函数等值线。 4.结合目标函数的要求求出最优解。图 解 法(1.1c)(1.1a)(1

7、.1b)(1.1d)图 解 法(a)可行域有界 (b)可行域有界 (c)可行域无界唯一最优解多个最优解 唯一最优解(d)可行域无界 (e)可行域无界 (f)可行域为空集多个最优解 目标函数无界 无可行解线性 规划 及单 纯形 法v线性规划问题及数学模型 v图解法 v单纯形法原理 v单纯形法计算步骤 v单纯形法进一步讨论 v数据包络分析 v其他应用例子单纯形法原理 线性规划问题的解的概念 凸集及其顶点 几个基本定理解 的 概 念可行解：变量满足所有约束条件的一组值可行解集：所有可行解构成的集合可行域：可行解集构成n维空间的区域 线性规划问题解 的 概 念最优解：使得目标函数达到最优的可行解 最优

8、值：最优解对应的目标函数值 目的：求最优解和最优值 求解方法：单纯形法解的概念先研究AX=b 设 系数矩阵A是mn矩阵，秩为m， B是A中mm阶非奇异子矩阵（即|B|0），则 称B是线性规划问题的一个基。 B 是由m个线性独立的列向量组成基向量基变量非基变量： 其余变量解 的 概 念AX=BXB+NXN=b 令 非基变量XN=0 得BXB=b 和特解XB =B-1b结合XN=0 称为对应于B的基本解； 基本解个数=基的个数Cnm 基可行解 可行的基本解XB0 XN=0 可行基：对应于基可行解的基A=（B | N）解 的 概 念最优基：对应的基本可行解也是最优 基本可行解个数基的个数Cnm基本可

9、行解的非零分量均为正分量，其正分量个数 m。退化的基本可行解：基本可行解的非零分量个数小于 m时，也就是在基本可行解中一个 或多于一个的基变量取零值时凸 集 及 其 顶 点基本概念： 凸集设K是n维欧氏空间的一个点集，若任意两点X（1）K，X（2）K的连线上的一切点：X（1）+（1-）X（2） K（01），则称K为凸集。凸 集 的 概 念顶点顶点设K是凸集，XK；若K 中不存在两个不同的点X（1） K，X（2） K 使X=XX=X（1 1）+ +（1-1-）X X（2 2） （ 0101）则称X为K的一个顶点（也称为 极点或角点）。 凸 集 的 概 念凸集凸集不是凸集顶点基 本 定 理若线性规

10、划问题有最优解，一定存在一个基可行解（可行域 顶点）是最优解。定理定理1 1引理引理定理定理2 2定理定理3 3若线性规划问题存在可行解，则该问题的可行解集（即可行域） 是凸集。线性规划问题的可行解x(x1, x2, xn)为基可行解的充要条 件是x的正分量所对应的系数列向量是线性独立的。线性规划问题的基可行解x对应线性规划问题可行域(凸集) 的顶点解 的 几 何 意 义猜想1 线性规划的可行域是凸集； 猜想2 最优解若存在，则可以在可行域的顶点上得到； 猜想3 可行域的顶点的个数是有限的； 猜想4 若有两个最优解，则其连线上的点也是最优解， 即最优解有无穷多个 猜想5 对于标准型的线性规划X

11、是可行域顶点的充分必要 条件是X是基本可行解。几个事实线性 规划 及单 纯形 法v线性规划问题及数学模型 v图解法 v单纯形法原理 v单纯形法计算步骤 v单纯形法进一步讨论 v数据包络分析 v其他应用例子单 纯 形 算 法 理论方法 算法步骤 单纯形表 算例基 本 可 行 解 定 义理 论 方 法算 法 步 骤单 纯 形 表算 例初 始 单 纯 形 表迭 代 1迭 代 2对 偶 理 论 对偶规划 对偶理论 对偶单纯形算法规 范 形 式 的 对 偶 规 划一般形式的对偶规划实 例对 偶 理 论计算典式检验数否算 法 过 程初始正则解检查可行是则停止 得最优解选出基变量检查 是否无可 行解是则停止

12、否无最优解选入基变量灵 敏 度 分 析 概况 改变价值向量 改变右端向量概 况 信息的不确定性信息的变化：价值向量市场变化右端向量资源变化系数矩阵技术进步认知的误差 分析方法静态分析- 比较静态分析-动态分析改变价值向量v 一般改变情况v改变非基变量的价值向量v改变基变量的价值向量v算例一 般 改 变非 基 变 量基 变 量算 例改 变 右 端 向 量基 本 思 想用Excel“规划求解”工具求解线性规划问题线性规划问题及其数学模型u例1 某工厂要生产两种新产品：门和窗。经测算 ，每生产一扇门需要在车间1加工1小时、在车间3 加工3小时；每生产一扇窗需要在车间2和车间3各 加工2小时。而车间1

13、每周可用于生产这两种新产品 的时间为4小时、车间2为12小时、车间3为18小时 。已知每扇门的利润为300元，每扇窗的利润为500 元。而且根据经市场调查得到的该两种新产品的市 场需求状况可以确定，按当前的定价可确保所有新 产品均能销售出去。 u问该工厂应如何安排这两种新产品的生产计划， 可使总利润最大？u在该问题中，目标是总利润最大化，所要决策的变量 是新产品的每周产量，而新产品的每周产量要受到三 个车间每周可用于生产新产品时间的限制。因此，该 问题可以用目标、决策变量和约束条件三个因素加以 描述。 u实际上，所有的线性规划问题都包含这三个因素： （1）决策变量是问题中有待确定的未知因素。例

14、如决定企 业经营目标的各产品的产量等。 （2）目标函数是指对问题所追求的目标的数学描述。例如 利润最大、成本最小等。 （3）约束条件是指实现问题目标的限制因素。如原材料供 应量、生产能力、市场需求等，它们限制了目标值所能到 达的程度。解：例可用下表 表示。车间单位产品的生产时间（小时）每周可获得的生产 时间（小时）门窗11042021233218单位利润（元）300500（1）决策变变量本问题问题 的决策变变量是每周门门和窗的产产量。可设设：x1为为每周门门的产产量（扇）；x2为为每周窗的产产量（扇）。（2）目标标函数本问题问题 的目标标是总总利润润最大。由于门门和窗的单单位 利润润分别为别为

15、 300元和500元，而其每周产产量分别为别为 x1和x2，所以每周总总利润润z为为：z = 300x1500x2 （元）（3）约束条件本问题的约束条件共有四个。车间1每周可用工时限制：x1 4车间2每周可用工时限制：2x2 12车间3每周可用工时限制：3x1 +2x2 18非负约束:x1 0, x2 0例 线性规划模型: 这是一个典型的利润最大化的生产 计划问题。其中，“Max”是英文单 词“Maximize”的缩写，含义为“最大 化”； “s.t.”是“subject to”的缩写，表示“满 足于”。因此，上述模型的含义 是：在给定的条件限制下，求使得 目标函数z达到最大时x1，x2的取值 。u在Excel电子表格中建立线性规划模型u用Excel“规划求解”工具求解线性规划问题u在用电子表格建立数学模型（这里是一个线性规划模型）的过程中，有三个问题需要得到回答：（1）要作出的决策是什么？（决策变量）（2）在作出这些决策时，有哪些约束条件？（约束条件）（3）这些决策的目标是什么？（目标函数）u 用Excel“规划求解”工具求解线性规划问题（如果“工具”菜单中没有“规划求解”选项，请参见SOLVER文件夹下的