




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第一章、线性规划及单纯形法线性规划(LinearProgramming,LP)是运筹学的一个重要分支。一、问题提出什么是线性规划模型?线性规划模型的特点是什么?如何建立线性规划模型?标准化的提出及实现定义:对于求取一组变量xj(j=1,2,......,n),使之既满足线性约束条件,又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题,简称线性规划(LP)。线性规划模型的特点:
用一组未知变量表示所求的方案,这组未知变量称为决策变量;存在一定的限制条件,且为线性表达式,称之为约束方程;有一个目标要求(最大化或最小化),目标表示为未知变量的线性表达式,称之为目标函数;线性规划数学模型的三要素:目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素例1
胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个,椅子销售价格30元/个,生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时,油漆工2小时。生产一个椅子需要木工3小时,油漆工1小时。该厂每个月可用木工工时为120小时,油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大?线性规划模型
maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20线性规划数学模型三要素:
决策变量、约束条件、目标函数例2
营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择,它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小?各种食物的营养成分表解:设x1为每天猪肉的购入量,x2为鸡蛋的购入量,x3为大米的购入量,x4为白菜的购入量,则配餐问题的线性规划模型为:
minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1,x2,
x3,x40LP数学模型:+++=…)(2211nnxcxcxcZMinMax或≥=+++≥=+++≥=++0,,,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≤≤≤≥无限制二、线性规划模型的标准化:将一般形式→标准型线性规划的标准形式有如下四个特点:目标最大化;约束为等式;决策变量均非负;右端项非负。
问题:如何将一般形式的线性规划模型化为标准型,使其满足以下四个特点?目标最大化;约束为等式;决策变量均非负;右端项非负。
(1)目标函数为最小化:令Z'=-Z,则maxZ'=-CX。(2)约束方程为不等式:不等号左端加(减)松弛变量(剩余变量)。(3)决策变量xi小于零:令xi'=-xi
,替换原变量;决策变量xi无约束:令xi=xi‘-xi’‘,替换原变量。(4)右端常数项小于零;两边同乘-1。例3
将下列问题化成标准型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=-5x1,x2
0,x3
无非负限制
MaxS’=x1-2x2+3x3x1+x2+x3+x4=7
x1-x2+x3–x5=2
3x1-x2-2x3=5令x3=x3’-x3’’MaxS
=x1-2x2+3x3-3x3+0·x4+0·x5s.t.x1+x2+x3-x3+x4=7x1-x2+x3-x3-x5=2
3x1-x2-2x3
+2x3
=5x1,x2,
x3,x3,x4,x50标准型为:
练习:课后习题标准型的几种形式:(1)展开式+++=…2211nnxcxcxcMax=+++=+++=++0,,,..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≥(2)紧缩形式=≥===∑==njxmibxatsxcZMaxjnjijijnjjj,2,10,2,1..11∑……(3)矩阵形式其中:),,(21ncccC…=T=),,(21nxxxX…Tmbbbb),,,(21…==mnmmnnaaaaaaaaaA…………………2122221112
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年房屋租赁合同范本3
- 2025无固定期限劳动合同范本
- 年会会议合同范本
- 房顶更换简易合同范本
- 第12讲 二次函数图像与性质 4考点+16题型 2025年中考数学一轮复习讲练测(广东专用)
- 2025年劳动合同终止后如何顺利领取失业保险金
- 语言学导论知到课后答案智慧树章节测试答案2025年春内江师范学院
- 2025年度砂石料供应合同范本
- 2025授权软件开发合同
- 卤菜机构学员签合同(2025年版)
- 电动吸引器吸痰操作流程
- 《老师水缸破了》
- 2024-年广州市小升初英语真题含答案
- 自考06779应用写作学试卷(答案全面)
- 2023机电一体化技术专业介绍
- 公路路基施工技术规范 JTG∕T 3610-2019
- 养肝护肝科普课件
- 杜瓦瓶充装操作规程
- 7-1-2 现金规划案例分析
- 南书房家庭经典阅读书目300种书名
- 三菱触摸屏GS2107-WTBD、电脑同时与FX5U通信;两台触摸屏同时与PLC通信-图文RoZ
评论
0/150
提交评论