数学规划课件

第二章数学规划模型

数学规划论起始20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近1/4的问题可用数学规划进行求解。

数学规划模型的一般表达式：

为目标函数，为约束函数，为可控变量，为已知参数，为随机参数。

数学规划分为线性规划、非线性规划、动态规划、随机规划、整数规划、分式规划、几何规划、目标规划、平衡规划、参数规划、多目标规划等十几种。当然这么多规划其中亦有交叉。又可经过组产生新的规划，每一种规划有专著问世。

第一节线性规划模型线性规划模型是运筹学的重要分支，是20世纪三四十年代初兴起的一门学科。1947年美国数学家丹齐格G.B.Dantzig及其同事提出的求解线性规划的单纯形法及有关理论具有划时代的意义。他们的工作为线性规划这一学科的建立奠定了理论基础。随着1979年前苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家卡玛卡尔H.Karmarkar算法的相继问世，线性规划的理论更加完备成熟，实用领域更加宽广。线性规划研究的实际问题多种多样，如生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等。

例2.1生产组织与计划问题。某工厂计划生产甲、乙两种产品，主要材料有钢材3600kg、专用设备能力3000台时。材料与设备能力的消耗定额以及单位产品所获利润如下表所示，问如何安排生产，才能使该厂所获利润最大（只需建立数学模型）。产品单位产品消耗定额材料与设备甲（件）乙（件）现有材料与设备能力钢材（kg）铜材（kg）设备能力（台时）单位产品的利润（元）943600452000310300070120建模过程：设甲、乙两种产品计划生产量分别为和（件），总的利润为（元）。那么我们的任务就是：求变量的值为多少时，才能使总利润最大，由已知条件，，要受下列限制：(1)生产甲、乙两种产品所用钢材的总数不能超过现有钢材数，即(2)生产甲、乙两种产品所用铜材的总数不能超过现有铜材数，即(3)生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，即

(4)甲、乙两种产品的计划生产量不能为负数，即于是问题转化为求解如下的条件极值问题（数学模型）：

例2.2

设有m种物质，第种物资的库存量为，每种物资都可以生产n种产品,第种物资生产第种产品时，每生产单位产品所需物资量为，每种物资生产第种产品时，每单位产品可获利润（表2—2）问如何组织生产才能使利润最大？

用表示生产第种产品计划数，则问题归结为如下数学问题（数学模型）：

约束条件的意义是：每种原料生产n种产品所需要的资源总量不能超过该种资源的库存量；每种产品的生产计划数不能为负。

表2销地单位物资运价产地产量需求量类似的问题很多，诸如下料问题、配料问题、分配问题、工厂选址问题等等。它们的解决都是归结上述的线性规划问题，只是约束条件有的是等式，有的是不等式。通过以上两例可以看出：尽管所提问题的内容不同，但从构成数学问题的结构来看，却属于同一类优化问题，其结构具有如下特征：

（1）目标函数是决策变量的线性函数。（2）约束条件都是决策变量的线性等式或不等式。二、线性规划的解法概述、解的性质及单纯形法我们称如下的条件极值问题

为标准的线性规划问题。

若引进记号则（LP）可简单地表示为进一步，若令，则（LP）可表示为：

对于非标准形式的线性规划，可通过下列办法化成标准形式。①若求,可化为求.②若约束条件中含有不等式或则可引进新变量（称为松弛变量），化为等式约束：或③今后总假定，否则在等式两边乘以-1即可。④若变量无非负限制，则引入两个非负变量与令，便可化为标准形式。解法概述（1）单纯形法：1947年由美国数学家Dantzig提出，虽然在特殊情况下可能出现循环，但这种方法仍是目前求解线性规划问题最常用的方法。事实上在大量的实际问题计算中看出，循环情况从未出现过（仅在特意构造下才能出现）。它是一种迭代方法。（2）椭球法：1977年由前苏联数学家khachiyan提出的多项式时间算法，它在理论上保证了多项式时间算法的存在性。但大量数值研究发现，对于大多数实际问题，椭球法在计算上不如单纯形方法。线性规划问题的软件解法求解线性规划的常用方法是1947年G.B.Dantzig提出的单纯形法。这种方法是以寻找最优解的迭代过程为主线。基本思路是：给出一个基可行解（一个顶点）后，判断其是否为最优解；若它不是最优解，可用迭代的方法转换到另一个基可行解（顶点），最终找到使目标函数值更优的基可行解。经过有限次迭代后，这一迭代过程以找到最优解或判定问题无最优解为目标。另外，求解线性规划的方法还有Karmarkar算法和椭球算法。求解线性规划的软件很多，下面介绍Mathematica和MATLAB软件。Mathematica和MATLAB求解Mathematica命令可用于求解各种形式的线性规划问题的命令。命令的输入格式：

c=c1x1+c2x2+…+cnxn；

m={a11x1+a12x2+…+a1nxn<=b1，

…

am1x1+am2x2+…+amnxn<=bm}；用于求极小值的命令：

ConstrainedMin[c，m，{x1,x2,…,xn}]用于求极大值的命令：

ConstrainedMax[c，m，{x1,x2,…,xn}]MATLAB命令

命令输入格式及线性规划模型如下：其中：x0是算法迭代的初始点；nEq表示等式约束的个数。三、建模举例例2.4营养配餐问题。每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表2-3中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20kg，其它蔬菜的供应在一周内不多于40kg，每周共需供应140kg蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少kg？

问题分析与模型建立设分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：

约束条件：铁的需求量至少6个单位数：磷的需求量至少25个单位数：维生素A的需求量至少17500个单位：维生素C的需求量至少245个单位：烟酸的需求量至少5个单位数：

每周需供应140千克蔬菜，即

0≤x1≤400≤x2≤400≤x3≤400≤x4≤200≤x5≤400≤x6≤40

b=(-1)*[140;6;25;17500;245;5];

xLB=zeros(6,1);

xUB=[40;40;40;20;40;40];

nEq=1;

x0=0*ones(6,1);

x=lp(c,A,b,xLB,xUB,x0,nEq);

disp('青豆需要的份数')

x(1)disp('胡罗卜需要的份数')

x(2)disp('菜花需要的份数')x(3)disp('白菜需要的份数')x(4)disp('甜菜需要的份数')x(5)disp('土豆需要的份数')x(6)执行后输出青豆需要的份数ans=

40胡罗卜需要的份数ans=

40.0000菜花需要的份数

ans=

0白菜需要的份数

ans=

20.0000甜菜需要的份数

ans=

0土豆需要的份数ans=

40最小费用

ans=

560.0000四、整数线性规划在许多线性规划模型中，变量取整数时才有意义。例如，不可分解产品的数目，如汽车、房屋、飞机等，或只能用整数来记数的对象。这样的线性规划称为整数线性规划，简称整数规划，记为IP。整数规划分为两类：一类为纯整数规划，记为PIP，它要求问题中全部变量都取整数；另一类是混合整数规划，记之为MIP，它的某些变量只能取整数，而其他变量则为连续变量。整数规划的特殊情况是0-1规划，其变量只取0或者1；图论中的一些问题（如背包问题等）也可用0-1规划来描述。

在整数规划模型中，若每一变量只取0或1，即为0-1规划模型。0-1规划模型因其特殊性，又不同于整数规划的解法。如一般0-1规划的隐枚举法，指派问题中的匈牙利法，背包问题则可以用动态规划的方法求解。下面的几个例子说明了0-1规划在实际问题中的使用。例5.2背包问题有n件物品，编号为1，2，…，n。第件重为kg，价值为元。今一装包者欲将这些物品装入一包，其质量不能超过kg，问应装入哪几件价值最大？

解引入变量

将物品装包不将物品装包于是得问题的模型为

取0或1，i=1，2，…，n背包问题看似简单，但应用很广，例如某些投资问题即可归入背包问题模型。此类问题可以

描述为：设有总额为元的资金，投资几项事业，第项副业需投资元，利润为元问应选择哪些项总利润为最大？

例2.6某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为，相应的钻探费用为，并且井位选择要满足下列限制条件：

（1）或选和，或选；（2）选择了或就不能选，反之亦然；（3）在中最多只能选两个。试建立其数学模型：

解引入变量

选择不选择

于是以上问题的数学模型为：

例2.7指派问题。有项任务，由个人来完成，每人只能干一件，第个人完成第项任务需要的时间为小时，问怎样安排能使总用时最少？

解引入0-1型变量

人完成任务人不去完成任务

于是该问题的数学模型为

整数规划的解法较复杂，主要有分枝定界法、割平面法，隐枚举法及解指派问题的匈牙利法等。

分配甲、乙、丙、丁去完成A、B、C、D四项任务，每人完成一项，每项任务只能由一个人去完成，试做出任务分配使总时间最少。（个人完成各项任务如下表）个人完成各项任务如下表任务人员

AB

C

D甲86109乙912711丙7435丁95811编写Lingo程序如下model:sets:worker/w1..w4/;job/j1..j4/;