2023學(xué)年度 線性規(guī)劃問題舉例

線性規(guī)劃問題舉例作為上述線性規(guī)劃問題的數(shù)學(xué)模型的應(yīng)用，下面將對(duì)三個(gè)問題建立線性規(guī)劃模型．這些問題以及其他線性規(guī)劃問題的更詳細(xì)的討論，在本書的第三部分給出．運(yùn)輸問題一個(gè)制造廠希望把若干單位的產(chǎn)品從幾個(gè)倉庫發(fā)送到若干個(gè)零售點(diǎn)．每個(gè)零售點(diǎn)都需要一定數(shù)量的產(chǎn)品，而每個(gè)倉庫也能供應(yīng)一定數(shù)量的產(chǎn)品．這里作如下規(guī)定：m=倉庫的數(shù)目．n=零售點(diǎn)的數(shù)目．a(chǎn)i=第i個(gè)倉庫能供應(yīng)產(chǎn)品的總量．bj=第j個(gè)零售點(diǎn)所需產(chǎn)品的總量．xij=從倉庫i運(yùn)到零售點(diǎn)j的產(chǎn)品數(shù)量．這里xij是待定的未知量．如作出表格(當(dāng)m=2，n=3)則可以看出從倉庫1運(yùn)出產(chǎn)品的總量能用線性方程表示為x11＋x12＋x13=a1．(2．1)對(duì)于倉庫2有x21＋x22＋x23=a2．(2．2)也要考慮三個(gè)零售點(diǎn)所需產(chǎn)品的總量，用下列方程表示：制造廠知道從倉庫i運(yùn)到零售點(diǎn)j一個(gè)單位產(chǎn)品的費(fèi)用為cij．我們還假定費(fèi)用關(guān)系是線性的，即運(yùn)送xij單位的費(fèi)用為cijxij．制造廠希望確定，從每個(gè)倉庫到每個(gè)零售點(diǎn)，要運(yùn)送多少數(shù)量的產(chǎn)品，才能使全部運(yùn)輸費(fèi)用為極小．使費(fèi)用為極小的目標(biāo)，可通過極小化線性費(fèi)用函數(shù)c11x11＋c12x12＋c13x13＋c13x13＋c21x21＋c22x22＋c23x23(2．4)來實(shí)現(xiàn)．因?yàn)橐粋€(gè)非負(fù)的xij表示從倉庫i到零售點(diǎn)j的運(yùn)輸量，所以我們要求全部變量xij≥0．把等式(2．1)至(2．3)，目標(biāo)函數(shù)(2．4)和變量非負(fù)的條件聯(lián)合起來，則m=2，n=3的運(yùn)輸問題就可以表示成下列線性規(guī)劃問題：作為運(yùn)輸問題的一個(gè)數(shù)值例子，讓我們考慮兩個(gè)倉庫三個(gè)零售點(diǎn)的問題，其中可把這個(gè)問題寫成線性規(guī)劃問題如下：我們注意上述方程可代表一組會(huì)計(jì)上的帳目，它們記錄了倉庫與零售點(diǎn)之間貨物流通量．類似地，許多線性規(guī)劃問題的方程只不過是會(huì)計(jì)步驟的數(shù)學(xué)表達(dá)．下表給出一個(gè)平凡解即x11=0，x12=5，x13=0，x21=8，x22=0，x28=2．相應(yīng)的目標(biāo)函數(shù)值是2x12＋3x21＋x23=2·5＋3·8＋1·2=36．第二組解(許多組解中的一組)是其目標(biāo)函數(shù)值為26．由第十章的方法可以證明，這個(gè)解是極小解．(對(duì)于此例，讀者應(yīng)能驗(yàn)證，任何其他解所得到的運(yùn)輸費(fèi)用都大于26．)活動(dòng)性分析問題某公司掌握了幾種數(shù)量固定的資源(如原材料，勞動(dòng)力和設(shè)備)，合起來能生產(chǎn)若干不同產(chǎn)品中的一種或這些產(chǎn)品的某種組合．已知公司每生產(chǎn)一個(gè)單位的j種產(chǎn)品所需要的i種資源的數(shù)量，同時(shí)也已知每生產(chǎn)一個(gè)單位的j種產(chǎn)品所能獲得利潤(rùn)的數(shù)量．公司希望生產(chǎn)的產(chǎn)品組合能使其獲得的總利潤(rùn)為最大．對(duì)此問題可以作如下定義：m=資源的種類數(shù)．n=產(chǎn)品的種類數(shù)．a(chǎn)ij=生產(chǎn)一個(gè)單位的j種產(chǎn)品所需i種資源的數(shù)量．bi=i種資源的最大可用量．cj=生產(chǎn)單位j種產(chǎn)品的利潤(rùn)數(shù)．xj=j種產(chǎn)品的活動(dòng)水平(或產(chǎn)量)．有時(shí)稱aij為投入－產(chǎn)出系數(shù)或技術(shù)系數(shù)．使用i種資源的總量可表示為線性函數(shù)ai1x1＋ai2x2＋…＋ainxn．因?yàn)樯鲜鍪褂胕種資源的總量必須小于或等于i種資源的最大可用量，所以對(duì)i種資源有下列線性不等式：ai1x1＋ai2x2＋…＋ainxn≤bi．由于負(fù)的xj沒有實(shí)際意義，所以我們要求所有xj≥0．生產(chǎn)xj單位的j種產(chǎn)品所獲得的利潤(rùn)為cjxj．上述極大化利潤(rùn)函數(shù)問題的數(shù)學(xué)表達(dá)如下：如第二章將討論的那樣，一個(gè)不等式可等價(jià)于非負(fù)變量的一個(gè)等式，所以上述問題是一般線性規(guī)劃問題的另一種提法．為了說明上述模型，我們考慮在Gass[172]中所給出的例子．一個(gè)生產(chǎn)家具的公司計(jì)劃生產(chǎn)兩種產(chǎn)品——椅子和桌子，其可用資源包括400板英尺①的紅木板和450個(gè)工時(shí)．已知生產(chǎn)每把椅子需用紅木板5板英尺，10個(gè)工時(shí)，其利潤(rùn)為45美元，而生產(chǎn)每張桌子需用紅木板20板英尺和15個(gè)工時(shí)，其利潤(rùn)為80美元．問題是要確定，在資源約束范圍內(nèi)，公司生產(chǎn)多少把椅子和多少張桌子，其總利潤(rùn)最大．生產(chǎn)一把椅子需消耗5板英尺的木板和10個(gè)工時(shí)，而生產(chǎn)一張桌子需消耗20板英尺木板和15個(gè)工時(shí)．令x1為椅子的生產(chǎn)量，x2為桌子的生產(chǎn)量．上述活動(dòng)性分析問題，用線性規(guī)劃的形式可寫成下述極大化利潤(rùn)函數(shù)的問題：當(dāng)然，對(duì)于上述約束條件，具有很多組可能的解．例如，僅生產(chǎn)椅子的解為x1=45，x2=0，其利潤(rùn)為45×45=2025美元；僅生產(chǎn)桌子的解為x1=0，x2=20，其利潤(rùn)為80×20=1600美元．求出的最優(yōu)解為：生產(chǎn)椅子x1=24，生產(chǎn)桌子x2=14，其利潤(rùn)為2200美元．食物配料問題這里給出若干不同食物的營(yíng)養(yǎng)成分含量．例如，我們所考慮的不同食物中，已知每英兩食物含有多少毫克的鐵或磷，我們也已知每種營(yíng)養(yǎng)成分的最低日需要量．因?yàn)槊坑墒澄锏馁M(fèi)用是已知的，所以問題是，在滿足營(yíng)養(yǎng)成分的最低日需要量的條件下，確定費(fèi)用最低的食物配方．定義m=營(yíng)養(yǎng)成分的種類數(shù)．n=食物的種類數(shù)．a(chǎn)ij=在每一英兩的第j種食物中含有第i種營(yíng)養(yǎng)成分的毫克數(shù)．bi=第i種營(yíng)養(yǎng)成分最低日需要量的毫克數(shù)．cj=每英兩第j種食物的費(fèi)用．xj=購買第j種食物的英兩數(shù)(xj≥0)．購買的所有食物中含有第i種營(yíng)養(yǎng)成分的總量可表示為ai1x1＋ai22＋…＋ainxn．因?yàn)檫@一總量必須大于或等于第i種營(yíng)養(yǎng)成分的最低日需要量，這個(gè)線性規(guī)劃問題可表示如下：下面給出關(guān)于食物配料問題的一個(gè)簡(jiǎn)單數(shù)值例題．考慮兩種食物x1和x2以及含有維生素B1、磷、鐵三種營(yíng)養(yǎng)成分的食物配料問題．每種食物中含有各種營(yíng)養(yǎng)成分的數(shù)量(毫克/英兩，簡(jiǎn)寫為mg/oz)列于下表對(duì)于這兩種食物的飲食，至少要求獲得維生素毫克，磷毫克，鐵毫克．x1的費(fèi)用為2美分/英兩，x2的費(fèi)用為5/3美分/英兩．根據(jù)前述一般食物配料問題的格式，本例相應(yīng)的線性規(guī)劃問題如下：這個(gè)問題的最優(yōu)解為x1=20/7英兩，x2=40/7英兩的混合飲食，其費(fèi)用為美元．把這一結(jié)果與單純用食物x1或單純用食物x2的解進(jìn)行費(fèi)用比較，讀者將會(huì)受到啟發(fā)．對(duì)于上面的一些例子，以及所有歸結(jié)為線性規(guī)劃問題一般形式的問題，我們都假定某些基本的線性關(guān)系式成立．線性規(guī)劃的比例性要求，可通過活動(dòng)性分析和食物配料問題來說明，在這些問題中，我們假定活動(dòng)(指產(chǎn)量或配料)水平的改變會(huì)引起所需資源或營(yíng)養(yǎng)成分按比例地改變．當(dāng)我們對(duì)全部生產(chǎn)所用的資源求和或?qū)θ渴澄镏械臓I(yíng)養(yǎng)成分求和時(shí)，也用到了可加性的要求．雖然我們有權(quán)懷疑這些假定的普遍性，但它們的合理性或近似性已使它們?cè)诂F(xiàn)實(shí)世界中得到大量重要的應(yīng)用．附注最早的線性規(guī)劃方法的應(yīng)用，分為三種主要類型：軍事應(yīng)用——來源于空軍SCOOP方案，各種經(jīng)濟(jì)間的Leontief投入－產(chǎn)出模型以及有關(guān)零和二人對(duì)策與線性規(guī)劃之間關(guān)系的問題．這些應(yīng)用領(lǐng)域已得到擴(kuò)大和發(fā)展，但線性規(guī)劃應(yīng)用的重點(diǎn)已經(jīng)轉(zhuǎn)移到工業(yè)領(lǐng)域．此外，線性規(guī)劃問題的應(yīng)用已經(jīng)發(fā)展到社會(huì)和城市的各種問題，例如教育、法律實(shí)施、衛(wèi)生事業(yè)、環(huán)境保護(hù)等應(yīng)用方面的書目包括在下述分類的文獻(xiàn)目錄中：農(nóng)業(yè)、合同裁決、工業(yè)、經(jīng)濟(jì)分析、軍事、人員分配、生產(chǎn)計(jì)劃與存貨控制、結(jié)構(gòu)設(shè)計(jì)、交通研究、運(yùn)輸與網(wǎng)絡(luò)理論、貨郎擔(dān)問題及其他應(yīng)用．有關(guān)補(bǔ)充