根據(jù)圖解法求解線性規(guī)劃問題的結(jié)果知,一個(gè)線性規(guī)劃問題的解可能有四種情況:唯一、無窮、無界和無解。那么利用單純形計(jì)算時(shí),如何判斷一個(gè)線性規(guī)劃問題的解可能是哪一種情況呢?這里給出四個(gè)判定定理(以標(biāo)準(zhǔn)型線性規(guī)劃為例...[繼續(xù)閱讀]

    (1)對于檢驗(yàn)數(shù)的最優(yōu)判別,若目標(biāo)是max,則要求所有非基變量的檢驗(yàn)數(shù)≤0;若目標(biāo)是min,則要求所有非基變量的檢驗(yàn)數(shù)≥0。(2)根據(jù)最大正檢驗(yàn)數(shù)來確定進(jìn)基變量,有時(shí)并非是最佳的選擇,這里實(shí)際上需要考慮從初始基可行解出發(fā)沿哪個(gè)方向...[繼續(xù)閱讀]

    對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題(問題A):maxZ=c1x1+c2x2+…+cnxn若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基,則引入所謂的人工變量xn+1,…,xn+m,構(gòu)造如下形式的線性規(guī)劃問題(問題B):maxZ=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m問題B中M為任意大的正...[繼續(xù)閱讀]

    兩階段法是把一般線性規(guī)劃問題的求解過程分為兩個(gè)階段。即:第一階段:在原線性規(guī)劃問題中引入人工變量,并構(gòu)造僅含有人工變量的目標(biāo)函數(shù),使其目標(biāo)函數(shù)最小化,用單純形法求解,以去掉人工變量。若第一階段求得最優(yōu)解對應(yīng)的最...[繼續(xù)閱讀]

    本章主要介紹了求解線性規(guī)劃問題的兩種方法:單純形法和人工變量法。單純形法是求解線性規(guī)劃的經(jīng)典方法,其基本思路是先找出一個(gè)初始的基可行解,判斷其是否為最優(yōu)解;如果不是,則轉(zhuǎn)換到另一個(gè)基可行解,并使目標(biāo)函數(shù)的值逐步...[繼續(xù)閱讀]

    一、判斷題1.單純形法是求解線性規(guī)劃模型的唯一方法。()2.用單純形法求解線性規(guī)劃問題,必須要有單位陣作為初始可行基。()3.單純形法的迭代計(jì)算是從一個(gè)可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一個(gè)可行解。()4.基本可行解的個(gè)數(shù)不會...[繼續(xù)閱讀]

    【例4-1】在第二章的【例2-1】中,討論了某工廠資源的合理利用問題,建立了線性規(guī)劃模型:maxZ=3x1+5x2已知最優(yōu)解為:x*1＝4,x*2＝5,z*＝37?，F(xiàn)在從另一個(gè)角度考慮這個(gè)問題。假定該廠的決策者考慮自己不生產(chǎn)甲、乙兩種產(chǎn)品,而把原擬用于...[繼續(xù)閱讀]

    以上從兩個(gè)資源利用問題,引出了對資源的估價(jià)問題,得到了對偶規(guī)劃。原問題與其對偶問題之間通常有三種不同的關(guān)系形式,以下將原問題記作(P)問題,對偶問題記作(D)問題。1.對稱型對偶問題定義4.1:設(shè)原LP問題為:maxZ=c1x1+c2x2+…+cnxnx...[繼續(xù)閱讀]

    這一節(jié)給出對偶問題的一些性質(zhì),為敘述方便,僅在對稱形式下進(jìn)行分析。maxZ=cxminw=yb定理4.1(對稱性定理)對偶問題的對偶是原問題。證明:先將(D)問題化成原問題形式maxw′=(-bT)yT由定義4.1,設(shè)xT為它的對偶變量,寫出它的對偶問題。這就是...[繼續(xù)閱讀]

    考慮一對對稱的對偶問題。從上節(jié)對偶問題的基本性質(zhì)可知,當(dāng)(P)問題求得最優(yōu)解x*時(shí),其(D)問題也得到最優(yōu)解y*,且有:bi代表第i種資源的擁有量;對偶變量y*i的意義代表在資源最優(yōu)利用條件下對單位第i種資源的估價(jià)。這種估價(jià)不是資源...[繼續(xù)閱讀]