運籌學復習題.doc

10級信管專業(yè)運籌學復習題線性規(guī)劃一、填空題1. 線性規(guī)劃模型包括 決策變量 、目標函數(shù) 、約束條件 三個要素。2線性規(guī)劃問題的標準形式中，決策變量取 非負 ，線性約束條件取 等式，所有線性約束等式右邊的常數(shù)必須 非負 ，并且目標函數(shù)求 最大 _。3線性規(guī)劃問題是求一個 線性目標函數(shù) 在一組 線性約束條件 下的最值問題。4線性規(guī)劃問題的可行解是指滿足 所有約束條件_ 的解。5在線性規(guī)劃問題中，基本可行解的非零分量所對應的列向量 線性無關 。6若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的 頂點_ 達到。7圖解法只適用于含有 兩個 _ 決策變量的線性規(guī)劃問題。8求解線性規(guī)劃問題可能的結果有 唯一最優(yōu)解，無窮多最優(yōu)解，無界解，無可行解 。9在用圖解法求解線性規(guī)劃問題時，如果取得最值的等值線與可行域的一段邊界重合，則 最優(yōu)解不唯一 。10、線性規(guī)劃的代數(shù)解法是運用代數(shù)消元法的原理實現(xiàn) 基可行解 的轉換，以尋求最優(yōu)解。11、對偶問題的對偶問題為 原問題 。12、在一對對偶問題中，原問題的約束條件的右端常數(shù)是對偶問題的目標函數(shù)系數(shù)。13、在大M法中，M表示充分大的正數(shù)。14、如果原問題的某個變量無約束，則對偶問題中對應的約束條件應為等式。15、在現(xiàn)性規(guī)劃問題的基本解中，所有的非基變量等于 0 。16、 最大化的線性規(guī)劃問題為無界解時，則對偶問題 無可行解_ 。17、在運輸問題的表上作業(yè)中，位勢方程是由 基變量xij 確定。18、在運輸問題的表上作業(yè)中，非基變量xij的檢驗數(shù)ij= Ui + Vj - Cij 。二 單選題1. 線性規(guī)劃問題是針對 （ D ）求極值問題.A.約束 B.決策變量 C. 秩 D.目標函數(shù)2. 若某個線性約束右端的常數(shù)bk0, 化為標準形式時原不等式 （ D ） A. 不變 B.左端乘1 C .右端乘1 D. 兩邊乘1 3. 如果線性規(guī)劃問題有可行解，那么該解必須滿足 （ A ） A.所有約束條件 B.變量取值非負 C.所有等式要求 D.所有不等式要求4. 如果一個線性規(guī)劃問題有n個變量，m個約束方程(mn)，系數(shù)矩陣的秩為m，則基本解的個數(shù)最多為 （ C ） 。Am個 Bn個 C 個 D 個5、下列哪些不是運籌學的研究范圍（ D ）A 質量控制 B 動態(tài)規(guī)劃 C 排隊論 D 系統(tǒng)設計6、對于線性規(guī)劃問題，下列說法正確的是（ D ）A 線性規(guī)劃問題可能沒有可行解 B 在圖解法上，線性規(guī)劃問題的可行解區(qū)域都是“凸”區(qū)域C 線性規(guī)劃問題如有最優(yōu)解，則最優(yōu)解可在可行解區(qū)域頂點上到達 D 上述說法都正確7、在求解運輸問題的過程中運用到下列哪些方法（ D ）A 西北角法 B 位勢法 C 閉回路法 D 以上都是8、使用人工變量法求解極大化線性規(guī)劃問題時，當所有的檢驗數(shù)在基變量中仍含有非零的人工變量，表明該線性規(guī)劃問題 （ D ） A有唯一的最優(yōu)解 B有無窮多最優(yōu)解 C為無界解 D無可行解9、若線性規(guī)劃最優(yōu)解某個變量的值不等于零，則將對偶問題最優(yōu)解代入該變量對應的對偶約束條件后，這一約束條件必然為 （B ） A 不等式， B 等式， C 小于零， D 大于零 10、滿足線性規(guī)劃問題全部約束條件的解稱為（C） A 最優(yōu)解 B 基本解 C 可行解 D 多重解 11、 用單純形法的代數(shù)形式求解最大化線性規(guī)劃問題中，若某非基變量檢驗數(shù)為零，而其他非基變量檢驗數(shù)全部0，則說明本問題 （ B ） 。A有惟一最優(yōu)解 B有多重最優(yōu)解 C無界 D無解12、 線性規(guī)劃問題有可行解且凸多邊形無界，這時 （ C ） A.沒有無界解 B. 沒有可行解 C.可能有無界解 D.有有限最優(yōu)解13、線性規(guī)劃模型不包括下列 （ D ） 要素。A目標函數(shù) B約束條件 C決策變量 D狀態(tài)變量動態(tài)規(guī)劃：一、填空題1、實際問題中,決策變量的取值通常限制某一允許范圍內,稱這個范圍為允許決策集合2、動態(tài)規(guī)劃,是由美國數(shù)學家伯爾曼(R.Bellman)等人1951年開始研究,提出了解決這類多階段決策問題的，其核心理論是 最優(yōu)化原理 。3、最優(yōu)策略是由一系列的部分決策所構成,即一個整過程的最優(yōu)策略包含了 所有 階段的決策。4、動態(tài)規(guī)劃方法的特點就是把所給的最優(yōu)化問題,根據(jù)實際情況,適當?shù)貏澐譃槿舾蓚€互相聯(lián)系的 階段 。5、描述過程狀態(tài)的變量稱為 狀態(tài)變量 。6、一個階段的狀態(tài)僅由它 上一階段 的狀態(tài)和 決策 來完全確定,而與更前面的狀態(tài) 無關，這種特性被稱為 無后效性 。7、指標函數(shù)是用來衡量 程實現(xiàn)的優(yōu)劣 的一種數(shù)量指標 。8、構成動態(tài)規(guī)劃模型的條件能夠描繪受控過程的演變特征， 滿足無后效性 ， 可知性(可測性),9、寫出狀態(tài)轉移方程應該形如 sk=Tk(sk-1,uk) 10、動態(tài)規(guī)劃是解決 多階段決策過程 最優(yōu)化問題的一種方法。11、用動態(tài)規(guī)劃可以解決管理中的 最短路問題、裝載問題、庫存問題、資源分配問題、生產過程最優(yōu)化問題 。12、根據(jù)時間參量是離散的變量還是連續(xù)的變量，可以把動態(tài)規(guī)劃的模型分為 離散決策過程 和 連續(xù)決策過程 。13、用動態(tài)規(guī)劃求解問題時，一般是根據(jù) 時間 和 空間 的自然特征去劃分階段。14、由所有各階段的決策組成的決策序列稱為 策略 。15、指標函數(shù) 是衡量全過程策略或k子過程策略優(yōu)劣的數(shù)量指標。16、最優(yōu)策略的任一子策略都是 最優(yōu)的 。17、對于狀態(tài)變量和決策變量只取連續(xù)值，過程的演變方式為確定性時，這種動態(tài)規(guī)劃問題稱為 連續(xù)確定性動態(tài)規(guī)劃問題 。18、隨機型的動態(tài)規(guī)劃問題是指狀態(tài)的 轉移律 是不確定的。 19、在隨機型的動態(tài)規(guī)劃問題中，由于下一階段到達的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的 期望效益值 進行優(yōu)化。20、在用逆向解法求動態(tài)規(guī)劃時，fk(sk)的含義是：_。二、選擇題1.某人要從上海搭乘汽車去重慶，他希望選擇一條線路，經過轉乘，使得車費最少。此問題可以轉化為（B）A.最大流量問題求解 B.最短路問題求解C.最小樹問題求解 D.最小費用最大流問題求解2.動態(tài)規(guī)劃中的指標函數(shù)是一種（A）A數(shù)量關系 B.大小關系 C.方向關系 D.目的關系3.最短路問題中在圖上直接作業(yè)的方法叫做（C）A圖解法 B序解法 C標號法 D表格法4.狀態(tài)轉移方程是用于解決（D）的。A運輸問題 B指派問題 C資源分配問題 D動態(tài)規(guī)劃問題5、根據(jù)決策過程的演變是確定性的還是隨機性的，動態(tài)規(guī)劃又可分為確定性的決策過程和（B）的決策過程。 .離散 B .隨機性 C .連續(xù) D .連續(xù)確定性6、利用動態(tài)規(guī)劃的方法解最短路問題，我們不僅求出了全過程的最短路，還求出了（ C ）到終點的最短路。 A .起始點 B .中間階段點 C.任一點 D .終點7、已知第n+1階段的狀態(tài)是由第n階段的狀態(tài)和決策決定，用方