kl800.com省心范文网

运筹学与最优化方法第4章_图文







线性规划

运筹学

线性规划

本章内容
? ? ? ? ? ? ? ? ? 线性规划问题及其数学模型 线性规划的图解法 线性规划解的基本性质 单纯形算法 初始基本可行解求法 对偶性及对偶单纯形方法 线性规划灵敏度分析 线性规划的建模实例 用数学软件求解线性规划模型介绍

运筹学

线性规划

线性规划研究的主要问题 一类是已有一定数量的资源(人力、物质、时 间等),研究如何充分合理地使用它们,才能使完 成的任务量为最大。 另一类是当一项任务确定以后,研究如何统筹 安排,才能使完成任务所耗费的资源量为最少。 —— 实际上,上述两类问题是一个问题的两个不同 的方面,都是求问题的最优解( max 或 min )。 线性规划(Linear Programming)创始人:1947年 美国人G.B.丹齐克(Dantzing) 1951年提出单纯形算法(Simpler method)

§ 4.1 线性规划问题及数学模型
一、线性规划问题的提出
例4.1生产计划问题(资源分配问题):某工厂生产门 窗两种产品,已知的条件如表所示,试制订总利 润最大的生产计划。
车间 1 2 3 单位利润(元) 单位产品生产所需时间 门 1 0 3 300 窗 0 2 2 500 每天可用生产时间 (小时) 4 12 18

运筹学

线性规划

问题 分析
可控因素:每天生产两种产品的数量,分别设为 x1 , x2 目标:每天的生产利润最大 利润函数 300 x1 ? 500 x2 受制条件: 各车间每天所用工时不超过可用量 车间 1: x1 ? 40 车间 2: 2 x2 ? 12 车间 3: 3x1 ? 2 x2 ? 12 蕴含约束:产量为非负数 x1 , x2 ? 0

运筹学
max 300 x1 ? 500 x2 x1 ? 4

线性规划

模型

s.t.

2 x2 ? 12 3x1 ? 2 x2 ? 18 x1 , x2 ? 0

用Excel软件求解: 产品门生产2件 产品窗生产6件 最大利润3600(元)

运筹学

线性规划

例4.2投资问题:某公司有100万元资金要投资(要 求全部用完)。该公司有六个投资项目可选,已知 的条件如表所示,该公司希望投资风险最小,每年 红利至少为6.5万,最低平均增长率为12%,最低平 均信用度为7。试解该问题。
投资项目 风险(%) 1 2 3 4 5 6 18 6 10 4 12 8 红利(%) 4 5 9 7 6 8 增长率(%) 信用度 22 7 12 8 15 8 4 10 2 10 4 6

运筹学

问题 分析

线性规划

可控因素:项目投资额,设第 i 项目投资额为 xi , i ? 1,2, ?,6 目标:总风险最小, 总风险函数
0.18 x1 ? 0.06 x2 ? 0.10 x3 ? 0.04 x4 ? 0.12 x5 ? 0.08 x6

受制条件: 投资总额 100 万元 红利至少 6.5 万

x1 ? x2 ? x3 ? x4 ? x5 ? x6 ? 100

0.04 x1 ? 0.05 x2 ? 0.09 x3 ? 0.07 x4 ? 0.06 x5 ? 0.08 x6 ? 6.5

最低平均增长率为 12%
0.22 x1 ? 0.07 x2 ? 0.12 x3 ? 0.08 x4 ? 0.15 x5 ? 0.08 x6 ? 12

最低平均信用度为 7
4 x1 ? 10 x2 ? 2 x3 ? 10 x4 ? 4 x5 ? 6 x6 ? 700

蕴含约束:投资额非负数

xi ? 0, i ? 1,2, ?,6

min 0.18 x1 ? 0.06 x2 ? 0.10 x3 ? 0.04 x4 ? 0.12 x5 ? 0.08 x6

模型

用Excel软件求解:

? x1 ? x2 ? x3 ? x4 ? x5 ? x6 ? 100 ?0.04 x ? 0.05 x ? 0.09 x ? 0.07 x ? 0.06 x ? 0.08 x ? 6.5 1 2 3 4 5 6 ? ? s.t.?0.22 x1 ? 0.07 x2 ? 0.12 x3 ? 0.08 x4 ? 0.15 x5 ? 0.08 x6 ? 12 ?4 x ? 10 x ? 2 x ? 10 x ? 4 x ? 6 x ? 700 2 3 4 5 6 ? 1 ? xi ? 0, i ? 1,2, ? ,6 ?

项目1投资25万元 项目2投资0万元 项目3投资12.5万元 项目4投资62.5万元 项目5投资0万元 项目6投资0万元 平均总风险8.25%

运筹学

线性规划

例4.3运输问题:
一个制造厂要把若干单位的产品从 m 个仓库 Ai ; i ? 1,2, ?, m 发送到 n 个零售点 B j ; j ? 1,2, ?, n ,仓库 Ai 能 供应的产品数量为 ai ; i ? 1,2, ?, m , 零售点 B j 所需的产品的 数量为 b j ; j ? 1,2, ?, n 。假设供给总量和需求总量相等,且 已知从仓库 Ai 运一个单位产品往 B j 的运价为 c ij 。问应如 何组织运输才能使总运费最小?
单位运价表(cij) B1 A1 A2 … A3 c11 c21 … cm1 B2 c12 c22 … cm2 … … … … … Bn c1n c2n … cmn
A1 A2 … A3

产销平衡表(决策变量xij=0或1)
B1 x11 X21 … xm1 B2 x12 X22 … xm2 B3 … … … … B4 x1n X2n … xmn

产量 a1 a2 … am

销量

b1

b2



bn

运筹学

线性规划

问题分析
可控因素: 从仓库 Ai 运往 B j 的产品数量 设为 xij ; i ? 1,2, ?, m, j ? 1,2, ?, n 目标:总运费最小 费用函数 ? ? cij xij
i ?1 j ?1 m n

受控条件: 从仓库运出总量不超过可用总量, 运入零售点的数量不低于 需求量。由于总供给量等于总需求量,所以都是等号。即

?x
j ?1
m

n

ij

? ai ; i ? 1,2, ? , m
? b j ; j ? 1,2, ? , n

?x
i ?1

ij

蕴含约束:数量非负 xij ? 0; i ? 1,2, j ? 1,2,3,4

运筹学

模 型

min ?? cij xij
i ?1 j ?1

2

4

线性规划

?n ?? xij ? ai ; i ? 1,2, ? , m ? j ?1 ?m s.t.?? xij ? b j ; j ? 1,2, ? , n ? i ?1 ? xij ? 0; i ? 1,2 ? , m, j ? 1,2, ? , n ? ? 两个例子的特点是:
1 都用一组决策变量X = (x1,x2,…,xn)T表示某一方案,且决策变 量取值非负; 2 都有一个要达到的目标,并且目标要求可以表示成决策变量 的线性函数; 3 都有一组约束条件,这些约束条件可以用决策变量的线性等 式或线性不等式来表示。 这样的数学模型称线性规划模型。

运筹学

线性规划

一般形式
目标函数

Opt. z ? c1 x1 ? c2 x2 ? ? ? cn xn ?ai1 x1 ? ai 2 x2 ? ? ain xn ? bi ; i ? 1, 2,..., p ?a x ? a x ? ? a x ? b ; i ? p ? 1,..., m (4-1) i2 2 in n i ? i1 1 s.t. ? x j ? 0; j ? 1, 2,..., q ? ? x j 无限制 ; j ? q ? 1, q ? 2,..., n ?
约束条件

Opt.=Optimize (使最优化)表示min或max

运筹学

线性规划

其中
x j ; j ? 1,2,...,n 称为待定的决策变量;
x ? ( x1 , x 2 ,? x n ) ? 称为待定的决策向量;
c ? (c1 , c2 , ?, cn ) 称为价值向量;
c j , j ? 1,2,..., n 为称价值系数; b ? (b1 , b2 ,..., bm )T 称为右端向量;

矩阵

? a11 ? ? a 21 A?? ? ? ?a ? m1

a12 a 22 ? am2

? a1n ? ? ? a 2n ? ? 称为(技术)系数矩阵。 ? ? ? ? a mn ? ?

运筹学

线性规划

当p=0,q=n时,模型(4-1)为: 规范形式

max c x

min c x
(4-2)

? Ax ? b 或 ? Ax ? b s.t.? s.t.? ?x ? 0 ?x ? 0
当p=m,q=n时,模型(4-1)为: 标准形式

max c x ? Ax ? b s.t.? ?x ? 0
(4-3)

运筹学

线性规划

解的概念
可行解(或可行点) :满足所有约束条件的向量
x ? ( x1 , x 2 ,? x n ) ?

可行集(或可行域) :所有的可行解的全体
D ? {x Ax ? b, x ? 0}

最优解:在可行域中目标函数值最大(或最小) 的可行解,最优解的全体称为最优解集合
O ? { x ? D c x ? c y , ?y ? D }

最优值:最优解的目标函数值
v ? c x, x ? O

运筹学

线性规划

? 若 D ? ? 称模型(4-3)无解或不可行; ? 若 D ? ?但 Z ? C
X ? ?cjx j 在
j ?1 n

D上 (下) 无界,

称模型(4-3)无界; ? 若 D ? ?且 Z ? C
X ? ?cjx j 在
j ?1 n

D 上有 (下) 界,

称模型(4-3)有最优解。

非标准形式标准化方法:
线性规划标准模型的一般表达式:
3.约束条件为不等式:
ai1 x1 ? ai 2 x2 ? ? ? ain xn ? bi

max Z ? c1 x1 ? c2 x2 ? ? ? cn xn
? a11 x1 ? a12 x2 ? ? ? a1n xn ? b1 ? a x ? a x ??? a x ? b 2n n 2 ? 21 1 22 2 ? s.t. ? ??????????? ?a x ? a x ? ? ? a x ? b mn n m ? m1 1 m 2 2 x1 , x2 ,? xn ? 0 ? ?
min Z ? ? c j x j
j ?1 n

≥0

引进松驰变量xs:

ai1 x1 ? ai 2 x2 ? ? ? ain xn ? xs ? bi

4.约束条件为不等式:

ai1 x1 ? ai 2 x2 ? ? ? ain xn ? bi
引进剩余变量xs:

非标准形式标准化或规范化的方法: 1.目标函数转换

ai1 x1 ? ai 2 x2 ? ? ? ain xn ? xs ? bi

5.决策变量为自由变量:

令Z ? ? Z
'
n n ' j ?1 j ?1

令x j ? u ? v u ? 0, v ? 0
6.约束等式化不等式:

max Z ? ? ? c j x j ? ? ( ?c j ) x j
2.约束右端项为负: 两端乘-1:

ai1 x1 ? ai 2 x2 ? ? ? ain xn ? bi ? ? ai1 x1 ? ai 2 x2 ? ? ? ain xn ? bi ? ? ? ai1 x1 ? ai 2 x2 ? ? ? ain xn ? ?bi

?ai1 x1 ? ai 2 x2 ? ? ? ain xn ? ?bi

例4. 4 把下列线性规划问题转化为标准形式
min z ? ?2 x1 ? x2 ? 3x3 ? ? max z ? ? ? z ? 2 x1 ? x2 ? 3x3 ? 3x3? ? ? ?5 x1 ? x2 ? 3x3 ? 3x3? ? x4 ? 7 ? x ? x ? 4 x ? ? 4 x ?? ? x ? 2 ? 1 2 3 3 5 s.t.? ? ? ?3x1 ? x2 ? 2 x3 ? 2 x3? ? 5 ? x1 , x2 , x3 , x3?, x4 , x5 ? 0 ? ? ?

见基P10例4

?5 x1 ? x2 ? 3x3 ? 7 ?x ? x ? 4x ? 2 ? 1 2 3 s.t.? ? ? 3x1 ? x2 ? 2 x3 ? ?5 ? ? x1 , x2 ? 0, x3为自由变量 ?

min z ? ? x1 ? x2 ?2 x1 ? x2 ? ?2 ?x ? 2x ? 2 ? 1 2 s.t.? ? x1 ? x2 ? 5 ? x1 ? 0 ? ?

max z ? ? x1 ? ( x3 ? x4 ) ?2 x1 ? ( x3 ? x 4 ) ? x5 ? ?2 ? x ? 2( x ? x ) ? x ? 2 ? 1 3 4 6 s.t.? ? x1 ? ( x3 ? x4 ) ? x7 ? 5 ? xi ? 0; i ? 1,3,4,5,6,7 ?
max z ? ? x1 ? ( x3 ? x 4 ) ?? 2 x1 ? x3 ? x 4 ? 2 ? x ? 2( x ? x ) ? 2 ? 1 3 4 s.t.? ? x1 ? ( x3 ? x 4 ) ? 5 ? xi ? 0; i ? 1,3,4 ?

利用上述转换一般LP模型可化为规范型:
? ? max z ? ? ? z ? 2 x1 ? x2 ? 3x3 ? 3x3? ? ? ?5 x1 ? x2 ? 3x3 ? 3x3? ? 7 ?? x ? x ? 4 x ? ? 4 x ?? ? 2 2 3 3 ? 1 ? ? ? s.t.?3x1 ? x2 ? 2 x3 ? 2 x3? ? ?5 ?? 3x ? x ? 2 x ? ? 2 x ?? ? 5 1 2 3 3 ? ? ? ? x1 , x2 , x3 , x3? ? 0 ?

运筹学

线性规划

§ 4.2线性规划的图解法
一、图解法
对于只有两个变量的线性规划问题可以用图解法求解:

max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0

x2
最优解

6
可行域

4

-8
0
目标函数等值线

6

x1

例4.5 用图解法求解例4.1

max 300 x1 ? 500 x2 x1 ? 4

s.t.

2 x2 ? 12 3x1 ? 2 x2 ? 18 x1 , x2 ? 0

B是直线
2 x2 ? 12与3x1 ? 2 x2 ? 18

交点解之得 产品门生产2件 产品窗生产6件 最大利润3600(元)

运筹学

线性规划

4.3 线性规划解的基本性质
max z ? ? x1 ? x 2 ?2 x1 ? x 2 ? ?2 解线性规划 ? x1 ? 2 x 2 ? 2 ? s.t.? ? x1 ? x 2 ? 5 ? x1 ? 0 ?
最优解(1,4)

例4.6

2 x1 ? x 2 ? ?2

x1 ? 2 x 2 ? 2 x1 ? x 2 ? 5

运筹学

线性规划

当目标函数改变后,等直线的方向会发生改变,如 果等值线与某个约束对应的函数直线平行, 则该函 数值线上的所有可行解都是最优解
最优解(1,4)

2 x1 ? x 2 ? ?2

x1 ? 2 x 2 ? 2

x1 ? x 2 ? 5

一、四种结局:
x2
x2

x1 唯一最优解 x2 x2 无界解

x1

x1 无穷多最优解 无可行解

x1

Ex 1、 化标准形

2、用图解法求解

运筹学

线性规划

二、可行域的几何结构
基本假设
考虑线性规划的标准形式
max c x ? Ax ? b s.t.? ?x ? 0

其中 x, c ? R n , b ? R m , A ? R m?n ,并且假定可行域

D ? {x ? R n Ax ? b, x ? 0} 不空,系数矩阵 A 是行
满秩的, r( A) ? m ,否则的话可以去掉多余约束。

运筹学

线性规划

凸 集
凸集及其性质: 定义 4.1:设 S ? R n 是 n 维欧氏空间的点集,若对任 意 x ? S , y ? S 的和任意 ? ? [0,1] 都有

?x ? (1 ? ? ) y ? S
x

就称 S 是一个凸集。 定理 4.2 任意多个凸集的交还是凸集 定理 4.1 线性规划的可行域
y

D ? {x Ax ? b, x ? 0} 是凸集

♂返回

运筹学

线性规划

可行域的凸性
超平面 半空间 多面凸集

H ? {x ? R n a ? x ? b} H ? ? {x ? R n a ? x ? b} ; H ? ? {x ? R n a ? x ? b}

S ? {x ? R n ai? x ? bi ; i ? 1,2,..., p;ai? x ? bi ; i ? p ? 1, p ? 2,..., p ? q}
定义 4.2:设 S 为凸集 x ? S ,如果对任意 y, z ? S 和 0 ? ? ? 1 ,都有

x ? ?y ? (1 ? ? ) z 则称 x 为 S 的顶点。

运筹学

线性规划

问 题
1.可行域顶点的个数是否有限? 2.最优解是否一定在可行域顶点上达到? 3.如何找到顶点? 4.如何从一个顶点转移到另一个顶点

♂返回

运筹学

线性规划

三、基本可行解与基本定理
基本可行解定义:
因为在模型(4-3)中 r( A) ? m ,故 A 中必有 m 列线性无关,不妨设 前 m 列线性无关,它们构成矩阵 B,其余列构成矩阵 N,则 B 可逆且
A ? ( B, N ) 。

令, x =( x B , x N )。则
Ax ? b

分块

Bx B ? Nx N ? b
N

左乘 B ?1

x B ? B ?1 Nx N ? B ?1b
?x ?

取x 为自由变量 x B ? B ?1b ? B ?1 Nx N ?????? X ? ? B ? 是AX ? b 的全部解 ? xN ?

特取 x N =0 的可行解。

? B ?1b ? ? 是 AX=b 的特解,若 x ? 0 也就是模型(4-3) x?? ?0 ? ? ?

运筹学

线性规划

定义 4.3:设 B 是秩为 m 的约束矩阵 A 的一个 m 阶满秩子方 阵,则称 B 为一个基; B 中 m 个线性无关的列向量称为基向量, 变量 x 中与之对应的 m 个分量称为基变量,其余的变量为非基变
? B ?1b ? ? 称为相应于 量,令所有的非基变量取值为 0,得到的解 x ? ? ?0 ? ? ? B 的基本解。当 B ?1b ? 0 则称基本解为基本可行解,这时对应的 基阵 B 为可行基。

如果 B ?1b ? 0 则称该基可行解为非退化的,如果一个线性规 划的所有基可行解都是非退化的则称该规划为非退化的。

运筹学

线性规划

可行解、非可行解、基本解和基本可行解的关系:
全部解

可 行 解 非可行解 基本可行解 基本解

♂返回

运筹学
例 4.7 考虑问题:
max z ? x1 ? x 2 ?? 2 x1 ? x 2 ? x3 ? 2 ?x ? 2x ? x ? 2 ? 1 2 4 s.t.? ? x1 ? x 2 ? x5 ? 5 ? x j ? 0; j ? 1,2,3,4,5 ? ? ? 2 1 1 0 0? ? ? A ? ? 1 ? 2 0 1 0? 系数矩阵 ? 1 1 0 0 1? ? ? ? 1 0 0? ? ? 2 0 0? ? ? ? ? B2 ? ? 1 1 0 ? B1 ? ? 0 1 0 ? 基阵为 ? 1 0 1? ?0 0 1? ? ? ? ?

线性规划

对应的基解分别为 x 1 ? (0,0,2,2,5) ? 和 x 2 ? ( ?1,0,0,3,6) ? , 其中 x 1 为 基本可行解, x 2 不是基本可行解。

运筹学
小结:

线性规划

? 可行解:满足约束条件 AX=b 和 X ? 0 的解。所有可行解的集合 称可行域记为 D。 ? B 是一个基:矩阵 A 中 m×n 阶非奇异子矩阵(∣B∣≠0) 。 ? Pj ( j = 1 2 … … m) 为基向量:Pj 是基 B 的某列。 ? Xj 为基变量:Pj 为基向量( j = 1 2 … … m) ? 基本解:满足约束条件 AX=b,且所有的非基变量取值为 0 的 m 解,最多有 C n 个。 ? 基本可行解:满足非负约束条件的基本解。
? B ?1b ? ? 是基本可行解,即基 B 使 ? B 为可行基:B 是基, x ? ? ?0 ? ? ?

B ?1b ? 0 。
基本解是否是可行解很容易判断, 但可行解是否是基本可行解又如何 判断呢?

运筹学

线性规划

基本定理
定理 4.3 可行解 x 是基本可行解的充要条件是它的正分 量所对应的矩阵 A 中列向量线性无关。 定理 4.4 x 是基本可行解的充要条件是 x 是可行域 D 的 顶点。 定理 4.5 一个标准的 LP 问题如果有可行解,则至少有 一个基本可行解
推论:非空多面凸集 D={ x ? R Ax ? b x ? 0 }至少存一个顶点。
n

定理 4.6 一个标准的 LP 问题如果有有限的最优值,则 一定存在一个基本可行解是最优解。
推论:若模型(4-1)有最优解,则其最优解一定能在基本可行解中 找到。

运筹学
定理 4.5 和定理 4.6 合称 LP 的基本定理。 在基本可行解中找到最优解的关键?

线性规划

现在由基本定理可知若能判断基本可行解是否是最优解,并能给出 从一个基本可行解转到另一个基本可行解的方法, 则我们就能在基本可 行解中找到最优解。从而把一个无限的问题转化为一个有限的问题。 问题: 1. 如何找一个基本可行解? 2. 如何判断一个基本可行解是最优解? 3. 如果一个基本可行解不是最优解,则如何从一个基本可行解转到 另一个基本可行解?

运筹学

§ 4.4 单纯形法
max c x (1) (2) ? (3)

线性规划

一、单纯形方法的原理和步骤
考虑标准 LP 问题:
? Ax ? b s.t. ? ?x ? 0

?x ? max ? cB , cN ? ? B ? ? xN ? ? ?x ? ? B, N ? ? B ? ? b ? ? ? xN ? s.t. ? ?? xB ? ? 0 ?? x N ? ?? ?

原线性规划等价于
max cB B ?1b ? ? x ? cB b? ? ? N x N ? x B ? B ?1 NxN ? B ?1b ? b? s.t.? ?x ? 0

(4-4)

称为原问题对应于基 B 的典式。 x 其中 r( A) ? m , 是它的一个非退化的基本可行解, 基为 B= ( AB , AB ,?, AB ) , 基变量为 xB = ( xB , xB ,?, xB ) A 的剩余列的子块为 N (通过改变变量次序可使 A=(B,N)) ,非基变量为 xN , ? N ? cN ? cB B ?1N , ? B ? 0 , ? ? (? B , ? N )
1 2 m

1

2

m

? B ?1b ? 由(4-4)可看出当 x ? ? 0 ? 是基本可行解而且 ? N ? 0 时,Z= Z0 ? cBb? 最小。 ? ?

运筹学

线性规划 定理 4.7(最优性准则)在原问题对应于基 B 的典式中,

如果 ? ? 0 ,则基本可行解 x 为原问题的最优解。 定理 4.8 (无界准则)如果向量 ? 的第 k 个分量 ? k ? 0 ,而 向量 B ?1 Ak ? 0 ,则原问题无界。 定理 4.9(最优解的存在性)对于非退化的基本可行解 x , 若向量 ? 的第 k 个分量 ? k ? 0 ,而向量 B ?1 Ak . 至少有一个正分
? ? 量,则可以找到一个新的基本可行解 x ? x ? ? d 使得 c x ? c x 。
? ? B ?1 Ak ? ? ? 其中 d ? ? ? ? ek , ? ? min{bi? / aik aik ? 0, i ? 1,2,..., m} , ? O ?
? bi? ? ( B ?1b) i , aik ? ( B ?1 Ak )i ,分别是 B ?1b和B ?1 Ak 的第 i 个分量。

运筹学

线性规划

? B ?1b ? Th.4.7 给出标准 LP 问题的基本可行解 x ? ? ? ,由交的检验数向量 ? 0 ? ( ? ? 0 否?)判定其是否为该 LP 问题的最优解的方法。 ? B ?1b ? Th.4.8 给出标准 LP 问题由他的某一基本可行解 x ? ? ? 的检验数 ? 、 ? 0 ?

基 B 与约束矩阵 A 一起来确认该 LP 问题无界(无最优解)的方法。 Th4.9 给出标准 LP 问题由其一非最优基本可行解去得另一个更优基 本可行解的方法。 由于由一个基本可行解去找另一个更优的基本可行解关键是基 变量的变换(用非基变量代替原来的基变量) ,故把这个过程称为换 基。

运筹学

线性规划

单纯形法的基本思想:从一个基本可行解出发,如果判定它不是最 优解, 也不能确认该问题无界则用 Th.4.9 提供的换基方法使目标函数减 小,直至找出最优可行解或确认该 LP 问题无界为止。
找出一个初始可行解


是否最优

最优解

循 环



结束

转移到另一个目标函数 (找更大的基本可行解)

运筹学

线性规划

单纯型法步骤如下 1.找一个初始的可行基 B; 2.求出对应的典式及检验数向量 ? ; 3.求 ? k
? max{ ? j j ? 1,2,..., n} ;

4. 如果 ? k

? 0 则该基可行解就是最优解停止; 否则转第

5 步;

5.若 B ?1 Ak ? 0 停止,原问题无界,否则转第 6 步; 6.求 ?
? ? ? ? min{bi? / aik aik ? 0, i ? 1,2,..., m} ? br? / a rk ,

7. 以 Ak 替代 Ar 得到一个新的基,转第 2 步。

二、表格单纯形法
用一种类似矩阵的表格操作来示单纯形方法,这种表 称为单纯形表.
cj→ CB xB CN xN

1、 初始单纯形表的建立
(1)表格结构:
cj→ cB xB c1 x1 c2 x2 b’ b’1 b’2 c1 x1 1 0 … 0 0 c2 x2 0 1 … 0 0 … … … … … … 0 cm xm 0 0 … 1 0 cm+ xm+1 … … cn xn a’1n a’2n … a’mn σn

θ

cB xB b’ cB xB b’
θ

Em B-1N θ σN

-z
θ1 θ2


-xB b’ O

a’1m+1 … a’2 m+1 … … …

… … … cm xm b’m -z 0 -CB b

a’mm+1 … σm+1 …

θm
0

(2)表格设计依据:
将-Z看作不参与基变换的基变量,把目标函数表达式 改写成方程的形式,和原有的m个约束方程组成一个具有 n+m+1个变量、m+1个方程的方程组:
max Z ? C x

max cB B ?1b ? ? N x N

? Ax ? b 化典式 ? x B ? B ?1 NxN ? B ?1b s.t.? ? s.t.? ?x ? 0 ?x ? 0

? ? z ? CB xB ? C N xN ? 0 ? ?1 C B 其增广矩阵为 ? ? xB ? B ?1 Nx N ? b? ?O E ?

CN B ?1 N

0? ? b? ?

? 1 ? C B ? ? ?1 C B ?? ?? O Em ? ? O I m ? ? 1 CB ?? ?O B ?1 ? ?O O Em CN N

CN B ?1 N

0 ? ? ?1 O ??? b? ? ? O E m CN

C N ? B ?1 NCB B ?1 N

?CB b? ? ? b? ?

0 ? 初等行变换 ? 1 CB ? ? ???? ? b? ? O Em ?CB b? ? ? 1 ??? ? ? ?O b O Em

B ?1 N

0 ? 初等行变换 ? ? ???? b? ? ? z0 ? ? b? ?

C N ? B ?1 NCB B ?1 N

?N
B ?1 N

运筹学
2、 用单纯形表计算,作新单纯形表

线性规划

如果 x k 为入基变量, x r 为出基变量,则经过变换可以得到新的单纯形 ? 表。方法是把出基变量 xr 和入基变量 xk 所在行列交叉处的元素 ark(称为转 轴元用*号或方括号标注)化为 1,所在列其余元素化为 0。

cj→ cB xB
c1 x1
? b
? b1

c1 …
x1

cr …
xr … ? a1r …

cm
xm

cm+1 …
x m ?1 … ? a1m ?1 …

ck …
xk …

cn
xn
? a1n

… …

θ
? 1?

1

0 …

0 … …

… … cr



… … … … 0 …





… …
? a rn


? r?

? xr br? / a rk

? 1/ a rk … 0

? a rm?1 …

1 … …

… … cm xm
- z0


? bm

… … … … 0 …
? a mr …

… 1 …0





… …
? … a mn
? ?n


? ?m

? a mm?1 … 0
? ? m ?1 …

? - xB b

? 0 … - ? k / a rk

0 …

? ? ? ? ? 其 中 aij ? aij ? a rj aik / a rk ; i ? 1,2,...,m, i ? r, j ? k

? ? ? ? ? a rj ? a rj / a rk , br ? br? / a rk ,

? ? ? ? ? ? ? ? bi ? bi? ? aik bi? / a rk , ? ?j ? ? j ? a rj? j / a rk ; cB B ?1b ? cB B ?1b ? br?? k / a rk 。

max z ? 5 x1 ? 2 x2 ? 3x3 ? x4 ? x5

例1.8 求解线性规划 见基P33和38例1例2

? x1 ? 2 x2 ? 2 x3 ? x4 ? 8 ? s.t.?3x1 ? 4 x2 ? x3 ? x5 ? 7 ? x ? 0; j ? 1,2,..., 5 ? j

cj→
? ?C B ? ? E ?C N B ?1 N ?5 2 0? ? ?? 1 2 ?? ? b ?3 4 ? 0 0 1? 1 0 8? ? 0 1 7? ? 0 ?2 1 0 0 1 0 3 ?1 1 0 ? 2 1 0 8? ? 1 0 1 7? ?

5 b 8 7 1 4 3 x1 1 3 3 1/2 [5/2] 1 0 1 x4 x5 x3 x5

2 x2 2 4 0 1 3 -4 2/5 6/5

3 x3 [2] 1 4 1 0 0 1 0

-1 x4 1 0 0 1/2 -1/2 -2

1 x5 0 1 0 0 1 0 8 6/5

cB xB -1 1 3 1 3 5

?
4 7

?3 0 4 ? ? 1 2 [2] ? ?3 4 1 ? ?4 ? 1 ? ? 1/ 2 1 ? ? [5 / 2] 3 ? ? 0 ?26 / 5 ? ?0 2 / 5 ? ?1 6 / 5 ?

σj=cj-zj

0 ?15 ? 1/ 2 0 4 ? ? ?1 / 2 1 3 ? ? ?9 / 5 ?2 / 5 ?81 / 5 ? 3 / 5 ?1 / 5 17 / 5 ? ? ?1 / 5 2 / 5 6/5 ? ?

σj=cj-zj -15 x3 17/5 x1 6/5

3/5 -1/5 -1/5 2/5 -9/5 -2/5

σj=cj-zj -81/5 0 -26/5 0

σ≦0,已是最优单纯形表 x1=6/5,x2=0,x3=17/5,x4=0,x5=0为最优解,最优值为z=81/5

运筹学

例 4.9 求解例 4.1 问题
max Z ? 300 x1 ? 500 x2 ? x1 ? 4 ?2 x ? 12 ? 2 s.t. ? ?3x1 ? 2 x2 ? 18 ? x1 , x2 ? 0 ?

线性规划

max Z ? 300 x1 ? 500 x2

标准化:

? x1 +x3 ? 4 ?2 x +x ? 12 ? 2 4 s.t. ? ?3x1 ? 2 x2 ? + x5 ? 18 ? xi ? 0, i ? 1, 2,?,5 ?

以 x 3 、 x 4 和 x 5 为基变量就可以得到初始基可行解 (0,0,4,12,18) ? ,其对应的 单纯形表为:
xB
x3

300 b’ 4

500

0

0

0

x1
1

x2
0 [2] 2 500

x3
1 0 0 0

x4
0 1 0 0

x5
0 0 1 0

?
--6 9

x4
x5

12 0 18 3 0 300

运筹学

线性规划

迭代 1:由于 ? 2 ? 500 ? 0 最大,所以该基可行解不是最优解,同时系 数 矩 阵 该 列 有 大 于 0 的 元 素 , 所 以 取 x2 为 入 基 变 量 。 计 算 ? ? min{12 , 18} ? 6 ,所以取第二个约束对应的基变量 x 4 为出基变量, 2 2 就可以得到一个新的基可行解,在上表中把 x 2 对应的列变成单位向 量,则可以得到该基可行解的单纯形表:
300
xB
x3

500

0

0

0

b’ 4 12 18 0 4 6 6

x1
1 0 3 300 1 0 [3]

x2
0 [2] 2 500 0 1 0 0

x3
1 0 0 0 1 0 0 0

x4
0 1 0 0 0 1/2 -1 -250

x5
0 0 1

?
--6 9

x4 x5
x3

x2

x5

0 0 4 0 --1 2 0

-3000 300

运筹学

线性规划

迭代 2:由于 ? 1 ? 300 ? 0 ,所以取 x1 为入基变量。计算 ? ? 2 ,所以 x 3 为出基变量, 就可以得到一个新的基可行解,在上表中把 x 3 对应的列变成单位向量,则可以得 到该基可行解的单纯形表:
xB
x3

300 b’ 4 6 6 -3000 2 6 2

500

0

0

0

x1
1 0 [3] 300 0 0 1

x2
0 1 0 0 0 1 0 0

x3
1 0 0 0 1 0 0 0

x4
0 1/2 -1 -250 1/3 1/2 -1/3 -150

x5
0 0 1 0 -1/3 0 1/3 -100

?
4 --2

x2

x5
x3

x2 x1

-3600 0

由于检验数都小于等于 0, 所以该基可行解就是最优解, 对应的最优解为 (2,6,2,0,0) , 最优值为 3600。

运筹学

min z ? ? x2 ? 2 x3

线性规划

1 1 13 ? x1 ? x4 ? x5 ? ? 2 2 2 ? 1 3 5 x2 ? x4 ? x5 ? 例 4.10 求解问题 ? ? s.t. ? 2 2 2 ? 1 1 1 x3 ? x4 ? x5 ? ? 2 2 2 ? ? x j ? 0; j ? 1, 2,...,5 ?

取基变量为以 x1 、 x2 和 x3 为就可以得到初始基可行解 (13/ 2,5 / 2,1/ 2, 0, 0)? , 其对应的单纯形表为:
x1
0

x2
0 0 1 0

x3
0 0 0 1

x4
3/2 -1/2 -1/2 -1/2

x5
-5/2

RHS -7/2

x1 x2
x3

1 0 0

5/2 13/2 3/2 5/2 1/2 1/2

注:第 0 行基变量对应的元素必需用约束行化为 0 才是单纯形表。

因为 ? 4 ? 3 / 2 ? 0, 但A4 ? 0 ,所以此问题无界。故无解。

♂返回

运筹学

线性规划

注意:1 当检验数向量 ? 中有不止一个正分量时,每一个正分量对应的非基变量都 可选为进基变量(由用非基变量变为基变量的变量) ,但不同的选择是会影响目标 函数的下降速度,会影响我们求最优解所需换基的次数(换基次数越小越好) 。 ? ?目标函数值C ? x ? C ? x ? ?? k ??? k 越大目标函数值越小。但 ? k 最大不一定 ? 最大,也就不能保证 ?? k 最大。 2.目前当检验数向量 ? 中有不止一个正分量时,如何选择进基变量?最好的策 略是什么?尚未解决。 3.为了使换基过程能由计算机编程执行一般常取 ? 最大的分量对应的非基变 量为进基变量。 brp br1 br2 bi 4. 若 ? = min{ | aik ? 0, i ? 1, 2,?, m} ? 则 可 选 xr1 , xr2 ? xrp ? ??? aik ar1k ar2k arp k
? 中任意一个为离基变量。但在新的基本可行解中第 r1 , r2 ? rp 个分量均为 0,? x 此

时是一个退化的基本可行解,但非退化的 LP 问题是不会出现上述问题的。

运筹学

§4.5 初始解

线性规划

单纯形法必需是从基本可行解出发找最优解,但 一般要找一个初始的基本可行解并不是那么容易。若 约束方程的系数矩阵中出现一个单位阵,用单位阵的 每一个列向量对应的决策变量作为“基变量”,则很 容易就得到了一个初始的基本可行解。要使系数矩阵 中出现一个单位阵,一个简单的方法就是添加人工变 量,找到一个单位矩阵基(叫人工基)。但添加人工 变量后又不能影响目标函数的取值,一般可采用两种 方法处理:大M法和两阶段法。

运筹学

线性规划
m i n ? x 1 ?2 x2 z ? x1 ? x2 ? 2 ?? x ? x ? 1 ? 1 2 s.t.? ? x2 ? 3 ? x1 , x2 ? 0 ?

一、大 M 法
例 4.11(见基 P42 例 3)用 M 法求解 LP 问题
max z ? ? x 1 ?2 x 2 ? x 1 ? x 2 ? x3 ? 2 ?? x ? x ? x ? 1 ? 1 2 4 s.t.? ? x 2 ? x5 ? 3 ? x j ? 0, j ? 1,2, ? ,5 ?

把它标准化

(1)

此时,约束条件的系数矩阵中不含有单位矩阵,没有明显的基 怎么办?将其加上人工变量 x 6 , x 7 ,变为
max z ? ? x 1 ?2 x2 ? Mx6 ? Mx7 ? x 1 ? x 2 ? x3 ? x6 ? 2 ?? x ? x ? x ? x ? 1 ? 1 2 4 7 s.t.? ? x 2 ? x5 ? 3 ? x j ? 0, j ? 1,2, ? ,5 ?

(2)

运筹学

线性规划

此时的(1)与(2)一般情况下是不等价的,只有当 x 6 = x 7 =0 时才等价。 我们在目标函数中把 x 6 ,x 7 前面系数设成-M, “罚 称作 因子” ,其含义是只要 x 6 , x 7 ≠0,目标函数就不可能达到最优。 为此,尽快逼它=0,即把它从基中赶出来。求解时,把 M 看成非 常大的常数来处理。 对(2)作初始表:

-1
xB
x6 x7

2

0

0

0

b’ 2 1

x1
1

x2
1

x3
-1 0 0
-M

x4
0 -1 0
-M

x5
0 0 1 0

-M -M x6 x7 1 0 0 0 0 1 0 0

?
2 1 3

-1 [1] 0
-1

x5 3
0

1
2+2M

运筹学
用单纯形法迭代计算
xB
x6

线性规划
-1 b’ 2 1 3
3M

2

0
x3

0
x4

0
x5

-M
x6

-M
x7

x7
x5

x1 x 2 1 1 -1 [1] 0 1
-1 2+2M

?
2 1 3 1/2 --2 1 --3

-1 0 0
-M

0 -1 0
-M

0 0 1
0

1 0 0
0

0 1 0
0

最优解为
x ? (0,3,1,2,0,0,0)T
T 原LP的最优解为 x ? (0,3)

x6

1 1 2
-2+M

[2] -1 1 1 0 0
0

0 1 0 0

-1 0 0

1 -1 1

0 0 1
0

1 0 0
0

-1 1 -1
-2-2M

x2
x5

1+2M 0

-M 2+M

其最优值为

Z min ? ?6

x1 x2
x5

1/2 3/2 3/2
-5/2

-1/2 [1/2] 0 -1/2 1/2
3/2

1/2 1/2 -1/2
-1/2-M

-1/2 1/2 -1/2
-3/2-M

1 -1/2 0 1/2
0 1/2

0 1
0

x4 x2 x5 x4 x2
x3

1 2 1
-4

2 1 -1
-3

0

-1

1 0 0
0

0 0 1
0

1 1 -1
2-M

-1 0 0
-M

1 -1 0 [1]
0 2

2 3 1
-6

1 0 -1
-1

0 1 0
0

0 0 1
0

1 0 0
0

1 1 1
-2

0 0 -1
-M

-1 0 0
-M

运筹学

线性规划

一般若模型( 2.4.1)的约束条件的系数矩阵中不含有单位矩阵, 则强行 加上人工变量 xn?1 ,? , xn ? m ,变为求解辅助问题
max z ? c x ? M ? Ax ? x a ? b s.t.? ? x ? 0, x a ? 0
? n?m i ? n ?1

?x

i

( 2.4.5)

当 M 为足够大的正数时其最优解对应的人工变量 x a ? 0 , 从而最优解 对应于原问题的可行解,且目标函数值相等;同时原问题的任意可行 解 x 对应于辅助问题的可行解 (x,0) ? ,且目标函数值相等。所以两个 规划最优值相等,且辅助问题的最优解 (x,0) ? 对应可得原问题的最优 解 x 。因此只需求解辅助问题就可求得原问题的最优解。
另外,如最后基变量中还存在目标中以M为系数的人工变量,则原问题无解。

运筹学

线性规划

注:用大M法处理人工变量,再用手工计算是不 会碰到麻烦。但用电子计算机求解时,对M就只 能在计算机内输入一个极其最大字长的数字。如 果LP问题中的,或等参数值与这个代表M的数相 对比较接近,或远远小于这个数字,由于计算机 计算时取值上的误差,有可能使计算结果发生错 误。为了克服这个困难,多采用两阶段法。

运筹学 二、两阶段法

线性规划

?基本思想: 第一阶段,通过求解辅助问题的最优基可 行解得到原问题的初始基可行解。
辅助问题
设原问题为

第二阶段,求原问题的最优解。

min c ? x ? Ax ? b s.t.? ?x ? 0
min g ? ? xi
辅助问题为
i ? n ?1 n?m

( 4-3) ?

? Ax ? x a ? b s.t.? ? x ? 0, x a ? 0
?

(4-5)

其中 xa ? ( xn ?1 , xn ?2 ,..., xn ?m ) 为人工变量。

运筹学 辅助问题与原问题的关系

线性规划

1.原问题有可行解的充分必要条件是辅助问题的最优值为 0。 2.由于 b ? 0 ,所以辅助问题的基变量即是引入的人工基变量 x a ? ( x n ?1 , x n ? 2 ,...,x n ? m ) ? ,初始基本可行解为 (0, b ? ) ? 。 3.辅助问题有可行解 (0, b ) ,同时 x a ? 0 ,所以 ? x i ? 0 。即
i ? n ?1
? ?

n?m

问题的目标函数有下界,所以辅助问题一定有最优解。
x x 4.首先求辅助问题的最优基本可行解 ( ~, ~a ) ,如果最优值为 0, x x x 则 ~a ? 0 , ~ 是原问题的基本可行解。(因 ( ~, ~a ) 是辅助问题的基本 x 可行解,其非零分量 ~ 对应系数矩阵的列向量线性无关。故 ~ 是原问 x x 题的基本可行解。)

运筹学

线性规划

求辅助问题解的三种情况:
1.最优目标函数值为 ? x i ? 0 且 x a 为非基变量,则此时 ~ 是原问题 x
i ? n ?1 n?m

的基本可行解,~ 是基变量。在辅助问题最优单纯形表中删除 x a 对应 x 的列,同时计算出检验数就可以得到原问题的单纯形表。 2.最优目标函数值为 ? x i ? 0 ,则原问题没有可行解。
i ? n ?1 n?m

3. 最优目标函数值为 ? x i ? 0 且 x a 中有部分变量为基变量, 则此时 ~ x
i ? n ?1

n?m

是原问题的基本可行解,但基变量会有些改变,要将其中的人工变量 进一步换出基。 (见 P32)

运筹学

线性规划

例 4.12 ( 见 基 P47 例 4 ) 用 二 阶 段 法 求 解 前 例 LP 问 题
m i n ? x 1 ?2 x2 z ? x1 ? x2 ? 2 ?? x ? x ? 1 max z ? ? x 1 ?2 x 2 ? 1 2 s.t.? ? x 1 ? x 2 ? x3 ? 2 x2 ? 3 ? ?? x ? x ? x ? 1 4 ? x 1 , x2 ? 0 s.t.? 1 2 ? ? ? x 2 ? x5 ? 3 把它标准化 ? x j ? 0, j ? 1,2, ? ,5 ?

(1)

将其加上人工变量 x 6 , x 7 ,建立辅助模型
max z ? ? x6 ? x7 ? x 1 ? x 2 ? x3 ? x6 ? 2 ?? x ? x ? x ? x ? 1 ? 1 2 4 7 s.t.? ? x 2 ? x5 ? 3 ? x j ? 0, j ? 1,2, ? ,5 ?

(2)

运筹学
以 x 6 和 x 7 为基变量,其对应的单纯形表为:
z g c C b’ 2 1 3 0 4 1 1 2 -2 2 1/2 3/2 3/2 -5/2 1 -1 0 2 0 0 0
x3

线性规划
c
0 0
x4

0 0
x5

0 -1
x6

0 -1
x7

xB

b’ 1/2 3/2 3/2 -5/2 1 2 1 -4 2 3 1 -6

-1 x1 1 0 0 0 2 1 -1 -3 2 1 -1 -1

2 x2

0
x3

0
x4

0
x5

?

xB
x6

x7 x5

x1 x 2 1 1 -1 [1] 0 1
-1 0 [2] -1 1 1 2 1 0 0 0 0 0 0 0 1 0 0 0 2 2 0 1 0

?
2 1 3

x1

x2
x5

-1 0 0 0 -1 -1 0 0 0 -1 -1/2

0 -1 0 0 -1 1 -1 1 2 1 1/2

0 0 1 0 0 0 0 1 0 0 0 0 1 0 0

1 0 0 0 0 1 0 0 0 0 1/2 1/2 -1/2 -1/2 -1

0 1 0 0 0 -1 1 -1 -2 -2 -1/2 1/2 -1/2 3/2 0

0 -1/2 [1/2] 1 -1/2 -1/2 0 1/2 1/2 0 0 1 0 0 0 1 0 0 1/2 -1 -1 [1] 2 0 0 1 0 3/2 1 0 0 0 1 0 0 0

0 1 0 --1 3 0 0 0 1 0 1 1 1 -2 ----3 2 --3

z g
x6

x4

x2
1/2 --2
x5

x2
x5

x4

z g
x1

x2
x3

x2
x5

-1/2 -1/2 1/2 1/2 1/2 0 3/2 0

T 最优解为 x ? (0,3,1,2,0)

z g

由于检验数都小于等于 0,辅助问题最优值为 0 且人工变量都是非基变量,所以去掉辅助问 题检验数和人工变量的行列,后继续求解得

T 原LP的最优解为 x ? (0,3)

其最优值为

Z min ? ?6

运筹学

线性规划

三、关于单纯形方法的几点说明和修正单纯形法
1、退化问题的处理
按最小比值 ? 来确定换出基变量时,有时出现两个以上相同的最小 比值,从而使下一个表的基可行解中出现一个或多个基变量等于零的 退化解。退化解出现的原因是模型中存在多余的约束,使多个基可行 解对应同一个顶点。 当存在退化解时, 就有可能出现迭代计算的循环。 即从一个可行基经有限次迭代后又回到原来的可行基。尽管可能性及 其微小,但在理论上讲是存在的。有人提出用下标值最小的变量作为 换出变量、 摄动方法、 字典序方法和 Bland 反循环方法等来防止循环, 但计算量大编程复杂。

E.Beale 曾给出一个循环的例子: 用单纯型法求解 maxZ=3/4 x 4 -20 x 5 +1/2 x 6 -6 x 7 s.t

x1

+1/4 x 4 -8 x 5

- x6 + x6

+9 x 7 =0 =1

x2
x3

+1/2 x 4 -12 x 5 -1/2 x 6 +3 x 7 =0

x j ? 0( j ? 1,2,?7)
显然, x1 , x 2 , x 3 是初始可行基变量,经过 6 次迭代后,又回到了初始状态。得不到最优 解。有兴趣的同学可自行用单纯型法验证本题产生的循环现象。而实际上本题有最优解: X*=(3/4,0,0,1,0,1,0)T

运筹学

线性规划

2、修正的单纯形算法
用计算机计算 LP 问题时要考虑如何节省储存单元和减少计算量,所以用计算机编 程解 LP 问题通常采用修正变量法。为了让同学们能把计算机编程技术与我们的课程学 习结合,补充介绍修正单纯形法。 前面我们对单纯形法表来历分析时提到,单纯形法实际上是把分块矩阵
? ? ?1 CB ? ?O B ? CN ? 0 ? 初等行变换 ? ?1 CB ? ? ???? ? b? ? O Im ? CN

N

B ?1 N
? ?N

0 ? 初等行变换 ? ? ???? b? ? z0 ? ? b ?

? ?1 O ? ? O Im

? ? CN ? B ?1 NCB

B ?1 N

? ?CB b ? ? ?1 O ??? b ? ? O Im

B ?1N
?1

因此单纯形法表中实际上我们所关注的数据只是 B b z 0 ? N以及? N 中最大的

? k对应的B ?1 N的列Ak ,其余数据是多少无关紧要。

运筹学
因为由标准 LP 问题的典式已知
? ? T ? ? z0 ? c? x ? cB B ?1b ? ? ? xN ? cB B ?1b , ? N ? cB B ?1 N ? cN

线性规划

设初始基为 B ? ( AB1 ,? , ABr ,?, ABm ) 换基后新基为 B ? ( AB1 ,? , ABk ,? , ABm ) 则

B ?1B ? B ?1 ( AB1 ,?, Ak ,?, ABm ) ? ( B ?1 AB1 ,?, B ?1 Ak ,?, B ?1 ABm ) ? (?1 ,?, ? r ?1 , Ak , ? r ?1 ,?, ? m ) ? Erk
于是 B ? BErk


B ?1 ? ( BErk )?1 ? Erk ?1 B ?1

? 1 0 ? ?a1k ark ? 0 ? ? ? 0 1 ? ?a2 k ark ? 0 ? 由逆矩阵计算易知 Erk ?1 ? ? ?? ? ? ? ? ?? ? ? 0 0 ? ?amk ark ? 0 ? ? ?1 ?1 ?1 ?1 ?1 ?1 ?1 又因为 Erk Erk ? ( Erk ?1 ,?, Erk ? r ?1 , Erk Ak , Erk ? r ?1 ,?, Erk ? m ) ? E 所以 Erk Ak ? ? r
而 Erk ( B 所以 ( B
?1
?1 ?1

Ak ) ? ( Erk ?1 B ?1 Erk ?1 Ak ) ? ( B ?1 ? r )

初等行变换 Ak ) ???? ( B ?1 ? r ) ?

运筹学
1. 2. 3. 4. 5. 对给定的基 B 计算 B?1
?1 计算 b ? B b 和 ? N ? cN ? cB B N
T ? ? ?1

线性规划

计算, ? N ? 0 则已获得最优解, 若 停止。 否则令 ? k ? max(?i , ?i ? 0) 确定入基变量。 计算 z ? cB B b ? cB b 和 Ak ? B Ak ? (a1k , a2 k ,?, amk ) 判断 Ak ? 0 ,.是原问题无界,停止。否进行下一步。
? ?1 ? ?1 ?

6.

? ? ? ? min{bi / a ik a ik ? 0, i ? 1,2,...,m} =
ABr 得新基 B 。

br , r ? {1, 2,? , m} ,在 B 中以 Ak 取代 ark

7. 8.

计算 Erk ? B B 计算 B
?1

?1

? ( BErk )?1 ? Erk ?1 B ?1 ,用 B ?1代替B ?1 反回②。

运筹学

线性规划

注意:修正单纯形法适合修正单纯形法计算机编程计算。人工计算还是 用单纯形法表直观方便且不易出错。一般适合人工计算的方法不一定 适合计算机计算,反之亦然。因此计算机编程计算一定要研究算法, 否则编不出好程序。

3、特殊问题的处理
运输问题、变量有界线性规划问题等特殊问题,虽然是线性规划模型可 用单纯形法求解,但由于约束条件较多,导至计算和存贮量较大,普通 计算机和软件难以求解。因此针对它们的特点又发展出一些专用的算法。

4、Karmarkar算法

作业:

运筹学

线性规划

§ 4.6 对偶性及对偶单纯形方法
? 对偶规划问题

? 对偶理论 ? 对偶单纯形算法

运筹学

线性规划

一、规范形LP问题的对偶问题
1、规范形 LP 的对偶规划
min z ? c ? x

由规范形式:

(2.5.1) ? Ax ? b s.t. ? ?x ? 0 Max z*=b ? w (2.5.2)
w?0

构造一个新 LP 问题: s.t A? w ? c

其中: w ? (w1 , w2 ,?, wm ) 称(2.5.2)是原 LP 问题,记为(P)LP,而称(2.5.2)是 (2.5.1) 的对偶 LP 问题,记为(D)LP。 显然(2.5.2)的对偶 LP 问题是(2.5.1),即(2.5.2)与(2.5.1)互为其 对偶 LP 问题。 可用下表表示这对互为其对偶的规划问题, 并称它为对偶表。

运筹学

线性规划

对偶表

x1 ? 0 c1
v|

x2 ? 0 c2
v|
a12 ?

? ?

xn ? 0 cn

Min max

v|
a1n

w1 ? 0
w2 ? 0
? wm ? 0

a11

? b1
? b2 ? ? bm

a11 a12 ? a1n ???????????? a11 a12 ? a1n

运筹学 对偶规划有什么实际意义? 考察下例子

线性规划

例13 资源的合理利用问题(基P 73例1) 某工厂用三种原料生产二种产品,已知的条件如下表所 示,试制订总利润最大的生产计划。 设每天生产两种产品的
所需资源数量/件 产品甲 产品乙 资源 A 可用量 资源 A1 资源 A 2 资源 A 3 利润/件(千元) 5 2 1 10 2 3 5 15 17 10 15

数量分别为 x1 , x 2 , 则
max z ? 10 x1 ? 15 x 2 ?5 x1 ? 2 x 2 ? 17 ?2 x ? 3x ? 10 ? 1 2 s.t.? ? x1 ? 5 x 2 ? 15 ? x1 , x 2 ? 0 ?

运筹学
下面从另一个角度来讨论这个问题:

线性规划

假定由于市场变化,决策者决定不再生产甲乙种产品,而是将厂里的现 有资源用于接受外来加工任务,收取加工费。试问该决策者应制定怎样 的收费标准(合理的)? 分析问题: 1、每种资源收费用不能低于自己生产时的可获利润; 2、资源单位定价不能太高,要使对方能够接受。
设w1 , w2 , w3 分别为三种资源的收费单价,w 为总收费,一般而言,w 越大

越好,但因需双方满意,故模型为
min w=17w1 ? 10w2 ? 15w3 ?5w1 ? 2 w2 ? w3 ? 10 ? ? 2 y1 ? 3 y2 ? 5 y3 ? 5 ? w ,w ,w ? 0 ? 1 2 3
max z ? 10 x1 ? 15 x 2 ?5 x1 ? 2 x 2 ? 17 是原模型 ?2 x1 ? 3x2 ? 10 的对偶规划。 ? s.t.? ? x1 ? 5 x 2 ? 15 ? x1 , x 2 ? 0 ?

运筹学
对偶问题的经济解释
①资源影子价格 原始问题是利润最大化的生产计划问题:

线性规划

运筹学

线性规划

对偶问题是资源定价问题:
总利润(元) 资源限量(吨)

min s.t.

y?

b1w1 a11w1

?b2 w2 ?

?bm wm ? wm ?1

? a21w2 ? ? am1wm

资源价格(元/吨)

? c1 ? c2 ?

a12 w1 ? a22 w2 ? ? am 2 wm ? ? ? ? a1n w1 ? a2 n w2 ? ? amn wm w1 w2 ? wm wm ?1

? wm ? 2 ? ? wm ? n wm ? 2 ? wm ? n

? cn ?0

对偶问题是资源定价问题,对偶问题的最优解w1、w2、...、 wm称为m种资源的影子价格(Shadow Price)

运筹学 资源影子价格的性质:

线性规划

z ? y ? b1w1 ? b2 w2 ? ? ? bi wi ? ? ? bm wm
z ? ?z ? b1w1 ? b2 w2 ? ? ? (bi ? ?bi )wi ? ? ? bm wm

?z ? ?bi wi
?z o 最大利润的增量 wio ? ? ? 第i种资源的边际利润 ?bi 第i种资源的增量

? 影子价格越大,说明这种资源越是相对紧缺。 ? 影子价格越小,说明这种资源相对不紧缺。 ? 如果最优生产计划下某种资源有剩余,这种资源的 影子价格一定等于 0。

运筹学
②产品的机会成本

线性规划

增加单位资源可以增加的利润

max z ? c1x 1 ? c 2 x 2 ? ? c j x j ? ? c n x n s.t. a 11 x 1 ? a 12 x 2 ? ? a 1j x j ? ? a 1n x n ? b1 w1 a 21 x 1 ? a 22 x 2 ? ? a m1 x 1 ? a m2 x 2 x1 x2 ? ? a 2j x j ? ? ? ? a mj x j ? xj

? ? a 2n x n ? b 2 w2 ? ? ? ? ? a mn x n ? b m wm ? xn ? 0

减少一件产品可以节省的资源 机会成本 a1 j w1 ? a2 j w2 ? ? ? aij wi ? ? ? amj wm 表示减少一件产品所节省的资源可以增加的利润

运筹学
③产品的差额成本(Reduced Cost)

线性规划

min y ? b1 w1 ? b2 w2 ? ? bm wm ? c1 s.t. a11 w1 ? a 21 w2 ? ? a m1 wm ? wm ?1 ? wm ?2 a12 w1 ? a22 w2 ? ? a m 2 wm ? c2 ? ? ?? ? ? ? wm ?n ? cn a1n w1 ? a 2 n w2 ? ? a mn wm w1 w2 ? wm wm ?1 wm ?2 ? wm ?n ? 0
wm? j ? ( w1a1 j ? w2 a2 j ? ? ? wm amj ) ? c j ? W T a j ? c j

机会成本

差额成本

利润

差额成本=机会成本 - 利润

运筹学

线性规划

2、标准 LP 问题的对偶规划
min z ? c ? x
(P)LP

? Ax ? b s.t. ? ?x ? 0

化规范形后得 (4-3)

min y ? b ? w ? A w ? c (4-5) ? s.t. ? ? w无约束 ?
T

(D)LP

min z ? c ? x

min z ? c ? x

min z ? c ? x

证: :

?? A ? ? Ax ? b ? ? ? Ax ? b ? ?? ? x ? b (规范形) ? s.t. ? s.t. ?? Ax ? ?b s.t. ?? ? A ? x?0 ? ?x ? 0 ?x ? 0 ? ?

max y ? b ? x

令w1 ? w2 ?? A ?T ? w1 ? T T 1 2 ?? ? ? ? ? 2 ? ? c ? ? A ( w ? w ) ? c ? s.t. ? A w ? c ﹟ s.t. ?? ? A ? ? w ? s.t. ? 1 2 ? ? w无约束 ?w , w ? 0 ? ? 1 2 ? w ,w ? 0 ?

max y ? b ? x

min y ? b ? w

运筹学

线性规划

3、一般 LP 问题的对偶规划
min z ? c ? x
(P)LP

? A1 x ? b1 (4-1) 化规范形后得 ? 2 2 s.t. ? A x ? b ? x1 ? 0, x 2无约束 ?
1 2 1 2

? w1 ? max y ? b ? ? 2 ? ?w ? ?? A1T ? ? w1 ? ? c1 (4-6) ?? ?? ? s.t. ?? A2T ? ? w2 ? ? c 2 ? ? ? 1 2 ? w 无约束, w ? 0
(D)LP

其中 A ? (aij ) P?n , A ? (ai ? P j )( m ? P )?n , c ? (c j ) q?1 , c ? (c j ? q )( n ?q )?1

w1 ? ( wi ) P?1 , w2 ? ( wi ? P )( m? P )?1 , x1 ? ( x j ) q?1 , x 2 ? ( x j ? q ) ( n ?q )?1

运筹学

线性规划

对偶规则:
?原问题有m个约束条件,对偶问题有m个变量. ?原问题有n个变量,对偶问题有n个约束条件. ?原问题的价值系数对应对偶问题的右端项. ?原问题的右端项对应对偶问题的价值系数. ?原问题的约束系数矩阵转置后为对偶问题的约束系数矩阵. ?原问题的约束条件与对偶问题方向相反. ?原问题与对偶问题优化方向相反. ?原问题变量非负约束对应对偶约束为不等式. ?原问题变量无非负约束对应对偶约束为等式.

运筹学

线性规划

可用如下对偶表表示对偶规则: 一般 LP 问题的对偶表:
x1 c1 x2 ? xq c2 ? cq xq ?1 ? xn cq ?1 ? cn
|| || Min max

?
a11 a21 a p1

?

?

??

w1
w2
?

a12 ? a1q

a1q ?1 ? a1n

? b1
? b2
?

a22 ? a2 q a2 q ?1 ? a2 n a p 2 ? a pq a pq ?1 ? a pn

????????????

wp
w p ?1
?

? bp ? bp ?1
?

a p ?11 a p ?12 ? a p ?1q a p ?1q ?1 ? a p ?1n
????????????

wm

am1

am 2 ? amq amq ?1 ? amn

? bm

有了对偶表易建对偶模型。

运筹学
max z=2x1 ? x2 ? 4 x3 ? 2 x1 ? 3x2 ? x3 ? 1 例 14 原 LP 问题 ? 3x1 ? 2 x2 ? x3 ? 4 ? ? ? ? 5 x1 ? 6 x2 ? x3 ? 3 (见基P 79例2) ? x1 ? 0, x2 ? 0, x3无约束. ?
求对偶规划模型。 解:因该 LP 问题的对偶表:

线性规划
? max z=-2x1 ? x2 ? 4 x3 ? ? ?2 x1 ? 3x2 ? x3 ? 1 ? 3x? ? 2 x ? x ? 4 ? 1 2 3 ? ? ? ?5 x1 ? 6 x2 ? x3 ? 3 ? x1 ? 0, x2 ? 0, x3无约束. ? ?

x1 ? 0 x2 ? 0 x3
-2 1

min W=w1 ? 4 w2 ? 3w3
max min ≤1 ≤-4 =3

w1 ? 0
w2 ? 0 w3

-2 3 -5

3 2 6

4 ?|| 1 -1 1

? DP

? ?2 w1 ? 3w2 ? 5w3 ? ?2 ? 3w ? 3w ? 6w ? 1 ? 1 2 3 s.t ? ? w1 ? w2 ? w3 ? 4 ? w1 , w2 ? 0, w3无约束 ?

?

?

运筹学
由原 LP 问题,求对偶问题的模型的方法:

线性规划

①把原 LP 问题的不等式统一。当目标最大时,统一成 ? 的形式; 当目标最小时,统一成 ? 的形式。 ②原 LP 问题的每一个约束 (除非负约束外) 对应一个对偶变量 wi , 若该约束是不等式约束,则 wi ? 0,否则 wi 无约束。 ③原 LP 问题的每一个变量 xi 有系数向量 Aj ? (a1 j , a2 j ,?, amj )T 是其对 偶的第 i 个约束行系数, xi ? 0, 若 则对偶约束是与原约束相反的不 等式约束。否则应的对偶约束是等式约束。 ④原 LP 问题的目标函数的变量 xi 的系数是第 i 个对偶约束右边常 数;反之对偶 LP 问题的目标函数的变量 wi 的系数是第 i 个对偶约 束右边常数。 ⑤原 LP 问题的目标函数求最大,则对偶问题就求最小;原 LP 问 题的目标函数求最小,则对偶问题就求最大。原 LP 问题的目标函 数的系数是约束。

运筹学

线性规划

二、对偶理论
Th.4.10 如果原 LP 问题有最优解,则它的对偶问题也有最优解。且 max z=min y。 Th.4.12(对称性定理)任何 LP 问题的对偶问题的对偶是原问题。即原 LP 问题与对偶 LP 问题互为其对偶。 Th.4.13 对给定的原始 LP 问题, 下表所给的三种情况恰有一种出现。
对偶问题与原问题的解的关系:
对偶 有最优解 问题无界 无可行解 原始 有最优解 ① × × 问题无界 × × ③ 无可行解 × ③ ② 其中“×”表示不可能发生,只有 4 种情况(3 类)可发生。

运筹学

线性规划

Th.4.14(互补松紧性)设 x 0 、 w 0 分别是原始问题和对偶问题的可行 解,则它们分别是各自的最优解的充分必要条件是
ui ? wi ( aiT x 0 ? bi ) ? 0 v j ? ( c j ? AT j w0 ) x j ? 0 i ? 1, 2,?, m j ? 1, 2,?, n

其中 aiT ? (ai1 , ai 2 ,?, ain ), 是约束矩阵 A 的第 i 行。Aj 是 A 的第 j 列。 注:
ui ? wi ( aiT x 0 ? bi ) ? 0 v j ? ( c j ? AT j w0 ) x j ? 0 i ? 1, 2,?, m j ? 1, 2,?, n

称为互补松紧条件。其含意是若

对偶问题中的变量 wi ? 0 ,则原问题中对应的第 i 个约束条件必取等 号,反之若原 LP 问题中的变量 xi ? 0 ,则对偶问题中对应的第 i 个约 束条件必取等号。即对偶问题中的最优基本可行解 w 0 中的非零分量 使原问题中对应的第 i 个约束条件必取等号,反之也然。

min z ? 3x1 ? 4 x2 ? 2 x3 ? 5 x4 ? 9 x5

例 15

已知LP

? x2 ? x3 ? 5 x4 ? 3x5 ? 2 ? s.t. ? x1 ? x2 ? x3 ? x4 ? 2 x5 ? 3 ? x ? 0, j ? 1, 2,3, 4,5 ? j

(见基P 86例4)

其对偶线性规划DP的最优解为ω*=(1,3)T,试用松紧互补定理求LP的最优解。 max W=2w1 ? 3w2 解:由LP得DP为 把ω*=(1,3)T代入对偶约束知,对偶的 ? w2 ? 3 第3,4个约束为松约束,由松紧互补定 ? w ?w ?4 2 理得x*3=x*4=0和 ? 1
? DP ? w1 ? w2 ? 2 ? s.t ? ?5w1 ? w2 ? 5 ?3w ? 2 w ? 9 2 ? 1 ? w1 , w2 ? 0 ? ?

由ω*=(1,3)T,得Zmin=Wmax=11,即
* * ? x2 ? 3x5 ? 2 解方程 ? * * * ? x1 ? x2 ? 2 x5 ? 3 ? * * * 3x1 ? 4 x2 ? 9 x5 ? 11 ?

* * * 3x1 ? 4 x2 ? 9 x5 ? 11

得 x1* ? 1 ? x5 * x2 * ? 2 ? 3 x5 *

令x*5=0和x*5=2/3得LP的两个 最优解x(1)=(1,2,0,0,0)T x(2)=(2/5,0,0,0,2/3)T

所以LP的全部最优解为: λx(1)+(1-λ) x(2) , λ∈[0,1]

运筹学

线性规划

三、对偶单纯形算法
对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶 原理和单纯形法的原理而设计出来的,因此称为对偶单纯形法。不要 简单理解为是求解对偶问题的单纯形法。
max z ? c ? x

对标准 LP 问题

? Ax ? b s.t. ? ?x ? 0

定义(基本正则解) :设 B 是标准 LP 问题的一个基,关于基 B 的 T 基本解为 x ? ( xB , xN )T (不一定是可行解) ? T ? c ? cB B ?1 A ? 0 ,则称 B ,若 是正则基, x ? ( xB , xN )T 是基本正则解。 单纯形法求解基本思想:从基本可行解出发寻找既是基本可行解 又是基本正则解的解=最优解。即从满足 B ?1b ? 0 的基本解入手,在保 持 B ?1b ? 0 的条件下寻找满足 c? B ?1 A ? c? ? 0 的基本解。 B 对偶单纯形法求解基本思想: 从基本正则解出发寻找既是基本正 ? 则解又是基本可行解的解=最优解。即从满足 c ? ? cB B ?1 A ? 0 的基本解
? 出发,在保持 c ? ? cB B ?1 A ? 0 的条件下寻找满足 B ?1b ? 0 的基本解。

运筹学

线性规划

注意到基本正则基 B 就对应其对偶问题的一个可行解 w ? ( B ?1 )T cB 。由对偶 理论可以知道,对于一个线性规划问题,我们能够通过求解它的对偶问题来 找到它的最优解。因此可得对偶单纯形法求解方法如下: 从对偶的一个基本可行解开始,保持对偶问题的可行性,向原始可行解的 方向迭代,即从一个基本可行解(迭代)到另一个基本可行解,使目标函数 值 减 少 使 目 标 函 数 值 ( z ? wT b ? wT Ax ? cB B ?1b ? cBb ? cT x ) 减 少 , 当 迭 代 到 xB ? B ?1b ? 0 时,即找到了原 LP 问题的最优解,这就是对偶单纯形法。 设 B 是原 LP 问题的基本正则基,那么始何换基才能使基即保持正则性又 能使目标函数值减少使目标函数值减少呢? 同理与单纯形法一样,由对应的典式的分析可得对偶单纯形法步骤如下 (见基 P95-96) 1.找一个初始的正则基 B,列对偶单纯形表。 2.求 br ? min{bi i ? 1, 2,..., m} 确定出基变量。出对应的典式及检验数向量 ? 。 3.若 br ? 0 停止,该基对应的解 x ? ( B ?1b, O)T 就是最优解;否则转入下一步。 4. 如果 arj ? 0 j ? 1, 2,? m ,停止,原 LP 问题无解;否则转入下一步。 5. 求 min{? j / arj | arj ? 0, j ? 1, 2,..., n} ? ? k / ark 确定出基变量。 6. 以 ark 为转元作一次旋转得新的对偶单纯形表,转第 2 步。

运筹学
max z ? ?3x1 ? 2 x2

线性规划
max z ? ?3x1 ? 2 x2

?2 x1 ? 3x2 ? x3 ? 18 ? 2 x1 ? 3x2 ? x3 ? 18 例 16 解 LP 问题 ? x1 ? x2 ? 2 标准化得 ? x1 ? x2 ? x4 ? 2 ? ? s.t. ? s.t. ? x ? 3x2 ? 10 ? x1 ? 3x2 ? x5 ? 10 (见基P 96例7改) ? 1 ? x j ? 0; j ? 1, 2,3 ? x j ? 0; j ? 1, 2,3, 4,5 ? ? 取 x3 , x4 , x5 为对偶的基变量,列初始表得
c

xB
x3

b’ 18 -2 -10 0 8 -16/3 10/3 20/3

-3 x1

-2 x2

0
x3

0
x4

0
x5

c

xB
x3

b’ 4 4 2 16

-3 x1 0 1 0 0

-2 x2 0 0 1 0

0
x3

0
x4

0
x5

x4
x5

2 3 1 -1 1 0 -1 [-3] 0 -3 -2 0 1 0 0 0 1 0 -[4/3] 0 1/3 1 -7/3 0

0 1 0 0 1 1 0 0

0 0 1 0 1 1/3 -1/3 -2/3

x1

x2

1 0 0 0

3/4 -3/4 1/4 -7/4

5/4 -1/4 -1/4 -5/4

x3

x4

T 最优解为 x ? (4,2,4,0,0)

x2

原LP的最优解为 x ? (4,2,4)
其最优值为

T

Z max ? ?16

min z ? 5 x1 ? 21x3

例 17 用对偶单纯形法解 LP 问题

? x1 ? x2 ? 6 x3 ? 2 ? s.t. ? x1 ? x2 ? 2 x3 ? 1 ? x ? 0; j ? 1, 2,3, 4,5 ? j

max z ? ?5 x1 ? 21x3 ? x ? x ? 6 x3 ? x4 ? 2 解:模型标准化得 ? 1 2 s.t. ? x1 ? x2 ? 2 x3 ? x5 ? 1 ? x ? 0; j ? 1, 2,3, 4,5 ? j

max w ? 2 y1 ? y2

? y1 ? y2 ? y3 ? 5 对偶问题为 ? ? y1 ? y2 ? y4 ? 0 ? s.t. ? ?6 y1 ? 2 y2 ? y5 ? 21 ? y j ? 0; j ? 1, 2,3, 4,5 ?
b 2 1 0 0 0

取 x4 , x5 为基变量,列初始表得
c

xB
x4
x5 x3 x5 x3

b’ -2 -1 0 1/3 -1/3 -7 1/4 1/2 -31/4

-5 x1 -1 -1 -5

-21 x2 1 -1 -21

0
x3

0
x4

0
x5

yB
y3

c’ 5 0 21 0

y1
1 -1 6* 2 0 0 1 2 0 0 1 0

y2
1 1 2 1 2/3* 4/3 1/3 1 1 0 0 0

y3
1 0 0 0 1 0 0 0

y4
0 1 0 0 0 1 0 0

y5
0 0 1 0 -1/6 1/6 1/6 0 -1/4 1/2 1/4 ----7/2 ----7/2

-6* -2 0 1 0 0 1 0

1 0 0 -1/6 -1/3

0 1 0 0 1

y4 y5
y3

即从最优单纯 形表中即可得 LP的解又可得 DP的解。

1/6 -1/6 2/3* -4/3 -3/2 0 1 0 -7/2 -1/2 2 -1/2

-7/2 0 -1/3 1/4 1/2 -3/2

?B

?1 y 4
y1

3/2 7/2 7/2 0

x1

0 -11/4 -4/9

-y

y2 y4 y1

9/4 1/2 11/4 -31/4

3/2 0 -2 1 -1/2 0 -1/2

-X
T 注意, 因y ? C B B ?1 , A ? ( B,? I ), T C T ? (C B , O ) ? B ?1 A ? ( I ,? B ?1 ) ? T T ? T ? C B B ?1 A ? C T ? C B ( I ,? B ?1 ) ? C T T ? (O,?C B B ?1 ) ? (O,? w)

0 -1/4

由于检验数都小于等于0,所以对应的基可行解就是原问题 的最优解,最优值为31/4,对应的最优解为 x1=1/2,x2=0,x3=1/4。

作业

§ 4.7线性规划灵敏度分析
在实际问题中,规划模型中的大多数数 据是测量、统计、评估或决策而得出来的。 因此有必要分析当这些数据发生波动时会对 最优解和最优值产生什么影响。这就是灵敏 度分析。

一、价值系数 cj 的变化分析 一般市场条件一变, j 值就会发生变化, c 下面我们将分 析 cj 的变化会导致最优单纯形表怎样变化?
max z ? c ? x

设标准 LP 问题

? Ax ? b 的最优单纯形表为 s.t. ? ?x ? 0
xB
xN

xB
Z

B ?1b
- cB B b
T ?1

I O

B ?1 N
- cB B N ? cN
T T ?1

运筹学
xB
Z

xB

xN

线性规划

B ?1b
- cB B b
T ?1

I O

B ?1 N
- cB B N ? cN
T T ?1

从上表可看出 cj 的变化会只导致 ? N 和 z 的变化。若仍有 T T T T ? N ? cB B ?1 N ? cN ? 0, zmin ? cB B ?1b , x ? ( B ?1b, O)T ? 0 时,它还是最优单纯形 表. 当 c 改变为 c* ? c ? ?c 时
* T T T T T T T ? NT ? ?(cB ? ?cB ) B ?1N ? (cN ? ?cN ) ? ? N ? ( ??cB B ?1N ? ?cN ),

* 若 ? NT ? O, 则 x ? ( B ?1b, O)T ? 0 仍是最优解,最优值变为
T T T T zmin ? (cB ? ?cB ) B ?1b ? cB B ?1b ? ?cB B ?1b

否则把以 c*代入要按单纯形法断续迭代。

运筹学

线性规划

* 1. 如果只有一个非基变量的系数 ck ? ck ? ?ck ,则只有 ? k 变化为
* T * T * ? k ? cB Ak ? ck ? cB Ak ? ck ? (ck ? ck ) ? ? k ? ?ck

所以当 ? k* ? 0 ? ?ck ? ?? k 时,最优表还是最优表,否则把以 ck* 代入要按单纯形法断续迭代。
* 2. 如果只有一个基变量的系数 ck ? ck ? ?ck ,则只有 ? k 变化为
* T * T * ? k ? cB Ak ? ck ? cB Ak ? ck ? (ck ? ck ) ? ? k ? ?ck ? 0 ? ?ck ? ?ck

若基变量 xk 对应第 r 行, 需把第 r 行乘 ?ck 去减第 0 行得新单 纯形表。

运筹学
max Z ? 300 x1 ? 500 x2 ? x1 ? 4 ?2 x ? 12 ? 2 s.t. ? ?3x1 ? 2 x2 ? 18 ? x1 , x2 ? 0 ?

线性规划

例 16. 在例 1.1 中工厂生产门窗两种产品的最优计划问题归结为下列 线性规划

已知最优单纯形表如下

300
xB
x3

500

0

0

0

b’ 2 6 2

x1
0 0 1

x2
0 1 0 0

x3
1 0 0 0

x4
1/3 1/2 -1/3 -150

x5
-1/3 0 1/3 -100

?

x2 x1

-3600 0

(1)确定门的利润 c 由 300 元变为 500 元时,最大利润如何变化? 1 (2)若门窗的利润 c ,c 都发生了变化,最大利润如何变化?(求二种产品的价格 1 2 波动范围使原最优解保持最优)

运筹学

线性规划

解 : 设 c1 的 增 量 是 ?c1 ? 200 , 因 为 x1 是 基 变 量 , 只 有 ? 1 发 生 变 化
? 1* ? ?1 ? ?c1 ? 0 ? ?c1 ? ?c1 ,代入上表得

不是最优表,继续迭代, 得,最优解 X*=(2,6,2, x 3 0,0)保持不变。最优值 变为 4000。
x3

300
xB

500

0

0

0

b’ 2 6 2 -3600 2 6 2

x1
0 0 1 200 0 0 1

x2
0 1 0 0 0 1 0 0

x3
1 0 0 0 1 0 0 0

x4
1/3 1/2 -1/3 -150 1/3 1/2 -1/3 -250/3

x5
-1/3 0 1/3 -100 -1/3 0 1/3 -100/3

?

x2 x1

x2 x1

-4000 0

运筹学
设 c1 , c2 的增量为 ?c1 , ?c2 * T T T T T ? NT ? ? N ? ( ?cB B ?1N ? ?cN ) ? ? N ? ?cB B ?1N

线性规划

? 1 1 / 3 ?1 / 3 ? ?c ?c ?c ? (0, ?150, ?100) ? (0, ?c2 , ?c1 ) ? 0 1 / 2 0 ? ? (0, ?150 ? 2 ? 1 , ?100 ? 1 ? ? 2 3 3 ? 0 ?1 / 3 1 / 3 ? ? ?

若在单纯形表上做则是
300
xB
x3

500

0

0

0

b’ 2 6 2 -3600
-3600- 2 ?c1 - 6?c2

x1
0 0 1
?c1
0

x2
0 1 0
?c2
0

x3
1 0 0 0
0

x4
1/3 1/2 -1/3 -150
? 150 ? ?c1 ?c2 ? 3 2

x5
-1/3 0 1/3 -100
? 100 ? ?c1 3

?

x2 x1

所以 ? 150 ?

?c1 ?c2 ? ? 0, 3 2 ?c ? 100 ? 1 ? 0 3

时,最优生产方案不变,但最优值会发生变化。

注: ? 300 ? ?c1 ? 4500 是分别变化的解,即其中之一不变时的解。
? 300 ? ?c2

这些我们可用 Excel 规划求解帮我们做。

注:这里是分别市场上二种得到的结论,若考虑产品价格同时变化,则要求为
? ? 900 ? 2?c1 ? ?c2 , 若?c ? 150时, 则 ? 200 ? ?c , 若?c ? ?150时, 则 ? 600 ? ?c , ? 1 2 1 2 3 ? ?? 300 ? ?c1 ?

在用规划求解时,我们选择敏感性报告并保存得敏感性报告表如下

Microsoft Excel 11.0 敏感性报告 工作表 [例1.1.xls]Sheet1 报告的建立: 2011-9-28 10:10:53

可变单元格 单元格 名字 $B$4 可变单元格→ Max Z=∑cjxj $C$4 可变单元格→ 约束 单元格 名字 $D$7 a1j→ ∑aijxj $D$8 a2j→ ∑aijxj $D$9 a3j→ ∑aijxj 终 阴影 约束 允许的 允许的 值 价格 限制值 增量 减量 2 0 4 1E+30 2 12 150 12 6 6 18 100 18 6 6 终 递减 目标式 允许的 允许的 值 成本 系数 增量 减量 2 0 300 450 300 6 0 500 1E+30 300

价值系数cj的变 化的灵敏度分析

右端常数bi的变化 的灵敏度分析

即敏感性报告给出的是分别变化的灵敏度分析。

运用敏感性报告给出的产品价值同时变化的灵敏度分析
敏感性报告中给出的只是单个产品价值变化的灵敏度分析,对同时变化有 如下一种间单的分析方法:

百分之百法则——若目标函数系数同时变动,则当它们增 加(或减少)时相对其允许增量(或允许减量)的相对变 化率之和不超过百分之百(100%)时,最优解不变,则当 它们增加(或减少)相对其允许增量(或允许减量)的相 对变化率之和超过百分之百(100%)时,不能确定最优解 是否改变。 运用见P35
也可利用软件做交叉变化分析来取代.

运筹学 二、右端常数 bi 的灵敏度变化分析

线性规划

标准 LP 问题的最优单纯形表中还可看出,当右端常数向量 b 改变为 b* ? b ? ?b 时,只有表的最后一列会发生变化,故只需修改最 后一列即可。修改的方法如下: b * ? B ?1b* ? B ?1 (b ? ?b) ? b ? B ?1?b ,
* T T T T z0 ? cB b * ? cB B ?1b* ? cB B ?1 (b ? ?b) ? z0 ? cB B ?1?b
* T T 若 b * ? O ,则 x ? ( B ?1b* , O)T 是最优解,最优值为 z0 ? cB b * ? z0 ? cB B ?1?b , 否则用对偶单纯形法断续求解。 例:对于上例作下列分析: (3)车间 2 可用工时 b2 增加 1 小时,总利润如何变化,最优解是

否发生变化? (4)若同时改变三个车间的可用工时,总利润如何变化,最优解是 否发生变化? 解:总利润和最优解都与 b 有关都会发生变化,一般我们关心最优 基是否会变,即生产的品种是否会变。

运筹学
? 2 ? ? 1 1 / 3 ?1 / 3 ? ? 0 ? b * ? b ? B ?1?b ? ? 6 ? ? ? 0 1 / 2 0 ??1? ? ? ? ?? ? ? 2 ? ? 0 ?1 / 3 1 / 3 ? ? 0 ? ? ? ? ?? ? 设 b2 的增量是 ?b2 ? 1 , , ? 2? ? 1/ 3 ? ? 7 / 3 ? ? ? 6 ? ? ? 1 / 2 ? ? ? 13 / 2 ? ? 0 ? ? ? ? ? ? ? 2 ? ? ?1 / 3 ? ? 5 / 3 ? ? ? ? ? ? ?

线性规划

不是最优表, 继续迭代, 得, 最优解 X*=(5/3,13/2, 7/3,0,0)生产品种保持 不变。最优值变为
? 7/3 ? ? 0 500 300 ? ? 13 / 2 ? ? 3750 ? ? ? 5/3 ? ? ?

300
xB
x3

500

0

0

0

b’ 2 6 2

x1
0 0 1

x2
0 1 0 0

x3
1 0 0 0

x4
1/3 1/2 -1/3 -150

x5
-1/3 0 1/3 -100

?

x2 x1

-3600 200

总利润增加了 150 元。

运筹学
设 b1 , b2 , b3 的增量为 ?b1 , ?b2 , ?b3
? 2 ? ? 1 1 / 3 ?1 / 3 ? ? ?b1 ? b * ? b ? B ?1?b ? ? 6 ? ? ? 0 1 / 2 0 ? ? ?b2 ? ? ? ? ?? ? ? 2 ? ? 0 ?1 / 3 1 / 3 ? ? ?b ? ? ? ? ?? 3 ? ? 2 ? ? ?b1 ? ?b2 / 3 ? ?b3 / 3 ? ? 2 ? ?b1 ? ?b2 / 3 ? ?b3 / 3 ? ??? ? ? ? 6? ? ? ?b2 / 2 6 ? ?b2 / 2 ? ? ? ? ? ? ? 2 ? ? ??b / 3 ? ?b / 3 ? ? 2 ? ?b / 3 ? ?b / 3 ? 2 3 2 3 ? ? ? ? ? ? 若要解仍可行,则 b * ? 0 ,即

线性规划

2 ? ?b1 ? ?b2 / 3 ? ?b3 / 3 ? 0 6 ? ?b2 / 2 ? 0 2 ? ?b2 / 3 ? ?b3 / 3 ? 0

?2 ? ?b1 ? ?6 ? ?b2 ? 6 时解仍可行,对应方案仍是最优的 ?6 ? ?b3 ? 6

这些我们可用 Excel 规划求解帮我们做。 注:这里是分别考虑,三个车间可工时变化得到的结论,若若同时改变
?6 ? 3?b1 ? ?b2 ? ?b3 ? 0 ? 三个车间的可用工时,则为 ? ?b2 ? ?12 , ? ?b ? ? b ? 6 3 ? 2

如 ?b1 ? ?b2 ? 1, 则 ? 5 ? ?b3 , ? 10 . ?b1 ? ?b2 ? ?1, 则 ? 7 ? ?b3 , ? 2 .

运用敏感性报告给出的生产条件约束值同时变化的灵敏度分析 百分之百法则——若生产条件约束值同时变动,则当它们增 加(或减少)相对其允许增量或允许减量的相对变化率之和 不超过百分之百(100%)时,最优基不变,则当它们增加 (或减少)相对其允许增量或允许减量的相对变化率之和超 过百分之百(100%)时,不能确定最优基是否改变。 运用见P43
也可利用软件做交叉变化分析来取代.

三、技术系数矩阵A变化的灵敏度变化分析

若生产的工艺技术条件的变化,则系数aij就会随之变化, 即系数矩阵A就会随之变化。我们也可分析A的变化对最优 方案的影响。若增加一道生产工艺就要增加一个约束条件, 新增一个决策变量即是把原来忽略的一个因素考虑进去(或 者是增加新产品也相当于增加一个决策变量,系数矩阵也将 增加一列),又会如何?……这些都是属于灵敏度分析的内 容。 在目前计算机普及率很高的情况下,通常的方法是程序 中修改A后重新计算成即可。

作业:P50—52,1,3,5

运筹学 小结: 一般信息的变化: 价值向量—市场变化

线性规划

右端向量—资源变化
系数矩阵—技术进步 ?C的变化只影响检验数(对偶问题的解),不影响原问题 的基本解; ?b的变化只影响原问题的基本解,不影响检验数(对偶问 题的解);

?A中系数的变化可能既影响原问题的基本解,又影响对偶 问题的解。
?灵敏度分析时,要弄清楚:1)系数在什么范围内变化时, 最优解(基)不变;2)若系数的变化使最优解发生变化, ♂返回 如何最简便地求得新最优解。

例19 雅致家具厂生产计划优化问题
雅致家具厂生产4种小型家具,由于该四种家具具有不同的大小、形状、重量和风 格,所以它们所需要的主要原料(木材和玻璃)、制作时间、最大销售量与利润均 不相同。该厂每天可提供的木材、玻璃和工人劳动时间分别为600单位、1000单位 与400小时,详细的数据资料见下表。问: (1)应如何安排这四种家具的日产量,使得该厂的日利润最大? (2)家具厂是否愿意出10元的加班费,让某工人加班1小时? (3)如果可提供的工人劳动时间变为398小时,该厂的日利润有何变化? (4)该厂应优先考虑购买何种资源? (5)若因市场变化,第一种家具的单位利润从60元下降到55元,问该厂的生产计 划及日利润将如何变化?

表1 雅致家具厂基本数据
家 具 类 型 劳 动 时 间 (小时/件) 木 材(单 位/件) 玻 璃 (单位/件) 单位产品利 润(元/件) 最大销售量 (件)

1
2 3 4

2
1 3 2

4
2 1 2

6
2 1 2

60
20 40 30

100
200 50 100

可提供量

400小时

600单位

1000单位

解:依题意,设置四种家具的日产量分别为决策变量 x1,x2,x3,x4,目标要求是日利润最大化,约束条件为三 种资源的供应量限制和产品销售量限制。 据此,列出下面的线性规划模型:
MaxZ ? 60 x1 ? 20 x2 ? 40 x3 ? 30 x4 (木材约束) ① ?4 x1 ? 2 x2 ? x3 ? 2 x4 ? 600 ? ② ?6 x1 ? 2 x2 ? x3 ? 2 x4 ? 1000 (玻璃约束) ?2 x1 ? 1x2 ? 3 x3 ? 2 x4 ? 400 (劳动时间约束) ③ ? (家具1需求量约束) ? x ? 100 ④ s.t.? 1 (家具2需求量约束) ⑤ ? x2 ? 200 ? x3 ? 50 (家具3需求量约束) ⑥ ? (家具4需求量约束) ⑦ ? x4 ? 100 ? x , x , x , x ? 0 (非负约束) ⑧ ? 1 2 3 4

其中X1,X2,X3,X4分别为四种家具的日产量。

用Excel求解得对应的敏感性报告(灵敏度分)析如下表所示。
递减成本指目标函 数中决策变量的系 数必须改进多少才 能得到该决策变量 的正数解,改进对 最大值为增加,对 最小值为减少。 最优解
c

+ △c

-△c

实际使用量

对偶最 优解

b

+△

b

-△

b

根据模型运行结果可作出如下分析: (1)由模型的解可知,雅致家具厂四种家具的最优日产量分别为100件、80件、40 件和0件,这时该厂的日利润最大,为9200元。 本问题的敏感性报告如上页表所示。 由上述敏感性报告可进行灵敏度分析,并回答题目中的问题(2)一(5)。 (2)由敏感性报告可知,劳动时间的影子价格为12元,即在劳动时间的增量不超过25 小时的条件下,每增加l小时劳动时间,该厂的利润(目标值)将增加12元。 因此,付给某工人10元以增加l小时劳动时间是值得的,可多获利为: 12—10=2(元)。 (3)当可提供的劳动时间从400小时减少为398小时时,该减少量在允许的减量(100小 时)内,所以劳动时间的影子价格不变,仍为12元。 因此,该厂的利润变为: 9200+12X(398—400)=9 176(元)。 (4)由敏感性报告可见,劳动时间与木材这两种资源的使用量等于可提供量,所以它 们的约束条件为“紧”的,即无余量的;而玻璃的使用量为800,可提供量为1000, 所以玻璃的约束条件是“非紧”的,即有余量的。 因此,应优先考虑购买劳动时间与木材这两种资源。 (5)由敏感性报告可知,家具1的目标系数(即单位利润)允许的减量为20,即当家具1 的单位利润减少量不超过20元时,最优解不变。因此,若家具1的单位利润从60元下 降到55元,下降量为5元,该下降量在允许的减量范围内,这时,最优解不变。 因此,四种家具的最优日产量仍分别为100件、80件、40件和0件。 最优值变为: 9200+(55-60)X100=8 700(元)。

§ 4.8 线性规划应用实例
一、 资源分配问题
这类问题的特点是: 目标:总绩效最大(利润或收入或产量最大) 约束:实际使用的资源数量≦可用的资源数量 决策变量(方案):要能对总绩效和实际使用的资源数量进行 测度。 例20某商务房地产开发投资公司,在四个不同的投资时期三个项目所
需资金和公司可用资金如下表所示,问该公司应在每个项目上按多大比例 投资,才能使投资组合获得最大的总净现值.
各时期三项目所需资金和公司可用资金 年份 0 1 2 3 净现值 办工楼项目 40 100 190 200 45 宾馆项目 80 160 240 310 70 90 140 160 220 50 25 45 65 80 单位:百万 购物中心项目 可用资金

分析:这是一个可用资金分配问题,要求,实际使用的资金额≦可用的资金额 设x为公司在第j个项目上的投资比例,

可控因素:各项目投资比例设xj为公司在第j个项目上的投资比例,j=1,2,3 目标:总净现值最大.总净现值函数Z=45 x1+70 x2+50 x3

受制条件:各年实际使用的资金额≦各年可用的资金额.为了写约束,一般我们要通 过假设来对问题做一些必要的简化和说明. 假设1:各项目投资不分先后,净现值都相同. 假设2:忽略所获得利息,只考虑每一时点累计资金使用情况.
40 x1 ? 80 x 2 ? 90 x3 ? 25 100 x1 ? 160 x 2 ? 140 x3 ? 45 190 x1 ? 240 x 2 ? 160 x3 ? 65 200 x1 ? 310 x 2 ? 220 x3 ? 80

蕴含约束:各项目投资比例非负. xj ≥0,j=1,2,3,

模型

max Z ? 45 x1 ? 70 x 2 ? 50 x3 ?40 x1 ? 80 x 2 ? 90 x3 ? 25 ? ?100 x1 ? 160 x 2 ? 140 x3 ? 45 ? s.t.?190 x1 ? 240 x 2 ? 160 x3 ? 65 ?200 x ? 310 x ? 220 x ? 80 1 2 3 ? ? x j ? 0, j ? 1,2,3 ?

用Excel软件求解

二、成本收益平衡问题
这类问题的特点是: 目标:以最低成成本实现指定效益(完成或超额完成指定任务) 约束:实际实现的水平≧最低可接受水平 决策变量(方案):要能对总成本和实际实现的水平进行测度。
例21某航空公司正准备增加其中心机场的往来航班,因此需雇佣更多的服务 人员。分析研究新的航班时刻表,以确定一天中不同时段为实现客户满意水 平必需工作的服务人员数见下表,在三个项目,四个不同的投资时期所需资 某航空公司服务人员排班问题的有关数据 金如下表:
问题是:在保证每个时段所 6:00AM~8:00AM 需服务水平的前提下,求使得 8:00AM~10:00AM 人员总工资最少的排班方案。 10:00AM~中午 中午~2:00PM 即以最小成本提供令人满意 2:00PM~4:00PM 的服务。
4:00PM~6:00PM 6:00PM~8:00PM 8:00PM~10:00PM 10:00PM~午夜 午夜~6:00AM 每人每天工资(元) 170 160 175 180 时段 排班 1 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 195 排班 2 排班 3 排班 4 排班 5 最少需要人数 48 79 65 87 64 73 82 43 52 15

可控因素:不同班次的排班人数。设xj为第j班的排班人数,j=1,2,3,4,5 目标:人员总工资最少.人员总工资函数 min Z=170 x1+160 x2+175x3+180 x4+195x5 受制条件:各时段的在岗人数不得少于最少需要人数
时段1 x1 ? 48 : 时段2:x1 ? x 2 ? 79 时段3:x1 ? x 2 ? 65 时段4:x1 ? x 2 ? x3 ? 87 时段5:x 2 ? x3 ? 64 时段6:x3 ? x 4 ? 73 时段7:x3 ? x 4 ? 82 时段8:x 4 ? 43 时段9:x 4 ? x5 ? 52 时段10:x5 ? 15

模型
min Z ? 170 x1 ? 160 x2 ? 175 x3 ? 180 x4 ? 195 x5 ? x1 ? 48 ? ? x1 ? x2 ? 79 ? x1 ? x2 ? 65 ? ? x1 ? x2 ? x3 ? 87 ? x ? x ? 64 3 ? 2 ? s.t.? x3 ? x4 ? 73 ? x ? x ? 82 4 ? 3 ? x4 ? 43 ? x ? x ? 52 5 ? 4 ? x5 ? 15 ? ? x j ? 0, j ? 1,2,3 ?

蕴含约束:不同班次的排班人数非负. xj ≥0,j=1,2,3,

用Excel软件求解

三、 网络配送问题(运输问题,分配问题)
这类问题的特点是: 目标:以最低成成本或最大效益完成完成供给任务。 约束:实际实现的供给量=需求量 决策变量(方案):要能对总成本和实际实现的供给量进行测度。
例:

四、混合问题(配料问题)
这类问题的特点是: 目标:以最低成成本或最大效益完成完成生产任务。 约束:产品质量或产量达到要求或满足需求; 收益实际实现的水平≧最低可接受水平; 实际使用的资源数量≦可用的资源数量。 决策变量(方案):要能对总成本和实际效益进行测度。 这类问题是前三类问题的混合型,所以它的约束有三种类型

运筹学

线性规划

例 23 配料问题
? 某公司用A、B、C三种原料生产三种不同规格的 产品甲、乙、丙。相关数据见下表,问该公司应 如何安排生产,才能使总利润最大?

分析: 可控因素:产品甲、乙、丙的产量?它可描述目标总收说函数,但无法描述 成本,因为原料使用是一个配比要求用量不确定,不同的配方成本不同,配 方确定产量也随之确定,收入也可确定,所以应决策的是如何决定各产品的 原料配方,才能使总利润最大?所以设 x ij 为第i种产品中使用原料j的数量, 则

运筹学
产品 甲 乙 丙 各种原料用量 原料 A
x11

线性规划
B
x12 x 22
x32

C
x13 x 23 x33

各种产品产量

?x
j ?1 3

3

1j

x 21
x31

?x
j ?1 3

2j

?x
j ?1

2j

?x
i ?1

3

i1

?x
i ?1

3

i2

?x
i ?1

3

i3

目标:总利润z最大, z=收入-成本
max z ? 90 ? x1 j ? 85? x2 j ? 65? x3 j ? 60 ? xi1 ? 35? xi 2 ? 30 ? xi 3
j ?1 j ?1 j ?1 i ?1 i ?1 i ?1 3 3 3 3 3 3

受制条件:资源约束
资源A: xi1 ? 200 ?
i ?1 3 3

产品质量约束
产品甲:x11 ? 50% ? x1 j ; x12 ? 35% ? x1 j ;
j ?1 3 j ?1 3 3 3

资源B: xi 2 ? 150 ?
i ?1 3

产品乙:x21 ? 40% ? x2 j ; x22 ? 45% ? x2 j ;
j ?1 3 j ?1 3

资源C: xi 3 ? 100 ?
i ?1

产品丙:x31 ? 30% ? x3 j ; x32 ? 50% ? x3 j ; x33 ? 20% ? x3 j
j ?1 j ?1 j ?1

3

蕴含约束:各产品中使用原料的数量非负.xi j≥0,i,j=1,2,3, 于是化简得该问题优化模型为
max z ? 30 x11 ? 55 x12 ? 60 x13 ? 25 x21 ? 50 x 22 ? 55 x 23 ? 5 x31 ? 30 x32 ? 35 x33 ? x11 ? x 21 ? x31 ? 200 ? ? x12 ? x 22 ? x32 ? 150 ? x13 ? x 23 ? x33 ? 100 ? ?0.5 x11 ? 0.5 x12 ? 0.5 x13 ? 0 ?0.35 x ? 0.65 x ? 0.35 x ? 0 11 12 13 ? ? s.t.?0.6 x 21 ? 0.4 x 22 ? 0.4 x 23 ? 0 ?0.45 x ? 0.55 x ? 0.45 x ? 0 21 22 23 ? ?0.7 x31 ? 0.3x32 ? 0.3x33 ? 0 ?0.5 x ? 0.5 x ? 0.5 x ? 0 31 32 33 ? ?0.2 x31 ? 0.2 x32 ? 0.8 x33 ? 0 ? ? xij ? 0, i, j, ? 1,2,3 ?

用Excel软件求解

例24 产品配套问题
某产品由两个零件I和三个零件II组成,每个零件均可由三个车间各 自生产,但各车间的生产效率和总工时限制各不相同,见下表,试确定各 车间生产每种零件的工作时间,使生产产品的件数最多。

生产效率(件/小时) 车 1 2 3 间 总 工 时 100 50 75 零件 I 8 10 16 零件 II 6 15 21

生产工时数 零件 I 零件 II

x11 x 21 x 31

x12 x 22 x 32

设xij表示第i个车间生产第j个零件的时间
则: 生产出两种零件的数量分别是
8x11 ? 10x 21 ? 16x31 , 6x12 ? 15x 22 ? 21x32
? ? ? ? 8 x11 ? 10x 21 ? 16x 31 6 x12 ? 15x 22 ? 21x 32 ? , 组装成的产品数为 z= min? 2 3 ? ?

注意——Z是非线性表达式!

处 理

① 引入一个新变量 , Y 令 Y=
? 8 x11 ? 10 x21 ? 16 x31 6 x12 ? 15 x22 ? 21x32 ? min? , ? 2 3 ?

? ? ?

则目标要求可以写成: Max Z = Y

② 把Y 的表达式改写成两个不等式增添到约束条件中去
8X11 ? 10X 21 ? 16X 31 Y? , 2 6 X12 ? 15X 22 ? 21X 32 Y? ; 3

于是得到该问题的LP模型为:
Max Z=Y

? x ? x ? 100 ? x11 ? x21 ? 50 ? 21 22 ? x ? x ? 75 ? 32 s.t.? 31 ?8 x11 ? 10 x21 ? 16 x31 ? 2 y ?6 x ? 15 x ? 21x ? 3 y 22 32 ? 12 ? x11, x12, x 21, x 22, x31, x32, y ? 0 ?

用数学软件求得 X11=50,x21=50,x31=75 ,x12=0其余为 0,maxy=1050即生产产 品的件数最多1050件.

LINGO快速入门
LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一 种建立最优化模型的语言,可以简便地表达大规模问题,利用LINGO高 效的求解器可快速求解并分析结果。 当你在windows下开始运行LINGO系统时,会得到类似下面的一个窗口:

外层是主框架窗口,包含了所有菜单命令和工具条,其它所有的窗口 将被包含在主窗口之下。在主窗口内的标题为LINGO Model – LINGO1的窗口是LINGO的默认模型窗口,建立的模型都都要在该窗 口内编码实现。

数学函数 LINGO提供了大量的标准数学函数: @abs(x) 返回x的绝对值 @sin(x) 返回x的正弦值,x采用弧度制 @cos(x) 返回x的余弦值 @tan(x) 返回x的正切值 @exp(x) 返回常数e的x次方 @log(x) 返回x的自然对数 @lgm(x) 返回x的gamma函数的自然对数 @sign(x) 如果x<0返回-1;否则,返回1 @floor(x) 返回x的整数部分。当x>=0时,返回不超过x的最大整数;当 x<0时,返回不低于x的最大整数。 @smax(x1,x2,…,xn) 返回x1,x2,…,xn中的最大值 @smin(x1,x2,…,xn) 返回x1,x2,…,xn中的最小值 变量界定函数 变量界定函数实现对变量取值范围的附加限制,共4种: @bin(x) 限制x为0或1 @bnd(L,x,U) 限制L≤x≤U @free(x) 取消对变量x的默认下界为0的限制,即x可以取任意实数 @gin(x) 限制x为整数 在默认情况下,LINGO规定变量是非负的,也就是说下界为0,上界为+∞。 @free取消了默认的下界为0的限制,使变量也可以取负值。@bnd用于设定一 个变量的上下界,它也可以取消默认下界为0的约束。

集循环函数 集循环函数遍历整个集进行操作。其语法为 @function(setname[(set_index_list)[|conditional_qualifier]]: expression_list); @function相应于下面罗列的四个集循环函数之一;setname是要遍历的集; set_ index_list是集索引列表;conditional_qualifier是用来限制集循环函数的范围, 当集循环函数遍历集的每个成员时,LINGO都要对conditional_qualifier进行评价, 若结果为真,则对该成员执行@function操作,否则跳过,继续执行下一次循环。 expression_list是被应用到每个集成员的表达式列表,当用的是@for函数时, expression_list可以包含多个表达式,其间用逗号隔开。这些表达式将被作为约 束加到模型中。当使用其余的三个集循环函数时,expression_list只能有一个表 达式。如果省略set_index_list,那么在expression_list中引用的所有属性的类型 都是setname集。 1.@for 该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束, 不过@for函数允许只输入一个约束,然后LINGO自动产生每个集成员的约束。 2.@sum 该函数返回遍历指定的集成员的一个表达式的和。 3.@min和@max 返回指定的集成员的一个表达式的最小值或最大值。

LINGO WINDOWS命令
一、文件菜单(File Menu) 1. 新建(New) 2. 打开(Open) 3. 保存(Save) 4. 另存为...(Save As...) 5. 关闭(Close) 6. 打印(Print) 7. 打印设置(Print Setup...) 8. 打印预览(Print Preview) 9. 输出到日志文件(Log Output...) 该命令用于生成一个日志文件,它存储接下来在“命令窗口”中输入的所有命令。 10.提交LINGO命令脚本文件(Take Commands...) 该命令可以将LINGO命令脚本(command script)文件提交给系统进程来运行。 11.引入LINGO文件(Import Lingo File...) 该命令可以打开一个LINGO格式模型的文件,然后LINGO系统会尽可能把模型 转化为LINGO语法允许的程序。 12.退出(Exit)

二、编辑菜单(Edit Menu)
1. 恢复(Undo) 2. 剪切(Cut) 3. 复制(Copy) 4. 粘贴(Paste) 5. 粘贴特定..(Paste Special。。) 与上面的命令不同,它可以用于剪贴板中的内容不是文本的情形。 6. 全选(Select All) 7. 匹配小括号(Match Parenthesis) 从编辑菜单中选用“Match Parenthesis”命令、单击“Match Parenthesis”按钮或 按Ctrl+P组合键可以为当前选中的开括号查找匹配的闭括号。 8. 粘贴函数(Paste Function) 从编辑菜单中选用“Paste Function”命令可以将LINGO的内部函数粘贴到当前插入 点。

三、 LINGO菜单
1. 求解模型(Slove) 从LINGO菜单中选用“求解”命令、单击“Slove”按钮或按Ctrl+S组合键可以将 当前模型送入内存求解。 2. 求解结果...(Solution...) 从LINGO菜单中选用“Solution...”命令、单击“Solution...”按钮或直 接按Ctrl+O组合键可以打开求解结果的对话框。这里可以指定查看当前内存中求解 结果的那些内容。

3. 查看...(Look...) 从LINGO菜单中选用“Look...”命令或直接按Ctrl+L组合键可以查看全部的或 选中的模型文本内容。 4. 灵敏性分析(Range,Ctrl+R) 用该命令产生当前模型的灵敏性分析报告。灵敏性分析是在求解模型时作出的,因 此在求解模型时灵敏性分析是激活状态,但是默认是不激活的。为了激活灵敏 性分析,运行LINGO|Options…,选择General Solver Tab, 在Dual Computations列表框中,选择Prices and Ranges选项。灵敏性分析耗费相当 多的求解时间,因此当速度很关键时,就没有必要激活它。 5. 模型通常形式...(Generate...) 用该命令可以创建当前模型的代数形式、LINGO模型或MPS格式文本。 6.调试(Debug) 用该命令可以分析Lp无解或无界的原因。 7.解答(Solution) 用该命令可以选择求解结果中输出非零变量。 8.模型图示(Picture) 用该命令可以按图形或文本方式显示模型中的非零系数。 9.选项(Options) 用该命令可以打开一个含7个选项的窗口。 (1)界面(Interface)选项卡 主要控制界面、输出方式、文件格式等。 (2)通用求解程序(General Solver)选项卡 主要控制求解程序的一些通用参数。

(3)Linear Solver(线性求解器)选项卡 主要控制LP求解程序的一些参数。
选项组 选项 含义
求解时的算法,有四种可能的设置: 1.· Solver Decides:LINGO自动选择算法 2.(缺省设置) 3.· Primal Simplex:原始单纯形法 4.· Dual Simplex:对偶单纯形法 5.· Barrier: 障碍法 (即内点法) 控制线性模型中约束满足的初始误差限(缺省值为3*10-6) 控制线性模型中约束满足的最后误差限(缺省值为10-7)

Method 求解方法

Initial Linear Feasibility Tol 初始线性可行性误差限 Final Linear Feasibility Tol. 最 后线性可行性误差限 Model Reduction 模型降维

控制是否检查模型中的无关变量,从而降低模型的规模: · Off:不检查 · On:检查 · Solver Decides:LINGO自动决定(缺省设置)
有三种可能的设置: · Solver Decides:LINGO自动决定(缺省设置) · Partial:LINGO 对一部分可能的出基变量进行尝试 · Devex:用Steepest-Edge(最陡边)近似算法对所有可能 的变量进行尝试,找到使目标值下降最多的出基变量 有三种可能的设置: · Solver Decides:LINGO自动决定(缺省设置) · Dantzig:按最大下降比例法确定出基变量 · Steepest-Edge:最陡边策略,对所有可能的变量进行尝 试,找到使目标值下降最多的出基变量 选择该选项,LINGO将尝试将一个大模型分解为几个小模型 求解;否则不尝试 选择该选项,LINGO检查模型中的数据是否平衡(数量级是 否相差太大)并尝试改变尺度使模型平衡;否则不尝试

Primal Solver 原始单纯形法 Pricing Strategies 价格策略(决定 出基变量的策略 )

Dual Solver对 偶单纯形法

Matrix Decomposition 矩阵分解 Scale Model 模型尺度的改变

(4)Nonlinear Solver(非线性求解器)选项卡
选项组 选项 含义 控制模型中约束满足的初始误差限(缺省值为10-3)

Initial Nonlinear Feasibility Tol. 初始非线 性可行性误差限 Final Nonlinear Feasibility Tol. 最后非线性 可行性误差限 Nonlinear Optimality Tol. 非线性规划的最优性误差限 Slow Progress Iteration Limit缓慢改进的迭代 次数的上限

控制模型中约束满足的最后误差限(缺省值为10-6) 当目标函数在当前解的梯度小于等于这个值以后,停止迭代(缺省值为2*10-7) 当目标函数在连续这么多次迭代没有显著改进以后,停止迭代(缺省值为5)

Derivatives 导数

Numerical 数值法
Analytical 解析法 Crash Initial Solution 生成初始解 Quadratic Recognition 识别二次规划

用有限差分法计算数值导数(缺省值) 用解析法计算导数(仅对只含有算术运算符的函数使用)

选择该选项, LINGO将用启发式方法生成初始解;否则不生成(缺省值)

选择该选项, LINGO将判别模型是否为二次规划,若是则采用二次规划算法 (包含在线性规划的内点法中);否则不判别(缺省值)

Strategies 策略

Selective Constraint Eval 有选择地检查约束 SLP Directions SLP方向 Steepest Edge 最陡边策略

选择该选项, LINGO在每次迭代时只检查必须检查的约束(如果有些约束函数 在某些区域没有定义,这样做会出现错误);否则,检查所有约束(缺省值)

选择该选项, LINGO在每次迭代时用SLP (Successive LP,逐次线性规划)方法 寻找搜索方向(缺省值) 选择该选项, LINGO在每次迭代时将对所有可能的变量进行尝试,找到使目标 值下降最多的变量进行迭代;缺省值为不使用最陡边策略

(5)Integer Pre-Solver(整数预处理求解器)选项卡
选项组 选项 含义

Heuristics 启发式方法

Level

控制采用启发式搜索的次数(缺省值为3,可能的值为0-100). 启发式方法的目的是从 分枝节点的连续解出发,搜索一个好的整数解。 每个分枝节点使用启发式搜索的最小时间(秒)

Min Seconds

Probing Level 探测水平(级别)

控制采用探测(Probing)技术的级别(探测能够用于混合整数线性规划模型,收紧变量 的上下界和约束的右端项的值)。可能的取值为: 1.· Solver Decides:LINGO自动决定(缺省设置) · 1-7:探测级别逐步升高。

Application 应用节点

控制在分枝定界树中,哪些节点需要增加割(平面),可能的取值为: · Root Only:仅根节点增加割(平面) · Nodes:所有节点均增加割(平面) All · Solver Decides:LINGO自动决定(缺省设置)

Constraint Cuts 约束的割(平面)

Relative Limit 相对上限

控制生成的割(平面)的个数相对于原问题的约束个数的上限(比值),缺省值为0.75

Max Passes 最大迭代检查的次数

为了寻找合适的割,最大迭代检查的次数。有两个参数: · Root:对根节点的次数(缺省值为200) · Tree:对其他节点的次数(缺省值为2)

Types 类型

控制生成的割(平面)的策略,共有12种策略可供选择。 (如想了解细节,请参阅整数 规划方面的专著)

(6)Integer Solver(整数求解器)选项卡 整数预处理程序只用于整数线性规划模型(ILP模型),对连续规划和非 线性模型无效。
选项组 Direction Priority Absolute 绝对误差限 Relative 相对误差限 选项 含义 控制分枝策略中优先对变量取整的方向,有三种选择: 1.· Both:LINGO自动决定(缺省设置) ;2.· Up:向上取整优先 3.· Down:向下取整优先 控制分枝策略中优先对哪些变量进行分枝,有两种选择: 1.· LINGO Decides:LINGO自动决定(缺省设置);2.· Binary:二进制(0-1)变量优先 当变量与整数的绝对误差小于这个值时,该变量被认为是整数。缺省值为10-6 当变量与整数的相对误差小于这个值时,该变量被认为是整数。缺省值为8*10-6 当以前面的求解结果为基础,热启动求解程序时采用的算法,有四种可能的设置: · LINGO Decides:LINGO自动选择算法(缺省设置) · Primal Simplex:原始单纯形法 · Dual Simplex:对偶单纯形法 · Barrier: 障碍法 (即内点法) 当不以前面的求解结果为基础,冷启动求解程序时采用的算法,有四种可能的设置:(同上) 当当前目标函数值与最优值的绝对误差小于这个值时,当前解被认为是最优解(也就是说:只需 要搜索比当前解至少改进这么多个单位的解)。缺省值为8*10-8 当当前目标函数值与最优值的相对误差小于这个值时,当前解被认为是最优解(也就是说:只需 要搜索比当前解至少改进这么多百分比的解)。缺省值为5*10-8 在程序开始运行后这么多秒内,不采用相对误差限策略;此后才使用相对误差限策略。缺省值为 100秒。 同上一章LINDO部分的介绍 控制如何选择节点的分枝求解,有以下选项: · LINGO Decides: LINGO自动选择(缺省设置) ;· Depth First:按深度优先 ; · Worst Bound:选择具有最坏界的节点 ;· Best Bound:选择具有最好的界的节点 控制采用强分枝的层数。也就是说,对前这么多层的分枝,采用强分枝策略。所谓强分枝,就是 在一个节点对多个变量分别尝试进行预分枝,找出其中最好的解(变量)进行实际分枝。

Branching 分枝

Integrali ty 整性

LP Solver LP求解程 序

Warm Start 热启动

Cold Start

冷启动

Absolute 目标函数的绝对误差限 Optimalit y 最优性 Relative 目标函数的相对误差限 Time To Relative 开始采 用相对误差限的时间(秒) Hurdle 篱笆值 Tolerance s 误差限 Node Selection 节点选择 Strong Branch 强分枝的层数

(7)Global Solver(全局最优求解器)选项卡
选项组 选项 Use Global Solver 使用全局最优求解 程序 含义 选择该选项,LINGO将用全局最优求解程序求解模型,尽可能得到全局最优解(求解花费的时间可 能很长);否则不使用全局最优求解程序,通常只得到局部最优解 有两个域可以控制变量上界(按绝对值): 1.1、 Value:设定变量的上界,缺省值为1010; 2.2、 Application列表框设置这个界的三种 3.应用范围: · None: 所有变量都不使用这个上界; · All: 所有变量都使用这个上界; · Selected:先找到第1个局部最优解,然后对满足这个上界的变量使用这个上界(缺省设置) 有两个域可以控制变量上界(按绝对值): 1、 Optimality:只搜索比当前解至少改进这么多个单位的解(缺省值为10-6); 2、 Delta:全局最优求解程序在凸化过程中增加的约束的误差限(缺省值为10-7)。 可以控制全局最优求解程序的三类策略: 1、Branching:第1次对变量分枝时使用的分枝策略: · Absolute Width(绝对宽度) · Local Width(局部宽度) · Global Width(全局宽度) · Global Distance(全局距离) · (Absolute) Violation(绝对冲突) Abs · (Relative) Violation(相对冲突,缺省设置) Rel 2、Box Selection: 选择活跃分枝节点的方法: · Depth First(深度优先) · Worst Bound(具有最坏界的分枝优先,缺省设置) 3、Reformulation:模型重整的级别: · None(不进行重整) · Low(低) · Medium(中) · High(高,缺省设置) 尝试多少个初始点求解,有以下几种可能的设置: · Solver Decides:由LINGO决定(缺省设置,对小规模NLP问题为5次,对大规模问题不使用多点求 解) · Off:不使用多点求解 · N(>1的正整数):N点求解 · Barrier: 障碍法 (即内点法)

Variable Upper Bound 变量上界

Tolerances 误差限 Global Solver 全局最优求解 程序

Strategies 策略

Multistart Solver 多初始点求解 程序

Attempts 尝试次数

四、 窗口菜单(Windows Menu) 1. 命令行窗口(Open Command Window) 该命令可以打开LINGO的命令行窗口。在命令行窗口中可以获得命令 行界面,在“:”提示符后可以输入LINGO的命令行命令。 2. 状态窗口(Status Window) 该命令可以打开LINGO的求解状态窗口。 如果在编译期间没有表达错误,那么LINGO将调用适当的求解器来求解 模型。当求解器开始运行时,它就会显示如下的求解器状态窗口 (LINGO Solver Status)。

求解器状态窗口对于监视求解器的进展和模型大小是有用的。其中 中断求解器按钮(Interrupt Solver):点击则LINGO在下一次迭代时停止求解。 关闭按钮(Close):点击则关闭求解器状态窗口,但可在任何时间通过选择 Windows|Status Window再重新打开。 更新时间间隔(Update Interval)的域:LINGO将根据该域指示的时间(以秒 为单位)为周期更新求解器状态窗口。可以随意设置该域,不过若设置为0将导 致更长的求解时间——LINGO花费在更新的时间会超过求解模型的时间。 变量框(Variables):Total显示当前模型的全部变量数,Nonlinear显示其中 的非线性变量数,Integers显示其中的整数变量数。 约束(Constraints)框:Total显示当前模型扩展后的全部有效约束数, Nonlinear显示其中的有效非线性约束数。非线性约束是该约束中至少有一个非 线性变量。 非零(Nonzeroes)框:Total显示当前模型中全部非零系数的数目,Nonlinear 显示其中的非线性变量系数的数目。 内存使用(Generator Memory Used,单位:K)框:显示当前模型在内存中使 用的内存量。可以通过使用LINGO|Options命令修改模型的最大内存使用量。 已运行时间(Elapsed Runtime)框: 显示求解模型到目前所用的时间,它可能受到系统中别的应用程序的影响。 求解器状态(Solver Status)框:显示当前模型求解器的运行状态。 扩展求解器状态(Extended Solver Status)框:显示LINGO中几个特殊求解 器的运行状态。包括分枝定界求解器(Branch-and- Bound Solver)、全局求解 器(Global Solver)和多初始点求解器(Multistart Solver)。该框中的域仅当 这些求解器运行时才会更新。

这里详细说明SET指令。凡是用户能够控制的LINGO系统参数,SET命令都能够 对它进行设置。SET命令的使用格式为: SET parameter_name | parameter_index [ parameter_value ], 其中parameter_name是参数名,parameter_index是参数索引(编号), parameter _value是参数值。当不写出参数值时,则SET命令的功能是显示该参 数当前的值。此外,“setdefault”命令用于将所有参数恢复为系统的默认值(缺 省值)。这些设置如果不用“freeze”命令保存到配置文件lingo.cnf中,则退出 LINGO系统后这些设置就无效了。
索引 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 参数名 ILFTOL FLFTOL INFTOL FNFTOL RELINT NOPTOL ITRSLW DERCMP ITRLTM TIMLIM OBJCTS MXMEMB CUTAPP ABSINT HEURIS HURDLE IPTOLA IPTOLR TIM2RL NODESL 缺省值 0.3e-5 0.1e-6 0.1e-2 0.1e-5 0.8e-5 0.2e-6 5 0 0 0 1 32 2 .000001 3 none .8e-7 .5e-7 100 0 初始线性可行误差限 最终线性可行误差限 初始非线性可行误差限 最终非线性可行误差限 相对整性误差限 非线性规划(NLP)的最优性误差限 缓慢改进的迭代次数的上限 导数 (0:数值导数, 1:解析导数) 迭代次数上限 (0:无限制) 求解时间的上限(秒) (0:无限制) 是否采用目标割平面法 (1:是, 0:否) 模型生成器的内存上限(兆字节)(对某些机器,可能无意义) 割平面法的应用范围(0:根节点, 1:所有节点, 2:LINGO 自动决定) 整性绝对误差限 整数规划(IP)启发式求解次数 (0:无, 可设定为 0~100) 整数规划(IP)的“篱笆”值(none:无, 可设定为任意实数值) 整数规划(IP)的绝对最优性误差限 整数规划(IP)的相对最优性误差限 采用 IPTOLR 作为判断标准之前,程序必须求解的时间(秒) 分枝节点的选择策略(0: LINGO 自动选择;1:深度优先;2: 最坏 界的节点优先;3: 最好界的节点优先) 简要说明

索引 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

参数名 LENPAG LINLEN TERSEO STAWIN SPLASH OROUTE WNLINE WNTRIM STABAR FILFMT TOOLBR CHKDUP ECHOIN ERRDLG USEPNM NSTEEP NCRASH NSLPDR SELCON PRBLVL SOLVEL REDUCE SCALEM PRIMPR DUALPR DUALCO RCMPSN MREGEN BRANDR BRANPR

缺省值 0 76 0 1 1 0 800 400 1 1 1 0 0 1 0 0 0 1 0 0 0 2 1 0 0 1 0 1 0 0

简要说明 终端的页长限制 (0:没有限制;可设定任意非负整数) 终端的行宽限制(0:没有限制;可设定为 64-200) 输出级别 (0:详细型, 1:简洁型) 是否显示状态窗口 (1:是, 0:否, Windows 系统才能使用) 弹出版本和版权信息 (1:是, 0:否, Windows 系统才能使用) 将输出定向到命令窗口 (1:是, 0:否, Windows 系统才能使用) 命令窗口的最大显示行数(Windows 系统才能使用) 每次从命令窗口滚动删除的最小行数 (Windows 系统才能使用) 显示状态栏(1:是, 0:否, Windows 系统才能使用) 文件格式(0:lng 格式, 1:lg4 格式, Windows 系统才能使用) 显示工具栏(1:是, 0:否, Windows 系统才能使用) 检查数据与模型中变量是否重名 (1:是, 0:否) 脚本命令反馈到命令窗口(1:是, 0:否) 错误信息以对话框显示 (1:是, 0:否, Windows 系统才能使用) 允许无限制地使用基本集合的成员名(1:是, 0:否) 在非线性求解程序中使用最陡边策略选择变量(1:是, 0:否) 在非线性求解程序中使用启发式方法生成初始解(1:是, 0:否) 在非线性求解程序中用 SLP 法寻找搜索方向 (1:是, 0:否) 在非线性求解程序中有选择地检查约束(1:是, 0:否) 对混合整数线性规划(MILP)模型,采用探测(Probing)技术的级别(0:LINGO 自动决 定;1:无;2-7:探测级别逐步升高) 线性求解程序(0: LINGO 自动选择, 1: 原始单纯形法, 2: 对偶单纯形法, 3: 障碍法 (即内点法)) 模型降维(2:LINGO 决定, 1:是, 0:否) 变换模型中的数据的尺度 (1:是, 0:否) 原始单纯形法决定出基变量的策略(0: LINGO 自动决定, 1: 对部分出基变量尝试, 2: 用最陡边法对所有变量进行尝试) 对偶单纯形法决定出基变量的策略(0: LINGO 自动决定, 1:按最大下降比例法确定, 2: 用最陡边法对所有变量进行尝试) 指定对偶计算的级别 (0: 不计算任何对偶信息;1:计算对偶价格;2:计算对偶价格 并分析敏感性) Use RC format names for MPS I/O (1:yes, 0:no) 重新生成模型的频率(0:当模型的文本修改后;1:当模型的文本修改或模型含有外部 引用时;3:每当有需要时) 分枝时对变量取整的优先方向(0:LINGO 自动决定;1:向上取整优先;2:向下取整优先) 分枝时变量的优先级 (0:LINGO 自动决定, 1:二进制(0-1)变量)

索引 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

参数名 CUTOFF STRONG REOPTB REOPTX MAXCTP RCTLIM GUBCTS FLWCTS LFTCTS PLOCTS DISCTS KNPCTS LATCTS GOMCTS COFCTS GCDCTS SCLRLM SCLRDL PRNCLR MULTIS USEQPR GLOBAL LNRISE LNBIGM LNDLTA BASCTS MAXCTR HUMNTM DECOMP GLBOPT GLBDLT GLBVBD GLBUBD GLBBRN GLBBXS GLBREF

缺省值 .1e-8 10 0 0 200 .75 1 1 1 1 1 1 1 1 1 1 1000 0 1 0 0 0 0 100,000 .1e-5 0 2 0 0 .1e-5 .1e-6 .1e+11 2 5 1 3 解的截断误差限 指定强分枝的层次级别

简要说明

IP 热启动时的 LP 算法 (0: LINGO 自动选择;1:障碍法 (即内点法);2:原始单纯形法;3: 对偶单纯形法) IP 冷启动时的 LP 算法(选项同上) 分枝中根节点增加割平面时,最大迭代检查的次数 割(平面)的个数相对于原问题的约束个数的上限(比值) 是否使用广义上界(GUB)割 (1:是, 0:否) 是否使用流(Flow)割 (1:是, 0:否) 是否使用 Lift 割 (1:是, 0:否) 是否使用选址问题的割 (1:是, 0:否) 是否使用分解割 (1:是, 0:否) 是否使用背包覆盖割 (1:是, 0:否) 是否使用格(Lattice)割 (1:是, 0:否) 是否使用 Gomory 割(1:是, 0:否) 是否使用系数归约割 (1:是, 0:否) 是否使用最大公因子割 (1:是, 0:否) 语法配色的最大行数 (仅 Windows 系统使用) 语法配色的延时(秒) (仅 Windows 系统使用) 括号匹配配色 (1:是, 0:否, 仅 Windows 系统使用) NLP 多点求解的次数 (0:无, 可设为任意非负整数) 是否识别二次规划 (1:是, 0:否) 是否对 NLP 采用全局最优求解程序 (1:是, 0:否) 线性化级别 (0:LINGO 自动决定, 1:无, 2:低, 3:高) 线性化的大 M 系数 线性化的 Delta 误差系数 是否使用基本(Basis) 割 (1:是, 0:否) 分枝中非根节点增加割平面时,最大迭代检查的次数 分枝中每个节点使用启发式搜索的最小时间(秒) 是否使用矩阵分解技术 (1:是, 0:否) 全局最优求解程序的最优性误差限 全局最优求解程序在凸化过程中增加的约束的误差限 全局最优求解程序中变量的上界 全局最优求解程序中变量的上界的应用范围(0: 所有变量都不使用上界; 1: 所有变量都使用上界; 2:部分使用) 全局最优求解程序中第 1 次对变量分枝时使用的分枝策略(0:绝对宽度;1:局部宽度;2:全局宽度;3:全局距 离;4:绝对冲突;5:相对冲突) 全局最优求解程序选择活跃分枝节点的方法(0:深度优先;1:具有最坏界的分枝优先) 全局最优求解程序中模型重整的级别: (0:不进行重整;1:低;2:中;3:高)

五、 帮助菜单(Help Menu)
1. 帮助主题(Help Menu) 从帮助菜单中选用“Help Menu”可以打开LINGO的帮助文件。 2. 关于LINGO(About Lingo) 关于当前LINGO的版本信息等。

例1.1 如何在LINGO中求解如下的LP问题:
min z ? 2 x1 ? 3x 2 ? x1 ? x 2 ? 350 ? x ? 100 ? 1 s.t.? ?2 x1 ? x 2 ? 600 ? x1 , x 2 ? 0 ?

在模型窗口中输入如下代码: model: min=2*x1+3*x2; x1+x2>=350; x1>=100; 然后点击工具条上的按钮 2*x1+x2<=600; end

即可运行

x4=0; y1=-4 x5=150; y2-=0 x6=0; y3=1

c

+ △c

-△c

价值系数C的变化 分析

右端常数b的 变化分析

b

+ △b

-△c

例1.2 使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位 运价如下表:

使用LINGO软件,编制程序如下: model: !6发点8收点运输问题; sets: warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets !目标函数; min=@sum(links: cost*volume); !需求约束; @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); !产量约束; @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); !这里是数据; data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; enddata end

然后点击工具条上的按钮

即可。


第4章 最优化方法(运筹学)_图文.ppt

第4章 最优化方法(运筹学)_物理_自然科学_专业资料。管理定量分析 第四章 最优化方法(运筹学) 第一节 线性(Linear Programing )规划 ? 第二节 运输问题和...

运筹学与最优化方法_图文.ppt

运筹学与最优化方法 - 运筹学 与最优化方法 吴祈宗等编制 ? 第一章 主要内容

新编文档-第4章最优化方法运筹学-精品文档_图文.ppt

新编文档-第4章最优化方法运筹学-精品文档 - 第四章 最优化方法(运筹学) 第

运筹学与最优化方法-第2章_图文.ppt

运筹学与最优化方法-第2章 - 第 2 章 基本概念 和 理论基础 第2章 基本

运筹学与最优化方法-第1章_图文.ppt

运筹学与最优化方法-第1章 - 运筹学 与最优化方法 吴祈宗 侯福均 编著 ?

运筹学最优化理论与方法第一章_图文.ppt

运筹学最优化理论与方法第一章 - ? 第一章 主要内容 运筹学思想与运筹学建模 ? 第二章 基本概念和理论基础 ? 第三章 线性规划 ? 第四章 最优化搜索算法的...

第3章运筹学与最优化方法课件_图文.ppt

第3章运筹学与最优化方法课件 - 第 三 章 线性规划 3.1 线性规划模型 例

运筹学与最优化方法第二章_图文.ppt

运筹学与最优化方法第二章 - 第 二 章 基本概念 和 基本理论 第二章 基本概

第9章运筹学与最优化方法课件_图文.ppt

第9章运筹学与最优化方法课件 - 第九章 层次分析 The Analytic H

第一章 运筹学思想与运筹学建模(运筹学与最优化方法-吴....ppt

运筹学 与最优化方法吴祈宗等编制 ? 第一章 主要内容 运筹学思想与运筹学建模 ? 第二章 基本概念和理论基础 ? 第三章 线性规划 ? 第四章 最优化搜索算法的...

运筹学-约束最优化方法_图文.pdf

运筹学-约束最优化方法 - 第五章 约束最优化方法 ? 最优性条件 ? 惩罚函数

第4章 最优化方法(运筹学)_图文.ppt

第4章 最优化方法(运筹学)_教育学_高等教育_教育专区。第4章 最优化方法(运筹学) 第四章 最优化方法(运筹学) 第一节 线性(Linear Programing )规划 ? 第...

运筹学与最优化方法第3章_图文.ppt

运筹学与最优化方法第3章 - 第 三章 有约束非线性规划 3.1 解的概念 考虑

运筹学与最优化方法(吴祈宗)第2章_图文.ppt

运筹学与最优化方法(吴祈宗)第2章 - 第 二 章 基本概念 和 基本理论 第二

第2章经典最优化方法_图文.ppt

第2章经典最优化方法 - 第2章 经典最优化方法 内容介绍 ? 微分学中求极值

运筹学与最优化方法优化建模_图文.ppt

运筹学与最优化方法优化建模 - 最优化方法 建模原理算法 SST 哈尔滨工业大学 尚寿亭 ? 教材与参考 ? [1] 吴祈宗 运筹学与最优化方法 北京:机械工业出版社...

运筹学与最优化方法(吴祈宗)第1章_图文.ppt

运筹学与最优化方法(吴祈宗)第1章 - 运筹学 与最优化方法 吴祈宗等编制 主要内容 第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章 ...

运筹学与最优化方法第二章_图文.ppt

运筹学与最优化方法第二章 - 第二章 基本概念和理论基础 2.1 数学规划模型的

运筹学与最优化方法建模_图文.ppt

运筹学与最优化方法建模 - 最优化方法 建模原理算法 SST 哈尔滨工业大学 尚寿亭 ? 教材与参考 ? [1] 吴祈宗 运筹学与最优化方法 北京:机械工业出版社, ...

【课件】运筹学与最优化方法(华南理工)第4章(06).ppt

【课件】运筹学与最优化方法(华南理工)第4章(06) 【课件】运筹学与最优化方法(华南理工)【课件】运筹学与最优化方法(华南理工)隐藏>> 第 三 章 无约束最优化...