1-1LP模型的结构及建模步骤及标准型

2020年2月2日11时27分1第一章线性规划模型和单纯形法1.1线性规划模型的结构及建模步骤主讲：郑来运机械工程学院2020年2月2日11时27分光华食品厂主要生产葱油饼干（Ⅰ型）和苏打饼干（Ⅱ型）。根据销售部门提供的信息可知，目前这两种饼干在市场上都很畅销，该厂能生产多少，市场就能卖出多少。但从生产部门得知，有三种关键设备即搅拌机、成型机、烘箱的生产能力，限制了该厂的饼干生产。该公司每天生产这两种饼干的量应为多少，可使其利润最大？2020年2月2日11时27分产品I产品2如何安排生产使利润最大？2020年2月2日11时27分光华食品厂主要生产葱油饼干（Ⅰ型）和苏打饼干（Ⅱ型），销售利润分别为500元/吨和400元/吨。根据销售部门提供的信息可知，目前这两种饼干在市场上都很畅销，该厂能生产多少，市场就能卖出多少。但从生产部门得知，有三种关键设备即搅拌机、成型机、烘箱的生产能力，限制了该厂的饼干生产。该公司每天生产这两种饼干的量应为多少，可使其利润最大？其具体数据如表所示：例1资源利用问题单位时耗(小时/吨）资源设备ⅠⅡ每天现有工时搅拌机3415成型机215烘箱2211利润（百元/吨）542020年2月2日11时27分1212121212max54341525s.t.2211,0Zxxxxxxxxxx例1资源利用问题121,3,max1700xxZ（吨）（吨）（元）即：生产葱油饼干(Ⅰ型)1吨苏打饼干(Ⅱ型)3吨企业利润：1700元2020年2月2日11时27分本节重点和难点及教学目标重点与难点：如何建立线性规划问题的数学模型？(建模条件、步骤及相应的技巧)教学目标：掌握建模的步骤和方法，能根据实际背景抽象和建立适当的线性规划模型。LinearProgrammingproblemanditsModels2020年2月2日11时27分例1资源利用问题单位时耗(小时/吨）资源设备ⅠⅡ每天现有工时搅拌机3415成型机215烘箱2211利润（百元/吨）54光华食品厂主要生产葱油饼干（Ⅰ型）和苏打饼干（Ⅱ型），销售利润分别为500元/吨和400元/吨。根据销售部门提供的信息可知，目前这两种饼干在市场上都很畅销，该厂能生产多少，市场就能卖出多少。但从生产部门得知，有三种关键设备即搅拌机、成型机、烘箱的生产能力，限制了该厂的饼干生产。该公司每天生产这两种饼干的量应为多少，可使其利润最大？其具体数据如表所示：2020年2月2日11时27分设：1x2xStep1--确定决策变量未知量，可由决策者决定和控制x1为饼干I的生产数量x2为饼干II的生产数量Step.12020年2月2日11时27分问题—目标：光华食品厂每天生产这两种饼干的量应为多少，可使其利润最大？目标函数：maxZ=5x1＋4x2Step2--定义目标函数单位时耗(小时/吨）资源设备ⅠⅡ每天现有工时搅拌机3415成型机215烘箱2211利润（百元/吨）541x2xStep.22020年2月2日11时27分为了达到该目标，怎么利用现有资源才最好呢?2020年2月2日11时27分光华食品厂主要生产葱油饼干（Ⅰ型）和苏打饼干（Ⅱ型）。根据销售部门提供的信息可知，目前这两种饼干在市场上都很畅销，该厂能生产多少，市场就能卖出多少。但从生产部门得知，有三种关键设备即搅拌机、成型机、烘箱的生产能力，限制了该厂的饼干生产。该公司每天生产这两种饼干的量应为多少，可使其利润最大。其具体数据如表所示：设备，现有工时受限制如何利用现有资源才最好？单位时耗(小时/吨）资源设备ⅠⅡ每天现有工时搅拌机3415成型机215烘箱2211利润（百元/吨）54辨认哪些是决策的关键影响因素？在选取这些关键因素时存在哪些资源和环境的限制？2020年2月2日11时27分搅拌机的工时限制：3x1+4x2≤15成型机的工时限制：2x1+x2≤5烘箱的工时限制：2x1+2x2≤11非负约束：产量非负x1≥0,x2≥0单位时耗(小时/吨)资源设备ⅠⅡ每天现有工时搅拌机3415成型机215烘箱2211利润(百元/吨)54Step3--表示约束条件约束条件Step.32020年2月2日11时27分(1)决策变量：x1为饼干I的生产数量，x2为饼干II的生产数量。(2)目标函数：目标是企业利润最大化maxZ=5x1+4x2(3)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。搅拌机的工时限制的约束条件表达为3x1+4x2≤15同理，成型机的工时限制约束条件表达为2x1+x2≤5烘箱的工时限制，其约束条件为2x1+2x2≤11非负约束：产品的产量为非负x1≥0，x2≥0LP模型：1212121212max54341525s.t.2211,0Zxxxxxxxxxx例1中建模的过程(小结)2020年2月2日11时27分解：用变量x1和x2分别表示光华食品厂生产饼干I和饼干II的数量。目标函数约束条件用数学语言完整描述1212121212max54341525s.t.2211,0Zxxxxxxxxxx2020年2月2日11时27分决策变量问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。一般取值要求非负目标函数目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小约束条件指决策变量取值时受到的各种资源条件的限制通常把各种限制条件表达为一组等式或不等式称约束条件约束条件是决策变量的线性函数线性规划模型的三要素总结当数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。2020年2月2日11时27分线性规划问题(LinearProgrammingproblem)研究内容：在一定的人力、财力、资源条件下，如何合理安排使用，使得效益最高；某项任务确定后，如何安排人、财、物，使之最省。线性规划问题的共同点：要求达到某些数量上的最大化或最小化；在一定的约束条件下追求其目标最优。2020年2月2日11时27分3.确定约束条件由决策变量所受的限制条件确定决策变量所要满足的约束条件。线性规划问题建模步骤总结1.确定决策变量根据影响所要达到目的的因素找到决策变量；2.写出目标函数由决策变量和所在达到目的之间的函数关系确定目标函数；2020年2月2日11时27分运筹学的工作步骤提出和形成问题建立数学模型求解解的检验解的控制解的实施2020年2月2日11时27分例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸。决策变量：取45%和92%的硫酸分别为x1和x2吨约束条件：求解二元一次方程组得解1008.092.045.01002121xxxx非负约束：x1≥0，x2≥0线性规划建模课堂练习------产品配比问题2020年2月2日11时27分若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？1008.092.085.073.045.03.01005432154321xxxxxxxxxx取这5种硫酸分别为x1、x2、x3、x4、x5，有若5种硫酸价格分别为400,700,1400,1900,2500元/t，如何使费用最小？123451234512345min400700140019002500100s.t.0.30.450.730.850.920.81000,1,2,...5jZxxxxxxxxxxxxxxxxj线性规划建模课堂练习------产品配比问题2020年2月2日11时27分线性规划模型举例2分析可控因素：从仓库iA运往jB的产品数量设为;1,2,1,2,3ijxij目标：总运费最小费用函数2311ijijijcx受控条件：从仓库运出总量不超过可用总量，运入各商场的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即123;1,2iiiixxxai12;1,2,3jjjxxbj蕴含约束：数量非负0;1,2,1,2,3ijxij运输问题：见课本第七页2020年2月2日11时27分建立数学模型min2311ijijijcx123;1,2iiiixxxais.t.12;1,2,3jjjxxbj0;1,2,1,2,3ijxij目标函数2020年2月2日11时27分线性规划模型---运输问题一个制造厂要把若干单位的产品从两个仓库2,1;iAi发送到零售点4,3,2,1;jBj，仓库iA能供应的产品数量为2,1;iai，零售点jB所需的产品的数量为4,3,2,1;jbj。假设供给总量和需求总量相等，且已知从仓库iA运一个单位产品往jB的运价为ijc。问应如何组织运输才能使总运费最小？2020年2月2日11时27分分析决策变量：从仓库iA运往jB的产品数量设为4,3,2,1,2,1;jixij目标：总运费最小目标函数minz=2141ijijijxc约束条件：从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即2,1;4321iaxxxxiiiii4,3,2,1;21jbxxjjj蕴含约束：数量非负4,3,2,1,2,1;0jixij运输问题模型2020年2月2日11时27分建立数学模型minz=2141ijijijxc2,1;4321iaxxxxiiiiis.t.4,3,2,1;21jbxxjjj4,3,2,1,2,1;0jixij运输问题模型2020年2月2日11时27分产品甲产品乙生产能力(小时)设备A73210设备B45200设备C24180计划利润(元/件)7065设：产品甲生产x1，产品乙生产x2目标：Maxz=70x1+65x2约束条件：设备A生产能力限制：7x1+3x2≤210设备B生产能力限制：4x1+5x2≤200设备C生产能力限制：2x1+4x2≤1801212121212max70657321045200..24180,0zxxxxxxstxxxx产量非负限制：x1，x2≥0决策变量决策变量目标函数约束条件三要素：1.决策变量2.目标函数3.约束条件例3生产计划2020年2月2日11时27分线性规划模型的一般形式一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2…,n，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi(i=1,2…,m)表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成112211112211211222221122()(,)(,)(,)0,1,2,,nnnnnnmmmnnmjMaxMinZcxcxcxaxaxaxorbaxaxaxorbaxaxaxorbxjn2020年2月2日11时27分njxj,...,2,1;为待定的决策变量，),,,(21ncccc为价值向量，njcj,...,2,1;为价值系数，12(,,...,)Tmbbbb为右端向量，矩阵mnmmnnaaaaaaaaaA212222111211为系数矩阵。线性规划模型的一般形式(注释)2020年2月2日11时27分紧缩形式线性规划模型的一般形式1()njjjMaxorMinZcx1(,)1,2,,..01,2,,nijjijjaxorbimstxjn在实际中一般xj≥0,但有时xj≤0或xj无符号限制。2020年2月2日11时27分()()..0MaxMinZCXAXorbstX或其中:线性规划问题的一般形式