《运筹学线性规划》PPT课件

《《运筹学线性规划》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、赵立强管理运筹学教程清华大学出版社第一章线性规划线性规划是运筹学的一个重要分枝。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法——单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更加广泛。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥重要作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛、计算技术比较简

2、单的特点，是现代管理科学的重要基础和手段之一。清华大学出版社第一节线性规划问题及其数学模型一、线性规划问题的数学模型线性规划问题主要解决以下两类问题：1、任务确定后，如何统筹安排，做到应用尽量少的人力和物力资源来完成任务；2、在一定量的人力、物力资源的条件下，如何安排、使用他们，使完成的任务最多。在生产管理和经济活动中，经常会遇到线性规划问题，如何利用线性规划的方法来进行分析，下面举例来加以说明。清华大学出版社例1－1：（计划安排问题）某工厂在计划期内安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所占用的设备A、B的台时、原材料的消耗及两种产品每件可获利润见表所示：III资源总量设备A(h)

3、0315设备B(h)4012原材料(公斤)2214利润(元)23问如何安排计划使该工厂获利最多？清华大学出版社解:假设x1、x2分别表示在计划期内生产产品I、II的件数。该问题可用如下数学模型表示为：目标函数：MaxZ=2x1+3x2约束条件：清华大学出版社例1－2(成本问题)某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A，B两处运回原油提炼，已知两处的原油成分含量见表1－2；又已知从A处采购的原油价格为每吨（包括运费）200元，B处采购的原油价格为每吨（包括运费）290元,问：该炼油厂该如何从A，B两处采购原油，在满足供应合同的条件下，使购买

4、成本最小。表1－2AB汽油15%50%煤油20％30％重油50％15％其它15％5％产品来源成分清华大学出版社分析：很明显，该厂可以有多种不同的方案从A，B两处采购原油，但最优方案应是使购买成本最小的一个，即在满足供应合同单位的前提下，使成本最小的一个采购方案。解：设分别表示从A，B两处采购的原油量（单位：万吨），建立的数学模型为：清华大学出版社以上两个例子，从数学上来讲，我们会发现此数学模型具有如下特点：(1)有一组非负的决策变量(decisionorcontrolvariable)；(2)有一组约束条件：含有决策变量的线性不等式(或等式)组(linearfunctionconstr

5、aints)；(3)有一个含有决策变量的线性目标函数(objectivelinearfunction)，按研究问题的不同，要求目标函数实现最大化或最小化。我们把满足上述三个条件的数学模型称为线性规划的数学模型。其一般形式如下：清华大学出版社在该数学模型中，方程(1.1)称为目标函数；(1.2)称为约束条件；(1.3)称为变量的非负约束条件。清华大学出版社二、线性规划问题的标准型由前面所举的例子可知，线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的；约束条件可以是“”形式、“”形式的不等式，也可以是等式。决策变量有时有非负限制，有时没有。这种多样性给讨论问题带来

6、了不便。为了便于今后讨论，我们规定线性规划问题的标准型为：清华大学出版社标准型具有如下特点：（1）目标函数求最大值；（2）所求的变量都要求是非负的；（3）所有的约束条件都是等式；（4）常数项非负。综合以上的讨论可以说明任何形式的线性规划问题都可以通过上述手段把非标准型的线性规划问题化成标准型。现举例如下：清华大学出版社例1－4试将如下线性规划问题化成标准型解：令x3=x4-x5,x4,x50,(1)式左端加上非负松弛变量x6；(2)式左端减去非负剩余变量x7,则可将上述线性规划问题化成如下的标准型：清华大学出版社第二节线性规划问题的图解法及几何意义一、线性规划问题的解的概念在讨论线性

7、规划问题的求解之前，先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为(1.6)、(1.7)、(1.8)式所示：清华大学出版社1.可行解:满足约束条件(1.7)，(1.8)的解X=(x1,x2,···,xn)称为线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。2.最优解:满足约束条件及目标函数(1.6)的可行解称为线性规划问题的最优解。3.基:假设A是约束方程组的系数矩阵，其秩数为m，B是矩阵A中由m列构成的非奇异