资源描述：
《《线性规划》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性规划LinearProgramming§1对线性规划的回顾§2线性规划在工商管理中的应用§3线性规划问题的计算机求解§4内点算法简介§5案例分析§1对线性规划的回顾线性规划定义：求一组变量x1、x2、…、xn的值，使之满足关于这组变量的若干个线性等式或不等式的约束条件，而且使这组变量的一个线性函数取到极大值(或极小值)。这些变量称为决策变量，所要优化的函数称为目标函数，决策变量是取实数值的连续变量。这样的问题称为线性规划。线性规划模型的结构目标函数：max，minmaxz(minf)=∑cjxj约束条件：≥,=,≤∑aijxj≤(=,≥)bi(i=1,2,…m)变量
2、符号：≥0,unr,≤0xj≥0(j=1,2,…n)线性规划数学模型的标准形式（标准型）目标函数求最大值函数约束条件全为等式决策变量全为非负函数约束条件右端项全为非负§1对线性规划的回顾下述5种情况如何化为标准型？1.约束条件为不等式2.目标函数取最小值3.xj为自由变量4.资源系数bi<05.m≥n§1对线性规划的回顾非标准形式化为标准形式总结线性规划模型化为标准形式变量Xj≥0不变Xj≤0令Xj*=-Xj,则Xj*≥0Xj无约束令Xj*--Xj*’=Xj,则Xj*,Xj*’≥0约束条件右端项bi≥0不变bi<0约束式两端同乘以”-1”形式ai1x1+…+ainxn=bi不
3、变ai1x1+…+ainxn≤biai1x1+…+ainxn+xsi=biai1x1+…+ainxn≥biai1x1+…+ainxn-xri=bi目标函数maxz=c1x1+…+cnxn不变minz=c1x1+…+cnxn令z*=-z,化为求maxz*=-c1x1-…-cnxn§1对线性规划的回顾线性规划问题解的概念可行解：满足函数约束条件和非负约束条件的解最优解：使目标函数达到最大值的可行解基：设A是约束方程组的m×n阶系数矩阵，B是矩阵A中m×m阶非奇异子矩阵，称B是线性规划问题的一个基基向量：基B中每一个列向量Pj非基向量：A中其余列向量Pj（不在B中）基变量：与基向量
4、Pj对应的决策变量xj非基变量：与非基向量对应的决策变量基解基可行解：满足非负约束条件的基解可行基：对应于基可行解的基§1对线性规划的回顾1可行解与最优解：最优解一定是可行解，但可行解不一定是最优解。基解不一定是可行解，可行解也不一定是基解。2可行解与基解：3可行解与基可行解：基可行解一定是可行解，但可行解不一定是基可能解。基可行解一定是基解，但基解不一定是基可行解。4基本解与基可行解：非可行解可行解基可行解基本解§1对线性规划的回顾线性规划问题解的概念6问题：最优解与基可行解？最优解不一定是基可行解，基可行解也不一定是最优解。5最优解与基本解：最优解不一定是基解，基解也不一
5、定是最优解。为什么？§1对线性规划的回顾非可行解可行解基可行解基本解考虑无穷多最优解的情况。线性规划问题解的概念线性规划解的性质定理1线性规划的可行域R是一个凸集，且有有限个顶点。定理3若线性规划有最优解，则必存在一个基可行解是最优解。——线性规划问题的可行域是一个凸集。——线性规划的每一个基可行解对应可行域的一个顶点(基可行解与可行域顶点一一对应)。定理2X是线性规划可行域R顶点的充要条件是X是线性规划的基本可行解。§1对线性规划的回顾——若线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优，即此时一定存在某个顶点是最优解。定理4若线性规划在可行域的两个顶点上达到最优
6、，则在两个顶点的连线上也达到最优。——若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。——最优解不一定是基可行解，基可行解也不一定是最优解。单纯形法一、单纯形法的解题思路从某一基可行解开始，转化到另一个相邻的基可行解，并且使相应的目标函数值有改进。即从可行域的一个顶点沿约束边界转换到可行域的另一个相邻的且使目标函数值有改进的顶点，直到目标函数值到达最优时的顶点为止。二、单纯形法的含义单纯形法是一种迭代算法，首先找到一个初始基可行解，然后判断它是否为最优解，如果是就停止迭代，否则，按照一定的法则，再找到一个更好且与当前基可行解相邻的基可行解，再进行判断，直到找不到更好
7、的基可行解或判断问题无解为止。§1对线性规划的回顾三、单纯形法的解题步骤1、找出初始可行基，确定初始基可行解，建立初始单纯形表。c1…cmcm+1…cncBxBbx1…xmxm+1…xnc1x1b11…0a1,m+1…a1,nc2x2b20…0a2,m+1…a2,n………………………cmxmbm0…1am,m+1…am,n0…0…§1对线性规划的回顾单纯形法例：线性规划问题数学模型的某种标准形式§1对线性规划的回顾单纯形法(单纯形法的解题步骤)2、检验各非基变量xj（j=m+1，m+2，…，n）的检验数
