線性問(wèn)題及圖解法

線性問(wèn)題及圖解法1第一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三《管理運(yùn)籌學(xué)》課程

教學(xué)大綱課時(shí)安排：

序號(hào)

課程內(nèi)容

學(xué)時(shí)

1第一講管理運(yùn)籌學(xué)序論，線性規(guī)劃問(wèn)題

42第二講線性規(guī)劃的圖解法及靈敏度分析43第三講線性規(guī)劃問(wèn)題的計(jì)算機(jī)求解及在管理中的應(yīng)用42第四講運(yùn)輸問(wèn)題43第五講整數(shù)規(guī)劃44第六講目標(biāo)規(guī)劃45第七講動(dòng)態(tài)規(guī)劃86第八講圖與網(wǎng)絡(luò)模型排隊(duì)論,對(duì)策論87第九講存儲(chǔ)論、排隊(duì)論、對(duì)策論及決策分析簡(jiǎn)介8第二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用20世紀(jì)整個(gè)世界參與規(guī)模最大的事件是什么？第二次世界大戰(zhàn)！整個(gè)世界的資源都投入到了第二次世界大戰(zhàn)中。如何才能更好地利用資源，分配有限的資源，這是一個(gè)值得研究的問(wèn)題。當(dāng)時(shí)在英國(guó)軍隊(duì)中率先成立了研究小組——運(yùn)籌小組來(lái)研究這些問(wèn)題，這就是著名的OR小組.很快美軍中也相繼成立了OR小組。戰(zhàn)爭(zhēng)——

運(yùn)籌學(xué)誕生的溫床。第三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用二戰(zhàn)中成功的運(yùn)籌學(xué)案例：英國(guó)防空部門如何布置防空雷達(dá)，建立有效的防空警報(bào)系統(tǒng)。英，美空軍如何提高對(duì)地面目標(biāo)轟炸的效率。如何安排反潛飛機(jī)的巡邏飛行線路。深水炸彈的合理爆炸深度，摧毀德軍潛艇數(shù)增加400%。商船如何編隊(duì)，遭潛艇攻擊時(shí)如何減少損失。使船只受敵機(jī)攻擊時(shí)，中彈數(shù)由47%降到29%。這些研究大大提高了盟軍的作戰(zhàn)能力，為反法西斯戰(zhàn)爭(zhēng)的最后勝利作出了巨大的貢獻(xiàn)！第四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用戰(zhàn)爭(zhēng)結(jié)束了！

整個(gè)世界投入到了戰(zhàn)后的重建國(guó)家的經(jīng)濟(jì)之中。運(yùn)籌學(xué)的方法相繼在工業(yè)，農(nóng)業(yè)，經(jīng)濟(jì)，社會(huì)問(wèn)題等各個(gè)領(lǐng)域中展開(kāi)了應(yīng)用。與此同時(shí)，運(yùn)籌數(shù)學(xué)有了飛快的發(fā)展，并形成了許多運(yùn)籌學(xué)的分支。線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃，動(dòng)態(tài)規(guī)劃，圖與網(wǎng)絡(luò)分析，統(tǒng)籌方法，排隊(duì)論，存儲(chǔ)論，對(duì)策論，決策論，多目標(biāo)決策。第五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的性質(zhì)和特點(diǎn)一種哲學(xué)方法論;研究“事”而非“物”;科學(xué)性，實(shí)踐性，系統(tǒng)性，綜合性;模型的特點(diǎn)——系統(tǒng)優(yōu)化模型。運(yùn)籌學(xué)——

為決策機(jī)構(gòu)在對(duì)其控制下業(yè)務(wù)活動(dòng)進(jìn)行決策時(shí)，提供以數(shù)量化為基礎(chǔ)的科學(xué)方法。運(yùn)籌學(xué)——

一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識(shí)和數(shù)學(xué)方法，解決實(shí)際中提出的專門問(wèn)題。運(yùn)籌學(xué)——

是一種給出問(wèn)題壞的答案的藝術(shù)，否則問(wèn)題的結(jié)果會(huì)更壞。第六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的工作步驟

運(yùn)籌學(xué)在解決大量實(shí)際問(wèn)題的過(guò)程中形成了自己的工作步驟：提出和形成問(wèn)題。即弄清問(wèn)題的目標(biāo)，可能的約束，問(wèn)題的可控變量以及有關(guān)參數(shù)，搜集有關(guān)資料;建立模型。即把問(wèn)題中可控變量，參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來(lái);求解。用各種手段（主要是數(shù)學(xué)方法，也可用其他方法）將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī)，解的精度要可由求決策者提出。第七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的工作步驟解的檢驗(yàn)。首先檢查求解步驟和程序有無(wú)錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)問(wèn)題；解的控制。通過(guò)控制解的變化過(guò)程決定是否要作一定的改變；解的實(shí)施。是指將解用到實(shí)際中必須考慮到實(shí)施的問(wèn)題，如向?qū)嶋H部門講清解的用法，在實(shí)施中可能產(chǎn)生的問(wèn)題和修改。第八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的模型運(yùn)籌學(xué)在解決問(wèn)題時(shí)，按研究對(duì)象不同可構(gòu)造各種不同的模型。模型是研究者對(duì)客觀現(xiàn)實(shí)經(jīng)過(guò)思維抽象后用文字、圖表、符號(hào)、關(guān)系以及實(shí)體模樣描述所認(rèn)識(shí)到的客觀對(duì)象。模型的有關(guān)參數(shù)和關(guān)系式是較容易改變的，這樣是有助于問(wèn)題的分析和研究。利用模型可以進(jìn)行一定預(yù)測(cè)、靈敏度分析等。模型的三種基本形式：（1）形象模型，（2）模擬模型，（3）符號(hào)或數(shù)學(xué)模型。構(gòu)造模型是一種創(chuàng)造性勞動(dòng)，成功的模型往往是科學(xué)和藝術(shù)的結(jié)晶，構(gòu)造模型的方法和思路通常有以下幾種：第九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用直接分析法按研究者對(duì)問(wèn)題內(nèi)在機(jī)理的認(rèn)識(shí)直接構(gòu)造出模型。運(yùn)籌學(xué)中已有不少現(xiàn)存的模型，如線性規(guī)劃模型、投入產(chǎn)出模型、排隊(duì)模型、存儲(chǔ)模型、決策和對(duì)策模型等等。這些模型都有很好的求解方法及求解軟件，但用這些現(xiàn)成的模型研究問(wèn)題時(shí)，應(yīng)注意不能生搬硬套。類比法有些問(wèn)題可以用不同方法構(gòu)造出模型；而這些模型的結(jié)構(gòu)性質(zhì)是類同的，這就可以互相類比。如物理學(xué)中的機(jī)械系統(tǒng)、氣體動(dòng)力學(xué)系統(tǒng)、水力學(xué)系統(tǒng)、熱力學(xué)系統(tǒng)及電路系統(tǒng)之間就有不少彼此類同的現(xiàn)象。甚至有些經(jīng)濟(jì)、社會(huì)系統(tǒng)也可以用物理系統(tǒng)來(lái)類比。在分析有些經(jīng)濟(jì)、社會(huì)問(wèn)題時(shí)，不同國(guó)家之間也可以找出某些類比的現(xiàn)象。第十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用數(shù)據(jù)分析法

對(duì)有些問(wèn)題的機(jī)理尚未了解清楚，若能搜集到與此問(wèn)題密切有關(guān)的大量數(shù)據(jù)，或通過(guò)某些試驗(yàn)獲得大量數(shù)據(jù)，這就可以用統(tǒng)計(jì)分析法建摸。試驗(yàn)分析法

有些問(wèn)題的機(jī)理不清，又不能作大量試驗(yàn)來(lái)獲得數(shù)據(jù)，這時(shí)只能通過(guò)做局部試驗(yàn)的數(shù)據(jù)加上分析來(lái)構(gòu)造模型。想定（構(gòu)想）法當(dāng)有些問(wèn)題的機(jī)理不清，又缺少數(shù)據(jù)，又不能作試驗(yàn)來(lái)獲得數(shù)據(jù)時(shí)，例如有些社會(huì)、經(jīng)濟(jì)、軍事問(wèn)題，人們只能在已有的知識(shí)、經(jīng)驗(yàn)和某些研究的基礎(chǔ)上，對(duì)于將來(lái)可能發(fā)生的情況給出邏輯上合理的設(shè)想和描述。然后用已有的方法構(gòu)造模型，并不斷修正完善，直至比較滿意為止。第十一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用運(yùn)籌學(xué)的主要應(yīng)用

二次大戰(zhàn)后運(yùn)籌學(xué)的應(yīng)用迅速轉(zhuǎn)向了民用，下面對(duì)某些重要領(lǐng)域給于簡(jiǎn)述。市場(chǎng)銷售------廣告預(yù)算和媒介選擇、競(jìng)爭(zhēng)性定價(jià)、新品開(kāi)發(fā)、銷售計(jì)劃的制訂。（美）杜邦公司在五十年代起就非常重視將運(yùn)籌學(xué)用于如何做好廣告工作、產(chǎn)品定價(jià)、新品引入。生產(chǎn)計(jì)劃------從總體確定生產(chǎn)、存儲(chǔ)和勞動(dòng)力的配合等計(jì)劃適應(yīng)波動(dòng)的需求計(jì)劃。巴基斯坦一重型制造廠用線性規(guī)劃安排生產(chǎn)計(jì)劃，節(jié)省10%的生產(chǎn)費(fèi)用。運(yùn)輸問(wèn)題------涉及空運(yùn)、水運(yùn)、公路、鐵路運(yùn)輸、管道運(yùn)輸?shù)?。公路網(wǎng)的設(shè)計(jì)和分析，市內(nèi)公共汽車路線的選擇和行車時(shí)刻表的安排，出租車的調(diào)度等。第十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用人事管理------需求估計(jì)，教育和培訓(xùn)，人員分配（各種指派問(wèn)題），合理利用，人才評(píng)價(jià)等。設(shè)備維修，更新和可靠性等。計(jì)算機(jī)和信息系統(tǒng)------內(nèi)存分配研究，網(wǎng)絡(luò)設(shè)計(jì)分析等。城市管理------緊急服務(wù)系統(tǒng)的設(shè)計(jì)和運(yùn)用，區(qū)域布局規(guī)劃，管道網(wǎng)絡(luò)設(shè)計(jì)等。（美）曾用排隊(duì)論確定紐約市緊急電話站的值班人數(shù)，（加）設(shè)計(jì)城市警車配置和負(fù)責(zé)范圍、指揮接警后的行走路線等。對(duì)策研究------價(jià)格競(jìng)爭(zhēng)，中央與地方政府投資分配博弈，工會(huì)與雇主間的博弈。第十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用國(guó)際運(yùn)籌與管理科學(xué)協(xié)會(huì)（INFORMS）及其下屬的管理科學(xué)實(shí)踐學(xué)會(huì)每年主持評(píng)定弗蘭茨·厄德曼獎(jiǎng)（FranzEdelman）以獎(jiǎng)勵(lì)為運(yùn)籌學(xué)在管理中的應(yīng)用的卓越成就者，一般會(huì)授予六位優(yōu)勝者，其獲獎(jiǎng)項(xiàng)目的文章都在第二年發(fā)表在著名刊物Interface的新年第一期上。下表列寫出了部分發(fā)表在該期刊上的獲獎(jiǎng)項(xiàng)目：組織應(yīng)用效果聯(lián)合航空公司在滿足乘客需求的前提下，以最低成本進(jìn)行訂票及機(jī)場(chǎng)工作班次安排每年節(jié)約成本600萬(wàn)美元Citgo石油公司優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送和營(yíng)銷每年節(jié)約成本7000萬(wàn)美元AT＆T優(yōu)化商業(yè)用戶的電話銷售中心選址每年節(jié)約成本4.06億美元，銷售額大幅增加第十四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三緒論

歷史，性質(zhì)，應(yīng)用荷瑪特發(fā)展公司(HomartDevelopmentCo.)優(yōu)化商業(yè)區(qū)和辦公樓銷售程序每年節(jié)約成本4000萬(wàn)美元標(biāo)準(zhǔn)品牌公司控制成品庫(kù)存（制定最優(yōu)再訂購(gòu)點(diǎn)和訂購(gòu)量確保安全庫(kù)存）每年節(jié)約成本380萬(wàn)美元施樂(lè)公司通過(guò)戰(zhàn)略調(diào)整，縮短維修機(jī)器的反應(yīng)時(shí)間和改進(jìn)維修人員的生產(chǎn)率每生產(chǎn)效率提高50%以上寶潔公司重新設(shè)計(jì)北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快了市場(chǎng)進(jìn)入速度每年節(jié)約成本2億美元法國(guó)國(guó)家鐵路公司制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日運(yùn)營(yíng)量年節(jié)約成本1500萬(wàn)美元，年收入大幅增加Delta航空公司優(yōu)化配置上千個(gè)國(guó)內(nèi)航線航班來(lái)實(shí)現(xiàn)利潤(rùn)最大化每年節(jié)約成本1億美元IBM重組全球供應(yīng)鏈，保持最小庫(kù)存的同時(shí)滿足客戶需求第一年節(jié)約成本7.5億美元第十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三第二章線性規(guī)劃及圖解法第十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三問(wèn)題的提出解決有限資源在有競(jìng)爭(zhēng)的使用方向中如何進(jìn)行最佳分配。線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，也是運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一。自1947年旦茨基（G.B.Dantzig）提出了一般線性規(guī)劃問(wèn)題求解的方法——單純形法（simplexmethod）之后，線性規(guī)劃已被廣泛應(yīng)用于解決經(jīng)濟(jì)管理和工業(yè)生產(chǎn)中遇到的實(shí)際問(wèn)題。調(diào)查表明，在全球500家最大的企業(yè)中，有85%的企業(yè)都曾使用線性規(guī)劃解決經(jīng)營(yíng)管理中遇到的復(fù)雜問(wèn)題。線性規(guī)劃的使用為應(yīng)用者節(jié)約了數(shù)以億萬(wàn)計(jì)的資金。線性規(guī)劃LinearProgramming（LP）第十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三本講中我們將討論什么是線性規(guī)劃問(wèn)題，線性規(guī)劃問(wèn)題的數(shù)學(xué)表示，基本概念和圖解方法。線性規(guī)劃問(wèn)題是什么樣的一類問(wèn)題呢？請(qǐng)看案例------線性規(guī)劃LinearProgramming（LP）第十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）曾幾何時(shí)長(zhǎng)江水，哺育華夏代代人;誰(shuí)知后代疏珍惜，清清江水黑如泥。案例河流污染治理規(guī)劃問(wèn)題第十九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）曾幾何時(shí)長(zhǎng)江水，哺育華夏代代人;誰(shuí)知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問(wèn)題第二十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）曾幾何時(shí)長(zhǎng)江水，哺育華夏代代人;誰(shuí)知后代疏珍惜，清清江水黑如泥。今日認(rèn)識(shí)未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問(wèn)題第二十一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）今日認(rèn)識(shí)未為晚，吾輩齊心治環(huán)境;線性規(guī)劃大有用，定讓江水綠如藍(lán)。曾幾何時(shí)長(zhǎng)江水，哺育華夏代代人;誰(shuí)知后代疏珍惜，清清江水黑如泥。工廠2工廠3工廠1工廠4工廠5工廠6工廠9工廠8工廠7案例河流污染治理規(guī)劃問(wèn)題第二十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）案例河流污染治理規(guī)劃問(wèn)題背景資料:長(zhǎng)江流域某區(qū)域內(nèi)有9化工廠，各廠每月產(chǎn)生的工業(yè)污水量如表-1，流經(jīng)各化工廠的河流流量如表-2，各化工廠治理工業(yè)污水的成本如表-3。上游廠排放的污水流到相鄰下游廠以前，有20%可自然凈化。根據(jù)環(huán)保標(biāo)準(zhǔn)河流中此種工業(yè)污水的含量不應(yīng)超過(guò)0.2%。從該區(qū)域整體考慮，各化工廠應(yīng)該分別處理多少工業(yè)污水才能既滿足環(huán)保要求，又使9化工廠治理工業(yè)污水的總費(fèi)用最少。第二十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三背景資料:線性規(guī)劃LinearProgramming（LP）化工廠11.2化工廠42化工廠72化工廠21化工廠51化工廠80.8化工廠33化工廠61化工廠91.5表-1污水產(chǎn)生量單位：萬(wàn)m3表-2流經(jīng)各化工廠的河流流量單位：萬(wàn)m3表-3治理工業(yè)污水的成本單位：百萬(wàn)元/萬(wàn)m3化工廠1500化工廠41200化工廠71200化工廠2300化工廠5600化工廠8200化工廠31800化工廠6400化工廠9700化工廠13化工廠44化工廠71化工廠25化工廠55化工廠82化工廠32化工廠66化工廠93第二十四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）194582637問(wèn)題分析：區(qū)域污染治理的決策——各個(gè)化工廠應(yīng)處理的工業(yè)污水量（或應(yīng)排放的工業(yè)污水量）。區(qū)域污染治理的約束——即滿足環(huán)保要求排放工業(yè)污水（區(qū)域內(nèi)河流中任何點(diǎn)檢測(cè)都應(yīng)符合環(huán)保標(biāo)準(zhǔn)）。區(qū)域污染治理的目標(biāo)——總治理成本最少。第二十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）194582637建立模型：（建模三步曲）1、——決策變量（設(shè)定）分析：設(shè)第i個(gè)化工廠應(yīng)處理的工業(yè)污水量為Xi萬(wàn)m3，則根據(jù)問(wèn)題描述的情況以化工廠1、2、…、9加以分析則可得如下近似關(guān)系式2、——環(huán)境約束（限制）分析：對(duì)化工廠2應(yīng)有---

（1-X2）/300≦0.2%

對(duì)化工廠8應(yīng)有---

（0.8-X8）/200≦0.2%第二十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）194582637對(duì)化工廠1應(yīng)有---｛（1.2-X1）+0.8（1-X2）+（0.8-X8）｝/500≦0.2%對(duì)化工廠9應(yīng)有——（1.5-X9）/700≦0.2%對(duì)化工廠7應(yīng)有——

（2-X7）+0.8（1.5-X9）/1200≦0.2%……此外顯然還應(yīng)有Xi≧0（i=1，2，3…8，9）綜上所述決策者所需考慮的區(qū)域內(nèi)各個(gè)化工廠應(yīng)處理的工業(yè)污水量Xi應(yīng)滿足上述所有不等式方程。我們將這些不等式方程構(gòu)成的方程組稱為污水治理的約束條件。第二十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）1945826373、——決策目標(biāo)（確定）分析：另一方面污水治理的總成本可表示為Z（單位：百萬(wàn)元）Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9而決策者的目標(biāo)是確定滿足約束條件的Xi使得Z取得最小值。因此決策目標(biāo)可表示為：MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9將上述分析歸納后即可得如下數(shù)學(xué)符合模型：第二十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）河流污染治理規(guī)劃問(wèn)題數(shù)學(xué)模型（整理之后）194582637MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9X2≧0.4X8≧1.6X1+0.8X2+0.8X8≧4.4X9≧0.1X7+0.8X9≧0.8X4+0.8X7+0.64X9≧2.16X6≧0.2X5+0.8X6≧0.6X3+0.8X4+0.8X5+0.64X6+0.64X7+5.12X9≧9.4Xi≧0（i=1，2，3，4，5，6，7，8，9）s.t.第二十九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）線性規(guī)劃模型——

LinearProgrammingModel

或LinearOptimizationModel

用線性規(guī)劃方法解決實(shí)際經(jīng)濟(jì)與管理問(wèn)題的第一步是分析建立能夠完整描述和反映實(shí)際問(wèn)題的線性規(guī)劃模型。第三十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）通常建立LP模型有以下幾個(gè)基本步驟：確定決策變量：決策變量是模型要確定的未知變量，也是模型最重要的參數(shù)，是決策者解決實(shí)際問(wèn)題的控制變量。確定目標(biāo)函數(shù)：目標(biāo)函數(shù)決定線性規(guī)劃問(wèn)題的優(yōu)化方向，是模型的重要組成部分。實(shí)際問(wèn)題的目標(biāo)可表示為決策變量的一個(gè)線性函數(shù)，并根據(jù)目標(biāo)函數(shù)的實(shí)質(zhì)確定優(yōu)化方向，一般可為最大化（max）或最小化（min）。第三十一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）通常建立LP模型有以下幾個(gè)步驟：確定約束方程：一個(gè)正確的線性規(guī)劃模型應(yīng)能通過(guò)約束方程來(lái)描述和反映一系列客觀條件或環(huán)境的限制，這些限制通過(guò)一系列線性等式或不等式方程組來(lái)描述。變量取值限制：一般情況下，決策變量取正值（非負(fù)值）。因此，模型中應(yīng)有變量的非負(fù)約束即Xj≥0，但要注意也存在例外的情形。第三十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）線性規(guī)劃的一般形式:max（或min）z=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn（≤=≥）b1a21x1+a22x2+…+a2nxn

（≤=≥）b2s.t.………………am1x1+am2x2+…+amnxn（≤=≥）bm

xj≥0（j=1，2…n）此模型的兩大基本特征：1、目標(biāo)函數(shù)為決策變量的線性函數(shù)；2、約束方程為決策變量的線性不等式或等式方程。第三十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1、目標(biāo)函數(shù)極大化——“max”2、等式約束條件——“=”且右端常數(shù)bi非負(fù)3、變量非負(fù)——“xj≥0”

maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）第三十四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）化標(biāo)準(zhǔn)形式的一般步驟目標(biāo)函數(shù)極小化“極大化”約束條件的右端項(xiàng)bi≤0“bi≥0”約束條件為不等式≤或≥“=”取值無(wú)約束（自由）變量“非負(fù)變量”取值非正變量“非負(fù)變量”線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式的作用——為單純形法求解作準(zhǔn)備！第三十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）線性規(guī)劃問(wèn)題的求解：（圖解）如何求解一般的線性規(guī)劃呢？下面我們分析一下簡(jiǎn)單的情況——

只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。第三十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法例1maxz=2x1+x25x2

≤15s.t.6x1+2x2

≤24x1+x2

≤5x1

，x2

≥0第三十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1

，x2≥0唯一最優(yōu)解X=（9/2，3/2）D-可行域目標(biāo)函數(shù)等值線：z=0=2x1+x2x1x25x2=156x1+2x2=24x1+x2=5第三十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法例

maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0第三十九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法maxZ=2X1+X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域第四十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ

minZ（3.8，4）34.2=3X1+5.7X2

紅色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏虻谒氖豁?yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZ

minZ

8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點(diǎn)是唯一最優(yōu)解第四十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法maxZ=5X1+4X2x1x2oD可行域

maxZ

minZ最優(yōu)解目標(biāo)值Z趨于無(wú)窮第四十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法maxZ=5X1+4X2x1x2o可行解域?yàn)榭盏谒氖捻?yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法圖解法的啟示線性規(guī)劃問(wèn)題解的可能情況

a.唯一最優(yōu)解

b.無(wú)窮多最優(yōu)解

c.無(wú)解（沒(méi)有有界最優(yōu)解，無(wú)可行解）若線性規(guī)劃問(wèn)題的可行域非空，則可行域是一個(gè)凸集；若線性規(guī)劃問(wèn)題的最優(yōu)解存在，則一定可以在可行域的凸集的某個(gè)頂點(diǎn)上達(dá)到。第四十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法進(jìn)行靈敏度分析在線性規(guī)劃問(wèn)題的模型中，一般有三類參數(shù)（常數(shù)），它們是：

cj

——常稱為“利潤(rùn)”參數(shù)，或成本參數(shù)；

bi

——常稱為“資源”參數(shù)；

aij

——常稱為“技術(shù)”參數(shù)。

靈敏度（敏感性）分析的目的是弄清楚這些參數(shù)的變化與原來(lái)的最優(yōu)解變化之間的影響關(guān)系。第四十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法進(jìn)行靈敏度分析

靈敏度分析通常有兩種類型：1、參數(shù)變化后，原最優(yōu)解是否改變？如改變，新的最優(yōu)解為何。2、若要保持原最優(yōu)解不變，允許參數(shù)在何范圍變化？下面以P10，例1為例，闡述用圖解方法進(jìn)行靈敏度分析。第四十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法進(jìn)行靈敏度分析P10，例1maxz=50x1+100x2

s.t.x1+x2

≤3002x1+x2

≤400x2

≤250x1

，x2

≥0第四十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法進(jìn)行靈敏度分析例1maxz=50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1

，x2≥0x1x2最優(yōu)解X=(x1,x2)=(50,250);maxz=27500第四十九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三線性規(guī)劃LinearProgramming（LP）圖解法進(jìn)行靈敏度分析

m