运筹学演示课件
运筹学演示课件
目录 第一章线性规划心 第二章对偶2 第三章整数规划□ 第四章运输问题圖 第五章网络优化 第六章动态规划□ 第七章排队论
目 录 第一章 线性规划 第二章 对偶 第三章 整数规划 第四章 运输问题 第五章 网络优化 第六章 动态规划 第七章 排 队 论
第一章线性规划 凵线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 凵基础解、基础可行解 单纯形表 凵线性规划的矩阵表示
第一章 线性规划 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示
线性规划模型 线性规划模型的结构 max(mr)z=CX 目标函数:max,min 约束条件:>,=,≤ S. t AX≥(=,)b 变量符号::≥0,unr,≤O x≥(≤)0,umr 线性规划的标准形式 miz=CⅩ 目标函数: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 t.x1+2≤6 最优解 +2X20 可行域 8 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<15 2x1+3 3≤18 X X2+x3≤3 0 min Z'=-2X1-3X2-X 2x1+3x 18 X6=3 X2, X3, X4, X5, 6 20
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
x1+3x+x3+x4 =15 3xd-x 18 基变量x1、x2、x3,非基变量x4、x5、x 1+3x2+x3=15 2x1+3x2-X3=18 +X3=3 基础解为 X5,x6)=(5,3,1,0,0,0) 是基础可行解,表示可行域的一个极点 目标函数值为:z=20
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
=15 2x1+3 =18 基变量x1、x2、x4,非基变量x3、x、x X1+3x2+x4=15 2x1+3 =18 基础解为 X5,x6)=(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