第2章线性规划模型、图解法、标准型PPT优秀课件

1、1 第一章第一章 线性规划（线性规划（LinearProgramming ） 教学目的：教学目的：本章重点引入线性规划问题的模型、模型、 几何性质、单纯形解法几何性质、单纯形解法和线性规划的 对偶定理对偶定理。应理解和掌握线性规划的 几何性质和求解原理，能针对实际问 题，建立相应的线性规划模型。 重重 点点：线性规划问题的求解方法、解的基本性质以及对 偶原理。 难难 点点：线性规划的单纯形法求解思想、矩阵表述、对偶 理论以及灵敏度分析 2 1、生产组织与安排问题：、生产组织与安排问题： 某工厂计划生产甲、乙两种产品。所需的设备台 时及A、B两种原材料消耗，详见下表 该工厂每生产一件甲产品可获利

2、2元，每生产一件乙产品 可获利3元，问如何安排生产计划，可使利润最大？ 1 线性规划问题及其数学模型线性规划问题及其数学模型 3 解解：设x1，x2分别为甲、乙产品的数量，则有 约束条件 x1+ 2x28 4x116 4x212 x10，x20，称x1，x2为决策变量 目标函数 max z=2x1+3x2 2、营养问题：、营养问题： 某公司养动物以供出售。这些动物的生长对 饲料中的三种营养元素特别敏感，分别称为营养元 素A、B、C。已求出这些动物每天至少需要700克 营养元素A，30克营养元素B，而营养C恰好为200 克。现有五种饲料可供选择，各种饲料的营养元素 及价格如下表所示，为了避免多使

3、用某种元素，规 定混合饲料中各种饲料最高含量分别为50、60、50、 70、40千克，求满足动物需要且费用最低的饲料配 方。 4 表2 所用饲料、营养元素及单价 12345需求/克 A321618700 B10.50.220.530 C0.510.220.8200 价格/元27495 解 ： 如教材14页 5 3、人力资源分配问题：、人力资源分配问题： 班次时间所需人数 16-1060 210-1470 314-1860 418-2250 522-220 62-630 6 总结： 线性规划三要素： 决策变量、目标函数、 约束条件 线性规划的特点: 目标线性、约束条件为线性不等式或等式 一般情况

4、下，其值均是正的 定义：线性规划（LP）的一般模型为 目标函数： max(min) z=c1 x1+ c2 x2+ + cn xn 约束条件： a11 x1 + a12 x2+ + a1n xn=（、）b1 a21 x1 + a22 x2+ + a2n xn=（、）b2 am1 x1+ am2 x2+ + amn xn=（、）bm x10，x20，xn0 7 2.1 图解法图解法 图解法不是解线性规划的主要方法,只是用于说明线性规 划解的性质和特点。只能解两个变量问题。 （用图解法求解,线性规划不需要化成标准型） 图解法的步骤： 1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求

5、最优值 线性规划图解法线性规划图解法 线性规划解的几种可能情况 1、唯一最优解 2、无穷多最优解 3、无可行解 4、无有限最优解(无界解) 8 例1： max z=2x1+ 3x2 x1+ 2x28 4x1 16 4 x2 12 x1，x2 0 有唯一解有唯一解 x1 x2 可行域 (4,2) z=14 目标函数 等值线 画图步骤画图步骤： 1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值 9 有无穷多解有无穷多解 两个顶点处达到最优解两个顶点处达到最优解 x2 x1 例2 max z =x1+2x2 s.t x1+2x28 4x2 16 4x1 12 x1, x2 0

6、10 约束条件围不成区域 (又称矛盾方程) 无可行解 0, 1243 22 . 23max 21 21 21 21 xx xx xx t s xxz 例3： x1 x2 11 max z=4x1+3x2 - 3 x 1 + 2 x 2 6 s.t -x1+3x2 18 x1, x2 0 无有限最优解(无界解) x2 例4： -3x1+2x2=6 12 图解法得出线性规划问题解的几种情况 问题 : 围成无界区域就不能有唯一解吗? 解的几种情况约束条件图形特点方程特点 唯一解一般围成有限区域,最优值 只在一个顶点达到 无穷多解在围成的区域边界上,至少 有两个顶点处达到最优值 目标和某一约束 方程成

7、比例 无可行解(无 解) 围不成区域有矛盾方程 无界解(无解) 围成无界区域, 且无有限 最优值 缺少一必要条件 的方程 13 max z=2x1+x2 5 x 2 1 5 s.t 6x1+2x2 24 x1+x2 5 x1, x2 0 用图解法解下面线性规划问题 14 线性规划问题若有最优解,一定在其可行域的顶点达到 （1）有最优解(唯一最优解必在一个顶点达到;无穷多 最优解至少在两个顶点达到); （2）无解(可行域为空集或目标函数无有限极值) 15 线性规划问题模型的标准型：线性规划问题模型的标准型： 分量形式：分量形式：线性规划（LP）的标准型： 目标函数： max z=c1 x1+ c

8、2 x2+ + cn xn 约束条件： a11 x1 + a12 x2+ + a1n xn=b1 s.t a21 x1 + a22 x2+ + a2n xn=b2 a m1 x1 + am2 x2+ + amn xn=bm x10，x20，xn0 且bi0，若 bi0的数乘（2）式在分别与（1）相加和相 减，这样得到 (x1-1)P1+(x2-2)P2+(xm-m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b 31 引理引理2 2 若若K K是有界凸集是有界凸集, ,则任何一点则任何一点 XKXK可表示为可表示为K K的顶点的凸组合的顶点的凸组合. . 证明略。 必要性（

9、基可行解顶点，用反证法）： X不是可行域的顶点,故可在可行域内找到两个不同的点 x(1),x(2)，使得 X =x(1)+(1-)x(2), 0m时, 有X j =xj(1)=xj(2)=0,由于x(1),x(2)是可行域的两点.应满足 Pjxj(1)=b 与 Pjxj(2)=b 将这两式相减,即得 Pj(xj(1)-xj(2)=0 因x(1)x(2),所以上式系数(xj(1)-xj(2)不全为零,故向量 P1,P2,Pm组线性相关与假设矛盾.即X不是基可行解. 32 若可行域有界若可行域有界, ,线性规划问题的目标函数一定可以线性规划问题的目标函数一定可以 在其可行域的顶点上达到最优在其可行域的顶点上达到最优. . 证：证：设X(1),X(2), ,X(k)是可行域的顶点,若X(0)不是顶 点且目标函数在X(0)处达到最优 z*=CX(0)(不妨设标准型是 z*=maxz),则X(0)可以用顶点表示为 X(0)=iX(i) i0,i=1 记X(1),X(2), ,X(k)中使max CX(i)的顶点为X(m)。于是， 由假设CX(0)为最优解，所以CX(0)=CX(m)，即最优解可在顶点 X(m)达到。 k i k i mm