线性规划-实用数学方法-最优解可行域顶点取得

1. 线性规划模型

对于许多实际问题，往往希望在满足一定条件的情况下，使目标达到最优（费用最小、利益最大、产值最高等），经常使用的方法就是线性规划。

例1 某机床厂生产A、B两种产品，每种产品的利润分别为400元与300元。生产A产品每千克需用甲、乙两种原材料，分别为2kg和1kg；生产B产品每千克需用甲、乙、丙三种原材料，每种原材料各1kg。若每天只有甲9kg、乙7kg和丙6kg，问该厂应如何安排生产，才能使总利润最大？

上述问题的数学模型：设该厂生产A产品1x kg和B产品2x kg时，总利润z最大，则1x, 2x应满足

例2 某种物资需要从m个产地A1 ，A2，…，Am 运往n个销地B1 ，B2，…，Bn ，每个产地的产量为a1 ，a2，…，am，每个销地的销量为b1 ，b2，…，bn ，从产地Ai运往销地Bj的运费单价为cij元，问如何安排调度使得总费用最小？

上述问题的数学模型：设从产地Ai运往销地Bj的量为xij，则xij应满足

这些都称为线性规划问题。一般线性规划问题的标准形式为

其中：bi≥0,i=1,2,…,m 。

线性规划问题可以表示为矩阵形式

其中：x称为决策变量，c Tx称为目标函数，Ax=b和x≥0称为约束条件。

2. 线性规划模型的解

定义1 对于线性规划模型：

（1）满足约束条件的解x，称为线性规划问题的可行解。

（2）使目标函数达到最大值的可行解称为最优解。(www.xing528.com)

（3）所有可行解构成的集合称为该问题的可行域，记为R。

当线性规划问题有最优解时，一定可以在可行域的某个顶点取得。当有唯一解时，最优解就是可行域的某个顶点，当有无穷多个最优解时，至少有一个最优解是可行域的顶点。

3. 可转化为标准形式的线性规划问题

对于不是标准形式的线性规划问题，可以通过如下方法转化为标准形式：

（1）若目标函数求极大可以转化为求极小。maxc T x等价于min-c Tx。（2）不等式约束条件转化为等式约束条件：

（3）bi＜0时，可以通过方程两端同时乘以-1变为bi≥0。

（4）若某个xj没有限制，可以通过引入两个非负变量x′j ≥0和x′j ≥0，令x j=x′j-x′j ，代入目标函数和约束条件即可。

当然，还有一些看起来不是线性规划的规划问题也可以转化为线性规划问题。例如

其中：x=[x1 ,x2,…,xn ]T ，A和b为相应的维数的矩阵和向量。

取

代入原规划问题，则原规划问题转化为如下线性规划：

一些其他形式的规划问题，也可以通过一些方法转化为线性规划问题，将在后面的具体问题中再具体分析。

对于简单的线性规划问题，可以通过图解法、单纯形法、两阶段法等求解，这里不再讲解。而对于一些复杂的线性规划模型，在计算机技术迅速发展的今天，我们可以借助计算机中的软件求解。