第3章31线性规划问题及其数学模型

第二章、第二章、 线性规划线性规划3.1 线性规划的概念线性规划的概念一、一、 线性规划问题的提出线性规划问题的提出 利用有限资源利用有限资源某工厂在计划期内要安排生产 、 两种产品，已知生产单位产品所需的设备台数及 A、 B两种原材料的消耗量，见表 2-1。该工厂每生产一件产品 可获利润 2元，每生产一件产品 可获利润 3元，问应如何安排生产计划使该工厂获得的利润最大？ 生产计划问题生产计划问题产品资源 资源限量设备 (台 时 ) 1 2 8原材料 A(g) 4 0 16000原材料 B(g) 0 4 12000如何制定生产计划，使两种产品总利润最大？如何制定生产计划，使两种产品总利润最大？利用有限资源：某鸡厂共饲养利用有限资源：某鸡厂共饲养 1万只鸡，用大豆和万只鸡，用大豆和谷物混合喂养，已知鸡消耗饲料谷物混合喂养，已知鸡消耗饲料 1kg /天，天， 鸡至少需鸡至少需要蛋白质、钙分别为要蛋白质、钙分别为 0.22、 0.06 kg/天，每公斤大豆天，每公斤大豆含蛋白质、钙为含蛋白质、钙为 50、 2，每公斤谷物含蛋白质，每公斤谷物含蛋白质、钙为、钙为 10、 10，大豆和谷物售价，大豆和谷物售价 0.4、 0.2元元 /kg。饲 料成分 大豆 谷物 营 养 /天天 .鸡鸡蛋白 质 .kg 50 10 0.22钙 .kg 2 10 0.06售价 .元 0.4 0.2设：每只鸡需要大豆 x1公斤，谷物 x2公斤，=+=2,1,00.220.20.42121jx0.1x 0.5xtsxxMinZj+ 0.0621 0.1x0.02x+ 121 xx=+=2,1,00.22100000.20.42121jx0.1x 0.5xtsxxMinZj+ 0.061000021 0. 1x 0.02x+ 1000021 xx设：养鸡场每天需要大豆 x1公斤，谷物 x2公斤二、线性规划的定义和数学描述（模型）二、线性规划的定义和数学描述（模型）1定义：定义：对于求取一组变量对于求取一组变量 xj (j =1,2,n)， 使之使之既满足线性约束条件，又使具有线性表达式的既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（题称为线性规划问题，简称线性规划（ LP）。）。2.配比问题和生产计划问题的线性规配比问题和生产计划问题的线性规划模型的特点：划模型的特点： 用一组未知变量表示要求的方案，这组用一组未知变量表示要求的方案，这组未知变量称为决策变量；未知变量称为决策变量；存在一定的限制条件，且为线性表达式存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线是最小化），目标表示为未知变量的线性表达式，称之为目标函数；性表达式，称之为目标函数；对决策变量有非负要求。对决策变量有非负要求。3 LP的数学描述的数学描述 (数学模型数学模型 )： （ 1）一般形式 += )( 2211 nnxcxcxcZMinMax 或=+=+=+0,),(),(),(2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabx axaxats + （ 2）紧缩形式）紧缩形式=njxmibxatsxcZMinMaxjnjijijnjjj,2,10,2,1),()(11或 （ 3）矩阵形式其中 : ),( 21 ncccC =T= ),(21 nxxxXTmbbbb ),( 21=mnmmnnaaaaaaaaaA212222111211（ 4）向量 矩阵形式：其中：njaaaP Tmjjjj ,2,1,),( 21 =),( 21 nPPPA =三、三、 LP的标准型：的标准型：1、 LP标准型的概念标准型的概念（ 1）什麽是）什麽是 LP的标准型？的标准型？（ 2） LP标准型的特点标准型的特点 目标函数约定是极大化目标函数约定是极大化 Max（或（或 Min） ; 约束条件均用等式表示约束条件均用等式表示 ; 决策变量限于取非负值决策变量限于取非负值 ; 右端常数右端常数 b均为非负值均为非负值 ;（ 3）数学表达式）数学表达式 :有几种形式有几种形式 ?为什麽为什麽 ?如何书写如何书写 ? 2、 LP问题的标准化问题的标准化 （ 1）目标函数的标准化）目标函数的标准化 MinZ=CX MaxZ=-CXZ=-Z目标函数标准化示意图目标函数标准化示意图（ 2） 约束条件的标准化约束条件的标准化 &