线性规划模型目标函数ppt课件.ppt

《线性规划模型目标函数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划1.线性规划内容一、线性规划模型二、线性规划模型的标准形式三、用matlab解线性规划2.线性规划所解决的问题具有以下共同的特征：2.存在一定的限制条件（即约束条件），这些限制条件是关于未知数的一组线性等式或线性不等式来表示。1.每一个问题都用一组未知数（x1，x2，…，xn）表示某一方案；这些未知数的一组定值就代表一个具体方案。由于实际问题的要求，通常这些未知数取值是非负的。3.有一个目标要求，称为目标函数。目标函数可表示为一组未知数的线性函数。根据问题的需要，需求目标函数实现最大化或最小化。一、线性规划模型3.一般的线性规

2、划问题的数学模型：目标函数(线性函数）：Min(max)z=c1x1+c2x2+…+cnxn约束条件(s.t.)：a11x1+a12x2+…+a1nxn(≥)b1a21x1+a22x2+…+a2nxn(≥)b2...am1x1+am2x2+…+amnxn(≥)bmx1，x2，…，xn≥0式中()可以是关系符号：>,<,=,≥,≤中的任意一个（线性等式或线性不等式）。一、线性规划模型4.线性规划模型的求解：图解法单纯形法matlab软件求解。以下介绍几种常见的线性规划问题。5.问题一：任务分配问题：某车间有甲、乙两台车床，可用于加工三种

3、工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？引例16.解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：目标函数：约束条件：7.问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件

4、/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：引例28.故目标函数为：约束条件为：9.线性规划模型目标函数：约束条件：注：本问题应还有一个约束条件：x1、x2取整数.故它是一个整数线性规划问题.这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规

5、划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.10.问题三：投资决策问题某公司拟在某市东、西、南三区建立门市部，拟议中有7个位置（点）Ai(i=1,2,…,7)可供选择。规定东区在A1、A2、A3三个点中至多选两个。西区A4、A5两个点中至少选一个。南区A6、A7两个点中至少选一个。并知道如果选用Ai点，则投资为bi元，估计每年可获利为ci元，但投资总额不得超过B元。问应该选择哪几个点可使年利润为最大？解设则投资决策问题归结为一个线性规划模型：引例311.故

6、目标函数为：约束条件为：s.t.这是一个0-1规划问题12.几个问题都是典型的最值问题。其中，“Min或Max”是英文单词“Minimize或Maximize”的缩写，含义为“最小化或最大化”；“s.t.”是“subjectto”的缩写，表示“受约束于…”。线性规划是运筹学的一个重要分支，应用很广。线性规划问题可以描述为求一组非负变量，这些非负变量在一定线性约束的条件下，使一个线性目标函数取得极大（极小）值的问题。由于式中的目标函数与约束条件均为线性函数，故被称为线性规划问题。13.线性规划的标准形式目标函数：Minz=c1x1+c2

7、x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0二、线性规划模型的标准形式14.线性规划的一般形式目标函数：Min(max)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn(≥)b1a21x1+a22x2+…+a2nxn(≥)b2...am1x1+am2x2+…+amnxn(≥)bmx1，x2，…，xn≥0式中()可以是关系符号：>,<,=,≥,≤中的任意一个

8、。二、线性规划模型的标准形式15.实际问题中的优化模型x是决策变量f(x)是目标函数gi(x)0是约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(