理论教育 标准型线性规划的定义及应用

标准型线性规划的定义及应用

时间:2023-11-18 理论教育 版权反馈
【摘要】:由于求解数学模型的算法都是为标准化的模型设计的,所以,为了便于对求解线性规划模型建立一个有效的算法,我们有必要对线性规划模型规定它的标准形式.今后,我们谈到的线性规划模型的标准型,都是指下列形式:也就是说,线性规划的标准型,是指:对目标函数一律求最小值;决策变量一律为非负变量;约束条件除变量的非负条件外一律为等式约束.今后,记线性规划模型的标准型为(LP).若令则(LP)便可写成下列形式:式(1-

标准型线性规划的定义及应用

由于求解数学模型算法都是为标准化的模型设计的,所以,为了便于对求解线性规划模型建立一个有效的算法,我们有必要对线性规划模型规定它的标准形式.今后,我们谈到的线性规划模型的标准型,都是指下列形式:

也就是说,线性规划的标准型,是指:对目标函数一律求最小值;决策变量一律为非负变量;约束条件除变量的非负条件外一律为等式约束.今后,记线性规划模型的标准型为(LP).

若令

则(LP)便可写成下列形式:

式(1-3)、式(1-4)中的X≥0均表示X中的各个分量xi≥0(今后此类符号意义与此相同,不再说明).对于(LP),其可行域K我们常写成:

各种形式的线性规划模型都可以化成标准型:

(1)若线性规划为

这时,只需要将求目标函数的最大值变换为求另一个目标函数的最小值:

令f=-z,于是,得到(LP):

(LP)与原有问题具有同样的可行域和最优解(若存在),只是最优值(若存在)相差一个符号而已.求解原有问题转化成求解(LP).

(2)约束条件为不等式.

如果线性规划具有不等式约束,这时我们可引进一个新变量x′,用下面两个约束条件代替这个不等式约束:

我们称x′为松弛变量.(www.daowen.com)

如果线性规划具有不等式约束

这时我们引进一个新变量x″,并用下面两个约束条件代替这个不等式约束:

我们称x″为剩余变量.

有时,x′和x″统称为松弛变量,它们在目标函数中的系数都为零.

(3)决策变量xj为自由变量:xj≷0.

解 它共有4处不符合标准型要求:对目标函数z是求最大值;x2≤0;x3为自由变量;第一、第二、第三个约束条件为不等式.为此,我们通过以下步骤把该模型标准化:

(1)令f=-z,把求max z改变为求min f;

(2)用-x4替换x2,x4为非负变量;

(3)用x5-x6替换x3,其中x5≥0,x6≥0;

(4)对不等式约束分别引进松弛变量x7和剩余变量x8,x9.

于是,得本问题的标准型:

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

我要反馈