1、實驗八最佳廣告編排方案【實驗目的】1了解線性規劃問題及其可行解、基本解、最優解的概念。2通過對實際應用問題的分析，初步掌握建立線性規劃模型的基本步驟和方法。3學習掌握MATLAB軟件求解有關線性規劃的命令。【實驗內容】一家廣告公司想在電視、廣播上做公司的宣傳廣告，其目的是爭取盡可能多地招徠顧客。下表是公司進行市場調研的結果：電視網絡媒體雜志白天最佳時段每次做廣告費用（千元）45862512受每次廣告影響的顧客數（千人）350880430180受每次廣告影響的女顧客數（千人）260450160100這家公司希望總廣告費用不超過750（千元），同時還要求：（1）受廣告影響的婦女超過200萬；（2）

2、電視廣告的費用不超過450（千元）；（3）電視廣告白天至少播出4次，最佳時段至少播出2次；（4）通過網絡媒體、雜志做的廣告要重復5到8次。【實驗準備】線性規劃是運籌學中產生較早的一個分支，如今在國防科技、經濟學、現代工農業、環境工程、生物學等眾多學科和領域里起著十分廣泛的應用。線性規劃是在一組線性條件的約束之下，求某一個線性函數的最值問題。一般地，線性規劃的數學模型為： () ( or , ) , 1 , 2 , , （1） 0 , 1 , 2 , , 用矩陣、向量符號，可以簡化線性規劃模型的表示： , , , 則線性規劃問題可寫為：() ( , ) （2） , 1 , 2 , , 這里， 稱

3、為目標函數，為目標函數的決策變量，為費用系數，是常數向量； ( or , ) 稱為約束條件，為線性規劃的系數矩陣，它是常數矩陣，為利潤（費用）向量，其中是subject to的縮寫，意思是“滿足約束條件”。1線性規劃的標準形式線性規劃問題的標準形式為 （3） 任何一種線性規劃都可以等價地轉換為標準形式。（1）約束條件標準化松弛變量法如果約束條件中有不等式： 或 通過引入兩個非負變量xn+1，xn+2將上述約束條件轉換成下面等價形式： 或 可見約束不等式均可轉換為約束等式。（2）目標函數的標準化若原問題是求（），可以轉換為求（）即可。2線性規劃問題的解在（3）中滿足約束條件，的向量（，）稱為線性

4、規劃問題的可行解，全體可行解組成的集合稱為可行域，使目標函數達到最小值的可行解稱為最優解。如果矩陣的某列所構成的方陣是滿秩的，則的列向量，構成線性規劃的一組基，稱為線性規劃問題的一個基陣，的剩余部分組成的子矩陣記為，則可以寫成（，）。則相應地可以寫成（，），的分量與的列相對應，稱為基變量；的分量與的列相對應，稱為非基變量。在約束中令所有非基變量取值為零時，得到的解（，0）稱為與相對應的基解。當基解所有的分量都取非負時，即滿足，則稱其為基可行解，相應的基陣的列向量構成可行基。既是最優解，又是基可行解的稱為最優基解。定理1如果線性規劃（3）有可行解，那么一定有基可行解。定理2如果線性規劃（3）有最

5、優解，那么一定存在一個基可行解是最優解。以上定理說明了如果所給的線性規劃（3）有最優解，只要從基可行解上尋找最優解就行了。由于基可行解的個數是有限的，只要對所有的基可行解一一檢查，就可以在有限次計算后確定最優解或斷定該問題無最優解。3求解線性規劃的MATLAB命令（1）MATLAB5.2及以下版本使用命令求解線性規劃模型： （4） 這里為×矩陣，為×1列向量，為×1列向量。x = lp( c , A , b )求解線性規劃模型（4）；x = lp( c , A , b , vlb , vub )指定決策變量的上下界vlbxvub；x = lp( c , A , b

6、 , 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 ,

7、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；可以

8、在MATLAB幫助文件中查閱有關該命令的詳細信息。【實驗方法與步驟】建立線性規劃模型有三個基本步驟：第一步，找出待定的未知變量（決策變量），并用代數符號來表示它們；第二步，找出問題的所有限制或約束條件，寫出未知變量的線性方程或線性不等式；第三步，找到模型的目標，寫成決策變量的線性函數，以便求其最大或最小值。1引例問題的分析與模型的建立首先，確定決策變量，要求如何安排白天電視、最佳時段電視、網絡媒體、雜志廣告的次數，用符號表示，分別設定為，；其次，確定所有的約束條件，廣告總費用不超過750（千元），則有45862512750受廣告影響的女顧客數不少于200萬，則有2604501601002000

9、電視廣告費用不超過450（千元），且白天至少播4次，最佳時段至少播出2次，則有4586450 ，4 ，2由于網絡媒體和雜志廣告要重復5到8次，則有58 ，58最后，確定問題的目標函數，由題意知確定廣告編排方案，使得受各種廣告影響的潛在顧客總數：350880430180最多。故該問題完整的線性規劃模型如下：35088043018045862512750 2604501601002000458600450000800084 ，2，5，52MATLAB計算機求解用MATLAB求解的程序代碼：>> c=-350 -880 -430 -180;%取將目標函數標準化>> a=45

10、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, )%無等式約束條件和的上界，取表缺省Optimization terminated successfully.x = 4.0000 3.1395 8.00008.0000Fval =-9.0428e+003【結果分析】引例問題的目標函數是求受廣告影響的最多顧客人數，而MATLAB命令

11、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個居民區的距離分別為4k