线性规划[单纯形法](第2章).pptVIP

解可能出现的情况： 可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到（称为唯一最优解） 最优解存在且不唯一，且在可行域的两个顶点上同时达到，则两顶点连线上的点都是该问题的最优解（多重解或多重最优解） * OR课件 LP 统称为无解 上节课回顾 OR课件 LP 上节课回顾 局限性：仅能求解两个变量的LP问题 重要启示： （1）LP问题的最优解一定在可行域的顶点上达到； （2）可行域中顶点的转移实现了数学迭代，顶点的转移使得目标函数值上升或下降。 －－单纯形法的基本原理和基本思想 OR课件 LP 第 2 章 单纯形法 Simplex Method OR课件 LP 单 纯 形 法 LP问题的几何意义 单纯形法的经济解释 单纯形法的计算步骤 单纯形法的进一步讨论 LP问题解的讨论 OR课件 LP 几何意义 基本概念 1、凸集： 2、顶点：上式中?＝1或0时对应的点。 OR课件 LP 几何意义 基本定理 LP问题的可行域是凸集 可行解是基本可行解的充要条件 基本可行解对应可行域的顶点 有可行解必有基本可行解，即凸集有顶点 最优解在可行域的顶点上达到 OR课件 LP 经 济 解 释 例2.1 设有一家具厂用木材和钢材生产A,B,C三种家具，生产一件家具所需的材料、每件家具可获得的利润以及每月可供的木材自河钢材数量如下表，问此家具厂应如何安排各种家具的生产量才能使企业获得最大的利润？ 8000 3000 材料可供量 4 1 5 3 2 1 1 4 4 A B C 单位产品获利（元） 木材 钢材 产 品 解：设A,B,C三件家具的产量(件数)分别为x1,x2,x3，有： OR课件 LP 经 济 解 释 模型的标准型为： 系数矩阵和基： 则：基变量为x4, x5; x1, x2 x3 为非基变量，变换标准型的约束条件： 代入目标函数： Z = 0 + 4x1 + x2 + 5x3 令非基变量等于0，基变量x4=8000, x5=3000 初始基本可行解 OR课件 LP 经 济 解 释 观察目标函数： 选x3入基，x1, x2仍为非基变量，且为0，代入上方程组： 则：基变量为x4, x3; x1, x2 x5 为非基变量，变换标准型的约束条件： 代入目标函数： Z = 3750 + 1.5x1 －0.25x2 －1.25x5 令非基变量等于0，基变量x3=750, x4=5000 基本可行解 当x3=750时，x5=0即为非基变量，x4=5000 OR课件 LP 经 济 解 释 观察目标函数： 选x1入基，x2, x5仍为非基变量，且为0，代入上方程组： 则：基变量为x1, x4; x2, x3 x5 为非基变量，变换标准型的约束条件： 代入目标函数： Z = 6000 －x2 －3x3 －2x5 令非基变量等于0，基变量x1=1500, x4=3500 最优解 当x1=1500时，x3=0即为非基变量，x4=3500 OR课件 LP 经 济 解 释 例题小结：明确以下问题： 变量的经济意义 目标函数及其系数的经济意义 变量换入、换出时的经济意义 目的在于：引入单纯形法的计算过程。 OR课件 LP 计 算 步 骤 将LP问题化标准型，求出初始基本可行解，并列入单纯形表 是否最优？ 是否无解？ 最优解 Y N Y 无解 N 确定换入变量、换出变量，得到一个新的基本可行解 ？ ？ ？ ？ OR课件 LP 计 算 步 骤 例2.1 线性规划问题的标准型： 初始单纯形表： ？推导 初始解为X=(0,0,0,8000,3000) Z=0 OR课件 LP 计 算 步 骤 检验数表达式推导： 判别式： MaxZ: cj – zj ≤ 0 (对于所有的非基变量）问题达到最优； OR课件 LP 计 算 步 骤 换入变量的确定： 换出变量的确定： 系数矩阵的变换： 按照增广矩阵的变换规则，将基变量的系数矩阵转化为单位矩阵，非基矩阵和资源向量作相应的变化。 OR课件 LP 计 算 步 骤 ? 2000 750 K L 4 主元素 x4 x3 0 5 750 1/2 1/4 1 0 1/4 5000 1 0 0 1 -1 5/2 5/4 5 0 5/4 3/2 -1/4 0 0 -5/4 K K ? 5000 1500 L 1/2 OR课件 LP 计 算 步 骤 x4 x3