《运筹学》课程PPT教学课件(Operations Research)第四章(4.2)具有整数解的线性规划问题

运筹学 Operations Research §4.2具有整数解的线性规划问题 对纯整数规划 maX Z=C X (P): s.t. Ax= b x≥0,整数,=1,2,…,n 其松弛线性规划问题(1 inear programming relaxation) maX 2=C x (LP): s.t. Ax=b x≥0 2021/2/20
2021/2/20 1 运 筹 学 Operations Research §4.2 具有整数解的线性规划问题 对纯整数规划 = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数 其松弛线性规划问题(linear programming relaxation) = = 0 . . max ( ) : x st Ax b z c x LP T

运筹学 Operations Research 命题1(1)K(P)≤K(LP) (2) LP (3)设利用单纯形法求解(LP)得最优解x,若x'为整数解, 则必为(P)的最优解 证 推论若(LP)不可行,则(P)也不可行 个“朴素的( nal ve)”的设想: 将(LP)的最优解取整得(P舶的最优解? 2021/2/20 2
2021/2/20 2 运 筹 学 Operations Research ( ) . (3) ( ) (2) 1(1) ( ) ( ) 则必为 的最优解 设利用单纯形法求解 得最优解 ,若 为整数解, 命题 IP LP x x z z K IP K LP IP LP 推论若(LP)不可行,则(IP)也不可行. 证:…… ▌ 一个“朴素的(naive)”的设想: 将(LP)的最优解取整得(IP)的最优解?

运筹学 Operations Research 上述想法不可行!如 max z=x, +x st 2x1+2x2≥1 -8x1+10x2≤13 x1,x2≥0,整数 max 2=x, +x2 st 2x1+2x,≥1 (LP) -8x,+10x<13 x,≥0 2021/2/20 3
2021/2/20 3 运 筹 学 Operations Research 上述想法不可行! 如 − + − + = + , 0,整数 8 10 13 . . 2 2 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x IP − + − + = + , 0 8 10 13 . . 2 2 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x LP

运筹学 Operations Research 图解法 13 2=x1 +z A 2021/2/20 4
2021/2/20 4 运 筹 学 Operations Research 图解法:

运筹学 Operations Research (LP)的最优解为4。),最优值为7 2 取整得(P)的最优解为(4,5),最优值为9 实际上,(IP)的最优解为(,2),最优值为3. 显然,二者差别甚大! 于是,求解整数规划的新算法的引入成为必要 2021/2/20
2021/2/20 5 运 筹 学 Operations Research ( ) (1,2 3. ( ) (4,5) 9. . 2 17 ) 2 9 ( ) (4, 实际上, 的最优解为 ),最优值为 取整得 的最优解为 ,最优值为 的最优解为 ,最优值为 T T T IP IP LP 显然,二者差别甚大! 于是,求解整数规划的新算法的引入成为必要

运筹学 Operations research 但是,也确有一些线性规划问题,其本身的结构就决定 了它必然存在整数解 单(幺)模阵( unimodular matrix):行列式的值为0 1,1的整数方阵. 全单(幺)模阵( total unimodular matrix):任一子方 阵均为单模阵的矩阵. 10 2021/2/20 6
2021/2/20 6 运 筹 学 Operations Research 单(幺)模阵(unimodular matrix):行列式的值为0,- 1,1的整数方阵. 全单(幺)模阵(total unimodular matrix):任一子方 阵均为单模阵的矩阵. 1 3 2 5 1 0 −1 1 1 0 但是,也确有一些线性规划问题,其本身的结构就决定 了它必然存在整数解

运筹学 Operations Research 命题2设矩阵A=(an)mn4n=0.-1,A的每列至多有两个非零元素 若可将A的行指标划分为1和2,使得 (1)当A的某列含有两个同号的非零元素时,这两个非零元素所在的 行指标分属l1和Ⅰ2; (2)当4的某列含有两个异号的非零元素时,这两个非零元素所在的 行指标同属和,■ 则A必为全单模阵 2021/2/20 7
2021/2/20 7 运 筹 学 Operations Research . (2) (1) 2 ( ) , 0, 1,1 . 1 2 1 2 1 2 则 必为全单模阵 行指标同属 和 , 当 的某列含有两个异号的非零元素时,这两个非零元素所在的 行指标分属 和 ; 当 的某列含有两个同号的非零元素时,这两个非零元素所在的 若可将 的行指标划分为 和 ,使得 命题 设矩阵 , 的每列至多有两个非零元素 A I I A I I A A I I A = ai j mn ai j = − A ▌

运筹学 Operations Research 例1判断矩阵是否为全单模阵? 10100 100 0-00 0 解:1={12},12={3,4}口 Th1(具有整数解的线性规划问题)对线性规划问题 T maX Z=C x (LP): s.t. Ax=b x≥0 2021/2/20 8
2021/2/20 8 运 筹 学 Operations Research 例1 判断矩阵是否为全单模阵? − − − = 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 A {1,2} {3 4} 解:I 1 = ,I 2 = , ▌ Th1(具有整数解的线性规划问题)对线性规划问题 = = 0 . . max ( ) : x st Ax b z c x LP T

运筹学 Operations Research 若A是全单模阵,b是整数向量,则(LP)的任一基本解 均为整数解 证:设(LP关于任一基的基本解为x=6 B b 则xB=Bbb b=±B'b是整数向量 B 2021/2/20
2021/2/20 9 运 筹 学 Operations Research . ( ) 均为整数解 若A是全单模阵,b是整数向量,则 LP 的任一基本解 证:设 关于任一基 的基本解为 , = = − 0 ( ) 1 B b x x LP B x N B . | | 则 1 b B b是整数向量 B B xB B b − = = = ▌

运筹学 Operations Research 例2求证:运输问题必有整数解,其中a;2b,∈Z+ mIn z=∑∑Cxn (TP) ∑x=b,j xn≥0,i=1,2,…,m,j=1,2,…,n 证:b=(a12a2,…,an,b12b2…b)是整数向量 2021/2/20 10
2021/2/20 10 运 筹 学 Operations Research 例2 求证:运输问题必有整数解, , . + 其中ai bj Z = = = = = = = = = = = x i m j n x b j n st x a i m z c x TP i j m i i j j i n j i j m i n j i j i j 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , min ( ) : 1 1 1 1 ( , , , , , , , ) . 证:b = a1 a2 am b1 b2 bn T 是整数向量
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 《运筹学》课程PPT教学课件(Operations Research)第四章(4.1)整数规划.ppt
- 《运筹学》课程教学讲义(Operations Research)第十二章(12.2)统筹图中有关参数的计算.doc
- 《运筹学》课程教学讲义(Operations Research)第十二章(12.1)统筹图.doc
- 《运筹学》课程教学讲义(Operations Research)第二章(2.2.2)最小树与森林.doc
- 《运筹学》课程教学讲义(Operations Research)第二章(2.2.1)树.doc
- 《运筹学》课程教学讲义(Operations Research)第二章(2.1.2)图的基本概念(2/2).doc
- 《运筹学》课程教学讲义(Operations Research)第二章(2.1.1)图的基本概念(1/2).doc
- 《运筹学》课程教学资源(讲义)第二章 图论绪言.doc
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)Users Guide.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第十章 数学问题的非传统解法.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第九章 概率论与数理统计问题的计.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第八章 数据插值、函数逼近问题的计算机求解.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第七章 微分方程问题的计算机求解.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第六章 代数方程与最优化问题的计算机求解.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第五章 积分变换与复变函数问题的计算机求解.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第四章 线性代数问题的计算机求解.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第三章 微积分问题的计算机求解.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第二章 MATLAB语言程序设计基础.ppt
- 东北大学:《MATLAB语言与现代科学运算》课程教学资源(PPT课件)第一章 计算机数学语言概述.ppt
- 《线性代数》第9讲 向量组的秩.ppt
- 《运筹学》课程PPT教学课件(Operations Research)第四章(4.3)割平面法.ppt
- 《运筹学》课程教学讲义(Operations Research)第五章(5.1)运输问题.doc
- 《运筹学》课程教学讲义(Operations Research)第五章(5.2)初始基本可行解.doc
- 《运筹学》课程教学讲义(Operations Research)第五章(5.3)最优性的检验.doc
- 《运筹学》课程教学讲义(Operations Research)第五章(5.4)算法步骤.doc
- 《运筹学》课程教学讲义(Operations Research)第六章(6.1)整数规划.doc
- 《运筹学》课程教学讲义(Operations Research)第六章(6.2)具有整数解的线性规划问题.doc
- 《运筹学》课程教学讲义(Operations Research)第六章(6.3.1)割平面法(1/2).doc
- 《运筹学》课程教学讲义(Operations Research)第六章(6.3.2)割平面法(2/2).doc
- 《运筹学》课程PPT教学课件(Operations Research)第六章 图论(6.0)绪言.ppt
- 《运筹学》课程PPT教学课件(Operations Research)第六章 图论(6.1)图的基本概念.ppt
- 《运筹学》课程PPT教学课件(Operations Research)第六章 图论(6.2)树.ppt
- 《运筹学》课程PPT教学课件(Operations Research)第六章 图论(6.3)中国邮递员问题.ppt
- 《运筹学》课程PPT教学课件(Operations Research)第六章 图论(6.4)旅行售货员问题.ppt
- 《运筹学》课程PPT教学课件(Operations Research)第六章 图论(6.6)最大流.ppt
- 《运筹学》课程教学讲义(Operations Research)第七章 决策论 7.1 决策的概念.doc
- 《运筹学》课程教学讲义(Operations Research)第七章 决策论 7.2 不确定型决策.doc
- 《运筹学》课程PPT教学课件(Operations Research)第七章 决策论.ppt
- 《运筹学》课程教学讲义(Operations Research)第九章 对策论.doc
- 《运筹学》课程PPT教学课件(Operations Research)第九章 对策论.ppt