《运筹学演示课件》

运筹学演示课件

运筹学演示课件

目录 第一章线性规划□ 第二章对偶2 第三章整数规划□ 第四章运输问题圖 第五章网络优化 第六章动态规划□ 第七章排队论

目 录 第一章 线性规划 第二章 对偶 第三章 整数规划 第四章 运输问题 第五章 网络优化 第六章 动态规划 第七章 排 队 论

第一章线性规划 凵线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 凵基础解、基础可行解 单纯形表 凵线性规划的矩阵表示

第一章 线性规划 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示

线性规划模型 线性规划模型的结构 max(mm)z=CⅩ 目标函数:max,mi 约束条件:>,=≤ s t AX2(=,≤)b 变量符号::≥0,unr,≤O x≥(≤)0,umr 线性规划的标准形式mnz=CX 目标函数:min 约束条件: s.t. AX=b 变量符号:≥0 X≥0

线性规划模型 线性规划模型的结构 目标函数 ：max，min 约束条件：≥,=,≤ 变量符号：：≥0, unr, ≤0 线性规划的标准形式 目标函数：min 约束条件 ：= 变量符号 ：≥0 X ( )0,unr s.t. AX ( , )b max(min) z C X T    =  = X 0 s.t. AX b min z C X T  = =

线性规划的图解 max zX1+3X2 St.X1+x20 可行域 0 目标函数等值线

线性规划的图解 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 可行域 目标函数等值线 最优解 6 4 -8 6 0 x1 x2

可行域的性质 ●线性规划的可行域是凸集 ●线性规划的最优解在极点上 凸集 凸集 不是凸集 极点

可行域的性质 ●线性规划的可行域是凸集 ●线性规划的最优解在极点上 凸集 凸集 不是凸集 极点

线性规划的基本概念 ●线性规划的基矩阵、基变量、韭基变量 目标函数□□□ 束条件 ■■口■■口■■■■=口右边常数 ■■■口■口 行列式≠0 基矩阵

线性规划的基本概念 ●线性规划的基矩阵、基变量、非基变量 = = 目标函数 约 束 条 件 行列式≠0 基矩阵 右边常数

max z= 2X1 +3x2 +X3 S t +3x2+x3<1 3X2 583 0 min Z =15 2x1+3

max z= 2x1 +3x2 +x3 s.t. x1 +3x2 +x3 15 2x1 +3x2 -x3 18 x1 -x2 +x3 3 x1, x2, x3 0 min z’= -2x1 -3x2 -x3 st x1 +3x2 +x3 +x4 =15 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3 x1, x2, x3, x4, x5, x6 0

X x =15 3x1-x +X5 =18 基变量x1、x2、x3,非基变量x4、x5、x 1+3x 2x1+3X2-X3=18 tx3 基础解为 )=(5,3,1,0,0,0) 是基础可行解,表示可行域的一个极点 目标函数值为:z20

x1 +3x2 +x3 =15 2x1 +3x2 -x3 =18 x1 -x2 +x3 =3 x1 +3x2 +x3 +x4 =15 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3 基变量x1、x2、x3，非基变量x4、x5、x6 基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=20

X 33 =15 2x =18 X2+x3 基变量x1、ⅹ 非基变量x3、x X1+3X2+x4=15 2x1+3x2 =18 X 基础解为 )=(27/5,12/5,0,2/5,0,0 是基础可行解,表示可行域的一个极点 目标函数值为:z=18

x1 +3x2 +x4 =15 2x1 +3x2 =18 x1 -x2 =3 基变量x1、x2、x4，非基变量x3、x5、x6 基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18 x1 +3x2 +x3 +x4 =15 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3