【正文】 取得，我們先找到一個初始基可行解。 證： 設 X0=(x10, x20, 從而，必然會找到一個 基本可行解 為最優(yōu)解。,Pr線性相關， ∴ X非基本可行解。+ (yr zr)Pr=0 ∵ Y、 Z為不同兩點， ∴ yjzj不全為 0， ∴ P1,P2,(2) j=1 r ? (yjzj)pj=0 j=1 r ,(1)(2),得 即 (y1 z1)P1+ (y2 z2)P2+(1) j=1 r ? pjzj = j=1 n ? pjzj=b ,n)， yj?0， zj?0 ∵ ?0, 1?0 ，當 xj=0， 必有 yj=zj=0 ∴ ? pjyj = j=1 n ? pjyj=b ,0)T為 非凸集頂點，則必存在 Y、 Z兩點，使得 X=?Y+(1?)Z， (0?1)，且 Y、 Z為可行解 或者 xj=?yj+(1?)zj (0?1)，（ j=1,2,xr,0,0, （ 2）充分性： X非凸集頂點 ? X非基本可行解 設 X=(x1,x2, xm ??m ， 0， 0)T X2=(x1 ??1， x2 ??2， （ 2） 定理 2： 線性規(guī)劃模型的基本可行解對應其可行域的頂點。+??mPm=0， ?m不全為 0，兩端同乘 ?≠ 0，得 ??1P1+??2P2++?mPm=0， 其中 ?1， ?2， ,Pm線性相關，即有 ?1P1+?2P2+(1) j=1 m 又 X是非基本可行解， ∴ P1,P2,0)T，為非基本可行解， ∵ X為可行解， ∴ ?pjxj=b， j=1 n 即 ? pjxj=b ,xm,0,0, 證：等價于 X非基本可行解 ?X非凸集頂點 （ 1）必要性 ： X非基本可行解 ? X非凸集頂點 不失一般性，設 X=(x1,x2,Pk恰好構成基， ∴ X為基本可行解。,xk的系數(shù)列向量 P1,P2, （ 2）充分性： X的正分量所對應的系數(shù)列向量線性獨立 ? X為基本可行解 若 A的秩為 m，則 X的正分量的個數(shù) k?m； 當 k=m時，則 x1,x2,xn)T 為基本可行解的充要條件是 X的正分量所對應的系數(shù)列向量線性獨立。 三個基本定理： 引理： 線性規(guī)劃問題的可行解 X=(x1, x2, 定理 1： 若 LP模型存在可行解，則可行域為凸集。 定理三 若線性規(guī)劃問題有最優(yōu)解，一定存在一個基 可行解是最優(yōu)解。 21 XX 、一、線性規(guī)劃問題基本定理 定理一 若線性規(guī)劃問題存在可行解，則問題的可行 域是凸集。 3．單純形法原理 凸集： 如果集合 C 中任意兩個點 ，其連線上的所有點也都是集合 C 中的點。比較其相鄰頂點函數(shù)值，若更優(yōu)，則逐點轉(zhuǎn)移，直到找到最優(yōu)解。 2. 線性規(guī)劃問題的圖解法 畫出線性規(guī)劃問題的可行域： 目標函數(shù)的幾何意義： 最優(yōu)解的確定： 圖解法的步驟： 1. 建立坐標系，將約束條件在圖上表示； 2. 確立滿足約束條件的解的范圍； 3. 繪制出目標函數(shù)的圖形； 4. 確定最優(yōu)解。 基可行解： 滿足變量非負的基解稱為 基可行解 可行基： 對應于基可行解的基稱為 可行基 例 4 說明什么是基、基 變量、基解、基可行解和可行基 實現(xiàn)目的： 1 2 3121 2 1 2 41 1 52 2612 1 2 3 4 5 62 2 1 22 2 1 22 8 2 84 1 6 4 1 6 4 12 4 12,0 , , , , , 0x x xxxx x x x xx x xx xxxx x x x x x x? ? ??? ????? ? ? ? ?????? ? ? ?????? ????? ? ? ???1 2 3 4 5 6m a x 2 3 0 0 0 0z x x x x x x? ? ? ? ? ? 為了便于建立 n 維空間中線性規(guī)劃問題的概念及便于理解求解一般線性規(guī)劃問題的單純形法的思路，先介紹圖解法。 基 ：約束方程組的一個滿秩子矩陣稱為規(guī)劃問題的一個 基 ，基中的每一個列向量稱為 基向量 ，與基向量對應的變量稱為 基變量 ，其他變量稱為 非基變量 。 ??????????????），（），（njxmibxaxczjinjjijnjjj??1 01 m a x11四、線性規(guī)劃問題的解 可行解： 滿足約束條件的解稱為 可行解 ，可行解的集合稱為 可行域 。 4x松弛變量和剩余變量統(tǒng)稱為松弛變量 （ 3）目標函數(shù)中松弛變量的系數(shù) 由于松弛變量和剩余變量分別表示未被充分利用的資源以及超用的資源，都沒有轉(zhuǎn)化為價值和利潤，因此 在目標函數(shù)中系數(shù)為零 。? ??????????????njjjnjjj xcxczzz11m i n)m a x (m a x2. 約束條件為不等式： （ 1）當約束條件為“ ≤”時 如： 122221 ?? xx可令： ， 顯然 1222 321 ??? xxx 03 ?x（ 2）當約束條件為“ ≥”時 如： 18121021 ?? xx可令： ， 顯然 04 ?x181210 421 ??? xxx 稱為 松弛變量。 一般線性規(guī)劃問題的數(shù)學模型： ????????????????????????????0,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa????????????????）（或）（或）（或目標函數(shù)： 約束條件： nn xcxcxcz ???? ?2211m i nm a x ）（或簡寫形式： ????????????????），（），（），（或）（或njxmibxaxczjinjjijnjjj??1 01 m i nm a x11矩陣形式表示為： m a x m i n0z C XAX bX?? ? ?????（ 或 ）（ 或 ， ）其中： ???????????????nnnnnnaaaaaaaaaA??????212222111211? ?ncccC , 21 ??? ? TnxxxX , 21 ??? ? Tnbbbb , 21 ??三、線性規(guī)劃問題的標準形式 標準形式： ??????????????），（），（njxmibxaxczjinjjijnjjj??1 01 m a x11標準形式特點： 4. 決策變量取值非負。 :指問題要達到的目的要求，表示為決策變量的函數(shù)。 167。生產(chǎn)每件產(chǎn)品 Ⅰ 需占用各設備分別為 0h，生產(chǎn)每件產(chǎn)品 Ⅱ ，需占用各設備分別為 0、 4h。 1．一般線性規(guī)劃問題的數(shù)學模型 ? 例如圖所示，如何截取 x使鐵皮所圍成的容積最大？ x a ? ? xxav ??? 220?dxdv0)2()2()2(2 2 ??????? xaxxa6ax ?一、問題的提出 某企業(yè)計劃生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品。 6．改進單純形法 167。 4．單純形法的計算步驟 167。 2．圖解法 167。167。 1．一般線性規(guī)劃問題的數(shù)學模型 167。 3．單純形法原理 167。 5．單純形法的進一步討論 167。 7．應用舉例及 Matlab求解方法 第一章 線性規(guī)劃及單純形法 167。這兩種產(chǎn)品都要分別在 A、 B、 C、 D四種不同設備上加工。已知各設備計劃期內(nèi)用于生產(chǎn)這兩種產(chǎn)品的能力分別為 1 1 12h，又知每生產(chǎn)一件產(chǎn)品 Ⅰ 企業(yè)能獲得 2元利潤，每生產(chǎn)一件產(chǎn)品Ⅱ 企業(yè)能獲得 3元利潤，問企業(yè)應安排生產(chǎn)兩種產(chǎn)品各多少件，使總的利潤收入為最大。 1．一般線性規(guī)劃問題的數(shù)學模型 產(chǎn)品 Ⅰ 產(chǎn)品 Ⅱ 計劃期內(nèi) 生產(chǎn)能力 A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 利潤 2 3 MAX 需滿足條件： 實現(xiàn)目的： ????????????????0,12 4 16 482122221212121xxxxxxxxm a x 32 21 ??? xxz二、線性規(guī)劃問題的數(shù)學模型 三個組成要素： :是決策者為實現(xiàn)規(guī)劃目標采取的方案、措施，是問題中要確定的未知量。 :指決策變量取值時受到的各種可用資源的限制，表示為含決策變量的等式或不等式。 1. 目標函數(shù)為求極大值； 2. 約束條件全為等式； 3. 約束條件右端常數(shù)項全為非負值； 一般線性規(guī)劃問題如何化為標準型： 1.