考研題庫 運(yùn)籌學(xué)教材編寫組《運(yùn)籌學(xué)》（第3版）配套題庫（真題 課后題 章節(jié)題 模擬題）

第二部分課后習(xí)題第1章線性規(guī)劃與單純形法第2章對(duì)偶理論與靈敏度分析第3章運(yùn)輸問題第4章目標(biāo)規(guī)劃第5章整數(shù)規(guī)劃第6章無約束問題第7章約束極值問題第8章動(dòng)態(tài)規(guī)劃的基本方法第9章動(dòng)態(tài)規(guī)劃應(yīng)用舉例第10章圖與網(wǎng)絡(luò)優(yōu)化第11章網(wǎng)絡(luò)計(jì)劃第12章排隊(duì)論第13章存儲(chǔ)論第14章對(duì)策論基礎(chǔ)第15章單目標(biāo)決策第16章多目標(biāo)決策第17章啟發(fā)式方法第三部分章節(jié)題庫第1章線性規(guī)劃與單純形法第2章對(duì)偶理論與靈敏度分析第3章運(yùn)輸問題第4章目標(biāo)規(guī)劃第5章整數(shù)規(guī)劃第6章無約束問題第7章約束極值問題第8章動(dòng)態(tài)規(guī)劃的基本方法第9章動(dòng)態(tài)規(guī)劃應(yīng)用舉例第10章圖與網(wǎng)絡(luò)優(yōu)化第11章網(wǎng)絡(luò)計(jì)劃第12章排隊(duì)論第13章存儲(chǔ)論第14章對(duì)策論基礎(chǔ)第15章單目標(biāo)決策第16章多目標(biāo)決策第17章啟發(fā)式方法第四部分模擬試題運(yùn)籌學(xué)教材編寫組《運(yùn)籌學(xué)》(第3版)模擬試題及詳解(二)第一部分名?？佳姓骖}2011年南開大學(xué)897運(yùn)籌學(xué)(商學(xué)院)考研真題2011年南開大學(xué)897運(yùn)籌學(xué)(商學(xué)院)考研真題及詳解一、某廠生產(chǎn)A、B兩種產(chǎn)品，需經(jīng)過金工和裝配兩個(gè)車間加工，有關(guān)數(shù)據(jù)如表1所示.產(chǎn)品B無論生產(chǎn)批量大小，每件產(chǎn)品生產(chǎn)成本總為400元。產(chǎn)品A的生產(chǎn)成本分段線性：第1件至第70件，每件成本為200元；從第71件開始，每件成本為190元。試建立線性整數(shù)規(guī)劃模型，使該廠生產(chǎn)產(chǎn)品的總利潤最大。(本題共15分)則建立線性整數(shù)規(guī)劃模型如下：其對(duì)偶問題的最優(yōu)解為Y*=(yi,y?,y3,…,ym)。另有一線性規(guī)劃(p2):證：問題1的對(duì)偶問題為：問題2的對(duì)偶問題為：易見，問題1的對(duì)偶問題與問題2的對(duì)偶問題具有相同的約束條件，從而，問題1的對(duì)偶問題的最優(yōu)解題的最優(yōu)解定是問題2的對(duì)偶問題的可行解。因?yàn)樵瓎栴}與對(duì)偶問題的最優(yōu)值相等，所以需加工小時(shí)數(shù)、設(shè)備的有效臺(tái)時(shí)和單位產(chǎn)品的利潤如表2所示。表2為4萬元，假定各設(shè)備的有效臺(tái)時(shí)數(shù)不變，投產(chǎn)這種產(chǎn)品在經(jīng)濟(jì)上是否合算?解：1.設(shè)生產(chǎn)甲、乙、丙三種產(chǎn)品各為xi,X2,x?單位，則由題意得加入松弛變量后，利用單純形法計(jì)算如下：001X?X?σ000010100解：設(shè)A、B、C分別代表三套儀器1#、2#,3#,A;表示在第i次實(shí)驗(yàn)中用儀器A,依此類推Bi、C,并設(shè)虛擬開始S和結(jié)束點(diǎn)D。則得網(wǎng)絡(luò)圖如圖1所示：求總的中斷試驗(yàn)的時(shí)間最小，即找最短路問題，利用Dijkstra算法計(jì)算如下：∵A?,B?,C?到S點(diǎn)距離相同，∴可同時(shí)標(biāo)號(hào)(5)比較T(A4)、T(B4)、T(C4),可得出，T(B4)最小的使用順序是：三=,即3#-2#-3#-2#。五、某農(nóng)場考慮是否提早種植某種作物的決策問題，如果提早種，又不遇霜凍.則收入為45元：如遇霜凍，則收入僅為10萬元.遇霜凍的概率為0.4。如不提早種，又不遇霜凍.則收入為35萬元：即使遇霜凍.受災(zāi)也輕，收入為25萬元，遇霜凍的概率為0.2,已知：(1)該農(nóng)場的決策者認(rèn)為：“以50%的機(jī)會(huì)每45萬元.50%的機(jī)會(huì)得10萬元”和“穩(wěn)獲35萬元”(2)該農(nóng)場的決笨者認(rèn)為：“以50%的機(jī)會(huì)得45萬元，50%的機(jī)會(huì)得35萬元”和“穩(wěn)獲40萬(3)該農(nóng)場的決策者認(rèn)為：“以50%的機(jī)會(huì)得35萬元，50%的機(jī)會(huì)得10萬元”和“穩(wěn)獲25萬元”二者對(duì)其來說沒有差別。(南開大學(xué)2011研)1.說明該決策者對(duì)風(fēng)險(xiǎn)的態(tài)度，按期望效用最大的原則，該決策者應(yīng)做何種決策?2.按期望收益最大的原則，該決策者又應(yīng)做何種決策?解：1.將最高收益45萬元的效用定為10,記為。把最低收益值10萬元的效用定為0,記為令提早種的期望效用為=,不提早種的期望效用為=。則,所以，決策者的決策應(yīng)為不提早種。2.令提早種的期望收益為三，不提早種的期望收益為三。表4(1)標(biāo)號(hào)過程③檢查B,在弧(B1,D)上，,則給D標(biāo)號(hào)(B1,20),這樣找到了一條增廣鏈，(2)調(diào)整過程，由(1)知，3=,得新的可行流量圖，如圖3所示。圖3依據(jù)上述方法，重復(fù)標(biāo)號(hào)及調(diào)整過程，直到不存在增廣鏈為止，最終得最大流量圖，如圖4所示。調(diào)運(yùn)方案如表5所示.A?A?A?圖4表5B?B?B?B?實(shí)際供出量七、某公司生產(chǎn)兩種小型摩托車.其中甲型完全由本公司制造，而乙型是進(jìn)口零件由公司裝配而成，這兩種產(chǎn)品每輛所需的制造、裝配及檢驗(yàn)時(shí)間如下表6所示。表6P?每周的總利潤至少為3000元：P?:每周甲型車至少生產(chǎn)5輛；P3:盡量減少各道工序的空余時(shí)間，三工序的權(quán)系數(shù)和它們的某商科技公司的MIS中心處理本公司信息系統(tǒng)的維護(hù)服務(wù)。公司其他部門職員打電話到信該中心每小時(shí)平均接受到40個(gè)服務(wù)請(qǐng)求，服務(wù)請(qǐng)求的到達(dá)服從泊松分布。每個(gè)請(qǐng)求的平均服務(wù)時(shí)間是3分鐘，且服從負(fù)指數(shù)分布。信息中心服務(wù)人員每小時(shí)的平均工資是15元。公司職員每小時(shí)為公司創(chuàng)造的收益是25元。我們已經(jīng)通過軟件計(jì)算出服務(wù)中心的服務(wù)人員個(gè)數(shù)與等待接受MIS維護(hù)服務(wù)的平均職員數(shù)之間的關(guān)系，如表7所示。表71.如果公司經(jīng)理希望職員等待MIS維護(hù)服務(wù)(排隊(duì)等待和服務(wù)等待的平均時(shí)間)不要超過52.如果公司經(jīng)理考慮聘用服務(wù)人員的成本以及因?yàn)榈却蛘诮邮躆IS維護(hù)服務(wù)造成的企25分，其中第一小題10分，第二小題15分)解：1.要求等待MIS維護(hù)服務(wù)時(shí)間小于等于5分鐘，已知平均服務(wù)時(shí)間是3分鐘，故服務(wù)時(shí)間是2分鐘，約是0.0333小時(shí)查表6可知，該信息中心最少需要聘用服務(wù)人員3人。cW234表856表93456Z869.432547.500262011年南開大學(xué)813運(yùn)籌學(xué)(信息學(xué)院)考研真題及詳解一、(35分)已知某工廠計(jì)劃生產(chǎn)A、B、C三種產(chǎn)品，備產(chǎn)品均需使用甲、乙、丙這三種數(shù)據(jù)如表1所示。試問：(1)應(yīng)如何安排三種產(chǎn)品的生產(chǎn)使得總利潤最大?(2)若另有兩種新產(chǎn)品D、E,生產(chǎn)單位D產(chǎn)品需用甲、乙、丙三種設(shè)備12小時(shí)、5小時(shí)、10小時(shí)，單位產(chǎn)品利潤2.1千元；生產(chǎn)單位E產(chǎn)品需用甲、乙、丙三種設(shè)備4小12小時(shí)，單位產(chǎn)品利潤1.87千元，請(qǐng)分別回答這兩種新產(chǎn)品投產(chǎn)是否合算?(3)若為了增加產(chǎn)量，可租用其他工廠的設(shè)備甲，可租用的時(shí)間是60小時(shí)，租金1.8萬元。(4)增加設(shè)備乙的工時(shí)是否可使工廠的總利潤進(jìn)一步增加?添加人工變量x?,X?,x6利用單純形法計(jì)算如表2所示。(2)增加新變量x7,x?,對(duì)應(yīng)的c7=2.1,cg=1.87,約束矩陣增加兩個(gè)列向量則判斷出：產(chǎn)品D的投產(chǎn)不合算，產(chǎn)品E投產(chǎn)合算。(3)即,其不影響檢驗(yàn)數(shù)的結(jié)果，故最優(yōu)解不變。(4)當(dāng)增加乙的工時(shí)，,故利潤不會(huì)增加。二、(15分)有A、B、C、D四種零件均可在設(shè)備甲或設(shè)備乙上加工。已知這兩種設(shè)備上分別加工一個(gè)零件的費(fèi)用如表3所示。又知設(shè)備甲或設(shè)備乙只要?jiǎng)淤M(fèi)用，分別為100元和150元?，F(xiàn)要求加工四種零件各3件，問應(yīng)如何安排生產(chǎn)使總的費(fèi)用最小?請(qǐng)建立該問題的線性規(guī)劃模型(不需求解)。加工一個(gè)零件的費(fèi)用(單位：元)表3三、(25分)某工程公司在未來1~4月份內(nèi)需完成三項(xiàng)工程：第一項(xiàng)工程的工期為1~3月份，總計(jì)需勞動(dòng)力80人月；第二項(xiàng)工程的工期為1~4月份，總計(jì)需勞動(dòng)力100人月；第三項(xiàng)工程的工期為3～4月份，總計(jì)需勞動(dòng)力120人月。該公司每月可用勞力為80人，但任一項(xiàng)工程上投入的勞動(dòng)力任一月內(nèi)不準(zhǔn)超過60人。問該工程公司能否按期完成上述三項(xiàng)工程任務(wù)，應(yīng)如何安排勞力?(請(qǐng)將該問題歸結(jié)為網(wǎng)絡(luò)最大流問題求解)解：可以構(gòu)建網(wǎng)絡(luò)圖(弧上數(shù)字為最大流量),如圖1所示。其中，結(jié)點(diǎn)1、2、3、4分別代表1、2、3、4月份，結(jié)點(diǎn)5、6、7分別代表第一、二、三項(xiàng)工程。通過標(biāo)號(hào)與調(diào)整，得到的最大流如圖2所示。圖2所以該公司能按期完成上述三項(xiàng)工程任務(wù)，安排勞力的方案可以為：1月份，安排60人做第一項(xiàng)任務(wù)、20人做第二項(xiàng)任務(wù)；2月份，安排60人做第二項(xiàng)任務(wù)；3月份，安排60人做第三項(xiàng)任務(wù)、20人做第一項(xiàng)任務(wù)；4月份，安排60人做第四項(xiàng)任務(wù)、20人做第三項(xiàng)任務(wù)。四、(25分)某工廠設(shè)計(jì)的一種電子設(shè)備由A、B、C三種元件串聯(lián)而成，已知三種元件的單價(jià)分別為2萬元、3萬元、1萬元，單件的可靠性分別為0.7、0.8、0.6,要求設(shè)計(jì)中使用元件的總費(fèi)用不超過10萬元，問應(yīng)如何設(shè)計(jì)使設(shè)備的可靠性最大?(請(qǐng)使用動(dòng)態(tài)規(guī)劃方法求解：設(shè)各種元件的個(gè)數(shù)為x1,X?,X3,則根據(jù)變量的個(gè)數(shù)，將該問題分為3階段。設(shè)狀態(tài)變量令最優(yōu)值函數(shù)f.(s)表示第k階段的初始狀態(tài)為sk,從第k階段至第3階段的最大值，用逆推方法用逆推方法由由,但1≤x?≤S?/3,s?≤10-2*1=8,∵I≤xi≤S?/2,且為整即購買三種元件分別為3件、1件、1件。五、(25分)某公司興建一座港口碼頭，只有一個(gè)裝卸船只的位置。設(shè)船只到達(dá)的間隔時(shí)間和裝卸時(shí)間都服從負(fù)指數(shù)分布，預(yù)計(jì)船只的平均到達(dá)率為3只/天，船只到港后如不能及時(shí)裝卸，停留一日公司將損失1500元。現(xiàn)需設(shè)計(jì)該港口碼頭的裝卸能力(即每日可以裝卸的船只數(shù)),已知單位裝卸能力每日平均生產(chǎn)費(fèi)用為2000元，問裝卸能力為多大時(shí)，每天的總支出最少?在此裝卸能力之下，求：(1)裝卸碼頭的利用率；(2)船只到港后的平均等候時(shí)間?(3)船只到港后總停留時(shí)間大于一天的概率。所以時(shí)，每天的總支出最少?！啻a頭的利用率為1-P?=2/3即船只到港后的平均等候時(shí)間是(3)設(shè)船只到港后的總停留時(shí)間T六、(25分)已知A、B各自的純策略及A的贏得矩陣如表4所示，求雙方的最優(yōu)策略及對(duì)策值。解：在A的贏得矩陣中第4列優(yōu)超于第2列，第1列優(yōu)超于第3列，故可劃去第2列和第3列，得到新的贏得矩陣對(duì)于=,第二行優(yōu)超于第4行，因此去掉第4行，得到1檢驗(yàn)數(shù)1檢驗(yàn)數(shù)00y?1檢驗(yàn)數(shù)01121001001000-1/81/7表501第二部分課后習(xí)題第1章線性規(guī)劃與單純形法可得A?的坐標(biāo)為(2,4),所以,該線性規(guī)劃問題具解：如圖1-2所示，該線性規(guī)劃問題的可行域無界。目標(biāo)函數(shù)在點(diǎn)A處取得最小值，求解方程組得A點(diǎn)的坐標(biāo)為,所以,該問題具有惟一最優(yōu)解。解：如圖1-3所示，該問題的可行域無界。目標(biāo)函數(shù)可以增加到無窮大，因此該問題無最優(yōu)解或稱為無界解。解：如圖1-4所示，該問題的可行域?yàn)榭占?，因此該線性規(guī)劃無可行解。1.2將下列線性規(guī)劃問題變換成標(biāo)準(zhǔn)型，并列出初始單純形表。 解：令,且;在第一個(gè)約束條件兩邊同時(shí)乘以-1后引入人工變量-=,在第二個(gè)約束條件右端加上松弛變量4=;在第三個(gè)約束條件右端減去剩余變量4=,同時(shí)加入人工變量三，將目標(biāo)函數(shù)最小化變換為最大化，得該線性規(guī)劃的標(biāo)準(zhǔn)型其中，M為充分大的正數(shù)，對(duì)應(yīng)的初始單純形表如表1-1所示。解：在上述約束條件兩邊同時(shí)乘以-1,然后分別引入人工變量x1:x?:.x,得該線性規(guī)劃的標(biāo)準(zhǔn)型其中，M為充分大的正數(shù)。對(duì)應(yīng)的初始單純形表如表1-2所示。1.3在下面的線性規(guī)劃問題中找出滿足約束條件的所有基解，指出哪些是基可行解，并代入目標(biāo)函數(shù)，確定哪一個(gè)是最優(yōu)解。解：在第二個(gè)約束條件兩邊同時(shí)乘以-1,得到該線性規(guī)劃問題的系數(shù)矩陣①因?yàn)槿?、三線性無關(guān)，故有P③因?yàn)?、=線性無關(guān)，故有令非基變量],解得故有基可行解⑥因B、「線性無關(guān)，故有,解得不是可行解。解：其系數(shù)矩陣為①因?yàn)镻、P線性無關(guān)，故有不是可行解。令非基變量x?=x?=0,解得為基可行解，P、P線性無關(guān)，故有③因?yàn)榱罘腔兞?=x?=0,解得不是可行解。④因?yàn)镻、P線性無關(guān)，故有⑤因?yàn)棰抟驗(yàn)?、P4線性相關(guān)，故一不能構(gòu)成基變量。在E=中，三為最大值，所以最優(yōu)解1.4分別用圖解法和單純形法求解下列線性規(guī)劃問題，并指出單純形法迭代的每一步相當(dāng)于圖1-5該線性規(guī)劃問題的可行域如圖1-5所示。由圖可1,對(duì)應(yīng)于圖上的點(diǎn)A?,其最優(yōu)目標(biāo)函數(shù)值—=三。引入松弛變量,得該線性規(guī)劃問題的標(biāo)準(zhǔn)型故問題的最優(yōu)解一,最優(yōu)目標(biāo)函數(shù)值z=33/4。單純形表第一步迭代得,對(duì)應(yīng)于圖1-5中的的坐標(biāo)原點(diǎn)；單純形表第二步迭代得,對(duì)應(yīng)于圖1-5中的點(diǎn)A?(4,0);單純形表第三步迭代得,對(duì)應(yīng)于圖1-5中的點(diǎn)A?該線性規(guī)劃的可行域如圖1-6所示，由圖知該線性規(guī)劃的惟一最優(yōu)解為,對(duì)應(yīng)于圖上的點(diǎn)A?(2,6),最優(yōu)目標(biāo)函數(shù)值為在上述問題的約束條件中引入松弛變量,得到該規(guī)劃問題的標(biāo)準(zhǔn)型利用單純形表進(jìn)行迭代計(jì)算如表1-4所示。故問題的最優(yōu)解一,最優(yōu)目標(biāo)函數(shù)值z=34。單純形表第一步迭代得I,對(duì)應(yīng)于圖1-6中的的坐標(biāo)原點(diǎn)；單純形表第二步迭代得,對(duì)應(yīng)于圖1-6中的點(diǎn)A?(0,6);單純形表第三步迭代得,對(duì)應(yīng)于圖1-6中的點(diǎn)A?(2,6)。1.5以第1.4題(1)為例，具體說明當(dāng)目標(biāo)函數(shù)中變量的系數(shù)怎樣改變時(shí)，使?jié)M足約束條件的可行域的每一個(gè)頂點(diǎn)，都有可能使目標(biāo)函數(shù)值達(dá)到最優(yōu)。①若則當(dāng)一時(shí)，目標(biāo)函數(shù)在點(diǎn)A?(4,0)處取得最大值；當(dāng)時(shí)，目標(biāo)函數(shù)在原點(diǎn)(0,0)處取得最大值；②若，則當(dāng)一日時(shí)，目標(biāo)函數(shù)在點(diǎn)A?(15/4,3/4)處取得最大值，其中時(shí)，在線段A?A?上的任一點(diǎn)取得最大值；當(dāng)一時(shí)，目標(biāo)函數(shù)在原點(diǎn)處取得最大在線段A?A?上的任一點(diǎn)取得最大值；當(dāng)一E=時(shí)，目標(biāo)函數(shù)在坐標(biāo)原點(diǎn)處取得最大值；(2)當(dāng)一E=時(shí)，目標(biāo)函數(shù)①當(dāng)一F時(shí)，目標(biāo)函數(shù)在點(diǎn)A?(4,0)處取得最大值；②當(dāng)一=時(shí)，目標(biāo)函數(shù)在可行域OA?A?A?中的任一點(diǎn)處均可取得最大值；③當(dāng)一==時(shí)，目標(biāo)函數(shù)在線段OA?上的任一點(diǎn)取得最大值。1.6分別用單純形法中的大法和兩階段法求解下述線性規(guī)劃問題，并指出屬哪一類解。在上述問題的第二個(gè)約束條件中減去剩余變量3,再加入人工變量一，得其中，是一個(gè)任意大的正數(shù)，應(yīng)用單純形法迭代計(jì)算如表1-5所示。0010111101表1-50-1010M/2+1-3M/2-1757最優(yōu)目標(biāo)函數(shù)值=故-為原線性規(guī)劃問題的基可行解。在上述兩個(gè)約束條件中依次分別減去剩余變量,再加上人工變量E,得的檢驗(yàn)數(shù)中,所以該線性規(guī)劃問題有無窮多最優(yōu)解。在上述線性規(guī)劃問題的約束條件中分別減去剩余變量x4:Xs,再加上人工變量X?:Xx,得第上述線性規(guī)劃問題最優(yōu)L,其目標(biāo)函數(shù)最優(yōu)值0*=0,可以繼續(xù)故此線性規(guī)劃問題有無窮多最優(yōu)解。去剩余變量再加上人工變量7,并化為標(biāo)準(zhǔn)型，得010010-Mx752361111000109939/80000σσ01/16σ變量=,故原線性規(guī)劃問題無可行解。去剩余變量再加上人工變量，得第一階段的數(shù)學(xué)模型為在最終單純形表中，人工變量x=1/2≠0,而所有非基變量的檢驗(yàn)數(shù)均滿足一舊，所在原線性規(guī)劃問題的約束條件中分別減去剩余變量=,再加上人工變量，σ001o3M/2+3/-5M/2-301σσ100==,0-11θ604在最終單純形表中，在最終單純形表中，11110100000σ0000x?11000000100010010-1/21/2-b由表1-15中計(jì)算可知，在上述問題的第一個(gè)約束條件中加入松弛變量三，第二個(gè)約束條件左右兩邊同時(shí)除以2再加入松弛變量=,得到該線性規(guī)劃問題的標(biāo)準(zhǔn)型解得最優(yōu)解三=,目標(biāo)函數(shù)z的上界(2)要求z的下界2,則一應(yīng)取其最小值；應(yīng)取其最大值，此時(shí)，在上述問題的第一個(gè)約束條件中加入松弛變量三，第二個(gè)約束條件左右兩邊同時(shí)除以2再加入松弛變量=,得到該線性規(guī)劃問題的標(biāo)準(zhǔn)型1.8表1-18是某求極大化線性規(guī)劃問題計(jì)算得到的單純形表。表中無人工變量，(1)表中解為惟一最優(yōu)解；(2)表中解為最優(yōu)解，但存在無窮多最優(yōu)解；(3)該線性規(guī)劃問題具有無界解；(4)表中解非最優(yōu)，為對(duì)解改進(jìn)，換入變量為F,換出變量為x?。(2)當(dāng)且三=0時(shí)，表中的解為最優(yōu)解，且原問題有無窮多個(gè)最優(yōu)解；進(jìn)，換入變量為E,換出變量為x6。1.9某晝夜服務(wù)的公交線路每天各時(shí)間區(qū)段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如表1-19所示。設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間區(qū)段一開始時(shí)上班，并連續(xù)工作8h,問該公交線路至少需配備解：設(shè)一為從第班次開始上班的司機(jī)和乘務(wù)員的人數(shù)，則可建立數(shù)學(xué)模型為：中A、B、C含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)及售價(jià)如表1-20所示。表1-20售價(jià)(元/問該廠每月應(yīng)生產(chǎn)這三種牌號(hào)糖果各多少千克，才能使該廠獲利最大?試建立該問題的線性規(guī)劃模型。解：設(shè)甲糖果中原料A、B、C的含量分別為xi:x?.Xx3;乙糖果中原料A,B,C的含量分別為丙糖果中原料A、B、C的含量分別為x7:xg:X,則生產(chǎn)甲糖果癲骨起骨寫千克，乙糖果—=千克，丙糖果—=,可建立如下數(shù)學(xué)模型：1.11某廠生產(chǎn)三種產(chǎn)品I,Ⅱ,Ⅲ。每種產(chǎn)品要經(jīng)過A,B兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成A工序，它們以A,A?表示；有三種規(guī)格的設(shè)備能完成B工序，它們以B,B?,B?表示。產(chǎn)品I可在A,B任何一種規(guī)格設(shè)備上加工。產(chǎn)品Ⅱ可在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在B?設(shè)備上加工；產(chǎn)品Ⅲ只能在A?與B?設(shè)備上加工。已知各種設(shè)備的單件工時(shí)，原材料費(fèi)，產(chǎn)品銷售價(jià)格，各種設(shè)備有效臺(tái)時(shí)以及滿負(fù)荷操作時(shí)設(shè)備的費(fèi)用如表1-21所示。要求安排最優(yōu)的生產(chǎn)計(jì)劃，使該廠利潤最大。A?47表1-21原料費(fèi)(元/0.20.30.5解：設(shè)|==分別為用Ai,A?加工產(chǎn)品I的件數(shù)，,x:X:X5分別用Bi,B?,B?加工產(chǎn)品I的件用A?及B?加工產(chǎn)品Ⅲ的件數(shù)。由題意，可建立數(shù)學(xué)規(guī)劃模型：即用A?加工產(chǎn)品I1200件，用A?加工產(chǎn)品I230件，用B?加工產(chǎn)品I0件，用B?加工產(chǎn)品 I859件，用B?加工產(chǎn)品I571件，用A?加工產(chǎn)品ⅡO件，用A?加工產(chǎn)品Ⅱ500件，用B?加工產(chǎn)品Ⅱ500件，用A?及B?加工產(chǎn)品Ⅲ324件，可獲得最大利潤1147元。第2章對(duì)偶理論與靈敏度分析2.1用改進(jìn)單純形法求解以下線性規(guī)劃問題。得到初始基,初始基變量;非基變量,對(duì)應(yīng)的系數(shù)非基變量的檢驗(yàn)數(shù)ox=C。-C?B=N?=(6.-2.3),則1為換入變量。,所以對(duì)應(yīng)的換出變量為x4。計(jì)算換入變量1的系數(shù)向量F及一=為：計(jì)算非基變量的檢驗(yàn)數(shù)為：由一=可確定F為換入變量，再由 知5為換出變量。計(jì)算換入變量的系數(shù)向量=及一==為：非基變量的檢驗(yàn)數(shù)向量為此時(shí)，非基變量的檢驗(yàn)數(shù)均為負(fù)，最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值為解：在第二個(gè)約束條件中減去剩余變量考，再分別在第一、二個(gè)約束條件中加入人工變量x4.x3,在第三個(gè)約束條件中加入松弛變量%,得該線性規(guī)劃的標(biāo)準(zhǔn)型：得到初始基,初始基變量,對(duì)應(yīng)的系數(shù)Xx=(x,x?,x),,對(duì)應(yīng)的系數(shù)。非基變量的檢驗(yàn)數(shù)L,則1為換入變量。,所以對(duì)應(yīng)的換出變量為x4。由此得到新的基B?、基變量XE及系數(shù)C、非基變量XA及系數(shù)Cx.分別為：計(jì)算換入變量1的系數(shù)向量P及B?為：由N?可確定為換入變量，再由知X5為換出變量。因?yàn)榉腔兞康臋z驗(yàn)數(shù)均大于0,故問題的最優(yōu)解為：2.2已知某線性規(guī)劃問題，用單純形法計(jì)算時(shí)得到的中間某兩步的計(jì)算表見表2-2,試將表2-2解：先求=,由上表中的上一部分知表中空缺的系數(shù)矩陣為迭代后的基變量對(duì)應(yīng)的系數(shù)，所以表2-2中要填寫的數(shù)字如表2-3所表2-32.3寫出下列線性規(guī)劃問題的對(duì)偶問題。解：設(shè)對(duì)應(yīng)于各約束條件的對(duì)偶變量為,則其對(duì)偶問題為：解：設(shè)對(duì)應(yīng)于各約束條件的對(duì)偶變量為,則其對(duì)偶問題解：設(shè)對(duì)應(yīng)于各約束條件的對(duì)偶變量為1,則其對(duì)偶問題為：2.4判斷下列說法是否正確，為什么?(1)如果線性規(guī)劃的原問題存在可行解，則其對(duì)偶問題也一定存在可行解；(2)如果線性規(guī)劃的對(duì)偶問題無可行解，則原問題也一定無可行解；(3)如果線性規(guī)劃的原問題和對(duì)偶問題都具有可行解，則該線性規(guī)劃問題一定具有有限最解：(1)錯(cuò)誤。線性規(guī)劃的原問題存在可行解，其對(duì)偶問題不一定存在可行解。當(dāng)原問題易知該線性規(guī)劃問題存在可行解，如,該問題的對(duì)偶問題為(2)錯(cuò)誤。當(dāng)線性規(guī)劃問題的對(duì)偶問題無可行解時(shí)，原問題可能具有無界解或者是無可行(3)錯(cuò)誤。當(dāng)線性規(guī)劃的原問題和對(duì)偶問題都具有可行解時(shí)，該線性規(guī)劃問題可能存在有2.5設(shè)線性規(guī)劃問題1是)是其對(duì)偶問題的最優(yōu)解。又設(shè)線性規(guī)劃問題2是其中三是給定的常數(shù)，求證證明：問題1的矩陣表示為設(shè)=為它的一個(gè)可行解，其對(duì)偶問題的最優(yōu)解為問題2的矩陣表示為設(shè)：=為它的一個(gè)可行解，其對(duì)偶問題的最優(yōu)解為問題1的對(duì)偶問題為問題2的對(duì)偶問題為由此可知，問題1的對(duì)偶問題與問題2的對(duì)偶問題有相同的約束條件，所以問題1的對(duì)偶問題的最優(yōu)解x=(i.…v)一定是問題2的對(duì)偶問題的一個(gè)可行解。又因?yàn)閅2是問題2對(duì)偶問題的最優(yōu)解，所以，2.6已知線性規(guī)劃問題用單純形法求解，得到最終單純形表如表2-4所示。表2-4解：(1)由題意可設(shè)初始單純形表的增廣矩陣為對(duì)矩陣二：=作初等行變換，使其第4,5列組成單位矩陣(2)由檢驗(yàn)數(shù)的計(jì)算式可知2.7已知線性規(guī)劃問題其對(duì)偶問題的最優(yōu)解為==,試應(yīng)用對(duì)偶問題的性質(zhì)，求原問題的最優(yōu)解。將分別代入對(duì)偶問題的各約束條件中，可知，式①和式②為嚴(yán)格不等式，由互補(bǔ)松弛性可知,所以根據(jù)互補(bǔ)松弛性知，原問題的兩個(gè)約2.8試用對(duì)偶單純形法求解下列線性規(guī)劃問題。解：在兩個(gè)約束條件兩邊同乘以-1,再分別加入松弛變量一F得到如下形式列出初始單純形表，并利用對(duì)偶單純形法進(jìn)行求解，求解過程如表2-5所示。表2-5得線性規(guī)劃問題的最優(yōu)解為L,目標(biāo)函數(shù)值為。解：先將上述線性規(guī)劃問題化成如下形式，以便得到對(duì)偶問題的初始可行基建立此問題的初始單純形表，并利用對(duì)偶單純法進(jìn)行計(jì)算，如表2-6所示。表2-61202/5(1)約束條件式①的右端常數(shù)由20變?yōu)?0;(2)約束條件式②的右端常數(shù)由90變?yōu)?0;(3)目標(biāo)函數(shù)中=的系數(shù)由13變?yōu)?;(4)=的系數(shù)列向量由(6)將原約束條件②改變?yōu)樗?，原問題得到最優(yōu)解為1,最優(yōu)目標(biāo)函數(shù)值=。(1)約束條件式①的右端常數(shù)由20變?yōu)?0列出單純形表，并利用對(duì)偶單純形法求解，求解過程如表2-8所示。表2-8所以，線性規(guī)劃問題的最優(yōu)解變?yōu)?最優(yōu)目標(biāo)函數(shù)值為=。(2)約束條件式②的右端常數(shù)由90變?yōu)?0列出初始單純形表，并利用對(duì)偶單純形法進(jìn)行迭代計(jì)算，求解過程如表2-9所示。表2-9所以，線性規(guī)劃的最優(yōu)解變?yōu)?最優(yōu)目標(biāo)函數(shù)值為—[(3)目標(biāo)函數(shù)中3的系數(shù)由13變?yōu)?在約束條件式③中加入松弛變量6,得。將此約束條件加入原單C50b5131σ030310001025027/25300000001000000010010所以，線性規(guī)劃的最優(yōu)解變?yōu)?最優(yōu)目標(biāo)函數(shù)值為一=。2.10已知某工廠計(jì)劃生產(chǎn)I,Ⅱ,Ⅲ三種產(chǎn)品，各產(chǎn)品需要在A,B,C設(shè)備上加工，有關(guān)表2-11設(shè)備代號(hào)IⅡⅢ設(shè)備有效臺(tái)時(shí)/月單位產(chǎn)品利潤/千元322.9試回答：(1)如何充分發(fā)揮設(shè)備能力，使生產(chǎn)盈利最大?(2)若為了增加產(chǎn)量，可借用其他的工廠的設(shè)備B,每月可借用60臺(tái)時(shí)，借用金1.8萬元，問借用設(shè)備B是否合算?(3)若另有兩種新產(chǎn)品IV,V,其中IV需用設(shè)備A12臺(tái)時(shí)，設(shè)備B5臺(tái)時(shí)，設(shè)備C10臺(tái)時(shí)，單位產(chǎn)品盈利2.1千元；新產(chǎn)品V需用設(shè)備A4臺(tái)時(shí)，設(shè)備B4臺(tái)時(shí)，設(shè)備C12臺(tái)時(shí)，單位產(chǎn)品盈利1.87千元。如設(shè)備A,B,C設(shè)備臺(tái)時(shí)不增加，分別回答這兩種新產(chǎn)品投產(chǎn)在經(jīng)濟(jì)上是否合算?(4)對(duì)產(chǎn)品工藝重新進(jìn)行設(shè)計(jì)，改進(jìn)結(jié)構(gòu)，改進(jìn)后生產(chǎn)每件產(chǎn)品I,需用設(shè)備A9臺(tái)時(shí)，設(shè)備B12臺(tái)時(shí)，設(shè)備C4臺(tái)時(shí)，單位產(chǎn)品盈利4.5千元，問這對(duì)原計(jì)劃有何影響?解：(1)設(shè)分別生產(chǎn)產(chǎn)品I,Ⅱ,Ⅲ三種產(chǎn)品：x?x3單位，由題意，可建立數(shù)學(xué)模型在上述線性規(guī)劃問題的約束條件中分別加上松弛變量建立初始單純形表，并利用單純形法進(jìn)行迭代，過程如表2-12所示。C3可σ10000100000010001030019σ所以生產(chǎn)IV產(chǎn)品在經(jīng)濟(jì)上不合算。在最終單純形表中對(duì)應(yīng)的列向量及對(duì)應(yīng)的檢驗(yàn)數(shù)為所以，生產(chǎn)產(chǎn)品V在經(jīng)濟(jì)上合算。將的系數(shù)列向量加入最終單純形表，并進(jìn)行進(jìn)一步迭代，如表2-13所示。0003x,107/41023/401/4021/24-3/8007σ,最優(yōu)目標(biāo)函數(shù)值為所以，改進(jìn)技術(shù)后能帶來更多的經(jīng)濟(jì)效益。2.11分析下列參數(shù)規(guī)劃中當(dāng)變化時(shí)最優(yōu)解的變化情況。解：在約束條件中分別加入松弛變量x4:x,:xs,并將模型化為標(biāo)準(zhǔn)型為令t=0,并利用單純形法進(jìn)行求解，如表2-14所示。000σXBbX?X?X?X?X?X?θ02301所以，該線性規(guī)劃問題的最優(yōu)解為一,將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終表上，如表2-15所示。表2-15當(dāng)t≤1時(shí)，所有變量的檢驗(yàn)數(shù)均不大于0,最優(yōu)解X=(0.100.230.0.0.20)";當(dāng)t>1時(shí)，,需進(jìn)行進(jìn)一步迭代，以三為換出變量，三為換入變量，進(jìn)一步迭代過程如表2-16所示。o00000000x?4301101000420σ所以，當(dāng)t>1時(shí)，最優(yōu)解為解：在約束條件中分別引入松弛變量,并化成如下標(biāo)準(zhǔn)型。表2-20令t=0,并利用單純形法進(jìn)行求解，如表2-17所示。所以，該線性規(guī)劃問題的最優(yōu)解為一,將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終表上，如表2-18所示。表2-18Cb01510o00當(dāng)O≤t≤8/3時(shí)，所有變量的檢驗(yàn)數(shù)均不大于0,最優(yōu)解一當(dāng)>8/3時(shí)，σ?>0,需進(jìn)行進(jìn)一步迭代，以F為換出變量，,=為換入變量，進(jìn)一步迭代過程如表2-19所示。表2-19θ當(dāng)t>5時(shí)，,需進(jìn)行進(jìn)一步迭代，以一三為換出變量，三為換入變量，進(jìn)一步迭代過程如表2-20所示。令t=0,并利用單純形法進(jìn)行求解，如表2-21所示。0200201b5210210001000101110110010000100010001001000101000010001001-計(jì)算：將計(jì)算結(jié)果代入到最終單純形表中，得到表2-22。表2-22所示。2-24所示。0σ表2-240100101001011010b10所以，當(dāng)t=0時(shí)，該線性規(guī)劃問題的最優(yōu)解為當(dāng)O≤≤6時(shí)，表2-25中=12.,得最優(yōu)解00所示。表2-28所以，當(dāng)11<t≤59時(shí)，族=12.0,,最優(yōu)解為3.1判斷表3-1和表3-2中給出的調(diào)運(yùn)方案能否作為用表上作業(yè)法求解時(shí)的初始解?為什么?表3-1表3-2解：表3-1中有5個(gè)基格，而要作為初始解，應(yīng)有m+n-l=3+4-1=6個(gè)基格，所以表3-1給出的調(diào)運(yùn)方案不能作為表上作業(yè)法的初始解；表3-2中，有10個(gè)數(shù)基格，而理論上只應(yīng)有m+n-l=9個(gè)，多出了一個(gè)，所以表3-2給出的調(diào)運(yùn)方案不能作為表上作業(yè)法的初始解。3.2表3-3和表3-4中，分別給出兩個(gè)運(yùn)輸問題的產(chǎn)銷平衡表和單位運(yùn)價(jià)表，試用伏格爾(Vogel)法直接給出近似最優(yōu)解。表3-3表3-4表3-9運(yùn)價(jià)12315182241336749解：(1)第一步：在表3-3中分別求各行和各列的最小運(yùn)價(jià)和次小運(yùn)價(jià)的差額，并分別填入該表的最右列和最下行，如表3-5所示。表3-5第二步：從行差額或列差額中選出最大者，選擇它所在行或列中的最小元素。在表3-5中，第3列是最大差額所在列。第3列中最小元素為1,可確定產(chǎn)地2的產(chǎn)品優(yōu)先供應(yīng)銷地3的需要，得表3-6。同時(shí)將運(yùn)價(jià)表中的第3列數(shù)字劃去，如表3-7所示。表3-6表3-7第三步：對(duì)表3-7中未劃去的元素再分別計(jì)算出各行、各列的最小運(yùn)價(jià)和次小運(yùn)價(jià)的差額，并填入該表的最右列和最下行。重復(fù)第一、二步，直到給出初始解為止，初始解如表3-8所(2)第一步：在表3-4中分別計(jì)算各行和各列的最小運(yùn)價(jià)和次小運(yùn)價(jià)的差額，并分別填入該表的最右列和最下行，如表3-9所示。第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表3-9中第3列是最大差額所在列。第3列中最小元素為3,可確定產(chǎn)地1的產(chǎn)品優(yōu)先供應(yīng)銷地3的需要。同時(shí)將運(yùn)價(jià)表中的第1行數(shù)字劃去，如表3-10所示。表3-10單單位銷地運(yùn)價(jià)12345產(chǎn)量139zS2435745M8填入該表的最右列和最下行。重復(fù)第一、二步，直到給出初始解為止，初始解見表3-10的3.3用表上作業(yè)法求表3-11至表3-14中給出的運(yùn)輸問題的最優(yōu)解(表中數(shù)字M為任意大正表3-11表3-12表3-13表3-14解：(1)解表3-11表3-19第一步：用伏格爾法求初始可行解(過程類似于上一題，不再贅述),求得的初始解如表3-15所示。第二步：用位勢法進(jìn)行最優(yōu)解的判斷。在對(duì)應(yīng)于表3-15的數(shù)字格處填入單位運(yùn)價(jià)，并增加的三和三，如表3-16所示。對(duì)于表3-16中的空格，依據(jù)檢驗(yàn)數(shù)，如表3-17所示。表3-16表3-17由表3-17可知，所有空格處的檢驗(yàn)數(shù)均為非負(fù)。所以，表3-15中的運(yùn)輸方案，即為此問題的最優(yōu)調(diào)運(yùn)方案，最小運(yùn)價(jià)為32。由于非基變量的檢驗(yàn)數(shù)中一3三，所以該運(yùn)輸問題有無窮多最優(yōu)解。(2)解表3-12第一步：用伏格爾法求初始可行解，求得的初始解，如表3-18所示。第二步：用位勢法進(jìn)行最優(yōu)解的判斷。在對(duì)應(yīng)于表3-18的數(shù)字格處填入單位運(yùn)價(jià)，并增加一行一列，在行中填入E,在列中填入日。令一，按照求出所有的和，并依據(jù)三=計(jì)算所有空格處的檢驗(yàn)數(shù)，計(jì)算結(jié)果如表3-19所示。由表3-19可知，所有空格處的檢驗(yàn)數(shù)均為非負(fù)。所以，表3-18中的運(yùn)輸方案即為此問題的最優(yōu)調(diào)運(yùn)方案，最小運(yùn)價(jià)為118。(3)解表3-13由于表3-13中產(chǎn)大于銷，因此需要增添一個(gè)假想的銷地“己”,其運(yùn)價(jià)為0,其銷量為2,如表3-20所示。表3-20第一步：用伏格爾法求初始可行解，求得的初始解，如表3-21所示。表3-21一行一列，在行中填入，在列中填入“。令=0,按照量=(J∈B)求出所有的“i和V,并依據(jù)表3-22表3-25由表3-22可知，所有空格處的檢驗(yàn)數(shù)均為非負(fù)。所以，表3-21中的運(yùn)輸方案即為此問題的最優(yōu)調(diào)運(yùn)方案，最小運(yùn)價(jià)為90。由于非基變量的檢驗(yàn)數(shù)中=所以該運(yùn)輸問題(4)解表3-14由于表3-14中產(chǎn)大于銷，因此需要增添一個(gè)假想的銷地“己”,其運(yùn)價(jià)為0,其銷量為40,如表3-23所示。表3-23第一步：用伏格爾法求初始可行解，求得的初始解，如表3-24所示。甲乙丙丁戊己123405第二步：用位勢法進(jìn)行最優(yōu)解的判斷。在對(duì)應(yīng)于表3-24的數(shù)字格處填入單位運(yùn)價(jià)，并增加一行一列，在行中填入V,在列中填入ü:。令Y=0,按照u:和V,并依據(jù)0,=c-(u+v,)iEN)計(jì)算所有空格處的檢驗(yàn)數(shù)，計(jì)算結(jié)果如表3-25所示。在表3-25中，。所以，表3-24中的運(yùn)輸方案不是此問題的最優(yōu)調(diào)運(yùn)方案，需從表3-25中的空格(3,1)出發(fā)點(diǎn)作一閉回路，并對(duì)閉回路上的點(diǎn)進(jìn)行正負(fù)編號(hào)，如表3-26表3-26運(yùn)運(yùn)甲乙丙丁戊己量12345由表3-26可知，調(diào)入量為0,按閉回路上的正、負(fù)號(hào)，加上或減去調(diào)入量。調(diào)整后的調(diào)運(yùn)方案，如表3-27所示。表3-27第四步：重復(fù)第二、三步，得到新的調(diào)運(yùn)方案，如表3-28所示。表3-28對(duì)表3-28中給出的調(diào)運(yùn)方案，再用位勢法進(jìn)行檢驗(yàn)，如表3-29所示。表3-29位價(jià)運(yùn)價(jià)甲乙西T戊己1280602M03063M0047805535036由表3-29可知，所有空格處的檢驗(yàn)數(shù)均為非負(fù)。所以，表3-28中的運(yùn)輸方案即為此問題的3.4已知運(yùn)輸問題的產(chǎn)銷平衡表、單位運(yùn)價(jià)表及最優(yōu)調(diào)運(yùn)方案分別見表3-30和表3-31,試表3-30表3-31(1)從A?→B?的單位運(yùn)價(jià)=在什么范圍變化時(shí)，上述最優(yōu)調(diào)運(yùn)方案不變?(2)從A?→B?的單位運(yùn)價(jià)=變?yōu)楹沃禃r(shí)，有無窮多最優(yōu)調(diào)運(yùn)方案?除表3-30中方案外，解：(1)因?yàn)?，?dāng)以單位運(yùn)價(jià)表計(jì)算的基變量檢驗(yàn)數(shù)為0,且非基變量檢驗(yàn)數(shù)為非負(fù)時(shí)，調(diào)運(yùn)方案不變。所以，假設(shè)三未知，對(duì)表3-30中的最優(yōu)調(diào)運(yùn)方案，利用位勢法計(jì)算非基變量的檢驗(yàn)數(shù)，如表3-32所示。表3-32表3-37計(jì)算得，當(dāng)廠時(shí)，表3-30給出的最優(yōu)方案不變。(2)當(dāng)存在某非基變量的檢驗(yàn)數(shù)為0時(shí)，有無窮多最優(yōu)解。假設(shè)C24未知，利用位勢法計(jì)算所有非基變量的檢驗(yàn)數(shù)，如表3-33所示。表3-33可得,所以當(dāng)C24變?yōu)?7時(shí)，此問題有無窮多最優(yōu)調(diào)運(yùn)方案。以表3-34表3-35預(yù)計(jì)售出后的利潤(元/套)也不同，詳見表3-36。請(qǐng)幫助該公司確表3-36解：用10減去利潤表上的數(shù)字，使之變成一個(gè)運(yùn)輸問題，如表3-37所示。利用伏格爾法求出表3-37運(yùn)輸問題的初始解，求解結(jié)果見表3-38。利用位勢法求出表3-38中各空格的檢驗(yàn)數(shù)，如表3-39。表3-39整。利用閉回路法進(jìn)行調(diào)整，結(jié)果如表3-40所示。表3-40利用位勢法求出表3-40中各空格的檢驗(yàn)數(shù)，如表3-41所示。表3-41由表3-41可知，所有空格處的檢驗(yàn)數(shù)均為非負(fù)。所以，表3-40中的運(yùn)輸方案即為此問題的最優(yōu)調(diào)運(yùn)方案，最小運(yùn)價(jià)為72000元。3.6甲、乙、丙三個(gè)城市每年需要煤炭分別為：320、250、350萬噸，由A、B兩處煤礦負(fù)運(yùn)價(jià)(萬元/萬噸)見表3-42。由于需大于供，經(jīng)研究平衡決定，甲城市供應(yīng)量可減少0～30萬噸，乙城市需求量應(yīng)全滿足，丙城市供應(yīng)量不少于270萬噸。試求將供應(yīng)量分配完又使總年煤炭總供應(yīng)量為850萬噸?？梢姽┥儆谛瑁侍摂M一個(gè)產(chǎn)地煤礦C,其供應(yīng)量為70萬噸，由題意可構(gòu)造如表3-43的運(yùn)價(jià)表。問題變?yōu)榍蠼獗?-43的最優(yōu)調(diào)運(yùn)方案。表3-43第一步：用伏格爾法求初始可行解，求得的初始解，如表3-44所示。表3-44第二步：用位勢法進(jìn)行最優(yōu)解的判斷。在對(duì)應(yīng)于表3-44的數(shù)字格處填入單位運(yùn)價(jià)，并增加表3-45由表3-45可知，所有空格處的檢驗(yàn)數(shù)均為非負(fù)。所以，表3-44中的運(yùn)輸方案即為此問題的最優(yōu)調(diào)運(yùn)方案，最小運(yùn)價(jià)為14650萬元。3.7某造船廠根據(jù)合同要從當(dāng)年起連續(xù)三年末各提供三艘規(guī)格型號(hào)相同的大型客貨輪，已知該廠在三年內(nèi)生產(chǎn)大型客貨輪的能力及每艘客貨輪的成本如表3-46所示。已知加班生產(chǎn)時(shí)，每艘客貨輪成本比正常生產(chǎn)時(shí)高出70萬元。又知造出來的客貨輪如當(dāng)年不交貨，每艘每積壓一年造成積壓損失為40萬元。在簽訂合同時(shí)，該廠已儲(chǔ)存了兩艘客貨生產(chǎn)量，使在滿足上述各項(xiàng)要求的情況下，總的生產(chǎn)解：設(shè)F為第1年的正常生產(chǎn)能力，F(xiàn)為第1年的加班生產(chǎn)能力；為第「年的需求訂貨，S為因積壓而產(chǎn)生的供貨能力。因?yàn)楫a(chǎn)大于銷，的運(yùn)價(jià)表。問題變?yōu)榍蠼獗?-47的最優(yōu)調(diào)運(yùn)方案。表3-47單位：千萬元第一步：用伏格爾法求初始可行解，求得的初始解，如表3-48所示。從表3-49中的空格==出發(fā)作一閉回路，利用閉回路法進(jìn)行調(diào)整，得到的結(jié)果如表3-50繼續(xù)重復(fù)第二、三步，再一次得到新的調(diào)運(yùn)方案，如表3-52所示。表3-52利用位勢法計(jì)算表3-52中空格處的檢驗(yàn)數(shù)，如表3-53所示。表3-532000M0MAMoMMM0s0v由表3-53可知，所有非基變量的檢驗(yàn)數(shù)均為非負(fù)。所以，表3-52中的解為最優(yōu)解，最小運(yùn)價(jià)為4730萬元。由于存在一個(gè)非基變量的檢驗(yàn)數(shù)為0,所以此問題有無窮多最優(yōu)解。即，該廠第1年生產(chǎn)2艘船供應(yīng)第1年和第2年；第2年正常生產(chǎn)4艘，其中2艘船供應(yīng)給第2年，另2艘儲(chǔ)備；第3年正常生產(chǎn)1艘供應(yīng)給第3年，加班生產(chǎn)3艘再供應(yīng)給第3年。另有2艘船是原先儲(chǔ)備下來而供應(yīng)給第1年。這樣可以使得總的生產(chǎn)費(fèi)用加積壓損失最少。4.1若用以下表達(dá)式作為目標(biāo)規(guī)劃的目標(biāo)函數(shù)，試述其邏輯是否正確?解：(1)不正確。當(dāng)要求==時(shí)，問題變?yōu)榍笠籉或一=最大，即超過目標(biāo)值越大越好，或未達(dá)到目標(biāo)值越大越好，這兩項(xiàng)是相反方向的，所以即表示未達(dá)到目標(biāo)值越大越好。圖4-2從圖4-2中可以看到，在考慮具有P1的目標(biāo)實(shí)現(xiàn)后，x:x2的取值范圍為OADFO;考慮P?的目標(biāo)要求實(shí)現(xiàn)后，x:x2的取值范圍為E=;考慮-三的目標(biāo)要求實(shí)現(xiàn)后，x?:x?的取值范圍為BE;考慮=的目標(biāo)要求實(shí)現(xiàn)時(shí)，因?yàn)槿臋?quán)系數(shù)大于=的權(quán)系數(shù)，故考慮,所以點(diǎn)E為滿意解，其坐標(biāo)為,即滿意解是一解：令各偏差變量為0,作出所有的約束直線，并標(biāo)示出各偏差量增加對(duì)約束直線的影響，如圖4-3所示。圖4-3的目標(biāo)要求實(shí)現(xiàn)時(shí)，要實(shí)現(xiàn)一|==|,從圖中可以看出，只有B點(diǎn)可使-三最小，所以B點(diǎn)為滿足目標(biāo)規(guī)劃問題的滿意解，其坐標(biāo)為一==|,即滿意解是|==。4.3用單純形法求解以下目標(biāo)規(guī)劃問題的滿意解。解：在第三個(gè)約束條件中加入松弛變量考，該目標(biāo)規(guī)劃的標(biāo)準(zhǔn)型為：建立初始單純形表，在表中將檢驗(yàn)數(shù)列按優(yōu)先因子個(gè)數(shù)排成兩行，并采用單純形法進(jìn)行進(jìn)一步迭代，如表4-1所示。表4-1c00000b2Z101005000108211000080000010020051000006103010020000061000200x0100110003001一00000001001010000100001000101/600000001001010由表4-1可知，為該目標(biāo)規(guī)劃的滿意解。由于非基變量三的檢驗(yàn)數(shù)為0,所以該問題有多重解。進(jìn)一步迭代得另一滿意解為解：建立初始單純形表，在表中將檢驗(yàn)數(shù)列按優(yōu)先因子個(gè)數(shù)排成4行，并采用單純形法進(jìn)行進(jìn)一步迭代，如表4-2所示。表4-2表4-2由表4-2可知，為該目標(biāo)規(guī)劃的滿意解。解：建立初始單純形表，在表中將檢驗(yàn)數(shù)列按優(yōu)先因子個(gè)數(shù)排成兩行，并采用單純形法進(jìn)行進(jìn)一步迭代，如表4-3所示。表4-34.4以下為目標(biāo)規(guī)劃問題，試求以下問題。(1)用單純形法求這問題的滿意解；(2)若目標(biāo)函數(shù)變?yōu)榻庥惺裁醋兓?(3)若第一個(gè)目標(biāo)約束的右端項(xiàng)改為120,這時(shí)原滿意解又有什么變化?解：(1)建立初始單純形表，在表中將檢驗(yàn)數(shù)列按優(yōu)先因子個(gè)數(shù)排成三行，并采用單純形法進(jìn)行進(jìn)一步迭代，求解過程如表4-4所示。表4-4由表4-4可知，為該目標(biāo)規(guī)劃的滿意解。(2)將變化的優(yōu)先等級(jí)直接反代入表4-4的最終單純形表中，再計(jì)算各變量的檢驗(yàn)數(shù)，如表4-5所示。表4-5表4-5目標(biāo)函數(shù)變化后，各檢驗(yàn)數(shù)均為非負(fù)，所以滿意解不變，仍為o(3)首先計(jì)算：將一的值代入表4-4中最終單純形表的b列中，并進(jìn)一步迭代，如表4-6所示。表4-64.5某商標(biāo)的酒是用三種等級(jí)的酒兌制而成。若這三種等級(jí)的酒每天供應(yīng)量和單位成本為：設(shè)該種牌號(hào)酒有三種商標(biāo)(紅、黃、藍(lán)),各種商標(biāo)的酒對(duì)原料酒的混合比及售價(jià)，見表4-7。決策者規(guī)定：首先必須嚴(yán)格按規(guī)定比例兌制各商標(biāo)的酒；其次是獲利最大；再次是紅商標(biāo)的酒每天至少生產(chǎn)2000kg,試列出數(shù)學(xué)模型。表4-7解：設(shè)以分別為兌制紅、黃、藍(lán)三種商標(biāo)的酒時(shí)第1種等級(jí)的酒的用量，由題意可建立如下數(shù)學(xué)模型：可根據(jù)如下模型求出：5.1對(duì)下列整數(shù)規(guī)劃問題，問用先解相應(yīng)的解：在該線性規(guī)劃問題的約束條件中分別加入松弛變量≥,,化為標(biāo)準(zhǔn)型先不考慮上述模型中的整數(shù)約束，利用單純形法進(jìn)行求解，如表5-1所示。表5-1此時(shí)的最優(yōu)解為,最優(yōu)目標(biāo)值時(shí)均為非可行解.用分支定界法進(jìn)一步求解此整數(shù)規(guī)劃.求得B?的最優(yōu)解為max于是得到l,再將B?分解成兩個(gè)子問題：求得三的最優(yōu)解為max面表5-2 B?已求得整數(shù)解，則可取為,故1,對(duì)于B?而言，繼續(xù)分解已無意義，可舍去。繼續(xù)將B?分解為兩個(gè)子問題：B?無可行解，舍去。求得B?的最優(yōu)解所以，得到最優(yōu)解,與用舍去法得到的最優(yōu)解一致。所以，用先解相應(yīng)的線性規(guī)劃然后湊整的辦法能得到最優(yōu)整數(shù)解。解：在該線性規(guī)劃問題的約束條件中分別加入松弛變量x::x4,并化為標(biāo)準(zhǔn)型先不考慮上述模型中的整數(shù)約束，利用單純形法進(jìn)行求解，如表5-2所示。此時(shí)的最優(yōu)解為時(shí)，為非可行解。對(duì)該最優(yōu)解進(jìn)行湊整，當(dāng)湊整為時(shí)，為非可行解。用分支定界法進(jìn)一步求解此整數(shù)規(guī)劃。記一，因?yàn)閄=(0.0.0.0)為可行解，所以1。將原問題分解為兩個(gè)求得B?的最優(yōu)解求得B?的最優(yōu)解B?已求得整數(shù)解，則可取故一,繼續(xù)將B?分解為兩個(gè)子問題：求得B?的最優(yōu)解減去B3、B?枝，從而最優(yōu)整數(shù)解5.2用分支定界法解以下問題。解：在該線性規(guī)劃問題的約束條件中分別加入松弛變量：x4,化為標(biāo)準(zhǔn)型先不考慮模型中的整數(shù)約束，利用單純形法求解，過程如表5-3所示。表5-3子問題：求得B?的最優(yōu)解求得B?的最優(yōu)解B?:maxz=x+x?B?:maxz=x+x?求得B?最優(yōu)解,或者為整數(shù)解，所以可取B?:maxz=x+x?因?yàn)?，減去B3分枝，得最優(yōu)整數(shù)解為解：(1)在該線性規(guī)劃問題的約束條件中分別加入松弛變量.x4,化為標(biāo)準(zhǔn)型先不考慮上述模型中的整數(shù)約束，利用單純形法進(jìn)行求解，如表5-4所示。表5-4最優(yōu)目標(biāo)值由表5-4中最終單純形表可得變量間的關(guān)系式：將系數(shù)和常數(shù)項(xiàng)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和，移項(xiàng)將系數(shù)和常數(shù)項(xiàng)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和，移項(xiàng)要求將該約束條件加入到表5-4的最終單純形表中，并進(jìn)行進(jìn)一步求解，如表5-5所示。表5-5由于x?:x?已為整數(shù)，所以最優(yōu)解為(2)在該線性規(guī)劃問題的約束條件中分別加入松弛變量及人工變量5,化為標(biāo)準(zhǔn)型maxz=3x-x?-Mx?先不考慮模型中的整數(shù)約束，利用單純形法進(jìn)行求解，如表5-6所示。表5-66一(2)≤0加入松弛變量，得到切割方程：將該約束條件加入到表5-6的最終單純形表中，并進(jìn)一步求解，如表5-7所示。表5-7從表5-7中得到的是非整數(shù)解，需要進(jìn)一步求解。按照上述步驟，再次加入切割方程并進(jìn)行求解，最終求得：5.4某城市的消防總部將全市劃分為11個(gè)防火區(qū)，設(shè)有4個(gè)消防(救火)站。圖5-1表示各防火區(qū)域與消防站的位置，其中①②③④表示消防站，1、2、.….、11表示防火區(qū)域。根據(jù)歷史資料證實(shí)，各消防站可在事先規(guī)定的允許時(shí)間內(nèi)對(duì)所負(fù)責(zé)的地區(qū)的火災(zāi)予以消滅。圖中虛線即表示各地區(qū)由哪個(gè)消防站負(fù)責(zé)(沒有虛線連接，就表示不負(fù)責(zé))?，F(xiàn)在總部提出：可否減少消防站的數(shù)目，仍能同樣負(fù)責(zé)各地區(qū)的防火任務(wù)?如果可以，應(yīng)當(dāng)關(guān)閉哪個(gè)?圖5-1提示：對(duì)每個(gè)防火站定義一個(gè)0-1變量=,令然后對(duì)每個(gè)防火區(qū)域列一個(gè)約束條件。于是，可建立如下數(shù)學(xué)模型：由條件②,④,⑨可判定,分析可知(1,0,1,1)為問題的一個(gè)可行解，此一==。假設(shè)可以減少一個(gè)消防站，即增加約束條件。通過單純形法計(jì)算可知，只有(1,0,1,1)為可行解，所以可關(guān)閉消防站②。5.5在有互相排斥的約束條件的問題中，如果約束條件是(≤)型的，我們可用加以一=項(xiàng)(F是0-1變量，M是很大的常數(shù))的方法統(tǒng)一在一個(gè)問題中。如果約束條件是(≥)型的，解：在互相排斥的約束條件問題中，如果約束件右端減去一，其中F是0-1變量，M是充分大的正數(shù)，且5.6解下列0-1規(guī)劃問題。解：通過觀察可知(0,0,1)T為可行解，相應(yīng)的z=2,故增加約束條件進(jìn)行枚舉及選擇，如表5-8所示。表5-8表5-10由表5-8可判定，最優(yōu)解為解：通過觀察可知(0,0,0,1)為可行解，相應(yīng)的z=4,故增加約束條件，進(jìn)行枚舉及選擇，如表5-9所示。由表5-9可判定最優(yōu)解為5.7有4個(gè)工人，要指派他們分別完成4項(xiàng)工作，每個(gè)人做各項(xiàng)工作所消耗的時(shí)間如表5-10所示。問指派哪個(gè)人去完成哪項(xiàng)工作，可使表7-1因?yàn)閙=3<n=4,指派不成功，轉(zhuǎn)入下一步。第三步：做最少的直線覆蓋所有的0元素，并進(jìn)行再指派第6章無約束問題第7章約束極值問題7.1在某一試驗(yàn)中變更條件F四次，測得相應(yīng)的結(jié)果Vi見表7-1,試為這一試驗(yàn)擬合一條直7.2有一線性方程組如下現(xiàn)欲用無約束極小化方法求解，試建立數(shù)學(xué)模型并說明計(jì)算原理。解：(1)建立數(shù)學(xué)模型：(2)以梯度法為例解無約束極值問題，計(jì)算原理如下：②或者對(duì)三求導(dǎo)，并令等于0,則可求得最佳步長三。以②為判斷準(zhǔn)則，重復(fù)迭代，直至滿足精度為止。7.3試判定下述非線性規(guī)劃是否為凸規(guī)劃。 從而可知一為嚴(yán)格凸函數(shù)，==為凸函數(shù)，為凹函數(shù)，所以這不是一個(gè)凸規(guī)劃分別計(jì)算,,海塞矩陣的行列式:從而可知f(X)為嚴(yán)格凸函數(shù)，g(X)為凹函數(shù)，8?(X)為凸函數(shù)，所以這不是一個(gè)凸規(guī)劃7.4試用斐波那契法求函數(shù)在區(qū)間[0,10]上的極小點(diǎn)，要求縮短后的區(qū)間長度不大于原區(qū)間長度的8%。用斐波那契法求解：(1)由=,可確定試點(diǎn)的個(gè)數(shù)一底，這里取一同。(3)由于,故取一(4)依次進(jìn)行迭代，得最終區(qū)間為L,近似極小點(diǎn)為=,近似7.5試用0.618法重做習(xí)題7.4,并將計(jì)算結(jié)果與用斐波那契法所得計(jì)算結(jié)果進(jìn)行比較?？纱_定試點(diǎn)的個(gè)數(shù)一F,計(jì)算得最終區(qū)間為比較，用0.618法求解，試點(diǎn)數(shù)n值大一些，但求值更接近于精確值。7.6試用最速下降法求解,選初始點(diǎn)一l,要求做三次迭代，并驗(yàn)證相鄰兩步的搜索方向正交。解：,用最速下降法迭代計(jì)算的過程如表7-2所示。表7-2迭代方向正交。7.7試用最速下降法求函數(shù)行計(jì)算，求出極大點(diǎn)，再以為初始點(diǎn)進(jìn)為初始點(diǎn)進(jìn)行兩次迭代，最后比較從上述兩個(gè)不同初始點(diǎn)出發(fā)的尋優(yōu)過程。 (1)以x?=(0.0)2為初始點(diǎn)，取精度一間，則,所以一用為極小點(diǎn)，即一日為f(X)的極大點(diǎn)。(2)以x=(0,1)為初始點(diǎn)，取精度8=0.1,采用相同的方法進(jìn)行兩次迭代，有：兩次的步長：;兩次迭代的結(jié)果：比較：一般的，二元二次凸函數(shù)的等值線是橢圓，橢圓的圓心即為極小值，(1)中負(fù)梯度方向直指圓心，且初值點(diǎn)與圓心在同一水平直線上，所以收斂很快；(2)中的搜索路徑呈直角鋸齒狀，所以收斂較慢。7.8試用牛頓法重解習(xí)題7.6。因?yàn)閒(X)為二次函數(shù)，所以一自，7.9試用牛頓法求解,取初始點(diǎn),用最佳步長進(jìn)行迭代。然后采用固定步長一國，觀察迭代情況，并加以分析說明。解：令,要求f(X)的極大點(diǎn)即求F(X)的極小點(diǎn)。仿照7.8的即極大點(diǎn)為由上可知，步長λ=1。故采用固定步長λ=1與采用最佳步長情形一致。。7.10試用共軛梯度法求二次函數(shù)的極小點(diǎn)，此處所以因此因此,即二為極小點(diǎn)。7.11令為一組A共軛向量(假定為列向量),A為對(duì)稱正定矩陣，試證用左乘上式，并且由共軛關(guān)系可知：故得證。 7.12試用變尺度法解,取初始點(diǎn),要求近 似極小點(diǎn)處梯度的模不大于0.5。解：取初始點(diǎn)可得,于是又因?yàn)?所以為近似極小點(diǎn)。7.13試以為初始點(diǎn)，使用(1)最速下降法(迭代4次);(2)牛頓法；(3)變尺度法。解：(1)用最速下降法：圖7-1(2)牛頓法：所以極小點(diǎn)為。其尋優(yōu)過程，如圖7-2所示。圖7-2(3)變尺度法：其尋優(yōu)過程，如圖7-3所示。圖7-37.14試用步長加速法(模矢法)求下述函數(shù)的極小點(diǎn)，初始點(diǎn),步長為。并繪圖表示整個(gè)迭代過程。表7-31,此時(shí)應(yīng)在點(diǎn)=附近搜索，縮小步長以求得符合精度要求的結(jié)果。所以，最優(yōu)解為一其迭代過程如圖7-4所示。圖7-47.15分析非線性規(guī)劃在以下各點(diǎn)的可行下降方向(使用教材中式(7-6)o并繪圖表示各點(diǎn)可行下降方向的范圍。解：將原非線性規(guī)劃改寫為：目標(biāo)函數(shù)和約束條件的梯度為：(1),起作用的約束為8:(X),所以則有所以，存在可行下降方向，如圖7-5所示。圖7-5(2),起作用的約束為8(X)和8?(X),所以令D=(x,y)2,則有該方程組無解，所以不存在可行下降方向，如圖7-6所示。圖7-6(3),起作用的約束為8?(X),所以所以，存在可行下降方向，如圖7-7所示。圖7-77.16試寫出下述二次規(guī)劃的K-T條件：解：原二次規(guī)劃可改寫為：設(shè)為K-T點(diǎn)，且與點(diǎn)起作用約束的各梯度線性無關(guān)，假設(shè)8?(X),g?(X)都是起作用7.17試寫出下述非線性規(guī)劃問題的K-T條件并進(jìn)行求解：解：(1)原非線性規(guī)劃問題可改寫成：目標(biāo)函數(shù)和約束函數(shù)的梯度為：對(duì)第一、二個(gè)約束條件分別引入廣義拉格朗日乘子=和-=,并令K-T點(diǎn)為，則有K-T為解該方程組，考慮以下幾種情形：由于該非線性規(guī)劃問題不是凸規(guī)劃，且K-T條件只是確定某點(diǎn)為最優(yōu)點(diǎn)的必要條件，而非充分條件，所以1或5不一定是全局極小點(diǎn)。(2)原非線性規(guī)劃問題可改寫成：目標(biāo)函數(shù)和約束函數(shù)的梯度為：對(duì)第一、二個(gè)約束條件分別引入廣義拉格朗日乘子/和/2,并令K-T點(diǎn)為X,則有K-T為解該方程組，考慮以下幾種情形：由于該非線性規(guī)劃問題是凸規(guī)劃，所以—:是該問題的全局極小點(diǎn)。7.18試找出非線性規(guī)劃問題的極大點(diǎn)，然后寫出其K-T條件，這個(gè)極大點(diǎn)滿足K-T條件嗎?試加以說明。解：原非線性規(guī)劃問題可改寫成：(1)找極大點(diǎn)將第一、二個(gè)約束條件相加得：即一=。又由第三個(gè)約束條件知，廟，約束條件得，以極大點(diǎn)為X*=(1,2)T,由于點(diǎn)X*起約束作用的梯度為7g?(X),▽g?(X”),它們線性相關(guān)，故點(diǎn)X=(1,2)T不是正則點(diǎn)。把極大點(diǎn)X*=(1,2)代入K-T條件，可求得。所以當(dāng)，時(shí)，極大點(diǎn)X?=(1,2)T滿足K-T條件。7.19試解二次規(guī)劃解：上述二次規(guī)劃問題可改寫為下列形式：顯然，目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)，并且因?yàn)樾∮?,引入人工變量一并在前面取負(fù)號(hào)，得到如下的線性規(guī)劃模型：7.20試用可行方向法求解取精度三而取搜索方向則w:(X)=(-1,-1)T,W?(X)=(-1,X?不是近似極小點(diǎn)。又一令則構(gòu)成下述線性規(guī)劃問題：為便于用單純形法求解，令從而得到其最優(yōu)解為：7.21試用SUMT外點(diǎn)法求解并求出當(dāng)罰因子等于1和10時(shí)的近似解。所以，當(dāng)7.22試用SUMT外點(diǎn)法求解,得in)的解為日=,,為最優(yōu)解。7.23試用SUMT內(nèi)點(diǎn)法求解解：構(gòu)造障礙函數(shù)則當(dāng)一F時(shí)，又由約束條件一，所以最優(yōu)解為7.24試用SUMT內(nèi)點(diǎn)法求解解：原問題可改寫為：第8章動(dòng)態(tài)規(guī)劃的基本方法8.1試分析《運(yùn)籌學(xué)》教材第8章第1節(jié)之例2問題中：(1)階段的劃分；(2)狀態(tài)變量和它的取值范圍；(3)決策變量和它的允許決策集合；(4)狀態(tài)轉(zhuǎn)移方程；(5)指標(biāo)函數(shù)與最優(yōu)指標(biāo)函數(shù)。解：(1)階段的劃分：共劃分為五個(gè)階段，階段變量k=1,2,3,4,5。(2)狀態(tài)變量為=,它表示第k年初完好的機(jī)器數(shù)量取值范圍，即(3)決策變量為三，它表示第k年度中高負(fù)荷下分配生產(chǎn)的機(jī)器數(shù)；De(s)表示第k階段從出發(fā)的允許決策集合，則(4)狀態(tài)轉(zhuǎn)移方程為開始到第5年結(jié)束的總產(chǎn)量的最大值，即8.2設(shè)某工廠自國外進(jìn)口一部精密機(jī)器，由機(jī)器制造廠至出口港有三個(gè)港口可供選擇，而進(jìn)口港又有三個(gè)可供選擇，進(jìn)口后可經(jīng)由兩個(gè)城市到圖8-1解：設(shè)階段變量,依次表示4個(gè)階段選擇路線的過程；狀態(tài)變量表示第k階段fe(sk)表示從初可能處的位置；決策變量=表示第k階段初可能選擇的路線；最優(yōu)值函數(shù)第k階段點(diǎn)5開始至終點(diǎn)E的最少運(yùn)費(fèi)，則有;圖8-2點(diǎn)A到第k階段狀態(tài)的最短距離，則有