单纯形法（new）ppt课件.ppt

《单纯形法（new）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《运筹学》南华大学经济管理学院曾经莲运筹帷幄，决胜千里第一章线性规划11.1线性规划概述1.2线性规划问题及其数学模型1.3线性规划的图解法及其几何意义1.4线性规划单纯形法与单纯形表1.5单纯形法的矩阵描述1.6人造基下的单纯形法1.7线性规划典型例题及应用主要内容2线性规划是是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支。1947年丹捷格提出了一般线性规划问题求解的方法——单纯形法。1.1线性规划概述31.2线性规划问题及其数学模型例1【经典例题】:某企业在计划期内要安排生产甲、乙两种产品，已知

2、其生产利润及原材料的消耗量如表1-1。问应如何安排生产计划使该企业获得的利润最大？甲乙资源限量/吨原材料A/吨1230原材料B/吨3260原材料C/吨0224产品利润千元/吨4050表1-11.2.1问题提出4分析设x1，x2分别表示在计划期内产品甲、乙的产量。III汇总约束条件目标原材料A1230原材料B3260原材料C0224产量x1x2单位利润4050利润5建模该生产计划问题可用数学模型表示为：目标函数maxz＝40x1＋50x2约束条件x1＋2x2≤303x1＋2x2≤602x2≤24x1，x2≥06【例2】

3、某工地租赁甲、乙两种机械来安装A、B、C三种构件，这两种机械每天的安装能力见表1-2。工程任务要求安装250根A构件，300根B构件和700根C构件；又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁甲、乙机械各多少天，才能使总租赁费最少？构件机械ABC机械甲5810机械乙6620表1-2机械安装能力信息7ABC租赁费租赁时间总租赁费目标机械甲5810250x1250x1+350x2min机械乙6820350x2实际工作量5x1+6x28x1+8x210x1+20x2任务250300700分析设租

4、赁机械甲x1天，机械乙x2天。该生产计划问题可用数学模型表示为：目标函数约束条件8性质：线性规划是一个线性的条件极值问题，可分为两类：已知一定数量的人力、物力、财力等资源，如何安排使用它们使完成的任务（或创的价值、实现的利润等）最多。当一项任务确定后，如何统筹安排尽量做到以最小的人力、财力、物力等资源去完成。线性规划定义：对于求取一组变量Xj（j＝1，2，3…n)使得它满足线性约束条件的目标函数取得极值的一类最优化问题。9特征每个问题都用一组决策变量（x1，x2，…，xn）表示某一方案；这组决策变量的值就代表一个具体

5、方案。一般这些变量取值是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划的数学模型。10B111.2.2线性规划数学模型的一般形式目标函数:max（min）z＝c1x1+c2x2+…cnxn(1.1)约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2………………………

6、…………(1.2)am1x1+am2x2+…+amnxn≤(=,≥)bmx1,x2,…xn≥0(1.3)目标函数中cj为价值系数；称为约束条件中aij为技术系数,bi为限额系数；（1.3）也称为变量的非负约束条件。121.2.3线性规划问题的标准型式标准式中要求bi>013线性规划问题的几种表示形式14用向量表示为：15用矩阵表示为：16如何变换为标准型：目标函数的标准化：MinZ=CXMaxZ’=－CX(Z=－Z’)负右端系数的转换：当bi≤0时，两端同乘（－1）约束条件的标准化：对于“≤“型，则在不等式的左端加一

7、非负变量（松弛变量），对于“≥“型，则在不等式的左端减一非负变量（剩余变量）。决策变量的转换：当xj≤0时，令xj／＝－xj，则xj／≥0；如xj无符号限制，则令xj＝xj／－xj//，xj／，xj//≥017例3：将下述线性规划模型（例1）化为标准型18在各不等式中分别加上一个松弛变量，使不等式变为等式，便得到标准型。19minz＝－x1＋2x2－3x3x1＋x2＋x3≤7x1－x2＋x3≥2－3x1＋x2＋2x3＝5x1，x2≥0，x3为无约束例4：将下述线性规划问题化为标准型s.t.20解：根据题意用x4－x5

8、替换x3替换，其中x4，x5≥0在第一个约束不等式≤号的左端加入松弛变量x6在第二个约束不等式≥号的左端加入剩余变量x7令z′＝－z令，把求minz改为求maxz′。得标准型maxz′＝x1－2x2＋3（x4－x5）x1＋x2＋（x4－x5）＋x6＝7x1－x2＋（x4－x5）－x7＝2－3x1＋x2＋2（x4－x5）＝5x1，x2，x4，x5