版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
最优化方法线性规划的基本概念
线性规划问题及其数学模型线性规划的图解法线性规划问题的标准型标准型线性规划的解线性规划的基本原理1.问题的提出:
在生产管理的经营活动中,通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源:劳动力、原材料、设备或资金等最佳:有一个标准或目标,使利润达到最大或成本达到最小。有限资源的合理配置有两类问题如何合理的使用有限的资源,使生产经营的效益达到最大;在生产或经营的任务确定的条件下,合理的组织生产,安排经营活动,使所消耗的资源数最少。1.1线性规划问题及其数学模型例1:某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每周可提供的资源总量如下表所示:每吨产品的消耗每周资源总量甲乙维生素(公斤)
3020160设备(台)
5115
已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果,甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大?
定义:
x1为生产甲种药品的计划产量数,
x2为生产乙种药品的计划产量数。
目标:要使总利润最大化maxz=5x1+2x2
约束:每周资源总量的限制,
30x1+20x2≤1605x1+x2≤15甲种药品每周产量不应超过4吨的限制x1≤4计划生产数不可能是负数,x1≥0x2≥0每吨产品的消耗
每周资源总量甲乙维生素(公斤)3020160设备(台)
5115单位利润(万元)
52
数学模型为每吨产品的消耗每周资源总量甲乙维生素(公斤)3020160设备(台)5115单位利润(万元)52这是一个如何合理的使用有限的资源,使生产经营的效益达到最大的数学规划问题。在满足一组约束条件的限制下,寻求决策变量x1,x2的决策值,使目标函数达到最大值。例2:某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有A、B、C三种化学成分,两种原料分别所含三种化学成分的百分比含量,以及按合同规定的产品中三种化学成分的最低含量如下表所示:已知甲、乙两种原料的成本分别是每公斤3元和2元,厂方希望总成本达到最小,问如何配置该产品?
原料化学成分含量(%)产品中化学成分的最低含量(%)甲乙A1234B232C3155化学成分定义x1,x2分别为每公斤产品中甲,乙两种原料的数量,目标:使总成本最小化minz=3x1+2x2约束:配料平衡条件,x1+x2=1产品中A、B、C三种化学成分的最低含量
12x1+3x2≥4
2x1+3x2≥2
3x1+15x2≥5非负性条件x1≥0,x2≥0
原料化学成分含量(%)产品中化学成分的最低含量(%)甲乙A1234B232C3155单位成本(元)32化学成分数学模型:
原料化学成分含量(%)产品中化学成分的最低含量(%)甲乙A1234B232C3155单位成本(元)32化学成分这是一个原料配制问题,是在生产任务确定的条件下,合理的组织生产,使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时,寻求变量x1和x2的值使目标函数取得最小值。例3:某铁器加工厂要制作100套钢架,每套要用长为2.9米,2.1米和1.5米的圆钢各一根。已知原料长为7.4米,问应如何下料,可使材料最省?
分析:在长度确定的原料上截取三种不同规格的圆钢,可以归纳出8种不同的下料方案:圆钢(米)ⅠⅡⅢⅣⅤⅥⅦⅦ2.9120101002.1002211301.531203104料头(米)00.10.20.30.80.91.11.4
问题归纳为如何混合使用这8种不同的下料方案,来制造100套钢架,且要使剩余的余料总长为最短。
设表示用第j种下料方案下料的原料根数,j=1,2…,8,目标:使余料总长度最小化minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8约束:三种规格圆钢根数x1+2x2+x4+x6=100
2x3+2x4+x5+x6+3x7=1003x1+x2+2x3+3x5+x6+4x8=100非负取整条件xj≥0(j=1,2…8)且取整数圆钢(米)ⅠⅡⅢⅣⅤⅥⅦⅦ2.9120101002.1002211301.531203104余料(米)00.10.20.30.80.91.11.4
数学模型
s.t.
这是一个下料问题,是在生产任务确定的条件下,合理的组织生产,使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最小值。圆钢(米)ⅠⅡⅢⅣⅤⅥⅦⅦ2.9120101002.1002211301.531203104料头(米)00.10.20.30.80.91.11.4且为整数
与规划问题有关的数学模型总有两部分组成:
约束条件:反映了有限资源对生产经营活动的种种约束,或者生产经营必须完成的任务;目标函数:反映生产经营者在有限资源条件下希望达到的生产或经营的目标。2.线性规划的一般数学模型
线性规划模型的特征:(1)用一组决策变量x1,x2,…,xn表示某一方案,且在一般情况下,变量的取值是非负的。(2)有一个目标函数,这个目标函数可表示为这组变量的线性函数。(3)存在若干个约束条件,约束条件用决策变量的线性等式或线性不等式来表达。(4)要求目标函数实现最大化(max)或最小化(min)。满足上述4个特征的规划问题称为线性规划问题。通常称为决策变量,为价值系数,为消耗系数,为资源限制系数。线性规划的模型的一般形式:目标函数
满足约束条件min(max)1.2线性规划的图解法
适用于求解两个变量的线性规划问题1.图解法的基本步骤例4:利用例1说明图解法的主要步骤,例1的数学模型为O51015x1x1=4x2101AB(2,5)C▽z5x1+x2=1530x1+20x2=1605x1+2x2=5
线性规划图解法的基本步骤(1)建立以x1,x2为坐标轴的直角坐标系,画出线性规划问题的可行域,(2)求目标函数z=C1x1+C2x2的梯度▽z=(c1,c2),(3)任取等值线
C1x1+C2x2=z0,沿梯度▽z正方向平移,
(若是极小化问题,则沿负梯度方向-▽z平移),求等直线将离未离可行域时与可行域的交点。(4)若交点存在,则该点坐标就是最优解X*
。例如:max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8
x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2192.图解法的几种可能结果
(1)有唯一最优解,如例1
则目标函数等值线10x1+2x2=z
与第二约束5x1+x2≤15
的边界线平行。将等值线沿梯度▽z=(10,2)正方向平移至B点时与可行域OABC的整条边界线AB重合。这表明线段AB上的每一点都使目标函数取得同样的最大值,因而都是最优解。(2)有无穷多最优解如例1中的目标函数设为:maxz=10x1+2x2
例5:试用图解法求解下列线性规划问题
(3)无界解(或称无最优解)无界解是指线性规划问题的最优解无界。若是极大化问题,则可使目标函数值z→+∝,
极小化问题则可使目标函数值z→-∝,有无界解的线性规划问题的可行域通常是无界区域,但反之则不必然。-1O24x1x224-▽z=(3,2)-2x1+x2=2x1-3x2=3-1O33(4)无可行解某些线性规划问题的可行域是空集,既不存在满足所有约束条件的点,这时问题无可行解,当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的要求,既不存在可行方案。
(3)无界解(或称无最优解)无界解是指线性规划问题的最优解无界。若是极大化问题,则可使目标函数值z→+∝,
极小化问题则可使目标函数值z→-∝,有无界解的线性规划问题的可行域通常是无界区域,但反之则不必然。1.标准线性规划模型
(1)线性规划问题的标准形式:
其中(1.1)为目标函数,(1.2)为约束条件,(1.3)为非负条件,为称呼方便,有时将(1.3)也称为约束条件。(1.2)
(1.3)1.3线性规划的标准形式(1.1)其中C=(c1,c2,…,cn)称为价值向量,
X=(x1,x2,…,xn)T为决策变量向量,
Pj=(a1j,x2j,…,xmj)T为决策变量xj所对应的消耗系数向量,
b=(b1,b2,…,bm)T为资源向量。(2)紧凑格式:(3)向量格式:其中为m×n阶矩阵(4)矩阵格式:C=(c1,c2,…,cn),
X=(x1,x2,…,xn)T,
b=(b1,b2,…,bm)T。262.非标准形式线性规划问题的标准化(1)极大化与极小化:原目标函数(2)
线性不等式与线性等式:其中xn+i
为非负松弛变量,其中xn+k
为非负剩余变量。
(3)非负变量与符号不受限制的变量若xi的符号不受限制,则可引进非负变量xi1,xi2,令
xi=xi1-xi2,使线性规划里所有的变量都转化为有非负限制的变量。(4)右端项有负值的问题:在标准形式中,要求右端项必须每一个分量非负。当某一个右端项系数为负时,如bi<0,则把该等式约束两端同时乘以-1,得到:-ai1x1-ai2x2-…-ain
xn
=-bi
。28例6:将下述线性规划问题化为标准型
符号不受限制解:令,可将目标函数化为min型,令,其中29考虑一个标准的线性规划问题:1.4标准型线性规划的解其中C为n维行向量,
X是n维列向量,
b是m维列向量,
A是m×n阶矩阵,假定满足m≤n,且R(A)=m.30
(2)最优解:使目标函数(1.4)达到最优值的的可行解称为最优解,最优解常用X*
表示。
(3)基:若B是A中m×m阶非奇异矩阵,即|B|≠0,则称B是线性规划问题的一个基。可行解集称为线性规划问题的可行域。线性规划问题解的概念:
(1)可行解:满足约束条件(1.5),(1.6)的解称为线性规划问题的可行解。31一个线性规划的基通常不是唯一的,但是基的个数也不会超过Cnm
个。一旦确定了线性规划的基,则相应的基向量、基变量和非基变量也就确定。若B是线性规划问题的一个基,那么B一定是由m个线性无关的列向量组成,不失一般性,可设
称为基向量,
与基向量Pj相对应的变量xj(j=1,2,…,m)称为基变量。32(4)基本解。设B是线性规划的一个基,若令n-m个非基变量等于0,则所得的方程组AX=b的解称为线性规划问题的一个基本解(简称基解)。有一个基就可以求得一个基本解。由基的有限性可知,基本解的个数也不会超过Cnm
个。由于基本解中的非零分量可能是负数,所以基本解不一定是可行的。(5)基本可行解。满足非负条件的基本解称为基本可行解(简称基可行解)。与基本可行解对应的基成为可行基。基本可行解的非零向量的个数小于等于m,并且都是非负的。由于基本可行解的数目一般少于基本解的数目,因此可行基的数目也要少于基的数目。
当基本可行解中有一个或多个基变量是取零值时,称此解为
退化的基本可行解。33
线性规划问题各种解的关系可用文氏图表示,
可行解
基本解基本可行解34例7:求下列约束方程所对应的线性规划的所有基本解,基本可行解。解:化为标准形式后为2×4阶矩阵。且R(A)=2,所以该线性规划基的个数≤=6个
若令非基变量,约束方程组为可得对应的基本解是一个基本可行解。x1,x2为基变量,35对应基本基本解对应基本基本解对应基本基本解
按相同步骤,可求得线性规划其他4个基:对应基本基本解36若利用图解法画出线性规划的可行域,如图,COBA448371.5
线性规划的基本原理
由图解法的步骤,可以从几何的角度得出以下两个结论:(1)线性规划问题的可行域是一个有界或无界的凸多边形,其顶点个数是有限个。(2)若线性规划问题有最优解,那么最优解一定可在可行域的某个顶点上找到。38(1)凸集:设K是n维欧式空间的一个点集,若任意两点X(1)∈K,X(2)∈K的连线上的一切点αX(1)+(1-α)X(2)∈K
(0<α<1),则称K为凸集。1.几个基本概念
线性约束条件凸集例顶点个数有限有限无限有限无限非凸集例39(1)凸集:设K是n维欧式空间的一个点集,若任意两点X(1)∈K,X(2)∈K的连线上的一切点αX(1)+(1-α)X(2)∈K
(0<α<1),则称K为凸集。1.几个基本概念
连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。线性约束条件凸集定义的几何解释40(2)凸组合:设X(1),X(2),…,X(k)是n维欧式空间En中的k个点,若存在μ1,
μ2,…,μk满足0≤μi≤1,(i=1,2,…,k),且μ1+μ2+…+μk=1,使X=μ1X(1)+μ2X(2)+…μk
X(k),则称X为X(1),X(2),…,X(k)的凸组合。凸组合的几何意义
凸集K中任意两点X(1),X(2)连线上的任一点X都是X(1)与X(2)的一个凸组合。41X(1)X(3)X(2)X’X=
X’
+(1-
)X(2),(0<
<1)x1x2OX’=
X(1)+(1-
)X(3),
(0<
<1)42X(1)X(3)X(2)X’X=u1X(1)+u2X(2)+u3X(3)x1x2OX’=
X(1)+(1-
)X(3),
(0<
<1)43(2)凸组合:设X(1),X(2),…,X(k)是n维欧式空间En中的k个点,若存在μ1,
μ2,…,μk满足0≤μi≤1,(i=1,2,…,k),且μ1+μ2+…+μk=1,使X=μ1X(1)+μ2X(2)+…μk
X(k),则称X为X(1),X(2),…,X(k)的凸组合。凸集K中任意两点X(1),X(2)连线上的任一点X都是X(1)与X(2)的一个凸组合。(3)顶点:设K为凸集,X∈K,若X不能用X(1)∈K,X(2)∈K两点(X(1)≠X(2))的一个凸组合表示为X=αX(1)+(1-α)X(2),其中0<α<1,则称X为K的一个顶点。或若凸集K中的点X不能成为K中任何线段的内点,则称X为K的一个顶点。44定理1:若线性规划问题存在可行域,则其可行域
D={X/AX=b,x≥0}是一个凸集。
证明:为了证明满足AX=b,X≥0的所有点(可行解)组成的几何体是凸集,只要证明D中任意两点任意两点X(1),X(2)
连线上的一切点均满足线性约束条件既可。2.线性规划的基本定理
任取,满足则对任意的有又因为均≥0,所以由此可知,即D是凸集。45证明:必要性:因为X是基本解,由基本解的定义,X的非零分量所对应的系数列向量线性无关,又因为X是可行解,由基本可行解的定义,非零分量均是正的,所以X的正分量所对应的系数列向量线性无关。
充分性:设X是线性规划问题的可行解,且正分量所对应的列向量也线性无关,则必有k≤m,若k=m,则刚好构成一个基,为相应的基本可行解。若k<m,则由线性代数知识,一定可以从其余的n-k个系数列向量中取出m-k个与构成最大线性无关向量组,其对应的基本可行解恰好为X,不过此时的X是一个退化的基本可行解。
引理1:线性规划问题的可行解
是基本可行解的充要条件是X的正分量所对应的系数列向量线性无关。46
定理2:设线性规划问题的可行域,则X是D的一个顶点的充分必要条件是X为线性规划问题的基本可行解。
证明思路:必要性:由引理1,若X是D的一个顶点,要证明X是线性规划的一个基本可行解,只要证明X的正分量所对应的系数列向量线性无关。
用反证法,倘若X的正分量所对应的系数列向量线性相关,则可以在D中找到两点,使,与X是D的顶点矛盾.
充分性:若X是线性规划的一个基本可行解,要证明X是可行
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2027年5月模拟考试高一生物易错题卷及答案
- 2027年5月模拟考试一年级数学押题卷及答案
- 2027年3月月考八年级道德与法治检测卷及答案
- 2026年高职(铁道工程技术)铁路路基施工资格考试试题及答案
- 2026年代谢慢病康复随访考点试卷及答案
- 2025届郧县三下数学期末统考试题含解析
- 八年级历史期末测试卷2025年亮点:世界古代史历史人物生平
- 2025年银行审计岗招聘笔试真题(附答案)
- 2025年银行贸易融资岗面试题库含答案
- 2025年银行结构化面试真题及答案
- 2026年上海市安全员B证(项目负责人)试题及解析附答案
- 《隧道施工与管理》全套教学课件
- T/ZACM 001-2025脑卒中后吞咽障碍耳穴压豆技术
- EPC项目图纸会审与深化方案
- 2026吸入制剂技术突破与呼吸系统药物开发报告
- DB32-T 5434-2026 太湖流域农业面源污染负荷评估规范
- 初中数学九年级上册圆的基本概念知识清单
- 2026年内江市科级干部任职资格考试题库附答案
- 遵义会议放光辉混声合唱谱
- 晕针患者麻醉管理
- 呼吸困难患者护理试题(带答案)
评论
0/150
提交评论