运筹学PPT完整全套教学课件

绪论第1章线性规划第2章线性规划的对偶理论第3章特殊线性规划第4章动态规划第5章图与网络分析第6章排队论第7章库存论第8章决策论第9章对策论运筹学

运筹学的简史

运筹学的特点

运筹学的模型

运筹学的应用与展望绪论

运筹学作为朴素的优化思想在中国发展历史中源远流长春秋时期的《孙子兵法》轮作制、间作制与绿肥制等先进的耕作技术田忌赛马则是对策论的典型范例运筹学的简史

现代运筹学的思想1914年，兰彻斯特开展了关于战争中兵力部署的理论，这就是军事运筹学中的战斗方程1915年，哈里斯对商业库存问题的研究是库存模型最早的工作1921年，博雷尔引进了博弈论中最优策略的概念，对某些博弈问题证明了最优策略的存在1928年，冯．诺依曼提出了二人零和博弈的一般理论1939年，康托洛维奇在解决工业生产组织和计划问题时，开创性的提出了线性规划模型，并给出了“解乘数法”的求解方法运筹学的简史运筹学的简史

运筹学真正作为科学名字出现在二次世界大战期间20世纪20年代末期英军每一个大的指挥部基本都成立了运筹研究小组，其成员包括数学家、物理学家、天文学家和军事专家多人，探讨如何抵御敌人的飞机和潜艇的袭击1921年，博雷尔引进了博弈论中最优策略的概念，对某些博弈问题证明了最优策略的存在1928年，冯．诺依曼提出了二人零和博弈的一般理论1939年，康托洛维奇在解决工业生产组织和计划问题时，开创性的提出了线性规划模型，并给出了“解乘数法”的求解方法

在我国，运筹学的研究与应用起步较晚在钱学森、许国志教授的推动下，中国第一个运筹学小组于1956年在中国科学院力学研究所成立。20世纪六七十年代，华罗庚先生的“优选法”和“统筹法”许国志和越民义先生在排队论的瞬时概率性态问题、非线性规划梯度算法收敛问题、组合优化中的排序问题运筹学的简史

莫斯和金博尔曾对运筹学下的定义是：“为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。”“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。”“运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会更坏。”运筹学的特点

运筹学研究的对象是政治、经济及科学技术等活动中能用数量关系来描述的有关运用、筹划与管理等方面的问题。科学性实践性系统性综合性运筹学的特点

运筹学模型是在对客观现实经过思维抽象后，用文字、图表、符号、关系式以及实体模样来描述客观对象，这些文字、图表、符号、关系式、实体模样就称为模型。一般模型有三种基本形式：形象模型，模拟模型，符号或数学模型（关系式）。

一般模型有三种基本形式：形象模型模拟模型符号或数学模型运筹学的模型

模型的一般数学形式可用下列表达式描述：目标的评价准则约束条件其中：——可控变量；

——已知参数；

——随机因素。运筹学的模型

运筹学在解决大量实际问题过程中逐步形成了一套系统的解决问题的方法和步骤，主要包括以下几个阶段：

提出和形成问题

建立模型

求解模型

解的检验

解的实施以上过程不是独立存在的，也绝非依次进行，应是一个呈螺旋状发展的过程。运筹学的模型

运筹学经过60多年的发展，其理论越来越艰深，应用愈来愈广泛，目前已经没有任何一个人可以是运筹学所有方向的专家。因而对未来运筹学的任何一个具有挑战性的课题的研究，尤其是对出现在新的学科交叉领域的重大问题的探索，就更需要一组具有运筹学的不同专长的人才组成的研究团队（类似于运筹学发展初期时的研究小组），其中还应该包含统计学、经济学、工商管理、计算机科学、行为科学等学科背景的人才，才能做出重要的科学发现和贡献。总之，运筹学还在不断地发展中，新的思想、观点和方法将会不断地出现。运筹学的应用与展望运筹学

绪论

第1章线性规划第2章线性规划的对偶理论第3章特殊线性规划第4章动态规划第5章图与网络分析第6章排队论第7章库存论第8章决策论第9章对策论运筹学1.1线性规划问题及数学模型1.2线性规划的图解法1.3单纯形法原理1.4单纯形法的计算步骤1.5单纯形法的进一步讨论1.6应用举例第1章线性规划1.1.1

问题的提出

在生产经营管理工作中，常常需要进行计划或规划。虽然不同行业计划的内容千差万别，但其共同点均可归结为解决两类主要的问题：一类是在资源(人力、物力、财力……)一定的情况下，如何利用这些有限的资源来完成最多的任务；另一类是在预期目标确定的情况下，如何利用最少的资源来完成这个确定的任务。1.1线性规划问题及数学模型

例1-1某建筑公司的预制厂利用沙、石、水泥三种原料A1、A2、A3，来生产两种产品B1和B2，已知该厂各种原料的现有数量、单位产品对各种原料的消耗量及单位利润如表1-1所示。在这些现有的资源的条件下，如何分配产品B1和B2的生产，才使公司取得最大利润。

1.1.1

问题的提出表1-1生产消耗及现有原料B1

B1原料现有(M3)A1A2A3132111908045单位利润(百元)54产产品原料品的消耗单位分析：设x1表示产品B1的生产数量，x2为产品B2的生产数量。公司可以获取的利润为(5x1+4x2

)百元，令z=5x1+4x2，因问题中要求获利最大，即maxz。又z是该公司能获取的利润的目标值，它是变量x1，x2的函数，其取值受到原材料A1、A2、A3的限制，由此例1-1的数学模型可表示为：1.1.1

问题的提出

例1-2现需100套钢架，每套用长为3.5m，2.6m和1.6m的圆钢各一根。原料长8.8m，问如何下料，使用的原材料最省。分析

现最简单做法是，在每一根原料上截取3.5m，2.6m和1.6m的圆钢各一根组成一套，100套钢架需用原料100根。若改为用套裁，就可以节约原材料。套裁方案见表1-2。1.1.1

问题的提出表1-2套裁方案方案ⅠⅡⅢⅣⅤ3.52112.6221.61325合计8.68.78.38.48料头0.20.10.50.40.8数长k(m)下j根为了得到100套钢架，需要混合使用各种下料方案。设按Ⅰ方案下料的原材料根数为x1，Ⅱ方案为x2，Ⅲ方案为x3，Ⅳ方案为x4，Ⅴ方案为x5。根据表1-2的方案，可列出以下数学模型：1.1.1

问题的提出在从以上两个例子可以看出，规划问题的数学模型包含三个要素组成：(1)变量，或称决策变量，是问题中要确定的未知量。每一个问题都用一组决策变量(x1，x2，…，xn)表示某一方案，这组决策变量的值就代表一个具体的方案。(2)约束条件，指决策变量取值时受到的各种资源条件的限制，通常可用一组含决策变量的等式或不等式来表示。(3)目标函数，它是决策变量的线性函数，按问题的不同，要求目标函数实现最大化或最小化。1.1.2线性规划问题的数学模型假定线性规划问题中含n个变量，分别用xj表示，在目标函数中xj的系数为cj，xj的取值受m项资源的限制，用bi表示第i种资源的拥有量，用aij表示变量xj取值为1个单位时所消耗或含有的第i种资源的数量，则上述线性规划问题的数学模型可表示为：1.1.2线性规划问题的数学模型上述模型(1-1)可简写为：1.1.2线性规划问题的数学模型向量表示形式为：矩阵表示形式为：由于目标函数和约束条件内容和形式上的不同，线性规划问题可以有多种表达式。为了便于讨论和制定统一的算法，规定线性规划问题的标准形式如下：1.1.3线性规划问题的标准形式对不符合标准形式(或称非标准形式)的线性规划问题，可分别通过下列方法化为标准形式。(1)目标函数为求最小值，这时只需将目标函数最小化变换求目标函数最大化。(2)约束条件的右端项bi<0时，只需将等式或不等式两端同乘(-1)，则约束条件右端项必大于零。(3)约束条件为不等式。这里有两种情况：1)约束条件为“≤”形式。对这样的约束，在“≤”不等式的左端加上一个非负的新变量即可以化为等式。新增的非负变量称为松弛变量。2)约束条件为“≥”形式。对这样的约束，在“≥”不等式的左端减去一个非负的新变量即可以化为等式。新增的非负变量称为剩余变量，亦可以称为松弛变量。1.1.3线性规划问题的标准形式(4)决策变量，这时可能有以下情况：1)决策变量xj≤0，则令非负变量x′j=−xj，显然x′j≥0。2)决策变量xj取值不受限制，可以用两个非负的新变量之差来代替。如变量xj取值不受限制，则令xj=x′j−x″j，新变量x′j和x″j为非负变量，xj的符号由x′j和x″j来确定。3)决策变量有上下界。对这种情况，可将上下界分别处理。引进新的变量使等于原变量减去下限值，如此则下限为零，满足标准形式的非负性要求。如已知决策变量xj的限制为aj≤xj≤bj，则令x′j=xj−aj，从而得0≤x′j≤bj−aj，现时的x′j满足了非负要求。用新变量x′j替换目标函数和约束条件中所有的原变量xj，再将上限约束列为新的约束条件并化为等式。1.1.3线性规划问题的标准形式

例1-3将下列线性规划问题化为标准形式。

1.1.3线性规划问题的标准形式

解

(1)因为x3符号不限，以x3=x′3−x″3代入目标函数和所有约束条件中，其中x′3，x″3均为非负变量。(2)对第一个约束加上松弛变量x4化为等式。(3)对后两个约束分别减去剩余变量x5和x6化为等式。(4)为了保持目标函数不变，使x4，x5和x6的目标系数均为零。得到的标准形式线性规划为：1.1.3线性规划问题的标准形式1.1.4

线性规划问题的解的概念(1)可行解，满足线性规划的约束条件(1-7)和(1-8)的解。(2)可行域，所有可行解组成的集合。(3)最优解，使线性规划目标函数(1-6)达到最大值的可行解。(4)基，若B是约束方程组系数矩阵A中m×m阶非奇异子阵(|B|≠0)，则称B是线性规划问题的一个基。(5)基向量，B中的每一个列向量Pj(j=1,2,…,m)。(6)基变量，与基向量Pj对应的决策变量，线性规划中除基变量以外的其他变量称为非基变量。假设系数矩阵A的秩m(m<n)，故方程组(1-7)有无穷多个解。不失一般性，不妨假设方程组的前m个变量的系数列向量的线性无关的，于是方程组(1-7)可改写为：

1.1.4

线性规划问题的解的概念(7)基解，若令(1-9)式的非基变量xm+1=xm+2=…=xn=0，由m个约束方程可解出个m基变量的惟一解XB，将这个解加上非基变量取0的值，得到(1-9)的一个解，称X为线性规划的基解。(8)基可行解，满足变量非负约束条件(1-8)的基解。(9)可行基,对应于基可行解的基。1.1.4

线性规划问题的解的概念

例1-5找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。

表1-3线性规划的基解基x1x2x3x4x5z是否基可行解P3P4P50051045是P2P3P40452017是P1P4P55005410是P2P3P40550-120否P1P3P5100-50415否P1P2P552.5001.517.5是P1P2P4540-3022否P1P2P32430019*是1-2线性规划的图解法图解法是采用直角坐标系及其基本原理设计出的一种求解方法，其步骤如下：第一步：在平面坐标系中，给出各约束条件的图形，并确定出可行域。第二步：画出目标函数直线束中穿过可行域的任一条直线，并将该直线沿目标函数取优(大或小)的方向平行移动，当直线离开可行域时，最后接触的可行域的顶点(极点)为最优点。第三步：联立通过最优点的方程得出最优解。第四步：将最优解代入目标函数得出最优值。1-2线性规划的图解法

例1-6

用图解求解线性规划

O图1-1x1x2ABC2x1+3x2=122x1+x2=86x1+7x2=7最优解X*=(3，2)T1-2线性规划的图解法

例1-7

用图解求解线性规划O图1-2x1x2x1=4x1+2x2=8ADBCx2=3线段BC上的点都是最优解1-2线性规划的图解法

例1-8

用图解求解线性规划O图1-3x1x2图1-3中的凸多边形ABCD为线性规划的可行域，它是无界的，因而可行解集也是无界集合。ADBCx1-x2=1-x1+2x2=01-2线性规划的图解法

例1-9

用图解求解线性规划O图1-4x1x2由图1-4可知，同时满足四个不等式的点不存在，所以该线性规划无可行解，即无可行域。x1+x2=-2-x1+x2=11-3单纯形法原理1.3.1

线性规划问题的几何意义

(1)凸集，设M是n维欧氏空间的一个点集。若M中任意两点X(1)，X(2)的连线上的一切点αX(1)+(1-α)X(2)(0≤α≤1)仍在点集M中，则称M为凸集。(2)顶点，设M是凸集，X∈M；若X不能用M中两个不同点X(1)，X(2)的线性组合表示为X=αX(1)+(1-α)X(2)(0<α<1)，则称为凸集M的一个顶点(或极点)。(3)凸组合，设X(1),X(2),…,X(k)是n维欧氏空间中k个点，若存在λ1,λ2,…,λk，且0≤λi≤1(i=1,2,…,k)，∑λ=1，使得X=λ1X(1)+λ2X(2)+…+λkX(k)，则称X为K个点X(1),X(2),…,

X(k)的凸组合。1.3.1线性规划问题的几何意义定理1-1线性规划问题的所有可行解的集合(即可行域)。引理1

线性规划问题的可行解X=(x1，x2，…，xn)T是基可行解的充要条件是的正分量所对应的系数列向量是线性独立的。定理1-2线性规划问题的基可行解X对应于可行域S顶点。引理2

若M是有界凸集，则任何一点X∈M可表示为的M顶点的凸组合。定理1-3若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。1.3.2确定初始基可行解为确定初始基可行解，首先确定初始可行基，方法如下：(1)若线性规划问题在约束条件式(1-13)的变量的系数矩阵中一般能直接观察到存在一个初始可行基。1.3.2确定初始基可行解(2)若线性规划问题的约束条件全部为“≤”形式的不等式，可以利用化为标准形式的方法，在每个约束条件的左端加上一个松弛变量。由于这个系数矩阵中含有一个单位矩阵(P1，…，Pm)，以这个单位矩阵为基，可以解出基变量值xi=bi(i=1，…，m)，因为有bi≥0，由此X=(b1，…，bm，0，…，0)T就是一个基可行解。1.3.3最优性检验与解的判别线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况。一般情况下，经过迭代后(1-14)式变成:将(1-15)式代入目标函数(1-12)式得:令:则:1.3.3最优性检验与解的判别最优解判别定理

若X=(b′1,…,b′m,0,…,0)T为一个基可行解，且对于一切j=m+1,…,n，有λj≤0

，则X为最优解。称λ为检验数.无穷多最优解判别定理

若X=(b′1,…,b′m,0,…,0)T为一个基可行解，且对于一切j=m+1,…,n，有λj≤0

，又存在某个非基变量的检验数λm+k=0，则线性规划问题有无穷多最优解.最优解判别定理

若X=(b′1,…,b′m,0,…,0)T为一个基可行解，有一个非基变量的检验数λm+k>0

，并且对i=1,…,m，有a′i,m+k≤0

，那么该线性规划问题有无界解.(1)换入变量的确定由式(1-18)可以看到，当某些λj>0时，xj增加则目标函数值还可以增大，这时需要将某个非基变量xj换到基变量中去(称为换入变量)。即则对应的xk为换入变量。(2)换出变量的确定若确定非基变量Pm+t为换入变量，必然可以找到一组不全为零的数，使得1.3.4基变换给式(1-20)两边同乘一个正数θ，将它加到(1-19)式，得到：当θ取适当值时，就能得到满足约束条件的一个可行解(非零分量的数目不大于m个)，就应当使(xi0-θβi,m+i)中的某一个为零，并保证其余的分量为非负,同时因为θ必须是正数,即则对应的xl为换出变量。按最小比值确定θ值，称为最小比值规则。由X(0)转换到X(1)的各分量的转换公式为：1.3.4基变换1.4单纯形法的计算步骤初始基初始基可行解是否最优确定入基变量确定出基变量重新确定新基可行解基变换否是停止计算确保新的基本解仍然可行使目标函数值可能的增大额最大1.4单纯形法的计算步骤第一步：求初始基可行解，列出初始单纯形表。第二步：最优性检验。如果表中所有检验数λj≤0，则表中的基可行解就是问题的最优解，计算到此结束，否则转入下一步。第三步：进行基变换，列出新的单纯形表。(1)确定换入变量。只要有检验数λj>0，对应的变量就可以作为换入变量，即则对应的xk为换入变量。1.4单纯形法的计算步骤(2)确定换出变量。根据θ规则计算，即对应的xl为换出变量。元素alk决定了从一个基可行解到另一个基可行解的转移方向，称为主元素。(3)以alk为主元素进行迭代，把xk所对应的列向量第四步：重复第二、三步一直到计算终止。1.4单纯形法的计算步骤为了计算上的方便和规格化，对单纯形法的计算设计了一种专门表格，称为单纯形表(见表1-4)。迭代计算中每找出一个新的基可行解时，就构造一个新单纯形表。表1-4

单纯形表cj→c1…cm…cj…cnθiCBXBbx1…xm…xj…xnc1x1b11…0…a1j…a1nθ1c2x2b20…0…a2j…a2nθ2cmxmbm0…1…amj…amnθmcj-zj0…0……1.4单纯形法的计算步骤

例1-10用单纯形法求解例1-1的线性规划问题。

解

给例1-1各约束条件添加松弛变量，将问题化为标准形式。取松弛变量x3，x4，x5为基变量，它对应的单位矩阵为基，这样得到初始基可行解X=(0,0,90,80,45)T，列出初始单纯形表(见表1-5)。表1-5初始单纯形表cj→54000θCBXBbx1x2x3x4x50x39013100900x480[2]1010400x5451100145cj-zj540001.4单纯形法的计算步骤表中有大于零的检验数，故表中的基可行解不是最优解，因为λ1>λ2，故确定x1为换入变量。为确定换出变量，将b列数字除以x1列同行数字得表1-6初始单纯形表cj→54000θCBXBbx1x2x3x4x50x35005/21-1/20205x14011/201/20800x550[1/2]0-1/2110cj-zj03/20-5/20因此x4为换出变量。2为主元素，将其加上“[]”标记。将换入变量x1替换基变量中的x4，画出新的单纯形表(见表1-6)1.4单纯形法的计算步骤表中仍有大于零的检验数λ2，故确定x2为换入变量。为确定换出变量，将b列数字除以x2列同行数字得表1-7初始单纯形表cj→54000θCBXBbx1x2x3x4x50x3250012-55x1351001-14x210010-12cj-zj000-1-3因此x5为换出变量，得到新的单纯形表(见表1-7)表1-7中所有检验数λj≤0，说明已找到问题的最优解X=(35,10,25,0,0)T，目标函数值z=215。1.4单纯形法的计算步骤

例1-11假如例1-1中生产单位产品B1利润由原来5百元降低至4百元，其他条件不变，应如何安排生产获利最多？

解

所求问题的标准形式为：取松弛变量x3，x4，x5为基变量，确定初始基可行解并建立初始单纯形表，其整个求解过程如表1-8所示。表中所有检验数λj≤0，说明已找到问题的最优解X=(35,10,25,0,0)T，目标函数值z=180。1.4单纯形法的计算步骤表1-8cj→44000θCBXBbx1x2x3x4x50x39013100900x480[2]1010400x5451100145cj-zj440000x35005/21-1/20204x14011/201/20800x550[1/2]0-1/2110cj-zj020-200x325001[2]-54x1351001-14x210010-12cj-zj0000-41.4单纯形法的计算步骤在最终单纯形表中，除基变量的检验数为零外，非基变量x4的检验数也为零，这表明如果让x4增加不会使目标函数值有所变化，也就是说，如果让x4作为换入变量继续迭代，就会得到另一个基可行解，见表1-9。表中所有检验数λj≤0，说明已找到问题的最优解X=(45/2,45/2,0,25/2,0)T，目标函数值z=180。表1-9cj→54000θCBXBbx1x2x3x4x50x425/2001/21-5/24x145/210-1/203/24x245/2011/20-1/2cj-zj0000-41.4单纯形法的计算步骤

例1-12利用单纯形表法求解下列线性规划问题

解

取松弛变量x3，x4，x5为基变量，确定初始基可行解并建立初始单纯形表，其整个求解过程如表1-10所示：在表1-10中，因为λ3>0，选x3为换入变量，但换入变量x3所在列的所有系数均小于等于零，故此问题具有无界解。1.4单纯形法的计算步骤表1-10cj-12-1000cBxBbx1x2x3x4x5x6θ0x443-111000x521-110100x64-2[1]-10014cj-zj-12-10000x48[1]0010180x56-1000112x24-21-1001cj-zj30100-2-1x181001010x5140001122x22001-1203cj-zj001-30-51.5.1人工变量法当线性规划的约束条件都是等式，而系数矩阵中不含有单位矩阵时，为了迅速地找到一个初始基可行解，往往通过人为添加非负变量(称这种人为引入的变量为人工变量)来构造一个单位基矩阵。设线性规划问题的约束条件是：分别给每一个约束方程加入人工变量xn+1，…，xn+m，得到：以xn+1，…，xn+m为基变量，令非基变量x1,…,xn为零，就可以得到一个初始基可行解X(0)=(0,…,0,b1,…,bm)T1.5.1人工变量法当由于人工变量的加入，破坏了原有模型的约束条件，因此上面得到X(0)的不再是原问题的基可行解。但如果在求解迭代过程中，人工变量能从基变量中退出，变为非基变量，即xn+1=…=xn+m=0，则新问题的基可行解就是原来线性规划问题的基可行解。为了实现这一目的，就要设法在迭代过程中让人工变量从基变量中退出去(或其值为零)。基变量中不再含有非零的人工变量，这表明原问题有解。若在最终表中当所有的，而在其中还有某个非零人工变量，表示原问题无可行解。1.大M法在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响，为此取人工变量在目标函数中的系数为－M(在最小化问题中取M)，这里是一个很大的正数。1.5.1人工变量法

例1-13试用大M法求解下列线性规划问题

解

在上述问题的约束条件中加入松弛变量x4，x5，人工变量x6，得到：利用单纯形法求解，求解过程见表1-11。1.5.1人工变量法表1-11cj13400-McBxBbx1x2x3x4x5x6θ0x413[3]2010013/30x517013010--Mx61321100113/2cj−zj1+2M3+M4+M0001x113/312/301/300-0x51701301017/3-Mx613/30-1/3[1]-2/30113/3λj=cj−zj07/3-M/34+M-1/3-2M/3001x113/312/301/30013/20x540[2]021-324x313/30-1/31-2/301-λj=cj−zj011/307/30-4-M1x13100-1/3-1/313x2201011/2-3/24x35001-1/31/61/2λj=cj−zj000-4/3-11/63/2-M表中所有检验数λj≤0，说明已找到问题的最优解X=(3,2,5)T，目标函数值z=29。2.两阶段法在两阶段法的第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数为零，人工变量的系数取某个正的常数(一般取1)，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。在第一阶段中，当人工变量取值为0时，目标函数值也为0，这时的最优解是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工变量，表明原线性规划问题无可行解。当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数继续寻找问题的最优解。1.5.1人工变量法1.5.1人工变量法

例1-14用两阶段法求解下列线性规划问题

解

在上述问题的约束条件中加入松弛变量x4，x5，人工变量x6，给出第一阶段的数学模型为利用单纯形法求解，求解过程见表1-12。1.5.1人工变量法表1-12cj000001cBxBbx1x2x3x4x5x6θ0x413[3]2010013/30x517013010-1x61321100113/2λj=cj−zj-2-1-10000x113/312/301/300-0x51701301017/31x613/30-1/3[1]-2/30113/3λj=cj−zj01/3-12/3000x113/312/301/30013/20x540[2]021-320x313/30-1/31-2/301-λj=cj−zj000001第一阶段求得的结果是z=0，得到的最优解是X=(13/3,0,13/3,0,4,0)T1.5.1人工变量法因为人工变量x6=0，所以(13/3,0,13/3,0,4)T是线性规划问题的基可行解。所以可进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数得系数，进行第二阶段计算，见表1-13。表1-13cj13400cBxBbx1x2x3x4x5θ1x113/312/301/3013/20x540[2]02124x313/30-1/31-2/30-λj=cj−zj011/307/301x13100-1/3-1/33x2201011/24x35001-1/31/6λj=cj−zj000-4/3-11/6表中所有检验数λj≤0，说明已找到问题的最优解X=(3,2,5)T，目标函数值z=29。1.5.2退化单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或者几个基变量等于零，这就出现退化解。这时换出变量xi=0，迭代后目标函数值不变。这时不同基表示为同一顶点。尽管计算过程的循环现象很少出现，但还是有可能的。为了解决这问题，先后有人提出了“摄动法”，“字典序法”。1974年勃兰特提出一种简便的规则，简称勃兰特规则：(1)选取cj-zj>0中下标最小的非基变量xk为换入变量。(2)当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。按勃兰特规划计算时，一定能避免出现循环。1.5.3单纯形法计算的矩阵表示用矩阵形式描述线性规划的标准形式为：初始单纯形表可见表1-14：表1-14初始解非基变量基变量bBNIcj-zjλN0,…,0基变换后的新单纯形表见表1-15：表1-15基可行解基变量非基变量b'IN'B-1cj-zj0,…,0λ'N-y1,…,-ym

例1-16某饲料厂用原料A、B、C加工生产三种不同的饲料甲、乙、丙。已知各种饲料中原料A、B、C的含量，原料成本，各种原料的限制用量，三种饲料的单位加工费及其售价如表1-19所示。该厂每月生产三种饲料各多少，可使饲料厂获利最大。。

1.6应用举例表1-19甲乙丙原料成本（元/kg）每天限制用量（kg）A≥50%≥25%65100B≤25%≤50%25100C3560售价(元/kg)5035251.6应用举例

解

(1)用i

=1,2,3分别代表原料A、B、C，用j=1,2,3分别代表甲、乙、丙三种不同的饲料。设xij为生产第j种饲料使用的第i种原料。(2)目标函数为(3)约束条件为1.6应用举例所以问题的数学模型为上述模型求解结果是：每天生产产品甲200Kg，分别需要用原料A为100Kg，原料B为50KG，原料C为50Kg。例1-16某部门拥有20万资金，拟今后五年内对下列项目投资。项目A：从第一年到第四年每年初需投资，并于次年末回收本利150%；项目B：第三年初投资，第五年末能回收本利135%，但最大投资额不超过8万元；项目C：第二年初投资，第五年末能回收本利140%，但最大投资额不超过6万元；项目D：五年内每年年初可购买公债或定期储蓄，于当年末归还，并回收本利9%。现要求确定这些项目每年的投资额，使到第五年末拥有的资金本利额最大。

1.6应用举例1.6应用举例

解

(1)确定变量,设xiA，xiB，xiC，xiD(i=1，2，3，4，5)分别表示第i年初投资项目A、B、C、D的资金额。

(2)资金流转分析:第一年年初需要将20万元资金投资给项目A、D，所以有：x1A+x1D=20，则年底回收项目D的本利为：x1D(1+9%)=1.09x1D，这些资金应在第二年年初投资给A，C，D三个项目，故有：x2A+x2C+x2D=1.09x1D第二年年底回收项目A第一年投资和项目D当年投资本利的总和为：1.15x1A+1.09x2D，这些资金在第三年初投资给项目A，B，D，有：x3A+x3B+x3D=1.15x1A+1.09x2D第三年年底回收项目A第二年投资和项目D当年投资的本利总和为：1.15x2A+1.09x3D，类似地，可得第四年投资为：x4A+x4D=1.15x2A+1.09x3D第五年投资为：x5D=1.15x3A+1.09x4D，第五年年末共回收资金：

1.15x4A+1.35x3B+1.4x2C+1.09x5D1.6应用举例

(3)数学模型:

(4)用单纯形法计算得到如下结果:第一年：x1A=0，x1D=20第二年：x2A=0，x2C=0，x2D=21.8第三年：x3A=0，x3B=8，x3D=15.762第四年：x4A=0，x4D=17.18058第五年：x5D=18.72683到第五年该部门拥有资金总额为31.21225万元本章小结与展望自从一般线性规划问题求解的方法——单纯形法提出之后，线性规划在理论上趋向成熟，在应用中日益广泛与深入。线性规划的应用与计算机软件的开发紧密联系，规模稍大的线性规划模型是无法用手工计算来求解的。对线性规划模型在实践中的模型一般含有几百到几千个变量和约束条件，有时变量和约束条件个数可达几十万个到百万个之多。对这类大规模的模型要用手工建模及输入计算机不现实的，因此近几年已开发出如AMPL（AMathematicalProgrammingLanguage）等建模语言，有效解决了大规模线性规划建模和优化计算问题。

绪论第1章线性规划

第2章线性规划的对偶理论第3章特殊线性规划第4章动态规划第5章图与网络分析第6章排队论第7章库存论第8章决策论第9章对策论运筹学

2.1对偶线性规划模型

2.2对偶问题的基本性质

2.3对偶单纯形法

2.4灵敏度分析

2.5参数线性规划

2.6案例分析第2章线性规划的对偶理论

例2-1某工厂计划用三种资源生产生产甲、乙两种产品，该厂可使用d1、d2、和d3三种生产资源的数量限制、每种产品所需各种生产资源及出厂后可获利润如表2-1所示，建立该厂总利润最大的数学模型。

2.1对偶线性规划模型表

2-1生产消耗及现有原料资源产品d1d2d3每件产品利润甲1215乙3114资源限量908045分析：现在从另一种角度讨论这个问题。假如工厂决定放弃生产产品甲、乙，而将其所有资源出租或出售，工厂就需要考虑如何给每种资源定价的问题。假设用y1，y2，y3分别表示三种生产资源d1，d2，和d3的单位附加额（售价=成本+附加额）。工厂做定价决策时会做如下考虑：用1个单位资源d1，2个单位资源d2和1个单位资源d3可以生产一件产品甲，可获利5元，那么生产每件产品甲的资源出让的所有收入应不低于生产一件产品甲的利润，也就是有2.1.1

问题的提出同理生产每件产品乙的资源出让的所有收入不应低于生产一件产品乙的利润，有2.1.1

问题的提出从工厂的角度看当然希望资源出让的利润越多越好，但从购买者来看支付越少越好，所以合理的价格是购买者用最少的资金购买全部资源，而工厂所获得的利润不应低于自己将资源用于生产时所获得的利润。问题可用数学模型表示:将线性规划问题（2-1）称为原问题，则线性规划问题（2-1）称为上述线性规划问题的对偶问题。这两个问题的数学模型之间有如下对应关系：（1）两个矩阵的系数矩阵互为转置；（2）原问题P的常数项是对偶问题D目标函数系数，反之，原问题P的目标函数系数是对偶问题D的常数项；（3）原问题P有n个决策变量，对偶问题D有n个约束方程；原问题P有m个约束方程，对偶问题P就有m个决策变量；（4）原问题P的约束是“≤”型，对偶问题D的约束是“≥”型；（5）原问题P的目标函数是求极大，对偶问题D的目标是求极小。2.1.1

问题的提出线性规划问题（2-1）的一般形式为:2.1.2对称型对偶关系的一般形式式（2-3）作为原问题，根据上述原问题和对偶问题的五条对应关系可得到其对偶问题为:用矩阵形式表示原问题（2-3）和对偶问题（2-4）为2.1.2对称型对偶关系的一般形式原问题和对偶问题之间的对应关系可用表2-2表示:表2-2对称型对偶关系表xjyix1…xn原始约束Minwy1a11…a1n≤b1┇┇…┇┇ymam1…amn≤bm对偶约束≥…≥Maxzc1…cn线性规划的原问题与对偶问题的关系，其变换形式归纳为表2-3中所示的对应关系2.1.3非对称型对偶关系表2-3非对称型对偶关系表maxZminGxⅠ≥0xⅡ自由xⅢ≤0cⅠ

cⅡ

cⅢ

≥=≤yA≥0bA≥aAⅠaAⅡaAⅢyB自由bB=aBⅠaBⅡaBⅢyC≤0bC≤aCⅠaCⅡaCⅢ2.1.3非对称型对偶关系

例2-2写出下列线性规划的对偶规划。2.1.3非对称型对偶关系

解

①画出对偶关系表如表2-4所示。表2-4对偶关系表maxZminGx1≥0x2自由x3≥0x4自由2111≥=≥=y1≥05≥1111

y2自由-4=2-130y3≤01≤10-31②据表2-4得对偶问题为2.2.1对偶问题的基本性质性质2-1对偶问题的对偶是原问题性(对称性)。性质2-2若X*是原问题的可行解,Y*是对偶问题的可行解，则存在CX*≤Y*b(弱对偶性)。性质2-3若若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解

(无界性)。性质2-4若X*是原问题的可行解,Y*是对偶问题的可行解，当CX*

=

Y*b，X*,Y*是最优解(最优性)。性质2-5若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等(对偶性)。性质2-6若X*和

Y*分别是原问题和对偶问题的可行解，XS和YS分别是原问题和对偶问题松弛变量的可行解，则X*和

Y*是最优解当且仅当YSX*=0

和Y*XS=0(互补松弛性)。2.2.1对偶问题的基本性质性质2-7设原问题是其对偶问题是则原问题单纯形表的检验数行对应其对偶问题的一个基本解，其对应关系见表2-5。表2-5XBXNXS0CN–CBB-1N–CBB-1YS1-YS2-Y2.2.1对偶问题的基本性质

例2-3已知线性规划的最优解为X=(6,2,0)T，求对偶问题的最优解。2.2.1对偶问题的基本性质

解

上述线性规划的对偶问题是因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即因解此方程组得y1=1，y2=1。对偶问题的最优解Y=(1,1)T，最优值w=26。2.2.1对偶问题的基本性质

例2-4已知下列线性规划对偶问题的最优解为y1*=0.8，y2*=0.6，z=5。用对偶性质求解原问题。

解

上述线性规划的对偶问题是2.2.1对偶问题的基本性质将y1*=0.8，y2*=0.6代入约束条件，可知ys2=2.8，ys3=1.6，ys4=1.6，由互补松弛条件可得x2*=x3*=x4*=0，又因为y1*>0，y2*>0，原问题的两个约束条件应取等式，即为解此方程组得x1*=1，x5*=1。对偶问题的最优解X=(1,0,0,0,1)T，最优值w*=5。2.2.1对偶问题的基本性质

例2-5已知线性规划(1)用单纯形法求最优解；(2)求出每步迭代对应对偶问题的基本解；(3)从最优表中写出对偶问题的最优解；(4)用公式求出对偶问题的最优解。2.2.1对偶问题的基本性质

解

(1)加入松弛变量后，单纯形迭代如表2-6所示。表2-6cj→44000θCBXBbx1x2x3x4x50x3122210060x41640010-0x5150[5]0015230000x36[2]010-2/534x4164001040x2301001/5-2000-3/50x13101/20-1/54x4400-214/54x2301001/500-10-1/5最优解X=(3,3)T，最优值z*=15。2.2.1对偶问题的基本性质(2)设对偶变量y1，y2，y3，松弛变量为y4，y5，由性质2-7及表2-5的关系得到对偶问题的基本解:(y1，y2，y3，y4，y5)=(-λ1，-λ2，-λ3，-λ4，-λ5)第一次迭代中λ=(2,3,0,0,0)，则Y(1)

=(0,0,0,-2,-3)第二次迭代中λ=(2,0,0,0,-0.6)，则Y(2)

=(0,0,0.6,-2,0)第三次迭代中λ=(0,0,-1,0,-0.2)，则Y(3)

=(1,0,0.2,0,0)(3)因为表2-6为最优解，故Y(3)

=(1,0,0.2,0,0)为对偶问题的最优解。2.2.1对偶问题的基本性质(4)表2-6中最终单纯形表中的最优基B-1为表2-6最终单纯形表中x3，x4，x5三列的系数,即因而对偶问题的最优解为由对偶问题的性质可知，在单纯形法的每步迭代中有目标函数：2.2.2影子价格式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。代表对一个单位第i种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而做出的估价，为区别起见，称为影子价格。(1)资源的市场价格是已知数，相对比较稳定，而影子价格则依赖于资源的利用情况，是未知数。(2)影子价格是一种边际价格，yi值等于在给定的生产条件下，bi每增加一个单位时目标函数z的增量。(3)资源的影子价格实际上是一种机会成本。(4)如果某种资源的影子价格不为零时，表明该种资源在生产中已耗费完毕；当生产过程中如果某种资源没有得到充分利用时，该种资源的影子价格为零。(5)影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献。2.2.2影子价格原问题与对偶问题的解之间的关系时指出：在单纯形表进行迭代时，b列得到是原问题的一个基本可行解，在检验数行得到对偶问题的一个基本解。单纯形法计算的基本思想是保持原问题为可行解的基础上，通过迭代，增大目标函数，当对偶问题的解也为基本可行解时，就达到了目标函数的最优值。对偶单纯形法是根据对偶问题的对称性，其基本思想是保持对偶问题为基本可行解，即通过迭代减少目标函数，当原问题达到基本可行解时，得到了目标函数的最优值。2.3对偶单纯形法对偶单纯形法的条件是：初始表中对偶问题可行，也就是极大化问题要求所有变量的检验数λj≤0，极小化问题时检验数λj≥0。对偶单纯形法适合于下列线性规划问题求解：2.3对偶单纯形法对偶单纯形法的计算步骤：(1)建立线性规划初始单纯形表。检查常数项b列数字，若所有bi≥0，检验数λj≤0，则已得到最优解。若b列数字中至少还有一个负分量，检验数保持非正，那么进行以下计算。(2)确定换出变量。选常数列中最小负数所对应行中的变量出基，即min{bi│bi≤0}=bl对应的基变量xl为换出变量。(3)确定换入变量。在单纯形表中检查xl所在行的各系数。若所有的alj≥0，则无可行解。若存在alj<0，计算2.3对偶单纯形法选θk最小比值的列对应的变量xk进基。(4)以akj为主元素，按原单纯形法在表中进行迭代计算，得到新的计算表。转到第（1）步重复运算。2.3对偶单纯形法

例2-6利用对偶单纯形法求解线性规划

解

先将约束不等式化为等式，并给等式两边乘以(-1)，再将极小化问题转换成极大化问题，以便得到对偶问题的初始可行基2.3对偶单纯形法建立此问题的初始单纯形表，见表2-7。表2-7cj→-1-3000bcBxBx1x2x3x4x50x3-2-1100-30x4[-3]-2010-4→0x5-1-2001-1λj-1↑-3000由表2-7看到，检验数行对应的对偶问题的解是可行解。因为b列数字为负，故需要进行迭代运算。确定x4为换出变量，x1为换入变量。按照单纯形法计算步骤进行迭代，得到表2-8。2.3对偶单纯形法表2-8cj→-1-3000bcBxBx1x2x3x4x50x301/31[-2/3]0-1/3→-1x112/30-1/304/30x50-4/30-1/311/3λj0-7/30-1/3↑0由表2-8得，对偶问题仍是可行解，而b列数字中仍有负分量，故重复上述迭代过程，得到表2-9。表2-9cj→-1-3000bcBxBx1x2x3x4x50x40-1/2-3/2101/2-1x111/2-1/2003/20x50-3/2-1/2011/2λj0-7/30-1/3↑0当线性规划问题的参数其中的一个或者几个发生变化时，线性规划问题的最优解会有什么变化，或者这些参数在什么范围变化时，线性规划问题的最优解不变，这就是灵敏度分析要研究解决的问题。单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化参数的变化直接在计算得到最优解的单纯形表中反映出来，这样就不需要从头计算，而直接对计算得到最优解的单纯形表进行检查和分析，看是否仍然满足最优解的条件，不满足的话，就可以从这个单纯形表进行迭代计算，求得最优解。2.4灵敏度分析灵敏度分析的步骤如下：(1)将参数的改变计算反映到最终单纯形表中。按以下公式计算出由参数aij,

bi,

cj变化而引起的最终单纯形表上相关数字的变化：2.4灵敏度分析(2)检查原问题是否仍为可行解；(3)检查对偶问是否仍为可行解；(4)表2-10所列情况进行处理。表2-10原问题对偶问题结论或继续计算的步骤可行解可行解仍然是问题的最优解可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引入人工变量，编制新的单纯形表重新计算设线性规划2.4.1价值系数cj的灵敏度分析设最优基的逆矩阵为检验数为要使得最优解不变，即当cj变化为cj'=cj+△cj后，检验数仍然是小于等于零。这时分cj是非基变量和基变量的系数两种情况讨论。(1)

cj是非基变量xj的系数2.4.1价值系数cj的灵敏度分析所以

△cj可变化的范围是(2)

ci是基变量xi的系数所以

△ci可变化的范围是2.4.1价值系数cj的灵敏度分析

例2-7某厂生产甲、乙两种产品，这两种产品都需要在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需要的时间，这些产品销售后所能获得的利润，以及这三种加工设备因各种条件限制所能使用的有效加工总时数如表2-11所示，试对产品利润进行灵敏度分析。表

2-11设备产品ABC每件产品利润甲35970乙95330有效工时540450720

解

设x1，x2分别为甲、乙两种产品的生产数量，得线性规划数模：2.4.1价值系数cj的灵敏度分析利用单纯形法，求得最优解对应的单纯形表如表2-12所示。表2-12cj7030000bcBxBx1x2x3x4x50x3001-12/5118030x20103/10-1/61570x1100-1/101/675λj000-2-20/35700设甲产品的利润c1=70发生变化△c1

，将其代入上表2-12中计算得表2-13。表2-13cj70+△c1

30000bcBxBx1x2x3x4x50x3001-12/5118030x20103/10-1/61570+△c1x1100-1/101/675λj000-2+△c1/10-20/3-△c1/65700+75△c12.4.1价值系数cj的灵敏度分析利用由表2-13可看出，当c1改变时，如果要保持表2-12中的最优解，则据最优判断条件知，检验数应满足：由此可知c1的变化范围为：30≤c1≤90。同理可得，当c2发生改变量时，对应的单纯形表如表2-14所示：表2-13cj7030+△c1

000bcBxBx1x2x3x4x50x3001-12/5118030+△c2x20103/10-1/61570x1100-1/101/675λj000-2-△c1/10-20/3+△c1/65700+15△c1由此可知c1的变化范围为：70/3≤c2≤70。2.4.1价值系数cj的灵敏度分析

例2-8已知线性规划，(1)求最优解；(2)若最优解不变，求c1,

c2,c3变化范围。

解

(1)加入松弛变量后用单纯形法求解，最优表如表2-15所示。表2-15cj→113000cBxBx1x2x3x4x5x6b0x40-201-1-15-1x111001-150x301100115λj0-300-1-2最优解为X

=(5,0,15)T，最优值Z=50。2.4.1价值系数cj的灵敏度分析

(2)因为x2为非基变量，x1,

x3为基变量，所以有:c2的变化范围是

对于c1：表2-15中x1对应行的系数，有:c1的变化范围是

对于c3：表2-15中x3对应行的系数，有:c3的变化范围是2.4.2资源限量bi的灵敏度分析当资源系数br发生变化，即当cj变化为br'=br+△br后，这样最终表中原问题的解相应的变为只要XB'≥0，因为最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB'为新的最优解。新的最优解的值可允许变化范围可以用下述方法确定。所以

△br可变化的范围是2.4.2价值系数bi的灵敏度分析

例2-9求例2-8的b1,

b2,b3在什么范围内变化时，原最优基不变。

解

加入松弛变量后用单纯形法求解，最优表如表2-15所示。表2-15cj→113000cBxBx1x2x3x4x5x6b0x40-201-1-15-1x111001-150x301100115λj0-300-1-2

由表2-15可知：2.4.2价值系数bi的灵敏度分析

对于b1：比值中的分母取B-1的第一列，有:b1的变化范围是

对于b2：比值中的分母取B-1的第二列，有:b2的变化范围是

对于b3：比值中的分母取B-1的第三列，有:b3的变化范围是2.4.3增加决策变量的分析增加变量的分析步骤如下：(1)设新增变量xk的目标系数为ck，相应的约束系数为Pk，计算(2)计算(3)计算λk，若λk≤0，只需将Pk'

和λk的值直接反映到最终单纯形表中，原最优解不变；若λk>0，则按单纯形法继续迭代。2.4.3增加决策变量的分析

例2-11对例2-7的问题进行讨论。现假设还有丙、丁两种产品可以用A，B，C三种设备加工，它们所用的定额及利润如表2-17所示。问丙或丁产品是否值得投资，若投资，新的最优解是多少？表

2-17设备产品ABC每件产品利润丙1