《线性规划问题及数其学模型文档资料》由会员分享，可在线阅读，更多相关《线性规划问题及数其学模型文档资料（42页珍藏版）》请在金锄头文库上搜索。
1、上页上页上页上页下页下页下页下页返回返回返回返回第第 一一 章章 线线 形形 规规 划划 本章学习重点本章学习重点 线性规划是运筹学中比较成熟的一个分支，线性规划是运筹学中比较成熟的一个分支，线性规划是运筹学中比较成熟的一个分支，线性规划是运筹学中比较成熟的一个分支，它具有成熟而有效的求解方法，可以借助于计它具有成熟而有效的求解方法，可以借助于计它具有成熟而有效的求解方法，可以借助于计它具有成熟而有效的求解方法，可以借助于计算机进行求解，在军事、经济等领域中具有广算机进行求解，在军事、经济等领域中具有广算机进行求解，在军事、经济等领域中具有广算机进行求解，在军事、经济等领域中具有广泛的应用。学
2、习本章，要掌握线性规划的泛的应用。学习本章，要掌握线性规划的泛的应用。学习本章，要掌握线性规划的泛的应用。学习本章，要掌握线性规划的数学数学数学数学模型模型模型模型（建模以及把不同形式的线性规划问题化（建模以及把不同形式的线性规划问题化（建模以及把不同形式的线性规划问题化（建模以及把不同形式的线性规划问题化为标准形式的方法）、为标准形式的方法）、为标准形式的方法）、为标准形式的方法）、求解方法求解方法求解方法求解方法。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright
3、2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回线性规划的地位与研究进程线性规划的地位与研究进程 作作作作为为为为一一一一门门门门科科科科学学学学的的的的线线线线性性性性规规规规划划划划，最最最最早早早早可可可可以以以以追追追追溯溯溯溯到到到到20202020世世世世纪纪纪纪30303030年年年年代代代代末末末末，前前前前苏苏苏苏联联联联数数数数学学学学家家家家康康康康德德德德洛洛洛洛维维维维奇奇奇奇等等等等人人人人关关关关于于于于生生生生产产产产组组组组织织织织和和和和运运运运输输输输问问问问题题题题研研研研究究究究所所所所作作作作的的的的
4、开开开开拓拓拓拓性性性性工工工工作作作作。1947194719471947年年年年，美美美美国国国国数数数数学学学学家家家家G.B.DantzigG.B.DantzigG.B.DantzigG.B.Dantzig以以以以及及及及美美美美国国国国空空空空军军军军的的的的SCOOPSCOOPSCOOPSCOOP研研研研究究究究小小小小组组组组提提提提出出出出了了了了线线线线性性性性规规规规划划划划问问问问题题题题的的的的一一一一般般般般性性性性解解解解法法法法即即即即单单单单纯纯纯纯形形形形法法法法, , , ,奠奠奠奠定定定定了了了了线线线线性性性性规规规规划划划划的的的的理理理理论论论论基基基
5、基础础础础。50505050年年年年代代代代后后后后，随随随随着着着着电电电电子子子子计计计计算算算算机机机机的的的的介介介介入入入入，线线线线性性性性规规规规划划划划的的的的应应应应用用用用越越越越来来来来越越越越普普普普遍遍遍遍，在在在在生生生生产产产产、管管管管理理理理、军军军军事事事事等等等等方方方方面面面面发发发发挥挥挥挥着着着着重重重重要的作用。要的作用。要的作用。要的作用。 线线线线性性性性规规规规划划划划目目目目前前前前仍仍仍仍然然然然还还还还在在在在发发发发展展展展，主主主主要要要要是是是是：大大大大型型型型线线线线性性性性规划问题，线性规划解法研究等。规划问题，线性规划解法
6、研究等。规划问题，线性规划解法研究等。规划问题，线性规划解法研究等。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.v 线性规划问题的提出线性规划问题的提出v 线性规划的基本概念线性规划的基本概念v 线性规划的数学模型线性规划的数学模型v 线性规划问题的标准形式线性规划问题的标准形式继续继续继续继续返回返回返回返回第一节第一节 线性规划问题线性规划问题 及其数学模型及其数学模型Evaluation only.Crea
7、ted with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回问题的提出问题的提出引例引例: : 生产计划问题生产计划问题Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回产品产品甲甲产品产品乙乙如何
8、安排生产如何安排生产使利润最大使利润最大？Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回什么是线性规划？什么是线性规划？什么是线性规划？什么是线性规划？ 在工业、农业、国防、建筑、交通运输、科研、商业在工业、农业、国防、建筑、交通运输、科研、商业在工业、农业、国防、建筑、交通运输、科研、商业在工业、农业、国防、建筑、交通运输、科研、商业等各种活动中，常常要求对资源进行
9、统一分配、全面规划等各种活动中，常常要求对资源进行统一分配、全面规划等各种活动中，常常要求对资源进行统一分配、全面规划等各种活动中，常常要求对资源进行统一分配、全面规划和合理调度，以便从各种可能安排方案中找出最优的计划和合理调度，以便从各种可能安排方案中找出最优的计划和合理调度，以便从各种可能安排方案中找出最优的计划和合理调度，以便从各种可能安排方案中找出最优的计划或设计，用以指导生产。在这类问题中，一方面有期望达或设计，用以指导生产。在这类问题中，一方面有期望达或设计，用以指导生产。在这类问题中，一方面有期望达或设计，用以指导生产。在这类问题中，一方面有期望达到最优要求的目标（例如希望产值最
10、高或消耗最少），另到最优要求的目标（例如希望产值最高或消耗最少），另到最优要求的目标（例如希望产值最高或消耗最少），另到最优要求的目标（例如希望产值最高或消耗最少），另一方面又要受到一定条件的限制（例如人力、物力、财力一方面又要受到一定条件的限制（例如人力、物力、财力一方面又要受到一定条件的限制（例如人力、物力、财力一方面又要受到一定条件的限制（例如人力、物力、财力的限制），如何安排才能使成效最高，消耗既定资源取得的限制），如何安排才能使成效最高，消耗既定资源取得的限制），如何安排才能使成效最高，消耗既定资源取得的限制），如何安排才能使成效最高，消耗既定资源取得的收益最大，或达到既定收益所消耗
11、的资源最少。这可以的收益最大，或达到既定收益所消耗的资源最少。这可以的收益最大，或达到既定收益所消耗的资源最少。这可以的收益最大，或达到既定收益所消耗的资源最少。这可以借助借助借助借助线性规划（线性规划（线性规划（线性规划（Linear ProgrammingLinear ProgrammingLinear ProgrammingLinear Programming，LPLPLPLP）来解决。来解决。来解决。来解决。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2
12、004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回线性规划研究的内容线性规划研究的内容在在现现有有的的资资源源条条件件下下，如如何何充充分分利利用用资资源源，使使任任务务或或目目标标完完成成得得最最好好（求求极极大大化问题）。化问题）。在在给给定定目目标标下下，如如何何以以最最少少的的资资源源消消耗耗，实现这个目标（求极小化问题）。实现这个目标（求极小化问题）。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2
13、011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回是问题中要确定的未知量，是问题中要确定的未知量，是问题中要确定的未知量，是问题中要确定的未知量，表明规划中的用数量表示的表明规划中的用数量表示的表明规划中的用数量表示的表明规划中的用数量表示的方案、措施，可由决策者决方案、措施，可由决策者决方案、措施，可由决策者决方案、措施，可由决策者决定和控制。定和控制。定和控制。定和控制。第第1步步 -确定决策变量确定决策变量设设 甲的产量甲的产量 乙的产量乙的产量 Evaluation only.Created with Aspose.Slides for .NET 3
14、.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回Max Z = x1 + x2决策变量决策变量第第2步步 -定义目标函数定义目标函数 利润利润利润利润Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 Max Z = 2 x1 + 3 x2系数系数第第
15、2步步 -定义目标函数定义目标函数Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回对我们有对我们有何限制何限制?Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页
16、返回返回返回返回第第3步步 -表示约束条件表示约束条件 x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0 0Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回该计划的数学模型该计划的数学模型 目标函数目标函数 Max Z = 2x1 + 3x2 约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 0x1 x2Eva
17、luation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回决策变量（决策变量（决策变量（决策变量（Decision variablesDecision variables）目标函数（目标函数（目标函数（目标函数（Objective functionObjective function）约束条件（约束条件（约束条件（约束条件（Constraint conditionsConstraint
18、 conditions）可行域（可行域（可行域（可行域（Feasible region)Feasible region)最优解（最优解（最优解（最优解（Optimal solution)Optimal solution)基本概念基本概念问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方明规划中的用数量表示的方案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定和控制。和控制。和控制。和控制。它是决策变量的函数它是决策变量的函数它是决策
19、变量的函数它是决策变量的函数指决策变量取值时受到的指决策变量取值时受到的指决策变量取值时受到的指决策变量取值时受到的各种资源条件的限制，通各种资源条件的限制，通各种资源条件的限制，通各种资源条件的限制，通常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等式或不等式。式或不等式。式或不等式。式或不等式。满足约束条件的决满足约束条件的决满足约束条件的决满足约束条件的决策变量的取值范围策变量的取值范围策变量的取值范围策变量的取值范围可行域中使目标可行域中使目标可行域中使目标可行域中使目标函数达到最优的函数达到最优的函数达到最优的函数达到最优的决策变量的值决策变量
20、的值决策变量的值决策变量的值Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题的共同特征线性规划问题的共同特征一组决策变量一组决策变量X X表示一个方案表示一个方案, ,一般一般X X大大于等于零。于等于零。约束条件是线性等式或不等式。约束条件是线性等式或不等式。目标函数是线性的。目标函数是线性的。 求目标函数最大求目标函数最大化或最小化化或最小化Evalua
21、tion only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 例例2(2(书书) ) 某厂生产甲乙两种产品，已知制成一吨产品某厂生产甲乙两种产品，已知制成一吨产品某厂生产甲乙两种产品，已知制成一吨产品某厂生产甲乙两种产品，已知制成一吨产品甲需用资源甲需用资源甲需用资源甲需用资源A 3A 3A 3A 3吨，资源吨，资源吨，资源吨，资源B 4mB 4mB 4mB 4m3 3 3 3；制成一吨产品乙
22、；制成一吨产品乙；制成一吨产品乙；制成一吨产品乙需用资源需用资源需用资源需用资源A 2A 2A 2A 2吨，资源吨，资源吨，资源吨，资源B 6mB 6mB 6mB 6m3 3 3 3，资源，资源，资源，资源c 7c 7c 7c 7个单位。若个单位。若个单位。若个单位。若一吨产品甲和乙的经济价值分别为一吨产品甲和乙的经济价值分别为一吨产品甲和乙的经济价值分别为一吨产品甲和乙的经济价值分别为7 7 7 7万元和万元和万元和万元和5 5 5 5万元，万元，万元，万元，三种资源的限制量分别为三种资源的限制量分别为三种资源的限制量分别为三种资源的限制量分别为90909090吨、吨、吨、吨、200m200
23、m200m200m3 3 3 3和和和和210210210210个单个单个单个单位，试决定应生产这两种产品各多少吨才能使创位，试决定应生产这两种产品各多少吨才能使创位，试决定应生产这两种产品各多少吨才能使创位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高造的总经济价值最高造的总经济价值最高造的总经济价值最高? ? ? ?Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返
24、回返回返回建模步骤：建模步骤：第一步：确定决策变量第一步：确定决策变量 x x1 1：生产产品甲的数量（吨）：生产产品甲的数量（吨） x x2 2：生产产品乙的数量（吨）：生产产品乙的数量（吨） 上述变量为由决策者决定的未知量，称上述变量为由决策者决定的未知量，称为为决策变量决策变量。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回第二步：确定目标函数第二步：确定目标函
25、数 以以 Z Z 表示生产甲和乙两种产品各为表示生产甲和乙两种产品各为x x1 1和和x x2 2（吨）时产生的经济价值，总经济价值（吨）时产生的经济价值，总经济价值最高的目标可表示为：最高的目标可表示为： max zmax z7 x7 x1 1十十5 x5 x2 2 这就是该问题的这就是该问题的目标函数目标函数。 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回第三步
26、：确定约束条件第三步：确定约束条件 本例的约束条件为三种资源的限制用量。对各本例的约束条件为三种资源的限制用量。对各本例的约束条件为三种资源的限制用量。对各本例的约束条件为三种资源的限制用量。对各个限制条件逐一加以分析，写出反映其限制关个限制条件逐一加以分析，写出反映其限制关个限制条件逐一加以分析，写出反映其限制关个限制条件逐一加以分析，写出反映其限制关系的表达式（等式或不等式），从而得到系的表达式（等式或不等式），从而得到系的表达式（等式或不等式），从而得到系的表达式（等式或不等式），从而得到约束约束约束约束条件条件条件条件。 资源资源资源资源A A A A限制：限制：限制：限制：3 x3
27、x3 x3 x1 1 1 1十十十十2 x2 x2 x2 x2 2 2 2 90 90 90 90 资源资源资源资源B B B B限制；限制；限制；限制；4 x4 x4 x4 x1 1 1 1十十十十6 x6 x6 x6 x2 2 2 2 200 200 200 200 资源资源资源资源C C C C限制：限制：限制：限制： 7 x 7 x 7 x 7 x2 2 2 2 210210210210 此外，产量此外，产量此外，产量此外，产量x x x x1 1 1 1和和和和x x x x2 2 2 2不能为负，只能取正值不能为负，只能取正值不能为负，只能取正值不能为负，只能取正值 非负条件：非负
28、条件：非负条件：非负条件： x x x x1 1 1 1 0 0 0 0， x x x x2 2 2 2 0 0 0 0 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回经上述分析，可将该问题表示为：经上述分析，可将该问题表示为： max zmax z7 x7 x1 1十十5 x5 x2 2 3 x 3 x1 1十十2 x2 x2 2 90 90 4 x 4 x1 1十
29、十6 x6 x2 2 200 200 7 x 7 x2 2 210210 x x1 1 0 0，x x2 2 0 0这种数学表达方式，称为该问题的一种数学模型。这种数学表达方式，称为该问题的一种数学模型。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回例例3 3：投资问题：投资问题 某单位有一批资金用于四个工程项目的投资，某单位有一批资金用于四个工程项目的投资，某单位有
30、一批资金用于四个工程项目的投资，某单位有一批资金用于四个工程项目的投资，用于各工程项目时所得之净收益（投入资金的百用于各工程项目时所得之净收益（投入资金的百用于各工程项目时所得之净收益（投入资金的百用于各工程项目时所得之净收益（投入资金的百分比）如下表所示：分比）如下表所示：分比）如下表所示：分比）如下表所示： 由于某种原因，由于某种原因，由于某种原因，由于某种原因，决定用于项目决定用于项目决定用于项目决定用于项目A A A A的投资不大于的投资不大于的投资不大于的投资不大于其它各项投资之和；而用于项目其它各项投资之和；而用于项目其它各项投资之和；而用于项目其它各项投资之和；而用于项目B B
31、B B和和和和C C C C的投资不小的投资不小的投资不小的投资不小于项目于项目于项目于项目D D D D的投资。的投资。的投资。的投资。试确定使该单位收益最大的投资试确定使该单位收益最大的投资试确定使该单位收益最大的投资试确定使该单位收益最大的投资分配方案。分配方案。分配方案。分配方案。工程项目工程项目工程项目工程项目A A A AB B B BC C C CD D D D收益（）收益（）收益（）收益（）15151515101010108 8 8 812121212Evaluation only.Created with Aspose.Slides for .NET 3.5 Client P
32、rofile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回第一步：确定变量第一步：确定变量 x x1 1、 x x2 2 、 x x3 3 、 x x4 4 分别表示用于项目分别表示用于项目A A、B B、C C、D D的投资百分数。的投资百分数。第二步：确定约束条件第二步：确定约束条件 x x1 1 x x2 2 x x3 3 x x4 400 x x2 2 x x3 3 x x4 400 x x1 1 x x2 2 x x3 3 x x4 41 1 x xj j 0 0，j j1 1，2,2,4,4E
33、valuation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回第三步：确定目标函数第三步：确定目标函数 max z=0.15xmax z=0.15x1 1+0.1x+0.1x2 2+0.08x+0.08x3 3+0.12x+0.12x4 4数学模型数学模型 max z = 0.15x max z = 0.15x1 1 + 0.1x+ 0.1x2 2 + 0.08x+ 0.08x3 3
34、+ 0.12x+ 0.12x4 4 x x1 1 x x2 2 x x3 3 x x4 4 0 0 x x2 2 x x3 3 x x4 4 0 0 x x1 1 x x2 2 x x3 3 x x4 4 1 1 x xj j 0 0，j j1 1，2,2,4,4Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回例例4 4：营养问题：营养问题 某动物饲养场利用某动物饲养场
35、利用n n种天然饲料来配制混种天然饲料来配制混合饲料使用，已知单位第合饲料使用，已知单位第j j种天然饲料的价格种天然饲料的价格为为c cj j，它含有第，它含有第i i种营养成份的量为种营养成份的量为a aijij；根据；根据动物生长的需要，要求具有动物生长的需要，要求具有m m种营养成份，且种营养成份，且第第i i种营养成份的含量不得低于种营养成份的含量不得低于b bi i。试确定在。试确定在保证动物营养需要的条件下用最低的饲料配保证动物营养需要的条件下用最低的饲料配合法。合法。Evaluation only.Created with Aspose.Slides for .NET 3.5
36、Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回设设x xj j为第为第j j种天然饲料的使用量，则种天然饲料的使用量，则a aij ij x xj j为第为第j j种天然饲料含有第种天然饲料含有第i i种营养成分的数量。则：种营养成分的数量。则：考虑到非负约束和目标要求，其数学模型为：考虑到非负约束和目标要求，其数学模型为：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0
37、.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回线性规划三要素线性规划三要素 线性规划线性规划线性规划线性规划(Linear Programming(Linear Programming，LP)LP)有：有：有：有：一组有待一组有待一组有待一组有待决策的变量决策的变量决策的变量决策的变量 （指模型中要求解的未知量指模型中要求解的未知量指模型中要求解的未知量指模型中要求解的未知量）一个线性的一个线性的一个线性的一个线性的目标函数目标函数目标函数目标函数 （指模型中要达到的目标的数学表达式）（指模型中要达到的目标的数学表达式）
38、（指模型中要达到的目标的数学表达式）（指模型中要达到的目标的数学表达式）一组线性的一组线性的一组线性的一组线性的约束条件约束条件约束条件约束条件 （指模型中的变量取值所需要满足的一切限制（指模型中的变量取值所需要满足的一切限制（指模型中的变量取值所需要满足的一切限制（指模型中的变量取值所需要满足的一切限制条件）条件）条件）条件） Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回
39、返回返回 线性规划模型的一般形式线性规划模型的一般形式 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回线性规划问题的标准形式线性规划问题的标准形式标准形式为标准形式为:目标函数最大目标函数最大约束条件等式约束条件等式决策变量非负决策变量非负Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pr
40、ofile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 简写为简写为其中：其中：其中：其中：c c c cj j j j -表示目标函数系数表示目标函数系数表示目标函数系数表示目标函数系数 a a a aijijijij-表示约束条件系数表示约束条件系数表示约束条件系数表示约束条件系数 b b b bi i i i -表示约束右端项表示约束右端项表示约束右端项表示约束右端项Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Pro
41、file 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 用向量表示用向量表示用向量表示用向量表示未知数未知数向量向量Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 用矩阵表示用矩阵表示用矩阵表示用矩阵表示A A系数矩阵系数矩阵C C价值向量价值向量b b资源向量资源向量X X决策
42、变量向量决策变量向量Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回一般线性规划问题的标准形化一般线性规划问题的标准形化线型规划问题的数学模型有各种不同的形式，为线型规划问题的数学模型有各种不同的形式，为了便于讨论和求解，需要将线型规划问题的数学了便于讨论和求解，需要将线型规划问题的数学模型写成一个统一的格式，称为线型规划问题的模型写成一个统一的格式，称为线型规划问题的
43、标准型。标准型。统一格式规定如下统一格式规定如下 ： 1、目标函数取最大化、目标函数取最大化 2、所用约束条件用等式来表示、所用约束条件用等式来表示 3、所有决策变量取非负值、所有决策变量取非负值 4、每一约束条件的右端常数（资源限量）为非负值、每一约束条件的右端常数（资源限量）为非负值Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 min Z=CX min Z=CX
44、 等价于等价于 max Z max Z = -CX = -CX“ ” 约束：加入非负松驰变量约束：加入非负松驰变量一般线性规划问题的标准形化一般线性规划问题的标准形化例：例： 目标函数目标函数目标函数目标函数 Max Max Z Z = 2 = 2x x1 1 + 3 + 3x x2 2 约束条件约束条件约束条件约束条件 x x1 1 + 2 + 2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、 x x2 2 0 0 0 0Evaluation only.Created with Aspose.Slides for .NET 3.5 Cli
45、ent Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 min Z=CX min Z=CX 等价于等价于 max Z max Z = -CX = -CX“ ” 约束：加入非负松驰变量约束：加入非负松驰变量一般线性规划问题的标准形化一般线性规划问题的标准形化例：例：Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页
46、上页上页上页下页下页下页下页返回返回返回返回 “ ” 约束：约束： 减去非负剩余变量；减去非负剩余变量； Max 例例例例 ： 可正可负（即无约束）；可正可负（即无约束）；Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回 解解 ：标准形为Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Prof
47、ile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回非标准型转化举例非标准型转化举例Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回复习思考题复习思考题1 1. .什么是模型结构的三要素？什么是模型结构的三要素？2.2.什么是线性规划模型？什么是线性规划模型？3.LP3.LP模型中
48、目标函数系数、约束条件系数、模型中目标函数系数、约束条件系数、约束右端项的含义指的是什么？通常以什么约束右端项的含义指的是什么？通常以什么符号表示？符号表示？4.LP4.LP模型的一般表示方法有几种形式？能否模型的一般表示方法有几种形式？能否写出这些形式？写出这些形式？Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回将数学模型转化为标准形将数学模型转化为标准形Evalu
49、ation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回某某某某企企企企业业业业生生生生产产产产两两两两种种种种产产产产品品品品，分分分分别别别别使使使使用用用用4 4 4 4种种种种原原原原料料料料制制制制成成成成，4 4 4 4种种种种原原原原材材材材料料料料目目目目前前前前库库库库存存存存量量量量分分分分别别别别为为为为300300300300，400400400400，50050
50、0500500和和和和500500500500吨吨吨吨，两两两两种种种种产产产产品品品品所所所所需需需需各各各各种种种种原原原原材材材材料料料料数数数数量量量量见见见见表表表表。又又又又知知知知两两两两种种种种产产产产品品品品的的的的单单单单位位位位利利利利润润润润分分分分别别别别为为为为2800280028002800和和和和3200320032003200元元元元/ / / /吨吨吨吨，如如如如何何何何计计计计划划划划两两两两种种种种产产产产品品品品的的的的产产产产量量量量，使使使使利利利利润达到最大。并将数学模型转化为标准形。润达到最大。并将数学模型转化为标准形。润达到最大。并将数学模型
51、转化为标准形。润达到最大。并将数学模型转化为标准形。 两种产品所需的原材料数量两种产品所需的原材料数量两种产品所需的原材料数量两种产品所需的原材料数量 原材料原材料原材料原材料产品产品产品产品 1 1 2 2 3 3 4 4 1 11.41.41.31.31.41.41.41.4 2 21.61.61.71.71.51.51.71.7 库存量库存量库存量库存量300300400400500500500500课堂作业：产品计划问题课堂作业：产品计划问题Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.
52、2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.上页上页上页上页下页下页下页下页返回返回返回返回线性规划模型Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.
