当前位置：文档之家 › 第二章线性规划及其单纯形法习题

第二章线性规划及其单纯形法习题

  • 格式：ppt
  • 大小：615.50 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

运筹学：线性规划的数学模型与单纯形法习题与答案

运筹学：线性规划的数学模型与单纯形法习题与答案

一、单选题1、线性规划具有唯一最优解是指（）。

A.不加入人工变量就可进行单纯形法计算B.最优表中非基变量检验数全部非零C.可行解集合有界D.最优表中存在非基变量的检验数为零正确答案：B2、线性规划具有多重最优解是指（）。

A.最优表中存在非基变量的检验数为零B.可行解集合无界C.基变量全部大于零D.目标函数系数与某约束系数对应成比例正确答案：A3使函数z=−x1+x2+2x3减少得最快的方向是（）。

A. (1,－1,－2)B. (－1,－1,－2)C. 1,1,2)D. (－1,1,2)正确答案：A4、线性规划的退化基可行解是指（）。

A.基可行解中存在为零的非基变量B.基可行解中存在为零的基变量C.非基变量的检验数为零D.所有基变量不等于零正确答案：B5、线性规划无可行解是指（）。

A.有两个相同的最小比值B.第一阶段最优目标函数值等于零C.用大M法求解时,最优解中还有非零的人工变量D. 进基列系数非正正确答案：C6、若线性规划不加入人工变量就可以进行单纯形法计算（）。

A.一定有最优解B.全部约束是小于等于的形式C.可能无可行解D.一定有可行解正确答案：D7、设线性规划的约束条件为x1+x2+x3=22x1+2x2+x4=4x1，…，x4≥0则非可行解是（）。

A. (0，1，1，2)B. (2，0，0，0)C. (1，0，1，0)D. (1，1，0，0)正确答案：C8、线性规划可行域的顶点一定是（）。

A.可行解B.非基本解C.非可行解D.最优解正确答案：A9、X是线性规划的基本可行解则有（）。

A.X不一定满足约束条件B.X不是基本解C.X中的基变量非零，非基变量为零D.X中的基变量非负，非基变量为零正确答案：D10、下例错误的结论是（）。

A.检验数就是目标函数的系数B.检验数是用来检验可行解是否是最优解的数C.不同检验数的定义其检验标准也不同D.检验数是目标函数用非基变量表达的系数正确答案：A11、在解决运筹学问题时，根据对问题内在机理的认识直接构造出模型的方法称为（）。

第2章线性规划建模及其单纯形法

第2章线性规划建模及其单纯形法

目标函数 Max z =1500x1+2500x2 约束条件 s.t. 3x1+2x2≤65
2x1+x2≤40 3x2≤75 x1 ,x2 ≥ 0
7
这是一个典型的利润最大化的生产计划问题。 其中，“Max”是英文单词“Maximize”的缩写，含 义为“最大化”； “s.t.”是“subject to”的缩写，表示“满足于…”。 因此，上述模型的含义是：在给定条件限制下，求 使目标函数z达到最大的x1 ,x2的取值
a21x1 + a22x...2 + … + a2nxn≤ b2 am1x1 + am2x2 + … + amnxn≤ bm
x1 , x2 , … , xn≥0
20
•标准形式 •目标函数： Max z=c1x1 + c2x2 + … + cnxn
•约束条件： a11x1 + a12x2 + … + a1nxn=b1 a21x1 + a22x...2 + … + a2nxn=b2 am1x1 + am2x2 + … + amnxn=bm x1 , x2 , … , xn≥0
4 x1 + 2 x2 + 3 x3 - 9 x4≥ 39 6 x2 + 2 x3 + 3 x4≤-58 x1 , x3 , x4 ≥0
31
解8x3:+7首x4先；，将目标函数转换成极大化:令z=-f=3x1–5x2– 其次考虑约束，有3个不等式约束，引进松弛变量 x5 ,x6 ,x7 ≥0 ； 由于x2无非负限制，可令x2=x2’-x2”,其中x2’≥0 x2”≥0 由于第3个约束右端项系数为-58，于是把该式两端乘 以-1。 于是，我们可以得到以下标准形式的线性规划问题：
运筹学 第二章线性规划 第三讲 单纯形法

运筹学 第二章线性规划 第三讲 单纯形法

1 -2 4 2
[1] 1 2 -1↑
1 0 0 0
1 0 0 0
1 -1 -2 1
0 1 0 0
0 1 0 0
0 0 1 0
0 0 1 0
5→ 6 21
5 1 11
5 6 21/2
表中λj≥0( j=1,2,…,5), 所以最优解为X=(0,5,0,1,11 )T , 最 优值 Z=2x1－2x2－x4=－2×5－1=－11。
大值，因此原问题只要有可行解，新的线性规划问
题的最优解中人工变量的取值一定为0， 这种方
法称为大M单纯形法（简称大M法）。
2.5 单纯形法 Simplex Method
Chapter 1 线性规划 Linear Programming
大M法中加入人工变量后新的线性规划问题为
max Z’=c1x1+c2x2+…+cnxn –Mxn+1 – … –Mxn+m
【解】首先将数学模型化为标准形式
2.5 单纯形法 Simplex Method
Chapter 1 线性规划 Linear Programming
max Z 3x1 2 x 2 x3
式中x4，x5为松弛变量，x5可 4 x1 3x 2 x3 x 4 4 作为一个基变量，第一、三 x x 2 x x 10 约束中分别加入人工变量x6 、 1 2 3 5 x7 ， 目 标 函 数 中 加 入 2 x1 2 x 2 x3 1 ―Mx6―Mx7一项，得到人工 x j 0, j 1,2,,5 变量单纯形法数学模型
0 0 1
Z＝2 x1 2 x2 (6 x1 x2 ) 6 x1 x2
第二章线性规划

第二章线性规划

l j b l k 1
akl 0
关
b bk akl
j akj akl akj
k akl akj bk

i ail aij bi
bk i 0 aij ail bi ail akl akl
B 1b b [b1 , b2 , , bm ]T
（2.28）
记记
1
，
j 1, 2,, n ，
B a j a j [a1 j , a2 j , , amj ]T ,
则（2.28）可写成
x1 x2 a2 m1 xm1 a2l xl a2 n xn b2 xm amm1 xm 1 aml xl amn xn bm . a1m1 xm1 a1l xl a1n xn b1
,
x 中只有 xl bk 0 ，其余分量皆为 0。于是，由 N
（2.26）式得
z z l xl z l bk . （2.37）
z z
特别当 bk 0 时，只要 l 0 ，必有
z z
结论是： 引入判别数为正的变量， 将保证 B 的基本容许解的目标函数值不大于 B 的基本容 许解的目标函数值。
令 N
T T 1 T c B B N c N ，于是
故
因为 xN 0 ，因此，只要 N 0 ，必有 z z 。
由此得到判断基本容许解是最优解的一个充分 条件。
T z z N xN ， （2.26） T z z N xN .
有最优点
解无界
Dantzig 单纯形法的思想涉及以下三个具 体问题： 一、初始基本容许解的产生； 二、最优性准则； 三、基本容许解的改进。
第2章 线性规划与单纯形法(2)

第2章 线性规划与单纯形法(2)


max z = 20 x1 + 30 x2 3 x1 + 10 x2 ≤ 150, x1 ≤ 30, x1 + x2 ≥ 40, x1 , x2 ≥ 0.
管
max z = 20 x1 + 30 x2 − Mx6 3x1 + 10 x2 + x3 = 150, x1 + x4 = 30, x1 + x2 − x5 + x6 = 40, xi ≥ 0, i = 1, 2,..., 6
管
理
运
筹
学
4
要注意到人工变量是与松弛、剩余变量不同的。 松弛变量、剩余变量它们可以取零值，也可以取 正值，而人工变量只能取零值。一旦人工变量取 正值，那么有人工变量的约束方程和原始的约束 方程就不等价了，这样所求得的解就不是原线性 规划的解了。为了竭尽全力地要求人工变量为零， 我们规定人工变量在目标函数中的系数为－M， M 这里M为任意大的数。这样为了使目标函数实现 最大就必须把人工变量从基变量中换出。如果一 直到最后，人工变量仍不能从基变量中换出，也 就是说人工变量仍不为零，则该问题无可行解。 以下讨论如何解含有人工变量的线性规划问题
• 由于不存在单位矩阵,在第1,2个约束条件加上 一个人工变量x6,x7,并在目标函数中加上-Mx6Mx7得到的线性规划问题：
max f ' = −2 x1 − 3 x2 + 0 x3 + 0 x4 + 0 x5 − Mx6 − Mx7
x1 + x 2 − x 3 + x 6 = 3 5 0, x1 − x 4 + x 7 = 1 2 5, 2 x1 + x 2 + x 5 = 6 0 0, x1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ≥ 0 .
《运筹学》习题线性规划部分练习题及答案整理版

《运筹学》习题线性规划部分练习题及答案整理版

《运筹学》线性规划部分练习题一、思考题1.什么是线性规划模型，在模型中各系数的经济意义是什么？2 .线性规划问题的一般形式有何特征？3.建立一个实际问题的数学模型一般要几步？4.两个变量的线性规划问题的图解法的一般步骤是什么？5.求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？6.什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。

7•试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。

8•试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。

9.在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？10.大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？11 •什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？二、判断下列说法是否正确。

1.线性规划问题的最优解一定在可行域的顶点达到。

2.线性规划的可行解集是凸集。

3.如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。

4.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。

5 .线性规划问题的每一个基本解对应可行域的一个顶点。

6.如果一个线性规划问题有可行解，那么它必有最优解。

7.用单纯形法求解标准形式（求最小值）的线性规划问题时，与j' 0对应的变量都可以被选作换入变量。

8 .单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。

9.单纯形法计算中，选取最大正检验数二k对应的变量xk作为换入变量，可使目标函数值得到最快的减少。

10 . 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。

三、建立下面问题的数学模型1.某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到第三年年初都可以投资。

第二章 线性规划习题(附答案)

第二章 线性规划习题(附答案)

习题2-1 判断下列说法是否正确：（1） 任何线性规划问题存在并具有惟一的对偶问题； （2） 对偶问题的对偶问题一定是原问题；（3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；（4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；（5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。

（7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；（8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。

2-2将下述线性规划问题化成标准形式。

⎪⎪⎩⎪⎪⎨⎧≥≥-++-≤+-+-=-+-+-+-=无约束43214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()⎪⎩⎪⎨⎧≥≤≤-+-=++-+-=无约束321321321321,0,0624.322min 2x x x x x x x x x st x x x z 解：(1)令'''444x x x =-，增加松弛变量5x ，剩余变量6x ，则该问题的标准形式如下所示：'''12344'''12344'''123445'''123446'''1234456max 342554222214..232,,,,,,0z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-⎧-+-+-=⎪+-+-+=⎪⎨-++-+-=⎪⎪≥⎩ (2)令'z z =-，'11x x =-，'''333x x x =-，增加松弛变量4x ，则该问题的标准形式如下所示：'''''1233''''1233''''12334''''12334max 22334..26,,,,0z x x x x x x x x s t x x x x x x x x x x =+-+⎧++-=⎪+-++=⎨⎪≥⎩ 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

2.2 单纯形法

2.2 单纯形法


不过,若原(LP)是非退化的,则其任一个基本可行
解均是非退化的,从而不会出现此问题.
2＞ 检验数向量 有不只一个正分量. 理论上任意可选取一个正分量作为定理中的 k
0
由 Th3 , k x k : 0 1 , 目标函数的值减少 k

ˆ c x c x k
T T

T
x
目标函数的典式
令
j c B A j c j , j 1, , n 检验数
T
常数项
z0 c x cB b
T T
A1 , , Am
Aj e j

B
1
B Im
XJTU
第二章 线性规划
T T
OR
j 1, , m


T
j c B A j c j c B e j c j c j c j 0,
cB B
T 1
Ac
T
T
1 , , n
0 , cB BT 1 NhomakorabeaT
对应于 x 的
B , N
T



N cN

检验数向量
b 对应于基本可行解 x , 原标准形式(LP) 0

m in z z 0 s .t. xB B x 0
单纯形法求解原LP问题：或者求得一最优解，或者 判定原LP问题无界。
XJTU
设原LP问题为：
m in c x s .t.
T
第二章 线性规划
OR
Ax b 0 x 0
D
对此问题引入m个人工变量 x a ( x n+1 , , x n+m ) ，
第二章 线性规划典型习题

第二章 线性规划典型习题

求解如下的线性规划问题
max Z = 10 x1 + 15 x2 + 12 x3 5 x1 + 3 x2 + x3 ≤ 9 − 5 x1 + 6 x2 + 15 x3 ≤ 15 2 x1 + x2 + x3 ≥ 5 x1 , x2 , x3 ≥ 0
化标准型
max Z = 10 x1 + 15 x2 + 12 x3 5 x1 + 3x2 + x3 ≤ 9 − 5 x1 + 6 x2 + 15 x3 ≤ 15 2 x1 + x2 + x3 ≥ 5 x1 , x2 , x3 ≥ 0
max Z = 10 x1 + 15 x2 + 12 x3 − Mx7 5 x1 + 3 x2 + x3 + x4 = 9 − 5 x1 + 6 x2 + 15 x3 + x5 = 15 2 x1 + x2 + x3 − x6 + x7 = 5 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0
2 - 4 取子矩阵D 取子矩阵 3，D3 = -1 7
D3 ≠ 0
D3为一个基
对于D 基变量为X 为非基变量， 对于 3 ，基变量为 1、X4，X2、X3为非基变量，令 X2、X3=0 X1 =34/5、X4=7/5 、
可行解
P2、P3
3 -1 取子矩阵D 取子矩阵 4，D4 = 2 - 6
在每根7.4米长的原料钢筋上截取2.9米、2.1米和1.5米的料各1 在每根7.4米长的原料钢筋上截取2.9米 2.1米和1.5米的料各1 7.4米长的原料钢筋上截取2.9 米和1.5米的料各 这样每根原料就都剩下了0.9米长的废料无法利用。 0.9米长的废料无法利用 根，这样每根原料就都剩下了0.9米长的废料无法利用。 所谓合理利用原材料，就是要使废料最少， 所谓合理利用原材料，就是要使废料最少，因此考虑如何在原 材料上合理套裁，以下几种方法都是能节省材料的较好方案： 材料上合理套裁，以下几种方法都是能节省材料的较好方案：
第二章 线性规划与单纯形法

第二章 线性规划与单纯形法

max z =2x1+3x2 2x1+2x2+x3=12 x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1-6≥0
图解法
第2节 解
例8：求下述线性规划的所有基解、基可行 解及最优解。 max z =3x1+x2+3x3 x1+x2+x3＝2 x1+2x2+4x3＝6 x1，x2，x3≥0
第1节 线性规划问题及其数学模型
要求：将下列线性规划问题转化为标准型。 例4：min z =x1+2x2+3x3 -2x1+x2+x3≤9 -3x1+x2+2x3≥4 3x1-2x2-3x3=-6 x1≤0，x2≥0，x3取值无约束
第1节 线性规划问题及其数学模型
例4： x x , x x xz , z 解：令 1 13 3 3 max z′=x1′-2x2-3x3′+3x3〞+0x4+0x5 2x1′+x2+x3′-x3〞+x4=9 3x1′+x2+2x3′-2x3〞-x5=4 3x1′+2x2+3x3′-3x3〞=6 x1′，x2，x3′，x3〞，x4，x5≥0
第3节 图解法
三、图解法解的类型 唯一最优解：仅有一点使目标函数值取得最大 （小）值 无穷多（多重）最优解：线段（射线）上任意 一点都使目标函数值取得相同的最大（小）值 无界解：可行域无界，目标函数值可以增大到 无穷大 无可行解：可行域为空集 无界解和无可行解统称为无最优解

目标函数求最大值 函数约束条件全为等式 决策变量全为非负 函数约束条件右端项全为非负
线性规划(2单纯形法) (1)

线性规划(2单纯形法) (1)


X1 X 2 0 3
X4 -15 X3 9
作主元运算, 得到新的基础可行解: X(2)=(0,0,9,1,0)t S= 35
C CB -1 4 σ XB 10 3 4 X3 0 1 -1 X4 1 0 1 X5 -2 1 1 9 35 b Θ
X1 X 2 0 3
X4 -15 X3 9
判断是否最优解:X(2)=(0,0,9,1,0)T S= 35 计算检验数,所有检验数全小于零,达到最优解, X*=(0,0,9,1,0)T S = 35
=
CB B-1b
0 CN-CB B-1N
二、判别
•若检验数全小于等于零，则基B所对应 的基础可行解X就是最优解，终止。 •若存在检验数大于零，但所对应的进 基变量XS的系数向量PS小于等于零，则 原问题无最优解，终止。
•若存在检验数大于零，且对应的常数 项大于零，则需要换基迭代。
三、换基迭代 •确定进基变量XS，其中 max( Ơj | Ơj > 0 ) = Ơs
•继续寻找更优的基础可行解，进一步改进目 标函数值。当某一个基础可行解不能再改善 时，该解就是最优解。
一、已知初始可行基求最优解
线性规划标准型的矩阵形式(3)：
Max S = CX
(1-17)
s.t. AX=b
X0
(1-18)
(1-19)
a11 a12 …. a1n
b1
A=
a21 a22 …. a2n
第一行加上第二行的（-6）倍
C CB -1 1 σ XB 10 X1 3 X2 0 1 6 4 X3 0 1/3 5 -1 X4 1 0 0 1 X5 -2 1/3 0 1 3 -10 b Θ
X4 -15 X5 3 4

第二章 线性规划与单纯形法14节


2、标准形式的特征？？？
2018/10/11 10
二、 线性规划的标准形
3、线性规划的标准化方法
（1）把最小化目标函数转化为求最大化问题。 （2）约束条件右端项为负时两边同乘以－1 （3）把约束方程中的不等式转化为等式。具体做法是：对于≤的 情况，引进松弛变量，对于≥的情况，引进剩余变量。 （4）将变量中的非正限制或无限制转化为非负限制。其中，对 于无限制变量的处理：一是同时引进两个非负变量，然后用它 们的差代替无限制变量，即令 二是从约束方程 ' " xk x k xk 中任取一个包含无限制变量的等式约束，解出该变量，并把它 代入目标函数和其他约束方程中去，以消除该无限制变量。
2018/10/11
13
小
结
1.什么是线性规划，掌握线性规划在管理中的几个应用 例子 2.线性规划数学模型的组成及其特征 3.线性规划数学模型的一般表达式和标准形式。 4.
返回首页
2018/10/11
图解法
Exit
14
第二节 线性规划的图解法
1.图解法的含义 在直角坐标系中，描绘出约束条件和变量限制的公 共区域，然后通过观察确定符合目标要求的变量的取值。 2.几个概念 （ 1 ）可行解 : 由约束条件和变量取值限制围成的公共 区域中的每一个点都称为线性规划问题的可行解。 （2)可行域:所有可行解的集合，构成线性规划问题的 可行域。 (3)等值线:使目标函数取相等值的所有点的集合，称 为目标函数的等值线。 (4)法向量: 与等值线垂直的向量。分为正法向量和负 2018/10/11 15 法向量。
基：约束系数矩阵A中，m个线性无关的列向量，称为
m维实空间中的一个基。其中，每个列向量称为基向 量，全部基向量构成基矩阵（也可简称为基），剩下 的n-m个列向量称为非基向量，所有的非基向量构成 非基矩阵。

线性规划单纯形法(例题)

《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》⎪⎩⎪⎨⎧≥=++=+++++=⎪⎩⎪⎨⎧≥≤+≤++=0,,,24261553).(002max ,,0,24261553).(2max 14.18432142132143214321212121x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。

分别用图解法和单纯形）】（页【为初始基变量，选择43,x x)1000(00)0010(01)2050(12)6030(24321=⨯+⨯-==⨯+⨯-==⨯+⨯-==⨯+⨯-=σσσσ为出基变量。

为进基变量，所以选择41x x3/1)6/122/10(00)0210(03/1)3/1240(10)1200(24321-=⨯+-⨯-==⨯+⨯-==⨯+⨯-==⨯+⨯-=σσσσ为出基变量。

为进基变量，所以选择32x x24/724/528/11012/112/124/1100021110120124321-=⨯+-⨯-=-=-⨯+⨯-==⨯+⨯-==⨯+⨯-=）（）（）（）（σσσσ4334341522max ,)43,415(),(2112=+⨯=+===x x z x x X TT 故有：所以，最优解为⎪⎪⎩⎪⎪⎨⎧≥=++=+=+++++=⎪⎪⎩⎪⎪⎨⎧≥≤+≤≤+=0,,,,18232424).(0002max ,,,0,182312212).(52max 24.185432152142315432154321212121x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。

数学建模 - 第二章 线性规划及单纯形法

p j a1 j , a2 j ,, amj 为A的第j列向量
T
max s.t.
p
j 1
n
j
xj b
x0
13
§2 线性规划问题的图解法
max s.t.
z cx Ax b x0
(1) (2) (3)
定义1 在LP 问题中，凡满足约束条件(2)、(3)的 解 x = (x1,x2,…,xn)T 称为LP 问题的可行解， 所有可行解的集合称为可行解集（或可行域）。 记作 D={ x | Ax = b ,x≥0 }。 定义2 设LP问题的可行域为D，若存在x*∈D，使得 对任意的x∈D 都有c x*≥c x，则称x*为LP 问题
设 xj 没有非负约束，若 xj ≤0，可令 xj = - xj’ ，
则 xj’ ≥0；
又若 xj 为自由变量，即 xj 可为任意实数，
可令 xj = xj’ - xj’’，且 xj’ , xj’’ ≥0
11
第二章
线性规划及单纯形法
max z’= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x7≥0
x2
2x1 x2 2
x1 4x2 4
max z = 2x1 + 2x2 s.t. 2x1 – x2 ≥ 2 -x1 + 4x2≤ 4 x1，x2 ≥ 0
Note:
可行域为无界区域，
目标函数值可无限
增大，即解无界。
(１,0)
O
A
x1
称为无最优解。

第二章 线性规划及单纯形法


标准形式
目标函数： 目标函数： 约束条件： 约束条件： Max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0，bi ≥0 ，
（一）一般式
Max(min)Z=C1X1+ C2X2+…+CnXn a11X1+ a12X2+…+ a1nXn ≥(=, ≤)b1 a21X1+ a22X2+…+ a2nXn ≥(=, ≤)b2 … … … am1X1+ am2X2+…+ amnXn ≥(=, ≤)bm Xj ≥0(j=1,…,n) 0( )
三、线性规划问题的标准形式 线性规划问题的标准形式
2、约束条件不是等式的问题： 约束条件不是等式的问题： 设约束条件为
ai1 x1+ai2 x2+ … +ain xn ≤ bi
可以引进一个新的变量s ，使它等于约束右边与左 边之差
s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) (
一、问题提出
Ⅰ 设备A 设备 设备B 设备 调试工序 利润 0 6 1 2
例1生产计划问题
Ⅱ 5 2 1 1 每天可用能力 15 24 5
两种家电各生产多少, 可获最大利润? 两种家电各生产多少, 可获最大利润

线性规划和其单纯形法习题

旳最优解。若目旳函数中用 C 替代 C后，问题旳最
优解变为 X
求证： (C C)( X X 0 ) 0
0
2
5
6
2
F
0
4
5
2
0
5 已知某线性规划问题旳约束条件为
2x1 x2 x3
25
st. 4xx11
3x2 7 x2
x3
x4 2x4
x5
30 85
x1 x2 x3 x4 x5 0
判断下列各点是否为该线性规划问题可行域上旳顶点：
X (5,15, 0, 20, 0)
X (9, 7, 0, 0,8) X (15, 5,10, 0, 0)
项目 X1 X2 X3 X4
X5
X4 6 (b) (c) (d) 1 0
X5 1 -1
3 (e) 0 1
Cj-ZJ
(a) -1 2
00
X1 (f) (g) 2 -1 1/2 0
X5 4 (h) (i) 1 1/2 1
Cj-ZJ
0
-7 (j) (k) (l)
6、设 X 0 是线性规划问题 max z CX , AX b, X 0
x1 0, x2 0, x3无约束
3 对下述线性规划问题找出全部基解，指出那些是基可行 解，并拟定最优值。
min
Z
5x1
2x 2
3x 3
2x 4
x 2x 3x 4x 7
s.t. 21x1
2
2x 2
3
x 3
4
2x 4
3
x 0( j 1,...., 4) j
4、已知线性规划问题 :
性规划旳目旳函数为 max Z 5x1 3x2约束形式为

运筹学第四版第二章线性规划及单纯形法


方案的制定受到那些现实条件制约：
确定约束条件
人力资源（劳动力）的限制： 9x1 4x2 360
设备工时的限制：
4x1 5x2 200
原材料资源的限制：
3x1 10x2 300
此外，决策变量的取值不应为负值即 x1 0, x2 0
6
综上所述，我们得到了这个问题的数学模型
目标函数 约束条件
大？
项目
Ⅰ
设备A (h)
0
设备B (h)
6
调试工序(h) 1
利润（元） 2
Ⅱ 每天可用能力
5
15
2
24
表1-2
1
5
1
12
其数学模型为：
max Z 2x1 x2
5x2 15
6xx11
2x2 x2
24 5
x1, x2 0
13
例3：捷运公司在下一年度的1～4月份的4个月内拟租用仓库
堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租
借费用随合同期而定，期限越长，折扣越大，具体数字见表
1-4。租借仓库的合同每月初都可办理，每份合同具体规定
租用面积和期限。因此该厂可根据需要，在任何一个月初办
理租借合同。每次办理时可签一份合同，也可签若干份租用
面积和租用期限不同的合同。试确定该公司签订租借合同的
最优决策，目的是使所租借费用最少。
14
max Z 70 x1 120 x2
9x1 s.t. 43xx11
x1,
4x2 5x2 10x2 x2 0
360 200 300
资源约束
非负约束
其中 约束条件可记 s.t (subject to), 意思为“以… 为条件“、”假定“、”满足“之意。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2、将下述线性规划问题化成标准形式
min Z 2 x1 2 x2 3 x3 x1 x2 x3 4 st. 2 x1 x2 x3 6 x 0, x 0, x 无约束 2 3 1
3 对下述线性规划问题找出所有基解，指出那些是基可行 解，并确定最优值。
25 2 x1 x2 x3 x 3 x x4 30 1 2 st. 4 x1 7 x2 x3 2 x4 x5 85 x2 x3 x4 x5 0 x1
判断下列各点是否为该线性规划问题可行域上的顶点：
X (5,15, 0, 20, 0) X (9, 7, 0, 0,8) X (15,5,10, 0, 0)
2 用单纯形法求解下列线性规划问题 max Z 2 x1 x2 x3
x2 x3 60 3x1 x x2 2 x3 10 1 st. x2 x3 20 x1 x j 0 ( j 1, 2,3)
max Z 6 x1 2 x2 10 x3 8 x4 6 x2 4 x3 4 x4 20 5 x1 3x 3x2 2 x3 8 x4 25 1 st. 2 x2 x3 3x4 10 4 x1 x j 0 ( j 1, 2,3, 4)
优解变为 X 求证：
(C C)( X X ) 0
0


X3
(d) (e) 2
X4
1 0 0
X5
0 1 0
Cj-ZJ X1 X5
(f)
4
(g)
(h)
2
(i)
-1
1
1/2
1/2
0
1
Cj-ZJ
0
-7
(j)
(k)
(l)
精品课件！
精品课件！
6、设
X
0
是线性规划问题

max z CX , AX b, X 0
C 的最优解。若目标函数中用 代替 C后，问题的最
1
2 3 4
下表中所列的解均满足约束条件1-3，试指出表中哪些是可行 解，哪些是基解，哪些是基可行解。
序号 A X1 2 X2 4 X3 3 X4 0 X5 0
B
C D E F
10
3 1 0 0
0
0 4.5 2 4
-5
2 4 5 5
0
7 0 6 2
4
4 -0.5 2 0
5 已知某线性规划问题的约束条件为
min Z 5 x1 2 x2 3x3 2 x4 x1 2 x2 3x3 4 x4 7 s.t. 2 x1 2 x2 x3 2 x4 3 x 0( j 1,...., 4) j
4、已知线性规划问题 :
max Z x1 3x2 x1 x 2 x 1 2 st. x2 x1 ... x3 x4 x5 x5 0 5 10 4

X1
X3 X1 Cj-Zj (1)a~g的值 2 a c d b
X2
0 e -1
X3
1 0 f
x4
1/5 1 g
(2) 表中给出的解是否为最优解
5、已知某线性规划问题的初始单纯形表和用单纯刑法迭代 后得到的表如下所示1
(b) -1 (a)
X2
(c) 3 -1
3、求解线性规划问题当某一变量的取值无约束时，通 常用 x j
x x
' j
'' j
来替换，其中
。 x'j 0 ，x''j 0
试说明，能否在基变量中同时出现，为什么？
4、 下表为用单纯形法计算时某一步的表格。已知该线 性规划的目标函数为 max Z 5x1 3x2约束形式为 x3、x4为松弛变量，表中解代入目标函数后得Z=10
课后练习（二）
1、分别用图解法和单纯形法求解下述线性规划问题，并 指出单纯形法迭代的每一步相当于图解法可行域中的哪一 个顶点
max Z 2 x1 x2 3 x1 5 x2 15 st. 6 x1 2 x2 24 x ,x 0 1 2
max Z 10 x1 5 x2 3 x1 4 x2 9 st. 5 x1 2 x2 8 x ,x 0 1 2