运筹学教程（管理人必备）

nullnull运 筹 学 教 程 4.0 版 蒋 绍 忠 制作 浙 江 大 学 管 理 学 院 2005年6月null运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。 运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。前言—运筹学简介null运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。null战后这些研究成果逐渐公开发表，这些理论和 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。运筹学的内容十分广泛，包括线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、整数规划、运输问题、网络优化、动态规划和排队论。目 录目 录 第一章 线性规划 第二章 对偶 第三章 整数规划 第四章 运输问题 第五章 网络优化 第六章 动态规划 第七章 排 队 论第一章 线性规划第一章 线性规划 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示null线性规划模型线性规划模型的结构 目标函数 ：max，min 约束条件：≥,=,≤ 变量符号：：≥0, unr, ≤0 线性规划的标准形式 目标函数：min 约束条件 ：= 变量符号 ：≥0线性规划的图解线性规划的图解max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0可行域目标函数等值线最优解64-860x1x2可行域的性质可行域的性质线性规划的可行域是凸集 线性规划的最优解在极点上 凸集凸集不是凸集null线性规划可行域和最优解的几种情况1、可行域封闭 唯一最优解2、可行域封闭 多个最优解3、可行域开放 唯一最优解4、可行域开放 多个最优解5、可行域开放 目标函数无界6、无可行解nullx3=0x4=0max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40x1=0, x2=0 x3=3, x4=1x1=0, x4=0 x2=1, x3=2x2=0, x3=0 x1=3, x4=1x3=0, x4=0 x1=2, x2=1x1=0, x3=0 x2=3, x4=-2线性规划的基本概念—基础解、基础可行解、极点x2=0x1=0OABCDnull标准化的线性规划问题，有n个变量，m个约束。 令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这个m×m的矩阵称为线性规划的一个基。等于0的n-m个变量称为非基变量，m个变量称为基变量。 求解m×m的线性方程组，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基础解。 如果一个基础解中的所有变量都是非负的，这个基础解称为基础可行解。 线性规划的基础可行解就是可行域的极点。线性规划的基本概念—基础解、基础可行解、极点nullmax z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40x1=0, x2=0 x3=3, x4=1 基础可行解x1=0, x4=0 x2=1, x3=2 基础可行解x2=0, x3=0 x1=3, x4=1 基础可行解x3=0, x4=0 x1=2, x2=1 基础可行解x1=0, x3=0 x2=3, x4=-2 是基础解，但不是可行解OABx3=0x4=0x2=0x1=0CD可行域null几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值： 一组平行线 目标函数值等于一个常数的解null搜索所有基础可行解求出最优解null基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=20null基变量x1、x2、x4，非基变量x3、x5、x6基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18null基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基础解，但不是可行解，不是一个极点。null基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18null基变量x2、x3、x4，非基变量x1、x5、x6基础解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基础解，但不是可行解。null基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=15null基变量x1、x2、x3，非基变量x4、x5、x6基础解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基础解但不是可行解。null－ ＋＋ －单纯形法原理（1）—松弛变量的表示max z=x1+2x2 s.t. x1+x23 x2 1 x1, x20max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40x2=0x1=0x3=0x4=0OABCD－ ＋＋ －nullx2=0x1=0x3=0x4=0OABC第一次叠代： 目标函数和基变量分别用非基变量表示： z=-x1-2x2 选择x2进基 x3 =3-x1-x2 x4=1 -x2单纯形法原理(2)—第一次叠代null确定离基变量的进一步讨论设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x25/4=1.25 4/3=1.33 2/1=2min{5/4,4/3,2/1}=5/4 当x2增加到1.25时 x3＝0离基x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2x3增加 4/3=1.33 2/1=2min{4/3,2/1}=4/3 当x2增加到1.33时 x4＝0离基x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2x3增加 x4增加 2/1=2min{2/1}=2/1 当x2增加到2时 x5＝0离基x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2x3增加 x4增加 x5增加x2可以无限增加，可行域是开放区域，目标函数无界nullx2=0x1=0x3=0x4=0OABC第二次叠代： 目标函数和基变量分别用非基变量表示： z=-2-x1+2x4 选择x1进基 x3 =2-x1+x4 x2=1 -x4单纯形法原理（3）—第二次叠代nullx2=0x1=0x3=0x4=0OABC第三次叠代： 目标函数和基变量分别用非基变量表示： z=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4 非基变量在目标函数中的系数全部大于0，已获得最优解。单纯形法原理（4）—最优解的判定nullx2=0x1=0x3=0x4=0OABC单纯形法原理(5)—叠代过程回顾第一次叠代 x2进基，x4离基第二次叠代 x1进基，x3离基(x1,x2,x3,x4)= (0,0,3,1), z=0(x1,x2,x3,x4)= (0,1,2,0), z=-2(x1,x2,x3,x4)= (2,1,0,0), z=-4 最优解null单纯形法原理（6）—单纯形法总结STEP 0 找到一个初始的基础可行解，确定基变量和非基变量。转STEP 1。 STEP 1 将目标函数和基变量分别用非基变量表示。转STEP 2。 STEP 2 如果目标函数中所有非基变量的系数全部为正数，则已经获得最优解。运算终止。否则，选取系数为负数并且绝对值最大的非基变量进基。转STEP 3。 STEP 3 如果进基变量增加时，基变量都不减少，则可行域开放，目标函数无界。运算终止。否则，随着进基变量的增加，最先下降到0的基变量离基。转STEP 1。进基变量、离基变量、基变换进基变量、离基变量、基变换目标函数约束条件基矩阵右边常数=基变量null进基变量离基变量目标函数约束条件右边常数=null目标函数约束条件新的基矩阵右边常数=null进基变量离基变量目标函数约束条件基矩阵=null目标函数约束条件新的基矩阵右边常数=null线性规划基本概念练习（1）036x1x2OABCEFGHI46-2min z=-x1+2x2 s.t. 3x1+2x2≤12 (1) x1+2x2≥ 6 (2) -2x1+ x2≤ 4 (3) x1, x2≥ 01、约束条件（1）对应的直线是（ ），对应的半平面是…… 约束条件（2）对应的直线是（ ），对应的半平面是…… 约束条件（3）对应的直线是（ ），对应的半平面是……2、这个线性规划的可行域是（ ）。 3、对于z=2和4,分别画出目标函数等值线。 4、这个线性规划的最优解位于（ ）。ACEFBCDHEGHICDGEz=2z=4CD4null036x1x2OABCEFGHI46-2D线性规划基本概念练习（2）5、x1等于0的直线是( )， x2等于0的直线是( )， x3等于0的直线是( )， x4等于0的直线是( )， x5等于0的直线是( )。 6、A点对应的基变量是( )，非基变量是（ ）； D点对应的基变量是( )，非基变量是（ ）。 7、A点不是可行解， 是由于( )<0, F点不是可行解， 是由于( )<0, I 点不是可行解， 是由于( )<0。4x1=0x2=0x3=0x4=0x5=0ODGFIOABACEFBCDHEGHI8、x1,x2,x5≥0, x3,x4≤0的区域是( ) x1,x2,x3,x5≥0, x4≤0的区域是( ) x2,x3,x4,x5≥0, x1≤0的区域是( ) x1,x2,x3,x4≥0, x5≤0的区域是( )x1,x4,x5x3,x2x2,x3,x5x1,x4x4x5x1,x4ABCOACDDGHEFGnull线性规划基本概念练习（3）036x1x2OABCEFGHI46-2D4x1=0x2=0x3=0x4=0x5=09、从O到D的单纯形迭代， 进基变量是（ ），离基变量是（ ）。 从D到C的单纯形迭代，进基变量是（ ），离基变量是（ ）。 从C到E的单纯形迭代，进基变量是（ ），离基变量是（ ）。x2x4x1x3x4x5单纯形表单纯形表min z’=-x1-2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0z’+x1+2x2 =0 x1+x2+ x3 =3 x2 +x4=1nullz’=-x1-2x2 x3 =3-x1-x2 x4=1 -x2z’=-2-x1+2x4 x3=2-x1+x4 x2 =1 -x4z’=-4+x3+x4 x1 =2-x3+x4 x2=1 -x4单纯形法原理单纯形表null求解线性规划问题写成标准化形式null写出单纯形表25/136/20-3-20-2-72011/201-1/27/1/21x51/2101/218/1/2071811/21/2x20x6离基，②为主元，进行行变换，将②变为1，4和1变为0x2进基，计算RHS和x2在约束条件中的系数的比值，比值小的基变量离基x5离基，x1进基，null0-4-2-2-1-8601102-11x101-1101411010x20得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0） min z’=-86，max z=86null单纯形表的结构 基变量在目标函数中的系数等于0，基变量在约束条件中的系数是一个单位矩阵。nullStep 0 获得一个初始的单纯形表，确定基变量和非基变量 Step 1 检查基变量在目标函数中的系数是否等于0，在约束条件中的系数是否是一个单位矩阵。 Step 2 如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且绝对值最大的变量进基，转step 3。 Step 3 如果进基变量在约束条件中的系数全为负数或0，则可行域开放，目标函数无界。停止。否则选取右边常数和正的系数的最小比值，对应的基变量离基，转step 4。 Step 4 确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转Step 2。单纯形表的运算null标准化。引进松弛变量x4，x5null写出单纯形表x1进基，x4离基。第二行除以2null行变换。将主元变成1，主元所在列的其他元素变为0x2进基，x5离基。第三行除以5null行变换。将主元变成1，主元所在列的其他元素变为0检验数全部为负数或0，获得最优解。 最优解为：（x1，x2，x3，x4，x5）＝（6，12，0，0，0） min z’=-42，max z=42null初始基础可行解约束条件全部是≤，右边常数全部是非负的线性规划问题，引进松弛变量后，可以直接得到一个初始基础可行解。在这个解中，原来的变量为非基变量，松弛变量为基变量。例如：min z=x1+x2-2x3 s.t. 3x1+2x2- x3≤35 x1- x2+2x3≤28 x1, x2, x3≥0min z=x1+x2-2x3 s.t. 3x1+2x2- x3+x4 =35 x1- x2+2x3 +x5=28 x1, x2, x3, x4, x5≥0x1=x2=x3＝0为非基变量，x4=35，x5=28为基变量，得到初始的基础可行解。引进松弛变量null约束条件中有≥约束，右边常数全部是非负的线性规划问题，引进松弛变量（Slack Variables）后，无法直接得到一个初始基础可行解。例如：min z=x1+x2 s.t. 3x1+2x2≥35 x1- x2≥28 x1, x2≥0min z=x1+x2 s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 (A) x1, x2, x3, x4≥0x1=x2＝0为非基变量，x3=-35，x4=-28为基变量，不是可行解。为了得到(A)的基础可行解，在(A)的约束条件中再引进两个变量x5，x6≥0，这两个变量称为人工变量（Artificial Variables）。min z=x1+x2 s.t. 3x1+2x2 -x3 +x5 =35 x1- x2 -x4 +x6=28 (B) x1, x2, x3, x4, x5, x6≥0null（B）有一个初始的基础可行解： (x1, x2, x3, x4, x5, x6) = (0, 0, 0, 0, 35, 28)，但它不是（A）的可行解。 只有当x5=x6=0时，（B）的可行解才同时也是（A）的可行解。这样的解中x5，x6一定是非基变量。 因此，可以这样来求得（A）的一个初始基础可行解：从（B）以人工变量x5，x6为基变量的初始基础可行解出发，用单纯形法对（B）进行进基－离基变换，如果x5，x6都离基，成为非基变量，则（B）的这个基础可行解就是（A）的一个可行解。为了迫使人工变量尽快离基，构造一个新的极小化目标函数，这个目标函数等于所有人工变量之和。min z=x1+x2 s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 (A) x1, x2, x3, x4≥0min z=x1+x2 s.t. 3x1+2x2 -x3 +x5 =35 x1- x2 -x4 +x6=28 (B) x1, x2, x3, x4, x5, x6≥0nullmin z’=x5+x6 s.t. 3x1+2x2 -x3 +x5 =35 x1- x2 -x4 +x6=28 x1, x2, x3, x4, x5, x6≥0min z=x1+x2 s.t. 3x1+2x2 -x3 =35 x1- x2 -x4=28 x1, x2, x3, x4≥0求解辅助问题，得到辅助问题的最优解引进人工变量x5，x6，构造辅助问题，辅助问题的目标函数为所有人工变量之和min z’=0?人工变量不能离基，原问题没有可行解。把辅助问题的最优解作为原问题的初始基础可行解用单纯形法求解原问题，得到原问题的最优解否是两阶段法的算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图null两阶段法STEP 0 引进松弛变量，成为标准形式。 STEP 1 如果约束条件的系数矩阵中没有一个单位矩阵，引进人工变量，构造辅助问题。 STEP 2 求解辅助问题。得到辅助问题的最优解。如果辅助问题的最优解中人工变量都离基成为非基变量，即辅助问题最优解的目标函数值min z’=0，则辅助问题的最优解就是原问题的一个初始基础可行解。如果辅助问题最优解中仍有人工变量没有离基，即辅助问题最优解的目标函数值min z’>0，则原问题没有可行解。 STEP 3 转到第二阶段，从原问题的初始基础可行解出发，求出原问题的最优解。null案例一 食油生产计划储罐1储罐2储罐3储罐4储罐5硬质油1硬质油2软质油1软质油2软质油3硬质油精炼软质油精炼混合成品油原料加工成品第二章 对偶线性规划第二章 对偶线性规划对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关系 最优解的Kuhn-Tucher条件 对偶可行基对偶单纯形法 对偶的经济解释 DUAL一、对偶的定义一、对偶的定义原始问题 min z=CTX s.t. AX≥b X ≥0对偶问题 max y=bTW s.t. ATW≤C W ≥0≥minbACTCATbT≤maxmnmnnull二、对偶问题的性质1、对偶的对偶就是原始问题 min z=CTX s.t. AX≥b X ≥0 max y=bTW s.t. ATW≤C W ≥0min y=-bTW s.t. -ATW≥-C W ≥0 max z’=-CTX s.t. -AX≤-b X ≥0 null2、其他形式问题的对偶原始问题约束条件的性质，影响对偶问题变量的性质。 原始问题变量的性质，影响对偶问题约束条件的性质。min z=CTX s.t. AX≥b X ≥0max y=bTW s.t. ATW≤C W ≥0min z=CTX s.t. AX=b X ≥0max y=bTW s.t. ATW≤C W :unrmin z=CTX s.t. AX≤b X ≥0max y=bTW s.t. ATW≤C W ≤0nullmin z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max y=6w1+12w2+8w3+15w4 s.t. 3w1- w2+2w3+ w4 2 -w1+2w2+ w3+3w4 4 2w1- 3w2+2w3- w4 -1 w1 0,w2 ,w3 0,w4 0≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3: unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。null三、原始对偶关系1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解 z=CTXF ≥WTAXF ≥WTb=y 2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=ynull3、原始问题和对偶问题最优解之间的互补松弛关系 min z=CTX s.t. AX-XS=b X, XS≥0max y=bTW s.t. ATW+WS=C W, WS≥0min z=CTX s.t. AX≥b X ≥0max y=bTW s.t. ATW≤C W≥0互补松弛关系XTWS=0 WTXS=0nullmin z=CTX s.t. AX-XS=b X, XS ≥0max y=bTW s.t. ATW+WS=C W, WS ≥0XTWS=0 WTXS=0ATWIWsCmn=nXA-IXsb=nmm原始问题和对偶问题变量、松弛变量的维数nullw1... wi ... wm wm+1 ... wm+j ... wn+m x1 ... xj ... xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjwm+j=0 wixn+i=0 (i=1,2,…,m; j=1,2,…,n) 在一对变量中，其中一个大于0，另一个一定等于0null3、原始问题和对偶问题最优解的充分必要条件 null四、对偶单纯形法null对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 0, 0, -1, -2, -1)不是对偶问题的可行解null对偶问题的解（w1, w2, w3, w4, w5,w6）=(0, 2/3, 0, 1/3, 0, -1/3)不是对偶问题的可行解null对偶问题的解（w1, w2, w3, w4, w5,w6）=(1/2, 1/2, 0, 1/2, 0, 0)是对偶问题的可行解null结论 单纯形法求解的过程，从对偶的观点来看，是在始终保持原始可行解的条件下，不断改进对偶可行性的过程。一个从对偶不可行的解，经过几次叠代，逐步向对偶可行解靠拢，一旦得到的解既是原始可行的，又是对偶可行的，这个解就分别是原始问题和对偶问题的最优解。null1、用单纯形表求解原始问题的四种形式min z=CTX s.t. AX≥b X ≥0min z=CTX s.t. AX ≤ b X ≥0max z=CTX s.t. AX ≥ b X ≥0max z=CTX s.t. AX ≤ b X ≥0（2）（3）（4）（1）null单纯形表和对偶(1)min z=CTX s.t. AX-XS=b X, XS≥0max y=bTW s.t. ATW+WS=C W, WS≥0nullmin z=CTX s.t. AX-XS=b X, XS≥0max y=bTW s.t. ATW+WS=C W, WS≥0WT=CBTB-1 WST=CT-WTAnullmin z=CTX s.t. AX+XS=b X, XS≥0max y=bTW s.t. ATW+WS=C W ≤0, WS≥0单纯形表和对偶(2)nullmin z=CTX s.t. AX+XS=b X, XS≥0max y=bTW s.t. ATW+WS=C W ≤0, WS≥0WT=CBTB-1 WST=CT-WTAnullmax z=CTX s.t. AX-XS=b X, XS≥0max y=bTW s.t. ATW-WS=C W ≤0, WS≥0单纯形表和对偶(3)nullmax z=CTX s.t. AX-XS=b X, XS≥0min y=bTW s.t. ATW-WS=C W ≤0, WS≥0WT=CBTB-1 WST=WTA- CTnullmax z=CTX s.t. AX+XS=b X, XS≥0max y=bTW s.t. ATW-WS=C W, WS≥0单纯形表和对偶(4)nullmax z=CTX s.t. AX+XS=b X, XS≥0min y=bTW s.t. ATW-WS=C W, WS≥0WT=CBTB-1 WST=WTA- CTnullmin z=6x1+8x2+3x3 s.t. x1+ x2 ≥1 x1+2x2+x3 ≥-1 x1, x2, x3 ≥0max y=w1-w2 s.t. w1+ w2 ≤6 w1+2w2 ≤8 w2 ≤3 w1, w2≥0max y=w1-w2 s.t. w1+w2+w3 =6 w1+2w2 +w4 =8 w2 +w5=3 w1, w2, w3, w4, w5≥0 (w1, w2) =(6,0) (w1,w2,w3,w4,w5) =(6, 0, 0, 2, 3)min z=6x1+8x2+3x3 s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x5≥0(x1, x2, x3 | x4, x5) (w1, w2 | w3, w4, w5)x2=x3=x4=0x1=1, x5=2(x1, x2, x3, x4, x5) =(1, 0, 0, 0, 2)nullmin z=6x1+8x2+3x3 s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x5≥0max y=w1-w2 s.t. w1+w2+w3 =6 w1+2w2 +w4 =8 w2 +w5=3 w1, w2, w3, w4, w5≥0(w1, w2, w3, w4, w5)=(6, 0, 0, 2, 3)(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2)-w3 –w4 –w5 –w1 –w2null如何从最优单纯形表中读出对偶问题的解（1）初始 单纯形表最优 单纯形表null如何从最优单纯形表中读出对偶问题的解（2）初始 单纯形表最优 单纯形表null2、对偶单纯形法（初始解原始不可行的问题）nullnullnull已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35null3、初始解原始、对偶都不可行的问题null解法1：先解决原始可行性nullnull在得到原始可行解时同时得到对偶可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17null解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解nullnull得到原始可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17null五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）null2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、wm称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min ynull3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0nullw1 w2 wm4、产品的机会成本null机会成本利润差额成本5、产品的差额成本（Reduced Cost）wm+j=(ai1w1+ai2w2+...aimwm)-cj 差额成本＝机会成本－利润null5、互补松弛关系的经济解释wixn+i=0如果wi>0，则xn+i=0如果xn+i>0，则wi=0边际利润大于0的资源，在最优生产计划条件下没有剩余wm+jxj=0如果wm+j>0，则xj=0如果xj>0，则wm+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）null和资源有关的量 资源限量（吨） 资源占用（吨） 资源剩余（吨） ＝资源限量－资源占用 资源的影子价格 （资源的边际利润）（元/吨） 和产品有关的量 产品利润（元/件） 产品产量（件） 产品的机会成本（元/件） 产品的差额成本（元/件） ＝机会成本－利润互补松弛关系nullmax z=32x1+31x2+55x3+32x4+70x5 s.t. x1+2x2+ 3x4+2x5≤4000 2x1+2x2+3x3+ x4+4x5≤2000 x1 +2x3+2x4+2x5≤1800 4x1+3x2+5x3 +3x5≤2400 x1，x2，x3，x4，x5≥0nullLP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 45850.00 VARIABLE VALUE REDUCED COST X1 0.000000 7.250000 X2 550.000000 0.000000 X3 0.000000 8.000000 X4 900.000000 0.000000 X5 0.000000 8.500000 ROW SLACK OR SURPLUS DUAL PRICES 2) 200.000000 0.000000 3) 0.000000 15.500000 4) 0.000000 8.250000 5) 750.000000 0.000000 NO. ITERATIONS= 2null2000075038002000180016507.2508.008.539.253163.03278.5产品的机会成本＝Σ产品对设备的消耗×设备的影子价格资源的占用＝ Σ产品产量×产品对设备的消耗资源的剩余＝资源限量－资源占用产品的差额成本＝产品的机会成本－产品利润产品产量和产品的机会差额成本互补松弛资源剩余和资源的影子价格互补松弛第四章 运输问题第四章 运输问题 运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、对偶变量法 确定进基变量，调整运量，确定离基 变量 运输问题网络图运输问题网络图供应地需求地供应量需求量总供应量60吨总需求量60吨供求平衡的运输问题运输问题线性规划模型运输问题线性规划模型供应地约束需求地约束由于前m个供应地约束和后n个需求地约束是线性相关的，因此运输问题系数矩阵的秩0时，相应的wij=0，同时由单纯形表的结构可以知道，对偶问题的松弛变量的相反数就是非基变量的检验数，因此，运输问题非基变量的检验数可以通过下列步骤得到： 对于m+n-1个基变量，可以得到对偶问题的m+n-1个等式约束 令一个对偶变量vm＝0，就可以由m+n-1个等式，求出m个对偶变量ui和vj的值 已知ui，vj和cij的值，可以求出对偶问题松弛变量，即非基变量检验数的值null令v3=0，得到以下等式方程组v3=0 u2=7 v2=-5 u1=10 v1=-7-w13=u1+v3-c13=+4 -w21=u2+v1-c21=-4null+4-4null对于基变量x23=11，有u2+v3=c23=7，令v3=0，得到u2=7v3=0u2=7u1=10v2=-5v1=-7对于基变量x22=7，有u2+v2=c22=2，由u2=7，得到v2=-5对于基变量x12=10，有u1+v2=c12=5，由v2=-5，得到u1=10对于基变量x11=12，有u1+v1=c11=3，由u1=10，得到v1=-7对于非基变量x13， 有检验数为：u1+v3-c13=10+0-6=+4对于非基变量x21， 有检验数为：u2+v1-c21=7+(-7)-4=-4+4-4null总结：求运输问题单纯形法非基变量检验数的对偶变量法： 对于基变量xij>0，有ui+vj=cij 对于m+n-1个基变量以及vn=0，可以列出m+n个等式方程，求解m+n个对偶变量ui和vj 非基变量xij的检验数，等于ui+vj-cij+4-4null非基变量xij的检验数zij-cij—对偶变量法(1)v4=0nullu3+v4=c34 u3=6非基变量xij的检验数zij-cij—对偶变量法(1)nullu3+v3=c33 v3=4非基变量xij的检验数zij-cij—对偶变量法(1)nullu2+v3=c23 u2=-2非基变量xij的检验数zij-cij—对偶变量法(1)nullu2+v2=c22 v2=6非基变量xij的检验数zij-cij—对偶变量法(1)nullu2+v1=c21 v1=10非基变量xij的检验数zij-cij—对偶变量法(1)nullu1+v1=c11 u1=-4非基变量xij的检验数zij-cij—对偶变量法(1)nullz12-c12=u1+v2-c12=(-4)+6-7=-5-5非基变量xij的检验数zij-cij—对偶变量法(1)nullz13-c13=u1+v3-c13=(-4)+4-5=-5-5-5非基变量xij的检验数zij-cij—对偶变量法(1)nullz14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-5非基变量xij的检验数zij-cij—对偶变量法(1)nullz24-c24=u2+v4-c24=(-2)+0-7=-9-9-5-5-7非基变量xij的检验数zij-cij—对偶变量法(1)nullz31-c31=u3+v1-c31=6+10-5=1111-5-5-7-9非基变量xij的检验数zij-cij—对偶变量法(1)nullz32-c32=u3+v2-c32=6+6-9=+3+3-5-5-7-911非基变量xij的检验数zij-cij—对偶变量法(1)null选择进基变量,确定离基变量x31进基, min{x21,x33}=min{8,6}=6, x33离基+3-5-5-7-911null调整运量,重新计算检验数,确定进基、离基变量x14进基, min{x11,x34}=min{14,13}=13, x34离基-11-5-5+4+2-8null调整运量, 重新计算检验数所有zij-cij<0,得到最优解。 Min z=6×1+3 ×13+8 ×2+4 ×13+2 ×12+5 ×19=142-11-5-5-4-8-2null确定初始基础可行解西北角法最小元素法求非基变量的检验数闭回路法对偶变量法确定进基变量确定离基变量得到新的基础可行解运输问题单纯形法总结沿回路调整运量null35638422530z=1428例题：用西北角法得到初始基础可行解null-3z12-c12=(c11-c21+c22)-c12=(8-9+10)-12=-3z=1428用闭回路法求各非基变量的检验数null35638422530-3-2用闭回路法求各非基变量的检验数null35638422530-3-2-9用闭回路法求各非基变量的检验数null35638422530-3-2-9-11用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9+4用闭回路法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9+4+2用闭回路法求各非基变量的检验数null35638422530v4=0v3=3v2=7v1=6u1=2u2=3u3=12u4=10对于基变量xij，有ui+vj=cij用对偶变量法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9+4+2v4=0v3=3v2=7v1=6u1=2u2=3u3=12u4=10非基变量xij的检验数：zij-cij=ui+vj-cij，与闭回路法的结果相同用对偶变量法求各非基变量的检验数null35638422530-3-2-9-11+5+14+9+4+2第五章 网络优化第五章 网络优化 网络的基本概念 网络最小费用流问题 网络最大流问题 最短路径问题网络的基本概念网络的基本概念节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）ji路径（Path） 前后相继并且方向相同的边序列 P={(1,2),(2,3),(3,4)}42314231网络由节点和边组成null回路（Circuit） 起点和终点重合的路径称为回路 μ={(1,2),(2,4),(4,1)} 回路中各条边方向相同4231链（Chain） 前后相继并且方向不一定相同的边序列称为链 C={(1,2),(3,2),(3,4)}4231null连通图 任意两个节点之间至少有一条链的图称为连通图24351圈(Cycle) 起点和终点重合的链称为圈 ρ ={(1,2),(2,4),(3,4),(1,3)} 圈中各条边方向不一定相同4231树(Tree) 无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点，在右图中，节点1、3、5是悬挂节点树的性质树的性质任何树至少有一个悬挂节点243512435124351如果树的节点个数为m，则边的个数为m-1树中任意两个节点之间只有唯一的一条链在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈网络的生成树网络的生成树由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树(Spanning Tree)，网络中不属于生成树的边称为生成树的弦网络的生成树的变换网络的生成树的变换网络的一个生成树，增加一条弦，形成唯一的圈，去掉圈中生成树的一条边，得到一个新的网络的生成树生成树2生成树3生成树1////网络的生成树和线性规划的关系网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基 生成树上的边对应于线性规划的基变量 生成树的弦对应于线性规划的非基变量 生成树的变换对应于线性规划单纯形法的进基和离基变换网络最小费用流问题网络最小费用流问题b2=-