目標規(guī)劃及目標規(guī)劃模型

上傳人：6*** IP屬地：貴州上傳時間：2023-01-03 格式：PPTX 頁數(shù)：47 大?。?41.20KB 積分：20 舉報 版權申訴

已閱讀5頁，還剩42頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

目標規(guī)劃

在科學研究、經濟建設和生產實踐中，人們經常遇到一類含有多個目標的數(shù)學規(guī)劃問題，我們稱之為多目標規(guī)劃。本章介紹一種特殊的多目標規(guī)劃叫目標規(guī)劃(goalprogramming)，這是美國學者Charnes等在1952年提出來的。目標規(guī)劃在實踐中的應用十分廣泛，它的重要特點是對各個目標分級加權與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點的思考方式。本章分目標規(guī)劃模型、目標規(guī)劃的幾何意義與圖解法和求解目標規(guī)劃的單純形方法等三個部分進行介紹。

2.1目標規(guī)劃模型

2.1.1問題提出

為了便于理解目標規(guī)劃數(shù)學模型的特征及建模思路,我們首先舉一個簡單的例子來說明.

例2.1.1某公司分廠用一條生產線生產兩種產品A和B，每周生產線運行時間為60小時，生產一臺A產品需要4小時，生產一臺B產品需要6小時．根據(jù)市場預測，A、B產品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產計劃時，經理考慮下述4項目標：

2.1目標規(guī)劃模型2.1.1問題提出(續(xù))首先，產量不能超過市場預測的銷售量；其次，工人加班時間最少；第三，希望總利潤最大；最后，要盡可能滿足市場需求,當不能滿足時,市場認為B產品的重要性是A產品的2倍．試建立這個問題的數(shù)學模型．討論：

若把總利潤最大看作目標，而把產量不能超過市場預測的銷售量、工人加班時間最少和要盡可能滿2.1目標規(guī)劃模型

2.1.1問題提出(續(xù))足市場需求的目標看作約束，則可建立一個單目標線性規(guī)劃模型

設決策變量x1，x2

分別為產品A，B的產量

MaxZ=12x1+18x2

s.t.4x1+6x260

x28

x1,x20

2.1目標規(guī)劃模型2.1.1問題提出(續(xù))容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T

到(3,8)T

所在線段上的點,最優(yōu)目標值為Z*=180,即可選方案有多種.在實際上,這個結果并非完全符合決策者的要求,它只實現(xiàn)了經理的第一、二、三條目標，而沒有達到最后的一個目標。進一步分析可知，要實現(xiàn)全體目標是不可能的。2.1目標規(guī)劃模型2.1.2目標規(guī)劃模型的基本概念把例的4個目標表示為不等式.仍設決策變量x1，x2

分別為產品A，B的產量.那麼,第一個目標為:x19，x28；

第二個目標為:4x1+6x260；

第三個目標為:希望總利潤最大，要表示成不等式需要找到一個目標上界，這里可以估計為252（=129+188），于是有12x1+18x2

252；

第四個目標為:x1

9，x2

8；

2.1.2目標規(guī)劃模型的基本概念（續(xù)）下面引入與建立目標規(guī)劃數(shù)學模型有關的概念．

（1）、正、負偏差變量d

+，d-

我們用正偏差變量d

+表示決策值超過目標值的部分；負偏差變量d-表示決策值不足目標值的部分。因決策值不可能既超過目標值同時又未達到目標值，故恒有d

+d-＝0．

（2）、絕對約束和目標約束我們把所有等式、不等式約束分為兩部分：絕對約束和目標約束。2.1.2目標規(guī)劃模型的基本概念（續(xù)）絕對約束是指必須嚴格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設例2.1.1中生產A，B產品所需原材料數(shù)量有限制，并且無法從其它渠道予以補充，則構成絕對約束。目標約束是目標規(guī)劃特有的，我們可以把約束右端項看作要努力追求的目標值，但允許發(fā)生正式負偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。2.1目標規(guī)劃模型

2.1.2目標規(guī)劃模型的基本概念（續(xù)）

對于例2.1.1,我們有如下目標約束

+d1--d1+=9(2.1.1)

x2+d2--d2+=8(2.1.2)

4x1+6x2

+d3--d3+=60(2.1.3)

12x1+18x2

+d4--d4+=252(2.1.4)2.1目標標規(guī)規(guī)劃劃模模型型目標標規(guī)規(guī)劃劃模模型型的的基基本本概概念念（（續(xù)續(xù)））(3)、、優(yōu)先先因因子子與與權權系系數(shù)數(shù)．．對于于多多目目標標問問題題，，設設有有L個目目標標函函數(shù)數(shù)f1,f2,,fL,決策策者者在在要要求求達達到到這這些些目目標標時時，，一一般般有有主主次次之之分分。。為為此此，，我我們們引引入入優(yōu)優(yōu)先先因因子子Pi，i=1,2,,L.無妨妨設設預預期期的的目目標標函函數(shù)數(shù)優(yōu)優(yōu)先先順順序序為為f1,f2,,fL,我們們把把要要求求第第一一位位達達到到的的目目標標賦賦于于優(yōu)優(yōu)先先因因子子P1，次位位的的目目標標賦賦于于優(yōu)優(yōu)先先因因子子P2、……，，并規(guī)規(guī)定定Pi>>Pi+1，i=1,2,,L-1.目標標規(guī)規(guī)劃劃模模型型的的基基本本概概念念（（續(xù)續(xù)））即在在計計算算過過程程中中,首首先先保保證證P1級目目標標的的實實現(xiàn)現(xiàn)，，這這時時可可不不考考慮慮次次級級目目標標；；而而P2級目目標標是是在在實實現(xiàn)現(xiàn)P1級目目標標的的基基礎礎上上考考慮慮的的，，以以此此類類推推。。當當需需要要區(qū)區(qū)別別具具有有相相同同優(yōu)優(yōu)先先因因子子的的若若干干個個目目標標的的差差別別時時，，可可分分別別賦賦于于它它們們不不同同的的權權系系數(shù)數(shù)wj。優(yōu)先先因因子子及及權權系系數(shù)數(shù)的的值值，，均均由由決決策策者者按按具具體體情情況況來來確確定定．（4））、、目目標標規(guī)規(guī)劃劃的的目目標標函函效效．．目標標規(guī)規(guī)劃劃的的目目標標函函數(shù)數(shù)是是通通過過各各目目標標約約束束的的正正、、負負偏偏差差變變量量和和賦賦于于相相應應的的優(yōu)優(yōu)先先等等級級來來構構造造的的．．§2.1目標標規(guī)規(guī)劃劃模模型型目標標規(guī)規(guī)劃劃模模型型的的基基本本概概念念（（續(xù)續(xù)））決策策者者的的要要求求是是盡盡可可能能從從某某個個方方向向縮縮小小偏偏離離目目標標的的數(shù)數(shù)值值。。于于是是，，目目標標規(guī)規(guī)劃劃的的目目標標函函數(shù)數(shù)應應該該是是求求極極小?。海簃inf＝f（d+，d-)．．其基基本本形形式式有有三三種種：①要要求求恰恰好好達達到到目目標標值值，，即即使使相相應應目目標標約約束束的的正正、、負負偏偏差差變變量量都都要要盡盡可可能能地地小小。。這這時時取取min（（d++d-)；；②要要求求不不超超過過目目標標值值，，即即使使相相應應目目標標約約束束的的正正偏偏差差變變量量要要盡盡可可能能地地小小。。這這時時取取min（（d+)；；目標標規(guī)規(guī)劃劃模模型型的的基基本本概概念念（（續(xù)續(xù)））③要要求求不不低低于于目目標標值值，，即即使使相相應應目目標標約約束束的的負負偏偏差差變變量量要要盡盡可可能能地地小小。。這這時時取取min（（d-)；；對于于例例2.1.1,我們們根根據(jù)據(jù)決決策策者者的的考考慮慮知知第一一優(yōu)優(yōu)先先級級要要求求min（（d1++d2+)；；第二二優(yōu)優(yōu)先先級級要要求求min（（d3+)；；第三三優(yōu)優(yōu)先先級級要要求求min（（d4-)；；第四四優(yōu)優(yōu)先先級級要要求求min（（d1-+2d2-)，，這里里,當當不不能能滿滿足足市市場場需需求求時時,市市場場認認為為B產品品的的重重要要性性是是A產品品的的2倍倍．．即即減減少少B產品品的的影影響響是是A產品品的的2倍倍，，因因此此我我們們引引入入了了2:1的的權權系系數(shù)數(shù)。。§2.1目標標規(guī)規(guī)劃劃模模型型目標標規(guī)規(guī)劃劃模模型型的的基基本本概概念念（（續(xù)續(xù)））綜合合上上述述分分析析，，我我們們可可得得到到下下列列目目標標規(guī)規(guī)劃劃模模型型Minf=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)s.t.x1+d1--d1+=9x2+d2--d2+=84x1+6x2+d3--d3+=60(2.1.5)12x1+18x2+d4--d4+=252x1,x2,di-,di+0,i=1,2,3,4.§2.1目標標規(guī)規(guī)劃劃模模型型目標標規(guī)規(guī)劃劃模模型型的的一一般般形形式式根據(jù)據(jù)上上面面討討論論,我我們們可可以以得得到到目目標標規(guī)規(guī)劃劃的的一一般般形形式式如如下下§2.1目標標規(guī)規(guī)劃劃模模型型目標標規(guī)規(guī)劃劃模模型型的的一一般般形形式式(續(xù)續(xù))（LGP））中的的第第二二行行是是K個目目標標約約束束，，第第三三行行是是m個絕絕對對約約束束，，ckj和gk是目目標標參參數(shù)數(shù)。。§2.2目標標規(guī)規(guī)劃劃的的幾幾何何意意義義及及圖圖解解法法對只只具具有有兩兩個個決決策策變變量量的的目目標標規(guī)規(guī)劃劃的的數(shù)數(shù)學學模模型型，，我我們們可可以以用用圖圖解解法法來來分分析析求求解解．．通通過過圖圖解解示示例例，，可可以以看看到到目目標標規(guī)規(guī)劃劃中中優(yōu)優(yōu)先先因因子子，，正正、、負負偏偏差差變變量量及及權權系系數(shù)數(shù)等等的的幾幾何何意意義義。?！?.2目標規(guī)劃的幾幾何意義及圖圖解法§2.2目標規(guī)劃的幾幾何意義及圖圖解法（續(xù)續(xù)）下面用圖解法法來求解例我們先在平面面直角坐標系系的第一象限限內，作出與與各約束條件件對應的直線線，然后在這這些直線旁分分別標上G-i，i=1，2，，3，4。圖中x，y分別表示問題題（）的x1和x2；各直線移動使使之函數(shù)值變變大、變小的的方向用+、-表示示di+,di-（如圖所示）．§2.2目標規(guī)劃的幾幾何意義及圖圖解法05101520y

x2015105+-G-1+-G-2+-G-4+-G-3圖2-1§2.2目標規(guī)劃的幾幾何意義及圖圖解法下面我們根據(jù)據(jù)目標函數(shù)的的優(yōu)先因子來來分析求解．．首先考慮第第一級具有P1優(yōu)先因子的目目標的實現(xiàn)，，在目標函數(shù)數(shù)中要求實現(xiàn)現(xiàn)min（d1++d2+),取d1+=d2+=0.圖2–2中陰影部分即即表示出該最最優(yōu)解集合的的所有點。我們在第一級級目標的最優(yōu)優(yōu)解集合中找找滿足第二優(yōu)優(yōu)先級要求min（d3+)的最優(yōu)解.取取d3+=0,可得到圖2–3中陰影部分即即是滿足第一一、第二優(yōu)先先級要求的最最優(yōu)解集合。。§2.2目標規(guī)劃的幾幾何意義及圖圖解法圖2-205101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾幾何意義及圖圖解法圖2–305101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.2目標規(guī)劃的幾幾何意義及圖圖解法第三優(yōu)先級要要求min（d4-)，根據(jù)圖示可知知，d4-不可能取0值值，我們取使使d4-最小的值72得到圖2–4中兩陰影部分分的交線(紅紅色粗線)，，其表示滿足足第一、第二二及第三優(yōu)先先級要求的最最優(yōu)解集合。。最后，考慮第第四優(yōu)先級要要求min（d1-+2d2-)，即要在黑色粗粗線段中找出出最優(yōu)解。由由于d1-的權因子小于于d2-，因此在這里可可以考慮取d2-=0。于是解得d1-=5，最優(yōu)解為A點x=3，y=8?！?.2目標規(guī)劃的幾幾何意義及圖圖解法圖2–405101520yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)§2.3求解目標規(guī)劃劃的單純形方方法目標規(guī)劃的數(shù)數(shù)學模型,特特別是約束的的結構與線性性規(guī)劃模型沒沒有本質的區(qū)區(qū)別，只是它它的目標不止止是一個,雖雖然其利用優(yōu)優(yōu)先因子和權權系數(shù)把目標標寫成一個函函數(shù)的形式,但在計算算中無法按單單目標處理,所以可用用單純形法進進行適當改進進后求解。在在組織、構造造算法時，我我們要考慮目目標規(guī)劃的數(shù)數(shù)學模型一些些特點，作以以下規(guī)定：(1)因為為目標規(guī)劃問問題的目標函函數(shù)都是求最最小化，所以以檢驗數(shù)的最最優(yōu)準則與線線性規(guī)劃是相相同的；§2.3求解目標規(guī)劃劃的單純形方方法(續(xù))(2)因為為非基變量的的檢驗數(shù)中含含有不同等級級的優(yōu)先因子子，Pi>>Pi+1，i=1,2,,L-1.于是從每個檢檢驗數(shù)的整體體來看：Pi+1（i=1,2,,L-1）優(yōu)先級第k個檢驗數(shù)的正正、負首先決決定于P1，P2，…，Pi優(yōu)先級第k個檢驗數(shù)的正正、負。若P1級第k個檢驗數(shù)為0，則此檢驗驗數(shù)的正、負負取決于P2級第k個檢驗數(shù)；若若P2級第k個檢驗數(shù)仍為為0，則此檢檢驗數(shù)的正、、負取決于P3級第k個檢驗數(shù)，依依次類推。換換一句話說，，當某Pi級第k個檢驗數(shù)為負負數(shù)時，計算算中不必再考考察Pj（j>I）級第k個檢驗數(shù)的正正、負情況；；§2.3求解目標規(guī)劃劃的單純形方方法(續(xù))（3）根據(jù)（（LGP）模型特征，當當不含絕對約約束時，di-（i=1,2,…,K）構成了一組基基本可行解。。在尋找單純純形法初始可可行點時，這這個特點是很很有用的。解目標規(guī)劃問問題的單純形形法的計算步步驟(1)建立初初始單純形表表．在表中將將檢驗數(shù)行按按優(yōu)先因子個個數(shù)分別列成成K行。初始的檢檢驗數(shù)需根據(jù)據(jù)初始可行解解計算出來，，方法同基本本單純形法。。當不含絕對對約束時，di-（i=1,2,…,K）構成了一組基基本可行解，，這時只需利利用相應單位位向量把各級級目標行中對對應di-（i=1,2,…,K）的量消成0即即可得到初始始單純形表。。置k＝1；§2.3求解目標規(guī)劃劃的單純形方方法(續(xù))(2)檢查當當前第k行中是否存在在大于0，且且對應的前k-1行的同列檢驗驗數(shù)為零的檢檢驗數(shù)。若有有取其中最大大者對應的變變量為換入變變量，轉(3)。若無這這樣的檢驗數(shù)數(shù)，則轉(5)；(3)按單純純形法中的最最小比值規(guī)則則確定換出變變量，當存在在兩個和兩個個以上相同的的最小比值時時，選取具有有較高優(yōu)先級級別的變量為為換出變量，，轉（4）；；§2.3求解目標規(guī)劃劃的單純形方方法(續(xù))(4)按單純純形法進行基基變換運算，，建立新的單單純形表，（（注意：要對對所有的行進進行轉軸運算算）返回(2)；(5)當k＝K時，計算結束束。表中的解解即為滿意解解。否則置k=k+1，返回（2）。。§2.3求解目標規(guī)劃劃的單純形方方法(續(xù))例試用單純形法法來求解例的目標規(guī)劃模模型(2.1.5)Minf=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)s.t.x1+d1--d1+=9x2+d2--d2+=84x1+6x2+d3--d3+=6012x1+18x2+d4--d4+=252x1,x2,di-,di+0,i=1,2,3,4.§2.3求解目標規(guī)劃劃的單純形方方法(續(xù))解:首先處理初始始基本可行解解對應的各級級檢驗數(shù)。由于P1,P2優(yōu)先級對應的的目標函數(shù)中中不含di-,所以其檢驗數(shù)數(shù)只需取系數(shù)數(shù)負值。分別別為(0，0，，0，-1，，0，-1，，0，0，0，0；0)和(0，0，，0，0，，0，0，0，-1，0，0；0)