习运筹学 题 1 (1)

1、习 题 11 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。 答案： (a)唯一解); (b)唯一解);(c)唯一解); (d)无界解）2 用单纯形法求解下列线性规划问题。 答案： (a)唯一解)，对偶问题; (b)唯一解），3 用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。 答案：(a)无界解；(b)唯一解)，对偶问题4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数al的值。表1-54 初始单纯形表bx1x2x3x4x5x46(b)(c)(d)10x51-13(e)

2、01cj-zj(a)-1200表1-55 单纯形法迭代后的表bx1x2x3x4x5x1(f)(g)2-11/20x54(h)(i)11/21cj-zj0-7(j)(k)(l)表1-55基变量x1列向量，所以g=1,h=0 （2）初始表 某步表 有已知表查出 （3）初始表主元行×（-主元检验数/主元）加到检验数行得下一步表的检验数行。表1-54第一行系数×（-a/b）+表1-54检验数行=表1-54检验数行即：故：。5某厂生产、三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品可在A、B任何一种设备

3、上加工；产品可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据见下表1-56，试安排最优生产计划，使该厂获利最大。表1-56 产品的有关数据表设备产品设备有效台时设备加工费（元/小时）A1A2B1B2B35 7647109812116 00010 0004 0007 0004 0000.050.030.060.110.05原料费（元/件）售价（元/件）0.251.250.352.000.502.806 一家糖果商店出售三种不同品牌的果仁糖，每个品牌含有不同比例的杏仁、核桃仁、胡桃仁。为了维护商店的质量信誉，每

4、个品牌中所含有的果仁的最大、最小比例是必须满足的，如下表1-57所示：表1-57 每个品牌中所含有的果仁的比例表品牌含量需求每磅售价（美元）普通腰果仁不超过20%胡桃仁不低于40%核桃仁不超过25%杏仁没有限制0.89豪华腰果仁不超过35%杏仁不低于40%核桃仁、胡桃仁没有限制1.10蓝带腰果仁含量位于30%50%之间杏仁不低于30%核桃仁、胡桃仁没有限制1.80表1-58列出了商店从供应商每周能够得到的每类果仁的最大数量和每磅的价格：表1-58 每类果仁的最大数量和每磅的价表果仁类型每磅价格（美元）每周最大供应量（磅）杏仁0.452000核桃仁0.554000腰果仁0.705000胡桃仁0.

5、503000商店希望确定每周购进杏仁、核桃仁、腰果仁、胡桃仁的数量，使周利润最大。建立数学模型，帮助该商店管理人员解决果仁混合的问题。7 写出下列线性规划问题的对偶问题。 答案： （a） （b）8 已知线性规划问题： 试应用对偶理论证明上述线性规划问题最优解为无界。答案：显然为该问题的可行解， 其对偶问题为：显然第一个约束与变量非负要求矛盾，故对偶问题无可行解。由无界性该问题最优解为无界。9 已知线性规划问题： 要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=(2,2,4,0)T，试根据对偶理论求出对偶问题最优解。答案：对偶问题设对偶问题的最优解为将X*=(2,2,4,0)T代入原问

6、题，约束（4）为严格不等式（即x*S1，x*S2，x*S3）0），由互补松弛性，y*4=0。又因为x*1 =2,x*2 =2,x*3 =4都大于0，由互补松弛性，对偶问题对应（1）-（3）约束为等式，（即y*S1= y*S2 =y*S3=0）故有，解得对偶问题的最优解为。10 已知线性规划问题： 先用单纯形法求出最优解，再分析在下列条件单独变化的情况最优解的变化。（1）目标函数变为；（2）约束右端项由变为；（3）增添一个新的约束条件：。答案：最终表 cj 2 -1 1 0 0bCB XBx1 x2 x3 x4 x52 x10 x5 1 1 1 1 0 0 3 1 1 1 610 0 -3 -1

7、 -2 0该问题的最优解，最优值对偶问题的最优解，最优值（1）目标函数中非基变量的系数由-1变为3 重新计算的检验数最优解发生变化，将的检验数，系数代入最终表，用单纯形法求解之，见下表 cj 2 3 1 0 0bCB XBx1 x2 x3 x4 x52 x10 x5 1 1 1 1 0 0 3 1 1 1 610* 0 （1） -1 -2 02 x13 x21 0 2/3 2/3 -1/30 1 1/3 1/3 1/38/310/30 0 -4/3 -7/3 -1/3该问题的最优解，最优值对偶问题的最优解,最优值（2），故最优基不变最优解为，最优值（3）最优解不满足新加的约束将约束化为等式，选

8、松弛变量作为基变量得将其添加到最终表得过渡表，然后将第一行乘-1加到第三行将基变量x1的系数列向量化为单位向量 cj 2 -1 1 0 0 0bCB XBx1 x2 x3 x4 x5 x62 x10 x50 x6 1 1 1 1 0 0 0 3 1 1 1 0 1 0 -2 0 0 1 610-2 2 x10 x50 x6 1 1 1 1 0 0 0 3 1 1 1 0 0 -1 -3 -1 0 1 6 10（-8）0 -3 -1* -2 0 02 x10 x51 x3 1 2/3 0 2/3 0 1/3 0 8/3 0 2/3 1 1/3 0 1/3 1 1/3 0 -1/3 10/3 22

9、/38/30 -8/3 0 -5/3 0 -1/3新的最优解，最优值11 用分支定界法求解下列整数规划问题：(1) (2) 12 用隐枚举法求解下列0-1规划问题： xj=0 或1，j = 1，2，3，4，513 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务已知各条航线的起点、终点城市及每天航班数见表1-59。假定各条航线使用相同型号的船只，又各城市之间的航程天数见表1-60。又知每条船只每次装卸货物的时间各需1天，则该航运公司至少应配备多少条船,才能满足所有航线的运货需求? 建立模型并用软件求解。表1-59 各条航线的起点、终点城市及每天航班数表航线起点终点每

10、天航班1234EBADDCFB3211表1-60 各城市之间的航程天数表 终点起点ABCDEFABCDEF012147710313882301555141315017207851703785203014设某公司有五个人可以完成五项工作，每人做每项工作的用时如表1-61所示。每人仅做一项工作，每项工作仅一人做。如何安排是用时最少？建立数学模型并用软件求解表1-61 每人完成任务的用时表 单位：天 工作人员ABCDE人员甲127979人员乙89666人员丙71712149人员丁15146610人员戊410710915 思考题（1） 线性规划问题在数学模型的形式、可行域的组成和最优点的位置等方面与非

11、线性规划问题有什么不同？（2） 如何理解线性规划问题的求解其实就是可行域顶点的转换方法？（3） 线性规划的基解、基可行解和最优解之间有什么关系？（4） 在解得转换中，如何保证从一个基可行解转换得到的仍然是一个基可行解？（5） 在解的转换中，如何保证目标函数的值不仅下降，而且下降得最多？（6） 在单纯形算法中，如何选择主元？主元可以是负的吗？（7） 线性规划问题的约束条件是等式约束时，如何通过建立辅助规划问题的一个初始基本可行解？（9） 简述对偶单纯形法的优点、适用条件和求解步骤。(10) 试从经济上解释对偶问题和对偶变量的含义。（11）分支定界法求解极大化问题时，任何一个可行解的目标函数是否都

12、是该问题目标函数值的下界？16 案例练习题目：木材的储存和收购售出最优化问题问题背景：在实际的销售模型中，往往会碰到一类由于每个时期的需求和供给量不同，而需要囤积货物在后期高价出售的问题，由于受到储存的成本，储存的空间，每个时期的销量等各方面的限制，使这个问题显得愈加复杂。 目标：要求就一个实际的木材的储存和收购售出的问题，简化该模型，使用线性规划的方法对其进行求解，并对各个参数进行灵敏度分析，最后给出合理的方案。问题提出：江苏省某木材储运公司有一个非常大的仓库以用来存储和出售木材，由于木材的每季度价格不同，该公司计划在每季度初购入木材，根据实际的市场需求，一部分用于出售，另一部分则存储起来，等待以后出售。 已知该公司的仓库的最大存储量为200万立方米，储存费用为(a+bu)元/万立方米，其中a=7万，b=10万，u为存储的时间（季度数）。已知每季度的买进卖出价格以及预计的销售量如表1-62所示。由于木材不适宜长期存储，所有的库存木材应该于每年的秋天末售完。表1-62 买进卖出价格以