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

1、线性规划问题的提出 线性规划的基本概念 线性规划的数学模型 线性规划问题的标准形式,1.1 一般线性规划问题及其数学模型,线性规划简介,Linear Programming, LP 是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。 线性规划通常研究资源的最优利用、设备最佳运行、成本收益平衡和网络配送等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。,线性规划

2、简介,1902年，Julius Farkas发表论文阐述线性规划的问题； 1938年，英国，康德进行较为详细的研究； 1947年，英国，George Dantzig单纯形法，从而为线性规划的推广奠定了基础。,1.1.1问题的提出,例1: 生产计划问题,决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions）,基本概念,问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,它是决策变量的函数,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。,

3、是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。,第1步 -确定决策变量,设 I的产量 II的产量 利润,第2步 -定义目标函数,max Z = x1 + x2,Note：max stands for maximize,max Z = 2 x1 + 3 x2,第2步 -定义目标函数,第3步 -表示约束条件,x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0,该计划的数学模型,目标函数 max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,线性规划问题的共同特征,一组决

4、策变量X表示一个方案,一般X大于等于零。 约束条件是线性等式或不等式。 目标函数是线性的。 求目标函数最大化或最小化,方法总结：如何建立线性规划数学模型 研究的问题是求什么，即设置决策变量； （由研究者供决策部门加以确定，故得名） 问题要达到的目标是什么，即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值； 限制达到目标的条件是什么，即建立约束条件。,例2 饼干生产问题 某厂生产两类饼干，需搅拌机A1，成形机A2 ，烘箱A3三种设备，每天的所需机时及机时限制，利润指标如下表，问如何制订生产计划，可使获得最高利润？,【解】 设x1、x2为每天生产 、 两种饼干的产量（单位：吨

5、），则目标函数是,约束条件有：,搅拌机约束,成形机约束,烘箱约束,非负约束,本问题的数学模型,某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表二所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？,例3、最优生产计划问题,表二 产品资源消耗,【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型为：,目标函数,资源约束,例4 最优人员安排 某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表三所示。,表三 营业员需要量统计表,商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。