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

1 第一章 线性规划及单纯形法习题

1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。

（1）0,42266432min21212121xxxxxxxxz (2)

0,12432223max21212121xxxxxxxx

(3)

83105120106max212121xxxxxxz (4)

0,2322265max12212121xxxxxxxxz

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

(1)无约束43214321432143214321,0,,2321422245243minxxxxxxxxxxxxxxxxxxxxz (2)

无约束3214321321321321,0,0232624322minxxxxxxxxxxxxxxxxz

3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。

(1)

)6,,1(0231024893631223min6143214321321jxxxxxxxxxxxxxxzj (2)

)4,,1(01022274322325min432143214321jxxxxxxxxxxxxxzj

4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。 2 (1)

0,825943510max12212121xxxxxxxxz (2)

0,242615532max12212121xxxxxxxxz

1 第1章 线性规划

Chapter 1 Linear Programming

本章内容提要

线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。

学习本章要求掌握以下内容：

 线性规划模型的结构

 线性规划的标准形式，非标准形式转化为标准形式

 线性规划的图解以及相应的概念。包括：约束直线，可行半空间，可行解，可行域，凸集，极点，目标函数等值线，最优解

 线性规划的基本概念。包括：基，基础解，基础可行解，基变量，非基变量，进基变量，离基变量，基变换

 单纯形法原理。包括：基变量和目标函数用非基变量表出，检验数，选择进基变量的原则，确定离基变量的方法，主元，旋转运算

 单纯形表。包括初始单纯形表的构成，单纯形表运算方法

 初始基础可行解，两阶段法

 退化的基础可行解

§1.1 运筹学和线性规划

1.1.1 运筹学

运筹学（Operations Research）是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。如轰炸战术的评价和改进、反潜艇作战研究等，研究结果在战争实践中取得了明显得效果。这些研究当时在英国称为Operational Research，直译为作战研究。战争结束以后，这些研究方法不断发展完善，并逐步形成学科理论体系，其中一些主要的理论和方法包括：线性规划，网第一章 线性规划

2 络流，整数规划，动态规划，非线性规划，排队论，决策分析，对策论，计算机模拟等。这些理论和方法在经济管理领域也得到了广泛应用，Operations Research也转义成为“作业研究”。我国将Operations Research译成“运筹学”，非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来。

第1章 线性规划

本章介绍了什么是线性规划，线性规划数学模型的概念及其建立数学模型方法；阐述了线性

规划的图解法、解的概念及解的形式；详细介绍了普通单纯形法、人工变量单纯形法及单纯形法

计算公式。

1．考核知识点

（1） 基本概念：数学模型、决策变量、目标函数、约束条件、标准型、图解法、基矩阵、基变

量、非基变量、可行解、基解、基可行解、最优解、基最优解、唯一解、多重解、无界解、无可

行解、单纯形法、最小比值、入基变量、出基变量、解的判断、大M法、两阶段法、改进单纯形

法。

（2） 建立简单的线性规划数学模型。

（3） 求解线性规划的图解法。

（4） 基、可行基及最优基的定义。

（5） 可行解、基本解、基可行解、最优解、基本最优解的定义及其相互关系。

（6） 有唯一解、有无穷多解、无界解、无可行解的判断。

（7） 求解线性规划的单纯形法。

（8） 求解线性规划的人工变量法。

（9） 单纯形法中的5个计算公式。

2．学习要求

（1） 深刻领会线性规划的各种基与解的基本概念，它们之间的相互关系。

（2）掌握图解法的计算步骤，注意怎样将目标函数表达成一条直线，这条直线如何平移使得目

标函数值上升或下降。

（3） 熟练掌握单纯形法计算的全过程，特别应注意如何列出单纯形表，如何由一个基可行解换

到另一个基可行解，基可行解是最优解、无界解或多重解的判断准则。

（4） 理解在什么情况下加入人工变量，人工变量起何作用，用大M法计算时目标函数的变化，

两阶段法计算时目标函数的构成，掌握这两种计算方法的全过程，在什么情形下线性规划无可行

解。

（5） 理解用矩阵形式代替单纯形表，并用矩阵公式求解线性规划。

3．重点

建立线性规划数学模型，有关线性规划解的概念、解的形式，单纯形法计算、大M法、两阶段法。

4．难点解析

（1）建立线性规划数学模型

建立数学模型是学习线性规划的第一步也是关键的一步。建立正确的数学模型要掌握3

个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么即建立目标函数，

,.

一、选择填空

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

二、判断正误

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

三、将下列问题化为标准型

1.123412341231324237..2358,0,0,MaxZxxxxxxxxstxxxxxxx符号不限

[解] 令'22xx，'445xxx，在约束1中引入非负的松弛变量6x，约束2两边同乘以-1。整理得：

''12345''123456'123''12345623()()7..23()58,,,,,0MaxZxxxxxxxxxxxstxxxxxxxxx

即：

12345123456123123456237..2358,,,,,0MaxZxxxxxxxxxxxstxxxxxxxxx

2. Min Z=-x1+5x2-2x3

x1 +x2 - x3 ≤ 6

2x1 - x2 +3x3 ≥ 5

x1 + x2 = 10 s.t. ,.

x1 ≥ 0, x2 ≤ 0, x3符号不限

[解] 首先，令对变量x3进行处理，令x3 = x’3- x4;再令x’2 = - x2。然后对目标函数和约束条件进行标准化。

Max Z=x1+5x2+2x3-2x4

x1 - x2 - x3+x4+x5 = 6

2x1 + x2 +3x3 - 3x4 -x6 = 5

x1 - x2 = 10

x1, x2, x3, x4, x5, x6≥ 0

四、用图解法求解下列线性规

1. min Z= - x1+2x2