规划模型一演示文稿

规划模型一演示文稿当前第1页\共有50页\编于星期三\11点（优选）规划模型一当前第2页\共有50页\编于星期三\11点案例一、

家具生产的安排

家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米每张桌子要使用15个工时，0.2立方木材售价80元。每张椅子使用10个工时，0.05立方木材售价45元。问为达到最大的收益，应如何安排生产？当前第3页\共有50页\编于星期三\11点分析：

1.求什么？生产多少桌子？生产多少椅子？

2.优化什么？收益最大

3.限制条件？原料总量劳力总数x1x2MaxZ=80x1+45x20.2x1+0.05x2

≤415x1+10x2≤450当前第4页\共有50页\编于星期三\11点模型I：以产值为目标取得最大收益.设：生产桌子x1张,椅子x2张,(决策变量)

要优化的目标表示为：maxf=80x1+45x2

对决策变量的约束（约束条件）：

0.2x1+0.05x2≤415x1+10x2≤450,x1≥0,x2≥0,

模型II.在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。（将在下一讲中介绍）当前第5页\共有50页\编于星期三\11点规划问题：在约束条件下求目标函数的最优值点。规划问题包含3个组成要素:

决策变量(decisionvariable)目标函数(objectivefunction)

约束条件(constraint)当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,

否则称为非线性规划问题。当前第6页\共有50页\编于星期三\11点可行解（feasiblesolution）

使得约束条件成立的决策变量的一组值可行域（feasibleregion）

全体可行解组成的集合（经常记为S）

最优解（optimalsolution）

可行域中使目标函数达到所需最大或最小的可行解

当前第7页\共有50页\编于星期三\11点线性规划问题求解方法1、图解法(Graphicalmethod)

：(解两个变量的线性规划问题)

在平面上画出可行域（凸多边形），计算目标函数在各极点(多边形顶点)处的值比较后，取最值点为最优解。当前第8页\共有50页\编于星期三\11点凸集(Convexset)凸集非凸集如果某个集合中任意两点连起来的直线都属于该集合，则称其为凸集，否则为非凸集，如下图所示数学定义：是凸集当且仅当对任意实数和任意的均成立当前第9页\共有50页\编于星期三\11点极点(Extremepoint)

设K是凸集，，若X不能用K中两个不同的点的凸组合表示为<)10()1()2()1(<-+=aaaXXX则称X是K的一个极点或顶点。X是凸集K的极点是指X不可能是K中某一线段的内点，只能是K中某一线段的端点。O当前第10页\共有50页\编于星期三\11点命题1

线性规划问题的可行解集是凸集

可行解集：线性不等式组的解（可行域）

0.2x1+0.05x2=415x1+10x2=450

可行解：满足约束条件的解。绿色区域中的每一个点（包括边界点）都是可行解。此区域是【案例一】的线性规划问题的解的集合（可行解域）。可行域当前第11页\共有50页\编于星期三\11点命题2

线性规划问题的目标函数关于不同的目标值是一族平行直线,目标值的大小描述了直线距离原点的远近

【案例一】的目标函数Z=80x1+45x2在这个坐标平面上，它可以表示以Z为参数、-16/9为斜率的一族平行线：位于同一直线上的点，具有相同的目标函数值，称为“等值线”。当前第12页\共有50页\编于星期三\11点当Z值由小变大时，直线沿其法线方向向右上方移动。当移动到C时，Z值在可行域的边界上实现最大化。最优解（14，24），Z=2200。最优生产方案:桌子生产14张，椅子生产24张，最大利润2200元(最优值）。C当前第13页\共有50页\编于星期三\11点命题3

线性规划问题的最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).

当前第14页\共有50页\编于星期三\11点2、单纯形法（SimplexMethod

）:

通过确定约束方程组的基本解,

并计算相应目标函数值,

在可行解集的极点中搜寻最优解.

当前第15页\共有50页\编于星期三\11点在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。线性规划问题的标准型为:1．目标函数求最大值（或求最小值）2．约束条件都为等式方程3．变量xj非负4．常数bi非负线性规划的标准型(StandardformofLP)当前第16页\共有50页\编于星期三\11点

模型的标准化决策变量:x1,x2,…,xn.

目标函数:Z=c1x1+c2x2+…+cnxn.

约束条件:a11x1+…+a1nxn≤b1,……am1x1+…+amnxn≤bm,当前第17页\共有50页\编于星期三\11点模型的标准化

10.引入松弛变量将不等式约束变为等式约束若有ai1x1+…+ainxn≤bi,则引入xn+i≥0,使得

ai1x1+…+ainxn+xn+i=bi

若有aj1x1+…+ajnxn≥bj,则引入xn+j≥0,使得

aj1x1+…+ajnxn-xn+j=bj.

且有Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.

当前第18页\共有50页\编于星期三\11点20.将目标函数的优化变为目标函数的极大化.若求minZ,令Z’=–Z,则问题变为maxZ’.30.引入人工变量,使得所有变量均为非负.若xi

没有非负的条件,则引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,则可使得问题的全部变量均非负.当前第19页\共有50页\编于星期三\11点标准化模型

求变量x1,x2,…,xn,maxZ=c1x1+…+cnxn,s.t.a11x1+…+a1nxn=b1,……am1x1+…+amnxn=bm,x1≥0,…,xn≥0,当前第20页\共有50页\编于星期三\11点【例】将下列线性规划化为标准形【解】（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以令当前第21页\共有50页\编于星期三\11点(2)第一个约束条件是≤号，在≤左端加入松驰变量(slackvariable)x4，x4≥0,化为等式；(4)第三个约束条件是≤号且常数项为负数，因此在≤左边加入松驰变量x6，x6≥0，同时两边乘以－1。（5）目标函数是最小值，为了化为求最大值，令Z′=－Z,得到maxZ′=－Z，即当Z达到最小值时Z′达到最大值，反之亦然。(3)第二个约束条件是≥号，在≥左端减去剩余变量(Surplusvariable)x5，x5≥0。也称松驰变量当前第22页\共有50页\编于星期三\11点综合起来得到下列标准型当前第23页\共有50页\编于星期三\11点当某个变量xj≤0时,令x/j=－xj

。当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束将其化为两个不等式再加入松驰变量化为等式。当前第24页\共有50页\编于星期三\11点【例】将下例线性规划化为标准型【解】

此题关键是将目标函数中的绝对值去掉。令则有当前第25页\共有50页\编于星期三\11点得到线性规划的标准形式

当前第26页\共有50页\编于星期三\11点单纯形法的基本思想

对于一个标准型LP问题，从一个初始基可行解出发，判断其是否为最优解，若是则结束；否则求一个与其“相邻”的、改进的基可行解。再判断这个解是否最优，若是则结束，否则再求一个“相邻”的、改进的基可行解……如此迭代下去，直到找到基最优解或判定问题无解为止。x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例1，OQ1Q2或OQ4Q3Q2当前第27页\共有50页\编于星期三\11点单纯形法要解决的三方面的问题：（1）如何确定初始的基可行解？（2）如何进行解的最优性判别？（3）如何寻找改进的基可行解？当前第28页\共有50页\编于星期三\11点标准形式LP的基本可行解

在n个变量m个约束的标准LP中，指定其中

n–m个变量为0，从约束条件中可解得其余m个变量的唯一非负解，此时所对应的线性规划的可行解称为该LP的基本可行解（basicfeasiblesolution），上述n-m个变量称为自由变量（freevariables），剩下的m个变量称为基变量，简称基（basic）用单纯形法解线性规划问题的具体步骤将在矩阵的学习之后做详细的介绍当前第29页\共有50页\编于星期三\11点3、用MATLAB软件求解线性规划问题线性规划问题的求解方法包括图解法、单纯形法、矩阵法等.但在决策变量个数较多，求解过程都比较复杂时，用MATLAB软件求解线性规划问题则比较简单.当前第30页\共有50页\编于星期三\11点MATLAB求解线性规划问题的命令⑴X=linprog(f,A,b)求解LP问题命令格式命令函数linprog()当前第31页\共有50页\编于星期三\11点⑵[X,fval]=linprog(f,A,b,Aeq,Beq,LB,UB)求解LP问题当前第32页\共有50页\编于星期三\11点⑶[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options).其功能是求解有初始值X0和用options指定优化参数进行优化的LP问题.函数说明(1)fAXb线性规划的不等式约束条件AeqBeq线性规划的等式约束条件目标函数取得极值的决策变量组成的列向量矩阵向量矩阵向量目标函数的系数组成的向量当前第33页\共有50页\编于星期三\11点LBX0OptionsfvalUB变量的上界约束变量的初始值变量的下界约束控制规划过程的参数系列优化结束后得到的目标函数值当前第34页\共有50页\编于星期三\11点[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)目标函数取得极值的决策变量组成的列向量优化结束后得到的目标函数值目标函数的系数组成的向量线性规划的不等式约束条件矩阵向量控制规划过程的参数系列变量的初始值变量的下界约束变量的上界约束线性规划的等式约束条件矩阵向量当前第35页\共有50页\编于星期三\11点(2)运用linprog()命令时，系统默认为它的各种linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)都存在，且按固定顺序排列。本例中，在存在约束LB的情况下，它后面的参数没给出，可以不声明，但是LB前面的参数即使没给出（例如等式约束条件）也要用空矩阵“[

]”的方式给出声明，不能省略。函数说明(3)返回值exitflag有3种情况：exitflag=－1表示优化结果不收敛。exitflag=1表示优化过程中变量收敛于解X。

exitflag=0表示优化结果已经超过函数的估计值或者已声明的最大叠代次数；当前第36页\共有50页\编于星期三\11点(4)返回值output有3个分量，iterations表示优化过程的叠代次数，cgiterations表示PCG叠代次数，algorithm表示优化采用的运算规则。函数说明(5)返回值lambda有4个分量，ineqlin是线性不等式约束条件，eqlin是线性等式约束条件，upper是变量的上界约束条件，lower是变量的下界约会条件。它们的返回值分别表示相应的约束条件在优化过程中是否有效，本例中可以看到，三个不等式约束中的后两个是有效的。当前第37页\共有50页\编于星期三\11点(6)线性规划问题没有可行解时,系统提示

Warning:Theconstraintsareoverlystringent;thereisnofeasiblesolution.如果优化成功,系统将会提示:Optimizationterminatedsuccessfully函数说明当前第38页\共有50页\编于星期三\11点

案例二（生产计划的问题）某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？

ⅠⅡ资源限量设备128(台时)原材料A4016(kg)原材料B0412(kg)单位产品利润（万元）23

返回当前第39页\共有50页\编于星期三\11点用MATLAB

求解案例二中关于生产计划的LP问题解原LP问题为

MATLAB命令的标准形是求目标函数的最小值,通常将maxf通常转变为min-f来编程求解。原问题转化为当前第40页\共有50页\编于星期三\11点在MATLAB中输入>>clear>>f=-[2,3];>>A=[1,2;4,0;0,4];>>B=[8,16,12];>>lb=[0,0];>>[X,fval]=linprog(f,A,B,[],[],lb)击回车键，显示最优解及目标函数最优值Optimizationterminatedsuccessfully.X=

4.0000

2.0000当前第41页\共有50页\编于星期三\11点fval=

-14.0000所以，工厂应选择生产第Ⅰ、Ⅱ产品的产量分别为4件和2件，工厂最多可获利14万元。当前第42页\共有50页\编于星期三\11点案例三(营养配餐问题)

假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。试建立满足营养的前提下使购买食品费用最小的数学模型。序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002返回当前第43页\共有50页\编于星期三\11点用MATLAB求解案例三中的线性规划问题。解原LP模型为在MATLAB中输入>>clear>>f=[10,6,3,2];>>A=[-10,-8,-9,-2;-5,-6,-2,-1;-4,-2,-3,-5];b=[-30,-5.5,-8];>>lb=[0,0,0,0];>>[X,fval]=linprog(f,A,b,[],[],lb)当前第44页\共有50页\编于星期三\11点显示最优解及目标函数最优值Optimizationterminatedsuccessfully.X=0.00000.00003.3333

0.0000

所以应购买3.3333千克大米才能既满足营养需求，又能使购买食品的费用最小。当前第45页\共有50页\编于星期三\11点

案例四(投资问题)某公司有一批资金用于4个工程项目的投资，其投资各项目时所得的净收益如下表：

工程项目ABCD收益(%)1510812由于某种原因，决定用于项目A的投资不大于其他各项投资之和而用于项目B和C的投资要大于项目D的投资。试建立该公司收益最大的投资分配方案的数学模型。

返回当前第46页\共有50页\编于星期三\11点用MATL