管理运筹学线性规划精选PPT.ppt

《管理运筹学线性规划精选PPT.ppt》由会员分享，可在线阅读，更多相关《管理运筹学线性规划精选PPT.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理运筹学线性规划第1 页，此课件共71 页哦第一讲 线性规划2第2 页，此课件共71 页哦第一章 线性规划的数学模型 线性规划 Linear Programming LP 规划论中的静态规划 解决有限资源的最佳分配问题 求解方法：图解法 单纯形解法 3第3 页，此课件共71 页哦第一章 线性规划的数学模型4第4 页，此课件共71 页哦第一节 线性规划一般模型一、线性规划问题的三个要素 决策变量 决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件 任 何 问 题 都 是 限 定 在 一 定 的 条 件 下 求 解，把 各 种 限 制 条 件 表 示 为 一 组 等式或不等式，称之

2、为约束条件。约束条件是决策方案可行的保障。LP 的约束条件，都是决策变量的线性函数。目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。5第5 页，此课件共71 页哦第一节 线性规划一般模型 例1.生产计划问题 某 厂 生 产、两 种 产 品，已 知 生 产 单 位 产 品 所 需 的 设 备 台 时 及A、B 两种原材料的消耗，以及资源的限制，相关数据如表所示：问如何安排、两产品的产量，使利润为最大。二、线性规划模型的构建 产品资源工时单耗 资源限制设备原料A原料B 1 1 2 1 0 1300 台时400 千克

3、250 千克单位产品获利 50 元 100 元6第6 页，此课件共71 页哦第一节 线性规划一般模型(1)决 策 变 量。要 决 策 的 问 题 是、两 种 产 品 的 产量，因 此 有 两 个 决 策 变 量：设x1为 产 品 产 量，x2为 产品产量。(2)约 束 条 件。生 产 这 两 种 产 品 受 到 现 有 生 产 能 力 的制约，原料用量也受限制。设备的生产能力总量为300 台时，则约束条件表述为 x1+x2 300 A、B 两种原材料 约束条件为2x1+x2 400 x2 250 建立模型7第7 页，此课件共71 页哦第一节 线性规划一般模型(3)目标函数。目标是利润最大化，用

4、Z 表示利润，则 maxZ=50 x1+100 x2(4)非 负 约 束。、产 品 的 产 量 不 应 是 负 数，否 则 没 有 实 际 意 义，这个要求表述为 x1 0，x2 0 综上所述，该问题的数学模型表示为 maxZ=50 x1+100 x2 x1+x2 300 2x1+x2 400 x2 250 x1 0,x2 0S.t.8第8 页，此课件共71 页哦第一节 线性规划一般模型 某 名 牌 饮 料 在 国 内 有 三 个 生 产 厂，分 布 在 城 市A1、A2、A3,其 一 级 承 销 商 有4 个，分 布 在 城 市B1、B2、B3、B4，已 知 各 厂 的 产 量、各 承 销

5、商 的 销 售 量 及 从Ai到Bj的每 吨 饮 料 运 费 为Cij，为 发 挥 集 团 优 势，公 司 要 统 一筹划运销问题，求运费最小的调运方案。例2.运输问题运输问题 销地产地B1 B2 B3 B4产量A1A2A3 6 3 2 5 7 5 8 4 3 2 9 7523销量 2 3 1 49第9 页，此课件共71 页哦第一节 线性规划一般模型(1)决策变量。设从Ai到Bj的运输量为xij，(2)目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)约束条件。产量之和等于销量之和

6、,故要满足：供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3 销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4 非负性约束 xij0(i=1,2,3；j=1,2,3,4)10第10 页，此课件共71 页哦第一节 线性规划一般模型 用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式 为：三、线性规划的一般模型 max(min)Z=c1x1

7、+c2x2+cnxn a11x1+a12x2+a1nxn(,)b1a21x1+a22x2+a2nxn(,)b2 am1x1+am2x2+amnxn(,)bmx1,x2,xn()011第11 页，此课件共71 页哦第二节 线性规划的图解法 图解法即是用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。一、图解法的基本步骤12第12 页，此课件共71 页哦第二节 线性规划的图解法1.可行域的确定 例1的数学模型为 maxZ=50 x1+100 x2 x1+x2 300 2x1+x2 400 x2 2

8、50 x1 0,x2 0 x2=2502x1+x2=400 x1x2100 200300100200300 五边形ABCDO 内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。400400 x1+x2=300ABCDOz=0=50 x1+100 x2 Z=27500=50 x1+100 x213第13 页，此课件共71 页哦第二节 线性规划的图解法2.最优解的确定 目标函数 Z=50 x1+100 x2 代表以Z 为参数的一族平行线。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使

9、目标函数最优(极大或极小)的解。最优值:取最优解时对应的目标函数值14第14 页，此课件共71 页哦第二节 线性规划的图解法 由 线 性 不 等 式 组 成 的 可 行 域 是 凸 集(凸 集 的 定 义 是：集合内部任意两点连线上的点都属于这个集合)。可 行 域 有 有 限 个 顶 点。设 规 划 问 题 有n 个 变 量，m 个约束，则顶点的个数不多于Cnm个。目 标 函 数 最 优 值 一 定 在 可 行 域 的 边 界 达 到，而 不 可 能在其内部。二、几点说明15第15 页，此课件共71 页哦第二节 线性规划的图解法三、解的可能性x1=82x2=123x1+4 x2=36x1x24

10、 8 123690 0A AB BC(4,6)C(4,6)D D例 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.Z=24Z=36Z=12 唯一最优解：只有一个最优点。多 重 最 优 解：无 穷 多 个 最 优 解。若 在 两 个 顶 点 同 时 得到最优解，则它们连线上的每一点都是最优解。16第16 页，此课件共71 页哦第二节 线性规划的图解法 无 界 解：线 性 规 划 问 题 的 可 行 域 无 界，使 目 标 函 数 无限增大而无界。（缺乏必要的约束条件）三、解的可能性（续）例如 maxZ=3x1+2 x2-2x1+x2 2 x

11、1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x11 2 3-1Z=6Z=12S.t.17第17 页，此课件共71 页哦第二节 线性规划的图解法 无可行解：若约束条件相互矛盾，则可行域为空集三、解的可能性（续）例如 maxZ=3x1+2 x2-2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x11 2 3-1S.t.18第18 页，此课件共71 页哦第三节 线性规划的标准型 线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化和极小化；约束条件有“”、“”和“”三种情况；决策变量一般有非负

12、性要求，有的则没有。为 了 求 解 方 便，特 规 定 一 种 线 性 规 划 的 标 准 形 式，非标准型可以转化为标准型。标准形式为：目标函数极大化，约束条件为等式，右端常数项bi0，决策变量非负。一、标准型19第19 页，此课件共71 页哦第三节 线性规划的标准型1.代数式二、标准型的表达方式 有代数式、矩阵式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ=cjxj aijxjbi(i=1,2,m)xj0(j=1,2,n)简记20第20 页，

13、此课件共71 页哦第三节 线性规划的标准型2.矩阵式 21第21 页，此课件共71 页哦第三节 线性规划的标准型 目标函数极小化问题 目标函数极小化问题 minZ=CTX，只需将等式两端乘以-1 即变为极大化问题。因为minZ=-max(-Z)=CTX，令Z=-Z，则maxZ=-CX 右端常数项非正 右端常数项非正 两端同乘以-1 约束条件为不等式 约束条件为不等式 当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式；当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。决策变量 决策变量x xk k没有非负性要求没有非负性要求 令xk=xk-x k，x

14、k=xk，x k 0，用xk、x k 取代模型中xk三、非标准型向标准型转化 22第22 页，此课件共71 页哦第三节 线性规划的标准型 例1 的标准型 例1 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.x1+x3=8 2x2+x4=12 3x1+4 x2+x5=36 x1,x2,x3,x4,x5 0 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 23第23 页，此课件共71 页哦 minZ=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36-x1-x2-x3-2 x1 0,x30 第三节 线性规划的

15、标准型 例 minZ=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6-x1-x2+x3-2 x1 0,x3 0 标准化1S.t.24第24 页，此课件共71 页哦第三节 线性规划的标准型 标准化2 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36-x1-(x2-x 2)-x3-2 x1,x2,x 2,x3 0 标准化3 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3 02

16、5第25 页，此课件共71 页哦第三节 线性规划的标准型 标准化4 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4 0 标准化5 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x3-x5=6 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4,x5 026第26 页，此课件共71 页哦第三节 线性规划的标准型 标准化6 minZ=x1+2(x2-x 2)+3 x3 x1+

17、2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x3-x5=6 x1+(x2-x 2)-x3+x6=2 x1,x2,x 2,x3,x4,x5,x6 0 标准化7 maxZ=-x1-2(x2-x 2)-3x3+0 x4+0 x5+0 x6 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x3-x5=6 x1+(x2-x 2)-x3+x6=2 x1,x2,x 2,x3,x4,x5,x6 0 27第27 页，此课件共71 页哦第四节 线性规划解的概念 可行解：满足约束条件AX=b,X0 的解。最优解：使目标函数最优的可行解，称为最优解。基 m n，且m 个方程线

18、性无关，即矩阵A 的秩为m；根据线性代数定理可知，n m，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。一、线性规划解的概念 28第28 页，此课件共71 页哦第四节 线性规划解的概念 线性方程组的增广矩阵 例1 的标准型 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+2x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 0 x1x2x3x4x5单位矩阵 单位矩阵29第29 页，此课件共71 页哦第四节 线性规划解的概念 基矩阵：系数矩阵A 中任意m 列所组成的m 阶非奇异子矩阵，称为该线性规划问题的一个基矩阵

19、。或称为一个基，用B 表示。称基矩阵的列为基向量，用Pj表示(j=1,2,m)。不在B 中的向量称为非基向量的基矩阵B 最多为C53=10 个P1 P2 P3 P4 P530第30 页，此课件共71 页哦第四节 线性规划解的概念 基变量：与基向量Pj相对应的m 个变量xj称为基变量，其余的m-n 个变量为非基变量。基解：令所有非基变量等于零，对m 个基变量所求的解，对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。x3x4x5 基变量是x3,x4,x5 非基变量是x1,x2 令非基变量x1=x2=0，得到一个基解 x3=300

20、，x4=400，x5=25031第31 页，此课件共71 页哦第四节 线性规划解的概念 基可行解：满足非负性约束的基解称为基可行解。可行基：对应于基可行解的基，称为可行基。最优基：最优解对应的基矩阵，称为最优基。非可行解可行解基解基可行解32第32 页，此课件共71 页哦第四节 线性规划解的概念 定理 定理1 1.若线性规划问题存在可行域，则其可行域一定是凸集。定理 定理2 2.线性规划问题的基可行解对应可行域的顶点。定定理理3 3.若 可 行 域 有 界，线 性 规 划 的 目 标 函 数 一 定 可 以 在 可 行 域 的顶点上达到最优。二、线性规划的基本定理 线 性 规 划 问 题 可

21、以 有 无 数 个 可 行 解，最 优 解 只 可 能 在 顶 点 上 达 到，而 有限 个 顶 点 对 应 的 是 基 可 行 解，故 只 要 在 有 限 个 基 可 行 解 中 寻 求 最 优 解 即可。从 一 个 顶 点 出 发 找 到 一 个 可 行 基，得 到 一 组 基 可 行 解，拿 目 标 函 数 做 尺度衡量一下看是否最优。如 若 不 是，则 向 邻 近 的 顶 点 转 移，换 一 个 基 再 行 求 解、检 验，如 此 迭 代循环目标值逐步改善，直至求得最优解。三、线性规划的解题思路 33第33 页，此课件共71 页哦第二章 线性规划单纯形法 单纯形法(Simplex Me

22、thod)是美国人丹捷格(G.Dantzig)1947 年创建的 这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法 表格法 矩阵法34第34 页，此课件共71 页哦第二章 线性规划单纯形法35第35 页，此课件共71 页哦第一节 单纯形法原理一、代数解法 x1x2x3x4x5x3x4x5非奇异子阵，做为一个基基变量x3,x4,x5非基变量x1,x2 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 036第36 页，此课件共71 页

23、哦第一节 单纯形法原理 将基变量用非基变量线性表示，即x3=300-x1-x2 x4=400-2x1-x2 x5=250-x2 令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=300，x4=400，x5=250即X0=(0,0,300,400,250)T 一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0。1.求初始基可行解 37第37 页，此课件共71 页哦第一节 单纯形法原理 确定入基变量 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250 从目标函数m

24、axZ=50 x1+100 x2+0 x3+0 x4+0 x5可知：非 基 变 量x1和x2的 系 数 均 为 正 数，生 产 哪 种 产 品 都 会 增加利润。因 为x2的 系 数 大 于x1的 系 数，即 生 产 单 位 乙 产 品 比 甲 产品 利 润 更 高 一 些，故 应 优 先 多 生 产 乙 产 品，即 优 先 把x2作为入基变量。2.第一次迭代 38第38 页，此课件共71 页哦第一节 单纯形法原理 确定离基变量 基变量用非基变量线性表示x3=300-x1-x2 x4=400-2x1-x2 x5=250-x2 保持原非基变量x1=0，x2变成基变量时应保证 x3,x4,x5非负

25、，即有2.第一次迭代（续）x3=300-x2 0 x4=400-x2 0 x5=250-x2 0 x2 300 x2 400 x2 250 则离基变量为x539第39 页，此课件共71 页哦第一节 单纯形法原理2.第一次迭代（续）主行主列主元 进基变量所在列为主列，离基变量所在行为主行 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250 40第40 页，此课件共71 页哦第一节 单纯形法原理 基变换 进行初等变换，变主元为1，主列为单位列向量。2.第一次迭代（续）-Z+50 x1+100 x2+0 x3+

26、0 x4+0 x5=0 x1+x2+x3=300 2 x1+x2+x4=400 x2+x5=250-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1+x3-x5=50 2 x1+x4-x5=150 x2+x5=250此时x2，x3，x4为基变量初等行变换41第41 页，此课件共71 页哦第一节 单纯形法原理2.第一次迭代（续）将基变量用非基变量线性表示，即x2=250-x5 x3=50 x1+x5x4=150-2x1+x5 令非基变量x1=0，x5=0，找到另一个基可行解 x1=0，x2=250，x3=50，x4=150，x5=0即X1=(0,250,50,15

27、0,0)T 目标函数Z=2500042第42 页，此课件共71 页哦第一节 单纯形法原理 确定入基变量3.第二次迭代 目标函数，Z=50 x1+0 x2+0 x3+0 x4-100 x5+25000 非基变量x1的系数 1=50（检验数）为正数，确定x1为入基变量。-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1+x3-x5=50 2 x1+x4-x5=150 x2+x5=250第一次迭代结果43第43 页，此课件共71 页哦第一节 单纯形法原理 确定出基变量3.第二次迭代（续）x3=50+x5-x1 0 x2=150-2x1+x5 0 x4=250 x5 0

28、 x1 50 x1 75基变量用非基变量线性表示 x1=50+x5-x1 x2=150-2x1+x5 x4=250 x5 保持原非基变量x5=0，x1变成基变量时应保证 x2,x3,x5非负，即 对应的x3定为出基变量44第44 页，此课件共71 页哦第一节 单纯形法原理 基变换 变主元为1，主列为单位列向量。3.第二次迭代（续）-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1+x3-x5=50 2 x1+x4-x5=150 x2+x5=250-Z+0 x1+0 x2-50 x3+0 x4-50 x5+27500=0 x1+x3-x5=50-2x3+x4+x5

29、=50 x2+x5=250基变量为x1 x2，x4 45第45 页，此课件共71 页哦第一节 单纯形法原理3.第二次迭代（续）将基变量用非基变量线性表示，即x1=50 x3+x5x2=250-x5x4=50+2x3-x5 令非基变量x3=0，x5=0，又找到一个基可行解 目标函数-Z+0 x1+0 x2-50 x3+0 x4-50 x5+27500=0 x1=50，x2=250，x3=0，x4=50，x5=0即 X2=(50,250,0,50,0)T Z=27500 检验数j非正，得最优解X*=(4,6,4,0,0)T，Z*=4246第46 页，此课件共71 页哦第一节 单纯形法原理二、单纯形

30、法的几何意义X0=(0,0,300,400,250)TX1=(0,250，50，150,0)TX1=(50,250,0,50,0)Tx2=2502x1+x2=400 x1x2100 200 300100200300400400 x1+x2=300ABCDO47第47 页，此课件共71 页哦第二节 表格单纯形法 表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。一、单纯形法表CjC1C2CjCn 比值 CBXBbx1x2xjxnCB1xB1b1a1 1a12 a1j a1n1CB2xB2b2a21a22 a2j a2n2CBnxBnbmam1am2 amj amnm检验数j-

31、Z 12 j n48第48 页，此课件共71 页哦第二节 表格单纯形法 将线性规划问题化成标准型。找出或构造一个m 阶单位矩阵作为初始可行基，建立初始单纯形表。计 算 各 非 基 变 量xj的 检 验 数 j=Cj-CBPj，若 所 有 j0，则 问 题 已 得 到 最 优 解，停止计算，否则转入下步。在 大 于0 的 检 验 数 中，若 某 个 k所 对 应 的 系 数 列 向 量Pk0，则 此 问 题 是 无 界解，停止计算，否则转入下步。根 据max j j0=k原 则，确 定xk为 换 入 变 量(进 基 变 量)，再 按 规 则 计 算：=minbi/aik|aik0=bl/aik

32、确 定xBl为 换 出 变 量。建 立 新 的 单 纯 形 表，此 时基变量中xk取代了xBl的位置。以aik为 主 元 素 进 行 迭 代，把xk所 对 应 的 列 向 量 变 为 单 位 列 向 量，即aik变 为1，同列中其它元素为0，转第 步。二、单纯形法的计算步骤 49第49 页，此课件共71 页哦第二节 表格单纯形法 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1+x3=8 2x2+x4=12 3x1+4 x2+x5=36 三、单纯形法计算举例Cj 比值CBXBb检验数jx1x2x3x4x53 5 0 0 08 1 0 1 0 012 0 2 0 1 036 3

33、 4 0 0 1x3x4x50000 3 5 0 0 0-12/2=636/4=950第50 页，此课件共71 页哦第二节 表格单纯形法检验数j8 1 0 1 0 06 0 1 0 1/2 012 3 0 0-2 1x3x2x5050-30 3 0 0-5/2 08-4Cj 比值CBXBb检验数jx1x2x3x4x53 5 0 0 08 1 0 1 0 012 0 2 0 1 036 3 4 0 0 1x3x4x50000 3 5 0 0 0-12/2=636/4=951第51 页，此课件共71 页哦第二节 表格单纯形法Cj 比值CBXBb检验数jx1x2x3x4x53 5 0 0 08 1

34、0 1 0 06 0 1 0 1/2 012 3 0 0-2 1x3x2x5050-30 3 0 0-5/2 08-4检验数j4 0 0 1 2/3-1/36 0 1 0 1/2 04 1 0 0-2/3 1/3x3x2x1053-42 0 0 0-1/2-1最优解:X*=(4,6,4,0,0)T，Z*=4252第52 页，此课件共71 页哦第二节 表格单纯形法 最优基 Cj3 5 0 0 0比值CBXBbx1x2x3x4x50 x34 0 0 1 2/3-1/35 x26 0 1 0 1/2 03 x14 1 0 0-2/3 1/3检验数j-42 0 0 0-1/2-1x3x2x1 最优基的

35、逆 最优基和最优基的逆53第53 页，此课件共71 页哦第二节 表格单纯形法 例如maxZ=3x1+2 x2-2x1+x2 2 x1-3 x2 3 x1,x2 0S.t.标准化 maxZ=3x1+2 x2-2x1+x2+x3=2 x1-3 x2+x4=3 x1,x2,x3,x4 0Cj 比值CBXBb检验数jx1x2x3x43 2 0 02-2 1 1 03 1-3 0 1x3x4000 3 2 0 0-3检验数j8 0-5 1 2x3x103-3 1-3 0 1-9 0 11 0-3 此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界 值不存在，有

36、进基变量但无离基变量。54第54 页，此课件共71 页哦第三节 人工变量问题 用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。一、人工变量 采用人造基的办法：人工构造单位矩阵 人工构造单位矩阵 在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0 时，约束条件才是它本来的意义。处理方法有两种：大M 法 两阶段法55第55 页，此课件共71 页哦第三节 人工变量问题 没有单位矩阵，不符合构造初始基的条件，需加入人工变量

37、。人工变量最终必须等于0 才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M 为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。大M 法 例如 maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1-2 x2+x3=4 x1,x2,x3 0S.t.56第56 页，此课件共71 页哦第三节 人工变量问题 按大M 法构造人造基，引入人工变量x4,x5 的辅助问题如下：maxZ=3x1-x2-2 x3-M x4

38、-M x5 3x1+2 x2-3 x3+x4=6 x1-2 x2+x3+x5=4 x1,x2,x3,x4,x5 0Cj 比值CBXBb检验数jx1x2x3x4x53-1-2-M-M6 3 2-3 1 04 1-2 1 0 1-10M 3+4M-1-2-2M 0 0 x4x5-M-M2457第57 页，此课件共71 页哦第三节 人工变量问题Cj 比值CBXBb检验数jx1x2x3x4x53-1-2-M-M6 3 2-3 1 04 1-2 1 0 13+4M-1-2-2M 0 0 x4x5-M-M24检验数j2 1 2/3-1 1/3 02 0-8/3 2-1/3 10-3-8M/31+2M-1-

39、4M/30 x1x53-M-1检验数j3 1-2/3 0 1/6 1/21 0-4/3 1-1/6 1/20-5/30-M-5/6-M-1/2x1x33-258第58 页，此课件共71 页哦第四节 单纯形法补遗 进基变量相持：单纯形法运算过程中，同时出现多个相同的 j最大。在 符 合 要 求 的 j(目 标 为max：j0，min：j0)中，选 取 下 标 最 小 的 非 基 变 量 为换入变量；离基变量相持：单纯形法运算过程中，同时出现多个相同的最小 值。继续迭代，便有基变量为0，称这种情况为 退化解 退化解。选取其中下标最大的基变量做为换出变量。多重最优解：最优单纯形表中，存在非基变量的检

40、验数 j=0。让这个 非基变量进基，继续迭代，得另一个最优解。无界解：大于0 的检验数中，若某个 k所对应的系数列向量Pk0，则解无界。无可行解：最终表中存在人工变量是基变量。59第59 页，此课件共71 页哦第三章 对偶理论 若 例1 中 该 厂 的 产 品 平 销，现 有 另 一 企 业 想 租 赁 其 设备。厂 方 为 了 在 谈 判 时 心 中 有 数，需 掌 握 设 备 台 时 费用 的 最 低 价 码，以 便 衡 量 对 方 出 价，对 出 租 与 否 做 出抉择。在 这 个 问 题 上 厂 长 面 临 着 两 种 选 择：自 行 生 产 或 出 租设备。首先要弄清两个问题：合理安

41、排生产能取得多大利润?为保持利润水平不降低，资源转让的最低价格是多少？问题 的最优解：x1=4，x2=6，Z*=42。一、对偶问题 60第60 页，此课件共71 页哦第三章 对偶理论 第二个问题：出让定价 假设出让A、B、C 设备所得利润分别为y1、y2、y3 原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 y1+0y2+3y3 3 同理，对乙产品而言，则有 0y1+2y2+4y3 5 设备台时出让的收益（希望出让的收益最少值）min=8y1+12y2+36y3 显然还有 y1，y2，y3061第61 页，此课件共71 页哦第三章 对偶理论 对偶问

42、题的最优解：y1=0，y2=1/2，y3=1，W*=42 两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。例1的对偶问题的数学模型 min=8y1+12y2+36y3 y1+0y2+3y3 3 0y1+2y2+4y3 5 y1，y2，y30 S.t.maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1,x2 0S.t.62第62 页，此课件共71 页哦第三章 对偶理论 这说明yi是右端项bi每增加一个

43、单位对目标函数Z 的贡献。对偶变量 yi在经济上表示原问题第i 种资源的 边际价值 边际价值。对偶变量的值 yi*所表示的第i 种资源的边际价值，称为 影子价值 影子价值。若原问题的价值系数Cj表示单位产值，则yi 称为 影子价格 影子价格。若原问题的价值系数Cj表示单位利润，则yi 称为 影子利润 影子利润。二、对偶问题的经济解释 63第63 页，此课件共71 页哦第三章 对偶理论 影 子 价 格 不 是 资 源 的 实 际 价 格，而 是 资 源 配 置 结 构 的 反 映，是 在 其 它 数据 相 对 稳 定 的 条 件 下 某 种 资 源 增 加 一 个 单 位 导 致 的 目 标 函

44、 数 值 的 增 量 变化。对资源i 总存量的评估：购进购进 or 出让 出让 对资源i 当前分配量的评估：增加 增加 or 减少 减少它 表 明 了 当 前 的 资 源 配 置 状 况，告 诉 经 营 者 应 当 优 先 增 加 何 种 资源，才能获利更多。告诉经营者以怎样的代价去取得紧缺资源。提示设备出租或原材料转让的基价。告诉经营者补给紧缺资源的数量，不要盲目大量补给。借助影子价格进行内部核算。特别注意 64第64 页，此课件共71 页哦第四章 灵敏度分析 线 性 规 划 研 究 的 是 一 定 条 件 下 的 最 优 化 问 题，采 用 优 化 方 案 可 以 达到 节 约 资 源、提

45、 高 效 益 的 目 的，但 是 对“优 化 方 案”必 须 要 有 全 面的认识，不可机械地对待。优 化 方 案 是 建 立 在 特 定 的 资 源 环 境 和 技 术 条 件 之 上 的，而 环 境 和 条件 总 是 处 在 不 断 地 变 化 之 中，如 产 品 价 格、原 材 料 成 本、加 工 技 术水 平、资 源 消 耗 系 数 等 时 有 波 动，所 以 优 化 方 案 是 个 相 对 稳 定 的 概念。当基础数据发生变化时，最优方案也就变了。基 础 数 据 往 往 是 测 算 估 计 的 数 值，虽 然 在 运 算 过 程 中 要 求 十 分 严 格，但 基 础 数 据 的 误

46、 差 是 不 可 避 免 的。为 了 对 优 化 结 果 有 更 全 面 的 了 解 和恰当的运用，就需要进行灵敏度分析。灵敏度分析的意义 65第65 页，此课件共71 页哦第四章 灵敏度分析 灵敏度分析又称敏感性分析或优化后分析，它研究基础数据发生波动后对最优解的影响，以及在多大的范围内波动才不影响最优基。灵敏度分析就是研究最优解对数据变化的敏感程度。感性太强，则说明最优解的稳定性程度较低。灵敏度分析解决的问题：参数在什么范围变化而最优基不变。已知参数的变化范围，考察最优解(最优基)是否改变。灵敏度分析的概念 66第66 页，此课件共71 页哦第四章 灵敏度分析 价值系数Cj变化影响检验数

47、参数Cj的变化范围 67第67 页，此课件共71 页哦第四章 灵敏度分析 非基变量Cj的变化范围 非基变量Cj变化，只影响它自己的检验数Cj3 5 0 0 0比值CBXBbx1x2x3x4x50 x34 0 0 1 2/3-1/35 x26 0 1 0 1/2 03 x14 1 0 0-2/3 1/3检验数j0 0 0-1/2-168第68 页，此课件共71 页哦第四章 灵敏度分析 基变量CBl的变化范围CjC15 0 0 0比值CBXBbx1x2x3x4x50 x34 0 0 1 2/3-1/35 x26 0 1 0 1/2 0C1x14 1 0 0-2/3 1/3检验数j0 0 0-2C1/3+5/2-C1/369第69 页，此课件共71 页哦第四章 灵敏度分析 例如 参数bi的变化范围 70第70 页，此课件共71 页哦第四章 灵敏度分析71第71 页，此课件共71 页哦