最優(yōu)化理論與方法(線性部分)思考題與作業(yè)要求 - 用于合并

1、最優(yōu)化理論與方法（線性部分）思考題1. 就你學(xué)過的運籌學(xué)問題，寫出能夠建立線性規(guī)劃模型的問題，并舉例（建立模型）。以下四種食物1、2、3、4，依次售價為50、20、30、80，而我們?nèi)梭w每天需攝取至少500卡路里，6盎司巧克力，10g糖以及8g脂肪，具體成分如下，飲食的營養(yǎng)價值食物類型卡路里巧克力（盎司）糖(盎司)脂肪（盎司）1.巧克力糖4003222.巧克力冰淇淋2002243.可口可樂1500414.蛋糕500045要求：建立一個以最小成本滿足每天營養(yǎng)需求的線性規(guī)劃模型。模型如下：minz=50x1+20x2+30x3+80x4s.t. 400x1+200x2+150x3+500x4500

2、 3x1 + 2x2 6 2x1 + 2x2 + 4x3 + 4x4 102x1 + 4x2 + 1x3 + 5x4 8 xi0(i=1，2，3，4)2. 舉例（說明問題、建立模型）論述線性規(guī)劃在交通、運輸、物流和安全管理中的應(yīng)用。答：現(xiàn)在物流業(yè)面臨的新問題是： 認定所給問題確實是一個線性規(guī)劃問題； 把它建立起線性數(shù)學(xué)模型； 并能夠完成具體實務(wù)的全部工作。第一個問題實質(zhì)上是具體實務(wù)究竟?jié)M足什么條件才能應(yīng)用線性規(guī)劃的方法。一般地說，必須有：一定要滿足將目標表為最小化或最大化的要求；一定要有達到目標的不同方法，且必須要有選擇的可能性；要求的目標是有限制條件的；必須將約

3、束條件用數(shù)學(xué)表示為線性等式或線性不等式，并將目標函數(shù)化為線性函數(shù)。運籌學(xué)中的指派問題、最短路問題，最小費用流問題可轉(zhuǎn)化為運輸問題或轉(zhuǎn)運問題。設(shè)某種物品有 m 個產(chǎn)地 A1，A2，.，Am,各產(chǎn)地的產(chǎn)量分別是 a1，a2，am；有 n 個銷地 B1，B2，.，Bn；各銷地的銷量分別為b1，b2，bn ，假定從 產(chǎn)地 Ai（i=1，2，m） 向銷地 Bi（j=1，2，n） 運輸單位物品的運價為Cij，若用表示從到的運輸量，則在產(chǎn)銷平衡條件下，總費用最低的數(shù)學(xué)模型為minz=i=1

4、mj=1ncijxiji=1mxij=bj，j=1，2，nj=1nxij=ai，i=1，2，mxij0以下是運輸問題的數(shù)學(xué)模型，包含 m×n 個變量，(m+n)個約束方程，其系數(shù)矩陣的結(jié)構(gòu)比較松散，且特殊。3. 對一個用單純形法求解不會產(chǎn)生循環(huán)（且能求得最優(yōu)解）的n個變量m個約束的線性規(guī)劃問題，估算一下基本計算次數(shù)。答：即說明約束系數(shù)矩陣為m×n 的矩陣，且滿足檢驗數(shù)，如有無窮多的最優(yōu)解還有存在某個非基變量。其基本計算次數(shù)為：4. 簡述線性規(guī)劃求解算法的改進歷史。答：針對一般線性規(guī)劃問題的求解方法（單純形法 改進單純形法 對偶單純形法），到后來特殊的線性規(guī)劃問題求解算法（表

5、上作業(yè)法）5. 證明課本（清華版運籌學(xué)（第三版）2.5題。證明：下面用矩陣形式將原問題表示為：（1） max z1=CXAXbX0設(shè)其可行解為X1，其對偶問題的最優(yōu)解為Y1=(y1*，ym*)。（2） max z2=CXAXb+kX0設(shè)其可行解為X2，其對偶問題的最優(yōu)解為Y2。問題1的對偶問題為min =YbYACY0問題2的對偶問題為min =Y(b+k)YACY0由此可見，問題1的對偶問題的約束條件與問題2的對偶問題的約束條件相同，從而問題1的對偶問題的最優(yōu)解Y1=(y1*，ym*)一定是問題2的對偶問題的可行解。而問題2的對偶問題的最優(yōu)解為Y2，故Y2b+kY1b+k=Y1b+Y1k=Y

6、1b+i=1mkiyi*。因為原問題與對偶問題的最優(yōu)函數(shù)值相等，故有max z2max z1+i=1mkiyi*6. 有人說：“原問題有多重解（多個最優(yōu)解），對偶問題一定也有多重解”，此話是否正確？請舉一算例。答：這句話是錯誤的。對偶問題的最優(yōu)解只有在線性規(guī)劃中此問題才是對的，如果是非線性規(guī)劃就不對了。舉例：任意一個問題有多重解非線性規(guī)劃均滿足。7. D-W分解算法適合那種類型的線性規(guī)劃問題？請舉一算例。答：D-W分解算法適合按照下列方法分解約束條件和變量：集合1中的約束條件只涉及變量集合1中的變量。集合2中的約束條件只涉及變量集合2中的變量。集合k中的約束條件只涉及變量集合k中的變量。集合k

7、+1中的約束條件可以涉及任何變量。集合k+1中的約束條件稱為中心約束條件。適合按照以上方式分解的LP。算例：一家公司在兩家工廠生產(chǎn)兩種鋼材。工廠1每天可以使用12噸煤，工廠2每天可以使用15噸煤；煤不能在兩工廠之間運輸，工廠1每天可以使用10小時的鼓風(fēng)爐時間，工廠2每天可以使用4小時的鼓風(fēng)爐時間，鐵礦位于兩家工廠之間，每天提供80噸鐵，鋼材1每噸售價170美元，鋼材2每噸售價160美元。所有鋼材都送給一個客戶；從工廠1運一噸鋼材需要80美元，工廠2運一噸鋼材需要100美元。假設(shè)運輸成本是唯一的可變成本，表述并求解一個使該公司利潤（收入運輸成本）最大的LP。公司的資源要求產(chǎn)品需要的鐵（t）需要的

8、煤(t)需要鼓風(fēng)爐時間(h)工廠1鋼材1832工廠1鋼材2611工廠2鋼材1731工廠2鋼材2521x1=工廠1每天生產(chǎn)的鋼材1的噸數(shù)x2=工廠1每天生產(chǎn)的鋼材2的噸數(shù)x3=工廠2每天生產(chǎn)的鋼材1的噸數(shù)x4=工廠2每天生產(chǎn)的鋼材2的噸數(shù)LP:變量集合1：x1和 x2工廠1 的變量變量集合2：x3和 x4工廠2 的變量約束條件集合1：1和（2）工廠1 的約束條件約束條件集合2：3和（4）工廠2 的約束條件約束條件集合3：（5）工廠1 的約束條件8. 何謂“原始-對偶”單純形法？請舉一算例。答：應(yīng)用對偶原理求解原始線性規(guī)劃的一種方法在原始問題單純形表格上進行對偶處理。線性規(guī)劃問題：添加松弛變量以后

9、的標準型，再將標準型中燈飾兩邊乘以-1，則以上問題轉(zhuǎn)化為：然而在有些問題中，我們很容易找到初始基本解，因此使用對偶單純形法求解線性規(guī)劃問題是有一定條件的，其條件是： (1) 單純形表的b列中至少有一個負數(shù). (2) 單純形表中的基本解都滿足最優(yōu)性檢驗. 對偶單純形法與原始單純形法相比有兩個顯著的優(yōu)點： (1) 初始解可以是不可行解，當(dāng)檢驗數(shù)都非正時，即可進行基的變換，這時不需要引入人工變量，因此簡化了計算. 9. 何謂有界變量的線性規(guī)劃問題？如何求解？請舉一算例。答：實際運用中的線性規(guī)劃問題,其決策變量具有上下界限

10、的限制。至于其求解算法，以先 轉(zhuǎn)化為標準形式的線性規(guī)劃問題,然后按照單純形方法進行求解，或者是有界變量單純形法。以下是一具體算例（基線算法）：列出母表：X1X2X3X4X5RHS2-1000v11110102-1-2018取初始基本可行解（0，0，-1，11，6），初始解x1和x2中都取其對應(yīng)下界,我們可將x1和x2作為下非基變量，可將x3作為進基，得BL表，X1X2X3X4X5RHS 2-3100v-1v2-1401010-vv106-70018+2vv-4ll其解為-1，2，選取2為旋轉(zhuǎn)主元得到新的BL表：X1X2X3X4X5RHS 1-321200v22v10052121010-v2v1

11、802-3018-vv14lu其對應(yīng)不等式組的解為2,10，此表已為最優(yōu)表，最優(yōu)值max z=10，計算得最優(yōu)解為4，0，2，4，4。10. 何謂線性規(guī)劃的逆問題，分別對“最優(yōu)解的逆線性規(guī)劃問題”和“對目標函數(shù)值的線性規(guī)劃逆最優(yōu)值問題”舉出算例。答：給定線性規(guī)劃問題一個可行但非最優(yōu)的解,要求在某種模的意義下,盡可能少的調(diào)整價值向量,使其成為新問題的最優(yōu)解。最優(yōu)解的逆線性優(yōu)化問題算例：對目標函數(shù)值的線性規(guī)劃逆最優(yōu)值問題算例：11. 對同一優(yōu)化問題，是否存在決策變量一樣但所建模型不一樣的情況？請舉例；是否存在目標函數(shù)中沒有決策變量的最優(yōu)化問題？答：同一優(yōu)化問題存在決策變量一樣但是所建模型不一樣的。

12、處理實際問題時，一般沒有一個唯一正確的模型，而是有多種不同的方案。建模是一個演進過程，從一個初始模型往往需要不斷的完善漸漸演化成一個完整的數(shù)學(xué)模型。舉例：針對港口岸橋調(diào)度問題，最終的目標函數(shù)，我們可以要求總成本最小，亦可要求所有岸橋總行走里程最短。最終建立的模型不一樣。決策變量是建立最優(yōu)化問題模型三要素之一，故不存在目標函數(shù)中沒有決策變量的最優(yōu)化問題。12. 簡述建立線性多目標規(guī)劃的過程，自選一個實際問題，建立模型并用圖解法和單純形法求解。答：主要研究多余一個目標函數(shù)的在給定區(qū)域上的最優(yōu)化。即先確定此規(guī)劃的決策變量，還要引進正、負偏差，以及完善約束條件（絕對約束和目標約束），確定優(yōu)化因子（優(yōu)先等級）與權(quán)系數(shù)，確定目標規(guī)劃的目標函數(shù)，完成最終的線性多目標規(guī)劃。一個生產(chǎn)問題