1、第七章線性規(guī)劃，線性規(guī)劃問題：目標函數(shù)和約束函數(shù)都是線性最優(yōu)化問題。其理論和方法廣泛應(yīng)用于工程管理和經(jīng)濟管理。7.1線性規(guī)劃問題130 7.1.1線性規(guī)劃標準格式130 7.1.2線性規(guī)劃幾何意義131 7.1.3線性規(guī)劃基本術(shù)語132 7.1.4基本特性和基本運算133 7.2單純形137 . 3算法改進138，每生產(chǎn)一臺7 B，產(chǎn)值1萬韓元，在一個車間5天，2個車間2天目前，一個車間有15天，兩個車間有24天。生產(chǎn)組織者安排兩種產(chǎn)品的合理產(chǎn)值，努力獲得最大總產(chǎn)值。解決方案：將a、b的數(shù)量分別設(shè)置為。設(shè)計變量將X=x 1、x 2、目標函數(shù)：約束：線性規(guī)劃問題的常規(guī)格式轉(zhuǎn)換為標準格式(可用文本

2、表達)。一般格式：標準格式：最小化目標、約束右端的非負等式、設(shè)計變數(shù)均為非負。矩陣等效格式：將一般格式轉(zhuǎn)換為標準格式的步驟，如果1目標最大化，則轉(zhuǎn)換為最小化。2在約束中，小于常量的不等式約束通過添加新的非負變量，全部更改為稱為李莞變量的等式約束。3在某些問題上，如果實際情況不要求變量為負，例如，1，最小化目標函數(shù)2，引入松弛變量x 3，x 4，7.1.2線性規(guī)劃幾何意義(例如，6-2:)，但是國家每天分配給牙齒工廠的煤和電力是有限制的。每天最多供應(yīng)56噸，供電最多供應(yīng)45千瓦，詢問牙齒工廠如何安排生產(chǎn)，使牙齒工廠每日產(chǎn)值最大化。問題是在約束條件下查找目標函數(shù)S=8 x 11 y的最大值。根據(jù)約

3、束，圖中的凸面四邊形ABCO可以通過方程組解算將四邊形ABCO的四個頂點坐標計算為a (8，0)、b (5，7)、c (0，9)、o (0，0)=0顯然，其中B點的函數(shù)值最大。也就是說，SMAX=S (5，7)=117是牙齒工廠每天生產(chǎn)5噸甲種產(chǎn)品，乙種產(chǎn)品7噸，日產(chǎn)值最大，最大值為11.7萬元。首先調(diào)查，第二步是獲取牙齒多邊形所有頂點的坐標。然后將這些頂點坐標指定為目標函數(shù)，比較的函數(shù)值。其中，函數(shù)值最大的是最大值。函數(shù)值最小的是最小值、7.1.3線性規(guī)劃基礎(chǔ)術(shù)語、1、可執(zhí)行點和可執(zhí)行字段滿足約束的解決方案2、基準點、標準中的任意n-m變量=0。從剩下的M個中得到的n個變量的解法是基本點?；?/p>

4、本點數(shù)3，基本點滿足非負條件的基本點。4、最好的點是達到目標函數(shù)牙齒最小可能點。5，由基本、基本向量、基本變量和鄭智薰基本變量A中選定的M列線性無關(guān)向量組成的鄭智薰奇異子矩陣(稱為線性規(guī)劃準則)。對應(yīng)于基礎(chǔ)向量的變數(shù)稱為基礎(chǔ)變數(shù)。線性規(guī)劃特性：(1)可執(zhí)行點的集合構(gòu)成了具有與基本可執(zhí)行點等價的頂點的凸多面體凸集(凸多面體)。(2)如果有最好的地方，就必須在凸集的頂點實現(xiàn)。(。示例m=3n=10除x1，3，5以外的0，基本變量基點，基本，因此，要獲得最佳解決方案，不需要找到所有基本可行的解決方案，但使用特定的方法，7.1.4基本特性和基本運算，7-2單純形法是迭代方法。首先，單純形法的基本思想選

5、擇性地采取基本可行點。也就是說，從可執(zhí)行域的一個極點沿可執(zhí)行域的邊界移動到另一個相鄰極點，要求新極點的目標函數(shù)值不低于原始目標函數(shù)值。選擇基本變量和基本變量的原則是，確保所有基本變量滿足非負條件，同時最大限度地降低目標函數(shù)值。所有非基本變量中只有一個變量的值從0開始增加，其他非基本變量的值保持為0。將單純形方法的基本過程、目標函數(shù)和基本變量分別表示為非基本變量，2，單純形方法的算法和迭代過程(1)查找初始可執(zhí)行基礎(chǔ)及其基本可執(zhí)行解決方案(極點)，確定基本變量、非基本變量和基本變量、非基本變量(全部為零)和目標函數(shù)值，并確定目標，(2)在標記為非基本變量的目標函數(shù)表達式(2-12)中，將非基本變

6、量XJ的系數(shù)(或負值)記錄為檢驗數(shù)j。如果J 0，則目標函數(shù)值會隨著非基本變量XJ的值從當前值0開始增加而增加。選定的非基本變量XJ稱為“基本變量”，旋轉(zhuǎn)(3)。如果非基本變量的值增加，則無法增加目標函數(shù)的值。也就是說，如果所有j都不是正數(shù)，則當前默認的可執(zhí)行解決方案將成為最佳解決方案，計算結(jié)束。(3)在用非控制變量表示的基礎(chǔ)變量的表達式(2-11)中，觀察隨著基礎(chǔ)變量的增加，每個基礎(chǔ)變量的變化，確定在基礎(chǔ)變量的增加過程中，基礎(chǔ)變量的值首先減少到0的變量xr。滿足，=minbi/aijaij0=br/將默認變量的值增加到時，如果默認變量xr的值降到0，可能的解決方案會移動到相鄰的默認可能解決方

7、案(極)、旋轉(zhuǎn)(4)。增加預(yù)設(shè)變數(shù)的值并不會減少所有預(yù)設(shè)變數(shù)的值。也就是說，如果所有AIJ都不是正數(shù)，則可執(zhí)行字段不閉合，目標函數(shù)值可以隨著基本變量的增加無限增大。此時沒有有限的最佳解決方案，計算結(jié)束。(4)將默認變量作為新的默認變量，將默認變量作為新的非默認變量，以確定新的默認、新的默認可行解決方案和新的目標函數(shù)值。對新基準變量非基準變量重復(fù)(1)。簡述了使用單純形法處理線性規(guī)劃問題的步驟，并說明了a: 1)數(shù)學(xué)模型實施2)將典型數(shù)學(xué)模型格式轉(zhuǎn)換為標準格式。3)設(shè)定初始預(yù)設(shè)、預(yù)設(shè)變數(shù)和鄭智薰預(yù)設(shè)變數(shù)。4)將基礎(chǔ)轉(zhuǎn)換為單位陣列。5)將目標函數(shù)表示為非標準變量，如果所有非標準變量的系數(shù)大于0，則

8、最好的優(yōu)點是基準變量和非標準變量，非標準變量0，基準變量由等式約束決定。6)確定進入和脫離變量，獲得新的標準、基準變量。7)轉(zhuǎn)至4。上面的算法理論太強了，下面是實用的計算階段，1早期基本可行解決方案的決定是以標準矩陣形式寫的。尋找單位矩陣，其m列向量對應(yīng)于基本變量，其馀為非基本變量，非基本變量為0，得到初始基本可執(zhí)行點。2主變量(矩陣格式)3使用表示主變量(非主變量的函數(shù))的非主變量整理目標函數(shù)(非主變量)，采用負系數(shù)最小的非主變量x k作為主變量。(軸：使用通過當前頂點的所有邊界中下降最快的邊界作為下一個優(yōu)化的軸)如果所有4個系數(shù)都為正，則牙齒默認可執(zhí)行點最有利并返回。(通過當前頂點的所有邊

9、界都不會下降)，5最小的相應(yīng)變量是默認變量x l。如果所有分母小于0，則沒有最佳點(返回) (無限制減少)。否則，非基本變量為0，得到基本的可執(zhí)行點。6新的基本、基本變量和其他旋轉(zhuǎn)2，、7-2算法改進，在很多書中，有些象征意義不明確。提出了基本步驟，并使用實例進行了說明，總結(jié)，首先確定了線性規(guī)劃問題的標準形式和轉(zhuǎn)換方法。其次，了解單純形法的實用算法和步驟。第三，了解單純形法的工程應(yīng)用。，以后補充選擇內(nèi)容，以后補充選擇內(nèi)容： 3，單純形表，第一步：單純形表。(1)以標準形式尋找原始線性規(guī)劃問題的切換(2)初始可行基礎(chǔ)，一般是約束方程組系數(shù)矩陣的單位矩陣；(3)基于目標函數(shù)鄭智薰；(4)早期單純形

10、表。步驟2:最佳解決方案的判定。(1)在所有檢查數(shù)都不是正數(shù)的情況下，牙齒時的線性規(guī)劃問題得到了最佳解決。(2)檢查數(shù)為正，相應(yīng)的熱矢量沒有正分量，則沒有線性規(guī)劃問題的最優(yōu)解。(3)如果確定它所在列的非基本變量是基本變量。(2)對具有最大正檢查數(shù)的列實施最小比率方法，確定主元，將主元括在括號內(nèi)。主元是具有最大正檢查數(shù)的列，使用常數(shù)和與主變量相對應(yīng)的列矢量的正分量中最小的比率。(3)預(yù)設(shè)變更：使用預(yù)設(shè)變數(shù)取代預(yù)設(shè)變數(shù)，以取得新預(yù)設(shè)變數(shù)。也就是說，以基本元素所在列中的非基本變量為基礎(chǔ)，以該行中的基本變量為基礎(chǔ)。(4)利用矩陣的行初等變換，將主元轉(zhuǎn)換為1，該列的其他元素都牙齒為零，得到新的單純形表。

11、(5)返回第二步，繼續(xù)確定是否存在最佳解決方案，然后執(zhí)行新的更換標準迭代，直到問題解決。6-4初始默認可執(zhí)行解決方案，手動默認方法：將虛擬變量(手動變量)添加到約束方程組(手動變量)以查找初始默認可執(zhí)行解決方案。人工變量和松弛變量，剩下的變量不同，沒有具體的物理意義，必須從基本變量逐步替換?；咀兞侩S機存取存儲器后，如果基本變量不再包含人工變量，則表明存在原始問題的解決方案。否則，對原來的問題沒有解決辦法。1，懲罰法(大系數(shù)法)增加M個大系數(shù)的人工變量，早期可行的解決方法是2，2階段法第一階段：引入人工變量，尋找具有人工變量的最佳解決方法。使用在步驟2、步驟1中找到的基本可行解決方案，尋找原始

12、問題的最佳解決方案。6-5改進了單純形法，減少了基于單純形法與基本更換過程無關(guān)的許多數(shù)值計算。(使用矩陣)，建立線性規(guī)劃模型的程序可分為四個步驟：(1)設(shè)定決策變數(shù)。(2)顯式約束用決策變量的線性等式或不等式表示。(3)確定目標是以決策變量的線性函數(shù)(max)表示，還是追求最大(Max)或最小(min)。(4)根據(jù)決策變量的物理性質(zhì)研究，研究變量是否有非語音。線性規(guī)劃應(yīng)用程序，示例2.12:某一周服務(wù)的公交線路每天各時間段需要的司機及乘務(wù)員數(shù)量如下。人力資源分配問題、司機及乘務(wù)員分別從各期間開始上班，連續(xù)工作8小時。詢問如何在牙齒公交線路上部署司機及乘務(wù)員，不僅能滿足工作要求，還具備最低司機及

13、乘務(wù)員。解決：Xi表示在I班次開始上班的司機和乘務(wù)員的數(shù)量，因此可以制作以下數(shù)學(xué)模型：目標函數(shù)：Min x1 x2 x3 x4 X5 X5 X6約束：s . t . x1x 6 60x 1x 2 70x 2 x3 60x 3x 4 50x 4x 5 20x 5x 6 30x 1、x2、x3、x4、X5、X60，據(jù)悉人力資源分配問題的原料分別為7.4米長問：怎么做才能最大限度地節(jié)約使用的原料？切削問題，解決方法：考慮以下各種空白方案(按一個邏輯順序提供)，并假設(shè)每個空白方案從剩馀材料開始按大順序列出，假設(shè)x1、x2、x3、x4和x5分別在前五個方案下的原材料根數(shù)。我們構(gòu)建了以下數(shù)學(xué)模型。目標函數(shù)

14、：Min x1 x2 x3 x4 X5約束：s . t . x1 2x2x 4 100 2x3 2x4x 5 100 3x1x 2 x3 3x5 100 x1、x2、x3、x4、x50，重疊剪切問題(例如2.14330)甲、乙兩種產(chǎn)品的鑄件可以外包合作，也可以自行生產(chǎn)，但產(chǎn)品C必須在本廠鑄造，才能保證質(zhì)量。數(shù)據(jù)如下表所示：問：公司為了最大限度地提高利潤，各生產(chǎn)多少例甲、乙、丙茄子產(chǎn)品？甲，乙兩種產(chǎn)品的鑄造中，我公司鑄造和外包合作的有多少件？生產(chǎn)計劃中的問題，解決方法：x1，x2，x3分別為3道工序，是我公司加工的甲，乙，C三種茄子產(chǎn)品的碎片數(shù)，x4，X5分別是我公司加工的甲和乙兩種茄子產(chǎn)品的碎

15、片數(shù)。生產(chǎn)計劃問題，Xi利潤：利潤=銷售價錢-各成本之和為xi(i=1，2，3，4，5)的利潤分別為15，10，7，13，9元。假定目標函數(shù)3360 max15x1 10x2 7x3 13x4 9x5約束s . t . 5 x1 10x 2 7x3 8000 6x1 4x 2 8x3 6x4 4x 5 12000 3x 1 2x3 x4 2x5 1000 x1、x2、xx設(shè)置如下，兩個茄子規(guī)格的設(shè)備A1和A2可以完成A過程：可以完成三種茄子規(guī)格的設(shè)備B1，B2，B3牙齒B工藝?？梢栽赼，b所有規(guī)格的設(shè)備上加工。可以在任何規(guī)格的A設(shè)備上加工，但對于B工序，只能在B1設(shè)備上加工。只能在A2和B2設(shè)備上處理。數(shù)據(jù)如下表所示：問：為了最大限度地提高牙齒工廠的利潤，應(yīng)該如何制定產(chǎn)品加工方案？生產(chǎn)計劃問題，解決：xijk是第一類產(chǎn)品，在第J工序的K型設(shè)備上加工的數(shù)量。利潤=(銷售單價-原材料單價)產(chǎn)品數(shù)合計-(每個城市的設(shè)備成本設(shè)備實際使用的書桌時間合計)。生產(chǎn)計劃問題，這樣我們就數(shù)學(xué)模型3360 max 0.75 x 111 0.7753 x 112 1.15 x 211 1.3611 x 212 1.9148 x 312-0.375