运筹学i(本科).ppt

管理运筹学管理运筹学I(本科本科)目目 录录第第1章章 线性规划线性规划第第2章章 对偶理论对偶理论第第3章章 运输问题运输问题第第4章章 整数规划与分配问题整数规划与分配问题 第第5章章 图与网络分析图与网络分析第第6章章 计划评审法和关键路线法计划评审法和关键路线法第第7章章 目标规划目标规划2第第1章章 线性规划线性规划1.1 线性规划的数学模型线性规划的数学模型1.2 图解法图解法1.3 单纯形法原理与计算步骤单纯形法原理与计算步骤1.4 单纯形法进一步讨论单纯形法进一步讨论1.5 线性规划建模线性规划建模3ex1.1ex1.1ex1.1ex1.1:甲企业计划生产两种产品甲企业计划生产两种产品、，这两种产，这两种产品都要分别在品都要分别在A A、B B、C C、D D四种不同设备上加工，四种不同设备上加工，已知每生产一件产品的设备加工工时、设备生产已知每生产一件产品的设备加工工时、设备生产能力、产品单位利润如下表，问能力、产品单位利润如下表，问、各生产多各生产多少使利润达到最大？少使利润达到最大？1.1 线性规划数学模型线性规划数学模型 生产能力生产能力生产能力生产能力A 2 2 12A 2 2 12B 1 2 8B 1 2 8C 4 0 16C 4 0 16D 0 4 12D 0 4 12获利获利获利获利 2 2元元元元/件件件件 3 3元元元元/件件件件4解解 设分别生产设分别生产、产品数量为产品数量为x1、x2 则利润则利润Z=2x1+3x2,考虑到设备的生产能力则应受到以下条考虑到设备的生产能力则应受到以下条件的限制使得件的限制使得2x1+2x212x1+2x284x1 164x2 12x1，x2 0利润目标为max z=2x1+3x2 A 设备生产能力约束B 设备生产能力约束C、D 设备生产能力约束现实问题变量非负Z=2x1+3x2 max5 线性规划模型三要素线性规划模型三要素决策变量（决策变量（variable）：指决策者为实现规：指决策者为实现规划目标采取的方案、措施，是问题中要确划目标采取的方案、措施，是问题中要确定的未知量。定的未知量。目标函数（目标函数（objective）：问题要达到的目的要求。：问题要达到的目的要求。约束条件约束条件(constrains)：决策变量取值时受到的：决策变量取值时受到的各种资源的限制。各种资源的限制。目标函数和约束条件皆为决策变量的目标函数和约束条件皆为决策变量的线性函数线性函数6 线性规划数学模型的几种形式目标函数：max（min）z=c1x1+c2x2+cnxna11x1+a12 x2+a1n xn(,=)b1 a21x1+a22 x2+a2n xn(,=)b2 am1x1+am2 x2+amn xn(,=)bm x1,x2,xn 0.约束条件s.t.简简写写形形式式7矩矩阵阵形形式式向向量量形形式式8标准形式标准形式：非标准形式如何转化？非标准形式如何转化？目标函数为求极小值目标函数为求极小值约束条件为不等式约束条件为不等式变量取值无约束变量取值无约束目标函数求最大值目标函数求最大值约束条件取等式约束条件取等式变量非负变量非负ex1.2 91.2 1.2 图解法图解法优点优点优点优点：直观性强，便于了解线性规划问题解的情况：直观性强，便于了解线性规划问题解的情况：直观性强，便于了解线性规划问题解的情况：直观性强，便于了解线性规划问题解的情况计算步骤计算步骤计算步骤计算步骤：缺点缺点缺点缺点：只能求解两个变量的线性规划模型：只能求解两个变量的线性规划模型：只能求解两个变量的线性规划模型：只能求解两个变量的线性规划模型建立坐标系建立坐标系图示约束条件，确定满足约束的解的范围图示约束条件，确定满足约束的解的范围画出目标函数直线族画出目标函数直线族确定最优解确定最优解10可行域可行域目标函数等值线目标函数等值线最优解64-860 x1x211线性规划问题解的情况线性规划问题解的情况唯一最优解（交于一点）唯一最优解（交于一点）无穷多个最优解（交于一条线段）无穷多个最优解（交于一条线段）无解（无可行域）无解（无可行域）无界解无界解121.3 1.3 单纯形法单纯形法解的概念解的概念可行解可行解：满足约束条件的解：满足约束条件的解X=X=（x x1,1,x,xn n）T T称为线性规划称为线性规划问题的可行解。问题的可行解。可行域可行域：可行解的集合。：可行解的集合。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基基：若：若A A为约束方程组的为约束方程组的mn阶系数矩阵，阶系数矩阵，R（A）=m,B是是A的的mm阶满秩子矩阵，则称阶满秩子矩阵，则称B为线性规划问题的一为线性规划问题的一个基。个基。13基向量基向量：B B中的每一个列向量中的每一个列向量p pj j称为基向量。称为基向量。基变量基变量：基向量：基向量p pj j对应的变量对应的变量x xj j称为基变量。称为基变量。基解基解：在约束方程组：在约束方程组 A X=b 中，令所有的非基变量都为零，中，令所有的非基变量都为零，即即 x xm+1 m+1=x=xm+2 m+2=x=xn n=0=0，,又因为又因为B B满秩，根据克拉姆法则，满秩，根据克拉姆法则，由由m m个约束方程组可解出个约束方程组可解出m m个基变量的唯一解个基变量的唯一解X XB BX XB B=（x x1 1,x,x2,2,x xm m）,将这个解加上非基变量取将这个解加上非基变量取0 0的值有的值有X=X=（x x1 1,x,x2,2,x xm m，0 0，0 0 ）T T，称，称X X为线性规划问题的基解。为线性规划问题的基解。基可行解基可行解：若基解：若基解X0X0，则，则X X为基可行解。为基可行解。可行基可行基：对应于基可行解的基称为可行基。：对应于基可行解的基称为可行基。14ex1.7 ex1.7 找出下列线性规划问题的基解、基可行解找出下列线性规划问题的基解、基可行解15凸集及其顶点凸集及其顶点凸集凸集不是凸集顶点顶点凸集凸集：如果集合：如果集合C C上任意两个点上任意两个点X X1 1、X X2 2，其连线上的所有点都，其连线上的所有点都在集合在集合C C上，则上，则C C是凸集。是凸集。顶点顶点:16基本定理基本定理定理定理1 1：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，则问题的可行域是凸集。引理引理1 1：线性规划问题的可行解：线性规划问题的可行解X=X=（x x1 1,x,xn n）T T为基可行解的充为基可行解的充分必要条件是分必要条件是X X的正分量所对应的系数列向量是线性无关的。的正分量所对应的系数列向量是线性无关的。定理定理2 2：线性规划问题的基可行解：线性规划问题的基可行解X X对应线性规划问题可行域对应线性规划问题可行域（凸集）的顶点。（凸集）的顶点。定理定理3 3：若线性规划问题有最优解，一定存在一个基可行解是最：若线性规划问题有最优解，一定存在一个基可行解是最优解。优解。推论推论：若线性规划问题有最优解，至少在可行域的一个顶点取：若线性规划问题有最优解，至少在可行域的一个顶点取得最优。得最优。17单纯形法计算步骤：单纯形法计算步骤：化为标准型化为标准型求初始基可行解，求初始基可行解，列出初始单纯形表列出初始单纯形表最优性检验最优性检验从一个基可行解转换从一个基可行解转换到相邻的基可行解到相邻的基可行解迭迭代代18单纯形表单纯形表c c1 1 c c2 2 c cm m c cj j c cn n x x1 1 x x2 2 x xm m x xj j x xn n c cj j c c1 1 x x1 1 b b1 1c c2 2 x x2 2 b b2 2:c cm m x xm m b bm m c cB B 基基 b b1 1 0 0 0 0 a a1j 1j a a1n1n0 0 1 1 0 0 a a2j 2j a a2n2n:0 0 0 0 1 1 a amj mj a amj mj c cj j-z zj j0 0 0 0 0 0 19ex1.8 ex1.8 用单纯性法求解下列线性规划问题用单纯性法求解下列线性规划问题20ex1.9 ex1.9 用单纯性法求解下列线性规划问题用单纯性法求解下列线性规划问题211.4 单纯形法进一步讨论人工变量法人工变量法22化为标准型：化为标准型：添加人工变量添加人工变量x x6 6、x x7 7：23两阶段法两阶段法第一阶段：第一阶段：求解一个目标函数中只包含人工变量的线性规划模型求解一个目标函数中只包含人工变量的线性规划模型第二阶段：第二阶段：若第一阶段的模型目标函数值为若第一阶段的模型目标函数值为0,则原问题有可行解。则原问题有可行解。24解的判别：解的判别：唯一最优解唯一最优解基变量不含人工变量基变量不含人工变量所有的检验数所有的检验数 0 0所有的所有的非基变量非基变量的检验数的检验数 0=700X1+0.5X2+0.2X3+2X4+0.5X5=300.5X1+X2+0.2X3+2X4+0.8X5=100ENDLINDO 输入输入文件：文件：LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1)32.43590 VARIABLE VALUE REDUCED COST X1 0.000000 0.059615 X2 0.000000 0.593590 X3 0.000000 0.352564 X4 39.743591 0.000000 X5 25.641026 0.000000LINDO 输出输出文件：文件：30 Ex1.11 Ex1.11 某糖果厂用原料某糖果厂用原料A A、B B、C C加工成三种不同牌号的加工成三种不同牌号的糖果甲、乙、丙，已知各种牌号糖果中糖果甲、乙、丙，已知各种牌号糖果中A A、B B、C C含量、原料含量、原料成本、各种原料的每月限用量，三种牌号糖果的单位加工费成本、各种原料的每月限用量，三种牌号糖果的单位加工费及售价如下表所示，问该厂每月生产这三种糖果各多少千克，及售价如下表所示，问该厂每月生产这三种糖果各多少千克，使该厂获利最大，建立此问题的数学模型并求解。使该厂获利最大，建立此问题的数学模型并求解。甲甲 乙乙 丙丙 原料成本原料成本 每月限用量每月限用量 （元（元/kg）(kg)A 60%30%2.00 2000B 1.50 2500C 20%50%60%1.00 1200加工费加工费（元（元/kg）售价售价（元（元/kg）3.40 2.85 2.25 0.5 0.4 0.3 31MAX(3.40-0.5)(X11+X21+X31)+(2.85-0.4)()+(2.25-0.3)(X13+X23+X33)-2.0(X11+X12+X13)-1.50(X21+X22+X23)-1.0(X31+X32+X33)=0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+X12+X13=2000X21+X22+X23=2500X31+X32+X33=0.6（X11+X21+X31）X31=0.3(X12+X22+X32)X32=0.5（X12+X22+X32）X33=0.6（X13+X23+X33）END原始模型：原始模型：32MAX 0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32-0.05X13+0.45X23+0.95X33STX11+X12+X13=2000X21+X22+X23=2500X31+X32+X33=0X31-0.2X11-0.2X21-0.2X31=0X32-0.5X12-0.5X22-0.5X32=0X33-0.6X13-0.6X23-0.6X330）,则该约束条件取严格等式；反则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定之如果约束条件取严格不等式，则其对应的对偶变量一定为零。为零。49ex 2.3 已知线性规划问题：要求要求：（：（1 1）写出其对偶问题；（写出其对偶问题；（2 2）已知原问题最优解为）已知原问题最优解为X X*=（2 2，2 2，4 4，0 0），试根据对偶理论，直接求出对偶问题的最），试根据对偶理论，直接求出对偶问题的最优解。优解。50（6）基解的互补性基解的互补性 和和变量的对应关系变量的对应关系：线性规划问题原问题和对偶问题之间存在一对线性规划问题原问题和对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应于对偶问互补的基解，其中原问题的松弛变量对应于对偶问题的变量，对偶问题的剩余变量对应原问题的变量，题的变量，对偶问题的剩余变量对应原问题的变量，这些互相对应的变量如果在一个问题的解中是基变这些互相对应的变量如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。将这对互量，则在另一个问题的解中是非基变量。将这对互补的基解分别代入原问题和对偶问题的目标函数中，补的基解分别代入原问题和对偶问题的目标函数中，有有z=.51LP1LP2y1 对应对应 x3 y2 对应对应x4 y3对应对应x5 x1对应对应y4 x2对应对应y5 52LP1的最终单纯行表：的最终单纯行表：C C C CB B B B 基基基基b b b bx x x x1 1 1 1x x x x2 2 2 2x x x x3 3 3 3x x x x4 4 4 4x x x x5 5 5 52 x2 x2 x2 x1 1 1 10 x0 x0 x0 x4 4 4 43 x3 x3 x3 x2 2 2 23 3 3 34 4 4 43 3 3 31 1 1 10 0 0 00 0 0 00 0 0 00 0 0 01 1 1 11/21/21/21/2-2-2-2-20 0 0 00 0 0 01 1 1 10 0 0 0-1/5-1/5-1/5-1/54/54/54/54/51/51/51/51/5z z z zj j j j-c-c-c-cj j j j0 0 0 00 0 0 00 0 0 01 1 1 10 0 0 01/51/51/51/5C C C CB B B B 基基基基b b b by y y y1 1 1 1y y y y2 2 2 2y y y y3 3 3 3y y y y4 4 4 4y y y y5 5 5 512 y12 y12 y12 y1 1 1 115 y15 y15 y15 y3 3 3 31 1 1 11/51/51/51/51 1 1 10 0 0 02 2 2 2-4/5-4/5-4/5-4/50 0 0 01 1 1 1-1/2-1/2-1/2-1/21/51/51/51/50 0 0 0-1/5-1/5-1/5-1/5z z z zj j j j-c-c-c-cj j j j0 0 0 00 0 0 04 4 4 40 0 0 03 3 3 33 3 3 3LP2的最终单纯行表的最终单纯行表532.4 影子价格影子价格 b bi i 是线性规划问题约束的右端项，代表第是线性规划问题约束的右端项，代表第i i种资源种资源的拥有量的拥有量 。而对偶变量。而对偶变量 y yi i 的意义代表对一个单位第的意义代表对一个单位第i i种资源的估价，这种估价不是资源的市场价格，是根据种资源的估价，这种估价不是资源的市场价格，是根据资源在生产中做出的贡献而作的估价，称之为影子价格。资源在生产中做出的贡献而作的估价，称之为影子价格。54（1）影子价格与市场价格的区别影子价格与市场价格的区别：市场价格是已知数，相对比较稳定，而它的影市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的企业生产任务、产品结构等情况发生变化，资源的影子价格随之改变。影子价格随之改变。55（2）影子价格影子价格 是一种边际价格是一种边际价格56（3）资源的影子价格又资源的影子价格又 是一种机会成本是一种机会成本 在纯市场经济条件下，在在纯市场经济条件下，在ex2.4中，当第中，当第3种资源种资源的市场价格低于的市场价格低于1/5时，可以买进这种资源；当市场时，可以买进这种资源；当市场价格高于影子价格时，就会卖出这种资源。影子价价格高于影子价格时，就会卖出这种资源。影子价格最终会与市场价格处于同等水平。格最终会与市场价格处于同等水平。57（4）互补松弛性的经济含义互补松弛性的经济含义58（5）检验数的经济意义检验数的经济意义c cj j 代表第代表第j j种产品的产值，种产品的产值，是生产该种产品是生产该种产品所消耗各项资源影子价格的总和，即产品的隐含成所消耗各项资源影子价格的总和，即产品的隐含成本。当产品的产值大于成本时，生产该产品有利可本。当产品的产值大于成本时，生产该产品有利可图，应安排该种产品（检验数大于零的变量作为进图，应安排该种产品（检验数大于零的变量作为进基变量）。基变量）。59（6）资源影子价格的应用资源影子价格的应用 对线性规划的求解是确定资源的最有效分配方案，对线性规划的求解是确定资源的最有效分配方案，而对其对偶问题的求解则是确定资源的恰当估价，这种而对其对偶问题的求解则是确定资源的恰当估价，这种估价直接涉及到资源的最有效利用。估价直接涉及到资源的最有效利用。资源的影子价格可以作为资源的影子价格可以作为公司内部的结算价格公司内部的结算价格；社；社会上可对一些最紧缺的资源，借助影子价格规定使用这会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上交的利润额，以控制某些公司超种资源一单位时必须上交的利润额，以控制某些公司超低成本使用社会资源，侵蚀公众福利。低成本使用社会资源，侵蚀公众福利。602.5 对偶单纯形法对偶单纯形法612.6 灵敏度分析灵敏度分析 灵敏度分析灵敏度分析：对系统或事物因周围条件变化显示：对系统或事物因周围条件变化显示出来的敏感程度的分析。出来的敏感程度的分析。62灵敏度分析的步骤灵敏度分析的步骤（1）将参数的改变计算反映到最终的单纯形表上将参数的改变计算反映到最终的单纯形表上（2）检查原问题是否仍为可行解检查原问题是否仍为可行解（3）检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解63（3）检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解（4）按下表所列情况得出结论和决定继续计算步骤按下表所列情况得出结论和决定继续计算步骤原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解可行解可行解可行解可行解仍为问题的最优解仍为问题的最优解仍为问题的最优解仍为问题的最优解可行解可行解可行解可行解非可行解非可行解非可行解非可行解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解非可行解非可行解非可行解非可行解可行解可行解可行解可行解用对偶单纯形法继续迭代求最用对偶单纯形法继续迭代求最用对偶单纯形法继续迭代求最用对偶单纯形法继续迭代求最优解优解优解优解非可行解非可行解非可行解非可行解非可行解非可行解非可行解非可行解引进人工变量，编制新的单纯引进人工变量，编制新的单纯引进人工变量，编制新的单纯引进人工变量，编制新的单纯行表重新计算行表重新计算行表重新计算行表重新计算64分析分析cj变化的影响变化的影响65分析分析bi的变化范围变化范围66增加一个变量的分析增加一个变量的分析增加一个变量的分析在实际问题中反映为增加一种新产品。增加一个变量的分析在实际问题中反映为增加一种新产品。ex 2.7 ex 2.7 现在该公司计划增加一种新产品现在该公司计划增加一种新产品x x6 6，已知该，已知该产品单位利润为产品单位利润为4 4元元，p p6 6=(2 4 5)=(2 4 5)T T，原有条件不变，原有条件不变，试分析该公司是否生产这种新产品？试分析该公司是否生产这种新产品？67增加一个约束条件的分析增加一个约束条件的分析 增加一个约束条件的分析在实际问题中反映为增加一道工增加一个约束条件的分析在实际问题中反映为增加一道工序或者增加一种资源限制。序或者增加一种资源限制。ex 2.8 ex 2.8 增加一个约束条件增加一个约束条件 3x3x1 1+2x+2x2 21414，要求分析，要求分析最优解变化。最优解变化。68第第3章章 运输问题运输问题3.1 运输问题的数学模型运输问题的数学模型3.2 表上作业法表上作业法3.3 产销不平衡的运输问题及其应用产销不平衡的运输问题及其应用693.1 运输问题的数学模型运输问题的数学模型ex3.1ex3.1 某食品公司经销的主要产品之一就是糖果，其下属三个生某食品公司经销的主要产品之一就是糖果，其下属三个生产厂，该公司把这些糖果分别运往四个地区门市部销售，已知各产厂，该公司把这些糖果分别运往四个地区门市部销售，已知各加工厂产量、各门市部销售量及从每个加工厂到各销售门市部每加工厂产量、各门市部销售量及从每个加工厂到各销售门市部每吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各门市部需求量的情况下，使总的运费支出为最小。门市部需求量的情况下，使总的运费支出为最小。销地销地销地销地 产地产地产地产地B B1 1 B B2 2 B B 3 3 B B4 4 生生生生产产产产量量量量A A1 1 A A2 2A A3 33 11 3 103 11 3 101 9 2 81 9 2 87 4 10 57 4 10 57 74 49 9需求量需求量需求量需求量3 6 5 63 6 5 6运价运价运价运价70 销地销地销地销地 B Bj j 产地产地产地产地 A Ai iB B1 1 B Bn n 生产量生产量生产量生产量A A A A1 1 1 1 A A A Am m m mc c c c11111111 c c c c1n1n1n1n c c c cm1 m1 m1 m1 c c c cmnmnmnmna a a a1 1 1 1a a a am m m m需求量需求量需求量需求量b b1 1 b bn n运价运价运价运价c cij ij一般运输问题的运输表一般运输问题的运输表7172733.2 运输单纯形法运输单纯形法 表上作业法表上作业法分析实际问题列出产销分析实际问题列出产销平衡表及单位运价表平衡表及单位运价表确定初始调运方案确定初始调运方案（最小元素法最小元素法ororVogelVogel法法）求检验数求检验数（闭回路法闭回路法or or 位势法位势法）找出绝对值最大的负检验数，闭找出绝对值最大的负检验数，闭回路法调整，得出新的调运方案回路法调整，得出新的调运方案所有检验数所有检验数00是是否否得到最优方案得到最优方案算出总的运费算出总的运费迭代迭代74表表3-1 表上作业法计算表上作业法计算 销地销地销地销地 B B1 1B B2 2B B 3 3B B4 4生生生生产产产产量量量量A A1 1 x x11113 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9需求量需求量需求量需求量3 36 65 56 6运价运价运价运价产地产地产地产地753.3 产销不平衡的运输问题及其应用产销不平衡的运输问题及其应用ex3.2ex3.2 设有设有A A1 1、A A2 2、A A3 3三个产地生产某种物资，其产量分别为三个产地生产某种物资，其产量分别为7t7t、5t5t、7t7t，B B1 1、B B2 2、B B3 3、B B4 4四个销售地需要该物资，销量分四个销售地需要该物资，销量分别为别为2t2t、3t3t、4t4t、6t6t，又知各产销地之间的单位运价如下表，又知各产销地之间的单位运价如下表，试决定总运费最小的调运方案。试决定总运费最小的调运方案。处理产销不平衡的思路：转化为产销平衡问题76 销地销地销地销地 B B1 1B B2 2B B 3 3B B4 4生生生生产产产产量量量量A A1 1 2 211113 34 47 7A A2 210103 35 59 95 5A A3 37 78 81 12 27 7需求量需求量需求量需求量2 23 34 46 6运价运价运价运价产地产地产地产地表表表表3-23-277ex3.3ex3.3 设有三个化肥厂供应四个地区的农用化肥。假定等量的设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区化肥在这些地区使用效果相同，已知各化肥厂年产量，各地区需要量及从各化肥厂到各地区单位化肥的运价如表需要量及从各化肥厂到各地区单位化肥的运价如表3-33-3所示，所示，试决定使总的运费最节省的化肥调拨方案。试决定使总的运费最节省的化肥调拨方案。78 产产产产量量量量（万吨）（万吨）（万吨）（万吨）A A16161313222217175050B B14141313191915156060C C1919202023235050最低需求（最低需求（最低需求（最低需求（万吨万吨万吨万吨）最高需求（最高需求（最高需求（最高需求（万吨万吨万吨万吨）30305050707070700 030301010不限不限不限不限需求需求需求需求地区地区地区地区化肥厂化肥厂化肥厂化肥厂表表表表3-33-3运价运价运价运价79ex3.4ex3.4 江南厂按照合同要求需于每个季度末分别完成江南厂按照合同要求需于每个季度末分别完成1010、1515、2525、2020台同一规格的柴油机。已知该厂每个季度生产能力及生台同一规格的柴油机。已知该厂每个季度生产能力及生产每台柴油机的成本如表产每台柴油机的成本如表3-43-4所示，又如果生产的柴油机当季所示，又如果生产的柴油机当季不交货，每台每积压一个季度需储存、维护费用不交货，每台每积压一个季度需储存、维护费用0.150.15万元。要万元。要求在完成合同的条件下，制订使该厂全年生产、储存和维护费求在完成合同的条件下，制订使该厂全年生产、储存和维护费用为最小的决策方案。用为最小的决策方案。季度季度季度季度 生产能力（台）生产能力（台）生产能力（台）生产能力（台）单台成本（万元）单台成本（万元）单台成本（万元）单台成本（万元）1 12 23 34 4252535353030101010.810.811.111.111.011.011.311.3表表表表3-43-480ex3.5 ex3.5 东海造船厂根据合同要在当年算起的连续三年年末各提东海造船厂根据合同要在当年算起的连续三年年末各提供三条规格相同的大型货轮。已知该厂今后三年的生产能力及供三条规格相同的大型货轮。已知该厂今后三年的生产能力及生产成本如表生产成本如表3-53-5所示。所示。已知加班生产情况下每条货轮成本比正产生产时多出已知加班生产情况下每条货轮成本比正产生产时多出7070万万元元，又知造出的货轮如当年不交货，每条货轮，又知造出的货轮如当年不交货，每条货轮每每积压一年将增积压一年将增加维护保养等费用为加维护保养等费用为4040万元万元。在签订合同时该厂已有两条。在签订合同时该厂已有两条当年当年制造的制造的未交货的积压货轮。该厂希望在第三年年末在交完合同未交货的积压货轮。该厂希望在第三年年末在交完合同任务后能储存一条备用。问该厂应该如何生产计划，使在满足任务后能储存一条备用。问该厂应该如何生产计划，使在满足上述要求的条件下，使总的费用支出为最小？上述要求的条件下，使总的费用支出为最小？81 年度年度年度年度 正常生产时可正常生产时可正常生产时可正常生产时可完成的货轮数完成的货轮数完成的货轮数完成的货轮数加班生产时可加班生产时可加班生产时可加班生产时可完成的货轮数完成的货轮数完成的货轮数完成的货轮数正常生产时每正常生产时每正常生产时每正常生产时每条货轮成本条货轮成本条货轮成本条货轮成本第一年第一年第一年第一年第二年第二年第二年第二年第三年第三年第三年第三年2 2 2 24 4 4 41 1 1 13 3 3 32 2 2 23 3 3 3500500500500万万万万600600600600万万万万550550550550万万万万表表表表3-53-582ex3.6 ex3.6 东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产能力分别为能力分别为120120、160160、100100万万t t，公司同三个城市签订了下年，公司同三个城市签订了下年度的供货合同：城市度的供货合同：城市1-1101-110万万t,t,城市城市2-1502-150万万t,t,城市城市3-703-70万万t,t,但但城市城市3 3表示愿意购买剩余的全部煤炭。另有城市表示愿意购买剩余的全部煤炭。另有城市4 4虽未签订合同，虽未签订合同，但也表示只要公司有剩余煤炭，原全部收购。已知从各矿至四但也表示只要公司有剩余煤炭，原全部收购。已知从各矿至四个城市的煤炭单位运价见表个城市的煤炭单位运价见表3-63-6。1 12 23 34 4吉祥吉祥吉祥吉祥平安平安平安平安双福双福双福双福8 85 56 67 72 24 45 51 13 32 23 35 5表表表表3-63-6城市城市煤矿煤矿83第第4章章 整数规划与分配问题整数规划与分配问题4.1 整数规划的特点及作用整数规划的特点及作用4.2 分配问题与匈牙利法分配问题与匈牙利法4.3 分枝定界法分枝定界法 4.4 整数规划建模整数规划建模844.1 整数规划的特点及作用整数规划的特点及作用整数规划整数规划：要求一部分或全部决策变量必须取整数：要求一部分或全部决策变量必须取整数 的规划问题（的规划问题（整数线性规划整数线性规划）。）。整数规划的定义和分类整数规划的定义和分类85纯整数规划纯整数规划：全部决策变量取整数的线性规划。：全部决策变量取整数的线性规划。混合整数规划混合整数规划：只要求一部分决策变量取整数的线：只要求一部分决策变量取整数的线 性规划问题。性规划问题。0-1规划规划：要求决策变量取：要求决策变量取0或或1逻辑值的规划问题。逻辑值的规划问题。86逻辑变量在建模中的用法逻辑变量在建模中的用法（1 1）m m个约束条件中只有个约束条件中只有k k个起作用个起作用87（2 2）约束条件的右端项可能是约束条件的右端项可能是r r个值中的某一个个值中的某一个88（3 3）两组条件满足其中一组两组条件满足其中一组89（4 4）用以表示含固定费用的函数用以表示含固定费用的函数90ex4.1 ex4.1 现有资金总额为现有资金总额为B B，可供选择的项目为，可供选择的项目为n n个。项个。项目目j j（j=1j=1nn）所需投资额和预期收益分别为所需投资额和预期收益分别为a aj j和和c cj j。此外，由于种种原因，有三个附加条件：此外，由于种种原因，有三个附加条件：第一：若选择项目第一：若选择项目1 1就必须选择项目就必须选择项目2 2；第二：项目第二：项目3 3和和4 4至少选择一个；至少选择一个；第三：项目第三：项目5 5、6 6、7 7恰好选择两个。恰好选择两个。问应当如何选择投资项目，才能使总收益最大？试建问应当如何选择投资项目，才能使总收益最大？试建立此问题的数学模型。立此问题的数学模型。914.2 分配问题与匈牙利法分配问题与匈牙利法 m m件任务分别由件任务分别由m m个人完成，已知第个人完成，已知第j j（j=1j=1m）个人完）个人完成第成第i i（i=1i=1m）件任务的成本费用为）件任务的成本费用为c cijij，问应如何分配任，问应如何分配任务可使总费用最小。务可使总费用最小。人员人员人员人员B Bj j 任务任务任务任务A Ai iB B1 1 B Bmm A A A A1 1 1 1 A A A Am m m mc c c c11111111 c c c c1m1m1m1m c c c cm1 m1 m1 m1 c c c cmmmmmmmm 成本成本成本成本 c cij ij分配问题分配问题（Assignment Problem）的数学模型的数学模型9293匈牙利法匈牙利法 1955 1955年，年，库恩库恩利用匈牙利数学家利用匈牙利数学家康尼格康尼格的关于矩阵中独的关于矩阵中独立零元素的定理，提出了解分配问题的一种算法，习惯上称立零元素的定理，提出了解分配问题的一种算法，习惯上称之为匈牙利法。之为匈牙利法。匈牙利法的关键是利用了分配问题最优解的下列性质：匈牙利法的关键是利用了分配问题最优解的下列性质：若从分配问题的系数矩阵（若从分配问题的系数矩阵（称为效率矩阵称为效率矩阵）的）的某行（或某列）某行（或某列）的各元素分别减去一个常数的各元素分别减去一个常数k k，得到一个新的矩阵，则以新，得到一个新的矩阵，则以新矩阵为系数矩阵的分配问题与原分配问题的最优解相同矩阵为系数矩阵的分配问题与原分配问题的最优解相同。因。因为系数矩阵的这种变化并不影响到数学模型的约束方程组，为系数矩阵的这种变化并不影响到数学模型的约束方程组，而只是使目标函数减少了常数而只是使目标函数减少了常数k k,所以最优解不发生变化。所以最优解不发生变化。94变换效率矩阵变换效率矩阵 确定独立零元素确定独立零元素是否有是否有m m个个独立零元素独立零元素NY未划去零元素未划去零元素是否构成闭回路是否构成闭回路每行减去本行最小元素每行减去本行最小元素每列减去本列最小元素每列减去本列最小元素从从“行行”找，找，“列列”画线画线从从“列列”找，找，“行行”画线画线Y最优解最优解间间隔隔指指派派沿沿闭闭回回路路N找到未被直线覆盖最找到未被直线覆盖最小元素小元素k k，画线的行，画线的行U Ui i=0=0，否则，否则U Ui i=k=k,画线画线的列的列v vj j=-k=-k，否则，否则v vj j=0=0匈牙利法计算步骤匈牙利法计算步骤:每一元素分别每一元素分别减去减去U Ui i和和v vj j95ex4.2 ex4.2 有一份说明书要分别翻译成英、日、德、俄四种文字，有一份说明书要分别翻译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成。因个人专业不同，他们完交给甲、乙、丙、丁四个人去完成。因个人专业不同，他们完成不同文字的翻译所需的时间如表成不同文字的翻译所需的时间如表4-14-1所示，应如何分配翻译所示，应如何分配翻译任务，使这四个人分别完成四项任务总的时间为最小。任务，使这四个人分别完成四项任务总的时间为最小。甲甲甲甲乙乙乙乙丙丙丙丙丁丁丁丁译成英文译成英文译成英文译成英文译成日文译成日文译成日文译成日文译成德文译成德文译成德文译成德文译成俄文译成俄文译成俄文译成俄文2 2151513134 410104 4141415159 91414161613137 78 811119 9表表表表4-14-1 人人工作工作96一般的分配问题一般的分配问题（1 1）人数人数和和事数事数不等的问题不等的问题 人少事多，一人只做一件事人少事多，一人只做一件事：添上一些：添上一些虚拟的人虚拟的人，这些虚，这些虚拟人完成各事的拟人完成各事的费用系数为费用系数为0 0，即这些费用不会发生的。，即这些费用不会发生的。人少事多，事情必须全部完成人少事多，事情必须全部完成：意味着某些人要完成若干：意味着某些人要完成若干件事情，则可将件事情，则可将该人化作相同的几个人该人化作相同的几个人来接受指派，这几个来接受指派，这几个“相同的人相同的人”做同一件事的费用系数当然也相同。做同一件事的费用系数当然也相同。人多事少人多事少：添上一些：添上一些虚拟的事虚拟的事，当然完成虚拟事的费用为，当然完成虚拟事的费用为0 0。97（2 2）某事不能由某人