线性规划模型及其举例

1、线性规划模型及其举例摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。 关键词：资源规划；约束条件；优化模型；最优解在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。一.背景介绍如果产出量与投入量存在（或近

2、似存在）比例关系，则可以写出投入产品的线性函数式：， （1）若将（1）式中第（）个线性方程作为待求的目标函数，其余个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为：OPT. ST. > ( =, < ), . （2） （2）式特点是有个待求的变量（）；有1个待求的线性目标函数，有个线性约束等式或不等式，其中（）为有限的资源投入常量。将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。1决策变量（Decision Variable,DV）在约束条件范围内变化且能影响（或限定）目标函数大小的变量。决策变量表示一种活动，变量的一组数据代表一

3、个解决方案，通常这些变量取非负值。2约束条件（Subject To,ST）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都应考虑是否符合实际，有没有可行性，因而要构造基于科学预测的综合性约束（或限定）条件。3目标函数（Objective Function,OF）人们有目的活动，总是希望获得最满意的目标值，该目标值可以表达成决策变量的一个函数，即目标函数。根据需要，目标函数可以取极大化，极小化两种类型，即求最优解。4影子价格（Shadow Price），用线性规划方法计算出来的反映资源最优使用效果的价格。用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应

4、的极小值，其解就是对偶解，极小值作为资源的经济评价，表现为影子价格。二建模的基本步骤1. 确定目标函数（按照模型所需要解决的问题，用数学函数来描述目标）2. 确定决策变量（目标的实现与那些变量有关，这里有主要变量和次要变量，在建模的初期可以进考虑主要变量对目标的影响，随后可以逐步增加变量的个数）3. 确定约束条件（这是优化模型建模过程中最重要，也是最难的，在很多情况下，是否能够得到最优解，最优解是否合理，都是取决于约束条件的建立）4. 模型求解（使用数学工具或数学软件求解）5. 结果分析（分析结果的合理性、稳定性、敏感程度等）三线性规划的一般模型一般地，假设线性规划数学模型，有个约束，有个决策

5、变量（），目标函数的变量系数用表示，称为价值系数。约束条件的变量系数用表示，称为工艺系数。约束条件右端的常数用表示，称为资源限量。则线性规划数学模型的一般表达式可写成：ST. , , 四线性规划模型处理1. 图解法就是在平面直角坐标系上画出各个约束条件所容许变化的范围，通过图上作业法求到最优解和目标函数极值。图解法只适用于求解两个决策变量的Lp（线性规划）问题。2. 单纯形法 给定一般的Lp问题：。 建立Lp问题的典式： 。 计算检验数：。利用进行基可行解的最优性检验（i），人工变量，判定，为最优解，输出最优解，。（ii）>0 (至少有一个>0，且>0)转下步。 选择进基变量

6、>0=，列的为进基变量。 选择退基变量>0=,行的退基。 确定主元>0，根据主元进行行换基：（意为初等变换）。利用新基对，进行基变换：；，再转第三步。3. 对偶单纯形法（为求影子价格作准备） 确定为Lp问题的一个初始基，其对应的变量为。 判断的可行性：若，则是Lp问题的最优解，这时计算停止，输出最优解。否则进行第步。 若存在，使得<0，且在单纯形表中与对应行的非基变量的系数全部非负，则Lp问题无可行解；否则进行第步。确定基变量：令<0，对应的基变量为为出基变量。 确定进基变量：计算<0=。选择对应的非基变量为进基变量。行列交叉的元素为主元。以为主元，按单纯形

7、法换基迭代运算，得到一个新的基可行解，仍记为，返回到五线性规划举例例1（图形解）这个问题的图解如图1所示。引进松弛变量x3，x4³0，问题变成为标准形式maxz=x1+2x2s.t.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3x4³0OABCDx1x23210123x3=0x4=0x1=0x2=0 其解如阴影部分所示例2.求线性规划 (对偶单纯形求解)引入多余变量x5、x6把约束化为等式，然后再给两边同乘以（-1）后约束变为： -x1 -2x2 -3x3 -x4 + x5 =-2 -2x1 +x2 - x3 + 3x4 +x6 =-3  

8、   得对偶单纯形表： Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 -2 -1 -2 -3 -1 1 0 0 x6 -3 -2 1 -1 3 0 1 Zj 0 0 0 0 0 0 Zj -Cj -2 -3 -5 -6 0 0 此时基本解为X=（0，0，0，0，-2，-3），不可行。所以进行第二步。 因为min-3，-2=-3，所以x6为换出变量；又因为min-2/-2 ，-5/-1=1，所以x1为换入变量，就是要将x1下的系数列向量由 变换成 形式（和以前学过的单纯形法中的线性变换完全一致）。做行线性变换， 行（2）×

9、;（-1/2）；行（1）+行（2）后得出另一个基本解为：X=（3/2，0，0，0，-1/2）此时单纯形表如下：Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 -1/2 0 -5/2 -5/2 -5/2 1 -1/2 2 x1 3/2 1 -1/2 1/2 -3/2 0 -1/2 Zj 2 -1 1 -3 0 -1 Zj -Cj 0 -4 -4 -9 0 -1 仍然不是可行解，还要继续求解。 因为-1/2 < 0,所以x5为换出变量；由因为=8/5，所以x2和x3都可以作为换入变量，任选其中一个x2 ，做线性变换： 行（1）×（-2/5

10、）；行（2）+行（1）×（1/2） 得到一个基本解为X=（8/5，1/5，0，0，0），因解是可行的，所以是满足最优检验下的基本可行解因而也是最优解。此时单纯形表如下 Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 3 x2 1/5 0 1 1 1 -2/5 1/5 2 x1 8/5 1 0 1 -1 -1/5 -2/5 Zj 2 3 5 1 -8/5 -1/5 为了实现缩短作出最优方案的时间，运用MATLAB编程，运用计算机模拟计算处理。MATLAB是MATrix LABoratory的缩写，它将计算可视化和编程功能集成在非常便于使用的环境中，是一个交互式的，以距阵计算为基础的科学和工程计算软件