1、Linear Programming,運 籌 學 課 件,線 性 規(guī) 劃,線性規(guī)劃問題及其數學模型 圖解法 單純形法原理 單純形法計算步驟 單純形法的進一步討論 數據包絡 其他應用例子 案例分析,線性規(guī)劃概述,線性規(guī)劃（Linear Programming，簡記為LP）是運籌學中的一個最重要、應用最廣泛的分支。 線性規(guī)劃及其通用解法-單純形法一般認為是美國學者丹捷格（G.Dantzig）在1947年研究美國空軍軍事規(guī)劃時提出的。 蘇聯學者康托洛維奇在1939年解決工業(yè)生產組織與計劃問題時就提出類似線性規(guī)劃的模型及解法；康托洛維奇的工作當時沒有被重視，但直到1960年康托洛維奇再次發(fā)表最佳資源利

2、用的經濟計算一書后，才受到重視。 一些常見的帶有Spreadsheet的軟件，如：Excel、Lotus1-2-3等，均有內置的線性規(guī)劃求解功能。 最優(yōu)化問題求解軟件，如：Lindo、Lingo、Matlab等。,線性規(guī)劃問題提出,在生產管理和經營活動中經常會提出這樣一類問題：如何利用有限的人力、物力、財力等資源，取得最好的效果。例如： 配載問題 一交通工具，運輸幾種不同體積、重量的物資，如何裝配， 所運的物資最多？ 下料問題 用圓鋼制造長度不等的機軸，如何下料，所剩的余料最少？ 生產計劃問題 企業(yè)生產A、B兩種電器產品，兩種產品的市場需求狀況可以確定，按當前的定價可確保所有產品均能銷售出去。

3、 企業(yè)可提供的兩種原材料和勞動時間的數量是有限的。產品A與產品B各應生產多少，可使企業(yè)總利潤最大?,線性規(guī)劃問題提出,上述這些問題有如下共同特點： 問題解決要滿足一定條件，稱為約束條件； 問題有多個滿足條件的解決方案； 問題解決有明確的目標要求，對應不同方案有不同目標值，可表示成目標函數。,線 性 規(guī) 劃 問 題 及 其 數 學 模 型,問題提出與建模 生產計劃問題 運輸問題 線性規(guī)劃模型 一般形式 規(guī)范形式 標準形式 形式轉換,常山機械廠制造、兩種產品。已知各制造一件時分別占用的設備A、B、C的臺時，每天可用于這兩種家電的能力、各售出一件時的獲利情況如下表所示。問該企業(yè)應制造兩種產品各多少件

4、，可使獲取的利潤最大。,生 產 計 劃 問 題,問 題 分 析,模 型,運 輸 問 題,問 題 分 析,模 型,線性規(guī)劃問題的三個要素,決策變量 決策問題待定的量值稱為決策變量。 決策變量的取值有時要求非負。 約束條件 任何問題都是限定在一定的條件下求解，把各種限制條件表示為一組等式或不等式，稱之為約束條件。 約束條件是決策方案可行的保障。 LP的約束條件，都是決策變量的線性函數。 目標函數 衡量決策方案優(yōu)劣的準則，如時間最省、利潤最大、成本最低。 目標函數是決策變量的線性函數。 有的目標要實現極大，有的則要求極小。,何謂線性規(guī)劃問題,最優(yōu)化問題 我們稱如下一般問題：“在一定約束條件下，求目標

5、函數的最大或最小值”為最優(yōu)化問題，用數學模型描述的最優(yōu)化問題，稱為數學規(guī)劃問題。 線性規(guī)劃問題 在最優(yōu)化問題中，如果約束條件與目標函數均是線性的，我們就稱之為線性規(guī)劃問題。,線性規(guī)劃的數學模型,如果規(guī)劃問題的數學模型中，決策變量的取值是連續(xù)的，既可以為整數，也可以為分數、小數或實數，目標函數是決策變量的線性函數，約束條件是含決策變量的線性等式或不等式，則該規(guī)劃問題的數學模型為線性規(guī)劃的數學模型。,線性規(guī)劃數學模型,建立線性規(guī)劃問題數學模型的步驟： Step1 分析實際問題； Step2 確定決策變量； Step3 找出約束條件； Step4 確定目標函數； Step5 整理、寫出數學模型。,【

6、例1.1】某市今年要興建大量住宅,已知有三種住宅體系可以大量興建，各體系資源用量及今年供應量見下表： 要求在充分利用各種資源條件下使建造住宅的總面積為最大(即求安排各住宅多少m2)，求建造方案。,線性規(guī)劃問題舉例,【例1.2】最優(yōu)生產計劃問題。某企業(yè)在計劃期內計劃生產甲、乙、丙三種產品。這些產品分別需要要在設備A、B上加工，需要消耗材料C、D，按工藝資料規(guī)定，單件產品在不同設備上加工及所需要的資源如表1.1所示。已知在計劃期內設備的加工能力各為200臺時，可供材料分別為360、300公斤；每生產一件甲、乙、丙三種產品，企業(yè)可獲得利潤分別為40、30、50元，假定市場需求無限制。企業(yè)決策者應如何

7、安排生產計劃，使企業(yè)在計劃期內總的利潤收入最大？,線性規(guī)劃問題舉例,產品資源消耗表,【例1.3】某商場決定：營業(yè)員每周連續(xù)工作5天后連續(xù)休息2天，輪流休息。根據統(tǒng)計，商場每天需要的營業(yè)員如表1.2所示。,表1.2 營業(yè)員需要量統(tǒng)計表,商場人力資源部應如何安排每天的上班人數，使商場總的營業(yè)員最少。,線性規(guī)劃問題舉例,【例1.4】合理用料問題。某汽車需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是1.5，1，0.7（m），這些軸需要用同一種圓鋼來做，圓鋼長度為4 m?，F在要制造1000輛汽車，最少要用多少圓鋼來生產這些軸？,線性規(guī)劃問題舉例,注意：（）求下料方案時應注意，余料不能超過最短毛坯

8、的長度； （）最好將毛坯長度按降的次序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案 。 （）如果方案較多，用計算機編程排方案，去掉余料較長的方案，進行初選。,【例1.5】配料問題。某鋼鐵公司生產一種合金，要求的成分規(guī)格是：錫不少于28%，鋅不多于15%，鉛恰好10%，鎳要界于35%55%之間，不允許有其他成分。鋼鐵公司擬從五種不同級別的礦石中進行冶煉，每種礦物的成分含量和價格如表1.4所示。礦石雜質在治煉過程中廢棄，現要求每噸合金成本最低的礦物數量。假設礦石在冶煉過程中，合金含量沒有發(fā)生變化。,表1.4 礦石的金屬含量,線性規(guī)劃問題舉例,解: 設xj（j=1,2，

9、5）是第j 種礦石數量，得到下列線性規(guī)劃模型,注意：礦石在實際冶煉時金屬含量會發(fā)生變化，建模時應將這種變化考慮進去，有可能是非線性關系。配料問題也稱配方問題、營養(yǎng)問題或混合問題，在許多行業(yè)生產中都能遇到。,【例1.6】投資問題。某投資公司在第一年有200萬元資金，每年都有如下的投資方案可供考慮采納：“假使第一年投入一筆資金，第二年又繼續(xù)投入此資金的50%，那么到第三年就可回收第一年投入資金的一倍金額”。投資公司決定最優(yōu)的投資策略使第六年所掌握的資金最多。,線性規(guī)劃問題舉例,【例1.7】均衡配套生產問題。某產品由2件甲、3件乙零件組裝而成。兩種零件必須經過設備A、B上加工，每件甲零件在A、B上的加工時間分別為5分鐘和9分鐘，每件乙零件在A、B上的加工時間分別為4分鐘和10分鐘?，F有2臺設備A和3臺設備B，每天每臺可供加工時間為8小時。為了保持兩種設備均衡負荷生產，要求一種設備每天的加工總時間不超過另一種設備總時間1小時。怎樣安排設備的加工時間使每天產品的產量最大。,線性規(guī)劃問題舉例,線性規(guī)劃問題的一般形式,目標函數,約束條件,假定線性規(guī)劃問題有n個決策變量，m個約束條件。一般地，線性規(guī)劃問題數學模型中可表示成如下形