03.2运筹学大M法

实 验 报 告

实验课程名称 运 筹 学

实验项目名称 大M法或两阶段法的上机实验

年 级

专 业

学生姓名

学 号

00 学 院

实验时间： 年 月 日 1 姓 名 学

号 实验组

实验时间 指导教师 成 绩

实验项目名称 大M法或两阶段法的上机实验

实验目的及要求：

实验目的：

1. 学会用Tora软件或Lindo软件求解线性规划问题，

2.理解每一步迭代计算中进基与出基变量等，了解大M法或两段法的上机实验。

实验要求：

完成作业P97页第6题及第7题（4）。

实验（或算法）原理：

1.大M法思路：

在单纯形法的基础上，为了使解线性规划有一个统一的解法，我们把所有求目标函数最小值的问题化为求目标函数最大值的问题。只要把目标函数乘以-1，就可以把原来求目标函数最小值的问题化为求目标函数最大值问题。为了找到一个满足条件的单位向量（非负），就需要加人工变量，注意人工变量与松弛变量和剩余变量是不同的，松弛变量和人工变量可以取零值也可以取正值，而人工变量只可以取零值，否则就会不等价。我们规定人工变量在目标函数中的系数为-M，M为任意大的数，这样只要人工变量大于零，所求的目标函数就是一个任意小的数，为了使目标函数最大，就必须将人工变量从

基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量

仍不为零，则该问题无可行解。像这样，为了构造初始可行基得到初始可行解，把人工变量”强行”的加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大的目标函数里的系数为-M的方法叫做大M法，M叫做罚因子。

1.4节中关于大M法和两阶段法的课堂例题讨论

课堂讨论题 习题1.5(2)P.51

用大M法和两阶段法求解

0,34233min2121212121xxxxxxxxxxz

标准化后为

0,,,34233min43212142132121xxxxxxxxxxxxxxz

采用大M法数学模型为 0,,,3423)(3min62162142153216521xxxxxxxxxxxxxxxMxxz

单纯形表法求解如下：

jc 3 1 0 0 M M 

BC Bx b 1x 2x 3x 4x 5x 6x

M

0

M 5x

4x

6x 3

4

3 1

2

1 (1)

1

1 -1

0

0 0

1

0 1

0

0 0

0

1 3

4

3

jjcz 3-2M 1-2M M 0 0 0

1

0

M 2x

4x

6x 3

1

0 1

1

0 1

0

0 -1

1

(1) 1

0

0 1

-1

-1 0

0

1 -

1

0

jjcz 2 0 1-M 0 2M-1 0

jc 3 1 0 0 M M 

BC Bx b 1x 2x 3x 4x 5x 6x 1

0

0 2x4x

3x 3

1

0 1

1

0 1

0

0 0

0

1 0

0

-1 0

1

0 1

-1

1

jjcz 3 2 0 0 0 M M-1

因此的最优解如下

TX]1030[*，最优目标函数min z=3。

采用两阶段法。第一阶段的数学模型是：

0,,,3423min621621421532165xxxxxxxxxxxxxxx

单纯形表法的求解如下

jc 0 0 0 0 1 1 

BC Bx b 1x 2x 3x 4x 5x 6x

1

0

1 5x

4x

6x 3

4

3 1

2

1 (1)

1

1 -1

0

0 0

一 线性规划图解法

1. 线性规划的标准形式：

(1) 目标函数最大；约束条件等式；决策变量非负（x≥0）；资源限量非负（b≥0）。

(2) 图解法两个变量系数C1、C2，斜率k=-(C1/C2)

(3) 图解法K≥0时，绝对值越大越靠近Y轴；K≤0时，绝对值越大越靠近Y轴。

(4) 阴影区：无论斜率为正或负，小于的部分阴影区都在线的下方。

二 单纯形法

1. 大M法

（1） 加入人工变量-Mxi…，M无穷大。

（2） 最后将人工变量xi替换出去，且σ≤0.

2. 两阶段法

（1）第一阶段：目标函数为 max𝑧′=−𝑥𝑖…，得到最终表。

（2）第二阶段：目标函数替换为原目标函数，在最终表里继续计算σ，直到都小于等于0。

3. 单纯表特殊情况的解判断

（1） 最优解中人工变量大于0，线性规划无解。

（2） 某次迭代过程，表中有一个σ＞0，且该列系数向量都小于等于0，线性规划无界。（因为比较比值大小时都是负的）。

（3） 某个非基变量σ=0，无穷解。

（4） 退化问题：相同的比值，选择下标大者离基。σk相同，任选一个入基。

4. 初等行变换

✓ 某一行（列），乘以一个非零倍数。

✓ 某一行（列），乘以一个非零倍数，加到另一行（列）。

✓ 某两行（列），互换。

三 单纯形法灵敏度分析

1. 对偶问题

原问题：max𝑧=𝑐𝑥 对偶问题：min𝑓=𝑏𝑇𝑦

Ax≤b 𝐴𝑇y≥𝑐𝑇

X≥0 y≥0

（1） 原问题统一为以上标准型，再进行下一步。

（2） 原问题第i个约束条件等号，对偶问题i个决策变量无约束。 （3） 原问题第i个决策变量无约束，对偶问题第i个约束条件等号。

（4） 原问题的对偶价格为对偶问题的最优解。（参考习题册第7、19题）

1. 简答题

（1） 运筹学的工作步骤

提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；

建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；

求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。复杂模型的求解需用计算机，解得精度要求可有决策者提出；

解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；

解的控制：通过控制解的变化过程决定对解是否做一定的改变；

解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。

（2） 退化产生原因及解决办法

单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。

勃兰特规则：

1.选取cj-zj＞0中下标最小的非基变量xk为换入变量，即k=min(j｜cj-zj＞0)

2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。

（3）对偶问题的经济解释

• 这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。

• 对偶变量 yi在经济上表示原问题第i种资源的边际价值。

• 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。 njmiiijjybxcZ11iiybZ若原问题的价值系数Cj表示单位产值，则yi 称为影子价格；

若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。

影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。

（4）分枝定界法步骤

a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解，

b) 若求得的最优解符合整数要求，则是原IP的最优解；

c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。