管理运筹学(修改稿6)

1、.开课前的话开课前的话 1.课程及参考书课程及参考书 课程名：运筹学课程名：运筹学 课程类别：专业基础课课程类别：专业基础课, 必修必修. 教材教材:韩伯棠编著韩伯棠编著,管理运筹学管理运筹学, 高等教育出版社高等教育出版社 参考书参考书: 1)钱颂迪主编钱颂迪主编,运筹学运筹学 清华大学出版社，清华大学出版社，1990年第年第2版版 2)韩大卫编著韩大卫编著,管理运筹学管理运筹学, 大连理工大学出版社大连理工大学出版社. 2.讲授学时与内容讲授学时与内容 1) 学时：学时：36 2) 讲授主要章节：第讲授主要章节：第2章，第章，第3章，章，第第4章；第章；第12章章; 第第13章章;第第16

2、章等。章等。另外还有另外还有1个案例。个案例。. 3.学习及考试要求：学习及考试要求： 本课程重在本课程重在36学时的学习，学了什么考什么，学时的学习，学了什么考什么，闭卷考试。故要求坚持听课；选择笔记；思考问闭卷考试。故要求坚持听课；选择笔记；思考问题；认真作业。题；认真作业。 4.最终成绩形成：最终成绩形成： 平时分平时分0.4期末考试分期末考试分0.6 + 回答问题分回答问题分 平时成绩：平时成绩： 1)考勤考勤20分。分。 2)案例分析案例分析20分。分。 期末考试：下学期考。考讲了的题目。期末考试：下学期考。考讲了的题目。.管理运筹学属于管理（优化）方法课程管理运筹学属于管理（优化）

3、方法课程应用分四步骤：应用分四步骤： 1.1.把实际问题抽象成运筹学把实际问题抽象成运筹学( (有关分支有关分支) )问问题；题； 2.2.建立运筹学建立运筹学( (有关分支有关分支) )问题模型；问题模型； 3.3.求解有关运筹学模型；求解有关运筹学模型； 4.4.利用模型和求解的数据进行利用模型和求解的数据进行决策决策分析，分析，达到优化目的。达到优化目的。第一章第一章 线性规划模型及图解法线性规划模型及图解法 1 1 线性规划问题模型线性规划问题模型 2 2 图解法图解法.1 1 线性规划问题模型线性规划问题模型 一、一、问题的提出问题的提出-引例引例 例例1.(20091.(2009高

4、考题高考题5 5分分) ) 在家电下乡活动中在家电下乡活动中, , 某厂要将某厂要将100100台洗衣机台洗衣机运到某乡镇运到某乡镇, , 现有现有4 4辆甲型货车和辆甲型货车和8 8辆乙型货车辆乙型货车可供使用可供使用, ,每辆甲型货车运费为每辆甲型货车运费为400400元元, , 可装可装2020台洗衣机台洗衣机, , 每辆乙型货车可装每辆乙型货车可装1010台洗衣机台洗衣机, , 运运费为费为300300元元, ,若每辆车至多可运一次若每辆车至多可运一次, ,则该厂所则该厂所花最小运费为花最小运费为: : A. 2000A. 2000元元 B. 2200B. 2200元元 C. 2400

5、C. 2400元元 D. 2800D. 2800元元. 解：设解：设y1辆辆为为使用甲型货车使用甲型货车，y2辆辆为为使用乙型货使用乙型货车车，则有则有 目标函数：目标函数： Min f =400y1+300y2 约束条件：约束条件： s.t. 20 y1 + 10 y2 100 y1 4 y2 8 y1 ，y20 这就是这就是例例1 的线性规划模型。的线性规划模型。. 例例2. 某工厂计划在某个月安排某工厂计划在某个月安排、两种产两种产品的生产，已知生产单位产品所需的设备台时及品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：两种原材料的消耗、资源的限制，

6、如下表： 问题：问题： 1）工厂应分别生产多少）工厂应分别生产多少、产品，才能使获总产品，才能使获总利润最多？利润最多？ . 2）若工厂不生产产品，改出售资源，应如何确定这三）若工厂不生产产品，改出售资源，应如何确定这三种资源的单位利润，使出售资源的总利润不低于出售种资源的单位利润，使出售资源的总利润不低于出售产品的总利润？产品的总利润？ 解：解： 1) 设设x1，x2分别表示分别表示 、两产品的产销量，两产品的产销量，则有则有 目标目标(利润利润)函数：函数： Max z = 50 x1 + 100 x2 约束条件：约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2

7、 250 x1 , x2 0 这就是问题这就是问题1的线性规划模型。的线性规划模型。 下面讨论问题下面讨论问题2的线性规划模型的线性规划模型. 解：解：2) 设设y1，y2，y3分别为设备、原料分别为设备、原料A、原料原料B的单位利润，则有的单位利润，则有 目标目标(利润利润)函数：函数： Min f =300y1+400y2+250y3 约束条件：约束条件： s.t. Y1 + 2y2 + 0y3 50 Y1 + y2 + y3 100 Y1，y2，y30 这就是问题这就是问题2的线性规划模型的线性规划模型. 二、线性规划问题的一般模型二、线性规划问题的一般模型 1.建模过程建模过程 1)

8、理解要解决的问题，了解解题的目标和条件；理解要解决的问题，了解解题的目标和条件； 2) 定义决策变量（定义决策变量（ x1 ，x2 ， ，xn ），每一组值表），每一组值表示一个方案；示一个方案； 3) 用决策变量的线性函数形式写出目标函数，确定最用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；大化或最小化目标； 4) 用一组决策变量的等式或不等式，表示解决问题过用一组决策变量的等式或不等式，表示解决问题过程中必须遵循的约束条件。程中必须遵循的约束条件。 2.线性规划线性规划模型三要素：模型三要素： 1) 决策变量决策变量 用符号来表示可控制的因素用符号来表示可控制的因素 2)

9、目标函数目标函数 Max Z 或或 Min F 3) 约束条件约束条件 s.t. (subject to) 满足于满足于. 3. 线性规划模型一般形式线性规划模型一般形式(p12)目标函数：目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件：约束条件：s.t. a11 x1 + a12 x2 + + a1n xn ( =, ）b1 a21 x1 + a22 x2 + + a2n xn ( =, ）b2 am1 x1 + am2 x2 + + amn xn ( =, ) bm x1 ，x2 ， ，xn 0 . 4. 几点注意几点注意 1) 目标函数与

10、约束条件必须线性，否则是非线目标函数与约束条件必须线性，否则是非线性规划；性规划； 2) 决策变量是连续分布的，否则可能是整数规决策变量是连续分布的，否则可能是整数规划；划； 3) 目标是单一的，否则是多目标规划；目标是单一的，否则是多目标规划； 4) 决策变量的系数是确定的不变的决策变量的系数是确定的不变的.2 图图 解解 法法一、几个名词一、几个名词1.1.可行解可行解(p11) ：满足所有约束条件的解称为该线性规划：满足所有约束条件的解称为该线性规划问题的可行解问题的可行解( (或可行方案或可行方案) )。2.2.最优解、最优值：使目标函数值达最大最优解、最优值：使目标函数值达最大( (

11、或最小或最小) )的可的可行解称为该线性规划问题的最优解，此目标函数值称行解称为该线性规划问题的最优解，此目标函数值称为最优值。为最优值。3.3.可行域可行域(p12) 线性规划问题可行解的集合称为可行域。线性规划问题可行解的集合称为可行域。二、图解举例二、图解举例 对于只有两个决策变量的线性规划问题，可以在平对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图求解。面直角坐标系上作图求解。 下面通过例下面通过例1 1详细讲解其方法：详细讲解其方法：.例例1. 目标函数：目标函数： Max z = 50 x1 + 100 x2 约束条件约束条件(s.t.) ： x1 + x2 300

12、 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最优解：得到最优解：x1 = 50， x2 = 250 最优目标值最优目标值 z = 27500.第一步第一步 确定可行域确定可行域 (1)(1)作直角坐标系：分别取决策变量作直角坐标系：分别取决策变量X X1 1 , X , X2 2 为坐标为坐标向量建立平面直角坐标系。在直角坐标系里，图上任向量建立平面直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值。意一点的坐标代表了决策变量的一组值。 （2 2）作直线：对每个不等式，先取其等式在坐标系）作直线：对每个不等式，先取

13、其等式在坐标系中作直线，然后确定不等式所决定的半平面。中作直线，然后确定不等式所决定的半平面。 （3）确定可行域：把五个图合并成一个图，取各约）确定可行域：把五个图合并成一个图，取各约束条件的公共部分，如图束条件的公共部分，如图2-1所示。所示。第二步第二步 确定最优解和最优值确定最优解和最优值 (1)改写目标函数为：改写目标函数为： x2=-(50/100) x1+z/100 . (2)以以Z为参数作平行线族：当为参数作平行线族：当z取某一固定值时得到一取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称条直线，直线上的每一点都具有相同的目标函数值，称之为之为“等值线等值线”

14、。平行移动等值线得到以。平行移动等值线得到以Z为参数的平为参数的平行线族，当移动到行线族，当移动到B点时，点时，z在可行域内实现了最大化。在可行域内实现了最大化。 (3)确定最优解和最优值：确定最优解和最优值：B(50,250) Z=27500。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE. 三、线性规划的标准化内容之一：三、线性规划的标准化内容之一：引入松驰变量引入松驰变量（含义是资源的剩余量（含义是资源的剩余量p15p15） 例例1 1 中引入中引入 s s

15、1 1， s s2 2， s s3 3 模型化为模型化为 目标函数：目标函数： Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s2 , s3 0 此例最优解的实际意义：对于最优解此例最优解的实际意义：对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0说明：生产说明：生产50单位单位产品和产品和250单位单位产品将消耗完所有产品将消耗完所有的设备台时数

16、及原料的设备台时数及原料B，但对原料，但对原料A则还剩余则还剩余50千克。千克。. 四、线性规划问题解的几种情况四、线性规划问题解的几种情况(p15)： 1.唯一最优解。例唯一最优解。例12.无穷多个最优解。若将例无穷多个最优解。若将例1中的目标函数变为中的目标函数变为 max z=50 x1+50 x2则线段则线段BC上的所有点都代表了最优解；上的所有点都代表了最优解；3.无界解无界解(无最优解无最优解)。即可行域无界，目标函数值可以。即可行域无界，目标函数值可以无穷大或无穷小。一般来说，这可能是忽略了一些无穷大或无穷小。一般来说，这可能是忽略了一些必要约束条件，因实际问题不可能有如此宽松的

17、环必要约束条件，因实际问题不可能有如此宽松的环境；境；4.无可行解无可行解(无解无解)。若在例。若在例1的数学模型中再增加一个的数学模型中再增加一个约束条件约束条件4x1+3x21200，则可行域为空域，不存在，则可行域为空域，不存在满足约束条件的解。如果实际问题出现这种情况，满足约束条件的解。如果实际问题出现这种情况，说明约束过紧或无可行决策方案。说明约束过紧或无可行决策方案。. 五、目标函数最小化举例五、目标函数最小化举例 例例2 2 某公司计划用某公司计划用A A、B B两种原料配制两种原料配制79-179-1消毒液消毒液350350吨，技术规定其中吨，技术规定其中A A原料至少需要原料

18、至少需要125125吨。现生产每吨。现生产每吨吨A A原料需要原料需要2 2小时，生产每吨小时，生产每吨B B原料需要原料需要1 1小时，生产成小时，生产成本分别为，每吨本分别为，每吨A A原料原料2 2万元，每吨万元，每吨B B原料原料3 3万元，而公司万元，而公司计划期最多能提供计划期最多能提供600600个小时生产个小时生产A A、B B原料。原料。 问：计问：计划期应如何配制方能使生产划期应如何配制方能使生产A A与与B B的总成本最低的总成本最低? ?解：目标函数：解：目标函数： Min f = 2x1 + 3 x2 约束条件约束条件(s.t.) ： x1 + x2 350 x1 1

19、25 2 x1 + x2 600 x1 , x2 0.采用图解法。得采用图解法。得Q点坐标（点坐标（250，100）为最优解。）为最优解。 最优值最优值Min f=22503 100=800 A(125，350) f=1300 B(125，225) f=925 Q(250，100) f=800 A B 100200300400500600100200300400600500 x1 =125x1+x2 =3502x1+3x2 =8002x1+3x2 =9002x1+x2 =6002x1+3x2 =1200 x1 x2 Q.3 3 线性规划模型标准形式线性规划模型标准形式及图解法的灵敏度分析及图解

20、法的灵敏度分析 一、标准形式一、标准形式(p17) 目标函数目标函数 Max z = c1 x1 + c2 x2 + + cn xn 约束条件：约束条件： a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0可以看出，线性规划的标准形式有如下四个特点：可以看出，线性规划的标准形式有如下四个特点：1)1)目标函数最大化；目标函数最大化； 2)2)结构约束为等式；结构约束为等式；3)3)决策变量均非负；决策变量均非负； 4

21、)4)结构约束右端项非负。结构约束右端项非负。 对于各种非标准形式的线性规划问题，我们总可对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式以通过以下变换，将其转化为标准形式: :. 二、化一般形式为标准形式二、化一般形式为标准形式 1.1.极小化目标函数的问题：极小化目标函数的问题： 设目标函数为设目标函数为 Min f = cMin f = c1 1x x1 1 + c+ c2 2x x2 2 + + c+ + cn nx xn n ( (可以可以) )令令 z z -f -f ， 则该极小化问题与下面的极大化问题有相同的最优解，则该极小化问题与下面的极大化问题有

22、相同的最优解， 即即 Max z = - cMax z = - c1 1x x1 1 - c- c2 2x x2 2 - - c- - cn nx xn n 但必须注意，尽管以上两个问题的最优解相同，但它们但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即最优解的目标函数值却相差一个符号，即 Min f Min f - Max z- Max z.2 2、约束条件不是等式的问题：、约束条件不是等式的问题： 设约束条件为设约束条件为 a ai1 i1 x x1 1+a+ai2 i2 x x2 2+ +a+ +ain in x xn n b bi i 可以引进一个新

23、的变量可以引进一个新的变量s s ，使它等于约束右边与左，使它等于约束右边与左边之差边之差 s=bs=bi i(a(ai1 i1 x x1 1 + a+ ai2 i2 x x2 2 + + a+ + ain in x xn n ) ) 显然，显然，s s 也具有非负约束，即也具有非负约束，即s0s0， 这时新的约束条件成为这时新的约束条件成为 a ai1 i1 x x1 1+a+ai2 i2 x x2 2+ +a+ +ain in x xn n+s = b+s = bi i. 当约束条件为当约束条件为 a ai1 i1 x x1 1+a+ai2 i2 x x2 2+ +a+ +ain in x

24、 xn n b bi i 时，时， 类似地令类似地令 s=(as=(ai1 i1 x x1 1+a+ai2 i2 x x2 2+ +a+ +ain in x xn n)- b)- bi i 显然，显然，s s 也具有非负约束，即也具有非负约束，即s0s0，这时新的约，这时新的约 束条件成为束条件成为 a ai1 i1 x x1 1+a+ai2 i2 x x2 2+ +a+ +ain in x xn n-s = b-s = bi i 为了使为了使约束由不等式成为等式而引进的变量约束由不等式成为等式而引进的变量s,s,当不等式为当不等式为“小于等于小于等于”时称为时称为“松弛变量松弛变量”；当不等

25、式为；当不等式为“大于等于大于等于”时时称为称为“剩余变量剩余变量”。如果原问题中有若干个非等式。如果原问题中有若干个非等式约束，则将其约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量和剩余转化为标准形式时，必须对各个约束引进不同的松弛变量和剩余变量。变量。. 3.右端项有负值的问题：右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如当某一个右端项系数为负时，如 bi0,则有 若 ，则有yi*=0XXYXYnjijijbxa1*njijijbxa1*Y.第第六六章章 运运 输输 问问 题题 1

26、 1 运运 输输 模模 型型 2 2运输问题的应用运输问题的应用 3 3运输问题计算机求解运输问题计算机求解 4 4 运输问题的表上作业法运输问题的表上作业法.第一节第一节 运输问题模型运输问题模型 运输问题是特殊的线性规划问题运输问题是特殊的线性规划问题 一、特点一、特点 1.广泛的应用性广泛的应用性 运输问题涉及到公路、铁路、航空、水运、运输问题涉及到公路、铁路、航空、水运、管道、线路等，加之还有些问题可转换为运输问管道、线路等，加之还有些问题可转换为运输问题题(如供产销问题如供产销问题) 2.特殊性特殊性 在模型三要素中在模型三要素中,决策变量的含意一般是运输决策变量的含意一般是运输量；

27、目标函数多是求总运输费最小；约束条件在量；目标函数多是求总运输费最小；约束条件在很多情况下是线性方程组。很多情况下是线性方程组。 模型形式还可以是模型形式还可以是表格。表格。.二、引例二、引例 例例1、某公司从两个产地、某公司从两个产地A1、A2将物品运往将物品运往三个销地三个销地B1、B2、B3，各产地的产量、各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下的销量和各产地运往各销地每件物品的运费如下表所示。表所示。 问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？. 解：解： 这是一个这是一个 产销平衡运输问题。设产销平衡运输问题。设Xij 为从产为

28、从产地地Ai运往销地运往销地Bj的运输量；目标函数为求最小总的运输量；目标函数为求最小总运费运费 ；约束条件为：总产量；约束条件为：总产量 = 总销量总销量 其线性规划模型如下：其线性规划模型如下： Min f = 6X11+ 4X12+ 6X13+ 6X21+ 5X22+ 5X23 s.t. X11+ X12 + X13 = 200 X21 + X22+ X23 = 300 X11 + X21 = 150 X12 + X22 = 150 X13 + X23 = 200 Xij 0 ( i = 1、2；j = 1、2、3）. 三、产销平衡运输问题一般模型三、产销平衡运输问题一般模型 先给一些符

29、号约定：先给一些符号约定： A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地； B1、B2、Bn 表示某物资的表示某物资的n个销地；个销地； si 表示产地表示产地Ai的产量；的产量； dj 表示销地表示销地Bj 的销量；的销量； cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价；的单位运价； xij 为从产地为从产地Ai运往销地运往销地Bj的运输量。的运输量。 得到下列产销平衡运输问题一般模型：得到下列产销平衡运输问题一般模型： 1.平衡运输问题线性规划模型平衡运输问题线性规划模型. m n Min f = cij xij i = 1 j = 1 n

30、s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) .2.平衡运输问题表格模型平衡运输问题表格模型 销地销地产地产地B1B2Bn产量产量A1c11c12c1ns1A2c21c22c2ns2 Amcm1cm2cmnsm销量销量d1d2dn 总产量总产量=总销量总销量.例例1的表格模型的表格模型. 四、有关结论及注意事项四、有关结论及注意事项 结论：产销平衡运输问题模型必有最优解。结论：产销平衡运输问题模型必有最优解。 注意注意1 有些求最大值的实际问题有些求最大值的实际问题,

31、可以转换可以转换为运输问题来建模为运输问题来建模,这需要将目标函数由求极大这需要将目标函数由求极大转换为求极小；转换为求极小； 注意注意2 运输问题线性规划模型的约束条件可运输问题线性规划模型的约束条件可以出现不等式，但表格模型的产销量不可以不以出现不等式，但表格模型的产销量不可以不平衡；平衡； 注意注意3 在以下的讨论中，我们利用运输问题在以下的讨论中，我们利用运输问题的特殊性，总把运输问题建成表格模型。的特殊性，总把运输问题建成表格模型。.3 3 运输问题的应用运输问题的应用一、供需不平衡的运输问题一、供需不平衡的运输问题1.供小于需的运输问题供小于需的运输问题例例2、石家庄北方研究院有一

32、、二、三，三个区。每年分、石家庄北方研究院有一、二、三，三个区。每年分别需要用煤别需要用煤3000、1000、2000吨，由河北临城、山西吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分盂县两处煤矿负责供应，价格、质量相同。供应能力分别为别为1500、4000吨，运价为：吨，运价为：. 问题问题1. 求一个总运费最小的调运方案求一个总运费最小的调运方案 。 问题问题2. 由于供小于需，经院研究决定一区供由于供小于需，经院研究决定一区供应量可减少应量可减少0-300吨，二区必须满足需求量，三吨，二区必须满足需求量，三区供应量不少于区供应量不少于1500吨，试求总费用为最低的吨

33、，试求总费用为最低的调运方案。调运方案。 解解1. 建立表格模型如下：建立表格模型如下：一区一区二区二区三区三区供应量供应量山西山西1.801.701.554000河北河北1.601.501.751500假想地假想地500需求量需求量300010002000.解解2： 根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表： 这里这里 M 代表一个很大的正数，其作用是强代表一个很大的正数，其作用是强迫相应的迫相应的 x31、 x33、 x34取值为取值为0。.例例3、设有、设有A、B、C三个化肥厂供应三个化肥厂供应1、2、3、4，四个地区的农用化肥。假设效果相同，有关数据四个地区的农用

34、化肥。假设效果相同，有关数据如下表：如下表： 试求总费用为最低的化肥调拨方案。试求总费用为最低的化肥调拨方案。. 解：解： 根据题意，作出产销平衡与运价表：根据题意，作出产销平衡与运价表：. 因为最低需求必须满足，这样，为了防止虚因为最低需求必须满足，这样，为了防止虚构产地的产量运往最低需求，我们把虚构产地运构产地的产量运往最低需求，我们把虚构产地运往最低需求销地的运费取定为充分大的正数往最低需求销地的运费取定为充分大的正数M ，从而可使最低需求得到真正的满足。而最高需求从而可使最低需求得到真正的满足。而最高需求与最低需求的差，可由实产地运送也可由虚产地与最低需求的差，可由实产地运送也可由虚产

35、地运送，当由虚产地运送时，把相应的虚产地运费运送，当由虚产地运送时，把相应的虚产地运费取定为取定为 0 。对应。对应 4”的销量的销量50 是考虑问题本身取是考虑问题本身取定的数据，根据产销平衡要求确定定的数据，根据产销平衡要求确定 D的产量为的产量为 50。 . 2. 供大于需的运输问题供大于需的运输问题 例例4. 某资料如下：某资料如下： 销地销地产地产地B1B2B3供给量供给量A159215A231718A362817需求量需求量181216 5046. 解：虚设一个假想的销地解：虚设一个假想的销地B4，可建模如下：可建模如下： 问问1. 运往虚拟销地的运价是多少运往虚拟销地的运价是多少

36、? 问问2. 若若A2产地不允许库存，那么产地不允许库存，那么A2运往运往B4的运的运价是多少价是多少?B1B2B3B4(虚虚) 供给量供给量A159215A231718A362817需求量需求量181216 4 5050.二、生产与储存问题二、生产与储存问题例例5、某厂按合同规定须于当年每个季度末分别提、某厂按合同规定须于当年每个季度末分别提供供10、15、25、20台同一规格的柴油机。已知台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每如下表。如果生产出来的柴油机当季不交货，每台每积压一个

37、季度需储存、维护等费用台每积压一个季度需储存、维护等费用0.15万元。万元。试求在完成合同的情况下，使该厂全年生产总费试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。用为最小的决策方案。. 解：把第解：把第 i 季度看作第季度看作第i个工厂，其生产的柴个工厂，其生产的柴油机数目看作第油机数目看作第 i 个工厂的产量；把第个工厂的产量；把第 j 季度看季度看作第作第j个销售中心，其合同交货的柴油机数目看个销售中心，其合同交货的柴油机数目看作第作第 j 个销售点的销量；单位成本加储存、维护个销售点的销量；单位成本加储存、维护等费用看作单位运价；并设等费用看作单位运价；并设 xij为第

38、为第 i 季度生产的季度生产的柴油机、第柴油机、第 j 季度交货的数目。则该生产、库存季度交货的数目。则该生产、库存与交货问题可转换为运输问题，并可建立下列产与交货问题可转换为运输问题，并可建立下列产销平衡运输问题模型：销平衡运输问题模型： . . 例例6、光明仪器厂生产电脑绣花机是以销定光明仪器厂生产电脑绣花机是以销定产的。已知产的。已知1至至6月份各月的生产能力、合同销量月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：和单台电脑绣花机平均生产费用见下表：. 已知上年末库存已知上年末库存103台绣花机，如果当月生台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，

39、产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本每台增加运输成本0.1万元万元,每台机器每月的平均每台机器每月的平均仓储费、维护费为仓储费、维护费为0.2万元。在万元。在7-8月份销售淡月份销售淡季，全厂停产季，全厂停产1个月，因此在个月，因此在6月份完成销售合同月份完成销售合同后还要留出库存后还要留出库存80台。加班生产机器每台增加成台。加班生产机器每台增加成本本1万元。万元。 问应如何安排问应如何安排1-6月份的生产计划，可使总月份的生产计划，可使总的生产费用（包括生产、运输、仓储、维护）最的生产费用（包括生产、运输、仓储、维护）最少？少？.解：解： 这个生产存储问题可化为运输

40、问题来做。考这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地虑：各月生产与交货分别视为产地和销地 1）1-6月份合计生产能力（包括正常、加月份合计生产能力（包括正常、加班生产能力和上年末储存量）为班生产能力和上年末储存量）为743台，销量为台，销量为707台。设一假想销地销量为台。设一假想销地销量为36； 2）上年末库存）上年末库存103台，只有仓储费和运输费，台，只有仓储费和运输费，把它列为第把它列为第0行；行； 3）6月份的需求除月份的需求除70台销量外，还要台销量外，还要80台库台库存，其需求应为存，其需求应为70+80=150台；台； 4）1-6表示表示1-6

41、月份正常生产情况，月份正常生产情况， 1，-6表示表示1-6月份加班生产情况。月份加班生产情况。 产销平衡与运价表如下：产销平衡与运价表如下：.用用“管理运筹学管理运筹学”软件解得的结果：软件解得的结果：1-6月最低生月最低生产费用为产费用为8307.5万元，每月的销售安排如下表：万元，每月的销售安排如下表：.2 2运输问题计算机求解运输问题计算机求解 例子：.4 4 运输问题的表上作业法运输问题的表上作业法 表上作业法是一种求解运输问题的特殊方法，表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。但如果用单纯形表求解则有其实质是单纯形法。但如果用单纯形表求解则有mn个方程，个方程，m

42、n个变量，表格会很大。如当个变量，表格会很大。如当m=20，n=30时就有时就有50个约束条件，在单纯形表个约束条件，在单纯形表中至少有中至少有600个个(考虑人工变量考虑人工变量)变量。这样，即变量。这样，即使用计算机求解，输入数据也会很复杂。表上作使用计算机求解，输入数据也会很复杂。表上作业法则可避免这种复杂性。业法则可避免这种复杂性。 平衡运输问题表格模型的表上作业法的步骤如平衡运输问题表格模型的表上作业法的步骤如下：下：. 1.求初始基本可行解求初始基本可行解 从产销平衡的运输问题的线性规划模型的从产销平衡的运输问题的线性规划模型的约束条件可知，其系数矩阵约束条件可知，其系数矩阵A的前

43、的前m(个产地个产地)行行之和等于后之和等于后n(个销地个销地)行之和，即行之和，即A的行向量组线的行向量组线性相关；同理增广矩阵的行向量组也是线性相关性相关；同理增广矩阵的行向量组也是线性相关的的(第第126页例页例1的线性规划模型可说明这一点的线性规划模型可说明这一点)。 实际上有理论保证：在平衡运输问题模型实际上有理论保证：在平衡运输问题模型约束条件中，线性方程组的系数矩阵的秩与增广约束条件中，线性方程组的系数矩阵的秩与增广矩阵的秩相等，均为矩阵的秩相等，均为mn1，这意味着基本可，这意味着基本可行解所含基变量的个数必为行解所含基变量的个数必为mn1。 具体操作步骤是在具体操作步骤是在m

44、n的产销平衡表上给的产销平衡表上给出出m+n-1个数字格，其相对应的调运量的值即为个数字格，其相对应的调运量的值即为基变量的值。基变量的值。.2. 求各非基变量的检验数。即除了上述求各非基变量的检验数。即除了上述m+n-1个基变量以外的空格的检验数，判个基变量以外的空格的检验数，判别是否达到最优解，如果已是最优，停止别是否达到最优解，如果已是最优，停止计算，否则转到下一步。计算，否则转到下一步。3. 确定入基变量和出基变量，找出新的基本确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。可行解。在表上用闭回路法调整。4. 重复重复2、3直到得到最优解。直到得到最优解。. 例例10

45、.喜庆食品公司有三个生产面包的工喜庆食品公司有三个生产面包的工厂厂A1，A2，A3，有四个销售公司，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元单位为吨，运价的单位为百元/吨。问该公吨。问该公司应如何调运产品在满足各销点的需求量司应如何调运产品在满足各销点的需求量的前提下总运费最少？的前提下总运费最少？ 这是一个产销平衡的运输问题，因此不需这是一个产销平衡的运输问题，因此不需

46、要再设假想产地和销地了。要再设假想产地和销地了。 表格模型如下：表格模型如下：. 销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656 2020.一、确定初始基本可行解一、确定初始基本可行解 为了把初始基本可行解与运价区分开，我们为了把初始基本可行解与运价区分开，我们把把运价运价放在每一栏的放在每一栏的右上角右上角，每一栏的中间写上，每一栏的中间写上初始基本可行解（调运量）。初始基本可行解（调运量）。 1.西北角法西北角法：先从表的左上角（即西北角）：先从表的左上角（即西北角）的变量的变量x11开始分配运输量，并使开始分配运输量，并使x11取

47、尽可能大取尽可能大的值，即的值，即x11=min(7,3)=3,则则x21与与x31必为零。同必为零。同时把时把B1的销量与的销量与A1的产量都减去的产量都减去3填入销量和产填入销量和产量处，划去原来的销量和产量。同理可得余下的量处，划去原来的销量和产量。同理可得余下的初始基本可行解。初始基本可行解。. 销地销地产地产地B1 B2 B3 B4 产量产量 A13 3 4 11 3 107 4 0 A2 1 2 9 2 2 84 2 0 A3 7 4 3 10 6 59 6 0 销量销量3062053060 2020.2.最小元素法最小元素法 西北角法是对西北角的变量分配运输量，西北角法是对西北角

48、的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使，并使x21取尽可能大的值，即取尽可能大的值，即x21=min(4,3)=3,把把A1的产量改为的产量改为1，B1的销量改的销量改为为0，并把，并把B1列划去。在剩下的列划去。在剩下的33矩阵中再找矩阵中再找最小运价，同理可得其他的基本可行解。最小运价，同理可得其他的基本可行解。 一般来说用最小元素法求得的初始基本可行一般来说用最小元素法求得的初始基本可行解比西北角法求得的初始基本可行解好。这样从解比西

49、北角法求得的初始基本可行解好。这样从用最小元素法求得的初始基本可行解出发求最优用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。解的迭代次数可能少一些。. 销地销地产地产地 B1 B2 B3 B4 产量产量 A1 3 11 4 33 107 3 0 A2 3 1 9 1 2 84 1 0 A3 76 4 103 59 3 0销量销量 3 060 540630 20 20. 在求初始基本可行解时要注意的两个问题：在求初始基本可行解时要注意的两个问题：1.当我们取定当我们取定xij的值之后，会出现的值之后，会出现Ai的产量与的产量与Bj的销的销量都改为零的情况，这时只能划去量都改为

50、零的情况，这时只能划去Ai行或行或Bj列，但列，但不能同时划去不能同时划去Ai行与行与Bj列。列。2.用最小元素法时，可能会出现只剩下一行或一列的用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为格划掉。这样可以保证填过数或零的格为m+n-1个，个，即保证基变量的个数为即保证基变量的个数为m+n-1个。个。. 二、最优解的判别二、最优解的判别 1.计算检验数计算检验数 （位势法）（位势法）

51、位势法介绍：位势法介绍： 结论结论1. 用表上作业法求解运输问题模型时，用表上作业法求解运输问题模型时，Xij的检验数的检验数ijij可由公式可由公式ijij=C=Cijij-(u-(ui i+v+vj j) )得到。得到。(i=1,2,m(i=1,2,m，j=1,2,n)j=1,2,n) 结论结论2.2.将所有的基变量的检验数将所有的基变量的检验数ij ij = 0= 0代代入公式入公式ij ij = C= Cijij-(u-(ui i+v+vj j) )，可构成一个方程组，可构成一个方程组，再求解，可求出结论再求解，可求出结论1 1中的中的u ui i，v vj j(i=1,2,m(i=1

52、,2,m，j=1,2,n)j=1,2,n) 现对该例现对该例149149页的表页的表729729所提供的信息进所提供的信息进行计算如下：行计算如下：. 由 0=13=3-u1-v3 得 u1+v3=3 由 0=14=10-u1-v4 得 u1+v4=10 由 0=21=1-u2-v1 得 u2+v1=1 由 0=23=2-u2-v3 得 u2+v3=2 由 0=32=4-u3-v2 得 u3+v2=4 由 0=34=5-u3-v4 得 u3+v4=5 这是一个具有6个方程，7个未知量的方程组，他有无穷多解。现以u1为自由未知量，并令u1=0，则求得ui，vj如下表：. 销地产地 B1 B2 B

53、3 B4 ui A1 1 2 4 3 0 A2 3 1 1 -1 -1 A3 10 6 12 3 -5 vj 2 9 3 10 2020311310851029471.三、求下一个基本可行解 改进运输方案的办法闭回路调整法 闭回路：是指在已给出的调运方案的运输表上，从一个非基变量的空格出发，沿水平或垂直方向前进，若遇到代表基变量的填入数字的格，则向左或右（当然也可以不改变方向）转90度，继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。 看下例：. 销地产地 B1 B2 B3 B4 ui A1 1 2 4 3 0 A2 3 1 1 -1 -

54、1 A3 10 6 12 3 -5 vj 2 9 3 10 2020. 闭回路调整法：当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。本例中取24 24 = -1 = -1 ，表明增加一个单位的x24运输量，可使得总运费减少1。在以x24为出发点的闭回路中，找出所有偶数的顶点的调运量：x14=3，x23=1，取x24=min(3,1)=1。把闭回路上所有为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。. 销地产地 B1 B2 B3 B4 ui A1 4(+1) 3(-1) 0 A2 3 1 (-1

55、) +1 -1 A3 6 3 -5 vj 2 9 3 10 20 20311310851029471. 销地产地 B1 B2 B3 B4 产量 A1 5 2 7 A2 3 1 4 A3 6 3 9 销量 3 6 5 6 2020. 对上表再用位势法计算检验数并进行最优性检验，如下表，可知已获得最优解。 销地产地B1 B2 B3 B4 ui A1 0 2 5 2 0 A2 3 2 1 1 -2 A3 9 6 12 3 -5 vj 3 9 3 10 20 20310851024713119.四、如何找多个最优方案 识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数

56、为零。如在本题中给出的最优运输方案中x11的检验数为0，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可得到另一个最优方案。. 销地产地 B1 B2 B3 B4A1 (+2) 5 2(-2)A2 3(-2) 1(+2)A3 6 3. 销地产地 B1 B2 B3 B4A1 2 5 A2 1 3A3 6 3.第七章 整数线性规划 整数规划可分为整数线性规划和整数非线性规整数规划可分为整数线性规划和整数非线性规划，本章我们讨论的是整数线性规划。划，本章我们讨论的是整数线性规划。 整数线性规划又可分为：整数线性规划又可分为： 1. 纯整数线性规划（所有变量都为非负整纯整数线性规

57、划（所有变量都为非负整数）；数）； 2. 混合整数线性规划（只有一部份变量为非混合整数线性规划（只有一部份变量为非负整数）；负整数）； 3. 0-1线性规划（变量的取值只限于线性规划（变量的取值只限于0和和1）。）。. 7.17.1整数线性规划的应用整数线性规划的应用 例例1 :1 :京成畜产品公司计划在市区的东、西、南、北四区京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟定有建立销售门市部，拟定有1010个位置个位置 A Aj j (j(j1 1，2 2，3 3，10)10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，可供选择，考虑到各地区居民的消费水平及居民居住密

58、集度，规定：在东区有规定：在东区有A A1 1 、A A2 2 、A A3 3 三个点至多选择两个；在西区有三个点至多选择两个；在西区有A A4 4 、 A A5 5 两个点至少选一个；在南区有两个点至少选一个；在南区有A A6 6 、A A7 7 两个点至少选两个点至少选一个；在北区有一个；在北区有A A8 8 、 A A9 9 、A A1010 三个点至少选两个。三个点至少选两个。A Aj j 各点的设备投资及每年可获利润由于地点不同都是不一样的，各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示预测情况见表所示 ( (单位：万元单位：万元) )。但投资总额不能超过。但

59、投资总额不能超过720720万万元，问应选择哪几个销售点，可使年利润为最大元，问应选择哪几个销售点，可使年利润为最大? ?.解：设：解：设： xi = 1 (Ai 点被选用）或点被选用）或 0 (Ai 点没被选用）。点没被选用）。 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z =36xMax z =36x1 1+40 x+40 x2 2+50 x+50 x3 3+22x+22x4 4+20 x+20 x5 5 +30 x +30 x6 6+25x+25x7 7+48x+48x8 8+58x+58x9 9+61x+61x1010s.t. 100 xs.t. 100 x1

60、 1+120 x+120 x2 2+150 x+150 x3 3+80 x+80 x4 4+70 x+70 x5 5+90 x+90 x6 6 +80 x +80 x7 7+140 x+140 x8 8+160 x+160 x9 9+180 x+180 x1010 720 720 x x1 1 + x + x2 2 + x + x3 3 2 2 x x4 4 + x + x5 5 1 1 x x6 6 + x + x7 7 1 1 x x8 8 + x + x9 9 + x + x1010 2 2 x xj j 0 0 且且x xj j 为为0-10-1变量，变量，i = 1,2,3,10i