1、目標(biāo)規(guī)劃求解方法第1頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五1.序列法序列法的基本思想和方法序列法的迭代步驟序列法的評價(jià) 二.線性目標(biāo)規(guī)劃的求解方法：第六章 多目標(biāo)規(guī)劃第2頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五1.序列法基本思想：目標(biāo)規(guī)劃通過引入偏差變量將各級目標(biāo)轉(zhuǎn)化成目標(biāo)約束，再極小化偏差變量來實(shí)現(xiàn)各級目標(biāo)。當(dāng)偏差變量達(dá)到極小值0時，該級目標(biāo)被完全實(shí)現(xiàn)。序列法是按照優(yōu)先級別去極小化各級目標(biāo)的偏差變量的，即極小化該級目標(biāo)偏差變量是在不破壞上級目標(biāo)已經(jīng)達(dá)到的最優(yōu)值的前提下進(jìn)行的，所以該級目標(biāo)的偏差變量未必能達(dá)到極小值0。那么該級目標(biāo)偏差變量極小化的程度就是該級目

2、標(biāo)在不破壞前級目標(biāo)最優(yōu)值的前提下被實(shí)現(xiàn)的程度。多目標(biāo)規(guī)劃6-4第3頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7具體方法： 序列法按照目標(biāo)函數(shù)中各目標(biāo)的優(yōu)先級別,順序?qū)⒛繕?biāo)規(guī)劃分解為一系列單目標(biāo)的線性規(guī)劃,用單純形法逐一求解.在求解過程中確定進(jìn)基變量,離基變量及主元的原則與線性規(guī)劃的單純形法相同,不同的是要以不影響較高級目標(biāo)的最優(yōu)值為前提求解較低級目標(biāo)的最優(yōu)值.如此反復(fù)迭代,直到進(jìn)行到最低級目標(biāo)的目標(biāo)函數(shù)達(dá)到最優(yōu)為止.30111=-+-ddx多目標(biāo)規(guī)劃6-4第4頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五1.序列法序列法的基本思想和方法序列法的迭代步驟序列法的評價(jià)

3、 二.線性目標(biāo)規(guī)劃的求解方法：第六章 多目標(biāo)規(guī)劃第5頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7迭代步驟:30111=-+-ddx(1) 建立 P1 級目標(biāo)的單目標(biāo)線性規(guī)劃：多目標(biāo)規(guī)劃6-4第6頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7(1) 建立P1 級的單目標(biāo)線性規(guī)劃：用單純形法求解：對 P1 級目標(biāo)而言已是最優(yōu)表。所以 P1 級目標(biāo)已被完全實(shí)現(xiàn)。多目標(biāo)規(guī)劃6-4第7頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7迭代步驟:30111=-+-ddx(2) 建立 P2 級目標(biāo)的單目標(biāo)線性規(guī)劃：多目標(biāo)規(guī)劃6-4第8頁，共33頁，2022

4、年，5月20日，9點(diǎn)12分，星期五例6-7化簡:(2) 建立 P2 級目標(biāo)的單目標(biāo)線性規(guī)劃：多目標(biāo)規(guī)劃6-4第9頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7(2) 建立P2 級的單目標(biāo)線性規(guī)劃：用單純形法求解：對 P2 級目標(biāo)而言還未達(dá)到最優(yōu)。經(jīng)過兩次單純形法的迭代，可得最優(yōu)表。多目標(biāo)規(guī)劃6-4第10頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7最優(yōu)表4-5(2) 建立P2 級的單目標(biāo)線性規(guī)劃：此時對P2 級目標(biāo)而言已達(dá)到最優(yōu)。所以P2 級目標(biāo)未被完全實(shí)現(xiàn)，還差580。多目標(biāo)規(guī)劃6-4第11頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7迭

5、代步驟:30111=-+-ddx(3) 建立 P3 級目標(biāo)的單目標(biāo)線性規(guī)劃：多目標(biāo)規(guī)劃6-4第12頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7化簡：(3) 建立 P3 級目標(biāo)的單目標(biāo)線性規(guī)劃：由P2 級目標(biāo)的最優(yōu)表4-5，多目標(biāo)規(guī)劃6-4第13頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7最優(yōu)表4-5(2) 建立P2 級的單目標(biāo)線性規(guī)劃：基變量將會使P2 級目標(biāo)已得的最優(yōu)值 minZ2 = 580的檢驗(yàn)數(shù)分別是8, 12, 1 0所以如果它們進(jìn)基做為了不使必須令這些非基變量的取值永遠(yuǎn)為 0多目標(biāo)規(guī)劃6-4第14頁，共33頁，2022年，5月20日，9點(diǎn)12

6、分，星期五例6-7化簡：(3) 建立P3 級的單目標(biāo)線性規(guī)劃：由P2 級目標(biāo)的最優(yōu)表4-5，所以P3 級目標(biāo)未被完全實(shí)現(xiàn)。多目標(biāo)規(guī)劃6-4第15頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7迭代步驟30111=-+-ddx(4) 建立 P4 級目標(biāo)的單目標(biāo)線性規(guī)劃：所以P4 級目標(biāo)已被完全實(shí)現(xiàn)。多目標(biāo)規(guī)劃6-4第16頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7最優(yōu)解：最優(yōu)值向量：結(jié)論：P1 , P4級目標(biāo)已被完全實(shí)現(xiàn),P2 , P3級目標(biāo)未被完全實(shí)現(xiàn)。多目標(biāo)規(guī)劃6-4第17頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五1.序列法序列法的基本思想和

7、方法序列法的迭代步驟序列法的評價(jià) 二.線性目標(biāo)規(guī)劃的求解方法：第六章 多目標(biāo)規(guī)劃第18頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五1.序列法優(yōu)點(diǎn)：求解思路清晰，在整個求解過程中僅用到了我們所熟悉的單純形方法.缺點(diǎn)：需要對每一級目標(biāo)構(gòu)造一個相應(yīng)的單目標(biāo)線性規(guī)劃，然后去求解。對于級別較多的模型，迭代次數(shù)多，計(jì)算量大。多目標(biāo)規(guī)劃6-4第19頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五第四節(jié) 目標(biāo)規(guī)劃線性目標(biāo)規(guī)劃的數(shù)學(xué)模型線性目標(biāo)規(guī)劃的求解方法 序列法多階段法單純形法 第六章 多目標(biāo)規(guī)劃第20頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五2.單純形法單純形法的基本思想

8、單純形法的迭代步驟 二.線性目標(biāo)規(guī)劃的求解方法：第六章 多目標(biāo)規(guī)劃第21頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五2.單純形法基本思想：把目標(biāo)中優(yōu)先因子Pj 理解為一種特殊意義下的正常數(shù)，用Pj 取代(LP)中的成本系數(shù) cj , 從而目標(biāo)規(guī)劃可以理解為一個標(biāo)準(zhǔn)的(LP)，然后用單純形法求出它的最優(yōu)解。多目標(biāo)規(guī)劃6-4第22頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五2.單純形法單純形法的基本思想單純形法的迭代步驟 二.線性目標(biāo)規(guī)劃的求解方法：第六章 多目標(biāo)規(guī)劃第23頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7多目標(biāo)規(guī)劃6-4第24頁，共33頁，2

9、022年，5月20日，9點(diǎn)12分，星期五例6-7表1多目標(biāo)規(guī)劃6-4第25頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五例6-7表1P1 行檢驗(yàn)數(shù)都 當(dāng)前的基本可行解對P1級目標(biāo)已達(dá)最優(yōu)，故檢查P2行檢驗(yàn)數(shù)。所以 P1 級目標(biāo)已被完全實(shí)現(xiàn)。多目標(biāo)規(guī)劃6-4第26頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五表1例6-7P2 行有檢驗(yàn)數(shù) 當(dāng)前的基本可行解對P2級目標(biāo)不是最優(yōu)的。x1 進(jìn)基， 離基。多目標(biāo)規(guī)劃6-4第27頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五表2例6-7P2 行檢驗(yàn)數(shù) -12 0 所以 x2 進(jìn)基， 離基。P2行檢驗(yàn)數(shù) -8 0不能進(jìn)基。多目標(biāo)

10、規(guī)劃6-4第28頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五表3例6-7P2 行檢驗(yàn)數(shù) -2 0，但P1 行相應(yīng)的檢驗(yàn)數(shù)為1， 不能進(jìn)基。P2 行檢驗(yàn)數(shù) -6 0， 進(jìn)基, 離基。 多目標(biāo)規(guī)劃6-4第29頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五表4最優(yōu)表例6-7當(dāng)前基本可行解對 P2 ， P3 ， P4 級目標(biāo)都已達(dá)到最優(yōu)，所以是最優(yōu)解。多目標(biāo)規(guī)劃6-4第30頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五表4最優(yōu)表最優(yōu)解：最優(yōu)目標(biāo)值向量：例6-7多目標(biāo)規(guī)劃6-4第31頁，共33頁，2022年，5月20日，9點(diǎn)12分，星期五2.單純形法單純形法的基本思想單純形法的迭代步驟 二.線