1、运筹学习题线性规划部分练习题及答案整理版运筹学线性规划部分练习题一、思考题1.什么是线性规划模型，在模型中各系数的经济意义是什么？2 .线性规划问题的一般形式有何特征？3.建立一个实际问题的数学模型一般要几步？4.两个变量的线性规划问题的图解法的一般步骤是什么？5.求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？6.什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。7试述线性规划问题的可行解、基础解、基础可行解、 最优解、最优基础解的概念及它们之间的相互关系。8试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、 有无穷多个最优解、无界解或无可
2、行解。9.在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？10.大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什 么？最大化问题呢？11 什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情 况下，继续第二阶段？二、判断下列说法是否正确。1.线性规划问题的最优解一定在可行域的顶点达到。2.线性规划的可行解集是凸集。3.如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。4.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件， 可行域的范围一般将扩大。5 .线性规划问题的每一个基本解对应可行域的一个顶点。6.如果
3、一个线性规划问题有可行解，那么它必有最优解。7. 用单纯形法求解标准形式（求最小值）的线性规划问题时，与 j 0对应的变量都 可以被选作换入变量。8 .单纯形法计算中，如不按最小非负比值原则选出换出变量， 则在下一个解中至少有一个基变量的值是负的。9.单纯形法计算中，选取最大正检验数 二k对应的变量xk作为换入变量，可使目标函数值得到最快的减少。10 . 一旦一个人工变量在迭代中变为非基变量后， 该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。三、建立下面问题的数学模型1.某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到第三年年初都可以投资。预计每年年初投资，年
4、末可收回本利 120%，每年又可以重新将所获本利纳入投资计划；项目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万吨；产 地A2年产原料26万吨，同时需要成品13万吨；产地A3年产原料24万吨，不需要成 品。又知A1与A
6、2间距离为150公里， A1与A3间距离为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需成品
7、数（万吨）71304某旅馆每日至少需要下列数量的服务员. （见表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
9、、n两种产品的需求量为：产品I在 1 4月份每月需1万件，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元，而租用外
10、厂仓库时上述费用增加为 1.5元，试问在满足市场需求情况下，该厂应如何安排生产，使总的生产加库存费用最少？（建立模型，不求 解）7.某工厂I、n、川三种产品在下一年个季度的合同预定数如表 2 5所示，该三种产品第一季度初无库存，要求在在第四季度末每种产品的库存为 150件。已知该厂每季度生产工时为15000小时，生产产品I、n、川每件需 3, 4, 3小时。因更换工艺装备，产品I在第 二季度无法生产。规定当产品不能按期交货时， 产品I、n每件每迟交一个季度赔偿 20元,产品川赔偿15元，又生产出来的产品不在本季度交货的，每件每季度的库存费为 5元。问应如何安排生产，使总的赔偿加库存费用最小。表
11、2 5含 口产 口仃季度1234I1500100020001200n1500150012001500出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两种纱带，纱带由纱线加工而成。这四种产品的
12、产值，可变成本（即材料、人工等随产品数量变化的直接费用） ，加工工时等由表2 7给出，工厂有供纺纱的总工时 7200h，织带的总工时 1200h（1） 列出线性规划模型，以便确定产品数量，使总的利润最大。（2） 如果组织这次生产的固定成本（即与产品数量无关的间接费用）为 20万元，线性规划模型有何变化？表2 7项目ABCD单位产值（元）1681401050406单位可变成本（兀）4228350140单位纺纱工时（h）32104单位织带工时（h）0020. 510.某制衣厂生产4种规格的出口服装，有三种制衣机可以加工这 4种服装，他们的生产效率（每天制作的服装件数） 等有关数据如表28所示，试确
13、定各种服装的生产 数量，使总的加工费用最小。表2 8衣服规格制 衣 机需要生产 数量（件）ABCI30060080010000n2804507009000出2003506807000IV1504104508000每天加工费（元）8010015011.某制衣厂生产两种服装，现有 100名熟练工人。已知一名熟练工人每小时生产 10件服装I或6件服装n。据销售部门消息，从本周开始，这两种服装的需求量将持续上升。 见表2 9，为此，该厂决定到第8周末需培训出100名新工人，两班生产。已知一名工人一周 工作40小时，一名熟练工人每周时间可培训出不多余 5名的新工人（培训期间熟练工人和培训人员不参加生产）
14、熟练工人每周工资 400元，新工人在培训期间工资每周 80元，培训合格后参加生产每周工资 260元，生产效率同熟练工人。在培训期间，为按期交货， 工厂安排部分工人加班生产每周工作 50小时，工资每周600元。又若所定的服装不能按期交货，每推迟交货一周的赔偿费为：服装I每件 10元，服装n每件20元。工厂应如何安排生产，使各项费用总和最少。表2 9 （单位：千件/ 周）周次服装、12345678I2020242533344042n121417222225252512某家具制造厂生产五种不同规格的家具。 每种家具都要经过机械成型、 打磨、上漆几种 主要工序。每种家具的每道工序所用时间及每道工序的可
15、用时间，每种家具的利润由表 2 10给出。问工厂应如何安排生产，使总的利润最大？表 2 10生产工序所需时间（小时）每道工序-一-二二四五可用时间成型346233600打磨435643950上漆233432800利润（百元）2 .734 .52.5313.某混合饲料场饲养为某种动物配置。 已知此动物的生长速度和饲料中的三种营养成分甲、乙、丙有关，且每头动物每天需要营养甲 85克，乙5克，丙18克。现有五种饲料都含有这 三种营养成分，每种饲料每公斤所含营养成分及每种饲料成本如表 2 11所示，求即满足动物成长需要又使成本最低的饲料配方。表 2 11饲料营养甲（克）营养乙（克）营养丙（克）成本（元
16、）10. 500 . 100 . 08222 . 000 . 060 . 70633 . 000 . 040 . 35541 . 500 . 150 . 25450 . 800 . 200 . 023投资所得的收益及银行所得利息也可用于投资 .求使公司在第五年底收回资金最多的投资方案.16.某工厂生产I、n、川、w四种产品，产品I需依次经过 a B两种机器加工，产品n需依次经过 A C两种机器加工，产品川需依次经过 B、C两种机器加工，产品W需依次经过 A B机器加工。有关数据如表212所示，请为该厂制定一个最优生产计划。表 2 12产 品机器生产率（件/小时）原料成本（元）产品价 格（元）A
17、BCI10201665n20102580出10151250w20101870机器成本（元/小时）200150225每周可用小时数15012070四、用图解法解下列线性规划1maxZ = X +2x22maxZ = 2x1 2x2X4- 100X33x1 5x2 -15 6X +2x2 兰 12x1 , x2 色 03min Z = 2X +3x2% +3x2 启 3 + x2 2i X , x2 3 05 maxZ 二 3x1 9x2X +3x2 兰 32一旳+x2兰4* x2 兰 62X -5x2 兰 0为，X2 - 0五、用单纯形法解下列线性规划问题。C） maxZ = 2X _ x2 x
18、33X +x2 +x3 兰 60X -x2 +2x3 兰 10X x2 - x3 乞 20XX2，X3 - 0 maxZ =3X x2 3x3 2禺 +x2 +x3 兰 2 x1 2x2 3x3 - 5 2X +2x2 +x3 兰 6 maxZ 二 x1 2x2 3x3 _ x4+2x2 +3x3 =152x +x2 +5x3 =20x1 x2 x3 x4 =10* , X2 , X3 , X4 - 0X 一 X? 2 -1* 一 0.5X + x2 兰 2x1 ,x 04min Z = 2X - 10x2一 x2 兰 2= 3x1 - X2 王-5x1 , x2 06 maxZ 二旳 x22
19、X + x2 兰 20+x2 芒10| x5i X1 , X2 占0（可用大M法或两阶段法）。 maxZ = 2x1 x2 x3 4比 +2x2 +2x3 4 2捲+4乂2 兰204x1 8x2 2x3 乞 16l捲也乂3狂0（4）maxZ 二 2x1 4x2 x3x +3x2 + x4 兰 42X + x2 w 3I x2 +4x3 + & 兰 3X1 , X2 , X3 , X4 - 0（6）maxZ 二 30x1 40x24x1 + 3x2 - x3 = 30 + 3x2 - x3 = 12N , X2 , X3 启 0 maxZ =6X x2 _x3 x4LX +2x2 +x3 =15
20、（8）maxZ 二 4X 3x22X12X1工5x3 =184x2 x3 x4 =10轡，X2 , X3 , X4 - 03x1 6x2 3x3 - 4x46X1 3X33X - 6x2 4x4为，X2 , X3 , X4 - 012120（10）maxZ =5x -2x2 x3（9）min Z = 3x2x2 4x3 8x4X +2x2 +5X3 +6X4 兰8 2X + 5x2 十 3x3 5x4 兰 3Xi , X2 , X3 , X4 r 0（11）max -2x1 3x2 _ x3 x4 X _ x2 + 2x3 + x4 z 9 2x2 +x3 -x4 _ 2X + X2 - 3X
21、3 + X4Xi +X3Xi , X2 , X3 , X4 一 05 -1-3X + 4x2 + x3 兰 6 2X +x2 +3x3 3 2x1 , x2色，x3符号不限 （12）maxZ =5x1 3x2 6x3 +2x2 +x3 兰 182x + x2 +3x3 兰 161 X + x2 + x3 = 10X , x2 - 0, x3符号不限六、表2 13中给出求极大化问题的单纯形表， 问表中a1，a2，C1，C2，d为何值时以及表中变量属于哪一种类型时有：（1 ）表中解为唯一最优解； （2）表中解为无穷多最优解之一；（3）表中解为退化的可行解；（4 ）下一步迭代将以X1代替基变量X5
22、；（5 ）该线性规划问题具有无界解； （6）该线性规划问题无可行解。表 2 13XBbX1X2X3X4X5d4100X3a121010X435001a23X5000Cj -ZjC1C2七、某医院的护士分四个班次， 每班工作12 h。报到的时间分别是早上 6点，中午12点,下午6点，夜间12点。每班需要的人数分别为 19人，21人，18人，16人。问：（1） 每天最少需要派多少护士值班？（2） 如果早上6点上班和中午12点上班的人每月有 120元加班费，下午 6点和夜间12 点上班的人每月分别有 100元和150元加班费，如何安排上班人数，使医院支付的加 班费最少？八、某石油公司有两个冶炼厂。甲
23、厂每天可生产高级、中级和低级的石油分别为 200，300和200桶，乙厂每天可生产高级、中级和低级的石油分别为 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分别
24、表示第一年投资到项目I、n的资金额； X21，x23分别表示第二年投资到项目I、川的资金额； X31，X34分别表示第三年投资到项目I、的资金额。则得线性规划模型如下：maxZ 二 0.2x11 0.2x21 0.2x31 0.5x12 0.6x23 0.4x34X11 + X12 3000000.2X1 + X21 + X12 * X23 300000 0.2X1 0.2x21 +X31 0.5x2 +X23 +X34 兰 300000 x12 200000x23 700X +0.5x2 +0.2x3 +2x4 + 0.5x5 兰 300.5X +x2 +0.2x3 十2x4 十 0.8x5
25、 王 100、 Xj0 (j =123,4,5);3解：设Xij表示由Ai运往Aj的原料数(单位：万吨)(i , j = 1,2,3)。其中i = j时， 表示Ai留用数；yij表示由Ai运往 Aj的成品数(单位：万吨)(i，j 1,2,3)。其中 i=j时，表示Ai留用数；zi表示在Ai设厂的年产成品数(单位：万吨)(心1,2,3)。 则这一问题的数学模型为：min Z =3(X12 X13 X21 X23 X31 X32) 2.5(y12 %3 Y21y23 y31 32) 5.5可 4z?壮X11X12X13=30x21x22X23=13x31x32X33=24x11x21X31= 4z
26、1x12x22X32= 4z2x13x23X33二 4z3yny12=Z1y21y22y23二 Z2y31 * y32 * y33 = z3%i F % =7yi2 + y22 * y32 = 13z25勺0订0,z -0(i, j =1,2,3)4.解：设Xi (i =1 , 2, 3, 4, 5, 6)为第i班开始上班的服务员人数。则数学模型:m i rZ = x! x2 x3 x4 x5 x6X6X1-80X1X2-90X2X3-80X3X4-70X4X5-40X5X6-30Xj-0(j J ,6)5.用x1 , x2 , x3分别表示大豆、玉米、麦子的种植公顷数； x4,x5分别表示奶牛和鸡的饲养数；X6，x7分别表示秋冬季和春夏季的劳动力（人日）数，则有maxZ =3000X 4100x2 4600x3 900x4 20x5 20x6 25x7为 +x2 +x3 +1.5x4 100 （土地限制）400x4 +3x5 15000 （资金限制）20为 +35x2 +10x3 +100x4 +0.6x5 十 x 3500 （劳动力限制）丿 50为 +175x2 +40x3 +50x4 +0.3x5 + x7 兰 4000 （劳动力限制）
