运筹学复习参考资料知识点及习题

《运筹学》复习参考资料知识点及习题

第一部分 线性规划问题的求解

一、两个变量的线性规划问题的图解法：

㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。 ㈡图解法：

图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；

2、确定可行解域；

3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；

注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）

例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示： 消 设 备 A B C 产 耗 品 利润 （万元） 甲 乙 有效总工时 3 5 9 9 5 3 540 450 720 70 30 —— 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？

（此题也可用“单纯形法”或化“对偶问题”用大M法求解）

1 / 27

《运筹学》复习参考资料知识点及习题

解：设x1、x2为生产甲、乙产品的数量。

max z = 70x1+30x2 s.t.

⑴

?3x1?9x2?540?5x?5x?450?12? 9x?3x?72012???x1，x2?0 ⑵ ⑶ ⑷ ⑸、⑹

可行解域为oabcd0，最优解为b点。 由方程组

?5x1?5x2?450? 解出x1=75，x2=15 9x?3x?7202?1?x1?T

∴X=??x??=（75，15）

?2?*

∴max z =Z*= 70×75+30×15=5700

2 / 27

《运筹学》复习参考资料知识点及习题

例2：用图解法求解

max z = 6x1+4x2 s.t.

⑴

?2x1?x2?10?x?x?8?12? x?72???x1，x2?0解：

⑵ ⑶ ⑷ ⑸、⑹

可行解域为oabcd0，最优解为b点。 由方程组

?2x1?x2?10? 解出x1=2，x2=6 x?x?8?12?x1?T

∴X=??x??=（2，6）

?2?*

∴max z = 6×2+4×6=36

3 / 27

《运筹学》复习参考资料知识点及习题

例3：用图解法求解

min z =－3x1+x2 s.t.

⑴

?4?x1?x2?3???2x1?5x2?12 ?x?2x?82?1??x1，x2?0解：

⑵ ⑶ ⑷ ⑸ ⑹、⑺

可行解域为bcdefb，最优解为b点。

?x1?44由方程组? 解出x1=4，x2=

2x?5x?1252?14T?x1?*??∴X=??=（4，）

5?x2?41∴min z =－3×4+=－11

554 / 27