《线性规划模型及其举例.doc》由会员分享，可在线阅读，更多相关《线性规划模型及其举例.doc（7页珍藏版）》请在三一文库上搜索。
1、线性规划模型及其举例摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。 关键词：资源规划；约束条件；优化模型；最优解在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。一.背景介绍如果产出量与投入量存在（或近
2、似存在）比例关系，则可以写出投入产品的线性函数式：， （1）若将（1）式中第（）个线性方程作为待求的目标函数，其余个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为：OPT. ST. ( =, 0 (至少有一个0，且0)转下步。 选择进基变量0=，列的为进基变量。 选择退基变量0=,行的退基。 确定主元0，根据主元进行行换基：（意为初等变换）。利用新基对，进行基变换：；，再转第三步。3. 对偶单纯形法（为求影子价格作准备） 确定为Lp问题的一个初始基，其对应的变量为。 判断的可行性：若，则是Lp问题的最优解，这时计算停止，输出最优解。否则进行第步。 若存在，使得0，且在单纯形表中与
3、对应行的非基变量的系数全部非负，则Lp问题无可行解；否则进行第步。确定基变量：令0，对应的基变量为为出基变量。 确定进基变量：计算0=。选择对应的非基变量为进基变量。行列交叉的元素为主元。以为主元，按单纯形法换基迭代运算，得到一个新的基可行解，仍记为，返回到五线性规划举例例1（图形解）这个问题的图解如图1所示。引进松弛变量x3，x40，问题变成为标准形式maxz=x1+2x2s.t.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3x40OABCDx1x23210123x3=0x4=0x1=0x2=0 其解如阴影部分所示例2.求线性规划 (对偶单纯形求解)引入多余变量x5、x6把约束化
4、为等式，然后再给两边同乘以（-1）后约束变为： -x1 -2x2 -3x3 -x4 + x5 =-2 -2x1 +x2 - x3 + 3x4 +x6 =-3 得对偶单纯形表： 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为
5、换入变量，就是要将x1下的系数列向量由 变换成 形式（和以前学过的单纯形法中的线性变换完全一致）。做行线性变换， 行（2）（-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为换出变量；由因
6、为=8/5，所以x2和x3都可以作为换入变量，任选其中一个x2 ，做线性变换： 行（1）（-2/5）；行（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的缩写，它将计算可视化和编程功能集成在非常便于使用的环境中，是一个交互式的，以距阵计算为基础的科学和工程计算软件。MATLAB的特点可以简要地归纳如下：编程效率高，计算功能强，使用简便，易于扩充等特点。参考文献：1. 沈继红等 数学建模 哈尔滨工程大学出版社 2003年 2. 胡富昌 线性规划 中国人民大学出版社 2004年 3. 谷源盛 运筹学 重庆大学出版社 2003年 4. 姜启源等 数学模型 高等教育出版社 2005年