运筹学习题集

运筹学习题集习题一1.1用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。(1)minz＝6x1＋4x2(2)maxz＝4x1＋8x2st.2x1＋x2≥1st.2x1＋2x2≤103x1＋4x2≥1.5－x1＋x2≥8x1,x2≥0x1,x2≥0(3)maxz＝x1＋x2(4)maxz＝3x1－2x2st.8x1＋6x2≥24st.x1＋x2≤14x1＋6x2≥－122x1＋2x2≥42x2≥4x1,x2≥0x1,x2≥0(5)maxz＝3x1＋9x2(6)maxz＝3x1＋4x2st.x1＋3x2≤22st.－x1＋2x2≤8－x1＋x2≤4x1＋2x2≤12x2≤62x1＋x2≤162x1－5x2≤0x1,x2≥0x1,x2≥01.2.在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。(1)maxz＝3x1＋5x2(2)minz＝4x1＋12x2＋18x3st.x1＋x3＝4st.x1＋3x3－x4＝32x2＋x4＝122x2＋2x3－x5＝53x1＋2x2＋x5＝18xj≥0（j＝1,…,5）xj≥0（j＝1,…,5）1.3.分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。(1)maxz＝10x1＋5x2st.3x1＋4x2≤95x1＋2x2≤8x1,x2≥0(2)maxz＝100x1＋200x2st.x1＋x2≤500x1≤2002x1＋6x2≤1200x1,x2≥01.4.分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类：(1)maxz＝4x1＋5x2＋x3(2)maxz＝2x1＋x2＋x3st.3x1＋2x2＋x3≥18st.4x1＋2x2＋2x3≥42x1＋x2≤42x1＋4x2≤20x1＋x2－x3＝54x1＋8x2＋2x3≤16xj≥0（j＝1,2,3）xj≥0（j＝1,2,3）(3)maxz＝x1＋x2(4)maxz＝x1＋2x2＋3x3－x4st.8x1＋6x2≥24st.x1＋2x2＋3x3＝154x1＋6x2≥－122x1＋x2＋5x3＝202x2≥4x1＋2x2＋x3＋x4＝10x1,x2≥0xj≥0（j＝1,…,4）(5)maxz＝4x1＋6x2(6)maxz＝5x1＋3x2＋6x3st.2x1＋4x2≤180st.x1＋2x2＋x3≤183x1＋2x2≤1502x1＋x2＋3x3≤16x1＋x2＝57x1＋x2＋x3＝10x2≥22x1,x2≥0，x3无约束x1,x2≥01.5线性规划问题maxz＝CX，AX＝b，X≥0，如X*是该问题的最优解，又λ＞0为某一常数，分别讨论下列情况时最优解的变化：（1）目标函数变为maxz＝λCX；（2）目标函数变为maxz＝（C＋λ）X；（3）目标函数变为maxz＝X，约束条件变为AX＝λb。1.6下表中给出某求极大化问题的单纯形表，问表中a1,a2,c1,c2,d为何值时以及表中变量属于哪一种类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）表中解为退化的可行解；（4）下一步迭代将以x1替换基变量x5；（5）该线性规划问题具有无界解；（6）该线性规划问题无可行解。x1x2x3x4x5x3d4a1100x42－1－5010x53a2－3001cj－zjc1c20001.7战斗机是一种重要的作战工具，但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外，需抽一部分用于培训驾驶员。已知每年生产的战斗机数量为aj（j＝1,…,n），又每架战斗机每年能培训出k名驾驶员，问应如何分配每年生产出来的战斗机，使在n年内生产出来的战斗机为空防作出最大贡献？1.8.某石油管道公司希望知道，在下图所示的管道网络中可以流过的最大流量是多少及怎样输送，弧上数字是容量限制。请建立此问题的线性规划模型，不必求解。2541031114365687351.9.某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：班次时间所需人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八小时，问该公交线路至少配备多少名司机和乘务人员。列出此问题的线性规划模型。1.10某班有男生30人，女生20人，周日去植树。根据经验，一天男生平均每人挖坑20个，或栽树30棵，或给25棵树浇水；女生平均每人挖坑10个，或栽树20棵，或给15棵树浇水。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型，不必求解。1.11.某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立此问题的线性规划的数学模型。甲乙丙原料成本(元/千克)每月限量（千克）A≥60％≥15％2.002000B1.502500C≤20％≤60％≤50％1.001200加工费（元/千克）0.500.400.30售价3.402.852.251.12.某商店制定7－12月进货售货计划，已知商店仓库容量不得超过500件，6月底已存货200件，以后每月初进货一次，假设各月份此商品买进售出单价如下表所示，问各月进货售货各多少，才能使总收入最多？请建立此问题的线性规划模型，不必求解。月份789101112买进单价282425272323售出单价2924262822251.13.某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日，春夏季4000人日，如劳动力本身用不了时可外出干活，春夏季收入为2.1元／人日，秋冬季收入为1.8元／人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工秋冬季为100人日，春夏季为50人日，年净收入400元／每头奶牛。养鸡时不占土地，需人工为每只鸡秋冬季需0.6人日，春夏季为0.3人日，年净收人为2元／每只鸡。农场现有鸡舍允许最多养3000只鸡，牛栏允许最多养32头奶牛。三种作物每年需要的人工及收人情况如下表所示。大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540年净收入(元／公顷)175300120试决定该农场的经营方案，使年净收人为最大。(建立线性规划模型，不需求解)习题二2.1写出下列线性规划问题的对偶问题(1)maxz＝10x1＋x2＋2x3(2)maxz＝2x1＋x2＋3x3＋x4st.x1＋x2＋2x3≤10st.x1＋x2＋x3＋x4≤54x1＋x2＋x3≤202x1－x2＋3x3＝－4xj≥0（j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3)minz＝3x1＋2x2－3x3＋4x4(4)minz＝－5x1－6x2－7x3st.x1－2x2＋3x3＋4x4≤3st.－x1＋5x2－3x3≥15x2＋3x3＋4x4≥－5－5x1－6x2＋10x3≤202x1－3x2－7x3－4x4＝2＝x1－x2－x3＝－5x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2已知线性规划问题maxz＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为maxz＝λCX（λ≠0）；（4）模型中全部x1用3代换。2.3已知线性规划问题minz＝8x1＋6x2＋3x3＋6x4st.x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3＋x4＝2x1＋x3≥2xj≥0（j＝1,2,3,4）(1)写出其对偶问题；(2)已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。2.4已知线性规划问题minz＝2x1＋x2＋5x3＋6x4对偶变量st.2x1＋x3＋x4≤8y12x1＋2x2＋x3＋2x4≤12y2xj≥0（j＝1,2,3,4）其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。2.5考虑线性规划问题maxz＝2x1＋4x2＋3x3st.3x1＋4x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80xj≥0（j＝1,2,3）（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。2.6已知线性规划问题maxz＝10x1＋5x2st.3x1＋4x2≤95x1＋2x2≤8xj≥0（j＝1,2）用单纯形法求得最终表如下表所示：x1x2x3x4bx201—x110—1?j=cj-Zj00——试用灵敏度分析的方法分别判断：（1）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变；（2）约束条件右端项b1，b2，当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；（3）问题的目标函数变为maxz＝12x1＋4x2时上述最优解的变化；（4）约束条件右端项由变为时上述最优解的变化。2.7线性规划问题如下：maxz＝—5x1＋5x2＋13x3st.—x1＋x2＋3x3≤20①12x1＋4x2＋10x3≤90②xj≥0（j＝1,2,3）先用单纯形法求解，然后分析下列各种条件下，最优解分别有什么变化？（1）约束条件①的右端常数由20变为30；（2）约束条件②的右端常数由90变为70；（3）目标函数中x3的系数由13变为8；（4）x1的系数列向量由（—1，12）T变为（0，5）T；（5）增加一个约束条件③：2x1＋3x2＋5x3≤50；（6）将原约束条件②改变为：10x1＋5x2＋10x3≤100。2.8用单纯形法求解某线性规划问题得到最终单纯形表如下：cj基变量50401060Sx1x2x3x4ac0116bd1024?j=cj-Zj00efg（1）给出a，b，c，d，e，f，g的值或表达式；（2）指出原问题是求目标函数的最大值还是最小值；（3）用a+?a，b+?b分别代替a和b，仍然保持上表是最优单纯形表，求?a，?b满足的范围。2.9某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30000千克。已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸千克，每打日记本用白坯纸千克，每箱练习本用白坯纸千克。又知每生产一捆原稿纸可获利2元，生产一打日记本获利3元，生产一箱练习本获利1元。试确定：（1）现有生产条件下获利最大的方案；（2）如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工？如要的话，招多少临时工最合适？2.10某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。产品原料甲乙可用量（千克）原料成本（元/千克）A241601.0B321802.0销售价（元）1316（1）请构造数学模型使该厂利润最大，并求解。（2）原料A、B的影子价格各为多少。（3）现有新产品丙，每件消耗3千克原料A和4千克原料B，问该产品的销售价格至少为多少时才值得投产。（4）工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产？在保持原问题最优基的不变的情况下，最多应购入多少？可增加多少利润？习题三3.1求