线性规划模型及其举例.doc

《线性规划模型及其举例.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、益（如产品量最多，利润最大）。一.背景介绍如果产出量与投入量存在（或近似存在）比例关系，则可以写出投入产品的线性函数式：，（1）若将（1）式中第（）个线性方程作为待求的目标函数，其余个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为：OPT.ST.>(=,<),.（2）（2）式特点是有个待求的变量（）；有1个待求的线性目标函数，有个线性约束等式或不等式，其中（）为有限的资源投入常量。将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。1．决策变量（DecisionVariable,

3、DV）在约束条件围变化且能影响（或限定）目标函数大小的变量。决策变量表示一种活动，变量的一组数据代表一个解决方案，通常这些变量取非负值。2．约束条件（Subject..To,ST）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都应考虑是否符合实际，有没有可行性，因而要构造基于科学预测的综合性约束（或限定）条件。3．目标函数（ObjectiveFunction,OF）人们有目的活动，总是希望获得最满意的目标值，该目标值可以表达成决策变量的一个函数，即目标函数。根据需要，目标函数可以取极大化，极小化两种类型，即求最优解。4．

4、影子价格（ShadowPrice），用线性规划方法计算出来的反映资源最优使用效果的价格。用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为资源的经济评价，表现为影子价格。二．建模的基本步骤1.确定目标函数（按照模型所需要解决的问题，用数学函数来描述目标）2.确定决策变量（目标的实现与那些变量有关，这里有主要变量和次要变量，在建模的初期可以进考虑主要变量对目标的影响，随后可以逐步增加变量的个数）3.确定约束条件（这是优化模型建模过程中最重要，也是最难的，在很

5、多情况下，是否能够得到最优解，最优解是否合理，都是取决于约束条件的建立）4.模型求解（使用数学工具或数学软件求解）5.结果分析（分析结果的合理性、稳定性、敏感程度等）三．线性规划的一般模型一般地，假设线性规划数学模型，有个约束，有个决策变量（），目标函数的变量系数用表示，称为价值系数。约束条件的变量系数用表示，称为工艺系数。约束条件右端的常数用表示，称为资源限量。则线性规划数学模型的一般表达式可写成：S．T.,,四．线性规划模型处理1.图解法..就是在平面直角坐标系上画出各个约束条件所容许变化的围，通过图上作业法求到最优解和目

6、标函数极值。图解法只适用于求解两个决策变量的Lp（线性规划）问题。2.单纯形法给定一般的Lp问题：。建立Lp问题的典式：。计算检验数：。利用进行基可行解的最优性检验（i），人工变量，判定，为最优解，输出最优解，。（ii）>0(至少有一个>0，且>0)转下步。选择进基变量>0}=，列的为进基变量。选择退基变量>0}=,行的退基。确定主元>0，根据主元进行行换基：（意为初等变换）。利用新基对，，进行基变换：；，再转第三步。3.对偶单纯形法（为求影子价格作准备）确定为Lp问题的一个初始基，其对应的变量为。判断的可行性：若，，则是Lp

7、问题的最优解，这时计算停止，输出最优解。否则进行第步。若存在，使得<0，且在单纯形表中与对应行的非基变量的系数全部非负，则Lp问题无可行解；否则进行第步。确定基变量：令<0}，对应的基变量为为出基变量。确定进基变量：计算<0}=。选择对应的非基变量为进基变量。行列交叉的元素为主元。以为主元，按单纯形法换基迭代运算，得到一个新的基可行解，仍记为，返回到..五．线性规划举例例1．（图形解）这个问题的图解如图1所示。引进松弛变量x3，x4³0，问题变成为标准形式maxz=x1+2x2s.t.x1+x2+x3=3(1)x2+x4=1(

8、2)x1x2x3x4³0OABCDx1x23210123x3=0x4=0x1=0x2=0其解如阴影部分所示例2.求线性规划(对偶单纯形求解)引入多余变量x5、x6把约束化为等式，然后再给两边同乘以（-1）后约束变为：-x1-2x2-3x3-x4+x5=-2-2x1+x2-x3