第2章 线性规划（第1节） 运筹学课件.pptVIP

2．非标准形式线性规划问题的标准化 对于非标准形式线性规划模型，我们可通过适当的数学转换，将其化成标准形式，下面分别不同的情况讨论如下： (1)求目标函数最小值 如果原模型是求目标函数最小值，记为 由于 令 就可将原目标函数化为求最大值 (2)约束条件是“ ” 如果原模型的约束条件中，有若干方程为 “ ”，则可对每一个这样的约束方程分别引入一个非负的变量，称为松弛变量，将其化为等式。 (3)约束条件是“ ”型。 如果原模型的约束条件中，有若干方程为 “ ”型，则可对每一个这样的约束方程分别引入一个非负的松弛变量，此时其系数应为负的，将其化为等式。 4)约束条件右边为负。 这种情况只需在约束条件两边同乘 “-1”，即可把约束条件右边化为正的。 (5)决策变量无符号限制。 如果有的决策变量可以取正值，也可取负值或零，也就是没有符号限制，那么可以用两个非负变量的差来代替。 例1.3 已知线性规划问题 约束条件： 试将此问题化为标准形式。 第二章 线性规划 线性规划(Linear Programming)是运筹学中研究得比较早,理论成熟，方法有效，应用广泛的一个重要分支。在运筹学中占有重要的位置。 早在20世纪30年代末，前苏联数学家康托洛维奇发表的小册子《生产组织与计划中的数学方法》，首先提出了线性规划模型，这是有关线性规划的最早文献； 其后，美国也开始研究这个问题，最有影响的是希契科克研究的运输问题及其解。 后来由于第二次世界大战的需要，军事中有关规划、侦察、后勤、生产等各方面的问题被陆续提出，人们对线性规划问题的求解与应用展开了系统的研究，并于1947年由美国人旦茨格等提出了线性规划的单纯形算法，较好地解决了线性规划的求解问题，从而奠定了线性规划作为一门学科的基石。 随着电子计算机技术的不断发展，使线性规划的求解能力大大提高，更为线性规划在经济等各领域的广泛应用提供了极为有利的条件。线性规划已成为现代化管理的一种重要的手段。 线性规划研究的对象大体可分为两大类， 一类是在现有的人、财、物等资源的条件下，研究如何合理地计划、安排，可使得某一目标达到最大，如产量、利润目标等。 另一类是在任务确定后，如何计划、安排，使用最少的人、财、物等资源，去实现该任务，如使生产成本、费用最少等。这两类问题从本质上说是相同的，它们都是在一组约束条件下，去实现某一个目标的最优(最大或最小)。 线性规划中研究的问题要求目标与约束条件均是线性的，而目标函数只能是一个。 对于目标与约束条件非线性的情况，由“非线性规划”问题专门讨论，对于多于一个决策目标的问题将在“目标规划”中讨论。好在经济管理问题中，大量的问题是线性的，从而使线性规划有着极大的应用价值。 节1.1 线性规划的数学模型及其标准形式 在本节中我们先讨论建立决策问题中的数学模型的一般方法，再给出几个线性规划问题的实例，建立它们的数学模型，最后再给出线性规划数学模型的标准形式。 一、建立决策问题数学模型的一般方法 建立决策问题数学模型一般可从以下三方面进行考虑。 1．确定决策变量 1．确定决策变量 对于一个决策问题，首先要明确的是：要我们决策什么?也就是说，有哪些可供选择的方案。 2．建立目标函数 作为一个决策问题，在决策者的心目中，必然会有各种决策的目标，如希望产品产量最大，利润最大，成本最低等。而这些目标实现得好坏，取决于采用的决策方案，因此，我们说，决策目标是决策方案的函数，也就是决策变量的函数，称为目标函数。 作为建立数学模型的第二步，即要对每个决策目标，建立目标函数，找到目标值与决策变量的数量关系。 在本章线性规划中，讨论的数学模型只含一目标函数。且这函数关系是线性的，至于多个决策目标的数学模型，属于目标规划讨论的问题。 3．确定约束条件 一个决策问题的决策目标一般不可能无限制地被优化。 在其实现优化的过程中，必然会受到有关外界条件的制约。 一个成本最小化的决策目标，就可能受制于一定的产量要求等等。这些限制往往是决策方案(即决策变量)的等式或不等式，称为约束条件。 在本章线性规划模型中，我们要求模型的所有约束条件也必须是线性的。 二、线性规划问题举例 例1.1 (生产安排问题)。假定某工厂生产甲、乙、丙三种产品，都要经过三种不同的工序加工。每一件产品所需要的加工时间(分钟)和每天对各道工序的加工能力(每天多少分钟)以及销售各种产品的单位利润如表1.1所示。 表1.1 工序 每件产品加工时间（分钟） 每天加工能力（分钟） 甲产品 乙产品 丙产品 一 1 2 1 430 二 3 0 2 460 三 1 4 0 420