线性规划模型目标函数

线性规划1.线性规划内容一、线性规划模型二、线性规划模型的标准形式三、用matlab解线性规划2.线性规划所解决的问题具有以下共同的特征：2.存在一定的限制条件（即约束条件），这些限制条件是关于未知数的一组线性等式或线性不等式来表示。1.每一个问题都用一组未知数（x1

，x2

，…，xn

）表示某一方案；这些未知数的一组定值就代表一个具体方案。由于实际问题的要求，通常这些未知数取值是非负的。3.有一个目标要求，称为目标函数。目标函数可表示为一组未知数的线性函数。根据问题的需要，需求目标函数实现最大化或最小化。一、线性规划模型3.一般的线性规划问题的数学模型：

目标函数(线性函数）：

Min(max)z=c1x1

+c2x2

+…+cnxn

约束条件(s.t.)：

a11x1+a12x2+…+a1nxn(≥)b1a21x1+a22x2+…+a2nxn(≥)b2

...am1x1+am2x2

+…+amnxn

(≥)bm

x1

，x2

，…，xn

≥0

式中()可以是关系符号：>,<,=,≥,≤中的任意一个（线性等式或线性不等式）。一、线性规划模型4.线性规划模型的求解：图解法单纯形法matlab软件求解。以下介绍几种常见的线性规划问题。

5.问题一：任务分配问题：某车间有甲、乙两台车床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？引例16.解

设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：目标函数：约束条件：7.问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：引例28.故目标函数为：约束条件为：9.线性规划模型目标函数：

约束条件：

注：本问题应还有一个约束条件：x1、x2取整数.故它是一个整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.10.问题三：投资决策问题某公司拟在某市东、西、南三区建立门市部，拟议中有7个位置（点）Ai(i=1,2,…,7)可供选择。规定东区在A1、A2、A3三个点中至多选两个。西区A4、A5两个点中至少选一个。南区A6、A7两个点中至少选一个。并知道如果选用Ai点，则投资为bi元，估计每年可获利为ci元，但投资总额不得超过B元。问应该选择哪几个点可使年利润为最大？解设则投资决策问题归结为一个线性规划模型：引例311.故目标函数为：约束条件为：s.t.这是一个0-1规划问题12.几个问题都是典型的最值问题。其中，“Min或Max”是英文单词“Minimize或Maximize”的缩写，含义为“最小化或最大化”；“s.t.”是“subjectto”的缩写，表示“受约束于…”。线性规划是运筹学的一个重要分支，应用很广。线性规划问题可以描述为求一组非负变量，这些非负变量在一定线性约束的条件下，使一个线性目标函数取得极大（极小）值的问题。由于式中的目标函数与约束条件均为线性函数，故被称为线性规划问题。13.线性规划的标准形式

目标函数：

Minz=c1x1

+c2x2

+…+cnxn

约束条件：

a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2

...am1x1+am2x2

+…+amnxn=bm

x1，x2，…，xn≥0二、线性规划模型的标准形式14.线性规划的一般形式

目标函数：

Min(max)z=c1x1

+c2x2

+…+cnxn

约束条件：

a11x1+a12x2+…+a1nxn(≥)b1a21x1+a22x2+…+a2nxn(≥)

b2

...am1x1+am2x2

+…+amnxn

(≥)

bm

x1，x2，…，xn≥0

式中()可以是关系符号：>,<,=,≥,≤中的任意一个。二、线性规划模型的标准形式15.实际问题中的优化模型x是决策变量f(x)是目标函数gi(x)0是约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划优化模型的分类16.线性规划标准型的特点：1、目标函数是Min（最小化）；2、约束条件为等式；3、决策变量为非负数；4、右端常数要求为非负数。17.三、用matlab解线性规划基本用法用MATLAB优化工具箱求解线性规划时不要求一定化为标准形，而是要求化为如下形式：

下一页18.线性规划的矩阵表示19.用MATLAB解线性规划minz=cX

1.模型：命令：x=linprog（c,A,b）

[x,fval]=linprog

(…)返回最优解ｘ及ｘ处的目标函数值fval2.模型：minz=cX

命令：x=linprog（c，A，b，A1,b1）注意：若没有不等式：存在，则令A=[]，b=[].20.3.模型：minz=cX

V1≤X≤V2命令：[1]x=linprog（c，A，b，A1,b1,V1，V2）

[2]

x=linprog（c，A，b，A1,b1,V1，V2,X0）

注意：[1]若没有等式约束:,则令A1=[],b1=[]。若v1=zeros(2,1),表示2行1列的零矩阵。[2]其中X0表示初始点21.解编写M文件xxgh1.m如下：c=[-0.4,-0.28,-0.32,-0.72,-0.64,-0.6];

A=[0.01,0.01,0.01,0.03,0.03,0.03;0.02,0,0,0.05,0,0;0,0.02,0,0,0.05,0;0,0,0.03,0,0,0.08];

b=[850;700;100;900];

A1=[];b1=[];

v1=[0;0;0;0;0;0];v2=[];[x,fval]=linprog(c,A,b,A1,b1,v1,v2)22.Optimizationterminatedsuccessfully.x=1.0e+004*3.50000.50003.00000.00000.00000.0000fval=-2.5000e+00423.例2用MATLAB解线性规划问题24.解

Matlab程序如下:c=[-2,-1,1];A=[1,4,-1;2,-2,1];b=[4;12];A1=[1,1,2];b1=6;v1=[0,0,-inf];v2=[inf,inf,5];[x,z]=linprog(c,A,b,A1,b1,v1,v2)运行后得到输出Optimizationterminatedsuccessfully.x=4.66670.00000.6667z=-8.666725.例3

用MATLAB求解线性规划问题解首先转化为求最小值问题26.Matlab程序如下c=[-2,-3,5];A=[-2,5,-1];b=-10;A1=[1,1,1];b2=[7];v1=[0,0,0];[x,z]=linprog(c,A,b,A1,b1,v1)运行后得到输出x=6.42860.57140.0000z=-14.5714键入s=-z运行后得到原问题的目标函数最大值s=14.571427.解:编写M文件xxgh2.m如下：

c=[6,3,4];A=[0,1,0];b=[50];Aeq=[1,1,1];beq=[120];vlb=[30,0,20];vub=[];

[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)28.Optimizationterminatedsuccessfully.x=30.000050.000040.0000fval=490.000029.例5：任务分配问题：某车间有甲、乙两台车床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？30.解

设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：目标函数：约束条件：

解答31.s.t.

问题32.编写如下:c=[13,9,10,11,12,8];A=[0.4,1.1,1,0,0,0;0,0,0,0.5,1.2,1.3];b=[800;900];A1=[1,0,0,1,0,0;0,1,0,0,1,0;0,0,1,0,0,1];b1=[400,600,500];vl=zeros(6,1);v2=[];[x,fval]=linprog(c,A,b,A1,b1,v1,v2)33.结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.34.例6：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：35.线性规划模型：目标函数：

36.编写如下：c=[40;36];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[9;15];%调用linprog函数：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)37.结果为：x=9.00000.0000fval=360即只需聘用9个一级检验员.

注：本问题应还有一个约束条件：x1、x2取整数.故它是一个整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.返回38.习题1.建立下列线性规划问题的数学模型（1）某工厂生产A、B、C三种产品，三种产品对于材料费用、劳动力和电力的单位消耗系数，资源限量和单位产品价格如表1.1