数学建模优化理论与方法.pptxVIP

一.线性规划的理论与方法 线性规划是指目标函数是由线性函数给出，约束条件由线性等式或者不等式给出的优化问题。 最早提出线性规划问题并进行专门研究的学者—康托洛维奇。 康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。 自从1947年美国学者丹青格提出求解线性规划问题的一般方法—单纯形方法 后，才使线性规划的理论和方法日臻成熟。1.1 线性规划模型的特征 （1）由决策变量构成，反映决策的目标是线性函数。（2）一组由决策变量的线性等式或不等式构成约束 条件。（3）对决策变量取值范围加以限制的非负约束。例1：某工厂生产甲、乙两种产品，每件产品的利润、所消耗的材料、工时及每天的材料限额和工时限额，如表1.1所示。试问如何安排生产，使每天所得的利润为最大？表1.1甲乙限额材料2324工时3226利润(元/件)43 设每天生产甲、乙两种产品分别为 x1 , x2 则该问题可描述为由如下数学模型：1.2 线性规划问题的标准型 如下形式的线性规划模型被称作标准型:也可用矩阵形式描述:A:资源消耗系数矩阵b: 资源限量向量C:价格向量X:决策变量向量同时我们对标准型作如下假定: 一般的线性规划问题通过变换可化成标准型 , 变换方式可以归结为:1.3 线性规划问题解的概念 对于线性规划问题基解可行解基可行解x23x1+2x2=26Q3(6,4)Q2(6,4)2x1+3x2=24Zx1OQ1(26/3,0)1.4 线性规划问题的图解法 下面结合例1的求解来说明图解法步骤。例1第一步：在直角坐标系中分别作出各种约束条件，求出可行域（图中阴影部分）。第二步：作出一条目标函数等值线，并确定 Z 值增大的方向。第三步：沿 Z 值增大方向移动，当移至 Q2(6,4) 点时，Z 值为最大，Z*=36 .1.5 基本定理 从理论上来讲,采用“枚举法”找出所有基可行解,并 一一比较,一定会找到最优解。但当 m, n 较大时,这种方法是不经济和不可取的。 下面介绍求解线性规划问题的有效方法——单纯形方法。单纯形法的实质是从一个基可行解向另一个基可行解（极点到极点）的迭代方法。1.6 求解线性规划问题的单纯形方法 以下通过例1的求解过程说明单纯形方法的基本步骤。例1：第一步：引进松驰变量 x3 , x4 将原问题化为标准型。标准型第二步：找出初始可行基，建立初始单纯形表。 见下表1.2。表 1.2 cj 4 3 0 0CBXBb x1x2x3x400x3x42426 2 3 1 0 3 2 0 1Z0 -4 -3 0 0第三步：最优性检验。 第四步：换基迭代。表1.3 cj 4 3 0 0CBXBb x1x2x3x400x3x42426 2 3 1 0 [3] 2 0 11226/3Z0 -4 -3 0 004x3x120/326/3 0 [5/3] 1 -2/3 1 2/3 0 1/3413Z104/3 0 -1/3 0 4/3同理，确定 x2 换入，x3 换出，继续迭代得表 1.3表 1.3 cj 4 3 0 0CBXBb x1x2x3x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5Z36 0 0 1/5 6/5 表中最后一行的所有检验数都已是正数或零，从而得到基本最优解 X*=(6,4,0,0)T, Z*=36 。由于 x3 , x4 是引进的松弛变量，因此原问题的最优解为 x1=6, x2=4, 最优值 Z*=36 。 我们无意过深涉及线性规划的具体计算方法，而着重介绍的是如何建立若干实际的线性规划模型，如何使用现成的数学软件进行求解，以及如何对结果进行深入的分析。 下面以奶制品加工生产计划为例，进行详细的讨论。例2 一奶制品加工厂用牛奶生产 A1 , A2 两种奶制品，1 桶牛奶可以在设备甲上用 12 小时加工成 3 公斤 A1,或者在设备乙上用 8 小时加