1、4.1 4.1 自來水輸送與貨機(jī)裝運(yùn)自來水輸送與貨機(jī)裝運(yùn) 某市有甲，乙，丙，丁某市有甲，乙，丙，丁四個(gè)居民區(qū)四個(gè)居民區(qū)，自來水，自來水由由A，B，C三個(gè)水庫三個(gè)水庫供應(yīng)供應(yīng)四個(gè)區(qū)每天必須得到保證的四個(gè)區(qū)每天必須得到保證的基本生活用水量基本生活用水量分別為分別為30，70，10，10千噸，但由于水資源千噸，但由于水資源緊張，三個(gè)水庫每天最多只能分別供應(yīng)緊張，三個(gè)水庫每天最多只能分別供應(yīng)50，60，50千噸自來水。千噸自來水。問題問題由于地理位置的差別，自來水公司從各水庫由于地理位置的差別，自來水公司從各水庫向各區(qū)送水所需付出的向各區(qū)送水所需付出的引水管理費(fèi)引水管理費(fèi)不同不同(見表見表41.其中其

2、中C水庫與丁區(qū)之間沒有輸水管道水庫與丁區(qū)之間沒有輸水管道)。其他管理費(fèi)用都是其他管理費(fèi)用都是450元元/千噸千噸.根據(jù)公司規(guī)定，各區(qū)根據(jù)公司規(guī)定，各區(qū)用戶按照統(tǒng)一標(biāo)準(zhǔn)用戶按照統(tǒng)一標(biāo)準(zhǔn)900元元/千噸收費(fèi)。千噸收費(fèi)。此外四個(gè)區(qū)都向公司申請了額外用水量，分別為每此外四個(gè)區(qū)都向公司申請了額外用水量，分別為每天天50，70，20，40千噸。千噸。該公司應(yīng)如何分配供水量，才能獲利最多該公司應(yīng)如何分配供水量，才能獲利最多? 由為了增加供水量，自來水公司正在考慮進(jìn)行水由為了增加供水量，自來水公司正在考慮進(jìn)行水庫改造，使三個(gè)水庫每天的最大供水量都提高一庫改造，使三個(gè)水庫每天的最大供水量都提高一倍，倍，問那時(shí)供

3、水方案應(yīng)如何改變問那時(shí)供水方案應(yīng)如何改變?公司利潤可加到公司利潤可加到多少？多少？引水管理費(fèi)引水管理費(fèi)（元（元/千噸）千噸）甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/表表41 從水庫向各區(qū)送水的引水管理費(fèi)從水庫向各區(qū)送水的引水管理費(fèi)分分析析分配供水量就是安排從三個(gè)水庫向四個(gè)區(qū)送水分配供水量就是安排從三個(gè)水庫向四個(gè)區(qū)送水的方案，目標(biāo)是獲利最多的方案，目標(biāo)是獲利最多. 而從題目給出的數(shù)據(jù)看，而從題目給出的數(shù)據(jù)看，A，B，C三個(gè)水庫的三個(gè)水庫的供水量供水量160千噸，不超過四個(gè)區(qū)的基本生活用水千噸，不超過四個(gè)區(qū)的基本生活用水量與額外用水量之和量與額外用

4、水量之和300千噸，因而總能賣出并千噸，因而總能賣出并獲利，于是自來水公司每天的獲利，于是自來水公司每天的總收入總收入是元，是元，與與送水方案無關(guān)送水方案無關(guān)同樣，公司每天的其它同樣，公司每天的其它管理費(fèi)管理費(fèi)用元也與送水方案無關(guān)用元也與送水方案無關(guān) 所以，所以，要使利潤最大要使利潤最大只需使只需使引水管理費(fèi)最小引水管理費(fèi)最小即可另外，送水方案自然要受三個(gè)水庫的供即可另外，送水方案自然要受三個(gè)水庫的供應(yīng)和四區(qū)的需求量的限制應(yīng)和四區(qū)的需求量的限制 分分析析模模 型型 建建 立立)3 , 2 , 1( i決策變量為決策變量為A，B，C三個(gè)水庫三個(gè)水庫 分別向甲，分別向甲，乙，丙，丁四個(gè)區(qū)乙，丙，丁

5、四個(gè)區(qū) 的供水量，設(shè)水庫的供水量，設(shè)水庫 向向 區(qū)的日供水量為區(qū)的日供水量為 由于由于C水庫與丁區(qū)之間沒水庫與丁區(qū)之間沒有輸水管道，即有輸水管道，即 ，因此只有，因此只有11個(gè)決策變個(gè)決策變量量 )3 , 2 , 1( i)4 , 3 , 2 , 1(jijijx034x由上分析，問題的目標(biāo)可以從獲利最多轉(zhuǎn)化為由上分析，問題的目標(biāo)可以從獲利最多轉(zhuǎn)化為引水管理費(fèi)最少，于是有引水管理費(fèi)最少，于是有3332312423222114131211230200190150190130140 170220130160 xxxxxxxxxxxMinZ（4.1.1） 約束條件有兩類；一類是是水庫的供應(yīng)量限制，約

6、束條件有兩類；一類是是水庫的供應(yīng)量限制，另一類是各區(qū)的需求量限制另一類是各區(qū)的需求量限制 由于供水量總能賣出并獲利，水庫的供應(yīng)量限由于供水量總能賣出并獲利，水庫的供應(yīng)量限量可以表示為：量可以表示為： (4.1.2) 5014131211xxxx(4.1.3) 6024232221xxxx(4.1.4) 50333231xxx考慮的各區(qū)的基本生活用水量與額外用水量，考慮的各區(qū)的基本生活用水量與額外用水量，需求量限制可以表示為：需求量限制可以表示為：(4.1.8) 5010(4.1.7) 3010(4.1.6) 14070(4.1.5) 80302414332313322212312111xxxx

7、xxxxxxx模型求解模型求解（4.1.1）（）（4.1.8）構(gòu)成一線性規(guī)劃模型（當(dāng)）構(gòu)成一線性規(guī)劃模型（當(dāng)然加上然加上 的非負(fù)約束）輸入的非負(fù)約束）輸入LINDO求解，得求解，得到如下結(jié)果。到如下結(jié)果。 ijx送水方案為：送水方案為： A水庫向乙區(qū)供水水庫向乙區(qū)供水50千噸，千噸， B水庫向乙，丁區(qū)分別供水水庫向乙，丁區(qū)分別供水50，10，千噸，千噸， C水庫向甲，丙分別供水水庫向甲，丙分別供水40，10千噸千噸 引水管理費(fèi)為引水管理費(fèi)為24400元，元， 利潤為利潤為144000-72000-24000=47600元元 討論討論如果如果A，B，C三個(gè)水庫每天的最大供水量都提三個(gè)水庫每天的最

8、大供水量都提高一倍，則公司總供水能力為高一倍，則公司總供水能力為320千噸，大于總千噸，大于總需求量需求量300千噸，水庫供水量不能全部賣出，因千噸，水庫供水量不能全部賣出，因而不能像前面那樣，將獲利最多轉(zhuǎn)化為引水管而不能像前面那樣，將獲利最多轉(zhuǎn)化為引水管理費(fèi)最少。理費(fèi)最少。因此因此需要計(jì)算需要計(jì)算A，B，C三個(gè)水庫分別向甲，乙，三個(gè)水庫分別向甲，乙，丙，丁四個(gè)區(qū)供應(yīng)每千噸水的凈利潤，丙，丁四個(gè)區(qū)供應(yīng)每千噸水的凈利潤，既從收既從收入入900元中減去其他管理費(fèi)元中減去其他管理費(fèi)450元，再減去表元，再減去表41中的引水管理費(fèi)，得表中的引水管理費(fèi)，得表42 凈利潤（元/千噸）甲乙丙丁A290320

9、230280B310320260300C260250220/表表42 從水庫向各區(qū)送水的凈利潤從水庫向各區(qū)送水的凈利潤 決策目標(biāo)為決策目標(biāo)為 3332312423222114131211220250260300260 320310280230320290 xxxxxxxxxxxMaxZ（4.1.9） 由于水庫供水量不能全不賣出，所以上面約束由于水庫供水量不能全不賣出，所以上面約束（4.1.2）（4.1.4）的右端增加一倍的同時(shí)，）的右端增加一倍的同時(shí)，應(yīng)將等號改為小于，既應(yīng)將等號改為小于，既 (4.1.10) 10014131211xxxx(4.1.11) 12024232221xxxx(4.

10、1.12) 100333231xxx約束（約束（4.1.5）（）（4.1.8）不變將（）不變將（4.1.5）（4.1.12）構(gòu)成的線性規(guī)劃模型輸入）構(gòu)成的線性規(guī)劃模型輸入LINDO求求解。解。 送水方案：送水方案：A水庫向乙區(qū)供水水庫向乙區(qū)供水100千噸，千噸，B水庫水庫向甲，乙，丁區(qū)分別供水向甲，乙，丁區(qū)分別供水30，40，50千噸千噸C水水庫甲，丙區(qū)分別供水庫甲，丙區(qū)分別供水50，30千噸總利潤為千噸總利潤為88700元元 本題考慮的是將某種物質(zhì)從若干供應(yīng)點(diǎn)運(yùn)往一本題考慮的是將某種物質(zhì)從若干供應(yīng)點(diǎn)運(yùn)往一些需求點(diǎn)，在供需量約束條件下使總費(fèi)用最小，些需求點(diǎn)，在供需量約束條件下使總費(fèi)用最小，或總

11、利潤最大，這類問題一般稱為運(yùn)輸問題，或總利潤最大，這類問題一般稱為運(yùn)輸問題，是線性規(guī)劃應(yīng)用最廣泛的領(lǐng)域之一是線性規(guī)劃應(yīng)用最廣泛的領(lǐng)域之一評注評注在標(biāo)準(zhǔn)的運(yùn)輸問題中，供需量通常是不平衡的，在標(biāo)準(zhǔn)的運(yùn)輸問題中，供需量通常是不平衡的，擔(dān)這并不會引起本質(zhì)的區(qū)別，一樣可以方便的擔(dān)這并不會引起本質(zhì)的區(qū)別，一樣可以方便的建立線性規(guī)劃模型求解建立線性規(guī)劃模型求解 貨機(jī)裝運(yùn)貨機(jī)裝運(yùn) 問問 題題某架貨機(jī)有三個(gè)貨艙；前艙，中艙，后艙，三某架貨機(jī)有三個(gè)貨艙；前艙，中艙，后艙，三個(gè)貨艙所能裝載的貨物的最大重量和體積都有個(gè)貨艙所能裝載的貨物的最大重量和體積都有限制，如表限制，如表43所示所示.為了保持飛機(jī)的平衡為了保持飛

12、機(jī)的平衡,三個(gè)貨艙中實(shí)際裝載貨物三個(gè)貨艙中實(shí)際裝載貨物的重量必須與其最大容許重量成比例的重量必須與其最大容許重量成比例 。前倉中倉后倉重量限制(噸)10168體積限制（立方米）680087005300表表43 三個(gè)貨艙裝載貨物的最大容許重量和體積三個(gè)貨艙裝載貨物的最大容許重量和體積 現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運(yùn)，其有關(guān)信現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運(yùn)，其有關(guān)信息如表息如表44最后一列指裝運(yùn)后所獲得的利潤最后一列指裝運(yùn)后所獲得的利潤 重量（噸）空間（立方米/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850表表44 四類裝運(yùn)貨

13、物的信息四類裝運(yùn)貨物的信息 應(yīng)如何安排裝運(yùn)，使該貨機(jī)本次飛行獲利最大應(yīng)如何安排裝運(yùn)，使該貨機(jī)本次飛行獲利最大?模模 型型 假假 設(shè)設(shè)1 每種貨物可以分割到任意?。幻糠N貨物可以分割到任意??；2 每種貨物可以在一個(gè)或多個(gè)貨艙中任意每種貨物可以在一個(gè)或多個(gè)貨艙中任意 分布；分布；3 多種貨物可以混裝，并保證不留空隙多種貨物可以混裝，并保證不留空隙模模 型型 建建 立立決策變量決策變量:用用 表示第表示第 種貨物裝入第種貨物裝入第 個(gè)貨艙的重個(gè)貨艙的重量量(噸噸)，貨艙，貨艙 分別表示前倉、中倉、后倉分別表示前倉、中倉、后倉. ijxij3 , 2 , 1j決策目標(biāo)是最大化總利潤，即決策目標(biāo)是最大化總

14、利潤，即 （4.1.13） )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxxMax約束條件包括以下約束條件包括以下4個(gè)方面：個(gè)方面：1) 供裝載的四種貨物的總重量約束，即供裝載的四種貨物的總重量約束，即 18131211xxx15232221xxx23333231xxx12434241xxx （4.1.14）（4.1.15）（4.1.16）（4.1.17） 2) 三個(gè)貨艙的重量限制，即三個(gè)貨艙的重量限制，即 1041312111xxxx1642322212xxxx843332313xxxx（4.1.18） （4.1.19

15、） （4.1.20） 3) 三個(gè)貨艙的空閑限制，即三個(gè)貨艙的空閑限制，即680039058065048041312111xxxx870039058065048042322212xxxx530039258065048043332313xxxx（4.1.21）（4.1.22）（4.1.23） 4) 三個(gè)貨艙裝入重量的平衡約束，即三個(gè)貨艙裝入重量的平衡約束，即81610433323134232221241312111xxxxxxxxxxxx (4.1.24） 模模 型型 求求 解解 將以上模型輸入將以上模型輸入LINDO求解，可以得到結(jié)果為：求解，可以得到結(jié)果為： 貨物貨物2裝入前倉裝入前倉10噸、裝入后倉噸、裝入后倉5噸；噸； 貨物貨物3裝入中倉裝入中倉13噸、裝入后倉噸、裝入后倉3噸；噸； 貨物貨物4裝入中倉裝入中倉3噸噸.最大利潤約最大利潤約121516元（最優(yōu)解四元（最優(yōu)解四舍