【正文】 Mathematical Model 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 3 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 線性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行等問(wèn)題。Z=3400 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 7 線性規(guī)劃的數(shù)學(xué)模型由 決策變量 Decision variables 目標(biāo)函數(shù) Objective function 及約束條件 Constraints 構(gòu)成?，F(xiàn)在要制造 1000輛汽車，最少要用多少圓鋼來(lái)生產(chǎn)這些軸？ 【解】這是一個(gè)條材下料問(wèn)題 ，設(shè)切口寬度為零。 鋼鐵公司擬從五種不同級(jí)別的礦石中進(jìn)行冶煉 ， 每種礦物的成分含量和價(jià)格如表 。 第五年： (x7/2+x9)=x8+2x5 第一年： x1+x2=200(萬(wàn)元 ) 第二年： (x1/2 +x3)+x4=x2 第三年 (x3/2+x5)+x6=x4+2x1 第四年： (x5/2+x7)+x8=x6+2x3 到第六年實(shí)有資金總額為 x9+2x7，整理后得到下列線性規(guī)劃模型 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 【 解 】 設(shè) x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資； x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資金 x9：第五年的保留資金 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 18 79121 2 3 41 3 4 5 63 5 6 7 85 7 8 9m a x 22002 2 2 04 2 2 2 04 2 2 2 04 2 2 00 , 1 , 2 , , 9jZ x xxxx x x xx x x x xx x x x xx x x xxj??????? ? ? ??? ? ? ? ? ???? ? ? ? ??? ? ? ? ?????? 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 1 X1 2 X2 3 X3 4 X4 0 5 X5 6 X6 0 7 X7 8 X8 0 9 X9 0 最優(yōu)解： Z＝ x1：第一年的投資； x2：第一年的保留資金 x3：第二年新的投資； x4：第二年的保留資金 x5：第三年新的投資； x6：第三年的保留資金 x7：第四年新的投資 x8：第四年的保留資金 x9：第五年的保留資金 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 19 【 例 】 均衡配套生產(chǎn)問(wèn)題 。將絕對(duì)值約束寫成兩個(gè)不等式 60)109()45(60)109()45(21212121?????????xxxxxxxx 線性規(guī)劃的數(shù)學(xué)模型 Mathematical Model of LP 121212121212m a x12135 4 9609 10 14404 6 604 6 600Zyyxyxxxxxxxxxy x x???????????????????? ? ???????－ －、 、2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 21 線性規(guī)劃的一般模型 一般地 ， 假設(shè)線性規(guī)劃數(shù)學(xué)模型中 ， 有 m個(gè)約束 ， 有 n個(gè)決策變量xj, j=1,2… ,n， 目標(biāo)函數(shù)的變量系數(shù)用 cj表示 , cj稱為 價(jià)值系數(shù) 。 依據(jù)目標(biāo)函數(shù)求最大或最小移動(dòng)目標(biāo)函數(shù)直線，直線與可行域相交的點(diǎn)對(duì)應(yīng)的坐標(biāo)就是 最優(yōu)解。 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 42 【 例 】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型 ???????????無(wú)約束、 211212145||||maxxxxxxxxZ【 解】 此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。當(dāng) m=n時(shí)，基矩陣唯一，當(dāng) mn時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過(guò) mnC2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 47 【例 】線性規(guī)劃 321 24max xxxZ ???????????????????5,1,0226103553214321?jxxxxxxxxxj 求所有基矩陣。 最優(yōu)解 (optimal solution) 滿足式 （ 1 .1） 的可行解稱為最優(yōu)解 ，即是使得目標(biāo)函數(shù)達(dá)到最大值的可行解就是最優(yōu)解 ， 例如可行解 是例 2的最優(yōu)解 。例如，滿足式（ ） ~()是最優(yōu)解 ,又是 B3的基本解 ,因此它是基本最優(yōu)解。 1Q2QO 3Q4Q 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 56 【 定理 】 若線性規(guī)劃可行解 K非空 ,則 K是凸集。 基本概念 Basic Concepts 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 58 1. 線性規(guī)劃常用的概念：可行解、基本解、基本 可行解、最優(yōu)解、基本最優(yōu)解、基、可行基、最優(yōu)基、凸集、極點(diǎn)（凸點(diǎn)）、凸組合 。 最優(yōu)解判斷標(biāo)準(zhǔn) 當(dāng)所有檢驗(yàn)數(shù) λj≤0（ j=1， … ， n）時(shí)，基本可行解為最優(yōu)解。 單純形法 Simplex Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 68 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 表 1－ 5 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 最優(yōu)解 X=(25， 35/3， 0， 0， 0)T，最優(yōu)值 Z=145/3 單純形法 Simplex Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 69 【例 】用單純形法求解 421 22min xxxZ ??????????????????????5,1,0212665521421321?jxxxxxxxxxxj【解】 這是一個(gè)極小化的線性規(guī)劃問(wèn)題 ,可以將其化為極大化問(wèn)題求解 ,也可以直接求解 ,這時(shí)判斷標(biāo)準(zhǔn)是： λj≥0(j=1， … ， n)時(shí)得到最優(yōu)解 。目標(biāo)函數(shù)中含有基變量 x4,由第二個(gè)約束得到 x4=6+x1－ x2，并代入目標(biāo)函數(shù)消去 x4得 1 2 1 2 1 22 2 ( 6 ) 6Z x x x x x x? ? ? ? ? ? ? ?＝ 單純形法 Simplex Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 70 XB x1 x2 x3 x4 x5 b θ x3 x4 x5 1 1 6 [1] 1 2 1 0 0 0 1 0 0 0 1 5→ 6 21 5 6 21/2 λj 1 1↑ 0 0 0 x2 x4 x5 1 2 4 1 0 0 1 1 2 0 1 0 0 0 1 5 1 11 λj 2 0 1 0 0 表中 λj≥0,j=1,2,? ,5所以最優(yōu)解為 X=(0,5,0,1,11,)最優(yōu)值 Z=2x1－ 2x2－ x4=－ 2 5－ 1=－ 11 極小值問(wèn)題 ,注意判斷標(biāo)準(zhǔn) ,選進(jìn)基變量時(shí) ,應(yīng)選 λj0的變量 xj進(jìn)基。 單純形法 Simplex Method 檢驗(yàn)數(shù) 目標(biāo)函數(shù)用非基變量表達(dá)時(shí)的變量系數(shù) 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 63 進(jìn)基列 出基行 bi /ai2， ai20 θi 表 14 (1) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 λj 3 4 0 0 (2) x3 x2 λj