大学应用数学：线性规划问题的标准形式

由前面的实例可以看出，线性规划问题的数学模型多种多样，约東条件有的是“≤”形式，有的是“≥”形式，有的是“=”形式，目标函数有的是求最小值，有的是求最大值，这种多样性给问题的求解带来很大麻烦.因此为了讨论和计算的方便，有必要将各种不同的形式统一起来，成为一种标准形式.

1.标准形式

规定线性规划问题数学模型的标准形式为：

其中bi≥0（i=1，2，…，m）.

线性规划问题数学模型的标准形式简称为标准形，它必须满足：

（1）约束条件中，所有决策变量都有非负限制，其他约束条件均用等式表示.

（2）目标函数是求最小值.

（3）约束条件等式右端的约束常数非负.

标准形（7.1）还可以写成矩阵形式：

其中c=（c1，c2，…，cn），X=（x1，x2，…，xn）T，b=（b1，b2，…，bm）T，

此时线性规划问题的可行解又记为

2.标准化

如果线性规划问题的数学模型不是标准形，可按下面方法将其化为标准形：

（1）如果是求目标函数的最大值，即求

max S=c1x1+c2x2+…+cnxn

则可令S′=-S，从而转化为求目标函数S′的最小值，即

min S′=-S=-c1x1-c2x2-…-cnxn(https://www.xing528.com)

（2）约束条件有线性不等式.如果约束条件中有线性不等式，则可以引入新的非负变量（称为松弛变量），把不等式转化为等式.

例如，约束条件为“≤”，则可在“≤”的左端加上一个非负的松弛变量，使原不等式变为等式，把“≤”号改为“=”.

又如，约束条件为“≥”，则可在“≥”的左端减去一个非负的松弛变量，使原不等式变为等式，把“≥”号改为“=”.

松弛变量在经济问题中可以看成未被利用的资源（或未考虑的因素），它在目标函数中的系数恒为零，因而松弛变量在目标函数的表达式中可以写出来也可以不写出来，对松弛变量应作非负的限制.

（3）含有不是非负的决策变量.如果某个决策变量xj（j=1，2，…，n）没有非负的限制，则可以引入两个非负的变量代入约束条件和目标函数中，从而对全部变量都有非负限制.

（4）约束常数中有负数.如果某个表达式右端的约束常数bk为负数，则只需将该式两边同乘以-1即可.

例7.3　将下列线性规划模型化为标准形式：

解　引入松弛变量x4≥0，x5≥0.

令，且

令S′=-S，则得标准形如下：

练习7.1

1.写出下列问题的数学模型.

（1）电视台为某个广告公司特约播放两套片集.其中片集甲插放时间为20分钟，广告时间为1分钟，收视观众为60万；片集乙播放时间为10分钟，广告时间为1分钟，收视观众为20万.广告公司规定每周至少有6分钟广告，而电视台每周只能为该公司提供不多于80分钟的节目时间.问电视台每周应播放两套片集各多少次，才能获得最高的收视率?

（2）若需在长为4 000 mm的圆钢上截出长为698 mm和518 mm的两种毛坯，问怎样截取才能使残料最少?

2.把下列线性规划问题化为标准形式.