数学建模--线性规划.ppt

线性规划（LP）的概念线性规划是指如何最有效或最佳地谋划经济活动。它所研究的问题有两类：一类是指一定资源的条件下，达到最高产量、最高产值、最大利润；一类是任务量一定，如何统筹安排，以最小的消耗去完成这项任务。如最低成本问题、最小投资、最短时间、最短距离等问题。前者是求极大值问题，后者是求极小值问题。总之，线性规划是一定限制条件下，求目标函数极值的问题。线性规划问题的一般形式简写形式LP向量形式LP向量形式LP矩阵形式松弛变量LP问题的标准形式转化为LP问题的标准形式的措施例a线性规划问题的数学模型特点运用线性规划方法的特点及局限性图解法线性规划模型的解法两个变量的线性规划模型的图解法单纯形法数学软件，如Lindo软件、Lingo软件、Matlab、Mathematica等图解法当决策变量个数n=2时，LP问题可以通过在平面上作图的方法求解，称为图解法。图解法求解的目的：1.判别线性规划问题的求解结构。2.在存在最优解的条件下，把问题的最优解找出来。例4：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？练习：一家广告公司想在电视、广播上做公司的宣传广告，其目的是尽可能多的影响顾客。下表是公司进行市场调查的结果这家公司希望总广告费用不超过750（千元），同时还要求：（1）受广告影响的妇女超过200万；（2）电视广告的费用不超过450（千元）；（3）电视广告白天至少播四次，最佳时段至少播出两次；（4）通过网络媒体、杂志做的广告要重复5到8次。1.问题的分析与模型的建立首先，确定决策变量，要求如何安排白天电视、最佳时段电视、网络媒体、杂志广告的次数，用符号表示，分别设定为；其次，确定所有广告的约束条件，广告总费用不超过750（千元），则有受广告影响的女顾客数不少于200万，则有电视广告的费用不超过450（千元）；且电视广告白天至至少播四次，最佳时段至少播出两次，则有由于通过网络媒体、杂志做的广告要重复5到8次，则有最后，确定问题的目标函数，由题意知确定广告编排方案，使得受各种广告影响的潜在顾客总数为：最多。则该问题完整的线性规划模型如下：2.用MATLAB计算机来求解c=[-350-880-430-180];将-c目标函数标准化A=[45862512;-260-450-160-100;458600;0010;0001];b=[750;-2000;450;8;8];Aeq=[];Beq=[];vlb=[4;2;5;5];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,,vlb,vub)3、利用Mathematica软件求解(1)直接输入表达式求解：命令：ConstrainedMin[目标函数，{约束条件}，{非负变量}]或ConstrainedMax[目标函数，{约束条件}，{非负变量}]输入时注意：（1）等号要写两次；（2）所有变量都必须是非负变量例5求解下列线性规划问题：解：用Mathematica编程如下：运行结果如下：[z=24,{x1?8,x2?0}]练习:求解下列线性规划问题（1）（2）s.t.s.t.例6有两个农场A和B，上级规定它们每月分别向三所大学D1，D2，D3的食堂送米65吨和110吨，这三所大学食堂每月需米分别为50吨、80吨和45吨。A农场离大学分别为15km、10km和11km，B农场离大学分别为14km、18km和25km。问如何分配这两个农场的供米，才能使总运量