资源描述：
《线性规划模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第一章线性规划模型一、线性规划模型的建立例1某工厂A有生产卬，乙二种产品的能力，H.生产i吨甲产品需要3个工口和0.35吨小麦。生产一吨乙产品需要4个工日和0.25吨小麦。该厂仅有工人12人，一个月只能Hl300个工日，小麦一个月只能进21吨，并且还知生产一吨甲产品可盈利80（白元），生产一吨乙产品可盈利90（百元）。那么，工厂A在一月中应如何安排这两种产品的生产，使之获得瑕大的利润？由以上条件可列表如下：资源甲乙总和工日34300小麦0.350.2521盈利8090问题一的数学模型：设旺分别表示一月中生产
2、甲，乙二种产品的数量，称之为决策变量。所得利润为Z,问题一的bl标是使得总利润函数z=80%,+90兀2有最大值。工日的约束为：3%,+4x2<300原料小麦的约束为：0.35坷+0.25兀2<21显然1=1标函数和约朿条件都(1.1)T是问题_可归结为求目标函数在约束条件下的最大值问题,是决策变量的线性函数，即可建立以下线性规划模型maxz=80%!+90x2s.t.3%!+4x2<3000・35兀［+0.25*2S21x{,x2>01.1线性规划模型的一般形式max^inin)z=工cixiZ=1s.t
3、.^aijxj-(-»=X-i=1,2…(m个约束)(1.2)j=iXj>0j=1,2・・・,”矩阵形式max^inin)z=c1Xs.t.AX<(>=)&(1.3)X>0其中X=(兀1，兀2,…XJ为决策向量，c=(c,,c2,---cn)z为目标函数的系数向量,b=(bi，b?,・・・bj为常数向量,4=(勺)为系数矩阵。V丿恥“1.2线性规划模型的标准形minz=cTXs.t.AX=bX>0对于例1町取：=(80,90),A=‘34、,b=#300、o,0.350.25丿,21丿(1.4)1.3如何
4、化一般形为标准形1.3.1目标函数的转化例2—个工厂的卬，乙，丙三个车间牛产同一种产品，每件产品由4个零件A和3个零件B组成。这两种零件耗用两种不同的原材料，而这两种原材料的现有数额分别是300公斤和500公斤。每个牛产班的原材料的耗用量和零件产量如下表。问这三个车间应各开多少班数，才能使这种产需的配套数达到最人？乍间每班用料数每班产量（个）原料1原料2零件A零件B叩8675乙5969丙38848%!+5兀2+3兀勺<300「(1.5)6兀1+9兀2+8x3<500甲，乙，丙生产A零件总数是：7兀］+6x2
5、+8x3，生产B零件总数是:5xj+9x2+4x3。解：设州，兀2，心是甲，乙，丙三个车间所开的生产班数，由原材料的限制条件，得因为目标函数是要使产品的配套数最大，而每个零件要4个A零件，3个B零件，所以产吊的最人量不超过沁严和5屮響4春较小的一个卡是产品的配套数,即S=min+6x2+8x35兀］+9x2+4x34这个日标函数不是线性函数，但rij以通过适当的变换把它化为线性的，设.7兀
6、+6x9+8小5兀
7、+9x9+4x.y=min1(1.6)则上式可以等价于卜•而两个不等式7X(+6x2+8兀3〉5兀
8、］+9兀2+4兀3>(1・7)故可得如下线性规划模型:maxS=ys.t.7兀］+6x2+8兀3—4yA05x,+9兀2+4兀3-3y>0(1.8)8%!+5x2+3x3<3005%j+9x2+8x3<500xpx2,x3,y>0目标函数为求最大值，令5=-y即可将原问题转化为在相同约束条件卜•求最小值。1.3.2约束条件的转化d內+勺兀2-baxxx+a2x2>-b若约束条件中有n和w号，则口J在w（>）号的左端加上（或减去）一个非负变量（称为松弛变量）使其变成二号约朿。如4X（+5x2>6变为4旺+5兀
9、2-尤3=6。若约朿条件带有绝对值号，如⑷坷+02X25：,则可等价转化为:若决策变量没有非负限制，称为自由变量。例如x,e（-oo,+oo）为口由变量，则可引入>0,y2>0,令Xj=yt-y2代入模型即可。二、线性规划的求解方法2.1线性规划解的概念定义1・1满足约束条件的解x=（x,,x2,---,xjr,称为线性规划问题的可行解，而使目标隊I数达到最小值的可行解叫最优解。所有可行解构成的集合称为可行域，记为/?。2.2线性规划解的基本理论定理1・1如果线性规划问题存在对行域，则其对行域是凸集。定理1
10、・2如果线性规划问题的可行域有界，则问题的最优解一定在可行域的顶点上达到。2.3单纯形法单纯形法是求解线性规划问题的最常用、最有效的算法z—。单纯形法是首先由GeorgeDantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由定理2可知，如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个极点,据一定规则判断其
