【正文】 x3 + x6 + x9 ? 60 x1， 已知產(chǎn)品的規(guī)格要求、產(chǎn)品單價、每天能供應(yīng)的原材料數(shù)量及原材料單價分別見表 12表 129。 清華大學(xué)出版社 例 1－ 13（投資問題） 已知某集團有 1,000,000元的資金可供投資，該集團有五個可供選擇的投資項目，其中各種資料如下： 表 127 投資項目 風(fēng)險 % 紅利 % 增長 % 信用度 1 10 5 10 11 2 6 8 17 8 3 18 7 14 10 4 12 6 22 4 5 4 10 7 10 該集團的目標(biāo)為：每年紅利至少是 80,000元，最低平均增長率 14%，最低平均信用度為 6，該集團應(yīng)如何安排投資，使投資風(fēng)險最小？ 清華大學(xué)出版社 解 :設(shè) xi表示第 i項目的投資額 i =1,2,3,4,5，目標(biāo)是投資風(fēng)險最小化，因此目標(biāo)函數(shù)為： min z = ( + + + + ) 數(shù)學(xué)模型為： min z = + + + + x1 + x2 + x3 + x4+ x5 = 1,000,000 x1 + x2 + x3 + x4+ x5≥ 80,000 + x2 + x3 + x4+ x5≥140,000 (11 x1 + 8 x2 + 10 x3 + 4 x4+10 x5)/5≥6 xi ≥ 0 ( i =1,2,3,4,5) 用單純形法可計算出結(jié)果。盡可能多地掌握一些典型模型不僅有助于深刻理解線性規(guī)劃本身的理論，而且有利于靈活地處理千差萬別的問題，提高解決實際問題的能力。將第一階段的最終計算表 1—23中的人工變量列取消，并將目標(biāo)函數(shù)系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，重新計算檢驗數(shù)行，可得如下第二階段的初始單純形表；應(yīng)用單純形算法求解得最優(yōu)解。因人工變量 x6 = x7 = 0，所以 ( 0, 1, 1 ,12, 0 )T 是原問題的基本可行解。第一階段我們已求得 W 180。 表 1—23 cj 0 0 0 0 0 1 1 θ XB b x1 x2 x3 x4 x5 x6 x7 x4 12 3 0 0 1 2 2 5 x2 1 0 1 0 0 1 1 2 x3 1 2 0 1 0 0 0 1 W39。 表 1—20 6 7 6 71 2 3 41 2 3 5 61 3 717m in m a x2 114 2 321, , 0Z x x W x xx x x xx x x x xx x xxx?? ? ? ? ? ?? ? ? ???? ? ? ? ? ???? ? ? ??? ??cj 0 0 0 0 0 1 1 XB b x1 x2 x3 x4 x5 x6 x7 x4 11 1 2 1 1 0 0 0 x6 3 4 1 2 0 1 1 0 x7 1 2 0 1 0 0 0 1 W39。 各階段的計算方法及步驟與前述單純形法完全相同，下面用例子說明該方法的應(yīng)用。于是只需要將第一階段最終計算表中的目標(biāo)函數(shù)行的數(shù)字換成原問題的目標(biāo)函數(shù)的數(shù)字，就得到了求解原問題的初始計算表，再進行第二階段的求解。 2) 若 (LP)*的最優(yōu)基本可行解 則 (LP) 必不可行。 定理 設(shè)原線性規(guī)劃問題記成 (LP)，由它而引入的新的線性規(guī)劃問題記成 (LP)*。第一階段是先求出基本可行解 (或判斷出原線性規(guī)劃問題無解 )，第二階段利用已求出的初始基本可行解來求最優(yōu)解。 初始單純形表 1—16 cj 3 1 1 0 0 M M θ XB b x1 x2 x3 x4 x5 x6 x7 x4 11 1 2 1 1 0 0 0 11 x6 3 4 1 2 0 1 1 0 x7 1 2 0 [1] 0 0 0 1 1 Z 4M 36M M1 3M1 0 M 0 0 清華大學(xué)出版社 表 1—19 cj 3 1 1 0 0 M M θ XB b x1 x2 x3 x4 x5 x6 x7 x1 4 1 0 0 1/3 2/3 2/3 5/3 x2 1 0 1 0 0 1 1 2 x3 9 0 0 1 2/3 4/3 4/3 7/3 Z 2 0 0 0 1/3 1/3 1/3M 2/3M 在表 1—19中，所有的 ?j ? 0，故得到最優(yōu)解： X* = ( 4, 1, 9, 0, 0, 0, 0 ) 目標(biāo)函數(shù)值 Z′= 2 , 原問題的最優(yōu)目標(biāo)值為 : Z* = 2 。利用表 1—15得初始單純形表，單純形算法得表 1—16 ～表 1—19。 清華大學(xué)出版社 例 111 試用大 M法求解如下線性規(guī)劃問題的最優(yōu)解。這就是大 M法。為此，就必須假定人工變量在目標(biāo)函數(shù)中的價值系數(shù)為 (M)(對于極大化目標(biāo) )， M為充分大的正數(shù)。 清華大學(xué)出版社 二、人工變量法 (大 M法 ) 對于加入人工變量的線性規(guī)劃問題的目標(biāo)函數(shù)如何處理？我們希望人工變量對目標(biāo)函數(shù)取值不受影響。 1 1 1 1 1 12 1 1 2 2 21111( ), , , , , 0n n nn n nm mn n n m mn n n ma x a x x ba x a x x ba x a x x bx x x x?????? ? ? ???? ? ? ?????? ? ? ?????(0) 清華大學(xué)出版社 引入人工變量問題解的判定 ? 若經(jīng)過基的變換，基變量中不再包含有人工變量，表明原問題有基可行解。這時分別給每一個約束條件加入一個人工變量 xn+1, …, xn+m , 得 : 由此可以得到一個 m階單位矩陣。 表 1—6 這時，檢驗數(shù)全部小于等于 0，即目標(biāo)函數(shù)已不可能再增大，于是得到最優(yōu)解： X*=(2,5,0,4,0) 目標(biāo)函數(shù)的最大值為： Z*=19 cj 2 3 0 0 0 θi XB B x1 x2 x3 x4 x5 x2 5 0 1 1/3 0 0 x4 4 0 0 4/3 1 2 x1 2 1 0 1/3 0 1/2 Z 19 0 0 1/3 0 1 T 清華大學(xué)出版社 例 110 ???????????????????????0x 1..x 612x6 4x 2 16 x5 4x 18 4 22112 32212..2312m a xxxxxxxtsxxZcj 2 3 0 0 0 0 θi XB b x1 x2 x3 x4 x5 x6 x3 12 2 2 1 0 0 0 6 x4 8 1 2 0 1 0 0 4 x5 16 4 0 0 0 1 0 x6 12 0 [4] 0 0 0 1 3 Z 0 2 3 0 0 0 0 清華大學(xué)出版社 例10 cj 2 3 0 0 0 0 θi XB b x1 x2 x3 x4 x5 x6 x3 12 2 2 1 0 0 0 6 x4 8 1 2 0 1 0 0 4 x5 16 4 0 0 0 1 0 x6 12 0 [4] 0 0 0 1 3 Z 0 2 3 0 0 0 0 cj 2 3 0 0 0 0 θi XB b x1 x2 x3 x4 x5 x6 x3 6 2 0 1 0 0 1/2 3 x4 2 [1] 0 0 1 0 1/2 2 x5 16 4 0 0 0 1 0 4 x2 3 0 1 0 0 0 1/4 Z 9 2 0 0 0 0 3/4 清華大學(xué)出版社 cj 2 3 0 0 0 0 θi XB b x1 x2 x3 x4 x5 x6 x3 6 2 0 1 0 0 1/2 3 x4 2 [1] 0 0 1 0 1/2 2 x5 16 4 0 0 0 1 0 4 x2 3 0 1 0 0 0 1/4 Z 9 2 0 0 0 0 3/4 cj 2 3 0 0 0 0 θi XB b x1 x2 x3 x4 x5 x6 x3 2 0 0 1 2 0 1/2 4 x1 2 1 0 0 1 0 1/2 x5 8 0 0 0 4 1 [2] 4 x2 3 0 1 0 0 0 1/4 12 Z 13 0 0 0 2 0 1/4 清華大學(xué)出版社 cj 2 3 0 0 0 0 θi XB b x1 x2 x3 x4 x5 x6 x3 2 0 0 1 2 0 1/2 4 x1 2 1 0 0 1 0 1/2 x5 8 0 0 0 4 1 [2] 4 x2 3 0 1 0 0 0 1/4 12 Z 13 0 0 0 2 0 1/4 cj 2 3 0 0 0 0 θi XB b x1 x2 x3 x4 x5 x6 x3 0 0 0 1 1 1/4 0 x1 4 1 0 0 1 1/4 0 x6 4 0 0 0 2 1/2 1 x2 2 0 1 0 1/2 1/8 0 Z 14 0 0 0 3/2 1/8 0 退化 清華大學(xué)出版社 第四節(jié) 單純形算法的進一步討論 一、初始基本可行解的確定 利用單純形算法的一個根本前提是要有一個初始的基本可行解。x5 3x2+x3=15 4x1+x4=12 2x1+2x2＋ x5=14 x1， x2， x3， x4， x5≥0 解： （ 1）由標(biāo)準(zhǔn)型得到初始單純形表： cj 2 3 0 0 0 θi XB b x1 x2 x3 x4 x5 x3 15 0 [3] 1 0 0 5 x4 12 4 0 0 1 0 x5 14 2 2 0 0 1 7 Z 0 2 3 0 0 0 清華大學(xué)出版社 (2) max{?1, ?2}=3=?2，所以 x2為換入變量。x3+0 m in { | 0 }ili j lii j i lbbaaa???? ? ? ?清華大學(xué)出版社 例 1－ 8 利用單純形算法求解例 1－ 1的線性規(guī)劃問題。 若 則選基變量 xl為換出變量。這就是說，要使原基本可行解的某一個正分量 xj變?yōu)?0，同時保持其余分量均非負(fù)。當(dāng)有兩個或兩個以上 ?j 0時，為了使目標(biāo)函數(shù)值增加的最快，我們一般選擇 ?j 0中的最大者，即： ?j = max {?l∣ ?l 0 } ?j所對應(yīng)的變量 xj為換入變量 (就是下一個基的基變量 )。 定理 無有限最優(yōu)解判別定理： 若 為對應(yīng)于基 B 的基本可行解，有一個 ，而對于 有 ，則線性規(guī)劃問題無有限最優(yōu)解 (也稱為無最優(yōu)解 )。 jx清華大學(xué)出版社 定理 最優(yōu)解判別定理 : 若 為對應(yīng)于基 B 的基本可行解，且對于一切 ，有 ?j ? 0，則 X 為線性規(guī)劃問題的最優(yōu)解。 12 0m m nx x x??? ? ? ?T 清華大學(xué)出版社 2．最優(yōu)性檢驗