2014线性规划教案解读.doc

线性规划的模型及例子 (一) 模型举例 1~8 （二）线性规划模型的一般形式 9~13 用单纯形法解线性规划的模型的原理 （一）图例 13~15 （二）单纯形法 15~20 灵敏度分析与参数线性规划 （一）灵敏度分析 21~21 （二）参数线性规划 21~22 线性规划的对偶问题的提法及其经济意义 23~24 整数线性规划的解法及一些建模技巧 （一）整数线性规划的求解 25~30 （二）几个典型的整数线性规划问题 31~35 （三）添加0-1变量建立整数线性规划模型的一些技巧 35~42 进一步的应用举例 43~46 所用软件参考47~50 线性规划是运筹学的一个大分支——数学规划的组成部分.线性规划理论由苏联数学家康托洛维奇上世纪30年代给出，他是线性规划学科的奠基人，由于他的这一贡献1975年获得诺贝尔经济学奖.美国科学院、美国文理科学院与美国工程院德高望重的院士G．B Dantzig*毕生从事线性规划的理论研究与应用研究.解一般线性规划问题的单纯形算法即由他于1947年建立. 线性规划的模型 一般来讲，线性规划的模型的特征为：（1）要求解的问题的目标能用某种效益指标度量大小，并能用线性函数描述目标的要求；（2）为达到这个目标存在多种方案；（3）要达到的目标是在一定约束条件下实现的，这些条件可用线性等式或不等式描述.以下分3部分来讲：模型举例、线性规划问题的数学模型的一般形式、线性规划问题的标准形式. （一）模型举例 用线性规划求解的典型问题有生产计划问题、合理下料问题、混合配料问题、运输问题等. 以下我们通过几个例子来说明线性规划问题的来源： 例1 （资源利用问题） 先看一个具体问题： 某工厂生产两种产品，已知生产产品每公斤需耗煤9吨，耗电4百度，用工3个劳动日（一个劳动日指一个工人劳动一天）；生产产品每公斤需耗煤4吨，耗电5百度，用工10个劳动日.产品每公斤的利润是700元，产品每公斤的利润是1200元.因客观条件所限，该厂只能得到煤360吨、电2万度、劳力300个劳动日.问该厂应生产产品各多少，才能使获得的总利润最大？ 分析：将已知数据列表如下 产品（公斤） A B 资源限制 煤（吨） 9 4 电（百度） 4 5 用工（日） 3 10 利润（元） 700 1，200 问题是要决策产品的生产量，故设产品的生产量分别为（单位：公斤），（这是问题需要求解的未知量，又称为决策变量）.问题的目标是要使工厂所获得的总利润最大，现用表示总利润（单位：百元），则总利润是决策变量的线性函数：（称此函数为问题的目标函数）.同时注意到决策变量的取值要受到资源限制条件的约束， 此外，由于产品的生产量不应取负值，故决策变量还应满足非负性限制： 上述5个不等式，称为此问题的约束条件. 综上所述可知，上述实际问题可抽象成如下数学问题，称为此实际问题的数学模型： s.t.(subject to)， 一般地，资源利用问题的提法如下： 设某企业有种不同的资源，记为，用来生产种产品，记为已知每生产产品一单位需消耗资源的数量为，且知客观条件对该企业拥有资源的限制量为.又知产品的单位利润为.问如何计划各种产品的生产量，在不超过各种资源限额的条件下，使企业获得的总利润最大？ 将已知数据列表为： 产品 耗费 原料 资源限制 利润 设产品的生产量为.则各种产品的生产对资源的总消耗量为 ，此消耗量不应超过资源的限制量.因此，决策变量应满足下列个不等式： 由于产量不应取负值，故还应满足 整个生产的总利润，记为，是变量的线性函数： 问题是寻求使取大值的生产方案.所以上述一般资源利用问题的数学模型可表述为： max s.t. ， 例2 运输问题 设某种物资（如粮食、钢材、煤炭等）有个发点（仓库或产地），记为；有个收点（需求单位或销地），记为. 已知发点的物资储备量为吨，收点的需求量为吨，到每吨物资的运费为元.要求制定一个调运方案，使它满足各收、发点的供需要求，又使总运费最小.仍将已知数据列表如下： 收地 运费 发地 物资储备量 需求量 设由到的物资运量为，则从发出的物资总量为，它不能超过的储量；在收到的物资总量为，应要求它等于的需求量.总运费.因此运输问题的数学模型可表述为： Min s.t. . 例3 合理下料问题 生产实践中经常遇到这样的问题，要把长度一定的线材截成不同尺寸的毛坯，一般情况下，很难使原材料得到完全利用，总会多出一些料头. 怎样合