第1章1线性规划模型与标准化

第一章、第一章、 线性规划及单纯形线性规划及单纯形法法线性规划（ Linear Programming， LP） 是运筹学的一个重要分支 。1947 年，丹捷格 (Dantzig)提出了求解线性规划问题的一种一般解法 单纯形法 (Simple Method)，使线性规划在理论上趋于成熟，应用日益广泛。随着计算机技术的发展，用计算机处理大规模线性规划问题之后，线性规划的应用更加广泛和深入。目前，它已成为解决现代管理和某些科学技术问题的重要手段之一。1.1 线性规划的概念线性规划的概念一、一、 线性规划问题的提出线性规划问题的提出 利用有限资源利用有限资源某工厂在计划期内要安排生产 、 两种产品，已知生产单位产品所需的设备台数及 A、 B两种原材料的消耗量，见表 1-1。该工厂每生产一件产品 可获利润 2元，每生产一件产品 可获利润 3元，问应如何安排生产计划使该工厂获得的利润最大？ 生产计划问题生产计划问题产品资源 资源限量设备 (台 时 ) 1 2 8原材料 A(g) 4 0 16000原材料 B(g) 0 4 12000如何制定生产计划，使两种产品总利润最大？如何制定生产计划，使两种产品总利润最大？利用有限资源：某鸡厂共饲养利用有限资源：某鸡厂共饲养 1万只鸡，用大豆和万只鸡，用大豆和谷物混合喂养，已知一只鸡消耗饲料谷物混合喂养，已知一只鸡消耗饲料 1kg /天天 ，它至，它至少需要蛋白质、钙分别为少需要蛋白质、钙分别为 0.22、 0.06 kg/天。又知每天。又知每公斤大豆含蛋白质、钙为公斤大豆含蛋白质、钙为 50、 0.2，每公斤谷，每公斤谷物含蛋白质、钙为物含蛋白质、钙为 10、 0.1，大豆和谷物售价，大豆和谷物售价0.4、 0.2元元 /kg。问怎样喂养，鸡场最合算？。问怎样喂养，鸡场最合算？饲 料成分 大豆 谷物 营 养 /天天 .鸡鸡蛋白 质 .kg 50 10 0.22钙 .kg 0.2 0.1 0.06售价 .元 0.4 0.2设：每只鸡每天需要大豆 x1公斤，谷物 x2公斤，+= 0.20.4 21 xxMinZ=+2,1,00.2221jx0.1x 0.5xtsj+ 0.0621 0.001x0.002x+ 121 xx=+=2,1,00.22100000.20.42121jx0.1x 0.5xtsxxMinZj+ 0.061000021 0.001x0.002x+ 1000021 xx设：养鸡场每天需要大豆 x1公斤，谷物 x2公斤二、线性规划的定义和数学描述（模型）二、线性规划的定义和数学描述（模型）1定义：定义：对于求取一组变量对于求取一组变量 xj (j =1,2,n)， 使之使之既满足线性约束条件，又使具有线性表达式的既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（题称为线性规划问题，简称线性规划（ LP）。）。2.配比问题和生产计划问题的线性规配比问题和生产计划问题的线性规划模型的特点：划模型的特点： 用一组未知变量表示要求的方案，这组用一组未知变量表示要求的方案，这组未知变量称为决策变量；未知变量称为决策变量；存在一定的限制条件，且为线性表达式存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线是最小化），目标表示为未知变量的线性表达式，称之为目标函数；性表达式，称之为目标函数；对决策变量有非负要求。对决策变量有非负要求。在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小线性规划数学模型的组成：目标函数 Max F 或 Min F约束条件 s.t. (subject to) 满足于决策变量 用符号来表示可控制的因素3 LP的数学描述的数学描述 (数学模型数学模型 )： 一般形式 += )( 2211 nnxcxcxcZMinMax 或=+=+=+0,),(),(),(2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabx axaxats + 三、三、 LP的标准型：的标准型：1、 LP标准型的概念标准型的概念（ 1）什麽是）什麽是 LP的标准型？的标准型？（ 2） LP标准型的特点标准型的特点 目标函数约定是极大化目标函数约定是极大化 Max; 约束条件均用等式表示约束条件均用等式表示 ; 决策变量限于取非负值决策变量限于取非负值 ; 右端常数右端常数 b均为非负值均为非负值 ;即标准形式为： （ 1）展开式 += 2211 nnxcxcxcMax=+=+=+0,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabx axaxats +（ 2）紧缩形式）紧缩形式=njxmibxatsxcZMaxjnjijijnjjj,2,10,2,111 （ 3）矩阵形式其中 : ),( 21 ncccC =T= ),(21 nxxxXTmbbbb ),( 21=mnmmnnaaaaaaaaaA212222111211（ 4）向量 矩阵形式：其中：njaaaP Tmjjjj ,2,1,),( 21 =),( 21 nPPPA =2、 LP问题的标准化问题的标准化 （ 1）目标函数的标准化）目标函数的标准化 MinZ=CX MaxZ=-CXZ=-Z目标函数标准化示意图目标函数标准化示意图（ 2） 约束条件的标准化约束条件的标准化 & 约束条件是约束条件是 类型类型 左边左边 加加 非负松弛变量非负松弛变量 & 约束条件是约束条件是 类型类型 左边左边 减减 非负剩余变量非负剩余变量 & 变量符号不限变量符号不限 引入新变量（引入新变量（ 0）& 常数项常数项 b0 约束条件的两边同乘约束条件的两边同乘 -1例例 1.4 将下列问题化成标准型将下列问题化成标准型 :Min S = -x1+2x2-3x3s.t. x1+x2+x3 7x1-x2+x3 2-3x1+x2+2x3 = - 5x1,x2 0, x3 无非负限制无非负限制Max S=x1-2x2+3x3x1+x2+x3 +x4=7x1-x2+x3 x5= 23x1-x2-2x3 = 5令 x3=x3-x3Max S = x1-2x2+3x3 -3x3 +0x4+0x5s.t. x1+x2+x3 -x3 +x4 =7x1-x2+ x3 -x3 -x5=23x1-x2-2x3 +2x3 = 5x1, x2