线性规划及单纯形法 一．选择
1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策
2. 运筹学研究的基本手段是（A ）。
A 建立数学模型
B 进行数学分析
C 进行决策分析
D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。
A 进行系统局部独立分析
B 考虑系统局部优化
C 考虑系统的整体优化
D 进行系统的整体决策
4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数
5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部
6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解
A Z min
B )min(Z -
C )max(Z -
D Z max -
7. 标准形式的线性规划问题，最优解（C ）是可行解
A 一定
B 一定不
C 不一定
D 无法确定
8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解
9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ）
A 管理问题
B 规划问题
C 决策问题
D 优化问题
10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4
11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解
12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解
13. 线性规划问题的基可行解()T
n X X X ,,1 =为基可行解的充要条件是X 的正分量所对
应的系数列向量是（B ）
A 线性相关
B 线性独立
C 非线性独立
D 无法判断
14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ）
A 唯一最优解
B 无穷多最优解
C 无界解
D 无可行解
15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ）
A 集合
B 凸集
C 顶点
D 子集
16.线性规划问题求解的时候，目标函数与某一个约束条件平行，则解的情况为（ D ） A 无穷多最优解B 无可行解C 唯一最优解D 无法确定
17.线性规划问题求解的时候,该线性规划问题有可行域，目标函数与某一个约束条件平行，则解的情况为（A ）
A 无穷多最优解
B 无可行解
C 唯一最优解
D 无法确定 18．运筹学涉及的主要领域是（C ）
A 技术问题
B 经济问题
C 管理问题
D 以上都不是 19.齐王赛马的故事运用运筹学的（C ）理论。 A 规划论B 存贮论C 博弈论D 排队论
20.工业企业生产中多台设备的看管、机修服务等问题属于（ D ） A 规划论B 存贮论C 博弈论D 排队论
21.单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['''B N b I . 其中b '
为（Ｂ ）
A I b =' B
b B b
1
'
-= C B b
b 1
'
-= D
B b ='
22. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中N '
为（C ）
A I N =' B
B
N N 1
'-= C
N B
N 1
'-= D
B N ='
23. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中P j
'
为（B ）
Ａ
I j P ='
Ｂ
P
B
P j
j 1
'
-= Ｃ
B P P j j 1
'
-= Ｄ
B j P ='
24. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中Y -'
为（D ）
Ａ
I Y =-'
Ｂ
P
B Y j
1
'-=- Ｃ
B
P Y j
1
'-=- Ｄ
B C Y
B 1
'
--=-
25. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中
σ
'N
为（A ）
Ａ
N C C B N N '
'
-=σ
Ｂ σ
σ
N
N
B 1
'-=
Ｃ
N C C N B N '
'
-=σ
Ｄ B C B N
1
'--=σ
26. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中
σ
'N
为（A ）
ＡN B C C B N N 1'--=σ ＢσσN N B N B C C 1'--=ＣN C C N B N -=σ' Ｄ B C C B N N
1
'--=σ
27. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中
σ
'N
为（A ）
ＡN Y C N N ''-=σ ＢσσN B N Y C -=' ＣY C C N B N -=σ' Ｄ Y C C B N N
'
'-=σ
28. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中
σ
'N
为（A ）
ＡP C C j B j N ''-=σ ＢσσN j B N P C -=' ＣP C C j N B N -=σ' Ｄ
P C C j B N N
-=σ
'
29. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中
σ
'N
为（A ）
ＡP B C C j B j N 1'--=σ ＢσσN j B N P C -=' ＣP C C j N B N -=σ' Ｄ
P C C j B N N
-=σ
'
30. 单纯形法的迭代计算实际上是对约束方程的系数矩阵实施行的初等变换。由线性代数知道，对矩阵]|||[I N B b 实施行的初等变换时，当B 变换为I ，由此上述矩阵将变换为
]|||['
''B N b I .其中
σ
'N
为（A ）
ＡP Y C j j N ''-=σ ＢY P C j B N -=σ' ＣP C C j N B N -=σ' Ｄ
P C C j B N N
-=σ
'
二．填空
1. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（可行解）。
2. 在线性规划问题中，图解法适合用于处理 （变量）为两个的线性规划问题。
3. 运筹学的英文缩写为（OR ）
4. 运筹学按照所解决问题性质的差别，将实际问题归纳不同类型的数学模型，分别是（线性规划）（非线性规划）（动态规划）（图与网络分析）（存贮论）（排队论）（对策论）（决策论）。
5. 运筹学研究的基本特点是（考虑系统的整体优化）（多学科的配合）以及(模型方法的应用）
6.（ 朴素）运筹学思想在我国古代最早诞生。
7. 线性规划问题求解的时候,该线性规划问题可行域是空集，则（ 无可行解）。 8. 单纯形法计算线性规划问题的时候，θ值在单纯形表的（右）侧。
9. 单纯形法计算线性规划问题的时候，是计算变量为（ｎ ）维的情况。
10. 由于计算机计算取值的时候的误差，可以对添加人工变量后的线性规划问题分为（两个阶段 ）来计算。
11. 在单纯形法计算的时候，一般要求（0≤j σ）的时候停止计算。
12. 线性规划问题化为标准形式的时候，松弛变量和剩余变量统称为（松弛变量） 13. 图解法是应用（平面作图）的方式进行求解。
14. 运筹学一词来源于《史记》中（运筹帷幄之中，决胜千里之外）。 15. 运筹学作为一门数学学科，是在（第二次世界大战期间）形成的 16. 生产计划制定是典型的（ 线性规划问题） 数学模型的应用。 17. 人事管理是典型的（ 线性规划问题） 数学模型的应用。
18. 线性规划问题在添加松弛变量之后，其在目标函数中的系数为（ 零） 19. 线性规划问题的可行解的集合称为（ 可行域）。
20. 在线性规划中，如果系数矩阵中存在（ 单位阵）,就可以直接写出初始可行基。
21.据《大英百科全书》释义：运筹学是一门应用于管理有组织系统的科学，为掌管这类系统的人提供（决策目标）和（数量分析）的工具。
22.我国《辞海》中关于运筹学的释义为：运筹学主要是研究经济活动与军事活动中能用（数量）来表达有关运用、筹划与管理方面的问题。它根据问题的要求，通过（数学分析与运算），作出综合性的合理安排，以达到较经济较有效地使用人力物力。
23.运筹学一词的英文为Operations Research,可直译为（运用研究）或（作业研究）。
24.我国从“夫运筹帷幄之中，决胜于千里之外”这句古语中，将O.R 正式译作（运筹学）。 25.西汉初年，天下已定，汉高祖刘邦赞（ 张良）说："夫运筹帷幄之中，决胜千里之外”. 26.将实际问题的数据资料代入模型，找出的精确的或者近似的解毕竟是模型的解，由于模型只是对实际问题的理想化近似，特别一些大模型难免会包含各种缺陷，需要不断完善，为了检验得到的解是否正确，常采用（回溯）的方法。
27.（管理科学）是研究人类管理活动的规律及其应用的一门综合性交叉科学，这是运筹学研究和提出问题的基础。
28.如果集合C 中任意两个点21,x x ，其连线上的所有点也都是集合C 中的点，称C 为（ 凸集）。
29.如果C 中不存在任何两个不同的点21,x x ，使X 成为这两个点连线上的一个点。或者这样叙述：对任何C x C x ∈∈21,，不存在)10()1(21<<-+=a x a ax x ，则称x 是凸集C
的（顶点）。
30.当线性规划中约束条件为“=”或“≥”时，化为标准形式后，一般约束条件的系数矩阵中不包含有单位矩阵。这时为能方便地找出一个初始的基可行解，可添加人工变量来人为地构造一个单位矩阵作为基，称做（人工基）。 三．判断
1.图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（正确）
2.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。（正确）
3.线性规划问题的每一个基解对应可行域的一个顶点（不正确）
4.线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。（正确）
5.若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。（不正确）
6.线性规划问题中添加了人工变量，问题满足最优性条件时基变量仍含人工变量，表明问题有可行解（不正确 ）
7.运筹学是一门应用于管理有组织系统的科学。（正确）
8.运筹学涉及的主要领域是管理问题，研究的基本手段是建立数学模型。（正确） 9.图形●是凸集。（正确）
10.线性规划问题求解的时候,该线性规划问题有可行域且不是闭合，则解为无界解。（不正确）
11. 判断下面的数学模型是否是线性规划
12.2
212min x x Z +=
???≥≤+0,4.2
121x x x x t s
答： 否
判断下面的数学模型是否是线性规划
13.2132m ax x x Z +=
???≥≤+0,12.2
12221x x x x t s
答： 否 14.
判断下面的数学模型是否是线性规划
32142x x x S ++=
???
??≥≤+-≥-0,,021.3
212121x x x x x x x t s
运筹学教程（胡运权主编，清华第4版）部分习题答案（第一章）1.1 （1）无穷多解：α (6/5, 1/5) + (1- α) (3/2, 0)，α∈ [0,1]。 （2）无可行解； （3）x* = (10,6)，z* = 16； （4）最优解无界。 1.2 （1）max z’ = 3x1 - 4x2 + 2x3 - 5x’4 + 5x’’4 s.t. –4x1 + x2 – 2x3 + x’4– x’’4 = 2 x1 + x2 – x3 + 2x’4– 2x’’4 + x5 = 14 –2x1 + 3x2 + x3 – x’4+ x’’4– x6 = 2 x1, x2, x3, x’4, x’’4, x5, x6 ≥ 0 （2）max z’ = 2x’1 + 2x2 – 3x’3 + 3x’’3 s.t. x’1 + x2 + x’3 – x’’3 = 4 2x’1 + x2 – x’3 + x’’3 + x4 = 6 x’1, x2, x’3, x’’3, x4, ≥ 0 1.3 （1）基解：(0, 16/3, -7/6, 0, 0, 0)； (0, 10, 0, -7, 0, 0)； (0, 3, 0, 0, 7/2, 0)，是基可行解，z = 3，是最优解； (7/4, -4, 0, 0, 0, 21/4)； (0, 16/3, -7/6, 0, 0, 0)； (0, 0, -5/2, 8, 0, 0)； (1, 0, -1/2, 0, 0, 3)； (0, 0, 0, 3, 5, 0)，是基可行解，z = 0； (5/4, 0, 0, -2, 0, 15/4)； (3/4, 0, 0, 0, 2, 9/4)，是基可行解，z = 9/4； (0, 0, 3/2, 0, 8, 0)，是基可行解，z = 3，是最优解。 （2）基解：(-4, 11/2, 0, 0)； (2/5, 0, 11/5, 0)，是基可行解，z = 43/5； (-1/3, 0, 0, 11/6)； (0, 1/2, 2, 0)，是基可行解，z = 5，是最优解；
线性规划及单纯形法 一．选择 1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策 2. 运筹学研究的基本手段是（A ）。 A 建立数学模型 B 进行数学分析 C 进行决策分析 D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。 A 进行系统局部独立分析 B 考虑系统局部优化 C 考虑系统的整体优化 D 进行系统的整体决策 4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数 5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部 6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解 A Z min B )min(Z - C )max(Z - D Z max - 7. 标准形式的线性规划问题，最优解（C ）是可行解 A 一定 B 一定不 C 不一定 D 无法确定 8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解 9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ） A 管理问题 B 规划问题 C 决策问题 D 优化问题 10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4 11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解 12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解 13. 线性规划问题的基可行解()T n X X X ,,1 =为基可行解的充要条件是X 的正分量所对 应的系数列向量是（B ） A 线性相关 B 线性独立 C 非线性独立 D 无法判断 14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ） A 唯一最优解 B 无穷多最优解 C 无界解 D 无可行解 15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ）
第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21Λj x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321Λj x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1
1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。
2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=0 ,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x 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 x
3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-= =?+?-==?+?-==?+?-=σσσσ 为出基变量。 为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110 120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 4 33 4341522max , )4 3,415(),(2112= +?=+===x x z x x X T T 故有：所以，最优解为
??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x 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 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x
第1章 线性规划与单纯形法 1、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。 ??? ??≥≥+≥++=0 x x 42x 4x 66x 4x 3x 2x minz )a (21 21212 1， ?? ? ??≥≥+≤++=0 x ,x 124x 3x 2 x 2x 2x 3x maxz )b (2121212 1 ?? ???≤≤≤≤≤++=8x 310x 5120 10x 6x x x maxz )c (21 212 1 ?? ? ??≥≤+-≥-+=0 x ,x 23x 2x 2x 2x 6x 5x maxz )d (2121212 1 2、用单纯形法求解下列线性规划问题。 ?????≥ ≤+≤++=0 x ,x 82x 5x 94x 3x 5x 10x maxz )a (21 2 121 2 1 ????? ? ? ≥ ≤+≤+≤+=0 x ,x 5x x 242x 6x 155x x 2x maxz )b (2 1 212 122 1 3、用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。 ??? ?? ??≥≥-≥+-≥+++-=0 x x x 0 x 2x 2x 2x 6 x x x 2x x 2x maxz )a (3 , 2,132 3 13213 21 ??? ??≥≥+≥++++=0 x , x ,x 6 2x 3x 82x 4x x x 3x 2x minz )b (3 21 2 1 3 21 3 21 4、已知线性规划问题的初始单纯形表（如表1所示）和用单纯形法迭代后得到的表（如表2所示）如下，试求括弧中未知数a ～l 的值。 表1
图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21 j x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
使用单纯形法解线性规划 问题 The Standardization Office was revised on the afternoon of December 13, 2020
使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1）将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ .： 1234123561371234567211 42321,,,,,,0x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2）找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一 次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表
由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为： 表四：第二次迭代后的单纯形表 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表
线性规划的单纯形法表格方法 Max. z=5x 1+2x 2+3x 3 -x 4 +x 5 s.t. x 1+2x 2+2x 3 +x 4 =8 3x 1+4x 2+x 3 +x 5 =7 x j ≥0 j=1,2,3,4,5 表1 由表的中间行可求出基本可行解，令x1=x2=x3=0,由约束条件得 x4=8,x5=7. 表中最后一行分别为： ()1787811-=+-=???? ??-=z ()3)31(53111511=+--=???? ??--=-z c ()0)42(24211222=+--=???? ??--=-z c ()4)12(31211333=+--=??? ? ??--=-z c 因为c j -z j 行中存在正值，所以当前基本可行解不是最优解。c j -z j 行中的4最大因而非基变量 X 3使z 有最大的单位增量，把X 3选作新的（换入）基变量。 为确定被换出的基变量，采用最小比值法。用X 3列的值除以约束条件的常数（8/2=4，7/1=7）。第一行有最小比值，把它叫做旋转行。第一行原来的基变量是X 4 ，此时X 4为换出基变量，新的基变量为X 3、X 5。为此需要把表中X 3对应在约束条件中系数变为单位值（1，0）。在表1中：1）用2除旋转行使X 3系数为1；2）用-1/2乘旋转行加到第二行消去X 3。 ()153123413=+=???? ??=z ()1455/2/2113511=-=???? ??-=-z c ()-4623113222=-=???? ??-=-z c ()-21-11/2-21/13-133=-=??? ? ??-=-z c 因为c j -z j 行中仍存在正值，所以当前基本可行解不是最优解。c j -z j 行中的1最大因而非基变 量X 1使z 有最大的单位增量，把X 1选作新的（换入）基变量。
单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行 void PrintAnswer();数不合法"<
相关主题
文本预览