+2x2=100 +2x3=10 x≥0(=1,2,3) 并使得总钢筋数∫(x)=x+x2+x最小的一组数(x1,x2,x)。 一般的,设用某原材料(条材或板材)下零件A,A2,…,An的毛坯,根据过去经验 在一件原材料上有B1,B2…Bn种不同的下料方式,每种下料方式可得各种毛坯个数及每 种零件需要量如下表1-4所示,问应怎样安排下料方式,使得既得满足需求,用的原料 又小 解:设采用B,种方式下料时,需要的原材料数为x,则这一问题的数学模型为 求一组变量的值x(j=1,2,…,n),使它满足 ∑Cx1≥a(i=1,2…,m) (所下的A零件总数不能低于a) ≥0 并且使目标函数∫(x)=∑x的值最小。 表1-4 各种方式下 下料方式 的零件个数 B B2 B,零件需要量 零件名称 CC A2 C A CC 例1.4(投资计划问题) 个公司制订投资计划问题的关键是在预算范围内,合理选择投资项目,使总的资 金回收额达到最大。 例如,某建筑企业拥有20万资金,拟在今后五年内对下列项目投资。已知: 项目A:从第一年到第四年每年年初需要投资,并于次年末回收本利115% 项目B:第三年年初需要投资,到第五年末能回收本利125%,但规定最大投资不 超过8万元 项目C:第二年初需要投资,到第五年末能回收本利140%,但规定最大投资额不 超过6万元 项目D:五年内每年年初可购买公债或定期储蓄,于当年末归还,并加利息9%
( , , j x x x x x j + = + = ≥ = 1 2 2 3 3 2 100 2 100 0 1 2 3) 并使得总钢筋数 f ( ) x x = + x + x 1 2 3最小的一组数( , , ) T x x x 1 2 3 。 一般的，设用某原材料（条材或板材）下零件 的毛坯，根据过去经验 在一件原材料上有 1 2 , , , A A " Am 1 2 , , , B B " Bn 种不同的下料方式，每种下料方式可得各种毛坯个数及每 种零件需要量如下表 1-4 所示，问应怎样安排下料方式，使得既得满足需求，用的原料 又小。 解：设采用 Bj 种方式下料时，需要的原材料数为 j x ，则这一问题的数学模型为： 求一组变量的值 j x （ j = 1 2, ,", n ），使它满足 ( , , , ) n ij j i j j C x a i m x = ≥ = ≥ ∑ " 1 1 2 0 （所下的 Ai 零件总数不能低于ai ） 并且使目标函数 ( ) n j j f x = = ∑ 1 x 的值最小。 表 1-4 各种方式下 下料方式 的零件个数 零件名称 B1 2 B " Bn 零件需要量 m A A A 1 2 # n n m m C C C C C C C C C 11 12 1 21 22 2 1 2 " " # # " # " mn m a a a 1 2 # 例 1.4 （投资计划问题） 一个公司制订投资计划问题的关键是在预算范围内，合理选择投资项目，使总的资 金回收额达到最大。 例如，某建筑企业拥有 20 万资金，拟在今后五年内对下列项目投资。已知： 项目 A：从第一年到第四年每年年初需要投资，并于次年末回收本利 115%； 项目 B：第三年年初需要投资，到第五年末能回收本利 125%，但规定最大投资不 超过 8 万元； 项目 C：第二年初需要投资，到第五年末能回收本利 140%，但规定最大投资额不 超过 6 万元； 项目 D：五年内每年年初可购买公债或定期储蓄，于当年末归还，并加利息 9%
现要求确定这些项目每年的投资额,使到第五年末拥有的资金本利总额为最大 分析: 1.假设变量,设以x1x,xc,x(=1,2,3,4,5)分别表示第年i年初给项目A,B,C, D的投资额 2.资金流转分析,原则是每年年初应把资金全部投出去,手中不留呆滞资金。因 此,第一年年初将20万元资金投给A,D项目,有 x+xD=20000,0年底回收项目D的本息为:x1D(1+9%)=1.09xD 这些资金应在第二年年初投资给A,C,D三个项目,故有x24+x2c+x2D=1.09xD 第二年年底回收项目A的第一年投资和项目D当年投资的本利总合为: 1.15xA+1.09x2D这些资金在第三年初投资给项目A,B,D,有 x5A+xB+x3D=1.15xA+1.09x2D第三年底回以A项的第二年投资和D项当年投资的 本利总合为:1.15x4+1.09x30 类似的,可得第四年投资为:x4+x4D=1.15x24+109x30 第五年投资为:xD=1.15x34+1.09x4D 第五年年底共回收资金: 项目A:1.15x4 项目B:125xa,且xB≤8000 项目C:1. 且 项目D:1 从而得到该投资问题的模型为:求x12x,xC,x(=1,2,3,4,5),使其满足 x1+xD=200000 xip +x2a+x2c tx 0 1.15x,,-1.09x+x2,+x+x=0 1.15x24-1.09x2D+x4+x4D=0 115x-1.09 5D x5≤80000 x2c≤60000 ≥0(=1,2…,5) 并使f(x)=1.15x1A+125x8+1.40xc+109xD最大 例1.5(混凝土搅拌站选址问题) 在一个联合协作多点开口建筑施工的场地中,一个大型搅拌站的安装位置,对施工 的进度将起很大的作用,特别是基础浇灌阶段更为重要,由此,我们来建立一个选址问 题的数学模型 设共有n个施工地点(广义的称需求点),有m个可供选择建站的地点(广义的称
现要求确定这些项目每年的投资额，使到第五年末拥有的资金本利总额为最大。 分析： 1．假设变量，设以 , , , ( , , , , iA iB iC iD x x x x i = 1 2 3 4 5)分别表示第年 i 年初给项目 A，B，C， D 的投资额。 2．资金流转分析，原则是每年年初应把资金全部投出去，手中不留呆滞资金。因 此，第一年年初将 20 万元资金投给 A，D 项目，有 A D x x 1 1 + = 200000，则年底回收项目 D 的本息为： ( %) . D D x + = x 1 1 1 9 1 09 这些资金应在第二年年初投资给 A，C，D 三个项目，故有 . A C D D x + x x + = x 2 2 2 1 1 09 第二年年底回收项目 A 的第一年投资和项目 D 当年投资的本利总合为： . . A D x + x 1 1 15 1 09 2 这些资金在第三年初投资给项目 A，B，D，有 . . A B D A D x + + x x = x + x 333 1 2 1 15 1 09 . . 第三年底回以 A 项的第二年投资和 D 项当年投资的 本利总合为： A D x + x 2 3 1 15 1 09 类似的，可得第四年投资为： . . A D A D x + x x = + x 4 4 2 3 1 15 1 09 第五年投资为： . . D A D x = + x x 5 3 1 15 1 09 4 第五年年底共回收资金： 项目 A： . A x4 1 15 项目 B： . B x3 1 25 ，且 B x3 ≤ 80000 项目 C： . C x2 1 40 ，且 C x2 ≤ 60000 项目 D： . D x5 1 09 从而得到该投资问题的模型为：求 , , , ( , , , , iA iB iC iD x x x x i = 1 2 3 4 5)，使其满足 . . . . . . . , , , ( , , , ) A D D A C D A D A B D A D A D A D D B C iA iB iC iD x x xxx x x x x x x x x x x x x x x x x x x x i + = − + + + = − − + + + − − + + = − − + = ≤ ≤ ≥ = 1 1 1 2 2 2 1 2 3 3 3 2 3 4 4 3 4 5 3 2 200000 1 09 0 1 15 1 09 0 1 15 1 09 0 1 15 1 09 0 80000 60000 0 1 2 " 5 = 并使 ( ) . . . . A B C D f x x = + 1 15 432 1 25x +1 40x +1 09x5 最大。 例 1.5 （混凝土搅拌站选址问题） 在一个联合协作多点开口建筑施工的场地中，一个大型搅拌站的安装位置，对施工 的进度将起很大的作用，特别是基础浇灌阶段更为重要，由此，我们来建立一个选址问 题的数学模型。 设共有 n 个施工地点（广义的称需求点），有 m 个可供选择建站的地点（广义的称
为供应点),每个点至多建立一个搅拌站,现设在地点i建站的生产能力为(单位:立 方米),在地点i搅拌站生产的单位时间的固定成本为F(F可用固定资产折旧来衡量) 施工点j的需求量为S,从搅拌站i到施工点j的单位运费为C 设x为从搅拌站i向施工点j供应的混凝量(单位:立方米) l1表示是否选择地点i建立搅拌站, 则 ∫,若选;点 0,若不选i点 归纳得到数模:求满足 xn≤rl,(i=1,2,…,m) x≥S(=12…m) x≥0;u1取0或1(=1,2…,m,j=12…,m) 并使∫(x)=∑∑Cx+∑F取最小值的x/(=1,2…,mj=12…,n i=l j=l 综合上述各例,不难看出我们所建立的数学表示都具有一个共同特点:要求出一组 非负数x≥0(=1,2,…,m),且使它们满足一组线性条件(一组线性方程或线性不等式), 并且使得某一关于n个变量x的线性函数取得最大值或最小值。我们把这一类问题统称 为线性规划问题。 1.2线性规划的标准形式 121线性规划问题的标准形式 把上节例子加以概括,我们可以把它们抽象成这样一类数学问题: 求满足条件: a1x+a2x2+…+a1nxn≥(≤或= a21x+a2x2+…+a2nxn≥(≤或=)b2 (1-1) anx+an2x2+…+ ax≥(≤或=)。 0(j=1, 并且使∫(x)=C耳+c2+…+Gx取最大(小)值得一组数x(j=1,2,…,n)。(-3) 其中,a(=1,2,…mj=1,2…,m),b及c都是已知常数,(1-1)式中的线性条件
为供应点），每个点至多建立一个搅拌站，现设在地点 i 建站的生产能力为 （单位：立 方米），在地点 i 搅拌站生产的单位时间的固定成本为 （ 可用固定资产折旧来衡量） 施工点 j 的需求量为 ，从搅拌站 i 到施工点 j 的单位运费为 。 ir Fi Fi j S Cij 设 ij x 为从搅拌站 i 向施工点 j 供应的混凝量（单位：立方米） i u 表示是否选择地点 i 建立搅拌站， 则 = ，若不选 点 ，若选 点 i i ui 0 1 归纳得到数模：求满足 n ij j=1 ij ij ( , , , ) ( , , ) 0 1( , , , ; , , , ) i i m j i x ru i m x S j n x i m j = ≤ = ≥ = ≥ = = ∑ ∑ 1 1 2 1 2 1 2 1 2 " " 0; ui 取 或 " " n 并使 ( ) m n m ij ij i i i j i f x C x = = = = ∑∑ +∑ 1 1 1 Fu 取最小值的 xij (i m = = 1 2, ," " , ; j 1 2, , , n) ) 综合上述各例，不难看出我们所建立的数学表示都具有一个共同特点：要求出一组 非负数 ( , , , ij x ≥ = 0 1 j 2 " n ，且使它们满足一组线性条件（一组线性方程或线性不等式）， 并且使得某一关于 n 个变量 j x 的线性函数取得最大值或最小值。我们把这一类问题统称 为线性规划问题。 1.2 线性规划的标准形式 1.2.1 线性规划问题的标准形式 把上节例子加以概括，我们可以把它们抽象成这样一类数学问题： 求满足条件： (1-1) ( , , , ) n n n n m m mn n j a x a x a x a x a x a x a x a x a x x j n + + ≥ ≤ + + ≥ ≤ + + ≥ ≤ ≥ = 11 1 12 2 1 21 1 22 2 2 1 1 2 2 0 1 2 " " """"""""""""""" " " 1 2 m + ( 或= )b + ( 或= )b + ( 或= )b (1-2) 并且使 ( ) n n f x c = + x c x + + c x 1 1 2 2 " 取最大（小）值得一组数 j x ( , j =1 2,", n) " ) 。(1-3) 其中，a i ij( , =1 2,",m; j = 1 2, , , n ，bi 及ci 都是已知常数，（1-1）式中的线性条件
可以是方程式也可以是不等式,亦可以二者兼有 凡能表为以上形式的问题统称为线性规划问题。 (1-1)式称为线性规划的约束条件 (1-2)式称为线性规划的未知变量(决策变量)。 (1-3)式称为线性规划的目标函数 为了讨论方便起见,我们把以上线性规划问题统归成如下标准形式: 求满足约束方程: a1x+a2x2+…+a1nx=b1 a2x+a2x2+…+a2nxn=b2 bn x≥0(=12,…,n) b≥0(=1,2…,m) 使∫(x)=Cx十C2x+…+Cnx最大的一组数x=(x1,x2,…,x)。 为了叙述方便起见,我们用(L,P)代表以上的标准形线性规划。 1.标准线性规划的矩阵形式: b 设A b AX=b C=(c,C2…,cn),则(L,P)的矩阵形式为求满足条件 K≥0 并且使∫(x)=CX取最大的一组数X。 Maxf(x)=CX 简记为: sX≥0 b≥0 2.标准线性规划的向量形式 b b 则得(L,P)的向量形式
可以是方程式也可以是不等式，亦可以二者兼有。 凡能表为以上形式的问题统称为线性规划问题。 （1-1） 式称为线性规划的约束条件。 （1-2） 式称为线性规划的未知变量（决策变量）。 （1-3） 式称为线性规划的目标函数。 为了讨论方便起见，我们把以上线性规划问题统归成如下标准形式： 求满足约束方程： ( , , , ) 0( , , , ) n n n n m m mn n j i a x a x a x a x a x a x a x a x a x x j n b i m + + + + + + ≥ = ≥ = 11 1 12 2 1 21 1 22 2 2 1 1 2 2 0 1 2 1 2 " " """"""""""" " " " 1 2 m + = b + = b + = b 使 ( ) n n f x c = + x c x + + c x 1 1 2 2 " 最大的一组数 ( , , , ) T n x = x x x 1 2 " 。 为了叙述方便起见，我们用（L，P）代表以上的标准形线性规划。 1．标准线性规划的矩阵形式： 设 X= b= n n m m mn n m a a a x b a a a x b A a a a x b = 11 12 1 1 1 21 22 2 2 2 1 2 " " """""" # # " ( , , , ) C c n = c c 1 2 " ，则（L，P）的矩阵形式为求满足条件 AX b X = ≥ 0 并且使 f ( ) x = CX 取最大的一组数 X 。 简记为： ≥ ≥ = = 0 . 0 ( ) b X AX b st Maxf x CX 2．标准线性规划的向量形式 设 则得（L，P）的向量形式： = mj j j j a a a P " 2 1 = mb b b b " 2 1
Maxf(x)=∑cx axf(x)=∑c,x ∑qx=b ∑Px=b ≥0 s1x,≥0 b≥0 122将一般线性规划问题划为标准形式的方法 将非标准形式线性规划为标准形式线性规划时有以下几种情况可能出现,处理的方 法有 1.目标函数为极小化。对目标函数为极小化的问题只要将目标函数乘以(-1)即 可化为等价的极大化问题 2.约束条件为不等式。部分或全部约束条件为不等式有两种情况: (1)约束条件为不等式或等于形式。对这样的约束,在不等式的左端加上一个非 负的新变量即可化为等式。新增的非负变量成为松弛变量 (2)约束条件为大于或等于形式。对这样的约束,在不等式的左端减去一个非负 的新变量即可化为等式。新增的非负变量称为剩余变量,亦可以称为松弛变量。 3.决策变量有非正约束。如果x≤0,则用非负变量x代替,使x=-x。 4.决策变量x符号不受限制。标准形式中要求变量为非负,碰到变量无非负约束 时,可以用两个非负的新变量之差来代替。如变量x无非负性要求,则将它写成 x=x-x,新变量x和x为非负变量,而x的符号将由x和x来确定 5.决策变量有上下界。对这种情况,可将上下界分别处理。引进新的变量使等于 原变量减去上下限值,如此则下限为零,满足标准形式的非负性要求。如已知决策变量 x,的限制为a≤x,≤b,;则以x=x,-a代替x,从而得0≤x≤b-a,现时的x满足了 非负要求。并用新变量x替换目标函数和约束条件中所有的原变量x,,再将上限约束列 为新的约束条件并化为等式。 下面举例说明如何将一般非标准形式的线性规划问题划为标准形式的线性规划问 例1.6将下列线性规划问题化为标准形式 maxf(x)=2x,-x2+x3 < 2x-x+x212 x1-4x2-4x3 2 x1,x2≥0,x3不限
≥ ≥ = = ∑ ∑ = = 0 . 0 ( ) 1 1 j j n j ij j j n j j j b x a x b st Maxf x c x 或 ≥ ≥ = = ∑ ∑ = = 0 . 0 ( ) 1 1 j j n j j j j n j j j b x P x b st Maxf x c x 1.2.2 将一般线性规划问题划为标准形式的方法 将非标准形式线性规划为标准形式线性规划时有以下几种情况可能出现，处理的方 法有： 1．目标函数为极小化。对目标函数为极小化的问题只要将目标函数乘以（-1）即 可化为等价的极大化问题。 2．约束条件为不等式。部分或全部约束条件为不等式有两种情况： （1）约束条件为不等式或等于形式。对这样的约束，在不等式的左端加上一个非 负的新变量即可化为等式。新增的非负变量成为松弛变量。 （2）约束条件为大于或等于形式。对这样的约束，在不等式的左端减去一个非负 的新变量即可化为等式。新增的非负变量称为剩余变量，亦可以称为松弛变量。 3．决策变量有非正约束。如果 j x ≤ 0 ，则用非负变量 ' j x 代替，使 ' j j x = −x 。 4．决策变量 j x 符号不受限制。标准形式中要求变量为非负，碰到变量无非负约束 时，可以用两个非负的新变量之差来代替。如变量 j x 无非负性要求，则将它写成 ' " j j j x = x − x ，新变量 ' j x 和 " j x 为非负变量，而 j x 的符号将由 ' j x 和 " j x 来确定。 5．决策变量有上下界。对这种情况，可将上下界分别处理。引进新的变量使等于 原变量减去上下限值，如此则下限为零，满足标准形式的非负性要求。如已知决策变量 j x 的限制为a x j j ≤ ≤ bj ；则以 ' j j x = x − a 代替 j x ，从而得 ' j 0 ≤ x ≤ −b a，现时的 ' j x 满足了 非负要求。并用新变量 ' j x 替换目标函数和约束条件中所有的原变量 j x ，再将上限约束列 为新的约束条件并化为等式。 下面举例说明如何将一般非标准形式的线性规划问题划为标准形式的线性规划问 题。 例 1.6 将下列线性规划问题化为标准形式： max ( ) . , , f x x x x x x x x x s t x x x x x x = − + + − ≤ − + ≥ − − ≥ ≥ 1 2 1 2 3 1 2 3 1 2 3 1 2 3 2 3 20 2 1 4 4 2 0 不限 x3 2