第2章 線性規(guī)劃實驗

第2章線性規(guī)劃實驗2.1基礎(chǔ)知識2.2使用LINDO軟件求解線性規(guī)劃問題2.3使用Lingo軟件求解線性規(guī)劃問題2.4使用WinQSB軟件求解線性規(guī)劃問題2.5使用MATLAB軟件求解線性規(guī)劃問題2.1基礎(chǔ)知識

線性規(guī)劃（LP）是運籌學(xué)的一個重要分支。自1947年美國數(shù)學(xué)家GeorgeBernardDantzig提出了求解線性規(guī)劃問題的單純形法后，線性規(guī)劃在理論上日益成熟，在實際中的應(yīng)用也更加廣泛，在工業(yè)、農(nóng)業(yè)、經(jīng)濟管理、軍事和交通運輸?shù)雀鞣矫娑及l(fā)揮了重要作用。線性規(guī)劃問題的數(shù)學(xué)模型

在經(jīng)濟和生產(chǎn)活動中，生產(chǎn)者往往要追求收益最大、成本最小等目標。線性規(guī)劃能解決的就是在有限資源的約束條件下，使獲得收益（或支付成本）的線性目標取得最大值（或最小值）的問題，其中收益、成本和約束條件均為變量的線性表達式。

線性規(guī)劃問題的數(shù)學(xué)模型包含三個組成要素：

決策變量目標函數(shù)約束條件2.1基礎(chǔ)知識

2.1基礎(chǔ)知識

線性規(guī)劃問題的求解方法圖解法以一個決策變量為橫軸，另一個決策變量為縱軸，畫出平面直角坐標系；在坐標系上畫出每個約束條件對應(yīng)的直線或區(qū)域；確定可行域；確定線性規(guī)劃問題解的情況。單純形法找出初始基可行解；若初始基可行解不存在，則該線性規(guī)劃問題無最優(yōu)解；否則，進入下一步；若初始基可行解存在，以該初始基可行解作為起點，根據(jù)檢驗數(shù)的最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出使目標函數(shù)值更優(yōu)的基可行解；按照上一步進行迭代，直到對應(yīng)檢驗數(shù)滿足最優(yōu)性條件，得到問題的最優(yōu)解。特別要注意的是，若在迭代過程中發(fā)現(xiàn)問題的目標函數(shù)值無界，說明該線性規(guī)劃問題存在無界解，應(yīng)終止迭代。2.1基礎(chǔ)知識

線性規(guī)劃問題的求解方法人工變量法若線性規(guī)劃問題的約束條件是等式，而且系數(shù)矩陣中不包含單位矩陣，則可以采用人工變量法進行求解。大M法若目標函數(shù)為maxz，將人工變量的系數(shù)取為-M（M是充分大的正數(shù)）；若目標函數(shù)為minz，將人工變量的系數(shù)取為M，然后利用單純形法求解。

兩階段法第一階段：求解一個目標函數(shù)僅含有人工變量的極小化問題。若最優(yōu)值為0，去掉人工變量轉(zhuǎn)為第二階段；若最優(yōu)值為非0值，則原問題無可行解，停止計算。第二階段：去掉第一階段中的人工變量，將第一階段得到的最優(yōu)解作為初始基可行解，再利用單純形法進行求解。2.2使用LINDO軟件求解線性規(guī)劃問題

利用LINDO軟件求解線性規(guī)劃問題，不需要將問題化成標準型，只需將線性規(guī)劃模型輸入該軟件的編輯窗口即可。LINDO軟件默認變量是非負的，如果變量是有界或無約束的，那么使用FREE語句可以把指定變量的非負約束去掉。

實驗?zāi)康氖煜INDO軟件求解線性規(guī)劃問題的方法步驟，并理解求解結(jié)果。

掌握LINDO軟件對線性規(guī)劃問題解的情況的判別。

通過利用LINDO軟件求解線性規(guī)劃問題，進一步理解線性規(guī)劃問題的建模和求解。2.2使用LINDO軟件求解線性規(guī)劃問題

實驗內(nèi)容例2.1利用LINDO軟件求解下列線性規(guī)劃問題。

2.2使用LINDO軟件求解線性規(guī)劃問題

2.2使用LINDO軟件求解線性規(guī)劃問題

1.模型1求解步驟打開LINDO軟件后，在編輯窗口輸入模型12.2使用LINDO軟件求解線性規(guī)劃問題

單擊窗口“Solve”菜單中的“Solve”選項或單擊工具欄中的

按鈕2.2使用LINDO軟件求解線性規(guī)劃問題

模型1的輸出結(jié)果如右圖

2.2使用LINDO軟件求解線性規(guī)劃問題

2.模型2求解步驟打開LINDO軟件后，在編輯窗口輸入模型22.2使用LINDO軟件求解線性規(guī)劃問題

求解模型2，得到模型2的輸出結(jié)果如右圖

2.2使用LINDO軟件求解線性規(guī)劃問題

3.模型3求解步驟打開LINDO軟件后，在編輯窗口輸入模型32.2使用LINDO軟件求解線性規(guī)劃問題

單擊窗口“Solve”菜單中的“Solve”選項或單擊工具欄中的

按鈕求解模型3，彈出模型3的錯誤信息對話框，提示無界解。2.2使用LINDO軟件求解線性規(guī)劃問題

單擊對話框中的“OK”按鈕，出現(xiàn)模型3的解狀態(tài)對話框，最優(yōu)解狀態(tài)顯示為無界（“Unbounded”）。該問題有無界解。2.2使用LINDO軟件求解線性規(guī)劃問題

4.模型4求解步驟打開LINDO軟件后，在編輯窗口輸入模型42.2使用LINDO軟件求解線性規(guī)劃問題

單擊窗口“Solve”菜單中的“Solve”選項或單擊工具欄中的

按鈕求解模型4，彈出模型4的錯誤信息對話框，提示無可行解。2.2使用LINDO軟件求解線性規(guī)劃問題

單擊對話框中的“OK”按鈕，出現(xiàn)模型4的解狀態(tài)對話框，最優(yōu)解狀態(tài)顯示為為無可行解（“Infeasible”）。該問題無可行解。2.3使用Lingo軟件求解線性規(guī)劃問題

利用Lingo軟件求解線性規(guī)劃問題，可以避免大量的煩瑣的計算，能夠輕松、有效地獲得規(guī)劃問題的解。Lingo軟件求解線性規(guī)劃問題的過程采用的是單純形法，一般首先尋求一個可行解，在有可行解的情況下再尋求最優(yōu)解。

實驗?zāi)康氖煜ingo軟件求解線性規(guī)劃問題的方法步驟，并理解求解結(jié)果。掌握Lingo軟件對線性規(guī)劃問題解的情況的判別。實驗內(nèi)容例2.2利用Lingo軟件求解例2.1中的線性規(guī)劃問題。

2.3使用Lingo軟件求解線性規(guī)劃問題

2.3使用Lingo軟件求解線性規(guī)劃問題

1.模型1求解步驟打開Lingo軟件后，在編輯窗口輸入模型12.3使用Lingo軟件求解線性規(guī)劃問題

單擊“Lingo”菜單中的“Solve”選項或單擊工具欄中的

按鈕,求解該模型，得到模型1的解狀態(tài)對話框。2.3使用Lingo軟件求解線性規(guī)劃問題

模型1的解報告窗口2.3使用Lingo軟件求解線性規(guī)劃問題

2.模型2求解步驟打開Lingo軟件后，在編輯窗口輸入模型22.3使用Lingo軟件求解線性規(guī)劃問題

求解模型2，得到模型2的解狀態(tài)對話框2.3使用Lingo軟件求解線性規(guī)劃問題

2.3使用Lingo軟件求解線性規(guī)劃問題

3.模型3求解步驟打開Lingo軟件后，在編輯窗口輸入模型32.3使用Lingo軟件求解線性規(guī)劃問題

單擊“Lingo”菜單中的“Solve”選項或單擊工具欄中的

按鈕求解模型3，彈出模型3的錯誤信息對話框，提示無界解。2.3使用Lingo軟件求解線性規(guī)劃問題

單擊對話框中的“OK”按鈕，彈出對話框，警告：模型的當前解可能不是最優(yōu)的或是不可行的。2.3使用Lingo軟件求解線性規(guī)劃問題

該問題有無界解。2.3使用Lingo軟件求解線性規(guī)劃問題

繼續(xù)單擊對話框中的“OK”按鈕，彈出模型3的解狀態(tài)對話框。4.模型4求解步驟打開Lingo軟件后，在編輯窗口輸入模型42.3使用Lingo軟件求解線性規(guī)劃問題

單擊“Lingo”菜單中的“Solve”選項或單擊工具欄中的

按鈕求解模型4，彈出模型4的錯誤信息對話框，提示無可行解。2.3使用Lingo軟件求解線性規(guī)劃問題

單擊對話框中的“OK”按鈕，彈出對話框，警告：模型的當前解可能不是最優(yōu)的或是不可行的。2.3使用Lingo軟件求解線性規(guī)劃問題

該問題無可行解。2.3使用Lingo軟件求解線性規(guī)劃問題

繼續(xù)單擊對話框中的“OK”按鈕，彈出模型4的解狀態(tài)對話框。利用WinQSB軟件求解線性規(guī)劃問題時，需要調(diào)用“LinearandIntegerProgramming”模塊，且不需要將模型化為標準型。當決策變量是有界變量或無約束變量時，可以不用轉(zhuǎn)化，只需要修改系統(tǒng)的變量類型即可。對于不等式約束，可以在輸入數(shù)據(jù)時直接輸入不等式符號。2.4使用WinQSB軟件求解線性規(guī)劃問題

實驗?zāi)康氖煜inQSB軟件求解線性規(guī)劃問題的方法、步驟，并理解求解結(jié)果。熟悉WinQSB軟件求解線性規(guī)劃問題的圖解法。了解WinQSB軟件用單純形法和大M法求解線性規(guī)劃問題的過程。

實驗內(nèi)容例2.3利用WinQSB軟件求解線性規(guī)劃問題。

2.4使用WinQSB軟件求解線性規(guī)劃問題

方法1利用單純形法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

選擇“開始”

→“程序”→“WinQSB”→“LinearandIntegerProgramming”→“File”→“NewProblem”菜單命令，

生成對話框，輸入模型信息方法1利用單純形法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

2.在編輯窗口輸入模型方法1利用單純形法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

方法1利用單純形法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

選擇“SolveandAnalyze”→“Solveand

Display

Steps”菜單命令，得到初始單純形表方法1利用單純形法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

再選擇“Simplex

Iteration”→

“NextIteration”菜單命令，得到單純形法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

1.在編輯窗口輸入模型后，

“SolveandAnalyze”→“GraphicMethod”菜單命令或者單擊工具欄中的按鈕方法2利用圖解法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

2.在圖解法變量選

擇對話框中選擇橫坐標和縱坐標，單擊“OK”按鈕。方法2利用圖解法的求解步驟2.4使用WinQSB軟件求解線性規(guī)劃問題

方法2利用圖解法的求解步驟

例2.4利用WinQSB軟件求解線性規(guī)劃問題。

2.4使用WinQSB軟件求解線性規(guī)劃問題

2.4使用WinQSB軟件求解線性規(guī)劃問題

選擇“開始”

→“程序”→“WinQSB”→“LinearandIntegerProgramming”→“File”→“NewProblem”菜單命令，

生成對話框，輸入模型信息2.4使用WinQSB軟件求解線性規(guī)劃問題

2.在編輯窗口輸入模型2.4使用WinQSB軟件求解線性規(guī)劃問題

3.選擇“SolveandAnalyze”→“Solveand

Display

Steps”菜單命令，得到初始單純形表，表中C2、C3為人工變量，目標函數(shù)中人工變量的系數(shù)為-M。2.4使用WinQSB軟件求解線性規(guī)劃問題

2.5使用MATLAB軟件求解線性規(guī)劃問題

線性規(guī)劃問題的目標函數(shù)求的是最大值或最小值，約束條件的不等式符號可以是小于等于號也可以是大于等于號。為了利用MATLAB軟件求解線性規(guī)劃問題，將模型轉(zhuǎn)化成如下形式：

式中，f、x、b、beq、lb、ub為向量；A、Aeq為矩陣。

再調(diào)用linprog函數(shù)來求解模型。2.5使用MATLAB軟件求解線性規(guī)劃問題

實驗?zāi)康氖煜ATLAB軟件求解線性規(guī)劃模型的基本命令和M文件的編寫。了解MATLAB軟件優(yōu)化工具箱求解線性規(guī)劃問題的方法