線性規(guī)劃問(wèn)題的解

線性規(guī)劃問(wèn)題的解第1頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月最優(yōu)解：若基本可行解又是最優(yōu)解（也稱基本最優(yōu)解），這個(gè)基就稱為最優(yōu)基（optimalbasis）。基本解：對(duì)于基,令非基變量為零,求得滿足（1-13）的解，稱為基對(duì)應(yīng)的基本解（basicsolution）。基本可行解：滿足（1-14）的基本解稱為基本可行解（basicfeasiblesolution）；基本可行解所對(duì)應(yīng)的基稱為可行基（feasiblebasis）。第2頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

二.解的性質(zhì)

在右圖中設(shè)線段長(zhǎng)度與之比為，由此得

o第3頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月第4頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃問(wèn)題的幾個(gè)定理定理1-4線性規(guī)劃問(wèn)題有可行解,必有基本可行解；有最優(yōu)解,必有基本最優(yōu)解。定理1-1線性規(guī)劃問(wèn)題的可行域是凸集。定理1-2A為線性規(guī)劃問(wèn)題可行域的極點(diǎn)的充要條件是的A正分量對(duì)應(yīng)的系數(shù)列向量線性無(wú)關(guān)。（證明從略）。

定理1-3A是可行域的極點(diǎn)的充要條件是它為基本可行解。（證明從略。）第5頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月綜上所述,我們?cè)诶碚撋系玫搅司€性規(guī)劃問(wèn)題的以下結(jié)論：線性規(guī)劃問(wèn)題的可行域是一凸集（包括有界凸集和無(wú)界凸集）；線性規(guī)劃問(wèn)題的每個(gè)基本可行解對(duì)應(yīng)著可行域的一個(gè)極點(diǎn)（頂點(diǎn)）；若線性規(guī)劃問(wèn)題有最優(yōu)解,必在可行域的某一極點(diǎn)上得到。由此可見,我們只需在基本可行解中尋求最優(yōu)解。如何有效地尋求最優(yōu)解,這就是下節(jié)要介紹的單純形法。

第6頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月§1-5單純形法一、單純形法的基本思路如果線性規(guī)劃問(wèn)題存在最優(yōu)解，一定有一個(gè)基本可行解是最優(yōu)解。因此單純形法迭代的基本思路是：先找出一個(gè)基本可行解，判斷其是否為最優(yōu)解，如為否，則轉(zhuǎn)換到相鄰的基本可行解，并使目標(biāo)函數(shù)值不斷增大，一直找到最優(yōu)解為止。

第7頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月1、確定初始基可行解

max(1-17)

在約束條件（1-18）式的變量的系數(shù)矩陣中總會(huì)存在一個(gè)單位矩陣，不妨設(shè)為

(1-20)第8頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月式中稱為基向量,同其對(duì)應(yīng)的決策變量稱為基變量,模型中的其它變量稱為非基變量。在(1-18)式中令所有非基變量等于零,即可找到一個(gè)解

X=(，)T=(b1,…,bm,0,…,0)T因有b≥0,故X滿足約束(1-19),是一個(gè)基本可行解記為又稱初始基本可行解。2、從一個(gè)基本可行解轉(zhuǎn)換為相鄰的基本可行解設(shè)初始基本可行解中的前m個(gè)為基變量,即第9頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月經(jīng)一系列變換得第10頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月3、最優(yōu)性檢驗(yàn)和解的判別第11頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月（1-24）式中因,所以只要,就有。通常簡(jiǎn)寫為或,它是對(duì)線性規(guī)劃問(wèn)題的解進(jìn)行最優(yōu)性檢驗(yàn)的標(biāo)志第12頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月第13頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月二、單純形法的矩陣描述在線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型：Max

第14頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月中，不妨設(shè)是一個(gè)可行基，則系數(shù)矩陣Ａ可分塊為（Ｂ，Ｎ）。對(duì)應(yīng)于Ｂ的基變量為，，非基變量為，Ｎ＝。并令，其中為基變量的系數(shù)列向量，N為非基變量的系數(shù)列向量。于是原問(wèn)題可化為第15頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月即對(duì)約束方程兩邊同左乘以，得 =，并代入目標(biāo)函數(shù)，得第16頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月令非基變量=0得=,從而相應(yīng)的基本可行解為目標(biāo)函數(shù)取值為又由于,故有第17頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月將及Z的表達(dá)式又可寫成令，，則又有+=+第18頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月第四步：重復(fù)第二、三兩步，一直到計(jì)算結(jié)束為止。

三、單純形法的計(jì)算步驟根據(jù)上節(jié)中講述的原理,單純形法的計(jì)算步驟如下：第一步：求初始基本可行解,列出初始單純形表。第二步：最優(yōu)性檢驗(yàn)。第三步：從一個(gè)基本可行解轉(zhuǎn)換到相鄰的目標(biāo)函數(shù)值更大的基本可行解，列出新的單純形表。

第19頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月一、大M法

在上一節(jié)例1-9中，化為標(biāo)準(zhǔn)形式后約束條件的系數(shù)矩陣中含有單位矩陣，以此作初始基，使求初始基可行解和建立初始單純形表都十分方便。但時(shí)?；癁闃?biāo)準(zhǔn)形后的約束條件的系數(shù)矩陣中不存在單位矩例1-10用單純形法求解線性規(guī)劃問(wèn)題

§1-6.初始可行基的求法

第20頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月解先將其化成標(biāo)準(zhǔn)形有MaxMax第21頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月 這種情況下，可以通過(guò)添加兩列單位向量，使連同約束條件中的向量構(gòu)成單位矩陣。

是人為添加上去的，它相當(dāng)于在上述問(wèn)題的約束條件（1-34）中添加變量，約束條件(1-35)中添加變量，變量相應(yīng)稱為人工變量。由于約束條件（1-34）（1-35）在添加人工變量前已是等式為使這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零。為此，令目標(biāo)函數(shù)中人工變量的系數(shù)為任意大的負(fù)值，用“-M”代表。7p第22頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月“-M”稱為“罰因子”，即只要人工變量取值大于零，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最優(yōu)。因而添加人工變量后，例1-10的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式就變?yōu)閙ax 該模型中與對(duì)應(yīng)的變量為基變量，令非基變量等于零，即得到初始基可行解,并列出初始單純形表。在單純形法迭代運(yùn)算中，M可當(dāng)作一個(gè)數(shù)學(xué)符號(hào)一起參加運(yùn)算。檢驗(yàn)數(shù)中含M符號(hào)的項(xiàng)，當(dāng)M的系數(shù)為正時(shí)，該檢驗(yàn)數(shù)為正，當(dāng)M的系數(shù)為負(fù)時(shí)，該項(xiàng)檢驗(yàn)數(shù)為負(fù)。第23頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月

例1-10添加人工變量后，用單純形法求解的過(guò)程見下頁(yè)表1-8。最優(yōu)解為：

二、

兩階段法 用大M法處理人工變量，在用手工計(jì)算求解時(shí)不會(huì)碰到麻煩。但用電子計(jì)算機(jī)求解時(shí)，對(duì)M就只能在計(jì)算機(jī)內(nèi)輸入一個(gè)機(jī)器最大字長(zhǎng)的數(shù)字。如果線性規(guī)劃問(wèn)題中的或等參數(shù)值與這個(gè)代表M的數(shù)相對(duì)比較接近，或遠(yuǎn)遠(yuǎn)小于這個(gè)數(shù)字，由于計(jì)算機(jī)計(jì)算時(shí)取值上的誤差，有可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。為了克服這個(gè)困難，可以對(duì)添加人工變量后的線性規(guī)劃問(wèn)題分兩個(gè)階段來(lái)計(jì)算，稱為兩階段法。第24頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月表1-8-30100-M-M0-M-M4191111000001[1]1-1-11-200003-3-2M4M10-M004130211-10313-21-10-1106[6]0403-3100-M-3+6M04M+103M-4M01-1/21第25頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月入基出基原則首先是檢驗(yàn)數(shù)即單純形表中系數(shù)矩陣的第列的價(jià)值系數(shù)減去第列元素乘以對(duì)應(yīng)行所在的基的價(jià)值系數(shù)的和的差。當(dāng)目標(biāo)函數(shù)是求max時(shí)，大者對(duì)應(yīng)的列所在的變量為入基變量，如果有幾個(gè)檢驗(yàn)數(shù)一樣大，且是最大者，取腳標(biāo)小的變量為入基變量；當(dāng)目標(biāo)函數(shù)是求min時(shí)，小者為入基變量。由于第26頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月續(xù)表

-3110[2/3]01/2-1/21/63/203011/30001/39000001-1/21/2-1/2-00303/2-M-3/2-M+1/213/23/20103/4-3/41/4000001-1/21/2-1/205/2-1/2100-1/41/41/4-9/2000-3/4-M+3/4-M-1/4第27頁(yè)，課件共28頁(yè)，創(chuàng)作于2023年2月兩階段法的第一階段是先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)（一般取1），夠成新的目標(biāo)函數(shù)，在保持原問(wèn)題約束條件不變的情況下求這個(gè)目