2013年运筹学期中练习自测试卷一、填空题1.线性规划问题2312312max3..2223250,1,2izxxstxxxxxxi的标准形式：24512456127max3..2223250,1,2,3,5,6,7izxxxstxxxxxxxxxi。2.图解法求解线性规划问题时，如果目标函数存在有限最优值，则最优解一定可以在可行域顶点达到。3.x是可行域的顶点充分必要条件是x是线性规划问题的基本可行解。4.线性规划问题2312312max3..2223250,1,2,3izxxstxxxxxxi用两阶段方法求解的辅助问题：612346125min..2223250,1,2,3,4,5,6igxstxxxxxxxxxi。5.两阶段方法求解线性规划问题时，第一阶段结束辅助问题目标函数大于零则原问题无解。6.线性规划问题2312312max3..2223250,1,2izxxstxxxxxxi的对偶问题：121212112min2523021..23,0wyyyyyystyyy。7.线性规划问题如果无界，则其对偶问题无解。8.求解运输问题的初始基本可行解有哪些方法：西北角方法、最小元素法、伏格尔法。9.求解整数线性规划问题的常用方法：分支定界方法、割平面方法。10.利用割平面方法求解某纯整数LP问题，如果在迭代过程中出现下述表格：x1x2x3x4RHSz00-1/4-1/4-3/2x1101/6-1/61x201-1/32/31/4则由x2行生成的割平面条件为：34221334xx。二、解答题11.线性规划问题121212min2..363230,1,2izxxstxxxxxi（1）写出标准形，（2）单纯形方法求解，（3）写出对偶问题，（4）利用（2）求得的解以及互补松紧条件写出对偶问题的最优解，（5）求c1的取值范围使得当前最优解仍为最优解，（6）求b1的取值范围使得当前最优基仍为最优基。12.用表上作业法求解下表中的运输问题。B1B2B3B4供应量A1106201115A212792025A361416185需求量515151013.用分支定界方法求解整数规划问题，且均为整数0,255.22108.02.1..34max21212121xxxxxxtsxxz。14.某市为了方便市民出行，准备修建四条城铁路线。四条线路决定由四家建筑公司分别承建。已知建筑公司对各线路的报价如下表。那么市政府如何给四家公司分配任务才能使费用最少？要求建立模型并求解。线路1线路2线路3线路4建筑公司121097建筑公司2154148建筑公司313141611建筑公司441513915.某企业计划生产甲、乙两种产品，这些产品分别在A、B、C、D四种不同的设备上加工。生产单位产品的资源消耗、资源拥有量及产品利润见下表。在C、D两种设备的使用时间受严格限制的基础上，考虑以下几个方面：（1）力求使企业利润不低于12百元。（2）考虑到市场需求，力争使甲、乙两种产品的比例大致为1:1。（3）要求充分利用A，尽可能不加班；必要时可以加班使用设备B，但不希望加班。建立模型并求解。消耗产品设备甲乙机时A2212B128C4016D0515利润（百元/件）23
