1、線性規(guī)劃,線性規(guī)劃是一種幫助管理者制定決策的方法; 在許多領域都有成功的應用案例, 它在模型上表現(xiàn)為一個線性的函數(shù)在一組線性約束條件下的求極大值或求極小值問題; 最常見的三類問題是: 資源分配問題; 成本效益平衡問題和物流網(wǎng)絡配送問題.,資源分配問題,紅星重型機械廠的產品組合問題 產品甲: 需要原料A,原料B,設備工時; 產品乙: 也需要原料A,原料B,設備工時;由于原料A,原料B,設備工時的數(shù)量有限,如何安排生產,使獲利最大

2、?問題 1.公司是否該生產這兩個產品? 2如果生產, 產品生產組合如何?(各生產多少?),資源分配問題,這是一個定量問題決策目標---利潤最大化步驟1---收集相關數(shù)據(jù)如下:(見P10),資源分配問題,步驟2--- 建立數(shù)學模型 1) 決策變量—決策量化的手段 x1=產品甲 的生產數(shù)量 x2 =產品乙 的生產數(shù)量

3、 2) 目標函數(shù)---衡量決策效果(優(yōu)劣)的指標 Z= 4x1 + 3x2 求最大值 3) 約束條件 x1 ≤ 6 (原料A數(shù)量約束) 2 x2 ≤8 (原料B數(shù)量約束) 2x1 + 3x2 ≤18 (設備工時約束)

4、 x1, x2 ≥ 0 (非負約束),建立數(shù)學規(guī)劃模型的四個步驟 明確問題，確定決策變量； 決策變量是構成解決方案的要素或單元，決策變量的組合構成一個可行解決方案。 明確約束條件并用決策變量的等式或不等式表示； 盡可能分類描述，防止差錯和遺漏 用決策變量的函數(shù)表示目標，并確定是求極大（Max）、極?。∕in）還是特定值； 根據(jù)決策變量的物理性質研究變量是否有非負性或上下界。,資源分

5、配問題,資源分配（resource-allocation）問題是將有限的資源 分配到各種活動中去的線性規(guī)劃問題。這一類問題的 共性是在線性規(guī)劃模型中每一個函數(shù)限制均為資源限 制(resource constraint) , 并且每一種有限資源都可以表 現(xiàn)為如下的形式：  使用的資源數(shù)量 ? 可用的資源數(shù)量,資源分配問題,例1的數(shù)學模型可以用代數(shù)形式描述如下：這實際上是求一個線性函數(shù)在一組線性約束條件

6、下的最大值問題，我們稱之為線性規(guī)劃問題模型。,資源分配問題,我們稱x1、x2為決策變量，Z = 4 x1 + 3 x2為目標函數(shù)，約束（1.1）-（1.3）為函數(shù)約束，約束（1.4）為非負約束。決策變量的任何一個取值稱為模型的一個解，若解滿足所有約束條件，則稱為可行解，反之（至少違反一個約束條件），稱其為非可行解，使目標函數(shù)值最大化的可行解稱為最優(yōu)解。,成本收益平衡問題,成本收益平衡問題（ Cost-benefit-trade-o

7、ff Problem ） 是一類線性規(guī)劃問題，這類問題中，通過選擇各種 活動水平的組合，從而以最小的成本來實現(xiàn)最低可 接受的各種收益的水平。這類問題的共性是，所有 的函數(shù)約束均為收益約束，并具有如下的形式：  完成的水平 ? 最低可接受的水平,成本效益平衡問題,某飼料公司希望用玉米、紅薯兩種原料配制一種混合飼料，各種原料包含的營養(yǎng)成份和采購成本都不相同，公司管理層希望能夠確定混合飼料中各種原料的數(shù)量，使得飼料

8、能夠以最低的成本達到一定的營養(yǎng)要求。研究者根據(jù)這一目標收集到的有關數(shù)據(jù)如下：,成本效益平衡問題,為建立線性規(guī)劃模型，我們引入變量如下：x1 = 混合飼料中玉米的數(shù)量x2 = 混合飼料中紅薯的數(shù)量,成本效益平衡問題,目標函數(shù)是Z = 0.8 x1 + 0.5 x2，表示飼料的成本函數(shù)，即如何確定x1、x2使得成本Z = 0.8 x1 + 0.5 x2最低且滿足最低營養(yǎng)要求的約束，這些約束條件是：碳水化合物需求： 8 x1 + 4

9、 x2 ≥20蛋白質需求： 3 x1 + 6 x2 ≥18維他命需求： x1 + 5 x2 ≥16另有非負約束：x1 ≥0， x2 ≥0,成本效益平衡問題,因此，這個問題的線性規(guī)劃模型為：,物流網(wǎng)絡配送問題,偉達物流公司需將甲、乙、丙三個工廠生產的一種新產品運送到A、B兩個倉庫，甲、乙兩個工廠的產品可以通過鐵路運送到倉庫A，數(shù)量不限；丙工廠的產品可以通過鐵路運送到倉庫B，同樣，產品數(shù)量不限。由于鐵路運輸

10、成本較高，公司也可考慮由獨立的卡車來運輸，可將多達80個單位的產品由甲、乙、丙三個工廠運到一個配送中心，再從配送中心以最多90單位的載貨量運到各個倉庫。公司管理層希望以最小的成本來運送所需的貨物。,物流網(wǎng)絡配送問題,需要收集每條線路上的單位運輸成本和各工廠產品的產量以及各倉庫分配量等數(shù)據(jù)：,物流網(wǎng)絡配送問題,為了更清楚地說明這個問題，我們用一個網(wǎng)絡圖來表示該網(wǎng)絡配送問題（見圖2-1）。圖中節(jié)點v1、v2、v3表示甲、乙、丙三個工廠，節(jié)點

11、v4表示配送中心，節(jié)點v5、v6表示兩個倉庫；每一條箭線表示一條可能的運輸路線，并給出了相應的單位運輸成本，對運輸量有限制的路線的最大運輸能力也同時給出。,物流網(wǎng)絡配送問題,物流網(wǎng)絡配送問題,我們要解決的是各條路線最優(yōu)運輸量，引入變量fij表示由 vi經(jīng)過路線(vi,vj)運輸?shù)絭j的產品數(shù)。問題的目標是總運輸成本最小化，總運輸成本可表示為：總運輸成本 = 7.5 f15+ 3 f14 + 8.2 f25 + 3.5 f24 + 2.

12、3 f45 + 3.4 f34 + 2.3 f46 + 9.2 f36,物流網(wǎng)絡配送問題,相應的約束條件包括對網(wǎng)絡中的每個節(jié)點的供求平衡約束。對生產節(jié)點v1、v2、v3來說，由某一節(jié)點運出的產品數(shù)量等于其產量，即： f15 + f14 = 100 f25 + f24 = 80 f34 + f36 = 70,物流網(wǎng)絡配送問題,對配送中心v4，運進的產品數(shù)量等于運出的產品數(shù)量： f14 + f24 + f34 = f45 + f46

13、對倉庫v5、v6，運進的產品數(shù)量等于其需求量 f15 + f25+ f45 = 120 f46+ f36 = 130,物流網(wǎng)絡配送問題,此外，對網(wǎng)絡中有運輸容量限制的路線的約束是：該路線上的運輸產品數(shù)量不超過該線路的運輸能力，即：f14≤80， f24 ≤80， f34≤80， f45 ≤90， f46 ≤90。并且，所有fij ≥0（非負約束）。,物流網(wǎng)絡配送問題,共同的特征,從以上幾個例子可以看出，線性規(guī)劃問題有如

14、下共同的特征：每個問題都用一組決策變量（x1, x2, . . . , xn ），這組決策變量的值都代表一個具體方案；有一個衡量決策方案優(yōu)劣的函數(shù)，它是決策變量的線性函數(shù)，稱為目標函數(shù)。按問題不同，要求目標函數(shù)實現(xiàn)最大化或最小化；存在一些約束條件，這些約束條件包括①函數(shù)約束，可以用一組決策變量的線性函數(shù)（稱為約束函數(shù)）大于等于“≥”、小于等于“≤”或等于“=”一個給定常數(shù)（稱為右端項）；②決策變量的非負約束。,一般形式,線性規(guī)劃的

15、一般形式為：,資源分配問題一般形式,資源分配問題是將有限的資源分配從事各種活動的線性規(guī)劃問題，其一般形式可以描述為：管理層計劃用m種資源去從事n種活動，通過收集每種資源的總量和每種活動單位資源使用量以及單位貢獻等數(shù)據(jù)如下表所示，來確定活動的數(shù)量使得在資源許可的條件下貢獻最大。,資源分配問題一般形式,資源分配問題一般形式,我們用表示xj第j種活動的數(shù)量(水平)，則目標函數(shù) 最大化。對于第i種資源， 我們有約束條件：

16、 即資源消耗量不超過的資源總量,資源分配問題一般形式,因此，這類問題的數(shù)學模型為：,成本效益平衡問題一般形式,以上所討論的成本效益平衡問題是通過選擇各種活動水平的組合，從而以最小的成本實現(xiàn)最低可接受的各種效益水平。該問題的一般形式可描述為：管理層計劃用n種活動去提高m種效益的水平，通過調查得知每種活動對各種效益的單位貢獻、每種活動的單位成本以及每種效益的最低可接受水平如表,成本效益平衡問題一般形式,成本效益平衡問題一般形式,

17、我們用表示xj第j種活動的數(shù)量(水平)，則目標函數(shù) 最小化。對于第i種效益，我們有,成本效益平衡問題一般形式,因此，這類問題的數(shù)學模型為：,物流網(wǎng)絡配送問題一般形式,物流網(wǎng)絡配送問題一般形式可描述為：假定在一n個頂點m條?。ň€路）的運輸網(wǎng)絡中，有若干發(fā)點發(fā)送一定數(shù)量的物資流，同時又有若干收點接收這些物資流。由于每條弧運輸費用不同，運輸能力也有一定限制，管理者希望以最小的運輸成本完成由發(fā)點到收點的運輸配送。,物流網(wǎng)絡配送問題一般形式,

18、我們用fij表示由 vi經(jīng)過路線(vi,vj)運輸?shù)絭j的流量， Cij表示線路(vi,vj)的最大運輸能力（容量限制）， wij表示由頂點vi沿線路(vi,vj)流向vj的單位流量成本。,物流網(wǎng)絡配送問題一般形式,物流網(wǎng)絡配送問題模型為 :,線性規(guī)劃問題的圖解法,當決策變量只有兩個時，線性規(guī)劃問題可以用在平面上作圖的方法求解，這種方法稱為圖解法。由于這種方法簡單、直觀、容易理解，所以有助于了解線性規(guī)劃問題的實質和求解的原理?，F(xiàn)用

19、紅星重型機械廠的產品組合問題中的線性規(guī)劃來說明圖解法,線性規(guī)劃問題的圖解法,紅星重型機械廠的產品組合問題的線性規(guī)劃問題：,線性規(guī)劃問題的圖解法,我們首先建立x1O x2坐標平面（見圖2-2），坐標系上橫軸是x1軸，縱軸是x2軸。由非負約束x1 ≥0， x2 ≥0可知，所有可行解的集合（稱為可行域）應在第一象限。然后，我們要逐個地查看每個函數(shù)約束都允許的非負解，再考慮所有的約束條件。第一個函數(shù)約束x1 ≤6，截取x1軸的直線x1 = 6

20、的線上或線左邊的解是滿足這個約束條件的；第二個約束2x2 ≤8，有相似的結果，即x2 = 4線及下方的解滿足這個約束。我們將函數(shù)約束條件的邊界直線稱為約束邊界，相應的方程稱為約束邊界方程,線性規(guī)劃問題的圖解法,線性規(guī)劃問題的圖解法例1,確定了可行域以后，我們希望找出哪些解是最優(yōu)解，即使目標函數(shù)Z = 4x1 + 3x2盡可能大的可行解。我們給目標函數(shù)一個值，例如給定Z =12，可以在圖上畫出一條直線4x1 + 3x2 = 12（見圖1-

21、3），在直線上的任一點處，對應的目標函數(shù)值均為12，故稱該直線為目標函數(shù)的等值線。Z =12只是目標函數(shù)的一個給定值，對于其它Z的給定值，如Z = 15也可在圖上畫出一條直線4x1 + 3x2 = 15，顯然，對于Z的不同給定值k，4x1 + 3x2 = k是一組平行的直線族，當k的值由小變大時，目標函數(shù)的等值線平等移動，它與可行域的最后一個交點（一般是可行域的一個頂點）就是所求的最優(yōu)點，即圖2-3中的B點,線性規(guī)劃問題的圖解法,線性規(guī)

22、劃問題的圖解法,由上可以看出，線性規(guī)劃問題的最優(yōu)解出現(xiàn)在可行域的一個頂點上，此時線性規(guī)劃問題有唯一最優(yōu)解。但有時線性規(guī)劃問題還可能出現(xiàn)有無窮多個最優(yōu)解、無有限最優(yōu)解、甚至沒有可行解的情況，我們仍通過例子說明。,線性規(guī)劃問題的圖解法,（1）無窮多最優(yōu)解。若將上例中的目標函數(shù)變?yōu)榍驧ax Z = 4x1 + 6x2，則目標函數(shù)的等值線與邊界線2x1 + 3x2 = 18平行，線段BC上的任意一點都使Z取得相同的最大值，此時線性規(guī)劃問題有無窮