重大考研运筹学讲义

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

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

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

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

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

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

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

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

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

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

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

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

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

14、所示关系:5、运筹学的发展趋势运筹学作为一门学科，在理论和应用方面，无论就广度和深度来说都有着无限广阔的前景。它不是一 门衰老过时的学科，而使一门处于年轻发展时期的学科，这从运筹学目前的发展趋势便可看出。运筹学的理论研究将会得到进一步系统的、深入的发展。数学规划是20世纪40年代末期才开始出现的。经过十多年的时间，到了20世纪60年代，它已形成了应用数学中一个重要的分支，各种方法和各种理论纷纷出现，蔚为壮观。但是，数学规划也和别的学科一样，在各种方法和理论出现以后，自然要走 上统一的途径。也就是说，用一种或几种方法和理论把现存的东西统一在某些系统之下来进行研究。而目 前这种由分散到统一、由具体

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

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

17、量一般都是很大的。只是有了存储量大、计算速度 快的计算机，才使得运筹学得应用成为可能，并反过来推动了运筹学的进一步发展。如算法复杂性这个学 科就是运筹学与计算机相结合的产物。总之，运筹学虽然只有四五十年的历史，但发展如此之快，运筹学工作者如此之多，都是前所未有的。运筹学作为一门学科，在理论及应用方面，无论就其广度还是深度来说，都有着无限广阔的前景。它对于 加速我国的四个现代化建设必将起到十分重要的作用。线性规划模型线性规划（Linear Programming，简记为LP）问题研究的是在一组线性约束条件下一个线性函数最优问题。第3页共20页重庆大学运筹学重点讲义 1. 1线性规划问题举例例1.

18、1.1某工厂用3种原料Pl，B，P3生产3种产品Q，Q2,Q3。已知单位产品所需原料数量如表1.1.1所示，试制订出利润最大的生产计划。单位产品所需产品_ _原料数量（kgj、Q1Q2Q3原料可用量P12301500P2024800P33252000单位产品的利润（千兀）354表 1.1.1分析 设产品Qj的产量为Xj个单位，j 1,2,3，它们受到一些条件的限制。首先，它们不能取负值,即必须有Xj0,j 1,2,3 ;其次，根据题设，三种原料的消耗量分别不能超过它们的可用量，即它们又必须满足：2x13x215002X24X38003x12X25x32000我们希望在以上约束条件下，求出X1,

19、 X2, X3，使总利润Z 3X1 5X2 4X3达到最大，故求解该问题的数学模型为：max z3x15x24X32x13x21500s.t2x24X38003x12x25X32000Xj0,j 1,2,3类似这样的问题非常多。 1. 2线性规划模型以上例子具有这样的特征：（1） 问题中要求有一组变量（决策变量），这组变量的一组定值就代表一个问题中的具体方案；（2） 存在一定的限制条件（约束条件），这些限制条件可以用一组线性等式或不等式来表示；（3）有一个目标要求（目标函数），可以表示为决策变量的线性函数，并且要求这个目标函数达到 最优（最大或最小） 。将这三个条件归结在一起，就得到线性规划问

20、题。线性规划问题的标准形式是具有如下形式的问题：min c1x1 c2x L cnxna12X2La1nXnb1L LL L LL LL L LLs.tam1Xlam2X2LamnXnbmX10, X20,L,Xn0(1.1.1)第4页共20页重庆大学运筹学重点讲义T果令 A 讦 m n ， aja1j,a2j 丄，amjTX1，X2丄，Xn，则上述标准线性规划问题可以用矩阵形式表示,min cCq,C2 丄TxstAxs.tminnCjXjj 1najXjj 1TT,Cnb Q 丄,bm(1.1.2)0 j 1,2,L ,n除了线性规划问题的标准形式之外，还有其它形式的线性规划问题，但这些问

21、题都可以通过一些简单 代换化为标准线性规划问题。（1）极大化问题Xj(1.1.3)对于目标函数为极大化问题，nmax zCj Xj如j 1 ，可以等价地化为极小化问题，nmaxcjxjminj 1j（2）不等式约束问题CjXj1对于形如aj1X1 束 aj1X1aj2X2Laj2X2ajn xnrjbj的不等式约束，可以通过引入所谓“松弛变量 bj （其中 rj 0）；ajn Xn束，可以通过引入所谓（3）“剩余变量无非负条件问题Sj ”化为等式约束而对于形如aj1X1a j 2 X2Laj2X2a jn xnrj ”化为等式约Lajn Xn bj的不等式约Sj bj （其中 Sj 0对于变量

22、Xj无非负约束条件问题，可以定义Xj因此，本章主要讨论标准形式的线性规划问题（1Xj1.1.1)2 1Xj ,xj的性质和求解方法。0,Xj20，从而化为非负约束。线性规划问题的可行域及最优性条件 2. 1线性规划问题的可行域（1）凸组合与凸集定义1.2.1设S Rn是n维欧氏空间中的一个点集，X S , y S,z x （1 ）y为x和y的凸组合。0,1，称定义1.2.2设S Rn是n维欧氏空间中的一个点集，若对任何x S, y S与任何,1】，都有x (1 )y S就称S是一个凸集。凸集与非凸集如图1.2.1所示。凸集2 X20页X重庆大学运筹学重点讲义（2）线性规划问题的可行域与凸集对于

23、标准线性规划问题（1.1.1），令D x Rn | Ax b, x 0表示它的可行域。 0是凸集。定理1.2.1线性规划问题（1.1.1 ）的可行域R1及非零向量aRn定义1.2.3给定bD xRn | Ax b,x是Rn中的一个超平面。定理1.2.2由超平面都是凸集。定义1.2.4，称集合xRn|aTx bH产生了两个闭半空间H x Rn|aTxb、xRn| aT x b称集合S x Rn | aT x bi, i为多面凸集。非空有界的多面凸集称为凸多面体。1,T,P；ai xbi,i1, , p q因此，线性规划问题（1.1.1 ）的可行域D（3） 极点和极方向定义1.2.5设S为凸集，x

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

25、1.2.7任何10 ,n12d R是凸集S的一个方向。若对凸集S的任何方向d , d ,以及1 2d1d2d1时，必有d极点、方向和极方向如图d2，则称d为凸集S的一个极方向。.2.2所示。d2)定理 1.2.3当x满足1为极方向，贝U x D当且仅重庆大学运筹学重点讲义kjdjiXiXi 1kii 1i 0,i 1,L ,k(1.2.1)j 0, j 1L ,l即x D的充分必要条件为 x可以表示为D的极点的凸组合与极方向的非负线性组合。 注：这种表示方法不一定唯一。多面凸集中点的表示如图1.2.3所示。X2xX* I II 1 I 3X11X - i K ri * * II n I ! 1

26、 laV* m1d12d2X 2. 2线性规划问题的最（1） 两个变量线性规划如果一个线性规划问题只有两个变， 与可行区域的关系利用图解法求解该问题二例1.2.1求解线性规划0 Xd24X12X3d21我们可以直观了解可行区域D的结构，同时还可利用目标函数X1图1.2.3多面凸集中点的表示图示2为 x22x1 2x22s.tx1 x25X 0,x20解：可行区域D如图1.2.4所示。在区域4人2人3人40的内部及边界上的每一个点都是可行点，目标函数的等直线zX1 X2（z取定某一个常值）的法线方向（梯度方向）（1,1/是函数值增加最快的方向（负梯度方向是函数值减小最快的方向）。沿着函数的负梯度

27、方向移动，函数值会减小，当移动到点A2（1,4）T时，再继续移动就离开区域D 了。于是A2点就是最优解，而最优值为 z 1 43。x22可以看出，点、A、A；、?2x-izX10A4z 3如果将例1.2.1中的目标函 所示。-*X11.50X25 X1 2x22汕问题可行域的极点。可行区域不变，用图解法求解的过程如图1.2.5图 1.2.40A2第7页共20页r. y.: DA1X2、x1x252x22重庆大学运筹学重点讲义由于目标函数Z 4X1 2X2的等值线与直线 A1A2平行，当目标函数的等值线与直线A1A2重合（此时z4）时，目标函数z 4X1 2x2达到最小值4,于是，线段A1A2上

28、的每一个点均为该问题的最优解。特别地，线段 A1 A2的两个端点，即可行区域D的两个顶点A1 （0,2）T , A2（1,4）T均是该线性规划问题的最优解。此时，最优解不唯一。例1.2.2用图解法解线性规划minz2%X1X21s.tX13x23该问题的可行区域如图1.2.6所示。X10,x2 0X2z2x1X2X2解：与上例求解方法类似， 界，因此，移动可以无限制下 无界。A去,从图解法的几何直观容易得到下面几XiX21.线性规划的可行区域 D是若x1 3x2（2， 1）移动，由于可行域D无；有限最优解，即该问题Xi半平面的交集，它形成了一个多面凸集（也可能是空集）。.对于给定的线性规划问题

29、，如果它有最优解6最优解总可以在可行域D的某个顶点上达到。在这种情况下还包含两种情况：有唯一解和有无穷多解。.如果可行域无界，线性规划问题的目标函数可能有无界的情况。（2） 线性规划问题的最优解对于具有n个变量的一般的线性规划问题也有类似的结论。这可以通过多面凸集的表示定理（定理1.2.3）得到。疋D x理 1.2.4Rn | Ax如果cTd j如果标准线性规划问题（1.1.1 ） min c X：Ax b,x 0的可行域 b,x 0非空，x1,L ,xk为d的所有极点，d1丄，川为D的所有极方向，则有：0 （ j 1,2,L ,l ）,则问题（1.1.1）有有限最优解，并且若T i A -

30、.|T pmin c x : i 1,2,L , k c x且满足上面条件的极点唯一，则xp为问题（1.1.1 ）的唯一最优解；若min cTxi: i 1,2,L ,kcT xP1 LcTxPs则最优解不唯一，xP1、L、xPs都是问题（1.1.1）的最优解，另外，所有xP1、L、xPs的凸组合都是问题（1.1.1） 的最优解；如果存在q1,2丄满足cTdq0，则问题（1.1.1 ）无有限最优解;匕2丄，1）都有cTdj 0，且存在r 1,2丄，l满足cTdr 0 ,min cT x1 : i 1,2,L ,kcT pC x，则问题（1.1.1 ）的最优解不唯一,x xPrd都是其最优解，其

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

32、 验上面的各种情况。（3）线性规划问题的最优性条件Kuhn和Tucker从理论上给出了线性规划问题的最优性条件，从理论上圆满解决了线性规划问题最优 解所满足的条件。定理1.2.55对于标准线性规划问题（LP）： min CX：Ax b, x ，x是其最优解的充分必要条 件为存在w， v使得下式成立：Ax b,x 0vTx0c AT w v 0,v 0(122)但是，仅仅从这个定理出发，很难直接来求解线性规划问题，因此，下面我们将介绍用于求解线性规 划问题的一种迭代方法单纯形方法。求解线性规划问题的单纯形方法 3. 1基本可行解及线性规划问题的基本定理考虑标准形式的线性规划问题（LP）:线性无关

33、的列向量，它们构成满秩方阵 B 成的子阵记为N，即A （B, N），再把x 则Ax b可记作min cTx:Ax b,x 0，假设秩（A） m，故a中必有m个（为叙述方便，假定B （ A, A2,L , Am）,把A中其余各列组 （XX2， , xn ）的分量也相应地分为两部分，记为xB和xN ,BxB Nxn b1 1xbB b B Nxnxb_x _给Xn任意一组值Xn，则可得到对应的Xb的一组值xB，于是Xn便是约束方程组 Ax b的一个解。B 1bx若令XN 0，就得到约束方程组的一种特殊形式的解0。定义1.3.1设B是秩为m的约束矩阵A Rmn中的一个m阶满秩子方阵，则称B为一个基（

34、或基阵）。 B中m个线性无关的列向量称为基向量，变量x中与之对应的 m个分量称为基变量，其余的分量称为非XbB 1bX基变量。令所有的非基变量取值为零，得到的解Xn0,称为相应于B的基本解。当B 1b 0时，称基本解X为基本可行解，这时对应的基B称为可行基。定理1.3.1可行解X是基本可行解的充要条件是它的正分量所对应的A中列向量线性无关。由定义知，基本可行解至少有n m个分量为零，从几何上看它至少属于n m个超平面的交集。定理1.3.2 x是基本可行解的充要条件是 X是可行域D的极点。定理1.3.2是一个非常重要的定理，它将线性规划问题可行域的极点与线性规划问题的基本可行解一第9页共20页重

35、庆大学运筹学重点讲义min cTx：Ax b,x 0，若可行域一对应起来，因此，我们前面讨论的线性规划问题的最优解（如果有的话）是在其可行域的极点上达到, 对应的就是在基本可行解上达到。所以，我们以后只需要讨论基本可行解。定理1.3.3 一个标准形式的线性规划问题（1.1.1）:D x Rn|Ax b,x 0非空，则至少有一个基本可行解。定理1.3.3给出了基本可行解的存在性。定理1.3.4若标准形式的线性规划问题（1.1.1）： min C x:Ax b,x 0有有限的最优值，则一定 存在一个基本可行解是最优解。由基本可行解与可行基的这种对应关系，我们知道给定一个标准形式的线性规划问题，它最

36、多有个可行基，因而基本可行解的个数不会超过Cn，从而多面凸集 D的顶点个数不会超过 Cn个。由定理1.3.4可知，线性规划问题实际上是一个组合问题：即在有限个可行解中找出最优解。一个基本可行解 x，如果它的所有的基变量都取正值，称它是非退化的；如果有的基变量也取零值， 称它为退化的。一个线性规划问题，如果它的所有基本可行解都是非退化的，就说该问题是非退化的，否 则说它是退化的。 3. 2求解线性规划问题的单纯形方法考虑标准线性规划问题（LP）:. Tmin c xAx bs.t x 0解线性规划问题著名的单纯形方法（Simplex Method）是G.B.Dantzig 在1947年提出的。本

37、节我们介绍单纯形方法的理论、基本计算步骤及具体实施运算的单纯形表。（1）假设假设 1.3.1 D x Rn | Ax b,x 0；假设 1.3.2 秩（Am n）m, m n ;1假设1.3.3 A中存在满秩矩阵 B满足B b 0 ;假设1.3.4所考虑的（LP）问题是非退化的。上面四个基本假设是为了方便讨论单纯形方法而做的，实际上，在我们学完单纯形方法后会发现，这 四个假设都不是必须的。我们已经知道，对于一个标准线性规划问题（LP）,如果它有最优解，则必可在某一基本可行解处达到，因而只需在基本可行解集合中寻求即可。单纯形方法的主要思想就是先找出一个基本可行解，判别它 是否为最优解，如不是，就

38、找一个更好的基本可行解，再进行判别，如此迭代进行，直至找到最优解，或 者判定该问题无有限最优解。（2）基本可行解的一些性质由假定1.3.3和1.3.4，已找到了一个可行基B，对应一个非退化的基本可行解x，此时可将方程组Ax b化成与之等价的方程组1 1(1.3.1)(1.3.2)Xb B 1Nxn B 1b为叙述方便，这里假定B 4 A丄，Am) , Xb (X1，X2丄，Xm)T，且有B % 0。记向量AjB 1Aj (a1j,a2j,amj)T, j 1, ,n1Tb B b (b1,bm)则(1.3.1)式可写成n _XbXjAj bj m 1或1 xB B NxN b第10页共20页重

39、庆大学运筹学重点讲义对目标函数cTx作相应的变换，记c为J 的系数，则/ T T、(cB)cN )其中Cb是基变量对应的系数，Cn是非基变量对应Tz c XcB(bcBbcBb_T _X对应的目标函数值用Z。表示，则z0 CXAj是一个第j个分量为1,其余分量为0的m维向量。故有0,jcBb。由于T -Cb Aj CjjCb AjT cTB1A(N)TTCB XB CN XNB NXn ) Cn Xn (cTB 1N cN)Xn n(cB Aj Cj)Xjm 1(A1,cj，j1,1,cT (0,cTB(1.3.3),Am)B B I m 故当 j 1L , m 时,m,n1Nn)cN )从而

40、（1.3.3）式可记为cBbTx经过变换后与原问题等价的问题是（对应于基本可行解minb 0)Zo(1.3.4)st XbXB 1NXn0(1.3.5)它充分反映了基本可行解 X的特征。最优性准则定理1.3.5如果（1.3.4）式中0，则X为原问题的最优解。另外，如果对应于非基变量的每个j 0，则x为原问题的唯一最优解； 如果对应于非基变量的某个j优解不唯一。无有限最优解情况0，则X虽然为原问题的最优解，但此时最，而向量AkB1Ak0，则原问题无有限定理1.3.6如果（1.3.4）中的向量 的第k个分量k 0 dAkdek最优解。另外，0是（LP ）问题的一个极方向。 基可行解可以改进的条件定

41、理1.3.7如果（1.3.4）中的向量 的第k个分量 k 0， 另一个基可行解$，满足cT $（3）基可行解的改进基可行解的改进的思想是：且同时向量人从原来的非基变量中选一个变量让它变为基变量,B人| 0，则原问题存在基本可行解，必须从原来的基变量中选一个让它变为非基变量。也就是说新基与原有的基有的列向量，仅有一列向量不同。应该选择哪一个非基变量变为基变量呢？若已知为保证新得到的解仍是m 1个相同k 0，因为m 1 k n，与k相对应的是非基变量Xk，因此当Xk变为基变量时，它的值由零变为正数，比如说第11页共20页重庆大学运筹学重点讲义Xk0，其余的非基变量仍取值为零。由(1.3.4)式知对

42、应新解的目标函数值为zz。的取值大小应以保证新解是基本可行解为原则。寻找x的具体方法如下，取kz。至显然A?为使?0，只要b Ak 0即可,所以令Ak0AdAk0AxminaikekAd|aik0,i1,mbrark从而保证了 X 0。因而 解。X的各分量为：?是可行解。由于向量组,Ar1, Ak, Ar,Am线性无关，则(1.3.6)球是基本可行br由b 0，得ark0，因此有由于相应于基本可行解 x的向量 数向量，它的各个分量称为检验数。Xibrark0,jcT?cT xTT 1 .2瓦1Lark,m,i r1L ,n,j k(137)CbB A c有重要的作用，我们称它为基本可行解X的检

43、验注意，由假设1.3.4，在(1.3.6)式中最小比值是唯一的。如果检验数向量有不止一个正分量，可以任意选取一个正分量作为定理中的k 0。而选择正值k的最好策略是什么？这个问题至今尚未解决。一般常取最大的那个k，所对应的 兀“入基”，而(1.3.6)算出的br.ark所对应的Xr “出基”，这就是从一个基本可行解X移动到另一个“更好”的基本可行解?的过程。新旧基本可行解?与X的差别在于以原来的非基变量Xk代替原来的基变量人，而成为第r个基变量，而Xr变为非基变量。整个过程称为换基，或说进行了一次迭代，称 A为退出基列，Ak为进入基列，Xr为离基变量，Xk为进基变量。(4)单纯形方法上面三个定理

44、给出了单纯形法的迭代步骤，给定一个基本可行解X，计算与其对应的检验数向量。若 0，则X就是最优解；如果的某个分量 k 0 ,而人 0，则原问题无界；如果k 0且人含 有正分量，那么按照公式(1.3.6)和(1.3.7)式求出另一个基本可行解 X 使目标函数值减少k个单位。得到新的基本可行解后，再按以上程序进行，这样便可得到一个基本可行解的序列。在假设1.3.4的前提下，第12页共20页重庆大学运筹学重点讲义每迭代一次目标函数值严格减少，因而序列中的基本可行解不可能重复出现。由于基本可行解的个数是有 限的，故最终一定能找到最优解或者判定问题无界，所以得到如下定理。定理1.3.8对于任何非退化的线

45、性规划问题，从任何基本可行解开始，经过有限多次迭代，或得到一 个基本可行的最优解，或做出该线性规划问题无界的判断。在单纯形方法的一次迭代过程中，迭代前后的两个基有 m 1个相同的列向量，这样的基称为相邻基。在几何上，可以严格证明相邻基所对应的是可行域多面凸集D的相邻顶点。因此直观的说，单纯形方法就是从可行域多面凸集的一个顶点迭代到与其相邻的另一个顶点，直至找到最优解或判定问题无界。下面给 出具体的计算步骤。单纯形方法步骤第1步找一个初始的可行基 B;第2步求出对应的典式及检验数向量:第3步求kmax j | j 1, n；Xbxb第4步若k0，停止。已找到最优解Xn0及最优值z cBb ；第5

46、步若Ak0，停止.原问题无界；min|aik0,i1, ,mbr第6步求aikark ；第7步以Ak代替ABr得到新的基，转第2步。直接用公式进行单纯形法的迭代计算，对于用笔计算是很不方便的，其中最复杂的是进行基变换，但实施基变换所用的实际上是消元法。因此，可以将单纯形法的全部计算过程在一个类似增广矩阵的数表上 进行，这种表格称为单纯形表 3。解线性规划问题的进一步讨论及例 4. 1两阶段法及关于单纯形方法的几点说明(1) 两阶段方法求初始可行解设原问题为Tmin c x0)(1.4.1)第一个阶段是判断线性规划是否有可Ax b (b s.tx 0所谓两阶段法,就是将线性规划问题的求解过程分成

47、两个阶段， 行解，如果没有可行解，计算停止；如果有可行解，按第一阶段的方法可以求得一个初始基本可行解，使 运算进入第二阶段。第二阶段使从这个初始的基本可行解开始，使用单纯形方法或者判定线性规划问题无 界，或者求得一个最优解。第一阶段：给问题(141)增加m个人工变量Xa (Xn1， ,Xnm)，用单纯形法解如下的辅助问题min gxis.tAx xaX 0,xa(1.4.2)n个变量的标准形式线性规划问题，且i n 1并且，问题(1.4.2)满足假设131、1.3.2和1.3.3，是一个有 m人工变量对应的 m列构成了一个 m阶单位矩阵，基本可行解x 0, Xab ，所对应的目标函数值为第13

48、页共20页重庆大学运筹学重点讲义gobiii，可以用单纯形方法求解。问题（241）与其辅助问题（242）有如下关系：若原问题（241）的可行区域 D，辅助问题（242）的可行区XXD域为D，则X D 和 Xa是等价的。而min g 。由于Xa，故辅助问题（2.4.2）的目标函数有下界如下三种可能情况：情形1问题（2.4.2）的最优值g，且人工变量已得到原问题（2.4.1）的一个基本可行解。XD（2.4.2）的当Xa0的解 ，当且仅当有g ，从而问题（242）必有最优解。计算结果有Xj, j n 1, ,n m，皆为非基变量，此时我们情形2问题（2.4.2）的最优值g ，说明原问题没有可行解。这

49、时或者原问题的约束方程组不相容， 即有秩（A）秩（A,b）；或者方程组虽相容，但没有非负解。总之，D，运算结束。情形3问题（2.4.2）的最优值g ，而某些人工变量虽然取值为零，但仍是基变量。当情形1出现时，把人工变量对应的列从单纯形表中去掉，得到原问题的一个初始可行解，直接转入第二阶段：即对原目标函数 z CTX应用通常的单纯形法求解。当情形3出现时，设基变量为XB1，XBr， XBm，XBr为一人工变量，显然有0。我们观察表中第r行中非基变量的系数，即考察arj，如果它们不全为零，设 ars ，以ars为转轴元进行一次旋转变换（注意，此时不要求ars ）后，由于br ，所以，故g值不变，最

50、优解也不变，只是将零值的Xs变成了基变量，代替了取零值的人工变量XBr，这样使基变量中减少了一个人工变量（这种情况是退化情况）。如果非基变量的系数 arj都为零，则这时有秩（A）秩（A） m，这表明第r个约束方程是多余的， 将它删去就可以了。如果基变量中还有其他人工变量，重复刚才的过程，直至基变量中没有人工变量。事实上，通过两阶段方法我们已经解决了开始介绍单纯形方法的四个假设中的三个。同样是使用单纯形方法从算法角度已经解决了：（ 1）什么条件下D ；（ 2）什么条件下秩（A） m ；以及（3）什么条1件下B b 的问题。更重要的是，解决这些假设并没有用到其它工具，仍然是单纯形方法。因此，单纯

51、形方法在求解线性规划问题时是封闭的。（2）关于退化问题5设给定了线性规划的一个可行基，它对应的基本可行解是 几 A所以 XB, AB1 XB2 AB2 L XBm ABmmin zC1X1LCnXna1 xa12X2LCnXna21 Xa?%La2n Xnb2s.t L L LL L LLL L L Lam1X1am2 X2LamnXnbmXj ，j1,L，n，对应的基阵是AB1，AB2，L，ABm X(1.4.3) 。如果X是退化的基本可行解，它的基变量 零，或者说向量b被向量组AB1，AB2丄，ABm用非负系数线性表示时，有的系数等于零。X应该满足约束条件,oXBj中就有一部分等于如果能够对b作一个微小的变动，使b被AB,，AB2丄,ABm用非负系数线性表示时，系数全部是正的，那么X就变成非退化的 了。进一步，如果变动b使得所有的基阵都有上述性质 ，那么这个变动b以后的线性规划问题就是非退化的。第14页共2页重庆大学运筹学重点讲义的常数项b后面加上ai128i2L8inr1，得到下列线性规划问题：min zGXLCnXn必812X2La1nXnda122nLCn821X1822 X2La2nXnPa212a2