运筹学教案设计1

运筹辔款案

重庆交通大学管理学院

运筹学C课程教学大纲

一、课程名称：运筹学OperationsResearch

课程负责人李建章

二、学分：5,其中，理论教学学分4.5,实验（实践）教学学分0.5

总学时数：72+16,其中理论教学学时72,实验（实践）教学学时16

三、适用专业：工程管理，工程造价，工商管理、物流管理

四、课程教材：《运筹学》教材编写组编：《运筹学》（第三版），清华大学出版社，2005年

五、参考书目：胡运权主编：《运筹学基础及应用》，哈尔滨工业大学出版社，1998年

徐永仁主编：《运筹学试题精选与答题技巧》，哈尔滨工业大学出版社，2000年

弗S希利尔等著：《数据、模型与决策》，中国财政经济出版社，2（X）1年

周华任等编著：《运筹学》辅导及习题精解，陕西师范大学出版社2005年

弗雷德里克6.希利尔（FrederickS.Hillier）,杰拉尔德,J.利伯曼（Gerald

J.Lieberman）,胡运权、等运筹学导论（第9版）清华大学出版社（2010-05出版）

韩伯棠：管理运筹学（第3版）（附光盘）韩伯棠高等教育出版社（2010-01出版）

六、开课单位：管理学院

七、课程的性质、目的和任务：

运筹学课程是管理类专业的一门非常重要的专业基础课，是采用科学、特别是数学的方法

研究人类对各种资源的运用及筹划活动的基本规律，以便发挥有限资源的最大效益，从而达到

总体、全局优化的目标。本课程的主要目的和任务是：

1、培养具备将现实的生产和管理问题，通过科学的、数量化的方法和技术进行思考、分

析和解决的思想。

2、使学生了解运筹学的工作步骤及其特点，掌握建立、分析和解决生产、生活及科学研

究和管理工作中各种问题的运筹学模型的基本概念、基本理论、基本方法和应用。

3、培养学生能运用运筹学的计算机软件解决大型数学模型的求解实际问题的能力。

八、课程的基本要求：

本课程实践性教学环节学时数为16,主要要求学生能使用Lingo软件解决求解大型的运筹

学模型。

九、课程内容：

1、绪论

了解运筹学的简史，运筹学的性质和特点，运筹学的工作步骤，运筹学的模型和运筹学的

应用。

2、线性规划与单纯形法

理解线性规划的数学模型的•般形式和标准形式，掌握线性规划问题的建模方法。

掌握线性规划的图解法及最优解的状况。

掌握线性规划问题的解的概念（可行解，最优解，基，即变量，非基变量，基解，基可行

解和可行基以及凸集及顶点）和线性规划问题的性质。

掌握单纯形法的原理和步骤。

掌握表格形式的单纯形法。

掌握用人工变量的方法求初始基可行解。

掌握线性规划问题的计算机求解方法。

&阅读材料

张建中许绍吉，《线性规划》1999年

胡运权主编：《运筹学基础及应用》，哈尔滨工业大学出版社，1998年

徐永仁主编：《运筹学试题精选与答题技巧》，哈尔滨工业大学出版社，2000年

3、对偶理论与灵敏度分析

2

理解单纯形法的矩阵描述，了解对偶问题的意义。

掌握原问题与对偶问题的对偶关系。

掌握对偶问题的基本性质。

掌握对偶单纯形法。

理解对偶问题的经济解释。

掌握线性规划问题的灵敏度分析。

掌握线性规划问题的灵敏度分析的计算机方法。

&阅读材料

张建中许绍吉，《线性规划》1999年

胡运权主编：《运筹学基础及应用》，哈尔滨工业大学出版社，1998年

徐永仁主编：《运筹学试题精选与答题技巧》，哈尔滨工业大学出版社，2000年

4、.S.希利尔等著：《数据、模型与决策》，中国财政经济出版社，2001年

4、运输问题

理解运输问题的数学模型及其特点。

掌握运输问题的表上作业法。

理解将不平衡的运输问题化为产销平衡的运输问题的方法。

掌握运输问题的应用和计算机求解。

&阅读材料

张建中许绍吉，《线性规划》1999年

胡运权主编：《运筹学基础及应用》，哈尔滨工业大学出版社，1998年

徐永仁主编：《运筹学试题精选与答题技巧》，哈尔滨工业大学出版社，2000年

弗.S.希利尔等著：《数据、模型与决策》，中国财政经济出版社，2001年

5、目标规划

掌握目标规划的数学模型的建立。

掌握目标规划的求解方法。

了解目标规划的求解的计算机方法。

&阅读材料

卢开澄编著：《单目标、多目标与整数规划》，清华大学出版社，1999年

胡运权主编：《运筹学基础及应用》，哈尔滨工业大学出版社，1998年

徐永仁主编：《运筹学试题精选与答题技巧》，哈尔滨工业大学出版社，2000年

6、整数规划

理解整数规划和0-1规划问题的数学模型。

了解整数规划的分枝定界法和割平而法

掌握指派问题的算法。

掌握整数规划和0-1规划问题的计算机算法。

&阅读材料

卢开澄，《单目标、多目标与整数规划》第八章多目标规划1999年

胡运权主编：《运筹学基础及应用》，哈尔滨工业大学出版社，1998年

徐永仁主编：《运筹学试题精选与答题技巧》，哈尔滨工业大学出版社，2000年

7、图与网络分析

理解有关图的基本概念。

掌握树的性质和特点以及求图的支撑树和最小支撑树的破圈法和避圈法。

掌握最短路的Dijkstra算法及在管理问题中的应用。

掌握网络最大流的有关概念和性质及求网络最大流的标号法。

了解图的一笔画问题。

r解最短路问题和最大流问题的计算机算法。

&阅读材料

3

卢开澄，《单目标、多目标与整数规划》第九章、第十章1999年

8、排队论

熟悉排队论的基本概念。

理解到达间隔的分布和服务时间的分布。

掌握单服务台负指数分布排队系统的分析(包括M/M/1/8/8,M/M/1/N/oo,M/M/l/8/m)。

了解多服务台负指数分布排队系统的分析。

了解排队系统的最优化问题。

&阅读材料

卢开澄，《单目标、多目标与整数规划》第九章、第十章1999年

胡运权主编：《运筹学基础及应用》，哈尔滨工业大学出版社，1998年

徐永仁主编：《运筹学试题精选与答题技巧》，哈尔滨工业大学出版社，2000年

弗.S.希利尔等著：《数据、模型与决策》，中国财政经济出版社，2001年

十、先修课程：高等数学线性代数，概率论

十一、考核方式：

1、期末考试：闭卷、笔试。

2、成绩采用100分制记分，期末考试占70%。上机考试和平时成绩占30虬

十二、课时分配：

理论教学：72学时

教学内容学时分配

1、结论1学时

2、线性规划与单纯形法16学时

3、对偶理论与灵敏度分析12学时

4、运输问题6学时

5、目标规划3学时

6、整数规划8学时

7、图与网络分析12学时

8、排队论12学时

9、运筹学案例分析2学时

实验教学：16学时

大纲制订人：李建章

大纲审定人：池洁

4

一、绪论

学习目的了解运筹学的简史、运筹学的性质和特点。熟悉运筹学的工

作步骤和运筹学的模型。了解运筹学的应用。

重点和难点运筹学的性质和特点及运筹学的工作步骤。

§1、运筹学的简史

运筹学作为科学名字是出现在20世纪30年代末。当时英、美对付德

国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运

用时却并不好用。为此一些科学家研究如何合理运用雷达从而开始进行

一类新问题的研究。因为它与研究技术问题不同，就称之为“运用研究”

(OperationalResearch)o这种“运用研究”就是“运筹学”。运筹

学的英语是。perationResearch。

§2、运筹学的性质和特点

运筹学是一门应用科学。至今还没有统一且确切的定义。提出以下

儿个定义来说明运筹学的性质和特点。一个是“为决策机构在对其控制

下的业务活动进行决策时，提供以数量化为基础的科学方法以它强调

的是数量化的存学方法。另一定义是：“运筹学是一门应用科学，它广

泛区用醐有的科学技术知识和数学方法,解决实际中提出的专门问题，

为决策者选择最优决策提供定量依据J

§3、运筹学的工作步骤

运筹学在解决大量实际问题过程中形成了自己的工作步骤。

(1)提出和形成问题。即要弄清问题的目标，可能的约束，问题的可

控变量以及有关参数，搜集有关资料。

(2)建立模型。即把问题中可控变量、参数和目标与约束之间的关系

用一定的模型表示出来。

(3)求解。用各种手段(主要是数学方法，也可用其它方法)将模型

求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机,

解的精度要求可由决策者提出。

(4)解的检验。首先检查求解步骤和程序有无错误，然后检查解是否

反映现实问题。

5

(5)解的控制。通过控制解的变化过程决定对解是否要做一定的改变。

(6)解的实施。是指将解用到实际中必须考虑到实施的问题，如向实

际部门讲清解的用法，在实施中可能产生的问题和修改。

以上过程应反复进行。

§4、运筹学的模型

运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模

型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以

及实体模样描述所认识到的客观对象。

模型有三种基本形式：(1)形象模型,(2)模拟模型,(3)符号或

数学模型。

建立数学模型的方法主要有以下五种：

(1)直接分析法

(2)类比法

(3)数据分析法

(4)试验分析法

(5)想定(构想)法

§5、运筹学的应用

运筹学在早期的应用主要在军事领域。现已发展到广泛的领域：

(1)市场销售

(2)生产计划

(3)库存管理风

(4)运输问题

(5)财政和会计

(6)人事管理

(7)设备维修、更新和可靠性、项目选择和评价

(8)工程的优化设计

(9)计算机和信息系统

(10)城市管理等等说

6

7

二，饯彼规划鸟目标规划

线性规划是运筹学的一个重要分支，自从1947年G.B.Dantzig提出

了一般线性规划问题求解的方法——单纯形法之后，线性规划在理论上

趋向成熟，在实用中日益广泛与深入。

第一章线性规划与单纯形法

本章内容

第一节线性规划问题及其数学模型

第二节线性规划问题的几何意义

第三节单纯形法

第四节单纯性法的计算步骤

第五节单纯形法的敬进一步讨论（大M法与两阶段法求初始基可行解）

重点与难点

1、将实际生产问题、管理问题建立线性规划的数学模型。

2、线性规划数学模型的一般形式

1）决策变量

2）目标函数

3）约束条件

4）符号约束

3、线性规划数学模型的标准形式

4、两个自变量的线性规划的图解法

5、*一般线性规划的单纯形法基础

1）线性规划解的基本概念

-可行解

-最优解

-基

-基解

-基可行解

-可行基

2）线性规划的几何意义

-凸集

-k个点的凸组合

-凸集的顶点

-线性规划可行域是凸集

8

3）基可行解的特征

-可行解是基可行解的充分必要条件是其非零分量的系数列

向量线性无关

-基可行解对应于可行域的顶点

4）线性规划的基本定理

-若线性规划有最优解则最优值一定可在某基可行解处取到，

即包含一个基可行解（顶点）为最优解。

-K个最优解的凸组合都是最优解。

-线性规划的枚举法及其缺点。

6、*线性规划单纯形法

1）线性规划单纯形法的步骤

-找一个基可行解作为初始解

-最优解的判断

-换基

-旋转

2）表格单纯形法

7、*单纯形法的其它问题

1）最优性的判断

-唯一最优解判断

-无穷多最优解判断

-无界解判断

2）检验数的公式法

oj=cj-zj=cj-CBPj,

3）最小化问题的最优性判断与换基

-所有检验数都非负为最优解

-最小的检验数对应的变量进基

4）人工变量法求基可行解

-两阶段法

-大M法

9

第一节线性规划问题及其数学模型

1.1问题的提出

在生产管理和经营活动中经常提出一类问题，即如何合理地利用有

限的人力、物力、财力等资源，以便得到最好的经济效果。

线性规划主要解决两类问题：

1、资源有限，要求生产的产品（或利润）最多。

2、任务（或产品）一定，要求消耗的资源（或成本）最少。

例1某工厂在计划期内要安排生产I、n两种产品，已知生产单位产

品所需的设备台时及A、B两种原材料的消耗，如表1T所示，问应

该如何安排计划才能使该工厂获利最多？

III

设备128台时

原材料A4016kg

原材料B0412kg

单位产品利润（元）23

解设xi,X2分别表示计划期内产品I和产品n的产量，因为设备的有效

台时是8,这是一个限制产量的条件，所以在确定产品I和产品n的产

量时，要考虑不超过设备的有效台时数，即可用不等式表示为

X]+2X2^8

同理，因原材料A、B的限量，可以得到以下不等式

4xiW16

4x2^12

由于该工厂的目标是不超过所有资源限量的条件下，如何确定产量不、

X2以得到最大的利润，若用z表示利润，这时Z=2X]+3X2,综上所述，该问

题可用芈学模型表示为：

目标函数maxZ=2XI+3X2

满足约束条件X,+2X2^8

4X1W16

4x2^12

X1,x2NO

例2靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500

万立方米，在两个化工厂之间也有一条流量为200万立方米的支流。第

一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工

厂每天排放这种工业污水L4万立方米。从第一化工厂排出的工业污水

流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业

10

污水应不大于0.2%。这两个工厂都需要各自处理一部分工业污水。第

一化工厂处理工业污水的成本是1000元/万立方米，第二化工厂处理工

业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，

每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最

小？

解这个问题可用数学模型描述。设两化工厂每天处理工业污水量

分别为X1,X2万n?.由于要求从第一化工厂到第二化工厂之间，河流中工

业污水含量不大于0.2%,由此可得近似关系式

(2-X1)/500W2/1000

流经第二化工厂后，河流中的工业污水量不大于0.2%,这时有近似关系

式

[0.8(2-Xi)+(1.4-X2)]/700^2/1000

由于每个工厂每天处理的工业污水量不会大于每天的排放量，故有

XiW2;x2^1.4

这问题的目标是要求两厂用于处理工业污水的总费用最小。

即z=lOOOxi+800x2.综合上述，这个环保问题可用数学模型表示为：

目标函数minz=l000x1+800x2

约束条件x.^l

0.8XI+X2^1.6

XiW2

X2WL4

Xi,X220

从以上两例可以看出，他们都是属于一类优化问题。它们的共同特征：

(1)每一个问题都用一组决策变量(Xi,X2,X”)表示某一方案;

这组决策变量的值就有代表一过具体方案。

(2)一般这些变量取值是非负的。

(3)存在一定的约束条件，这些约束条件可以用一组线性等式

或线性不等式来表示。

(4)都有一个要求达到的目标，它可用决策变量的线性函数(称

为目标函数)来表示。按问题的不同，要求目标函数实现

最大化或最小化。

满足以上四个条件的数学模型称为线性规划的数学模型。其一般形

式为：

目标函数max(min)z=c1xi+c2x2+...+cnxn(1.1)

约束条件allXi+al2X2+...+alnxn^(=,2)b1

11

a21Xi+a22Xz+…+a2nXnW（=，N）b2

.........................（1.2）

amlX]+am2X2+…+amnXnW（=，》）bm

XL…,Xn》O（1.3）

在线性规划的数学模型中，方程（L1）称为目标函数；（1.2）、（1.3）

称为约束条件；（1.3）也称为一变量的非负约束条件。

1、选择适当的决策变量

注意设决策变量的原则

2、用决策变量表达目标函数

收入或利润极大化

成本或支出极小化

3、用决策变量表达所有的约束条件

4、注意变量的符号约束

设决策变量的原则

1、将决策者想知道但还不知道的设为未知数;

2、所取决策变量要便于表达目标函数和约束条件。

3、当将决策者想知道但还不知道的是由多个部分组成时,则应将最基

本的部分取为决策变量。

例3合理下料问题（P38例理）

例4人事管理问题

例5P38例11配料问题

1.2图解法

图解法简单直观，有助于了解线性规划问题的有关概念及求解的基

本原理。但它只适用于两个自变量或可转化为两个自变量的问题。

考虑例1的数学模型：

maxZ=2X）+3X2

X1+2X2W8

4x1W16

4x2W12

Xi,x2^0

1、由于X1,X220,因此满足约束条件的解（叫可行解）在第一象限。而

每个约束条件都代表了一个半平面。因此可行解集是由几个半平

面围成的一个凸多边形。

12

上述问题的最优解是唯一的。但对一般线性规划问题，求解结果还

可能出现以下儿种情况：

(1)无穷多最优解(多重解)。若将例1中的目标函数变为Z=2X1+4X2,

(3)无可行解。

例maxz=2x1+3x2

X1+2X2W8

4X1W16

4X2^12

-2X]+X224

X|,x2^0

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

由前可知，线性规划问题由各种不同的形式，为了研究线性规划问题

的求解方法，我们要把它们化成标准形式。这里规定的标准形式为：

13

maxz=cix]+c2x2+...+cnxn

s.ta]]x।+a12X2+•••1nxn=b)

a21X1+222X2+…+a2nXn=b2

=

am1X[+am2X2+...+3mn^nbm

Xi,X2,…,Xn》O

其中bi》o(i=l,2,...,m)

简写形式为：maxz=fc*j

六1

=bi

SJ<i=1,2,•••/«;j=l,2,---,n

Xj>0

向量和矩阵表示

maxz=CX

Xpjxj=b

'j=i

Xj>0,j=1,2,…,〃

其中，C=(Ci,C2,---,Cn)

向量Pj对应的决策变量是Xj.

矩阵形式为：

maxz=CX

[AX=B

X>0

all

a12•••aln

a21

A=

如;I'TKELPJ

amlam2…amn_

14

0

L（）j

称A为约束条件的mxn维系数矩阵，一般m<n;m,n>0;

b为资源向量；

C为价值向量；

X为决策变量向量。

实际遇到的各种线性规划问题的数学模型都应变换为标准形式后求

解。

以下讨论如何化标准型的问题：

（1）若要求目标函数实现最小化，即minz=CX.这时只需将目标

函数最小化变换为最大化，即令z'=-z,于是得到maxz'=-CX,

这就和标准型的目标函数的形式一致了。

（2）约束方程为不等式。这里有两种情况：一种是约束方程为‘W'

不等式，则可在'W'不等式的左边加上非负松池变量，把原‘W'不

等式变为等式；另一种是约束方程不等式，则可在不等式

的左端减去一个非负剩余变量（也可称松弛变量），把不等式约束条件

变为等式约束条件。

（3）若存在取值无（符号）约束的变量Xk,可令Xk=Xk'-Xk【其中Xk',Xk''

20。

下面举例说明。

例3将下面的数学模型化为标准型。

MaxZ=2XI+3X2

X,+2X2^8

4xW16

4xzW12

Xi,X220

解将各不等式加上松弛变量即得

MaxZ=2XI+3X2

XI+2X2+X3=8

4xi+x,i=16

4X2+X512

XI,X2,X3,X4X5^0

例4将下述线性规划问题化为标准型

15

minZ=-XI+2X2-3X3

XI+X2+X3^7

XI-X2+X3^2

-3XI+X2+2X3=5

XI,X2NO,X3为无约束

解步骤为

1、令X3=X4-X5,其中X4,X520；

2、在第一个不等式W的左边加上松弛变量X6；

3、在第二个不等式2的左边减去剩余变量X7；

4、令z'=-z,把求minz改为求maxz';即可得该问题的标准型

maxZ'=X-2X2+3(x「xj

X1+X2+(X「X5)+X6=7

x-x+(x4-x)

25-X7=2

-3XI+X2+2(X4-X5)=5

xbX2,x4,X5,x6,x7^0

1.4线性规划问题的解概念

可行解满足约束条件和非负约束的解称为可行解，而使目标函数达到

最大值的可行解叫最优解。

基设A是约束方程组的mxn维系数矩阵，其秩为m。B是A中mxm阶非奇异

子矩阵(|BWO),贝豚B是线性规划问题的一个基。即矩阵B是由m个线

性独立的列向量组成。不失一般性，可设

a\2…a\m、

B==(巴，22，”,以)

aa

、明”,n2mm>

称Pj(J=l,2,…,m)为基向量，与基向量Pj相应的XjO==l,2,…,m)为基

变量。否则称为非基变量。为了进一步讨论线性规划问题的解，下面研

究约束方程(1.5)的求解问题。假设该方程组系数矩阵A的秩为m,因m<n,

故它有无穷多个解。假设前m个变量的系数列向量是线性独立的。这时

(1.5)可写成

16

一“

£PjXj=b-£PjXj

j=lj=tn+l

方程祖（1.7）的一个基是

a\\〃12…a\m'

B=：♦：：=（6,尸2,…&）

%，2…amm>

设xB是对应于这个基的基变量

XB=（X[,X2,…,Xm）T

现若令（1.7）的非基变量Xm+产Xm+2=.—=Xn=0，并用高斯消去法，可以

求出一个解

X=（Xi,X2,...,Xm,0,...,0）l

这个解的非零分量的数目不大于方程的个数m,称为基解。于是，由一个

基可以求出一个基解。

基可行解满足非负条件（1.6）的基解，称为基可行解。于是基可行

解的非零分量的数目也不大于m,并且都是非负的。

可行基对应于基可行解的基，称为可行基。

可见，约束方程祖（1.5）具有的基解的数目最多是个。

基解中非零分量的个数小于m时（或基变量有零时），这基解（或基

可行解）称为退化解（或退化基可行解）。

17

第二节线性规划问题的几何意义

2.1基本概念

凸集设K是n维欧氏空间的一点集，若任意两点X⑴£K,X⑵£K

的连线上的点aX⑴+(l-a)£K,(OWaWl),则称K为凸集。

一般的实心圆，实心多边形、实心多面体等都是凸集，而圆周和有

洞的圆盘等都不是凸集。

凸组合设X⑴，X⑵，…，X的是n维欧氏空间E11中的k个点，若存

在口2，…，口k,且0WLWl,i=l,2,…,k;i>=l，使

1=1

(，)(2)(k)

X=UiX+Ll2X+...4-PkX

则称X为X⑴，X。)，…,X(k)的凸组合。

顶点设K是凸集,X£K,若X不能用不同的两点X"kK和乂2*K

的线性组合表示为

X=aX⑴+(l-a)X⑵，(0<a<1)

则称X为K的一个顶点(或极点)。

2.2基本定理

定理1若线性规划问题存在可行域，则其可行域

。=X'fPjXj=b,Xj>0

Ij=l>

是凸集。

引理1线性规划问题的可行解X=(Xi,X2,…,。尸为基可行解的充分必

要条件是X的正分量是线性独立的。

定理2线性规划问题的基可行解X对应于可行域的顶点。

引理2若K是有界凸集，则任意一点XWK可表示为K的顶点的凸

组合O

定理3若可行域有界，线性规划问题的目标函数一定可以在其可行

域的顶点上达到最优。

有时目标函数可能在多个顶点达到最大值。这时这些顶点的凸组合

上也达到最大值。称这种线性规划问题有无限多个最优值。

18

第三节单纯形法

3.1单纯形法举例

例6试以例1来讨论它的求解。例1的标准型为

maxz=2xi+3x2+0x3+0x4+0x5

xi+2x2+x3=8

4xi+x4=16

4X2+X5=12

Xj20,j=l,2,…,5

解约束方程的系数矩阵

’12100、

4=(尸”8,8，尸4，己)=40010

、04001,

从(1.12)中可以看到X3,X4,X5的系数列向量

是线性独立的，这些向量构成一个基

‘100、

B=(PsR,PJ=010

0"

对应于B的变量X3,X4,X5为基变量，从(1.12)中可以得到

x3=8-x]-2x2

x4=16-4X](1.13)

X5=12-4X2

将(1.13)代入目标函数(1.11)得到

Z=0+2X]+3X2

当令非基变量X|=X2=0,便得到z=0.这时得到一个基可行解X(())

X(0)=(0,0,8,16.12/

现分析(1.13),由于X2的系数为正，显然当将X2越大则目标函数Z的

值也越大。当将X2定为换入变量后，必须从X3,X4,X5中换出一个，并保

证其余的变量都是非负，即X3,X4,X520。

当Xi=0,由(1.13)式得到

x3=8-2x220

x4=16^0(1.15)

19

X5=12-4X220

从(1.15)中可以看出,X2的最大值只有选择

X2=min(8/2,-,12/4)=3

时，才能使(1.15)成立。因当X2=3时，基变量X5=0,这就决定用x2

去替换X5。以上数学描述说明了每生产一件产品H,需要用掉各种资源

的数量为2,0,40由这些资源中的薄弱环节，就确定了产品H的产量,

这里就是由原材料B的数量确定了产品II的产量x2=12/4=3件。

为了求得以X3,X4,X2为基变量的一个基可行解和进一步分析问题，需

将(1.13)中X2与X5的位置对换。得到

X3+2X2=8-x)(1)

x4=16-4X](2)(1.16)

4x2=12-X5(3)

用高斯消去法，将(1.16)式中的系数列向量变换为单位列向量。其运

算步骤是：(3)'=(3)/4；(1)，=(1)-2X(3):(2)'=(2),并

将结果仍按原顺序有:

x3=2-X|+1/2X5⑴，

x4=16-4x](2)'(1.17)

X2=3-1/4X5(3)

再将(1.17)代入目标函数(1.11)得到

Z=9+2+2XR3/4+2X5(1.18)

(1)

令非基变量x,=x5=0,得到z=9,并得到另一个基可行解X

X⑴=(0,3,2,16,0)T

从目标函数的表达式(1.18)中可以看到，非基变量X1的系数是正

的，说明目标函数值还可以增大，X⑴不一定是最优解。于是再用上述

方法，确定换入、换出变量，继续迭代，再得到另一个新的基可行解

X⑵，

炉=(2,3,0,8,0)T

再经过一次迭代，再得到一个基可行解X⑶

父3)=(4,2,0,0,4)T

而这时得到目标函数的表达式是：

z=14-1.5x3-0.125x4(1.19)

再分析(1.19),可见到所有非基变量X3,X4的系数都是负数。这说明若

要用剩余资源X3,X4,就必须支付附加费用。所以当Xa=X4=0时，即不再

利用这些资源时，目标函数达到最大值。所以X⑶是最优解。即应当产

品I生产4件，产品n生产2件，工厂才能得到最大利润。

3.2初始基可行解的确定

20

为了确定初始基可行解，要首先找出初始可行基，其方法如下:

1、若线性规划问题

maxz=2。八

j=i

£PjXj=b

六1

x.>0

从Pj(j=l,2,…,n)中一般能直接观察到存在一个初始可行基

1000、

0100

B=H)=00

10

00()"

2、对所有约束条件是“W”形式的不等式，可以利用化标准型的方

法，在每个约束条件的左端加上一个松驰变量。经各整理，重新

对七及aij(i=l,2,...,m;j=l,2,…,n)进行编号，则可得下列方程组

X]+a],m+lXm+l+…+ainXn=bi

X2+a2,m+lXm+l+…+a2nXn=b2

+am,m+lXm+l+-•・+amnXn=bm

XjNO,j=l,2,...n

显然得到一个mxm单位矩阵

1000、

0100

B=(P\,P>…,P",)=0

010

0001,

以B作为可行基。移项得

xI=bi-aijm+iXm+|-...-alnxn

X2=b2-a2,m+1Xm+「…-a2nXn

Xm=bm-am,m+lXm+l-…-amnXn

令Xm+l=Xm+2=—=Xn=0,由(1.23)可得

Xj=bi(I=l,2,...,m)

又因bj'O,所以得到一个初始基可行解

X=(xi,X2».••,xm,0,...,0)

T

=(b],b2,...,bm,0,...,0)

3.对所有约束条件是“N”形式的不等式及等式约束情况，若不存在单

21

位矩阵时，就采取人造基的方法。即对不等式约束减去一个非负的剩余

变量后，再加上一个非负的人工变量。对于等式约束加上一个非负的人

工变量，总能得到一个单位矩阵。

3.3最优性检验与解的判别

线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无

界解和无可行解四种情况，为此需要建立对解的判别准则。一般情况下,

经过迭代后（1.23）式变为Xj=b"fa"（i=l,2,…,m）（1.24）

j=tn+\

将（1.24）式代入目标函数（1.20）,整理后得

z=2c4+£（c）->/叫"

i=\j=m+\/=1

令z（）=ZW，Zj=gc闻（j=m+l,…,n）

i=li=l

于是z=z（）+Z（c）-z/xj再令er,=Cj-Zj（j=m+l,...,n）

j=m+l

则z=z0+fbjXj（1.27）

y=/n+l

1、最优解的判别定理：若x（°）=（〃心…耳,,0,...,0）T为对应与基B的一

个基可行解，且对于一切j=m+l,...,n有。jWO,则X（°）为最优解，

称。j为检验数。

2、无穷多最优解判别定理：若X（°）=（〃也，…%,0,...,0）T为一个基可行

解，对于一切j=m+l,...,n有。jWO,又存在某个非基变量的检验

数。m+k=。,则线性规划问题有无穷多最优解。

3、唯一最优解判别定理：若X（°）=（〃㈤，.也,,0,...,0）T为一个基可行

解，对于一切上=111+1,…,n有。j<0,则线性规划问题有无穷多最优

解。

4、无界解判别定理：若X（°）=（〃必…叫,,0,..,0）T为一个基可行解，有

一个。m+k>0,并且对i=l,2,…,m有aE+kWO,那么该线性规划问题

具有无界解（或称无最优解）

3.4基变换

1、换入变量的确定：由（1.27）式看到，当某些。/0时，%增加则

目标函数还可以增大，这时要将某个非基变量占换到基变量中去（称为

换入变量）。若有两个以上的。j>0,那么选哪个非基变量作为换入变量

呢？为了使目标函数值增加最快，从直观上一般选。j>0种的大者（可

以任意选或按最小下标选）即

22

max(oj>0)=ok

则对应的Xk为换入变量。(实际上换一次基将使目标函数值改进。k。)o

3、换出变量的确定

按最小比值确定换出变量。

3.5迭代(旋转运算)

将约束条件的增广矩阵中新基变量的系数通过矩阵的行变换或

Gauss变换变为单位矩阵。

例7试用上述方法计算例6的两个基变换。

解约束条件的增广矩阵为

Xix2x3x4x5b

'121008、

4001016

400112,

当以X3,X4,X5为基变量，X],X2为非基变量，令X]=X2=0,可得到一

个基可行解

X(0)=(0,0,8,16,12)

现用X2去替换X5,于是将X3,X4,X2的系数矩阵变换为单位矩阵，经变

换后为

Xix2X3X4x5b

"1010-1/22、

4001016

(()1001/43J

令非基变量x1,X5=0,得到新的基可行解

X⑴=(0,3,2,16,0)T

23

第四节单纯性法的计算步骤

4.1单纯形表(其功能与增广矩阵相似)

将(1.22)式与目标函数组成n+1个变量，m+1个方程的方程组。

X]+a1,m+lXm+l+…+a】nXn=b]

X2+@2,m+1Xm+l+…+a2nXn=b2

Xni+am,m+lXm+l+・•.+amnXn=bm

-Z+C1X1+C2X2+•..+CmXm+Cm+lXm+l+—.+CnXn=O

为了便于迭代运算，可将上述方程组写成增广矩阵

-Z・・・・・・b

X]X2xmXm+|Xn

'010…0ai,m+l…ain

b

001…0a2,m+2…a2n2

..«•

b

000…1a,n„„,

C]C2…品c，”+i・••%

若将Z看成不参与基变换的基变量，它与X”X2,Xm的系数构成一

个基，这时可采用行初等变换将C/2,4变换为零，使其对应的系数

矩阵为单位矩阵，得到

b

-zXiX2.•XmXm+l・・・Xn

'010.••0瓦

b

001•••0Q2M+2«2«2

•.•••

000•••1a,nn

-ECA

100-•・0c.一斗外

/=11=11=1

可根据上述增广矩阵设计计算表如下:

…・・・

CjClCmCm+1Cn0

・・・

bXi・•.

CBXBXmXm+lXn

Qi

ClX1bi10ai,m+ia〕n

b?・・・・・・02

C2X200@2,m+1a2n

CmXmbm0・・・1am,m+1・・・^mnOm

〃】in

C

-ZA・・・♦♦・

-z00G+l-G-ZG%，

/=1Z=1i=l

4.2计算步骤

(1)找出初始可行基，确定初始基可行解，建立初始单纯形表。

24

“I

(2)检验各非基变量Xj的检验数是%=q若%WO,j=m+l,…,”

则已得到最优解。可停止计算。否则，转入下一步。

(3)在%>0,/=〃?+1,…,〃中，若有某个4对应项Xk的系数列向量PkW

0,则此问题是无界，停止计算。否则，转入下一步。

(4)根据max(Oj>0)=Ok,确定Xk为换入变量，按6规则计算

0-min(—Ia*>0)--

a.kaik

可确定XI为换入变量。转入下一步。

(5)以现为主元素进行迭代(即用高斯消去法或称为旋转运算)，把

Xk所对应的列向量

将XB列中的X1换为Xk,得到新的单纯形表。重复(2)—(5),直到

终止。现用例1的标准型来说明上述计算步骤。

(1)根据例1的标准型，去松弛变量X3,X4,X5为基变量，它对应的

单位矩阵为基。这就得到初始即可行解

X(0)=(0,0,8,16,12/

将有关数值填入表中，得到初始单纯形表。

表1-3

Cj23000

bXi9

CBXBx2x3x4x5

0X38121004

-

0x41640010

0x512040013

-z023000

各非基变量的检验数为

o1=cl-z1=2-(0x2+0xl+0x4+0x0)=2

。2=C2-Z2=3-(0X2+0X2+0X0+0X4)==3

⑵因检验数都大于0,且RT2有正分量存在，转入下一步

(3)max(ob。2)=max(2,3)=3;对应的变量x2为换入变量。计算。

25

9=min(—Iai2>0)=min(8/2,-,l2/4)=3

'ai2-

它所在行对应的X5为换出变量，X2所在的列与X5所在的行交叉处［4］为

主元素。

(4)以⑷为主元素进行旋转运算，即初等变换，使P2变为(O,o,1)

丁,在XB列中招-X2替换X5,于是彳等到新表1-4

Cj23000

b9

CBXBX1X2X3x4X5

0x3210