西安交通大学MBA运筹学作业-关于线性规划的作业题

《运筹学》书上有关线性规划的作业题目一、将给出的线性规划问题化为标准型和对偶型两种类型：MinZ=X1+3X2+2X3+4X42X1+3X2-X3+X4=10S.t.3X1-2X2+2X3-X4≥-5X1-X2+X3-X4≤-3X1≥0，X2≤0，X3≥0，X4符号不限解：（1）令444xxx，其中440,0xx，在第二个约束不等式左边加上松弛变量5x，在第三个约束不等式左边减去松弛变量6x，令zz，化minz为maxz，则标准型为：12344max3244zxxxxx123441234451234461234456231032215..30,0,,,,,0xxxxxxxxxxxstxxxxxxxxxxxxx（2）设对偶变量为123,,yyy，对偶问题模型为：Max1231053wyyy123123123123123231323..2240,0,0yyyyyystyyyyyyyyy二、已知某线性规划问题的约束条件为：2X1+X2-X3=30-X1+2X2+X3-X4=55X2+X3-2X4-X5=60Xj≥0，j=1,2,…,5判断下列各点是否为该线性规划问题可行域的顶点。①X=(5,20,0,20,0)②X=(9,12,0,0,8)③X=(15,10,10,0,0)④X=(0,30,0,45,0)解：该线性规划问题中1215p2120p3111p4012p5001p分别将各点带入上述约束条件：①不满足约束条件，故不是可行域的顶点；②满足约束条件，为可行域的顶点；③满足约束条件，为可行域的顶点；④满足约束条件，为可行域的顶点；三、用单纯形法求解该线性规划。MaxZ=6X1-2X2+2X3+2X4X1+4X2-4X3+X4≤6S.t.2X1-X2+X3+3X4≤21-X1+3X2+3X3-X4≤29X1，X2，X3，X4≥0解：1、求一份初始基可行解12341441,,,21131331Apppp四、某饲养场饲养动物出售，设每头动物每天至少需要650g蛋白质、3g矿物质及6mg维生素。现有四种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示，要求确定既满足动物生长的营养需要，又使费用最省的配料方案（只建模，不求解）。饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）123430020010040010.80.420.61.20.51.80.80.60.31.5解：minz12340.8x0.6x0.3x1.5x1234123412341234300x200x100x400x650X0.8x0.4x2x3..0.6x1.2x0.5x1.8x6X,x,x,x0st五、某厂生产A，B，C三种产品，每种产品都要经过甲、乙两道工序。设该厂有两种规格的设备甲1甲2能完成甲工序；有三种规格的设备乙1，乙2和乙3能够完成乙工序。每种设备完成每个产品的加工工时，每台设备的可用工时，每工时的费用以及每件产品的原料费用和销售价格如下表所示，其中空缺位置表示该设备不能加工该种产品，要求安排最优的生产计划，使该厂利润最大，试建立相应的线性规划模型（不求解）。工序设备产品ABC设备有效台时设备加工费（元/h）甲甲1甲2483795000110000.100.05乙乙1乙2乙36255633000600040000.080.120.07原料费（元/件）单价（元/件）0.30.50.81.52.54对产品A来说，设以甲1，甲2完成甲工序的产品分别为X1，X2件，转入乙工序时，以乙2，乙3完成乙工序的产品分别为X3,X4,件；对产品B来说，设以甲1，甲2完成甲工序的产品分别为X5,X6，转入乙工序时，以乙1,乙3完成乙工序的产品为X7，X8件；对产品C来说，设以甲2完成甲工序的产品为X9件，则以乙2完成乙工序的产品也为X9件。由上述条件可得：12345678xxxxxxxx由题目所给的数据可得解此题的数学模型为：1256915269793948(1.50.3)()(2.50.5)()(40.8)0.15000(48)0.0511000(379)0.083000(62)0.126000(55)0.074000(63)zxxxxxxxxxxxxxxxx1526979394812345678948500037911000623000..556000634000,,,,,,,,0xxxxxxxstxxxxxxxxxxxxxMax注：以下这道题是星期五(3月9日)早上郭老师板书过的题:在极大化问题的下列表中，六个常数a1，a2，a3，β，σ1，σ2之值未知（假定无人工变量），分别写出对六个未知数的约束条件，使以下各小题关于该表的说法为真。①现行解最优，但不唯一；②现行解不可行（指出哪个变量造成）；③一个约束条件有矛盾；④现行解是退化的基本可行解；⑤现行解可行，但问题无有限最优解；⑥现行解是唯一最优解；⑦现行解可行，但将x1取代X6后，目标函数能改进。CBXBbX1X2X3X4X5X6X3β4a110a20X42-1-501-10X63a3-300-41σ1σ200-30解：CjXj121212131321512(1)0,0,0(2)0,0,0,,0(3)=00,04=3a043a;(5)0,0;(6)0,0aX；但中至少一个为；或而且；(4),为人工变量，且。