运筹学概论 第4章 目标规划

第四章——1

第四章 整数规划

4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解）

表4－1

设备

材 料 甲 乙 资源限量

材料A（kg） 2 3 14

材料B（kg） 1 0.5 4.5

利润（元/件） 3 2

解：设生产甲、乙这两种设备的数量分别为x1、x2，由于是设备台数，则其变量都要求为整数，建立模型如下：

2123maxxxz

为整数21212121,0,5.45.01432xxxxxxxx

4.2 2197maxxxz

且为整数0,35763.212121xxxxxxts

割平面法求解。（下表为最优表）

jc 7 9 0 0 b

CB XB x1 x2 x3

x4

9 x2

0

1 7/22 1/22 7/2

7 x1 1 0 －1/22 3/22 9/2

cj－zj 0 0 －28/11 －15/11

解：

线性规划的最优解为：

63max,0,2/7,2/94321zxxxx

由最终表中得：

27221227432xxx ④

将系数和常数项分解成整数和非负真分式之和，上式化为；

213221227432xxx

移项后得： ①②③④

①②③ 第四章——2 即： 21221227212212274343xxxx

只要把增加的约束条件加到B问题的最优单纯形表中。

表4－3

jc 7 9 0 0 0 b

CB XB x1 x2 x3 x4 x5

9 x2 0 1 7/22 1/22 0 7/2

7 x1 1 0 －1/22 3/22 0 9/2

0 x5 0 0 －7/22* －1/22 1 －1/2

cj－zj 0 0 －28/11 －15/11 0

第四章——1第四章 整数规划

4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如

下，问这两种设备各生产多少使工厂利润最大？（只建模不求解）

表4－1设备

材 料甲乙资源限量

材料A（kg）2314

材料B（kg）10.54.5

利润（元/件）32

解：设生产甲、乙这两种设备的数量分别为x

1、x

2，由于是设备台数，则其变量都要求为整数，

建立模型如下：

2123maxxxz









为整数

21212121

,0,5.45.01432

xxxxxxxx

4.2

2197maxxxz









且为整数0,35763

.

212121

xxxxxx

ts

割平面法求解。（下表为最优表）

jc7900

CBXBx1x2x3x4b

9x2017/221/227/2

7x110－1/223/229/2

cj－zj00－28/11－15/11

解：

线性规划的最优解为：

63max,0,2/7,2/9

4321zxxxx

由最终表中得：

④

27

221

227

432xxx

将系数和常数项分解成整数和非负真分式之和，上式化为；

21

3

221

227

432xxx

移项后得：①

②

③

④

①

②

③第四章——2即：

21

221

227

21

221

227

4343xxxx

只要把增加的约束条件加到B问题的最优单纯形表中。表4－3



jc79000

CBXBx1x2x3x4x5b

9x2017/221/2207/2

7x110－1/223/2209/2

0x500－7/22*－1/221－1/2

cj－zj00－28/11－15/110

这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到：

表4－4jc79000

CBXBx1x2x3x4x5b

9x2010013

7x11001/7－1/732/7

0x30011/7－22/711/7

cj－zj000－1－8

由计算结果知还没有得到整数解，重新再寻找割平面方程。

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

1 基本要求

一、将线性规划化为标准型和写出相应的对偶规划；

二、用图解法求解具有两个决策变量的线性规划问题；

三、用单纯形方法及人工变量法求解线性规划问题；

四、灵敏度分析；

五、整数规划与分枝定界法，0-1规划与隐枚举法，指派问题

六、求解产销平衡的运输问题和产销不平衡的运输问题；

七、动态规划与求解。

例题选讲

例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆，每生产一件产品Ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。

设备

产品 A B C D

Ⅰ 2 1 4 2

Ⅱ 3 2 1 4

解 设生产产品Ⅰ和Ⅱ分别为1x和2x件，则由条件可得关系

max 12 23zxx

121212122312284162412xxxxxxxx

0,1,2ixi

⑴标准型的概念：

①目标函数为极大化；

②资源常数0ib；

③约束条件关系为等式；

④决策变量0ix。

例： 将下面的线性规划化为标准型 2 min 12343425zxxxx

1234123412344223142322xxxxxxxxxxxx

123400,,0,xxxx无非负限制

解 max 7193834255zzxxxxx