目录第一部分课程设计题 (2)案例题一：线性规划 (2)案例题二：运输问题 (3)第二部分练习题 (5)线性规划问题练习题一 (5)练习题二 (5)练习题三 (6)练习题四 (7)练习题五 (8)运输问题练习题六 (9)练习题七 (10)练习题八 (11)练习题九 (12)练习题十 (13)练习题十一 (13)练习题十二 (14)最短路问题练习题十三 (15)练习题十四 (15)练习题十五 (16)最小支撑树问题练习题十六 (17)练习题十七 (18)最大流问题练习题十八 (18)练习题十九 (19)练习题二十 (20)参考文献： (21)案例题一某工厂拥有A 、B 、C 三种类型的生产设备，生产甲乙两种设备元件，每件产品在生产过程中所需要占用的设备台数、每件元件可获得的利润以及三种设备可以用的时数如下表所示：元件甲 元件乙 设备能力（h ） 设备A2 4 80 设备B1 2 42 设备C2 1 50 利润（元/件） 120 160问题是：工厂应生产多少单位元件甲和元件乙才能使获利最多？为多少？线性规划模型：目标函数: Max z =120x 1+160x 2约束条件: 2x 1 + 4x 2 ≤ 80s.t x 1 + 2x 2 ≤ 422x 1 + x 2 ≤ 50x 1 ,x 2 ≥ 0在上述约束条件中一次分别加入松弛变量54321,,,,x x x x x ，将其化为标准型： 目标函数: Max z =120x 1+160x 2约束条件: 2x 1 + 4x 2 + x 3 = 80x 1 + 2x 2 + x 4 = 42s.t. 2x 1 + x 2 + x 5 = 50x 1 ,x 2 ,x 3 ,x 4 ,x 5≥ 0以x 3 ,x 4 ,x 5，为基变量，则x 1 ,x 2 为非基变量，确定初始基本可行解为：X （0）=（0 0 80 42 50）T经手算得到最优解为：X 1 = 20 X 2 = 10 X 4 = 2（松弛标量，表示B 设备有2个机时的剩余）X（1）=（20 10 0 2 0）T最优值 z* = 4000上机验算结果如下**********************最优解如下*************************目标函数最优值为 : 4000变量最优解相差值------- -------- --------x1 20 0x2 10 0x3 0 33.333x4 2 0x5 0 26.667约束松弛/剩余变量对偶价格------- ------------- --------1 0 1202 0 1603 0 33.333目标函数系数范围 :变量下限当前值上限------- -------- -------- -------- x1 80 120 320x2 60 160 240x3 无下限 0 33.333 x4 无下限 0 66.667 x5 无下限 0 26.667 常数项数范围 :约束下限当前值上限------- -------- -------- --------1 50 80 842 40 42 无上限3 20 50 80案例题二某大型工厂有三家分厂，分别是分厂A，分厂B，分厂C，三家分厂生产同一种产品，日产量分别是5万吨,8万吨,7万吨，该厂共有四个销售处，其日销售量分别是6、5、8、4万吨，每个工厂到各个销售处的单位运费（万元/万吨），如下表。
试确定总运输费用最少的调运方案。
销地产地 1 2 3 4 产量（万吨）甲 7 6 4 6 5乙 5 9 8 3 8丙 3 5 2 4 74销量（万吨） 6 5 8利用表上作业法手算求得最优方案为：X12=4, X13=2, X21=2, X24=3, X31=3, X33=5, X42=4最小运费：z=4*5+3*2+6*2+0*3+4*3+2*5+3*4=72(万元)上机验算结果如下：********************************************起至销点发点 1 2 3 4 -------- ----- ----- ----- -----1 023 02 4 0 0 43 2 0 5 0此运输问题的成本或收益为: 72注释：总需求量多出总供应量 3第2个销地未被满足，缺少 3上机练习题练习1 线性规划问题⎪⎪⎩⎪⎪⎨⎧≥≤++-≥-≤+---=0,,10834124272323min 32132213213211x x x x x x x x x x x x x x z软件运行结果：**********************最优解如下*************************目标函数最优值为 : 0变量 最优解 相差值------- -------- --------x1 0 5x2 0 2.25x3 0 6约束 松弛/剩余变量 对偶价格------- ------------- --------1 7 02 12 03 0 1目标函数系数范围 :变量 下限 当前值 上限 ------- -------- -------- --------x1 -4 1 无上限 x2 无下限 -3 -.75 x3 -8 -2 无上限 常数项数范围 :约束 下限 当前值 上限 ------- -------- -------- --------1 0 7 无上限2 无下限 -12 03 0 0 9练习2 线性规划问题⎪⎪⎩⎪⎪⎨⎧≥≥++≥++≥++++=0,,3222434223804060min 321321321321321x x x x x x x x x x x x x x x z软件运行结果：**********************最优解如下*************************目标函数最优值为 : 76.66变量 最优解 相差值------- -------- --------x1 .833 0x2 .667 0x3 0 60约束 松弛/剩余变量 对偶价格------- ------------- --------1 1.833 02 0 -6.6673 0 -16.667目标函数系数范围 :变量 下限 当前值上限 ------- -------- -------- --------x1 40 60120 x2 15 4060 x3 20 80无上限常数项数范围 :约束 下限 当前值上限 ------- -------- -------- --------1 无下限 23.833 2 1.5 46 3 2 38练习3 线性规划问题max z = 2x 1-4x 2+5x 3-6x 4⎪⎩⎪⎨⎧≥≤+++-≤+-+0,,,14322824432143214321x x x x x x x x x x x x软件运行结果：**********************最优解如下*************************目标函数最优值为: 31变量最优解相差值------- -------- --------x1 8 0x2 0 66x3 3 0x4 0 130约束松弛/剩余变量对偶价格------- ------------- --------1 0 112 0 9目标函数系数范围:变量下限当前值上限------- -------- -------- --------x1 -1.667 2 无上限x2 无下限-4 62x3 -4 5 无上限x4 无下限-6 124常数项数范围:约束下限当前值上限------- -------- -------- --------1 -.6672 无上限2 -2 1 无上限练习4 线性规划问题Max z = 10X1 + 20X2X1 + X2≤ 2s.t. X1 + 5X2≤ 1X1 + X2≤ 1X1,X2≥ 0软件运行结果：**********************最优解如下************************* 目标函数最优值为 : 10变量最优解相差值------- -------- --------x1 1 0x2 0 30x3 1 0x4 0 10x5 0 0约束松弛/剩余变量对偶价格------- ------------- --------1 0 02 0 103 0 0目标函数系数范围 :变量下限当前值上限------- -------- -------- -------- x1 4 10 无上限 x2 无下限 20 50x3 0 0 7.5 x4 无下限 0 10x5 0 0 7.5 常数项数范围 :约束下限当前值上限------- -------- -------- --------1 12 无上限2 0 1 13 1 1 无上限练习5 线性规划应用问题某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。
现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示：饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1 3 1 0．5 0．22 2 0．5 1．0 0．73 1 0．2 0．2 0．44 6 2 2 0．35 12 0．5 0．8 0．8要求确定既满足动物生长的营养要求，又使费用最省的选择饲料的方案。
软件运行结果：**********************最优解如下*************************目标函数最优值为 : 35.0001变量最优解相差值------- -------- --------x1 0 .05x2 0 .6x3 0 .35x4 116.667 0x5 0 .2约束松弛/剩余变量对偶价格------- ------------- --------1 0 -.052 203.333 03 133.333 0目标函数系数范围 :变量下限当前值上限------- -------- -------- -------- x1 .15 .2 无上限 x2 .1 .7 无上限 x3 .05 .4 无上限 x4 0 .3 .4x5 .6 .8 无上限常数项数范围 :约束下限当前值上限------- -------- -------- --------1 300 700 无上限2 无下限 30 233.3333 无下限 100 233.333练习6 运输问题求最优运输方案。
BjAi B1B2B3B4aiA13 11 3 10 7A21 92 8 4A37 4 10 5 9bj3 6 5 6最优解如下********************************************起至销点发点 1 2 3 4-------- ----- ----- ----- -----1 0 0 5 22 3 0 0 13 0 6 0 3此运输问题的成本或收益为: 85练习7 运输问题已知某运输问题的供需以及单位运价如下表所示。