[工学]2线性规划及其对偶问题.ppt

线性规划及其对偶问题 1 线性规划问题及其数学模型 2 线性规划问题的图解法 3 单纯形法 4 对偶问题 5 EXCEL求解线性规划 6 灵敏度分析 1 线性规划问题及其数学模型 例 某建筑设计院设计每万ｍ２办公建筑和工业厂房需要的建筑师、结构工程师、设备工程师和电气工程师的平均人数列在表。问该院应如何安排设计任务，才能使设计费收入最大? 隐含的假设 比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , cj为确定值 2 线性规划问题的图解法 直观结论 线性规划问题的解有四种情况 唯一最优解 无穷多最优解 无有限最优解 无可行解 若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）； 若线性规划问题有最优解，则 唯一最优解对应于可行域的一个顶点； 无穷多个最优解对应于可行域的一条边； 3 单纯形法 3.1 线性规划问题的标准形式 3.2 线性规划问题的基本解 3.3 单纯形法的基本思想 3.1 线性规划问题的标准形式 3.2 线性规划问题的基本解 3.3 单纯形法 例 某房地产公司欲开发一七通一平空地，总面积2500m2。公司原计划开发商业楼1000m2，住宅楼5250m2。请根据下列前提条件，确定其是否最佳开发方式。 (1)根据规划要求：沿马路建商业房，为4层楼框架结构，其余为砖混住宅，为6层楼；容积率为2.5，建筑密度≤50%。 (2)开发日期为2003年12月，建筑物完成时间不超过一年半。 (3)根据预测，一年半以后商业楼平均造价为1400元/m2，砖混住宅平均造价为950元/m2 ，不计土地成本。 (4)预计建筑物完成后商业楼及住宅均可全部售出，商业楼出售当时的平均售价为2400元/m2 ，住宅楼出售当时的平均售价为1700元/m2 。 (5)物业出售时的税费为总额的5%。 (6)公司投入资金不超过650万元。 分析： 容积率＝总建筑面积/总占地面积 建筑密度＝建筑基地总面积/总占地面积 (1)总建筑面积 2500×2.5=6250m2 (2)建筑基地总面积 2500×50%＝1250m2 (3)商业楼每平方米的利润: (0.24－0.14一0.24×5%)=0.088(万元/m2) (4)住宅楼每平方米的利润: (0.17一0.095一0.17×5%)=0.0665(万元/m2) 设商业楼建筑面积为x1m2;砖混住宅建筑面积为x2m2 求x1、x2 目标函数max Z=0.088 x1＋0.0665 x2 满足: x1＋x2≤6250 x1/4+x2/6≤1250 0.14 x1十0.095 x2≤650 x1、x2≥0 为了便于计算，变换一下约束条件及目标函数。（由于在整个价值最优程序中只是相对的价值是重要的，而不是它们绝对值。绝对值的值只影响目标函数的最后值，但不影响设计变量的最优值）因此，我们可以将其变换为: x1/4+x2/6≤1250 转变为 3 x1十2 x2≤15000 0.14 x1十0.095 x2≤650 转变为 1.4737 x1十x2≤6842 max Z=0.088 x1＋0.0665 x2 转变为 max Z‘= Z /0.0665＝1.323 x1＋x2 数学模型 max Z‘= 1.323 x1+x2 x1＋x2≤6250 3 x1十2 x2≤15000 1.4737 x1十x2≤6842 x1、x2≥0 例 某项目经理部有三种住宅可以承建。三种住宅每百平方米的利润分别为6000元、8000元和5000元。承建时主要考虑木工和瓦工工时的安排。由于现在瓦工空闲，应尽量多安排；而可支配的木工工时虽然仅有26000个，但不允许有任何空闲。三种住宅每百平方米需用的瓦工和木工工时列在表中。另外，公司要求至少安排12000瓦工工时。问三种住宅各承建多少平方米．可使利润最大? 设：由32.5#水泥配制的C20，C25，C30混凝土各为x1、x2、x3， 由42.5#水泥配制的C20，C25，C30混凝土各为x4、x5、x6 则32.5#水泥的总耗量为 253x1＋302x2＋362x3 42.5#水泥的总耗量为 211x4＋257x5＋302x6 案例:建设监理公司监理工程师配置问题 某建设监理公司(国家甲级)，侧重国家大中型项目的监理，仅在武汉市就正在监理七项工程，总投资均在5000万元以上。由于工程开工的时间不同，多工程工期之间相互搭接，具有较长的连续性，2002年监理的工程量与2003年监理的工程量大致相同。 每项工程安排多少监理工程师进驻工地，一般是根据工