2023年运筹学复习参考资料知识点及习题.doc

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

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

㈠概念准备：

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

定义：达成目的的可行解为最优解。

㈡图解法：

图解法采用直角坐标求解：x1——横轴；x2——竖轴。

1、将约束条件（取等号）用直线绘出；

2、拟定可行解域；

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

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

4、拟定最优解及目的函数值。

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

例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：

品产耗消备设

品

产

耗

消

备

设

ABC

利润

（万元）

甲

乙

359

953

70

30

有效总工时

540450720

——

问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？

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

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

⑴maxz=70x1+30x

⑴

⑵

⑵

⑸、⑹

⑸、⑹

⑷

⑶

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

由方程组

解出x1=75，x2=15

∴X*==（75，15）T

∴maxz=Z*=70×75+30×15=5700

例2：用图解法求解

⑴maxz=6x1+4x

⑴

⑵

⑵

⑸、⑹

⑸、⑹

⑷

⑶

解：

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

由方程组

解出x1=2，x2=6

∴X*==（2，6）T

∴maxz=6×2+4×6=36

例3：用图解法求解

⑴minz=－3x1+x

⑴

s.t.

⑵

⑵

⑶

⑷

⑸

⑹、⑺

解：

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

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

∴X*==（4，）T

∴minz=－3×4+=－11

二、标准型线性规划问题的单纯形解法：

㈠一般思绪：

1、用简朴易行的方法获得初始基本可行解；

2、对上述解进行检查，检查其是否为最优解，若是，停止迭代，否则转入3；

3、根据θL规则拟定改善解的方向；

4、根据也许改善的方向进行迭代得到新的解；

5、根据检查规则对新解进行检查，若是最优解，则停止迭代，否则转入3，直至最优解。

㈡具体做法（可化归标准型的情况）：

设已知

maxz=c1x1+c2x2+…+cnxn

s.t.

对第i个方程加入松弛变量xn+i，i=1，2，…，m，得到

列表计算，格式、算法如下：

CB

XB

b

c1

c2

…

cn+m

θL

x1

x2

…

xn+m

cn+1

xn+1

b1

a11

a12

…

a1n+m

cn+2

xn+2

b2

a21

a22

…

a2n+m

.

.

.

.

.

.

.

.

.

…

…

…

…

cn+m

xn+m

bn

am1

am2

…

amn+m

z1

z2

…

zn+m

σ1

σ2

…

σn+m

注①：zj=cn+1a1j+cn+2a2j+…+cn+mamj=，（j=1，2，…

σj=cj－zj,当σj≤0时，当前解最优。

注②：由max{σj}拟定所相应的行的变量为“入基变量”；

由θL=拟定所相应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时规定将主元素变为1，此列其余元素变为0。

例1：用单纯形法求解（本题即是本资料P2“HYPERLINK图解法”例1的单纯形解法；也可化“HYPERLINK对偶问题”求解）

maxz=70x1+30x2

s.t.

解：加入松弛变量x3，x4，x5，得