《机械优化设计线性规划》由会员分享，可在线阅读，更多相关《机械优化设计线性规划（56页珍藏版）》请在金锄头文库上搜索。
1、机械优化设计 第五章第五章 线性规划线性规划第一节线性规划的标准形式与基本性质第一节线性规划的标准形式与基本性质第一节线性规划的标准形式与基本性质第一节线性规划的标准形式与基本性质第二节基本可行解的转换第二节基本可行解的转换第二节基本可行解的转换第二节基本可行解的转换第三节单纯形方法第三节单纯形方法第三节单纯形方法第三节单纯形方法 线性规划线性规划第四节单纯形法应用举例第四节单纯形法应用举例第四节单纯形法应用举例第四节单纯形法应用举例第五节修正单纯形法第五节修正单纯形法第五节修正单纯形法第五节修正单纯形法机械优化设计* 目标函数和约束条件都是线性的，像这类约束目标函数和约束条件都是线性的，像这
2、类约束函数和目标函数都是为线性函数的优化问题，称作函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解的，但是也有采用线性逼近方法求解非线性问题的。非线性问题的。此外，线性规划方法还常被用作解决非线性问题的此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优就是采用线性规
3、划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。化问题，线性规划方法就更有用了。第五章线性规划第五章线性规划机械优化设计*解：设生产解：设生产A、B两产品分别两产品分别为为x1, x2台，则该问题的优台，则该问题的优化数学模型为：化数学模型为：例例5-1： 某工厂要生产某工厂要生产A、B两种产两种产品，每生产一台产品品，每生产一台产品A 可获产值可获产值2万万元；需占用一车间工作日元；需占用一车间工作日3天，二车天，二车间工作日间工作日6天；每生产一台产品天；每生产一台产品B 可可获产值获产值1万元；需占用一车间工作日万元；需占用一车间工作日5天，二车间工作日天，二车间工作日2天
4、。现一车间可天。现一车间可用于生产用于生产A、B产品的时间产品的时间15天，二天，二车间可用于生产车间可用于生产A、B产品的时间产品的时间24天。试求出生产组织者安排天。试求出生产组织者安排A、B两两种产品的合理投资产数，以获得最大种产品的合理投资产数，以获得最大的总产值。的总产值。一、线性规划实例一、线性规划实例机械优化设计*例例5-2：生产甲种产品每件需使用材料生产甲种产品每件需使用材料9kg9kg、3 3个工时、个工时、4kw4kw电，获电，获利润利润6060元。生产乙种产品每件需用材料元。生产乙种产品每件需用材料4kg4kg、1010个工时、个工时、5kw5kw电，电，可获利可获利12
5、0120元。若每天能供应材料元。若每天能供应材料360kg360kg，有，有300300个工时，能供个工时，能供200kw200kw电。试确定两种产品每天的产量，使每天可能获得的电。试确定两种产品每天的产量，使每天可能获得的利润最利润最大大？ 分析：分析：每天生产的每天生产的甲、乙两种产品甲、乙两种产品甲、乙两种产品甲、乙两种产品分别为分别为 件件 （工时约束）（工时约束）（电力约束）（电力约束）（材料约束）（材料约束）( (利润最大利润最大) )机械优化设计*将其化成线性规划标准形式：将其化成线性规划标准形式：求求使使且满足且满足机械优化设计*例5-3：某厂生产甲、乙两种产品，已知：两种产品
6、分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？机械优化设计*日利润最大日利润最大生产能力限制生产能力限制劳动力限制劳动力限制变量非负变量非负解解: 设甲、乙两种产品的日产件数分别为设甲、乙两种产品的日产件数分别为s.t.机械优化设计*建模例建模例1： 某公司有钢材、铝材、铜材某公司有钢材、铝材、铜材1200t，800t和和650t，拟调往，拟调往物资紧张的地区甲、乙、丙。已知甲、乙、丙对上述物资的总需求分物资紧张的地区
7、甲、乙、丙。已知甲、乙、丙对上述物资的总需求分别为：别为：900t，800t和和1000t。各种物资在各地销售每吨的获利如下表。各种物资在各地销售每吨的获利如下表所示。试问公司应如何安排调运计划，才能获利最大？建立该问题的所示。试问公司应如何安排调运计划，才能获利最大？建立该问题的数学模型。数学模型。钢材钢材铝材铝材铜材铜材甲甲260300400乙乙210250550丙丙180400350物资物资获利获利地区地区机械优化设计*建模例建模例2： 某工厂生产某工厂生产A、B、C三种产品，现根据订货合同以及生三种产品，现根据订货合同以及生产状况制定产状况制定5月份的生产计划，已知合同甲为：月份的生产
8、计划，已知合同甲为：A产品产品1000件，单件件，单件价格为价格为500元，违约金为元，违约金为100元元/件；合同乙为：件；合同乙为：B产品产品500件，单件件，单件价格为价格为400元，违约金为元，违约金为120元元/件；合同丙为：件；合同丙为：B产品产品600件，单件件，单件价格为价格为420元，违约金为元，违约金为130元元/件；件；C产品产品600件，单件价格为件，单件价格为400元，元，违约金为违约金为90元元/件；有关各产品生产过程所需工时以及原材料的情况件；有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标，建立该工厂的生产计划线性规划模型见下表。试以利润为目标，
9、建立该工厂的生产计划线性规划模型 。工序工序1工序工序2工序工序3原材料原材料1 原材料原材料2其他成本其他成本产品产品A /件件2323410产品产品B /件件1132310产品产品C /件件2124210总工时或原材料总工时或原材料460040006000100008000工时或原材料成本工时或原材料成本（元）（元）1510102040机械优化设计*建模例建模例3： 成批生产企业年度生产计划的按月分配成批生产企业年度生产计划的按月分配 。在成批生产的机械制造企业中，不同产品劳动量的结构上可能在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间
10、，另一种有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按产品的劳动量可能集中在铣床和其他机床上。因此，企业在按月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。 在年度计划按月分配时一般要考虑在年度计划按月分配时一般要考虑:1）从数量和品种上保从数量和品种上保证年度计划的完成；证年度计划的完成；2）成批的产品尽可能在各个月内均衡生）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；产或集中在几个月内生产；3）由于生产技术准备等方面原因，）由于生产技术准备等方面原因，某
11、些产品要在某个月后才能投产；某些产品要在某个月后才能投产；4）根据合同要求，某些产）根据合同要求，某些产品要求在年初交货；品要求在年初交货；5）批量小的产品尽可能集中在一个月或）批量小的产品尽可能集中在一个月或几个月内生产出来，以便减少各个月的品种数量等等。如何在几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。满足上述条件的基础上，使设备均衡负荷且最大负荷。机械优化设计*线性规划数学模型的一般形式：线性规划数学模型的一般形式：求求使使且满足且满足说明：说明：1 1）m=n,m=n,唯一解唯一解2 2）mn,mn,无解无解3 3）mn,mm)
12、为转轴元素，此元素，此时xt进入入基，基， xs出基。出基。这样就完成了从一个基本解到另一个基本就完成了从一个基本解到另一个基本解的解的转换机械优化设计*解：用解：用a11, a22作作为轴元素元素进行两次行两次转轴运算：运算：例：例：给定如下方程定如下方程组，试进行基本解的行基本解的转换运算。运算。得到一得到一组基本解：基本解： x1=-12 x2=-20 x3=x4=x5=0机械优化设计*用用a25作作为轴元素元素进行第三次行第三次转轴运算：运算：又得到一又得到一组基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0此此时x5进入基，入基， x2出基。出基。机械优化设计*二、
13、从一个基本可行解转到另一个基本可行解二、从一个基本可行解转到另一个基本可行解当已经得到一组基本可行解，若要求把当已经得到一组基本可行解，若要求把xk选进基本变量，选进基本变量，并使下一组基本解是可行解的话，并使下一组基本解是可行解的话，则在第则在第k k列要选取不为列要选取不为任何负值的元素作为转轴元素任何负值的元素作为转轴元素机械优化设计*alk作为转轴元素进行转轴运算：作为转轴元素进行转轴运算：机械优化设计*机械优化设计*方程组第一行发生的变化：方程组第一行发生的变化：机械优化设计*alk作作为轴元素，元素，xk选进基本变量后，选进基本变量后， xk的取值由零变成了的取值由零变成了一个正值
14、一个正值 ，则原来各基本变量的取值变为，则原来各基本变量的取值变为: : 若是基本可行解若是基本可行解, 应该保保证各差各差值最小者最小者为零零 : 决定了离基决定了离基变量量为xi机械优化设计*若想用若想用xk取代取代xl成成为可行解中的基本可行解中的基本变量，就量，就应该选 所对应的行成为转轴行，即所选取的行要满所对应的行成为转轴行，即所选取的行要满足条件足条件: :规则规则机械优化设计*例：例：基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0基本基本变量量x1、x5 基本可行解的基本可行解的转换： 1）x2、x4系数全部系数全部为负，只能，只能选取取x3所在的第所在的第
15、3列列为转轴行行 2） , 由于由于 ，则取第一行取第一行为转轴行行, 于是取于是取a13=2为转轴元素，使元素，使x3取代取代x1成成为基本基本变量。量。机械优化设计*经转轴运算得：运算得：得基本可行解：得基本可行解： 机械优化设计*结论结论：可把松驰变量作为初始基本可行解中的一部分基本可把松驰变量作为初始基本可行解中的一部分基本 变量。变量。三、初始基本可行解的求法三、初始基本可行解的求法原始约束条件原始约束条件:引入松驰变量引入松驰变量:可得一组基本可行解：可得一组基本可行解：机械优化设计*一、单纯形法的基本思想从一个初始基本可行解X0出发，寻找目标函数有较大下降的一个新的基本可行解X1
16、,代替原来的基本可行解X0，如此完成一次迭代。随后作出判断，如果未达到最优解，则继续迭代下去。因为基本可行解的数目有限，所以经过有限次迭代一定能达到最优解。采用单纯形法求解线性规划问题，主要应解决以下三个问题：采用单纯形法求解线性规划问题，主要应解决以下三个问题：（1）如何确定初始基本可行解；）如何确定初始基本可行解；（2）如何由一个基本可行解迭代出另一个基本可行解，）如何由一个基本可行解迭代出另一个基本可行解，同同时保证目标函数的下降性时保证目标函数的下降性；（3）如何判断一个基本可行解是否为最优解。）如何判断一个基本可行解是否为最优解。机械优化设计*二二. .最优解规则最优解规则 对应一组
17、基本可行解：对应一组基本可行解： 前前m个变量组成基本可行解的基本变量个变量组成基本可行解的基本变量相应的目标函数值为相应的目标函数值为: :机械优化设计*经过转轴运算得到另经过转轴运算得到另一组基本可行解为一组基本可行解为:其中：其中：进基变量进基变量xk出基变量出基变量xs机械优化设计*对应的目标函数为对应的目标函数为: :机械优化设计*由于要求由于要求结论结论: :一旦所有的一旦所有的 , , 即可停止即可停止 转轴运算转轴运算, ,对应的可行解就是对应的可行解就是最优解。最优解。r是是 对线性规划问题的解进行最优性检验的标对线性规划问题的解进行最优性检验的标 志，称之为检验数。志，称之
18、为检验数。机械优化设计*具体计算时应选取具体计算时应选取: :由于有可能同时有几组由于有可能同时有几组 都为负值都为负值最速变化规则最速变化规则机械优化设计*1）最速变化规则决定）最速变化规则决定进基的进基的非基本变量非基本变量结论结论：2） 规则决定了规则决定了出基的出基的基本变量基本变量3）若对基本可行解）若对基本可行解X，所有检验数，所有检验数rk 0，则，则X 为最优解。为最优解。 机械优化设计*例例5-35-3某某建建筑筑单单位位拟拟盖盖一一批批二二人人、三三人人和和四四人人的的宿宿舍舍单单元元，要要确确定定每每一一种种宿宿舍舍单单元元的的数数目目，以以获获得得最最大大利利润润。其其
19、限限制制条条件件如如下下：1 1）预预算算不不能能超超过过90009000千千元元。2 2）宿宿舍舍单单元元总总数数不不得得少少于于350350套套。3 3）每每类类宿宿舍舍单单元元的的百百分分比比为为：二二人人的的不不超超过过总总数数的的20%20%，三三人人的的不不超超过过总总数数的的60%60%，四四人人的的不不超超过过总总数数的的40%40%（百百分分比比总总和和超超过过100100，这这是是上上限限）。4 4）建建造造价价格格为为：二二人人的的宿宿舍舍单单元元是是2020千千元元，三三人人的的宿宿舍舍单单元元是是2525千千元元，四四人人的的宿宿舍舍单单元元是是3030千千元元。5
20、5）净净利利润润为为：二二人人的的宿宿舍舍单单元元是是2 2千千元元，三三人人的的宿宿舍舍单单元元是是3 3千千元元，四四人人的的宿宿舍舍单单元元是是4 4千千元。元。解：略解：略机械优化设计*修正单纯形法的迭代过程如下：（1）根据问题的需要，加入松弛变量或人工变量，写出初始）根据问题的需要，加入松弛变量或人工变量，写出初始基方阵基方阵E，求，求E-1和基本解和基本解（2）计算）计算 和和 ，对应于非基本变量计，对应于非基本变量计算相应的算相应的 。若所有。若所有 （对极小化问题），则（对极小化问题），则x为最优解；否则转至步骤（为最优解；否则转至步骤（3）。）。（3）选取进入新的基方阵的）选
21、取进入新的基方阵的 ，找出，找出 ，计算，计算 。若所有。若所有 ，则无解；否则转至步骤，则无解；否则转至步骤（4）。）。机械优化设计*修正单纯形法的迭代过程如下：（4）计算）计算 ，选取离开，选取离开基方阵的基方阵的 ，形成新的基方阵，形成新的基方阵 ，转至步骤（，转至步骤（5）。）。（5）计算新的矩阵）计算新的矩阵 的逆矩阵的逆矩阵 和和 。每迭代一次，就构成一个新的逆矩阵。每迭代一次，就构成一个新的逆矩阵。然后转至步骤（然后转至步骤（1）重复计算，直到求得最优解和相应的目标）重复计算，直到求得最优解和相应的目标函数值（极小值或极大值）。函数值（极小值或极大值）。机械优化设计*E E N N D D ? ?
