线性规划课件

数学规划其中，x是决策变量，f(x)是目标函数，gi(x)0是约束条件。数学规划问题模型的一般形式数学规划问题划分线性规划：目标函数和约束条件都是线性的非线性规划：目标函数或者约束条件是非线性的整数规划：决策变量是整数值多目标规划：具有多个目标函数目标规划：具有不同优先级的目标和偏差动态规划：求解多阶段决策问题的最优化方法等等一、线性规划1.1线性规划问题提出1.2线性规划问题的数学模型1.3线性规划问题的解1.4线性规划问题应用实例例：某车间有甲、乙两台机床，可用于加工三种工件。假定两台机床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用不同机床加工单位工件所需的台时数和加工费用如下表。问怎样分配机床的加工任务，才能既满足加工工件的要求，又使加工费用最低？1.1线性规划问题提出解：设在甲机床上加工工件1、2、3的数量分别为x1、x2、x3，

在乙机床上加工工件1、2、3的数量分别为x4、x5、x6,1.1线性规划问题提出例：某厂生产Ⅰ、Ⅱ两种产品，分别在A、B、C三种不同的设备上加工。生产每件产品Ⅰ需占用各设备分别为2h、4h、0h，生产每件产品Ⅱ需占用各设备分别为2h、0h、5h。已知各设备计划期内生产能力分别为12h、16h、15h，又知每生产一件产品Ⅰ可获利2w，每生产一件产品Ⅱ可获利3w。问该厂应安排生产两种产品各多少件，可使总利润最大。1.1线性规划问题提出解：设生产产品I、Ⅱ分别x1、x2件一般线性规划问题的数学模型1.2线性规划问题的数学模型简写形式目标函数约束条件决策变量

1.2线性规划问题的数学模型向量形式矩阵形式1.2线性规划问题的数学模型非线性规划问题转化为线性规划问题简写线性规划问题的标准形式1.2线性规划问题的数学模型集合形式1.2线性规划问题的数学模型向量形式矩阵形式标准形式简写非标准形线性规划问题的标准化

1.目标函数minz=CX令z=-z，有maxz=-CX2.约束条件a)bi<0的情况

例

x1-2x2=-1-x1+2x2=11.2线性规划问题的数学模型2.约束条件b)约束条件为“”的情况令x3=12-2x1-2x20

x4=16-4x10x5=15-5x20例1.2线性规划问题的数学模型非标准形线性规划问题的标准化

2.约束条件b)约束条件为“”的情况1.2线性规划问题的数学模型非标准形线性规划问题的标准化

3.决策变量a)若xk0，

令xk=-xk，则xk0b)若xk为自由变量，令xk=xk-xk，且xk

0

，xk01.2线性规划问题的数学模型非标准形线性规划问题的标准化

例：将下述线性规划模型化为标准形式

解：令z=-z，则1.2线性规划问题的数学模型令x1=-x1，x3=

x3-x3，且x30，x30得原问题的等价标准形1.2线性规划问题的数学模型1.可行解：满足约束条件的解X=(x1,…,xn)T2.可行域：可行解的集合3.最优解：使目标函数达到最大值的可行解4.最优值：最优解对应到目标函数值1.3线性规划问题的解线性规划问题解的概念1.3线性规划问题的解图解法求解z=15x1x2A(6,0)B(0,6)2x1+2x2=12O4x1=165x2=15Q1Q2Q3Q4(3,3)x2OQ1Q2Q3Q4x1线性规划问题求解的几种可能结局1.唯一最优解2.无穷多最优解1.3线性规划问题的解线性规划问题求解的几种可能结局1.唯一最优解2.无穷多最优解3.无界解Ox1x21.3线性规划问题的解线性规划问题求解的几种可能结局1.唯一最优解2.无穷多最优解3.无界解4.无可行解x2Ox11.3线性规划问题的解用Matlab求解线性规划问题的解Matlab函数linprog()的调用形式：[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub,x0,Options)其中：x为最优解，fval返回对应的目标函数最优值，x0是x的初始值，Options是控制参数。1.3线性规划问题的解例：c=[2;3;-5];A=[-2,5,-1;1,3,1];b=[-10;12];Aeq=[1,1,1];beq=7;x=linprog(-c,A,b,Aeq,beq,zeros(3,1))value=c'*x1.3线性规划问题的解用Matlab求解线性规划问题的解c=[2;3;1];A=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-A,-b,[],[],zeros(3,1))1.3线性规划问题的解用Matlab求解线性规划问题的解例：1.4线性规划问题应用实例线性规划建模步骤:①设立决策变量；②明确约束条件并用变量的线性等式或不等式表示；③用变量的线性函数表示目标，并确定是求极小还是极大；④根据变量的物理性质研究变量是否有非负性。

投资的收益和风险1.4线性规划问题应用实例二、基本假设和符号规定

投资的收益和风险1.4线性规划问题应用实例三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…,n}

投资的收益和风险1.4线性规划问题应用实例4.模型简化：三、模型的建立与分析

投资的收益和风险1.4线性规划问题应用实例三、模型的建立与分析

投资的收益和风险1.4线性规划问题应用实例四、模型1的求解

由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。因此，从a=0开始，以步长△a=0.001进行循环搜索。

投资的收益和风险1.4线性规划问题应用实例a=0;whilea<=0.1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')四、模型1的求解

投资的收益和风险1.4线性规划问题应用实例Matlab计算结果：四、模型1的求解

投资的收益和风险1.4线性规划问题应用实例2.投资越分散，投资者承担的风险越小，即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.风险大，收益也大；a=0.003

x=0.49490.12000.20000.05450.1154Q=0.1266a=0.006

x=0.00000.24000.40000.10910.2212Q=0.2019a=0.008

x=0.00000.32000.53330.12710.0000Q=0.2112a=0.010

x=0.00000.40000.58430.00000.0000Q=0.2190a=0.020

x=0.00000.80000.18820.00000.0000Q=0.2518a=0.040

x=0.00000.99010.00000.00000.0000Q=0.2673

五、结果分析

投资的收益和风险1.4线性规划问题应用实例3.曲线上任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。4.在a=0.006附近有一个转折点，在该点左边，风险增加很少时，利润增长很快，在该点右边，风险增加很大时，利润增长很慢。所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，投资方案为:风险度收益x0

x1

x2x3

x40.00600.201900.24000.40000.10910.2212五、结果分析

投资的收益和风险1.4线性规划问题应用实例某食品公司有三个糖果加工厂，每天的糖果生产量分别为：A1—7t，A2—4t，A3—9t。该公司把这些糖果分别运往四个地区销售，各地区每天的销售量为：B1—3t，B2—6t，B3—5t，B4—6t。已知从每个加工厂到各地区每吨糖果的运价如下表所示。问该食品公司应如何调运，在满足各地区需要的情况下，使总的运费支出为最小。

单位：元/t运输问题1.4线性规划问题应用实例产销表运价表运输问题1.4线性规划问题应用实例解：设xij为从第i个产地调运给第j个销地的物资的数量，使总的运费支出最小，可以表为以下数学形式：运输问题1.4线性规划问题应用实例m行n行运输问题1.4线性规划问题应用实例

有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因个人专长不同，他们完成翻译不同文字所需的时间如表所示。应如何分配，使四个人分别完成这四项任务总的时间为最小。指派问题1.4线性规划问题应用实例解：设[aij]表示分配问题的效率矩阵，令则指派问题的数学模型一般写为：指派问题1.4线性规划问题应用实例某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?人力资源分配问题1.4线性规划问题应用实例分析：不同上班班次时段的司机和乘务人员数结束时段开工时段1234566:00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-2:002:00-6:0016:00-10:00210:00-14:00314:00-18:00418:00-22:00522:00-2:0062:00-6:00每时段需要的总人数607060502030人力资源分配问题1.4线性规划问题应用实例解：设xi

表示第i班次时开始上班的司机和乘务人员数，则有结束时段开工时段1234566:00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-2:002:00-6:0016:00-10:00210:00-14:00314:00-18:00418:00-22:00522:00-2:0062:00-6:00每时段需要的总人数607060502030人力资源分配问题1.4线性规划问题应用实例解：设xi

表示第i班次时开始上班的司机和乘务人员数，则有结束时段开工时段1234566:00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-2:002:00-6:0016:00-10:00x1x1210:00-14:00x2x2314:00-18:00x3x3418:00-22:00x4x4522:00-2:00x5x562:00-6:00x6x6每时段需要的总人数607060502030人力资源分配问题1.4线性规划问题应用实例某企业生产甲、乙、丙三种产品，每一产品均须经过A、B两道工序。A工序有两种设备可完成，B工序有三种设备可完成，除甲产品和乙产品的A工序可随意安排外，其余只能在要求的设备上完成。加工单位产品所需工序时间及其他各项数据的费用有关资料见下表。试制订利润最大的产品加工方案。设备产品甲产品乙产品丙费用/有效台时A1510300/6000A27912321/10000B168250/4000B2411783/7000B37200/4000原料单价(元/件)0.250.350.5销售单价(元/件)1.252.002.8生产计划问题1.4线性规划问题应用实例设备产品甲产品乙产品丙费用/有效台时A1510300/6000A27912321/10000B168250/4000B2411783/7000B37200/4000原料单价(元/件)0.250.350.5销售单价(元/件)1.252.002.8生产计划问题1.4线性规划问题应用实例设备产品甲产品乙产品丙费用/有效台时A15x110x6300/6000A27x29x712x8321/10000B16x38(x6+x7)250/4000B24x411x8783/7000B37x5200/4000原料单价(元/件)0.250.350.5销售单价(元/件)1.252.002.8目标函数：利润=收入-成本-加工费maxz=[(1.25-0.25)(x1+x2)+(2-0.35)(x6+x7)+(2.8-0.5)x8]–[0.05(5x1+10x6)+0.03(7x2+9x7+12x8)+0.06(6x3+8x6+8x7)+0.11(4x4+11x8)+0.05×7x5]=0.75x1+0.7753x2-0.375x3-0.4474x4-0.35x5

+0.65x6+0.8611x7+0.6844x8收入-成本-加工费生产计划问题1.4线性规划问题应用实例约束条件：设备产品甲产品乙产品丙费用/有效台时A15x110x6300/6000A27x29x712x8321/10000B16x38(x6+x7)250/4000B24x411x8783/7000B37x5200/4000原料单价(元/件)0.250.350.5销售单价(元/件)1.252.002.8生产计划问题1.4线性规划问题应用实例要做100套钢架，每套用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料长7.4m，问应如何下料使所用料最省？方案长度(m)123456782.9120101002.1002211301.531203104合计7.47.37.27.16.66.56.36残料00.10.20.30.80.91.11.4下料问题1.4线性规划问题应用实例解：设采用方案i下料的原料根数为xi方案长度(m)123456782.9120101002.1002211301.531203104合计7.47.37.27.16.66.56.36残料00.10.20.30.80.91.11.4下料问题1.4线性规划问题应用实例解：设采用方案i下料的原料根数为xi方案长度(m)123456782.9120101002.1002211301.531203104合计7.47.37.27.16.66.56.36残料00.10.20.30.80.91.11.4下料问题1.4线性规划问题应用实例产品名称规格要求单价(元/kg)甲原材料1不少于50%,原材料2不超过25%50乙原材料1不少于25%,原材料2不超过50%35丙不限25某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问该厂应如何安排生产，使利润为最大？原材料名称每天最多供应量单价(元/kg)11006521002536035配料问题1.4线性规划问题应用实例解：设xij

表示第i种（i=1(甲)、i=2(乙)、i=3(丙)）产品中原料j的含量。对于甲：x11，x12，x13；产品甲的产量为x11+x12+x13

对于乙：x21，x22，x23；产品乙的产量为x21+x22+x23

对于丙：x31，x32，x33；产品丙的产量为x31+x32+x33

对于原料1：x11，x21，x31；原料1的需求量为x11+x21+x31

对于原料2：x12，x22，x32；原料2的需求量为x12+x22+x32

对于原料3：x13，x23，x33；原料3的需求量为x13+x23+x33

目标函数：利润最大，利润=收入-原料支出

约束条件：规格要求4个，供应量限制3个配料问题1.4线性规划问题应用实例利润=总收入-总成本=三种产品单价*产品数量-使用的原料单价*原料数量目标函数：Maxz=50(x11+x12+x13)+35(x21+x22+x23)+25(x31+x32+x33)-65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33)=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

产品名称单价(元/kg)原材料名称单价(元/kg)甲50165乙35225丙25335配料问题1.4线性规划问题应用实例约束条件（1）：产品规格要求

x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+