运筹学课件第一章线性规划及单纯形法_第1页
运筹学课件第一章线性规划及单纯形法_第2页
运筹学课件第一章线性规划及单纯形法_第3页
运筹学课件第一章线性规划及单纯形法_第4页
运筹学课件第一章线性规划及单纯形法_第5页
已阅读5页,还剩100页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第一章线性规划及单纯形法1、一般线性规划问题的数学模型2、图解法4、单纯形法的计算步骤5、单纯形法的进一步讨论6、线性规划模型的应用3、单纯形法原理

为了完成一项任务或达到一定的目的,怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的,这个过程就是规划。例1有一正方形铁皮,如何截取x使容积为最大?xa此为无约束极值问题一、一般线性规划问题的数学模型(一)、问题的提出

设备产品ABCD利润(元)

Ⅰ

2

1

4

0

2

Ⅱ

2

2

0

4

3有效台时12

81612

例2已知资料如下表所示,问如何安排生产才能使利润最大?或如何考虑利润大,产品好销。模型maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12此为带约束的极值问题1、问题中总有未知的变量,需要我们去解决。

要求:有目标函数及约束条件,一般有非负条件存在,由此组成规划数学模型。

如果在规划问题的数学模型中,变量是连续的(数值取实数)其目标函数是有关线性函数(一次方),约束条件是有关变量的线性等式或不等式,这样,规划问题的数学模型是线性的。反之,就是非线性的规划问题(其中一个条件符合即可)。(二)线性规划问题的数学模型目标函数:约束条件:①②③2、线性规划数学模型的一般形式也可以记为如下形式:目标函数:约束条件:如将上例用表格表示如下:设变量

产品j

设备i

有效台时

利润

向量形式:矩阵形式:规划确定型随机型静态规划动态规划线性规划非线性规划整数规划非整数规划整数规划非整数规划3、规划类型(三)线性规划问题的标准形式1、标准形式其中bi为非负①②③

2、特征:

⑴.目标函数为求极大值,也可以用求极小值;

⑵.所有约束条件(非负条件除外)都是等式,右端常数项为非负;

⑶.变量为非负。3、转换方式:

⑴.目标函数的转换如果是求极小值即,则可将目标函数乘以(-1),可化为求极大值问题。也就是:令,可得到上式。即⑵.约束方程的转换:由不等式转换为等式。称为松弛变量称为剩余变量⑶.变量的变换若存在取值无约束的变量,可令其中:例1将下列线性规划问题化为标准形式为无约束(无非负限制)

解:

用替换,且,将第3个约束方程两边乘以(-1)将极小值问题反号,变为求极大值标准形式如下:引入变量例2将线性规划问题化为标准型为无约束解:例3将下述线性规划模型化为标准形式。标准形式①②③(四)线性规划问题的解1、解的概念

⑴可行解:满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。

⑵最优解:使目标函数达到最大值的可行解。

⑶基:B是矩阵A中m×n阶非奇异子矩阵(∣B∣≠0),则B是一个基。则称Pj

(j=12……m)为基向量。∴

Xj

为基变量,否则为非基变量。

⑷基解:满足条件②,但不满足条件③的所有基对应的解,最多为个。

⑸基可行解:满足非负约束条件的基解,简称基可行解。

⑹可行基:对应于基可行解的基称为可行基。非可行解可行解基解基可行解Maxz=2x1+3x2

st.x1+x2≤3 x1+2x2≤4 x1,x2≥0

Maxz=2x1+3x2+0x3+0x4

st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解:X=(0,0)T,X=(0,1)T,X=(1/2,1/3)T

等。设B=1001,令,则|B|=1≠0,令x1=x2=0,则x3=3,x4=4,X=(0,0,3,4)T例:x3x4——基变量令B=1110x1x3

,则令x2=x4=0,则x3=-1,x1=4,X=(4,0,-1,0)T|B|=-1≠0,——非基可行解——基可行解标准化

建立直角坐标,图中阴影部分及边界上的点均为其解,是由约束条件来反映的。例1⑴⑵⑶⑷二、图解法012345678123456⑴⑵⑶⑷作图∴最优解:x1=4x2=2有唯一最优解,Z=14x2

x1(42)⑴⑵⑶⑷例2例3⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2

x2

⑴⑵x1x2

无可行解例4练习1⑴线性规划问题的可行域是凸集(凸多边形)。凸集凸集不是凸集顶点⑵最优解一定是在凸集的某一顶点实现(顶点数目不超过个)三、单纯形法原理⑶先找一个基可行解,与周围顶点比较,如不是最大,继续比较,直到找出最大为止。3、解的情况唯一解无穷解无界解无可行解有最优解无最优解(一)、基本思想将模型的一般形式变成标准形式,再根据标准型模型,从可行域中找一个基可行解,并判断是否是最优。如果是,获得最优解;如果不是,转换到另一个基可行解,当目标函数达到最大时,得到最优解。(二)、线性规划模型的标准形式1、标准形式四、单纯形法(三)、单纯形法例一、变成标准型约束方程的系数矩阵为基变量为非基变量I为单位矩阵且线性独立Maxz=2x1+3x2

st.x1+x2≤3 x1+2x2≤4 x1,x2≥0

Maxz=2x1+3x2+0x3+0x4

st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解:X=(0,0)T,X=(0,1)T,X=(1/2,1/3)T

等。设B=1001,令,则|B|=1≠0,令x1=x2=0,则x3=3,x4=4,X=(0,0,3,4)T回顾:x3x4——基变量令B=1110x1x3

,则令x2=x4=0,则x3=-1,x1=4,X=(4,0,-1,0)T|B|=-1≠0,——非基可行解——基可行解标准化令:则:∴基本可行解为(001281612)

此时,Z=0然后,找另一个基可行解。即将非基变量换入基变量中,但保证其余的非负。如此循环下去,直到找到最优解为止。注意:为尽快找到最优解,在换入变量时有一定的要求。如将目标系数大的先换入等。找出一个初始可行解是否最优转移到另一个目标函数(找更大的基可行解)最优解是否循环直到找出为止,核心是:变量迭代结束其步骤总结如下:当时,为换入变量确定换出变量为换出变量接下来有下式:用高斯法,将的系数列向量换为单位列向量,其步骤是:结果是:代入目标函数:有正系数表明:还有潜力可挖,没有达到最大值;此时:令得到另一个基本可行解

(0,3,6,2,16,0)有负系数表明:若要剩余资源发挥作用,就必须支付附加费用。当时,即不再利用这些资源。如此循环进行,直到找到最优为止。本例最优解为:(4,2,0,0,0,4)(四)、单纯形表判定标准:若求

或例题:cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001-Z0

23000012/28/2-12/4cj230000cBxBbx1x2x3x4x5x6000x3x4x516

400010

-Z

3x23010001/42620100-1/2100100-1/2-900002-3/4cj

230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4-Z-9

20000-3/46/2216/4-cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44-412-Z-13000-201/4cj230000cBxBbx1x2x3x4x5x60203x6x1x5x2

4402

002-401101-10000-441001-1/2100-Z-1400-1/2-100000-201/4-13-Z4-412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cjcj230000cBxBbx1x2x3x4x5x60203x3x1x6x2

0442001-1-1/4010001/40

000-21/210101/2-1/80-Z-14000-3/2-1/80000-201/4-13-Z4-412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj练习00-1/12-7/24-33/4-Z

x2x112x1x2x3x4bxBcB2100cj15/43/4011/4-1/810-1/125/24(一)、模型情况

变量:xj≥0xj≤0xj无约束结1、组成约束条件:≥=≤b

目标函数:maxmin果2、变量xj≤0令xj′=-xj

,xj′≥0

xj≥0不处理

xj无约束令xj=xj′-xj″,xj′≥0,xj″≥0唯一最优无穷最优无界解无可行解五、单纯形法的进一步讨论

3、约束条件:加入松弛变量加入人工变量先减去再加上例:加入人工变量后,目的是找到一个单位向量,叫人工基。其目标价值系数要确定,但不能影响目标函数的取值。一般可采用两种方法处理:大M法和两阶段法。即假定人工变量在目标函数中的系数为M(任意大正数),如果是求极大值,需加-M;如果是求极小值,需加M。如基变量中还存在M,就不能实现极值。⑴.大M法:cj3-1-100-M-McBxBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-20100011-Z’4M3-6M-1+M-1+3M0-M00cBxBbx1x2x3x4x5x6x70x4103-20100-1--Mx610100-11-21-1x31-2010001--Z’M+11-1+M00-M01-3Mcj3-1-100-M-McBxBbx1x2x3x4x5x6x70x4123001-22-54-1x210100-11-2--1x31-2010001--Z’21000-11-M-M-1cBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z’-2000-1/3-1/31/3-M2/3-M∴最优解为(4190000),Z=-2cj-31100MMcBxBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-Z-4M-3+6M1-M1-3M0M00cBxBbx1x2x3x4x5x6x70x4103-20100-1-Mx610100-11-211x31-2010001--Z-M-1-11-M00M03M-1cj-31100MMcBxBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001--Z-2-10001M-1M+1cBxBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3-Z20001/31/3M-1/3M-2/3∴最优解为(4190000),Z=-2用计算机处理数据时,只能用很大的数代替M,可能造成计算机上的错误,故多采用两阶段法。

第一阶段:在原线性规划问题中加入人工变量,构造如下模型:⑵.两阶段法:对上述模型求解(单纯形法),若W=0,说明问题存在基本可行解,可以进行第二个阶段;否则,原问题无可行解,停止运算。第二阶段:在第一阶段的最终表中,去掉人工变量,将目标函数的系数换成原问题的目标函数系数,作为第二阶段计算的初始表(用单纯形法计算)。例:第一阶段cj00000-1-1cBxBbx1x2x3x4x5x6x70x4111-21100011-1x63-4120-1103/2-1x71-20100011-w’4-61301000x4103-20100-1-1x610100-11-210x31-2010001--w’1010010-30x4123001-22-50x210100-11-20x31-2010000-w’000000-1-1cj3-1-100cBxBbx1x2x3x4x50x4123001-24-1x210100-1--1x31-20100--Z’21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3-Z’-2000-1/3-1/3第二阶段∴最优解为(41900),目标函数Z=-2

设规划模型约束条件为,需加入人工变量,而得到一个m×m的单位矩阵,即基变量组合。因人工变量为虚拟变量,且存在于初始基本可行解中,需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量,表示原问题有解。若当,而还有人工变量(非零)时,则表示原问题无可行解。1、目标函数:max,min3、无可行解的判断:运算到检验数全负为止,仍含有人工变量,无可行解。

5、退化:即计算出的θ(用于确定换出变量)存在有两个以上相同的最小比值,会造成下一次迭代中由一个或几个基变量等于零,这就是退化(会产生退化解)。虽任意换出变量,目标函数值不变,但此时不同的基却表示为同一顶点,其特例是永远达不到最优解。需作如下处理:

⑴.当中出现两个以上最大值时,选下标最小的非基变量为换入变量;

⑵.当θ中出现两个以上最小值时,选下标最小的基变量为换出变量。建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj≥0xj无约束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解图解法、单纯形法单纯形法不处理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z′=-ZminZ=-maxz′0-M根据上表列出初始单纯形表A(二)、线性规划小结A练习-M+1/7-1/7-M-16/7-50/700-102/7-Z1/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj0-M0-5+2M3-4M2+3M-Z51-101-5210x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cj作业0100x2-4-2/35/3-10/3x1300-Z-1/3-1/300-2/32/3-1/32/3x2-44010-1/31/3105/3-5/310/340/310/3x804-1/31/301-1/31/3-5/34/3x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj4M-4311x2-43-6M-21-4x130-M005-3M3M-52-3M-Z2/31-100-22-12x10-M14\400101-1314\4x8020001-11-22x7-Mx10x9x8x7x6x5x3bxBcB-M00-M5-52cj0100x2-4-31/2-3/25/2-15/2x13-M0-1/2-M+9/200-17/22\7-Z001/21/2001/28\3x2-4001/2-1/21-1[5/2]6\1x65-111/25/200-5/210\5x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj0100x2-4-13-45-10x13-M00-M+41-1-68-Z-0001-11-22x2-46001-12-2512\2x80--1103-11-54x90x10x9x8x7x6x5x3bxBcB-M00-M5-52cj一般而言,一个经济、管理问题凡是满足以下条件时,才能建立线性规划模型。

⑴.要求解问题的目标函数能用数值指标来反映,且为线性函数;

⑵.存在着多种方案;

⑶.要求达到的目标是在一定条件下实现的,这些约束可用线性等式或不等式描述。六、线性规划模型的应用(一)、资源的合理利用

一般提法:某厂计划在下一生产周期内生产B1,B2,…Bn种产品,要消耗A1,A2,…Am种资源,已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示,问如何安排生产计划,才能充分利用现有的资源,使获得的总利润最大?单件产消耗品资源资源限制单件利润(二)、生产组织与计划问题

一般提法:某工厂用机床A1,A2,…Am加工B1,B2,…Bn种零件。在一个周期内,各机床可能工作的机时(台时),工厂必须完成各种零件的数量、各机床加工每个零件的时间(机时/个)和加工每个零件的成本(元/个)如表所示,问如何安排各机床的生产任务,才能完成加工任务,又使总成本最低?加工零时间件机床机时限制必须零件数加工零成本件机床(三)、合理下料问题一般提法设用某种原材料截取零件A1,A2,…Am的毛坯。根据以往的经验,在一种原材料上可以有B1,B2,…Bn种不同的下料方式,每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示,问应如下料才能既满足需要又使原材料消耗最少?下料下料毛件数方式坯型号需要毛坯数现有一批某种型号的圆钢长8米,需要截取2.5米长的毛坯100根,长1.3米的毛坯200根。问如何才能既满足需要,又能使总的用料最少?100200

321002462.5米1.3米需要根数一二三四下料下料毛件数方式坯型号设变量为第j

种方法的所有原料件数例题1:

(四)、合理配料问题一般提法某饲养场用n种饲料B1,B2,…Bn配置成含有m种营养成分A1,A2,…Am的混合饲料,其余资料如表所示。问应如何配料,才能既满足需要,又使混合饲料的总成本最低?

含饲量料成分最低需要量原料单价例题2:某人每天食用甲、乙两种食物(如猪肉、鸡蛋),其资料如下:问两种食物各食用多少,才能既满足需要、又使总费用最省?设:Xj

表示Bj

种食物用量。

21.5原料单价1.007.5010.00

0.10.151.70.751.101.30A1A2A3

最低需要量甲乙

含食量物成分(五)、运输问题已知资料如表所示:单位销运价地产地产量销量模型如下:某运输问题的资料如下:6483销量7524852431921092产量单位销地运价产地例题3:(六)、作物布局问题单土产地作物播种面积土地面积此外,还有连续投资、投入产出等模型问题。例2.2某地区有三个矿山A1,A2,A3,生产同一种矿物。另外有四个这种矿物消费地(铁厂)B1,B2,B3,B4。各矿山产量及铁厂的需要量和矿山将矿物运到铁厂的单位运价如表2-2。问应如何调运,才使总运费最省?(一)运输问题的数学模型解:该题有两个限制条件:一个是产量,一个是需量。目标是总运费最省。设:xij表示从第i个矿山运往第j个铁厂的矿物运量。这样得到以下两组线性方程组:(1)各矿山矿物的生产量与运出量平衡方程:(2)各铁厂矿物供应量与需要量平衡方程(3)矿物的运输量应非负

(4)目标函数(二)资源最优利用的数学模型例2.3某厂生产A、B产品1kg需用资源数见表2-3,已知生产A1kg价值7千元,B1kg12千元。应该生产A和B产品各多少才能

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论