經(jīng)濟(jì)數(shù)學(xué)（第三版） 教案 4.最優(yōu)配置與最佳效果分析

第四講最優(yōu)配置與最佳效果分析-------安排生產(chǎn)問題及解決方案教學(xué)目標(biāo)：掌握安排生產(chǎn)問題的解決方案。教學(xué)內(nèi)容：討論安排生產(chǎn)問題問題，線性規(guī)劃概念及圖解法。教學(xué)重點(diǎn)：建立線性規(guī)劃模型教學(xué)難點(diǎn)：安排生產(chǎn)問題與線性規(guī)劃模型的聯(lián)系一、問題引入引例：美國空軍為了保證士兵的營養(yǎng)，規(guī)定每餐的食品中，要保證一定的營養(yǎng)成份，例如蛋白質(zhì)、脂肪、維生素等等，都有定量的規(guī)定。當(dāng)然這些營養(yǎng)成分可以由各種不同的食物來提供，例如牛奶提供蛋白質(zhì)和維生素，黃油提供蛋白質(zhì)和脂肪，胡蘿卜提供維生素，等等。由于戰(zhàn)爭條件的限制，食品種類有限，又要盡量降低成本，于是在一盒套餐中，如何決定各種食品的數(shù)量，使得既能滿足營養(yǎng)成分的需求，又可以降低成本？問題分析：在本例中要利用有限的資源，去使得一份套餐既能滿足營養(yǎng)要求又可以降低成本。用數(shù)學(xué)語言來說，就是在一定的約束條件下，求線性函數(shù)的最大和最小值問題。更加廣義的來看待配餐問題，我們知道，現(xiàn)代的企業(yè)管理問題千變?nèi)f化，企業(yè)內(nèi)部的生產(chǎn)計劃有各種不同的情況。從空間層次看，在工廠要根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制定產(chǎn)品的生產(chǎn)計劃，在車間級則要根據(jù)產(chǎn)品生產(chǎn)計劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制定生產(chǎn)批量計劃。而這類問題都可以通過建立相應(yīng)的線性規(guī)劃模型來解決。那么，什么是線性規(guī)劃？怎樣建立線性規(guī)劃模型？這正是我們要學(xué)習(xí)的內(nèi)容。二、典型問題解決方案案例1：某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，要用、、3種不同的原料．從工藝資料知道：每生產(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)計劃，使一天的總利潤最大呢？解決方案：設(shè)企業(yè)每天生產(chǎn)甲產(chǎn)品為噸，生產(chǎn)乙產(chǎn)品為噸，稱，為決策變量，他們不能任意取值，要受到可供利用的原料資源數(shù)量的限制．又因為產(chǎn)品的產(chǎn)量一般是一個非負(fù)數(shù)，所以有，，稱為非負(fù)約束．由于生產(chǎn)1噸甲產(chǎn)品需耗用3種原料分別為1，1，0單位，因而生產(chǎn)噸甲產(chǎn)品需要耗用3種原料分別為，，0單位；由于生產(chǎn)1噸乙產(chǎn)品需耗用3種原料分別為1，2，1單位，因而生產(chǎn)噸乙產(chǎn)品需要耗用3種原料分別為，2，單位．又因為每天3種原料的供應(yīng)能力分別為6，8，3單位，所以當(dāng)企業(yè)每天生產(chǎn)甲產(chǎn)品噸，乙產(chǎn)品噸時，對于原料、、，我們有如下的不等式：原料：，原料：，原料：.上面得到的3種原料的線性不等式是決策變量，取值所必須滿足的條件，它們約束了決策變量，不能取任意值，稱它們?yōu)榧s束條件．容易看出，滿足約束條件的變量，的值不唯一，即表示約束條件的線性不等式組有無窮多組解．如是一組解，此外也是一組解，還可以找出許多．這說明僅考慮到原料供應(yīng)量的制約，對生產(chǎn)的安排是有選擇余地的．這些安排生產(chǎn)的方案都是可行的，應(yīng)該從中挑選出最優(yōu)方案．那么，根據(jù)什么挑選最優(yōu)方案？由于每一個可行方案，即每一組滿足約束條件的變量值，都對應(yīng)一個兩種產(chǎn)品的總利潤，在一般情況下，不同可行方案所對應(yīng)的總利潤也不相同，所以應(yīng)該找出使得總利潤最大的可行方案，這就是最優(yōu)方案．由于生產(chǎn)1噸甲產(chǎn)品企業(yè)的利潤收入為300元，生產(chǎn)1噸乙產(chǎn)品企業(yè)的利潤收入為400元．于是甲乙兩種產(chǎn)品的總利潤為元，它是決策變量，的線性函數(shù)，稱函數(shù)為目標(biāo)函數(shù)．這樣，最優(yōu)方案就是使得目標(biāo)函數(shù)最大的可行方案．綜上所述，得到描述原問題的數(shù)學(xué)模型如下：（1）利用Excel求解可得，當(dāng)時，取得最大值元．線性規(guī)劃的相關(guān)概念從引例1可知最優(yōu)化問題就是在給定條件下尋找最優(yōu)方案的問題，其數(shù)學(xué)模型由三部分組成的：=1\*GB3①決策變量；=2\*GB3②目標(biāo)函數(shù)；=3\*GB3③約束條件．進(jìn)一步，如果目標(biāo)函數(shù)和約束條件均為線性關(guān)系，我們把這樣的最優(yōu)化問題稱為線性規(guī)劃問題，條件=1\*GB3①、=2\*GB3②、=3\*GB3③稱為線性規(guī)劃問題的三要素．=1\*GB3①決策變量決策變量是指最優(yōu)化問題中所涉及的與約束條件和目標(biāo)函數(shù)有關(guān)的待確定的量.一般來說，它們都有一些限制條件（約束條件），與目標(biāo)函數(shù)緊密關(guān)聯(lián).如引例2企業(yè)生產(chǎn)的甲、乙兩種產(chǎn)品數(shù)量,是兩個決策變量，決策變量一般表示為.=2\*GB3②目標(biāo)函數(shù)線性規(guī)劃問題中與變量有關(guān)的可以是求最大值，也可以是求最小值的函數(shù)稱為目標(biāo)函數(shù)，例如，若目標(biāo)函數(shù)表示生產(chǎn)費(fèi)用，則希望生產(chǎn)費(fèi)用最小．無論目標(biāo)函數(shù)是最大還是最小，總之是希望目標(biāo)函數(shù)達(dá)到最優(yōu)．目標(biāo)函數(shù)一般表達(dá)式為：.=3\*GB3③約束條件在最優(yōu)化問題中，求目標(biāo)函數(shù)的最值時，決策變量必須滿足的限制稱為約束條件.例如，許多實際問題變量要求必須非負(fù)，這是一種限制；在產(chǎn)品的安排生產(chǎn)問題時，產(chǎn)品的產(chǎn)量受到原材料、人力資源的限制等.在研究問題時，這些限制我們必須用數(shù)學(xué)表達(dá)式準(zhǔn)確地描述它們.約束條件按照表達(dá)式可分為等式約束和不等式約束：不等式約束;等式約束.綜上所述，本章將要討論的線性規(guī)劃問題的數(shù)學(xué)模型可表示如下(7.1)在線性規(guī)劃問題模型中，滿足約束條件的解稱為可行解，所有可行解的集合稱為可行集；使目標(biāo)函數(shù)取值最大或最小的可行解稱為最優(yōu)解，對應(yīng)于最優(yōu)解的目標(biāo)函數(shù)值稱為最優(yōu)值．三、圖解法學(xué)習(xí)圖解法的主要目的在于幫助理解線性規(guī)劃問題解的性質(zhì).下面首先通過一個具體實例來說明圖解法的原理和步驟.例7.1求解線性規(guī)劃問題解(1)建立平面直角坐標(biāo)系，畫出可行域.因為，所以滿足約束條件的點(diǎn)都落在第一象限及坐標(biāo)軸的正半軸上.在坐標(biāo)系中畫出直線，這條直線將整個坐標(biāo)平面分成兩個半平面，顯然，坐標(biāo)原點(diǎn)滿足不等式，所以，滿足約束條件的所有點(diǎn)落在直線上及原點(diǎn)所在一側(cè)的半平面內(nèi).同理，滿足約束條件的所有點(diǎn)位于直線上及以該直線為分割線的原點(diǎn)所在一側(cè)的半平面內(nèi)；滿足約束條件的所有點(diǎn)位于直線上及以該直線為分割線的原點(diǎn)所在一側(cè)的半平面內(nèi).上述三個平面點(diǎn)集在第一象限的交集即為可行域（包含邊界），如圖7-1.可行域內(nèi)任意一點(diǎn)的坐標(biāo)都是該線性規(guī)劃問題的可行解.圖7-1可行域圖(2)繪制目標(biāo)函數(shù)等值線.在幾何上，目標(biāo)函數(shù)代表平面上的一族平行直線，其中一條直線對應(yīng)一個值.落在同一條直線上的點(diǎn)，如果又落在可行域上，那么這樣的點(diǎn)就是具有相同目標(biāo)函數(shù)值的可行解，所以平行直線族中的每一條直線又稱為等值線.試探性給定值，如、，畫出相應(yīng)的等值線，如圖7-1.不難發(fā)現(xiàn)，等值線離原點(diǎn)越遠(yuǎn)，的值越大.(3)確定最優(yōu)解.最優(yōu)解必須是滿足約束條件，并使目標(biāo)函數(shù)達(dá)到最優(yōu)值的解，故的值只能在可行域中去尋找.當(dāng)?shù)戎稻€由原點(diǎn)開始向右上方移動時，的值逐漸增大，于是，當(dāng)移動到與可行域相切時，切點(diǎn)就是代表最優(yōu)解的點(diǎn).本例中等值線與可行域的切點(diǎn)為，點(diǎn)是直線和的交點(diǎn)，坐標(biāo)為，所以，最優(yōu)解為，最優(yōu)值為19.通過例7.1，不難總結(jié)出圖解法的基本步驟如下：（1）根據(jù)約束條件畫出可行域；（2）根據(jù)目標(biāo)函數(shù)的表達(dá)式畫出目標(biāo)函數(shù)等值線，并標(biāo)明目標(biāo)函數(shù)值增加的方向；（3）在可行域中，尋求符合要求的等值線與可行域邊界相切的點(diǎn)或點(diǎn)集，并求出最優(yōu)解和最優(yōu)值.例7.2某?；锸抽L期以面粉和大米為主食，面食每100g含蛋白質(zhì)6個單位，含淀粉4個單位，售價0.5元，米食每100g含蛋白質(zhì)3個單位，含淀粉7個單位，售價0.4元，學(xué)校要求給學(xué)生配制盒飯，每盒盒飯至少有8個單位的蛋白質(zhì)和10個單位的淀粉.問：應(yīng)如何配制盒飯，才既科學(xué)又費(fèi)用最少?1.模型建立決策變量：設(shè)每盒盒飯需要面食（百克），米食（百克）.目標(biāo)函數(shù)：使費(fèi)用最少，即.約束條件：營養(yǎng)需求約束：每盒盒飯至少需要含有8個單位的蛋白質(zhì)和10個單位的淀粉，故可得非負(fù)約束：每盒盒飯需要面食和米食的重量均必須大于等于0，所以有綜上所述，得藥品生產(chǎn)問題的數(shù)學(xué)規(guī)劃模型為：2.圖解法求解(1)建立平面直角坐標(biāo)系，根據(jù)約束條件畫出可行域，如圖7-2所示.圖7-2配餐問題的可行域圖(2)目標(biāo)函數(shù)代表平面上的一族平行直線，其中一條直線對應(yīng)一個值，如圖中虛線所示.(3)本例中等值線與可行域的切點(diǎn)為，此時目標(biāo)函數(shù)取得最小值，點(diǎn)是直線和的交點(diǎn)，坐標(biāo)為，所以，最優(yōu)解為，最優(yōu)值為.因此，當(dāng)每盒盒飯面食（百克），米食（百克）時既符合營養(yǎng)要求又費(fèi)用最少，最少費(fèi)用為元.例7.3某工廠在計劃期內(nèi)要安排生產(chǎn)=1\*ROMANI、=2\*ROMANII兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：表7-1產(chǎn)品的消耗、資源的限制表=1\*ROMANI=2\*ROMANII資源限制設(shè)備11300（臺時）原料A21400（千克）原料B01250（千克）單位產(chǎn)品獲利（元）50100問：工廠應(yīng)分別生產(chǎn)多少單位=1\*ROMANI、=2\*ROMANII產(chǎn)品才能使工廠獲利最多？1.模型建立決策變量：設(shè)產(chǎn)品=1\*ROMANI生產(chǎn)單位，產(chǎn)品=2\*ROMANII生產(chǎn)單位.目標(biāo)函數(shù)：要使得獲利最多，即約束條件：資源限制約束：設(shè)備的最多可用臺時為300臺時，即同理，原料A、B的消耗量不能超過資源限制，因此可得非負(fù)約束：每種原料的含量均必須大于等于0，所以有綜上所述，得藥品生產(chǎn)問題的數(shù)學(xué)規(guī)劃模型為：2.圖解法求解(1)建立平面直角坐標(biāo)系，根據(jù)約束條件畫出可行域，如圖所示.圖7-3安排生產(chǎn)問題的可行域圖(2)目標(biāo)函數(shù)代表平面上的一族平行直線，其中一條直線對應(yīng)一個值，如圖中直線.(3)本例中等值線與可行域的切點(diǎn)為，點(diǎn)是直線和的交點(diǎn)，坐標(biāo)為，所以，最優(yōu)解為，最優(yōu)值為27500.因此，當(dāng)工廠生產(chǎn)產(chǎn)品=1\*ROMANI：50單位，=2\*ROMANII：250單位時，獲得最大利潤為27500元.線性規(guī)劃問題解的性質(zhì)圖解法雖然只能用來求解只含兩個變量的線性規(guī)劃問題，但通過它的解題思路和幾何直觀所得到的一些性質(zhì)，對線性規(guī)劃問題解的理解有很大的幫助.一般地，含兩個變量的線性規(guī)劃問題的解有下面四種情況：（1）有可行解且有唯一最優(yōu)解；（2）有可行解且有無窮多最優(yōu)解；（3）有可行解但無最優(yōu)解；（4）無可行解.同時，若線性規(guī)劃問題存在最優(yōu)解，它一定在可行域的某個頂點(diǎn)得到，若在兩個頂點(diǎn)同時得到最優(yōu)解，則它們連線段上的任意一點(diǎn)都是最優(yōu)解，即有無窮多最優(yōu)解.上述結(jié)論可以推廣到變量多于兩個的一般情形，得線性規(guī)劃問題解的性質(zhì)如下：性質(zhì)1求解線性規(guī)劃問題時，解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解.性質(zhì)2若線性規(guī)劃問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（如果有無窮多最優(yōu)解）一定可以在基可行解(頂點(diǎn))中找到.習(xí)題1．試述線性規(guī)劃問題數(shù)學(xué)模型的組成部分及特征，判別下列數(shù)學(xué)模型是否為線性規(guī)劃模型（模型中為常數(shù)，為可取某一常數(shù)值的參變量，為變量）。2.考慮如表9.2所示的生產(chǎn)計劃問題，建立線性規(guī)劃模型，以確定最優(yōu)生產(chǎn)方案。表9.23某工廠用A、B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，每生產(chǎn)一件甲產(chǎn)品使用4個A配件耗時1h，每生產(chǎn)一件乙產(chǎn)品使用4個B配件耗時2h.該廠每天最多可從配件廠獲得16個A配件和12個B配件，按每天工作8h計算，若生產(chǎn)一件甲產(chǎn)品獲利2萬元，生產(chǎn)一件乙產(chǎn)品獲利3萬元，問工廠應(yīng)如何安排生產(chǎn)，以使得總利潤最大？4．某礦山車隊有4輛載重量為10t的甲型卡