实验八 最佳广告编排方案
【实验目的】
1．了解线性规划问题及其可行解、基本解、最优解的概念。
2．通过对实际应用问题的分析，初步掌握建立线性规划模型的基本步骤和方法。 3．学习掌握MATLAB软件求解有关线性规划的命令。
【实验内容】
一家广告公司想在电视、广播上做公司的宣传广告，其目的是争取尽可能多地招徕顾客。下表是公司进行市场调研的结果： 每次做广告费用（千元） 受每次广告影响的顾客数（千人） 受每次广告影响的女顾客数（千人） 白天 45 350 260 电视 最佳时段 86 880 450 25 430 160 12 180 100 网络媒体 杂志 这家公司希望总广告费用不超过750（千元），同时还要求：（1）受广告影响的妇女超过200万；（2）电视广告的费用不超过450（千元）；（3）电视广告白天至少播出4次，最佳时段至少播出2次；（4）通过网络媒体、杂志做的广告要重复5到8次。
【实验准备】
线性规划是运筹学中产生较早的一个分支，如今在国防科技、经济学、现代工农业、环境工程、生物学等众多学科和领域里起着十分广泛的应用。
线性规划是在一组线性条件的约束之下，求某一个线性函数的最值问题。一般地，线性规划的数学模型为：
min(ormax) z＝c1x1＋c2x2＋…cnxn
s.t. ai1x1＋ai2x2＋…ainxn ≤ ( or ＝ , ≥ ) bi, i＝1 , 2 , … ,m （1） xj≥ 0 , j＝1 , 2 , … , n 用矩阵、向量符号，可以简化线性规划模型的表示：
a11 a12 … a1n x1 b1 c1 A＝ a21 a22 … a2n , x＝ x2 , b＝ b2 , c ＝ c2
… … … … … … … an1 an2 … ann xn bn cn 则线性规划问题可写为：
min(ormax) z＝cx
s.t. Ax≤ (or ＝ , ≥) b （2） xi≥0 , i＝1 , 2 , … , n
这里，z＝cx 称为目标函数，xi为目标函数的决策变量，c为费用系数，是常数向
180
''量；Ax ≤ ( or ＝ , ≥ ) b称为约束条件，A为线性规划的系数矩阵，它是常数矩阵，b为利润（费用）向量，其中s.t.是subject to的缩写，意思是“满足约束条件”。
1．线性规划的标准形式
线性规划问题的标准形式为
min z＝c'x
s.t. Ax＝b （3） x≥0
任何一种线性规划都可以等价地转换为标准形式。 （1）约束条件标准化––––松弛变量法 如果约束条件中有不等式：
ai1x1＋ai2x2＋…ainxn≤bi 或
aj1x1＋aj2x2＋…ajnxn≥bj
通过引入两个非负变量xn+1，xn+2将上述约束条件转换成下面等价形式： ai1x1＋ai2x2＋…ainxn＋xn?1＝bi xn?1≥0 或
aj1x1＋aj2x2＋…ajnxn－xn?2＝bj xn?2≥0 可见约束不等式均可转换为约束等式。 （2）目标函数的标准化
若原问题是求（max）z＝cx，可以转换为求（min）z＝－cx即可。 2．线性规划问题的解
在（3）中满足约束条件Ax＝b，x≥0的向量x＝（x1，x2，…，xn）’称为线性规划问题的可行解，全体可行解组成的集合称为可行域，使目标函数z＝cx达到最小值的可行解称为最优解。
如果矩阵A的某m列所构成的方阵B是满秩的，则B的列向量Pi1，Pi2，…，Pim构成线性规划的一组基，称B为线性规划问题的一个基阵，A的剩余部分组成的子矩阵记为
‘
。x则相应地可以写成x＝（xB，xN），xB的分量与N，则A可以写成A＝（B，N）
'''B的列相对应，称为基变量；xN的分量与N的列相对应，称为非基变量。在约束Ax＝b中令所有非基变量取值为零时，得到的解x＝（Bb，0）称为与B相对应的基解。当基
解所有的分量都取非负时，即满足xB≥0，则称其为基可行解，相应的基阵B的列向量构成可行基。既是最优解，又是基可行解的x称为最优基解。
定理1 如果线性规划（3）有可行解，那么一定有基可行解。
定理2 如果线性规划（3）有最优解，那么一定存在一个基可行解是最优解。
以上定理说明了如果所给的线性规划（3）有最优解，只要从基可行解上寻找最优解就行了。由于基可行解的个数是有限的，只要对所有的基可行解一一检查，就可以在有限次计算后确定最优解或断定该问题无最优解。
‘
?13．求解线性规划的MATLAB命令 （1）MATLAB5.2及以下版本使用命令 求解线性规划模型：
min z＝c'x （4）
181
s.t. Ax≤b
这里A为m×n矩阵，c为n×1列向量，b为m×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表示Ax≤b中前n个约束条件等式约束； 可以用help lp查阅有关该命令的详细信息。 （2）MATLAB5.3以上版本使用命令
MATLAB5.3以上的版本中优化工具箱（Optimization Toolbox）作了相当大的改进，虽然保留了lp命令，但已经使用新的命令linprog取代lp，并且在未来版本中将删除lp命令。
求解的线性规划模型：
min z＝c'x
s.t. Ax≤b （5）
x＝beq Aeq·
lb≤x≤up
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．引例问题的分析与模型的建立
首先，确定决策变量，要求如何安排白天电视、最佳时段电视、网络媒体、杂志广告的次数，用符号表示，分别设定为x1，x2，x3，x4；
其次，确定所有的约束条件，广告总费用不超过750（千元），则有
45x1＋86x2＋25x3＋12x4≤750 受广告影响的女顾客数不少于200万，则有
260x1＋450x2＋160x3＋100x4≥2000
电视广告费用不超过450（千元），且白天至少播4次，最佳时段至少播出2次，则有 45x1＋86x2≤450 ， x1≥4 ， x2≥2 由于网络媒体和杂志广告要重复5到8次，则有 5≤x3≤8 ， 5≤x4≤8
182