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

第一章 线性规划与单纯形法经营管理中如何有效地利用现有人力、物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力、物力去实现目标。这类统筹规划的问题用数学语言表达，先根据问题要达到的目标选取适当的变量，问题的目标通过变量的函数形式表示（成为目标函数），对问题的限制条件用有关变量的等式或不等式表达（成为约束条件）。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。有关线性规划问题的建模，求解和应用的研究构成了运筹学中的线性规划分支。用线性规划求解的典型问题有运输问题、生产计划问题、下料问题、混合配料问题等。有些线性规划问题的目标函数是非线性的，但往往可以采用分段线性化邓手法，转化为线性规划问题。第一节 线性规划问题及其数学模型一、问题的提出及数学模型例一：美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时，调试时间，调试工序每天可用于这两种家电的能力。各售出一件的获利情况，如表11所示。问该公司应制造两种家电各多少件，使获得的利润为最大。表11每天可用能力设备A（h）设备B（h）调试工序(h)06152115245利润（元）21设该公司应制造家电件，家电件，该公司每天可获得的利润为（）元，因问题中要求获得的利润为最大，即。又是该公司能获得的利润的目标函值，它是变量、的函数，成为目标函数。、的取值受到设备A、B和调试工序的限制，用于描述限制条件的数学表达式成为约束条件。数学模型为：目标函数约束条件（S.T.） 例2：捷运公司拟在下一年度的14月份的4个月需租用仓库堆放物资。已知各月份所需仓库面积数列于表12。仓库租用费随合同期而定，期限越长，折扣越大。具体数字见表13。租界仓库的合同每月初都可办理，每份合同的具体规定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租界合同。每次办理时可签一份，也可签若干份租用面积和租界期限不同的合同，试确定该公司签订的租界合同的最优决策，目的是所付租界费用最小。表12月份1234所需仓库面积（100）15102012表13合同租界期限1个月2个月3个月4个月合同期内的租金（元/100）2800450060007300解：若用变量表示捷运公司在第个月初签定的租借期为个月的仓库面积的合同（单位为100）。因5月份起该公司不需要租界仓库，故均为零。该公司希望总的租界费用为最小，故有如下的数学模型：目标函数：约束条件这个模型中的约束条件分别表示当月初签订的租界合同的面积数加上该月前签订的未到期的合同的租界面积数总和，应不少于该月所需的仓库面积数。例3：某公司经营某种产品，该产品由3个生产点生产，日产量为，分别销往4个销售点,各销地的日销售量分别为：。已知每吨产品从各产点到各销售地 的运价如表13所示，问如何调运，保证产销平衡且总运费最小？表13 （单位：百元/吨）产量5610360ton419740ton423860ton销量30504040160ton解：这是一个产销平衡的运输问题，即各产地的产量之和等于各销地的销量的总量。设表示从生产点到销售点的调运量。数学模型为：目标函数为：下面从数学的角度来归纳上述三个例子的共同点：（1）、每一个问题都有一组变量称为决策变量，一般记为。对决策变量的每一组值：代表了一种决策方案。通常要求决策变量取值非负，即。（2）、每一个问题中都有决策变量需要满足的一组约束条件线性的等式或不等式。（3）、都有一个关于决策变量的线性函数称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划问题（linear programming）有时简称为LP问题。一般数学模型为s.t.其中为变量（决策变量）是目标函数，或实现最大化，或实现最小化。s.t.是subject to的英文缩写，它表示“以为条件”，“假定”，“满足”之意。（1）（m）称为约束条件，称为约束条件，它可以的不等式，也可以是严格的等式。(m+1)称为非负约束条件。称为价值系数称为资源拥有量称为技术系数或工艺系数，表示变量取值为一个单位时所消耗或含有的第种资源的数量。上述模型的简写形式为： s.t.用向量表示时，上述模型可写为： s.t.其中；用矩阵和向量表示为： s.t.其中A= A为约束方程组（约束条件）的系数矩阵。 变量的取值一般为非负，即；从数学意义上可以有。又如果变量表示第i种产品本期内产量相对于前期产量的增加值，则的取值范围为（），称取值不受约束，或无约束。二、线性规划问题的标准形式。标准形式： s.t.（注意：有些书上规定是求极小值），约束条件全为等式，约束条件右端常数项全为非负值（），变量的取值全为非负值。对不符合标准形式（或称非标准形式）的线性规划问题，可分别通过下列方法化为标准形式。1、目标函数为求极小值，即为因为求就等价于求，令，即化为2、若某个约束方程的右端项，则在此等式或不等式两端同乘以（1），则等式或不等式的右端项必大于零。3、若约束条件是小于等于型，则在该约束条件不等式左边加上一个新变量称为松弛变量，将不等式改为等式。如：4、若约束条件是大于等于型，则在该约束条件不等式左边加上一个新变量称为剩余变量，将不等式