运筹学讲义

运筹学讲义 绪论（2学时）

参考教材：

（1） 运筹学基础教程（魏权龄） （2） 管理运筹学（韩伯棠） （3） 管理运筹学通论（韩大卫） （4） 运筹学（胡运权）

先修课程：一元微积分、线性代数、概率统计 学时：48+（8） 主讲教师：狄军锋 一、 运筹学发展 1、 运筹学的产生 ? ? ? ? ?

最早与1938年出现于英国，简称OR(operational Research) 夫运筹帷幄之中，决胜于千里之外，吾不如子房。---史记 古代运筹学思想：田忌赛马+丁谓挖沟+沈括运军粮

二战中的运筹学：反潜艇策略、深水炸弹的起爆深度、诺曼底登陆 运筹学在我国的发展：

① 50年代中期，钱学森、许国志等教授将运筹学由西方引入我国。 ② 管梅谷（1962年，山东师范大学）：“中国邮递员问题” ③ 华罗庚：优选法（1970）和统筹法（1965）

2、运筹学的定义：管理运筹学是一门应用科学，它广泛应用现有的科学技术和数学方法，解决管理中提出的专门问题，为决策者选择最优或较优的决策提供定量依据。运筹学是一门新兴的交叉学科，来源于军事、管理和经济。本课程主要介绍用于解决管理领域问题的运筹学，因此称为管理运筹学，也有人称为管理科学。

二、运筹学解决问题的思路

提出问题→建模→求解→结果分析与调整→实施 二、 运筹学的学科内容：

线性规划（LP）；*整数规划（IP）；*非线性规划(NP)；*多目标规划（MP）；动态规划（DP）；对策论（GT）；决策分析（DA）；存贮论（IC）；排队论（QT）；图论（Graph Theory） 三、章节安排 1、绪论（2学时） 2、线性规划(14学时) 3、动态规划（6学时） 4、存储论（6学时） 5、对策论（10学时） 6、决策论（6学时） 7、统筹方法（2学时） 8、总复习（2学时） 四、应用举例 1、 猴子运香蕉 2、 海盗分宝石 3、 猜生日

1

第二

*主要内容

1、线性规划的一般形式、压缩形式、矩阵形式、向量形式 2、线性规划问题的图解法（3） 3、线性规划问题的标准形式 4、单纯形方法（4）

5、线性规划问题应用举例（3） 6、运输问题的解法（4）

§1 线性规划问题的基本模型

一、 引例

【引例1】某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品需的设备台时，A、B两种原材料的消耗以及每种产品可获利润如下表所示。问应如何安排生产进度使工厂的获利最多？

设备 原材料A 原材料B 单位产品利润（元）

Ⅰ 1 4 0 2

Ⅱ 2 0 4 3

资源限量 8台时 16kg 12kg

该问题可用一句话描述：即在有限资源的情况下，求使利润最大的生产计划方案。

maxf?2x1?3x2?x1?2x2?8?4x?16?1s.t??4x2?12??x1,x2?0【引例2】营养配餐问题

假定一个成年人每天需要从食物中获取300cal热量，55g蛋白质，88mg钙。如果一个市场上有四种食品可供选择，它们每kg所含热量和营养成分以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食物的费用最小？

序号 1 2 3 4 食品名称 猪肉 鸡蛋 大米 白菜 热量（cal） 1000 800 900 200 蛋白质（g） 50 60 20 10 钙（mg） 价格（元） 400 200 300 500 20 7 5 2

minz?20x1?7x2?5x3?2x4?1000x1?800x2?900x3?200x4?3000?50x?60x?20x?10x?55 ?1234s..t??400x1?200x2?300x3?500x4?800?xj?0(j?1,2,3,4)?

2

二、 LP问题的模型

＊线性规划：变量满足线性约束的条件下，求使线性目标函数值最优的问题。 1、一般形式 2、紧缩形式

max(min)f?c1x1?c2x2???cnxn?a11x1?a12x2??a1nxn?(?,?)?b1max(min)f??cjxjj?1?ax?ax??ax?(?,?)?b2nn2?211222 ?n?ax?(?,?)?b(i?1,2,?,m)s..t??i??ijjs..tj?1??ax?ax??ax?(?,?)?bmnnm?x?0(j?1,2,?n)?m11m22?jx?0(j?1,2,?n)??j3、矩阵形式 4、向量形式

nmax(min)f?cx?Ax?(?,?)b s.t??x?0其中

max(min)f?cx?n?）b ??pjxj?(?，s.t?j?1?x?0(j?1,2,?,n)?，

A???aij??m?n?(p1p,2?,pn,，x?(x1,x2,?,xn)Tc?(c1,c2,?,cn)，

b?(b1,b2,?,bm)T 。

三、 线性规划标准模型

由线性规划模型的一般形式的讨论可知，线性规划模型有多种不同情况：目标函数可以是最大或最小，约束条件可以有大于等于、小于等于或等于三种情况。为便于线性规划模型的求解，可将线性规划模型的一般形式统一转化为标准形式，这里规定线性规划标准模型的条件：目标函数最小化、约束条件为等式、决策变量均非负、右端项非负。 线性规划标准模型的一般表达式：

minf?c1x1?c2x2???cnxn ?a11x1?a12x2???a1nxn?b1?ax?ax???ax?b2112222nn2??s..t?????????????ax?ax???ax?bmnnm?m11m22x1,x2,?xn?0??化一般型为标准型： ①

maxf→min(?f)??cx

② ≤→左边+松弛变量；≥→左边-剩余变量 ③ 变量xj④

?0→?xj?0；变量xj无限制→令xj?x'j?x''j

bi?0→等式两边同乘以（-1）.

3

§2图解法

一、 线性规划几何解的有关概念 考虑线性规划模型一般形式：

Max(Min)f?cx

?）b?Ax?(?， s..t?x?0?可行解：凡满足约束条件和非负条件的决策变量的取值x?(x1,x2,?,xn)称为线性规划可行解。 可行域：所有可行解的集合称为线性规划的可行域。

最优解：使目标函数达到最优值的可行解称为线性规划的最优解二、 图解法基本步骤

在明确线性规划可行解、可行域和最优解的基础上，介绍线性规划的图解法。对于两个或三个变量的线性规划问题，可以通过平面图或立体图进行求解，是线性规划问题解的几何表示。图解法的优点简单、直观，有助于理解线性规划问题求解的基本原理。它的局限性在于只能对两个或三个变量的线性规划问题求解。 图解法的基本步骤可以概括如下：

（1）建立平面（空间）直角坐标系。取决策变量为坐标向量，标出坐标原点、坐标轴指向及单位长度。 （2）确定线性规划解可行域。根据非负条件和约束条件画出解的可行域。只有在第一象限的点才满足线性规划非负条件，将以不等式表示的每个约束条件化为等式，在坐标系第一象限作出约束直线，每条约束直线将第一象限划分为两个半平面，通过判断确定不等式所决定的半平面。所有约束直线可能形成或不能形成相交区域，若能形成相交区域，相交区域任意点所表示解称为此线性规划可行解，这些符合约束限制的点集合，称为可行集或可行域。转到第三步；否则该线性规划问题无可行解。

（3）绘制目标函数等值线（面）。目标函数等值线（面）就是目标函数取值相同点的集合，通常是一条直线（二维平面）或一个平面（三维空间）。

（4）寻找线性规划最优解。对于目标函数的任意等值线（面），确定该等值线（面）平移后值增加的方向，平移此目标函数的等值线（面），使其达到既与可行域相交又不可能使目标函数值再增加的位置。相交位置存在三种情况：若有唯一交点时，目标函数等值线（面）与可行域相切，切点坐标就是线性规划的最优解；若相交于多个点，称线性规划有无穷多最优解；若相交于无穷远处，此时无有限最优解。 【例】 运用图解法求解线性规划问题

***TX*?(x1,x2,?,xn)。

Tmaxf?2x1?3x2?x1?2x2?8?4x?16?1s.t??4x2?12??x1,x2?0

三、线性规划问题几何解的讨论

利用图解法可以讨论线性规划解的四种情况。

（1）唯一最优解。线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。

（2）无穷多最优解。线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值达到最优的解。如果例的目标函数变为Maxf

目标函数的等值线正好和约束条件x1?x2?8?3x1?3x2，

4

相平行。在目标函数向右上方平移的过程中，与可行域相切于划问题存在无穷多最优解。

x1?x2?8上的所有点，此时，该线性规

（3）无有限最优解（无界解）。线性规划问题的无有限最优解是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。考虑下述线性规划模型：Maxf?x1?x2

?x1?4 s..t?x?0,x?0?12利用图解法进行求解时，可行域是一个非封闭的无界区域，x2的取值可以无限增大，同时，目标函数

f值

也可以增大到无穷，如下图所示。在这种情况下，称线性规划无有限最优解或无界解。原因在于建立线性规划模型时，遗漏了某种必要资源的约束。

x2 x2 x1+2x2=4 2 x1-2x2=5 x1 4 x1 o 4 5 （4）无可行解。当线性规划问题中的约束条件不能同时满足时，将出现无可行域的情况，这时不存在可行解，即该线性规划问题无解。考虑下述线性规划模型

Maxf?x1?x2

?x1?2x2?4?t?x1?2x2?5 s..?x?0,x?02?1利用图解法进行求解时，在第一象限内，所有约束条件不能形成一个相交平面区域，如上图。线性规划问题不存在可行域，也就是说，问题没有可行解。其原因是线性规划模型自身的错误，约束条件之间自相矛盾，应根据实际情况进行调整。

针对线性规划几何解还有一些重要的性质，这里不加证明叙述如下：（1）线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无有限最优解、无可行解。（2）若线性规划可行域非空，则可行域必定是一个凸集。（3）若线性规划可行域非空，则凸集至多有有限个极点。（4）若线性规划优解存在，则最优解或最优解之一肯定能够在可行域（凸集）的某个极点找到。

通过上述的讨论，求线性规划问题最优解，可以转化为在其可行域有限个极点上进行搜索的方法。基本思路是，先找出凸集任意一个极点，计算极点的目标函数值。比较与之相邻的目标函数值是否比该极点的目标函数值更优，如果为否，则该极点就是最优解，如果为是，转到比该点目标函数值更优的另一极点。重复上述过程，直到找出使目标函数值达到最忧的极点为止。

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学讲义在线全文阅读。