运筹学原理与算法 下载 pdf 百度网盘 epub 免费 2025 电子书 mobi 在线

《运筹学原理与算法》与现行的其他运筹学教材相比，不涉及非线性规划，但增加了网络*选址问题，扩充了网络规划和分配问题的内容。对一些经典运筹问题，补充了一些运筹理论，还补充了一些更加简便、实用的运筹算法。《运筹学原理与算法》的另一个特点是，把运筹方法的程序设计纳入教学内容中，详细、完整、规范地给出了各种运筹方法的算法步骤。

《运筹学原理与算法》是针对应用数学专业本科生编写的教材，也可作为经济管理、系统工程、计算机工程等专业的本科生教材，还可供相关专业研究生及科技工作者参考。

前言

第1章 线性规划

1.1 线性规划的模型及概念

一、线性规划及其模型

二、线性规划的几何意义

1.2 单纯形法

一、线性规划的单纯形表

二、可行基与基可行解的概念和性质

三、已知一个可行基的单纯形法

1.3 对偶单纯形法

一、正则基的概念和性质

二、已知一个正则基的对偶单纯形法

习题1

第2章 线性规划全过程算法

2.1 两阶段法

一、求可行基的方法

二、全过程算法一(两阶段法)

2.2 大M单纯形法

一、基本原理

二、全过程算法二(大M单纯形法)

2.3 大M对偶单纯形法

一、基本原理

二、全过程算法三(大M对偶单纯形法)

2.4 亚基迭代算法

一、概念

二、全过程算法四(亚基迭代算法)

习题2

第3章 线性规划的扩展问题

3.1 线性规划的对偶理论

一、对偶线性规划的概念

二、对偶线性规划之间的关系

3.2 线性规划的灵敏度问题

一、灵敏度的概念

二、目标函数中非基变量的系数cj的灵敏度

三、目标函数中基变量的系数cR(i)的灵敏度

四、约束条件中常数项bi的灵敏度

五、约束条件中非基变量的系数asub>ij

暂无相关内容，正在全力查找中

暂无出版社相关信息，正在全力查找中！

第1 章

　线性规划

线性规划（linear programming）是运筹学中的一个重要分支，在现代工业、农业、商

业、交通运输、国防军事及经济管理等诸多领域都有着广泛、重要的应用．本章介绍的是

线性规划的基本概念、性质及在可行基或正则基已知的前提下求解线性规划的方法．

1.1 　线性规划的模型及概念

一、线性规划及其模型

现实中有许多问题可以表示成，在满足一组线性等式或线性不等式的条件下，寻求

一个能够使某个线性函数的值（或小）的一组变量的取值，这样的问题称为线性

规划问题．其中，被要求值达到（或小）的函数，称为线性规划的目标函数；要求变

量满足的所有条件称为线性规划的约束条件．

例1.1.1 　某厂生产产品A1 ，A2 ，… ，An 要用到原料B1 ，B2 ，… ，Bm.已知该厂每种

原料的拥有量、生产中每种单位产品要消耗的各种原料量，以及每种产品的单位价格，

见表1.1.1.

要研究的问题是：在现有条件下，要获得产值，每种产品应各生产多少？

设xj 为产品A j 的生产量（ j ＝ 1 ，2 ，… ，n） ，则目标函数为总产值

c1 x1 + c2 x2 + … + cn x n

约束条件为原料Bi的拥有量对各种产品A j 的生产量x j 的限制

ai1 x1 + ai 2 x2 + … + ai n xn ≤ bi 　（ i ＝ 1 ，2 ，… ，m）

以及客观条件xj ≥ 0（ j ＝ 1 ，2 ，… ，n）.因此，本题的数学模型为

max c1 x1 + c2 x2 + … + cn xn

s.t.

a1 1 x1 + a12 x2 + … + a1 n xn ≤ b1

a2 1 x1 + a22 x2 + … + a2 n xn ≤ b2

… …

am1 x1 + am2 x2 + … + amn xn ≤ bm

xj ≥ 0 　（ j ＝ 1 ，2 ，… ，n）

其中max 是英文maximum 的缩写，表示取；s.t.是英文subject to 的缩写，表示受

约束于….

例1.1.2 　从A1 ，A2 ，… ，An 矿石中均可提炼出B1 ，B2 ，… ，Bm 物质．已知每种矿石

中可以提炼的各种物质量、提炼单位矿石的费用，以及需要提取的各种物质量，见表

1.1.2.

要研究的问题是：要使总的提炼费用少，这n 种矿石应各选用多少？

设xj 为矿石A j 的选用量（ j ＝ 1 ，2 ，… ，n） ，则目标函数为总提炼费用

c1 x1 + c2 x2 + … + cn x n

约束条件为物质Bi的需要量对各种矿石A j 的选用量x j 的要求

ai1 x1 + ai 2 x2 + … + ai n xn ≥ bi 　（ i ＝ 1 ，2 ，… ，m）

以及客观条件xj ≥ 0（ j ＝ 1 ，2 ，… ，n）.因此，本题的数学模型为

min c1 x1 + c2 x2 + … + cn xn

s.t.

a11 x1 + a12 x2 + … + a1 n xn ≥ b1

a21 x1 + a22 x2 + … + a2 n xn ≥ b2

… …

am1 x1 + am2 x2 + … + amn xn ≥ bm

xj ≥ 0 　（ j ＝ 1 ，2 ，… ，n）

其中min 是英文minmum 的缩写，表示取小；s.t.的含义同上．

例1.1.3 　按照供需要求，要从发货点A1 ，A2 ，… ，Am 处将货物运往B1 ，B2 ，… ，Bn

各收货点．已知各发货点提供的货物量、各收货点的货物需求量、从各发货点到各收货

点的单位货物运费，见表1.1.3.

要研究的问题是：按照供需现状，如何安排各发货点到各收货点的货物量，才能使

总运费少？

设xij 为A i 点运往B j 点的货物量（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n） ，则目标函数为总

运费Σ

m

i ＝ 1 Σ

n

j ＝ 1

cij x ij.但约束条件要分为以下三种情况：

（1） Σ

m

i ＝ 1

ai ＝ Σ

n

j ＝ 1

bj 时，约束条件是：Ai 点运出的货物量应等于A i 点可提供的货物

量，Bj 点收到的货物量应等于B j 点的货物需求量，即Σ

n

j ＝ 1

xij ＝ ai i ＝ 1 ，2 ，… ，m ；

Σ m

i ＝ 1

xij ＝ bj （ j ＝ 1 ，2 ，… ，n） ；以及客观条件xij ≥ 0 i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n.此

时，数学模型为

min Σ

m

i ＝ 1 Σ

n

j ＝ 1

cij x ij

s.t.

Σ n

j ＝ 1

xij ＝ ai 　（ i ＝ 1 ，2 ，… ，m）

Σ m

i ＝ 1

xij ＝ bj 　（ j ＝ 1 ，2 ，… ，n）

xij ≥ 0 　（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）

（2） Σ

m

i ＝ 1

ai ≤ Σ

n

j ＝ 1

bj 时，约束条件是：Ai 点运出的货物量应等于A i 点可提供的货物

量，Bj 点收到的货物量应不超过B j 点的货物需求量，即Σ

n

j ＝ 1

xij ＝ ai i ＝ 1 ，2 ，… ，m ，

Σ m

i ＝ 1

xij ≤ bj （ j ＝ 1 ，2 ，… ，n） ；以及客观条件xij ≥ 0 i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n.此

时，数学模型为

min Σ

m

i ＝ 1 Σ

n

j ＝ 1

cij x ij

s.t.

Σ n

j ＝ 1

xij ＝ ai 　（ i ＝ 1 ，2 ，… ，m）

Σ m

i ＝ 1

xij ≤ bj 　（ j ＝ 1 ，2 ，… ，n）

xij ≥ 0 　（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）

（3） Σ

m

i ＝ 1

ai ≥ Σ

n

j ＝ 1

bj 时，约束条件是：Ai 点运出的货物量应不超过A i 点可提供的货

物量，Bj 点收到的货物量应等于B j 点的货物需求量，即Σ

n

j ＝ 1

xij ≤ ai （ i ＝ 1 ，2 ，… ，m） ；

Σ m

i ＝ 1

xij ＝ bj （ j ＝ 1 ，2 ，… ，n） ；以及客观条件xij ≥ 0（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）.此时，

数学模型为

min Σ

m

i ＝ 1 Σ

n

j ＝ 1

cij x ij

s.t.

Σ n

j ＝ 1

xij ≤ ai 　（ i ＝ 1 ，2 ，… ，m）

Σ m

i ＝ 1

xij ＝ bj 　（ j ＝ 1 ，2 ，… ，n）

xij ≥ 0 　（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）

例1.1.4 　某建筑工地因施工需要，要用12m 长的钢筋，截取5.5m 、3.5m 、2.5m

长的钢筋段各1600 、3500 、2800 根．试问：要使12m 长的钢筋用量少，应如何下料？

分析　按不同的下料方法可以获得的不同结果，见表1.1.4.

设按第j 种方案用12m 的钢筋xj 根（ j ＝ 1 ，2 ，… ，7） ，则目标函数为12m 长的钢筋

总用量x1 + x2 + … + x7.约束条件为截出的5.5m 、3.5m 、2.5m 长的钢筋数量应满足的

需要量2 x1 + x2 + x3 ≥ 1600 ，x2 + 3 x4 + 2 x5 + x6 ≥ 3500 ，x2 + 2 x3 + 2 x5 + 3 x6 + 4 x7 ≥

2800 ，以及客观条件xj ≥ 0（ j ＝ 1 ，2 ，… ，7）.因此，该问题的数学模型为

min x1 + x2 + … + x7

s.t.

2 x1 + x2 + x3 ≥ 1600

x2 + 3 x4 + 2 x5 + x6 ≥ 3500

x2 + 2 x3 + 2 x5 + 3 x6 + 4 x7 ≥ 2800

xj 为整数≥ 0 　（ j ＝ 1 ，2 ，… ，7）

例1.1.5 　在每项工作只能由一人承担的要求下，安排m 个人去完成n 项工作．已

知第i 人完成第j 工作的用时为cij （ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）.研究：如何进行工作

分配，才能使完成所有工作的总用时少？

设xij ＝

1 ，　安排第i 人承担第j 项工作，

0 ，　否则

（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n） ，yi 为第i

人承担的工作数（ i ＝ 1 ，2 ，… ，m） ，则目标函数为完成所有工作的总用时Σ

m

i ＝ 1 Σ

n

j ＝ 1

cij x ij.

约束条件是：每个人对各项工作是否承担应当与其承担的工作数相吻合，即Σ

n

j ＝ 1

xij ＝

yi （ i ＝ 1 ，2 ，… ，m） ；每项工作只能由一人承担Σ

m

i ＝ 1

xij ＝ 1（ j ＝ 1 ，2 ，… ，n） ；所有工作都必

须完成，即Σ

m

i ＝ 1

yi ＝ n ；以及xij ∈ ｛0 ，1｝ （i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n） 和yi ∈ ｛0 ，1 ，… ，n｝

（ i ＝ 1 ，2 ，… ，m）.因此，该问题的数学模型为

min Σ

m

i ＝ 1 Σ

n

j ＝ 1

cij x ij

s.t.

Σ n

j ＝ 1

xij ＝ yi 　（ i ＝ 1 ，2 ，… ，m）

Σ m

i ＝ 1

xij ＝ 1 　（ j ＝ 1 ，2 ，… ，n）

Σ m

i ＝ 1

yi ＝ n

xij ∈ ｛0 ，1｝ ，yi ∈ ｛0 ，1 ，… ，n｝ 　（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）

以上5 个问题的数学模型，目标函数和约束条件都是线性的，变量都是非负的，因

此，都属于线性规划问题．一般线性规划可分为以下三种形式：

（LP1）

min（或max） CT x

s.t.

A x ＝ b

x ≥ 0

（LP2）

min（或max） CT x

s.t.

A x ≤ b

x ≥ 0

（LP3）

min（或max） CT x

s.t.

A x ＝ b

Ax ≤ d

x ≥ 0

其中C ＝ （ c1 ，c2 ，… ，cn ）T ，x ＝ （ x1 ，x2 ，… ，xn ）T ，A ＝ （ aij ）m × n ，b ＝ （ b1 ，b2 ，… ，bm ）T ，A ＝

（ aij ）k × n ，d ＝ （ d1 ，d2 ，… ，dk ）T.

规定　（LP1）为线性规划的标准形．（ LP2）和（ LP3）不是标准形，但都可以化成标

准形．

定义1.1.1 　如果通过加（或减）非负变量把线性规划的不等式约束变成等式约

束，则称这样的非负变量为该线性规划的松弛变量．

例如，引入松弛变量xn + 1 ，xn + 2 ，… ，xn + m ≥ 0 ，可以把例1.1.1 中给出的非标准形线

性规划转化成标准形线性规划：

max c1 x1 + c2 x2 + … + cn xn

s.t.

a11 x1 + a12 x2 + … + a1 n xn + xn + 1 ＝ b1

a21 x1 + a22 x2 + … + a2 n xn + xn + 2 ＝ b2

… …

am1 x1 + am2 x2 + … + amn x n + xn + m ＝ bm

xj ≥ 0 　（ j ＝ 1 ，2 ，… ，n + m）

（1.1.1）

引入松弛变量xn + 1 ，xn + 2 ，… ，xn + m ≥ 0 ，可以把例1.1.2 给出的非标准形线性规划

转化成标准形线性规划：

min c1 x1 + c2 x2 + … + cn xn

s.t.

a11 x1 + a12 x2 + … + a1 n xn - xn + 1 ＝ b1

a21 x1 + a22 x2 + … + a2 n xn - xn + 2 ＝ b2

… …

am1 x1 + am2 x2 + … + amn x n - xn + m ＝ bm

xj ≥ 0 　（ j ＝ 1 ，2 ，… ，n + m）

（1.1.2）

不难理解，任何非标准形线性规划都可以转化成标准形线性规划，因此，如何构建

标准形线性规划问题的解法，是构建一般性线性规划问题的解法的关键．

二、线性规划的几何意义

定义1.1.2 　称集合x A x ＝ b ，x ≥ 0 为线性规划（ LP1）的可行域，该集合中的元

素称为线性规划（LP1）的可行解．

定义1.1.3 　如果（LP1）的可行解能够使（LP1）的目标函数达到目标要求，则该可

行解称为（LP1）的解，对应的目标函数值称为（LP1）的值．

线性规划（LP2）和（LP3）的可行域、可行解、解及值的定义类似．

我们知道，二元一次方程ai1 x1 + ai2 x2 ＝ bi 在x1 Ox2 直角坐标系中，图像是直线．三

元一次方程ai1 x1 + ai2 x2 + ai3 x3 ＝ bi在Ox1 x2 x3 直角坐标系中，图像为平面．但是在n ＞

3 时，n 元一次方程ai1 x1 + ai2 x2 + … + ain xn ＝ bi的图像是无法绘制的，为方便起见，称n

元一次方程的图像为超平面．因此，（LP1）的可行域是一系列超平面的公共点构成的集

合；（LP2）的可行域是一系列超平面围成的集合．特别是在n ＝ 2 时，（ LP2）的可行域是

由若干条直线围成的凸多边形．在n ＝ 3 时，（ LP2）的可行域是由若个平面围成的凸多

面体．

在线阅读地址：运筹学原理与算法在线阅读

在线听书地址：运筹学原理与算法在线收听

在线购买地址：运筹学原理与算法在线购买

暂无原文赏析，正在全力查找中！

编辑推荐

运筹学是20世纪30年代逐步发展起来的一门新兴学科，其涉及的内容具有共同的特征：在诸多因素制约下，为了实现既定的目标，如何通过数学方法作出*好的选择。这样的学科，无疑有着非常广泛的应用背景和重要的应用价值。

《运筹学原理与算法》是编者在多年从事运筹学教学和研究的基础上，结合运筹学的**发展，编写的面向应用数学专业的本科教材。

本书共13章，第1～10章由郭强编写，第11～13章由孙浩编写。

书籍介绍

《运筹学原理与算法》与现行的其他运筹学教材相比，不涉及非线性规划，但增加了网络最优选址问题，扩充了网络规划和分配问题的内容。对一些经典运筹问题，补充了一些运筹理论，还补充了一些更加简便、实用的运筹算法。《运筹学原理与算法》的另一个特点是，把运筹方法的程序设计纳入教学内容中，详细、完整、规范地给出了各种运筹方法的算法步骤。