線性規(guī)劃圖解法經典運籌學

線性規(guī)劃圖解法經典運籌學第一頁，共五十四頁，編輯于2023年，星期三

1、建模的一般步驟：步驟一：確定決策變量即用變量取不同的值來表示可供選擇的各種不同方案步驟二：建立目標函數即找到目標值與決策變量的數量關系步驟三：確定約束條件即決策變量所受到的外界條件的制約。約束條件一般為決策變量的等式或不等式要求：目標函數與約束條件均是線性的，且目標函數只能是一個。第二頁，共五十四頁，編輯于2023年，星期三2、線性規(guī)劃模型的一般形式：決策變量約束方程非負約束目標函數第三頁，共五十四頁，編輯于2023年，星期三三、線性規(guī)劃求解：四、線性規(guī)劃應用舉例計算機應用軟件第四頁，共五十四頁，編輯于2023年，星期三時間所需售貨員人數星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商場是個中型的百貨商場，它對售貨人員的需求經過統(tǒng)計分析如下所示：為保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應該如何安排售貨人員的作息，既滿足了工作的需要，又使配備的售貨人員的人數最少？解第五頁，共五十四頁，編輯于2023年，星期三時間所需售貨員人數星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人約束條件:星期日售貨員人數要求:星期一售貨員人數要求:星期二售貨員人數要求:星期三售貨員人數要求:星期四售貨員人數要求:星期五售貨員人數要求:星期六售貨員人數要求:數學模型:非負約束:第六頁，共五十四頁，編輯于2023年，星期三數學模型:解得:第七頁，共五十四頁，編輯于2023年，星期三時間所需售貨員人數星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商場是個中型的百貨商場，它對售貨人員的需求經過統(tǒng)計分析如下所示：為保證售貨人員充分休息，售貨人員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問應該如何安排售貨人員的作息，既滿足了工作的需要，又使配備的售貨人員的人數最少？解第八頁，共五十四頁，編輯于2023年，星期三方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(根)長度例4某工廠要做100套鋼架,每套用長為2.9m,2.1m,和1.5m的圓鋼各一根,已知原料每根長7.4m,問應如何下料,可使所用原料最省.分析:每根原料做一套鋼架,下角料：0.9m用套裁方式下料方案：第九頁，共五十四頁，編輯于2023年，星期三方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(根)長度下料方案：第十頁，共五十四頁，編輯于2023年，星期三方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(根)長度例4某工廠要做100套鋼架,每套用長為2.9m,2.1m,和1.5m的圓鋼各一根,已知原料每根長7.4m,問應如何下料,可使所用原料最省.下料方案：最優(yōu)下料方案：按方案1下料30根，方案2下料10根，方案4下料50根，共需原料90根。第十一頁，共五十四頁，編輯于2023年，星期三例5(產品配套問題）假定一個工廠的甲、乙、丙三個車間生產同一個產品，每件產品包括4個A零件，和3個B零件。這兩種零件由兩種不同的原材料制成，而這兩種原材料的現有數額分別為100克和200克。每個生產班的原材料需要量和零件產量如下表所示。問這三個車間各應開多少班才能使這種產品的配套數達到最大約束條件為：第十二頁，共五十四頁，編輯于2023年，星期三三個車間共生產A零件：三個車間共生產B零件非線性要求：目標函數：目標函數Z=x4線性第十三頁，共五十四頁，編輯于2023年，星期三數學模型：線性規(guī)劃問題第十四頁，共五十四頁，編輯于2023年，星期三例6（多周期動態(tài)生產計劃問題）華津機器制造廠專為拖拉機廠配套生產柴油機，今年頭四個月收到的定單數量分別為3000臺、4500臺、3500臺、5000臺。該廠正常生產每月可生產3000臺，利用加班還可生產1500臺，正常生產成本為每臺5000元，加工生產還要追加1500元，庫存成本為每臺每月200元。問華津廠如何組織生產才能使生產成本最低？分析：設C=成本=四個月正常生產的成本+四個月加班生產的成本+四個月庫存成本約束條件：第十五頁，共五十四頁，編輯于2023年，星期三需求約束：第4個月第3個月第2個月第1個月生產能力約束：數學模型：四個月定單數量分別為3000臺、4500臺、3500臺、5000臺每月可生產3000臺，利用加班還可生產1500臺庫存約束：第十六頁，共五十四頁，編輯于2023年，星期三例7.連續(xù)投資問題建模:某投資公司有100萬元資金用于投資，投資的方案可以有以下六種，現要做一個5年期的投資計劃，具體可選擇的投資方案如下：方案A：5年內的每年年初均可投資，且金額不限，投資期限1

年，年投資回報率7%。方案B：5年內的每年年初均可投資，且金額不限，投資期限2

年，年投資回報率10%（不計復利）。方案C：5年內的每年年初均可投資，且金額不限，投資期限3

年，年投資回報率12%（不計復利）方案D：只在第一年年初有一次投資機會，最大投資金額為50

萬元，投資期限4年，年投資回報率20%方案E：在第二年和第四年年初有一次投資機會，最大投資金額均為30萬元，投資期限1年，年投資回報率30%方案F：在第四年年初有一次投資機會，金額不限，投資期限2

年，年投資回報率25%假設當年的投資金額及其收益均可用于下一年的投資，問公司應如何投資才能使第五年末收回的資金最多？第十七頁，共五十四頁，編輯于2023年，星期三假設當年的投資金額及其收益均可用于下一年的投資，問公司應如何投資才能使第五年末收回的資金最多？第十八頁，共五十四頁，編輯于2023年，星期三連續(xù)投資問題模型:第十九頁，共五十四頁，編輯于2023年，星期三1.1.2、線性規(guī)劃的標準形式和矩陣表達式線性規(guī)劃問題的一般形式：第二十頁，共五十四頁，編輯于2023年，星期三1、線性規(guī)劃的標準形式第二十一頁，共五十四頁，編輯于2023年，星期三標準型式的特征:1、求目標函數的最大值2、約束方程為等式方程3、約束方程的右邊非負4、決策變量均非負非標準型式有以下幾種可能：1、求目標函數的最小值4、決策變量<0或無限制2、約束方程為不等式方程3、約束方程的右邊第二十二頁，共五十四頁，編輯于2023年，星期三2、非標準型式線性規(guī)劃問題的標準化-max（1）對求目標函數最小值:=第二十三頁，共五十四頁，編輯于2023年，星期三（2）約束條件為“≤”型松弛變量第二十四頁，共五十四頁，編輯于2023年，星期三（3）約束條件為“≥”型剩余變量第二十五頁，共五十四頁，編輯于2023年，星期三(4)約束條件右邊為負（6）決策變量無符號限制（5）決策變量≤0例如帶入約束方程及目標函數第二十六頁，共五十四頁，編輯于2023年，星期三則原線性規(guī)劃問題的標準型為:第二十七頁，共五十四頁，編輯于2023年，星期三第二十八頁，共五十四頁，編輯于2023年，星期三3.線性規(guī)劃問題的矩陣表達式：第二十九頁，共五十四頁，編輯于2023年，星期三

§1.3線性規(guī)劃的基本理論第三十頁，共五十四頁，編輯于2023年，星期三一、線性規(guī)劃的解1、可行解：2、可行域：（LP）的全體可行解構成的集合稱為可行域3、最優(yōu)解及最優(yōu)值：設S是（LP）的可行域不唯一唯一4、若對任意大的M>0,都存在可行解使得該線性規(guī)劃的目標函數值，則稱該線性規(guī)劃問題無界第三十一頁，共五十四頁，編輯于2023年，星期三二、兩個變量的線性規(guī)劃的圖解法解：（1）在直角坐標系上畫出可行域（2）做目標函數的等值線0可行域凸多邊形頂點.第三十二頁，共五十四頁，編輯于2023年，星期三解：（1）在直角坐標系上畫出可行域（2）做目標函數的等值線0無窮多..第三十三頁，共五十四頁，編輯于2023年，星期三解：（1）在直角坐標系上畫出可行域（2）做目標函數的等值線0目標函數無上界，該問題無界無最優(yōu)解第三十四頁，共五十四頁，編輯于2023年，星期三解：（1）在直角坐標系上畫出可行域0可行域為空集無可行解該問題無最優(yōu)解第三十五頁，共五十四頁，編輯于2023年，星期三圖解法的基本步驟：（一般是一個凸多邊形）注意：若是求目標函數的最小值，目標函數直線向下移動第三十六頁，共五十四頁，編輯于2023年，星期三關于線性規(guī)劃解的結論：1、若（LP）問題有可行解，則可行域是一個凸多邊形（或凸多面體）。它可能是有界的；也可能是無界的。2、若（LP）問題有最優(yōu)解，則最優(yōu)解可能是唯一的；也可能是無窮多個。如果是唯一的，這個解一定在該凸多邊形的某個頂點上；如果是無窮多個，則這些最優(yōu)解一定充滿凸多邊形的一條邊界（包括此邊界的兩個頂點）總之，若（LP）問題有最優(yōu)解，則最優(yōu)解一定可以在凸多邊形的某個頂點達到3、若（LP）問題有可行解，但沒有有限最優(yōu)解，此時凸多邊形是無界的（反之不成立）4、若（LP）問題沒有可行解，則該問題沒有最優(yōu)解第三十七頁，共五十四頁，編輯于2023年，星期三三、基與基本可行解不妨設AX=b有解，且m≤n利用線性代數的方法求出無窮多解？×只討論r<n,此時第三十八頁，共五十四頁，編輯于2023年，星期三且r(A)=r=m(若r<m,必有多余方程，可去掉）由線性代數結論知:若r(A)=m，則A中至少存在一個m階子式|B|≠0即A中存在滿秩的m階矩陣B,稱B為（LP）問題的一個基不妨設m≤n第三十九頁，共五十四頁，編輯于2023年，星期三定義1.3在（LP）問題中，A的任意一個m×m階的非奇異子方陣B（即|B|≠0）稱為（LP）問題的一個基一個線性規(guī)劃問題最多有基設r(Amxn)=r=m第四十頁，共五十四頁，編輯于2023年，星期三基基不是基第四十一頁，共五十四頁，編輯于2023年，星期三設r(A)=m<n不妨設A的前m列構成A的一個基基變量非基變量第四十二頁，共五十四頁，編輯于2023年，星期三基,基非基,第四十三頁，共五十四頁，編輯于2023年，星期三由于B可逆基本解定義1.4設B是（LP）問題的一個基，,A=（B,N）,稱此解為對應于基B的基本解自由未知量第四十四頁，共五十四頁，編輯于2023年，星期三基,非基,第四十五頁，共五十四頁，編輯于2023年，星期三定義1.5基本可行解的個數基本可行解對應的基稱為可行基第四十六頁，共五十四頁，編輯于2023年，星期三基,非基,基本可行解可行基第四十七頁，共五十四頁，編輯于2023年，星期三A的任意一個m×