線性規(guī)劃01可行區(qū)域與基本可行解

線性規(guī)劃

LinearProgrammingLudongUniversity2024/1/17LudongUniversity2線性規(guī)劃線性規(guī)劃問題可行區(qū)域與根本可行解單純形算法初始可行解對(duì)偶理論靈敏度分析計(jì)算軟件案例分析2024/1/17LudongUniversity3線性規(guī)劃問題線性規(guī)劃實(shí)例線性規(guī)劃模型

生產(chǎn)方案問題運(yùn)輸問題一般形式標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式概念形式轉(zhuǎn)換2024/1/17LudongUniversity4生產(chǎn)方案問題某工廠用三種原料生產(chǎn)三種產(chǎn)品，的條件如表2.1.1所示，試制訂總利潤(rùn)最大的生產(chǎn)方案單位產(chǎn)品所需原料數(shù)量（公斤）產(chǎn)品Q1產(chǎn)品Q2產(chǎn)品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000單位產(chǎn)品的利潤(rùn)（千元）3542024/1/17LudongUniversity5問題分析2024/1/17LudongUniversity6模型2024/1/17LudongUniversity7運(yùn)輸問題2024/1/17LudongUniversity8問題分析2024/1/17LudongUniversity9模型2024/1/17LudongUniversity10一般形式目標(biāo)函數(shù)約束條件自由變量非負(fù)變量2024/1/17LudongUniversity11注釋2024/1/17LudongUniversity12標(biāo)準(zhǔn)形式與標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式2024/1/17LudongUniversity13概念2024/1/17LudongUniversity14模型轉(zhuǎn)換約束轉(zhuǎn)換實(shí)例目標(biāo)轉(zhuǎn)換變量轉(zhuǎn)換2024/1/17LudongUniversity15約束轉(zhuǎn)換1不等式變等式不等式變不等式等式變不等式2024/1/17LudongUniversity16約束轉(zhuǎn)換2等式變不等式不等式變等式松弛變量剩余變量或不等式變不等式2024/1/17LudongUniversity17將LP轉(zhuǎn)化為標(biāo)準(zhǔn)形式例2024/1/17LudongUniversity18思考題和練習(xí)題

思考題：習(xí)題2〔P.73〕練習(xí)題：習(xí)題1，3，4〔P.72〕2024/1/17LudongUniversity19可行區(qū)域與根本可行解圖解法

可行域的幾何結(jié)構(gòu)

根本可行解與根本定理2024/1/17LudongUniversity20圖解法2024/1/17LudongUniversity21解線性規(guī)劃2024/1/17LudongUniversity22結(jié)論關(guān)于LP的解可能出現(xiàn)的情況：可行域是空集?？尚杏驘o(wú)界無(wú)最優(yōu)解。最優(yōu)解存在且唯一，那么一定在頂點(diǎn)上到達(dá)。最優(yōu)解存在且不唯一，一定存在頂點(diǎn)是最優(yōu)解。2024/1/17LudongUniversity23可行域的幾何結(jié)構(gòu)凸集可行域的凸性根本假設(shè)2024/1/17LudongUniversity24凸集2024/1/17LudongUniversity25可行域的凸性2024/1/17LudongUniversity26問題1.可行域頂點(diǎn)的個(gè)數(shù)是否有限？2.最優(yōu)解是否一定在可行域頂點(diǎn)上到達(dá)？3.如何找到頂點(diǎn)？4.如何從一個(gè)頂點(diǎn)轉(zhuǎn)移到另一個(gè)頂點(diǎn)?2024/1/17LudongUniversity27根本可行解與根本定理根本可行解的定義根本定理問題

2024/1/17LudongUniversity28根本可行解與根本定理根本可行解的定義根本定理問題令分塊

左乘2024/1/17LudongUniversity29根本可行解的定義如果，稱該基可行解為非退化的，如果一個(gè)線性規(guī)劃的所有基可行解都是非退化的那么稱該規(guī)劃為非退化的。2024/1/17LudongUniversity30根本可行解的定義2024/1/17LudongUniversity31根本定理2024/1/17LudongUniversity32問題根本可行解不一定都是最優(yōu)解，最優(yōu)解也不一定都是根本可行解。如果有兩個(gè)根本可行解是最優(yōu)解，那么兩解的凸組合也都是最優(yōu)解。如果最優(yōu)解不唯一，那么會(huì)有多個(gè)根本可行解是最優(yōu)解，它們必然在同一個(gè)面上。如果可行解個(gè)數(shù)有限，那么可以在基可行解中尋找最優(yōu)解。剩余的問題是如何判斷一個(gè)基可行解是最優(yōu)解？如果不是那么如何從一個(gè)基可行解轉(zhuǎn)到另一個(gè)基可行解？2024/1/17LudongUniversity33思考題和練習(xí)題

思考題：定理和定理一起被稱為線性規(guī)劃的根本定理，試證明定理和定理。練習(xí)題：習(xí)題5(4)，8，9〔P.72〕課堂作業(yè)長(zhǎng)征醫(yī)院在每天各時(shí)段內(nèi)需護(hù)士人數(shù)如下表所示該醫(yī)院安排4個(gè)護(hù)士上班班次：早班6:00-14:00，白班8:00-16:00，晚班14:00-22:00，夜班22:00-6:00〔次日〕，每名護(hù)士值一個(gè)班次?！?〕該醫(yī)院每天至少需多少名護(hù)士才能滿足值班需要?！?〕有人提議為簡(jiǎn)化管理，共設(shè)早晚夜三個(gè)班，取消白班，這種情況下又需要多少名護(hù)士能