运筹学实验指导书.docVIP

《运筹学》实验指导书

一、实验项目一

1、实验项目名称

线性规划问题的求解

2、实验内容

利用运筹学软件包2.0对线性规划问题进行求解，利用P26例5进行验证。

3、实验目的和要求

掌握应用运筹学软件包2.0对线性规划问题进行求解的方法。

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、求解

maxz=2x[1]-2x[2]

┌-2x[1]+x[2]≤2

s.t│x[1]-x[2]≤1

└x[j]≥0,j=1,2

解:标准型为

maxz=2x[1]-2x[2]

┌-2x[1]+x[2]+x[3]=2

s.t│x[1]-x[2]+x[4]=1

└x[j]≥0,j=1,2,..,4

数据文件:

220

-212

1-11

000

2-20

输出结果:

线性规划问题的最优解

┏━━━━━━━━━━━━━━━━━┓

┃基变量最优值┃

┃x(3)=4.00┃

┃x(1)=1.00┃

┣━━━━━━━━━━━━━━━━━┫

┃所有其它变量都等于零┃

┃目标函数的最优值maxz＝2.00┃

┗━━━━━━━━━━━━━━━━━┛

线性规划问题的多最优解

┏━━━━━━━━━━━━━━━━━┓

┃基变量最优值┃

┃x(3)=6.50┃

┃x(1)=3.50┃

┃x(2)=2.50┃

┣━━━━━━━━━━━━━━━━━┫

┃所有其它变量都等于零┃

┃目标函数的最优值maxz＝2.00┃

┗━━━━━━━━━━━━━━━━━┛

2、求解

minf=x[1]+x[2]

┌x[1]+2x[2]≥2

s.t│x[1]-x[2]≥1

└x[j]≥0,j=1,2

解:两阶段问题为

minz=x[5]+x[6]

maxf1=-x[1]-x[2]

┌x[1]+2x[2]-x[3]+x[5]=2

s.t│x[1]-x[2]-x[4]+x[6]=1

└x[j]≥0,j=1,2,...,6

数据文件:

2421

12-10102

1