運(yùn)籌學(xué)線性規(guī)劃的標(biāo)準(zhǔn)形式

關(guān)于運(yùn)籌學(xué)線性規(guī)劃的標(biāo)準(zhǔn)形式數(shù)學(xué)模型如下第2頁,共32頁，2024年2月25日，星期天改造方法（1）１、若目標(biāo)函數(shù)求最小值，則在函數(shù)式前加上“－”號(hào)，轉(zhuǎn)化為求最大值。轉(zhuǎn)化后目標(biāo)函數(shù)的最優(yōu)解不變，最優(yōu)值差一個(gè)符號(hào)。例：第3頁,共32頁，2024年2月25日，星期天改造方法（2）2、若約束條件中，某些常數(shù)項(xiàng)bi為負(fù)數(shù)，則可先在約束條件等式或不等式兩邊乘上“-1”，使得bi≥0。例：第4頁,共32頁，2024年2月25日，星期天改造方法（3）3、若約束條件不等式符號(hào)為“≤”，則在不等式左邊加上一個(gè)非負(fù)變量（稱為松弛變量），把不等式改為等式。例：新設(shè)一個(gè)非負(fù)變量第5頁,共32頁，2024年2月25日，星期天改造方法（4）4、若約束條件不等式符號(hào)為“≥”，則在不等式左邊減去一個(gè)非負(fù)變量（稱為剩余變量），不等式改為等式。例：新設(shè)一個(gè)非負(fù)變量第6頁,共32頁，2024年2月25日，星期天改造方法（5）5、若約束條件中，某些決策變量沒有非負(fù)要求：①xj≤0，則令新變量xj’=-xj；②xj無符號(hào)限制，則可增設(shè)兩個(gè)非負(fù)變量Vk≥0,Uk≥0，令原變量Xk=Vk-Uk，代入原線性規(guī)劃問題的目標(biāo)函數(shù)及約束條件。第7頁,共32頁，2024年2月25日，星期天例1第8頁,共32頁，2024年2月25日，星期天步驟1：minmax第9頁,共32頁，2024年2月25日，星期天步驟2：bi<0bi>0第10頁,共32頁，2024年2月25日，星期天步驟3：“≤”

“=“引入新變量(松弛變量）x5≥0，將約束條件不等式變?yōu)榈仁健?松弛變量第11頁,共32頁，2024年2月25日，星期天步驟4：“≥”

“=”引入新變量（剩余變量）x6≥0，將約束條件不等式變?yōu)榈仁??！?/p>

剩余變量第12頁,共32頁，2024年2月25日，星期天步驟5：滿足變量非負(fù)條件設(shè)新變量x7≥0，令x7=-x2，帶入目標(biāo)函數(shù)和約束條件中。設(shè)兩個(gè)新變量x8≥0，x9≥0，令x4=x8-x9，帶入目標(biāo)函數(shù)和約束條件中。

整理得：第13頁,共32頁，2024年2月25日，星期天整理后數(shù)學(xué)模型為：第14頁,共32頁，2024年2月25日，星期天松弛變量與剩余變量概念：松弛變量：在線性規(guī)劃模型中，如果約束條件為“≤”，則在不等式左邊加入一個(gè)非負(fù)變量，這個(gè)非負(fù)變量成為松弛變量。剩余變量：在線性規(guī)劃模型中，如果約束條件為“≥”，則在不等式左邊減去一個(gè)非負(fù)變量，這個(gè)非負(fù)變量成為剩余變量。第15頁,共32頁，2024年2月25日，星期天理解松弛變量的實(shí)際含義例：某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種產(chǎn)品的生產(chǎn)。生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制如下表：工廠每生產(chǎn)一單位甲產(chǎn)品可獲利50元，每生產(chǎn)一單位乙產(chǎn)品可獲利100元，問工廠應(yīng)分別生產(chǎn)多少單位產(chǎn)品甲和產(chǎn)品乙才能使得獲利最多？甲產(chǎn)品乙產(chǎn)品資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg第16頁,共32頁，2024年2月25日，星期天建立數(shù)學(xué)模型：設(shè)甲、乙兩種產(chǎn)品的產(chǎn)量分別為x1、x2：第17頁,共32頁，2024年2月25日，星期天DBC圖解法100200300400100200300400OA可行解域?yàn)镺ABCD最優(yōu)解為B點(diǎn)（50，250）第18頁,共32頁，2024年2月25日，星期天最優(yōu)解的解釋最優(yōu)解x1=50，x2=250表示甲產(chǎn)品生產(chǎn)50個(gè)單位，乙產(chǎn)品生產(chǎn)250個(gè)單位時(shí)，獲利最大。此時(shí)，資源利用情況為（代入約束條件）：設(shè)備臺(tái)時(shí)利用量=1*50+1*250=300=資源限制量原料A使用量=2*50+1*250=350<資源限制量400原料B使用量=1*250=250=資源限制量第19頁,共32頁，2024年2月25日，星期天引入松弛變量x3,x4,x5，將數(shù)學(xué)模型標(biāo)準(zhǔn)化：∵最優(yōu)解為x1=50,x2=250,∴代入標(biāo)準(zhǔn)化的數(shù)學(xué)模型，得松弛變量x3=0,x4=50,x5=0。第20頁,共32頁，2024年2月25日，星期天松弛變量的含義松弛變量x3=0，表示按最優(yōu)生產(chǎn)方案生產(chǎn)時(shí)，設(shè)備已充分利用，無多余的設(shè)備臺(tái)時(shí)。松弛變量x4=50，表示按最優(yōu)生產(chǎn)方案生產(chǎn)時(shí)，原料A未用完，還有50個(gè)單位。松弛變量x5=0，表示按最優(yōu)生產(chǎn)方案生產(chǎn)時(shí)，原料B已用完。所以，松弛變量不等于零，表示某種資源較充裕。第21頁,共32頁，2024年2月25日，星期天理解剩余變量的含義例：某公司由于生產(chǎn)的需要，共需要A、B兩種原料至少350噸（A、B兩種原料有一定的替代性），其中原料A至少購進(jìn)125噸。但由于A、B兩種原料的規(guī)格不同，各自所需的加工時(shí)間也是不同的，加工每噸原料A需要2小時(shí)，加工每噸原料B需要1小時(shí)，而公司總共有600個(gè)加工時(shí)數(shù)，又知道每噸原料A的價(jià)格為2萬元，每噸原料B的價(jià)格為3萬元，試問在滿足生產(chǎn)需要的前提下，在公司加工能力的范圍內(nèi)，如何購買A、B兩種原料，使得購進(jìn)成本最低？第22頁,共32頁，2024年2月25日，星期天建立數(shù)學(xué)模型：設(shè)x1，x2分別為原料A、B的購進(jìn)量：第23頁,共32頁，2024年2月25日，星期天將數(shù)學(xué)模型標(biāo)準(zhǔn)化引入剩余變量x3，x4，及松弛變量x5：第24頁,共32頁，2024年2月25日，星期天圖解法100200300400500600100200300400500BAC可行解域?yàn)锳BC最優(yōu)解為C點(diǎn)（250，100）第25頁,共32頁，2024年2月25日，星期天最優(yōu)解的解釋最優(yōu)解x1=250，x2=100表示最佳購買方案是原料A購進(jìn)250噸，原料B購進(jìn)100噸。代入約束條件分析：總購進(jìn)量=250+100=350噸=最低要求原料A購進(jìn)量=250>最低要求125原料加工時(shí)數(shù)=2*250+100=600=最高限制進(jìn)一步計(jì)算剩余變量和松弛變量:X3=0，表示正好達(dá)到最低要求；X4=125，表示超出最低要求，多購進(jìn)125噸；X5=0，表示工時(shí)數(shù)被全部利用。第26頁,共32頁，2024年2月25日，星期天關(guān)于松弛變量和剩余變量的信息也可以從圖解法中獲得。另外，第27頁,共32頁，2024年2月25日，星期天DBC松弛變量x3=0,x4=50,x5=0100200300400100200300400OA可行解域?yàn)镺ABCD最優(yōu)解為B點(diǎn)（50，250）132第28頁,共32頁，2024年2月25日，星期天松弛變量x3=0,x4=50,x5=0最優(yōu)解在B點(diǎn)。B點(diǎn)是第1、第3個(gè)約束條件對應(yīng)的直線的交點(diǎn)，所以第1、第3個(gè)約束條件加入的松弛變量為0，而第2個(gè)約束條件加入的松弛變量不為0（與B點(diǎn)還有一點(diǎn)距離）。第29頁,共32頁，2024年2月25日，星期天剩余變量X3=0,X4=125，松弛變X5=0100200300400500600100200300400500BAC可行解域?yàn)锳BC最優(yōu)解為C點(diǎn)（250，100）123第30頁,共32頁，2024年2月25日，星期天剩余變量X3=0,X4=125，