线性规划模型及其举例
摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。
关键词：资源规划；约束条件；优化模型；最优解
在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。 一.背景介绍
如果产出量与投入量存在（或近似存在）比例关系，则可以写出投入产品的线性函数式：
fi(x)??aijxj，i?1,2,…,m,m?1 （1）
j?1n若将（1）式中第（m?1）个线性方程作为待求的目标函数，其余m个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为：
OPT. f(x)??cjxj
j?1nST. ?aijxj> ( =, < )bi, i?1,2,…,m. （2）
j?1n xj?0, j?1,2,…,n
（2）式特点是有n个待求的变量xj（j?1,2,…,n）；有1个待求的线性目标函数f(x)，有m个线性约束等式或不等式，其中bi（i?1,2,…,m）为有限的资源投入常量。将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。
1．决策变量（Decision Variable,DV）在约束条件范围内变化且能影响（或限定）目标函数大小的变量。决策变量表示一种活动，变量的一组数据代表一个解决方案，通常这些变量取非负值。
2．约束条件（Subject To,ST）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都
1
应考虑是否符合实际，有没有可行性，因而要构造基于科学预测的综合性约束（或限定）条件。
3．目标函数（Objective Function,OF）人们有目的活动，总是希望获得最满意的目标值，该目标值可以表达成决策变量的一个函数，即目标函数。根据需要，目标函数可以取极大化，极小化两种类型，即求最优解。
4．影子价格（Shadow Price），用线性规划方法计算出来的反映资源最优使用效果的价格。用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为资源的经济评价，表现为影子价格。 二．建模的基本步骤
1. 确定目标函数（按照模型所需要解决的问题，用数学函数来描述目标）
2. 确定决策变量（目标的实现与那些变量有关，这里有主要变量和次要变量，在建模的初期可以进考虑主要变量对目标的影响，随后可以逐步增加变量的个数）
3. 确定约束条件（这是优化模型建模过程中最重要，也是最难的，在很多情况下，是否能够得到最优解，最优解是否合理，都是取决于约束条件的建立）
4. 模型求解（使用数学工具或数学软件求解）
5. 结果分析（分析结果的合理性、稳定性、敏感程度等） 三．线性规划的一般模型
一般地，假设线性规划数学模型，有m个约束，有n个决策变量
，目标函数的变量系数用cj表示，cj称为价值系数。约束条件的变量系数用aij表xj（j?1,2,…,n）
示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成：
nmax(min)z??cjxj
j?1nS．T. ?aijxj?(?,?)bi, i?1,2,…,m
j?1 xj?0, j?1,2,…,n 四．线性规划模型处理
1. 图解法
就是在平面直角坐标系上画出各个约束条件所容许变化的范围，通过图上作业法求到最优解和
2
目标函数极值。图解法只适用于求解两个决策变量的Lp（线性规划）问题。
2. 单纯形法
10 给定一般的Lp问题：{minz?cx|Ax?b,x?0}。
20 建立Lp问题的典式： {minz?cNcN?cBxB|NxN?BxB?b?0;xN,xB?0}。
30 计算检验数：?N?cN?cBB?1N。利用?N进行基可行解xB的最优性检验（i）?N?0，
人工变量R?0，判定xB?0，xN?0为最优解，输出最优解X*?[xB,xN]T，z*。 （ii）?N>0 (至少有一个?k>0，且
pk>0)转下步。
40 选择进基变量xk:max{?N,?N>0}=?k，k列的xk为进基变量。
50 选择退基变量xl:min{?i,?i?bi>0}=?l,l行的xl?xB退基。 aik?60 确定主元alk>0，根据主元进行行换基：B0??。 ?B1（?意为初等变换）
70利用新基B对N，b，z进行基变换：N?B?1N；b?B?1b?xB，z?cBxB再转第三步。
3. 对偶单纯形法（为求影子价格作准备）
10 确定B0为Lp问题的一个初始基，其对应的变量为x0。 20 判断
0x0的可行性：若xB?B?1b?0，?N?0，则x0是Lp问题的最优解，这时计算
停止，输出最优解。否则进行第30步。
30 若存在r(r?i?1,2,?,m)，使得(B?1b)r<0，且在单纯形表中与(B?1b)r对应行的非基变量
'的系数arj全部非负，则Lp问题无可行解；否则进行第40步。
40 确定基变量：令(B?1b)l?max{|(B?1b)r|,(B?1b)r<0}，对应的基变量为xl为出基变量。
50 确定进基变量：计算?k?min{'l行k列交叉的元素alk为主元。
?j'alj'<0}=|alj?k 。选择?k对应的非基变量xk为进基变量。'alk'60以alk为主元，按单纯形法换基迭代运算，得到一个新的基可行解，仍记为x0，返回到20
3
五．线性规划举例
例1．（图形解）
maxz?x1?2x2?x1?x2?3 ?st.?x2?1?x,x?0?12这个问题的图解如图1所示。引进松弛变量x3，x4?0，问题变成为标准形式
max z= x1 +2x2 s.t. 2 1 C x1=0 O 0 x2=0 1 2 3 A x1 x3=0 B x4=0 3 (1) (2) x1 +x2 +x3 x2 =3 +x4 =1 x1 x2 D x2 x3 x4 ?0 其解如阴影部分所示 例2.求线性规划 (对偶单纯形求解) min??2x1?3x2?5x3?6x4?x1?2x2?3x3?x4?2??2x1?x2?x3?3x4?3?x,x,x,x?0?1234
引入多余变量x5、x6把约束化为等式，然后再给两边同乘以（-1）后约束变为：
-x1 -2x2 -3x3 -x4 + x5 =-2 -2x1 +x2 - x3 + 3x4 +x6 =-3
得对偶单纯形表：
4
Cj→ CB 0 0 XB x5 x6 Zj Zj -Cj 2 b x1 -2 -1 -3 -2 0 -2 3 x2 -2 1 0 -3 5 x3 -3 -1 0 -5 6 x4 -1 3 0 -6 0 x5 1 0 0 0 0 x6
0 1 0 0
此时基本解为X=（0，0，0，0，-2，-3），不可行。所以进行第二步。
因为min{-3，-2}=-3，所以x6为换出变量；又因为min{-2/-2 ，-5/-1}=1，所以x1为换入变量，就是要将x1下的系数列向量由
变换成
形式（和以前学过的单纯形法中的线性变换完
全一致）。做行线性变换， 行（2）×（-1/2）；行（1）+行（2）后得出另一个基本解为：X=（3/2，0，0，0，-1/2）此时单纯形表如下：
Zj Zj -Cj 2 0 -1 -4 1 -4 -3 -9 0 0 -1 -1 Cj→ CB XB b 2 x1 0 1 3 x2 5 x3 6 x4 0 x5 1 0 0 x6 -1/2 -1/2 0 x5 -1/2 2 x1 3/2 -5/2 -5/2 -5/2 -1/2 1/2 -3/2 仍然不是可行解，还要继续求解。 因为-1/2 < 0,所以x5为换出变量；由因为
????4?4?9?1? min?,,,?=8/5，所以x2和x3都可以作为换入变量，任选其中一个x2 ，做线性变换：5551???????2222?
5
线性规划模型及其举例
