- 1、本文档共30页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
|
第一部分 线性规划问题的求解
一、两个变量的线性规划问题的图解法:
㈠概念准备:
定义:满足所有约束条件的解为可行解;可行解的全体称为可行(解)域。
定义:达到目标的可行解为最优解。
㈡图解法:
图解法采用直角坐标求解:x1——横轴;x2——竖轴。
1、将约束条件(取等号)用直线绘出;
2、确定可行解域;
3、绘出目标函数的图形(等值线),确定它向最优解的移动方向;
注:求极大值沿价值系数向量的正向移动;求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
㈢参考例题:(只要求下面这些有唯一最优解的类型)
例1:某厂生产甲、乙两种产品,这两种产品均需在A、B、C三种不同的设备上加工,每种产品在不同设备上加工所需的工时不同,这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示:
品产耗消备设
品
产
耗
消
备
设
A B C
利润
(万元)
甲
乙
3 5 9
9 5 3
70
30
有效总工时
540 450 720
——
问:该厂应如何组织生产,即生产多少甲、乙产品使得该厂的总利润为最大?
(此题也可用“ HYPERLINK \l P2例1的单纯形解法 单纯形法”或化“ HYPERLINK \l P7例1的对偶问题大M解法 对偶问题”用大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“ HYPERLINK \l P7例1的图解法 图解法”例1的单纯形解法;也可化“ HYPERLINK \l
您可能关注的文档
最近下载
- 固体废物管理知识培训课件.ppt VIP
- Midjourney 人工智能AI绘画教程:从娱乐到商用 课件 第1章 Midjourney 人工智能绘画简介.pptx
- 某啤酒厂废水处理工艺设计(4000m3d.docx
- 2025年无锡工艺职业技术学院单招职业技能测试题库及1套参考答案.docx VIP
- 高中课件:晶胞投影与原子分数坐标.ppt
- 高考“散文六种常考句段作用”题例解.doc VIP
- 2025年国航机务系统AMECO技术员岗位校园招聘笔试参考题库附带答案详解.pdf
- 中国翻译服务规范.PDF
- (高清版)DB33∕T 2080-2017 文化馆服务规范 .pdf VIP
- 2024年无锡工艺职业技术学院单招职业技能测试题库(全优).docx VIP
文档评论(0)