1Lecture7

GoalProgramming*SchoolofBusinessAdministrationHunanUniversityLecturer:E-mail:

2LectureOutlineWhat’sGoalProgramming？SolutionMethodofGPApplicationsofGP3這是一個(gè)典型的線性規(guī)劃問題，但實(shí)際中往往存在多個(gè)目標(biāo)，例如：為什么提出目標(biāo)規(guī)劃？采購部：最近原材料供應(yīng)緊張，就只有那么多原材料，不能超過人事部：勞動(dòng)力目前也很緊缺，就那么多了銷售部：由于產(chǎn)品B銷售疲軟，希望產(chǎn)品B產(chǎn)量不超過產(chǎn)品A的一半維修部：好久沒檢修過了，最好能節(jié)約4個(gè)設(shè)備臺(tái)時(shí)以便檢修財(cái)務(wù)部：計(jì)劃利潤(rùn)要是不少于480元就好了4幾個(gè)基本概念絕對(duì)約束和目標(biāo)約束偏差變量?jī)?yōu)先因子和權(quán)系數(shù)5絕對(duì)約束和目標(biāo)約束絕對(duì)約束：必須嚴(yán)格滿足的約束條件，也叫硬約束目標(biāo)約束：盡量要滿足的約束條件，又稱軟約束采購部：最近原材料供應(yīng)緊張，就只有那么多原材料，不能超過人事部：勞動(dòng)力目前也很緊缺，就那么多了銷售部：由于產(chǎn)品B銷售疲軟，希望產(chǎn)品B產(chǎn)量不超過產(chǎn)品A的一半維修部：好久沒檢修過了，最好能節(jié)約4個(gè)設(shè)備臺(tái)時(shí)以便檢修財(cái)務(wù)部：計(jì)劃利潤(rùn)要是不少于480元就好了如果采購部和人事部的要求必須滿足，那么它們就是絕對(duì)約束。6偏差變量對(duì)每一個(gè)決策目標(biāo)，引入正偏差變量d+：實(shí)際決策值超過目標(biāo)值的部分負(fù)偏差變量d-：實(shí)際決策值不足目標(biāo)值的部分注意：d+,

d-≥0,并且d+×d-＝0例：由于產(chǎn)品B銷售疲軟，希望產(chǎn)品B產(chǎn)量不超過產(chǎn)品A的一半x1-2x2+d--d+=0多目標(biāo)決策問題中,決策者對(duì)每個(gè)目標(biāo)都應(yīng)有一個(gè)期望值,即目標(biāo)值,但由于現(xiàn)實(shí)問題的矛盾性,并非每個(gè)目標(biāo)都能一一滿足,而只能盡量滿足。偏差變量7若要求利潤(rùn)指標(biāo)為bi=100萬元，則：若gi(X)=110萬元，則d+=10，同時(shí)d-=0若gi(X)=90萬元，則d-=10，同時(shí)d+=08優(yōu)先因子和權(quán)系數(shù)不同目標(biāo)的輕重緩急或優(yōu)先程度不同

只有高級(jí)目標(biāo)已滿足的基礎(chǔ)上，才考慮低級(jí)目標(biāo)

——優(yōu)先因子來反映(Pi>>Pi+1)

優(yōu)先因子相同，只是一個(gè)并另一個(gè)稍微優(yōu)先考慮

——權(quán)系數(shù)來反映(W)9目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)函數(shù)由偏差變量，優(yōu)先因子和權(quán)系數(shù)構(gòu)成。由于目標(biāo)規(guī)劃追求的是盡可能接近各既定目標(biāo)值，也即各有關(guān)偏差變量盡可能小，因此，目標(biāo)函數(shù)都是求極小化。幾種基本表達(dá)式：要求恰好達(dá)到目標(biāo)值：min(d-+d+)要求不超過目標(biāo)值，但允許不足：min(d+)要求不低于目標(biāo)值，但允許超過：min(d-)例1:假設(shè)上述生產(chǎn)計(jì)劃的例子中，三個(gè)軟約束優(yōu)先考慮銷售部，其次考慮維修部，再其次考慮財(cái)務(wù)部，則其目標(biāo)規(guī)劃模型為：（生產(chǎn)計(jì)劃問題）：某工廠在計(jì)劃期內(nèi)要安排A、B兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品的利潤(rùn)與所需的勞力、設(shè)備臺(tái)時(shí)及原材料消耗，如下：12070單位產(chǎn)品利潤(rùn)360工時(shí)200臺(tái)時(shí)300公斤4510943勞動(dòng)力設(shè)備原材料資源限額產(chǎn)品B產(chǎn)品A12070單位產(chǎn)品利潤(rùn)360工時(shí)200臺(tái)時(shí)300公斤4510943勞動(dòng)力設(shè)備原材料資源限額產(chǎn)品B產(chǎn)品A采購部：最近原材料供應(yīng)緊張，就只有那么多原材料，不能超過人事部：勞動(dòng)力目前也很緊缺，就那么多了銷售部：由于產(chǎn)品B銷售疲軟，希望產(chǎn)品B產(chǎn)量不超過產(chǎn)品A的一半維修部：好久沒檢修過了，最好能節(jié)約4個(gè)設(shè)備臺(tái)時(shí)以便檢修財(cái)務(wù)部：計(jì)劃利潤(rùn)要是不少于480元就好了11目標(biāo)規(guī)劃的一般數(shù)學(xué)模型12建模舉例例2：某車間有A、B兩條設(shè)備相同的生產(chǎn)線，它們生產(chǎn)同一種產(chǎn)品。A生產(chǎn)線每小時(shí)可制造2件產(chǎn)品，B生產(chǎn)線每小時(shí)可制造1.5件產(chǎn)品。如果每周正常工作時(shí)數(shù)為45小時(shí)，要求完成下列目標(biāo)的周生產(chǎn)計(jì)劃：（1）生產(chǎn)量達(dá)到210件/周；（2）A生產(chǎn)線加班時(shí)間限制在15小時(shí)內(nèi)；（3）充分利用工時(shí)指標(biāo)(不要加班)，并依A、B產(chǎn)量/小時(shí)的比例確定重要性。設(shè)A，B生產(chǎn)線每周工作時(shí)間為X1，X21.先確定決策變量2.確定約束條件生產(chǎn)量達(dá)到210件/周2x1+1.5x2≥2102x1+1.5x2+d1--d1+=210A生產(chǎn)線加班時(shí)間限制在15小時(shí)內(nèi)x1≤60x1+d2--d2+=60充分利用工時(shí)指標(biāo)x1+d3--d3+=45x1≤45x2+d4--d4+=45x2≤453。確定目標(biāo)函數(shù)minz=P1d1-+P2d2++4

P3d3++3P3d4+P1:d1-P2:d2＋P3:4d3++3d4+最終模型結(jié)果minz=P1d1-+P2d2++4

P3d3-+3P3d4-2x1+1.5x2+d1--d1+=210x1+d2--d2+=60x1+d3--d3+=45x2+d4--d4+=45X1,x2,di-,di+≥0（i=1,2,3,4)15建模舉例例3：某電子公司同一生產(chǎn)線制造A、B、C三種產(chǎn)品，每種產(chǎn)品單位耗時(shí)分別為5小時(shí)、8小時(shí)、12小時(shí)。生產(chǎn)線每月正常運(yùn)轉(zhuǎn)170小時(shí)。三種產(chǎn)品利潤(rùn)分別為A:100(千元),B:144(千元),C:252(千元)該公司確定的目標(biāo)：P1:充分利用工時(shí)P2:為滿足主要客戶的需求，A、B、C的產(chǎn)量須分別達(dá)到5、5、8，并依單位工時(shí)的利潤(rùn)比例確定權(quán)數(shù)P3:生產(chǎn)線的加班時(shí)間每月不宜超過16小時(shí)P4:A、B、C的月銷售指標(biāo)分別定為10、12、10,并依單位工時(shí)的利潤(rùn)比例確定權(quán)數(shù);P5:盡量減少生產(chǎn)線的加班時(shí)間。1.先確定決策變量設(shè)生產(chǎn)A、B、C三種產(chǎn)品的產(chǎn)量分別為x1,x2,x32.確定約束條件P1:充分利用工時(shí)5x1+8x2＋12x3≥1705x1+8x2＋12x3+d1--d1+=170P2:A、B、C的產(chǎn)量須分別達(dá)到5、5、8x1≥5x2≥5x3≥8x1+d2--d2+=5x2+d3--d3+=5x3+d4--d4+=8P3:生產(chǎn)線的加班時(shí)間每月不宜超過16小時(shí)5x1+8x2＋12x3≤1865x1+8x2＋12x3+d5--d5+=

186P4:A、B、C的月銷售指標(biāo)分別定為10、12、10x1≥10x2≥12x3≥10x1+d6--d6+=10x2+d7--d7+=12x3+d8--d8+=10P5:盡量減少生產(chǎn)線的加班時(shí)間5x1+8x2＋12x3≤1705x1+8x2＋12x3+d1--d1+=1703.確定目標(biāo)函數(shù)P1:d1-P2:20d2-+18d3-+21

d4-P3:d5+P4:20d6-+18d7-+21d8-minz=P1(d1-)+P2(20d2-+18d3-+

21d4-)+P3(d5+)+P4(20d6-+18d7-+21

d8-)+P5(d1+)P5:d1+18建模舉例例4.混合配方問題：某酒廠用三種等級(jí)的原料酒Ⅰ、Ⅱ、Ⅲ兌成制三種混合酒（A、B、C）。原料受到嚴(yán)格限制，每日供應(yīng)量分別為1500千克、2000千克和1000千克，供應(yīng)價(jià)分別為18元/千克、13.5元/千克和9元/千克。三種混合酒的配方及售價(jià)如表所示：混合酒兌制要求售價(jià)元/千克AⅢ不多于10%,Ⅰ不少于50%16.5BⅢ不多于70%,Ⅰ不少于20%15CⅢ不多于50%,Ⅰ不少于10%14.4目標(biāo)如下P1:按規(guī)定比例兌制；P2:獲利最大；P3:混合酒A每天至少生產(chǎn)2000千克。1.先確定決策變量設(shè)xij表示第i種原料在第j種酒中的含量2.確定約束條件按規(guī)定比例兌制x31≤0.1(x11+x21+x31)x11≥0.5(x11+x21+x31)x32≤0.7(x12+x22+x32)x12≥0.2(x12+x22+x32)x33≤0.5(x13+x23+x33)x13≥0.1(x13+x23+x33)原料供應(yīng)量x11+x12+x13≤1500x21+x22+x23≤2000x31+x32+x33≤10000.1x11+0.1x21-0.9x31+d1--d1+=0-0.5x11+0.5x21+0.5x31+d2--d2+=00.7x12+0.7x22-0.3x32+d3--d3+=0-0.8x12+0.2x22+0.2x32+d4--d4+=00.5x13+0.5x23-0.5x33+d5--d5+=0-0.9x13+0.1x23+0.1x33+d6--d6+=0獲利最大16.5(x11+x21+x31)＋15(x12+x22+x32)+14.4(x13+x23+x33)-18(x11+x12+x13)-13.5(x21+x22+x23)-9(x31+x32+x33)≥81000混合酒A每天至少生產(chǎn)2000千克x11+x21+x31≥2000為了使獲利最大，這里的理想值取利潤(rùn)的上界（或一個(gè)很大的數(shù)）=>-1.5x11-3x12-3.6x13+3x21+1.5x22+0.9x23+7.5x31+6x32+5.4x33+d7--d7+=81000=>x11+x21+x31+d8--d8+=200021混合配方問題目標(biāo)規(guī)劃模型22建模舉例例5.工資調(diào)整方案問題:某單位在考慮職工的升級(jí)調(diào)資方案時(shí)，依次遵循以下規(guī)定：（1）年工資總額不超過600,000萬元；（2）每級(jí)的人數(shù)不超過定編人數(shù)；（3）2，3級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%；3級(jí)編制不足的人數(shù)可錄用新職工來補(bǔ)充，1級(jí)職工中有10%要退休。有關(guān)資料如表所示，如何擬定一個(gè)滿意的方案？等級(jí)工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)120,0001012215,0001215310,0001515合計(jì)37421.先確定決策變量設(shè)x1,x2,x3分別表示提升到1，2，3級(jí)的人數(shù)2.確定約束條件年工資總額不超過600,000萬元20000（10-10×0.1+x1)+15000(12-x1+x2)+10000(15-x2+x3)+d1--d1+=600000每級(jí)的人數(shù)不超過定編人數(shù)10-10×0.1+x1+d2--d2+=1212-x1+x2+d3--d3+=1515-x2+x3+d4--d4+=152，3級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%x1+d5--d5+=12×0.2x2+d6--d6+=15×0.23.確定目標(biāo)函數(shù)minz=p1d1+p2(d2++d3++d4+)+p3(d5-+d6-)24工資調(diào)整方案問題目標(biāo)規(guī)劃模型minz=p1d1+p2(d2++d3++d4+)+p3(d5-+d6-)5000x1+5000x2+10000x3+d1--d1+=90000

-x1+x2+d3--d3+=3-x2+x3+d4--d4+=0x1+d5--d5+=2.4x2+d6--d6+=3xi≥0,(i=1,2,3);dj-,dj+≥0,(j=1,2,…,6)x1+d2--d2+=3s.t.25目標(biāo)規(guī)劃的圖解法兩個(gè)決策變量的目標(biāo)規(guī)劃可用圖解法來求解例：2533.3x1x210d1+d1-2040d3+d3-1620d2+d2-10（17.5,10）OABCEFD26目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃單純形法的特點(diǎn)目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃單純形法的要點(diǎn)27目標(biāo)規(guī)劃單純形法的特點(diǎn)目標(biāo)函數(shù)只有偏差變量，且求它們的”和”最小目標(biāo)函數(shù)中“價(jià)值系數(shù)”一般為優(yōu)先級(jí)的權(quán)重，因此檢驗(yàn)數(shù)不是一行，而是m行。在m行檢驗(yàn)數(shù)中，從上到下，按優(yōu)先級(jí)從高到低的順序排列。求解時(shí)，首先滿足優(yōu)先級(jí)高的變量。目標(biāo)規(guī)劃的單純形法28產(chǎn)品決策問題：某汽車工廠生產(chǎn)大轎車和載重汽車兩種型號(hào)的汽車，已知生產(chǎn)每輛汽車所用的鋼材都是2噸/輛，該工廠每年供應(yīng)的鋼材為1600噸；工廠的生產(chǎn)能力是每2.5小時(shí)可生產(chǎn)一輛載重汽車，每5小時(shí)可生產(chǎn)一輛大轎車，工廠全年的有效工時(shí)為2500小時(shí)；已知供應(yīng)給該廠大轎車用的座椅每年可裝配400輛。據(jù)市場(chǎng)調(diào)查，出售一輛大轎車可獲利4千元，出售一輛載重汽車可獲利3千元。工廠的生產(chǎn)目標(biāo)如下：P1.希望總利潤(rùn)為2600千元；P2.為了不使產(chǎn)品滯銷，大轎車的產(chǎn)量不要超過300輛；P3.保持正常生產(chǎn)，避免開工不足；P4.鋼材的消耗量不要超過庫存量。應(yīng)如何安排生產(chǎn)才能使工廠獲利最大？目標(biāo)規(guī)劃的單純形法29產(chǎn)品決策數(shù)學(xué)模型s.t.30初始單純形表00b2600431-10006503001000100300250052.50001050016002200001800430-2000100000052.500000220000031第一次迭代00b1400031-1-40046603001000100-100002.500-51040010000200-201500030-2-4000000-10002.500-5000200-20032第二次迭代00b200001-12001000300100010030004000100-20.40-20000002-0.81100000-22000000-1000000000000020033第三次迭代00b100000.5-0.51-0.60020010-0.50.500.600600011-101.60000-1100.4100-1-1000000.5-0.50-0.6000000-1000-1100.4034最優(yōu)解由于非基變量的檢驗(yàn)數(shù)全都小于零因此已獲最優(yōu)解只有第二個(gè)目標(biāo)值沒有完全滿足，偏差為100，即大轎車只生產(chǎn)200輛。35例某電視機(jī)廠生產(chǎn)46厘米和51厘米兩種電視機(jī)，平均生產(chǎn)能力1臺(tái)/小時(shí)，正常每日兩班，每周80小時(shí)。下周的最大銷售量是46厘米70臺(tái)，51厘米35臺(tái)。已知每出售一臺(tái)46厘米的獲利250元，51厘米的150元，試決定最優(yōu)生產(chǎn)計(jì)劃。經(jīng)理按重要程度確定以下目標(biāo)：避免開工不足，保持職工就業(yè)穩(wěn)定盡量少加班，每周加班不超過10小時(shí)努力達(dá)到預(yù)計(jì)的銷售量36數(shù)學(xué)模型37初始單純形表00530b80111000-1080570100100007033501001000-0100000011-1-110000-100000000-153000000000000-1038第一次迭代00530b10011-100-101007010010000033501001000350100000011-1-010-100-100000000-1030-50000000000-1039第二次迭代00530b010011-100-10-07010010000-32500-111010250100000011-11000-1000000000000-100-3-20030000000-1040第三次迭代00530b020011-1010-10701001000031500-111-101100000011-100-1000000000000-100-3-20-3030000010-141最優(yōu)解寫出上一步的檢驗(yàn)數(shù)，發(fā)現(xiàn)已是最優(yōu)解。最優(yōu)解：因此加班10小時(shí)(未能少加班)，51厘米的彩電少生產(chǎn)了15臺(tái)，未能滿足預(yù)期銷售目標(biāo)。42目標(biāo)規(guī)劃單純形法的要點(diǎn)約束方程中的負(fù)偏差為初始基變量。檢驗(yàn)數(shù)在單純形表中以矩陣形式表達(dá)，占有m行，且按優(yōu)先級(jí)順序排列。選擇換入變量時(shí)，先在優(yōu)先級(jí)最高的行中尋找正的檢驗(yàn)數(shù)，當(dāng)最高級(jí)的檢驗(yàn)數(shù)相同時(shí)，比較次高級(jí)的檢驗(yàn)數(shù)。在選擇換出變量時(shí)，若有多于一個(gè)的最小正比值，則選擇較高優(yōu)先級(jí)的變量換出。只要各變量的檢驗(yàn)數(shù)表達(dá)式中最高級(jí)權(quán)重的系數(shù)小于零，則已獲最優(yōu)解。43小結(jié)：求解目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型實(shí)際上是最小化的線性規(guī)劃，可以用單純形法求解。幾點(diǎn)注意事項(xiàng)：偏差變量一律都看作決策變量由于是求最小化，故最優(yōu)性條件是所有檢驗(yàn)數(shù)都≤0判定檢驗(yàn)數(shù)的大小時(shí)，必須注意P1>>P2>>P3>>…..例：一家生產(chǎn)某種產(chǎn)品的公司在生產(chǎn)周期內(nèi)的正常生產(chǎn)時(shí)間為100小時(shí)。為了提供產(chǎn)量，該公司可加班生產(chǎn)、轉(zhuǎn)包或雇臨時(shí)工，具體數(shù)據(jù)如下表：小時(shí)/單位產(chǎn)品費(fèi)用/小時(shí)平均優(yōu)質(zhì)水平正常生產(chǎn)2.010099%加班生產(chǎn)2.015098%轉(zhuǎn)包2.58095%臨時(shí)工3.08090%決策目標(biāo)為：P1:盡量滿足100單位產(chǎn)品的市場(chǎng)需求P2:優(yōu)質(zhì)品不