【天津大學】《運籌學》(精品課) P18 - 18. 線性規劃1 3節 教學錄像:綜合練習與應用(4)

长安书院_
146粉絲
1 次觀看·2026年7月14日
AI 生成·可能包含錯誤
我們將接着剛纔的應用的例子
我們進一步的來看一個應用小案例
這個仍然是一個應用問題
這個我們把它可以看作是一個小案例
是什麼樣的一個案例呢
叫做除塵器生產計劃
我們先來把問題看一下
某機器公司可以生產三種不同型號小型的除塵器
一種是政府用
一種是工業用
還有一種是民用除塵器
但是最後一種民用已經不生產了暫時
政府用除塵器的單價是1500
工業用除塵器的單價是1400
爲了完成個月的訂貨
生產車間需要制定出一個生產計劃
以使費用最低
因爲政府用和工業用除塵器
都分別有兩種型號
一種是使用最優質的原料
那麼就是高碳鋼和一些鋁
另一種是使用低碳鋼和大量的鋁
而金屬的價格差別很大
所以制定最優計劃也並非易事
客戶並不在意公司爲他們生產的除塵器
是屬於兩種型號中的哪一種
公司決定使用線性規劃制定最優計劃
問題的關鍵是滿足客戶的總訂貨要求
不超過公司的熟練工人與非熟練技術工人
以及生產能力的限制
以使生產費用最小
那麼通過這一段的介紹
我們知道這個公司
它可以生產三類的產品
都是除塵器
分別是政府用工業用和民用
民用暫時停止了生產
但是政府用和工業用都可以各分爲兩種型號
一種是用高碳鋼和一些鋁
另一種是使用低碳鋼和大量鋁
那麼由於客戶並不在意它是哪種型號
所以我們公司可以進行一個規劃和決策
到底生產兩種每一類產品
生產哪種型號多少數量
可以使總費用盡量小
這裏還提出了一些要求
就是說要滿足客戶的總訂貨
不超過公司的生產能力
這樣的一些個要求
那麼這裏我們還接着來看它的數據信息
你知道鋁的費用是107元
這個高碳鋼是38
低碳鋼29
下面一個表六給出了生產三種除塵器所需的原材料及勞動力工時等
好
我們看到這個表六呢
它的表頭我們先來看一下
給出的是我們這個的產品
能夠生產的三類產品
包括工業用政府用和民用
民用只是一個型號
清醒
而工業和政府用都各分爲兩種型號
那麼在表的左欄給出的是資源
我們生產每一種除塵器都要用到一些金屬
這裏主要涉及三種
分別是鋁高碳鋼和低碳鋼
還涉及什麼資源呢
就是熟練工和技術工的工時能力
另外呢
就是還要用到生產線
這個也是呢
以小時來計它的能力
並且這幾種資源的上限限量都在表的最右邊給出了
其中前三種資源沒有限制
後三種資源有限制
那麼我們接着來看
公司下個月的訂貨
已經知道是工業用除塵器三百隻
政府用除塵器五百隻
他們的金屬費用也已經是一個
已知的是一個三十萬五千八百二十元
好
這是我們知道案例給出了資源
單號數據和資源限量
接下來我們接着看
由於開工不足
公司決定再次生產民用輕型除塵器
它的售價是每隻八百元
數量不超過一百隻
我們還要求技術工人可以加班
加班的費用是每小時15元
剛纔我們知道
他的工人分爲兩類
一類是熟練工
一類是非熟練的技術工
其中技術工人可以加班
好
這個問題給出了之後
接下來的一個表期
給出了問題的線性規劃模型
因爲這個問題比較稍微大一點
所以我們這個模型直接給出了
在表期中
我們可以看到模型的變量設爲了九個
哪九個變量的這個模型
前三個是三種金屬的購買量
後五個是五種不同除塵器的生產數量
哪五種不同除塵器呢
就是這個工業和政府各兩個型號
另外就是民用的清醒一個型號
那麼這個是他的
後五個這個變量是五種型號的生產數量
那麼最後一個變量是熟練工加班的小時數
這是九個變量
那麼接下來約數模型中
我們這個表期中將還可以看到
約數也是九個
這九個約數分別是前三個約數
表示購買的三種金屬的數量
至少應該滿足生產的需求
後兩個表明
生產政府和工業用除塵器的數量要滿足訂貨
再後三個是熟練工技術工和生產線能力的限制
最後一個表示
最多可以生產一百個民用清醒除塵器
好
我們看到這個模型
那通過他這一段文字的敘述
感覺那他比一般的課上的立體
那要稍微複雜一點
而且他那是有一定的特色的
他的決策變量
不僅是產品的產量
而且把金屬的購買量
以及加班的小時數也都綜合在了要決策的變量中
好
下面呢
我們就來看一下這個表期
表期就是我們剛纔說的這個線性規劃的模型
在這個表期的表頭上
依次給出的是我們這個模型的九個變量
他們依次是購買鋁的數量
X1購買高碳鋼的數量
X2購買低碳鋼的數量
X3前三個變量
分別是購買三種金屬的數量
而後五個變量
也就是X4到X8
分別表示五種型號的產量
最後一個
X9表示加班的小時數
這個是表頭
它給出了變量設置
然後我們再看左邊這一列
左邊這一列
它的第一個式子成本
這是什麼呢
這個就是模型的目標
我們的目標
它設爲成本
那當然就是極小化了
然後接下來的是
下面這九個式子
就是剛纔說過的九個約束
九個約束
其中的前三個是金屬的購買數量
要滿足我們生產的需求
然後呢
後面的這兩個約束
是說的政府和工業用的
這個的生產量要滿足訂貨
因爲這個訂貨是已知的
那麼接下來呢
是這三個是技術工熟練工和生產線能力的限制
其中呢
這個就是技術工的是允許加班的
那麼我們最後一個
這個什麼呢
約束呢
表示家用的輕型儲存器
它的數量不能超過100
好
我們這個模型呢
它用一個表格來表示
是這個更加清楚一些
每一行的係數
只要乘以相應的變量
就得到了模型的表達式
比如說第一個式子是成本
這是目標
這個成本的就是購買三種金屬
它的單價
這是由剛纔前面的已知
然後後面呢
這個四種這個產品型號呢
沒有考慮它的成本
這個大家也可以考慮
想一下爲什麼
然後在輕型儲存器
就是最後的這個型號呢
它的因爲它的收益是800
收益是800
我們可以認爲成本是負的800
最後一個變量呢
它的成本是15元
就是加班一小時
那麼我們再來看一個式子
我們舉那麼一兩個分析一下
比如說這個鋁
它的表達式是什麼意思呢
這個鋁呢
就是大家看一下
它這個X1乘以這個係數-1
然後加上就是這個幾種型號
對鋁的需求資源單號數據
那麼就是它呢
應該是這個鋁的數量
它的購買量應當大於等於所需求的量
我們如果把這個X1呢
移到不等號的右端
現在不等號右端是零
就是變量我們都放在不等式的
不等號的左端了
但是你理解的時候可以這樣來分析
就是這個X1
它乘以-1就是-X1
如果移到這個式子的右端的話
就是X1大於等於
我們這個係數乘以相應的變量
這不就是鋁的實際用量嗎
那麼同樣這個後面的這個約束
都可以進行類似的解釋
其中這個政府和工業用
就是它的比如政府用
它的兩種型號的數量加起來
一共等於它的訂貨就可以
我們要決策的就是這兩種型號各生產多少
那麼這個我們剛纔說了
這個技術工是可以加班的
那麼技術工呢
除了它的這個幾種產品
對它資源單號數據之外
我們看到在加班小時數那裏
它的係數是-1
這個-1相應的是X9
就是加班的小時數
我們這個小時數是需要進行決策的變量
如果理解起來
我們也可以這樣來來理解
就是把這個加班的那一項
就是最後一項-的X9
如果移到不等式的右端
那就是原來的限制
也就是6400
技術工的原來的上限6400
再加上那個加班的小時數X9
這個就成爲我們的這個技術工的一個實際的上限
好
經過這樣的分析
我們基本上把這個模型的含義就解釋了
好
我們下面呢
對這個案例進行一些分析
我們考慮下列的問題
第一個問題是
下面個量
哪些在目標函數中考慮了
哪些沒有考慮
我們通過剛纔的模型的分析
我們知道
其中這個
第一個量
就是金屬的費用是考慮了的
第二個量
正常勞動成本
我們剛纔還記得
只考慮了加班的成本
正常的沒有考慮
加班的成本考慮了
管理的費用
沒有考慮
於是呢
這個問題
我們的回答
就是
這樣的一個結果
那麼通過這個呢
我們其實也可以
體會一下
哪些量
是可以在模型中優化的
適合在模型中優化的
哪些量
是不必要在模型中體現和優化
或者是很難以進行
計量和優化的
這個也是呢
我們在把線性規劃模型方法
應用在實際中的
通過這個案例呢
可以得到一些啓示
第二個問題
爲什麼在目標函數中
沒有考慮工業和政府用
除塵器的收益
卻考慮了民用除塵器的收益
這個含義呢
我們在前面也說了一下
就是
工業和政府用的除塵器的
它的收益呢
是固定的
它的訂貨也是固定的
但是民用的不是
民用的因爲我們並沒有事先知道
它究竟生產多少臺
而是通過模型優化計算以後
根據它的收益來計算
我們要決策的就是要
看一下它究竟應該生產多少
能使收益最優
因此我們這個回答呢
應該是前面那兩個
沒有考慮
就是它的這個收益是固定的
而後面那一個
因爲它是不是事先固定
是我們要優化的
所以我們要考慮
我們對上述的線性規劃模型
可以採用一些線性規劃的軟件
進行計算求解
因爲這個模型稍微大一點
比如我們採用lindo軟件
對模型計算的結果如下
我們知道計算軟件不是唯一的
我們這裏只是立舉了
一種軟件的計算結果
在這個計算軟件的輸出的結果當中
我們看一下
它的上半部分
我們看一下它的這個標題
是這個目標值
就是這一項
給出的是最優值
然後呢
這是variable是變量
那麼就是我們這個要求的這個解了
那麼這裏的那個第二列呢
給的就是這些解的
實際就是最優解
這些解的值就是最優解
最後一列給出的reduced cost
這個是我們曾經前面講過的差額成本
那麼下面我們呢
主要來看一下
它的這個就是最優解
最優解呢
我們這裏呢
就是由這個變量前面的假設的含義
可知
x123分別表示三種金屬的購買數量
x4是政府一型
x5政府二型
x6工業一型
x7工業二型
這幾個變量呢
是他們的生產數量
這些每個量
它的那個最優解的值都在第二列給出
這裏邊我們看到有一個x5
等於零
那這個就是在最優解中
政府二型不生產
那麼這個不生產的原因呢
肯定是從目標來決定的
我們看到它的差額成本是574.4
這說明呢
當它的這個收益增長574.4的時候
那麼它呢是才能考慮生產
另外呢
在這個最優解中的x9這個變量給出的是這個加班的小時數
x8這個變量給出的是這個輕型儲存器的生產數量
我們看到它是100
已經達到它的這個最大的那個的上限的量了
那麼下面這一部分的結果給出了什麼呢
它這個給出的是約數的
這個相應於每個約數的一個這個相關的信息
這些約數我們前面已經說過
一共有九個約數
這九個約數呢
分別是三種鋁和這個其他金屬的這個三種金屬的數量
要滿足使用的需求
另外呢
就是政府和工業的訂貨的需求
還有呢
就是這個技術工熟練工和生產能力的限制
以及輕型儲存器的數量的限制
我們看到呢
這個它的這幾種約數的
呃
我們看到這個第二列的數據給出的是
它的鬆弛或剩餘變量的值
呃
其中呢
都是零
基本上只有就是
呃
這個約數哈
就是熟練工的約數呢
它的這個呃
就是有
呃
1400的這個這個剩餘
那麼我們後面呢
給出的是那個隊友價格
也就是影子價格
呃
我們呢
是可以呢
這個看到呢
就是在這個熟練工
由於它熟練工
由於它是剩餘了1400
它的影子價格是等於零
這個是符合互補鬆弛定理的
呃
接下來呢
這個計算機的輸出啊
呃
還有一塊
這一塊呢
是靈敏度分析
呃
這一塊的上半部分給出的是
我們一看這個意思啊
就是它都是變量相應的
給出的是呢
這個目標中的係數
目標中的係數的這個變化範圍
就是和每個變量相應的價格
係數的靈敏度分析
這裏給出的是
它的當前值
還有它的
允許的
這個增加值增加多大
另外就是最右邊那一列給的是允許的減少的這個
呃
這個幅度的這個限度
然後接下來下面這一塊給出的是相應於約數的靈敏度分析
這個當然就是右端項資源限制項量
它的靈敏度分析了
同樣給出的是當前值
還有就是允許的增量的上限和減少的這個限度
好
呃
由於這個計算結果已經很清楚了
所以我們在這個基礎之上
呃
不難的對這個我們的案例啊
那個的進一步的一些分析啊
得到它的結論
我們來看一下
第二
第三個問題
問的是
民用氫型除塵器的數量爲何
其耗用各種金屬的數量是多少
這個因爲剛纔已經說過
就是在輸出結果中已經給出了最優解
氫型除塵器
它是最優計劃中生產100臺
那麼至於它的資源單號數據
我們在一開始題目中已經給出
我們前不是有一個單號的一個資源單號數據表嗎
那麼因此呢
我們用這個產量乘以它的單號就可以得到它實際的使用這些金屬的數量
問題四
技術工人加班費用是15元每小時
當這個費用變爲多大時
最優計劃將改變
那麼這個呢
呃就是關於價格係數的靈敏度分析
在我們的上一張幻燈片
呃就是在這個變它相應的這個變量的係數的靈敏度分析中可以得到答案
就是說呢
因爲它給出的
允許的那個範圍就是保持不變的範圍呢
是減少15至增加36.4
所以超出這個範圍
原來的最優計劃就將改變了
問題五
如果不允許加班
那麼總費用將如何變化呢
我們在這個問題中是允許加班的
對於不允許加班的情況
我們在本問題中呢
沒有給出確切的答案
所以我們這個可以選
不能確切得知
接下來的問題
第六個
假若熟練工的生產能力增加一小時
將會產生什麼影響
大家想熟練工
它的生產能力是一種資源
它增加一單位時
引起的目標的這個增量變化
實際就是影子價格
我們剛纔已經看到熟練工
其實呢
它已經剩餘了一些數量
所以它的影子價格是零
因此它再增加一小時
不會引起任何的影響
對這個成本和收益
第七個問題
假若工業用除塵器的訂貨增加一臺
那它的貢獻是什麼呢
我們這個呢
仍然是可以用它的影子價格來考量
就是它可以減少成本
852.2003
這個都是由那個
剛纔的計算機輸出的結果可以得到
第八個問題
爲使民用輕型除塵器市場擴大25臺
你願意再支付多少
由剛纔的靈敏度分析結果可知
如果擴大25臺
它是屬於這個約束的資源
保持最優積不變的那個範圍之內的
因此呢
可以直接用它的影子價格來進行分析和考量
也就是用它的影子價格
20就是25
現在是25臺
它的影子價格是296.7997
只要不超過這個的小於這個的這個額度
我們是可以考慮支付的
那麼問題9
此問題的最優解和最優質各是什麼
解釋其實際意義
我們在前面已經說過了
就是在計算結果表中已經可知
最後一個問題
政府二型在目標中的係數減少多少時
纔可能被生產
這個我們剛纔也已經說過
它的那個差額成本呢
是574.4
好的
那麼我們到這裏爲止
把這個就是除塵器生產計劃的案例呢
進行了一個分析
我們剛纔前面也說過了
這個案例呢
它更加接近實際一些
所以呢
我們根據這個分析呢
我們可以啊
對於將來用線性規劃的問題來解決真實的問題呢
應該是有一定的啓示的
好的
我們在前面已經介紹了各種的這個類型
以及綜合的應用和案例之後
我們最後一個問題
是一個研究性專題
我們來看一下
這個是個什麼問題呢
我們看一下問題
現在考慮線性規劃問題P
這是個具體的一個線性規劃
極小型Z等於X1加X2加1.5S3
約數呢
是X1加X3等於1
X2加S3等於1
X123大於等於0
這是一個具體的一個比較簡單的一個線性規劃
現在呢
我們請第一寫出它的對偶模型D
這個原來這個問題記作P
寫出對偶模型D之後
再用圖解法解對偶模型D
因爲我們看到這個原問題P
它是兩個約數
那麼它的對偶模型應該是兩個變量
所以可以用圖解法求解
第二問
將D也就是它的對偶模型
增加鬆弛變量後
化爲等式
這是第二問
這個我們是可以進行的
因爲我們實際看着這個模型
馬上就可以寫出它的對偶
或者想象一下它的對偶是什麼樣
剛纔說了它對偶是兩個變量
計爲Y1Y2
那麼由於原問題是三個變量
所以對偶是三個約數
那麼它的三個約數
它對偶是極大型
是小於等於約數
但是它的兩個變量
由於原問題是等式約數
所以它的對偶的兩個變量是自由變量
那麼這個對偶
既然它的約數是小於等於
所以可以增加鬆弛變量
化爲等式
第三問是
由互補鬆弛定理
本題的P和D的最優解
應當滿足這個互補鬆弛性
那麼它的那個增加的鬆弛變量
就是那個記作Sj
它和原問題的Xj相對應
它們二者乘積等於零
這是我們在互補鬆弛定理中講過的
這個對所有的J乘以
那麼假若還滿足
它們倆的相加
就是Xj加上Sj
嚴格大於零
則稱這個解是嚴格互補的
嚴格互補就是
這一對變量乘積等於零
它們倆至少有一個爲零
我們一般的解釋是這樣
但是假若它們倆只有一個爲零
也就是另一個不爲零
我們知道在線性規劃模型中
假若不爲零
它就得是大於零
因爲它都是非負的變量
如果是這樣的話呢
我們就可以稱這個解是嚴格互補的
這是對嚴格互補性和互補鬆弛定理的一般解釋
現在請以本問題來說明
當P和D中有多重最優解釋
則滿足嚴格互補條件的解
是多重最優解中的非頂點解
好
這個呢我們下面將用圖解法
因爲這個它隊友可以畫出圖來
我們可以看到這個頂點還是非頂點
可以比較直觀的看到
就是說我們這一問呢
可以在一會兒我們畫出圖來
我們再進行分析
問題給了一個提示
就是可由觀察法得到原問題P的一個
這個最優解呢
X星是001
好
我們下面呢對這個問題呢進行一個
這個分析和解答
我們剛纔呢已經說過了它的分析了
那麼接下來呢
我們就來看一下具體的解答
具體解答呢
就是我們這個什麼呢
這個就是先把隊友模型列出來
隊友模型列出來之後呢
它是兩個變量的問題
我們可以對它進行呢
就是說呀
這個圖解法來進行求解
那麼圖解法進行求解如圖所示
這道題
大家看到它的目標是Y1加Y2
是和這個就是一個其中的約數
它的係數相同
也就說明呢
它是這個多重最優解的情況
我們已經在圖上看到
最優的目標直線的位置
是和一個約數的邊界是重合的
我們這道題呢是個極大型
所以呢
它呢是最優的
這個目標直線的位置
它是向上斜上方移的
最後移到邊界的那個位置呢
取得最優位置
那麼我們這個問題呢
雖然是Y呢是一個自由變量
但是呢
由於這個目標
大家已經看到
它其實呢
它的最優的這個解
外的解實際都是這個
就是說呢是非負的
我們已經看到了它的這個位置
是在非負的範圍內
那麼我們在最優解的這個AB
線段上面
我們不難知道
它的兩個端點
或者叫頂點解
一個是A
一個是B
分別是0.51和10.5
這兩個是頂點最優解
但是這條線段上的
這個
所有的點實際都是它的最優解
其中呢
我們看到有一個A和B的
這個線段的這個終點呢
就是這個D
它呢也是一個這個最優解
好剛纔呢
是用圖解法
解了一下
對偶模型
那麼我們接着來
把第二問看一下
第二問呢
很簡單
就是把對偶模型
把它增加鬆弛變量
化爲等式
鬆弛變量分別記作S123
這裏的鬆弛變量的是非負的
好
這是第二
第二問
最後一問呢
就是第三問
第三問就是
請以本題爲例
考察這道題的互補鬆弛關係
它的嚴格互補性
我們剛纔題目已經提示了一個X星
它是原問題的最優解
那麼這個解和
我們這個對偶的頂點解
它的鬆弛變量
S
以及呢
頂點解A的鬆弛變量S
以及B的鬆弛變量相應的這個S
我們知道這個鬆弛變量
它實際是個向量在這裏面
每一個S呢
因爲這個S是S123嘛
所以它這個每個S呢
是由三個分量組成
這三個分量
恰好相應於原問題的
X123三個變量
由互補鬆弛性
它們的兩兩對應分量之積
應該等於零
但是呢
它滿足不滿足嚴格互補性呢
我們說呀
這個X星與兩個頂點解
就是A和B的頂點解相應的鬆弛變量
顯然是不滿足嚴格互補的
也就是說它並不能做到
每一對分量的之和大於零
也就至少有一個部位
就是它這個裏邊得有一個部位零
那麼它做不到
比如說我們這個X星
它和A點
那麼它這個第二個分量是零
而A的那個相應的S中第二個也是零
它這一對分量就不滿足嚴格互補性
但是呢
這個X星啊
它和非頂點解
也就是那個D點
它相應的那個這個鬆弛變量
它相應的鬆弛變量
就是這個S呢是零點二五零點二五零
它倆之間是滿足嚴格互補性的
也就是說呢
這個例子的分析
我們可以得到一個結論
這個結論雖然不是一般的
但是至少這個例子是這樣的
就是說呢
這個嚴格互補解是存在的
這是多重存在多重自由解的情況
而這個嚴格互補解是在非頂點解
達到
好
我們通過這個例子的初步的分析
我們其實呢
可以啊
對我們提出的這個問題
進行一個一般的進一步的研究
我們剛纔這個例子呢
是一個有多重自由解的情況
那麼如果
我們的原問題和隊友問題都是唯一解
那麼他也得滿足互補鬆弛關係
那這個時候的結論如何呢
是不是如果是唯一解的話
他就得是嚴格互補的呢
我們同學們
課下可以用已經做過的一些例子來加以驗證
接下來
我們可以考慮任何線性規劃的互補鬆弛關係
是否都一定存在嚴格互補解呢
我們爲了得到一般的結論
請大家可以課下進一步的研究
並查閱相關文獻
獲得答案
好
到這裏爲止呢
我們這個線性規劃
一至三節的綜合練習
我們就上到這裏了
希望大家能夠對線性規劃
這一個運籌學的最基本和有代表性的這一塊內容
能夠有深入的理解和掌握
謝謝大家
