运筹学讲义

运筹学讲义

引言

1．年轻的学科：20世纪30年代，英国，美国，加拿大等在防空作战研究上提出的一种方法。当时叫operational research,缩写为O.R. 是一门年轻的学科。我国是在56年在中科院力学研究所成立运筹小组，80年成立运筹学会。

2。应用数学：包括小到日常生活，如出门买东西的线路选择，大到国民经济建设优化组合，无处不在。例如，我国北宋时代，丁渭修皇宫P1。 3。讲授内容：ch1.§1～5;ch3; ch7;ch8;ch12;ch13.

第一章 线性规划及单纯型法

运筹学的一大分支是数学规划，而线性规划又是数学规划的重要组成部分。线性规划（linear programming 简写LP）也是运筹学最基本的内容。相对于其他运筹学分支，LP理论完善，方法简单，应用广泛，是任何运筹分支首先要阐明的基本知识。 §1 LP问题及其数学模型 一. 问题的提出及建模

例1 美佳公司计划制造Ⅰ，Ⅱ两种家

电产品。已知各制造一件事分别占用的设备 表1-1 Ⅰ Ⅱ 每天可用能力 A，B的台时、调试时间、调试工序及每天可项目 0 5 15 用于这两种家电的能力、各出售一件时的获设备A（h） 6 2 24 利情况，如表1-1所示。问该公司应各制造设备B（h） 两种家电各多少件，使获利最大？ 调试工序（ h ） 1 1 5

2 1 利润（元） 解：设制造Ⅰ，Ⅱ产品数量为x1，x2.则利润 z=2x1+x2

问题是：在现有设备、调试能力的限制下，如何确定产量x1，x2.可使利润最大？ 我们把它数学化：

目标函数：maxz=2x1+x2

??6x?1 约 束条件??x1??x1,5x2??x2?02x2x2?15(1)设备A的限制 设备B的限制 调试能力限制 非负约束

?24(2)

?5(3)(4)其中（1）～（3）资源限制，（4）为非负限制。 下面从数学的角度来归纳线性规划的模型特点：

（1） 每一个问题都有一组变量——称之为决策变量，一般记为x1，x2?xn。对决策变量的每一组值：(x1,x2,?xn)代表了一种决策方案。通常要求决策变量取值非负，即

(0)(0)(0)Txj?0（j=1，2，?n）.

1

（2）每个问题都有决策变量须满足的一组约束条件——线性的等式或不等式。

（3）每个问题都有一个关于决策变量的线性函数——称为目标函数，要求这个目标函数在满足约束条件下实现最大或最小化。

我们将约束条件及目标函数都是决策变量的线性函数的规划问题称之为线性规划。其一般模型为

（目标函数，或实现最大化，或实现最小化） max(min)z?c1x1?c2x2???cnxn （1.1.1）

??a11x1?a12x2??a1nxn?(?,?)b1?a21x1?a22x2??a2nxn?(?,?)b2s.t???????? (1.1.2) ( 资源约束)

??am1x1?am2x2??amnxn?(?,?)bm??x1,x2,?xn?0（1.1.3）(非负约束)

s.t 是subject to的英文缩写，它表示“以?为条件”、“假定”、“满足”之意。

另外，通常称目标函数中xj的系数cj为价值系数，bi表示第i种资源的拥有量。 用∑可将上述模型简化成： n max(min)z??cjxj

j?1?n s.t???aijxj?(?,?)bj(i?1,?m)

?j?1?xj?0(j?1,?n)用向量形式表示时，上述模型可写为：

max(min)z?CX ?n s.t???Pjxj?(?,?)b

?j?1?X?0??x1??a1j??式中C?(c?x??2??a??b1??2j??b2?1,c2,?cn)，X?????，Pj????，b????

??x?n???????amj????b?m??用矩阵表示为

max(min)z?CX

s.t??AX?(?,?)b?X?0

其中

2

?a11??a21 A=????a?m1称为约束方程组的系数矩阵。

a12a22?am2?a1n???a2n? ?????amn??§2 图解法

一．预备知识

1．直线上的点把平面分成三部分：直线上的点，直线一侧的点，直线上的点，直线另一侧的点。

例：?：x1+x2=5 用集合表示? =｛（x1，x2）∣x1+x2=5，x1，x2∈R｝ 2．二元一次不等式的解集代表一个平面域。 例：x1+x2≤5， 分两部分：

y x1+x2=5，及x1+x2<5

3. 梯度：对多元函数u=?(X),

5 X?(x1,x2,?xn)T∈S?Rn,有如下

的定义

定义：设u=?(X),X∈S?R,若在点

nx1+x2=5 O 5 x X0?(x1(0),x2(0),?xn(0))T处对于自变量X?(x1,x2,?xn)T的各分量的偏导数?f(X0)（i?1,2,?n)都成立，则称函数u=?(X)在点X0处一阶可导，并称向量???xi(X)=(?f(x0)?f(x0)?f(x0)T,,?)是u=?(X)在点X0出的梯度或一阶导数。 ?x1?x2?xn3例：?（x1，x2）=2x1+x2， X0=（x1（0），x2（0））=（1，2），

?f(X0)=2，?x1?f(X0)2=3x2?x2x2?2=12， ??（X0）=???2??。函数在f点X0处的几何意义是：??（X0）??12?是过点X0的?(X)等直线（面）在点X0出的法向量,沿梯度正方向为函数在该点增加最快的方向。

二．下面还是以例1来说明用图解法求解线性规划问题。

maxz=2x1+x2

3

??6x?1??x1??x1,5x2??x2?02x2x2?15(1)?24(2)?5(3)(4)x2 l? 5x2=15 P Q(3.5,1.5) t

（1）～（3）是三个平面域，加上（4）限制在Ⅰ象限，可行域为 Z=2

x1+

x2的梯度为

O 2x1+x2=z=2 6x1+2x2=2 x1 ?z=(?z?zT,)=(2,1)T,梯度方向为t,?x1?x2x1+x2=5 沿t的方向是增加的方向，将等直线沿t平行推进，即将离开还未离开可行域的一根等直线记为l，Q（3.5，1.5）即为此线性规划的最优解。Z=8.5. 即美佳公司应每天制造家电Ⅰ3.5件，家电Ⅱ1.5件，能获利润最大。最大利润z=8.5元。 三。LP问题求解的几种可能情况： 有最优解?

???1唯一，上例 ○

2无穷多最优解 ○

例 maxz=x1+x2

??6x?1??x1??x1,5x2??x2?02x2x2?15(1)?24(2)?5(3)(4)

目标函数z=x1+x2与约束线（3）x1+x2=5平行，最优解为PQ线段上的所有点。

?无最优解的情况 ?

?

无界解例：maxz=2x1+x2

1 无界解 ○2 无解 ○

?5x1?15 ?x,x?0?12可行域无界，造成无解解maxz=∞，主要原因是漏掉了一些约束。 无界例：maxz=2x1+x2

4