第一章线性规划的数学模型与纯形法
线性规划是运筹学的一个重要分枝,研究在给定的约束条件下,所考察的目标函数在某种意义下的极值问题。自1947年美国数学家丹捷格(G.B.Dantzig)提出了求解线性规划问题的方法——单纯形法之后,线性规划在理论上趋于成熟,在实际中的应用日益广泛与深入,特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后,它的适用领域更加广泛。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥重要作用;从应用范围来看,小到一个小组的日常工作和计划安排,大至整个部门甚至同民经济计划的最优方案的提出,都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点,是现代管理科学的重要基础和手段之一。
l.1线性规划问题及其数学模型
1.1.1线性规划问题的数学模型
在生产管理和经济活动中,人们经常会遇到线性规划问题。如何利川线性规划的方法来进行分析?下面举例来加以说明。
例1.1计划安排问题
某工厂在计划期内安排生产I、Ⅱ两种产品,已知生产单位产品需要消耗原材料A、B、C,具体数据见表l.1。
工厂每生产一卑位产品I可获利润2万元,每生产一单位产品Ⅱ可获利润3万元,问工厂应如何合理安排这两种产品的产量,使得在资源有限的条件下工厂获得利润最大?
解:工厂目前要决策的问题是生产多少单位产品I和生产多少单位产品Ⅱ才能获利最大,我们把在计划期内生产译位产品T和生产译位产品Ⅱ的单位数用变量。来表示,则称。为决策变量。因为在计划期内原材料A的可利用数量是15,所以在确定单位产品的产量时,有不等式:
同理,因在计划期内原材料B的限制,有不等式:
原材料C的限制,有不等式:
若用Z表示该工厂的利润,则该工厂的利润值:
综上所述,该工厂的计划安排问题可用如下数学模型表示为
目标函数
约束条件
例1.2成本问题
某炼油厂每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A、B两处运回原油提炼,已知两处的原油成分含量见表1.2;又已知从A处采购的原油价格为每吨(包括运费)200元,B处采购的原油价格为每吨(包括运费)290元,问:该炼油厂该如何从A、B两处采购原油,在满足供应合同的条件下,使购买成本最小。
分析:很明显,该厂可以有多种不同的方案从A、B两处采购原油,但最优方案应是使购买成本最小,即在满足供应合同单位的前提下,使成本最小的一个采购方案。
解:设分别表示从A、B两处采购的原油量(单位:万吨),则所有的采购方案均应同时满足:
采购成本(单位:万元)为的函数,即
.
而最终目标是求满足约束条件和使采购成本最小时的解。由此,建立的数学模型为从以上两个例子的数学模型可以看出,目标函数为决策变量的线性函数,约束条件也为决策变量的线性不等式(或等式),该类数学模型具有如下特点。
(l)有一组非负的决策变量(decisionorcontrolvariable),这组决策变量的值都代表一个具体方案。
(2)有一组约束条件,含有决策变量的线性不等式(或等式)组(linearfunctionconstraints),
(3)有一个含有决策变量的线性目标函数(objectivelinearfunction),按研究问题的不同,要求目标函数实现最大化或最小化。
我们把满足上述三个条件的数学模型称为线性规划数学模型。如果目标函数是决策变量的非线性函数或约束条件含有决策变量的非线性不等式(或等式),我们就称这类数学模型为非线性规划数学模型。
线性规划数学模型的一般形式如下:
在该数学模型中,式(1.1)称为日标函数;式(1.2)称为约束条件;式(1.3)称为变量的非负约束条件。
1.1.2线性规划问题的标准型
由前面所举的例子可知,线性规划问题可能有各种不同的形式。根据实际问题的要求,目标函数可能是求最大化,也可能是求最小化;约束条件可以是“≤”形式、“≥”形式的不等式,也可以是等式。决策变量有时有非负限制,有时没有非负限制。这种多样性给讨论问题带来了不便。为了便于讨论,我们规定线性规划问题描述为如下的标准形式:
这里我们假设
以上模型的简写形式为
用向量形式表达时,上述模型可以写为
用矩阵形式表达时,上述模型可以写为
我们称A为约束方程组的系数矩阵(m×n阶),一般情况下为正整数,分别表示约束条件的个数和决策变量的个数,C为价值向量,X为决策向量,通常为已知常数。
实际上,具体问题的线性规划数学模型是各式各样的,需要把它们化成标准型,并借助于标准型的求解方法进行求解。
以下就具体讨论如何把一般的线性规划模型化成标准型。
(1)目标函数的转化。若原问题的目标函数是求最小化,即,这时只需要将目标函数的最小值变换为求目标函数的最大值,即。令就是将目标函数乘以后转化为如下最大化问题:
(2)不等式约束转化为等式约束。不等式约束有两种情况:一是约束条件为“≤”形式的不等式,则在“≤”号的左边加入非负的松弛变量,把原“≤”形式的不等式转化为等式;另一种是约束条件为“≥”形式的不等式,则可在“≥”号的左边减去一个非负的剩余变量,把原“≥”形式的不等式转化为等式。同时相应的松弛变量或剩余变量在目标函数中的价值系数取值为O。
(3)变量约束的转换。若原线性规划问题巾某个变量为无非负要求的变量,即有某一个变量z,取正值或负值都口以。这时为了满足标准型对变量的非负要求,可令,其中,将其代入原问题,即在原问题中将z,用两个非负变量之差代替。
上述的标准型具有如下特点。
(l)日标函数求最大值。
(2)所求的决策变量都要求是非负的。
(3)所有的约束条仵都是等式。
(4)常数项为非负。
综合以上的讨论,我们可以把任意形式的线性规划问题通过上述手段化成标准型的线性规划问题。
例1.3将例1.1的线性规划数学模型化为标准型
解:引进3个新的非负变量使不等式变为等式,标准型为
例1.4试将如下线性规划问题化成标准型
解:由于无限制,所以令,第一个约束不等式左端加上非负松弛变量。第二个约束小等式左端减去非负剩余变量,目标函数由于求最小化,所以令,同时将目标函数及约束条件巾的。换为,则可将上述线性规划问题化成如下的标准型:
1.2线性规划问题的图解法及几何意义
1.2.1线性规划问题解的概念
在讨论线性规划问题的求解之前,要先了解线性规划问题解的概念。由前面讨论可知,线性规划问题的标准型如式(1.8)、式(1.9)、式(1.10)所示:
1.可行解
满足约束条件式(1.9)和式(1.10)的解称为线性规划问题的可行解;所有可行解的集合称为可行解集或可行域。
2.最优解
满足约束条件及目标函数(1.8)的可行解称为线性规划问题的最优解。
3.基
假设A是约束方程组的系教矩阵,其秩数为m,B是矩阵A中F列构成的非奇异子矩阵(B的行列式值不为0),则称B是线性规划问题的一个基。这就是说,矩阵B由m个线性无关的列向量组成。不失一般性,可假设:为线性规划问题的一个基。