ch1-5单纯形法

( B , N ) (CB CB B 1 B, CN CB B1 N ) C CB B1 A
主页
上页
下页
返回
结束
4.4 基变换—（L,K）旋转变换（换基迭代）
在单纯形法中，如果得到的基可行解经检 验不是最优解，又不能判定无有限最优解时， 就应该去找一个新的基可行解。 具体做法是从原可行基中撤换一个列向量 （当然要保证撤换后的各列向量仍然线性无 关），得到一个新的可行基，这称为基变换。 为换基，先要确定换入变量（进基变量），再 确定换出变量（出基变量），让它们相应的系 数列向量对换，进而便可求得一个新的基可行 解。
n）
Z CB B b N X N CB B b
1 1
j m 1

n
j
Xj
⑵
非基变量Xj前面的系数σj ,可以用来判断当前对应与 基B的基可行解是否为最优。故称为变量Xj对应的 检验数。
主页 上页 下页 返回 结束
定理4.1最优性判定定理 对某基可行解XB=B-1b，其余 Xj=0,若所有检验数σ j= Cj-CBB-1Pj ≤0 ， j=m+1,m+2, …,n，则该解为最 优解。
j


步骤3 若对于σk>0，有B-1Pk≤0，（即单纯形表中 Xk对应的系数列向量非正），则该问题无有限最 优解，计算停止；否则转步骤4
主页
上页
下页
返回
结束
min ( B 1b)i aik ) aik 0 ( B 1b)l alk 步骤4 计算 i
确定单纯形表中第L行对应的基变量为旋出变量。 步骤5 以alk为主元作（L,K）旋转变换，得新的 单纯形表，转步骤2

2. 求极限方法举例
例 1 求lim(3x2 5x 8).
x1
解：lim(3x2 5x 8) lim3x2 lim5x lim8.
x1
x1
x1
x1
3lim x2 5lim x 8.
x1
x1
3(lim x)2 5 8 3 5 8 6.
注意：{ x 0 | x x0 | } { x | x0 x x0 } \ { x0}
{x x0 x x0 } {x x0 x x0 } 说明 1) 用来刻划x与 x0的接近程度,与任意给定
的正数 有关.
2) 定义中0 | x x0 | 是重要的,不能去掉.
意义 关于无穷大的讨论,都可归结为关于无穷 小的讨论.
福州大学数计学院
15
二、极限的运算法则
1. 极限运算法则
定理
设 lim f ( x) A , lim g( x) B , 则
x
x
(1) lim[ f ( x) g( x)] A B ; x
(2) lim[ f ( x) g( x)] A B ; x
为什么？
解: 没有极限．
假设 f ( x) g( x) 有极限， f ( x)有极限，
由极限运算法则可知：
g( x) f ( x) g( x) f ( x) 必有极限，
与已知矛盾，
故假设错误．
福州大学数计学院
17
推论 1 如果lim f (x) A，c为常数，则 lim[cf (x)] c lim f (x) cA.
(分母有理化)
(1)解: 原式

运 筹 帷 幄 之 中
第一章
线 性 规 划及单纯形法
决 胜 千 里 之
Linear Programming
外
引言

运筹学的重要分支之一，应用最广泛的方法 之一 运筹学的最基本的方法之一，网络规划，整 数规划，目标规划和多目标规划都是以线性 规划为基础的 解决稀缺资源最优分配的有效方法，使付出 的费用最小或获得的收益最大

约束条件（ Constraints ）：线性等式或不等式 目标函数（ Objective function ）： z=ƒ(x1 … xn) 线性式，求z极大或极小

一、问题提出及一般模型
建模条件
(1) 优化条件：问题所要达到的目标能用线型函数描述，且 能够用极值 （max 或 min）来表示；
一、问题提出及一般模型
例1.1 某厂生产两种产品， 解： 1.决策变量：设产品I、II的产量 下表给出了单位产品所需资 分别为 x1、x2 源及单位产品利润
2.目标函数：设总利润为z，则有： max z = 2 x1 + x2 3.约束条件： 5x2 ≤ 15 6x1+ 2x2 ≤ 24 x 1+ x 2 ≤ 5 x1， x2≥0
3x1 ＋x2 +x3 +2 x4
x1、x2 、x3 、x4 ≥0
一、问题提出及一般模型
例1.3 某航运局现有船只种类、数量以及计划期内各条航 线的货运量、货运成本如下表所示：
航线号 船队 类型 1 1 2 3 2 4 1 1 2 编队形式 拖轮 1 A型 驳船 2 — 2 — B型 驳船 — 4 4 4 货运成本 （千元／队） 36 36 72 27 货运量 （千吨） 25 20 40 20
xj 0

工程优化设计中单纯形法的基本原理张云龙（大连海洋大学土木工程学院辽宁大连116023)摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。

在此基础上进一步讨论单纯形法的推广，即大M法和两相法。

关键词：线性规划图解法单纯形法大M法THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGNZHANG Yun-long(Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 16023)Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phase method.Key Words: Linear programming；Graphic method；Simplex Method; Big M Method1引言在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。

如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。

线性规划在工程实例中的应用已相当广泛。

虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。