数学建模方法与实践

作者简介

内容简介

第1章 线性规划
　　线性规划(linear programming，LP)，是研究线性约束条件下线性目标函数的极值的数学方法.对于整个运筹学来说，线性规划是最早、最成熟的一个分支.1947年，George Dantzig开发了一种解决线性规划问题的有效方法——单纯形算法.自单纯形算法开发以来，线性规划一直用于银行、教育、林业、石油和运输等行业中解决最优化问题.有些规划问题的目标函数是非线性的，但往往可以采用分段线性化等方法，转化为线性规划问题.用线性规划求解的典型问题有运输问题、生产计划、套裁下料、混合配料、证券投资选择、人事计划、库存计划与控制、消防系统选址等.
　　本章将主要介绍线性规划的基本知识，以及运输问题和整数规划，并介绍优化软件LINDO求解方法.在学习过程中，读者可以结合软件快速掌握相关知识.
　　1.1 引例
　　案例1 某公司生产两种化学产品，其耗材与获利情况如表1.1.1.
　　表1.1.1 决策表
　　问题是：
　　(1)如何安排生产计划使得获利最大?
　　(2)若产品2获利提高，提高多少可能导致生产计划改变？
　　(3)若原材料供应量增加，生产计划如何调整？
　　(4)若原料3的市场价格为30万元/吨，问公司是否应购买原料3，若购买以多少为宜？
　　案例2 某工厂近期接到一批订单，要安排生产甲、乙、丙、丁四种产品，每件产品分别需要原料A，B，C中的一种或几种中的若干单位，合同规定要在15天内完成，但数量不限.由于四种产品都在一种设备上生产，且一台设备同一时间只能加工一件产品.目前工厂只有一台正在使用中的这种设备(暂称设备1)，合同期内可挤出3天来生产这批订单，但会产生150元的机会成本损失;还有一台长期未用的设备(设备2)可以启用，启用时要做必要的检查和修理，费用是1000元;公司还考虑向邻厂租用两台这种设备(设备3和设备4)，由于对方也在统筹使用设备，租期分别只能是7天和12天，而且租期正好在合同期内，租金分别是2000和3100元，工厂决定租一台或两台，或一台也不租.另外每种产品如果生产的话会有固定成本和变动成本，这些数据加上每种产品所需的原料种类或数目、各种原料的可用数量以及制造每种产品所需的工时数和每种产品的单位价格都是已知的.假设每天工作8小时(这意味着四台设备的可用台时分别为24，120，56，96)，并且假设工厂最多使用这四台设备中的三台.问工厂如何安排这四种产品的产量和利用哪些设备，能在上述资源限制条件下获得的利润最大？
　　1.2 基本概念
　　线性规划问题可以分为两类.
　　(1)如何合理地使用有限的资源(原材料、劳动力、设备台时、资金等)以得到最大的效益(如利润最大或风险最小).
　　(2)为了达到一定的目标(生产指标或其他指标)，如何组织生产或安排相关计划以使消耗资源(原材料、劳动力、设备台时、资金等)最少.
　　线性规划模型通常包含以下三个部分.
　　决策变量 问题中可以控制的变化因素，通常记为，它的值可以至少在某一范围内变化.决策变量可分为两类：离散变量，如生产电子产品的件数;连续变量，如农作物的施肥量.决策变量又称可控变量.
　　目标函数通过变量构造的函数来表达决策者的某种愿望，如最大利润或最小成本等.
　　约束条件问题中必须满足的条件，如有限的人工时间、资金等，其数学表达式可以是以下三种形式之一，f(x).b，或f(x).b，或f(x)=b.
　　1.2.1 线性规划问题及模型
　　1.建立线性规划模型的例子
　　例1.2.1 某工厂在计划期内要安排生产甲、乙两种产品.已知制造甲产品需要A型配件5个，B型配件3个;制造乙产品需要A型配件2个，B型配件4个.而在计划期内该工厂只能提供A型配件180个，B型配件135个.又知道该工厂每生产一件甲产品可获利润20元，一件乙产品可获利润15元.问在计划期内甲、乙产品应该各安排生产多少件，才能使总利润最大?
　　解 将所述情况列成表格，这种表格通常称为决策表，见表1.2.1.确定决策变量，即能在实际中加以控制的那些变量如下：
　　x1:生产甲产品的件数，x2:生产乙产品的件数.
　　目标函数来自于决策者的希望(或愿望)，一般是：à使利润达到最大;á使资源(如人、机器、系统)利用率达到最大;.使一个给定的生产过程保持在一定的控制范围内的概率达到最大;.使成本达到最小;.使加班工作时间达到最小;.使劳动力调动最小;.使机器停修时间最小;.使风险达到最小(对个人、企业、环境);使与标准值的偏差量达到最小;等等.
　　本例中决策者希望总利润最大.因该工厂每生产x1件甲产品可获利润20x1元，生产x2件乙产品可获利润15x2元.设总利润为z，则目标函数为
　　在满足约束条件下，求出使z达最大的自变量x1，x2的值即可.
　　表1.2.1 决策表
　　约束条件一般包含：
　　(1)有限的原材料、有限的资金预算、有限的时间、有限的人员以及有限的能力或技术等等;
　　(2)各种“法定的”或受物理规律限制的现实目标，例如，变量仅取非负值的约定要求;
　　(3)规定一个函数必须大于等于(或者小于等于)某一最小(最大)值的约定要求;
　　(4)对变量在上下限范围内取值的实际限制(如一个系统元件的温度必须限制在它能承受的范围内).
　　列出各种约束条件后，应该进行仔细检查它们是否有明显的重复，是否可以组合或合并.
　　在本例中生产受配件总数的限制，生产甲、乙两种产品共需要A型配件5x1+2x2个，而在计划期内该厂只能提供A型配件180个，从而得到第一个约束需B型配件3x1+4x2个，而在计划期内该厂只能提供B型配件135个，从而得到第二个约束
　　同时，注意到产品数不能为负数，从而有
　　综上，可得如下数学模型：
　　其中，是subject to的缩写，表示“受 约束”.
　　现在已建立起一个数学模型，要求在满足约束条件下使目标达到最大值，这类最值问题称为规划问题.
　　2.线性规划的数学模型
　　此类规划问题具有以下特征.
　　(1)用决策变量表示可控因素，变量的一组取值(x1，x2， ，xn)代表一个解决方案，通常要求变量取非负值.
　　(2)存在一定的约束条件(例如材料、人力、设备、时间、费用等的限制)，可以用自变量的线性方程或线性不等式来表示.
　　(3)都有一个需达到的目标，该目标也是自变量的线性函数，称为目标函数.根据需要使目标函数最大化或最小化.
　　这类目标函数和约束条件都是自变量的线性函数的规划问题被称为线性规划问题.对线性规划问题而言，满足所有约束条件(包括非负条件)的解称为可行解，所有可行解构成的集合称为可行域.求解线性规划的目标就是在可行域中寻找使目标函数达到最大或最小值的可行解.下面，将前例推广到一般情形.
　　假定线性规划问题有n个变量，分别用xj(j=1，2， ，n)表示，在目标函数中xj的系数为cj(cj通常称为价值系数);xj的取值受到m项资源的限制，用bi(i=1，2， ，m)表示第i种资源拥有量，每单位xj消耗(或含有)第i种资源的数量用aij表示，称aij为技术系数或工艺系数.这时，线性规划问题的数学模型可抽象为
　　实际问题中变量xj的取值一般非负，即，但从数学意义上来说可以有xj.0;当xj的取值范围为时，称xj无约束.
　　3.线性规划的标准形式
　　由于线性规划模型的目标函数和约束条件各有多种表现形式，为了得到一种普遍适用的求解方法，需要将线性规划问题的数学模型化为统一的标准形式.
　　标准形式的线性规划模型中要求：
　　(1)目标函数一律是求最大值(有的书上是求最小值);
　　(2)约束条件一律化为等式;
　　(3)约束条件右端常数项bi一律为非负值，即;
　　(4)变量xj取值一律为非负值，即.
　　标准形式的表示方法有如下四种.
　　(i)一般表达形式：
　　(1.2.1)
　　(ii)简写形式：
　　(1.2.2)
　　(iii)向量形式：
　　(1.2.3)
　　其中
　　(iv)矩阵形式：
　　(1.2.4)
　　其中，C，X，b同上，
　　对不符合标准形式(称非标准形式)的线性规划问题，可通过以下方法转化为标准形式.
　　(1)目标函数的转化.
　　若原问题的目标函数是求最小值，即
　　则可将目标函数乘以.1，等价转化为求最大值