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