- 1、本文档共30页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第 PAGE 6 页 共 NUMPAGES 27 页
第一部分 线性规划问题的求解
一、两个变量的线性规划问题的图解法:
㈠概念准备:
定义:满足所有约束条件的解为可行解;可行解的全体称为可行(解)域。
定义:达到目标的可行解为最优解。
㈡图解法:
图解法采用直角坐标求解:x1——横轴;x2——竖轴。
1、将约束条件(取等号)用直线绘出;
2、确定可行解域;
3、绘出目标函数的图形(等值线),确定它向最优解的移动方向;
注:求极大值沿价值系数向量的正向移动;求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
㈢参考例题:(只要求下面这些有唯一最优解的类型)
例1:某厂生产甲、乙两种产品,这两种产品均需在A、B、C三种不同的设备上加工,每种产品在不同设备上加工所需的工时不同,这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示:
品产耗消备设
品
产
耗
消
备
设
A B C
利润
(万元)
甲
乙
3 5 9
9 5 3
70
30
有效总工时
540 450 720
——
问:该厂应如何组织生产,即生产多少甲、乙产品使得该厂的总利润为最大?
(此题也可用“单纯形法”或化“对偶问题”用大M法求解)
解:设x1、x2为生产甲、乙产品的数量。
⑴max z = 70x1+30x
⑴
⑵
⑵
⑸、⑹
⑸、⑹
⑷
⑶
可行解域为oabcd0,最优解为b点。
由方程组
解出x1=75,x2=15
∴X*==(75,15)T
∴max z =Z*= 70×75+30×15=5700
例2:用图解法求解
⑴max z = 6x1+4x
⑴
⑵
⑵
⑸、⑹
⑸、⑹
⑷
⑶
解:
可行解域为oabcd0,最优解为b点。
由方程组
解出x1=2,x2=6
∴X*==(2,6)T
∴max z = 6×2+4×6=36
例3:用图解法求解
⑴min z =-3x1+x
⑴
s.t.
⑵
⑵
⑶
⑷
⑸
⑹、⑺
解:
可行解域为bcdefb,最优解为b点。
由方程组 解出x1=4,x2=
∴X*==(4,)T
∴min z =-3×4+=-11
二、标准型线性规划问题的单纯形解法:
㈠一般思路:
1、用简单易行的方法获得初始基本可行解;
2、对上述解进行检验,检验其是否为最优解,若是,停止迭代,否则转入3;
3、根据θL规则确定改进解的方向;
4、根据可能改进的方向进行迭代得到新的解;
5、根据检验规则对新解进行检验,若是最优解,则停止迭代,否则转入3,直至最优解。
㈡具体做法(可化归标准型的情况):
设已知
max z = c1x1+ c2x2+…+ cnxn
s.t.
对第i个方程加入松弛变量xn+i,i =1,2,…,m,得到
列表计算,格式、算法如下:
CB
XB
b
c1
c2
…
cn+m
θL
x1
x2
…
xn+m
cn+1
xn+1
b1
a11
a12
…
a1 n+m
c n+2
xn+2
b2
a21
a22
…
a2 n+m
.
.
.
.
.
.
.
.
.
…
…
…
…
cn+m
xn+m
bn
am1
am2
…
am n+m
z1
z2
…
zn+m
σ1
σ2
…
σn+m
注①: zj =cn+1 a1j+ cn+2 a2j +…+ cn+m amj=,(j=1,2,…
σj =cj-zj ,当σj ≤0时,当前解最优。
注②:由max{σj}确定所对应的行的变量为“入基变量”;
由θL=确定所对应的行的变量为“出基变量”,行、列交叉处为主元素,迭代时要求将主元素变为1,此列其余元素变为0。
例1:用单纯形法求解(本题即是本资料P2“图解法”例1的单纯形解法;也可化“对偶问题”求解)
max z =70x1+30x2
s.t.
解:加入松弛变量x3,x4,x5,得到等效的标准模型:
max z =70
您可能关注的文档
最近下载
- 口腔粘膜病的病例汇报.pptx VIP
- 2023华为认证HCIE-Datacom H12-891新题库版-下(其它题部分).pdf VIP
- 医院信息系统建设可行性报告.doc
- 河北省石家庄二中实验学校2022-2023学年高一11月期中生物试题(解析版).docx
- 小学语文群文阅读教学讲座材料:问道群文阅读,创生多维课堂ppt课件.pptx VIP
- 曹冲称象 跨学科项目式学习设计方案.docx
- 必威体育精装版光伏发电PHC管桩施工方案.pdf
- 央视100集纪录片《中国通史》文字稿.docx
- 大学物理 II-(热学、振动和波、光学、量子)(北京交大)中国大学MOOC慕课 章节测验期末考试客观题答案.docx
- 《群文阅读的实施方法和策略》 课件.pptx VIP
文档评论(0)