线性规划方法课件.pptxVIP

线性规划方法;第1节线性规划及其单纯形求解方法;一、线性规划的数学模型;运输问题

假设某种物资（譬如煤炭、钢铁、石油等）有m个产地，n个销地。第i产地的产量为ai（i=1，2，…，m），第j销地的需求量为bj(j=1,2，…，n)，它们满足产销平衡条件

。

如果产地i到销地j的单位物资的运费为Cij，要使总运费达到最小，可这样安排物资的调运计划：;设xij表示由产地i供给销地j的物资数量，则上述问题可以表述为：

求一组实值变量xij(i=1，2，…，m；j=1，2，…，n)，使其满足;资源利用问题;设第j种产品的生产数量为xj(j=1，2，…，n)，则上述资源问题就是：;合理下料问题;设采用Bj方式下料的原材料数为xj，则上述问题可表示为：;（二）线性规划的数学模型;;采用矩阵形式可描述为：

在约束条件

AX≤(≥，＝)bX≥0

下，求未知向量，使得

Z=CX→max(min)

其中

;二、线性规划的标准形式及方法;;（二）化为标准形式的方法;;三、线性规划的解及其性质;基本解与基本可行解

在线性规划问题中，将约束方程组的m×n阶矩阵A写成由n个列向量组成的分块矩阵;如果B是A中的一个阶的非奇异子阵，则称B为该线性规划问题的一个基。不失一般性，不妨设

则称为基向量，与基向量相对应的向量为基变量，而其余的变量

为非基变量。;如果是方程组的解,则就是方程

组的一个解，它称之为对应于基B的基本解，简称基解。

满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基，称为可行基。;;(二)线性规划解的性质;线性规划解的性质

①线性规划问题的可行解集（可行域）为凸集。

②可行解集S中的点X是顶点的充要条件是基本可行解。

③若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到。

因此线性规划的最优解只需从其可行解集??有限个顶点中去寻找。

;四、线性规划问题的求解方法——单纯形法;相应地，记

目标函数记为

则对应于基B的基本解为;;;;(二)单纯形法的计算步骤;第3步，选主元。在所有大于零的检验数中选取最大的一个b0s，对应的非基变量为xs，对应的列向量为

若

则确定brs为主元项。

第4步，在基B中调进Ps，换出Pjr，得到一个新的基

第5步，在单纯形表上进行初等行变换，使第s列向量变为单位向量，又得一张新的单纯形表。

第6步，转入上述第2步。;例1：用单纯形方法求解线性规划问题;具体步骤如下：

第1步，确定初始单纯形表5.1.1。;第5步，进行初等行变换，得B2下的新单纯形表;五、应用实例:农场种植计划模型;表5.1.4不同等级耕地种植不同作物的单产(单位:kg/hm2);对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。

根据题意，决策变量设置如表5.1.5所示,表中Xij表示在第j等级的耕地上种植第i种作物的面积。

3种作物的产量可以用表5.1.6表示。

;作物种类;根据题意，约束方程如下,耕地面积约束

最低收获量约束

非负约束;（1）追求最大总产量的目标函数为

调用Matlab软件系统优化工具箱中的linprog函数，进行求解运算，可以得到一个最优解（如表5.1.7所示）。在该方案下，最优值，即最大总产量为6892200kg。从表中可以看出，如果以追求总产量最大为种植计划目标，那么，玉米的种植面积在I、II、III等耕地上都占绝对优势。;表5.1.7追求总产量最大的计划方案（单位：hm2）;(2)追求最大总产值的目标函数为

进行求解运算，可以得到一个最优解（