《运筹学》习题线性规划部分练习题及答案

1、运筹学线性规划部分练习题一、思考题1.什么是线性规划模型，在模型中各系数的经济意义是什么？2 .线性规划问题的一般形式有何特征？3. 建立一个实际问题的数学模型一般要几步？4. 两个变量的线性规划问题的图解法的一般步骤是什么？5. 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？6. 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。7 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。8 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。9. 在什么样的情况下采用

2、人工变量法，人工变量法包括哪两种解法？10. 大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什 么？最大化问题呢？11 什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情 况下，继续第二阶段？二、判断下列说法是否正确。1 .线性规划问题的最优解一定在可行域的顶点达到。2 .线性规划的可行解集是凸集。3. 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。4. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件， 可行域的范围一般将扩大。5 .线性规划问题的每一个基本解对应可行域的一个顶点。6. 如果一个线性规划问题有

3、可行解，那么它必有最优解。7. 用单纯形法求解标准形式（求最小值）的线性规划问题时，与j 0对应的变量都 可以被选作换入变量。8 .单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。9. 单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，可使目标函数值得到最快的减少。10 . 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。三、建立下面问题的数学模型1 .某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到第三年年初都可以投资。预计每年年初投资，年末可收回本利120%，每

4、年又可以重新将所获本利纳入投资计划；项目n需要在第一年初投资，经过两年可收回本利150% ,又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目川需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额不得超过15万元；项目需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？2 .某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、100克维生素。现有五种饲料可供选用，各种饲料每公斤营养

5、成分含量及单价如下表2 1所示：表 2 1饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1310 . 50 . 2220. 51 . 00. 7310. 20. 20. 446220. 35120. 50. 80. 8要求确定既满足动物生长的营养要求，又使费用最省的选择饲料的方案。设有某种原料的三个产地为 A1,A2,A3，把这种原料经过加工制成成品，再运往销售地。假设用4吨原料可制成1吨成品，产地 A1年产原料30万吨，同时需要成品7万吨；产 地 A 年产原料26万吨，同时需要成品13万吨；产地A3年产原料24万吨，不需要成 品。又知A1与A2间距离为150公里，A1与A3间距离

6、为100公里，A2与A3间距离为200公里。原料运费为 3千元/万吨公里，成品运费为 2.5千元/万吨公里；在 A1开设工厂加工费为 5.5千元/万吨，在A2开设工厂加工费为 4千元/万吨，在A3 开设工厂加工费为 3千元/万吨；又因条件限制，在 A2设厂规模不能超过年产成品5万吨，A1与A3可以不限制（见表2 2），问应在何地设厂，生产多少成品，才使生 产费用（包括原料运费、成品运费和加工费）最少？表2 2距产地产地、A1A2A3产原料数（万吨）加工费（千元/万吨）A10150100305 . 5A21500200264A31002000243需成品数（万吨）71304某旅馆每日至少需要下列

7、数量的服务员.（见表2 3）每班服务员从开始上班到下班连续工作八小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员。表2 一 3班次时1间 （日夜服务）最少服务员人数1上午6点一上午10点802上午10点一-下午2点903下午2点一下午6点804下午6点一夜间10点705夜间10点夜间2点406夜间2点一上午6点305. 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/人日，秋冬季收入为20元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需

8、要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元/每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养 200头。三种作物每年需要的人工及收入情况如表2 4所示表2 4大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540年净收入（元/公顷）300041004600试决定该农场的经营方案，使年净收入为最大。6. 市场对I、n两种产品的需求量为：产品I在1 4月份每月需1万件

9、，59月份每月需3万件，10 12月份每月需10万0件；产品H在3 9月份每月需1.5万件, 其它每月需5万件。某厂生产这两种产品的成本为：产品I在1 5月份内生产时每件5元，6 12月份内生产时每件 4.50元；产品H在在1 5月份内生产时每件 8元, 6 12月份内生产时每件 7元；该厂每月生产两种产品能力总和不超过12万件。产品I容积每件0.2立方米，产品n容积每件 0.4立方米。该厂仓库容积为1万5千立方米， 要求：（1）说明上述问题无可行解；（2）若该厂仓库不足时，可从外厂租借。若占用本厂仓库每月每立方米需 1元，而租用外厂仓库时上述费用增加为1.5元，试问在满足市场需求情况下，该厂

10、应如何安排生产，使总的生产加库存费用最少？（建立模型，不求 解）7. 某工厂I、n、川三种产品在下一年个季度的合同预定数如表2 5所示，该三种产品第一季度初无库存，要求在在第四季度末每种产品的库存为150件。已知该厂每季度生产工时为15000小时，生产产品I、n、川每件需 3, 4, 3小时。因更换工艺装备，产品I在第 二季度无法生产。规定当产品不能按期交货时，产品I、n每件每迟交一个季度赔偿 20元,产品川赔偿15元，又生产出来的产品不在本季度交货的，每件每季度的库存费为5元。问应如何安排生产，使总的赔偿加库存费用最小。表2 5含口产口仃季度1234I1500100020001200n150

11、0150012001500出1500200015002500&某玩具厂生产I、n、川三种玩具，这三种玩具需在A、E、C三种机器上加工，每60个为一箱。每箱玩具在不同的机器上加工所需的时间（天）如表2 6所示，本月可供使用的机器的时间为：A为15天，E为20天，C为2 4天。每箱玩具的价格为I:1500元；n： 1700元；川:2400元。问怎样安排生产，使总的产值最大。表2 一 6加工天数机器ABC玩具I261玩具n322玩具川52一9 某线带厂生产A、E两种纱线和C、D两种纱带，纱带由纱线加工而成。这四种产品的产值，可变成本（即材料、人工等随产品数量变化的直接费用），加工工时等由表2 7给出

12、，工厂有供纺纱的总工时 7200h，织带的总工时 1200h（1）列出线性规划模型，以便确定产品数量，使总的利润最大。（2）如果组织这次生产的固定成本（即与产品数量无关的间接费用）为20万元，线性规划模型有何变化？表2 7项目ABCD单位产值（元）1681401050406单位可变成本（兀）4228350140单位纺纱工时（h）32104单位织带工时（h）0020. 510. 某制衣厂生产4种规格的出口服装，有三种制衣机可以加工这4种服装，他们的生产效率（每天制作的服装件数） 等有关数据如表28所示，试确定各种服装的生产 数量，使总的加工费用最小。表2 8衣服规格制衣机需要生产 数量（件）AB

13、CI30060080010000n2804507009000出2003506807000IV1504104508000每天加工费（元）8010015011. 某制衣厂生产两种服装，现有100名熟练工人。已知一名熟练工人每小时生产10件服装I或6件服装n。据销售部门消息，从本周开始，这两种服装的需求量将持续上升。见表2 9，为此，该厂决定到第8周末需培训出100名新工人，两班生产。已知一名工人一周 工作40小时，一名熟练工人每周时间可培训出不多余5名的新工人（培训期间熟练工人和培训人员不参加生产）熟练工人每周工资400元，新工人在培训期间工资每周80元，培训合格后参加生产每周工资260元，生产效

14、率同熟练工人。在培训期间，为按期交货，工厂安排部分工人加班生产每周工作50小时，工资每周600元。又若所定的服装不能按期交货，每推迟交货一周的赔偿费为：服装I每件10元，服装n每件20元。工厂应如何安排生产，使各项费用总和最少。表2 9 （单位：千件/ 周）周次服装、12345678I2020242533344042n121417222225252512某家具制造厂生产五种不同规格的家具。 每种家具都要经过机械成型、 打磨、上漆几种 主要工序。每种家具的每道工序所用时间及每道工序的可用时间，每种家具的利润由表2 10给出。问工厂应如何安排生产，使总的利润最大？表 2 10生产工序所需时间（小时

15、）每道工序-一-二二四五可用时间成型346233600打磨435643950上漆233432800利润（百元）2 .734 .52.5313.某混合饲料场饲养为某种动物配置。已知此动物的生长速度和饲料中的三种营养成分甲、乙、丙有关，且每头动物每天需要营养甲 85克，乙5克，丙18克。现有五种饲料都含有这 三种营养成分，每种饲料每公斤所含营养成分及每种饲料成本如表2 11所示，求即满足动物成长需要又使成本最低的饲料配方。14.某食品厂在第一车间用 1单位原料N可加工3单位产品A及2单位产品B,产品A可 以按单位售价8元出售，也可以在第二车间继续加工， 单位生产费用要增加 6元，加工后单 位售价增

16、加9元。产品B可以按单位售价 7元出售，也可以在第三车间继续加工，单位生6元。原料N的单位购入价为2元，上述生产产费用要增加4元，加工后单位费用可增加 费用不包括工资在内。需1.5个工时，如 A继续加工，每单位需3工时，如B继续加工，每单位需N每月最多能得到10万单位。问如何安排生产，使工厂获利最大。15.某公司有30万元可用于投资，投资方案有下列几种： 方案I:年初投资能超过15万元。方案H:年初投资方案川：年初投资3个车间每月最多有 20万工时，每工时工资0.5元，每加工1单位N2个工时。原料元,第二年年底可收回5年内都可以投资，但投资额不元,元,第三年年底可收回 第四年年底可收回1. 3

17、 元。1. 4 元。1方案W:只在第二年年初有一次投资机会，每投资投资额不能超过10万元。方案V:只在第四年年初有一次投资机会，每投资资额不能超过20万元。方案存入银行，每年年初存入1元，年底可收回5年内都可以投资。5年内都可以投资。元，四年后可收回1.7元。但最多元，年底可收回1.4元。但最多投1.02 元.表 2 11饲料营养甲（克）营养乙（克）营养丙（克）成本（元）10. 500. 100. 08222. 000. 060. 70633. 000. 040. 35541 . 500. 150. 25450. 800. 200. 023投资所得的收益及银行所得利息也可用于投资.求使公司在第

18、五年底收回资金最多的投资方案.16.某工厂生产I、n、川、w四种产品，产品I需依次经过a B两种机器加工，产品n需依次经过 A C两种机器加工，产品川需依次经过 B、C两种机器加工，产品W需依次经过 A B机器加工。有关数据如表212所示，请为该厂制定一个最优生产计划。1.maxZx1 2x22.maxZ2x1 2x2表 2 12产品机器生产率（件/小时）原料成本（元）产品价 格（元）ABCI10201665n20102580出10151250w20101870机器成本（元/小时）200150225每周可用小时数15012070四、用图解法解下列线性规划3x1 5x2 15x1 x216x1

19、2x2 120.5x1 x2 2x1,x2 0x1 ,x2 03 min Z 2x1 3x24 min Z 2x1 10x2x1 3x2 3x1 x2 2x1 x2 23x1 x2 5x1 ,x2 0x1 ,x2 05 maxZ 3x1 9x26 maxZ x1 x2x1 3x2 32x1 x2 42x1 x2 20x2 6x1 x2 102x1 5x2 0x1 5x1 ,x2 0x1 , x2 0五、用单纯形法解下列线性规划问题。（可用大 M 法或两阶段法） 。(1) maxZ 2x1 x2 x3(2) maxZ 2x1 x2 x33x1 x2 x3 604x1 2x2 2x3 4x1 x2

20、 2x3 102x1 4x220x1 x2 x3 204x1 8x2 2x3 16x1,x2,x3 0x1,x2,x3 0(3) maxZ 3x1 x2 3x3(4) maxZ 2x1 4x2 x3x42x1 x2 x3 2x1 3x2 x4 4x1 2x2 3x3 52x1 x232x1 2x2 x3 6x2 4x3 x4 3x1 , x2 , x3 0x1 , x2 , x3 ,x4 0(5) maxZ x1 2x2 3x3 x4(6) maxZ 30x1 40x2100x3x1 2x2 3x3 152x1 x2 5x3204x1 3x2 x3 30x1 x2 x3 x4 10x1 3x2

21、 x3 12x1 , x2 ,x3 , x4 0x1 , x2 , x3 0(7) maxZ 6x1 x2 x3 x4maxZ 4x1 3x2(8)x1 2x2 x3153x1 6x2 3x3 4x4122x15x3186x13x3122x1 4x2 x3 x4 103x1 6x24x40x1 , x2 ,x3 , x4 0x1 , x2 , x3 , x4 0(9) min Z 3x1 2x2 4x3 8x4(10) max Z 5x1 2x2 x3X12X25X36x48x1 4x2 x362x15x23X35x432x1 x2 3x32X1 , X2 , X3,X40x1 , x2, x

22、3付号不限(11) max Z2x13x2X3X4(12) maxZ 5x1 3x2 6x3Xx2:2x3X492X2X3X45x1 2x2 x3182x1X23x3X412x1 x2 3x316X1X33x1 x2x3 10X , X2，X3,X40x1 , x20 , x3付号不限六、表2 13中给出求极大化问题的单纯形表，问表中ai , a2 ,C1 ,C2 ,d为何值时以及表中变量属于哪一种类型时有：（1 ）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）表中解为退化的可行解；（4 ）下一步迭代将以X1代替基变量X5 ；（5 ）该线性规划问题具有无界解；（6）该线性规划问题无

23、可行解。表 2 13XBbX1X2X3X4X5X3d4a1100X4X5231a253001001CjzjC1C2000七、某医院的护士分四个班次，每班工作12 h。报到的时间分别是早上6点，中午12点,下午6点，夜间12点。每班需要的人数分别为19人，21人，18人，16人。问：（1）每天最少需要派多少护士值班？（2） 如果早上6点上班和中午12点上班的人每月有 120元加班费，下午 6点和夜间12 点上班的人每月分别有 100元和150元加班费，如何安排上班人数，使医院支付的加 班费最少？八、某石油公司有两个冶炼厂。甲厂每天可生产高级、中级和低级的石油分别为200，300和200桶，乙厂每

24、天可生产高级、中级和低级的石油分别为100，200和100桶。公司需要这三种油的数量分别为14000，24000和14000桶。甲厂每天的运行费是 5000元，乙厂是4000元。问：（1 ）公司应安排这两个厂各生产多少天最经济？（2）如甲厂的运行费是 2000元，乙厂是5000元。公司应如何安排两个厂的生产。 列出线性规划模型并求解。运筹学习题解答第二章线性规划模型及其单纯形法二、（1） X V （3） V （4） V X X （7） V （8） V （9） X （10） V1解：设决策变量 x11 , x12分别表示第一年投资到项目I、n的资金额；X21 ,X23分别表示第二年投资到项目I、

25、川的资金额；X31，X34分别表示第三年投资到项目I、w的资金额。则得线性规划模型如下：maX Z 0.2X110.2X210.2X310.5 X120.6X230.4X34X11X123000000.2X11X21X12X233000000.2X110.2 X21 X310. 5X12X23X34300000X12200000X23150000X34100000X11 , X21 , X31, X12 , X23, X3402解：设五种饲料分别选取 X1 , X2 , X3 , X4 , X5 公斤，则得下面的数学模型： min Z 0.2X1 0.7 X2 0.4X3 0.3X4 0.8X

26、53X1 2X2X3 6X412X5700X1 0.5X20.2X32X4 0.5X5300.5 X1X20.2X32 X4 0.8 X5100Xj0 ( j1,2,3,4,5)；3解：设 Xi j 表示由 AA运往 Aj的原料数（单位：万吨) ( i , j 1, 2, 3) 。其中 ij 时，表示Ai留用数；yij表示由Ai运往Aj的成品数（单位：万吨）（i，j 1,2,3）。其中i j时，表示Ai留用数；zi表示在Ai设厂的年产成品数（单位：万吨）（i 1,2,3）。 则这一问题的数学模型为：min Z 3（X12 X13 X21 X23 X31 X32）2.5（ y12 y13 y21

27、y23 y31 y32） 5.5z1 4z2 3z3x11x12x1330x21x22x2313x31x32x3324x11x21x314z1x12x22x324z2x13x23x334z3y11y12y13z1y21y22y23z2y31y32y33z3y11y21y317y12y22y3213z25xi j0,yij0,zi 0(i, j1,2,3)4.解：设xi (i1，2， 3， 4， 5， 6）为第 i 班开始上班的服务员人数。则数学模型minZx1x2x3x4x5x6x6x180x1x290x2x380x3x470x4x540x5x630xj0(j 1, ,6)5.用x1，X2，x

28、3分别表示大豆、玉米、麦子的种植公顷数；X4，X5分别表示奶牛和鸡的饲养数； x6 ,x7 分别表示秋冬季和春夏季的劳动力（人日）数，则有maxZ 3000x1 4100x 2 4600x3 900x4 20x5 20x6 25x7x120x1x2 x3 1.5x410015000（土地限制 ）（资金限制 ） （劳动力限制 ）35x2400x4 3x510x3 100x40.6x5x6 350050x1175x240x350x40.3x5x7 4000（劳动力限制 ）x4200（牛栏限制 ）x51500（ 鸡舍限制 ）xj0 ( j1,2,7)6.解：（ 1）因为10 12 月份市场需求总计4

29、5 万件，这三个月最多生产 36 万件，故需10 月初有 9 万件的库存，超过该厂的最大仓库容积，故按上述条件，本题无解。（2 ）考虑到生产成本、库存费用和生产能力，该厂1012月份需求的不足只需在7 9月份生产出来留用即可，故设：Xi为第i个月生产的产品I的数量；为第i个月生512 11min Z(5xi 8yi)i 1i(4.5xi 7yi)(s1i6i 7s2i )xi10000 (i 1,2,3,4)xi 30000 (i5,6)yi50000 (i 1,2)yi 15000 (i 3, 4,5, 6)x730000 z7y7 15000 u7x8z7 30000 z8y8 u 7 1

30、5000 u8x9z8 30000 z9y9 u8 15000 u9x10z9 100000 z10y10 u9 50000u10x11z10 100000 z11y11 u10 50000u11x12z11100000y12 u1150000xiyi 120000 (i7,8,9,10,11,12)0.2zi0.4uis1is2i(i 7,8,9,10,11,12)产的产品n的数量；zi，ui分别为第i个月末产品I、 n的库存数，sii，s2i分别为用于第+ 1）个月库存的原有及租用的仓库容积（立方米），则所求问题的数学模型为：s1i 15000 (i 7,8,9,10,11,12)xi,y

31、i ,zi,ui,s1i,s2i 07解：设为j为第i个季度生产的产品j的数量；Si j为第i个季度末需库存的产品 j的数量;tij为第i个季度不能交货的产品 j的数量；yi j为第i个季度对产品j的预定数量，则有:min Z20(ti1xi1Xi 2Xi 315000 (i 1, 2,3, 4)x21044xiji1i1yi j150 (j 1,2,3)ixktijsiijyk j (i 1,2,3,4; jk1k1xi j ,si j , t ij0设Xj为第j （j1,2,3）种玩具的生产数量，则有：maXZ1500X11700X 2 2400X32X16X2X3153X12X22X32

32、05X12X224X1 , X2, X30 为整数解：（1）设A、E、C、D四种产品的生产数量分别为i1t i 2 )15ti 3335si ji1 j 11,2,3)maxZ (168 42) x1 (140 28) x2 (1050x1 , x2 , x3 , x4 ，则有：350)x3 (406 140)x43x1 2x2 10 x3 4x4 72002 x3 0.5 x4 1200 x1,x2,x3, x4 0(2)当增加固定资本2 0万元时，线性规划模型没有变化。10解：设 xi j(i仁2,3,4； j h2,3)为第j台制衣机生产第i种服装的天数，则有:11 解：设xi，yi分别

33、表示第i周用于生产服装I或服装n的工人数， 班的工人数，wi为从第i周开始参加培训新工人的熟练工人数，ui表示第i周起开始接受培Mi1和zi 表示第 i 周开始加训的新工人数，Vi1和vi2分别为第i周末没能按期交货的服装I或服装n的数量, Mi2分别为第i周对服装I或服装n的定货量，则有：880 260(8 i)ui18min Z600zii18(10vi1i1k20vi2)400xi(k1,2,8)kk240yivi2Mi2(k 1i1i1x1y1 w11000.25z1ixiyiwi100ut0.25zit18ui 100i1ui5wi(1i8)xi, yi , zi , wi,ui,v

34、i1 ,vi20i1vi1Mi1i1,2,8)(2 i 8)444min Z80 xi1100 xi 2150i1i1i1300x11600x12800x1310000280x21450x22700x239000200x31350 x32680 x337000150x41410x42450 x438000xi j0(i 1,2,3,4; j1,2,3)xi 312解：设五种家具的产量分别为min z2.7x13x24.5x3 2.5x4 3x53x14x26x32x43 x536004 x13x25x36x44x539502 x13x23 x34x45x52800x1 , x2 , x3 ,

35、x4 , x5 件， 则有x1,x2 ,x3,x4 ,x513解：设Xj (j1,2,3,4,5)为每公斤混合饲料中所含五种饲料的重量，则有min z2xi 6x2 5x34x4 3x50.50x12.00x23.00x31.50x40.80x5850.10x10.06x20.04x30.15x40.20为50.08x10.70x20.35x30.25x4O.O2X518Xi , X2 , X3 , X4 , X514.解：设 Xi：产品A的售出量；X2 :A在第二车间加工后的售出量;X3:产品B的售出量；X4 :B在第三车间加工后的售出量;X5 :第一车间所用的原料数量。则有maxz 8xi 9.5x2 7x3 8x42.75x5X51000003x22x41.5x52OOOOOXix2 3X5 OX3x4 2x5 OXi , X2 ,X3 ,X4，X5O15.解:max z设Xi1.2x14则有:16.解:xiiX21X31x6i 3OOOOOX12X22X32X42X62 1 .02 x61X42100000X13X23X631.2x11 1.02x62X14X54X641.2x12 1.3x21 1.0