线性规划模型及其举例

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

2、似存在)比例关系，则可以写出投入产品的线性函数式：f(x)=ax,i=1,2,m,m+1(1)iijjj=1若将(1)式中第(m+1)个线性方程作为待求的目标函数，其余m个线性方程作为资源投入的限制条件(或约束条件)，则(1)式变为：OPT.f(x)=工cxjjj=1ST.工ax(=,0,j=1,2,nj(2)式特点是有n个待求的变量x.(j=1,2,n);有1个待求的线性目标函数f(x)，有m个线j性约束等式或不等式，其中b(i=1,2,m)为有限的资源投入常量。将客观实际问题经过系统分i析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。1决策变量(DecisionVariabl

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

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

5、分析(分析结果的合理性、稳定性、敏感程度等)三. 线性规划的一般模型一般地，假设线性规划数学模型，有m个约束，有n个决策变量x(j=1,2,n)，目标函数的变量系数用c表示，c称为价值系数。约束条件的变量系数用a表jjjij示，a称为工艺系数。约束条件右端的常数用b表示，b称为资源限量。则线性规划数学模型的一ijii般表达式可写成：max(min)z二工cxjjj=1S.T.工ax,=)b,i=1,2,mijjij=1四线性规划模型处理1. 图解法就是在平面直角坐标系上画出各个约束条件所容许变化的范围，通过图上作业法求到最优解和目标函数极值。图解法只适用于求解两个决策变量的Lp(线性规划)问题

6、。2. 单纯形法lo给定一般的Lp问题：minz=cxIAx0。2o建立Lp问题的典式：minz=cc+cxINx+Bx=b0;x,x0。NNBBNBNB30计算检验数：a=c-cB-1N。利用Q进行基可行解x的最优性检验(i)Q0，x=0为最优解，输出最优解X*=x,xT，Z*。BNBN(ii)a0(至少有一个a0，且p0)转下步。Nkk40选择进基变量x:maxa,a0=a，k列的x为进基变量。kNNkkb50选择退基变量x:min0,0=0=0,1行的x0,根据主元进行行换基：BB(V意为初等变换)。lk0170利用新基B对N，b，z进行基变换：N=B-1N；b=B-1b=xBZ=cx再

7、转第三步。BB3. 对偶单纯形法(为求影子价格作准备)10确定B为Lp问题的一个初始基，其对应的变量为x0。020判断x0的可行性：若x0=B-lb0，a0，则x0是Lp问题的最优解，这时计算停止,BN输出最优解。否则进行第30步。30若存在r(rei=1,2,m)，使得(B-ib)0，且在单纯形表中与(B-ib)对应行的非基变量rr的系数a全部非负，则Lp问题无可行解；否则进行第40步。40确定基变量：令(B-1b)=maxl(B-1b)I,(B-1b)0，对应的基变量为x为出基变量。lrrl50确定进基变量：计算0=minjIa0二N。选择0对应的非基变量x为进基变量。kajakkljlk

8、l行k列交叉的元素a为主元。lk60以a为主元，按单纯形法换基迭代运算，得到一个新的基可行解，仍记为xo，返回到20lk五线性规划举例例1.（图形解）maxz=x+2x12x+x312st.彳x0V12这个问题的图解如图1所示。引进松弛变量X,x0,问题变成为标准形式34maxz=X1+2x2-X1+x2+x3=3(1)x2+x4=1(2)X1x2x3x40其解如阴影部分所示例2.求线性规划（对偶单纯形求解）mino=2x+3x+5x+6x1234x+2x+3x+x2123431234x,x,x,x01234引入多余变量X、x把约束化为等式，然后再给两边同乘以（-1）后约束变为:56-x-2x

9、-3xx+x=-212345-2x1+x2-x+33x4+x=-36得对偶单纯形表：此时基本解为X二（0，0，0，0，-2,-3），不可行。所以进行第二步。因为min-3，-2=-3，所以x为换出变量；又因为min-2/-2，-5/-1=1，所以x为换入变61量，就是要将下的系数列向量由变换成。形式（和以前学过的单纯形法中的线性变换完全一致）。做行线性变换，行（2）X（-1/2）；行（1）+彳亍（2）后得出另一个基本解为：X=（3/2,0，0，0，-1/2）此时单纯形表如下：仍然不是CTj235600CBXBbX1X2X3X4X5X60X5-1/20-5/2-5/2-5/21-1/22X13/

10、21-1/21/2-3/20-1/2Zj2-11-30-1Z-Cjj0-4-4-90-1要继续求解。因为-1/20,所以x为换出变量；由因为min二,二二二1|=8/5,所以x5555122222一和X3都可以作为换入变量，任选其中个X2,做线性变换:行(1)X(-2/5)；行(2)+行(1)X(1/2)得到一个基本解为X二(8/5,1/5,0,0,0),因解是可行的，所以是满足最优检验下的基本可行解因而也是最优解。此时单纯形表如下CTj235600CBXBbX1X2X3X4X5X63X21/50111-2/51/52X18/5101-1-1/5-2/5Zj2351-8/5-1/5为了实现缩短作出最优方案的时间，运用MATLAB编程，运用计算机模拟计算处理MATLAB是MATrixLABoratory的缩写，它将计算可视化和编程功能集成在非常便于使用的环境中，是一个交