《《运筹学教学资料》运筹学第1章第3-4节.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第1章第3-4节.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-1-China University of Mining and Technology运筹学 第一章第一章 线性规划线性规划1 线性规划问题及其模型线性规划问题及其模型2 线性规划问题几何意义线性规划问题几何意义3 单纯形法单纯形法4 单纯形法计算步骤单纯形法计算步骤5 单纯形法进一步讨论单纯形法进一步讨论6 应用举例应用举例-2-China University of Mining and Technology运筹学 本节学习要点：本节学习要点：1、重点掌握单纯形的变换过程及基本思路；、重点掌握单纯形的变换过程及基本思路；2、了解单纯形解的判别。、了解单纯形解的判别。-3-China Un
2、iversity of Mining and Technology运筹学 先找出一个基可行解，判断其是否为最优解；先找出一个基可行解，判断其是否为最优解；如为否，则转换到相邻的基可行解，并使目标函数值如为否，则转换到相邻的基可行解，并使目标函数值不断增大；不断增大；一直找到最优解为止。一直找到最优解为止。定义：定义：两个基可行解称为两个基可行解称为相邻相邻的，如果它们之间变换且的，如果它们之间变换且仅变换仅变换一个一个基变量。基变量。单纯形法迭代的单纯形法迭代的基本思路基本思路是：是：3 单单 纯纯 形形 法法-4-China University of Mining and Technolo
3、gy运筹学 单纯形法是一单纯形法是一种迭代的算法，它种迭代的算法，它的思想是在可行域的思想是在可行域的顶点的顶点基本可基本可行解中寻优。由于行解中寻优。由于顶点是有限个顶点是有限个,因因此，算法经有限步此，算法经有限步可终止。可终止。单纯形法的步骤单纯形法的步骤确定初始基本可行解确定初始基本可行解检验其是否最优？检验其是否最优？寻找更好的基本可行解寻找更好的基本可行解是是否否方法前提：模型化为标准型方法前提：模型化为标准型3 单单 纯纯 形形 法法-5-China University of Mining and Technology运筹学 3.1 引例：引例：例：例：3 单单 纯纯 形形 法
4、法-6-China University of Mining and Technology运筹学 为基变量为基变量没有安排生产没有安排生产1、2两种产品，资源没有利用，所以利润为零。两种产品，资源没有利用，所以利润为零。即这个基可行解不是极点。即这个基可行解不是极点。分析：如果将非基变量转变成基变量，目标函数就可能增大。分析：如果将非基变量转变成基变量，目标函数就可能增大。如果目标函数中还有正系数的非基变量存在，则说明目标如果目标函数中还有正系数的非基变量存在，则说明目标函数还有增大的可能。函数还有增大的可能。3 单单 纯纯 形形 法法-7-China University of Mining
5、 and Technology运筹学 将正系数最大的那个非基变量换入（即该变量将正系数最大的那个非基变量换入（即该变量0）,以获得该以获得该产品的最大产量和对应的最大利润。产品的最大产量和对应的最大利润。即即x2=6时可以使约束条件不被破坏。而此时时可以使约束条件不被破坏。而此时x5=0，不再适合做基变量，所以将其用不再适合做基变量，所以将其用x2换出，因此得到：换出，因此得到：3 单单 纯纯 形形 法法-8-China University of Mining and Technology运筹学 同理：同理：3 单单 纯纯 形形 法法-9-China University of Mining
6、 and Technology运筹学 此时的目标函数为：此时的目标函数为：函数中的函数中的x1，仍然没有利用，其系数仍然为正数，说明目标，仍然没有利用，其系数仍然为正数，说明目标还有增长的余地，该基可行解仍不是最优解，下一步将还有增长的余地，该基可行解仍不是最优解，下一步将x1换换入基变量中。入基变量中。即即x1=2时可以使约束条件不被破坏。而此时时可以使约束条件不被破坏。而此时x3=0，不再适合做基变量，所以将其用不再适合做基变量，所以将其用x1换出，因此得到：换出，因此得到：3 单单 纯纯 形形 法法-10-China University of Mining and Technology
7、运筹学 3 单单 纯纯 形形 法法-12-China University of Mining and Technology运筹学 给给定一个初始基可行解定一个初始基可行解 ,对线性规划问题对线性规划问题则基可行解可写成则基可行解可写成对应的对应的 A=(B,N)，3.2 解的判别定理解的判别定理3 单单 纯纯 形形 法法-13-China University of Mining and Technology运筹学 max称为基称为基 所对应的所对应的典式典式。3 单单 纯纯 形形 法法-15-China University of Mining and Technology运筹学 线性规划
8、线性规划典式典式(proper(proper form)form)的分量表示：的分量表示：称称 是非基变量是非基变量 的的检验数检验数。重要！重要！重要！重要！max3 单单 纯纯 形形 法法-16-China University of Mining and Technology运筹学 1）基可行解）基可行解注：注：给出基给出基 后后,由其典式可得出结论由其典式可得出结论2）其对应目标函数值）其对应目标函数值z0=CBB-1b（针对非基变量）（针对非基变量）3）检验数）检验数利用这组数来判断利用这组数来判断X0是否是最优解。是否是最优解。3 单单 纯纯 形形 法法-17-China Univ
9、ersity of Mining and Technology运筹学 定理定理定理定理1 1 最最最最优优优优解判定准解判定准解判定准解判定准则则则则 如果对一切如果对一切 则则 X 0是线性是线性规划问题的规划问题的最优解最优解。如果对一切如果对一切 则则 X 0是线性规是线性规划问题的划问题的唯一最优解唯一最优解。如果对一切如果对一切 并且存在某个并且存在某个 则线性规划问题有则线性规划问题有无穷多最优解无穷多最优解。如果存在一个如果存在一个 并且对一切并且对一切则线性规划问题则线性规划问题无最优解无最优解(也称也称无界解无界解，即最优值为无穷，即最优值为无穷)。设设 X 0 是基可行解，
10、则：是基可行解，则：3 单单 纯纯 形形 法法-18-China University of Mining and Technology运筹学 定理定理2 （基可行解改进定理）（基可行解改进定理）证明证明 略。略。设设X0是基可行解，典式如前所示，如果是基可行解，典式如前所示，如果 存在一个存在一个 ；中至少有一个正分量；中至少有一个正分量；所有的所有的 ;则一定存在另一个基可行解则一定存在另一个基可行解X1,使使3 单单 纯纯 形形 法法-19-China University of Mining and Technology运筹学 第一章第一章 线性规划线性规划1 线性规划问题及其模型线性
11、规划问题及其模型2 线性规划问题几何意义线性规划问题几何意义3 单纯形法单纯形法4 单纯形法计算步骤单纯形法计算步骤5 单纯形法进一步讨论单纯形法进一步讨论6 应用举例应用举例-20-China University of Mining and Technology运筹学 1947年，提出求解线性规划的单纯形法。年，提出求解线性规划的单纯形法。单纯形算法的直接思想：单纯形算法的直接思想：从一个基可行解开始，通过基变换，到另一个基可行解，从一个基可行解开始，通过基变换，到另一个基可行解，逐步达到最优解的过程。基变换是通过迭代法实现的。逐步达到最优解的过程。基变换是通过迭代法实现的。4.1 单纯形
12、算法计算步骤单纯形算法计算步骤-22-China University of Mining and Technology运筹学 找初始基可行解找初始基可行解X0及可行基及可行基B单单单单纯纯纯纯形形形形法法法法计计计计算算算算框框框框图图图图 j 0?写出最优解写出最优解与最优值与最优值停停是否有是否有 ik0无界解无界解N确定换出变量确定换出变量x l ,以以 kl为主元作基变换为主元作基变换停停NYY确定换入变量确定换入变量x k k=max j|j 04.1 单单纯纯形形算算法法计计算算步步骤骤-26-China University of Mining and Technology运筹
13、学 例例1.利用单纯形算法求解下面的线性规划问题。利用单纯形算法求解下面的线性规划问题。4.1 单单纯纯形形算算法法计计算算步步骤骤-27-China University of Mining and Technology运筹学 解：本问题有一个明显的可行解：本问题有一个明显的可行基基x3、x4、x5，它的典式为：，它的典式为：非基变量非基变量x1、x2的检验数为的检验数为3、5，基可行解，基可行解X0=(0,0,4,12,18)T不是最优解，取检验数最大者，不是最优解，取检验数最大者，x2作为换入变量作为换入变量再确定换出变量，由于：再确定换出变量，由于：-28-China Universi
14、ty of Mining and Technology运筹学 故故x4为换出变量，得到一个新可为换出变量，得到一个新可行基行基x3,x2,x5，其典式为其典式为由于由于x1的检验数为的检验数为30，故基可行解，故基可行解X1=(0,6,4,0,6)T不是最优解，不是最优解，让让x1为换入变量。为换入变量。令令-29-China University of Mining and Technology运筹学 所以所以 x5 为换出变量，又得一个新基为换出变量，又得一个新基x3,x2,x1非基变量非基变量x4、x5的检验数是的检验数是-3/2、-1，故，故X2=(2,6,2,0,0)T是最优解，是最
15、优解，并且是唯一最优解。并且是唯一最优解。，其典式为：，其典式为：-30-China University of Mining and Technology运筹学 0 2 4 xY 6 4 2 0QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)基可行解与图解法顶点的对应关系基可行解与图解法顶点的对应关系图示：图示：X0=(0,0,4,12,18)TX1=(0,6,4,0,6)TX2=(2,6,2,0,0)T4.1 单单纯纯形形算算法法计计算算步步骤骤-31-China University of Mining and Technology运筹学 4.2 4.2 单纯形表
16、单纯形表单纯形表单纯形表单纯形表单纯形表(simple tableau)是为单纯形算法而设计的一种是为单纯形算法而设计的一种计算表，其功能类似于方程组的增广矩阵，易于进行基计算表，其功能类似于方程组的增广矩阵，易于进行基变换运算。变换运算。-32-China University of Mining and Technology运筹学 设可行基设可行基 的典式为：的典式为：将式将式(1.4)与与(1.5)组成一个组成一个m+1个方程、个方程、n+1个变量的方程组个变量的方程组为为4.2 单单 纯纯 形形 表表-33-China University of Mining and Technolo
17、gy运筹学 此方程组的增广矩阵为：此方程组的增广矩阵为：其中基变量其中基变量 的系数构成单位矩阵，的系数构成单位矩阵，z是是 一个不参一个不参与基变换的变量。与基变换的变量。可设计可设计单纯形表单纯形表-34-China University of Mining and Technology运筹学 表表4-1单纯形表单纯形表基变量的价值系数基变量基矩阵非基变量检验数负目标函数-35-China University of Mining and Technology运筹学 231000CBXBbx1x2x3x4X5x60X4151311000X51823-10100X631-11001j0231
18、000例例1建立建立单纯单纯形表形表-36-China University of Mining and Technology运筹学 231000CBXBbx1x2x3x4X5x60X41513110050X51823-101060X631-11001-j02310003X251/311/31/300150X5310-2-11030X684/304/31/3016-15100-100-37-China University of Mining and Technology运筹学-15100-1000X240112/3-1/3041X1310-2-110-0X640045/3-4/311j-18
19、0020-100X230101/40-1/40X15100-1/61/31/22X310015/12-1/31/4j-20000-5/6-1/3-1/2-38-China University of Mining and Technology运筹学 注注2：min问题问题如果给定的线性规划问题是要求目标函数达到最小，如果给定的线性规划问题是要求目标函数达到最小，可以直接用单纯形计算，而不必先化成标准形中要求可以直接用单纯形计算，而不必先化成标准形中要求目标函数的极大值。目标函数的极大值。此时，要求检验数此时，要求检验数 时，基可行解才是最优解；时，基可行解才是最优解；迭代时，选负检验数最小者作
20、为换入变量。迭代时，选负检验数最小者作为换入变量。注注1：上面的计算过程也可以用基变换公式来实现。上面的计算过程也可以用基变换公式来实现。单纯形算法特别适合计算机实现。单纯形算法特别适合计算机实现。思考题：编程实现单纯形算法。思考题：编程实现单纯形算法。4.2 单单 纯纯 形形 表表-39-China University of Mining and Technology运筹学 解：建立单纯形表如下：解：建立单纯形表如下：例例2 求解线性规划问题：求解线性规划问题：4.2 单单 纯纯 形形 表表01-3020CBXBbx1x2x3x4x5x60 x1713-1020-0 x4120-24100
21、30 x6100-4308110/3j001-3020-40-China University of Mining and Technology运筹学 01-3020CBXBbx1x2x3x4x5x60 x11015/201/4204-3x330-1/211/400-0 x610-5/20-3/481-j90-1/203/42001-3020CBXBbx1x2x3x4x5x60 x1713-1020-0 x4120-2410030 x6100-4308110/3j001-30204.2 单单 纯纯 形形 表表-41-China University of Mining and Technolo
22、gy运筹学-18-3/40-5/201x603/41/41/4x40202x52000 x600-1/209j-1-1/203x3-3405/2110 x10 x3x2x1bXBCB-31001-3020CBXBbx1x2x3x4x5x61x242/5101/104/504-3x351/5013/102/50-0 x611100-1/2101-j111/5004/512/50最优解是最优解是 ，最优值为，最优值为 z=-11.4.2 单单 纯纯 形形 表表-42-China University of Mining and Technology运筹学 0.16-0.120102412x2-0.20.4001207x11.16-3.12100840 x3-1.20003.41000.10010,33012x220-0.51002.5500 x430.8-0.40107.82400 x3000127301001033000 x540010542000 x490001493600 x3x5x4x3x2x1B-1bCBXB每一列的含每一列的含义？义？每个表中的每个表中的B和和B-1的查的查找？找？思思 考考 题题