线性规划及单纯形法 一．选择
1. 运筹学应用分析、试验、（ ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策
2. 运筹学研究的基本手段是（ ）。
A 建立数学模型
B 进行数学分析
C 进行决策分析
D 建立管理规范 3. 运筹学研究的基本特点是（ ）。
A 进行系统局部独立分析
B 考虑系统局部优化
C 考虑系统的整体优化
D 进行系统的整体决策
4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（ ） A 表达式 B 约束条件 C 方程变量 D 价值系数
5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ ） A 边 B 平面 C 顶点 D 内部
6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（ ）的线性规划问题求解
A Z mi n
B )min(Z -
C )max(Z -
D Z max -
7. 标准形式的线性规划问题，最优解（ ）是可行解
A 一定
B 一定不
C 不一定
D 无法确定
8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ ）。 A 最优解 B 基可行解 C 可行解 D 基解
9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（ ）
A 管理问题
B 规划问题
C 决策问题
D 优化问题
10. 在线性规划问题中，图解法适合用于处理变量（ ）个的线性规划问题 A 1 B 2 C 3 D 4
11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解
12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（ ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解
13. 线性规划问题的基可行解()T
n X X X ,,1 =为基可行解的充要条件是X 的正分量所对
应的系数列向量是（ ）
A 线性相关
B 线性独立
C 非线性独立
D 无法判断
14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（ ）
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.212221x x x x t s
答： 否 14.
判断下面的数学模型是否是线性规划
32142x x x S ++=
???
??≥≤+-≥-0,,021.3
212121x x x x x x x t s
答：否
15.在线性规划问题里，Ｃ代表的是技术系数。（不正确） 16.在线性规划问题里，j i a 代表的是价值系数。（不正确）
17.线性规划问题的一般数学模型里，对变量没有约束要求。（不正确） 18.大Ｍ法就是人工变量法。（不正确）
19.两阶段法也是添加人工变量法求解的方法。（正确）
20.数据包络分析是一种对具有相同类型决策单元进行绩效评价的方法。（正确） 20.数据包络分析简称DEA.（正确）
22. 建立模型是运筹学应用的核心，辅助决策则是运筹学方法的精髓。（不正确）。 23.运筹学模型可以选择建立数学模型或者模拟模型。（正确）
24.目前运筹教材中的算法主要是求最优解，实际上管理问题的解只要满意或对最优解的足够近似即可。（正确）
25.网络计划比甘特图更能从系统的观点解释了工序间的联系和制约，为计划的控制优化提供了科学的依据。（正确）
26.运筹学是数学同管理学科间的重要桥梁，因而掌握运筹学的思想、模型、方法对管理工作者的成长将起到深远影响。（正确） 27.丁渭修皇宫的方法是属于朴素运筹学。（正确） 28.运筹学的研究不涉及多学科的配合。(不正确) 29.运筹学的研究讲究实验的方法。（不正确）
30.运筹学是从数量上揭示管理活动规律，促进管理科学发展的唯一学科。（不正确） 30．线性规划问题的唯一解法就是单纯形法。（不正确） 31.
四、名词解释
1.系统：所谓系统可以理解为是由相互关联、相互制约、相互作用的一些部分组成的具有某种功能的有机整体。
2.模型：是真实系统的代表，是对实际问题的抽象概括和严格的逻辑表达。模型表达了问题中可控的决策变量、不可控变量、工艺技术条件及目标有效度量之间的相互关系。
3.回溯的方法：即是将历史的资料输入模型，研究得到的解语历史实际的符合程度，以判断模型是否是正确。当发现有较大误差时，要将实际问题同模型重新对比，检查实际问题中的重要因素在模型中是否已考虑，检查模型中各公式的表达是否前后一致，检查模型中各参数取极值情况时问题的解，以便发现问进行修正的一种方法。
4.线性规划问题：经营管理中如何有效地利用现有人力物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力去实现。这类统筹规划的问题用数学语言表达，要建立目标函数及问题的约束条件，当变量连续取值，且目标函数和约束条件均为线性时，称此类模型为线性规划模型。
5.目标函数： 在经营管理中，对线性规划问题进行建立数学模型，根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式表示称为目标函数。
6.约束条件：在经营管理中，对线性规划问题进行建立数学模型，其中对问题的限制条件用有关变量的等式或不等式表达被称为约束条件。
7.非线性规划问题：如果在经营管理中，所建立的模型中目标函数及约束条件不全是线性的，对这类模型的研究便构成了非线性规划的问题。
8.动态规划问题：有些经营管理活动由一系列阶段组成，在每个阶段依次进行决策，而且各阶段的决策之间互相关联，因而构成一个多阶段的决策过程。动态规划则是研究一个多阶段决策过程总体优化的问题。
9.图与网络分析问题：生产管理中经常碰到工序间的合理衔接搭配问题，设计中经常碰到研究各种管道、线路的通过能力以及仓库、附属设备的布局问题。运筹学中把一些研究的对象用节点表示，对象之间的联系用连线（边）表示，点边的集合构成图。如果给图中各边赋予某些具体的权数，并指定了起点和终点，称这样的图为网络图。
10.存贮论问题：为了保证企业生产正常进行，需一定数量材料和物资的储备。存贮论则是研究在各种供应和需求条件下，应当在什么时间，提出多大的订货量来补充储备，使得应于采购、贮存和可能发生的短缺的费用损失的总和为最少等问题的运筹学分支。
11.排队论问题：是一种研究排队服务系统工作过程优化的数学理论和方法。在这类系统中，服务对象何时到达以及系统对每个对象的服务时间是随机的。排队论通过找出这类系统工作特征的数值，为设计新的服务系统和改进现有系统提供数量依据。工业企业生产中多台设备的看管、机修服务等都属于这类服务系统。
12.博弈论问题：也称对策论，是一种用来研究具有对抗性局势的模型。在这类模型中，参与对抗的各方均有一组策略可供选择，对策论的研究为对抗各方提供为获取对自己有利的结局应采取的最优策略。
13.决策论问题：在一个管理系统中，采用不同的策略会得到不同的结局和效果。由于系统状态和决策准则的差别，对效果的度量和决策的选择也有差异。决策论通过对系统状态的性质、采取的策略及效果的度量进行综合研究，以便确定决策准则，并选择最优的决策方案。 14.规划问题：生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的规划问题。
15.数学模型：是对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设，并运用适当数学工具得到的一个数学结构。
16.决策变量：指决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。 17.可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。 18.最优解：使目标函数达到最大值的可行解。
19.基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。
19.基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。
20.基可行解：满足变量非负的基解称为基可行解 21.可行基：对应于基可行解的基称为可行基
五．问答
1.写出线性规划问题的标准形式。（简写形式）
?????=≥===∑∑==），，（），，（n j x m i b x a x c z j
i n
j j ij n
j j
j 1 01
max 1
1
线性规划问题的标准形式。（向量形式）
CX z =max
??
???≥=∑=0.1X b x P t s n
j j j 线性规划问题的标准形式。（矩阵形式）
2.用向量形式表达线性规划问题的 一般形式。
CX z =m in)m ax (或
??
???≥≥=≤∑=0)(.1X b x P t s n
j j j ，
或 式中：()?
???????????=??????
????????=
????????????==m mj j j n n b b b b a a a Pj x x x X c c c C 21212121;;;,,,
答：
CX z =max
??
?≥=0
.X b
AX t s
3.用矩阵形式表达线性规划问题的一般形式。
CX z =)m in m ax (或
???≥≥=≤0
),(.X b AX t s 或 ????????????=mn m m n n a a a a a a a a a A 2
12222111211
4.用简写形式表达线性规划问题的一般形式。
5.写出线性规划问题最优性检验和解的判别。
答：(1) 当所有的0≤j σ 时，现有顶点对应的基可行解即为最优解。
(2) 当所有的0≤j σ 时，某一非基变量检验数0=s σ，s P 列向量中至少存在一个元素
0>is a ，该线性规划问题有无穷多最优解。
(3) 如果存在某个0>j σ，又j P 向量的所有分量0≤j i a ，这时线性规划问题存在无界解。 (4) 当所有的0≤j σ时，人工变量仍留在基变量中且不为零，该线性规划无可行解。
6.在线性规划模型中各系数的经济意义是什么。 答：
j x 为决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。
为目标函数:指问题要达到的目的要求，表示为决策变量的函数。 大括号里为约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。
?????=≥=≥=≤=∑
∑
==），，（），，（），（或）（或n j x m i b x a x c z j i n j j ij n j j
j 1 01 min max 1
1n
n x c x c x c z +++=...m in m ax 2211 ?????
????≥≥=≤+++≥=≤+++≥=≤+++0,,,,............
,..., (21221)
12222212111212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a L L z ）（或min max
j C 为价值系数；i b 为右端常数项是某种资源的限制；ij a 为技术系数。
7.两个变量的线性规划问题的图解法的一般步骤是什么？ 1）建立平面直角坐标系 2）根据约束条件找出可行域 3）图示目标函数 4）确定最优解
8.什么是线性规划的标准型？如何把一个非标准形式的线性规划问题转化成标准形式。
1） 目标函数求极小值：
令z Z -='
，即化为
2） 约束条件为不等式：
A 当约束条件为“≤”时，加上松弛变量
B 当约束条件为“≥”时，减去剩余变量 3） 取值无约束的变量
令'
''x x x -=，其中0,0'''≥≥x x
4）变量0≤j x
令j j x x -='
，显然0'≥j x
9.写出线性规划问题的可行解、基、最优解、基解、基可行解、可行基的概念。 答：可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。 最优解：使目标函数达到最大值的可行解。 基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。
基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。
基可行解：满足变量非负的基解称为基可行解 可行基：对应于基可行解的基称为可行基
?????=≥===∑
∑
==），，（），，（n j x m i b x a x c z j
i n
j j ij n
j j
j 1 01
max 1
1∑==n
j j
j x c z 1min (
)
∑∑
==-=-=-=-='n j j j n j j j x c x c z z z 1
1min )max(max
10.试述单纯形法的计算步骤。
1）非标准形式的线性规划问题首先要化成标准形式。 2）求出线性规划的初始基可行解，列出初始单纯形法表。 3）进行最优性检验 如果表中，所有检验数
0≤j σ，则表中的基可行解就是问题的最优解，计算到此为止，
否则转入下一步。
4）从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表。 5）重复第二、三步一直到计算终止。
11.在什么样的情况下采用人工变量法？人工变量法包括哪两种解法？
答：1）当非标准形式的线性规划问题化为标准形式后，如果在约束方程的系数矩阵中包含一个单位矩阵。选这个单位矩阵作为初始基，使得求初始基可行解和建立初始单纯形表都十分方便。但当线性规划的约束条件都是等式，而系数矩阵中又不包含有单位矩阵时，往往采用添加人工变量的方法来人为构造一个单位矩阵。当约束条件是“≥”的情况下，可以先在不等式左端减去一个大于等于零的剩余变量（也可称为松弛变量）化为等式，然后再添加一个人工变量。
2）人工变量法包括大M 法和两阶段法。
12.大M 法中，M 的作用是什么？对最大化问题，在目标函数中人工变量的系数取什么？ 答：1）约束条件中添加人工变量后，对任何可行解，这些等式约束必须满足，因此在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为足够大的一个负值，用“-M ”代表，只要当人工变量的取值不为零，目标函数就不可能极大化。对剩余变量，因实质上也是松弛变量，因此目标函数中的系数也为零。 2）对最大化问题，在目标函数中人工变量的系数取零。
13.图解法求解两个线性规划问题的解题思路和几何上的直观得到的一些概念判断，对求解一般线性规划问题的单纯形法的启示是什么？ 答：（1）求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解、无可行解；
（2）若线性规划问题的可行域存在，则可行域是一个凸集；
（3）若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多的话）一定能够在可行域（凸集）的某个顶点找到；
（4）解题思路是，先找到凸集的任一顶点，计算在顶点处的目标函数值，比较周围相邻顶点的目标函数值是否比这个值更优，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更优的另一顶点，重复上述过程，一直到找到使目标函数达到最优的顶点为止。
14.围绕着模型的建立、修正与应用，运筹学研究的步骤分为哪几点？（6分） 答：（共6分，每点1分）（1）分析与表述问题（2）建立模型（3)对问题求解（4）对模型和由模型导出的解进行检验（5）建立起对解的有效控制(6）方案的实施。
15.松弛变量或剩余变量在实际问题中分别表示的是什么？
答： .松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超用的资源数，均未转化为价值和利润，所以引进模型后他们在目标函数中的系数均为零。
六、计算
1.用图解法求下列线性规划问题
5）2193m ax x x Z +=
s.t ?????
????≥≤-≤≤+-≤+0
,0
5264
223212
122121x x x x x x x x x
x2
L1
L4
L2
L3
Z
(10,4)
MaxZ 与L1重合，有无穷多最优解66max *
=Z
2) 2143m ax x x Z +=
?
???
???
≥≤+≤+≤+-0
,16212282.21212121x x x x x x x x t s 解：
L1
L2
L3
(20/3,8/3)
唯一最优解()38,320，3
230max =Z 。
7）21200100m ax x x Z +=
???????≥≤+≤≤+0
,120062200500.2121121x x x x x x x t s
x2
L1
L3
200
500
()3400,200；有唯一最优解3140000
m ax =Z 。
8) 2184m ax x x Z +=
??
?
??≥≥+-≤+0
,81022.212121x x x x x x t s
x1
x25
8
5
无可行解
5)?????
?
?≥≥-≥+≥++=0,4212642468.max 2
1221212
1x x x x x x x x x t s
Maxz 为无界
x2
x14
(3/2.2)
L1
L2
Z
L3
2. 单纯形法求解(唯一解） 1).
j
c
2 1 0
0 0
θ
B C
B X
b
1x
2x
3x
4x
5x
3x
15 0 5 1 0 0
—— 0
4x
24 [6] 2 0 1 0 4 0
x 5
5
1 1 0 0 1
5 j
j z c -
2
1 0 0 0
0 3x
15 0 5 1 0 23
3 2 1x
4 1 1/3 0 1/6 0 12 0
x 5
1
[2/3]
-1/6
0 3/2 j
j z c -
16-
↑-1
1 0
3x
15/2 0 0 1 -1/4 -15/2 2 1x
7/2 1 0 0 1/4 -1/2 1
x 2
3/2
0 1 0
-1/4 3/2 j
j z c -
-1/4
-1/2
12
2121212max 2 5 156224
5 ,0z x x x x x x x x x =+ì?￡???+??í?+????3???
4
93
Q 2Q 1Q Z 581
L 2
L
3
217m ax ,23,2721===Z x x
1.用图解法与单纯形法求解，并指出每步迭代时映的点
???
??≥≤+≤++=0,825943.510max 2
12
211
212
1x x L x x L x x t s x x z
标准化
???
??≥=++=+++++=0,,,825943.00510max 4
3214213214321x x x x x x x x x x t s x x x x z
→j c
10
5 0 0
B c
基
b 1x
2x
3x
4x
0 3x
9 3 4 1 0 0
4x
8
5 2 0 0 j σ
10
5
→j c
10
5 0 0
B c
基
b
1x
2x
3x
4x
3x
5
21 0
5
14 1
5
3-
相对于Q 1点
相对于Q 2点
1x =1 2x =2/3 3x =0 4x =0
Maxz=17.5 2.
???????≥≤+≤≤++=0
,120062200500
.200100max 2132121
12121x x L x x L x L x x t s x x z
10
1x 5
8 1 5
2 0 5
1 j σ
1
-2
→j c
10
5 0 0
B c
基
b
1x
2x
3x
4x
5 2x
2
3 0 1 14
5 14
3- 10
1x 1
1 0 7
1- 7
2 j σ
1
14
5- 14
25-
Q 1
Q 2
3
L 1L 2
L 500
200
1
x 2
x
标准
??????
?≥=++=+=++0
,,,,120062200500543215214
1321x x x x x x x x x x x x x →j c
100 200 0 0 0
B C
基
b 1x
2x
3x
4x
5x
θ
0 3x
500 1 1 1 0 0 500 0 4x 200 1 0
0 1 0 — 0
5x
1200
2 []6
0 0 1 200 j σ
100
200
O 点
→j c
100 200 0 0 0
B C
基 b 1x
2x
3x
4x
5x
θ
0 3x
300 3
2 0 1 0 6
1- 450 0 4x 200 []1
0 0 1 0
200 200
2x
200
3
1 1 0 0 6
1 600
j σ
3
100 0
3
100-
1Q
→j c
100 200 0 0 0
B C
基
b 1x
2x
3x
4x
5x
θ
0 3x
3
500 0 0 1 3
2- 6
1- 100 1x 200 1 0 0 1
200
2x
3
400 0 1 0 3
1- 6
1
j σ
3
100- 3
100-
2Q
1x =200，2x =400/3,3x =500/3
3
1400003
400
200200100200100max 2
1=
?+?=+=x x z 2). 3).
??????
?≥≤≤+≤+-+=0
,2 - 102 42 42max 2121212121x x x x x x x x x x z ???????≥≥+-=++-+=0
,,10 5 27 532max 321321321321x x x x x x x x x x x x z
六. 将下述线性规划模型化为标准形式： 1.
化标准型
x x x z 3
2122min +-=
2.
?????
?
?≤≥≥+--=+-≤++++++=无约束
x x x x x x x x x x x x x x x x x x t s z 423
142132143214321,0,0,1
228
5327.32max ??
???
?
?≤≥≥+--=+-≤++++++=Z 无约束x x x x x x x x x x x x x x x x x x st 423,142132143214321,0,012285327
32max )2
解：令
```,`4
4
4
2
2
x x x x x -=-=
x x x x x x x x x M M z 8
7654432100```3`2max -+-+-++-=
?????
?
?=≥=+--+-=+---=+-++-)8,,1(,01``2`2285`327````.8744316321544321 j t s x x x x x x x x x x x x x x x x x j
????? ??-------110022201001000532000111111
??????
?≥-=--≥++≤++++-=取值无约束
321321321321321,0,6
3234
2 39
232min x x x x x x x x x x x x x x x z ()??
???????
??≥=++-+=+-+++-+-+=≥-==Z -=Z ???
??≥≤≤++-=++-+-=0111-11101-1110,,",',,'6"'`4"''0``2`2`2max 0",'"';-';';,0,064
22max )154332153321433215
4
332113333311321
3213213
21x x 其约束系矩阵如下：解无约束
x x x x x x x x x x x x x x x x x x
x x x x z x x x x x x x x x x x x x x x x x st M st Z
《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
线性规划及单纯形法 一．选择 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 ）
一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 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
实验报告 课程名称：运筹学导论 实验名称：线性规划问题实例分析专业名称：信息管理与信息系统 指导教师：刘珊 团队成员：邓欣(20112111 蒋青青(20114298 吴婷婷(20112124 邱子群(20112102 熊游(20112110 余文媛(20112125 日期：2013-10-25 成绩：___________
1．案例描述 南部联盟农场是由以色列三个农场组成的联合组织。该组织做出了一个关于农场农作物的种植计划，如下： 每一个农场的农业产出受限于两个量，即可使用的灌溉土地量和用于灌溉的水量。数据见下表： 适合本地区种植的农作物包括糖用甜菜、棉花和高粱。这三种作物的差异在于它们每亩的期望净收益和水的消耗量不同。另外农业部门已经制定了南部联盟农场作物总亩数的最大配额，见下表： 作物的任何组合可以在任何农场种植，技术部门的任务是找出一个种植方案使南部联盟农场的净收益最大化。 2.建立模型 决策变量为Xi(i=1,2,……,9,表示每个农场每种作物的种植量。 MAX Z=1000(X1+X2+X3+750(X4+X5+X6+250(X7+X8+X9 约束条件： （1）每一个农场使用的土地 X1+X4+X7≤400
X2+X5+X8≤600 X3+X6+X9≤300 (2每一个农场的水量分布 3X1+2X4+X7≤600 3X2+2X5+X8≤800 3X3+2X6+X9≤375 (3每一种作物的总种植量 X1+X2+X3≤600 X4+X5+X6≤500 X7+X8+X9≤325 非负约束Xi≥0 , i=1,2, (9) 3.计算机求解过程 步骤1.生成表格 步骤2.输入数据
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=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、线性规划问题及数学模型 2、线性规划问题的解及其性质 3、图解法 4、单纯形法 5、大M 法和两阶段法 重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。 要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握 其求解技巧；培养解决实际问题的能力。 §1 线性规划的数学模型及解的性质 一、数学模型（一般形式） 例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？ 解：设三种体系的建筑面积依次为1x ,2x ,3x 万平方米， 则目标函数为 321max x x x z ++= 约束条件为 ?? ?? ???????=≥≤++≤≤++≤++≤++3,2,10 4005.335.41470021015000 180190110200025301211000 122137105 3211321321321j x x x x x x x x x x x x x x j 例2 某工厂要安排生产甲、乙两种产品。已知：
问：如何安排两种产品的生产数量，才能使总产值最高？ 解：设 21,x x 分别为甲、乙两种产品的生产量： 则目标函数为 21127m ax 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) 约束条件 ()()()????? ????=≥=≥≤+++=≥≤+++=≥≤+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,0,,,22112222212111212111 可行解：满足约束条件的一组决策变量，称为可行解。 最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。 二、标准型 （一）问题的标准形式： n n x c x c x c z +++= 2211ma x ????? ?? ??=≥=+++=+++=+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,022112222212111212111
第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）??? ??≥≥+≥++=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，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表
运筹学 线性规划基本性质
线形规划基本性质目录 线性规划（概论） 线性规划问题:生产计划问题 例1.1 生产计划问题（资源利用问题）例1.1生产计划问题分析 例1.1生产计划问题模型 例1.1生产计划问题表格描述 例1 .2 营养配餐问题 各种食物的营养成分表 各种食物的营养成分表（转置） 例1 .2 营养配餐问题求解 用于成功决策的实例 线形规划的一般模型:特点 线形规划的一般模型:数学模型线性规划问题隐含的假定 比例性假定 可加性假定 连续性假定 确定性假定 线形规划的图解法 线形规划解的可能结果 线形规划的标准形式1 线形规划的标准形式2 非标准型LP的标准化:目标函数 非标准型LP的标准化:约束函数1 非标准型LP的标准化:约束函数2 非标准型LP的标准化:决策变量 线形规划解的概念：可行解 线形规划解的概念：最优解 线形规划解的概念：基本解 线形规划解的概念：最优基本解 线形规划的应用模型 生产计划问题 生产计划问题：表格分析 生产计划问题：模型 产品配套问题 产品配套问题：工时分析 产品配套问题：配套分析 产品配套问题：模型 结束放映
线性规划（概论） 线形规划是研究解决有限资源最佳分配的运筹学方法，即如何对有限的资源做出最佳方式的调配和最有利的利用，以便最充分地发挥资源的效能去获得最佳经济效益。
线性规划问题:生产计划问题 1、如何合理使用有限的人力、物力和资 金，实现最好的经济效益。 2、如何合理使用有限的人力、物力和资 金，以达到最经济的方式，完成生产 计划的要求。
例1.1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/张，椅子销售价格30元/把，生产桌子和椅子要求需要木工和油漆工两种工种。生产一张桌子需要木工4小时，油漆工2小时。生产一把椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？
线性规划的单纯形法表格方法 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选作新的（换入）基变量。
线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本内容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决
单纯形法求解线性规划的步骤 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();数不合法"< 一、需要掌握的主要内容 1、单纯形法的计算过程 （1）确定初始基本可行解 （2）最优性检验； （3）基变换。 2、单纯形法的灵敏度分析 （1）最终单纯形表中，变量系数的灵敏度分析针对最优解不变时，判断其变化范围； （2）约束条件常数项b的灵敏度分析针对最优解不变时，判断其变化范围； （3）增加一个变量的灵敏度分析 首先，确定增加变量在初始单纯形表中的系数列P j ；然后，求出其对应在最终单纯形表 中的系数列P j ；最后求出σ j =C j -C B B-1P j 。 若σ j ≤0，则最优解不变；σ j ≥0，则继续进行基变换，直到求出最优解。 二、需要基本掌握的内容 1、解、基本解、可行解、基本可行解等基本概念； 2、利用单纯形法求解如何判断无可行解、无界解和无穷最优解等基本理论； 3、如何写出一个线性规划的对偶问题； 4、对偶单纯形法的基本思路和过程。 一、填空题 （1）线性规划模型中，松弛变量的经济意义是，它在目标函数中的系数是。 （2）设有线性规划问题：max z=CX AX≤b X≥0 有一可行基B，记相应基变量为X B ,非基变量为X N ，则可行解的定义为，基本可行 解的定义为，B为最优基的条件是。 （3）线性规划模型具有可行域，若其有最优解，必能在上获得。 二、选择题 1．线性规划一般模型中，自由变量可以用两个非负变量的（）代换。 A．和 B．差 C．积 D．商 2．满足线性规划问题全部约束条件的解称为（） A．最优解 B．基本解 C．可行解 D．多重解 3．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得（） A．多重解 B．无解 C．无界解 D．退化解 4．原问题与对偶问题的（）相同。 A．最优解 B．最优目标值 C.解结构 D．解的分量个数 5.记线性规划原问题（p）max z=CX，对偶问题（D） min w=Yb AX≤b YA≥C 1 人力资源分配的问题 例1.某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段开始时上班，并连续工作八小时，问该公交线路怎样安排 司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 分析：不同上班班次时段的司机和乘务人员数 （图见书） 解：设 xi 表示第i 班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 ?? ? ??? ???? ? =≥≥+≥+≥+≥+≥+≥++++++=6,,2,1030205060 7060.6554433221616 54321 j x x x x x x x x x x x x x t s x x x x x x minZ j 且为整数 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？ 解：设xi ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 （图见书） ?? ? ??? ? ? ???? ?=≥≥++++≥++++≥++++≥++++≥++++≥++++≥++++++++++=7,6,,2,1028311925241528.432173217621765176547654365432543217654321 j 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 x x x x x x x x t s x x x x x x x minZ j 且为整数 约束条件：目标函数： 2 生产计划的问题 例3.某企业生产甲、乙、丙三种产品，每一产品均须经过A 、B 两道工序。A 工序有两种设备可完成，B 工序有三种设备可完成，除甲产品和乙产品的A 工序可随意安排外，其余只能在要求的设备上完成。加工单位产品所需工序时间及其他各项数据的费用有关资料见下表。试制订利润最大的产品加工方案。 （图见书） 解：用8个单下标变量分别表示3种产品在相应工序中的生产量，如表所示。 在约束条件中需考虑 x1+x2=x3+x4+x5 线性规划模型的目标函数为： max z=[(1.25-0.25)(x1+x2)+(2-0.35)(x6+x7)+(2.8-0.5)x8] - [0.05(5x1+10x6)+0.0321(7x2+9x7+12x8)+0.0625(6x3+8x6+8x7)+0.111857(4x4+11x8)+0.05×7x5] 即:max z=0.75x1+0.7753x2+0.65x6+0.8611x7+0.6844x8-0.375x3-0.4474x4-0.35x5 该问题线性规划模型为： max z= 0.75x1+0.7753x2+0.65x6+0.8611x7+0.6844x8-0.375x3-0.4474x4-0.35x5 ? ????? ??? ??=≥=---+≤≤+≤++≤++≤+8 ,,2,1004000770001144000886100012976000105..543215 8476387261 j x x x x x x x x x x x x x x x x x t s j 3 套裁下料问题 例4.现要做100套钢架，每套用长为2.9m,2.1m 和1.5m 的圆钢各一根。已知原料长7.4m ，问应如何下料使所用料最省？ 若用套裁，下面有几种套裁方案，都可以考虑采用 第五章线性规划在管理中的应用 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： + + 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1 + x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= + + 3、本问题的线性规划数学模型 max z= + + S．T． 8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1 + x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析 目标函数最优值为 : 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围 : 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限 .25 .333 常数项数范围 : 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 150 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润元/件，提高到元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格，0，表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在元/件以上，新产品Ⅱ的利润在到之间，新产品Ⅲ的利润在以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在到工时之间。各自每增加一个工时对总利润的贡献元，0元，元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= + + S．T． 8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1 + x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：元。 灵敏度报告： 目标函数最优值为 : 变量最优解相差值 x1 44 0 x2 10 0 x3 18 0 约束松弛/剩余变量对偶价格运筹学线性规划习题.doc
运筹学线性规划
运筹学 线性规划在管理中的应用案例
相关主题
文本预览