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

本文格式为Word版，下载可任意编辑第一章 线性规划与单纯形法 第一章 线性规划与单纯形法 线性规划的英文名称为“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 投资问题 某投资公司在2022年年初有200万元资金，每年都有如下的投资方案可供考虑采用：若第一年年初投入一笔资金，其次年年初又持续投入此资金的50%，那么到第三年年初就可回收第一年投入资金的两倍请为投资公司抉择最优的投资策略使2022年年初全体资金最多。

解：设 x1为2022年年初的投入资金，x2为2022年年初的预留资金； x3为2022年年初的投入资金，x4为2022年年初的预留资金； x5为2022年年初的投入资金，x6为2022年年初的预留资金； x7为2022年年初的投入资金，x8为2022年年初的预留资金； ?48?79?65?x3?x3x3x3?x4?x4x4x4x3,x4,?x5x5x5,?87?64?73 ?82?43?52?15?0上述数学模型表示，在得志每天各时间段工作需求的约束条件下，使总的人力本金最低 x9为2022年年初的预留资金 易知，2022年年初不再举行新的投资，由于这笔投资要到2022年年初才能收回每年的资金处境得志关系式：追加投资金额+新投资金额+预留资金=可利用的资金总额 2022年 x1?x2?200 2022年 (x1/2?x3)?x4?x2 2022年 (x3/2?x5)?x6?x4?2x1 2022年 (x5/2?x7)?x8?x6?2x3 2022年 x7/2?x9?x8?2x5 到2022年资金总额为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,?,c。