本科教学课件-《运筹学基础》

运筹学基础课程简介《运筹学基础》什么是运筹？运筹帷幄之中，

决胜千里之外运筹——对资源进行统筹安排，制定出最

优解决方案。帷幄——军用帐幕千里之外——战场

在小小的军帐之内作出正确的部署，能决定千里之外战场上的胜负。

做事前做好充分准备，后期的工作就能顺利进行。

很有才智的人无需上阵，只需做好前期的战略部署，就能够让事情获得成功。围魏救赵

战国时，魏将庞涓率军围攻赵国都城邯郸。赵求救于齐，齐王命田忌、孙膑率军往救。孙膑发现魏军主力在赵国，内部空虚，就带兵攻打魏国都城大梁，因而，魏军不得不从邯郸撤军，回救本国，路经桂陵要隘，又遭齐兵截击，几乎全军覆没。这个典故是指采用包抄敌人的后方来迫使它撤兵的战术。围魏救赵这一避实就虚的战法为历代军事家所欣赏，至今仍有其生命力。运筹学的应用2025/2/1田忌赛马

战国时期，齐王提出与大将军田忌赛马。双方约定：从各自的上、中、下三个等级的马中各选一匹参赛，每匹马均只能比赛一次，每次比赛双方各出一匹马，三局二胜，负者要付给胜者千金。

已知:在同级的马中，田忌的马不如齐王的马；

不同等级中，田忌的马可胜齐王低一等级的马。2025/2/1丁谓修复皇宫

北宋真宗年间，皇城失火，皇宫被毁，朝廷决定重建皇宫。丁谓负责修复烧毁的开封皇宫。丁谓到现场一察看，发觉有三大问题最难办。一是建房用土量大。若到郊外取土，路途太远。二是运输难，大批建筑材料，从外地只能由水路运到汴水。若再运到皇宫建筑工地，只能靠车马了。三是大片废墟垃圾，要运到远处倒掉。不知要花费多少人力、物力和时间。

丁谓再三思量，最后终于想出了一举三得的办法。他先让人从施工现场到汴水之间挖几条大深沟，挖出来的土堆在两旁，作烧砖瓦用。这样解决了用土的问题。接着，他把汴水引入沟中，使它成为运输的河流。等到工程结束，它将水排掉，把所有垃圾倒在沟内，重新填为平地，又成了良田。2025/2/1都江堰水利工程——运筹学思想的杰出运用

都江堰位于四川省都江堰市城西，是中国古代建设并使用至今的大型水利工程，被誉为“世界水利文化的鼻祖”，是四川著名的旅游胜地。通常认为，都江堰水利工程是由秦国蜀郡太守李冰及其子率众于前256年左右修建的。1982年，都江堰被中华人民共和国国务院公布为第二批全国重点文物保护单位之一。2000年，都江堰以其为“当今世界年代久远、惟一留存、以无坝引水为特征的宏大水利工程”，与青城山共同作为一项世界文化遗产被列入世界遗产名录。

生活中的运筹学家里来了客人，你想给他泡茶。但家里没有热水和茶叶；此外茶壶、茶杯也还没洗。其中，出去买茶叶要5分钟，烧热水要10分钟，洗茶壶2分钟，洗茶杯1分钟。而口渴的客人12分钟喝不到茶就会崩溃。

你如何在最短的时间内让客人喝到茶呢？1-12步骤1：烧水（10分钟）步骤2：在烧水的同时，去洗茶壶（2分钟）、洗茶杯（1分钟）、买茶叶（5分钟）。8分钟就可以完成这两件事，这样剩下4分钟还可以陪客人闲聊。结论：在已有的条件下，经过筹划、安排，选择一个最好的方案，就会取得最好的效果。可见筹划安排十分重要。

现有25匹马，要找出其中跑的最快的三匹马，比赛的时候一次最多安排五匹马同时比赛。想一想应该怎样安排？怎样安排能使比赛次数最少？现有8枚硬币，其中有一枚硬币是假的，假硬币比真硬币轻，给你一个天平，请用最少的次数找出那一枚硬币是假的。日常生活中

做任何事情之前，都要先做好运筹

计划——人员安排——执行

长期——中期——短期

学期——月——周——天结论运筹学适用于我们生活中的每一个角落、每一件事情，每一个行业。运筹学主要内容及学习方法线性规划整数规划运输路径规划网络计划技术动态规划库存管理排队论QSB软件操作运筹学的学习顺序每种方法的应用每种方法的算法软件求解每种方法的练习2025/2/1运筹学所能解决的问题生产计划问题——线性规划问题某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需要的设备台时以及A、B两种原材料的消耗以及资源的限制如下表所示，工厂每生产一件产品Ⅰ可获利50元，每生产一件产品Ⅱ可获利100元，问工厂应如何安排生产任务才能使获利最多？ⅠⅡ资源限制设备11300台时原料A21400kg原料B01250kg2025/2/1汽车厂生产计划——整数规划问题汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求、利润及工厂每月的现有量。请指定工厂的月生产计划，使工厂的利润最大。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）2342025/2/1背包问题——0-1规划问题背包可装入8单位重量，10单位体积的物品，以下物品装哪些，总价值最高？物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服45152025/2/1指派问题有一份中文说明书，需要翻译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人，他们将说明书翻译成不同文字所需要的时间如表所示，请问应该指派何人完成哪一项工作，能使花费的总时间最短？英日德俄甲215134乙1041415丙9141613丁781192025/2/1哥尼斯堡七桥问题——图论中的一笔画问题哥尼斯堡城中有一条河，河中有两个岛，河上有七座桥，一个散步者怎样才能走完七座桥，并且每座桥只走一次，最后又回到出发点？2025/2/1一个起点一个终点的最短路问题一名货车司机奉命在最短的时间内将一批货物从甲地运往乙地，从甲地到乙地的道路网纵横交错，因此有多种行车路线，这名司机应该选择哪条路线呢？（假设货车的运行速度是恒定的。）2025/2/1一个起点到多个终点的配送路径问题

有一个快递员送快递，他需要走完他负责投递的所有街道，把快递送到每个收件人手中，投完后回到快递网点，怎样走能使总路程最短？2025/2/1多个起点到多个终点的运量分配问题2025/2/1网络计划技术在地铁工程筹划中的应用2025/2/12025/2/1一定阶段最短路问题——动态规划问题

W先生每天驾车去公司上班。如图，W先生的住所位于u1，公司位于us，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。2025/2/1库存管理问题订货点技术ABC库存控制法JIT存货管理MRP库存管理法VMI管理系统2025/2/1排队论问题

某维修中心在周末限制安排一名员工为顾客提供服务。新来维修的顾客到达后，若已有顾客正在接受服务，则需要排队等待。若排队的人数过多，势必会造成顾客抱怨，会影响到公司产品的销售；若维修人员多，会增加维修中心的支出，如何调整两者的关系，使得系统达到最优.

它是一个典型的排队的例子,关于排队的例子有很多,例如：上下班坐公共汽车,等待公共汽车的排队;顾客到商店购物形成的排队;病人到医院看病形成的排队;售票处购票形成的排队等;另一种排队是物的排队，例如文件等待打印或发送;路口红灯下面的汽车、自行车通过十字路口等等.运筹学主要内容及学习方法线性规划整数规划运输路径规划网络计划技术动态规划库存管理排队论QSB软件操作运筹学的学习顺序每种方法的应用每种方法的算法软件求解每种方法的练习33项目一线性规划

(LinearProgramming)LP模型的应用LP的概念图解法单纯形法用软件求解LP模型本章主要内容：34一、线性规划模型的应用一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。存在着多种方案要求解问题的目标函数能用数值指标来反映，且为线性函数要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述2025/2/1例1、生产计划问题某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需要的设备台时以及A、B两种原材料的消耗以及资源的限制如下表所示，工厂每生产一件产品Ⅰ可获利50元，每生产一件产品Ⅱ可获利100元，问工厂应如何安排生产任务才能使获利最多？ⅠⅡ资源限制设备11300台时原料A21400kg原料B01250kg2025/2/1变量：x1、x2目标函数：z=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250x1、x2≥037例2、人力资源分配问题某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?38解：设xi表示第i班次时开始上班的司机和乘务人员人数。2025/2/1例3、运量分配问题某路桥建设公司选定A1、A2两个符合条件的石料厂，其产量分别为23吨和27吨，计划将石料运到B1、B2、B3三个工地，这三个工地的需求量分别为17吨、18吨、15吨。从各料厂到各工地的运价见下表，问如何制定调运方案，才能使总运费最省？B1B2B3产量A150607023A26011016027需求量171815变量：x11、x12、x13、x21、x22、x23目标函数：z=50x11+60x12+70x13+60x21+110x22+160x23约束条件：x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15x11、x12、x13、x21、x22、x23≥0

2025/2/141线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。

怎样辨别一个模型是线性规划模型？

二、线性规划的概念线性规划问题（LinearProgramming，简记为LP）为求一组非负的未知数，这些未知数在满足一组线性方程组的条件下，使某个线性函数取得最优值。约束条件：约束方程组目标函数：最优线性函数可行解：满足约束条件的值最优解：求出的模型的解最优值：最优解对应的目标函数值2025/2/143三、图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。2025/2/1例1、用图解法求解线性规划maxz=60x1+40x2x1+2x2≤12x1≤6x2≤4x1、x2≥0

图解法的步骤2025/2/1建立坐标系画出满足全部约束条件的区域（可行域）先确定一个目标函数值，画出等值线向最优的方向移动等值线，找到最优解

2025/2/1练习1、生产计划问题某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需要的设备台时以及A、B两种原材料的消耗以及资源的限制如下表所示，工厂每生产一件产品Ⅰ可获利50元，每生产一件产品Ⅱ可获利100元，问工厂应如何安排生产任务才能使获利最多？ⅠⅡ资源限制设备11300台时原料A21400kg原料B01250kg2025/2/1变量：x1、x2目标函数：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250线性规划问题解的可能性2025/2/1例2：用图解法求解下列线性规划问题

maxz=20x1+40x2x1+2x2≦12x1≦6x2≦4x1、x2≧02025/2/1例3：用图解法求解下列线性规划问题

minz=x1+x2-2x1+x2≦4x1-x2≦2x1、x2≧02025/2/1例4：用图解法求解下列线性规划问题

maxz=x1+x2-2x1+x2≦4x1-x2≦2x1、x2≧02025/2/1线性规划问题解的可能性2025/2/12025/2/1四、单纯形法1.线性规划模型的一般形式变量：x1、x2目标函数：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤25054目标函数：约束条件：简写为：55矩阵形式：其中：56目标函数：maxz=c1x1+c2x2+…….+cnxn2.线性规划模型的标准形式约束条件：a11x1+a12x2+…….+a1nxn=b1a21x1+a22x2+…….+a2nxn=b2am1x1+am2x2+…….+amnxn=bm………x1、x2、xn≧057特点：(1)目标函数为求最大值。(2)约束条件都为等式方程，且右端常数项bi都是非负数。(3)决策变量xj为非负。58目标函数的转换——最小值换成最大值如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令，可得到上式。即若约束条件右边的常数为负数，可用（-1）乘等式的两边。常数的变换——负数换成正数3.如何将非标准形式化为标准形式59约束方程的转换：不等式换为等式。称为松弛变量称为剩余变量若约束条件中有不等式，对于≦的不等式，可在不等式的左端加上一个松弛变量，使之变为等式；对于≧的不等式，可在不等式的左端减去一个剩余变量，使之变为等式，人工变量在目标函数中的系数为零。2025/2/1

maxz=60x1+40x2

x1+2x2≤12x1≤6

x2≤4x1、x2≥0例1、将下列线性规划问题化为标准形式

maxz=60x1+40x2

x1+2x2+x3=12x1+x4=6

x2+x5=4x1、x2、x3、x4、x5≥02025/2/1练习（p10）maxz=50x1+100x2

x1+x2≤300

2x1+x2≤400

x2≤2502025/2/1例1-4（p10）maxz=60x1+40x2x1+2x2≤12x1≤6x2≤4x1、x2≥0

4.单纯形法的原理上题中用图解法求解的时候，最优解是从可行域边界上的几个极点中选择的，五个极点的坐标分别为（0,0）（0,4）（4,4）（6,3）（6,0）2025/2/1maxz=60x1+40x2x1+2x2+x3=12x1+x4=6x2+x5=4x1、x2、x3、x4、x5≥0

把上述线性规划问题化为标准形式：五个极点的坐标（0,0）（0,4）（4,4）（6,3）（6,0）也可以表示为：（0,0,12,6,4）（0,4,4,6,0）（4,4,0,2,0）

（6,3,0,0,1）（6,0,6,0,4）64从上题可知，在五个可行解中，总是有两个变量的值是0，我们把这两个变量称作非基变量，其余的三个变量称作基变量。因此，求解线性规划问题可以变换非基变量和基变量，也就是逐个检查可行域的极点，直到找到使目标函数达到最优的极点坐标，该坐标值即为该线性规划问题的最优解。五个极点的坐标（0,0）（0,4）（4,4）（6,3）（6,0）也可以表示为：（0,0,12,6,4）（0,4,4,6,0）（4,4,0,2,0）

（6,3,0,0,1）（6,0,6,0,4）65单纯形法的计算步骤单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束66列出初始单纯形表，若表里没有单位矩阵，通过矩阵初等变换化出一个单位矩阵，确定基变量和非基变量。化初始表为标准表，另基变量所对应的目标函数行元素为零，则非基变量所对应的目标函数行元素为检验数。在标准表中，若检验数≤0则该表对应的基本可行解就是最优解，若检验数≧0，则改变基变量和非基变量，再检验。单纯形法的步骤几个概念2025/2/1初始单纯形表单位矩阵矩阵初等变换（加法、数与矩阵相乘）基变量和非基变量标准表68例1-4（P10）：用单纯形法求下列线性规划的最优解maxz=60x1+40x2x1+2x2≤12x1≤6x2≤4x1、x2≥0

2025/2/1解：1）将问题化为标准型，加入松驰变量x3、x4、x5则标准型为:

maxz=60x1+40x2

x1+2x2≤12x1≤6

x2≤4x1、x2≥0

maxz=60x1+40x2

x1+2x2+x3=12x1+x4=6

x2+x5=4x1、x2、x3、x4、x5≥0702）列出初始单纯形表，求出线性规划的初始基可行解。检验数x1x2x3x4x5b12100121001060100146040000z713）进行最优性检验如果表中所有检验数≦0，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。上一步中，基变量为x3、x4、x5，非基变量为x1、x2，检验数为60和40，均≧0，所以，需要改变基变量和非基变量。724）从一个基可行解转换到另一个目标值更大的基可行解，列出新的标准表确定换入基的变量。选择检验数≧0对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数其对应的xk作为换入变量。确定主元。根据下式计算θ

，选最小的θ对应的元素作为主元，通过矩阵变换把主元化为1。寻找新的基可行解。通过矩阵变换化出单位矩阵，得到新的基变量和非基变量，找出新的基可行解，并相应地可以画出一个新的标准表并进行检验。73x1x2x3x4x5b12100121001060100146040000z确定换入基的变量。选择x1作为换入变量。确定主元。12/1=12,6/1=6,选第一列第二行的元素作为主元。寻找新的基可行解。通过矩阵变换化出单位矩阵，得到新的基变量和非基变量，找出新的基可行解，并相应地可以画出一个新的标准表并进行检验。74x1x2x3x4x5b12100121001060100146040000zr1-r2x1x2x3x4x5b021-1061001060100146040000z75x1x2x3x4x5b12100121001060100146040000zr4-60r2x1x2x3x4x5b021-1061001060100140400-600Z-36076x1x2x3x4x5b021-1061001060100140400-600Z-360确定换入基的变量。选择x2作为换入变量。确定主元。6/2=3,4/1=4,选第二列第一行的元素作为主元。寻找新的基可行解。通过矩阵变换化出单位矩阵，得到新的基变量和非基变量，找出新的基可行解，并相应地可以画出一个新的标准表并进行检验。77①½*r1x1x2x3x4x5b011/2-1/20310010600-1/21/21100-20-400Z-480x1x2x3x4x5b021-1061001060100140400-600Z-360②r3-r1③r4-40r178通过计算得到，基变量为x1、x2、x5，非基变量为x3、x4。另非基变量=0，代入约束条件，求出基变量的值，最后得出该线性规划问题的最优解（6,3,0,0,1）。将最优解代入目标函数，求出该问题的最优值z=480。maxz=60x1+40x2x1+2x2+x3=12x1+x4=6x2+x5=4x1、x2、x3、x4、x5≥0

2025/2/1例1、生产计划问题某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需要的设备台时以及A、B两种原材料的消耗以及资源的限制如下表所示，工厂每生产一件产品Ⅰ可获利50元，每生产一件产品Ⅱ可获利100元，问工厂应如何安排生产任务才能使获利最多？ⅠⅡ资源限制设备11300台时原料A21400kg原料B01250kg2025/2/1变量：x1、x2目标函数：z=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250x1、x2≥081练习、用单纯形法求解下列线性规划问题1、例1-9（p18）maxz=x1-2x2x1-x2≧-2x1+2x2≦6x1、x2≥0

2、例1-11（p20）maxz=60x1+40x22x1+8x2=24x1+x3=6x2+x4=4x1、x2、x3、x4≥0

五、用QSB软件求解线性规划问题2025/2/11、QSB软件的界面2025/2/1LP/ILP模块2025/2/1例1、生产计划问题某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需要的设备台时以及A、B两种原材料的消耗以及资源的限制如下表所示，工厂每生产一件产品Ⅰ可获利50元，每生产一件产品Ⅱ可获利100元，问工厂应如何安排生产任务才能使获利最多？ⅠⅡ资源限制设备11300台时原料A21400kg原料B01250kg2025/2/1变量：x1、x2目标函数：z=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250x1、x2≥02025/2/1练习：例1-4（p10）用QSB求下列线性规划问题的解maxz=60x1+40x2x1+2x2≤12x1≤6x2≤4x1、x2≥0

942、例1-9（p18）maxz=x1-2x2x1-x2≧-2x1+2x2≦6x1、x2≥0

3、例1-11（p20）maxz=60x1+40x22x1+8x2=24x1+x3=6x2+x4=4x1、x2、x3、x4≥0

95本章小结 学习要点： 1、了解线性规划的应用2、了解线性规划的概念3、掌握用图解法解两个变量的线性规划问题4、掌握单纯形法的原理和步骤5、了解QSB软件并会用它求解线性规划问题2025/2/1例1、生产计划问题某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需要的设备台时以及A、B两种原材料的消耗以及资源的限制如下表所示，工厂每生产一件产品Ⅰ可获利50元，每生产一件产品Ⅱ可获利100元，问工厂应如何安排生产任务才能使获利最多？ⅠⅡ资源限制设备11300台时原料A21400kg原料B01250kg2025/2/1变量：x1、x2目标函数：z=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250x1、x2≥098例2、人力资源分配问题某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?99解：设xi表示第i班次时开始上班的司机和乘务人员人数。2025/2/1例3、运量分配问题某路桥建设公司选定A1、A2两个符合条件的石料厂，其产量分别为23吨和27吨，计划将石料运到B1、B2、B3三个工地，这三个工地的需求量分别为17吨、18吨、15吨。从各料厂到各工地的运价见下表，问如何制定调运方案，才能使总运费最省？B1B2B3产量A150607023A26011016027需求量171815变量：x11、x12、x13、x21、x22、x23目标函数：z=50x11+60x12+70x13+60x21+110x22+160x23约束条件：x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15x11、x12、x13、x21、x22、x23≥0

2025/2/1线性规划问题（LinearProgramming，简记为LP）为求一组非负的未知数，这些未知数在满足一组线性方程组的条件下，使某个线性函数取得最优值。约束条件：约束方程组目标函数：最优线性函数可行解：满足约束条件的值最优解：求出的模型的解最优值：最优解对应的目标函数值2025/2/1103三、图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标适用于任意变量、但必需将一般形式变成标准形式图解法的求解步骤建立坐标系画出满足全部约束条件的区域（可行域）先确定一个目标函数值，画出等值线向最优的方向移动等值线，找到最优解

104特点：(1)目标函数为求最大值。(2)约束条件都为等式方程，且右端常数项bi都是非负数。(3)决策变量xj为非负。四、单纯形法105单纯形法的计算步骤单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束106列出初始单纯形表，若表里没有单位矩阵，通过矩阵初等变换化出一个单位矩阵，确定基变量和非基变量。化初始表为标准表，另基变量所对应的目标函数行元素为零，则非基变量所对应的目标函数行元素为检验数。在标准表中，若检验数≤0则该表对应的基本可行解就是最优解，若检验数≧0，则改变基变量和非基变量，再检验。单纯形法的步骤几个概念2025/2/1初始单纯形表单位矩阵矩阵初等变换（加法、数与矩阵相乘）基变量和非基变量标准表LP/ILP模块项目2整数规划整数规划的应用整数规划——分支定界法0--1规划——隐枚举法指派问题——匈牙利法复习线性规划——非负连续变量、非负整数变量、0-1变量两个变量——图解法（画出可行域，画出等值线，等值线移动，找到最优解）两个以上变量——单纯形法（化为标准形式，列出初始单纯形表，确定基变量和非基变量，检验，变换基变量和非基变量，再检验）一、整数规划的应用1、货物装运问题：某物流公司在一段时间内拟用一辆集装箱汽车托运甲、乙两种货物，装甲种货物的集装箱每箱的体积5m3、质量2t，装乙种货物的集装箱每箱的体积4m3、质量5t，托运甲、乙两种货物每箱可获利润分别为2000元、1000元，该集装箱汽车最大可载体积为24m3、最大可载质量为13t，那么这两种货物各托运多少箱才能获得最大利润？变量：x1、x2目标函数：maxz=2000x1+1000x2约束条件：5x1+4x2≤242x1+5x2≦13x1、x2为整数2、钢管下料问题：现有原料钢管19米，顾客需要的钢管长度和数量为：4米钢管50根，6米钢管20根，8米钢管15根，请问如何下料套裁最节省成本？钢管切割方案序号4米（根）6米（根）8米（根）余料（米）14003231013201341203511116030170023变量：每种切割方案的使用次数x1、x2、x3、x4、x5、x6、x7目标函数：minz=x1+x2+x3+x4+x5+x6+x7约束条件：4x1+3x2+2x3+x4+x5≧50x2+2x4+x5+3x6≧20x3+x5+2x7≧15x1、x2、x3、x4、x5、x6、x7大于等于零且为整数3、汽车厂生产计划：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求、利润及工厂每月的现有量。请指定工厂的月生产计划，使工厂的利润最大。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234变量：每种汽车的计划产量x1、x2、x3目标函数：maxz=2x1+3x2+4x3约束条件：1.5x1+3x2+5x3≦600280x1+250x2+400x3≦60000x1、x2、x3大于等于零且为整数4、背包问题：背包可装入8单位重量，10单位体积的物品，以下物品装哪些，总价值最高？物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服4515变量：每种物品是否装入背包x1、x2、x3、x4、x5目标函数：maxz=20x1+30x2+10x3+18x4+15x5约束条件：5x1+3x2+x3+2x4+4x5≤82x1+x2+4x3+3x4+5x5≤10x1、x2、x3、x4、x5大于等于零且为整数5、指派问题：有一份中文说明书，需要翻译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人，他们将说明书翻译成不同文字所需要的时间如表所示，请问应该指派何人完成哪一项工作，能使花费的总时间最短？英日德俄甲215134乙1041415丙9141613丁78119英日德俄甲x11x12x13x14乙x21x22x23x24丙x31x32x33x34丁x41x42x43x44目标函数：minz=2x11+15x12+13x13+4x14+10x21+4x22

+14x23+15x24+9x31+14x32+16x33+13x34

+7x41+8x42+11x43+9x44约束条件：x11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1x取0或者1二、用分支定界法求解整数规划问题例2-1某物流公司在一段时间内拟用一辆集装箱汽车托运甲、乙两种货物，装两种货物的集装箱每箱的体积5m3、质量2t，装乙种货物的集装箱每箱的体积4m3、质量5t，托运甲、乙两种货物每箱可获利润分别为2千元、1千元，该集装箱汽车最大可载体积为24m3、最大可载质量为13t，那么这两种货物各托运多少箱才能获得最大利润？变量：甲货物、乙货物各托运多少箱x1、x2目标函数：maxz=2x1+x2约束条件：5x1+4x2≤24

2x1+5x2≤13x1、x2大于等于零且为整数整数规划问题的求解思路能否不考虑整数约束，直接求解线性规划问题，求出的解取整数？12345671234565x1+4x2=242x1+5x2=132x1+x2=4(4.8,0)求解松弛问题得到线性规划问题的解为（4.8,0）若四舍五入，得到（5,0），不符合约束条件1；若舍去小数，得到（4,0），不是最优解。可行域中所有的整数解：（0,0）（0,1）（0,2）（1,0）（2,0）（3,0）（4,0）（1,1）（1,2）（2,1）（3,1）（4,1）结论求解整数规划问题，不能用图解法或者单纯形法求解松弛问题后，直接取整数。求解整数规划问题，需要用专用的求解方法———————分支定界法货物装运问题变量：x1、x2maxz=2x1+x25x1+4x2≤242x1+5x2≤13

x1、x2≥0且为整数≤≥2、钢管下料问题：现有原料钢管19米，顾客需要的钢管长度和数量为：4米钢管50根，6米钢管20根，8米钢管15根，请问如何下料套裁最节省成本？钢管切割方案序号4米（根）6米（根）8米（根）余料（米）14003231013201341203511116030170023变量：每种切割方案的使用次数x1、x2、x3、x4、x5、x6、x7目标函数：minz=x1+x2+x3+x4+x5+x6+x7约束条件：4x1+3x2+2x3+x4+x5≧50x2+2x4+x5+3x6≧20x3+x5+2x7≧15x1、x2、x3、x4、x5、x6、x7大于等于零且为整数3、汽车厂生产计划：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求、利润及工厂每月的现有量。请指定工厂的月生产计划，使工厂的利润最大。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234变量：x1、x2、x3maxz=2x1+3x2+4x31.5x1+3x2+5x3≦600

280x1+250x2+400x3≦60000

x1、x2、x3≥且为整数≤≥三、0-1规划——隐枚举法例2-3（P37）AK公司准备开发几种新产品，该公司的4个项目组分别提出了各自的方案，但是由于公司的资金有限，不能对所有项目进行投资，必须在其中做出选择。下表列出了各个项目所需资金、工作人员以及将会产生的收益净现值等调研数据。公司计划投资总额不超过1100万元，可调用的工作人员一共有22人，另外，由于各种原因，项目1和项目4不能同时投资，问该公司应该如何挑选投资项目？项目序号投资额/万元需要工作人员数/人收益净现值/万元165016900250087003550765044005600变量：x1、x2、x3、x4目标函数：maxz=900x1+700x2+650x3+600x4约束条件：650x1+500x2+550x3+400x4≤110016x1+8x2+7x3+5x4≤22x1+x4≤1x1、x2、x3、x4=0或者1隐枚举法的概念解0-1规划最容易想到的方法就是穷举法，即检查变量取值为0或者1的每一种组合，在满足约束条件的前提下，目标函数值最优的即为最优解。这需要检查2n个组合，当变量个数n较大时，几乎是不可能的，因此只检查变量取值的部分组合，以求得最优解，这就是隐枚举法。隐枚举法的步骤先通过试探的方法找一个可行解，求出对应的目标函数值最优值一定不小于上面算出的目标函数值，增加过滤条件将新的约束条件排好序，对每个解，依次检查是否满足在检查的过程中，若遇到目标函数值优于上面的目标函数值，则更新过滤条件依次检查，直到找到最优解和最优值x1、x2、x3、x4maxz=900x1+700x2+650x3+600x4650x1+500x2+550x3+400x4≤110016x1+8x2+7x3+5x4≤22x1+x4≤1x1、x2、x3、x4=0或者1先找到一个可行解（1,0,0,0，）求出对应的目标函数值z=900增加新的约束条件900x1+700x2+650x3+600x4≥900序号点条件z值④①②③1(1,1,1,1)√×2(1,1,1,0)√×3(1,1,0,1)√×4(1,0,1,1)√×5(0,1,1,1)√×6(1,1,0,0)√×7(1,0,1,0)√×8(1,0,0,1)√√√×9(0,1,1,0)√√√√135010(0,1,0,1)×11(0,0,1,1)×12(0,0,0,1)×13(0,0,1,0)×14(0,1,0,0)×15(0,0,0,0)×例2-4某物流公司打算在昆明或贵阳至少设立一个销售分公司以增加市场份额，决策层同时可以在新设分公司的城市最多建一个配送中心。每种选择公司收益净现值、所需费用等调研数据均列在下表，根据公司的财务状况，总预算不得超过20万元，问如何决策方能使收益净现值最大？决策方案编号选址净现值/万元所需资金/万元1在昆明建分公司18122在贵阳建分公司1063在昆明建配送中心12104在贵阳建配送中心84x1、x2、x3、x4maxz=18x1+10x2+12x3+8x412x1+6x2+10x3+4x4≤20x3+x4≤1-x1+x3≤0-x2+x4≤0x1、x2、x3、x4=0或者1先找到一个可行解（0,1,0,1，）求出对应的目标函数值z=18增加新的约束条件18x1+10x2+12x3+8x4≥18序号点条件z值④①②③1(1,1,1,1)√×2(1,1,1,0)√×3(1,1,0,1)√×4(1,0,1,1)√×5(0,1,1,1)√√×6(1,1,0,0)√√√√287(1,0,1,0)√×8(1,0,0,1)×9(0,1,1,0)×10(0,0,1,1)×11(0,0,0,1)×12(0,0,1,0)×13(0,1,0,0)×14(1,0,0,0)×15(0,0,0,0)×4、背包问题：背包可装入8单位重量，10单位体积的物品，以下物品装哪些，总价值最高？物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服4515变量：每种物品是否装入背包x1、x2、x3、x4、x5目标函数：maxz=20x1+30x2+10x3+18x4+15x5约束条件：5x1+3x2+x3+2x4+4x5≤82x1+x2+4x3+3x4+5x5≤10x1、x2、x3、x4、x5大于等于零且为整数四、指派问题——匈牙利法指派问题的概念——派n个人去完成n项不同的工作，每个人一项工作，并且每项工作只能由一个人去完成，由于任务的性质和每个人的专长不同，不同的人去完成不同的工作其效率也不同。如何安排才能使工作总效率最高，这类问题称为指派问题（AssignmentProblem）例2-6设有B1、B2、B3、B4四项工作，分配给A1、A2、A3、A4四个人去完成，每个人一项工作，并且每项工作只能由一个人去完成，由于每个人的技术专长和工作经验不同，不同的人去完成不同的工作费用也不同，下表给出了每个人完成各项工作的费用。问如何分派，才能使总费用最小？B1B2B3B4A1215134A21041415A39141613A478119目标函数：minz=2x11+15x12+13x13+4x14+10x21+4x22

+14x23+15x24+9x31+14x32+16x33+13x34

+7x41+8x42+11x43+9x44约束条件:x11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1x取0或者1匈牙利法求解指派问题的一般步骤如下：第一步：变换系数矩阵（1）从系数矩阵的各行减去该行的最小元素。（2）从系数矩阵的各列减去该列的最小元素。

直至系数矩阵的各行各列均有0.第二步：画盖0线（画最少的线将系数矩阵的0全部盖住，若盖0线的）（1）从只有一个0元素的行开始，给这个0元素加括号，然后划去该行的其他元素，表示这行所代表的人，只有一种任务可指派，然后划去0所在列的其他0元素，表示这列所代表的任务已指派完，不必再考虑别人了。（2）从只有一个0元素的列开始，给这个0元素加括号，然后划去0所在行的其他0元素。第三步：若0的个数等于系数矩阵的阶数，令解矩阵中0对应的元素取1，其他元素取0，即可得到指派问题的最优解。215134104141591416137811901311260101105740142Ø

13

7

(0)6

(0)

6

9(0)5

3

2

Ø

1

(0)

Ø0001010

010

0

000100

13

706

0

6

905

3

20

100例2-8下表表示了某指派问题的成本矩阵，表中数据为不同的人承担不同的任务所需时间，求该指派问题总时间最少的方案。ABCDE甲56845乙34661丙55798丁67576戊746285684534661557986757674628盖0线的条数小于系数矩阵的阶数该如何求解？1240123550002431202152406第三步：若盖0线的条数小于系数矩阵的阶数，可按下列步骤进行：（1）从未被直线覆盖的元素中找出最小元素，所有未被直线覆盖的元素都减去该最小元素，位于水平直线与铅直直线交叉处的元素都加上这个最小元素，其余元素保持不变。（2）返回第二步。568453466155798675767462812401235500024312021524060

1

3002356000253120314

1

3051240123550002431202152406(0)

1

3

Ø

Ø2356

(0)Ø

(0)25312(0)

314

1

3

(0)

510

0

0

00

0

0

0

10

10

0

00

0

10

00

0

0

1

00

1

3002356000253120314

1

305项目2整数规划整数规划的应用整数规划——分支定界法0--1规划——隐枚举法指派问题——匈牙利法一、整数规划的应用1、货物装运问题：某物流公司在一段时间内拟用一辆集装箱汽车托运甲、乙两种货物，装甲种货物的集装箱每箱的体积5m3、质量2t，装乙种货物的集装箱每箱的体积4m3、质量5t，托运甲、乙两种货物每箱可获利润分别为2000元、1000元，该集装箱汽车最大可载体积为24m3、最大可载质量为13t，那么这两种货物各托运多少箱才能获得最大利润？2、钢管下料问题：现有原料钢管19米，顾客需要的钢管长度和数量为：4米钢管50根，6米钢管20根，8米钢管15根，请问如何下料套裁最节省成本？钢管切割方案序号4米（根）6米（根）8米（根）余料（米）140032310132013412035111160301700233、汽车厂生产计划：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求、利润及工厂每月的现有量。请指定工厂的月生产计划，使工厂的利润最大。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）2344、背包问题：背包可装入8单位重量，10单位体积的物品，以下物品装哪些，总价值最高？物品名称重量体积价值1书52202摄像机31303枕头14104休闲食品23185衣服45155、指派问题：有一份中文说明书，需要翻译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人，他们将说明书翻译成不同文字所需要的时间如表所示，请问应该指派何人完成哪一项工作，能使花费的总时间最短？英日德俄甲215134乙1041415丙9141613丁78119三、背包问题——隐枚举法解0-1规划最容易想到的方法就是穷举法，即检查变量取值为0或者1的每一种组合，在满足约束条件的前提下，目标函数值最优的即为最优解。这需要检查2n个组合，当变量个数n较大时，几乎是不可能的，因此只检查变量取值的部分组合，以求得最优解，这就是隐枚举法。隐枚举法的步骤先通过试探的方法找一个可行解，求出对应的目标函数值最优值一定不小于上面算出的目标函数值，增加过滤条件将新的约束条件排好序，对每个解，依次检查是否满足在检查的过程中，若遇到目标函数值优于上面的目标函数值，则更新约束条件。依次检查，直到找到最优解和最优值。四、指派问题——匈牙利法指派问题的概念——派n个人去完成n项不同的工作，每个人一项工作，并且每项工作只能有一个人去完成，由于任务的性质和每个人的专长不同，不同的人去完成不同的工作其效率也不同。如何安排才能使工作总效率最高，这类问题称为指派问题（AssignmentProblem）匈牙利法求解指派问题的一般步骤如下：第一步：变换系数矩阵（1）从系数矩阵的各行减去该行的最小元素。（2）从系数矩阵的各列减去该列的最小元素。第二步：寻找独立的0元素（1）从只有一个0元素的行开始，给这个0元素加括号，表示这行所代表的人，只有一种任务可指派，然后划去0所在列的其他0元素，表示这列所代表的任务已指派完，不必再考虑别人了。（2）从只有一个0元素的列开始，给这个0元素加括号，然后划去0所在行的其他0元素。第三步：若0的个数等于系数矩阵的阶数，令解矩阵中0对应的元素取1，其他元素取0，即可得到指派问题的最优解。第三步：若(0)的个数小于系数矩阵的阶数，可按下列步骤进行：（1）对没有“（）”的行打“×”号。（2）对已打“×”号的行中所有含0元素的列打“×”号。（3）对打有“×”号的列中含0元素的行打“×”号。（4）重复（1）（2）两步，直到打不出新的“×”号为止。（5）对没有打“×”号的行划一横线，打“×”号的列划一纵线（6）从未被直线覆盖的元素中找出最小元素，所有未被直线覆盖的元素都减去该最小元素，位于水平直线与铅直直线交叉处的元素都加上这个最小元素，其余元素保持不变。（7）返回第二步。项目三

运输路径规划复习：项目二整数规划整数规划的应用整数规划——分支定界法0--1规划——隐枚举法指派问题——匈牙利法一、整数规划的应用1、货物装运问题：某物流公司在一段时间内拟用一辆集装箱汽车托运甲、乙两种货物，装甲种货物的集装箱每箱的体积5m3、质量2t，装乙种货物的集装箱每箱的体积4m3、质量5t，托运甲、乙两种货物每箱可获利润分别为2000元、1000元，该集装箱汽车最大可载体积为24m3、最大可载质量为13t，那么这两种集装箱各托运多少箱才能获得最大利润？变量：x1、x2目标函数：maxz=2000x1+1000x2约束条件：5x1+4x2≤242x1+5x2≦13x1、x2为整数2、汽车厂生产计划：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求、利润及工厂每月的现有量。请指定工厂的月生产计划，使工厂的利润最大。小型中型大型现有量钢材（吨）1.535600劳动时间（小时）28025040060000利润（万元）234变量：每种汽车的计划产量x1、x2、x3目标函数：maxz=2x1+3x2+4x3约束条件：1.5x1+3x2+5x3≦600280x1+250x2+400x3≦60000x1、x2、x3大于等于零且为整数3、钢管下料问题：现有原料钢管19米，顾客需要的钢管长度和数量为：4米钢管50根，6米钢管20根，8米钢管15根，请问如何下料套裁最节省成本？钢管切割方案序号4米（根）6米（根）8米（根）余料（米）14003231013201341203511116030170023变量：每种切割方案的使用次数x1、x2、x3、x4、x5、x6、x7目标函数：minz=x1+x2+x3+x4+x5+x6+x7约束条件：4x1+3x2+2x3+x4+x5≧50x2+2x4+x5+3x6≧20x3+x5+2x7≧15x1、x2、x3、x4