【正文】 A1 A2 可用工時(shí) Ⅰ 3 2 800 Ⅱ 2 3 800 Ⅲ 1 1 350 習(xí) 題 1 用圖解法求解下面的線性規(guī)劃問題： ????????????????? 0,6 62310 2 34m a x2121212121xxxxxxxxxxZ????????????? 0,8102284m a x21212121xxxxxxxxZ??????????????????? 0,10 44318605252m a x21221212121xxxxxxxxxxxZx1 x2 1 2 3 (2) 型機(jī)床的臺(tái)數(shù)種零件表示生產(chǎn)設(shè)變量 ijij ABx323122211211 372330554030 xxxxxxZ ??????m a x????????????????).,..( 213210204040323122211211jixxxxxxxij且為整數(shù)x1 x2 1 2 3 (1) （一）、基本思想 將模型的一般形式變成標(biāo)準(zhǔn)形式，再根據(jù)標(biāo)準(zhǔn)型模型，從可行域中找一個(gè)基本可行解，并判斷是否是最優(yōu)。每個(gè)產(chǎn)品都經(jīng)過三道工序，資料如表所示。 例一、 ) 0 , ( 21 ?xx???????????????????0,0124 16 482122232m a x2121212121xxxxxxxxxxZ⑴ ⑵ ⑶ ⑷ 三、圖 解 法 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴ ⑵ ⑶ ⑷ 作 圖 ∴ 最 優(yōu) 解： x1 = 4 x2 = 2 有唯一最優(yōu)解， Z = 14 x2 x1 (4 2) ???????????????????00124 16 4821222322121212121xxxxxxxxxxZ,m a x⑴ ⑵ ⑶ ⑷ 例二、 例三、 ????????????????0,02 1223622m a x212212121xxxxxxxxxZ⑴ ⑵ ⑶ 無窮多最優(yōu)解 ????????????? 0,122m i n21212121xxxxxxxxZ⑴ ⑵ 無界解 x1 x1 x2 x2 ???????????? 0,6321 23m i n2121211xxxxxxxxZ⑴ ⑵ x1 x2 無可行解 ???????????????? 0,1 5 05 1 0 0321 7 0251810m a x2121212121xxxxxxxxxxZ???????????????? 0,4 3 22232m a x212212121xxxxxxxxxZ例四、 練習(xí) 1 效 產(chǎn)品 機(jī)床 率 A B 機(jī)床臺(tái)數(shù) Ⅰ 30 40 40 Ⅱ 55 30 40 Ⅲ 23 37 20 某車間用三種不同型號(hào)的機(jī)床 Ⅰ 、 Ⅱ 、 Ⅲ ，加工 A、B兩種零件，機(jī)床臺(tái)數(shù)、生產(chǎn)效率如表所示。 凸集 凸集 不是凸集 頂 點(diǎn) ⑵ 最優(yōu)解一定是在凸集的某一頂點(diǎn)實(shí)現(xiàn)（頂點(diǎn)數(shù)目不超過 個(gè)） Cmn⑶ 先找一個(gè)基本可行解，與周圍頂點(diǎn)比較，如不是最大，繼續(xù)比較，直到找出最大為止。 ⑹ 可行基：對應(yīng)于基可行解的基稱為可行基。 （二）、線性規(guī)劃問題的解 ⑷ 基本解：滿足條件②，但不滿足條件③的所有解，最多為 個(gè)。 ) ( 211111mmmmmpppaaaaB ?????????????????則稱 Pj ( j = 1 2 … … m) 為基向量。 ⑵ 最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。 （二）、數(shù)學(xué)模型 00 12211112121112211????????????????????nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcZ??????????????)()(( m i n )m a x目標(biāo)函數(shù)： 約束條件： ① ② ③ 線性規(guī)劃數(shù)學(xué)模型的一般形式 也可以記為如下形式 ： )21(j 0 )21(i )( Z ( m i n )m a x 11nxmbxaxcjnjijijnjjj????????????????目標(biāo)函數(shù)： 約束條件： 如將上例用表格表示如下： 設(shè)變量 )21( njxj ??? 產(chǎn) 品 j 設(shè) 備 i 有效臺(tái)時(shí) 利潤 mnmijnaaaaa 1111????????n 2 1 ??m? 2 1 mbbb? 21nccc 21 ??jcib向 量 形 式： ) ( 21 ncccC ?????????????nxxX ?1???????????mjjjaap ?1???????????mbbb ?1?????????? 0 )( ( m i n ) m a xXbxpCXZjj矩陣形式： ???????????mnmnaaaaA?????1111????????? 0 )( ( m i n ) m a xXbAXCXZ規(guī) 劃 確定型 隨機(jī)型 靜態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃 線 性規(guī) 劃 非線性規(guī)劃 整數(shù)規(guī)劃 非整數(shù)規(guī)劃 整數(shù)規(guī)劃 非整數(shù)規(guī)劃 規(guī)劃類型 一 般 有 兩種方法 圖 解 法 單純形法 兩個(gè)變量、直角坐標(biāo) 三個(gè)變量、立體坐標(biāo) 適用于任意變量、但需將 一般形式變成標(biāo)準(zhǔn)形式 二、線性規(guī)劃問題的求解方法 （一）、求解方法 解的概念 ⑴ 可行解：滿足約束條件②、③的解為可行解。 如果在規(guī)劃問題的數(shù)學(xué)模型中，變量是連續(xù)的（數(shù)值取實(shí)數(shù)）其目標(biāo)函數(shù)是有關(guān)線性函數(shù)（一次方），約束條件是有關(guān)變量的線性等式或不等式，這樣，規(guī)劃問題的數(shù)學(xué)模型是線性的。 模 型 max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0 . 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 此為帶約束的極值問題 問題中總有未知的變量，需要我們?nèi)ソ鉀Q。線 性 規(guī) 劃 (Linear Programming) 線性規(guī)劃問題及其數(shù)學(xué)模型 線性規(guī)劃問題的求解方法 線性規(guī)劃的圖解法 線性規(guī)劃的單純形法 單純形法的進(jìn)一步討論 線性規(guī)劃模型的應(yīng)用 為了完成一項(xiàng)任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個(gè)過程就是規(guī)劃。 例一、有一正方形鐵皮，如何截取 x 使容積為最大？ x a ? ? 2 2 xxav ???此為無約束極值問題 02222 ??????? )()()( xaxxa6ax ?0?dxdv一、 線性規(guī)劃問題及其數(shù)學(xué)模型 （ 一）、問題的提出 設(shè) 備 產(chǎn) 品 A B C D 利潤（元） Ⅰ 2 1 4 0 2 Ⅱ 2 2 0 4 3 有 效 臺(tái) 時(shí) 12 8 16 12 例二、已知資料如下表所示，問如何安排生產(chǎn)才能使利潤最大？或如何考慮利潤大，產(chǎn)品好銷。 要求：有目標(biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃數(shù)學(xué)模型。反之，就是非線性的規(guī)劃問題（其中一個(gè)條件符合即可）。所有解的集合為可行解的集或可行域。 ⑶ 基： B是矩陣 A中 m n階非奇異子矩陣（ ∣ B∣≠0 ），則 B是一個(gè)基。 ∴ Xj 為基變量，否則為非基變量。 Cmn ⑸ 基本可行解：滿足非負(fù)約束條件的基本解，簡稱基可行解。 非可行解 可 行 解 基解 基可行解 解的基本定理 ⑴ 線性規(guī)劃問題的可行域是凸集（凸多邊形）。