運(yùn)籌學(xué)知識(shí)點(diǎn)要求匯總

朽木易折，金石可鏤。千里之行，始于足下。第頁(yè)/共頁(yè)運(yùn)籌學(xué)知識(shí)點(diǎn)要求第一部分結(jié)論1、運(yùn)籌學(xué)的特點(diǎn)（1）以最優(yōu)性或合理性為核心。（2）以數(shù)量化、模型化為基本主意。（3）具有強(qiáng)烈的系統(tǒng)性、交錯(cuò)性特征。（4）以計(jì)算機(jī)為重要的技術(shù)支持。2、運(yùn)籌學(xué)模型求解主意：知道迭代算法的原理步驟。3、運(yùn)籌學(xué)模型（1）運(yùn)籌學(xué)模型：使用較多的是符號(hào)或數(shù)學(xué)模型，大多數(shù)為優(yōu)化模型。（2）模型的普通結(jié)構(gòu)（3）模型的三大要素決策變量、目標(biāo)函數(shù)及優(yōu)化方向、約束條件。（4）了解模型的分類4、建立優(yōu)化模型解決實(shí)際問(wèn)題（1）要求能對(duì)較容易的實(shí)際問(wèn)題建立優(yōu)化模型。主要涉及：普通線性計(jì)劃模型，整數(shù)（異常是0－1計(jì)劃）計(jì)劃模型。5、了解運(yùn)籌學(xué)運(yùn)用領(lǐng)域。第二部分線性計(jì)劃1、線性計(jì)劃模型的幾種表示形式及特點(diǎn)2、線性計(jì)劃模型的標(biāo)準(zhǔn)形式及如何標(biāo)準(zhǔn)化3、線性計(jì)劃問(wèn)題各種解的概念及關(guān)系（關(guān)系圖示）（可行解、非可行解、基本解、基本可行解、最優(yōu)解，基本可行解的個(gè)數(shù)小于等于）4、線性問(wèn)題有關(guān)解的基本定理（主要是概念理解）（1）不一定都有最優(yōu)解（2）若有，一定會(huì)在基本可行解上達(dá)到（3）基本可行解的個(gè)數(shù)有限小于等于（4）并非所有最優(yōu)解都是基本可行解（5）了解凸集與凸組合的概念，理解兩個(gè)最優(yōu)解的凸組合都是最優(yōu)解。（6）可行解為基本可行解的充要條件5、線性計(jì)劃單純形法（1）制作初始單純表（注重非基變量檢驗(yàn)系數(shù)的求法，異常注重求有待定系數(shù)時(shí)的檢驗(yàn)系數(shù)）（2）各種解的判別條件，對(duì)于最大化目標(biāo)函數(shù)問(wèn)題，包括：唯一最優(yōu)解：有最優(yōu)解無(wú)窮多最優(yōu)解存在一個(gè)k有：（或稱之為線性計(jì)劃問(wèn)題存在可擇最優(yōu)解）無(wú)界解，存在k有：（3）線性計(jì)劃問(wèn)題求解結(jié)果中解的情況有最優(yōu)解（唯一最優(yōu)解、無(wú)窮多最優(yōu)解），無(wú)界解，無(wú)可行解（4）基變換中入基變量的決定A、入基變量的須要條件（）B、最速升高準(zhǔn)則的理解，不是使目標(biāo)函數(shù)改進(jìn)最大，而是使目標(biāo)函數(shù)改進(jìn)速度最大。（5）最小比值決定出基變量的目的：保證基變換后新的基本解是可行的。（6）會(huì)單純形迭代計(jì)算求解線性計(jì)劃問(wèn)題6、什么是線性計(jì)劃問(wèn)題退化情況？會(huì)引起什么樣后果？7、大M法（罰函數(shù)法）：（1）輔助問(wèn)題目標(biāo)函數(shù)的構(gòu)造，（2）輔助問(wèn)題解與問(wèn)題解的關(guān)系（3）能用大M法（罰函數(shù)法）求解線性計(jì)劃問(wèn)題。8、兩階段法：（1）第一階段的目的判斷原問(wèn)題是否有可行解，當(dāng)目標(biāo)函數(shù)值為0時(shí)，第一階段問(wèn)題的人工基變量已退出基變量，其最優(yōu)即為原問(wèn)題的一個(gè)基本可行解，在計(jì)算表中為典型形式。若第一階段最優(yōu)解值>0說(shuō)明原問(wèn)題無(wú)可行解。（2）第一階段的計(jì)劃模型的目標(biāo)函數(shù)（不要求利用兩階段法殘破求解線性計(jì)劃問(wèn)題）本部分的典型計(jì)算題;（1）利用單純形法殘破求解線性計(jì)劃問(wèn)題（2）利用大M法殘破求解線性計(jì)劃問(wèn)題（3）給定單純形計(jì)算表，其中有部分未知參數(shù)，計(jì)算含參數(shù)的線性計(jì)劃問(wèn)題單純表中各非基變量的檢驗(yàn)系數(shù)，并判斷參數(shù)在什么范圍變化時(shí)有（1）最優(yōu)解（2）唯一最優(yōu)解（3）無(wú)界解第三部分對(duì)偶問(wèn)題、對(duì)偶單純形法與靈巧度分析1、對(duì)偶問(wèn)題與原問(wèn)題的轉(zhuǎn)換關(guān)系（1）約束條件數(shù)為對(duì)方?jīng)Q策變量數(shù)（2）約束條件不等號(hào)與變量正負(fù)號(hào)關(guān)系（3）自由變量與等式約束的對(duì)應(yīng)關(guān)系（4）要能直接寫出對(duì)偶問(wèn)題2、對(duì)偶問(wèn)題的性質(zhì)（幾個(gè)基本概念）（1）對(duì)偶問(wèn)題的對(duì)偶問(wèn)題為原問(wèn)題（2）無(wú)界性（可按照一個(gè)問(wèn)題有無(wú)界解——>另一問(wèn)題無(wú)可行解）（4）對(duì)偶定理：原問(wèn)題與對(duì)偶問(wèn)題，若一個(gè)問(wèn)題有最優(yōu)解，則另一個(gè)問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。應(yīng)用：用于判斷某個(gè)問(wèn)題無(wú)最優(yōu)解，（見書上P75題3.7）3、互補(bǔ)松馳定理及應(yīng)用（1）定理內(nèi)容（2）應(yīng)用之一：已知一個(gè)問(wèn)題的最優(yōu)解，不用單純形法，用解代數(shù)方程的主意，求對(duì)偶問(wèn)題（或另一對(duì)應(yīng)問(wèn)題）的最優(yōu)解。（見P74練習(xí)題3.3）（3）經(jīng)濟(jì)意義解釋4、影子價(jià)格概念及經(jīng)濟(jì)意義5、對(duì)偶單純形法（求解異常線性計(jì)劃問(wèn)題）（1）適用條件（2）會(huì)計(jì)算（3）在最優(yōu)單純形表下增強(qiáng)一個(gè)約束條件，如何轉(zhuǎn)化成能用對(duì)偶單純形法求解的單純形表形式，并用對(duì)偶單純形法求解。6、關(guān)于靈巧度分析計(jì)算要求（1）計(jì)算cj（包括基變量系數(shù)或非基變量系數(shù)）的變化范圍，使最優(yōu)基不改變（2）給定cj從原值變化為新值時(shí)，判斷最優(yōu)基是否改變，若改變，可繼續(xù)用單純形法，在原最優(yōu)解表的基礎(chǔ)上求新的最優(yōu)解（3）計(jì)算bi（約束條件右端項(xiàng)）的變化范圍，使最優(yōu)基不改變（4）詳細(xì)給定某bi從原值變化到新值時(shí)，判斷最優(yōu)基是否改變，若改變，可將換最優(yōu)解表中對(duì)應(yīng)b列數(shù)據(jù)，并利用對(duì)偶單純形法求解（注重B的逆矩陣可直接從單純形中看出）（5）增強(qiáng)一個(gè)約束條件，如何判斷最優(yōu)基是否改變，若改變，如何在原最優(yōu)解表下求新的最優(yōu)解?？蓪⒃顑?yōu)解代入新約束，若滿意，則不改變，否則，最優(yōu)基將改變。改變時(shí)，可將新增約束標(biāo)準(zhǔn)化，在原最優(yōu)解表中加一行與一列，消去該行中原基變量，該行bi值一定是一個(gè)負(fù)數(shù)，可利用對(duì)偶單純形法求解。上述要求內(nèi)容可參看PPT相關(guān)內(nèi)容與例子。第四部分運(yùn)輸問(wèn)題1、一些基本概念（1）運(yùn)輸問(wèn)題一定有最優(yōu)解（無(wú)論是平衡還是非平衡運(yùn)輸問(wèn)題，但線性計(jì)劃問(wèn)題則不一定）（2）分類：平衡，非平衡：產(chǎn)大于銷與銷大于產(chǎn)。（3）表上作業(yè)法決定初始調(diào)運(yùn)計(jì)劃主意三種：西北角法、最小元素法、伏格爾法（普通情況下，此法與最優(yōu)計(jì)劃較臨近）（4）表上作業(yè)法所決定的基變量（數(shù)字格）的個(gè)數(shù)＝m+n-1（5）退化情況及處理主意2、控制平衡運(yùn)輸問(wèn)題表上作業(yè)求解法的計(jì)算（最小元素+位勢(shì)法）3、如何將不平衡運(yùn)輸問(wèn)題轉(zhuǎn)化為平衡運(yùn)輸問(wèn)題注重：（1）對(duì)于產(chǎn)大于銷時(shí)，某產(chǎn)地產(chǎn)品必須運(yùn)出多時(shí)，如何轉(zhuǎn)換（只轉(zhuǎn)換不求解）（2）產(chǎn)大于銷時(shí)，若給出各產(chǎn)地產(chǎn)品就地存貯時(shí)的單位存貯費(fèi)用，如何轉(zhuǎn)化為平衡運(yùn)輸問(wèn)題，并要求能求解此類問(wèn)題（依然用表上作業(yè)法：即用最小元素求初始調(diào)運(yùn)計(jì)劃，用位勢(shì)法求檢驗(yàn)系數(shù)，用閉合回路法調(diào)節(jié)調(diào)運(yùn)計(jì)劃）（3）銷大于產(chǎn)時(shí)，某地需求必須得到滿意時(shí)如何轉(zhuǎn)換（只轉(zhuǎn)換不求解）（4）需求有上下限時(shí)非平衡運(yùn)輸問(wèn)題如何轉(zhuǎn)化為平衡運(yùn)輸問(wèn)題（只轉(zhuǎn)換不求解）4、對(duì)于在求初始調(diào)運(yùn)計(jì)劃時(shí)，產(chǎn)生的退化情況如何處理：在同時(shí)劃去的行列中任選一個(gè)空格填上運(yùn)量0即可。第五部分整數(shù)計(jì)劃與指派問(wèn)題1、基本概念（1）整數(shù)計(jì)劃問(wèn)題的定義及分類（2）求解主意的特牲A、舍位取整——不能用B、窮舉法——無(wú)效C、普通有效，主意的思路——增強(qiáng)約束，隱去若干非整數(shù)解，求解陪同問(wèn)題2、分枝定界法要求控制一些相關(guān)概念術(shù)求解原理步驟，不要求詳細(xì)求解。（1）分枝約束條件的增強(qiáng)，如xi=bi非整數(shù)，可分離增強(qiáng)約束A、xi>=[bi]+1B、xi<=[bi]將上個(gè)計(jì)劃問(wèn)題分為兩個(gè)計(jì)劃問(wèn)題（即兩枝）（2）如何決定上、下界（3）在分枝定界過(guò)程中，上下界的變化邏輯：上界不斷減小，下界不斷增強(qiáng)。（4）在該主意中，某分解結(jié)果浮上什么情況時(shí)，需要舍去該分枝（即舉行剪枝）A、無(wú)可行解B、最優(yōu)解小于下界C、該枝最優(yōu)解已是整數(shù)解3、割平面主意（1）控制如何利用陪同問(wèn)題（注：將整數(shù)計(jì)劃問(wèn)題的整數(shù)約束條件去掉，從而得陪同計(jì)劃問(wèn)題的過(guò)程有的書又稱之為松馳過(guò)程。對(duì)應(yīng)陪同計(jì)劃問(wèn)題被稱之為松馳問(wèn)題）最優(yōu)單純形表中取非整數(shù)約束行系數(shù)，構(gòu)造一個(gè)割平面約束不等式（或稱為割平面方程）（2）增強(qiáng)割平面約束后，如何利用對(duì)偶單純形法求最優(yōu)解。4、如何利用0－1決策變量xii=1,2,…,n表示項(xiàng)目挑選中一些異常約束：如n個(gè)項(xiàng)目中，最多挑選8個(gè)，最少挑選3個(gè)。項(xiàng)目3與項(xiàng)目5互斥。項(xiàng)目6的挑選以項(xiàng)目2的挑選為前提條件等。5、指派問(wèn)題的匈牙利算法計(jì)算題（要會(huì)計(jì)算）（1）該算法適用情況A、目標(biāo)函數(shù)為最小化情況（否則將轉(zhuǎn)換成最小化問(wèn)題）B、效率矩陣為元素均大于等于0的方陣（2）要會(huì)計(jì)算（3）對(duì)最大化