工业系统工程线性规划模型.ppt

1、线性规划模型,石河子大学经贸学院 程 钢,线性规划是在一组线性不等式或等式方程的约束条件下，求一线性目标函数的极值的数学方法。 线性规划模型由两部分构成：约束条件与目标函数。其中的线性约束方程，是决策者在追求其目标时所面临的各种限制条件，这些约束条件，即有可能是资源方面的，也有可能是来自经营自身的，或来自外部经济、技术环境等方面，目标函数是所追求目标的数量化表示。,线性规划法-例1,某农户有耕地20亩,可以采用甲乙两种种植方式组织生产。其中甲方式每亩需要投资280元，投工6个工日，可获取收入1000元，已方式每亩需投资150元，投工15个工日，可获取收入1200元。该农户共有资金4200元，2

2、40个劳动工日，问如何安排甲乙两种方式的生产，可使总收入最大。,线性规划模型的基本假设,投入产出的比例不变,价格固定不变,产品间的边际替换率不变,线性规划的求解,图解法,单纯形法，1947,梯度投影法 1984,线性规划的求解-图解法,可行解：满足规划中所有约束条件及非负约束的决策变量的一组取值，仅与约束条件有关，与目标函数无关。,可行（解）域：由所有可行解构成的集合。任何一个线性规划问题的可行域，都是一个有限或无限的凸多边形，每个角称为可行域的极点。,最优解：是目标函数达到最优（最大或最小）的可行解。,最优性定理：若一个线性规划问题有解，则最优解一定可以在可行域的某个极点上可以找到一个最优解

3、。同时也可能有其他最优解存在，当它们也只可能存在于可行域的其他极点或是边界上。,线性规划的求解-图解法,O(0,0) A(0,16) B(6.7,13.3) C(9.2,10.8) D(15,0),ZO=0 ZA=19200 ZB=22660 ZC=22160 ZD=15000,线性规划的求解-图解法,线性规划法-例2,某饲料公司用甲、乙两种原料配置饲料，甲、乙两种原料的营养成分及配合饲料中所含各种营养成分最低含量由下表给出，已知甲、乙两种原料的价格分别为10元和20元，求满足营养需要的饲料最小成本配方。,线性规划的求解-图解法,A(0,15) B(2.5,7.5) C(9,1) D(15,0

4、),ZA=300 ZB=175 ZC=110 ZD=150,线性规划的求解-图解法,线性规划的对偶规划,原问题,对偶问题,对偶性质,原问题与对偶问题互为对偶。 原问题与对偶问题或都有最优解(最优值相同)，两最优解之间存在一定的关系，或都没有最优解。 可知:研究对偶问题可以简化计算(当原问题很复杂时,可先求解对偶问题,再根据一定的关系得出原问题的最优解。,对偶变量的经济解释,对偶变量yi在经济上表示原问题第i种资源的边际贡献，即当第i种资源增加一个单位时，相应的目标值z的增量； 对偶问题的最优解yi*是原问题第i种资源的影子价格 应用：1.出租资源或设备时,租金价格的设定(至少高于该资源在企业内的影子价格)； 2.企业内资源I的存量设定(当资源I的影子价格=市场价格时,可买进该资源;否则卖出)； 3.调整资源的分配量以增加利润,线性规划模型的建立,选择决策变量,确定目标函数,设定约束条件,数据的获取,线性规划模型的局限性,线性以技术不变和价格不变为前提，不能有效的处理涉及到时间的问题，因此，线性规划以短期规划为基础。,农业生产中，投入产出不完全是线性关系，在技术相对稳定的条件下，资源报酬递减规律起作用，而线性规划隐含着资源的编辑报酬固定，因此要完全满足其假设