理论教育 线性规划问题的标准形式优化措施

线性规划问题的标准形式优化措施

时间:2023-07-06 理论教育 版权反馈
【摘要】:我们知道,线性规划问题的目标函数可能是最大化或最小化的,约束条件可能是等式或不等式,变量可能是非负的或者无限制的,这使得线性规划问题呈现出多种形式,不利于讨论其一般解法。在单纯形法中,通常称具备以下条件的线性规划问题为线性规划问题的标准形式:目标函数为最大化;约束条件均为等式,且右端项非负;所有变量非负。

线性规划问题的标准形式优化措施

我们知道,线性规划问题的目标函数可能是最大化或最小化的,约束条件可能是等式或不等式,变量可能是非负的或者无限制的,这使得线性规划问题呈现出多种形式,不利于讨论其一般解法。因此,为了研究线性规划问题的一般解法,首先需要明确线性规划问题的一个标准形式。在单纯形法中,通常称具备以下条件的线性规划问题为线性规划问题的标准形式:

(1)目标函数为最大化;(2)约束条件均为等式,且右端项非负;(3)所有变量非负。

即线性规划模型的标准形式可表示为

也可将其写成

则可将线性规划模型的标准形式写成线性规划模型的矩阵形式:

其中x为决策变量向量,c为价值系统向量,A为系数矩阵,b为资源向量。(www.daowen.com)

线性规划问题的标准形式为讨论其一般解法提供了便利,但自然产生的一个问题是:是不是所有的线性规划问题都可以转化为上述的标准形式呢?事实上这是线性规划模型的标准化问题,根据如下转化规则可将所有不同类型的线性规划问题转化为标准形式:

(1)若某一线性规划问题的目标函数为min z=cx,则令z=-z,即将其目标函数变为max z=-cx,这就与标准形式的要求一致了。

(2)当约束条件为不等式时,若约束条件为≤型,则可在其左边加上一个非负松弛变量,将其转化为等式;若约束条件为≥型,则可在其左边减去一个非负剩余变量,将其转化为等式。

例2.3(线性规划问题的标准化)将下述线性规划问题化为标准形:

解根据前述转化规则,令x1=-x1,x3=x4-x5,在第一个约束条件左边加入松弛变量x6,在第二个约束条件左边减去剩余变量x7,令z=-z,将目标函数由最小化变为最大化,得到

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈