1线性规划教程.ppt

线性规划及单纯形法 (Linear Programming); ; 设 备 产 品;问题中总有未知的变量，需要我们去解决。;;也可以记为如下简写形式：;如将上例用表格表示如下：;向 量 形 式：;矩阵形式：;1.1.3 线性规划问题的标准形式;练习：将下述LP模型标准化：;规 划;一 般 有 两种方法;1、解的概念; ⑸ 基本可行解：满足非负约束条件的基本解，简称基可行解。;Max z=2x1+3x2 st. x1+x2≤3 x1+2x2≤4 x1,x2≥0; 例1. 某地区有三个矿山A1，A2，A3，生产同一种矿物。另外有四个这种矿物消费地（铁厂）B1，B2，B3，B4。各矿山产量及铁厂的需要量和矿山将矿物运到铁厂的单位运价如表2-2。问应如何调运，才使总运费最省？;解：该题有两个限制条件：一个是产量，一个是需量。目标是总运费最省。 设：xij表示从第i个矿山运往第j个铁厂的矿物运量。这样得到以下两组线性方程组： （1）各矿山矿物的生产量与运出量平衡方程：;（2）各铁厂矿物供应量与需要量平衡方程 ;（4）目标函数 ;（二）资源最优利用的数学模型;解：设A、B两产品的计划产量为x1、x2 则数学模型为： ;（三）机床负荷问题的数学模型;（三）机床负荷问题的数学模型; 解：设xij表示第i种机床用来生产第j种产品的台数，则数学模型为： （1）加工甲、乙产品机床台数平衡方程： ;（3）变量非负： ;（四）人员分配的数学模型 ;解：设xij表示i个工人分配担任第j项工作的情况，并xij取1和0两个值， xij=1，表示第i个工人分配担任第j项工作； xij=0，表示i个工人不担任第j项工作。 数学模型： （1）每个工人只担任一项工作 ;（2）每项工作必由一个工人担任 ;（五）合理配料问题的数学模型;（五）合理配料问题的数学模型; （六）合理下料问题的数学模型;（六）合理下料问题的数学模型;设：x1、x2、x3、x4、x5、x6、x7、x8分别表示这八种下料方式钢管消耗的总根数，则数学模型：; 建立直角坐标 ，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。;0; 例二、;⑴; 某车间用三种不同型号的机床Ⅰ、Ⅱ、Ⅲ，加工A、B两种零件，机床台数、生产效率如表所示。问如何合理???排机床的加工任务，才能使生产的零件总数最多？;1.3.1凸集和顶点;（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。;定理1：若线性LP模型存在可行解，则可行域为凸集。;引理：线性规划问题的可行解X=(x1, x2,······,xn)T 为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。;证：用反证法 X非基本可行解?X非凸集顶点 （1）必要性：X非基本可行解? X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，;由 (1)+(2)得 (x1+ ??1)P1+ (x2+ ??2)P2+······+ (xm+ ??m)Pm=b 由 (1)-(2)得 (x1 -??1)P1+ (x2 - ??2)P2+······+ (xm -??m)Pm=b;（2）充分性： X非凸集顶点? X非基本可行解;∵ Y、Z为不同两点，∴ yj-zj不全为0， ∴ P1,P2,······,Pr线性相关， ∴ X非基本可行解。;z1=CX1=CX0-C?=zmax-C? ，z2=CX2=CX0+C? =zmax+C? ∵ z0 = zmax ? z1 ， z0 = zmax ? z2 ， ∴ z1 = z2 = z0 ，即 X1 、 X2也为最优解， 若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优解。 从而，必然会找到一个基本可行解为最优解。;单纯形法的计算步骤：;1.3.3初始基本可行解的确定：;1.3.4 从一个基本可行解向另一个基本可行解转换; 又P1 P2 …… Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即 Pj = a1j P1 + a2j P2 +······+ amj Pm ，即 Pj =? aij pi ， 移项，两端同乘?0 ，有 ?(Pj-? aij pi )=0 ·········(2);∴ X1 也为基本可行解。;因?0，所以有如下结论：;（一）、基本思路;找出一个初始可行解;;判定标准：;;;;;练习;迭代次数;（一）、模型情况 变