资源描述：
《数学建模优化理论与方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学规划的理论与方法1.线性规划理论与方法2.目标规划的理论与方法3.整数规划的理论与方法非线性规划的理论与方法5.动态规划6.最优控制理论y一.线性规划的理论与方法线性规划是指目标函数是由线性函数给出，约束条件由线性等式或者不等式给出的优化问题。最早提出线性规划问题并进行专门研究的学者—康托洛维奇。康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。自从1947年美国学者丹青格提出求解线性规划问题的一般方法—单纯形方法后，才使线性规划的理论和方法日臻成熟。（1）由决策变量构成，反映决策的目标是线性函数。（2）一组由决策变量的线性等式或不等式构成约束条件。（3）对
2、决策变量取值范围加以限制的非负约束。1.1线性规划模型的特征例1：某工厂生产甲、乙两种产品，每件产品的利润、所消耗的材料、工时及每天的材料限额和工时限额，如表1.1所示。试问如何安排生产，使每天所得的利润为最大？表1.1甲乙限额材料2324工时3226利润(元/件)43设每天生产甲、乙两种产品分别为x1,x2则该问题可描述为由如下数学模型：1.2线性规划问题的标准型如下形式的线性规划模型被称作标准型:也可用矩阵形式描述:A:资源消耗系数矩阵b:资源限量向量C:价格向量X:决策变量向量同时我们对标准型作如下假定:一般的线性规划问题通过变换可化成标准型,变换方式可以归结为:1.3线性
3、规划问题解的概念对于线性规划问题可行解基解基可行解1.4线性规划问题的图解法下面结合例1的求解来说明图解法步骤。例1第一步：在直角坐标系中分别作出各种约束条件，求出可行域（图中阴影部分）。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)第二步：作出一条目标函数等值线，并确定Z值增大的方向。第三步：沿Z值增大方向移动，当移至Q2(6,4)点时，Z值为最大，Z*=36.1.5基本定理从理论上来讲,采用“枚举法”找出所有基可行解,并1.6求解线性规划问题的单纯形方法一一比较,一定会找到最优解。但当m,n较大时,这种方法是不经济和不可取
4、的。下面介绍求解线性规划问题的有效方法——单纯形方法。单纯形法的实质是从一个基可行解向另一个基可行解（极点到极点）的迭代方法。以下通过例1的求解过程说明单纯形方法的基本步骤。例1：第一步：引进松驰变量x3,x4将原问题化为标准型。标准型第二步：找出初始可行基，建立初始单纯形表。见下表1.2。cj4300CBXBbx1x2x3x400x3x4242623103201Z0-4-300表1.2第三步：最优性检验。第四步：换基迭代。cj4300CBXBbx1x2x3x400x3x424262310[3]2011226/3Z0-4-30004x3x120/326/30[5/3]1-2/31
5、2/301/3413Z104/30-1/304/3表1.3同理，确定x2换入，x3换出，继续迭代得表1.3cj4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5Z36001/56/5表1.3表中最后一行的所有检验数都已是正数或零，从而得到基本最优解X*=(6,4,0,0)T,Z*=36。由于x3,x4是引进的松弛变量，因此原问题的最优解为x1=6,x2=4,最优值Z*=36。例2一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1,或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全
6、部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1,设备乙的加工能力没有限制。试为该厂制定一个我们无意过深涉及线性规划的具体计算方法，而着重介绍的是如何建立若干实际的线性规划模型，如何使用现成的数学软件进行求解，以及如何对结果进行深入的分析。下面以奶制品加工生产计划为例，进行详细的讨论。生产计划，使每天获利最大，并进一步讨论以下3个附加问题：若用35元可买到1桶牛奶，买吗？若买，每天最多买多少?若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元
7、?由于市场需求的变化，A1的获利增加到30元/公斤，应否改变生产计划？1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1每天：分析x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2决策变量数学模型原料供应劳动时间加工能力非负约束解法1：图解法。x1x20ABCDl1l2l3l4l5约束条件Z=0Z=2400Z=3360c从图中可以看出，在B(20,30)点得到最优解。解法2：软件实现。求解线
