线性规划模型及其举例

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

2、入量存在(或近似存在)比例关系，则可以写出投入产品的线性函数式：nfi(x)ajXj , i 1,2,，m,m 1(1)j i若将(1)式中第(mi)个线性方程作为待求的目标函数，其余 m个线性方程作为资源投入的限 制条件(或约束条件)，则(1)式变为：nOPT. f(x)CjXjj 1 nST.ajXj > ( =, < ) b, i 1,2,m.(2)j1Xj 0, j 1,2，,n(2)式特点是有n个待求的变量Xj ( j 1,2，,n);有1个待求的线性目标函数f(x),有m个线 性约束等式或不等式，其中h (i 1,2，,m)为有限的资源投入常量。将客观实际问题经过系统分

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

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

5、最难的，在很多情况下，是否能够 得到最优解，最优解是否合理，都是取决于约束条件的建立）4 .模型求解（使用数学工具或数学软件求解）5 .结果分析（分析结果的合理性、稳定性、敏感程度等）3 .线性规划的一般模型一般地，假设线性规划数学模型，有 m个约束，有n个决策变量Xj （ j 1,2,n）,目标函数的变量系数用5表示，cj称为价值系数。约束条件的变量系数用 a。表 示，aj称为工艺系数。约束条件右端的常数用bi表示，h称为资源限量。则线性规划数学模型的一n般表达式可写成：max（min） zcjjj iS. T.a% ( , )b, i 1,2,mXj 。，j 1,2,n4 .线性规划模型处

6、理1 .图解法就是在平面直角坐标系上画出各个约束条件所容许变化的范围，通过图上作业法求到最优解和目标函数极值。图解法只适用于求解两个决策变量的Lp （线性规划）问题。2 .单纯形法10 给定一般的 Lp 问题：min z cx | Ax b, x 0。20 建立 Lp 问题的典式：min z CnCn CbXb | Nxn Bxb b O;Xn,Xb 0。30计算检验数：n Cn CbB 1N o利用n进行基可行解xb的最优性检验（i ） n 0 ,人T工变量 R 0,判定xb 0, xn 0为最优解，输出最优解Xxb,xn , z 0（ii ） n >0 （至少有一个k >0,且

7、 pk>0）转下步。40选择进基变量xk : max n, n >0= k, k列的xk为进基变量。5°选择退基变量x : min i, i >0= l , l行的x xb退基。 aik6°确定主元a*。，根据主元进行行换基：B°Bi （意为初等变换）。7°利用新基B）CtN , b , z进行基变换：N B 1N ; b B 1b xb , z cBxB再转第三步。3.对偶单纯形法（为求影子价格作准备）1°确定Bo为Lp问题的一个初始基，其对应的变量为 x°02°判断x°的可行性：若xB B 1

8、b 0, n °,则x°是Lp问题的最优解，这时计算停止， 输出最优解。否则进行第3°步。3°若存在r（r i 1,2,|,m）,使得（bvO,且在单纯形表中与（B 1b）对应行的非基变量 的系数a；j全部非负，则Lp问题无可行解；否则进行第4°步。4°确定基变量：令（B 1b）i max| （B 1b）|,（B 1b）v0,对应的基变量为xi为出基变量。50确定进基变量：计算k min=|哪0=。选择k对应的非基变量Xk为进基变量。 ajalkl行k列父叉的兀素源为主兀。60以ak为主元，按单纯形法换基迭代运算，得到一个新的基可行解

9、，仍记为 x0 ,返回到20五.线性规划举例例1.（图形解）maxz x, 2x2 x, x2 3 st. x2 1 x1 ,x2 0这个问题的图解如图1所示。引进松弛变量x3, x4 0,问题变成为标准形式maxz=xi+2x2.xi+x2+x3=3(1)x2+x4=1(2)xix2乂3x40其解如阴影部分所示例2.求线性规划（对偶单纯形求解）min2x1 3x2 5% 6x4x1 2x2 3x3 x42x1 x2x33x4xi,x2,x3,x4引入多余变量乂5、乂6把约束化为等式，然后再给两边同乘以（-1）后约束变为:-x i -2x 2 -3x 3 -x 4 + x 5=-2-2x i

10、+x 2 - x 3 + 3x 4 +x 6 =-3得对偶单纯形表:C 一235600CbXbbxix2x3x4x5x60x5-2-i-2-3-ii00x6-3-2i-i30iZ000000Z -Cj-2-3-5-600A目标是mm型，所以检验数为己-S此时基本解为X= （0, 0, 0, 0, -2, -3）,不可行。所以进行第二步因为min-3 , -2=-3 ,所以x6为换出变量；又因为min-2/-2, -5/-1=1 ,所以xi为换入变量，就是要将xi下的系数列向量由；形式（和以前学过的单纯形法中的线性变换完全一致）。做行线性变换，行（2） 乂 （-i/2 ）;行（i） +行（2）后

11、得出另一个基本解为：X= （3/2 ,0, 0, 0, -i/2 ）此时单纯形表如下:仍然不是C 一235600CBXbbXiX2X3X4X5X60X5-1/20-5/2-5/2-5/21-1/22X13/21-1/21/2-3/20-1/2Z2-11-30-1Z -C0-4-4-90-1可行解，还4491一一.要继续求解。因为-1/2 < 0,所以X5为换出变量；由因为min , ,1 =8/5,所以X255512222和X3都可以作为换入变量，任选其中一个 X2 ,做线性变换：行(1) X (-2/5 );行(2) +行(1) X ( 1/2 )得到一个基本解为X= (8/5, 1/5, 0, 0, 0),因解是可行的，所以是满足最优检验下的基本可行解因而也是最优解。此时单纯形表如下C 一235600CBXbbXiX2X3X4X5X63X21/50111-2/51/52X18/5101-1-1/5-2/5Z2351-8/5-1/5为了实现缩短作出最优方案的时间，运用 MATLAB,运用计算机模拟计算处理。MATLAB1MATrix LABoratory的缩写，它将计算可视化和编程功