运筹学实验指导书.doc

《运筹学》实验指导书
一、实验项目一
1、实验项目名称
线性规划问题的求解
2、实验内容
,利用P26例5进行验证。
3、实验目的和要求
。
4、实验原理
单纯形法
5、实验仪器和设备
微型电子计算机
6、实验步骤
a. 应用单纯形算法对标准型
max{cx│Ax=b, x≥0}
的线性规划问题求解最优解
b. 数据文件格式
第1行 m,n,l0,ll
m: 约束方程的个数;
n: 决策变量的个数(不包括基变量);
l0: 人工变量的个数;
ll: ll=1---有人工变量,
ll=0---无人工变量.
第2─第m+3行
a[i,j](i=1,m+2;j=1,m+n+1)
a[i,j](i=1,m;j=1,n): 约束方程的系数矩阵;
a[i,j](i=1,m;j=n+1,n+m): m阶单位矩阵,其中人工变量必须置于最后l0个;
a[i,j](i=1,m;j=n+1): 约束方程的右端常数项列向量;
a[i,j](i=m+1;j=1,m+n+1):
ll=0---全部填零,
ll=1---第1至第m行上位于j列中所有人工变量系数之和;
a[i,j](i=m+2;j=1,m+n+1): 目标函数行上诸检验数.
c. 运行
按工具条运行按钮.
d. 输出结果
(a) 基可行解;
(b) 最优解.
e. 算例
1、求解
max z=2x[1]-2x[2]
┌-2x[1]+x[2]≤2
│ x[1]-x[2]≤1
└ x[j]≥0,j=1,2
解: 标准型为
max z=2x[1]-2x[2]
┌-2x[1]+x[2]+x[3] =2
│ x[1]-x[2] +x[4]=1
└ x[j]≥0,j=1,2,..,4
数据文件:
2 2 0
-2 1 2
1 -1 1
0 0 0
2 -2 0
输出结果:
线性规划问题的最优解
┏━━━━━━━━━━━━━━━━━┓
┃基变量最优值┃
┃ x( 3)= ┃
┃ x( 1)= ┃
┣━━━━━━━━━━━━━━━━━┫
┃所有其它变量都等于零┃
┃目标函数的最优值 max z= ┃
┗━━━━━━━━━━━━━━━━━┛
线性规划问题的多最优解
┏━━━━━━━━━━━━━━━━━┓
┃基变量最优值┃
┃ x( 3)= ┃
┃ x( 1)= ┃
┃ x( 2)= ┃
┣━━━━━━━━━━━━━━━━━┫
┃所有其它变量都等于零┃
┃目标函数的最优值 max z= ┃
┗━━━━━━━━━━━━━━━━━┛
2、求解
min f=x[1]+ x[2]
┌ x[1]+2x[2]≥2
│ x[1]- x[2]≥1
└ x[j]≥0,j=1,2
解: 两阶段问题为
min z= x[5]+x[6]
max f1=-x[1]-x[2]
┌ x[1]+2x[2]-x[3] +x[5] =2
│ x[1]- x[2] -x[4] +x[6] =1
└ x[j]≥0,j=1,2,...,6
数据文件:
2 4 2 1
1 2 -1 0 1 0 2
1 -1 0 -1 0 1 1
2 1 -1 -1 0 0 3
-1 -1 0 0 0 0 0
输出结果:
┌──────────────────────────┐
│最优解│
├──────────────────────────┤
│变量值│
│ x( 2)= │
│ x( 1)= │
├──────────────────────────┤
│所有其它的变量均为零. │
│目标函数最优值为- │
└──────────────────────────┘
a. 应用对偶单纯形算法检验数全部为非正而初始基本解不可行的线性规划问题求解最优解
b. 数据文件格式
第1行 m,n
m: 约束方程的个数;
n: 决策变量的个数.
第2─第m+1行
a[i,j](i=1,m;j=1,m+n+1)
a[i,j](i=1,m;j=1,n): 约束方程的系数矩阵;
a[i,j](i=1,m;j=n+1,n+m): m阶单位阵;
a[i,j](i=1,m;j=n