天津大学《数学建模》课件- 线形规划基础

第三章数学规划模型通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等最佳：有一个标准或目标，如使利润达到最大、成本最小、时间最短等。线性规划问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的需求数量分别为400、600和500，且已知用2种不同车床加工单位数量的各工件所需的台时数和加工费用，如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3；在乙车床上加工工件1、2、3的数量分别为x4、x5、x6，则数学模型subjectto例2

靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小工厂1工厂2200万m3500万m3设x1、x2——分别代表工厂1和工厂2处理污水的数量(万m3)则目标函数：minz=1000x1+800x2约束条件：

第一段河流（工厂1——工厂2之间）：(2－x1)/500≤0.2%

第二段河流：[0.8(2－x1)+(1.4－x2)]/700≤0.2%

此外有：

x1≤2；x2≤1.4有：

minz=1000x1+800x2

(2－x1)/500≤0.2%[0.8(2－x1)+(1.4－x2)]/700≤0.2%

x1≤2x2≤1.4x1、x2≥0s.t500+2-x1线性规划模型的特征：（1）用一组决策变量x1，x2，…xn表示某一方案;（2）有一个目标函数，这个目标函数可表示为这组变量的线性函数;（3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达;（4）要求目标函数实现极大化（max）或极小化（min）。满足上述4个特征的规划问题称为线性规划问题O51015x1x1=4x2101AB(2,5)C5x1+x2=1530x1+20x2=1605x1+2x2=5线性规划的最优解在可行域的顶点上几种可能结果

(1）有唯一最优解，如例1。（2）有无穷多最优解如例1中的目标函数设为maxZ=10x1+2x2

9O51015x1x1=4x25101AB（2，5）C5x1+x2=1530x1+20x2=16010x1+2x2=5如果有两个顶点是最优解，那么这两顶点的连线上的点也都是例，试用图解法求解下列线性规划问题

st.（3）无界解无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值Z→+∝,

极小化问题则可使目标函数值Z→-∝，

-1O24x1x224-2x1+x2=2x1-3x2=3-1O33（4）

无解。某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。

例max

z=x1+2x2

－x1+2x2≥1x1+x2≤－2x1、x2≥0无可行解。1－112OA13解的情况：1.有最优解唯一最优解无穷多最优解2.无界解3.无解线性规划的一般数学模型目标函数约束条件

通常称为决策变量，为价值系数，为消耗系数,为资源限制系数。

s.t

线性规划的标准形式（1）极大化与极小化：若，令，

原目标函数。(2)

线性不等式与线性等式：

其中为非负松弛变量，

其中为非负剩余变量。非标准形式线性规划问题的标准化17

(4)非负变量与符号不受限制的变量若xi的符号不受限制，则可引进非负变量xi1,xi2，令

xi=xi1-xi2，这样就可以使线性规划里所有的变量都转化为有非负限制的变量。（5）

(3)右端项为负约束两端乘以（－1）例，将下述线性规划问题化为标准型

令,其中符号不受限制线性规划的求解方法图解法单纯形法…..模型的软件求解-MATLAB1.模型：minz=cX

命令：x=linprog（c,A,b）

2.模型：minz=cX

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

VLB≤X≤VUB

[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]

x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点4.命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.编写M文件如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];

A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;0

00.03000.08];

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

Aeq=[];beq=[];

vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

s.t.改写为：例

问题一的解答编写M文件如下:c=[1391011128];A=[0.41.11000;0000.51.21.3];b=[800;900];Aeq=[100100；010010；001001];beq=[400;600;500];vlb=zeros(6,1);vub=[];[x,fval]=linpr