实验四：整数规划
一、实验目的：整数规划问题建模及软件求解。
二、实验要求：
1.掌握一般整数规划、0-1整数规划问题、指派问题的建模；
2.了解求解整数规划问题的方法：分支定界法、割平面法、隐枚举法、匈牙利法；
3.学会用matlab、 lingo软件求解整数规划问题。
三、实验内容：
1、求解下列整数规划问题：
.,0,30561652..max2121212121为整数xxxxxxxxtsxxz
(1)给出lingo原始代码；(2)求解结果粘贴。
(1)
model:
max=x1+x2;
2*x1+5*x2<=16;
6*x1+5*x2<=30;
@gin(x1);@gin(x2);
end
(2)
Global optimal solution found.
Objective value: 5.000000
Objective bound: 5.000000
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 0
Variable Value Reduced Cost
X1 5.000000 -1.000000
X2 0.000000 -1.000000
第 1 页 共 8 页
答案参见我的新浪博客：/s/blog_3fb788630100muda.html 《运筹学》试卷一
一、（15分）用图解法求解下列线性规划问题
二、（20分)下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，、为松弛变量，试求表中到的值及各变量下标到的值。
—1 3 1
0 0
1 6
1
1 —2 0 0
2
-1
1 1/2
1/2 0
1
4
0 7
三、（15分）用图解法求解矩阵对策，
其中
四、(20分）
（1）某项工程由8个工序组成，各工序之间的关系为
工序 a b c d e f g h
紧前工序 - — a a b,c b,c,d b,c,d e
试画出该工程的网络图.
（2）试计算下面工程网络图中各事项发生的最早、最迟时间及关键
线路(箭线下的数字是完成该工序的所需时间，单位：天）
第 2 页 共 8 页
答案参见我的新浪博客：/s/blog_3fb788630100muda.html
五、（15分)已知线性规划问题
其对偶问题最优解为，试根据对偶理论求原问题的最优解。
六、（15分）用动态规划法求解下面问题：
七、（30分）已知线性规划问题
用单纯形法求得最优单纯形表如下，试分析在下列各种条件单独变化的情况下，最优解将如何变化。
2 -1 1 0 0
2
3 1
0 1
3 1
1 1
1 0
1 6
10
0 —3 -1 —2 0
（1）目标函数变为；
(2）约束条件右端项由变为；
（3）增加一个新的约束：
八、（20分)某地区有A、B、C三个化肥厂向甲、乙、丙、丁四个销地供应同一种化肥，已知产地产量、销地需求量和各产地运往不同销地单位运价如下表，试用最小元素法确定初始调运方案，并调整求最优运输方案
销地
产地 甲 乙 丙 丁 产量
A 4 12 4 11 16
B 2 10 3 9 10
第四章——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/94321zxxxx
由最终表中得：
27221227432xxx ④
将系数和常数项分解成整数和非负真分式之和，上式化为；
213221227432xxx
移项后得： ①②③④
①②③ 第四章——2 即： 21221227212212274343xxxx
只要把增加的约束条件加到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 页 共 7 页
《运筹学》试卷一
一、（15分）用图解法求解下列线性规划问题
二、（20分）下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，、为松弛变量，试求表中到的值及各变量下标到的值。
-1
3
1
0 0
1 6
1
1 -2 0 0
2
-1
1 1/2
1/2 0
1
4
0 7
五、（15分）已知线性规划问题
其对偶问题最优解为，试根据对偶理论求原问题的最优解。
第 2 页 共 7 页
七、（30分）已知线性规划问题
用单纯形法求得最优单纯形表如下，试分析在下列各种条件单独变化的情况下，最优解将如何变化。
2 -1 1 0
0
2
3
1
0 1
3 1
1 1
1 0
1 6
10
0 -3 -1 -2 0
（1）目标函数变为；
（2）约束条件右端项由变为；
（3）增加一个新的约束：
八、（20分）某地区有A、B、C三个化肥厂向甲、乙、丙、丁四个销地供应同一种化肥，已知产地产量、销地需求量和各产地运往不同销地单位运价如下表，试用最小元素法确定初始调运方案，并调整求最优运输方案
销地
产地 甲 乙 丙 丁 产量
A 4 12 4 11 16
B 2 10 3 9 10
C 8 5 11 6 22
需求量 8 14 12 14 48
第 3 页 共 7 页
《运筹学》试卷二
一、（20分）已知线性规划问题：
（a）写出其对偶问题；
（b）用图解法求对偶问题的解；
（c）利用（b）的结果及对偶性质求原问题的解。
二、（20分）已知运输表如下：
销地
产地 B1 B2 B3 B4 供应量
A1 3 2 7 6 50
A2 7 5 2 3 60
A3 2 5 4 5 25
需求量 60 40 20 15
（1）用最小元素法确定初始调运方案；
（2）确定最优运输方案及最低运费。
