线性规划问题及其数学模型ppt课件.ppt

《线性规划问题及其数学模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线形规划本章学习重点线性规划是运筹学中比较成熟的一个分支，它具有成熟而有效的求解方法，可以借助于计算机进行求解，在军事、经济等领域中具有广泛的应用。学习本章，要掌握线性规划的数学模型（建模以及把不同形式的线性规划问题化为标准形式的方法）、求解方法。线性规划的地位与研究进程作为一门科学的线性规划，最早可以追溯到20世纪30年代末，前苏联数学家康德洛维奇等人关于生产组织和运输问题研究所作的开拓性工作。1947年，美国数学家G.B.Dantzig以及美国空军的SCOOP研究小组提出了线性规划问题的一般性解法

2、即单纯形法,奠定了线性规划的理论基础。50年代后，随着电子计算机的介入，线性规划的应用越来越普遍，在生产、管理、军事等方面发挥着重要的作用。线性规划目前仍然还在发展，主要是：大型线性规划问题，线性规划解法研究等。线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回第一节线性规划问题及其数学模型问题的提出引例:生产计划问题产品甲产品乙如何安排生产使利润最大？什么是线性规划？在工业、农业、国防、建筑、交通运输、科研、商业等各种活动中，常常要求对资源进行统一分配、全面规划和合理调

3、度，以便从各种可能安排方案中找出最优的计划或设计，用以指导生产。在这类问题中，一方面有期望达到最优要求的目标（例如希望产值最高或消耗最少），另一方面又要受到一定条件的限制（例如人力、物力、财力的限制），如何安排才能使成效最高，消耗既定资源取得的收益最大，或达到既定收益所消耗的资源最少。这可以借助线性规划（LinearProgramming，LP）来解决。线性规划研究的内容在现有的资源条件下，如何充分利用资源，使任务或目标完成得最好（求极大化问题）。在给定目标下，如何以最少的资源消耗，实现这个目标（求极小化问

4、题）。是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步-确定决策变量设——甲的产量——乙的产量MaxZ=x1+x2决策变量第2步--定义目标函数——利润MaxZ=2x1+3x2系数第2步--定义目标函数对我们有何限制?第3步--表示约束条件x1+2x284x1164x212x1、x20该计划的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x2决策变量（Decisionvariables）目标函数（Ob

5、jectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值线性规划问题的共同特征一组决策变量X表示一个方案,一般X大于等于零。约束条件是线性等式或不等式

6、。目标函数是线性的。求目标函数最大化或最小化例2(书)某厂生产甲乙两种产品，已知制成一吨产品甲需用资源A3吨，资源B4m3；制成一吨产品乙需用资源A2吨，资源B6m3，资源c7个单位。若一吨产品甲和乙的经济价值分别为7万元和5万元，三种资源的限制量分别为90吨、200m3和210个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高?建模步骤：第一步：确定决策变量x1：生产产品甲的数量（吨）x2：生产产品乙的数量（吨）上述变量为由决策者决定的未知量，称为决策变量。第二步：确定目标函数以Z表示生产甲

7、和乙两种产品各为x1和x2（吨）时产生的经济价值，总经济价值最高的目标可表示为：maxz＝7x1十5x2这就是该问题的目标函数。第三步：确定约束条件本例的约束条件为三种资源的限制用量。对各个限制条件逐一加以分析，写出反映其限制关系的表达式（等式或不等式），从而得到约束条件。资源A限制：3x1十2x2≤90资源B限制；4x1十6x2≤200资源C限制：7x2≤210此外，产量x1和x2不能为负，只能取正值非负条件：x1≥0，x2≥0经上述分析，可将该问题表示为：maxz＝7x1十5x23x1十2x2≤904x

8、1十6x2≤2007x2≤210x1≥0，x2≥0这种数学表达方式，称为该问题的一种数学模型。例3：投资问题某单位有一批资金用于四个工程项目的投资，用于各工程项目时所得之净收益（投入资金的百分比）如下表所示：由于某种原因，决定用于项目A的投资不大于其它各项投资之和；而用于项目B和C的投资不小于项目D的投资。试确定使该单位收益最大的投资分配方案。工程项目ABCD收益（％）1510812第一步：确定变量x1、x2、x