当前位置：文档之家 › (完整word版)第二章运筹学 线性规划

(完整word版)第二章运筹学 线性规划

  • 格式：doc
  • 大小：815.50 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

第二章线性规划

第二章线性规划



线性规划要研究的两类问题中都包含有约束条件和目 标函数。用数学的方式描述，规划的目的就是在给定 的限制条件（或称约束条件）下，求目标函数的极值 问题（包括极小值和极大值）。
2
线性规划的数学模型
3
解： 设产品 的产量为：1 , 产品 的产量为：x2 x
4
5
6
7

配料问题：由若干种不同价格、不同成分含量的原料，用 不同的配比混合调配出一些不同规格的产品，在原料的供 应量限制和保证产品成分含量的前提下，如何进行配料来 获取最大利润或使总成本最低。
15
2.2.3 线性规划求解的可能结局
1、有唯一的最优解
2、有无穷多个最优解 （将目标函数改为 z=4x1+3x2 ）
x2
max z 4 x1 3 x2 x1 2 x2 5 2 x x 4 1 2 s.t. 4 x1 3 x2 9 x1 , x2 0
3x1 2 x2 4 x3 3
3x1 2 x2 4 x3 xs 3
剩余变量
变量xs实际上是原式左端减去右端的差，即 ：
xs 3x1 2 x2 4 x3 3
当约束条件是“ ”型的不等式时，只要将该约 束条件左端减去一个非负的剩余变量即可化为等式。 无论是松弛变量还是剩余变量在决策中都不产生实际价 值，因此它们在目标函数中的系数都应该为零。有时也将松 29 弛变量和剩余变量统称为松弛变量。
2x1+x2=4 D C
x1+2x2=5 B 4x1+3x2=9 O A x1
16
3、无界解
指线性规划问题有可行解，但是 在可行域，目标函数值是无界的， 因而达不到有限最优值。因此线 性规划问题不存在最优解。

管理运筹学课件第2章 线性规划

管理运筹学课件第2章 线性规划

x1 x2 ≤ 8
产量非负 x 1 , x 2 ≥ 0
决策变量
（decision variable）
总利润表三达要式素
目标函数 （objective function）
约束条件 生产能力,不 （subject to） 允许超过 当目标函数与约束条件均为决策变
量的线性函数，且变量取连续值时，
当xk的值由0增加到θ时，原来的基变 量xl取值首先变成零，选择其为出基变 量。称θ的表达式为最小比值原则。
如果所有aik ≤0, xk的值可以由0增加到 无穷，表示可行域是不封闭的，且目 标函数值随进基变量的增加可以无限 增加，此时不存在有限最优解。
下面对以上讨论进行总结.
2019/8/31
课件
15
称为线性规划LP；变量取整称为整
数线性规划ILP；变量取二进制为
0-1规划BLP。
2019/8/31
课件
5
2.1.2 线性规划的数学模型
【例2.1】（合理配料问题）由下表建立一个LP模型求解满足动物成长 需要又使成本最低的饲料配方。
饲料 营养甲(g/kg) 营养乙(g/kg) 营养丙(g/kg) 成本(g/kg)
x1+x2=8

x1
2019/8/31
课件
11
2.2.3 线性规划几何解的讨论
线性规划几何解存在四种情况：唯一最优解、无穷 多最优解、无界解、无可行解。 可行域为封闭有界区域时，可能存在唯一最优解， 无穷多最优解两种情况； 可行域为非封闭无界区域时，可能存在唯一最优解， 无穷多最优解，无界解三种情况； 可行域为空集时，没有可行解，原问题没有最优解。
1
0.5
0.1
0.08

运筹学 第二章 线性规划课件

运筹学 第二章 线性规划课件

ij m n
1
m
则模型可表示为
Maxz CX
s .t
.
AX X
0
b
2020/11/9
运筹学 第二章 线性规划
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 428.0000
VARIABLE VALUE X1 20.000000 X2 24.000000
A
B
CD
0.1
0
0.1 0.2
0
0.1
0.2 0.1
0.4
0.6
2.0 1.7
试决定买M与N二种饲料各多少公斤而使支出的总费用为 最少？
运筹学 第二章 线性规划
2020/11/9
解：设购买M、N饲料各为 x , x ，则
1
2
M 1 i x 1 n 0 4 x 2 z
0.1x1 0 x 2 0.4
第二章 线性规划（Linear Programming）
第一节 线性规划的模型与图解法 第二节 单纯形法 第三节 对偶问题与灵敏度分析 第四节 运输问题 第五节 线性整数规划
2020/11/9
运筹学 第二章 线性规划
第一节 线性规划的模型与图解法
一、线性规划问题及其数学模型
在生产管理和经营活动中经常需要解决：如何 合理地利用有限的资源，以得到最大的效益。
2020/11/9
运筹学 第二章 线性规划
2020/11/9
例1 某工厂可生产甲、乙两种产品，需消耗 煤、电、油三种资源。现将有关数据列表如下：
资源单耗 产 品
资源 煤 电 油
单位产品价格
甲乙

管理运筹学_第二章_线性规划的图解法

管理运筹学_第二章_线性规划的图解法

线性规划中超过约束最低限的部分，称为剩余量。 记s1,s2为剩余变量，s3为松弛变量，则s1=0, s2=125,
s3=0，加入松弛变量与剩余变量后例2的数学模型变为 标准型： 目标函数： min f =2x1+3x2+0s1+0s2+0s3 约束条件： x1+x2-s1=350， x1-s2=125, 2x1+x2+s3=600, x1, x2, s1,s2,s3≥0.
阴影部分的每 一点都是这个线 性规划的可行解， 而此公共部分是 可行解的集合， 称为可行域。
B
X2=250
100
100
300
x1
B点为最优解， X1+X2=300 坐标为（50, 250）， Z=0=50x1+100x2 此时Z=27500。 Z=10000=50x1+100x2 问题的解： 最优生产方案是生产I产品50单位，生产Ⅱ产品250单位，可得 最大利润27500元。
Z=10000=50x1+50x2
线段BC上的所有点都代表了最优解，对应的最优值相 同： 50x1+50x2=15000。
10
3. 无界解，即无最优解的情况。对下述线性规划问题：
目标函数：max z =x1+x2 约束条件：x1 - x2≤1 -3x1+2x2≤6 x1≥0, x2≥0．
x2 -3x1+2x2=6 3
其中ci为第i个决策变量xi在目标函数中的系数， aij为第i个约束条件中第j个决策变量xj的系数， bj(≥0)为第j个约束条件中的常数项。
16
灵敏度分析
灵敏度分析：求得最优解之后，研究线性规划的

运筹学基础对偶线性规划(2)

运筹学基础对偶线性规划(2)

y1 +2y2 +y3 ≤ 3
-3y1 +y3 ≤ -5
y1 -y2 +y3＝1
y1 ≥ 0, y2 , y3 ≤ 0
对偶问题（或原问题） 目标函数最大化（ maxZ）
n 个约束 m 个变量 目标函数价值向量（系数） 约束条件限定向量
≤ 约束 ≥
＝
≥0 变量 ≤ 0
无限制
§2.2 线性规划的对偶理论
n 个变量 m 个约束 约束条件限定向量（右边项） 目标函数价值向量
≥0 变量 ≤ 0
无限制
对偶问题（或原问题） 目标函数最大化（ maxZ）
n 个约束 m 个变量 目标函数价值向量（系数） 约束条件限定向量
≤ 约束 ≥
＝
-2 x1
x3 3
≥ 约束 ≤
≥0 变量 ≤ 0
x1,x2,x3
＝
无限制
原问题线性规划模型 对偶线性规划模型
max f 2x1 3x2 min g 8y1 16 y2 12 y3
x1 2 x2 8 s.t.44x1xx,12x2 11620
s.t.
y1 4y2 2 2y1 4y3 3
yi 0,i 1,2,3
下列的表给出了原问题模型和模型的对应关系，这些也可以
≥ 约束 ≤
＝
≥ 约束 ≤
＝
反号
Hale Waihona Puke ≤0 变量 ≥ 0无限制
原问题(maxZ)与对偶之关系：
原问题 目标函数max
对偶问题 目标函数min
n个
变 量
无 00约束
n个 约
束
条
件
原问题(maxZ)口诀: 变量决定约束是同号
约 m个

运筹学第二章

运筹学第二章

例2.4：将以下线性规划问题转化为 标准形式
Max s.t. Z = 3 x1 - 5 x2 + 8 x3 2x1 + 2x2 - x3 = 15.7
4 x1
+ 3x3 = 8.9
x1 + x2 + x3 = 38 x2 , x3 ≥ 0
4.右端项有负值的问题：
在标准形式中，要求右端项 必须每一个分量非负。当某一个 右端项系数为负时，如 bi<0，则 把该等式约束两端同时乘以-1， 得到：
产品甲 设备A 3 产品乙 2 设备能力 （h） 65
设备B
设备C 利润（元/件）
2
0 1500
1
3 2500
40
75
问：如何安排生产计划，才能使制药厂利润最大？
解：设变量 xi为第i种（甲、乙）产品的生 产件数（i＝1，2）。根据前面分析，可 以建立如下的线性规划模型： Max
z = 1500 x1 + 2500 x2
MinZ=∑xi
i=1
X6 +
x1 x1 + x2 x2 + x3 x3 + x4 x4 + x5 x5 + x6
≥ 8 ≥ 12
≥ 10
≥ 8 ≥ 6 ≥ 4
二、线性规划模型的一般形式
目标函数 s.t.
产品对资源的 单位消耗量
利润系数
Max(Min)z=c1x1+c2x2+……+cnxn
a11x1+a12x2+……+a1nxn≥(=、≤)b1 a21x1+a22x2+……+a2nxn≥(=、≤)b2 …… am1x1+am2x2+……+amnxn≥(=、≤)bm

管理运筹学(第二章 线性规划的图解法)


3
南京财经大学管理科学与工程学院
第二章 线性规划的图解法
线性规划问题的一些共同特点
•都有要求达到某些数量上的最大化或最小化的目标 •所有线性规划问题都是在一定的约束条件下来追求其目标的
4
南京财经大学管理科学与工程学院
第二章 线性规划的图解法
§2.1 问题的提出
§2.2 图解法
§2.3 图解法的灵敏度分析
4）确定约束条件：
原料约束：x1 + x2 ≥ 350， x1 ≥ 125
加工时数约束：2x1 + x2 ≤ 600
非负约束：x1 , x2 ≥ 0
25
南京财经大学管理科学与工程学院
§2.2
图解法
解：目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 ≥ 350 x1 ≥ 125 x2 2x1 + x2 ≤ 600 x 1 , x2 ≥ 0
• 决策变量（X）
决策问题待定的量值称为决策变量。 决策变量的取值要求非负。
• 目标函数（ Max F 或 Min F ）
衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 目标函数是决策变量的线性函数。 有的目标要实现极大，有的则要求极小。
• 约束条件 （s.t. (subject to) 满足于）
2
南京财经大学管理科学与工程学院
第二章 线性规划的图解法
线性规划在管理中一些典型的应用
•合理利用线材问题：如何在保证生产的条件下，下料最少 •配料问题：在原料供应量的限制下如何获取最大利润 •投资问题：从投资项目中选取方案，使投资回报最大 •产品生产计划：合理利用人力、物力、财力等，使获利最大 •劳动力安排：用最少的劳动力来满足工作的需要 •运输问题：如何制定调运方案，使总运费最小

运筹学第2章-线性规划的对偶理论

❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
Ma例x：Z （ 2第x一1 章3例x22）
2 x1 2 x2 12
当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的：
Zmax=Wmin
二、原问题和对偶问题的关系
1、对称形式的对偶关系
（1）定义：若原问题是
MaxZ c1 x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21
x1
a22
二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
5y3 3
，y
2
3
0
（用于生产第i种产 品的资源转让收益不 小于生产该种产品时 获得的利润）
对偶变量的经济意义可以解释为对工时及原材 料的单位定价 ；
若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低）
内，使得产品的总利润最大 。
MaxZ 2x1 3x 2
2x1 2x2 12
s.t.54xx12
16 15
x1, x 2 0
它的对偶问题就是一个价格系统，使在平衡了 劳动力和原材料的直接成本后，所确定的价格系统 最具有竞争力：
MinW 12y1 16y2 15y3
2y1 4y2
2
s.t.2y1y，1y
y1, y2, , ym 0

(完整word版)运筹学课后习题答案林齐宁版本北邮出版社

No .1 线性规划1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而成。

这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目ABCD单位产值 (元) 168 140 1050 406 单位成本 (元) 42 28 350 140 单位纺纱用时 (h) 3 2 10 4 单位织带用时 (h)20.5工厂有供纺纱的总工时7200h ，织带的总工时1200h 。

(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？ 解：(1)设A 的产量为x 1，B 的产量为x 2，C 的产量为x 3，D 的产量为x 4，则有线性规划模型如下：max f (x )=(16842)x 1 +(14028)x 2 +(1050350)x 3 +(406140)x 4=126 x 1 +112 x 2 +700 x 3 +266 x 4s.t. ⎪⎩⎪⎨⎧=≥≤+≤+++4,3,2,1 ,012005.02 720041023434321i x x x x x x x i(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。

2、将下列线性规划化为极大化的标准形式解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x 4，在第二行添加人工变量x 5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x 6, x 7，并令x x x 333='-''，则有max[f (x )]= {2 x 13 x 2 5('-''x x 33)+0 x 4M x 5+0 x 6 +0 x 7}s.t. 0,,,,,,,13 55719 13 55719 16 9976 5 7654332173321633215332143321≥'''=+''+'-+-=+''-'+-=+''+'-+-=+''-'+--⎪⎪⎪⎩⎪⎪⎪⎨⎧x x x x x x x x x x x x x x x x x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧±≥≤+-=-+--≥-+++=不限321321321321321 ,0,13|5719|169765 ..532)(m in x x x x x x x x x x x x t s x x x x f3、用单纯形法解下面的线性规划⎪⎪⎩⎪⎪⎨⎧≥≤++-≤++-≤-+++= ,0,,4205.021********* ..352)(max 321321321321321x x x x x x x x x x x x t s x x x x f 解：在约束行1,2,3分别添加x 4, x 5, x 6松弛变量，有初始基础可行解和单纯形法迭代步骤如下：C j1 12 z jC j2 1/3 1/6 11/6 1/6 z j5/6 5/6 C j3/5 1/1011/107/20z j11/20 C jz j11/ 29/811/8答：最优解为x1 =244.375, x2 =0, x3 =123.125, 剩余变量x6 =847.1875；最优解的目标函数值为858.125。

运筹学 第二章

8
由例1的求解的过程中，我们观察到如下事实： 由例 的求解的过程中，我们观察到如下事实： 的求解的过程中 1）若某一个线性规划问题有最优解，则一定有一个可行域的 ）若某一个线性规划问题有最优解， 顶点对应一个最优解。 顶点对应一个最优解。 2）线性规划存在有无穷多个最优界的情况。 ）线性规划存在有无穷多个最优界的情况。 如例1中将目标函数改为 如例 中将目标函数改为 max z = 50 x 1 + 50 x 2 , 则代表目标函数 的直线平移到最优位置后， 重合。 的直线平移到最优位置后， 与直线 x 1 + x 2 = 300 重合。 3）线性规划存在无界解，即无最优解的情况。 如 ）线性规划存在无界解，即无最优解的情况。 x2 • 目标函数： 目标函数： max z = x + x , 约束条件： 约束条件： x 1 − x 2 ≤ 1, − 3 x 1 + 2 x 2 ≤ 6, x 1 ≥ 0, x 2 ≥ 0. 此时称该问题无界！ 原因： 原因：某些约束条件没有考虑到
第二章 线性规划的图解法
几种常见的典型的线性规划问题在管理上的应用: 几种常见的典型的线性规划问题在管理上的应用: 1.合理利用线材问题: 现有一批长度一定的钢管， 1.合理利用线材问题: 现有一批长度一定的钢管， 由于生产的 合理利用线材问题 需要， 需要， 要求截出不同规格的钢管若干。 试问应如何下料， 要求截出不同规格的钢管若干。 试问应如何下料，既满足了 生产的需要，又使得使用原材料钢管最少。 生产的需要，又使得使用原材料钢管最少。 最少 2.配料问题: 用若干种不同价格不同成分含量的原料， 2.配料问题: 用若干种不同价格不同成分含量的原料，用不 配料问题 同的配比混合调配出一些不同的规格的产品， 同的配比混合调配出一些不同的规格的产品， 在原料供应量的限 制和保证产品的成分的含量的前提下，如何获取最大的利润。 制和保证产品的成分的含量的前提下，如何获取最大的利润。 最大的利润 3.投资问题: 从不同的投资项目中选出一个投资方案， 3.投资问题: 从不同的投资项目中选出一个投资方案，使得 投资问题 投资回报为最大 最大。 投资回报为最大。 4.产品生产计划: 合理充分利用厂里现有的人力、物力、财 4.产品生产计划: 合理充分利用厂里现有的人力、物力、 产品生产计划 做出最优的生产计划，使得工厂获利最大 最大。 力，做出最优的生产计划，使得工厂获利最大。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第二章 线性规划主要内容：1、线性规划问题及数学模型 2、线性规划问题的解及其性质3、图解法4、单纯形法5、大M 法和两阶段法重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。

要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握其求解技巧；培养解决实际问题的能力。

§1 线性规划的数学模型及解的性质一、数学模型（一般形式）例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？解：设三种体系的建筑面积依次为1x ,2x ,3x 万平方米， 则目标函数为 321max x x x z ++=约束条件为 ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥≤++≤≤++≤++≤++3,2,104005.335.414700210150001801901102000253012110001221371053211321321321j x x x x x x x x x x x x x x j例2 某工厂要安排生产甲、乙两种产品。

已知：问：如何安排两种产品的生产数量，才能使总产值最高？ 解：设21,x x 分别为甲、乙两种产品的生产量：则目标函数为 21127max x x z += 约束条件为⎪⎪⎩⎪⎪⎨⎧=≥≤+≤+≤+2,1,03001032005436049112121j x x x x x x x j从以上两例可以看出，它们都属于一类优化问题。

它们的共同特征：①每一个问题都有一组决策变量（n x x x 21,）表示某一方案；这组决策变量的值就代表一个具体方案。

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

②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。

③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。

满足以上三个条件的数学模型称为线性规划的数学模型。

其一般形式为：目标函数 n n x c x c x c z +++= 2211m ax (m in)约束条件 ()()()⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=≥≤+++=≥≤+++=≥≤+++nj x bx a x a x a b x a x a x a b x a x a x a j mn mn m m n n n n ,,2,1,0,,,22112222212111212111可行解：满足约束条件的一组决策变量，称为可行解。

最优解：使目标函数取得最大（小）值的可行解，称为最优解。

最优值：目标函数的最大（小）值，称为最优值。

二、标准型（一）问题的标准形式：n n x c x c x c z +++= 2211ma x⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+++=+++=+++nj x bx a x a x a b x a x a x a b x a x a x a j mn mn m m n n n n ,,2,1,022112222212111212111第二章 线性规划 第 5 页其中 n m m i b i <=≥,,2,10注意：任何一个一般型都可转化为一个标准型。

（二）标准型的表示方法：1、和式形式：∑==nj jj x c z 1max()()⎪⎩⎪⎨⎧=≥==∑=n j x m i b x a jnj i j ij ,,2,10,,2,112、矩阵形式：CXz =max⎩⎨⎧≥=0X b AX其中[]n c c c C ,,,21 =-------价格系数向量⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=m b b b b 21-------资源向量（限定系数向量）⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=mn m m n n a a a a a a a a a A ,,,,,,,,,212222111211 -----------约束条件系数矩阵[]Tn x x x X ,,,21 =--------决策变量3、向量形式：n n x c x c x c z +++= 2211m ax⎩⎨⎧≥=++02211j n n x b P x P x P x 其中⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=j n j j j a a a P ,,2,1 为约束条件系数矩阵A 的第j 列。

（三）一般型化为标准型的方法 1、CX z =min引进新的目标函数Z Z -=', 则可化为CXZ -='max2、不等式约束①in in i i b x a x a a ≤+++ 221第二章 线性规划 第 7 页引进新的非负决策变量, 使得1+n xi n n in i i b x x a x a x a =+++++122111+n x 称为松弛变量，在目标函数中，其价格系数为0。

②i n in i i b x a x a x a ≥+++ 2211引进新的非负决策变量1+n x ,使得i n n in i i b x x a x a x a =-++++122111+n x 称为剩余变量，在目标函数中，其价格系数为0。

3、若0<i b ，即02211<=+++i n in i i b x a x a x a可变为02211>-=----i n in i i b x a x a x a4、若某个变量j x 无非负限制，称为自由变量。

令00≥''≥'''-'=j j j j j x x x x x例3 将下列问题化为标准型21127m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤+≤+0,0300103200543604921212121x x x x x x x x解：标准型为54321000127m ax x x x x x z ++++=5,4,3,2,103001032005436049521421321=≥=++=++=++⎪⎪⎩⎪⎪⎨⎧j x x x x x x x x x x j例4 将下列问题化为标准型32173m in x x x z -+-=⎪⎪⎩⎪⎪⎨⎧≥=++-≥+-≤+-无约束3213213213210,64542732x x x x x x x x x x x x 解：令zz -=' ，标准型为：543210073m ax x x x x x z +++-='⎪⎪⎩⎪⎪⎨⎧≥=++-=-+-=++-无约束35421321532143210,,,64542732x x x x x x x x x x x x x x x x第二章 线性规划 第 9 页令333x x x ''-'=则标准型为：54332100773x z max x x x x x ++''-'+-='三、线性规划问题的解标准型CXz =max⎩⎨⎧≥=0X bAX],,,[21212222111211n nm mn m m n n P P P a a a a a a a a a A =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⨯记n P P P21秩:()n m mA rank <=im i i P P P ,,,21 []im i i P P P B ,,,21 =1、基阵：若列向量是线性无关的，则称为LP 问题的一个基阵。

基矩阵中每个列向量称为基向量。

⎪⎪⎩⎪⎪⎨⎧≥'''=''-'++-=-''-'+-=+''-'+-0,,,,,644542733254332131215332143321x x x x x x x x x x x x x x x x x x x x由非基向量组成的矩阵称为非基矩阵，记为()m n m N -⨯例如：531001030105400149⨯⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=A取[]⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡==100010001,,5431P P P B 线性无关，则⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=10354491N []⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡==003104019,,4312P P P B 线性无关，则⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=11005042N2、基变量：基矩阵中各列向量对应的变量称为基变量，记为[]Tim i i B x x x X ,,,21 =。

如[]5431,,P P P B =, 则基变量为543,,x x x 。

对应于非基向量的变量称为非基变量，记为 []Tin m i n x x X ,,)1( +=3、基本解：设基矩阵为[]m 21P ,,, P P B =，则非基矩阵[]n m P P N ,,1 +=∴[]N BA = ⎥⎦⎤⎢⎣⎡=N B X X X那么，约束方程 []b X X N B N B =⎥⎦⎤⎢⎣⎡ 即b NX BX N B =+ --------有无穷解 令0=N X 则b B X bBX B B 1-==那么，约束方程组的解 ⎥⎦⎤⎢⎣⎡=-01b B X ，将其称为LP 问题的基本解。

注意：基本解不一定是可行解，若01≥-b B ,则称⎥⎦⎤⎢⎣⎡=-01b B X 为LP 问题的基本可行解，对应于基本可行解的基矩阵，称为可行基。

4、最优解：对应于某一可行基，使目标函数获得最优值的基本可行解，称为最优解。

最优解所对应的基矩阵称为最优基。

举例说明： 54321000127m ax x x x x x z ++++=第二章 线性规划 第 11 页⎪⎪⎩⎪⎪⎨⎧≥=++=++=++0,,,,300103200543604954321521421321x x x x x x x x x x x x x x约束矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1001030105400149A若取基矩阵[]⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡==100010001,,5431P P P B则非基矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=10354491N基变量⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=5431x x x X B ,非基变量⎥⎦⎤⎢⎣⎡=211x x X N⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡===-30020036011b Ib b B∴基本解为()TX 300,200,360,0,0= 是基本可行解若取基矩阵()⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡==1030540491,,2132P P P B 则⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1001002N()TB x x x X 213,,2=⎥⎦⎤⎢⎣⎡=542x x X N⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=-24208412b B()TX 0,0,84,24,20=∴ -----基本可行解注意：基本可行解与可行域的顶点坐标是一一对应的。