运筹期末复习题 - 图文

第二章 线性规划的图解法

P23 1.考虑下面线性规划问题：

maxz?2x1?3x2?x1?2x2?6 ?s..t?5x1?3x2?15?x,x?0?12（1）画出可行域.

（2）当z?6时，画出等值线2x1?3x2?6. （3）用图解法求出最优解及最优目标函数值. 解：可行域为：OABCO.

x2 5 3 A 2 B O C 3

6

x1

2z等值线x2??x1?.最优解在B点.由

33 解得最优解：x1=?x1?2x2?6 ?5x?3x?15?12121569，x2?.最优目标函数值：z??. 777

P25 4.考虑下面线性规划问题：

maxz?10x1?5x2?3x1?4x2?9 ?s..t?5x1?2x2?8?x,x?0?12（1）用图解法求解.

（2）写出此线性规划问题的标准型.

第 1 页 共 6 页

（3）求出此线性规划问题的两个松弛变量的值. 解：（1）可行域为：OABCO.

x2 4 z=16 2.2 A B O z=5

C z=11 1.6

3

x1

等值线x2??2x1?

z最优解在B点.由 5?3x1?4x2?9 ?5x?2x?8?123.最优目标函数值：z??17.5. 2解得最优解：x1=1，x2?（2）标准型为：

maxz?10x1?5x2?9?3x1?4x2?s1 ?s..t?5x1?2x2?s2?8?x,x,s,s?0?1212（3）s1?0,s2?0

P25 5.考虑下面线性规划问题：

minf?11x1?8x2?10x1?2x2?20?3x?3x?18 ?12s..t??4x1?9x2?36??x1,x2?0（1）用图解法求解.

（2）写出此线性规划问题的标准型.

（3）求出此线性规划问题的三个剩余变量的值. 解：（1）可行域为：ABCD.

第 2 页 共 6 页

10 x2 A 6 B 4 C D O 2

6

9

x1

等值线x2??11fx1?最优解在B点.由 88

?10x1?2x2?20 ?3x?3x?18?12解得最优解：x1=1，x2?5.最优目标函数值：z??51. （2）标准型为： maxz??f??11x1?8x2?20?10x1?2x2?s1?3x?3x?s2?18 ?12s..t??s3?36?4x1?9x2??x1,x2?0（3）s1?0,s2?0,s3?13

第五章 单纯形法

P97 3. 请考虑表5-14所给出的不完全初始单纯形表。

表5-14

x1 x2 x3 s1 6 30 25 0 3 1 0 1 0 2 1 0 2 1 -1 0 zj ? （1）把上面的表格填写完整. （2）按照上面的完整表格，写出此线性规划模型.

XB CB s2 0 0 1 0 s3 0 0 0 1 b ? 40 50 20 第 3 页 共 6 页

（3）这个初始解的基是什么？写出这个初始解和其对应的目标函数值. （4）在进行第一次迭代时，请确定其入基变量和出基变量，说明理由，并在表格上标出主元.解：（1） b ? x1 x2 x3 s1 s2 s3 XB CB 6 30 25 0 0 0 s1 0 3 1 0 1 0 0 40 40 s2 0 0 2 1 0 1 0 50 25 s3 0 2 [1] -1 0 0 1 20 20 zj 0 0 0 0 0 0 0 ? 6 30 25 0 0 0 (2)此规划的模型为：

max z?6x1?30x2?25x3

?40?3x1?x2

?2x2+x3?50 ? ? ?2x1?x2?x3?20 ?x,x,x?0?123

（3）初始解的基为：

?100??? B??010?

?001??? 初始解为：x1?0,x2?0,x3?0,s1?40,s2?50,s3?20,目标函数值为z?0 （4）入基变量为：x2，因为?2=30最大；出基变量为：s3，因为比值?3=20最小.

第 4 页 共 6 页

P97 5. 用单纯形法解下列线性规划问题 （1）

max z?12x1?8x2?5x3

?3x1?2x2?x3?20?

?x1?x2?x3?11 ?

?12x1?4x2?x3?48

?x,x,x?0?123

x1 x2 x3 x4 XB CB 12 8 5 0 x4 0 3 2 1 1 x5 0 1 1 1 0 x6 0 (12) 4 1 0 zj 0 0 0 0 ? 12 8 5 0 x4 0 0 (1) 3/4 1 x5 0 0 2/3 11/12 0 x1 12 1 1/3 1/12 0 zj 12 4 1 0 ? 0 4 4 0 x2 8 0 1 3/4 1 x5 0 0 0 (5/12) -2/3 x1 12 1 0 -1/6 -1/3 zj 12 8 4 4 ? 0 0 1 -4 x2 8 0 1 0 11/5 x3 5 0 0 1 -8/5 x1 12 1 0 0 -3/5 zj 12 8 5 12/5 ? 0 0 0 -12/5 所有?j?0，所以当前的基本可行解是最优解。 最优解为：x1?2,x2?5,x3?4；最优值为：z?84

第 5 页 共 6 页

x5 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 -9/5 12/5 2/5 12/5 -12/5 x6 0 0 0 1 0 0 -1/4 -1/12 1/12 1 -1 -1/4 1/12 1/6 0 0 -2/5 1/5 1/5 1/5 -1/5 b ? 20/3 11 4 8 21/2 12 32/3 4 --- 20 11 48 0 8 7 4 48 8 5/3 4/3 80 5 4 2 84

本文来源：https://www.bwwdw.com/article/n5gd.html