线性规划第一讲一般线性规划问题的数学模型.ppt

线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式 1 1一般线性规划问题及其数学模型 线性规划简介 LinearProgramming LP是运筹学的重要分支之一 在实际中应用得较广泛 其方法也较成熟 借助计算机 使得计算更方便 应用领域更广泛和深入 线性规划通常研究资源的最优利用 设备最佳运行 成本收益平衡和网络配送等问题 例如 当任务或目标确定后 如何统筹兼顾 合理安排 用最少的资源 如资金 设备 原标材料 人工 时间等 去完成确定的任务或目标 企业在一定的资源条件限制下 如何组织安排生产获得最好的经济效益 如产品量最多 利润最大 线性规划简介 1902年 JuliusFarkas发表论文阐述线性规划的问题 1938年 英国 康德进行较为详细的研究 1947年 英国 GeorgeDantzig单纯形法 从而为线性规划的推广奠定了基础 1 1 1问题的提出 例1 生产计划问题 决策变量 Decisionvariables 目标函数 Objectivefunction 约束条件 Constraintconditions 基本概念 问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 它是决策变量的函数 指决策变量取值时受到的各种资源条件的限制 通常表达为含决策变量的等式或不等式 是问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 第1步 确定决策变量 设 I的产量 II的产量 利润 第2步 定义目标函数 maxZ x1 x2 Note maxstandsformaximize maxZ 2x1 3x2 第2步 定义目标函数 第3步 表示约束条件 x1 2x2 84x1 164x2 12x1 x2 0 该计划的数学模型 目标函数maxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 x1 x2 线性规划问题的共同特征 一组决策变量X表示一个方案 一般X大于等于零 约束条件是线性等式或不等式 目标函数是线性的 求目标函数最大化或最小化 方法总结 如何建立线性规划数学模型研究的问题是求什么 即设置决策变量 由研究者供决策部门加以确定 故得名 问题要达到的目标是什么 即建立目标函数 目标函数一定是决策变量的线性函数并且求最大值或求最小值 限制达到目标的条件是什么 即建立约束条件 例2饼干生产问题某厂生产两类饼干 需搅拌机A1 成形机A2 烘箱A3三种设备 每天的所需机时及机时限制 利润指标如下表 问如何制订生产计划 可使获得最高利润 解 设x1 x2为每天生产 两种饼干的产量 单位 吨 则目标函数是 约束条件有 搅拌机约束 成形机约束 烘箱约束 非负约束 本问题的数学模型 某企业在计划期内计划生产甲 乙 丙三种产品 这些产品分别需要要在设备A B上加工 需要消耗材料C D 按工艺资料规定 单件产品在不同设备上加工及所需要的资源如表二所示 已知在计划期内设备的加工能力各为200台时 可供材料分别为360 300公斤 每生产一件甲 乙 丙三种产品 企业可获得利润分别为40 30 50元 假定市场需求无限制 企业决策者应如何安排生产计划 使企业在计划期内总的利润收入最大 例3 最优生产计划问题 表二产品资源消耗 解 设x1 x2 x3分别为甲 乙 丙三种产品的产量数学模型为 目标函数 资源约束 例4最优人员安排某商场决定 营业员每周连续工作5天后连续休息2天 轮流休息 根据统计 商场每天需要的营业员如表三所示 表三营业员需要量统计表 商场人力资源部应如何安排每天的上班人数 使商场总的营业员最少