第一章 线性规划与单纯形法

第一章 线性规划与单纯形法

线性规划的英文名称为“Linear Programming”，简称LP，它是运筹学中发展最早、理论与计算方法最成熟的分支，应用十分广泛。线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好（如产量最多，利润最大，成本最小）。简单地讲，也就是资源的最优利用问题。这类问题是在生产管理和经营活动中经常会遇到的。

早在1823年法国数学家傅里叶（Fourier）就提出了与线性规划有关的问题。 1939年，前苏联的经济学家康托洛维奇（Канторович）发表了重要著作《生产组织与计划中的数学方法》，书中针对生产的组织、分配、上料等一系列问题，提出了线性规划的模型，并给出了“解乘数法”的求解方法。当时这个工作未引起足够的重视。

1947年美国数学家丹捷格（Dantzig）提出了线性规划的一般数学模型和求解线性规划问题的通用方法——单纯形法（Simplex method），这标志着线性规划这一运筹学的重要分支的诞生。此后，对线性规划的研究日渐受到关注。

1960年康托洛维奇再次发表了《最佳资源利用的经济计算》一书，受到国内外的重视，为此他获得了诺贝尔经济学奖。此外，阿罗、萨缪尔逊、西蒙、多夫曼和胡尔威茨等一批经济学家也因在线性规划研究中的贡献而获得了诺贝尔奖。在这批经济学家的努力下，线性规划的理论得到了不断的完善，已发展成为一门成熟的理论。今天，它已成为一个标准的工具，被广泛地应用于工业、农业、交通运输、军事和经济等各种决策领域，为世界上许多具有相当规模的公司和商业企业节省了数千乃至数百万美元的成本。

本章首先通过几个应用实例，引出线性规划问题并建立其数学模型，介绍线性规划的一些基本概念以及简单情形下的几何解法它的一般求解方法

图解法，然后介绍线性规划的基本理论，讨论

单纯形法，最后，介绍运用软件WinQSB解线性规划问题。

第一节 线性规划问题的数学模型

一、 线性规划问题的实例

在生产管理和经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方案。这里所说的“资源”，一般包括劳动力、原材料、设备、资金等等都是有限的。而常见的“最佳”一般有两种含义，使利润最大化或成本最小化。

例1.1生产计划问题

红星玻璃制品厂是一个有3个工人的生产两种类型手工艺窗户的小厂。窗户一种是木框架的，一种是铝框架的。3个工人的分工是：张三制作木框架，每天做4个；李四制作铝框架，每天做6个；王二制作和切割玻璃，每天制作18平方米的玻璃。每一个木框架窗使用3平方米的玻璃，每一个铝框架窗使用2平方米的玻璃。又知每生产一个木框架窗可获得30元的利润，每生产一个铝框架窗可获得50元的利润。由于工厂产量小，可假设每天生产出来的产品都可以卖出。现在请为该厂制定一个每天的生产计划，使其获利最大。

- 5 -

解：工厂获利的多少取决于两种窗户的产量，产量越大获利越多，而两种窗户的生产又受到三个工人每天生产能力的限制。木框架窗需要张三和王二的生产能力，而不需要李四的生产能力。铝框架窗需要李四和王二的生产能力，而不需要张三的生产能力。可见两种产品都为王二的生产能力而竞争，如何分配有限的生产能力来产生最大的利润是这个问题的关键。表1.1概括了问题中给的相关数据。

表1.1 张三制作的木框架（个） 李四制作的铝框架（个） 王二制作的玻璃（平方米） 利润（元/个） 木框架窗户 1 0 3 30 铝框架窗户 0 1 2 50 工人的生产能力 4 6 18 这是一个典型的生产组合型的线性规划问题，下面建立其相应的数学模型。 制定生产计划的决策需要确定的是两种窗户的产量，记

x1表示每天木框架窗户的产量

x2表示每天铝框架窗户的产量

在此，称x1、x2是模型中的决策变量。记z表示利润，由表1.1最底下一行，得到

z?30x1?50x2

该厂的目标是选择x1和x2的值使得z?30x1?50x2的值最大，而x1和x2的值受三个

工人的生产能力的限制。表3.1表明每生产一个木框架窗户，需要张三制作的木框架一个，而张三每天仅能生产4个。这个限制条件用数学不等式表示为

x1?4

类似地，李四的生产能力限制条件的数学表示是

x2?6

生产两种窗户所需玻璃为3x1?2x2，因此王二的生产能力限制条件的表示是

3x1?2x2?18

最后，产量不能为负数，即x1?0，x2?0。

综上所述，该计划问题的数学模型表示为：

目标函数 maxz?30x1?50x2

x1?4??x2?6?满足约束条件 ?

?3x1?2x2?18??x1?0,x2?0上述模型表示，在满足工人生产能力的约束条件下，使工厂的总利润最大。 例1.2 人员分配问题

人民医院计划进行值班护士的人事改革，在满足护士工作需求的情况下尽可能节约成本。通过调查得知，该院每天各时间段内需求的值班护士数如表1.2所示：

- 6 -

表1.2 时间段 需求数 时间段 需求数 6：00~8：00 48 8：00~10：00 10：00~12：00 12：00~14：00 14：00~16：00 79 65 87 64 16：00~18：00 18：00~20：00 20：00~22：00 22：00~24：00 24：00~6：00 73 82 43 52 15 该院护士实行每周5天8小时的轮班工作制，一共有5个班次，另外由于护士不愿意被分配到某些轮班，故不同班次的报酬不一样。具体情况如下：

第一班：早上6：00到下午14：00， 报酬 170元； 第二班：上午8：00到下午16：00， 报酬 160元； 第三班：中午12：00到晚上20：00， 报酬 175元； 第四班：下午16：00到午夜24：00， 报酬 180元； 第五班：晚上22：00到次日早上6：00， 报酬 195元。

问题是在满足工作需求的情况下，每天应该分配多少护士给各轮班使总的人力成本最小化？

解：人力成本的多少取决于各班次分配的护士数，护士数越少，人力成本越少。而护士数不能过少，要满足各时间段工作的需求，即不能少于各时间段的需求数。下面建立数学模型。

这个问题的决策变量是各班次分配的护士数。记xi(i?1,2,3,4,5)为每天分配给第i班的护士数，每天总的人力成本为z，由各班次的值班报酬可得

z?170x1?160x2?175x3?180x4?195x5

该院的目标是使总的人力成本z?170x1?160x2?175x3?180x4?195x5最小化。z值的大小取决于xi值的给定，而xi值的选定又受各个时间段需求值班护士的人数约束。

例如，由表1.2知，上午6：00至上午8：00期间值班护士的需求人数是48人，根据该院的班次安排，这个时间段只有第一班的护士在值班，值班人数为x1。而实际值班人数不能少于需求人数，因此这个时间段的人数约束用数学不等式可表示为

x1?48

同样，上午8：00至上午10：00期间值班护士的需求人数是79人，此时第一班和第二班的护士都在值班，值班总人数为x1?x2，因此这个时间段的人数约束用数学不等式可表示为

x1?x2?79

类似地，我们可以给出其他时间段的约束条件。 综上所述，该问题的数学模型可以表示为：

- 7 -

minz?170x1?160x2?175x3?180x4?195x5

?x1?x?x2?1?x1?x2??x1?x2?x2?s..t?????????x1,x2,例1.3 投资问题

某投资公司在2001年年初有200万元资金，每年都有如下的投资方案可供考虑采纳：若第一年年初投入一笔资金，第二年年初又继续投入此资金的50%，则到第三年年初就可回收第一年投入资金的两倍。请为投资公司决定最优的投资策略使2006年年初所有资金最多。

解：设 x1为2001年年初的投入资金，x2为2001年年初的预留资金；

x3为2002年年初的投入资金，x4为2002年年初的预留资金； x5为2003年年初的投入资金，x6为2003年年初的预留资金； x7为2004年年初的投入资金，x8为2004年年初的预留资金；

?48?79?65?x3?x3x3x3?x4?x4x4x4x3,x4,?x5x5x5,?87?64?73 ?82?43?52?15?0上述数学模型表示，在满足每天各时间段工作需求的约束条件下，使总的人力成本最低。

x9为2005年年初的预留资金。

易知，2005年年初不再进行新的投资，因为这笔投资要到2007年年初才能收回。每年的资金情况满足关系式：追加投资金额+新投资金额+预留资金=可利用的资金总额。

2001年 x1?x2?200 2002年 (x1/2?x3)?x4?x2 2003年 (x3/2?x5)?x6?x4?2x1 2004年 (x5/2?x7)?x8?x6?2x3 2005年 x7/2?x9?x8?2x5

到2006年资金总额为x9?2x7，得到下列线性规划模型为：

maxz?2x7?x9x1?x2?200??x?2x?2x?2x?01234???4x1?x3?2x4?2x5?2x6?0 s..t??4x3?x5?2x6?2x7?2x8?0?4x5?x7?2x8?2x9?0?xj?0,j?1,2,?,9??- 8 -

二、线性规划问题的数学模型

数学模型是实际问题的一种数学简化表示。

从上述例子看到线性规划问题的数学模型一般包含三个组成要素：

（1）一组决策变量?x1,x2,?,xn?，指决策者为实现规划目标采取的方案，是问题中要确定的未知量；

（2）一个目标函数，指问题要达到的目的要求，表示为决策变量的函数，依问题的具体性质取最大值或最小值；

（3）一组约束条件，指决策变量取值时受到的各种实际条件的约束限制，表示为含决策变量的等式或不等式，一般还包含决策变量的非负约束。

另外在线性规划问题的数学模型中，目标函数和约束条件都是线性的。

对于不同的线性规划问题，其数学模型的形式也有不同，但其一般形式可表示为以下几种形式：

max(min)z?c1x1?c2x2??cnxn?a11x1?a12x2???a1nxn?(?,?)b1?ax?ax???ax?(?,?)b2112222nn2? ?s..t???ax?ax???ax?(?,?)bmnnm?m11m22x1,x2,?,xn?0??其中，xj表示决策变量，共有n个；约束条件共有m?n个；后n个约束条件一般称为决策变量的非负约束；cj为价值系数；aij称为技术系数；bi称为限额系数。在例1.1的生产计划问题中，cj表示第j种产品的单位价格；aij表示生产单位第j种产品对第i种资源的消耗量；bi表示第i种资源的拥有量。

以上模型用和式的简写形式为：

max(min)z??cjxjj?1n ?nax?(?,?)b(i?1,2,?,m)i??ijjs..t?j?1?xj?0(j?1,2,?,m)?用矩阵的形式来表示可写为：

max(min)z?CX

?AX?(?,?)bs..t??X?0其中 C?(c1,c2,?,cn)；TX??x1,x2,?,xn?；b??b1,b2,?,bn?；

T- 9 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第一章 线性规划与单纯形法在线全文阅读。