Bài giảng Tin học trong công nghệ hóa học – thực phẩm - Chương: Tối ưu hóa hàm nhiều biến bằng Microsoft Excel

ÑAÏI HOÏC QUOÁC GIA THAØNH PHOÁ HOÀ CHÍ MINH

TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA

___oOo___

TOÁI ÖU HOÙA HAØM NHIEÀU BIEÁN

BAÈNG MICROSOFT EXCEL

PGS. TS TRÒNH VAÊN DUÕNG

BOÄ MOÂN: QUAÙ TRÌNH VAØ THIEÁT BÒ CN HOÙA - TP

TOÁI ÖU HOÙA HAØM NHIEÀU BIEÁN

1- Ñaët vaán ñeà

ë á à

2- Thöïc hieän baèng MT (Excel)

ï ä è

3- ÖÙng duïng trong Coâng ngheä Hoùa – Thöïc phaåm – Sinh hoïc

ä ù

Ù

ï

â

ï

å

ï

4- Baøi taäp

ø ä

TOÁI ÖU HOÙA HAØM NHIEÀU BIEÁN

1. ÑAËT VAÁN ÑEÀ:

Hình dung moâ hình döôùi daïng moâ hình thöïc nghieäm sau:



•x₁

•x₂

•x_i

Hoäp ñen

y_i

x_i– bieán (thoâng soá) ñaàu vaøo;

y_i– thoâng soá ñaàu ra (bieán bò ñieàu khieån);

Tìm phương trình hồi qui: y = f(x_i)

Kiểm định: không tương hợp  chọn phương án khác;

tương hợp  tối ưu hoá

1. Ñaët vaán ñeà:

•Caàn tìm cöïc trò (tieåu) haøm nhieàu bieán: u = f(x₁, x₂, …, x_n).

Theo toaùn hoïc haøm f(x₁, x₂, …, x_n) ñaït cöïc trò taïi giaù trò caùc bieán laø

nghieäm cuûa heä phöông trình:

 u

x₁





 0

  u

 0



x





2





 u

x_n



 0





Neáu caùc haøm f(x₁, x₂, …, x_n) coù ñaïo haøm thì baøi toaùn tìm cöïc trò seõ

trôû thaønh baøi toaùn giaûi heä phöông trình (tuyeán tính hoaëc phi

tuyeán) maø ta ñaõ khaûo saùt trong chöông 1, 2 vaø 3

1. Ñaët vaán ñeà:

•Caàn tìm cöïc trò (tieåu) haøm nhieàu bieán: u = f(x₁, x₂, …, x_n).

- Khoâng coù ñaïo haøm;

- Coù bộ giá trị gần đúng ban đầu;

- Coù sai số cho phép;

1. Ñaët vaán ñeà:

•Caàn tìm cöïc trò (tieåu) haøm nhieàu bieán: u = f(x₁, x₂, …, x_n).

Thực hiện hai bước:

- Tìm bộ giá trị gần đúng ban đầu;

- Tìm giá trị đúng;

1. Ñaët vaán ñeà:

•Caàn tìm cöïc trò (tieåu) haøm nhieàu bieán: u = f(x₁, x₂, …, x_n).

Thực hiện hai bước:

- Tìm bộ giá trị gần đúng ban đầu;

- Tìm giá trị đúng;

2. Toái öu khoâng ñieàu kieän baèng phöông phaùp tìm kieám

luaân phieân töøng bieán:

•Ñeå söû duïng phöông phaùp naøy caàn ñaùp öùng moät soá ñieàu kieän sau:

•Ñaõ bieát daïng haøm f(x₁, x₂, …, x_n);

•Cho bieát ñoä chính xaùc , cuûa caùc bieán caàn ñaït ñöôïc ñeå haøm ñaït

cöïc trò;

•Bieát caùc giaù trò gaàn ñuùng ban ñaàu: x₀₁, x₀₂, …, x_0n;

Coá ñònh taát caû giaù trò caùc bieán x_itröø giaù trò cuûa moät bieán (giaû söû

bieán thöù nhaát) x₁(i 1) thì haøm f(x₁, x₀₂, …, x_0n) laø haøm moät bieán ñoái

vôùi x₁.

Giaûi baøi toaùn toái öu moät bieán ñoái vôùi x₁nhö ta ñaõ xeùt trong chöông

11. Töông töï nhö vaäy ta tieán haønh ñoái vôùi caùc bieán khaùc.

Nhö vaäy baøi toaùn tìm kieám theo töøng bieán ñöa baøi toaùn toái öu

nhieàu bieán thaønh nhieàu laàn giaûi baøi toaùn toái öu theo moãi bieán.

2. Toái öu khoâng ñieàu kieän baèng phöông phaùp tìm kieám

luaân phieân töøng bieán:

•Sau moãi laàn laëp ta caàn tính:

  x_1i1 x_1i x_2i1 x_2i  x_ni1 x_ni

Kieåm tra ñieàu kieän:    (*)

Neáu thoûa maõn thì keát thuùc tìm kieåm, khi ñoù boä giaù trò X tìm ñöôïc

laø nghieäm cuûa baøi toaùn;

Ngöôïc laïi thì phaûi ñieàu chænh vaø laëp laïi tìm kieám;

Giaûi baøi toaùn toái öu moät bieán ñoái vôùi x₁nhö ta ñaõ xeùt trong chöông

11. Töông töï nhö vaäy ta tieán haønh ñoái vôùi caùc bieán khaùc.

Cho: f(X), X₀, 

Tìm x_iđể: f(x_j0, x_i)  Min

Tìm x_kđể: f(x_j0, x_k)  Min

 

x_{i , j 1} x_{i , j}



  

Kết thúc

2. Toái öu khoâng ñieàu kieän baèng phöông phaùp tìm kieám

luaân phieân töøng bieán:

2 2

Ví duï: Tìm cöïc tieåu cuûa haøm hai bieán: u = (x₂– x₁) + (1 – x₁)²

töø giaù trò ban ñaàu (0,5; 0,5) vôùi ñoä chính xaùc 0,0001

Roõ raøng haøm ñaõ cho coù duy nhaát moät cöïc tieåu baèng 0, taïi toaï ñoä

(1,1)

Baøi toaùn thoûa maõn ñieàu kieän cuûa phöông phaùp tìm kieám theo töøng

bieán.

Ñeå giaûi baøi toaùn naøy baèng Microsoft Excel ta laäp baûng tính daïng

sau:

Trong baûng coät A, B ta ñaët caùc bieán x₁, x₂

ÔÛ coät C ta ñaët giaù trò haøm u, coøn coät D ta tính sai soá:  = u₁– u₂

Sau moãi laàn laëp, tieán haønh ñieàu kieän (*), neáu thoûa maõn thì döøng

laïi, neáu khoâng tieáp tuïc laëp ñeán khi ñaït yeâu caàu. Keát quaû ta laäp

baûng goàm caùc coâng thöùc trong baûng sau

2. Toái öu khoâng ñieàu kieän baèng phöông phaùp tìm kieám

luaân phieân töøng bieán:

Coâng thöùc

OÂ

A3 Ban ñaàu 0,5

B3 Ban ñaàu 0,5

C3 Haøm f(x₁,x₂) =(B3-A3^2)^2+(1-A3)^2

D5 (12.2) =ABS(A3-A5)+ABS(B3-B5)

•Copy coâng thöùc oâ C3 vaøo caùc oâ C4:C28

•

D5 vaøo caùc oâ D5, D7, D9, … (coät D coù chæ soá leû)

Thöïc hieän tính laëp theo trình töï sau:

Copy B3 vaøo B4

Nhaáp chuoät vaøo C4

2. Toái öu khoâng ñieàu kieän baèng phöông phaùp tìm kieám

luaân phieân töøng bieán:

•Keát quaû

tính toaùn

cho trong

baûng

2. Toái öu khoâng ñieàu kieän baèng phöông phaùp tìm kieám

luaân phieân töøng bieán:

1

Moâ phoûng quaù trình

hoäi tuï theo phöông

phaùp luaân phieân

töøng bieán

0,9

0,8

Keát quaû cho thaáy cöïc

trò baèng

y_Min= 8,82.10^9

0,7

taïi x₁= 0,99991;

x₂= 0,99981;

0,6

0,5

0,6

0,7

0,8

0,9

1

3. Toái öu khoâng ñieàu kieän theo phöông phaùp gradien:

Ñaây laø phöông phaùp tìm kieám nhanh nhaát, ñöôïc duøng ñoái vôùi

tröôøng hôïp khi coù haøm soá daïng giaûi tích vaø ñaïo haøm rieâng baäc 1

cuûa noù

•Ñeå aùp duïng phöông phaùp naøy caàn coù nhöõng ñieàu kieän sau:

•- Haøm ñöôïc cho döôùi daïng giaûi tích;

•- Ñoä chính xaùc  ñoái vôùi caùc bieán soá maø taïi ñoù haøm ñaït cöïc trò;

•- Caùc giaù trò gaàn ñuùng ban ñaàu x₁₀;

•- Coù coâng thöùc ñaïo haøm rieâng baäc 1 ñoái vôùi moãi bieán;

•Theo phöông phaùp tìm kieám ñaõ neâu, tieán haønh theo höôùng song

song vôùi caùc truïc toaï ñoä ñeán ñieåm cöïc trò ñoái vôùi moãi höôùng naøy;

•Thöïc teá ta khoâng bieát ñöôïc höôùng naøo laø toát nhaát, nhöng nhö ñaõ

bieát höôùng gradien laø höôùng taêng nhanh nhaát cuûa haøm. Do ñoù

höôùng ngöôïc laïi “antigradien” laø höôùng haøm giaûm nhanh nhaát;

3. Toái öu khoâng ñieàu kieän theo phöông phaùp gradien:

YÙ töôûng cuûa phöông phaùp tìm cöïc trò gradien nhö sau:

Choïn moät ñieåm ban ñaàu vaø tính gradien cuûa haøm ôû ñieåm ñoù.

Höôùng tìm kieám laø höôùng ngöôïc vôùi höôùng gradien.

Nghieäm cuûa baøi toaùn toái öu moät bieán laø ñieåm cöïc tieåu cuûa haøm

theo höôùng naøy.

Chaúng haïn ñoái vôùi haøm hai bieán thì laàn laëp thöù nhaát coù daïng:

U  f



x_1T, x_2T



 Min

U

x₂

U

x₁

x_2T x₂₀ h

x_1T x₁₀ h

Trong ñoù:

X₂₀

X₁₀

Coøn h laø ñoä daøi cuûa ñoaïn tính töø ñieåm gaàn ñuùng ban ñaàu ñeán ñieåm

cöïc trò theo höôùng löïa choïn. Ñoä daøi naøy ñöôïc xaùc ñònh baèng

phöông phaùp toái öu haøm moät bieán.

3. Toái öu khoâng ñieàu kieän theo phöông phaùp gradien:

Töø ñieåm tìm ñöôïc cuûa laàn laëp thöù nhaát (x_1T, x_2T) laø cô sôû ñeå tính

gradien döïa treân höôùng tìm kieám baèng phöông phaùp toái öu moät

bieán coù ñieåm cöïc trò.

Pheùp laëp naøy thöïc hieän cho ñeán khi khoâng vi phaïm ñieàu kieän tính

toaùn keát thuùc laø:

  ²  ²

u

   

 



 

   

x₁

x₂



 



Cho: f(X), X₀, 

F/X

X_i+1= X_i– hF/X

F

X







 



_



  

Kết thúc

3. Toái öu khoâng ñieàu kieän theo phöông phaùp gradien:

Töø ñieåm tìm ñöôïc cuûa laàn laëp thöù nhaát (x_1T, x_2T) laø cô sôû ñeå tính

gradien döïa treân höôùng tìm kieám baèng phöông phaùp toái öu moät

bieán coù ñieåm cöïc trò.

Pheùp laëp naøy thöïc hieän cho ñeán khi khoâng vi phaïm ñieàu kieän tính

toaùn keát thuùc laø: caên baäc 2 cuûa toång bình phöông ñaïo haøm rieâng

phaàn cuûa nguyeân haøm nhoû hôn ñoä chính xaùc ñaõ cho.

U 

²

1 x₁

2

Tìm cöïc trò haøm soá:



x₂ x₁²







Vôùi giaù trò ban ñaàu (0,5; 0,5).

Tröôùc heát ta tính ñaïo haøm rieâng phaàn caáp 1 cuûa haøm soá theo caùc

bieán:

U



 4



x₂ x₁²



x₁ 2



1  x₁





x



1





U

x₂

 2



x₂ x₁²







3. Toái öu khoâng ñieàu kieän theo phöông phaùp gradien:

Töø ñieåm tìm ñöôïc cuûa laàn laëp thöù nhaát (x_1T, x_2T) laø cô sôû ñeå tính

gradien döïa treân höôùng tìm kieám baèng phöông phaùp toái öu moät

bieán coù ñieåm cöïc trò.

Pheùp laëp naøy thöïc hieän cho ñeán khi khoâng vi phaïm ñieàu kieän tính

toaùn keát thuùc laø:

  ²  ²

u

   

 



 

   

x₁

x₂



 



Bài giảng Tin học trong công nghệ hóa học – thực phẩm - Chương: Tối ưu hóa hàm nhiều biến bằng Microsoft Excel - Trịnh Văn Dũng