第一章 线性规划模型.doc

1 第一章线性规划模型一、线性规划模型的建立例1 某工厂 A 有生产甲,乙二种产品的能力,且生产一吨甲产品需要 3 个工日和 吨小麦。生产一吨乙产品需要 4 个工日和 吨小麦。该厂仅有工人 12 人,一个月只能出 300 个工日,小麦一个月只能进 21 吨,并且还知生产一吨甲产品可盈利 80 (百元) ,生产一吨乙产品可盈利 90( 百元)。那么, 工厂 A 在一月中应如何安排这两种产品的生产, 使之获得最大的利润? 由以上条件可列表如下: 产品资源甲乙总和工日 34 300 小麦 21 盈利 80 90 问题一的数学模型:设1x ,2x 分别表示一月中生产甲,乙二种产品的数量,称之为决策变量。所得利润为 z ,问题一的目标是使得总利润函数 2190 80xxz??有最大值。工日的约束为: 300 43 21??xx 原料小麦的约束为: 21 25 035 0 21??. 于是问题一可归结为求目标函数在约束条件下的最大值问题, 显然目标函数和约束条件都是决策变量的线性函数,即可建立以下线性规划模型 0 21 25 035 0 300 43 90 80 21 21 21 21???????x,x . xxz max () 2 线性规划模型的一般形式???? n,,jx m,,ib, xcz min max j i nj j ij ni ii?? 210 21 1 1???????????() 矩阵形式???? 0?????X b, AX . Xcz min max T () 其中?? Tnx,x,xX? 21?为决策向量, ???,, 21?为目标函数的系数向量, ?? Tmb,b,bb? 21?为常数向量, ?? nm ijaA ??为系数矩阵。 线性规划模型的标准形 0???X b AX . Xcz min T () 对于例 1 可取: ?? 90 ,80 ? Tc ,?????????25 035 0 43.. A ,?????????21 300 b 。 如何化一般形为标准形 目标函数的转化例2 一个工厂的甲,乙, 丙三个车间生产同一种产品, 每件产品由 4 个零件 A和3 个零件 B 组成。这两种零件耗用两种不同的原材料,而这两种原材料的现有数额分别是 300 公斤和 500 公斤。每个生产班的原材料的耗用量和零件产量如下表。问这三个车间应各开多少班数, 才能使这种产品的配套数达到最大? 3 车间每班用料数每班产量(个) 原料 1 原料 2 零件 A 零件 B 甲8675 乙5969 丙3884 解:设1x ,2x ,3x 是甲,乙,丙三个车间所开的生产班数,由原材料的限制条件,得 500 896 300 358 321 321??????xxx xxx () 甲,乙, 丙生产 A 零件总数是:321867xxx??, 生产 B 零件总数是:321495xxx??。因为目标函数是要使产品的配套数最大, 而每个零件要 4个A 零件,3个B 零件, 所以产品的最大量不超过 4 867 321xxx??和3 495 321xxx??中较小的一个。设 S 是产品的配套数, 即???????????3 4954 867 321321xxx, xxx min S 这个目标函数不是线性函数,但可以通过适当的变换把它化为线性的,设???????????3 4954 867 321321xxx, xxx min y () 则上式可以等价于下面两个不等式 y xxx???4 867 321 ,y xxx???3 495 321 () 故可得如下线性规划模型:0 500 895 300 358 03495 04867 321 321 321 321 321????????????????y,x,x,x xxx xxx yxxx yS max () 目标函数为求最大值,令 yS??即可将原问题转化为在相同约束条件下求最小值。 4 约束条件的转化若约束条件中有?和?号, 则可在?(?) 号的左端加上( 或减去) 一个非负变量(称为松弛变量)使其变成= 号约束。如 654 21??xx 变为654 321???xxx 。若约束条件带有绝对值号,如 bxaxa?? 2211 ,则可等价转化为: ????????bxaxa bxaxa 2211 2211 。若决策变量没有非负限制,称为自由变量。例如???????,x 1 为自由变量,则可引入 00 21??y,y ,令 211yyx??代入模型即可。二、线性规划的求解方法 线性规划解的概念定