运筹学课程讲义

运筹学课程讲义第一部分 线性规划第一章 线性规划的基本性质1.1 线性规划的数学模型一、线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。桌子售价50 元/个，椅子售价30 元/个。生产桌子和椅子需木工和油漆工两种工种。生产一个桌子 需要木工4 小时，油漆工2小时。生产一个椅子需要木工3小时，油 漆工 1 小时。该厂每月可用木工工时为 120 小时，油漆工工时为 50 小时。问该厂如何组织生产才能使每月的销售收入最大？max z = 50x + 30x124x + 3x 1201 2 2x + x 012例：某工厂生产某一种型号的机床。每台机床上需要 2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。这些轴需用同一种圆钢制作， 圆钢的长度为74m。如果要生产100台机床，问应如何安排下料，才 能用料最省？二、数学模型的标准型1. 繁写形式2. 缩写形式3. 向量形式4. 矩阵形式三、任一模型如何化为标准型？1.若原模型要求目标函数实现最大化，如何将其化为最小化问题？2.若原模型中约束条件为不等式，如何化为等式？3.若原模型中变量xk是自由变量，如何化为非负变量?k4.若原模型中变量xj有上下界如何化为非负变量?max z = -5x - 6x - 7 x123一 x + 5x 一 3x 15123一 5x 一 6x +10x 20123x 一 x 一 x = 一5123x 0,x无约束123令 x二一x , x = x - x, x, x 0,-Z = Z1 1 3 3 3 3 3min z = 一5 x + 6x + 7 x 一 7 x + 0x 一 Mx 一 Mx1233567x + 5x 一 3x + 3x 一 x + x = 151233465 x - 6x +10x 一 10x + x = 20 0 123345671. 2 图解法该法简单直观，平面作图适于求解二维问题。使用该法求解线性规划问题时，不必把原模型化为标准型。、 图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最优值、 从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解）min z 二 6x + 4 x12最优解（2,0），最优值32 x + x 1123 1 22x , x 012直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。1.3 线性规划的基本概念和基本定理一、线性规划问题的基与解可行解最优解基基向量非基向量基变量非基变量基本解基本可行解最优基本可行解退化的基本解二、几何意义上的几个基本概念1. 凸集2. 凸组合3. 顶点三、线性规划问题的基本定理定理 1：若线性规划问题存在可行域，则其可行域是凸集。引理1:线性规划问题的可行解X二(x ,x , ,x )T为基本可行解的充要1 2 n条件是 X 的正分量对应的系数列向量是线性无关的。定理 2：线性规划问题的基本可行解对应于可行域的顶点。引理2: K是有界凸集，则任何一点XG K可表示为K的顶点的凸组 合。定理3:如果线性规划问题有有限最优解，则其目标函数最优值一定 可以在可行域的顶点上达到。四、求解线性规划问题的基本思路 在有限个基本可行解中寻找最优基本可行解。找一个基本可行解(m个线性无关的系数列向量)，由其换到另一个基本可行解。实质即为换基。前提是保证新的基本可行解的目标函数值比原来的更优而不是更劣。第二章 单纯形法它是求解线性规划最为成熟的算法。胜利家具厂生产桌子和椅子两种家具。桌子售价50 元/个，椅子售价 30 元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌 子需要木工4小时，油漆工2 小时。生产一个椅子需要木工3 小时， 油漆工 1 小时。该厂每月可用木工工时为 120 小时，油漆工工时为 50 小时。问该厂如何组织生产才能使每月的销售收入最大？max z = 50x + 30x124x + 3x 1201 2 2x + x 012将其变形，得4 x + 3 x + x = 120123 0 1234将x ,x对应的单位矩阵作为初始可行基。令x ,x为基变量，x ,x为非343412基变量。原模型变形为 max z = 50x + 30x 12x = 120 一 4x 一 3 x312 01234如果令非基变量x ,x等于零，得一个基本可行解（0，0，120, 50）, 12对应的目标函数值z = 0最优性检验：该解是否最优？显然不是。经济意义分析：x ,x等于零 12意味着家具厂不开工生产，销售收入为零，资源未得到充分利用。数学角度分析：非基变量x ,x前的系数都为正，表明目标函数值有增 12加的可能。只要将系数为正的非基变量与某一基变量对换，当换入变 量的值增加时，目标函数值就可能增加。换基迭代：寻找下一个可行解需要进行换基迭代。换基后需满足：（1） 新的解仍是基本可行解；（2）目标函数得到改善。选择入基变量：x,x系数均为正。对求目标函数极大化的问题，我们12希望目标值增加得越快越好，因此应选系数最大的X入基。1选择出基变量： x 入基后，其值从零增加并引起其他变量取值的变化。1由问题的典则表达式和变量必须取正值的条件，得下列不等式关系：x = 120-4x -3x 03 12x = 50 - 2x - x 04 12因迭代后X仍为取零值的非基变量，上式可简化为2120 - 4x 0150 - 2x 01很明显，只有选X = min（120/4,50/2）= 25时，才能使上述不等式成立，1并使基变量x变为零，正好满足非基变量必须为零的条件，所以可令4x 出基，新的典则方程变为44 x + x = 120 3x1322 x = 50 x x124化简后得 x1 = 25 0.5x2 0.5x4x = 20 x + 2 x 324代入目标函数可得z = 1250 + 5x -25x224得到下一个基本可行解（25， 0， 20， 0），并完成了第一次迭代。新解是最优解吗？需进行最优检验。由于目标函数中 x 的系数仍为2正，说明多生产椅子仍有利可图，该解仍不是最优解。再次迭代。x 入基， x 出基，换基后典则形式变为23z 二 1350 5x 15x334x 二 15 + 0.5x 1.5x134x 二 20 x + 2x234第三个基本可行解为（15，20，0，0），松弛变量都已为零，表明 资源已得到充分利用；非基变量在目标函数中的系数全为负值， 说明目标函数已无法进一步改善，因此该解已是最优解。2.1 单纯形法原理、 构造初始可行基1. 引入附加变量，把数学模型化为标准型2. 若约束条件中附加变量的系数是-1 或原约束即为等式，则必须 引入人工变量，以构成初始可行基3. 目标函数中，附加变量的系数为0,而人工变量的系数为M（很大的正数）二、求出一个基本可行解1. 用非基变量表示基变量和目标函数式4 x + 3x + 8 x + M（2123 x x13+ x ）+ M 5 2x 2x + x ）4255=（A M ）x +（3 M ）x +（8 3M ）x + Mx + Mx + 7 M123452. 求出一个基本可行解及相应的 z 值三、最优性检验1. 最优性检验的依据一检验数b j2. 最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数G 0,且人工变量为0则这个基本可行解是最优 j解。对于极大化问题，只要把上述定理中的G 0改成G 0,又存在某个非基变量的检验数为0,j且人工变量为 0，则线性规划问题有无穷多最优解。4. 无可行解情况若在极小化问题中，对于某个基本可行解，所有检验数y 0,j但人工变量工0,则该线性规划问题无可行解。四、基变换1. 基本可行解的改进定理2. 换入变量的确定3. 换出变量的确定最小非负比值规则9 =b /a =min b /a la 0r rk i i ik ik在单纯形法迭代中，基变换带来可行域顶点的变换，且相邻两次迭代所对应的顶点也是相邻的。4. 无有限最优解（无界解）判定定理：若在极小化问题中，对于某个基本可行解，有一个非基变量的检验数b 1234518x3-2102-1 13x220023 -192.4退化问题一、 什么是退化当基本解、基本可行解、最优基本可行解中有基变量为0 时，即出现 了退化。退化情况下，即使存在最优解，也可能出现循环现象，即迭代过程总是重复解的某一部分序列，目标函数值总是不变，永远达不到最优解。二、摄动法1. 摄动法简介对线性规划原问题，为了避免退化情况下发生循环，而使向量b摄动。2. 确定换出变量的步骤3. 举例三、勃兰特方法法则1：在极小化问题中，如果有几个检验数（c -z ）都是负的，那jj么选其中下标最小的非基变量作为换入变量。法则 2：在极小化问题中，根据最小非负比值规则确定换出变量时，如果有几个比值同时达到最小比值，那么选其中下标最小的基变量作 为换出变量。定理：只要在迭代时，遵循上述法则，就不会出现循环。3. 5 改进单纯形法 每次迭代只计算换入列、常数列及检验数行以提高计算效率。一、单纯形法的矩阵形式1. 用矩阵（分块）形式表示线性规划标准型把矩阵 A、C、X 分别按“基”与“非基”分成两块A=(B,N)C=(C ,C )BNXBXN其中B=(P , P，P )1N=P ， Pm+1m+2m， P )nC =(c ,c , ,c )Nm+1m+ 2nx1 x2xm+1xm+2将分块结果代入标准型，得BX +NX =bBNX 0, X 0BNmin z 二 C X + C XB BN N2. 用矩阵(分块)形式表示基本解、目标函数值及检验数X =B _ib- B -1NXBNz =C B _ib + (C - C B -iN) XBNBNb =C - C B -iNNNB令X = 0, 可得NX = B -1bBz =C B -1 bB3. 单纯型乘子 Y。Y= C B-1B、 改进单纯形法的求解步骤1. 完成第 0 次迭代表。构造初始可行基，计算 B -1。再利用公式0b =C - C BN 0N 0B0-1N = C - CN 0B0N，0计算第0次迭代表中的检验数。确定换入向量为 P ，换出向量为 P ，主元素是 a 。k Br rk2. 计算 B-1i+11) 构造基矩阵 Bi+12) 计算 B-1i+1第一种方法：已知B ，用初等变换法求其逆矩阵B-1 oi+1i+1第二种方法：已知B-1和第i次迭代表的换入列P，主元素为a，,ikrk通过取主变换求出 B-1 oi+13. 计算第i +1次迭代表的常数列和检验数。常数列=B -1bi+10Y =C B 一i中Bi,中b =C - Y NNi+1 Ni+1中 i+14. 进行最优性检验如果b 0,且人工变量为0则已经得到最优解。否则，转下步。Ni+15. 计算第 i + 1 次迭代表中的换入列 P 。kP = B 一1 Pki +1k6. 确定第 i +1 次迭代表中换出向量的下标 B 。r最小非负比值规则令 i =i +1，返回步骤 2。三、 逆的乘积形式B_i =E EE Ei+1i i-11 0改进单纯形法的基本思想就是给定初始基本可行解后，通过修改旧基的逆来获得现行基的逆，进而完成单纯形法的其他运算。四、计算举例0-1 0 0-1 0TT-2 1 1-2 1常数列二B-121 0223_5_-2 1_5_1求 B -1 :3-1212122Y 二 C B -i =(8,310 =(2,3)3B 33-2 17 b = C - YN =(ccccc )- Y(P P P P P )N 3N 33 31456731 4 5 6 7=(4 0 0 M M )-(2 3丫1 -1010 0 0 -1 0 1 丿=(400M M )-(2 - 2 - 3 2 3)=(2 2 3 M - 2 M - 3)第三章 线性规划的对偶原理3.1 线性规划的对偶问题一、对偶问题的提出换位思考家具厂的线性规划问题，该问题站在家具厂管理者的角度追求销售收 入最大max z = 50x + 30x124x + 3x 1201 2 2x + x 012某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资 源来加工他的产品。他需要与家具厂谈判付给该厂每个工时的价格。 如果该企业家已对家具厂的经营情况有详细了解，他可以构造一个数 学模型来研究如何才能既让家具厂觉得有利可图，肯把资源出租给 他，又使自己付的租金最少。目标:租金最少；y -付给木工工时的租金；y -付给油漆工工时的租金12min w = 120 y + 50 y12所付租金应不低于家具厂利用这些资源所能得到的利益1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收入4y + 2y 50122）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收入3y + y 30123）付给每种工时的租金应不小于零 y 0,y 0二、原问题与对偶问题的数学模型1. 对称形式的对偶 原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称 的，称为对称形式的对偶。原问题：min z = CX bX 0对偶问题：max w = Yb YA 02. 非对称形式的对偶若原问题的约束条件全部是等式约束（即线性规划的标准型），即min z = CX 0则其对偶问题的数学模型为max w = Yb YA bAX 0即min z =CXX-bX0设丫产,ym), Y2=(ym+1,ym+2,y2m)o根据对称形式的对偶模型,写出上述问题的对偶问题：maX W 二鸽亠)(丫起)0Y20maX W =( 丫厂丫丿 b( Y1-Y2)A0Y20令 Y= Y1-Y2, 得对偶问题为max w = YbYACY 是自由变量3. 原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数min z目标函数max wn个变量n个约束变量 0约束变量 0约束自由变量约束=m个约束m个变量约束变量 0约束变量 0约束=自由变量约束条件的限定向量目标函数的价值向量目标函数的价值向量约束条件的限定向量max = 2 x + x + 3x + x1234x + x + x + x 5原问题：2x -2x +3 = -4 1 134x , x 0, x , x无约束1324m i nw = 5y 一 4 y + y123y + 2 y + y 2123对偶问题：y 一 y =11 2 3123y + y =113y 0, y无约束,y 0123min = 3x 一 2x 一 3x + 4x1234x 一 2x + 3x + 4x 一5 0, x 0, x , x 无约束 1423max w = 3 y 一 5 y + 2 y123y + 2 y 4123y 0, y 无约束1233.2 对偶问题的基本性质和基本定理、 对称性定理 对称性定理：对偶问题的对偶是原问题。、 弱对偶性定理弱对偶性定理：若X（0）和Y（0）分别是原问题和对偶问题的可行解，则有 C X（） Y（0）b o三、最优性定理 最优性定理：若X（o）和Y（o）分别是原问题和对偶问题的可行解，且有C X（o）=Y（o）b，则X（o）和Y（o）分别是原问题和对偶问题的最优解。四、对偶定理 对偶定理：有一对对偶的线性规划问题，若其一有一个有限的最优解，则另一个也有最优解，且相应的目标函数值相等。若任一个问题具有无界解，则另一个问题无可行解。五、单纯型乘子 Y 的定理单纯型乘子 Y 的定理：若线性规划原问题有一个对应于基 B 的最优基本可行解，则此时的单纯型乘子Y= C B i是相应于对偶问题的一B个最优解。六、对称形式对偶的互补松弛定理对称形式对偶的互补松弛定理：若X（o）和Y（o）分别是原问题和对偶问 题的可行解，则X（o）和Y（o）都是最优解的充要条件是，对所有i和j, 下列关系式成立：1. 如果 x（o）0，必有 Y（o）P =cj j j2. 如果 Y（o）P c，必有 x（o）=0j j j3. 如果 y（o）0，必有 A X（o）=bi i i4. 如果 A X（o）b ，必有 y（o）=oi i i其中 P 是 A 的第 j 列， A 是 A 的第 i 行。ji互补松弛定理意味着：如果原问题最优解X（o）中第j个变量x（o）为正，j则其对偶问题中与之对应的第j个约束式在最优情况下必呈严格等式 （即其松弛变量为o）而如果对偶问题中第j个约束式在最优情况下 呈严格不等式，则原问题最优解X（o）中第j个变量x（o）必为o。类似地， j如果对偶问题最优解Y（o）中第i个对偶变量y（o）为正，则其原问题中i与之对应的第i个约束在最优情况下必呈严格等式（即其剩余变量为 o）；而如果原问题中第i个约束在最优情况下呈严格不等式，则对偶 问题最优解Y（o）中第i个对偶变量y（o）必为o。i互补松弛性：YX二0 YX二0X, Y为最优解SS对一对对偶规划的最优解而言，如果对应某一约束条件的对偶变 量的值为非零，则该约束条件取严格等式；反之，如果某个约束条件 取严格不等式，则其对应的对偶变量一定为零。七、非对称形式对偶的互补松弛定理非对称形式对偶的互补松弛定理：若X（。）和Y（o）分别是原问题和对偶 问题的可行解，则X（o）和Y（o）都是最优解的充要条件是，对所有j, 下列关系式成立：1. 如果 x（o）0，必有 Y（o）P =cj j j2. 如果 Y（o）P c，必有 x（o）=0j j jmax z = x + x12例：已知线性规划问题| X+ X 2 + X3 - 2 0123试用对偶理论证明上述线性规划问题无最优解该问题存在可行解，如 X = （0,0,0）又对偶问题为min w = 2 y + y12 y 2y 112y 2 + y 2 1y y 012y1,y20由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优解八、最优对偶变量（影子价格）的经济解释由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等。如果在得到最优解时，某种资源并未完全利用，其剩余量就是该约束 中剩余变量的取值，那么该约束相对应的影子价格一定为零。因为在 得到最优解时，这种资源并不紧缺，故此时再增加这种资源不会带来 任何效益。反之，如果某种资源的影子价格大于零，就说明再增加这 种资源的可获量，还回带来一定的经济效益，即在原问题的最优解中， 这种资源必定已被全部利用，相应的约束条件必然保持等式。3.3 对偶单纯形法一、对偶单纯形法与单纯形法的区别单纯形法在整个迭代过程中，始终保持原问题的可行性，即常数列0,而检验数C-C B一 1A（即C-YA）由有负分量逐步变为全部0 （即B变为满足YA0，而常数列由有负分量逐步变为全部0（即变为满足原 问题的可行性），即同时得到原问题和对偶问题的最优解。二、对偶单纯形法的求解步骤和计算举例1. 给定一个初始对偶可行的基本解2. 进行最优性检验 若现行常数列b 0,则停止计算。否则，转下步。3. 确定换出变量 将现行常数列b中最小的负元素所在行的基变量换出4. 确定换入变量最大负比值规则：在换出变量所在的第r行约束式中，找出各非基变量列中系数为负的那些元素，用相应的检验数b 分别除以这些负元j素，所得各负比值中最大者所在列即为换入列。5. 以 a 为主元素进行取主变换rk返回步骤 2，继续迭代。三、关于初始对偶可行的基本解1. 构造扩充问题min z = CX 0其中 R 是非基变量下标的集合。再增加一个变量和一个约束条件，得到其扩充问题：min z = CXX + 工 Px = bBj jvj琴x + 厶 x = M n +1jjeRx 0(i = 1,2, n +1)i2. 求扩充问题的初始对偶可行的基本解若基本解X(o)不是对偶可行的，即检验数中有负的，并假设负检验数B中最小的一个为b，则以b相应的变量x为换入变量，以x为换出kkkn +1变量，即以a为主元素进行取主变换，可得到全部检验数 0，即m+1,k得到一个对偶可行的基本解。3. 用对偶单纯形法求解扩充问题，并得到原问题的解答 因为扩充问题的对偶问题有可行解，根据对偶原理可知，扩充问题或 无可行解或有有限最优解。若扩充问题无可行解，则原问题也无可行解，若扩充问题得到最优解X (0 二(x (0),x (0), x (0)，贝U X (0)二(x (0),x(o) )是原问题的可行解。若扩充1n n+11n问题的目标函数最优值与M无关，则x (0)就是原问题的最优解。4. 计算举例3.4 灵敏度分析 研究初始单纯型表上的系数变化对最优解的影响，研究这些系数在什 么范围内变化时，原最优基仍是最优的；若原最优基不再是最优的， 如何用最简便的方法找到新的最优解。假定线性规划标准型最终表上已得到最优基B,最优结果为：X _ B-1bB=XN_ 0 _min z = C B-ibB一、 改变价值向量 Cc = c + Acr r r1. 在最终表内， x 是非基变量rC， z = C B-iP均不变；仅b变化。Bj Bjrb =c -z =c +Ac -z =b +Acr r r r r r r r若b 0，即Ac -a，则最优解不变;若a 0，则原最优基不再是最优的了。以x为换入变量，把最终表 rr上的a换成a ， c换成C ，继续用单纯形法求解。r r r r2. 在最终表内， x 是基变量rC 要改变，并因此影响到各个检验数。Bkj若 maxy /a I a oL Ac 0，则所有 a 0，即最优j kj kj r j kj kj j解不变。若Ac超出上述允许变化范围，即有a 0 Ab minx-Bi- I d id irV丿rid irV丿ir ir若Ab超过上述范围，则新得到的解为不可行解。但由于b的变化不 rr影响检验数，故仍保持所有检验数 0，即满足对偶可行性。这时可在原最终表的基础上，换上改变后的右端常数及相应的z值，用对偶单纯形法继续迭代，以求出新的最优解。三、 改变约束矩阵 A1. 非基向量列 P 改变为 P jj影响最终表上的第j列数据和第j个检验数。a = c 一 C B-1Pj j Bj若a 0，则原最优解仍是新问题的最优解。 j若b 0，则原最优基在非退化情况下不再是最优基。这时，应在原 j最终表的基础上，换上改变后的第j列数据B-1P和b ，把x作为换入 j j j变量，用单纯形法继续迭代。2. 基向量列 P 改变为 Pjj 重新计算四、增加一个新的约束条件 a x bm+1, j jm+1j=1即A X 0m +1 m +1 B 则现行对偶可行的基本解是新问题的可行解，亦即最优解。若(b -(A ) B-1b) 0，则原最优解就是新问题的最优解。n+1若b 0且为整数(j = 1,2,5)j4.3 汽油混合问题 变量的选取，是模型设立的关键。 逻辑关系的明晰，是模型设立的基础。4.4 购买汽车问题 明晰乘和的关系，用数字等数学符号将文字的约束关系表达出来4.5 产品加工问题 顺序理清方可使表达式明了。4.6 投资计划问题 列举各可行计划，逐期推算；同时注意限制性条件与同质较劣方案的放弃。4.7 企业年度生产计划问题一、 变量的选择最终产品的产量与新增设备的容量二、 构造线性规划模型1. 国家下达的指令性计划和市场需求约束x 一 x = Hj j jX D (j e J )jjh其中，x为完成国家指令性计划之后，超额生产的第j种产品产 j量，它也是决策变量；H 为国家对第 j 种产品的指令性计划指标；jD 为第 j 种产品在完成国家指令性计划之后，预测的市场最大 j需求量；J 为国家有指令性计划的产品的下标集合h对无指令性计划产品，则有X D (j 电 J )jjh其中， D 为所预测的市场对第 j 种产品的最大需求量j2. 设备生产能力约束弋 a -卩 y 卩 TG =1,2,9)ij i i i ij=13. 增加设备容量的限制约束 by Liii=1y Q G =1, 2,，9)ii4. 动力消耗约束艺 e x - x E j j E j=15. 下脚料的回收与复用约束x -Y r x 0(k =1，2, 3, 4)kRkj jjeJkp其中，J为产生第k种下脚料的产品下标集合kpx - Y q x 0(k =1, 2, 3, 4)kRkj jjJku6. 决策变量的非负约束x - 0 j(j =1， 2， 23)x - 0(j e J)jhy - 0(i =1, 2, 9)ixE - 0x - 0(k =1, 2, 3, 4)kR7. 目标函数max z =艺 P x - F 工 by - c x + 工 P xj ji iEk kRj=1i=1k =1综上，可得本问题的数学模型。4.8 企业年度生产计划的按月分配问题一月份axijj1Ybi1i=1x = x =051 81工 a x b( i =1 ,2, m)ijj1i1j=1x 0 j1( j =1 ,2, n)二月份i=i j=1ijj 2max z =迟bi2i=1x = x =052 82x = d 一 x42 4 41工 a x bij j 2 i2 j=1(i =1, 2,，m)x 0(j =1，2,，n )j24.9 合金添加的优化问题配料问题的推导min z =工 exjj j=1工(d 一 a )x (a 一 b ) w ij i ji ij=1工(d 一 c )x 0j例：某房地产公司有水泥100 单位、(i =1, 2,，m)(i =1, 2,，m)(j =1, 2, ，n)木材160单位和玻璃400 单位。用以建造A型和B型住宅。建一栋A型住宅需要水泥、木材和玻璃分别为 1、2、2 单位，售价每栋 100 万元；建一栋 B 型住宅需要水 泥、木材、玻璃分别为1、1、5 单位，售价每栋150 万元。该公司如 何安排两种住宅的建设，才能使总售价最大？max z = 100x +150x12x + x 1001 22x + x 160 1 22x + 5x 0且为整数12