1線性規(guī)劃與單純形法

1、運(yùn)籌學(xué)Operational Research主講：張曉果 運(yùn)籌學(xué)是一門基礎(chǔ)性應(yīng)用學(xué)科，主要是將社會經(jīng)濟(jì)建設(shè)實(shí)踐中經(jīng)濟(jì)、軍事、成產(chǎn)、管理、組織等事件中出現(xiàn)的一些帶有普遍性的運(yùn)籌問題加以提煉，然后利用科學(xué)方法進(jìn)行分析、求解等。前者提供模型，后者提供理論和方法。運(yùn)籌學(xué)主要研究系統(tǒng)最優(yōu)化問題，通過對建立的模型求解，為決策者進(jìn)行決策提供科學(xué)依據(jù)。緒 論一、運(yùn)籌學(xué)發(fā)展簡介二、運(yùn)籌學(xué)定義三、運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)四、運(yùn)籌學(xué)的應(yīng)用五、運(yùn)籌學(xué)的工作步驟六、運(yùn)籌學(xué)的分支一、運(yùn)籌學(xué)（OR）發(fā)展簡介英國稱為 Operational Research美國稱為 Operations Research樸素運(yùn)籌學(xué)思想的出現(xiàn)可以

2、追溯到很早戰(zhàn)國時(shí)期齊王田忌賽馬、北宋丁渭重修皇宮運(yùn)籌學(xué)的三個(gè)起源：軍事、經(jīng)濟(jì)、管理軍 事第一次世界大戰(zhàn)期間 1914-1915蘭徹斯特的若干軍事論文 研究戰(zhàn)爭的勝負(fù)同兵力多寡、火力強(qiáng)弱之間的關(guān)系； 愛迪生解決反潛戰(zhàn)的“戰(zhàn)術(shù)對策演示盤” 反潛戰(zhàn)的研究項(xiàng)目：匯編各項(xiàng)典型統(tǒng)計(jì)數(shù)據(jù)用于選擇回避或擊毀潛艇的最佳方法，使用“戰(zhàn)術(shù)對策演示盤”解決免受潛艇攻擊的問題。軍 事二戰(zhàn)期間的案例 鮑德西（Bawdsey）雷達(dá)站的研究“布萊克特馬戲團(tuán)/雜技班”的出色工作 項(xiàng)目的巨大實(shí)際價(jià)值：明確的目標(biāo)；整體化的思想；數(shù)量化的分析；多學(xué)科的協(xié)調(diào)；最優(yōu)化的結(jié)果 大西洋反潛戰(zhàn)Morse小組的重要工作 協(xié)助英國打破了德國對英吉

3、利海峽的海上封鎖；軍事運(yùn)籌學(xué)的特點(diǎn)定量化系統(tǒng)化方法迅速發(fā)展采集真實(shí)的數(shù)據(jù)多學(xué)科密切協(xié)作（數(shù)學(xué)、管理等）解決方法滲透著物理學(xué)思想管 理泰勒的動(dòng)作研究切削效率與車速、進(jìn)刀量等因素的數(shù)學(xué)關(guān)系優(yōu)選問題（提高切削效率）統(tǒng)籌方法（用于生產(chǎn)活動(dòng)分析和計(jì)劃安排）前蘇聯(lián)康特洛維奇的工作（生產(chǎn)組織與計(jì)劃方法）經(jīng) 濟(jì)QUSNAY（魁內(nèi)）1758年在凡爾賽發(fā)表經(jīng)濟(jì)表對經(jīng)濟(jì)中各部門的平衡關(guān)系做了最早的研究Walras（沃爾拉思）對經(jīng)濟(jì)平衡問題的研究1932年Von Neumann提出第一個(gè)廣義經(jīng)濟(jì)平衡模型馬克思是最早將數(shù)學(xué)用于經(jīng)濟(jì)研究的經(jīng)濟(jì)學(xué)家之一，在沃爾拉思鉆研他的數(shù)理經(jīng)濟(jì)問題的同時(shí)，馬克思也在研究他所碰到的數(shù)理經(jīng)濟(jì)

4、問題運(yùn)籌學(xué)的發(fā)展萌芽時(shí)期 樸素的OR思想自古有之早期研究 經(jīng)濟(jì)表、一戰(zhàn)、生產(chǎn)組織與計(jì)劃形成與發(fā)展時(shí)期 二戰(zhàn)；戰(zhàn)后20世紀(jì)50-60年代走向成熟 成立學(xué)會，創(chuàng)辦刊物，高校開課，軍事運(yùn)籌學(xué)運(yùn)籌學(xué)的發(fā)展趨勢成熟的學(xué)科分支縱深發(fā)展新的研究領(lǐng)域產(chǎn)生 與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀念不斷變化二、運(yùn)籌學(xué)定義運(yùn)籌學(xué)為決策機(jī)構(gòu)對所控制的業(yè)務(wù)活動(dòng)作決策時(shí)，提供以數(shù)量為基礎(chǔ)的科學(xué)方法Morse 和 Kimball運(yùn)籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個(gè)科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測、比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針

5、和政策英國運(yùn)籌學(xué)會二、運(yùn)籌學(xué)定義運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法對經(jīng)濟(jì)管理系統(tǒng)中人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理中國企業(yè)管理百科全書（1984年版）運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)，為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具大英百科全書二、運(yùn)籌學(xué)定義運(yùn)籌學(xué)用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國防等部門在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，是實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)，它可以用來預(yù)測發(fā)展趨勢，制定行動(dòng)規(guī)劃或優(yōu)選可行方案中國大百科全書（自動(dòng)控制與系統(tǒng)工程卷，1991年版）由于運(yùn)籌學(xué)涉及的主要領(lǐng)域是管理問題，研究的基本手段是建立數(shù)

6、學(xué)模型，并比較多地利用各種數(shù)學(xué)工具，于是有人將運(yùn)籌學(xué)稱做“管理數(shù)學(xué)”。三、運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)引入數(shù)學(xué)方法解決實(shí)際問題定性與定量方法結(jié)合系統(tǒng)與整體性從全局考察問題應(yīng)用性源于實(shí)踐、為了實(shí)踐、服務(wù)于實(shí)踐交叉學(xué)科涉及經(jīng)濟(jì)、管理、數(shù)學(xué)、工程和系統(tǒng)等多學(xué)科開放性不斷產(chǎn)生新的問題和學(xué)科分支多分支問題的復(fù)雜和多樣性四、運(yùn)籌學(xué)的應(yīng)用生產(chǎn)計(jì)劃：生產(chǎn)作業(yè)的計(jì)劃、日程表的編排、合理下料、配料問題、物料管理等。庫存管理：多種物資庫存量的系統(tǒng)組織與安排管理，確定某些設(shè)備的能力或容量，如停車場的大小、合理的水庫容量等運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及廠址的選擇等。人事管理：對人員的需求和使用的

7、預(yù)測，確定人員編制、人員合理分配，建立人才評價(jià)體系、人才開發(fā)的規(guī)劃、激勵(lì)機(jī)制的研究等。財(cái)務(wù)和會計(jì)：包括預(yù)測、貸款、成本分析、定價(jià)、證券管理、現(xiàn)金管理等。市場營銷：廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開發(fā)與銷售計(jì)劃制定等。城市管理：各種緊急服務(wù)系統(tǒng)的設(shè)計(jì)與應(yīng)用，城市垃圾的清掃、搬運(yùn)和處理，城市供水和污水處理系統(tǒng)的規(guī)劃，區(qū)域規(guī)劃，市區(qū)交通網(wǎng)絡(luò)的規(guī)劃與管理等。五、運(yùn)籌學(xué)的工作步驟提出問題用自然語言描述問題。建立數(shù)學(xué)模型用變量、函數(shù)、方程描述問題。求解主要用數(shù)學(xué)方法將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解，復(fù)雜模型求解要用計(jì)算機(jī)。解的檢驗(yàn)檢查模型和求解步驟有無錯(cuò)誤，檢查解是否反映現(xiàn)實(shí)問題。解的實(shí)施決策者根

8、據(jù)自己的經(jīng)驗(yàn)和偏好，對方案進(jìn)行選擇和修改，作出實(shí)施的決定。六、運(yùn)籌學(xué)的分支數(shù)學(xué)規(guī)劃包括：線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃，動(dòng)態(tài)規(guī)劃，隨機(jī)規(guī)劃，模糊規(guī)劃；圖論與網(wǎng)絡(luò)；排隊(duì)論；存儲論；對策論；決策論；可靠性和質(zhì)量管理等。七、如何學(xué)好運(yùn)籌學(xué) 學(xué)習(xí)運(yùn)籌學(xué)要把重點(diǎn)放在分析、理解有關(guān)的概念、思路上。在學(xué)習(xí)過程中，應(yīng)該多向自己提問，例如一個(gè)方法的實(shí)質(zhì)是什么，為什么這樣做，怎么做等。 學(xué)習(xí)或復(fù)習(xí)時(shí)要掌握三個(gè)重要環(huán)節(jié)：1.認(rèn)真閱讀教材和參考資料，以指定教材為主，同時(shí)參考其他有關(guān)書籍。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致的。注意主從，參考資料會幫助你開闊思路，使學(xué)習(xí)深入。 2.要

9、在理解了基本概念和理論的基礎(chǔ)上研究例題，注意例題是為了幫助理解概念、理論的。作業(yè)練習(xí)的主要作用也是這樣，它同時(shí)還有讓你自己檢查自己學(xué)習(xí)的作用。因此，做題要有信心，要獨(dú)立完成，不要怕出錯(cuò)。因?yàn)椋麄€(gè)課程是一個(gè)整體，各節(jié)內(nèi)容有內(nèi)在聯(lián)系，只要學(xué)到一定程度，知識融會貫通起來，你自己就能夠?qū)λ鲱}目的正確性作出判斷。3、要學(xué)會做學(xué)習(xí)小結(jié)。每一節(jié)或一章學(xué)完后，必須學(xué)會用精煉的語言來概述該書所講內(nèi)容。這樣，你才能夠從較高的角度來看問題，更深刻地理解有關(guān)知識和內(nèi)容。這就稱作“把書讀薄”，若能夠結(jié)合相關(guān)參考文獻(xiàn)并深入理解，把相關(guān)知識從更深入、廣泛的角度進(jìn)行論述，則稱為“把書讀厚”。第一章 線性規(guī)劃與單純形法本章

10、內(nèi)容重點(diǎn)線性規(guī)劃模型與解的主要概念線性規(guī)劃的單純形法，線性規(guī)劃多解分析線性規(guī)劃應(yīng)用建模第1節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型一、實(shí)例例1 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時(shí)和原料A、B的消耗量如下表。該工廠每生產(chǎn)一件產(chǎn)品可獲利2元，每生產(chǎn)一件產(chǎn)品可獲利3元，問應(yīng)如何安排生產(chǎn)計(jì)劃能使該廠獲利最多？ 解：這個(gè)問題可以用下面的數(shù)學(xué)模型來描述，設(shè)計(jì)劃期內(nèi)產(chǎn)品、的產(chǎn)量分別為x1，x2，可獲利潤用z表示，則有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1, x20例2 靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，兩工廠之間有一條流

11、量為每天200萬m3的支流（見圖）。第一化工廠每天排放污水2萬m3，第二化工廠每天排放污水 1.4萬m3。污水從工廠1流到工廠2前會有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/萬m3和800元/萬m3。問兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？ 解： 設(shè)工廠1和工廠2每天分別處理污水x1和x2萬m3，則有：Min z=1000 x1+800 x2 (2-x1)/500 0.0020.8(2-x1)+1.4-x2/700 0.002 x12, x21.4 x1, x20二、總結(jié)都有一個(gè)要達(dá)到的目標(biāo)，可以用決策變量的線

12、性函數(shù)(目標(biāo)函數(shù),Objective Function）來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。線性規(guī)劃（Linear Programming）問題的共同特征： 每一個(gè)問題都用一組決策變量(Decision Variable)（x1, x2, , xn）表示某一方案，這組決策變量的值代表一個(gè)具體方案，這些變量是非負(fù)的。 存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。結(jié)論：線性規(guī)劃是研究在一組線性不等式或等式約束條件下，使某一線性目標(biāo)函數(shù)取最大或最小的極值問題。 滿足以上條件的數(shù)學(xué)模型稱為線性規(guī)劃模型。線性規(guī)劃模型的一般形式如下：三、線性規(guī)劃問題的標(biāo)準(zhǔn)型1.

13、 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型的四個(gè)特點(diǎn)：目標(biāo)最大化、約束條件為線性等式、決策變量均非負(fù)、約束條件右端項(xiàng)非負(fù)。2. 所有LP問題均可化為標(biāo)準(zhǔn)型(1)若目標(biāo)函數(shù)為MinZ，令Z =-Z，則MinZ等價(jià)于MaxZ(2)將不等式約束條件化為等式約束條件令xj= xj - xj，對模型中的進(jìn)行變量代換。不符合標(biāo)準(zhǔn)型的幾個(gè)方面：目標(biāo)函數(shù)為 min z=c1x1+c2x2+cnxn令z=-z ,變?yōu)?max z= -c1x1- c2x2- -cnxn約束條件為 a11x1+a12x2+a1nxnb1加入非負(fù)變量xn+1，稱為松弛變量，有 a11x1+a12x2+a1nxn+xn+1=b1約束條件為 a11x1+a12x2

14、+a1nxnb1減去非負(fù)變量xn+1，稱為剩余變量，有 a11x1+a12x2+a1nxn - xn+1=b1變量xj無約束。例3可化為例4 化標(biāo)準(zhǔn)型3.線性規(guī)劃的向量和矩陣表達(dá)式式中：C = c1 c2 .cn矩陣式：向量式：課堂作業(yè)四、兩變量線性規(guī)劃問題的圖解法1.線性不等式的幾何意義 半平面作出LP問題的可行域作出目標(biāo)函數(shù)的等值線移動(dòng)等值線到可行域邊界得到最優(yōu)點(diǎn)2.圖解法步驟對于只有兩個(gè)變量的線性規(guī)劃問題，可以在二維直角坐標(biāo)平面上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。4x1=164x2=12x1+2x2=8x1x248430例6 （書P10）：Q(4,2)Z=2x1+3x2 做目標(biāo)函數(shù)

15、2x1+3x2的等值線，與陰影部分的邊界相交于Q(4,2)點(diǎn)，表明最優(yōu)生產(chǎn)計(jì)劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。唯一最優(yōu)解無窮多最優(yōu)解x1x2x1x2 解無界3. 圖解法(Graphical Solution)的啟示 具有兩個(gè)變量的線性規(guī)劃問題的可行域是凸多邊形。LP問題有可行解有最優(yōu)解唯一解無窮多解無最優(yōu)解（可行域?yàn)闊o界）無可行解（無解） 線性規(guī)劃問題的解的若干情況若線性規(guī)劃存在最優(yōu)解，它一定在可行域的某個(gè)頂點(diǎn)得到。若線性規(guī)劃問題有可行解，則可行域是一個(gè)凸多邊形。它可能有界，也可能無解。若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解可能是唯一的；也可能是無窮多個(gè)。如果是唯一的，這個(gè)解一定在該凸多邊形的

16、某個(gè)頂點(diǎn)上；如果是無窮多個(gè)，則這些最優(yōu)解一定充滿凸多邊形的一條邊界（包括此邊界的兩個(gè)頂點(diǎn)）。若線性規(guī)劃問題有可行解，但是沒有有限最優(yōu)解，此時(shí)凸多邊形是無界的。若線性規(guī)劃問題沒有可行解，則該問題沒有最優(yōu)解。五、標(biāo)準(zhǔn)型LP問題的解的概念可行解(Feasible Solution)：滿足（2）、（3）的解；最優(yōu)解(Optimal Solution)：滿足（1）的可行解；基(Basis)：設(shè) 為LP問題的系數(shù)矩陣， 為 A的非奇異子矩陣 ，則稱B為LP問題 的一個(gè)基。令B = =( P1 , P2 , , Pm ) 且| B | 0 ，則稱Pj (j=1,2,m) 為基向量。與基向量Pj對應(yīng)的變量xj

17、稱為基變量，記為XB = ( x1 , x2 , , xm )T，其余的變量稱為非基變量(Non-basic Variable) ，記為 XN = ( xm+1 , xm+2 , , xm+n ) T ?；兞?Basic Variable)：基解(Basic Solution)令非基變量 XN = 0，求得的一組基變量 XB的值稱為基解。 基可行解(Basic Feasible Solution) （頂點(diǎn)）滿足非負(fù)條件的基解(既是基解，又是可行解)?；顑?yōu)解既是基解，又是使目標(biāo)函數(shù)值達(dá)到最優(yōu)的解結(jié)論:基可行解數(shù)目 基解數(shù)目 線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解

18、 10/3 244x1x2x1+x2=43x1 +5x2=10第2節(jié) LP問題的基本理論一、基本概念二、基本定理定理1 LP問題的可行域?yàn)橥辜?引理：線性規(guī)劃問題的可行解X=(x1,x2,xn)T是基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。必要性：由基可行解的定義可知。定理2 線性規(guī)劃問題的基可行解對應(yīng)于可行域的頂點(diǎn)。定理3 若可行域有界，則LP問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。 重要結(jié)論: 線性規(guī)劃問題的所有可行解構(gòu)成的集合（可行域）是凸集(定理1);凸集的每個(gè)頂點(diǎn)對應(yīng)于一個(gè)基可行解(定理2),基可行解(頂點(diǎn))的個(gè)數(shù)是有限的;若線性規(guī)劃有最優(yōu)解,必在可行

19、域某頂點(diǎn)上達(dá)到(定理3).因此,我們可在有限個(gè)基可行解中尋找最優(yōu)解.第3節(jié) 單純形法(Simplex Method) 一、基本思想化LP問題為標(biāo)準(zhǔn)型，確定一個(gè)初始基可行解檢驗(yàn)解的最優(yōu)性結(jié)束Y樞軸運(yùn)算（旋轉(zhuǎn)運(yùn)算）尋找另一個(gè)基可行解N 要找到線性規(guī)劃問題的最優(yōu)解，只要在基可行解中尋找就可以了。雖然基可行解的數(shù)目是有限個(gè)（不超過Cnm個(gè)），但當(dāng)m,n較大時(shí)，要用“窮舉法”求出所有基可行解也是行不通的。因此，必須尋求一種更有效的方法。 單純形法的基本思路是：從線性規(guī)劃問題的一個(gè)基可行解開始，轉(zhuǎn)換到另一個(gè)使目標(biāo)函數(shù)值增大的基可行解。反復(fù)迭代，直到目標(biāo)函數(shù)值達(dá)到最大時(shí)，就得到了最優(yōu)解。 按照單純形法的思路

20、求解線性規(guī)劃問題, 要解決三個(gè)問題:給出基可行解; 檢驗(yàn)一個(gè)基可行解是否是最優(yōu)解; 轉(zhuǎn)換到另一個(gè)基可行解. 把線性規(guī)劃問題變成標(biāo)準(zhǔn)型后, 觀察是否每個(gè)約束方程中都有獨(dú)有的、系數(shù)為1的變量. 如果是,則取這些變量作為基變量,便得到一個(gè)基可行解; 否則,就給沒有這種變量的約束條件添加一個(gè)人工變量,同時(shí)修改目標(biāo)函數(shù). (見例題) 如果單純形表最后一行中的j都滿足 j0, 則對應(yīng)的基可行解是最優(yōu)解; 否則就不是最優(yōu)解. j稱為檢驗(yàn)數(shù). 第一,確定換入變量.在大于0的檢驗(yàn)數(shù)中找最大的為k, 對應(yīng)變量xk為換入變量. 第二,確定換出變量. 取=minbi/aik|aik0=bl/alk, 對應(yīng)的第l行的基

21、變量為換出變量. 第三, 旋轉(zhuǎn)運(yùn)算. 換入變量所在的行與換出變量所在的列交叉點(diǎn)的元素稱為主元素,用高斯消去法把主元素化成1, 同列的其他元素化成0, 得到一個(gè)新的單純形表,也就得到一個(gè)新的基可行解. 化為標(biāo)準(zhǔn)型單純形表算法Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 8 1612 1 2 1 0 0 4 4 0 0 1 0 - 0 4 0 0 1 3 0 2 3 0 0 0以4為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x2為換入變量，x5為換出變量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 2 16

22、3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 - -9 2 0 0 0 -3/4以1為主元素進(jìn)行運(yùn)算，x1為換入變量， x3為換出變量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 2 8 3 1 0 1 0 -1/2 - 0 0 -4 1 2 4 0 1 0 0 1/4 12 -13 0 0 -2 0 1/4以2為主元素進(jìn)行運(yùn)算，x5為換入變量， x4為換出變量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X5 3 X2 4 4 2 1 0 0 1/4 0 0 0

23、 -2 1/2 1 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0此時(shí)達(dá)到最優(yōu)解。X*=(4,2), MaxZ=14?；癁闃?biāo)準(zhǔn)型單純形表計(jì)算Cj 2 1 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 15 245 0 5 1 0 0 - 6 2 0 1 0 4 1 1 0 0 1 5 2 1 0 0 0以6為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x1為換入變量，x4為換出變量Cj 2 1 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 2 X1 0 X5 15 4 1 0 5 1 0 0 3 1 1/3 0 1/6 0 12 0

24、 2/3 0 -1/6 1 3/2 0 1/3 0 -1/3 0以2/3為主元素進(jìn)行運(yùn)算，x2為換入變量， x5為換出變量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 2 X1 3 X2 7.5 3.5 1.5 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 此時(shí)達(dá)到最優(yōu)解。X*=(3.5,1.5), MaxZ=8.5。用單純形法求解線性規(guī)劃問題的具體步驟如下： 找出初始可行基，確定初始基可行解，建立初始單純形表；轉(zhuǎn)。 檢驗(yàn)對應(yīng)于非基變量的檢驗(yàn)數(shù)j。若j0（xj為非基變量）都成立，則

25、已得最優(yōu)解，停止計(jì)算；否則轉(zhuǎn)。 在所有j0中，若有一個(gè)k對應(yīng)的xk的系數(shù)aik0 (i=1,2,m)，則此問題為無界解（無解），停止計(jì)算；否則轉(zhuǎn)。 根據(jù) max（j0）=k 確定xk為換入變量；根據(jù)規(guī)則minbi/aik1im, aik0bl/alk確定相應(yīng)的換出變量，并得到主元素alk。轉(zhuǎn)。 以alk為樞軸元素進(jìn)行轉(zhuǎn)軸運(yùn)算，得到新的單純形表。轉(zhuǎn). 用單純形法求解線性規(guī)劃問題后，應(yīng)回答下面幾個(gè)問題： 是否解無界？上面的步驟已作出回答。 是否無可行解？求解后，若人工變量都取0，則有可行解；否則，無可行解。 唯一最優(yōu)解還是無窮多最優(yōu)解？在最后的單純形表中，若所有非基變量的檢驗(yàn)數(shù)都嚴(yán)格小于0，則為唯

26、一最優(yōu)解；若存在某個(gè)非基變量的檢驗(yàn)數(shù)等于0，則有無窮多最優(yōu)解。第5節(jié) 單純形法的進(jìn)一步討論一、人工變量法1) 人工變量的識別2) 目標(biāo)函數(shù)的處理3) 計(jì)算(單純形法)（大M法，其中M為任意大的正數(shù))加入松弛變量x4;剩余變量x5;人工變量x6,x7Cj-31100MMCBXBbx1x2x3x4x5x6x70 x4111-21100011Mx63-4120-1103/2Mx71-20100011-3+6M1-M1-3M0M000 x4103-20100-1-Mx610100-11-211x31-2010001-11-M00M03M-1注意：本例是求最小值，所以用所有 來判別目標(biāo)函數(shù)是否實(shí)現(xiàn)了最小

27、化。因而換入變量xk的選取標(biāo)準(zhǔn)為結(jié)果得: X*=(4,1,9,0,0,0,0) Z*=-2Cj-31100MMCBXBbx1x2x3x4x5x6x70 x4123001-22-541x210100-11-2-1x31-2010001-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3M-2/3（接上表） 兩階段法(將LP問題分成兩個(gè)階段來考慮) 第I 階段: 不考慮原問題是否存在可行解，給原LP問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求最小化；然后用單純型法求解，若得w=0

28、，則進(jìn)行第二階段計(jì)算，否則無可行解。 第II 階段：將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問題的系數(shù)，作為第二階段的初始表。加入松弛變量x4;剩余變量x5;人工變量x6,x7用單純形法求解第一階段的結(jié)果得：Cj0000011CBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-201000116-1-301000 x4103-20100-1-1x610100-11-210 x31-2010001-0-1001030 x4123001-22-540 x210100-11-2-0 x31-2010000-0000011

29、此時(shí)，達(dá)到第一階段的最優(yōu)解，W=0Cj-31100CBXBbx1x2x3x4x50 x4123001-241x210100-1-1x31-20100-10001-3x141001/3-2/31x210100-11x390012/3-4/30001/31/3由于人工變量x6 =x7=0,所以（0,1,1,12,0）T是該線性規(guī)劃問題的基可行解。于是轉(zhuǎn)入第二階段運(yùn)算：此時(shí)達(dá)到該LP問題的最優(yōu)解：x1=4,x2=1,x3=9; 目標(biāo)函數(shù)值Z=-2。二、單純形法中存在的問題1.存在兩個(gè)以上的最大正檢驗(yàn)數(shù)。選擇任何變量（對應(yīng)最大正檢驗(yàn)數(shù)）作為進(jìn)基變量。2.最小比值相同。LP問題出現(xiàn)退化現(xiàn)象，即基變量取值

30、為0 Cj 3/4 -20 1/2 -6 0 0 0 CBXBbX1X2X3X4X5X6X70X501/4-8-191000X601/2-12-1/230100X71001000103/4-201/2-6000Cj 3/4 -20 1/2 -6 0 0 0 CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-300選取x1為換入變量；按Bland算法，選取下標(biāo)最小的x5為換出變量，得下表：此時(shí)換出變量為x1，換入變量為x4，迭代后目標(biāo)函數(shù)值不變，繼而出現(xiàn)了循環(huán)現(xiàn)象，達(dá)不到最優(yōu)解。解決退化的方法有：“攝動(dòng)法

31、”、“辭典序法”、 Bland規(guī)則等1974年Bland提出Bland算法規(guī)則：3. 最小比值原則失效Cj2300CBXBbX1X2X3X40X36-20113X24-3101Cj-Zj-121100-3經(jīng)過一次迭代后可得右表4. 在最優(yōu)表中出現(xiàn)某非基變量檢驗(yàn)數(shù)為0CBXBbX1X2X3X4X50X340012/3-1/34X260101/203X14100-2/31/3Cj-Zj-360000-10X46003/21-1/24X2301-3/401/43X1810100Cj-Zj-360000-1Cj-Zj034000第五節(jié) 應(yīng)用舉例例1 某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格

32、的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求、單價(jià)和原材料的供應(yīng)量、單價(jià)。該廠應(yīng)如何安排生產(chǎn)使利潤最大？產(chǎn)品名稱規(guī)格要求單價(jià)(元/kg）A原材料C不少于50%原材料P不超過25%50B原材料C不少于25%原材料P不超過50%35D不限25原材料名稱每天最多供應(yīng)量(kg)單價(jià)(元/kg)C10065P10025H6035用單純型法計(jì)算得結(jié)果:每天生產(chǎn)A產(chǎn)品200kg,分別需要原料:C為100kg;P為50kg;H為50kg. 總利潤收入Z=500元/天.先考慮一月份的線性規(guī)劃模型:例2 （書P41 例12）以一月份內(nèi)各種設(shè)備的生產(chǎn)能力總和為分母,生產(chǎn)產(chǎn)品所需要的各類設(shè)備的總臺時(shí)數(shù)為分子,可計(jì)算出一月份的

33、平均設(shè)備利用系數(shù)Z,將Z作為目標(biāo)函數(shù),可得下面的模型: 考慮二月份線性規(guī)劃模型時(shí):(1)從全年計(jì)劃中減去一月份已生產(chǎn)的數(shù)量;(2)對批量小的產(chǎn)品,如一月份已經(jīng)安排較大產(chǎn)量的,二月份將剩余部分安排生產(chǎn);(3)保證第4號產(chǎn)品在月底前交貨.這樣,我們可以依次對12個(gè)月列出線性規(guī)劃模型并求解,再根據(jù)具體情況對計(jì)算結(jié)果進(jìn)行必要調(diào)整.例3 某部門在今后5年內(nèi)連續(xù)給以下項(xiàng)目投資： 項(xiàng)目A，第一年至第四年每年年初投資，次年末回收本利 115%； 項(xiàng)目B，第三年初投資，第五年末回收本利 125%，最大投資額不超過4萬元； 項(xiàng)目C，第二年初投資，第五年末回收本利 140%，最大投資額不超過3萬元； 項(xiàng)目D，五年內(nèi)

34、每年初可購買公債，當(dāng)年末歸還，并加利息6% 。 該部門現(xiàn)有資金 10萬元，問該如何確定投資方案，使第五年末擁有的資金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D班次時(shí)間所需人數(shù)16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030例4 某公交線路每天各時(shí)段內(nèi)所需司乘 人員數(shù)如下： 設(shè)所有的司乘人員分別在各時(shí)段的開始上班，并連續(xù)工作8小時(shí)，問該公交線路至少需配備多少司乘人員。列出該問題的線性規(guī)劃模型。單純形法例1，生產(chǎn)配比問題 某長擬生產(chǎn)甲、乙兩種適銷

35、產(chǎn)品，每件利潤分別為3，5百元。甲、乙產(chǎn)品的部件各自在A、B兩個(gè)車間分別生產(chǎn)，每件甲、乙產(chǎn)品的部件分別需要A、B車間的生產(chǎn)能力1，2工時(shí)；兩種產(chǎn)品的部件最后都要在C車間裝配，裝配每件甲、乙產(chǎn)品分別需要3，4工時(shí)。A、B、C三個(gè)車間每天可用于生產(chǎn)這兩種產(chǎn)品的工時(shí)分別為8，12，36，應(yīng)如何安排生產(chǎn)這兩種產(chǎn)品才能獲利最多？下面用單純形法來計(jì)算（第0次迭代） cj35000比值基解x1x2x3x4x50 x38101000 x412001012/2=6(min)0 x5363400136/4=9檢驗(yàn)行035000表1（第1次迭代） cj35000比值基解x1x2x3x4x50 x381010085x

36、260101/200 x51200-214（min)檢驗(yàn)行30300-5/20表2（第2次迭代） cj35000比值基解x1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3檢驗(yàn)行42000-1/2-1表3解 先看有多少種裁料方案，再進(jìn)行組合和選擇。方案：例1 合理利用線材問題 現(xiàn)要做一百套鋼管,每套要長為2.9m、2.1m和1.5m的鋼管各一根。已知原料長7.4m，問應(yīng)如何下料，使用的原料最省。 設(shè)用方案,分別裁原料鋼管x1,x2, ,x8根, 則：Min z= x1+ x2+ x3+x4+ x5+x6+x7+x8 2x1+ x2+x3 + x4

37、 100 2x2+x3+ 3x5 +2x6+ x7 100 x1+ x3 +3x4 +2x6+3x7+4x8 100 x1, x2, x3, x4, x5 ,x6, x7, x8 0 例2 某工廠要用三種原材料C,P,H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A,B,D。已知產(chǎn)品的規(guī)格要求、單價(jià)和原料的供應(yīng)量、單價(jià)如下表。該廠應(yīng)如何安排生產(chǎn)，能使利潤最大？根據(jù)產(chǎn)品要求有： AC0.5A, AP0.25A BC0.25B, BP0.5B AC+AP+AH=A BC+BP+BH=B根據(jù)原料供應(yīng)量有： AC+BC+DC100 AP+BP+DP100 AH+BH+DH60設(shè)AC,AP,DH分別為x1,x2,x9，

38、有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+ x2+ x3) x2 0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x4+ x5+ x6) x1+ x4+ x7100 x2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9解：記產(chǎn)品A,B,D中C,P,H的含量分別為AC,AP,AH,BC,BP,BH,DC,DP,DH。例3 成批生產(chǎn)企業(yè)年度生產(chǎn)計(jì)劃

39、的按月分配。 在年度計(jì)劃按月分配時(shí)一般要考慮：從數(shù)量和品種上保證年度計(jì)劃的完成；成批的產(chǎn)品盡可能集中在幾個(gè)月內(nèi)生產(chǎn)；由于技術(shù)方面的原因，某些產(chǎn)品在某個(gè)月后才能生產(chǎn)；某些產(chǎn)品要求年初交貨；批量小的產(chǎn)品盡量集中在一個(gè)或幾個(gè)月內(nèi)生產(chǎn)出來，以便減少各月內(nèi)的品種數(shù)量?？紤]以上條件，使設(shè)備負(fù)荷均衡并使利用率最大化。 假定工廠有m類設(shè)備，用i表示(i=1,2,m)；生產(chǎn)n種產(chǎn)品，用j表示(j=1,2,n)。各產(chǎn)品的全年計(jì)劃量用dj表示。 用aij表示加工單位j種產(chǎn)品所需要的第i類設(shè)備的臺時(shí)數(shù)，bik表示k月份第i類設(shè)備的生產(chǎn)能力(臺時(shí))(k=1,2,12)。 再假定第5、8兩種產(chǎn)品下半年投產(chǎn)，第4號產(chǎn)品要求

40、二月底前完成全年計(jì)劃。 如要對全年12個(gè)月同時(shí)考慮，會使模型非常復(fù)雜，我們根據(jù)上述條件從1月到12月份，一個(gè)月一個(gè)月地分別建模計(jì)算。設(shè)k月份計(jì)劃生產(chǎn)j種產(chǎn)品的數(shù)量為xjk。一月份模型為： m n mMax z=( aijxj1) (bi1) i=1 j=1 i=1 n aijxj1bi1 (i=1,2,m) j=1xj1dj (j=1,2,n)x51=x81=0 xj10 (j=1,2,n)二月份模型為： m n mMax z=( aijxj2) (bi2) i=1 j=1 i=1 n aijxj2bi2 (i=1,2,m) j=1xj2dj-xj1 (j=1,2,n)x52=x82=0 xj

41、20 (j=1,2,n)例4 連續(xù)投資問題。某單位有資金10萬元，在今后5年內(nèi)可考慮下列投資項(xiàng)目，已知： 項(xiàng)目A：從第1到第4年每年初可投資，并于次年末回收本利115%； 項(xiàng)目B：第3年初需要投資，到第5年末回收本利125%，但最大投資額不超過4萬元； 項(xiàng)目C：第2年初需要投資，到第5年末能回收本利140%，但最大投資額不超過3萬元； 項(xiàng)目D：5年內(nèi)每年初可購買公債，當(dāng)年末回收本利106%。 問它應(yīng)該如何安排每年的投資，使到5年末擁有的資金最多？ x2A+x2C+x2D=1.06x1D解：每年的投資額應(yīng)不超過手中的資金。由于項(xiàng)目D每年都可投資，且當(dāng)年末就可收回。所以該單位每年必然把資金全部投出

42、去，即投資額等于手中的資金數(shù)。設(shè)第i年投資各項(xiàng)目的資金為xiA,xib,xiC,xiD 。數(shù)學(xué)模型為：Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0本章知識要點(diǎn)1.線性規(guī)劃及數(shù)學(xué)模型；2.線性規(guī)劃的標(biāo)準(zhǔn)型及如何化為標(biāo)準(zhǔn)型；3.線性規(guī)劃問題的解 可行解、最優(yōu)解、基、基向量與非基向量、基變量與非基變量、基解、基可行解、基最優(yōu)解、最優(yōu)基。4.解的幾何意義若線性規(guī)劃問題存在可行域，則是一個(gè)凸集;凸集的每個(gè)頂點(diǎn)對應(yīng)于一個(gè)基可行解;若線性規(guī)劃有有限最優(yōu)解,必在可行域某頂點(diǎn)上達(dá)到.本章知識要點(diǎn)5.線性規(guī)劃的求解方法（1）圖解法（含2個(gè)決策變量）；（2）單純形法。6.單純形法進(jìn)一步討論（1）人工變量法（大M法）；（2）兩階段法。7.最優(yōu)性檢驗(yàn)與解的判別（以極大化為例）（1）唯一最優(yōu)解；（2）無窮多最優(yōu)解；（3）無界解；（4）