线性规划11课件.ppt

内容：线性规划的数学模型，标准形式，基本概念及基本原理；线性规划的图解法，单纯形法，大M法，两阶段法。 重点： （1）线性规划的基本概念 （2）单纯形法的基本原理与计算步骤 难点： （1）单纯形法的基本原理与计算步骤 基本要求： （1）理解线性规划的基本概念：目标函数、约束条件、可行解与可行域、基可行解、最优解及它们之间的关系；会写线性规划的标准形式。 （2）理解并掌握线性规划求解的基本理论：可行域，基本可行解与凸集顶点的关系，最优解。 （3）掌握线性规划的图解法：可行域、等值线移动方向、最优解的存在性情况。 （4）熟练掌握线性规划的单纯形法：单纯形法的基本原理、基本步骤、最优解的判定。 （5）熟练掌握大M法、两阶段法的原理和计算步骤。 （6）能利用线性规划的知识对一些实践问题，如：组织生产计划问题、节约下料问题等，建模求解； （7）能利用当前的计算机软件求解线性规划问题。 1-3 线性规划问题解的概念 对于标准型LP问题 最优解：若基本可行解又是最优解（也称基本最优解），这个基就称为最优基（optimal basis）。 图解法得到的启示 1.求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解和无可行解。 2.若线性规划问题的可行域存在，则可行域是一凸集。 3.若线性规划问题的最优解存在，则最优解一定在某个顶点可达到。 4.解题思路是：先找出凸集的任一顶点，计算Z值，比较相邻顶点Z值，如大，转到相邻顶点，一直到找出使Z值最大的顶点为止。 可行解：满足约束条件（1-13）和（1-14）的解称为可行解。 基：A中任何一组m个线性无关的列向量构成的子矩阵,称为该问题的一个基（basis）,与中的这些列向量对应的变量称为基变量（basic variable） 基本解：对于基,令非基变量为零,求得满足（1-13）的解，称为基对应的基本解（basic solution）。 基本可行解：满足（1-14）的基本解称为基本可行解（basic feasible solution）；基本可行解所对应的基称为可行基（feasible basis）。 1-4 线性规划问题的图解法： 　　　当决策变量个数n=2时，LP问题可以通过在平面上作图的方法求解，称为图解法。 　　　图解法求解的目的： 1.判别线性规划问题的求解结局。 2.在存在最优解的条件下，把问题的最优解找出来。 图解法的步骤： 1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为可行域； 2.绘制目标函数图形。先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形； 3.求最优解。依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。 一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动 x1 x2 O 10 20 30 40 10 20 30 40 (3,4) (15,10) 最优解X=(15,10) 最优值Z=85 例1.11 2 4 6 x1 x2 2 4 6 最优解X=(3,1) 最优值Z=5 (3,1) min Z=x1+2x2 例1.12 (1,2) 2 4 6 x1 x2 2 4 6 X（2）＝（3,1） X（1）＝（1,3） (5,5) min Z=5x1+5x2 例1.13 有无穷多个最优解 即具有多重解,通解为 0≤α≤1 当α=0.5时 Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 2 4 6 x1 x2 2 4 6 (1,2) 无界解(无最优解) max Z=x1+2x2 例1.14 x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解 即无最优解 max Z=10x1+4x2 例1.15 由以上例题可知，线性规划的解有4种形式： 1.有唯一最优解(例1.11例1.12) 2.有多重解(例1.13) 3.有无界解(例1.14):产生原因：是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件。 4.无可行解(例1.15):原因是模型本身错误，约束条件之间互相矛盾，应检查修正。 1、2情形为有最优解 3、4情形为无最优解 1.通过图解法了解线性规划有几种解的形式 2.作图的关键有三点 (1)可行解区域要画正确 (2)目标函数增加的方向不能画错 (3)目