数据模型-线性规划.ppt

线性规划,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论其他应用例子,线性规划问题,问题的提出线性规划问题的数学模型线性规划概念和模型,问题的提出,例1 美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。表1-1,数学模型,例1中先用变量x1和x2分别表示美佳公司制造家电和的数量。这时该公司可获取的利润为(2x1+x2)元，令z=2x1+x2，因问题中要求获取的利润为最大，即max z。z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件。由此例1的数学模型可表为：,数学模型,max:maximize的缩写，“最大化”，s.t.subject to的缩写，“受限制于”,问题的提出,例2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,数学模型,例2中若用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：,概念和模型,定义：对于求取一组变量xj(j=1,2,.,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。,max（或min）,概念和模型,一般形式：,max（或min）,目标函数,约束条件,非负约束,称为决策变量,称为价值系数或目标函数系数,称为资源常数或约束右端常数,称为技术系数或约束系数,概念和模型,紧缩形式：,max（或min）,概念和模型,矩阵形式：,max（或min）,称为决策变量向量,称为价值系数向量或目标函数系数向量,称为资源常数向量或约束右端常数向量,称为技术系数或约束系数矩阵,标准形式,标准型的主要特征：目标最大；约束等式；变量非负；右端非负。,标准型,标准型的紧缩形式：,标准型的矩阵形式：,标准型,标准型的向量形式：,其中：,标准化,把一般的LP化成标准型的过程称为线性规划问题的标准化 方法：1 目标标准化 min Z 等价于 max(-Z)max Z=-cjxj 2 化约束为等式 加松弛变量、减剩余变量 3 变量非负化 做变换 或 4 右端非负,标准化,标准化举例：,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论其他应用例子,图解法,线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。,图解法,例1,运用图解法，以求出最优生产计划（最优解）。,图解法,由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。,1.建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。2.对约束条件加以图解，找出可行域。3.画出目标函数等值线。4.结合目标函数的要求求出最优解。,图解法,图解法,(a)可行域有界(b)可行域有界(c)可行域无界 唯一最优解多个最优解 唯一最优解,(d)可行域无界(e)可行域无界(f)可行域为空集 多个最优解 目标函数无界 无可行解,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,单纯形法原理,线性规划问题的解的概念凸集及其顶点几个基本定理,解的概念,可行解：变量满足所有约束条件的一组值可行解集：所有可行解构成的集合可行域：可行解集构成n维空间的区域,线性规划问题,解的概念,最优解：使得目标函数达到最优的可行解最优值：最优解对应的目标函数值目的：求最优解和最优值求解方法：单纯形法,解的概念,先研究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基本可行解的非零分量均为正分量，其正分量个数 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=X（1）+（1-）X（2）（01）则称X为K的一个顶点（也称为极点或角点）。,凸集的概念,凸集,凸集,不是凸集,基本定理,若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解。,定理1,引理,定理2,定理3,若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。,线性规划问题的可行解x(x1,x2,xn)为基可行解的充要条件是x的正分量所对应的系数列向量是线性独立的。,线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点,解的几何意义,猜想1 线性规划的可行域是凸集；猜想2 最优解若存在，则可以在可行域的顶点上得到；猜想3 可行域的顶点的个数是有限的；猜想4 若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个 猜想5 对于标准型的线性规划X是可行域顶点的充分必要条件是X是基本可行解。,几个事实,线性规划及单纯形法,线性规划问题及数学模型图解法单纯形法原理单纯形法计算步骤单纯形法进一步讨论数据包络分析其他应用例子,基 本 可 行 解 定 义,理 论 方 法,算 法 步 骤,单 纯 形 表,算 例,初 始 单 纯 形 表,迭 代 1,迭 代 2,规 范 形 式 的 对 偶 规 划,一般形式的对偶规划,实 例,对 偶 理 论,灵 敏 度 分 析,概况改变价值向量改变右端向量,概 况,信息的不确定性 信息的变化：价值向量市场变化 右端向量资源变化 系数矩阵技术进步 认知的误差分析方法 静态分析-比较静态分析-动态分析,改变价值向量,一般改变情况 改变非基变量的价值向量 改变基变量的价值向量 算例,一 般 改 变,非 基 变 量,基 变 量,算 例,改变右端向量,基 本 思 想,用Excel“规划求解”工具求解线性规划问题,线性规划问题及其数学模型,例1 某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂应如何安排这两种新产品的生产计划，可使总利润最大？,在该问题中，目标是总利润最大化，所要决策的变量是新产品的每周产量，而新产品的每周产量要受到三个车间每周可用于生产新产品时间的限制。因此，该问题可以用目标、决策变量和约束条件三个因素加以描述。实际上，所有的线性规划问题都包含这三个因素：（1）决策变量是问题中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。（2）目标函数是指对问题所追求的目标的数学描述。例如利润最大、成本最小等。（3）约束条件是指实现问题目标的限制因素。如原材料供应量、生产能力、市场需求等，它们限制了目标值所能到达的程度。,解：例可用下表 表示。,（1）决策变量本问题的决策变量是每周门和窗的产量。可设：x1为每周门的产量（扇）；x2为每周窗的产量（扇）。（2）目标函数本问题的目标是总利润最大。由于门和窗的单位利润分别为300元和500元，而其每周产量分别为x1和x2，所以每周总利润z为：z=300 x1500 x2（元）,（3）约束条件本问题的约束条件共有四个。车间1每周可用工时限制：x1 4车间2每周可用工时限制：2x2 12车间3每周可用工时限制：3x1+2x2 18非负约束:x1 0,x2 0,例 线性规划模型:,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z达到最大时x1，x2的取值。,在Excel电子表格中建立线性规划模型用Excel“规划求解”工具求解线性规划问题,在用电子表格建立数学模型（这里是一个线性规划模型）的过程中，有三个问题需要得到回答：（1）要作出的决策是什么？（决策变量）（2）在作出这些决策时，有哪些约束条件？（约束条件）（3）这些决策的目标是什么？（目标函数）,用Excel“规划求解”工具求解线性规划问题（如果“工具”菜单中没有“规划求解”选项，请参见SOLVER文件夹下的“Excel规划求解工具的安装说明.doc”）,在用Excel的“规划求解”工具求解线性规划问题，为单元格命名能使线性规划问题的电子表格模型更加容易理解。主要表现在两个方面：（1）在公式中使用名称使人们更容易理解公式的含义；（2）在“规划求解参数”对话框中使用名称使人们更加容易理解线性规划模型的含义。所以，一般给跟公式和模型有关的四类单元格命名。例如：在例1.1电子表格模型中，单元格命名如下：（1）数据单元格：单位利润（C4:D4）、可用工时（G7:G9）；（2）可变单元格：每周产量（C12:D12）；（3）输出单元格：实际使用（E7:E9）；（4）目标单元格：总利润（G12）。,1.3 用Excel“规划求解”工具求解线性规划问题,线性规划结束！,