管理运筹学I(本科)课件

1、管理运筹学I(本科)1 管 理 运 筹 学 2管理运筹学I(本科) 3管理运筹学I(本科) 4管理运筹学I(本科) 5管理运筹学I(本科) 解解 设分别生产设分别生产、产品数量为产品数量为x1、x2 则利润则利润 Z=2x1+3x2,考虑到设备的生产能力则应受到以下条考虑到设备的生产能力则应受到以下条 件的限制使得件的限制使得 2x1+2x212 x1 +2x28 4x1 16 4x2 12 x1，x2 0 利润目标为max z=2x1+3x2 A 设备生产能力约束 B 设备生产能力约 束 C、D 设备生产能力 约束 现实问题变量非负 Z=2x1 +3x2 max 6管理运筹学I(本科) 线性

2、规划模型三要素线性规划模型三要素 决策变量（决策变量（variable）：指决策者为实现规：指决策者为实现规 划目标采取的方案、措施，是问题中要确划目标采取的方案、措施，是问题中要确 定的未知量。定的未知量。 目标函数（目标函数（objective）：问题要达到的目的要求。：问题要达到的目的要求。 约束条件约束条件(constrains)：决策变量取值时受到的：决策变量取值时受到的 各种资源的限制。各种资源的限制。 目标函数和约束条件皆为决策变量的目标函数和约束条件皆为决策变量的线性函数线性函数 7管理运筹学I(本科) 线性规划数学模型的几种形式 目标函数：max（min）z=c1x1 +c2

3、x2 + +cnxn a11x1 +a12 x2+ +a1n xn(,=)b1 a21x1 +a22 x2+ +a2n xn (,=)b2 am1x1 +am2 x2+ +amn xn(,=)bm x1 ,x2 ,xn 0 . 约束条件s.t. 简简 写写 形形 式式 10 1 1 1 n) (j x m) (i)b,(xa . t . s xc)zmin(max j n j ijij n j jj 8管理运筹学I(本科) 矩矩 阵阵 形形 式式 b b b b a a a P x x x XcccC 0X b),(xP s.t. CXz)min(max m 2 1 mj 2j 1j j n

4、2 1 n21 n 1j jj 向向 量量 形形 式式 aaa aaa aaa A 0X )b,(AX s.t. CXz)min(max mnm2m1 2n2221 1n1211 9管理运筹学I(本科) 标准形式标准形式： 0X bAXs.t. CXz max 非标准形式如何转化？非标准形式如何转化？ 目标函数为求极小值目标函数为求极小值 约束条件为不等约束条件为不等 式式 变量取值无约束变量取值无约束 目标函数求最大值目标函数求最大值 约束条件取等式约束条件取等式 变量非负变量非负 ex1.2 取取值值无无约约束束， 321 321 321 321 321 x0 x, 0 x 63x2x3x

5、 42xx3x 9xx2x s.t. 3x2xxminz 10管理运筹学I(本科) 建立坐标系建立坐标系 图示约束条件，确定满足约束的解的范围图示约束条件，确定满足约束的解的范围 画出目标函数直线画出目标函数直线 族族 确定最优解确定最优解 11管理运筹学I(本科) 可行域可行域 目标函数等值线目标函数等值线 最优解 6 4 -8 6 0 x1 x2 12 12 12 12 ex1.3 maxzx3x xx6 s.t. -x2x8 x ,x0 12管理运筹学I(本科) 0 xx 155x 164x 122x2x ts 2x2xzmax ex1.4 21 2 1 21 21 ， . 0 xx 1

6、64x 122x2x ts 3x2xzmax ex1.5 21 1 21 21 ， . 0 xx 142xx 122x2x ts 3x2xzmax ex1.6 21 21 21 21 ， . 唯一最优解（交于一点）唯一最优解（交于一点） 无穷多个最优解（交于一条线段）无穷多个最优解（交于一条线段） 无解（无可行域）无解（无可行域） 无界解无界解 13管理运筹学I(本科) 解的概念解的概念 可行解可行解：满足约束条件的解：满足约束条件的解X=X=（x x1, 1, , x , xn n）T T称为线性规称为线性规 划问题的可行解。划问题的可行解。 可行域可行域：可行解的集合。：可行解的集合。 0

7、 . X bAXts CXzmax 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。 基基：若：若A A为约束方程组的为约束方程组的mn阶系数矩阵，阶系数矩阵，R（A）= m, B是是A的的mm阶满秩子矩阵，则称阶满秩子矩阵，则称B为线性规划问题的一为线性规划问题的一 个基。个基。为为一一个个基基，则则且且B0BAB,m)A(R mmnm 14管理运筹学I(本科) 基向量基向量：B B中的每一个列向量中的每一个列向量p pj j称为基向量。称为基向量。 m1 ppB 不不妨妨令令 基变量基变量：基向量：基向量p pj j对应的变量对应的变量x xj j称为基变量。称

8、为基变量。 基解基解：在约束方程组：在约束方程组 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 B X 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，

9、 0 0 ）T T，称，称X X为线性规划问题的基解。为线性规划问题的基解。 基可行解基可行解：若基解：若基解X0X0，则，则X X为基可行解。为基可行解。 可行基可行基：对应于基可行解的基称为可行基。：对应于基可行解的基称为可行基。 m n C 基基解解的的总总数数 15管理运筹学I(本科) ex1.7 ex1.7 找出下列线性规划问题的基解、基可行解找出下列线性规划问题的基解、基可行解 51j,0 x 4xx 10 x2xx 5xx . t . s x3x2xzmax j 52 421 31 321 10010 01021 00101 A 16管理运筹学I(本科) 凸集及其顶点凸集及其顶点

10、 凸集凸集 不是凸集 顶点顶点 凸集凸集：如果集合：如果集合C C上任意两个点上任意两个点X X1 1、X X2 2，其连线上的所有点都，其连线上的所有点都 在集合在集合C C上，则上，则C C是凸集。是凸集。 是凸集则C10Cx1x Cxx 2 121 ,)(, 的的定定点点是是凸凸集集则则称称 不不存存在在对对任任何何 Cx C,x)1(xxC,x,Cx 2121 顶点顶点: : 17管理运筹学I(本科) 基本定理基本定理 定理定理1 1：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，则问题的可行域是凸集。 引理引理1 1：线性规划问题的可行解：线性规划问题的

11、可行解X=X=（x x1 1,x,xn n）T T为基可行解的充为基可行解的充 分必要条件是分必要条件是X X的正分量所对应的系数列向量是线性无关的。的正分量所对应的系数列向量是线性无关的。 定理定理2 2：线性规划问题的基可行解：线性规划问题的基可行解X X对应线性规划问题可行域对应线性规划问题可行域 （凸集）的顶点。（凸集）的顶点。 定理定理3 3：若线性规划问题有最优解，一定存在一个基可行解是最：若线性规划问题有最优解，一定存在一个基可行解是最 优解。优解。 推论推论：若线性规划问题有最优解，至少在可行域的一个顶点取：若线性规划问题有最优解，至少在可行域的一个顶点取 得最优。得最优。 1

12、8管理运筹学I(本科) 单纯形法计算步骤：单纯形法计算步骤： 化为标准型化为标准型 求初始基可行解，求初始基可行解， 列出初始单纯形表列出初始单纯形表 最优性检验最优性检验 从一个基可行解转换从一个基可行解转换 到相邻的基可行解到相邻的基可行解 迭迭 代代 19管理运筹学I(本科) 单纯形表单纯形表 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 1 c c2 2 x x2 2 b b2 2 : : : : : : : : : : c cm m x x

13、m m b bm m c cB B 基基 b b 1 1 0 0 0 0 a a1j 1j a a1n 1n 0 0 1 1 0 0 a a2j 2j a a2n 2n : : : : : : : : : : : : : : : : : : : : 0 0 0 0 1 1 a amj mj a amj mj c cj j - - z zj j0 0 0 0 0 0 m 1i ijij acc m i inin acc 1 20管理运筹学I(本科) ex1.8 ex1.8 用单纯性法求解下列线性规划问题用单纯性法求解下列线性规划问题 0 x,x 124x 164x 82xx 122x2x . t

14、 . s 3x2xzmax 21 2 1 21 21 21 21管理运筹学I(本科) 0 x,x 5xx 242x6x 155x . t . s x2xzmax 21 21 21 2 21 ex1.9 ex1.9 用单纯性法求解下列线性规划问题用单纯性法求解下列线性规划问题 22管理运筹学I(本科) 0 x,x,x 9x3x 1xx2x- 4xxx . t . s x-3xzmax 321 32 321 321 31 人工变量法人工变量法 23管理运筹学I(本科) 化为标准型：化为标准型： 71j0,x 9xx3x 1xxxx2x- 4xxxx . t . s MxMxx-3xzmax j 7

15、32 65321 4321 7631 添加人工变量添加人工变量x x6 6、x x7 7： 0 x,x,x,x,x 9x3x 1xxx2x- 4xxxx .t .s x-3xzmax 54321 32 5321 4321 31 24管理运筹学I(本科) 两阶段法两阶段法 第一阶段：第一阶段： 71j0,x 9xx3x 1xxxx2x- 4xxxx . t . s xxmin j 732 65321 4321 76 求解一个目标函数中只包含人工变量的线性规划模型求解一个目标函数中只包含人工变量的线性规划模型 第二阶段：第二阶段： 若第一阶段的模型目标函数值为若第一阶段的模型目标函数值为0,则原问

16、题有可行解。则原问题有可行解。 25管理运筹学I(本科) 解的判别：解的判别： 唯一最优解唯一最优解 基变量不含人工变量基变量不含人工变量 所有的检验数所有的检验数 0 0 所有的所有的非基变量非基变量的检验数的检验数 0=700 X1+0.5X2+0.2X3+2X4+0.5X5=30 0.5X1+X2+0.2X3+2X4+0.8X5=100 END LINDO 输入输入 文件：文件： LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 32.43590 VARIABLE VALUE REDUCED COST X1 0.000000 0

17、.059615 X2 0.000000 0.593590 X3 0.000000 0.352564 X4 39.743591 0.000000 X5 25.641026 0.000000 LINDO 输出输出 文件：文件： 31管理运筹学I(本科) Ex1.11 Ex1.11 某糖果厂用原料某糖果厂用原料A A、B B、C C加工成三种不同牌号的加工成三种不同牌号的 糖果甲、乙、丙，已知各种牌号糖果中糖果甲、乙、丙，已知各种牌号糖果中A A、B B、C C含量、原料含量、原料 成本、各种原料的每月限用量，三种牌号糖果的单位加工费成本、各种原料的每月限用量，三种牌号糖果的单位加工费 及售价如下表

18、所示，问该厂每月生产这三种糖果各多少千克，及售价如下表所示，问该厂每月生产这三种糖果各多少千克， 使该厂获利最大，建立此问题的数学模型并求解。使该厂获利最大，建立此问题的数学模型并求解。 甲甲 乙乙 丙丙 原料成本原料成本 每月限用量每月限用量 （元（元/kg） (kg) A 60% 30% 2.00 2000 B 1.50 2500 C 20% 50% 60% 1.00 1200 加工费加工费 （元（元/kg） 售价售价 （元（元/kg） 3.40 2.85 2.25 0.5 0.4 0.3 32管理运筹学I(本科) MAX (3.40-0.5)(X11+X21+X31)+(2.85-0.4

19、)()+(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.95X33 ST X11+X12+X13=2000 X21+X22+X23 =2500 X31+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 原始模型：原始模型：

20、33管理运筹学I(本科) MAX 0.9X11+1.4X21+1.9X31+0.45X12+0.95X22+1.45X32- 0.05X13+0.45X23+0.95X33 ST X11+X12+X13=2000 X21+X22+X23 =2500 X31+X32+X33=0 X31-0.2X11-0.2X21-0.2X31=0 X32-0.5X12-0.5X22-0.5X32=0 X33-0.6X13-0.6X23-0.6X330） ,则该约束条件取严格等式；反则该约束条件取严格等式；反 之如果约束条件取严格不等式，则其对应的对偶变量一定之如果约束条件取严格不等式，则其对应的对偶变量一定 为

21、零。为零。 0 x c y a c y a 0, x 0 y b x a b x a 0, y j m 1i jiij m 1i jiijj i n 1j ijij n 1j ijiji ，则则若若 则则若若 ，则则若若 则则若若 50管理运筹学I(本科) ex 2.3 已知线性规划问题： 41j0 x 9xxx 6xxx 6x2x 8x3xx s.t. xx4x2xzmax j 321 432 21 421 4321 ， 要求要求：（：（1 1）写出其对偶问题；（写出其对偶问题；（2 2）已知原问题最优解为）已知原问题最优解为 X X* *= =（2 2，2 2，4 4，0 0），试根据对偶

22、理论，直接求出对偶问题），试根据对偶理论，直接求出对偶问题 的最优解。的最优解。 51管理运筹学I(本科) （6）基解的互补性基解的互补性 和和变量的对应关系变量的对应关系： 线性规划问题原问题和对偶问题之间存在一对线性规划问题原问题和对偶问题之间存在一对 互补的基解，其中原问题的松弛变量对应于对偶问互补的基解，其中原问题的松弛变量对应于对偶问 题的变量，对偶问题的剩余变量对应原问题的变量，题的变量，对偶问题的剩余变量对应原问题的变量， 这些互相对应的变量如果在一个问题的解中是基变这些互相对应的变量如果在一个问题的解中是基变 量，则在另一个问题的解中是非基变量。将这对互量，则在另一个问题的解中

23、是非基变量。将这对互 补的基解分别代入原问题和对偶问题的目标函数中，补的基解分别代入原问题和对偶问题的目标函数中， 有有z=. 52管理运筹学I(本科) 0yyy 35y2y 24y2y s.t. 15y16y12ymin 321 31 21 321 ,， 0 xx 155x 164x 122x2x s.t. 3x2xmaxz 21 2 1 21 21 , LP1 LP2 y1 对应对应 x3 y2 对应对应x4 y3对应对应x5 x1对应对应y4 x2对应对应y5 53管理运筹学I(本科) LP1的最终单纯行表：的最终单纯行表： LP2的最终单纯行表的最终单纯行表 54管理运筹学I(本科)

24、m 1i ii n 1j jj ybxcz b bi i 是线性规划问题约束的右端项，代表第 是线性规划问题约束的右端项，代表第i i种资源种资源 的拥有量的拥有量 。而对偶变量。而对偶变量 y yi i 的意义代表对一个单位第 的意义代表对一个单位第i i 种资源的估价，这种估价不是资源的市场价格，是根种资源的估价，这种估价不是资源的市场价格，是根 据资源在生产中做出的贡献而作的估价，称之为影子据资源在生产中做出的贡献而作的估价，称之为影子 价格。价格。 55管理运筹学I(本科) （1）影子价格与市场价格的区别影子价格与市场价格的区别： 市场价格是已知数，相对比较稳定，而它的影市场价格是已知

25、数，相对比较稳定，而它的影 子价格则有赖于资源的利用情况，是未知数。由于子价格则有赖于资源的利用情况，是未知数。由于 企业生产任务、产品结构等情况发生变化，资源的企业生产任务、产品结构等情况发生变化，资源的 影子价格随之改变。影子价格随之改变。 56管理运筹学I(本科) （2）影子价格影子价格 是一种边际价格是一种边际价格 的的增增量量函函数数每每增增加加一一个个单单位位时时目目标标 产产条条件件下下，的的值值相相对对于于在在给给定定的的生生 求求偏偏导导：对对 zb yy b z bz i ii i i , 0 xx 155x 164x 122x2x s.t. 3x2xmaxz ex2.4

26、21 2 1 21 21 , 57管理运筹学I(本科) （3）资源的影子价格又资源的影子价格又 是一种机会成本是一种机会成本 在纯市场经济条件下，在在纯市场经济条件下，在ex2.4中，当第中，当第3种资源种资源 的市场价格低于的市场价格低于1/5时，可以买进这种资源；当市场时，可以买进这种资源；当市场 价格高于影子价格时，就会卖出这种资源。影子价价格高于影子价格时，就会卖出这种资源。影子价 格最终会与市场价格处于同等水平。格最终会与市场价格处于同等水平。 58管理运筹学I(本科) （4）互补松弛性的经济含义互补松弛性的经济含义 则影子价格为零。 未得到充分利用，生产过程如果某种资源 ，则若 i

27、 i n 1j ijij b 0 y b x a 利用。表明该资源已得到充分当影子价格不为零时， 则若 n 1j ijiji b x a 0, y 59管理运筹学I(本科) （5）检验数的经济意义检验数的经济意义 m 1i iijjj 1 Bjj yacpBCc c cj j 代表第代表第j j种产品的产值，种产品的产值， 是生产该种产品是生产该种产品 所消耗各项资源影子价格的总和，即产品的隐含成所消耗各项资源影子价格的总和，即产品的隐含成 本。当产品的产值大于成本时，生产该产品有利可本。当产品的产值大于成本时，生产该产品有利可 图，应安排该种产品（检验数大于零的变量作为进图，应安排该种产品（

28、检验数大于零的变量作为进 基变量）。基变量）。 m 1i iijy a 60管理运筹学I(本科) （6）资源影子价格的应用资源影子价格的应用 对线性规划的求解是确定资源的最有效分配方案，对线性规划的求解是确定资源的最有效分配方案， 而对其对偶问题的求解则是确定资源的恰当估价，这而对其对偶问题的求解则是确定资源的恰当估价，这 种估价直接涉及到资源的最有效利用。种估价直接涉及到资源的最有效利用。 资源的影子价格可以作为资源的影子价格可以作为公司内部的结算价格公司内部的结算价格； 社会上可对一些最紧缺的资源，借助影子价格规定使社会上可对一些最紧缺的资源，借助影子价格规定使 用这种资源一单位时必须上交

29、的利润额，以控制某些用这种资源一单位时必须上交的利润额，以控制某些 公司超低成本使用社会资源，侵蚀公众福利。公司超低成本使用社会资源，侵蚀公众福利。 61管理运筹学I(本科) 0 x,xxx 34x2x2x 24xx2x s.t. 12x16x8x12xminz ex2.5 4321 421 321 4321 ， 列列线线性性规规划划用用对对偶偶单单纯纯行行法法求求解解下下 62管理运筹学I(本科) 灵敏度分析灵敏度分析：对系统或事物因周围条件变化显示：对系统或事物因周围条件变化显示 出来的敏感程度的分析。出来的敏感程度的分析。 10 1 1 1 n) (j x m) (ibxa . t .

30、s xczmax j n j ijij n j jj 63管理运筹学I(本科) 灵敏度分析的步骤灵敏度分析的步骤 （1）将参数的改变计算反映到最终的单纯形表上将参数的改变计算反映到最终的单纯形表上 i 1 i 1 PBP bBb * * （2）检查原问题是否仍为可行解检查原问题是否仍为可行解 （3）检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解 64管理运筹学I(本科) （3）检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解 （4）按下表所列情况得出结论和决定继续计算步骤按下表所列情况得出结论和决定继续计算步骤 65管理运筹学I(本科) 该该问问题题的的最最优优解解不不变变？ ，分分

31、别别在在什什么么范范围围内内变变化化、试试分分析析 ）（）（ 已已知知线线性性规规划划问问题题： 21 21 2 1 21 2211 0 xx 155x 164x 122x2x s.t. x3x2maxz ex2.6 , 分析分析cj变化的影响变化的影响 66管理运筹学I(本科) 该该问问题题的的最最优优基基不不变变？ 在在什什么么范范围围内内变变化化，、分分别别分分析析 线线性性规规划划问问题题： 321 21 32 21 121 21 0 xx 155x 164x 122x2x s.t. 3x2xmaxz ex2.7 , 分析分析bi的变化范围变化范围 67管理运筹学I(本科) 增加一个变

32、量的分析增加一个变量的分析 增加一个变量的分析在实际问题中反映为增加一种新产品。增加一个变量的分析在实际问题中反映为增加一种新产品。 ex 2.7 ex 2.7 现在该公司计划增加一种新产品现在该公司计划增加一种新产品x x6 6，已知该，已知该 产品单位利润为产品单位利润为4 4元元，p p6 6=(2 4 5)=(2 4 5)T T，原有条件不变，原有条件不变， 试分析该公司是否生产这种新产品？试分析该公司是否生产这种新产品？ 68管理运筹学I(本科) 增加一个约束条件的分析增加一个约束条件的分析 增加一个约束条件的分析在实际问题中反映为增加一道增加一个约束条件的分析在实际问题中反映为增加

33、一道 工序或者增加一种资源限制。工序或者增加一种资源限制。 ex 2.8 ex 2.8 增加一个约束条件增加一个约束条件 3x3x1 1+2x+2x2 21414，要求分析，要求分析 最优解变化。最优解变化。 69管理运筹学I(本科) 70管理运筹学I(本科) ex3.1ex3.1 某食品公司经销的主要产品之一就是糖果，其下属三个生某食品公司经销的主要产品之一就是糖果，其下属三个生 产厂，该公司把这些糖果分别运往四个地区门市部销售，已知各产厂，该公司把这些糖果分别运往四个地区门市部销售，已知各 加工厂产量、各门市部销售量及从每个加工厂到各销售门市部每加工厂产量、各门市部销售量及从每个加工厂到各

34、销售门市部每 吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各吨糖果的运价如下表所示，问该食品公司应如何调运，在满足各 门市部需求量的情况下，使总的运费支出为最小。门市部需求量的情况下，使总的运费支出为最小。 71管理运筹学I(本科) 一般运输问题的运输表一般运输问题的运输表 72管理运筹学I(本科) ij m 1i n 1j ij jiij xcz min z BAx 目目标标函函数数为为 ，则则总总的的运运输输费费用用为为 的的运运输输量量到到销销地地表表示示从从产产地地解解：设设 0 x n1jbx m1iax ts ij m 1i jij n 1j iij )( )( . 73

35、管理运筹学I(本科) 则则为为产产销销平平衡衡运运输输问问题题即即： ，若若总总产产量量等等于于总总需需求求量量 ,ba n 1j j m 1i i 0 x n1jbx m1iax ts xcminz ij m 1i jij n 1j iij m 1i n 1j ijij )( )( . 74管理运筹学I(本科) 分析实际问题列出产销分析实际问题列出产销 平衡表及单位运价表平衡表及单位运价表 确定初始调运方案确定初始调运方案 （最小元素法最小元素法ororVogelVogel法法） 求检验数求检验数 （闭回路法闭回路法or or 位势法位势法） 找出绝对值最大的负检验数，闭找出绝对值最大的负检

36、验数，闭 回路法调整，得出新的调运方案回路法调整，得出新的调运方案 所有检验数所有检验数00 是是 否否 得到最优方案得到最优方案 算出总的运费算出总的运费 迭代迭代 75管理运筹学I(本科) 表表3-1 表上作业法计算表上作业法计算 76管理运筹学I(本科) 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，又知各产

37、销地之间的单位运价如下表，又知各产销地之间的单位运价如下表， 试决定总运费最小的调运方案。试决定总运费最小的调运方案。 处理产销不平衡的思路：转化为产销平衡问题 77管理运筹学I(本科) 78管理运筹学I(本科) ex3.3ex3.3 设有三个化肥厂供应四个地区的农用化肥。假定等量设有三个化肥厂供应四个地区的农用化肥。假定等量 的化肥在这些地区使用效果相同，已知各化肥厂年产量，各的化肥在这些地区使用效果相同，已知各化肥厂年产量，各 地区需要量及从各化肥厂到各地区单位化肥的运价如表地区需要量及从各化肥厂到各地区单位化肥的运价如表3-33-3所所 示，试决定使总的运费最节省的化肥调拨方案。示，试决

38、定使总的运费最节省的化肥调拨方案。 79管理运筹学I(本科) 80管理运筹学I(本科) ex3.4ex3.4 江南厂按照合同要求需于每个季度末分别完成江南厂按照合同要求需于每个季度末分别完成1010、1515、 2525、2020台同一规格的柴油机。已知该厂每个季度生产能力及台同一规格的柴油机。已知该厂每个季度生产能力及 生产每台柴油机的成本如表生产每台柴油机的成本如表3-43-4所示，又如果生产的柴油机当所示，又如果生产的柴油机当 季不交货，每台每积压一个季度需储存、维护费用季不交货，每台每积压一个季度需储存、维护费用0.150.15万元。万元。 要求在完成合同的条件下，制订使该厂全年生产、

39、储存和维要求在完成合同的条件下，制订使该厂全年生产、储存和维 护费用为最小的决策方案。护费用为最小的决策方案。 81管理运筹学I(本科) ex3.5 ex3.5 东海造船厂根据合同要在当年算起的连续三年年末各东海造船厂根据合同要在当年算起的连续三年年末各 提供三条规格相同的大型货轮。已知该厂今后三年的生产能提供三条规格相同的大型货轮。已知该厂今后三年的生产能 力及生产成本如表力及生产成本如表3-53-5所示。所示。 已知加班生产情况下每条货轮成本比正产生产时多出已知加班生产情况下每条货轮成本比正产生产时多出7070 万元万元，又知造出的货轮如当年不交货，每条货轮，又知造出的货轮如当年不交货，每

40、条货轮每每积压一年积压一年 将增加维护保养等费用为将增加维护保养等费用为4040万元万元。在签订合同时该厂已有两。在签订合同时该厂已有两 条条当年制造的当年制造的未交货的积压货轮。该厂希望在第三年年末在未交货的积压货轮。该厂希望在第三年年末在 交完合同任务后能储存一条备用。问该厂应该如何生产计划，交完合同任务后能储存一条备用。问该厂应该如何生产计划， 使在满足上述要求的条件下，使总的费用支出为最小？使在满足上述要求的条件下，使总的费用支出为最小？ 82管理运筹学I(本科) 83管理运筹学I(本科) ex3.6 ex3.6 东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生东兴煤炭公司下属吉祥、平安

41、、双福三个煤矿，年生 产能力分别为产能力分别为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。 城

42、市城市 煤矿煤矿 84管理运筹学I(本科) 85管理运筹学I(本科) 整数规划整数规划：要求一部分或全部决策变量必须取整数：要求一部分或全部决策变量必须取整数 的规划问题（的规划问题（整数线性规划整数线性规划）。）。 12 12 12 12 maxz3x2x 2x3x14 s.t.x0.5x4.5 x , x 自 然 数 整数规划的定义和分类整数规划的定义和分类 86管理运筹学I(本科) 纯整数规划纯整数规划：全部决策变量取整数的线性规划。：全部决策变量取整数的线性规划。 混合整数规划混合整数规划：只要求一部分决策变量取整数的线：只要求一部分决策变量取整数的线 性规划问题。性规划问题。 0-1

43、规划规划：要求决策变量取：要求决策变量取0或或1逻辑值的规划问题。逻辑值的规划问题。 87管理运筹学I(本科) 逻辑变量在建模中的用法逻辑变量在建模中的用法 （1 1） m m个约束条件中只有个约束条件中只有k k个起作用个起作用 )m1i (bxam i n 1j jij 个个条条件件为为：设设 个个约约束束条条件件起起作作用用，假假定定第第 个个约约束束条条件件不不起起作作用用假假定定第第 引引进进逻逻辑辑变变量量 i0 i, 1 y i kmyyy Mybxa M i21 n 1j iijij 为为任任意意大大的的正正数数，则则又又 88管理运筹学I(本科) （2 2） 约束条件的右端项

44、可能是约束条件的右端项可能是r r个值中的某一个个值中的某一个 r21 n 1j jij bbbxa或或或或或或 ）（ ，否否则则 假假定定右右端端项项为为 引引进进逻逻辑辑变变量量r1i 0 b, 1 y i i 1yyy ybxa r21 n 1j r 1i iijij 89管理运筹学I(本科) （3 3） 两组条件满足其中一组两组条件满足其中一组 3x,4x;1x4,x 2121 ）否否则则（即即则则若若 ），（ 组组条条件件起起作作用用，第第 组组条条件件不不起起作作用用第第 令令21i i0 i,1 y i 1yy My3x My4x My1x My4x M 21 22 21 12

45、11 为为任任意意大大的的正正数数又又 90管理运筹学I(本科) （4 4） 用以表示含固定费用的函数用以表示含固定费用的函数 无无关关的的生生产产准准备备费费用用（固固定定费费用用）是是同同产产量量 函函数数：的的生生产产量量，其其生生产产费费用用表表示示产产品品 j j jjjj jj j K 0)(x0, )0 x( ,xcK )x(C jx 0 x0 0 x,1 y j j j ， 令令逻逻辑辑变变量量 10y y Mx0 s.t. )yKx(cminz j jj n 1j jjjj 或或 91管理运筹学I(本科) ex4.1 ex4.1 现有资金总额为现有资金总额为B B，可供选择的

46、项目为，可供选择的项目为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恰好选择两个。恰好选择两个。 问应当如何选择投资项目，才能使总收益最大？试建问应当如何选择投资项目，才能使总收益最大？试建 立此问题的数学模型。立此问题的数学模型。 92管理运筹学I(

47、本科) m m件任务分别由件任务分别由m m个人完成，已知第个人完成，已知第j j（j=1j=1m）个人）个人 完成第完成第i i （i=1i=1m）件任务的成本费用为）件任务的成本费用为c cij ij，问应如何分配 ，问应如何分配 任务可使总费用最小。任务可使总费用最小。 分配问题分配问题（Assignment Problem）的数学模型的数学模型 93管理运筹学I(本科) m 1i ij m 1j ij m 1i m 1j ijij )m1j(1x )m1i (1x . t . s xcminz ，否否则则 个个人人完完成成件件任任务务由由第第，第第 0 ji1 x ij 94管理运筹学

48、I(本科) 匈牙利法匈牙利法 1955 1955年，年，库恩库恩利用匈牙利数学家利用匈牙利数学家康尼格康尼格的关于矩阵中独的关于矩阵中独 立零元素的定理，提出了解分配问题的一种算法，习惯上称立零元素的定理，提出了解分配问题的一种算法，习惯上称 之为匈牙利法。之为匈牙利法。 匈牙利法的关键是利用了分配问题最优解的下列性质：匈牙利法的关键是利用了分配问题最优解的下列性质： 若从分配问题的系数矩阵（若从分配问题的系数矩阵（称为效率矩阵称为效率矩阵）的）的某行（或某列）某行（或某列） 的各元素分别减去一个常数的各元素分别减去一个常数k k ，得到一个新的矩阵，则以新，得到一个新的矩阵，则以新 矩阵为系

49、数矩阵的分配问题与原分配问题的最优解相同矩阵为系数矩阵的分配问题与原分配问题的最优解相同。因。因 为系数矩阵的这种变化并不影响到数学模型的约束方程组，为系数矩阵的这种变化并不影响到数学模型的约束方程组， 而只是使目标函数减少了常数而只是使目标函数减少了常数k k, ,所以最优解不发生变化。所以最优解不发生变化。 95管理运筹学I(本科) 变换效率矩阵变换效率矩阵 确定独立零元素确定独立零元素 是否有是否有m m个个 独立零元素独立零元素 N Y 未划去零元素未划去零元素 是否构成闭回路是否构成闭回路 每行减去本行最小元素每行减去本行最小元素 每列减去本列最小元素每列减去本列最小元素 从从“行行

50、”找，找，“列列”画线画线 从从“列列”找，找，“行行”画线画线 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 j 96管理运筹学I(本科) ex4.2 ex4.2 有一份说明书要分别翻译成英、日、德、俄四种文字，有一份说明书要分别翻译成英、日、德、俄四种文字， 交给甲、乙

51、、丙、丁四个人去完成。因个人专业不同，他们交给甲、乙、丙、丁四个人去完成。因个人专业不同，他们 完成不同文字的翻译所需的时间如表完成不同文字的翻译所需的时间如表4-14-1所示，应如何分配翻所示，应如何分配翻 译任务，使这四个人分别完成四项任务总的时间为最小。译任务，使这四个人分别完成四项任务总的时间为最小。 人人 工作工作 97管理运筹学I(本科) 一般的分配问题一般的分配问题 （1 1） 人数人数和和事数事数不等的问题不等的问题 人少事多，一人只做一件事人少事多，一人只做一件事：添上一些：添上一些虚拟的人虚拟的人，这些，这些 虚拟人完成各事的虚拟人完成各事的费用系数为费用系数为0 0，即这

52、些费用不会发生的。，即这些费用不会发生的。 人少事多，事情必须全部完成人少事多，事情必须全部完成：意味着某些人要完成若：意味着某些人要完成若 干件事情，则可将干件事情，则可将该人化作相同的几个人该人化作相同的几个人来接受指派，这几来接受指派，这几 个个“相同的人相同的人”做同一件事的费用系数当然也相同。做同一件事的费用系数当然也相同。 人多事少人多事少：添上一些：添上一些虚拟的事虚拟的事，当然完成虚拟事的费用，当然完成虚拟事的费用 为为0 0。 98管理运筹学I(本科) （2 2） 某事不能由某人做的分配问题某事不能由某人做的分配问题 若某件事一定不能由某个人来做，则可将相应的费用系若某件事一

53、定不能由某个人来做，则可将相应的费用系 数取数取任意大的系数任意大的系数 M M 即可。即可。 （3 3） 最大化分配问题最大化分配问题 目标函数是求最大值，按照下列方法转化为最小分配问目标函数是求最大值，按照下列方法转化为最小分配问 题题: :找出找出效率矩阵效率矩阵B B中最大的元素中最大的元素 m m，用用m m 分别减去原效率矩分别减去原效率矩 阵阵 B B 的每一个元素，得出新的效率矩阵的每一个元素，得出新的效率矩阵 C,C,则以则以C C为效率矩为效率矩 阵的最小化分配问题和以阵的最小化分配问题和以B B为效率矩阵的最大化分配问题最为效率矩阵的最大化分配问题最 优解相同，求解优解相

54、同，求解C C 。 99管理运筹学I(本科) 100管理运筹学I(本科) ex4.3 ex4.3 某商业公司计划开办某商业公司计划开办5 5家新商店，为了尽早建成营业，家新商店，为了尽早建成营业， 商业公司决定由商业公司决定由5 5家建筑公司分别承建，已知建筑公司家建筑公司分别承建，已知建筑公司A Ai i （i=15i=15）对新商店）对新商店B Bi i（i=15i=15）的建造费用的报价是）的建造费用的报价是c cij ij， ， 见表见表4-34-3，商业公司如何来分配建造任务，才能使总的建造费，商业公司如何来分配建造任务，才能使总的建造费 用最少？用最少？ 建筑商建筑商 商店商店 报

55、价报价 101管理运筹学I(本科) ex4.4 ex4.4 对于对于ex4.2ex4.2中的分配问题，为了保证工程质量，经研究中的分配问题，为了保证工程质量，经研究 决定，舍弃建筑公司决定，舍弃建筑公司A A4 4和和A A5 5，而让技术力量相对较强的建筑公，而让技术力量相对较强的建筑公 司司A A1 1 、A A2 2 和 和A A3 3来承建。根据实际情况，可以允许每家建筑公司来承建。根据实际情况，可以允许每家建筑公司 承建一家或二家商店。求使总费用最少的指派方案。承建一家或二家商店。求使总费用最少的指派方案。 建筑商建筑商 商店商店 102管理运筹学I(本科) 且且取取整整数数0 x,

56、x 4.50.5xx 143x2x . t . s 2x3xmaxz ex4.5 21 21 21 21 0 x,x 4.50.5xx 143x2x . t . s 2x3xmaxz 21 21 21 21 松松弛弛问问题题： 103管理运筹学I(本科) 分枝定界法的思路和步骤分枝定界法的思路和步骤 （1 1）求解整数规划的松弛问题）求解整数规划的松弛问题 设整数规划问题为设整数规划问题为A A，它的松弛问题为，它的松弛问题为B B，则，则A A的可行域的可行域 是是B B 的可行域的子集的可行域的子集 。若。若B B无可行解则无可行解则A A无可行解；若无可行解；若B B的最的最 优解是优解

57、是A A的可行解（满足的可行解（满足A A整数要求），则也是整数要求），则也是A A的最优解；的最优解； 否则否则B B的最优解（不满足的最优解（不满足A A的整数要求）就是的整数要求）就是A A最优解的上界最优解的上界 （求极大时）或下界值（求极小时），转（求极大时）或下界值（求极小时），转（2 2）。）。 104管理运筹学I(本科) （2 2）分枝）分枝 对问题对问题B B，任选一个不符合整数要求的变量进行分枝。，任选一个不符合整数要求的变量进行分枝。 ）。解解这这两两个个子子问问题题，转转（从从而而形形成成两两个个子子问问题题。 和和 中中的的一一个个：分分别别增增加加下下边边约约束束条

58、条件件对对 的的最最大大整整数数，为为不不超超过过且且设设设设选选择择 3 1bxbx B bb,bx jjjj jjjj 105管理运筹学I(本科) （3 3）定界）定界 对对B B的子问题求最优解，若该解满足的子问题求最优解，若该解满足A A的约束，即找到了的约束，即找到了A A 的一个可行解，否则该解为所属分枝的边界值（求极大化时的一个可行解，否则该解为所属分枝的边界值（求极大化时 为上界，求极小化时为下界）。为上界，求极小化时为下界）。 若所有的子问题的最优解均非若所有的子问题的最优解均非A A的可行解，则选取其边界的可行解，则选取其边界 值最大（求极大值时）或最小（求极小值时）的子问

59、题进一值最大（求极大值时）或最小（求极小值时）的子问题进一 步细分子问题求解步细分子问题求解 分枝过程一直进行下去，直到找到分枝过程一直进行下去，直到找到A A的一个可行解为止。的一个可行解为止。 若计算时同时出现两个以上可行解，则选取其中最大（求极若计算时同时出现两个以上可行解，则选取其中最大（求极 大值时）或最小（求极小值时）的一个保留，转（大值时）或最小（求极小值时）的一个保留，转（4 4）。）。 106管理运筹学I(本科) （4 4）剪枝）剪枝 将各子问题的边界值与保留的可行解的值进行比较，把将各子问题的边界值与保留的可行解的值进行比较，把 边界值边界值劣于劣于可行解的分枝剪去。若除保

60、留下来的可行解外，可行解的分枝剪去。若除保留下来的可行解外， 其余分枝均被剪去，则该可行解就是其余分枝均被剪去，则该可行解就是A A的最优解；否则回到的最优解；否则回到 （2 2），选取边界值最优的一个继续分枝。），选取边界值最优的一个继续分枝。 若计算中又出现新的可行解，则与原可行解进行比较，若计算中又出现新的可行解，则与原可行解进行比较， 保留最优的，并重复上述步骤。保留最优的，并重复上述步骤。 107管理运筹学I(本科) L0 X1=3.25 X2=2.5 Z=14.75 L1 X1=3.5 X2=2 Z=14.5 L2 X1=2.5 X2=3 Z=13.5 L11 X1=3 X2=2