《運籌學》期末復習及答案運籌學是一門應用數(shù)學學科，旨在通過建立數(shù)學模型、運用優(yōu)化方法來解決實際生活中的復雜決策問題。以下為你呈現(xiàn)運籌學期末復習的詳細內(nèi)容及答案。線性規(guī)劃部分基本概念線性規(guī)劃是運籌學中研究較早、發(fā)展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數(shù)學方法。線性規(guī)劃問題通常由目標函數(shù)和約束條件組成，目標函數(shù)是決策者希望最大化或最小化的線性函數(shù)，約束條件則是對決策變量的一系列線性不等式或等式限制。例：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)甲產(chǎn)品需用A原料2千克、B原料1千克；生產(chǎn)乙產(chǎn)品需用A原料1千克、B原料3千克。每生產(chǎn)一件甲產(chǎn)品可獲利30元，每生產(chǎn)一件乙產(chǎn)品可獲利40元。工廠現(xiàn)有A原料10千克，B原料12千克。問應如何安排生產(chǎn)計劃，才能使工廠獲得最大利潤？設生產(chǎn)甲產(chǎn)品\(x_1\)件，生產(chǎn)乙產(chǎn)品\(x_2\)件。目標函數(shù)：\(Z=30x_1+40x_2\)（求最大值）約束條件：\(\begin{cases}2x_1+x_2\leq10\\x_1+3x_2\leq12\\x_1\geq0,x_2\geq0\end{cases}\)求解方法-單純形法單純形法是求解線性規(guī)劃問題的常用方法。其基本思路是從可行域的一個頂點出發(fā)，通過迭代的方式逐步找到使目標函數(shù)最優(yōu)的頂點。步驟：1.將線性規(guī)劃問題化為標準型。對于上述例子，引入松弛變量\(x_3\)和\(x_4\)，將不等式約束化為等式約束：\(\begin{cases}2x_1+x_2+x_3=10\\x_1+3x_2+x_4=12\\x_1\geq0,x_2\geq0,x_3\geq0,x_4\geq0\end{cases}\)目標函數(shù)變?yōu)閈(Z=30x_1+40x_2+0x_3+0x_4\)2.建立初始單純形表。|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||----|----|----|----|----||2|1|1|0|10||1|3|0|1|12||-30|-40|0|0|0|3.進行迭代計算。選擇進基變量（目標函數(shù)系數(shù)絕對值最大的負系數(shù)對應的變量）和出基變量（根據(jù)最小比值法則確定），不斷更新單純形表，直到所有檢驗數(shù)非負。經(jīng)過計算，得到最優(yōu)解\(x_1=4.8\)，\(x_2=2.4\)，最大利潤\(Z=30\times4.8+40\times2.4=240\)元。對偶理論每一個線性規(guī)劃問題都存在一個與之對偶的線性規(guī)劃問題。原問題和對偶問題在最優(yōu)解和最優(yōu)值方面存在一定的關(guān)系。原問題：\(\maxZ=CX\)\(\begin{cases}AX\leqb\\X\geq0\end{cases}\)對偶問題：\(\minW=Yb\)\(\begin{cases}YA\geqC\\Y\geq0\end{cases}\)對偶問題的經(jīng)濟解釋是影子價格，它反映了資源的邊際價值。運輸問題基本概念運輸問題是一類特殊的線性規(guī)劃問題，主要研究如何將某種物資從若干個產(chǎn)地運往若干個銷地，在滿足各產(chǎn)地供應量和各銷地需求量的前提下，使總運輸費用最小。例：有三個產(chǎn)地\(A_1\)、\(A_2\)、\(A_3\)，產(chǎn)量分別為50噸、60噸、70噸；有四個銷地\(B_1\)、\(B_2\)、\(B_3\)、\(B_4\)，銷量分別為30噸、40噸、50噸、60噸。已知各產(chǎn)地到各銷地的單位運輸費用如下表所示，求總運輸費用最小的運輸方案。||\(B_1\)|\(B_2\)|\(B_3\)|\(B_4\)||----|----|----|----|----||\(A_1\)|3|1|7|4||\(A_2\)|2|6|5|9||\(A_3\)|8|3|3|2|求解方法-表上作業(yè)法1.初始調(diào)運方案的確定-西北角法：從運輸表的左上角（西北角）開始，依次分配物資，直到滿足所有產(chǎn)地的供應量和銷地的需求量。-最小元素法：優(yōu)先選擇單位運輸費用最小的格子進行分配。以最小元素法為例，首先選擇單位運輸費用最小的\(A_1B_2\)，分配40噸；然后依次進行分配，得到初始調(diào)運方案。||\(B_1\)|\(B_2\)|\(B_3\)|\(B_4\)|產(chǎn)量||----|----|----|----|----|----||\(A_1\)|0|40|10|0|50||\(A_2\)|30|0|30|0|60||\(A_3\)|0|0|10|60|70||銷量|30|40|50|60||2.最優(yōu)性檢驗采用閉回路法或位勢法檢驗當前調(diào)運方案是否最優(yōu)。如果存在負的檢驗數(shù)，則需要進行調(diào)整。3.方案調(diào)整根據(jù)閉回路法確定調(diào)整量，對調(diào)運方案進行調(diào)整，直到所有檢驗數(shù)非負，得到最優(yōu)調(diào)運方案。圖與網(wǎng)絡分析圖的基本概念圖是由頂點和邊組成的一種數(shù)學結(jié)構(gòu)，用于表示事物之間的關(guān)系。無向圖中邊沒有方向，有向圖中邊有方向。最小支撐樹問題最小支撐樹是一個連通無向圖中權(quán)值之和最小的樹。常用的求解方法有Prim算法和Kruskal算法。Prim算法：從一個頂點開始，每次選擇與已選頂點集合相連的邊中權(quán)值最小的邊，將對應的頂點加入已選頂點集合，直到包含所有頂點。例：有一個無向圖，頂點集合\(V=\{v_1,v_2,v_3,v_4,v_5\}\)，邊集合\(E\)及邊的權(quán)值如下表所示，求該圖的最小支撐樹。|邊|權(quán)值||----|----||\((v_1,v_2)\)|2||\((v_1,v_3)\)|4||\((v_2,v_3)\)|1||\((v_2,v_4)\)|7||\((v_3,v_4)\)|3||\((v_3,v_5)\)|5||\((v_4,v_5)\)|6|采用Prim算法，從頂點\(v_1\)開始：-第一步：選擇邊\((v_1,v_2)\)，權(quán)值為2。-第二步：在與\(\{v_1,v_2\}\)相連的邊中選擇權(quán)值最小的邊\((v_2,v_3)\)，權(quán)值為1。-第三步：在與\(\{v_1,v_2,v_3\}\)相連的邊中選擇權(quán)值最小的邊\((v_3,v_4)\)，權(quán)值為3。-第四步：在與\(\{v_1,v_2,v_3,v_4\}\)相連的邊中選擇權(quán)值最小的邊\((v_3,v_5)\)，權(quán)值為5。得到最小支撐樹的權(quán)值為\(2+1+3+5=11\)。最短路問題最短路問題是求圖中某一頂點到其他頂點的最短路徑。常用的算法有Dijkstra算法（適用于邊權(quán)非負的情況）和Floyd算法（可處理有負權(quán)邊但無負權(quán)回路的情況）。Dijkstra算法步驟：1.初始化：將起點的距離標記為0，其他頂點的距離標記為無窮大。2.選擇距離起點最近且未確定最短路徑的頂點，更新其鄰接頂點的距離。3.重復步驟2，直到所有頂點的最短路徑都確定。整數(shù)規(guī)劃基本概念整數(shù)規(guī)劃是要求決策變量取整數(shù)值的線性規(guī)劃問題。如果所有決策變量都要求取整數(shù)，則稱為純整數(shù)規(guī)劃；如果部分決策變量要求取整數(shù)，則稱為混合整數(shù)規(guī)劃。例：某公司擬投資兩個項目\(A\)和\(B\)，項目\(A\)需要投資50萬元，預計收益80萬元；項目\(B\)需要投資30萬元，預計收益50萬元。公司現(xiàn)有資金100萬元，問應如何選擇項目，才能使總收益最大？設選擇項目\(A\)為\(x_1\)（\(x_1=0\)或1），選擇項目\(B\)為\(x_2\)（\(x_2=0\)或1）。目標函數(shù)：\(Z=80x_1+50x_2\)（求最大值）約束條件：\(\begin{cases}50x_1+30x_2\leq100\\x_1,x_2\in\{0,1\}\end{cases}\)求解方法-分支定界法：將整數(shù)規(guī)劃問題分解為一系列子問題，通過對每個子問題的求解和界限的確定，逐步縮小搜索范圍，最終找到最優(yōu)整數(shù)解。-割平面法：通過增加線性約束（割平面）來縮小可行域，使得非整數(shù)最優(yōu)解被排除，最終得到整數(shù)最優(yōu)解。對于上述例子，通過枚舉法可得：當\(x_1=1\)，\(x_2=1\)時，\(Z=80+50=130\)萬元；當\(x_1=1\)，\(x_2=0\)時，\(Z=80\)萬元；當\(x_1=0\)，\(x_2=1\)時，\(Z=50\)萬元；當\(x_1=0\)，\(x_2=0\)時，\(Z=0\)萬元。所以最優(yōu)方案是選擇項目\(A\)和項目\(B\)，最大收益為130萬元。排隊論基本概念排隊論是研究排隊系統(tǒng)（又稱隨機服務系統(tǒng)）的數(shù)學理論和方法。排隊系統(tǒng)由顧客、服務臺、排隊規(guī)則等要素組成。排隊模型通常用符號\(X/Y/Z/A/B/C\)表示，其中\(zhòng)(X\)表示顧客到達間隔時間的分布，\(Y\)表示服務時間的分布，\(Z\)表示服務臺的數(shù)量，\(A\)表示系統(tǒng)的容量，\(B\)表示顧客源的數(shù)量，\(C\)表示排隊規(guī)則。常見排隊模型及指標計算-\(M/M/1\)模型：顧客到達間隔時間服從指數(shù)分布，服務時間服從指數(shù)分布，單服務臺。主要指標：-平均到達率\(\lambda\)：單位時間內(nèi)到達的顧客數(shù)。-平均服務率\(\mu\)：單位時間內(nèi)服務完的顧客數(shù)。-系統(tǒng)的利用率\(\rho=\frac{\lambda}{\mu}\)。-系統(tǒng)中顧客的平均數(shù)\(L_s=\frac{\lambda}{\mu-\lambda}\)。-隊列中顧客的平均數(shù)\(L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}\)。-顧客在系統(tǒng)中的平均逗留時間\(W_s=\frac{1}{\mu-\lambda}\)。-顧客在隊列中的平均等待時間\(W_q=\frac{\lambda}{\mu(\mu-\lambda)}\)。例：某銀行有一個服務窗口，顧客到達間隔時間服從指數(shù)分布，平均每小時到達10人；服務時間也服從指數(shù)分布，平均每小時服務15人。求該排隊系統(tǒng)的各項指標。\(\lambda=10\)人/小時，\(\mu=15\)人/小時，\(\rho=\frac{\lambda}{\mu}=\frac{10}{15}=\frac{2}{3}\)\(L_s=\frac{\lambda}{\mu-\lambda}=\frac{10}{15-10}=2\)人\(L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}=\frac{10^2}{15\times(15-10)}=\frac{4}{3}\)人\(W_s=\frac{1}{\mu-\lambda}=\frac{1}{15-10}=0.2\)小時\(W_q=\frac{\lambda}{\mu(\mu-\lambda)}=\frac{10}{15\times(15-10)}=\frac{2}{15}\)小時決策論基本概念決策論是研究在不確定或風險情況下如何進行決策的理論和方法。決策問題通常由決策者、決策方案、自然狀態(tài)和損益值等要素組成。決策準則-樂觀準則：決策者對未來持樂觀態(tài)度，選擇在最好自然狀態(tài)下收益最大的方案。-悲觀準則：決策者對未來持悲觀態(tài)度，選擇在最壞自然狀態(tài)下收益最大的方案。-后悔值準則：先計算每個方案在不同自然狀態(tài)下的后悔值（該自然狀態(tài)下的最大收益與該方案收益之差），然后選擇最大后悔值最小的方案。例：某企業(yè)擬生產(chǎn)一種新產(chǎn)品，有三種生產(chǎn)方案可供選擇：\(A_1\)、\(A_2\)、\(A_3\)。市場需求有三種可能狀態(tài)：暢銷、一般、滯銷，對應的損益值如下表所示。|方案|暢銷|一般|滯銷||----|----|----|----||\(A_1\)|80|50|-20||\(A_2\)|60|40|10||\(A_3\)|30|30|30|采用樂觀準則，選擇方案\(A_1\)（因為在暢銷狀態(tài)下\(A_1\)的收益最大）。采用悲觀準則，選擇方案\(A