【正文】 第三章 線性規(guī)劃模型 應(yīng)用運(yùn)籌學(xué) 浙江大學(xué)管理學(xué)院 杜紅 博士 副教授 第三章 線性規(guī)劃模型 ? 線性規(guī)劃問題的提出 ? 線性規(guī)劃問題的建模 ? 典型特征和基本條件 ? 一般模型和標(biāo)準(zhǔn)模型 ? 線性規(guī)劃的圖解方法 ? 敏感分析與影子價格 ? 線性規(guī)劃模型的應(yīng)用 ? 線性規(guī)劃問題的提出 解決有限資源的最佳分配問題。即如何對有限的資源作出最佳方式的調(diào)配和最有利的使用，以使最充分地發(fā)揮資源的效能去獲取最佳的經(jīng)濟(jì)效益。 線性規(guī)劃（ Linear Programming, LP) 康托洛維奇 1939 《 生產(chǎn)組織與計劃中 的數(shù)學(xué)方法 》 丹捷格 （美） 1947 單純形方法 第三章 線性規(guī)劃模型 ? 線性規(guī)劃問題的提出 線性規(guī)劃（ LP)問題包含下列要素： 變量： 決策要控制的因素 目標(biāo)： 決策目標(biāo)（最優(yōu)）的數(shù)學(xué)描述 約束條件： 實現(xiàn)目標(biāo)的一組限制條件 求 LP問題： 在約束條件下使目標(biāo)最優(yōu)的一組 變量的取值 解決環(huán)節(jié)： 確定問題、建立模型、問題求解、 經(jīng)濟(jì)分析、敏感性分析 第三章 線性規(guī)劃模型 ? 建立線性規(guī)劃問題模型 線性規(guī)劃問題舉例：教材 P40 LP模型： 決策變量：每周的生產(chǎn)批次 G、 T 目標(biāo)函數(shù)： max Z＝ 30 G+20 T （獲利最大） 約束條件： 1 G + 2 T≤40 （配料工序約束） (.) 2 G + 1 T≤40 （整流工序約束） 1 G + 1 T≤25 （包裝工序約束） G≥0。 T≥0 （生產(chǎn)批次的非負(fù)約束） 第三章 線性規(guī)劃模型 第三章 線性規(guī)劃模型 ?建立線性規(guī)劃問題模型 總結(jié)模型構(gòu)建的一般思路： 確定該 LP問題的目標(biāo)是什么？ 實現(xiàn)目標(biāo)取決于什么因素和條件？ 確定哪幾個因素為決策變量？ 目標(biāo)如何用決策變量來加以描述？ 約束條件如何表達(dá)？ 決策變量本身是否有限制條件？ 第三章 線性規(guī)劃模型 ? 例 31:請你構(gòu)建以下問題的 LP模型： 某工廠擁有 A、 B、 C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示： 用線性規(guī)劃制訂使總利潤最大的生產(chǎn)計劃。 每件產(chǎn)品占用的 機(jī)時數(shù)（小時 / 件） 產(chǎn)品甲 產(chǎn)品乙 產(chǎn)品丙 產(chǎn)品丁 設(shè)備能力 （小時） 設(shè)備 A 1 .5 1 .0 2 .4 1 .0 2 0 0 0 設(shè)備 B 1 .0 5 .0 1 .0 3 .5 8 0 0 0 設(shè)備 C 1 .5 3 .0 3 .5 1 .0 5 0 0 0 利潤 （元 / 件） 5 .24 7 .30 8 .34 4 .18 第三章 線性規(guī)劃模型 ? 建立的模型如下： 設(shè)變量 xi為第 i種產(chǎn)品的生產(chǎn)件數(shù)（ i＝ 1， 2， 3，4），目標(biāo)函數(shù) Z為相應(yīng)的生產(chǎn)計劃可以獲得的總利潤。在加工時間以及利潤與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，可以建立如下的線性規(guī)劃模型： max Z = + + + . + + + ≤2022 + + + ≤8000 + + + ≤5000 x1, x2, x3, x4 ≥0 ? 求解這個線性規(guī)劃，可以得到最優(yōu)解為： x1= x2=1500 x3=0 x4= ? 最大利潤為： z=（元） ? 請注意最優(yōu)解中利潤率最高的產(chǎn)品丙在最優(yōu)生產(chǎn)計劃中不安排生產(chǎn)。說明按產(chǎn)品利潤率大小為優(yōu)先次序來安排生產(chǎn)計劃的方法有很大局限性。尤其當(dāng)產(chǎn)品品種很多，設(shè)備類型很多的情況下，用手工方法安排生產(chǎn)計劃很難獲得滿意的結(jié)果。另外，變量是否需要取整也是需要考慮的問題。 第三章 線性規(guī)劃模型 ? 總結(jié)：線性規(guī)劃問題的典型特征 ? 可用一些變量表示這類問題的待定方案，這些變量 （決策變量）的一組值代表一個具體方案； ? 存在一定的約束條件，這些約束條件都能用關(guān)于 決策變量的線性不等式或等式來表示； ? 有一個期望達(dá)到的目標(biāo)，這個目標(biāo)能以某種確定的數(shù)量指標(biāo)刻劃出來，而這種數(shù)量指標(biāo)可表示為關(guān)于決策變量的線性函數(shù)，按所考慮的問題的不同，要求該函數(shù)值最大化或最小值。 第三章 線性規(guī)劃模型 ? 線性規(guī)劃問題的基本要求 ? 目標(biāo)函數(shù)和約束條件必須是線性函數(shù)； 線性表達(dá)：相加性、比例性 ? 決策變量的連續(xù)分布； 不限于整數(shù)，可以是小數(shù)，但不能四舍五入 ? 目標(biāo)函數(shù)的單一性； 多目標(biāo)是要設(shè)法簡化成單目標(biāo) ? 模型必須是確定型的； 所有參數(shù) (a、 b、 c)都應(yīng)是確定值 ? 決策變量的非負(fù)性 第三章 線性規(guī)劃模型 ? 線性規(guī)劃問題模型的一般形式： 目標(biāo)函數(shù)： 約束條件： m a x ( m i n ) z c x c x c xn n? ? ? ?1 1 2 2 ?mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(..22112222212111212111????????????????????????第三章 線性規(guī)劃模型 0x,x,x n21 ??? 線性規(guī)劃問題一般模型的簡化形式： 目標(biāo)函數(shù)： max Z = ∑Cj Xj 約束條件： ∑ai j Xj ≥(=, ≤) bi Xj ≥ 0 i = 1,2,3, …… ,m j = 1,2,3, …… ,n 第三章 線性規(guī)劃模型 j=1 n Xj 的單位貢獻(xiàn) 第 i 資源的約束量 Xj 的技術(shù)性系數(shù)： 表示第 j 種活動消耗資源 i 的數(shù)量 ? 線性規(guī)劃問題的標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)為最大化； 約束條件（非負(fù)條件除外）全為等式； 約束條件右端項為大于等于零； max Z = C1X1+C2X2+…+C nXn . a11X1+a12X2+…+a 1nXn=b1 a21X1+a22X2+…+a 2nXn=b2 …………… am1X1+am2X2+…+a mnXn=bm X1,X2,...,Xn≥0 第三章 線性規(guī)劃模型 ? 將非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式 ? 目標(biāo)函數(shù)為最小化： 令 Z’ = Z , Z’ 為最大化問題。 ? 若約束條件是小于等于型： 在不等式左邊加上一個新變量（松弛變量）， 不等式改為等式，目標(biāo)函數(shù)中新變量系數(shù)為零。 ? 若約束條件是大于等于型： 在不等式左邊減去一個新變量（剩余變量）， 不等式改為等式，目標(biāo)函數(shù)中新變量系數(shù)為零。 第三章 線性規(guī)劃模型 ?將非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式 ? 若約束方程右端項 bi 0 : 在約束方程兩端乘以（－ 1），不等號改變方向，然后再轉(zhuǎn)化成等式。 ? 若決策變量 Xk沒有非負(fù)要求： 作 兩個新變量 Xk’≥0, Xk” ≥0,令 Xk＝ Xk’ Xk” ，在原有模型中用（ Xk’ － Xk” ）代替所有的 Xk， 在非負(fù)約束中增加 Xk’≥0和 Xk” ≥0 。 第三章 線性規(guī)劃模型 第三章 線性規(guī)劃模型 ? 例 32: 將下列 LP問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式