1、第1節(jié)線性規(guī)劃問題和模型，第1節(jié)線性規(guī)劃模型從招聘總經(jīng)理談，第2節(jié)泰山工廠生產(chǎn)情況，泰山工廠可以生產(chǎn)兩種產(chǎn)品，需要三種資源，已知每種產(chǎn)品的收益，每種資源的限制和每種產(chǎn)品的資源消耗系數(shù)如下表所示。目前生產(chǎn)現(xiàn)狀：產(chǎn)品a不生產(chǎn)，生產(chǎn)產(chǎn)品b每日30，利潤3600，3，招聘總經(jīng)理！約翰：我申請！在現(xiàn)有資源情況下，可以實現(xiàn)4280的利益！案例為a產(chǎn)品20生產(chǎn)，b產(chǎn)品24生產(chǎn)的可能性：9 * 20 4 * 24=276360 4 * 20 5 * 24=200 3 * 20 10 * 24=300，4，如何達(dá)成？John使用運營研究的線性編程模型問題：如何安排生產(chǎn)計劃以獲得最多收益？步驟：1，確定決策變量：

2、a產(chǎn)品x1kg，B生產(chǎn)設(shè)置，B產(chǎn)品x2kg 2，確定目標(biāo)功能：maxZ=70X1 120X2 3，確定約束條件：設(shè)備約束條件9X1 4x 2360人員約束條件4X1 5X2y=ax b是直線。同樣，Z=70 x1 120 x2x2=70/120 x1-Z/120是一條直線，它是參數(shù)的等值線族。9x1 4x2 360 x1 360/9-4/9x2是線x1=360/9-4/9x2下的半平面。所有半平面相交稱為可執(zhí)行域，在可執(zhí)行域中的任意位置滿足所有約束條件的解決方案稱為可執(zhí)行解決方案。6，示例1圖標(biāo)，90 80 60 40 20，0 20 40 60 80 100，x1，x2，9x1 4x2 、9

3、、2、線性編程方法、示例2。工廠計劃期間，生產(chǎn)、兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備站和a、b兩種原材料的消耗，資源的限制，下表：問題：工廠必須分別生產(chǎn)多少單位、產(chǎn)品，工廠獲利最高？線性編程模型：目標(biāo)函數(shù)：Max z=50 x1 100 x2約束：s . t . x1x 23002 x2400 x2250 x1，x2 0，10，示例1。目標(biāo)函數(shù)：Max z=50 x1 100 x2約束：s . t . x1x 2300(a)2 x12400(b)X2250(c)x10(c)以下是范例1的詳細(xì)說明，其分別使用11、線性程式設(shè)計方法(續(xù))、(1)決定變數(shù)X1、X2設(shè)定座標(biāo)向量的直角座標(biāo)系統(tǒng)。直角坐標(biāo)系

4、中任意點的坐標(biāo)表示確定變量的一組值，示例1中的每個約束條件表示半平面。12，線性編程方法(繼續(xù))，(2)對于每個不等式(約束)，首先將該方程在坐標(biāo)系中拉直，然后確定不等式確定的半平面。13，線性編程方法(繼續(xù))，(3)將五個圖形合并為一個圖形，以聚合每個約束的公共部分，如圖2-1所示。14，線性編程方法(續(xù))，(4)目標(biāo)函數(shù)z=50 x1 100 x2，z獲取固定值時得到直線。直線上的每個點都具有相同的目標(biāo)函數(shù)值，稱為“輪廓”。平行移動等值線，移動到b點時z在可行域內(nèi)最大化。a、b、c、d、e是可執(zhí)行域的頂點，受限制約束的可執(zhí)行域的頂點也受到限制。15，線性規(guī)劃方法(續(xù))，重要結(jié)論：如果線性規(guī)

5、劃具有最優(yōu)解，則必須存在與最優(yōu)解相對應(yīng)的可行域的頂點。無限多個最優(yōu)解。如果將示例1中的目標(biāo)函數(shù)更改為max z=50 x1 50 x2，則線段BC上的所有點都表示最佳解決方案。無限解決方案。行字段的范圍可以無限擴展，目標(biāo)函數(shù)值可以無限擴展或無限擴展。通常，這表示模型中存在錯誤，并忽略某些必需的約束條件；沒有可行的解決方案。如果在示例1的數(shù)學(xué)模型中再添加一個約束條件4x1 3x21200，則可執(zhí)行域為空域，沒有滿足約束條件的解決方案，并且沒有最佳解決方案。16，線性編程方式(續(xù))，例2有些公司因生產(chǎn)要求，總a，b兩種原料至少有350噸(a，b兩種材料具有一定的替代性)，其中，a原料至少購買125

6、噸。但是因為a，b兩種原料的規(guī)格不同，所以需要的加工時間也不同。加工1噸a原料2小時，加工1噸b原料1小時，公司總加工時間為600小時。我還知道1噸a原料的價格為2萬元，1噸b原料的價格為3萬元，為了滿足生產(chǎn)需求，如何在公司加工能力范圍內(nèi)購買a，b兩種原料，使購置成本最低？17，線性編程方法(續(xù))，解決方案：目標(biāo)函數(shù)：Min f=2x1 3 x2約束：s . t . x1x 2350 x1122 x600 x1，x2 0使用圖形方法下圖：qpoint坐標(biāo)(250，100)是最佳解決方案。18，3，線性計劃一般形式的業(yè)務(wù)管理的核心內(nèi)容之一是各種生產(chǎn)要素和產(chǎn)品的部署問題。另一方面，在固定階段，企業(yè)

7、管理者可以“投入”的生產(chǎn)要素原材料、人員、設(shè)備時間是有限的。任何工廠、工廠、機器、所有固定資本在一定時間內(nèi)都不變，再堅固的資本也是有限度的。再從流動資本來看，原材料的來源和庫存，各種技工的數(shù)量和時間在很大程度上短期也是有限的。19，與一般形式的線性編程不同，業(yè)務(wù)管理員“投入”生產(chǎn)元素時必須有完美的目標(biāo)。企業(yè)經(jīng)營者的目標(biāo)當(dāng)然是求得最高收益和最低成本。受時間、空間、數(shù)量限制的“投入”生產(chǎn)要素，如何“適當(dāng)”分配，達(dá)到最佳領(lǐng)域，獲得最佳“產(chǎn)出”量，獲得最大利益。這就是企業(yè)管理者要面對的一個問題的兩個方面。企業(yè)管理者不僅要了解如何配置有限的生產(chǎn)要素，還要在多個供應(yīng)中找到最佳布局，實現(xiàn)自己的業(yè)務(wù)目標(biāo)最低成

8、本、最高利益。20、線性規(guī)劃的一般形式，實際上，以最低的成本追求最佳收獲的原始合理要求，因此，在任何合理的活動中，都有尋找“最佳”問題的存在。21、問題333配方問題，海貍飼料營養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天確切200克。現(xiàn)有5種飼料，配合使用，飼料成分如下：22，案例3建模，設(shè)置收集飼料I x1kg飼料II x2kg飼料III x3kg.目標(biāo)函數(shù)：最經(jīng)濟實惠的minZ=2x1 7x2 4x3 9x4 5x5約束條件：3x 2 x3 6x 4 18x 5700營養(yǎng)要求：x1 0.5x 2 0.2x 3 2x 4 0.5x 530.5x 1 x2 0.2x 3 2x

9、4 0.8x 5=每個時期需要的護(hù)士數(shù)量各不相同。統(tǒng)計信息：24，示例4建模，目標(biāo)函數(shù)：min Z=x1 x2 x3 x4 X5 X6約束：x1x 270x 2 x360x 3 x450x 4 X520x5x 630以外的.6，25，摘要：線性規(guī)劃的一般模式，目標(biāo)函數(shù)：max (min) z=c 1xn約束條件：a11a12x2 a13x3.a1 nxn；(=)B1 a21x 1 a22x 2 a23x 3.a2x80n；(=) B2.am1x1 am2x2 am3x3.amn xn(=)bn非負(fù)約束：x1 0，x2 0，xn 0，26，4，線性編程的標(biāo)準(zhǔn)格式，通用格式

10、目標(biāo)函數(shù)：max (min) z=xn約束條件：s.t.a11x1a12x2.a1n xn；(=，B1 a21x1 a22x2.a2n；(=，) B2.am1x1am2x2.amn xn；(=，)BM x1，x2，Xn 0標(biāo)準(zhǔn)格式目標(biāo)函數(shù)：max z=xn約束條件：s.t.a11a12x2.a1n xn=B1 a21 x1 a22x2.a2n xn=B2.am1x1 am2x 2 amn xn=BM x1、x 2、xn 0、bi 0，27，您可以看到線性編程的標(biāo)準(zhǔn)形式，線性編程的標(biāo)準(zhǔn)形式有四個特點：實現(xiàn)目標(biāo)最大化；約束是方程式。決定變量不是負(fù)數(shù)。右端不

11、是負(fù)值。對于各種非標(biāo)準(zhǔn)形式的線性編程問題，始終采用標(biāo)準(zhǔn)格式：28，線性編程的標(biāo)準(zhǔn)，1 .最小化目標(biāo)函數(shù)的問題：目標(biāo)函數(shù)min f=c 1x1c2x2.如果設(shè)置為cnxn(可能)，則設(shè)置z=-f會導(dǎo)致最小化問題與以下最大化問題具有相同的最佳解決方案：也就是說，maxz=-c 1x1-c2x2-.需要注意的是，-cnxn對上述兩個問題的最優(yōu)解是相同的，但最優(yōu)解的目標(biāo)函數(shù)值不同于min f=-max z，29，一個名為線性編程標(biāo)準(zhǔn)的單個符號。2、約束不是等式問題。將約束設(shè)置為ai1 x1ai2x2.ainxnbi是約束右邊和左邊的差s=bi(ai1 x1 ai2x 2.ainxn)也可以導(dǎo)入非負(fù)約束

12、，即具有s0的新變量s。此時，新約束為ai1 x1ai2x2.ainxn s=bi，30，成為線性配置的標(biāo)準(zhǔn)，約束為ai1 x1ai2x2.ainxn bi時s=(ai1 x1ai2x2.ainxn)-bi顯然在s中也有非負(fù)約束。也就是說，當(dāng)s0時，新的約束條件為ai1 x1 ai2x2.ainxn-s=bi，31，成為線性編程的標(biāo)準(zhǔn)，為使約束不等式而引入的變量s在不等式“小于或等于”時稱為“松弛變量”。如果不等式“大于或等于”，則稱為“剩馀變量”。如果原始問題中存在多個等式約束，則將它們轉(zhuǎn)換為標(biāo)準(zhǔn)形式時，必須為每個約束引入不同的松弛變量。3 .右端有負(fù)值的問題：在標(biāo)準(zhǔn)中，右端的項目必須分別是

13、非負(fù)元件。右端系數(shù)為負(fù)值(例如，bi 40將X2從0到8599；x1=0，x2=min (30/2，60/2，24/2)=12x2輸入基準(zhǔn)變量，X5輸出基準(zhǔn)變量。44，B2=(P3 P4 P2)，45， 1/2，替代，-，-，所以x1=X5=0 x (2)=(，(3)選取的X1為0，X5=0，X1=min(6/1，36/3，1)=6 X1輸入基準(zhǔn)，X3輸出基準(zhǔn)。47，B3=(P1 P4 P2)，因此x3=X5=0 x (3)=(6，12，0，18，0) t z (3)=840，48，49，B4=(P1 P5 P2)，因此x3=x4=0 x (4)=(15，15/2，0，0，9) t z (4)=975.pm)=I，54，XJ=0 (j=m 1，n)為55，1.5.2單純形方法原理，56，此時b=(p1p2.pm)，相應(yīng)的基本可能解決方案為，57，