- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第1-2章 线性规划 整数规划
第一章 线性规划
§1 线性规划
在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支―数学规划,而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。
1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床,每台销售后的利润分别为4000元与3000元。生产甲机床需用A、B机器加工,加工时间分别为每台2小时和1小时;生产乙机床需用A、B、C三种机器加工,加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时,问该厂应生产甲、乙机床各几台,才能使总利润最大?
上述问题的数学模型:设该厂生产x1台甲机床和x2乙机床时总利润最大,则x1,x2
应满足
(目标函数)maxz=4x1+3x2 (1)
?2x1+x2≤10?x+x≤8?12
s.t.(约束条件)? (2)
≤7x?2??x1,x2≥0
(1)式被称为问题的目标函数,(2)中的几个不等式这里变量x1,x2称之为决策变量,
是问题的约束条件,记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性
函数,故被称为线性规划问题。
总之,线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最小的问题。
在解决实际问题时,把问题归结成一个线性规划数学模型是很重要的一步,但往往也是困难的一步,模型建立得是否恰当,直接影响到求解。而选适当的决策变量,是我们建立有效模型的关键之一。
1.2 线性规划的Matlab标准形式
线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便,Matlab中规定线性规划的标准形式为
min cTx x
?Ax≤b?
s.t. ?Aeq?x=beq
?lb≤x≤ub?
其中c和x为n维列向量,A、Aeq为适当维数的矩阵,b、beq为适当维数的列向量。
-1-
例如线性规划
max cTx s.t. Ax≥b x
的Matlab标准型为
min ?cx s.t. ?Ax≤?b
T
x
1.3 线性规划问题的解的概念
一般线性规划问题的(数学)标准型为
max
z=∑cjxj (3)
j=1
n
?n
?∑aijxj=bii=1,2,L,ms.t. ?j=1 (4)
?x≥0j=1,2,L,n?j
可行解 满足约束条件(4)的解x=(x1,x2,L,xn),称为线性规划问题的可行解,而使目标函数(3)达到最大值的可行解叫最优解。
可行域 所有可行解构成的集合称为问题的可行域,记为R。 1.4 线性规划的图解法 10987654321z=1200246810x1+x2=8(2,6)x2=72x1+x2=10图1 线性规划的图解示意图
图解法简单直观,有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。对于每一固定的值z,使目标函数值等于z的点构成的直线称为目标函数等位线,当z变动时,我们得到一族平行直线。对于例1,显然等位线越趋于右上方,其上的点具有越大的目标函数值。不难看出,本例的最优解为x*=(2,6),最优目标值
T
z*=26。
从上面的图解过程可以看出并不难证明以下断言:
(1)可行域R可能会出现多种情况。R可能是空集也可能是非空集合,当R非空时,它必定是若干个半平面的交集(除非遇到空间维数的退化)。R既可能是有界区域,也可能是无界区域。
(2)在R非空时,线性规划既可以存在有限最优
您可能关注的文档
- 初中数学中考一轮复习(21).docx
- 2021年必威体育精装版大学生入党志愿书三篇.docx
- 江苏省沭阳县潼阳中学2021届高三英语一轮复习:虚拟语气导学案.docx
- 浅议代理记账毕业论文.docx
- 2021小学指导青年教师工作计划.docx
- 全国执业医师注册申请表健康检查表聘用证明(完整版) 2.docx
- 新版大学德语四级考试阅读攻略.docx
- 在课改中成长 -.docx
- 广播电视台党支部事迹材料.docx
- 测量经典试题及答案汇总.docx
- 四川省德阳市罗江中学2025届高三考前热身化学试卷含解析.doc
- 山东省枣庄现代实验学校2025届高三下学期第五次调研考试化学试题含解析.doc
- 吉林省长春市十一高中等九校教育联盟2025届高三一诊考试生物试卷含解析.doc
- 2025届江苏省盐城市伍佑中学高考仿真模拟化学试卷含解析.doc
- 2025届广西贺州中学高考冲刺押题(最后一卷)生物试卷含解析.doc
- 安徽省池州市贵池区2025届高三第一次模拟考试生物试卷含解析.doc
- 宁夏银川一中2025届高三(最后冲刺)化学试卷含解析.doc
- 广东省广州市增城区四校联考2025届高考压轴卷化学试卷含解析.doc
- 2025届邯郸市第一中学高考生物必刷试卷含解析.doc
- 2025届安徽省安庆市石化第一中学高考仿真卷化学试卷含解析.doc
最近下载
- 山东省泰安市泰山区2023-2024学年上学期期中考试七年级英语试题.docx VIP
- 财务管理实务 财务管理实务 实训指导书.doc
- 2024年新人教版九年级上册化学全册教案.docx
- 上海通用汽车GVDP整车开发流程.pdf VIP
- 苏教版四年级上册同步奥数培优 第十四讲 智巧问题.pdf VIP
- 2024年江苏省苏州高新区招聘“两新”组织党建专职党务工作者6人历年【综合基础知识500题】高频考点模拟试题及参考答案解析.docx VIP
- 2024年武汉市东湖生态旅游风景区管理委员会公开招聘机关派遣制工作人员9人笔试备考试题及答案解析.docx VIP
- 人教版普通高中地理选择性必修2区域发展.pdf
- 人体解剖学常考重要知识点.doc
- 2023年江苏苏州相城区招考聘用两新组织党建专职党务工作者23人笔试历年难易错点考题荟萃附带答案详解.docx VIP
文档评论(0)