数学建模优化080420课件

数学建模-------优化模型第二讲线性规划建模方法第三讲整数规划建模方法第四讲指派问题第六讲图论简介第五讲动态规划建模第一讲数学建模概论第一章数学建模概论1.1数学建模由来1.2从现实对象到数学模型1.3数学建模的重要意义1.4数学建模的方法和步骤1.5数学模型的特点和分类1.6近几年国内竞赛题1.7怎样学习数学建模与竞赛组队1.8撰写数学建模论文玩具、照片、飞机、火箭模型……~实物模型地图、电路图、分子结构图……~符号模型模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物模型集中反映了原型中人们需要的那一部分特征1.2从现实对象到数学模型我们常见的模型你碰到过的数学模型——“航行问题”用x表示船速，y表示水速，列出方程：答：船速每小时20千米/小时.甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?x=20y=5求解航行问题建立数学模型的基本步骤作出简化假设（船速、水速为常数）；

用符号表示有关量（x,y表示船速和水速）；

用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程）；

求解得到数学解答（x=20,y=5）；

回答原问题（船速每小时20千米/小时）。数学模型(MathematicalModel)和数学建模（MathematicalModeling)对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。建立数学模型的全过程（包括表述、求解、解释、检验等）数学模型数学建模数学建模的具体应用

分析与设计

预报与决策

控制与优化

规划与管理数学建模计算机技术知识经济如虎添翼数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用数学建模的一般步骤数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)表述求解解释验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践现实世界数学世界理论实践1.6近几年全国大学生数学建模竞赛题1.7怎样学习数学建模与竞赛组队数学建模与其说是一门技术，不如说是一门艺术技术大致有章可循艺术无法归纳成普遍适用的准则想像力洞察力判断力

学习、分析、评价、改进别人作过的模型

亲自动手，认真作几个实际题目•

如果可能的话，最好是数学好的懂得编程的一些知识，编程好的了解建模，搞论文写作也要了解建模，这样会合作得更好。因为数学好的在建立模型方案时会考虑到编程的便利性，以利于编程；编程好的能够很好地理解模型，论文写作的能够更好、更完全地阐述模型。否则会出现建立的模型不利于编程，程序不能完全概括模型，论文写作时会漏掉一些不经意的东西。•在合作的过程中，最好是能够在三人中找出一个所谓的组长，即要能够总揽全局，包括任务的分配，相互间的合作和进度的安排。•在建模过程中出现意见不统一——如何处理？仅我个人的经验而言，除了一般的理解与尊重外，我觉得最重要的一点就是“给我一个相信你的理由”和“相信我，我的理由是……”，不要作无谓的争论。

第二讲线性规划建模方法一、从现实问题到线性规划模型二、线性规划模型的求解三、线性规划建模实例四、线性规划的对偶问题例1加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/公斤，应否改变生产计划？每天:一、从现实问题到线性规划模型1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天A1A2现有资源设备128台时甲4016公斤乙0412公斤利润2030（元）制订生产计划,使每天获利最大例2工厂生产两种产品A1,A2,已知生产单位产品情况如表：设生产A1、A2分别x1、x2公斤

maxz=20x1+30x2(1)目标函数约束条件决策变量一、从现实问题到线性规划模型线性规划模型标准型:maxz=c1x1+c2x2+…+cnxn(LP)线性规划模型标准型矩阵表示：maxz=c

x

max(min)z=c1x1+c2x2+…+cnxn线性规划模型一般形式：1.线性规划的一般形化为标准型一般步骤(1)Minz=cx转化为maxz’=-cx(2)加松弛变量yi

(3)加剩余变量yi(4)若存在可正可负变量xi令

maxz=20x1+30x2(1)标准型(1),

x1+2x2+x3=8(2),4

x1+0

x2+x4=16(3),0x1+4x2+x5=12

maxz=20x1+30x2

x1+2x2+x3=84

x1+0

x2+x4=160x1+4x2+x5=12x1,x2,x3,x4,x5s.t例将下述线性规划问题化为标准型Minz=-

x1+2x2-3x3无约束标准型maxz’=

x1-2x2+3(x4–x5)+0x6+0x7(1),x3=

x4-x5,x4,x5(2),

x1+x2+x3+x6=7(3),

x1-x2+x3-x7=2合理下料问题有长度为8米的某型号圆钢，现需要长度为2.5米的毛坯100根，长度为1.3米的毛坯200根，如何选者下料方式，所需总用料最省？解：可能的下料方式：2.51.3130222314406设按第i种下料方式的圆钢xi根，i=1,2,3,4

minz=x1+x2+x3+x4有一组决策变量,约束条件是决策变量的线性等式或不等式,目标函数是决策变量的线性函数,这样的规划问题称为线性规划.记为（LP）例.某小区一个24小时营业便利店,一天各时段所需服务员最少人数如下表.根据实际情况,要求每个服务员必须连续工作八小时,试建立需服务员总人数最少的排班方案数学模型.班次123456时间2-66-1010-1414-1818-2222-2人48107124解：设各班次新增服务员数分别为x1,x2,x3,x4,x5,x6,则minz=

x1+x2+x3+x4+x5+x6且xi为整数连续投资问题某部门计划5年内用一百万投资下列项目：A：从第一年到第四年初需投资，此年末回收本利115%B:第三年初需投资，第五年末回收本利125%，投资额≤40万C:第二年初需投资，第五年末回收本利140%，投资额≤30万D：每年初可购买公债，当年末归还，利息6%如何投资，五年后获利最大？解：设第i年初投资项目A,B,C,D分别为xiA,xiB,xiC,

xiD万元,i=1,2,3,4,5x1A+x1D=100,x2A+x2C+x2D=1.06x1D,x3A+x3B+x3D=1.06x2D+1.15

x1A,x4A+x4D=1.06x3D+1.15

x2A,x5D=1.06x4D+1.15

x3A,x2C≤40,x3B≤30,xiA,xiB,xiC,

xiD≥0i=1,2,3,4,5.MaxZ=1.15x4A+1.40x2C+1.25x3B+1.06x5Ds.t.二、线性规划模型的求解（一）图解法（n<=3时）（二）单纯形法（三）数学软件：如LINDO软件maxz=c

x(LP)可行解：满足约束条件AX=b,X最优解:可行解中使目标最优的。即X*∈D,且任意X∈D,CX*≥CX可行集：所有可行解的集合的X的值A1A2现有资源设备128台时甲4016公斤乙0412公斤利润2030（元）制订生产计划,使每天获利最大工厂生产两种产品A1,A2,已知生产单位产品情况如下：设生产A1、A2分别x1、x2公斤

maxz=20x1+30x2(1)（一）图解法（n<=3时）(1)在平面上作出可行集ABCD34Z=60Z=140Z=0由图解法直观得:n=2时,(LP)的可行集是凸多边形,最优解可以在其某个顶点处达到.线性规划基本性质:(LP)的可行集是凸多面体,最优解可以在凸多面体的某个顶点处达到.线性规划求解思路:通过代数的方法描述高维空间凸多面体的顶点,再使用经济的方法来求出达到极值的顶点.x1x20(2)在可行集中找最优解

maxz=20x1+30x2(1)（二）单纯形法1.基、基本可行解的概念(顶点的代数描述)2.单纯形法一般步骤引入松弛变量x3,x4,x5,化为标准形:显然A的秩为3,任取3个线性无关的列向量,如P1,P2,

P3称为一组基,记为B=(P1,P2,

P3)。P1,P2,

P3

称为基向量,

基向量对应的变量x1,x2,x3称为基变量,其余列向量

P4,

P5

称为非基向量,

记为N=(P4,

P5).非基对应的变量x4,x5称为非基变量.A=(B,N),相应x=(xB,xN)T,c=(cB,cN)令非基变量xN

=0,解得基变量xB=B-1b,称(xB,xN)为基解.Ax=BxB+NxN=b,则xB=B-1b-B-1NxN,解的所有变量的值都非负，则称为基可行解，此时的基称为可行基.于是f=cBxB+cNxN,Ax=BxB+NxN=b,

则xB=B-1b-B-1NxN,f=cBB-1b+(cN–cBB-1N)xN

将A写成A=(B,N),相应x=(xB,xN)T,c=(cB,cN)基对应的变量xB称为基变量,非基对应的变量xN称为非基变量.令非基变量xN=0,解得基变量xB=B-1b,称(xB,xN)为基解.解的所有变量的值都非负，则称为基可行解，此时的基称为可行基.基可行解对应的目标值为f=cBB-1b。

若可行基进一步满足:cN–cBB-1N≥0,则对一切可行解x,必有f(x)≥cBB-1b,此时称基可行解x=(B-1b,0)T为最优解.另一个基本可行解定理：(LP)的可行集的顶点与(LP)的

基本可行解一一对应。单纯形法基本思想：目标重复此更优过程单纯形法基本步骤：不是最优解更优目标重复此过程(LP)的某个基本可行解最优解(LP)的某个基基可行解另一个基基本可行解最优解4.基可行解是最优解的判定准则因为f=cBB-1b+(cN–cBB-1N)xN，即f-0•xB+(cBB-1N-cN)xN=cBB-1b5.基可行解的改进改进方法：返回Maxz=2x1+3x2+x3解:本题特点是约束方程系数矩阵含单位子矩阵1111014701

A=()1001

B0=(P4,P5))=(X0=(0,0,0,3,9)TZ0=8Maxz=2x1+3x2+x3A1A2利润甲112乙143丙174资源39Max{2,3,1}=3x2进基x4=3-x1-x2-x3x5=9-x1-4x2-7x3=3-x2=9-4x2x5出基Min{3/1,9/4}=9/4)(14→)(01初等行变换111103147019

A=()→1111031/417/401/49/4

)(→3/40–3/41–1/43/41/417/401/49/4

)(B1=(P4,P2))=(1001

一、单纯形法的基本思想

1、顶点的逐步转移即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。

根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。

于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达到最优值（单纯形法的由来？）2．需要解决的问题：(1)为了使目标函数逐步变优，怎麽转移？(2)目标函数何时达到最优——判断标准是什麽？

二、单纯形法原理（用代数方法求解LP）劳动力原材料利润A112B143C173现有资源39例1第一步：引入非负的松弛变量x4,x5,将该LP化为标准型第二步：寻求初始可行基，确定基变量对应的基变量是x4，x5；

第三步：写出初始基本可行解和相应的目标函数值两个关键的基本表达式：①用非基变量表示基变量的表达式②用非基变量表示目标函数的11111表达式请解释结果的经济含义——不生产任何产品，资源全部节余（x4=3，x5=9），三种产品的总利润为0！第四步：分析两个基本表达式，看看目标函数是否可以改善？①分析用非基变量表示目标函数的表达式

非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加通常把非基变量前面的系数叫“检验数”；②选哪一个非基变量进基？

选x2为进基变量（换入变量）问题：能否选其他的非基变量进基？

任意一个

任意一个正检验数对应的非基变量

最大正检验数对应的非基变量

排在最前面的正检验数对应的非基变量×③确定出基变量：问题讨论

x2进基意味着其取值从0变成一个正数（经济意义——生产B产品），能否无限增大？当x2增加时，x4，x5如何变化？现在的非基变量是哪些？具体如何确定换出变量？由用非基变量表示基变量的表达式

当x2增加时，x4，x5会减小，但有限度——必须大于等于0，以保持解的可行性！于是当x2的值从0增加到9/4时，x5首先变为0，此时x4=3/4>0因此选x5为出基变量（换出变量）。这种用来确定出基变量的规则称为“最小比值原则”（或θ原则）。如果P1≤0，会出现什麽问题？

最小比值原则会失效！

基变换新的基变量——x2,x4；新的非基变量x1,x3,x5；写出用非基变量表示基变量的表达式：可得新的基本可行解X（1）=（0，9/4，0，3/4，0）T由⑤写出用非基变量表示目标函数的表达式:可得相应的目标函数值为Z（1）=27/4检验数仍有正的返回①进行讨论。第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解!为什麽？——分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！三、表格单纯形法：

1、

初始单纯形表的建立

(1)表格结构：

x1x2x3

x4x523300z11110147013x49x523300z（2）表格设计依据：把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具有n+m+1个变量、m+1个方程的方程组：取出系数写成增广矩阵的形式：

Xn+1，…，Xn+m所对应的系数列向量构成一个基用矩阵的初等行变换将目标函数中基变量系数化为零,这时变成0，相应的增广矩阵变成如下形式：其中，，j=1，2，…，n；

（3）检验数的两种计算方法：①利用矩阵的行变换，把目标函数表达式中基变量前面的系数变为0；②使用计算公式——

增广矩阵的最后一行就是用非基变量表示目标函数的表达式，σj（j=1，2，…，n）就是非基变量的检验数。2、例1的表格单纯形法计算过程：

x1x2x3x4x5

23300z111103x4147019x5

23300z3/4

0

-3/4

1

-1/43/4x41/417/401/49/4x25/40–9/40-3/4z-27/410-14/3-1/31x1012-1/31/32x200-1-5/3-1/3z-8从最优表可知:该LP的最优解是X*=(1,2,0,0,0)T相应的目标函数最优值是Zmax=8**求解：Maxz=4x1+x2+x3解:本题约束方程系数矩阵不含单位子矩阵√√√*x1x2x3x4x523100z111103x4147019x523100z3/4

0

-3/4

1

-1/43/4x41/417/401/49/4x25/40–17/40-3/4z-27/4√√√*10-14/3-1/31x1012-1/31/32x200-3-5/3-1/3Z-8阶段Ⅰ：MaxW=4x1+x2+x3单纯形法小结

求解思想－－

顶点的逐步转移，

条件是使目标函数值不断得到改善。表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。

（这一步计算机可自动完成）

确定初始可行基，写出初始基本可行解第二步：最优性检验计算检验数，检查：所有检验数是否≤0？

是——结束，写出最优解和目标函数最优值；还有正检验数——检查相应系数列≤0？是——结束，该LP无“有限最优解”！不属于上述两种情况，转入下一步—基变换。

确定是停止迭代还是转入基变换？

选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。第三步：基变换确定进基变量和出基变量。利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。第四步换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解和相应的目标函数值该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列≤0（最优解无界）停止迭代的标志（停机准则）计算机求解时的注意点1、输入数据中的分数，需先化为小数再执行输入过程。2、每一张迭代表格中由基变量列（Basic）和B(i)列（解答列）可以读出现行解及相应的目标函数值，同时显示进基变量和出基变量，从而很容易识别主元列、主元行和主元素。3、最终表显示最优解、最优目标函数值及总的迭代次数。如遇该线性规划无可行解或无“有限最优解”，则屏幕将显示有关信息：NOfeasiblesolution.或**unboundedsolution!!!求解：Maxz=5x1+x2+3x3化为标准性Maxz=5x1+x2+3x3约束方程的系数矩阵不含单位子矩阵，两段法求解：1.构造辅助规划求得原问题的初始可行基;2.单纯形表求解原问题（2）

两阶段法

第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数W为所有人工变量之和的相反数，目标要求是使目标函数极大化，约束条件与原线性规划相同。Maxw=-x5(FP)x5人工变量

求解结果①W最优值=0——即所有人工变量取值全为0（为什麽？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段；②W最优值=0——但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况①；如何转化？

选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来③W最优值>0——至少有一个人工变量取值>0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。第二阶段：

将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。问题讨论:如何实施?需要重新建立初始单纯形表吗？

实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。

x5

0000-1w211103x4-120014x5

-12000w+45/2

0

1

1

-1/21x4-1/21001/22x20000-1w从最优表可知:该FP的最优解是X*=(0,2,0,1,0)T相应的目标函数最优值是Wmax=0x1x2x3x4

5130z5/2

0

1

1

1x4-1/21002x211/2030z-21

0

2/5

2/52/5x1011/5

1/5

11/5x2004/5-11/5z-21/55/2

0

1

1

1x3-1/21002x2-200-3z-5从最优表可知:原(LP)的最优解X*=(0,2,1,0)T相应的目标函数最优值Zmax=5***例1加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/公斤，应否改变生产计划？每天:三、线性规划建模实例1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。模型求解

软件实现

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格

35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)现工厂决策者考虑停产A1,A2,接受外来加工问：接受外来加工可行条件？设原材料每桶

y1元，机器价格每小时y2元，加工能力每公斤y3元工厂同意合作前提:另一方接受的可能性：(LP)的对偶问题

35元可买到1桶牛奶，买吗？若买，每天最多买多少?设该厂现有生产条件下原材料每桶价值y1元,机器价格每小时价值y2元,加工能力每公斤价值y3元(LP)(DP)(DP)称为(LP)的对偶问题对称形式的对偶问题(LP)maxz=cT

x(DP)minw=bT

y性质：若x0和y0分别是(LP)和(DP)的可行解，则bTy0≥cTx0;bTy0=cTx0x0和y0分别是(LP)和(DP)的最优解(LP)(DP)1.(DP)中约束与(LP)中变量符号一致2.(DP)中变量与(LP)中约束符号相反结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加53

35元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)例2奶制品的生产销售计划

在例1基础上深加工1桶牛奶3千克A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤0.8千克B12小时,3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克制订生产计划，使每天净利润最大

30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？50桶牛奶,480小时至多100公斤A1

B1，B2的获利经常有10%的波动，对计划有无影响？1桶牛奶

3千克A1

12小时8小时4千克A2

或获利24元/千克获利16元/kg

0.8千克

B12小时,3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克出售x1千克A1,

x2千克A2，

X3千克B1,x4千克B2原料供应

劳动时间

加工能力

决策变量

目标函数

利润约束条件非负约束

x5千克A1加工B1，x6千克A2加工B2附加约束

模型求解

软件实现

LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No

OBJECTIVEFUNCTIONVALUE1)3460.800

VARIABLEVALUEREDUCEDCOST

X10.0000001.680000

X2168.0000000.000000

X319.2000010.000000

X40.0000000.000000

X524.0000000.000000

X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2结果解释每天销售168千克A2和19.2千克B1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1

除加工能力外均为紧约束结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000增加1桶牛奶使利润增长3.16×12=37.92增加1小时时间使利润增长3.2630元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）结果解释B1,B2的获利有10%的波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000

X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY

…………DORANGE(SENSITIVITY)ANALYSIS?YesB1获利下降10%，超出X3系数允许范围B2获利上升10%，超出X4系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。4.2自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。其他费用:450元/千吨

应如何分配水库供水量，公司才能获利最多？

若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40<总需求量：120+180=300总收入900160=144,000(元)收入：900元/千吨

其他费用:450元/千吨

支出引水管理费其他支出450160=72,000(元)使引水管理费最小供应限制约束条件需求限制

线性规划模型(LP)目标函数

水库i向j区的日供水量为xij（x34=0）决策变量

模型建立确定3个水库向4个小区的供水量模型求解

OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利润=总收入-其它费用-引水管理费=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理费24400(元)目标函数

总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其它费用(450)

–引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论

确定送水方案使利润最大需求约束可以不变求解OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X31

50.0000000.000000X320.00000020.000000X33

30.0000000.000000这类问题一般称为“运输问题”(TransportationProblem)总利润88700（元）

A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030如何装运，使本次飞行获利最大？

三个货舱最大载重(吨),最大容积(米3)

例2货机装运

重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡决策变量

xij--第i种货物装入第j个货舱的重量(吨）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000

X32

12.9473690.000000X33

3.0000000.000000X410.000000650.000000

X423.0526320.000000X430.000000650.000000货物2：前仓10,后仓5；

货物3:中仓13,后仓3；货物4:中仓3。货机装运模型求解最大利润约121516元货物~供应点货舱~需求点平衡要求运输问题运输问题的扩展第三讲整数规划建模方法一、从现实问题到整数规划模型二、整数规划模型的求解三、整数规划的建模实例4.1整数规划简介要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解4.2整数规划的分枝定界法3、求解分枝的松弛问题—定界过程设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况

4.2.1思路与解题步骤只解松弛问题1、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最优解2、分枝过程若松弛问题最优解中某个xk=bk不是整数，令bk为bk的整数部分构造两个新的约束条件xkbk和xkbk+1，分别加于原松弛问题，形成两个新的整数规划表4.2.1分枝问题解可能出现的情况情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或54.2.2分枝定界法举例

例4.1.1

解：松弛问题的最优解为x1=2.5,x2=2,OBJ=23由x1=2.5得到两个分枝如下：表4.2.3分枝问题的松弛解问题II的解即原整数问题的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题例.某厂拟用集装箱托运甲,乙两种货物。已知货物体积(米3/箱)重量(吨/箱)利润(百元/箱)甲9740乙72090托运限制5670问：如何安排利润最大？设甲乙分别托运x1,x2箱模型建立

IP(1)-(4)称为与(IP)相对应的线性规划(LP)求解(LP)得x1=4.81,

x2=1.82,z=356分枝定界法(branchandboundmethod)(IP)x1*,x2*,z*(LP) x1=4.81,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X1≤4X1≥5(LP2)x1=5,x2=1.57,z0=341(z*≤349定界)(LP3)x1=4,x2=2,z0=340X2≤2X2≥3(LP4)x2=3,x1=1.42,z0=327(z*≥340定界)(LP5)x2=1,x1=5.44,z0=308X2≤1(LP6)无可行解X2≥2X1≤4X1≥5分枝：设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划模型建立

小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)模型求解

3）

模型中增加条件：x1,x2,x3

均为整数，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2