运筹学复习专题

运筹学复习专题华中科技大学管理学院管理科学与信息管理系授课教师：傅小华Telephone:1398601962E-mail:fuxhua@考试的学科范围应考范围包括：线性规划动态规划整数规划网络规划评价目标运筹学考试的目标在于考查学生运筹学的基本概念、基本理论和方法的掌握以及对实际问题的分析、建立必要的数学模型和求解问题的能力。考生应能：正确理解运筹学中的基本概念和基本理论。正确分析实际问题并建立相应的数学模型。掌握求解运筹学中常见问题的方法。能正确的解释所求问题的计算结果。

考纲所规定出题形式与考试范围

数学规划建模专题

线性规划专题

动态规划专题

整数规划专题

图与网络规划专题

存储论专题考纲所规定出题形式与考试范围答题时间：180分钟。试卷分数：满分为150分。试卷结构及考查比例：问题建模40%基本理论和方法40%分析题20%。考纲所规定出题形式与考试范围线性规划线性规划问题及其数学模型。线性规划问题图解法、解的基本性质、单纯形法的基本原理、线性规划对偶理论及对偶单纯形法、灵敏度分析、运输问题。动态规划多阶段决策问题、动态规划基本方程、动态规划的递推方法、解析法和数值法。考纲所规定出题形式与考试范围整数规划整数规划问题的数学模型；分枝定界法与割平面法的基本原理；0-1规划问题与隐枚举法；分配问题。图与网络规划图与网络的基本概念，树与最小树问题，最短路问题，网络最大流问题，最小费用最大流问题。存贮论确定型存贮模型，随机型存贮模型考纲所规定出题形式与考试范围参考教材杨超.运筹学,北京,科学出版社,2004.钱颂迪.运筹学,北京,清华大学出版社,1993.邓成梁.运筹学的原理与方法,武汉,华中理工大学出版社,1996数学规划建模专题特点题量大、单题分值高综合性强出题范围大多态性不易辨别对错对建模者的综合素质要求高基本功扎实逻辑思辨与推理能力强细致周到思维稳定性相关考研真题2007

58(20)92006

1(20)4(20)82005

1(20)4(15)2004

34(10)10(20)20021(10)4(10)数学规划建模专题特点题量大、单题分值高综合性强出题范围大多态性不易辨别对错对建模者的综合素质要求高基本功扎实逻辑思辨与推理能力强细致周到思维稳定性数学规划的建模原则容易理解建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。容易查找模型中的错误这个原则的目的显然与(1)相关。常出现的错误有：书写错误、公式错误。容易求解对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。建立数学规划模型的四个步骤

明确问题，确定决策变量；决策变量是构成解决方案的要素或单元，决策变量的组合构成一个可行解决方案。

明确约束条件并用决策变量的等式或不等式表示；尽可能分类描述，防止差错和遗漏

用决策变量的函数表示目标，并确定是求极大（Max）、极小（Min）还是特定值；

根据决策变量的物理性质研究变量是否有非负性或上下界。例某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?一、工作安排问题线性规划问题建模解：设

xi

表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Min

z=x1+x2+x3+x4+x5+x6

约束条件：s.t.

x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0，整数例某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解:考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出二、下料问题假设x1,x2,x3,x4,x5分别为上面前5种方案下料的原材料根数。我们建立如下的数学模型。目标函数：

Minz=x1+x2+x3+x4+x5

约束条件：s.t.

x1+2x2+x4=1002x3+2x4+x5=1003x1+x2+2x3+3x5=100x1,x2,x3,x4,x5≥0模型1假设x1,x2,x3,x4,x5,x6,x7,x8分别为上面前8种方案下料的原材料根数。我们建立如下的数学模型。目标函数：

Minz=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8约束条件：

s.t.2x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100

x1+x3+3x4+2x6+3x7+4x8=100x1,x2,x3,x4,x5,x6,x7,x8=0，整数模型2假设x1,x2,x3,x4,x5,x6,x7,x8分别为上面前8种方案下料的原材料根数。我们建立如下的数学模型。目标函数：

Minz=x1+x2+x3+x4+x5+x6+x7+x8

约束条件：

s.t.2x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100

x1+x3+3x4+2x6+3x7+4x8=100x1,x2,x3,x4,x5,x6,x7,x8=0，整数模型3例:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？三、生产决策问题解：设x1，

x2，

x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4，

x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求xi

的利润:利润=售价-各成本之和可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下数学模型：

目标函数:Maxz=15x1+10x2+7x3+13x4+9x5

约束条件：

s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，产品Ⅰ依次经过设备A、B加工，产品Ⅱ依次经过设备A、C加工，产品Ⅲ依次经过设备B、C加工，已知有关数据如下表所示，问如何安排生产计划才能获利最大？试建立该问题的线性规划模型。产品机器生产率(件/小时)原料成本(元)产品价格(元)ABCI10201550II20525100III10201045成本(元/小时)200100200可用机时504560例:某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？四、混合问题解：设xij

表示第i

种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；

对于乙：x21，x22，x23；

对于丙：x31，x32，x33；

对于原料1：x11，x21，x31；

对于原料2：x12，x22，x32；

对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出

约束条件：规格要求4个；供应量限制3个。Max

z=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）

-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）

0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）

-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）

x11+x21+x31≤100(供应量限制）

x12+x22+x32≤100(供应量限制）

x13+x23+x33≤60(供应量限制）

xij≥0,i=1,2,3;j=1,2,3设某种动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。现有5种饲料可供选用，各种饲料营养成分的含量与单价如下表所示：试建立既满足动物生长的营养需要、又使费用最省的选用饲料方案的线性规划模型。饲料蛋白质(克)矿物质(克)维生素(毫克)单价(元/公斤)1310.50.2220.510.7310.20.20.446220.35180.50.80.8例：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A

：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如下表：五、连续投资问题求：解：1）确定决策变量：连续投资问题设xij(i=1-5，j=1、2、3、4)表示第i

年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量：

A

x11x21x31x41x51

B

x12x22x32x42

C

x33

D

x24a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？2）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是：

x11+x12=200

第二年：B次年末才可收回投资故第二年年初的资金为1.1x11，于是：x21+x22+x24=1.1x11

第三年：年初的资金为1.1x21+1.25x12，于是：

x31+x32+x33=1.1x21+1.25x12

第四年：年初的资金为1.1x31+1.25x22，于是：

x41+x42=1.1x31+1.25x22

第五年：年初的资金为1.1x41+1.25x32，于是：

x51=1.1x41+1.25x32

B、C、D的投资限制：

xi2≤30(i=1，2，3，4)，

x33≤80，x24≤100a)

Max

z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11

x31+x32+x33=1.1x21+1.25x12

x41+x42=1.1x31+1.25x22

x51=1.1x41+1.25x32

xi2≤30(i=1、2、3、4)，

x33≤80，x24≤100xij≥0(i=1,2,3,4,5；j=1,2,3,4）3）目标函数及模型：b)

Min

f=（x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.

x11+x12≤200

x21+x22+x24≤1.1x11

x31+x32+x33≤1.1x21+1.25x12

x41+x42≤1.1x31+1.25x22

x51≤1.1x41+1.25x32

xi2≤30(i=1、2、3、4)，

x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330xij≥0(i=1,2,3,4,5；j=1,2,3,4）某厂生产一种产品，该产品在未来5个月的需求量、每个月最大生产能力和单位生产成本如下表所示：另外，每件产品每月的存储费用为2元，假定1月初库存为5件。管理层希望制定合理的月生产计划，既满足需求又使总生产成本最低。试建立此问题的一般线性规划模型。月份12345需求量dj1115222315生产成本cj876410最大生产能力kj3122301516六、多阶段决策问题解：设第j月生产量为xj件，需求量为dj

，上月未交货量(第j月初库存)为sj-1，本月未交货量(第j+1月初库存)为sj，单位生产成本为cj

，单位存储费为B和最大生产能力为kj。则第j月所发生的产品流转与费用如下图所示：生产量：xj生产成本：cjxj可支配量：xj+sj-1需求量：dj未交货量：sj上季度未交货量：sj-1保管费用：Bsj-1本月费用：cj

xj+Bsj-1供应约束xj≤kjxj≥0需求约束xj+sj-1≥dj均衡约束sj=xj+sj-1-dj；s0=5

，s5=0某厂在今后四个月内需租用仓库堆放货物，已知各月需用仓库面积如下表所示：仓库租金随合同内容而定，租用期限越长折扣越大，具体如下表所示：租用仓库的合同每月初都可办理，每份合同具体规定仓库面积和期限。因此该厂可根据需要在任何一个月初办理租用合同。每次可签一份或若干份租用面积或租用期限不同的合同。总目标是总租金最少，试建立线性规划模型。月份1234所需仓库面积15102012合同租用期限1个月2个月3个月4个月单位面积租金2800450060007300一、产销不平衡的运输问题例：有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。需求地区化肥厂B1B2B3B4产量（万吨）A11613221750A21413191560A3192023---50最低需求（万吨）最高需求（万吨）3050707003010不限运价：万元/万吨运输问题建模分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表——产销平衡表A1A2A3DB'1B''1B2B3B'4B''4

产量销量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M13152050M产销平衡表A1A2A3D1613502217171414132019151015301930192020023MMM0M030M0205060505030207030105016B'1B''1B2B3B'4B''4

产量

销量供应约束需求约束二、有转运的运输问题例：已知A1、A2、A3三个工厂生产同一种产品，用相同的价格供应B1、B2、B3三个销售点，有2个转运站T1、T2。允许产品在各工厂、销售点和转运站间转运，已知各工厂、销售点、转运站之间的单位运价和产销量如下表所示。试求最经济运输方案。产地转运站销地产量A1A2A3T1T2B1B2B3产地A1862-410830A2851395910A3654228720转运站T12148463T2-328232销地B149242-5B2105863-4B38973254销量153510解：将此转运问题化为等价的运输问题需作如下处理：将所有的产地、转运站和销地都作为产地与销地，则此问题转化为8个产地与8个销地运输问题；对扩大的运输问题建立运价表，没有运输路线的运价设为M，自我运输的运价为0；所有转运站的产量等于销量，且为最大可能调运量，即均为60；在扩大的运输问题中，由于原产地与销地均具有转运功能，所以原产地的产量两于原销地的销量均需加上最大可能调运量，即在原数值上加上60。扩大的运输表如下表所示。产地转运站销地产量A1A2A3T1T2B1B2B3产地A10862M410890A28051395970A36504228780转运站T12140846360T2M328023260销地B1492420M560B2105863M0460B38973254060销量6060606060759570整数规划问题建模光华服装厂生产三种类型的：衬衣、短裤和长裤。生产各种服装的机器的固定费用如下：衬衣机器：2000元/周，短裤机器：1500元/周，长裤机器：1000元/周。每周可使用的劳动时间为150小时，可使用的布料为160平方米。生产各种服装的时间与布料消耗、各种服装的售价与可变成本如下表所示。建立最优周生产计划模型。一、固定费用问题服装类型劳动时间(小时)布料(平方米)可变成本(元)售价(元)衬衣3460120短裤234080长裤6480150某县辖下6个镇。现在准备建立若干个急救中心，急救中心必须建立在镇上，各镇之间的车辆行驶时间如下表所示。要求每个镇必须至少保证有一个急救中心位于15分钟车程之内，问如何建立急救中心使得数量最少。二、集合覆盖问题从到镇1镇2镇3镇4镇5镇6镇101020303020镇210025352010镇320250153020镇430351501525镇530203015014镇620102025140江夏汽车公司正在考虑生产3种类型的汽车：微型、中型和大型汽车。各种汽车的消耗和利润如下表所示。目前有6000吨钢材和60000小时的劳动时间，为了确保效益，每种汽车一旦生产就至少需生产1000辆。试建立生产计划模型。三、选择约束与假设约束条件汽车类型微型中型大型钢材(吨)1.53.05.0劳动时间(小时)302540利润(元)200030004000四、0-1变量应用讨论(3)应用0-1变量表示逻辑关系逻辑关系表达式至多允许a,b,…,g中的一个a+b+c+d+e+f+g≤1允许a,b,…,g中的二个a+b+c+d+e+f+g=2如果a，则必有bb≥a如果a，则不能ba+b≤1如果没有a，则应有ba+b≥1如果a，则必有b；如果b，则必有aa=b如果a，则必有b和cb≥a

且c≥a如果a，则必有b或cb+c≥a如果b和c，则必有aa≥b+c-1如果b或c，则必有aa≥b

且a≥c或a≥(b+c)/2如果b,c,d,e中两个或两个以上，则必有aa≥(b+c+d+e-1)/3如果n个项目(b,c,d,e,…)中的m个，则必有aa≥(b+c+d+e+…-m+1)/(n-m+1)Q1Q3Q2购买量购买价格p1p2p3(6)应用0-1变量表示价格折扣模型A异价折扣模型购买量不到Q1时购价为p1,超过Q1不到Q2部分购价为p2，余类推；B一价折扣模型

根据购买量按同一价格购买。例求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为：

11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59

显然不同的方案对应不同的费用。第i年度

12345购置费

1111121213设备役龄

0-11-22-33-44-5维修费用

5681118网络规划问题建模一、最短路问题W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31某歌舞团组织舞蹈表演，需要男女演员各5名，一男一女配成一对，为保证表演质量，要求配合默契的男女组合尽可能多，已知5对男女演员配合默契与否如下表所示，试建立网络模型解决配对问题。二、最大流问题女1女2女3女4女5男1否是否否否男2是否否否否男3是是否否否男4是是否否是男5否否是是是解：网络模型如下页所示，求出最大流量即可。某速递公司有5辆卡车，现有7种包裹需要运送，每种包裹有3件，5辆卡车的运输能力为6、4、5、4、3，假定每辆卡车不能运送两件以上同种包裹，试建立网络模型确定运输量最大的运输方案。解：建立网络模型如下页所示。从源S到包裹的连接弧容量为3，表示每种包裹最大可能运输量；从包裹到车的连接弧容量均为1，表示每辆车只能运输1件改种包裹；从车到汇的连接弧容量为各车运输能力，确保车辆不得超载；这样，从源到汇的最大流量即为最大运输量，在最大流量下包裹与车辆连接状态就是运输方案。某厂生产一种产品，该产品在未来5个月的需求量、每个月最大生产能力和单位生产成本如下表所示：另外，每件产品每月的存储费用为2元，假定1月初库存为5件。管理层希望制定合理的月生产计划，既满足需求又使总生产成本最低。试建立此问题的网络规划模型。月份12345需求量dj1115222315生产成本cj876410最大生产能力kj3122301516三、最小费用最大流解：设第j月生产量为xj件，需求量为dj

，上月未交货量(第j月初库存)为sj-1，本月未交货量(第j+1月初库存)为sj，单位生产成本为cj

，单位存储费为B和最大生产能力为kj。则第j月所发生的产品流转与费用如下图所示：生产量：xj生产成本：cjxj可支配量：xj+sj-1需求量：dj未交货量：sj上季度未交货量：sj-1保管费用：Bsj-1本月费用：cj

xj+Bsj-1供应约束xj≤kjxj≥0需求约束xj+sj-1≥dj均衡约束sj=xj+sj-1-dj；s0=5

，s5=00x11d12345x2x3x4x5d2d3d4d5ST012345ST线性规划专题线性规划问题及其数学模型线性规划问题图解法解的基本性质单纯形法的基本原理线性规划对偶理论及对偶单纯形法线性规划灵敏度分析运输问题相关考研真题20071(20)2(20)3(15)4(10)82006

12(20)3(20)47(30)200512(10)3(20)47(20)8(10)

2004

1(20)2(10)3(20)8(10)1020021

2(20)3(15)4

6(10)线性规划问题的特点决策变量：(x1…xn)T

代表某一方案，

决策者要考虑和控制的因素非负；目标函数：Z=ƒ(x1

…xn)为线性函数，求Z极大或极小;约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为线性规划问题。线性规划问题及其数学模型目标函数约束条件(3)线性规划模型一般形式隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值价值系数决策变量技术系数右端常数线性规划模型标准形式简记形式线性规划模型其它形式矩阵形式价值向量决策向量系数矩阵右端向量价值向量决策向量右端向量向量形式列向量对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:一般型向标准型的转化目标函数目标函数为极小化约束条件分两种情况：大于和小于决策变量可能存在小于零的情况1.极小化目标函数的问题：设目标函数为

Minf=c1x1+c2x2+…+cnxn

则可以令z

＝-f

，该极小化问题与下面的极大化问题有相同的最优解，即

Maxz=-c1x1-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即

Minf＝-Maxz2、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+…+ain

xn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+ain

xn

)

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ain

xn+s=bi

变量s称为松弛变量当约束条件为

ai1x1+ai2x2+…+ain

xn

≥bi

时，类似地令

s=(ai1x1+ai2x2+…+ain

xn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ain

xn-s=bi变量s称为剩余变量3.决策变量如果某个变量的约束条件为或者可令或者代入原问题如果某个变量为自由变量，则可令且线性规划问题图解法定义1：满足约束(2)的X=(X1…Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。例1

MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t解：(1)、确定可行域

X1+2X230

3X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域(2)、求最优解最优解：X*=(15,7.5)Zmax

=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C点：X1+2X2=30

3X1+2X2=600203010102030X1X2DABC最优解Z=975可行解Z=0等值线012345678123456⑴⑵⑶⑷∴有唯一最优解：x1=4x2=2最优值Z=14x2

x1(42)012345678123456⑴⑵⑶⑷x2

x1⑴⑵无界解x1x2

⑴⑵x1x2

无可行解直观结论若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；若线性规划问题有可行解，但无有限最优解，则可行域必然是无界的；若线性规划问题无可行解，则可行域必为空集。解的基本性质(1)解的基本概念定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。基阵非基阵基向量非基向量基变量非基变量令则定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。定义在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为非退化解，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题；若基本可行解中，有基变量为零，则称为退化解，该问题称为退化的线性规划问题。基本解中最多有m个非零分量。基本解的数目不超过个。非可行解解的集合：可行解基本解最优解基本可行解解空间例现有线性规划问题试求其基本解、基本可行解并判断是否为退化解。解:(1)首先将原问题转化为标准型

引入松弛变量x3和x4(2)求基本解由上式得可能的基阵由于所有|B|≠0,所以有6个基阵和6个基本解。对于基阵令则对于基阵令则为基本可行解，B13为可行基为基本可行解，B12为可行基对于基阵令则对于基阵令则对于基阵令则对于基阵令则为基本可行解，B24为可行基为基本可行解，B34为可行基0ABCDE1基本解为边界约束方程的交点；2基对应于可行解可行域极点；3相邻基本解的脚标有一个相同。(2)解的基本性质判别可行解为基可行解的准则定理1线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关.线性规划问题的基本定理:定理2和定理3定理2线性规划问题有可行解,则它必有基可行解.定理3若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.定理2线性规划问题有可行解,则它必有基可行解.证:设为线性规划问题的一个可行解.

若,则它是一个基可行解,定理成立;

若,则令的前k个分量为非零分量：若上述分量所对应的列向量线性无关,则它是一个基可行解,定理成立;若线性相关，从出发，必可找到线性规划问题的一个基可行解。由于线性相关，则存在一组不全为零的数，使得假定令若令(若令)(*)由(*)可知即与相比，的非零分量减少1个，若对应的k-1个列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无关。几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.单纯形法的基本原理例1MaxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(1)单纯形法的引入解：(1)、确定初始可行解B=(P3P4P5)=IZ=0+40X1+50X2X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2令X1=

X2=0X(1)=(0,0,30,60,24)TZ(1)=0(2)、判定解是否最优Z=0+40X1+50X2当X1从0↗或X2从0↗Z从0↗∴X(1)不是最优解(3)、由一个基可行解→另一个基可行解。∵50>40选X2从0↗，X1=0X3=30-2X20X230/2

X4=60-2X20X260/2

X5=24-2X20X224/2

X2=min(30/2,60/2,24/2)=12X2：进基变量，

X5：出基变量。B2=(P3P4P2)Z=0+40X1+50X2④X3+2X2=30-X1①X4+2X2=60-3X1

②2X2=24-X5③③×1/2

，③代入④式，①－③，②－③Z=600+40X1-25X5X3=6-X1+X5X4=

36-3X1+X5X2=12-1/2X5令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=600(2)'

判断∵40>0∴X(2)不是最优解。(3)'

选X1从0↗，X5=0X3=6-X10

X4=

36-3X10

X2=120

X1=min(6/1,36/3,1)=6X1进基，

X3出基。B3=(P1P4P2)Z=840-40X3+15X5X1=6-X3+X5X4=

18+3X3-2X5X2=12-1/2X5令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=840(2)"∵15>0∴X(3)不是(3)"

选X5从0↗，X3=0X1=6+X50

X4=

18-2X50

X2=12-1/2X5

0

X5=min(18/2,12/1/2)=9X5进基，

X4出基。B4=(P1P5P2)Z=975-35/2X3-15/2X4X1=15+1/2X3-1/2X4X5=

9+3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=9750(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2)X(3)Z=40X1+50X2单纯形法小结：

单纯形法是这样一种迭代算法——如下图…

当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。X1Z1保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增X2X3...XkZ2Z3...Zk

当Zk

中非基变量的系数的系数全为负值时，这时的基本可行解Xk

即是线性规划问题的最优解，迭代结束。(2)线性规划的典则形式标准型上式称为线性规划问题对应于基B的典则形式，简称典式。约束方程组的系数矩阵中含有一个单位矩阵，并以其为基；目标函数中不含基变量，只有非基变量。检验数(3)最优性判别定理在线性规划问题的典式中，设

X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若有

j0(j=m+1,m+2,…,n)则X(0)是线性规划问题的最优解，基B为最优基。证：设X为线性规划问题的一个可行解，必有

X0，当j0，则X

0Z*=CX(0)=Z(0)Z(0)+

X=CX

故X(0)为线性规划问题的最优解。在线性规划问题的典式中，设X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若有

j

0(j=m+1,m+2,…,n

)

且j+k=0

则线性规划问题有无穷多个最优解。无穷多最优解判别定理在线性规划问题的典式中，设X(0)

为对应于基B的一个基可行解，若某一非基变量xj+k的检验数

j+k>0

且对应的列向量

P’m+k=(a1,m+k,a2,m+k,…,am,m+k)0则线性规划问题具有无界解，即无有限最优解。无界解判别定理(4)基可行解改进定理在线性规划问题的典式中，设

X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若满足以下条件：某个非基变量的检验数

k>0(m+1kn);aik

(i=1,2,…,m)不全小于或等于零，即至少有一个aik

>0(1km);bi’>0(I=1,2,…,m),即X(0)为非退化的基可行解。则从X(0)出发，一定能找到一个新的基可行解X(1)，使得CX(1)>CX(0)

。(5)单纯形表将线性规划问题典式中各变量及系数填写在一张表格中，该表即为单纯形表。cj

c1c2…cncn+1cn+2…cn+m解CB基

x1x2…xn

xn+1xn+2…xn+m0000xn+1xn+2…xn+m

a11a12…a1n1a21a22…a2n1……………am1am2…amn

1b1

b2…

bm12…mj=cj–zj

1

2…

nn+1

n+2…n+m单纯形方法的矩阵表示BNIbCBCN00IB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1b对应I式的单纯形表——

I表(初始单纯形表)对应B式的单纯形表——B表迭代IB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1bBNIbCBCN00价值系数cjCBCN0解θ基系数基XBXNXSCBXBIB-1NB-1B-1b检验数σj0CN-CBB-1N-CBB-1CBB-1b当CN-CBB-1N≤0时，即为最优单纯形表价值系数cjCBCN0解θ基系数基XBXNXS0XBBNIb检验数σjCBCN00(1)、确定初始基域初始基本可行解,列出初始单纯形表(3)、若有j>0，Pj

全

0，停止，

没有有限最优解；否则转(4)(2)、对应于非基变量检验数j全小于零。

若是，停止，得到最优解；若否，转(3)。(6)单纯形法的迭代步骤θ=minaim+k>0=biaim+kbrarm+k定Xr为出基变量，arm+k为主元。由最小θ比值法求：Maxj=m+k→Xm+k

进基变量j

0(4)、转(2)a1m+k0a2m+k0ar,m+k

1amm+k

0初等行变换Pm+k=…………(5)、以arm+k为中心，换基迭代从步骤(2)-(5)的每一个循环，称为一次单纯形迭代.线性规划对偶理论及对偶单纯形法(1)对偶问题的提出对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？引例——俩家具制造商间的对话：唉!我想租您的木工和油漆工一用。咋样？价格嘛……好说，肯定不会让您兄弟吃亏。

王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意好惨了，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...

王老板李老板王老板的家具生产模型：x1、

x2是桌、椅生产量。Z是家具销售总收入（总利润）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）

2x1+x2

≤50（油漆工）

x1，x2

≥0原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0对偶线性规划问题，记为（D）所得不得低于生产的获利要使对方能够接受两个原则王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y240

2y1+2y2+2y350例1通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3为对偶变量，也称为影子价格(2)对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi

(i=1,2,…,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为(P)，对偶问题简记为(D)原始问题MaxZ=CXs.t.AX≤b

X

≥0bAC≤Maxnm对偶问题MinW=Ybs.t. YAT≥C Y≥0≥MinCTATbTnm例2：求线性规划问题的对偶规划解：由原问题的结构可知为对称型对偶问题例3：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。例4：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。上式已为对称型对偶问题，故可写出它的对偶规划令则上式化为对偶关系对应表原问题对偶问题目标函数类型MaxMin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与

0

对偶问题约束类型变量

0约束

的对应关系