运筹学1线性规划与单纯形法(清华大学出版社_胡运权主编)

第一章线性规划及单纯形法目录1.1线性规划问题及其数学模型1.2线性规划解的概念、性质及图解法1.3单纯形法1.4初始可行基的求法－人工变量法1.5线性规划问题的计算机求解1.6线性规划应用举例管理科学与工程学院本章重点:(1)掌握线性规划数学模型的基本特征和标准形式，以及线性规划问题数学模型的建立方法，学会用图解法求解简单的线性规划问题。(2)理解线性规划问题的解的概念，了解线性规划的基本理论。(3)了解单纯形表的构成，熟练掌握运用单纯形法求解线性规划问题。(4)掌握人工变量法（包括大Ｍ法和两阶段法）的计算步骤。管理科学与工程学院所研究的主要问题有两类:一项已确定的任务,如何统筹安排,做到以最少的人力,物力资源去完成该项任务?已有一定数量的人力,物力资源,如何安排使用它们,使完成的任务(或创造的财富,利润)最多?第一章线性规划及单纯形法线性规划是运筹学的一个重要的分支。早在20世纪30年代末就有人从运输问题开始研究它。自1947年美国人丹捷格(G.B.Dantzig)提出了求解线性规划问题的方法——单纯形法以后，线性规划从理论上日趋完整和成熟，在应用上也及为广泛。线性规划实质上是解决稀缺资源如何进行最优分配的问题，这类最优分配问题大部分是从经营管理中引出的，例如：产品的最优组合，生产排序，最优投资方案，人力资源分配等。在这类问题中，一个共性的问题是一些稀缺资源必须被分配到一些指定的生产活动中去，而这些资源的使用会伴随着费用或效益的发生。线性规划可用于合理分配这些资源，并使付出的费用最小或获得的收益最大。在本章中我们将首先介绍什么是线性规划问题，线性规划问题的数学表达式，简单线性规划问题的图解法等线性规划的基本概念，然后介绍线性规划的基本理论和求解线性规划的单纯形方法。管理科学与工程学院1.1线性规划问题及其数学模型•本小节介绍什么是线性规划问题，如何将实际问题转化为线性规划模型，线性规划问题的标准形式。回本章目录用线性规划方法解决实际问题的第一步是要将实际问题转化为线性规划模型。下面通过例子说明如何把具体问题转化为线性规划模型。一、线性规划模型举例例1.1生产计划问题家具厂生产桌子和椅子两种家具。桌子售价150元。椅子售价80元，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为180小时，油漆工工时为90小时。问该厂如何组织生产才能使每月的销售收入最大?解：将一个实际问题转化为线性规划模型有以下几个步骤：(1)确定决策变量：决策变量是模型要决定的未知量。在本例中，家具厂要确定桌子和椅子的生产数量，因此可定义：x1=生产桌子的数量，x2=生产椅子的数量。(2)确定目标函数：目标函数决定线性规划问题的优化方向。很明显，家具厂的目标是使销售收入最大，更具体一点，是使两种产品售价与产量的乘积的总和最大，因此目标函数可写为：maxz=150x1+80x2(3)确定约束方程：如果家具厂可以随意选择生产桌子和椅子的数量，他们的销售收入可以随意大。而这实际是不可能的，因为任何生产都会受到种种客观条件的限制。一个正确的模型应通过约束方程来反映这些客观条件。本例中的限制条件是每月可用的木工和油漆工的工时不能超过180和90小时。这两个条件可由以下方程表示：4x1+3x21802x1+x290(4)变量取值限制：一般情况下，决策变量只取正值（非负值）。因此，模型中应有变量的非负约束。在本例中，非负约束为x10，x20。将以上几部分结合起来就得到反映家具厂经营活动的完整的数学模型：maxz=150x1+80x2s.t.4x1+3x21802x1+x290x1,x20Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数Z达到最大的x1，x2取值。管理科学与工程学院例1.2：生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg712管理科学与工程学院建模问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=7X1+12X23、确定约束条件：人力约束9X1+4X2≤360设备约束4X1+5X2≤200原材料约束3X1+10X2≤300非负性约束X1≥0，X2≥0管理科学与工程学院完整的数学模型maxZ=7X1+12X29X1+4X2≤3604X1+5X2≤2003X1+10X2≤300X1≥0，X2≥0例1.3营养配餐问题假定一个成年人每天需要从食物中获取3000大卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每公斤所含热量和营养成分以及市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小。序号食品名称热量(大卡)蛋白质(g)钙(mg)价格(元)1猪肉100050400142鸡蛋8006020063大米10002030034白菜200105002表1.1各种食物的营养成分表解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型如下：minz=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800xi0i=1,...,4管理科学与工程学院例1.4—人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630X6管理科学与工程学院建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1+x6≥60非负性约束：xj≥0,j=1,2,…6管理科学与工程学院其他典型问题：•运输问题•生产的组织与计划问题•投资证券组合问题•指派问题•生产工艺优化问题例1.5运输问题设有两个砖厂A1、A2。其产量分别为23万块与27万块。它们的砖供应3个工地。其需要量分别为17万块、18万块、和15万块。而自各产地到各工地的运价列表如下：工地砖厂B1B2B3A1506070A260110160（其中运价为（元/万块））问如何调运，才使总运费最省？解：设xij表示由砖厂Ai运往工地Bj的砖的数量（单位：万块）（i=1,2;j=1,2,3),现列表如下：工地砖厂B1B2B3发量（万块）A1x11x12x1323A2x21x22x2327收量(万块)17181550因为由砖厂A1运往三个工地砖的总数应为A1的产量23万块,即:x11+x12+x13=23。同理由砖厂A2运往三个工地砖的总数应为A2的产量27万块,即:x21+x22+x23=27。另一方面，两个砖厂运往B1工地的砖的数量应等于B1的需要量17万块，即：x11+x21=17；同理可得：x12+x22=18；x13+x23=15。因此调运方案就是求满足前面所有约束条件的x11、x12、x13、x21、x22、x23一组变量的非负值。显然，可行的调运方案有很多，我们就是在这很多个调运方案中，找一个运费最少的方案。所求数学模型为：Minz=50x11+60x12+70x13+60x21+110x22+160x23s.t.x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15x11、x12、x13、x21、x22、x230一般地，设某种物资有m个产地：A1，A2，…，Am，联合供应n个销地：B1，B2，…，Bn。各产地产量（单位：吨），各销地销量（单位：吨），各产地到各销地的单位运价（单位：元/吨）如下表所示：表中：ai表示产地Ai的产量（i=1,2,…,m);bj表示销地Bj的销量（j=1,2,…,n);cij表示Ai,Bj间的单位运价（元/吨）销地产地B1B2…Bn产量（吨）A1A2Amc11c12…c1nc21c22…c2n…cm1cm2…cmna1a2am销量（吨）b1b2…bn问应如何调运，才使总运费最少？解：假定产销平衡（即：）。mjjmiiba11jix表示由产地Ai运往销地Bj的物资数),,2,1;,,2,1(njmi。那么，上述问题的数学模型为：mnmnxcxcxcz12121111min222221111211..axxxaxxxtsnn),,2,1;,,2,1(02122221211211121njmixbxxxbxxxbxxxaxxxjinmnnnmmmmnmm利用连加号，这一数学模型还可以写成:求一组变量xij,使它们满足：),,2,1;,,2,1(0)(),,2,1()(),,2,1(11njmixnjbxmiaxjimijjinjiji其中（*）式表示产地Ai发到各销地的发量总和应等于Ai的产量。（**）式表示各产地发到销地Bj的发量总和应等于Bj的销量。并使目标函数（总运费最少）minjjijixcz11min如果运输问题中，没有产销平衡这一限制，当产大于销时（即时）这一数学minjjiba11的数学模型应为：求一组变量xij,使它们满足：约束条件),,2,1;,,2,1(0),,2,1(),,2,1(11njmixnjbxmiaxijmijjinjiji产地Ai发到各销地的发量总和不超过Ai的产量）各产地发到销地Bj的发量总和等于Bj的销量）（调运量不能为负数）并使目标函数的值最小。jiminjjixcz11管理科学与工程学院课堂练习1—生产计划问题某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？产品A产品B资源限量劳动力设备原材料9434510460250320利润元/kg1014管理科学与工程学院完整的数学模型maxZ=10X1+14X29X1+4X2≤4604X1+5X2≤2503X1+10X2≤320X1≥0，X2≥0管理科学与工程学院课堂练习2——配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VAVBVC价格元/kgIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200管理科学与工程学院建模设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg饲料IVx4kg饲料Vx5kg目标函数：Z=2x1+7x2+4x3+9x4+5x5最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x1+2x2+x3+6x4+18x5≥700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200非负性要求：x1≥0,x2≥0,x3≥0,x4≥0,x5≥0管理科学与工程学院完整的数学模型minZ=2x1+7x2+4x3+9x4+5x53x1+2x2+x3+6x4+18x5≥700x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200x1≥0,x2≥0,x3≥0,x4≥0,x5≥0课堂练习3布局问题某农场要在B1