第二讲 线性规划导论

第二章 线性规划

一.线性规划所研究的问题可以归结为两方面： 1）在现有的资源条件下，如何充分利用资源，使目标完成的最好。（求极大问

题）.

2)在给定的目标和任务下，以最少的资源消耗或代价，去实现目标。（求极小

化问题）。

二.线性规划的标准型：

1.标准型： max z=c1x1+c2x2+…+cnxn

s.t. a11x1+a12x2+…a1nx1n=b1

a21x1+a22x2+…+a2nx2=b2

… am1x1+am2x2+…amnxn=bm

x1,x2,…,xn≥0

2.线性规划变换方法：

1）min转换为max 目标函数乘以(-1); 2）对于≤ 引进松弛变量，将其变成取等号。

对于≥ 引进剩余变量，将其变成取等号。

3）将变量中的非正限制或无限制转化为非负限制。

3.二维线性规划的图解法： 1）正法向量：由目标函数系数组成的与等值线垂直的向量，称正法向量。

2）等值线：使目标函数取相等值的所有点的集合，称等值线。

4.二维线性规划解的形式：

1）唯一最优解 2)无穷多个最优解 3)有可行解但无最优解 4）无可行解

5.线性规划解的概念：

1）解：满足约束方程条件的点。

2）可行解：满足所有约束条件的点。（非负性约束）

3）最优解：使目标函数得到极值的可行解。 4）基：由最大的线性无关的列向量所构成的子矩阵。（基向量/非基向量）

5）基变量：与基向量对应的变量称为基变量。同理（非基变量）

6）基本解：X=（B-1b）

（ 0 ）

7）基本可行解：对于基本解，同时又满足非负性要求称基本可行解。（可行解与基本解之间相交的部分）有图。

8）可行基：基本可行解对应的基。

9）基本最优解：满足目标函数要求的基本解。

10）退化基本可行解：基本可行解中存在取值为零的基变量。

6.线性规划的基本定理：

1）如果一个线性规划问题存在可行解，则一定有基本可行解。

2）若线性规划问题存在最优解，则一定存在最优基本可行解。

第二章 线性规划的基本性质

在生产、经济、技术领域，许多工程技术和管理问题实际上是线性的，或者是可以用线性函数近似表达的，所以线性规划的研究是很有意义的。而且对线性规划的理论的研究要比非线性规划领域成熟的多。掌握线性规划的基本理论和求解方法是本课程最重要的目标之一。

§2.1 线性规划解的几何特征

借助于平面图形可以直观地了解线性规划解的几何特征，具体介绍一个实例。

设有两个决策变量x1和x2的线性规划：

min - 2 x1 - x2

s.t. -3 x1 -4 x2 ≥-12 （2.1）

- x1 + 2 x2 ≥ -2

x1,x2, ≥ 0

首先在x1Ox2平面上画出（2.1）的可行域：

12121212{(,)|-3 -4 -12,- + 2 -2, , 0}TKxxxxxxxx

为此，只要画出K的边界：

-3 x1 -4 x2 ≥-12

- x1 + 2 x2 ≥ -2

x1 = 0,x2 = 0

该可行域如图2.1所示，它是一个由四条直线组成的凸多边形。任何一个含两个变量的线性规划的可行域都是以直线为边的凸多边形。

观察目标函数：

f(x) = - 2 x1 - x2

对于任一给定的实数a，方程 - 2 x1 - x2 =a 表示一条直线，称为f的等值线。变动a可以得到一族相互平行的直线。把f的等值线向函数值a减小的方向移动，它与凸多边形K的最后一个交点即为的最优解。最优解是凸多边形的一个顶点。 设目标函数f(x) = c1 x1 +c2 x2它是x1和x2的函数，它的斜率是12cc，它在任意一点的梯度：

运筹学基础及应用课后习题答案(第一二章习题解答)

第一章：线性规划

一、选择题

1. 线性规划问题中，目标函数可以是（ ）

A. 最大化

B. 最小化

C. A和B都对

D. A和B都不对

答案：C

解析：线性规划问题中，目标函数可以是最大化也可以是最小化，关键在于问题的实际背景。

2. 在线性规划问题中，约束条件通常表示为（ ）

A. 等式

B. 不等式

C. A和B都对

D. A和B都不对

答案：C

解析：线性规划问题中的约束条件通常包括等式和不等式两种形式。

二、填空题

1. 线性规划问题的基本假设是______。

答案：线性性

2. 线性规划问题中，若决策变量个数和约束条件个数相等，则该问题称为______。

答案：标准型线性规划问题

三、计算题

1. 求解以下线性规划问题：

Maximize Z = 2x + 3y

Subject to:

x + 2y ≤ 8

3x + 4y ≤ 12

x, y ≥ 0

答案：最优解为 x = 4, y = 2，最大值为 Z = 14。

解析：

画出约束条件的图形，找到可行域，再求目标函数的最大值。具体步骤如下：

1) 将约束条件化为等式，画出直线；

2) 找到可行域的顶点；

3) 将顶点代入目标函数，求解最大值。

第二章：非线性规划

一、选择题

1. 以下哪个方法适用于求解非线性规划问题（ ）

A. 单纯形法

B. 拉格朗日乘数法

C. 柯西-拉格朗日乘数法

D. A和B都对

答案：B

解析：非线性规划问题通常采用拉格朗日乘数法求解，单纯形法适用于线性规划问题。

2. 非线性规划问题中，以下哪个条件不是K-T条件的必要条件（ ）

A. 梯度条件

B. 正则性条件

C. 互补松弛条件

D. 目标函数为凸函数

答案：D

解析：K-T条件包括梯度条件、正则性条件和互补松弛条件，与目标函数是否为凸函数无关。

1 第三部分 运筹学

第四章 运筹学建模

4.1 运筹学概述

运筹学是用数学方法研究各种系统最优化问题的学科。其研究方法是应用数学语言来描述实际系统，建立相应的数学模型，并对模型进行研究和分析，据此求得模型的最优解；其目的是制定合理运用人力、物力和财力的最优方案；为决策者提供科学决策的依据；其研究对象是各种社会系统，可以是对新的系统进行优化设计，也可以是研究已有系统的最佳运营问题。因此，运筹学既是应用数学，也是管理科学，同时也是系统工程的基础之一。

运筹学一词最早出现于第二次世界大战期间，当时为了急待解决作战中所遇到的许多错综复杂的战略战术问题，英美一些具有不同学科和背景的科学家，组成了许多研究小组，专门从事军事行动的优化研究。研究的典型课题有：高射炮阵地火力的最佳配置、护航舰队规模的大小以及开展反潜艇作战的侦察等方面。由于受到战时压力的推动，加上不同学科互相渗透而产生的协同作用，在上述几个方面的研究都卓有成效，为第二次世界大战盟军的胜利起到积极作用，也为运筹学各个分支的进一步研究打下了基础。战后，这些科学家们转向研究在民用部门应用类似方法的可能性。因而，促进了在民用部门中应用运筹学有关方法的研究和实践。

1947年，美国数学家G．B．Dantzig提出了求解线性规划的有效方法——单纯形法。50年代初，应用电子计算机求解线性规划问题获得了成功。50年代末，工业先进国家的一些大型企业也陆续应用了运筹学的方法以解决企业在生产经营活动中所出现的许多问题，取得了良好效果。60年代中期，一些银行、医院、图书馆等都已陆续认识到运筹学对帮助改进服务功能、提高服务效率所起的作用，由此带来了运筹学在服务性行业和公用事业中的广泛应用。电子计算机技术的迅速发展，为广泛应用运筹学方法提供了有力工具，运筹学的应用又开创了新的局面。当前，运筹学在经济管理、生产管理、工程建设、军事作战、科学试验以及社会系统等各个领域中都得到了极为广泛的应用。一些发达国家的企业、政府、军事等部门都拥有相当规模的运筹学研究组织，专门从事运筹学的应用研究，并为上层决策部门提供科学决策所需的信息和依据。