《线性规划模型及其应用》由会员分享，可在线阅读，更多相关《线性规划模型及其应用（42页珍藏版）》请在金锄头文库上搜索。
1、第四章 线性规划模型及应用线性规划是运筹学的一个重要分支。运筹学：包括数学规划图论与网络线性规划非线性规划整数规划目标规划动态规划随机规划模拟论等对策论存储轮排队论决策论线性规划所研究的问题：一是在资源（如钢材、电力等）受限制的前提下，研究如何合理使用这些资源，以完成更多的任务；二是在任务一定的前提下，研究如何合理安排，用最少的资源来完成给定的任务。线性规划在实际应用中包括下列四个步骤：1.确定问题，明确目标和限制因素；2.建立模型；3.模型求解；4.应用模型和数据进行经济分析。第一节 线性规划问题的数学模型-p2第二节 线性规划问题的图解法-p8第三节 线性规划问题的基本理论-p11第四节
2、单纯形法-p16第五节 运输问题的特殊解法-p第一节 线性规划问题的数学模型一、问题的提出P138二、数学模型的建立例1：P137生产计划最大利润问题某企业拟生产A、B两种产品，需要经过车、铣两个工段，加工的工时定额、每天可用工时和两种产品可能获得的利润见下表。要求拟订一个获得利润最大的生产计划。加工工时定额（h/件）可利用工时（h/日）产品A产品B车床工段51060铣床工段4440可获得利润（元/件）68解：确定变量。确定目标函数。列出约束条件。决策变量为非负值。设X1、X2分别为产品A、B的生产数量，则建立线性规划模型为：例2：某工厂要做100套钢架，每套用长为2.9米、2.1米、1.5米
3、的圆钢各一根。已知原坯料每根长7.4米。如何下料，可使所用原材料最省？解：单一下料，利用率低；套裁法，利用率高。套裁下料方案：各方案下 下料方案 坯料根数坯料长度（m）一二二四三六四一五七六三七五八八2.9（m）211100002.1（m）021032101.5（m）10130234总长度（m）7.37.16.57.46.37.26.66余料（m）0.10.30.901.10.20.81.4设1，2，3，4，5，6分别表示六种下料方案切割的钢管根数，则截出：（1）长2.9m的坯料数：1+22+4+6根；（2）长2.1m的坯料数：23+24+5+6根；（3）长1.5m的坯料数：31+2+23+3
4、5+6根；建模：求1.一般形式2.紧缩形式定义：求一组变量xj (j=1,2,.,n)的值，在满足线性约束条件下，使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。3.标准形式目标函数为求最大值。若，为把目标函数化为求最大值，只需令：，于是，即约束条件为等式。若约束条件为不等式，需化不等式约束条件为等式约束条件，只需引入新的非负变量以表示不等式左右两端的差额就可以了。这些新变量统称为松弛变量（剩余变量），它在目标函数中所对应的系数为零。决策变量xj有非负限制。若决策变量xk无非负限制，这样的变量称为自由变量。将它化为标准形式有两种方法：引进新的非负变量
5、，代入约束条件和目标函数中，于是原问题就化为用n+1个非负变量来描述的线性规划问题。从约束条件中，选自由变量xk的系数不为零的等式，解出xk并代入其它m-1个约束方程和目标函数中，于是原问题就化为含n-1个非负变量，满足m-1个约束方程的线性规划问题。约束条件右端常数bi0，若bi0时，对于等式约束，只需在等式两边同时乘以-1；对于不等式约束，只需在不等式两边同时乘以-1，同时改变不等号的方向。若例3.将线性规划问题的数学模型化为标准形式。解：根据公式：，得作业1：解：引入，令作业2：根据，解得，代入第二节 线性规划问题的图解法图解法是用作图的方法来求线性规划问题的解，它适用于仅含两个决策变量
6、的线性规划问题的数学模型求解。虽然这种方法的应用范围受到很大的限制，但这种方法简单、直观，而且有助于理解线性规划问题求解的基本原理。见教材P144图解法步骤：求可行域：在平面直角坐标系中，可行域是各约束条件所表示的半平面的公共部分。求最优解：将目标函数Z看成参数，作出等值线，然后根据原问题求最大值（或最小值）的要求，令等值线沿Z值增加（或减少）方向在可行域内平行移动，直到找到等值线与可行域最后相交的一点，即为所要求的最优解。通过图解法求解，其可行域与最优解有可能出现下列情况：1. 可行域为有界域。 有唯一的最优解; 有多个最优解。2. 可行域为无界区域。 有唯一的最优解; 有多个最优解; 目标
7、函数无界（即Z ），因此无有限最优解。3. 可行域为空集，因此没有可行解。以上情况示于下图中。图中的虚线表示等值线，虚线上的箭头表示等值线的移动方向，阴影部分为可行域。综合上述讨论，可以看到：1. 线性规划问题的解有四种可能：唯一最优解，多个最优解，无界解（即无有限最优解）和无可行解。2. 线性规划问题的可行域（解）如果存在，其可行域一般是凸多边形（凸集）。3. 线性规划问题的基本可行解对应线性规划问题可行域（凸集）的顶点。4. 线性规划问题的最优解如果存在，则最优解一定在凸多边形的某一个顶点上取得（一定存在一个基本可行解是最优解）。上述结论，都可以推广到n个决策变量的线性规划问题上去。第三节
8、 线性规划问题的基本理论一、线性规划问题的解对于线性规划问题： 假定系数矩阵A的秩为m，且mn。先定义几个解的概念：1.可行解：满足线性规划问题约束条件和非负约束的一组值X=（x1，x2，xn）T，称为线性规划问题的可行解。全体可行解的集合，称为线性规划问题的可行集或可行域。2.最优解：使目标函数Z取得最大（小）值的可行解，称为最优解。最优解对应的目标函数值，称为最优值。3.基、基变量、非基变量：系数矩阵A中任意一个非奇异m阶子矩阵B，称为线性规划问题的一个基。如果决策变量xj所对应的系数列向量Pj包含在B中，则称xj为基变量；否则，称xj为非基变量。显然，当基改变时，相应的基变量，非基变量也
9、随之改变。不妨设：则x1，x2，xm 为基变量，x m+1，x m+2，xm+n为非基变量，由假设mn，所以约束方程组有无穷多解。假设B为一个基，则在方程组中，令非基变量x m+1=x m+2=xm+n=0得一个解：X=（x1，x2，xm，0，0）T4. 基本解：对于有n个决策变量和m个约束方程的线性方程组，在取定基的情况下，令n-m个非基变量等于零，求得方程组的解，称这个解为线性规划问题的基本解。5. 基本可行解：满足非负约束的基本解，称为基本可行解。对应于基本可行解的基B，称为可行基。显然，一个线性规划问题的基本解的个数不超过个，因此，基本可行解的个数，一般说来要小于个。即基本可行解的个数
10、要小于基本解的个数，最多是相等，而且每个基本可行解的非零分量个数不大于系数矩阵A的秩m。6. 退化解：非零分量的个数小于m的基本可行解，称为退化解。二、凸集用集合来描述线性规划理论比较方便，为此，先定义：线段：设A =（a1,a2,an），B =（b1,b2,bn）是n维欧氏空间的任意两点，所有满足下列条件的点X=（x1，x2，xn）的集合称为以A,B为端点的线段，A,B称为线段的端点，其余的点称为线段的内点。凸集：设D为n维欧氏线性空间的一个点集。如果对任意的Xl D，X2 D, 有：X = Xl 十（1 一 ）X2 D （0 1）则称D为凸集。例如，图 14 - 3 中（a），（b）,（c
11、）是由平面上任意两点连线上所有点组成的集合、四边形内所有点组成的集合、空间四面体内所有点组成的集合，都是凸集合 ; 而图14-3 的（d）就不是凸集合。顶点：设D是凸集，X D, 如果D中不存在不同的两点 Xl，X2，使：X= Xl +（1 一）X2（0 1）则称X是D的一个顶点（或称极点）。即一个凸集的顶点，它不能是该凸集的任何线段的内点。凸组合：设Xl，X2，Xk是n维欧氏空间Vn中的k个点。如果存在1,2,k，且0i1，（i=1,2,k），使：X=1Xl+2X2+k Xk，则称X为Xl,X2,Xk的凸组合。三、线性规划问题的基本定理定理 1 线性规划的可行解集合，一定是凸集。定理 2 线
12、性规划问题的可行解为基本可行解的充分与必要条件是它的正分量所对应的系数列向量线性无关。定理3 设，则X是D的顶点的充分与必要条件，X为线性规划问题的基本可行解。定理 4 设D为有界凸集，则对任意XD, 可表示为D的顶点的凸组合。定理 5 设可行域D有界，则线性规划问题的最优值一定在D的某个顶点达到。例1所给的线性规划问题的基本解、基本可行解，并从中选出最优解。解：引入松弛变量X3，X4，使数学模型化为标准形式： 由于显然，A的秩为2, 则线性规划问题的所有基本解、基本可行解如下表所示。由于最优解一定在可行域的顶点取得，而顶点又一定是基本可行解，且其个数是有限的，所以如例1, 只需求出该问题的所
13、有基本可行解，将其对应目标函数值一一进行比较，就可得到最优解（见下表）。然而，当决策变量的个数n, 约束方程的个数m比较大时，上述方法是行不通的，正确的方法是构造一个逐步改进的基本可行解的序列，使其对应的目标函数值逐步向最优值接近，最终取得最优解。线性规划问题的基本解与基本可行解基基变量非基变量基本解基本可行解目标函数值最优解图(P1,P2)(P1,P3)(P1,P4)(P2,P3)(P2,P4)(P3,P4)x1,x2x1,x3x1,x4x2,x3x2,x4x3,x4x3,x4x2,x4x2,x3x1,x4x1,x3x1,x2(50,250,0,0)(400/3,0,1000/3,0)(300,0,0,-500)(0,400,-200,0)(0,300,0,100)(0,0,600,400)是是是是47508000/345000是B点A点C点D点第四节 单纯形法一、单纯形法原理二、大M法与两阶段法三、单纯形法的计算步骤四、单纯形法的矩阵形式（一）单纯形法的基本思路-p16（二）一般线性规划问题的单纯形法-p27（三）单纯形表-p31（四）计算中可能遇到的几个问题-p37单纯形法的基本思路是：从一个基本可行解出发，转移到另一个基本可行解，每一次转移都使目标函数值得到改善，这在数学上称为从一
