当前位置：文档之家 › 线性规划问题的几何意义

线性规划问题的几何意义

  • 格式：ppt
  • 大小：139.50 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

第三章线性规划的解法习题解答090426y

第三章线性规划的解法习题解答090426y

第三章线性规划的解法§3.1重点、难点提要一、线性规划问题的图解法及几何意义1．图解法。

线性规划问题采用在平面上作图的方法求解，这种方法称为图解法。

图解法具有简单、直观、容易理解的特点，而且从几何的角度说明了线性规划方法的思路，所以，图解法还有助于了解一般线性规划问题的实质和求解的原理。

（1）图解法适用于求解只有两个或三个变量的线性规划问题，求解的具体步骤为：1）在平面上建立直角坐标系；2）图示约束条件，找出可行域。

具体做法是画出所有约束方程(约束条件取等式)对应的直线，用原点判定直线的哪一边符合约束条件，从而找出所有约束条件都同时满足的公共平面区域，即得可行域。

求出约束直线之间，以及约束直线与坐标轴的所有交点，即可行域的所有顶点；3）图示目标函数直线。

给定目标函数Z一个特定的值k，画出相应的目标函数等值线；4）将目标函数直线沿其法线方向向可行域边界平移，直至与可行域边界第一次相切为止，这个切点就是最优点。

具体地，当k值发生变化时，等值线将平行移动。

对于目标函数最大化问题，找出目标函数值增加的方向(即坐标系纵轴值增大的方向)，等值线平行上移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最大值的最优解；对于目标函数最小化问题，找出目标函数值减少的方向(即坐标系纵轴值减少的方向)，等值线平行下移到可行域(阴影部分)的临界点，最终交点就是取得目标函数最小值的最优解。

（2）线性规划问题的几种可能结果：1）有唯一最优解；2）有无穷多个最优解；3）无最优解(无解或只有无界解)。

2．重要结论。

（1）线性规划的可行域为一个凸集，每一个可行解对应该凸集中的一个点；（2）每一个基可行解对应可行域的一个顶点。

若可行解集非空，则必有顶点存在，从而，有可行解必有基可行解。

（3）一个基可行解对应约束方程组系数矩阵中一组线性无关的列向量，对于n 个变量m 个约束方程的线性规划问题，基可行解的个数不会超过!!()!m n n m n m C =-。

借助目标函数的几何意义解线性规划问题

借助目标函数的几何意义解线性规划问题

借助目标函数的几何意义解线性规划问题
线性规划问题是企业决策分析中常见的问题，它利用目标函数的几何意义来求解，目标函数的几何意义就是通过特定的函数曲线使得所求的最优解能够达到的最佳的位置及形状，以达到实现优化的最大化或者最小化的目的。

下面以做公司生产原料决策为例，讲解目标函数几何意义。

企业要求以X1和X2为两种原料采购，采购成本分别为1元和2元，通过原材料加工生产制成品，售价为3元每台。

线性规划问题就是在一定的条件下，如何选择X1和X2的采购量，用更少的采购成本来达到最高的利润。

假设有约束条件，比如最多只能采购3个X1和2个X2，那么，目标函数的几何意义表示的是把X1和X2的采购量作为变量，利润作为函数的函数曲线，在X1和X2的采购量满足约束条件的前提下，把曲线微调，把利润最大化，称为最佳曲线。

因此，结合目标函数几何意义，最终企业可以从曲线最高点处，获得最优原材料采购量，比如最高点处极大值为9，则最优解是，X1=3，X2=2，则最高利润为27元。

线性规划问题可以借助目标函数的几何意义来解决，也就是说，解决线性规划问题的问主要就是把函数曲线的极大值调整到可以实现最大化或最小化的结果位置。

从而可以有效的获得最优解。

2 线性规划

2 线性规划

第一节 线性规划问题及其数学模型
可加性假定：每个决策变量对目标函数和约
束方程的影响是独立于其他变量的，目标函 数值是每个决策变量对目标函数贡献的总和 连续性假定：线性规划问题中的决策变量应 取连续值。 确定性假定：线性规划问题中的所有参数都 是确定的参数。线性规划问题不包含随机因 素。
约 束 方 程
约束条件
变量约束
第一节 线性规划问题及其数学模型
线性规划问题隐含的假定： 比例性假定 可加性假定 连续性假定 确定性假定
比例性假定：决策变量变化引起的目标函数
的改变量和决策变量的改变量成比例，同样， 每个决策变量的变化引起约束方程左端值的 改变量和该变量的改变量成比例
≥0
=
≥0
第一节 线性规划问题及其数学模型
标准型的简缩形式
max Z
c x
j j 1
n
j
s .t
n aij x j bi , i 1,2 , , m j 1 x j 0 , i 1,2 , , m

第一节 线性规划问题及其数学模型
或
松弛变量
a i 1 x 1 a i 2 x 2 a in x n bi
a i 1 x1 a i 2 x 2 a in x n x p bi , x p 0
剩余变量
练习
例:将下列线性规划问题划为标准形式： min Z = x1+3x2
s.t.
6x1+7x28 -x1+3x2-6 x1-x2=3 x10
可行域无界
x1+2x2 10 x2 0 x1
可行域无界
x2
x1 0

最优化方法-线性规划

最优化方法-线性规划

引言
对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他 在1947年提出了求解线性规划的单纯形法（Simple Method），并同时给出了许多很有价值的理论，为线性规划 奠定了理论基础。在1953年，丹捷格又提出了改进单纯形法， 1954年Lemke(兰母凯)提出了对偶单纯形法（dual simplex method）。 在1976年， R. G. Bland 提出避免出现循环的方法后，使线 性规划的理论更加完善。但在1972年，V. Klee和G .Minmty 构造了一个例子，发现单纯形法的迭代次数是指数次运算，不 是好方法——并不是多项式算法（多项式算法被认为是好算 法），这对单纯形法提出了挑战。
B2
B3
70
50 60
A2
60 110 160
[解] 设xij 表示 Ai运往Bj的运量（万块） minS=50x11+60x12+70x13+60x21+110x22+160x23 S.t. x11+x12+x13=23 x21+x22+x23=27 x11+x21=17 x12+x22=18 x13+x23=15 xij≥0, i=1,2、j=1,2,3
2.线性规划问题的几何意义
2.1基本概念 凸集：设k为n维欧氏空间的一点集，任取X,Y∈K,若 连接X,Y的线段仍属于K,则称K为凸集。即任取α ,0<α <1 α X+(1-α )Y∈K 称K为凸集。 顶点（极点）：设K是凸集，X∈K,若X不能用不同的两
点 X(1) ∈K,X2) ∈K 的线性组合表示为 X=α X(1)+(1-α )X(2) (0<α <1) 则称X为极点。

浅谈线性规划问题中目标函数的几何意义

浅谈线性规划问题中目标函数的几何意义
维普资讯
２０ ０ ８年
《 田师 范专科 学校 学报 》（ 和 汉文综合版 ）
Ｊ１ ０ ８第 ２ ｕ． ０ ２ ８卷第 四期
总第 ５ 期 ４
浅谈线性规划问题中目标函数的几何意义
贾玉美
（ 和田地区二中 新疆和田 ８ ８０ ） ４ ００
Ｌ 安Ｊ 捅 本文主 要介绍了 解决线 性规划问 题的方 其关键是 法， 确定目
＝
。
一
面我们就 ｂ 的取值分两种情况来看看： ）与定点Ｍ（，ｂ ａ ）连线的斜率。： —— ：ｘ ａ可以变形为： － ： （） ＝ 且 ａ 。 １ ｂＯ ≠０ 此时 目标 函数 可化 为ｘ： ， ｚ 它表 示 以 ｚ为 ｙ 横截距，垂直于 Ｘ轴的直线。ｚ是一个与横截距相关的量，它的最 值由 ａ的符号，及直线 ｘ Ｏ ＝ 在线性区域内自左向右平行移动最先及 最后经过的点确定。由横截距取值情况知，当ａ ＞Ｏ时，将垂直于 Ｘ 轴的直线在线性区域内自左向右平行移动最先经过的点确定的是最 小值，最后经过的点确定的是最大值：当 ａ 时， ＜Ｏ 将垂直于 Ｘ 轴的 直线在线性区域内自左向右平行移动最先经过的点确定的是最大 值 ，最 后经过的点确定 的是最小值 。
－
（）ｂ ２ ≠０（∈Ｒ） 此时目 ａ 。 标函数可化为Ｙ 一 ÷ 尺， ＝÷＋∈
它示 一为率以为截的线ｚ一与截 相 例 ： 知ｆ －ｓ 表 以詈斜 ，三纵距直 。 个横距 关 ｂ 是 ２已 ｛ｘ＋ｙ＋４＞Ｏ且 。 －， ｚ取 范 。 ４。 ｐ 求 的 值 围 ２ ２
的 ，的 值 ｂ 符 ，斜 为詈直 在 性 域 自 量 它 最 由 的 号及 率 一的 线 线 区 内 下
６
，它
的几何意义是线性区域内的点 Ｐ（ ， ）与定点Ｍ（，ｂ 连线的斜 ｘｙ ａ ） 率的倒数。

线性规划问题的图解法

线性规划问题的图解法
bm 0 1 am ,m 1 amn m
j
0 0 j c j c i a ij
bi 其中： i a kj 0 a kj
单纯形法的计算步骤
例1.8 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
A
0
E
| 5
| 6
| 7
| 8
| 9
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16
C 4 x2 16
4 —B
3— 2— 1—
D
| 1 | 2 | 3 | 4
4—
3— 2— 1— 0
x1
图解法
9— 8—
目标函数 Max Z = 2x1 + 3x2
约束条件 x1 + 2x2 8
4x1 16 4x2 12 x1、 x2 0
x2
7—
6— 5—
4x1 16 4 x2 12 x1 + 2x2 8
4—
3— 2— 1— 0
可行域
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
x2
X1 + 1.9X2 = 11.4 (≤)
8=5X1+4X2 此点是唯一最优解 （ 0， 2）
D
43=5X1+4X2
可行域

高一数学线性规划试题答案及解析

高一数学线性规划试题答案及解析1.若实数、满足约束条件则的最大值是_________【答案】3【解析】画出可行域如下图所示，为目标函数在轴上的截距，画出的图像如图中虚线部分，平移直线过点时有最大值3．故答案为3．【考点】线性规划的应用．2.在直角坐标系中，已知点，，，点在三边围成的区域（含边界）上，且.（Ⅰ）若，求；（Ⅱ）用表示，并求的最小值.【答案】（1），（2）的最小值-1.【解析】（1）向量的坐标运算主要是利用加、减、数乘运算法则进行的.若已知有向线段两端点的的坐标，则应先求出向量的坐标，解题过程中要注意方程的思想的运用及运算法则的正确使用；（2）利用线性规划求目标函数的最值一般步骤：一画、二移、三求，其关键是准确的作出可行域，理解目标函数的意义；（3）在线性约束条件下，线性目标函数只有在可行域的顶点或者边界上取得最值.在解答选择题和填空题时可以根据可行域的顶点直接进行检验.试题解析：解（Ⅰ），∴....................5分由，，，8分设，直线过点时，取得最小值-1，即的最小值-1【考点】（1）向量的坐标表示;（2）线性目标函数的最值.3.已知点（3，1）和（- 4，6）在直线3x-2y+a=0的两侧，则a的取值范围是（）A．a<-7或 a>24B．a="7" 或 a=24C．-7<a<24D．-24<a<7【答案】C【解析】由线性规划相关知识：两点位于直线的两侧，则一侧使得直线方程大于零，一侧使得直线方程小于零.即有,故选C.【考点】线性规划.4.实数满足，如果目标函数的最小值为，则实数b的值为_____ .【答案】8【解析】绘制平面区域可得：要使由最小值-2，则直线,在轴上有最大截距为2，且经过点B,由,又因B也在上，故有.【考点】线性规划.5.已知变量满足约束条件，若的最大值为，则实数．【答案】-1或．【解析】作出约束条件所对应的可行域:,由于的最大值为,所以直线必过点A(-2,3)或点B(4,3),因此有解得或,故应填入:-1或．【考点】线性规划．6.设动点满足,则的最大值是．【答案】100【解析】先画出可行域，根据目标函数可知最优解为C（20，0），带入目标函数得最大者为100【考点】线性规划问题7.已知变量，满足约束条件，则的最小值为（）A．B．C．D．【答案】B.【解析】依题意可画出不等式组所表示的的可行域，可知直线与的交点，作出直线：，平移直线，则可知当，时，的最小值为.【考点】线性规划.8.设变量、满足约束条件，则z＝2x＋3y的最大值为【答案】18【解析】变量x，y满足约束条件，表示的可行域为如图，所以z＝2x＋3y的最大值就是经过M即的交点（3，4）时，所以最大值为：3×2+4×3=18．故答案为：18．【考点】线性规划的应用.9.不等式组表示的平面区域的面积为 .【答案】9【解析】由题意得：平面区域为一个三角形及其内部，其中因此面积为【考点】线性规划求面积10.某公司生产甲、乙两种桶装产品．已知生产甲产品1桶需耗A原料1千克、B原料2千克；生产乙产品1桶需耗A原料2千克，B原料1千克．每桶甲产品的利润是300元，每桶乙产品的利润是400元．公司在生产这两种产品的计划中，要求每天消耗A、B原料都不超过12千克．求该公司从每天生产的甲、乙两种产品中，可获得的最大利润．【答案】该公司从每天生产的甲、乙两种产品中，可获得的最大利润为2800元.【解析】设公司每天生产甲种产品x桶，乙种产品y桶，公司共可获得利润为z元/天，则由已知，得z=300x+400y．且画可行域如图所示，目标函数z=300x+400y可变形为解方程组得，即A(4，4).所以，Z=1200+1600=2800.所以，该公司从每天生产的甲、乙两种产品中，可获得的最大利润为2800元. 9分【考点】简单线性规划的应用点评：中档题，作为应用问题，解简单线性规划问题，要遵循“审清题意，设出变量，布列不等式组，画，移，解，答”等步骤。

运筹学线性规划与目标函数

存在可以量化的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示;
都有一个达到某一目标的要求，可用决策变量的线性函 数(称为目标函数)来表示。按问题的要求不同，要求目 标函数实现最大化或最小化。
11
1.1 问题的提出
决策变量及各类系数之间的对应关系
决策变量
资源
x1 x2 xn
13
1.2 图解法
1.2 图解法
例1是一个二维线性规划问题，可用作图法直观地进行求解。
max z 2x1 3x2
x1 2x2 2
4x1
16

4x2 12
x1 ,x2 0
14
1.2 图解法
max z 2x1 3x2
x2


2 3
x1

z 3
表示一簇平行线
4x1
16

4x2 12

max z=2x1+4x2
x1, x2 0
图1-4 无穷多最优解（多重最优解）
17
1.2 图解法
图1-5-1 无界解
max z x1 x2
2x1 x 4

x1 x2 2
x1,x2 o
max z 2x1 3x2
8
4
x1

4
16 x2 12


4
x1
4x2
x4 16 x5 12
x1, x2 0
x1, x2 , x3, x4 , x5 0
25
1.3 线性规划问题的标准型式
例4 将下述线性规划问题化为标准形式线性规划
min z x1 2x2 3x3

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第2章 线性规划

第二章线性规划教学目的：了解线性规划的基本概念，理解线性规划最优化原理、单纯形法原理，掌握单纯形法及其矩阵描述、人工变量法、，能够对简单的问题建模。

教学重点：线性规划的含义、性质；线性规划问题的求解方法——图解法、单纯形法。

线性规划模型的建立非标准型线性规划问题转化为标准线性规划问题；线性规划问题的图解法；解的存在情况判断；大M法；两阶段法；单纯形法的矩阵表示；教学难点：单纯形法的求解思想、矩阵表示、对偶理论、对偶单纯形法以及灵敏度分析。

学时： 8学时2.1 线性规划(Linear Programming,LP)问题及其数学模型（1学时）我们应用数学规划模型求解实际问题中，将实际问题抽象成数学模型，然后再对其求解。

2.1.1线性规划问题提出我们用一个简单例子来说明如何建立数学规划问题的数学模型。

例2.1 某家具厂生产桌子和椅子两种家具，有关资料见表2－1。

解：用数学语言来描述生产计划安排问题，这个过程称为建立其数学模型，简称建模。

设：①桌子、椅子生产的数量分别为x1，x2，称为决策变量。

因为产量一般是一个非负数，所以有x1，x2≥0，称非负约束。

②限制条件为木工和油漆工的加工时间约束了产品的生产量x1，x2。

约束如下：4x1＋3x2≤1202x1＋x2≤50③生产桌子、椅子x 1，x 2所得总收入为Z ，显然Z ＝50x 1＋30x 2。

我们希望总收入值能达到最大，这个关系用公式表达为max Z ＝50x 1＋30x 2 把上述所有数学公式归纳如下12121212max .0z 50x 30x 4x 3x 120s t 2x x 50x x =++≤⎧⎪+≤⎨⎪≥⎩，这就是一个最大化的线性规划模型。

例 2.2（运输工具的配载问题）有一辆运输卡车，载重2.5t ，容积183m ，用来装载如下的两种货物：箱装件125kg/个、0.43m /个；包装件20kg/个、1.53m /个。

问：如何装配，卡车所装物件个数最多？解 根据题意，设箱装件1x 个，包装件2x 个，那么需要满足条件：体积约束 120.4 1.518x x +≤重量约束 12125202500x x +≤非负约束12,0x x ≥目标要求 max z=12x x +我们对上面的式子稍作整理，便得到下面的形式：max z=12x x +1212120.4 1.518125202500,0x x x x x x +≤⎧⎪+≤⎨⎪≥⎩ 上述两例中所提出的问题，最终都归结为在变量满足线性约束条件的前提下，求使线性目标函数最大或最小的问题，这种问题称为线性规划问题。

从目标函数几何意义探求线性规划问题

从目标函数的几何意义探求线性规划问题新教材试验修订本中“简单的线性规划”是新增加的内容,在线性约束条件下研究目标函数的最值问题是一类常见题型。

在近几年高考试题中都有所体现,若能借助于目标函数的几何意义解题,可提供直观明了的解题思路,解题也显得迅速简捷。

本文通过对目标函数几何意义的诠释来解几类线性规划中的最值问题。

一、借助于平面向量的数量积解一类线性规划问题形如z=ax+by的目标函数,可以把它看成平面内的向量=(a,b)与向量=(x,y)的数量积即z==cosθ,因为为定值,所以z的最值主要由cosθ决定的,即向量在向量方向上的投影。

例1.(2005年山东卷15)设x、y满足约束条件x+y≤5,3x+2y≤12,0≤x≤3,0≤y≤4则使得目标函数z=6x+5y的值最大的点(x,y)是_______。

图1解析:作出可行域如图1,设n(x,y)为可行域内的任意一点,m(6,5),则z==cos∠mon,由数量积的几何意义(如图所示)得,当n(x,y)在a(2,3)时,在上的投影最大,即z=6x+5y取得最大值,zmax=27。

二、借助于两点间的距离解一类线性规划问题形如z=(x-a)2+(y-b)2的目标函数,可以把它看成点m(a,b)与点n(x,y)间距离的平方,即z=mn2,问题转化为研究m、n两点间距离平方的最值,又m为定点,所以z的最值主要由可行域内n点位置决定。

例2.已知2x+y-2≥0,x-2y+4≥0,3x-y-3≤0求z=x2+y2的最值,并求出z取得最值时x、y的值。

图2解析:作出满足约束条件的可行域如图2。

设p(x,y)为可行域内任意一点,目标函数z可视为o、p两点间的距离的平方,问题转化为研究距离平方的取值范围,由图易知可行域内,点c到原点o的距离最远,即:zmax=oc2=13,此时x=2,y=3。

又过o作直线ab:2x+y-2=0的垂线,垂足d(,),可知点d到原点的距离最近,即zmin=od2=。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

重要结论
根据以上讨论，可以得到以下结论： 线性规划问题的可行域是凸集（定理3.1）；凸集的 每个顶点对应一个基可行解（定理3.2），基可行解个数 是有限的，当然凸集的顶点也是有限的；若线性规划有最 优解，必在可行域某顶点上达到（定理3.3），亦即在有 限个基可行解中间存在最优解。因此，我们可以在有限个 基可行解中去找最优解。这就是下节将介绍的单纯形法的 理论依据，该方法就是一种在基可行解中搜索最优解的算 法。
因此，对于j=k+1,k+2,…,n，应有 k 1 2 0 ，由于P1,P2,…,Pk线性无关， 并且 pj xj xj 故 xj1 xj2 ,j=1,2,…,k.这就得到了x（1）=x（2）之矛盾。

2 1 xj xj 0







i1
i1
由X（0）的任意性,知线性规划在顶点X（m）处达到最优。

显然θ>0。 取x（1）=(x1+θα 1,x2+θα 2,…,xk+θα k,0,…,0)T x（2）=(x1-θα 1,x2-θα 2,…,xk-θα k,0,…,0)T
易于验证x（1）∈D，x（2） ∈D，x（1）≠x（2）且
1 2 1 1 X X X ，此与X是D的顶点矛盾，因而X是基可行解。 2 2 充分性：←设X是问题的基可行解，不妨设x1＞0,x2＞ 0,…,xk＞0, xk+1=…=xn=0（k≤m），于是P1,P2,…,Pk必线 性无关。若X不是D的顶点，则存在x（1）∈D，x（2） ∈D， x（1）≠x（2）及α ∈（０，１），有
定义（顶点）设K是凸集,X∈K，若X不能表示成任何 x（1）∈K， x（2）∈K两点连线的内点，则称X为K的一个顶 点（或极点）。 关于线性规划问题解的性质，介绍以下几个定理： 定理3.1 线性规划的可行域 D=｛x︱Ax=b,x≥0｝ 是一个凸集。 证明：设x（1）∈D，x（2） ∈D，且x（1）≠x（2） 则 Ax（1）=b, x（1）≥0；Ax（2）=b, x（2）≥0 令 x＝α x（1）+（1-α ）x（2） 则 Ax＝α Ax（1）+（1-α ）Ax（2）=b,且x≥0 ∴x∈D 因此，根据凸集的定义，知D是凸集。

x＝α x（1）+（1-α ）x（2）
于是，对j=k+1,k+2,…,n，有 0 xj α


2 1 xj 1 α x j
运 筹 学
主讲教师 向题的几何意义
定义（凸集） 设K是n维欧氏空间的一个点集，若 任意两点x（1）∈K ， x（2）∈K的连线上的一切点 α x（1）+（1-α ）x（2）=x∈K (0≤α ≤1) 则称K为凸集。 凸集的特征是：连接集合中任意两点的线段整个地 都在集合之中。实心的凸多边形、凸多面体都是凸集。 定义（凸组合） 设x（1） , x（2）,…,x（k）是n维欧氏 k 空间的k个点，若存在满足0≤μ i≤1, i=1,2…k, 1, i （ 1 ） （ 2 ） （ k ） i 1 则称 x=μ 1x +μ 2x +…+μ kx 为x（1）,x（2）,…,x（k）的凸组合.
j1


因此，Ｘ必为顶点。
引理２ 若Ｋ是有界凸集，则任何一点x∈Ｋ都可表 示为Ｋ的顶点的凸组合。
定理３.３ 若可行域非空有界，则线性规划问题一定 可以在可行域的某个顶点上找到最优解。 证明：不妨设可行域的顶点为x（１），x（2），…，x（k） 再设x（0）是可行域Ｄ的任意一点。由引理２，有 k i ， 0 x α ix 0≤α i≤１,Σ α i=1 i1 i k i k 0 i m 因此， 设 max cx cx cx cα ix α icx , i1k i1 i1 则有 k k 0 i cx α icx α icxm cxm
引理1 线性规划的可行解X=(x1,x2…xn)T是基可行解 的充要条件是： X的正分量对应的系数列向量是线性无关 的。
定理3.2 X是可行域D=｛x︱Ax=b,x≥0｝的顶点的充 要条件是：X是该线性规划问题的基可行解。 证明：必要性→设X是D的顶点。若X不是基可行解， 不妨设x1＞0,x2＞0,…,xk＞0, xk+1=…=xn=0.由引理1知 P1,P2,…,Pk必线性相关,于是存在不全为0的一组数α 1, x k j , α 2,…,α k满足 α jpj 0 , 令θ min j , k , 1,2, α j0 j1 α j