第1章1.1-1.3线性规划与单纯形方法ppt课件.ppt

《第1章1.1-1.3线性规划与单纯形方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章线性规划与单纯形方法1应用最广泛的运筹学方法根据统计，应用最广泛的运筹学学方法为：数学规划（线性规划，整数规划）模拟网络模型（包括PERT/CPM）决策分析排队理论库存模型2最基本的运筹学方法网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的；解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大；3第一章线性规划与单纯形方法线性规划的数学模型图解法线性规划的基本原理单纯形法4例1.1生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价50元，椅子售价30元，生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木

2、工3小时，油漆工1小时。该厂每月可用木工工时为120，油漆工工时为50。该厂如何生产才能使每月销售收入最大？引例5生产价格高的产品：能生产25个桌子，木工剩余20小时，销售收入1250元；替代生产方案1：生产20个桌子，10个椅子，木工仍剩余10小时，销售收入1300元；替代生产方案2：生产15个桌子，20个椅子，用完全部工时，销售收入1350元；生产方案6可能的生产方案用手工计算也可找出很多可行方案；对于简单问题有时也可找到最优方案；当问题更复杂时，如有20种产品，消耗10种资源，用人工计算是否有效？一个很简单的问题都可能存在无数可行解，从中找出

3、最优解不是容易的事。线性规划模型是求解这类问题的有效工具。7生产计划数学模型决策变量：模型要决定的未知量x1=生产桌子的数量，x2=生产椅子的数量。目标函数：决定线性规划优化方向max:z=50x1+30x2约束方程：反映客观条件的限制木工工时不能超过可用工时4x1+3x2120油漆工工时不能超过可用工时2x1+x250非负约束：变量取值的限制x10，x208生产计划问题的完整模型max:z=50x1+30x2s.t.4x1+3x21202x1+x250x10，x209例1.2营养配餐问题假定一个成年人每天需要从食物中获取3000大

4、卡的热量、55克蛋白质和800毫克的钙，市场上只有四种食品可供选择。它们每公斤所含热量和营养成分以及市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小。1.1线性规划的数学模型10食物营养表序号食品热量蛋白质钙价格名称(大卡)(g)(mg)(元)1猪肉100050400142鸡蛋8006020063大米9002030034白菜20010500211营养配餐模型变量：xj每天购入j种食品数量。目标函数：每天采购成本最小min:z=14x1+6x2+3x3+2x4约束方程：满足每天的营养要求满足3000大卡的热量要求1000x1+80

5、0x2+900x3+200x43000满足蛋白质摄入量要求：50x1+60x2+20x3+10x455满足钙摄入量要求：400x1+200x2+300x3+500x4800非负约束--采购量不能为负值x1，x2，x3，x4012营养配餐问题的完整模型min:z=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x4013线性规划是求一个线性函数在满足一组线性等式或不等式方程条件

6、下极值的数学问题的统称。线性规划的数学模型由三部分组成：1需要确定的决策变量；2需要优化（求极大或极小）的目标函数；3必须满足的约束条件。14某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354练习15问题分析16数学模型17线性规划问题的一般形式可以写为：max(min):z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn(=

7、,)b1······am1x1+am2x2+…+amnxn(=,)bmx1,x2,…,xn02.线性规划的一般模型18x1,...,xn为决策变量，表示第n种生产经营活动的规模，z=c1x1++cnxn称为目标函数，反映生产活动的目标。cj(j=1,2,...,n)为目标函数系数（又称价值系数）。表示与活动相关的费用或收益。ai1x1+ai2x2+…+ainxnbi为使用第i种资源的资源限制约束；aij为技术系数或投入产出系数，代表第j种经营活动需要第i种资源的单位投入或产出量，列向量b=(b1,...,bm)代表m种资源的可用量，

8、bi称为资源限量。xj0是限制决策变量的取值范围的非负约束19注：线性规划隐含的假定线性规划要求目标函数和约束方程必须是