实验一最佳广告安排方案.doc

实验一最佳广告安排方案

189
2020年5月29日
文档仅供参考
实验八　最佳广告编排方案
【实验目的】
1．了解线性规划问题及其可行解、基本解、最优解的概念。
2．经过对实际应用问题的分析,初步掌握建立线性规划模型的基本步骤和方法。
3．学习掌握MATLAB软件求解有关线性规划的命令。
【实验内容】
一家广告公司想在电视、广播上做公司的宣传广告,其目的是争取尽可能多地招徕顾客。下表是公司进行市场调研的结果:

电视
网络媒体
杂志

白天
最佳时段
每次做广告费用(千元)
45
86
25
12
受每次广告影响的顾客数(千人)
350
880
430
180
受每次广告影响的女顾客数(千人)
260
450
160
100
这家公司希望总广告费用不超过750(千元),同时还要求:(1)受广告影响的妇女超过200万;(2)电视广告的费用不超过450(千元);(3)电视广告白天至少播出4次,最佳时段至少播出2次;(4)经过网络媒体、杂志做的广告要重复5到8次。
【实验准备】
线性规划是运筹学中产生较早的一个分支,如今在国防科技、经济学、现代工农业、环境工程、生物学等众多学科和领域里起着十分广泛的应用。
线性规划是在一组线性条件的约束之下,求某一个线性函数的最值问题。一般地线性规划的数学模型为:
　　 () ＝＋＋…
＋＋… ≤ ( or ＝ , ≥ ) , ＝1 , 2 , … , (1)
≥ 0 , ＝1 , 2 , … ,
用矩阵、向量符号,能够简化线性规划模型的表示:
…
＝ … , ＝ , ＝ , ＝
… … … … … … …
…
则线性规划问题可写为:
　　　　　() 　＝
≤ ( ＝ , ≥) 　　　　　　　　　　　　　　 　 (2)
≥ , ＝1 , 2 , … ,
这里,＝ 称为目标函数,为目标函数的决策变量,为费用系数,是常数向量; ≤ ( or ＝ , ≥ ) 称为约束条件,为线性规划的系数矩阵,它是常数矩阵,为利润(费用)向量,其中是subject to的缩写,意思是”满足约束条件”。
1．线性规划的标准形式
线性规划问题的标准形式为
＝
＝ (3)
≥
任何一种线性规划都能够等价地转换为标准形式。
(1)约束条件标准化––––松弛变量法
如果约束条件中有不等式:
　　　　　　　　　　　＋＋…≤
或
　　　　　　　　　　　＋＋…≥
经过引入两个非负变量xn+1,xn+2将上述约束条件转换成下面等价形式:
　　　　　　　　　　　＋＋…＋＝
　　　　　　　　　　　≥
或
　　　　　　　　　　　＋＋…－＝
≥
可见约束不等式均可转换为约束等式。
(2)目标函数的标准化
若原问题是求()＝,能够转换为求()＝－即可。
2．线性规划问题的解
在(3)中满足约束条件＝,≥的向量＝(,,…,)’称为线性规划问题的可行解,全体可行解组成的集合称为可行域,使目标函数＝达到最小值的可行解称为最优解。　
如果矩阵的某列所构成的方阵是满秩的,则的列向量,,…,构成线性规划的一组基,称为线性规划问题的一个基阵,的剩余部分组成的子矩阵记为,则能够写成＝(,)。则相应地能够写成＝(,)‘,的分量与的列相对应,称为基变量;的分量与的列相对应,称为非基变量。在约束＝中令所有非基变量取值为零时,得到的解＝(,0)‘称为与相对应的基解。当基解所有的分量都取非负时,即满足≥,则称其为基可行解,相应的基阵的列向量构成可行基。既是最优解,又是基可行解的称为最优基解。
定理1　如果线性规划(3)有可行解,那么一定有基可行解。
定理2　如果线性规划(3)有最优解,那么一定存在一个基可行解是最优解。
以上定理说明了如果所给的线性规划(3)有最优解,只要从基可行解上寻找最优解就行了。由于基可行解的个数是有限的,只要对所有的基可行解一一检查,就能够在有限次计算后确定最优解或断定该问题无最优解。
3．求解线性规划的MATLAB命令
(1)MATLAB5.2及以下版本使用命令
求解线性规划模型:
＝　　　　　　　　 　　　　　　 (4)
≤
这里为×矩阵,为×1列向量,为×1列向量。

x = lp( c , A , b )　求解线性规划模型(4);
x = lp( c , A , b , vlb , vub )　指定决策变量的上下界vlb≤x≤vub;
x = lp( c , A , b , vlb , vub , x0 )　指定迭代的初始值x0;
x = lp( c , A , b , vlb , vub , x0 , n )　n表示≤中前n个约束条件等式约束;
能够用help lp查阅有关该命令的详细信息。
(2)MATLAB5.3以上版本使用命令
MATLAB5.3以上的版本中优化工具箱(Optimization Toolbox)作了相当大的改进,虽然保留了lp命令,但已经使用新的命令linprog取代lp,而且在未来版本中将删除lp命令。
求解的线性规划模型:
＝　　　　　　　　 　　　　　　
　　　 ≤ 　　　　　　　　　　　　　　　 (5)
　　　　　　　　　　　　　·＝
　　　　　　　　　　　　　≤≤

x = linprog( c , A , b )　求解线性规划模型(4);
x = linprog( c , A , b , Aeq , beq )　 求解模型(5),问题中没有指定x的上下界;
x = linprog( c , A , b , Aeq , beq , lb , ub )　 求解线性规划模型(5);
x = linprog( c , A , b , Aeq , beq , lb , ub , x0 )　 指定迭代的初始值x0;
如果模型(5)中不包含不等式约束条件,可用［］代替A和b表示缺省;如果没有等式约束条件,可用［］代替Aeq和beq表示缺省;如果某个xi无下界或上界,能够设定lb(i)＝－inf或ub(i)＝inf;
用［x , Fval］代替上述各命令行中左边的x,则可得到在最优解x处的函数值Fval;
能够在MATLAB帮助文件中查阅有关该命令的详细信息。
【实验方法与步骤】
建立线性规划模型有三个基本步骤:
第一步,找出待定的未知变量(决策变量),并用代数符号来表示它们;
第二步,找出问题的所有限制或约束条件,写出未知变量的线性方程或线性不等式;
第三步,找到模型的目标,写成决策变量的线性函数,以便求其最大或最小值。
1．引例问题的分析与模型的建立
首先,确定决策变量,要求如何安排白天电视、最佳时段电视、网络媒体、杂志广告的次数,用符号表示,分别设定为
其次,确定所有的约束条件,广告总费用不超过750(千元),则有
45＋86＋25＋12≤750
受广告影响的女顾客数不少于200万,则有
　　　　　　　　260＋450＋160＋100≥
电视广告费用不超过450(千元),且白天至少播4次,最佳时段至少播出2次,则有
　　　　　　　　45＋86≤450 ,　≥4 ,　≥2
由于网络媒体和杂志广告要重复5到8次,则有
　　　　　　　　5≤≤8 ,　5≤≤8
最后,确定问题的目标函数,由题意知确定广告编排方案,使得受各种广告影响的潜在顾客总数:＝350＋880＋430＋180最多。故该问题完整的线性规划模型如下:
　　　　　　　　　＝350＋880＋430＋180
　　　　　　　　　　45＋86＋25＋12≤750
　　　　　　　　　　　 －260－450－160－100≤－
　　　　　　　　　　　　45＋86＋0＋0≤450
　　　　　　　　　　　　0＋0＋＋0≤8
　　　　　　　　　　　　0＋0＋0＋≤8
　　　　　　　　　　　　≥4 ,≥2,≥5,≥5
2．MATLAB计算机求解
用MATLAB求解的程序代码:
>> c=[-350 -880 -430 -180];　　%取－将目标函数标准化
>> a=[45 86 25 12; -260 -450 -160 -100; 45 86 0 0; 0 0 1 0; 0 0 0 1];
>> b=[750; - ; 450; 8; 8];
>> lb=[4; 2; 5; 5];
>> [x , Fval]=linprog(c, a, b, [ ], [ ], lb, [ ])　　%无等式约束条件和的上界,取［］表缺省
Optimization terminated successfully.
x =
4.0000
3.1395
8.0000
8.0000
Fval =
-9.0428e+003
【结果分析】
引例问题的目标函数是求受广告影响的最多顾客人数,而MATLAB命令linprog针对线性规划模型(5)求最小值,那么我们取－,将目标函数化成标准形式,在求得－＝－的最小值后,我们即可得到的最大值,根据约束条件,受广告影响的最多潜在顾客人数为9042800人。
在这里,用命令lp能够求得相同的结果。
【练习与思考】
1．一服务部门一周中每天需要不同数目的雇员:周一到周四每天至少50人,周五和周日每天至少70人,周六至少85人。现规定应聘者需连续工作5天,试确定聘用方案,即周一到周日每天聘用多少人,使在满足需要的条件下聘用总人数最少。
如果周日的需要量由75增至90人,方案应如何改变?
2．某地液化气公司两营业点A和B每月的进气量分别为9万 m3(立方)和12万 m3(立方),联合供应4个居民区a、b、c、d,4个居民区每月对气的需求量依次分别为7.5万 m3、4.5万 m3、6万 m3、3万 m3。营业点A离4个居民区的距离分别为7km、3km、6km、5.5km,营业点B离4个居民区的距离分别为4km、8km、5km、2km。问如何分配供气量使得总运输量(万m3×km)达到最小?
3．某工厂制造甲、乙两种产品,每种产品消耗煤、电、工作日及获利如下表所示,现有煤360t(吨),电力200kw·h,工作日300个。请制定一个使总利润最大的生产计划。

煤(t)
电(kw·h)
工作日
单位利润(元/t)
甲
9
4
3
7000
乙
5
5
10
1