經(jīng)濟(jì)數(shù)學(xué)課件：最優(yōu)配置與最佳效果分析

最優(yōu)配置與最佳效果分析名言拉普拉斯在數(shù)學(xué)中，我們發(fā)現(xiàn)真理的主要工具是歸納和模擬.故事在美國的一個(gè)鄉(xiāng)村，一個(gè)老農(nóng)與兒子相依為命。一天，一個(gè)人找到了老農(nóng)說：“我想把你的小兒子帶到城里去工作?！崩限r(nóng)氣憤地說：“不行，絕對(duì)不行，你滾出去吧！”這個(gè)人說：“如果我在城里給你的兒子找個(gè)對(duì)象，可以嗎？”老農(nóng)搖搖頭：“不行，快滾出去吧！”這個(gè)人又說：“如果我給你兒子找的對(duì)象，也就是你未來的兒媳婦是洛克菲勒的女兒呢？”老農(nóng)想了又想，最終同意了。過了幾天，這個(gè)人找到了美國首富、石油大王洛克菲勒說：“我想給你的女兒找個(gè)對(duì)象?！甭蹇朔评照f：“快滾出去吧！”這個(gè)人又說：“如果我給你女兒找的對(duì)象，也就是你未來的女婿，他是世界銀行的副總裁，可以嗎？”洛克菲勒想了想，就同意了。又過了幾天，這個(gè)人找到了世界銀行總裁說：“你應(yīng)該馬上任命一個(gè)副總裁！”總裁先生搖頭頭說：“不可能，這里這么多副總裁，我為什么還要任命一個(gè)副總裁呢，而且必須馬上？”這個(gè)人說：“如果你任命的這個(gè)副總裁是洛克菲勒的女婿，可以嗎？”總裁先生想了想，就同意了。當(dāng)然，這只是一個(gè)虛構(gòu)的小故事，卻告訴了我們一個(gè)道理，只有合理配置資源才能創(chuàng)造最大的價(jià)值。目錄安排生產(chǎn)問題及解決方案1.使用EXCEL求解線性規(guī)劃問題2.最優(yōu)配置問題典型案例3.進(jìn)一步學(xué)習(xí)的數(shù)學(xué)知識(shí)：單純形法4.

引例：美國空軍為了保證士兵的營養(yǎng)，規(guī)定每餐的食品中，要保證一定的營養(yǎng)成份，例如蛋白質(zhì)、脂肪、維生素等等，都有定量的規(guī)定。當(dāng)然這些營養(yǎng)成分可以由各種不同的食物來提供，例如牛奶提供蛋白質(zhì)和維生素，黃油提供蛋白質(zhì)和脂肪，胡蘿卜提供維生素，等等。由于戰(zhàn)爭條件的限制，食品種類有限，又要盡量降低成本，于是在一盒套餐中，如何決定各種食品的數(shù)量，使得既能滿足營養(yǎng)成分的需求，又可以降低成本？一、問題引入第一節(jié)安排生產(chǎn)問題及解決方案

在本例中要利用有限的資源，去使得一份套餐既能滿足營養(yǎng)要求又可以降低成本。用數(shù)學(xué)語言來說，就是在一定的約束條件下，求線性函數(shù)的最大和最小值問題。更加廣義的來看待配餐問題，我們知道，現(xiàn)代的企業(yè)管理問題千變?nèi)f化，企業(yè)內(nèi)部的生產(chǎn)計(jì)劃有各種不同的情況。從空間層次看，在工廠要根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制定產(chǎn)品的生產(chǎn)計(jì)劃，在車間級(jí)則要根據(jù)產(chǎn)品生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制定生產(chǎn)批量計(jì)劃。而這類問題都可以通過建立相應(yīng)的線性規(guī)劃模型來解決?！締栴}分析】第一節(jié)安排生產(chǎn)問題及解決方案

某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，要用3種不同的原料A、B、C．從工藝資料可知：每生產(chǎn)1噸甲產(chǎn)品，需耗用3種原料分別為1，1，0單位；生產(chǎn)1噸乙產(chǎn)品，需耗用3種原料分別為1，2，1單位．每天原料供應(yīng)的能力分別為6，8，3單位．又知道每生產(chǎn)1噸甲產(chǎn)品，企業(yè)的利潤收入為300元，每生產(chǎn)1噸乙產(chǎn)品，企業(yè)利潤收入為400元．那么該企業(yè)應(yīng)該如何安排生產(chǎn)計(jì)劃，使一天的總利潤最大呢？二、典型問題解決方案【問題1】第一節(jié)安排生產(chǎn)問題及解決方案

設(shè)企業(yè)每天生產(chǎn)甲產(chǎn)品為噸，生產(chǎn)乙產(chǎn)品為噸，稱，為決策變量，他們不能任意取值，要受到可供利用的原料資源數(shù)量的限制．又因?yàn)楫a(chǎn)品的產(chǎn)量一般是一個(gè)非負(fù)數(shù)，所以有，，稱為非負(fù)約束．【解決方案】第一節(jié)安排生產(chǎn)問題及解決方案對(duì)于原料

我們有如下的不等式：

上面得到的3種原料的線性不等式是決策變量，取值所必須滿足的條件，它們約束了決策變量，不能取任意值，稱它們?yōu)榧s束條件．由于生產(chǎn)1噸甲產(chǎn)品企業(yè)的利潤收入為300元，生產(chǎn)1噸乙產(chǎn)品企業(yè)的利潤收入為400

元．于是甲乙兩種產(chǎn)品的總利潤為它是決策變量的線性函數(shù)，并稱此函數(shù)為目標(biāo)函數(shù).

綜上所述，得到描述原問題的數(shù)學(xué)模型如下：第一節(jié)安排生產(chǎn)問題及解決方案同時(shí)，我們可看出（1）式是由三部分組成的：①一組決策變量；②一個(gè)線性目標(biāo)函數(shù)；③一組線性約束方程．我們把滿足上述三個(gè)條件的最優(yōu)化問題稱為線性規(guī)劃問題，條件①、②、③稱為線性規(guī)劃問題的三要素．第一節(jié)安排生產(chǎn)問題及解決方案

在線性規(guī)劃問題中，滿足約束條件的解稱為可行解，所有可行解的集合稱為可行集；使目標(biāo)函數(shù)取值最大或最小的可行解稱為最優(yōu)解，對(duì)應(yīng)于最優(yōu)解的目標(biāo)函數(shù)值稱為最優(yōu)值．第一節(jié)安排生產(chǎn)問題及解決方案案例1

求解線性規(guī)劃問題第二節(jié)使用Excel求解線性規(guī)劃問題一、典型案例二、解決方案

Excel具有強(qiáng)大的規(guī)劃求解功能，可以解決最多有200個(gè)變量，100個(gè)外在約束和400個(gè)簡單約束（決策變量整數(shù)約束的上下邊界）的線性規(guī)劃與非線性規(guī)劃問題．因此，可通過Excel的規(guī)劃求解功能實(shí)現(xiàn)問題的求解。第二節(jié)使用Excel求解線性規(guī)劃問題第一步：啟動(dòng)Excel，在工作表中的A1，A2，A3，A10，E3，F(xiàn)3單元格中分別輸入文字“目標(biāo)函數(shù)系數(shù)”，“決策變量”，“約束條件”，“目標(biāo)函數(shù)值”，“約束條件左端的值”，“約束條件右端的值”；在B1，C1，D1單元格中輸入目標(biāo)函數(shù)的系數(shù)1，-2，1，在B4，C4，D4單元格中輸入第一個(gè)約束條件的系數(shù)1，1，1；同理，在相應(yīng)單元格中輸入其他約束條件的系數(shù)與約束條件右端的值，如下圖9-1所示：

三、Excel演算步驟第二節(jié)使用Excel求解線性規(guī)劃問題第二步：計(jì)算約束條件左端的值和目標(biāo)函數(shù)值．因?yàn)榧s束條件左端的值等于約束條件的系數(shù)乘以相應(yīng)的決策變量，所以在E4單元格中輸入公式“=B4*B2+C4*C2+D4*D2”，在E5單元格中輸入公式“=B5*B2+C5*C2+D5*D2”，依次類推在E9單元格中輸入公式“=B9*B2+C9*C2+D9*D2”；目標(biāo)函數(shù)的值等于目標(biāo)函數(shù)系數(shù)乘以決策變量，從而在D10單元格中輸入公式“=B1*B2+C1*C2+D1*D2”，如圖9-2所示．三、Excel演算步驟第二節(jié)使用Excel求解線性規(guī)劃問題第三步：單擊【工具】菜單中的【規(guī)劃求解】命令，在彈出的規(guī)劃求解對(duì)話框中輸入各項(xiàng)參數(shù)．（1）設(shè)置目標(biāo)單元格和可變單元格

在“規(guī)劃求解參數(shù)”對(duì)話框中選中“最大值”前的單選按鈕，設(shè)置目標(biāo)單元格為“$D$10”，可變單元格為“$B$2:$D$2”，如圖9-3所示．三、Excel演算步驟第二節(jié)使用Excel求解線性規(guī)劃問題（2）添加約束條件單擊【規(guī)劃求解參數(shù)】對(duì)話框中的【添加】按鈕，打開【添加約束】對(duì)話框，單擊單元格引用位置文本框，然后選定工作表中的E4單元格，則在文本框中顯示“$E$4”，選擇“<=”約束條件；單擊約束值文本框，然后選定工作表中的F4單元格，如圖9-4所示．三、Excel演算步驟第二節(jié)使用Excel求解線性規(guī)劃問題第四步：在【規(guī)劃求解參數(shù)】對(duì)話框中單擊【求解】按鈕，彈出圖9-5所示的【規(guī)劃求解結(jié)果】對(duì)話框，選中【保存規(guī)劃求解結(jié)果】單選按鈕．三、Excel演算步驟第二節(jié)使用Excel求解線性規(guī)劃問題

第五步：在【規(guī)劃求解結(jié)果】對(duì)話框中，單擊【確定】按鈕，工作表中就顯示出規(guī)劃求解的結(jié)果，如圖9-6所示．三、Excel演算步驟

從上圖可以很容易看出，當(dāng)變量時(shí)，目標(biāo)函數(shù)的最大值為．第二節(jié)使用Excel求解線性規(guī)劃問題

某機(jī)械廠需要長80厘米的鋼管800根，長60厘米的鋼管300根，這兩種長度不同的鋼管由長200厘米的鋼管截得．工廠該如何下料，使得用料最省?第三節(jié)最優(yōu)配置問題典型案例案例1鋼管下料問題對(duì)于下料問題，首先必須從問題中找到可能的下料方式．本問題是要用長200厘米的鋼管截得長80厘米與60厘米兩種型號(hào)的鋼管，下料方式一共有三種：第一種下料方式是一根長200厘米的鋼管截得長80厘米的鋼管兩根；第二種下料方式是一根長200厘米的鋼管截得長80厘米的鋼管一根與長60厘米的鋼管兩根；第三種下料方式是一根長200厘米的鋼管截得長60厘米的鋼管三根．知道了下料方式以后，我們分情況討論即可得到下料問題的數(shù)學(xué)規(guī)劃模型?！締栴}分析】

決策變量：設(shè)三種下料方式用掉長200厘米的鋼管分別為,,根．【模型建立】目標(biāo)函數(shù)：用掉的長200厘米的鋼管數(shù)量最少，即約束條件：對(duì)于所需長80厘米的鋼管：第一種下料方式截得根，第二種下料方式截得根，共截得根，它不能少于所需數(shù)量

800根，即第三節(jié)最優(yōu)配置問題典型案例對(duì)于所需長60厘米的鋼管：第二種下料方式截得第三種下料方式截得根，共截得根，根，它不能少于所需數(shù)量200根，即非負(fù)約束：又考慮到都是根數(shù)，因而它們?nèi)≈抵荒苁钦麛?shù)或零，表示為：第三節(jié)最優(yōu)配置問題典型案例綜上所述，得鋼管下料問題的數(shù)學(xué)規(guī)劃模型為：第三節(jié)最優(yōu)配置問題典型案例【模型求解】第一步：在Excel工作表中建立線性規(guī)劃模型，并計(jì)算約束條件左端的值和目標(biāo)函數(shù)值，如圖9-8所示：第二步：單擊【工具】菜單下的【規(guī)劃求解】選項(xiàng)，在彈出的規(guī)劃求解對(duì)話框中輸入各項(xiàng)參數(shù)．（1）設(shè)置目標(biāo)單元格和可變單元格第三節(jié)最優(yōu)配置問題典型案例【模型求解】

（2）添加約束條件考慮到，，都是根數(shù)，因而它們的取值只能是正整數(shù)或零，所以添加約束條件時(shí)需添加可變單元格等于整數(shù)．單擊單元格引用位置，然后選中B2單元格，在單元格引用位置會(huì)出現(xiàn)“$B$2”，約束條件選擇“int”，如圖9-10．依次方法添加決策變量，的整數(shù)約束條件．第三節(jié)最優(yōu)配置問題典型案例【模型求解】第三步：單擊【求解】按鈕，彈出【規(guī)劃求解結(jié)果】對(duì)話框，同時(shí)結(jié)果顯示在工作表中，如圖9-11所示．即用350根長200厘米的鋼管用于第一種方式的下料，用100根200厘米的鋼管用于第二種方式的下料，總共需要用到的鋼管數(shù)量為450根．第三節(jié)最優(yōu)配置問題典型案例

某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來水由三個(gè)水庫供應(yīng)，四個(gè)區(qū)每天必須得到保證的基本生活用水量分別為30，70，10，10千噸，但由于水源緊張，三個(gè)水庫每天最多只能供應(yīng)50，60，50千噸自來水．由于地理位置的差別，自來水公司從各水庫向各區(qū)送水所付出的引水管理費(fèi)不同.其他管理費(fèi)都是450元/千噸．根據(jù)公司規(guī)定，各區(qū)用戶按照統(tǒng)一標(biāo)準(zhǔn)900元/千噸收費(fèi)．此外，四個(gè)區(qū)都向公司申請(qǐng)了額外用水量，分別為每天50，70，20，40千噸．該公司如何分配供水量，才能獲利最多？案例2自來水運(yùn)送問題(運(yùn)輸問題)第三節(jié)最優(yōu)配置問題典型案例引水管理費(fèi)（元/千噸）甲乙丙丁A160130220170B140130190150C190200230【模型建立】

決策變量：

假設(shè)三個(gè)水庫

分別向甲、乙、丙、丁四區(qū)的供水量為.由于水庫與丁之間沒有輸水管道，即，此只有11個(gè)決策變量．

第三節(jié)最優(yōu)配置問題典型案例目標(biāo)函數(shù)：問題的目標(biāo)可以從獲利最多轉(zhuǎn)化為引水管理費(fèi)最少，于是有第三節(jié)最優(yōu)配置問題典型案例約束條件：約束條件有兩類：一類是水庫的供應(yīng)量限制，另一類是各區(qū)的需求量限制．由于供應(yīng)量總能賣出并獲利，水庫的供應(yīng)量限制可以表示為：考慮到各區(qū)的基本生活用水與額外用水量，需求量限制可以表示為：第三節(jié)最優(yōu)配置問題典型案例綜上所述，得自來水運(yùn)送問題的數(shù)學(xué)規(guī)劃模型為：第三節(jié)最優(yōu)配置問題典型案例【模型求解】第一步：在Excel工作表中建立線性規(guī)劃模型，并計(jì)算約束條件左端的值和目標(biāo)函數(shù)值．本例中決策變量有12個(gè)，在Excel工作表中B2至M2單元格，分別表示決策變量（束條件左端的值和目標(biāo)函數(shù)的值，如圖9-12所示．)，然后輸入各個(gè)約束條件（包括非負(fù)條件）的系數(shù)，同時(shí)計(jì)算約第三節(jié)最優(yōu)配置問題典型案例【模型求解】第二步：在彈出的【規(guī)劃求解參數(shù)】對(duì)話框中輸入?yún)?shù)．單擊【求解】按鈕，得到圖9-13所示結(jié)果．因此，最佳送水方案為：

水庫向乙區(qū)供應(yīng)50千噸，

水庫向乙、丁區(qū)分別供應(yīng)50，10千噸，

水庫向甲、丙區(qū)分別供應(yīng)40，10千噸．第三節(jié)最優(yōu)配置問題典型案例第四節(jié)進(jìn)一步學(xué)習(xí)的數(shù)學(xué)知識(shí)：單純形法一、線性規(guī)劃問題的標(biāo)準(zhǔn)型

線性規(guī)劃問題的標(biāo)準(zhǔn)型主要是針對(duì)線性規(guī)劃問題的約束條件而言的，具體表現(xiàn)形式為：其中皆非負(fù)．

一、線性規(guī)劃問題的標(biāo)準(zhǔn)型

在解決實(shí)際問題時(shí)，根據(jù)實(shí)際問題建立的模型常常不是標(biāo)準(zhǔn)型，那么如何把一個(gè)線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)型呢？(1)若求目標(biāo)函數(shù)

的最小值，則引進(jìn)新的目標(biāo)函數(shù)

(2)若約束條件中含有線性不等式約束，則需要引進(jìn)新的非負(fù)變量，把線性不等式約束化為線性等式約束，這樣引進(jìn)的新非負(fù)變量稱為松弛變量．(a)當(dāng)約束條件是時(shí)，在不等式左端加上松弛變量，將不等式約束化為等式約束．(b)當(dāng)約束條件是時(shí)，在不等式左端加上松弛變量，將不等式約束化為等式約束．第四節(jié)進(jìn)一步學(xué)習(xí)的數(shù)學(xué)知識(shí)：單純形法一、線性規(guī)劃問題的標(biāo)準(zhǔn)型

(3)若約束條件中線性等式約束的常數(shù)項(xiàng)為負(fù)值，則將該約束條件兩端同時(shí)乘以，使得常數(shù)項(xiàng)為正值．(4)若對(duì)某一變量無約束，可令作變量替換,使得對(duì)全部變量皆有非負(fù)限制．第四節(jié)進(jìn)一步學(xué)習(xí)的數(shù)學(xué)知識(shí)：單純形法二、單純形法的原理與步驟例

運(yùn)用單純形法求解線性規(guī)劃問題第四節(jié)進(jìn)一步學(xué)習(xí)的數(shù)學(xué)知識(shí)：單純形法第一步：引進(jìn)松弛變量，將所給線性規(guī)劃問題化為標(biāo)準(zhǔn)型：第二步：用非基變量表示基變量和目標(biāo)函數(shù)，求出一個(gè)基本可行解．由（2）可知：

，令各非基變量等于0,即，得到基變量

，它