重大考研运筹学讲义分析

1、重庆大学运筹学重点讲义线性规划【重点】运筹学的由来和发展，运筹学的主要内容，运筹学的方法论。1、运筹学的由来和发展运筹学是本世纪新兴的学科之一，它能帮助决策人解决那些可以用定量方法和有关理论来处理的问题。它在工业、商业、农业、交通运输、政府部门和其它方面都有重要的应用。现在它已经成为经济计划、系统工程、现代管理等领域的强有力的工具。自从人类社会诞生以来，人们都一直在经历着运用和筹划的决策过程。而运筹学的一些朴素思想可以追溯到很久以前。历史上曾经记载着很多巧妙的运用事例。例如，广为人知的我国战国时期齐王和大臣田忌赛马的故事： 在谋士孙膑的策划下，田忌竟以逊色于齐王马匹的劣势获得比赛的胜利，赢得千

2、金。 又如，北宋真宗年间，皇城失火，皇宫被毁，朝廷决定重建皇宫，当时亟待解决“取土”，“外地材料的储运”和“处理瓦砾”等三项任务，在修建皇宫负责人丁渭的精心策划下，巧妙的解决了上述三项任务。三国时期的运筹大师诸葛亮，更是众所周知的风云人物。在国外人们常推崇阿基米德为运筹学的先驱人物，因为他筹划有方，在保卫叙拉古、抵抗罗马帝国的侵略中做出了突出贡献。但运筹学作为科学名词出现是在20 世纪 30 年代末（第二次世界大战） 。当时英、美对付德国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却并不好用。为此一些科学家研究如何合理运用雷达开始进行一类新问题的研究。因为它与研究技术问题不

3、同，就称之为“运用研究 ”(OperationalResearch)。为了进行运筹学研究，在英、美的军队中成立了一些专门小组。开展了护航舰队保护商船队的编队问题和当船队遭受德国潜艇攻击时，如何使船队损失最少的问题的研究。在研究了反潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁数增加到400% ；研究了船只在受敌机攻击时，提出了大船应急转向和小船应缓慢转向的逃避方法。研究结果使船只在受到敌机攻击时，中弹数由47%降到 29% 。虽然运筹学这一科学名词出现于二战中，但在这之前已有许多蕴含运筹学思想和方法的书籍和论文出现。原苏联数学家康托洛维奇的生产组织与管理中的数学方法（属于规划论的内容）出版于19

4、39 年。但是当时未得到重视，直到1960 年康托洛维奇再次发表了最佳资源利用的经济计算一书后，才受到国内外的一致重视。为此康托洛维奇于1975年得到了诺贝尔经济学奖。冯·诺伊曼等所著对策论与经济行为一书（运筹学中对策论的创始作）成书前所发表的一系列论文在1928 年就开始刊出。排对论的先驱者丹麦工程师艾尔朗1917 年在哥本哈根电话公司研究电话通讯系统时，提出了排对论的一些著名公式。二战后，美国等国家的军方仍保留一些运筹研究小组，其他多数人转向把运筹学研究用于和平时期的工商业。美、德等国家的运筹学得以蓬勃发展，出现了应用研究和理论研究相互促进的局面。运筹学得到了很快的发展。50 年

5、代中期， 钱学森、 许国志等教授将运筹学由西方引入我国。在 1956 年曾用过运用学的名字， 1957年正式更名为运筹学。他们把运筹学结合我国的特点在国内推广应用。在经济数学方面，特别是投入产出表的研究和应用开展较早，质量管理的应用也有特色。在此期间以华罗庚教授为首的一大批数学家加入到运筹学的研究队伍，使运筹数学的许多分支很快跟上了当时的国际水平。1980 年我国的运筹学会成立， 运筹学杂志创始于1982 年， 1997 年改为运筹学学报 。2、运筹学的性质与特点运筹学是多种学科的综合性科学，也是最早形成的一门软科学。当人们把战时的运筹研究取得成功的经验在和平时期加以推广应用时，面临着一个广阔

6、的研究领域。在这一领域中，对于运筹学主要研究和解决什么问题有许多说法， 至今争论不休， 实际上形成了一个在争论中发展运筹学的局面。 在这四五十年中，我们能从它的争论中看出运筹学所具有的一些特点。 .引进数学研究方法。 运筹学是一门以数学为主要工具， 寻求各种问题最优方案的学科， 所以是一门优化科学。随着生产与管理的规模日益扩大，其间的数量关系也就更加复杂，从其间的数量关系来研究这些问题，即引进数学研究方法，是运筹学的一大特点。 .系统性。 运筹学研究问题是从系统的观点出发，研究全局性的问题，研究综合优化的规律，它是系统工程的主要理论基础。 .着重实际应用。在运筹学术界，有许多人强调运筹学的实用

7、性和对研究结果的“执行”，把“执行 ”看作运筹工作中的一个重要组成部分。有的运筹学教科书中，在讲述从理论上求得最优解之后，还要讲述根据实际情况对所得解进行进一步的考察，讲述对所得最优解如何进行灵敏度分析等。第1页共20页重庆大学运筹学重点讲义 .跨学科性。由有关的各种专家组成的进行集体研究的运筹小组总和应用多种学科的只是来解决实际问题是早期军事运筹研究的一个重要特点。如二战时英国在空军部门成立的防空运筹小组其成员包括数学家、物理学家、天文学家、生理学家和军事专家多人，任务时探讨如何抵御敌人的空袭和潜艇。这种组织和这种特点一直在一些地方和一些部门以不同的形式保留下来，这往往是研究和解决实际问题的

8、需要。从世界范围来看， 运筹学的成败以及应用的广泛程度，无不与有这样的研究组织和这种组织的工作水平有关。 .理论和应用的发展相互促进。 运筹学的各个分支学科， 都是由于实际问题的需要或以一定的实际问题为背景逐渐发展起来的。 初期一些老的学科方面的专家对运筹学做出了贡献。随后新的人才也逐渐涌现，新的理论相继出现，这往往就开拓出新的领域。例如，继 Dantzig 发明了求解线性规划的单纯形方法之后，又相继出现了一批职业的线性规划工作者，由于他们从事了大量的实践活动，反过来又进一步促进了线性规划方法的进一步发展，从而又出现了椭球法，内点法等新的解线性规划的方法。目前运筹学家们仍在孜孜不倦的研究新技术

9、、新方法，使运筹学这门年轻的学科不断向前发展。3、运筹学的主要内容运筹学发展到现在虽然只有四五十年的历史，但是内容丰富，涉及面广，应用范围大，已形成了一个相当庞大的学科。它的主要内容一般应包括线性规划、非线性规划、整数规划、动态规划、多目标规划、网络分析、排队论、对策论、决策论、存储论、可靠性理论、模型论、投入产出分析等等。它们中的每一个部分都可以独立成册，都有丰富的内容。线性规划、非线性规划、整数规划、动态规划、多目标规划这五个部分统称为规划论，它们主要是解决两个方面的问题。一个方面的问题是对于给定的人力、物力和财力，怎样才能发挥它们的最大效益；另一个方面的问题是对于给定的任务，怎样才能用最

10、少的人力、物力和财力去完成它。网络分析主要是研究解决生产组织、 计划管理中诸如最短路径问题、 最小连接问题、 最小费用流问题、以及最优分派问题等。特别在设计和安排大型复杂工程时，网络技术时重要的工具。排队现象在日常生活中屡见不鲜，如机器等待修理，船舶等待装卸，顾客等待服务等。它们有一个共同的问题，就是等待时间长了，会影响生产任务的完成，或者顾客会自动离去而影响经济效益；如果增加修理工、装卸码头和服务台，固然能解决等待时间过长的问题，但又会蒙受修理工、码头和服务台空闲的损失。这类问题的妥善解决是排对论的任务。对策论是研究具有厉害冲突的各方，如何制定出对自己有利从而战胜对手的斗争策略。例如，战国时

11、代田忌赛马的故事便是对策论的一个绝妙的例子。决策问题是普遍存在的，凡属“举棋不定”的事情都必须做出决策。人们之所以举棋不定，是因为人们在着手实现某个预期目标时，面前出现了多种情况，又有多种行动方案可供选择。决策者如何从中选择一个最优方案，才能达到他的预期目标，这是决策论的研究任务。人们在生产和消费过程中，都必须储备一定数量的原材料、半成品或商品。存储少了会因停工待料或失去销售机会而遭受损失，存储多了又会造成资金积压、原材料及商品的损耗。因此，如何确定合理的存储量、购货批量和购货周期至关重要，这便是存储论要解决的问题。对于一个复杂的系统和设备，往往是由成千上万个工作单元或零件组成的，这些单元或零

12、件的质量如何，将直接影响到系统或设备的工作性能是否稳定可靠。研究如何保证系统或设备的工作可靠性，这便是可靠性理论的任务。人们在生产实践和社会实践中遇到的事物往往是很复杂的，要想了解这些事物的变化规律，首先必须对这些事情的变化过程进行适当的描述，即所谓建立模型，然后就可通过对模型的研究来了解事物的变化规律。模型论就是从理论上和方法上来研究建立模型的基本技能。投入产出分析是通过研究多个部门的投入产出所必须遵守的综合平衡原则来制定各个部门的发展计划，借以从宏观上控制、调整国民经济，以求得国民经济协调合理的发展。4、运筹学的方法论运筹学的方法论包括以下几个部分：(1) 提出需要解决的问题：提出需要解决

13、的问题，确定目标，并分析问题所处的环境和约束条件。抓住主要矛盾，舍弃次要因素。(2) 建立模型：选用合适的数学模型来描述问题，确定决策变量，建立目标函数、约束条件等，并据此建立相应的运筹学模型。(3) 求解模型：确定与数学模型有关的各种参数，选择求解方法，求出解。解可以是最优解、次优解、满意解。(4) 解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题。(5) 解的控制：通过灵敏度分析等方法，对所求的解进行分析和评价，并据此对问题的提出和建模阶段进行修正。(6) 解的实施：提供决策所需的依据、信息和方案，帮助决策者决定处理问题的方针和行动。第2页共20页重庆大学运筹学重点讲义

14、另外，这六部分之间存在下图所示关系：提出问题建立模型求解模型解的检验解的控制解的实施5、运筹学的发展趋势运筹学作为一门学科，在理论和应用方面，无论就广度和深度来说都有着无限广阔的前景。它不是一门衰老过时的学科，而使一门处于年轻发展时期的学科，这从运筹学目前的发展趋势便可看出。 .运筹学的理论研究将会得到进一步系统的、深入的发展。 数学规划是 20 世纪 40 年代末期才开始出现的。经过十多年的时间，到了20 世纪 60 年代，它已形成了应用数学中一个重要的分支，各种方法和各种理论纷纷出现，蔚为壮观。但是，数学规划也和别的学科一样，在各种方法和理论出现以后，自然要走上统一的途径。也就是说，用一种

15、或几种方法和理论把现存的东西统一在某些系统之下来进行研究。而目前这种由分散到统一、由具体到抽象的过程正在形成，而且将得到进一步的发展。 .运筹学向一些新的研究领域发展。运筹学的一个重要特点是应用十分广泛，近年来它正迅速的向一些新的研究领域或原来研究较少的领域发展，如研究世界性的问题，研究国家决策，或研究系统工程等。 .运筹学分散融化于其它学科， 并结合其他学科一起发展。 如数学规划方法用于工程设计，常常叫做“最优化方法” ，已称为工程技术中的一个有力研究工具；数学规划用于 Leontief 的投入产出模型， 也称为西方计量经济学派常用的数学工具等等。 .运筹学沿原有的各学科分支向前发展，这仍是

16、目前发展的一个重要方面。如规划论， 从研究当目标规划进而研究多目标规划，这当然可以看成是对事物进行深入研究的自然延伸。事实上，在实际问题中想达到的目标往往由多个，而且有些还是互相矛盾的。再如，从研究短期规划到研究长期规划，这种深入研究也是很自然的，因为对于不少实际问题，人们主要关心的是未来的结果。 .运筹学中建立模型的问题将日益受到重视。从事实际问题研究的运筹学工作者，常常感到他们所遇到的困难是如何把一个实际问题变成一个可以用数学方法或别的方法来处理的问题。就目前来说，关于运筹学理论和方法的研究，远远超过了对上述困难的研究，要使运筹学能保持它的生命力，这种研究非常必要。 .运筹学的发展将进一步

17、依赖于计算机的应用和发展。 电子计算机的问世与广泛的应用是运筹学得以迅速发展的重要原因。实际问题中的运筹学问题，计算量一般都是很大的。只是有了存储量大、计算速度快的计算机，才使得运筹学得应用成为可能，并反过来推动了运筹学的进一步发展。如算法复杂性这个学科就是运筹学与计算机相结合的产物。总之，运筹学虽然只有四五十年的历史， 但发展如此之快， 运筹学工作者如此之多， 都是前所未有的。运筹学作为一门学科，在理论及应用方面，无论就其广度还是深度来说，都有着无限广阔的前景。它对于加速我国的四个现代化建设必将起到十分重要的作用。线性规划模型线性规划 ( Linear Programming ，简记为 LP

18、) 问题研究的是在一组线性约束条件下一个线性函数最优问题。第3页共20页重庆大学运筹学重点讲义§ 1 1线性规划问题举例例某工厂用 3 种原料 P1, P2 , P3 生产 3 种产品 Q1 , Q2 , Q3 。已知单位产品所需原料数量如表 所示，试制订出利润最大的生产计划。单位产品所需产品原料数量 (kg)Q1Q2Q3原料可用量原料P12301500P2024800P33252000单位产品的利润（千元）354表 1.1.1分析设产品 Q j 的产量为 x j 个单位， j1,2,3 ，它们受到一些条件的限制。 首先， 它们不能取负值，即必须有 xj0, j1,2,3 ；其次，根

19、据题设，三种原料的消耗量分别不能超过它们的可用量，即它们又必须满足：2x13x215002x24x38003x1 2 x25x32000我们希望在以上约束条件下，求出x1 , x2 , x3 ，使总利润 z3x15x24x3 达到最大，故求解该问题的数学模型为：max z 3x15x24 x32x13x21500s.t2x24 x38002x25x320003x1x j 0, j 1,2,3类似这样的问题非常多。§ 1 2 线性规划模型以上例子具有这样的特征：（ 1） 问题中要求有一组变量（决策变量） ，这组变量的一组定值就代表一个问题中的具体方案；（ 2） 存在一定的限制条件（约束

20、条件） ，这些限制条件可以用一组线性等式或不等式来表示；（ 3） 有一个目标要求（目标函数） ，可以表示为决策变量的线性函数，并且要求这个目标函数达到最优（最大或最小） 。将这三个条件归结在一起，就得到线性规划问题。线性规划问题的标准形式是具有如下形式的问题：min c1 x1c2 x2cn xna11x1a12 x2a1n xnb1st.am1x1am2 x2amn xnbmx10, x20, , xn0(1.1.1)A aija ja1 j , a2 j , , amjTTbb1, b2, ,bmTm n ，c c1 ,c2 , ,cn，以 及如 果 令第4页共20页重庆大学运筹学重点讲义

21、Tx x1, x2 , , xn ，则上述标准线性规划问题可以用矩阵形式表示，min cT xst.Axbx 0(1.1.2)或nmincjx jj1ns.tajxj bj1x j0j1,2, , n(1.1.3)除了线性规划问题的标准形式之外，还有其它形式的线性规划问题，但这些问题都可以通过一些简单代换化为标准线性规划问题。（ 1）极大化问题nmax zcjx j对于目标函数为极大化问题，如j 1，可以等价地化为极小化问题，因为nnmaxc j x jminc j x jj1j1。（ 2） 不等式约束问题对于形如 a j1x1 a j 2 x2ajn xn bj 的不等式约束，可以通过引入所

22、谓“松弛变量r j ”化为等式约束 a j1x1aj 2 x2ajn xnr jbj （其中 r j0 ）；而对于形如 a j1x1a j 2 x2a jn xnbj 的不等式约束，可以通过引入所谓“剩余变量sj ”化为等式约束a j1 x1a j 2 x2a jn xnsjbj （其中 sj0 ）。（ 3） 无非负条件问题对于变量 xj 无非负约束条件问题，可以定义x jxj1xj2 , x j10, x j20 ，从而化为非负约束。因此，本章主要讨论标准形式的线性规划问题（1.1.1）的性质和求解方法。线性规划问题的可行域及最优性条件§ 2 1 线性规划问题的可行域（ 1） 凸组

23、合与凸集定义设 SRn 是 n 维欧氏空间中的一个点集，xS ， yS， 0,1 ，称为 x 和 y 的凸组合。zx(1) y定义 1.2.2 设 SRn 是 n维欧氏空间中的一个点集，若对任何x S, y S 与任何 0,1 ，都有x(1) yS就称 S 是一个凸集。凸集与非凸集如图1.2.1 所示。x2x21xx1第5页共20页凸集非凸集图凸集与非凸集重庆大学运筹学重点讲义（ 2） 线性规划问题的可行域与凸集对于标准线性规划问题（1.1.1），令 D xRn | Axb, x 0 表示它的可行域。定理 1.2.1线性规划问题（ 1.1.1 ）的可行域 D xRn| Axb, x0 是凸集。

24、定义 1.2.3给定 bR1 及非零向量 a R n ，称集合H xRn| aT xb是 Rn 中的一个超平面。定理 1.2.2由超平面 H 产生了两个闭半空间H x Rn | aT x b 、 H x Rn | aT x b都是凸集。定义 1.2.4称集合S x Rn | aiT x bi , i 1, , p; aiT x bi ,ip 1, , p q为多面凸集。非空有界的多面凸集称为凸多面体。因此，线性规划问题（1.1.1）的可行域 D xRn | Axb, x0 是多面凸集。（ 3） 极点和极方向定义 1.2.5设 S 为凸集， xS。若对任何 yS ， zS ， yz，以及任何 0

25、1，都有xy(1) z则称 x 为凸集 S 的一个极点。按此定义， 平面上长方形的四个角点就是长方形区域的全部极点。平面图形中每个顶点至少是两条线的交点。一般对标准形式线性规划问题（1.1.1 ），当可行区域非空时，可以证明其可行域D 一定有极点，每个极点至少是n m 个超平面的交点（参见定理1.3.2）。至于多面凸集D 的极点个数的有限性，在下一段我们给出了顶点的代数结构后，结论将会更清楚。定义 1.2.6设 SRn 为凸集， dRn ， d0。若存在 xS 以及所有0 ，都有xdS则称 d 为凸集 S 的一个方向。定义 1.2.7设 SRn 为凸集， dRn 是凸集 S 的一个方向。若对凸

26、集S 的任何方向 d1 ， d 2 ，以及任何10，20，当d1d12 d 2时，必有 d 1d 20，则称 d 为凸集 S 的一个极方向。极点、方向和极方向如图1.2.2 所示。x21AddD定理1.2.3 设 x1, xk 为 Dx | Axb, x0 的所有极点， d 1, d l 为极方向，则 xD 当且仅当 x 满足0Bd2x1图极点（ A、 B）、方向（ d、 d1、 d2）和极方向（ d1、 d2）第6页共20页重庆大学运筹学重点讲义klxi xij d ji 1j1ki1i1ij0,i1,k0, j1, l即 xD 的充分必要条件为 x可以表示为 D 的极点的凸组合与极方向的非

27、负线性组合。注：这种表示方法不一定唯一。多面凸集中点的表示如图1.2.3 所示。x2xx3d112121 x1 1x1d2 ddDx1xxx43d 2§ 2 2 线性规划问题的最优解122（ 1）x42 x12 x3 d两个变量线性规划问题的图解法3d我们可以直观了解可行区域D 的结构， 同时还可利用目标函数如果一个线性规划问题只x有两个变量，与可行区域的关系利用图解法求解该问题。x1例 1.2.1求解线性规划0x2d2图 1.2.3minzx1x2多面凸集中点的表示图示2x1x22st.x12x22x1x25x10, x20解： 可行区域 D 如图 1.2.4 所示。在区域0A1

28、A2 A3 A4 0 的内部及边界上的每一个点都是可行点，目标函数的等直线 zx1 x2 (z 取定某一个常值 )的法线方向（梯度方向）(1,1)T是函数值增加最快的方向（负梯度方向是函数值减小最快的方向）。沿着函数的负梯度方向移动，函数值会减小，当移动到点A2(1,4)T时，再继续移动就离开区域D 了。于是 A2 点就是最优解，而最优值为z14 3。x22x1x22z3A2z1.5z0x1 x25x1 2x220、A1、A2、A3、A4可以看出，点都是该线性规划问题可行域的极点。A1D如果将例1.2.1 中的目标函数改为min z 4x12x2 A3，可行区域不变， 用图解法求解的过程如图

29、1.2.5所示。x10A4图x2A2z0第7页共20页x1x2 5x12x22A1D重庆大学运筹学重点讲义由于目标函数 z 4x1 2x2 的等值线与直线A1 A2 平行，当目标函数的等值线与直线A1 A2 重合 (此时z4 ) 时，目标函数 z 4x12x2 达到最小值4，于是，线段 A1 A2 上的每一个点均为该问题的最优解。 .特别地，线段A1 A2的两个端点，即可行区域D的两个顶点A(0,2)TA(1,4)T均是该线性规划问1，2题的最优解。此时，最优解不唯一。例 1.2.2用图解法解线性规划minz2x1x2x1x21s.tx13x23x10, x2 0解：该问题的可行区域如图1.2

30、.6 所示。x2z2x1x2x13x23x1 x2 1A(2, 1)T与上例求解方法类似，目标函数z 2 x1 x2沿着它的负法线方向移动，由于可行域D 无D界，因此，移动可以无限制下去，而目标函数值一直减小，所以该线性规划问题无有限最优解，即该问题无界。x1从图解法的几何直观容易得到下面几个重要结论：0B。线性规划的可行区域D 是若干个半平面的交集，它形成了一个多面凸集（也可能是空集）对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域D 的某个顶点上达到。在图 1.2.6这种情况下还包含两种情况：有唯一解和有无穷多解。如果可行域无界，线性规划问题的目标函数可能有无界的情况。（ 2）

31、线性规划问题的最优解对于具有 n 个变量的一般的线性规划问题也有类似的结论。这可以通过多面凸集的表示定理（定理1.2.3）得到。定 理 1.2.4如 果 标 准 线 性 规 划 问 题 （ 1.1.1 ） min cT x : Axb, x 0的可行域D xnR | A x , b x0x1 , , xkD 的所有极点，d 1, ,d l非空，为为 D 的所有极方向，则有： 如果 cT d j0 （ j 1,2,l ），则问题（ 1.1.1）有有限最优解，并且若mincT xi : i1,2, kcT x p，且满足上面条件的极点唯一，则x p 为问题（ 1.1.1）的唯一最优解；若mincT

32、 xi : i1,2,kcT x p1cT x ps ，则最优解不唯一， xp1、 、 x ps 都是问题（ ）的最优解，另外，所有 xp1、 、 x ps 的凸组合都是问题 （ ）的最优解； 如果存在 q1,2, l满足 cT d q0 ，则问题（ 1.1.1）无有限最优解； 如 果 对 所 有 j （ j1,2, , l ） 都 有 cT d j0 ， 且 存 在 r1,2, l 满 足 cT d r0 ，min cT xi : i 1,2,kcT x p，则问题（ 1.1.1）的最优解不唯一， xx pr d r都是其最优解，其中第8页共20页重庆大学运筹学重点讲义r0 。定理 1.2.

33、4 从代数角度给出了一般标准线性规划问题（1.1.1）所有解的组成情况：当目标函数的梯度与可行域的所有极方向夹角小于900 时，则问题有最优解；另外，在这种情况下，当目标函数只在一个极点上达到最小，则问题有唯一最优解；当目标函数在多于一个极点上同时达到最小，则问题有无穷多最优解。当目标函数的梯度与可行域的某一极方向夹角大于900 时，则问题无有限最优解。当目标函数的梯度与可行域的所有极方向夹角都不大于900 时，并且与某一个极方向的夹角恰好为900，同时，目标函数至少在一个极点上达到最小，则问题有无穷多最优解。下面要讲到的单纯形方法正是通过一种算法来实现和检验上面的各种情况。（ 3）线性规划问

34、题的最优性条件Kuhn 和 Tucker 从理论上给出了线性规划问题的最优性条件，从理论上圆满解决了线性规划问题最优解所满足的条件。T定理5 对于标准线性规划问题（ LP ）： min cx: Ax bx, 0 ， x 是其最优解的充分必要条件为存在 w ， v 使得下式成立：Axb, x0cAT wv 0,v 0vT x0(1.2.2)但是，仅仅从这个定理出发，很难直接来求解线性规划问题，因此，下面我们将介绍用于求解线性规划问题的一种迭代方法单纯形方法。求解线性规划问题的单纯形方法§ 3 1基本可行解及线性规划问题的基本定理（ LP）： minT，假设秩 ( A) m ，故 A 中

35、必有 m 个考虑标准形式的线性规划问题cx: Ax bx,0线性无关的列向量，它们构成满秩方阵B （为叙述方便，假定 B(A1, A2, Am) ），把 A 中其余各列组成的子阵记为 N ，即 A (B, N ) ，再把 x( x1 , x2 , xn )T 的分量也相应地分为两部分，记为xB 和 xN ，则 Axb 可记作BxB Nx Nb即xBB 1b B 1 NxNxxB给 xN 任意一组值 xN ，则可得到对应的xNxB 的一组值 xB ，于是便是约束方程组 Axb 的一个解。xB 1b若令 xN0 ，就得到约束方程组的一种特殊形式的解0。定义 1.3.1设 B 是秩为 m 的约束矩阵

36、 AR m n 中的一个 m阶满秩子方阵， 则称 B 为一个基 (或基阵 ) 。B 中 m 个线性无关的列向量称为基向量，变量x 中与之对应的 m 个分量称为基变量，其余的分量称为非xBB 1 bx0基变量。令所有的非基变量取值为零，得到的解xN1，称为相应于 B 的基本解。当 B b 0时，称基本解 x 为基本可行解，这时对应的基B 称为可行基。定理 1.3.1可行解 x 是基本可行解的充要条件是它的正分量所对应的A 中列向量线性无关。由定义知，基本可行解至少有nm 个分量为零，从几何上看它至少属于n m 个超平面的交集。定理 1.3.2x 是基本可行解的充要条件是x 是可行域 D 的极点。

37、定理 1.3.2是一个非常重要的定理，它将线性规划问题可行域的极点与线性规划问题的基本可行解一第9页共20页重庆大学运筹学重点讲义一对应起来，因此，我们前面讨论的线性规划问题的最优解（如果有的话）是在其可行域的极点上达到，对应的就是在基本可行解上达到。所以，我们以后只需要讨论基本可行解。定 理 1.3.3一 个 标 准 形 式 的 线 性 规 划 问 题 （ 1.1.1 ）： minD x Rn | Axb, x 0 非空，则至少有一个基本可行解。定理 1.3.3给出了基本可行解的存在性。T定理 1.3.4若标准形式的线性规划问题（1.1.1）： mincx: Ax bx,存在一个基本可行解是

38、最优解。cTx: Axbx,0，若可行域0有有限的最优值，则一定由基本可行解与可行基的这种对应关系，我们知道给定一个标准形式的线性规划问题，它最多有个可行基， 因而基本可行解的个数不会超过Cnm ，从而多面凸集 D 的顶点个数不会超过 Cnm 个。由定理可知，线性规划问题实际上是一个组合问题：即在有限个可行解中找出最优解。一个基本可行解 x ，如果它的所有的基变量都取正值，称它是非退化的；如果有的基变量也取零值，称它为退化的。一个线性规划问题，如果它的所有基本可行解都是非退化的，就说该问题是非退化的，否则说它是退化的。§ 3 2 求解线性规划问题的单纯形方法考虑标准线性规划问题（ L

39、P）：min cT xAxbs.tx0Cnm解线性规划问题著名的单纯形方法(Simplex Method)是 G.B.Dantzig在 1947 年提出的。本节我们介绍单纯形方法的理论、基本计算步骤及具体实施运算的单纯形表。（1） 假设假设 1.3.1D xRn | Axb, x 0；假设 1.3.2秩 ( Am n )m, mn ；假设 1.3.3A 中存在满秩矩阵B 满足 B 1b0 ；假设 1.3.4所考虑的（ LP）问题是非退化的。上面四个基本假设是为了方便讨论单纯形方法而做的，实际上，在我们学完单纯形方法后会发现，这四个假设都不是必须的。我们已经知道，对于一个标准线性规划问题（ LP），如果它有最优解，则必可在某一基本可行解处达到，因而只需在基本可行解集合中寻求即可。单纯形方法的主要思想就是先找出一个基本可行解，判别它是否为最优解，如不是，就找一个更好的基本可行解，再进行判别，如此迭代进行，直至找到最优解，或者判定该问题无有限最优解。（ 2）基本可行解的一些性质由假定 1.3.3 和 1.3.4，已找到了一个可行基B ，对应