线性规划模型及其举例
摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。
关键词：资源规划；约束条件；优化模型；最优解
在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。 一.背景介绍
如果产出量与投入量存在（或近似存在）比例关系，则可以写出投入产品的线性函数式：
1
()n
i ij j j f x a x ==∑，1,2,,,1i m m =+ (1)
若将（1）式中第（1m +）个线性方程作为待求的目标函数，其余m 个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为：
OPT. 1()n
j j j f x c x ==∑
ST. 1
n
ij j j a x =∑> ( =, < )i b , 1,2,,i m = (2)
0,j x ≥ 1,2,,j n =…
（2）式特点是有n 个待求的变量j x （1,2,,j n =…）；有1个待求的线性目标函数()f x ，有m 个线性约束等式或不等式，其中i b （1,2,,i m =…）为有限的资源投入常量。将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。
1．决策变量（Decision Variable,DV ）在约束条件范围内变化且能影响（或限定）目标函数大小的变量。决策变量表示一种活动，变量的一组数据代表一个解决方案，通常这些变量取非负值。
2．约束条件（Subject To,ST ）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都
应考虑是否符合实际，有没有可行性，因而要构造基于科学预测的综合性约束（或限定）条件。
3．目标函数（Objective Function,OF ）人们有目的活动，总是希望获得最满意的目标值，该目标值可以表达成决策变量的一个函数，即目标函数。根据需要，目标函数可以取极大化，极小化两种类型，即求最优解。
4．影子价格（Shadow Price ），用线性规划方法计算出来的反映资源最优使用效果的价格。用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为资源的经济评价，表现为影子价格。 二．建模的基本步骤
1. 确定目标函数（按照模型所需要解决的问题，用数学函数来描述目标）
2. 确定决策变量（目标的实现与那些变量有关，这里有主要变量和次要变量，在建模的初期可以进考虑主要变量对目标的影响，随后可以逐步增加变量的个数）
3. 确定约束条件（这是优化模型建模过程中最重要，也是最难的，在很多情况下，是否能够得到最优解，最优解是否合理，都是取决于约束条件的建立）
4. 模型求解（使用数学工具或数学软件求解）
5. 结果分析（分析结果的合理性、稳定性、敏感程度等） 三．线性规划的一般模型
一般地，假设线性规划数学模型，有m 个约束，有n 个决策变量
j x （1,2,,j n =…）
，目标函数的变量系数用j c 表示，j c 称为价值系数。约束条件的变量系数用ij a 表示，ij a 称为工艺系数。约束条件右端的常数用i b 表示，i b 称为资源限量。则线性规划数学模型的一般表达式可写成：
1
max(min)n
j j j z c x ==∑
S ．T. 1
(,)n
ij j i j a x b =≤≥=∑, 1,2,,i m =…
0j x ≥, 1,2,,j n =… 四．线性规划模型处理
1. 图解法
就是在平面直角坐标系上画出各个约束条件所容许变化的范围，通过图上作业法求到最优解和
目标函数极值。图解法只适用于求解两个决策变量的Lp （线性规划）问题。
2. 单纯形法
01 给定一般的Lp 问题：{min |,0}z cx Ax b x =≤≥。
02 建立Lp 问题的典式： {min |0;,0}N N B B N B N B z c c c x Nx Bx b x x =++=≥≥。
03 计算检验数：1N N B c c B N σ-=-。利用N σ进行基可行解B x 的最优性检验（i ）0N σ≤，
人工变量0R =，判定0B x ≥，0N x =为最优解，输出最优解*[,]T B N X x x =，*z 。 （ii ）N σ>0 (至少有一个k σ>0，且
k p >0)转下步。
04 选择进基变量:max{,k N N x σσ>0}=k σ，k 列的k x 为进基变量。
05 选择退基变量:min{,i
l i i ik
b x a θθ=
>0}=l θ,l 行的l B x x ≤退基。 06 确定主元lk a >0，根据主元进行行换基：01B B ∇
−−→（∇意为初等变换）
。 07利用新基B 对N ，b ，z 进行基变换：1N B N -=；1B b B b x -==，B B z c x =再转第三步。
3. 对偶单纯形法（为求影子价格作准备）
01 确定0B 为Lp 问题的一个初始基，其对应的变量为0x 。 02 判断
0x 的可行性：若0
10B x B b -=≥，0N σ≤，则0x 是Lp 问题的最优解，这时计算
停止，输出最优解。否则进行第03步。
03 若存在(1,2,,)r r i m ∈= ，使得1()r B b -<0，且在单纯形表中与1()r B b -对应行的非基变量
的系数'
rj a 全部非负，则Lp 问题无可行解；否则进行第04步。
04 确定基变量：令111()max{|()|,()l r r B b B b B b ---=<0}，对应的基变量为l x 为出基变量。
05 确定进基变量：计算'
'
min{
|j
k lj
lj
a a σθ=<0}='k
lk
a σ 。选择k θ对应的非基变量k x 为进基变量。l 行k 列交叉的元素'lk a 为主元。
06以'
lk a 为主元，按单纯形法换基迭代运算，得到一个新的基可行解，仍记为0x ，返回到02
