最佳廣告編排方案設(shè)計(jì)

1、暨南大學(xué)本科實(shí)驗(yàn)報(bào)告專用紙課程名稱決策支持系統(tǒng)成績(jī)?cè)u(píng)定實(shí)驗(yàn)項(xiàng)目名稱最佳廣告編排方案設(shè)計(jì)指導(dǎo)教師譚滿春學(xué)生姓名李永勝學(xué)號(hào)2009051049學(xué)院信息科學(xué)技術(shù)學(xué)院系數(shù)學(xué)系專業(yè)信息管理與信息系統(tǒng)學(xué)院信息科學(xué)技術(shù)學(xué)院系數(shù)學(xué)系專業(yè)信息與計(jì)算科學(xué)實(shí)驗(yàn)時(shí)間2011 年 10月9日上午10月14日上午溫度C濕度【實(shí)驗(yàn)?zāi)康摹?了解線性規(guī)劃問(wèn)題及其可行解、基本解、最優(yōu)解的概念。2 通過(guò)對(duì)實(shí)際應(yīng)用問(wèn)題的分析，初步掌握建立線性規(guī)劃模型的基本步驟和方法。3.學(xué)習(xí)掌握MATLAB件求解有關(guān)線性規(guī)劃的命令?！緦?shí)驗(yàn)內(nèi)容】一家廣告公司想在電視、廣播上做公司的宣傳廣告，其目的是爭(zhēng)取盡可能多地招徠顧客。F表是公司進(jìn)行市場(chǎng)調(diào)研的結(jié)果

2、:電視網(wǎng)絡(luò)媒體雜志白天最佳時(shí)段每次做廣告費(fèi)用（千兀）45862512受每次廣告影響的顧客數(shù)（千人）350880430180受每次廣告影響的女顧客數(shù)（千人）260450160100這家公司希望總廣告費(fèi)用不超過(guò)750 （千元），同時(shí)還要求：（1）受廣告影響的婦女超過(guò)200萬(wàn)；（2）電視廣告的費(fèi)用不超過(guò) 450 （千元）;（3）電視廣告白天至少播出4次，最佳時(shí)段至少播出2次；（4）通過(guò)網(wǎng)絡(luò)媒體、雜志做的廣告要重復(fù)5到8次。【實(shí)驗(yàn)準(zhǔn)備】線性規(guī)劃是運(yùn)籌學(xué)中產(chǎn)生較早的一個(gè)分支，如今在國(guó)防科技、經(jīng)濟(jì)學(xué)、現(xiàn)代工農(nóng)業(yè)、環(huán)境工程、生物學(xué)等眾多學(xué)科和領(lǐng)域里起著十分廣泛的應(yīng)用。線性規(guī)劃是在一組線性條件的約束之下，求某

3、一個(gè)線性函數(shù)的最值問(wèn)題。一般地，線性規(guī)劃的數(shù)學(xué)模型為：min（ max）= + + + +w（ or = ,> ） ,= 1 , 2 ,，（1）> 0 , = 1 , 2 , ，用矩陣、向量符號(hào)，可以簡(jiǎn)化線性規(guī)劃模型的表示：廠、廠'、 r則線性規(guī)劃問(wèn)題可寫(xiě)為:min （ max）w (=,)(2)> ,=1 , 2 , ，這里，=稱為目標(biāo)函數(shù)，為目標(biāo)函數(shù)的決策變量，為費(fèi)用系數(shù)，是常數(shù)向量；w (or =, > )稱為約束條件，為線性規(guī)劃的系數(shù)矩陣，它是常數(shù)矩陣，為利潤(rùn)(費(fèi)用)向量， 其中是subject to 的縮寫(xiě)，意思是“滿足約束條件” 。1.線性規(guī)劃的標(biāo)準(zhǔn)

4、形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為min =(3)任何一種線性規(guī)劃都可以等價(jià)地轉(zhuǎn)換為標(biāo)準(zhǔn)形式。(1 )約束條件標(biāo)準(zhǔn)化 松弛變量法如果約束條件中有不等式：+ + 或+ + 通過(guò)引入兩個(gè)非負(fù)變量 Xn+1, Xn+2將上述約束條件轉(zhuǎn)換成下面等價(jià)形式：+ + + Xn 卅=Xn 卅 >-或+ + Xnd2 =嚴(yán)Xnd2 >-可見(jiàn)約束不等式均可轉(zhuǎn)換為約束等式。(2) 目標(biāo)函數(shù)的標(biāo)準(zhǔn)化若原問(wèn)題是求(max)=，可以轉(zhuǎn)換為求( min)=即可。2線性規(guī)劃問(wèn)題的解在(3)中滿足約束條件=,的向量=(,)'稱為線性規(guī)劃問(wèn)題的 可行解，全體可行解組成的集合稱為可行域，使目標(biāo)函數(shù)=達(dá)到最小值的可行解

5、稱為最優(yōu)解。如果矩陣的某列所構(gòu)成的方陣是滿秩的，則的列向量，構(gòu)成線性規(guī)劃的一組基，稱為線性規(guī)劃問(wèn)題的一個(gè) 基陣，的剩余部分組成的子矩陣記為，則可以寫(xiě)成=(,)。則相應(yīng)地可以寫(xiě)成=(,)，的分量與的列相對(duì)應(yīng)，稱為 基變量；的分量與的列相對(duì)應(yīng)，稱為 非基 變量。在約束=中令所有非基變量取值為零時(shí)，得到的解=(B Jb , 0) 稱為與相對(duì)應(yīng)的基解。當(dāng)基解所有的分量都取非負(fù)時(shí)，即滿足，則稱其為基可行解，相應(yīng)的基陣的列向量構(gòu)成可行基。既是最優(yōu)解，又是基可行解的稱為最優(yōu)基解。定理1如果線性規(guī)劃(3)有可行解，那么一定有基可行解。定理2如果線性規(guī)劃(3)有最優(yōu)解，那么一定存在一個(gè)基可行解是最優(yōu)解。以上定理

6、說(shuō)明了如果所給的線性規(guī)劃(3 )有最優(yōu)解，只要從基可行解上尋找最優(yōu)解就行了。由于基可行解的個(gè)數(shù)是有限的，只要對(duì)所有的基可行解一一檢查，就可以在有限次計(jì)算后確定最優(yōu)解或斷定該問(wèn)題無(wú)最優(yōu)解。3求解線性規(guī)劃的 MATLAB命令(1) MATLAB5.2及以下版本使用命令求解線性規(guī)劃模型：min =(4)w這里為X矩陣，為X 1列向量，為X 1列向量。求解線性規(guī)劃模型(4);指定決策變量的上下界vlb < x< vub;指定迭代的初始值x0 ;n表示w中前n個(gè)約束條件等式約x = lp(c , A , b )x = lp(c , A , b,vlb , vub )x = lp(c , A

7、, b,vlb , vub , x0)x = lp(c , A , b,vlb , vub , x0, n )束；可以用help lp 查閱有關(guān)該命令的詳細(xì)信息。(2) MATLAB5.3以上版本使用命令MATLAB5.3以上的版本中優(yōu)化工具箱( Optimization Toolbox )作了相當(dāng)大的改進(jìn)，雖 然保留了 lp命令，但已經(jīng)使用新的命令linprog取代lp，并且在未來(lái)版本中將刪除lp命令。求解的線性規(guī)劃模型：min =w(5)Aeq = beqwwx = linprog( c , A , b )求解線性規(guī)劃模型(4);x = linprog( c , A , b , Aeq ,

8、 beq )求解模型(5)，問(wèn)題中沒(méi)有指定 x的上下界；x = linprog( c , A , b , Aeq , beq , lb , ub )求解線性規(guī)劃模型(5);x = lin prog( c , A , b , Aeq , beq , lb , ub , x0 )指定迭代的初始值x0;如果模型(5)中不包含不等式約束條件，可用代替 A和b表示缺?。蝗绻麤](méi) 有等式約束條件，可用代替 Aeq和beq表示缺??；如果某個(gè) 為無(wú)下界或上界，可 以設(shè)定 lb (i )= inf 或 ub (i ) = inf ；用x , Fval 代替上述各命令行中左邊的x,則可得到在最優(yōu)解 x處的函數(shù)值Fv

9、al ;可以在MATLAB幫助文件中查閱有關(guān)該命令的詳細(xì)信息?！緦?shí)驗(yàn)方法與步驟】建立線性規(guī)劃模型有三個(gè)基本步驟：第一步，找出待定的未知變量(決策變量)，并用代數(shù)符號(hào)來(lái)表示它們；第二步，找出問(wèn)題的所有限制或約束條件，寫(xiě)出未知變量的線性方程或線性不等式； 第三步，找到模型的目標(biāo)，寫(xiě)成決策變量的線性函數(shù)，以便求其最大或最小值。1 引例問(wèn)題的分析與模型的建立首先，確定決策變量，要求如何安排白天電視、最佳時(shí)段電視、網(wǎng)絡(luò)媒體、雜志廣告的次數(shù)，用符號(hào)表示，分別設(shè)定為，；其次，確定所有的約束條件，廣告總費(fèi)用不超過(guò)750 (千元)，則有45 + 86+ 25 + 12W 750受廣告影響的女顧客數(shù)不少于200萬(wàn)

10、，則有260 + 450+ 160+ 100 > 2000電視廣告費(fèi)用不超過(guò) 450 (千元)，且白天至少播4次，最佳時(shí)段至少播出 2次，則有45 + 86W 450 ,> 4 ,> 2由于網(wǎng)絡(luò)媒體和雜志廣告要重復(fù)5到8次，則有5ww 8 ,5 ww 8最后，確定問(wèn)題的目標(biāo)函數(shù)，由題意知確定廣告編排方案，使得受各種廣告影響的潛在 顧客總數(shù)：=350 + 880 + 430 + 180最多。故該問(wèn)題完整的線性規(guī)劃模型如下：max = 350 + 880+ 430 + 18045+ 86 + 25+ 12w 750260 450 160- 100 W 200045 + 86 +

11、0 + 0< 4500 + 0 + 0< 80 + 0 + 0+W 8>4 ,> 2,> 5,> 52. MATLAB十算機(jī)求解用MATLAB解的程序代碼：>> c=-350 -880 -430 -180;%取將目標(biāo)函數(shù)標(biāo)準(zhǔn)化>> a=45 86 25 12;-260 -450 -160 -100;45 86 0 0;0 0 1 0;0 0 0 1;>> b=750;-2000;450;8;8;>> lb=4;2;5;5;>> x, Fval=linprog(c,a,b,lb,)%無(wú)等式約束條件和的上界，取表缺省Optimization terminated successfully.x =4.00003.13958.00008.0000Fval =-9.0428e+003【結(jié)果分析】引例問(wèn)題的目標(biāo)函數(shù)是求受廣