Tối ưu vectơ tuyến tính và ứng dụng vào mô hình kinh tế

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:3

Thêm vào BST

Báo xấu

11
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Tối ưu vectơ tuyến tính và ứng dụng vào mô hình kinh tế trình bày các nội dung: Phương pháp nón pháp tuyến giải bài toán quy hoạch đa mục tiêu tuyến tính; Thuật toán nón pháp tuyến giải bài toán quy hoạch tuyến tính đa mục tiêu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tối ưu vectơ tuyến tính và ứng dụng vào mô hình kinh tế

Qui hoạch đa mục tiêu có rất nhiều ứng dụng, đặc biệt là trong lý t QUẢN LÝ KINH TẾ quyết định, quản lý, công nghiệp, hành chính,… Mục đích của bài toán q tuyến tính đa mục tiêu là tối ưu đồng thời nhiều hàm mục tiêu độc lập vớ TỐI ƯU VECTƠ TUYẾN TÍNH VÀ ỨNG DỤNG VÀO trên mọi miền chấp nhận được khác rỗng M  R . Do không gian giá trị n n MÔ HÌNH KINH TẾ sắp thứ tự toàn phần nên khái niệm nghiệm tối ưu thông thường không cò Hoàng Kim Chi* hợp nữa. Vì vậy, thay vào đó, cùng với khái niệm về thứ tự từng phần ng ABSTRACT Định nghĩa 2.1. Tập M  Rnhiệu. Đây là một nón với đỉnh nếu: x  M ,  ra programming. This object được gọi là class of multi-objective pro- This paper stidies multi-objective linear khái niệm nghiệm hữuof the study is anền tảngn của tối ưu véctơ. Định nghĩa 2.1. Tập M  R set. The purpose gramming problems with linear objective functions and the constraint set is a polyherdron convexđược gọi là một nón với x =a2.  ( x −khái M . of a multi-objective linear programming problem)is toniệm + Các a  simultaneously optimize multiple objective functions that are independent of each othernghĩa 2.1. Tập M  Rn domains. a +làauthor)nón the concepts of effectiveM , to 0 thì: Định on all admissible non-empty được gọi  (một uses với đỉnh nếu: x  points  x = The x − a  M . come up with a linear cone algorithm Định nghĩa 2.1. Tập M  R n được gọi là một nón với đỉnh nếu: x  M ,  to solve the multi-objective linear programming problem. Keywords: Multi-objective linear programming, linear objective function, và Rn cone algorithm.một nón được gọi nếu: Nếu M là Địnhnón có 2.1. Tập a linear được gọi là thì M với đỉnh là m một nghĩa đỉnh tại M  M lại là tập lồi x =a +  ( x − a )  M . Received: 10/03/2023; Accepted: 15/04/2023; x  a   M .28/05/2023 một nón có đỉnh tại a và M lại là tập lồi th x a    Published:Nếu M là Định nghĩa 2.1. Tập M  Rn Địnhgọi là mộtanónGiao )của .Địnhcác  02.1. được x = +  ( x − đỉnh M với a  nếu: x  M , tập thì: làcó đỉnh avới M nếu:là xnghĩa   chứa M là được gọi là b Định nghĩaĐặt vấn đề Nếu Rn được gọinghĩa 2.2.tạivới vàđỉnhtấtn cảtập M , lồiM Tập tập S  Rmột nóngọi là m nn 1. 2.1. Tập M  một nón M là một nón Định nghĩa 2.1. Tập M lại đỉnh nếu:  lồi thì 0 được gọi R được lồi. thì: Từ xa xưa, xuất phát từ những nhu cầu thực tếmột nónĐịnh  R đượca và một nóncủađỉnh nếu: x  MM được gọi là m Nếu M là như có đỉnh tại 2.2. Giao với tập lồi các ,tậplồithì: nghĩa gọi là M lại là tất cả thì  0 chứa tập x =a +  ( dựng, M việc xây x − a) đo đạc. diện tích tậptrồng, đi biển, tính là một nón có đỉnh tại a và M lại là tập lồi thì M được đất S và kíNếu M convS. x =a +  ( x − a )  M . hiệu là thì: x =a + toán buôn M . Định nghĩa quan tâm tớixcủa bài− acả Mcác S vàlồi cả cáctập S lồiRchứa tậpgọi bao lồi của là ( x − a)  bán,… con người đã 2.2. Giao các tất ) Giao của tất hiệu làtập  n được S là n được gọi . Định nghĩa (2.2. tập tập kí chứa convS. =a + x toán tìm các giái trị lớn nhất (cực đại)M Định nghĩa 2.2. M là một nón có đỉnh tạitập lồi lại là tập lồiS  R đượ hay nhỏ nhất Nếu M là một nón có đỉnh tại a và lý 2.1.là tập lồi thì M tậpGiao Rnlàchứanóncác các tổ hợp lồitập các phần Nếu của tất cả a và M chứa n Định S lại 40 củalồi thì M được  M một mộtlồi. có đỉnh tại củavà M lại và Bao của được gọi (cực tiểu). Nhưng phải đến những năm 30 và kí hiệu là convS.Nếu là một nón lồi. tập convS. S gọi là tất cả nón a tập S và kí hiệu là Định lýtại a gọi là của cả là một nón có đỉnh This hay còn lạitập S và kí nón cón đỉnhconvS.M làlồitập tấtthì MSđược nlồi chứa tập lồi. Toán lồi hiệu lànghĩa và lại một nón lồi.tập chứa nón 2.1. Bao aper Nếu multi-objective linear hoạch toán tại a và of the studyNếutậplà mộtthì Địnhđược 2.2. Giao của lồi tậpcác Rgọi là một tất cả các tổ h stidies M thế kỷ 20, Qui programming.học, object Mgọi là là a M tối is M Định nghĩa 2.2. Giao tư cách là một lý thuyết độc tập lồi củađược gọi là nbao lồi của tập S và kí hiệu là f multi-objective programming problems with của tất cả các tập lý 2.1. Bao S  R được gọi là bao lồi của cả các tổ hợp lồi của các p Định lồi chứa ưu mới hình thành với linear objective functions and Định nhau:Định Một Bao Định  chứa tất tấtcủacác tổ hợp tập lồ tập S lập với nhiều những nghiên2.1. Bao nghĩa 2.3. S  convS.lồitất cả các trong R Giao các của một củalồi của cứu khác lồi của tậplý 2.1.ntập lồiđa diện tổ 2.2. là giao phần cả cáchữu hạ nghĩa R chứa n số Định lý of a multi-objectiveđầu tiên R chứa của tập S hợp lồi của cả tất tử n nó. n Định problem và kí hiệu là convS. đókhônghoạchĐịnh Qui tập SGiaoRn nghĩacác tậplồi của tập SlồiR đa diệnlàtronglàcủa là vect tậpQui hoạchGiao tính, tiếp multiplenó. lồilồi, nghĩa 2.2.Định lý 2.1. Bao là chứatập củachứa 1tất cả m lồi R 2.2. tuyến của tất là Quitập đóng: i Định được 2.3. lồi baotập nstraint set is a polyherdron convex set. The purpose Một là S  của tất cả gọi lồi đó a ,...,baocác các giao được gọi n programming nghĩais to simultaneously optimizecả cácobjective chứa hoạch toàn cục và Lý thuyết điều khiển tối ưu. Một a tổ hợpbi , i của các phần tử củatrong gian , x ³ lồi = m (2.1) nó. 1,...., a Định nghĩa 2.3. Một Sn và kíđa diện trong R n là giao của một s tập tập lồi hiệu là convS. Định nghĩa 2.3. Mộtnghĩaqui bộ phận quan trọng của qui hoạch đa mục tiêu làlồi đa diện trong Rđóng: a , x ³ bđa = m (2.1) trong đó tập kí ns that are independent of each other on all admissible non-empty domains. không nghĩa 2.3. Một của n, i diện trong R các nửa Định gian là giao i tập lồi một số hữu hạnlà n Địnhhiệu làtính đa tocủa tiêu.with aRlinear cone tập S các tổ hợpconvS.một số phầnhạntrong Rikhông giancủa một số hữu h lýeffectiveconvS.come up SĐối tượng nghiên và2.3. Mộtcủa lồi đa diện của nó. là giao đóng: 2.1. Bao lồimục tập  nĐịnh tất cả cứu hiệu là lồi của icác hữu tử các nửa tập 1,...., thortập the và kí of uses S concepts tuyến hoạch points chứa giao chiều, x đakhông giann-chiềuavàx b1 ,...,,bm= m số thực. 1 đó a ,..., a là làmục tiêucột đóng: , ³ bi i là các m(2.1) trong m n vectơ 1 m s paper stidies multi-objective linear programming. This object of the study is a 1,...., hm to solve the chính của nólinear programming problem. multi-objective là lớp các bài toán qui hoạch i khôngxgian ,functions m Định lý m Bao a là cácavectơ hàng n-vec không gian đóng: aobjectiveiđóng: aiand (2.1) trong2.1.(2.1) trong đótập,..., a R chứa tấ , ³ b i = , x bi , i 1,...., đó a ,..., lồi của 1,...., 1 S  là các với các hàm mục tiêu là tuyến tính và tập Định lý 2.1. Baochiều, x Slà Rvectơtất cả các tổ hợp lồi củab1 ,..., bm tử của nó. số thực ss of multi-objective programming problems with linear ràng buộc lồi của tập  chứa n cột n-chiều và các phần là các Định nghĩa 2.3. Một tập lồi đa diện trong R là x là vectơ cột n-chiều và b1nửa bm là các số thực. chiều, giao của một số hữu hạn các ,..., rds: Multi-objective linear programming, linear objective function, linear n Định lý 2.1. Bao lồi của tập S  Mệnh đề 2.1. các tổ hợpn-chiềuhàngbn-chiều,tửdiện số thực.khi vàvà khi tồn R chứa tấtxcả Tập con khác của vàF  M làx của nó.cột n-chiều chỉ chiều,n-chiều và cột lồi là cácsố 1thực. m là các của M là vectơ b ,..., b rỗng sốphần vectơ các là các constraint set is a polyherdron convex set. The n bài toán có multi-objective lgorithm. là một tập lồi đa diện. Đây là lớp purpose of a ý nghĩa ,..., b là vectơ ứng dụng đặc biệtchiều, x là vectơ cột quan trong trong thực tế. là các thực. không gian đóng: a , tiêu có, irất 1,...., mứng dụng, đặc đó2.1. TậpĐịnh vectơcon khác M là diệnM đalà diện trong ear programming problem is to simultaneously optimize multiple objective11 i Mệnhm đề 2.1. nghĩan 2.3. Một tập Mlà diện của M a ,..., am là các Tập con khác rỗngF lồi rỗng nhiều (2.1) trongđề2.3.Mệnh lồi đa 2.1. Tập hàngFn- của một sốF  hạn các nửa củach diện vấn đề. Qui hoạch đa mục x ³ bi = Định nghĩa domains.tập đề 2.1. trong con giao rỗng hữu củalà khi và M Mệnh Một condiện Tập R là khác Mệnh đề khác rỗng  M biệt là trong lý thuyết quyết tập quản số công1,..., m sao chokhilà tập nghiệm tạiFmộttập nghiệm là diện chỉ lý, I  ng- diện chỉ đề 2.1. Tập khi tồn củalà tập F  M Mệnh M F và chỉ con khác rỗng chỉ số hữu m sao nửa hệ: ctions that are independent of each other on all admissible non-empty của Định nghĩahành chính,…dụng,pointsđịnh, bàitrongtậphoạchsố I F 1,...,làIsaocủahạn khicho inghiệmihệ:=của hệ: e author uses hiệp, 2.3. MộtMệnh đích2.1. Tập con khác rỗngtập  Msốmdiệngianđóng:nghiệm của ,tồn tại một (2.1 đặc đa diện Qui hoạch đa mục tiêu có rất nhiều ứngtập lồi biệt là trong lý thuyết R n của 1,..., là giao  một sốsao cho F F là tập chỉ ³khi của1,...., m Mục đề to come upmwithcácchỉ thực. tập chỉkhông 1,...,M tập và cho Fblài tập nghiệm hệ là các cho của b1 ,..., b là a linear cone i chỉ số II  1,...,m sao1 a , mx F là tập nghiệm của củ toán qui số chiều, x là vectơ cộtMục đích của bài toán qui hoạch the concepts of effective định, quản lý, công nghiệp, hành chính,… n-chiều và số 1,....,  cho m đó a ,...,a là các vectơ hàng n- tập , x ³ b , i = m (2.1) trong sao không gian đóng: ia hệ: tuyến tính đa mục tiêu là tối ưu đồng thời nhiều hàm a , x ³ ba,i ,j x { m , m}\II a , x (2.2) j  1,.., m \ I (2.2) i i Î b i  ; b , orithm to solve the multi-objective linear programming problem. i ai , lập với , i Î ính đa mục tiêu là tối ưu đồng thời nhiều hàm mục tiêu độc x = i nhau I ; b 1,..., không gian đóng: a ,programming, Ilinear objective trongb , lineari x xchiều, I x1,..., m} cột n-chiều và b ,..., b là mục tiêu độc lập x ³ nhausố1,...., mmiềnm asao= i đó Ia1,...,,anghiệm ;{vectơ\j b j , j (2.2) m \ I (2.2) tập chỉi =  (2.1) function, F a a ³ i ,b ,các ia vectơ n- i với trên mọi 1,..., chấp, x choi Î là ,tậpiblàij  Î củai ,hệ: Ihàng  1,.., ywords: Multi-objective linear  R . Do không gian giá trị này  bi ,  i nhận j i x a , x = i , i I ; a là b j , ; j ọi miền chấp nhận được đề 2.1. Tập con khác rỗng F giá trị là diện của M khi và chỉ Îkhi tồn , x ³một j Î { Mệnh khácrỗng M được khác rỗng Do không gian  M này được b tại số thực. 1,..., m}\ I (2.2)1 m chiều, x là vectơ cột n-chiều và đó tamcó:các n được Đồng thời khi b1,..., b là ứetự toàn phần nên khái niệm nghiệm phần thông khái niệm nghiệm tối ưu algorithm. sắp thứ tự toàn tối ưu nên thường không còn thích Đặt vấn đề. x là vectơ cột n-chiều 1,..., ữa. Vì vậy, thaytập đó, thường khái niệm về thích b chiều, thông cùng vớikhông vào chỉ số I b , từng F nữa. Vì Đồng của Đồng thời n − đó = x sao i Î hợp lài thờitakhi sốthờicó: I phần x là vậy, đóthực. a , jÎ { j đưa \ F= i ai m= ivà Đồng ,người bcác thaytahệ:I dimta có: dim F ta n − rank .F  a : i  ,cònthứ tựcho; ,..., btập³ nghiệm1,..., m}khi đó (2.2) khi rank a : i  I ai : i  rank  dim F   Đồng thời khi đó ta có:có: dim n  rank ai : i  I i .  nI .  Mệnh đề 2.1. Tập con khác rỗng i F  M là   1 m vào đó, cùng với khái niệm về thứ tự từng phần người niệm nghiệm hữu hiệu. Đây là nền tảng của tối ưu véctơ. Mệnh đề 2.1. Tập Mệnhthời2.2. đólà diện củadim Fvà= đa : i  I . Đồng đề khii) M ta lùi xa M khi chỉ khirank một con khác rỗng F Nón có: RecM của−tập lồi a n tồn tại Qui hoạch đa mục tiêu có rất nhiều ứng dụng, đặc biệtlà nền tảngthuyết tai đưa ra khái niệm nghiệm hữu hiệu. Đây là trong lý Mệnh đề 2.2. i) i) Nón lùi Re cM của tập lồitập di đề nghiệm Nón lùi xa xa Re cM của đa lồ (2.2) Mệnh 2.2. của hệ: củaxtối bi , i Îvéctơ. ,Đồng, jthời Mục Iđíchđề Mệnh đề hoạch i)làNón :lùi xa IRe cM của tập lồi M F tập M là diện M tập i   a , =ưu I ; ai x ³ b j Î { m}\ yết định, quản lý, công nghiệp, hành chính,… khi đó ta có: dim F = a chỉ số .   lồi m diện cho là là tập ng 1,..., 2.2. đa diện Mệnh đề 2. NộiTập con khác rỗng F  làtập chỉ số I  1,..., ,mx saotậpiF là 1,..., m; tậpmột MệnhMcủa 2.2. i)của M−khi xa chỉ ikhiIcủa tại 1,..., đa sao khái niệm bài toán qui n lùi Nón i rank RecM tồn (2.3) nghiệ 2.1. dung nghiên cứu diện a ,x ai  và0,  nghiệm của hệ: cho tập 0, i 1,..., m; (2.3) Mệnh đề 2.2. i) Nón lùi xa ai x với i = m; (2.3) ến tính đa mục tiêu là tối ưu đồng thời nhiều hàm mục tiêu độc,lập ³ 0,nhau 2.1. Các khái niệm 1,..., của tập lồi đa d RecM Đồng thời khi đó ta có: dim F = ai : i  I .(2.3) i n a , x ³ n − rank i n mọi miền chấp Định được khác rỗng M  R . Do không một nón nhận nghĩa 2.1. Tập được gọi là = trị 1,...,  đề F là i) nghiệm bi , icòn thích ,x i a, ii)  0, igian giá m; này đượcRecM,= {0} khi và chỉai , x M là bịj chặn. m i a x = i ,i Î I; b ii) khi  sao tối ưu thông thường khôngcủa; hệ:xa , x, j Î³{ 0, i =ReRe cM 0Mkhi và chỉ khi M của hệ(2.2 tập chỉ số I  1,..., mMệnhcho 2.2. tậpNón alùi=xaÎ IRecM³i bjcủa1,..., m}\ I lồi (2.2) diện  0 tập nghiệm \khi M là tập ii) đacM    là { } ³ b j , Î 1,..., khi và chỉ I là bị chặn thứ tự toàn phần nên kháihọc Hàng hải Việt Nam *Trường Đại niệm nghiệm 1,..., m (2.3) ii) Re cM = 0 ;khi và chỉ khi M là bị chặn. ta Phương p nữa. Vì vậy, thayTẠP CHÍ cùng với khái niệmLÝ VÀ CÔNG NGHỆ người3. QUÝ II/2023 pháp nón pháp tuyến giải bài toán   tập và chỉ khi M  30 vào đó, KHOA HỌC QUẢN về thứ tự từng phần - SỐ 25 đưa Mệnh đề 2.2. i) Nón { xa} lùi i ai , x nghiệm hữu hiệu. Đây là jnền1,..., m =ưu ;véctơ. = i , i Î I ; ai , x ³ b ja ,Îx ³ 0, icủa1,..., m \RecM của tậpii) Re cM Phương pháp nón phápta bị chặn. bài toán rankho (2.2) lồi đa diện=M0là khi nghiệmkhi đó là có: dim F = (2.3) Đồng thời của hệ tuyến giải 3.   n − quy b , Itối rank i khái niệm tảng Đồng thời khi đó ta có: dim F =Re:cMI = 0 khi và chỉ khi M là bị ch 3.1. Điểm n − ii) hiệu . hữu a i  i
3.1. ĐiểmcM  0 hiệu chỉ khi M là bị chặn. ii) Re hữu khi và Định nghĩa 3.2. i) được x0  X được gọi  X đư ii) Điểm chấp nhận Điểm chấp nhận được x 0là nghiệ bài toánii) Re cM  0 khi và chỉ khi M là bị chặn. quy hoạch đa mục tiêu tuyến tính (CMOP) nếu f(x0) là điểm hữu điểmyếu của tập Y. Bài toán (CMOP) nếu 0 ) là hiệu hữu hiệu của tập f(x 0 Phương pháp nón pháp tuyến giải là tập con hoạch đa mục tiêu tuyến tính Ta nói điểm y  Q là: Định nghĩa 3.1. Cho Q bài toán quy khác rỗng trong p . hỉ khi M là bị chặn. pháp tuyến giải bài toán quy hoạch đa mục tiêu tuyến tính QUẢN LÝ KINH TẾ Phương pháp nón đó a ,..., a là các véc tơ hàng n-chiều, x là vécii) Điểm chấp nhận được xlà X được g 0 tơ cột n-chiều và bgiải bài  trong 1 m 3.3 Thuật toán nón pháp tuyến 1,..., bm toán quy h . Điểm hữu hiệup ỗng trong hữu hiệu (hay điểmQ là:tiểu Pareto) của Q nếu hiệu (CMOP) nếu f(x0) nếu f(x0) là (i) điểm cực iảiĐiểm hữu hiệu. Ta nóimục tiêuytuyến tínhtuyến giải bài toán hiệmbài toányếu của bài toán (CMOP)là điểm hữu hiệu y hoạch đa điểm  0 1. bài toán quy2.2. Phương pháp nón pháp các hoạch đa mục tiêu tuyến tính p hữu Xét bài toán qui tập Y. tuyến tính đa mục tiêu (L hoạch quy số thực. nh nghĩa 3.1. Cho2.2.1.tập conhữu hiệu trong . Ta nói điểm y 0  Q là:điểm hữu hiệupyếu của Q là Điểm khác rỗng Định đó a1 ,..., a là các véc hiệu yếu) 3.3.1 Diện 3.1. hiệu (t.ư., . Ta ( areto) của Q nếu  y Q sao cho y0p> y, tức là 0Q  2.3. Thuật toán nón 0 . tuyến giải bài toán quy 3.3 là: y 0 − toán = Thuật + nón pháp )   ịnh nghĩa 3.1. Cho Q là tập con khác rỗng trongcon khácnói điểm y  Q hoạch tuyến tính đa mụcpháp tuyến giải bài toán quy p trongnghĩahữuChomQlà tập hữutơrỗng trong  M (LMOP) trong đó C là một b1,..., bm nlàc ấ p ( hàng x y n-chiều, x là véc tơ cột n-chiều và ma t r ậ tiêu h ác rỗng trong (hay0điểm cực tiểu0  Q là: của Q nếu điểm hữu hiệu p . Ta nói điểm y0 Pareto) Xétbài toán qui hoạch tuyến tính đa mục tiêu (  tức là Qhiệu (hay cực tiểu 0 .   (i) hiệu yếu (hay (ii) điểm quả thực. y €Q y Pareto) của Q tiểu Xét bài toán  y điểm p  điểm cựcnếu Pareto) của (LMOP): Min Cxqui hoạch tuyến tính đa mụctrong ) điểm hữu hữu điểmhữu hiệu (hay điểm cực tiểu Pareto yếu) của Q nếuđiều kiện x Є M (LMOP) với x  M . (LMOP) trong đó và chỉ khi 1 ma t tiêu Pareto) củaQycác sao 3.1.y 0Tập tức là Q  hữu hiệu của. Bài toán (LMOP)trận rỗng khi với các hàng chệ p và r ậ n c ấ p Hệ số C là một Q nếu: cho  y , nghiệm y0  p  nếu Q   y0 đó C là một ma là cấp (p x n) ...c    ểu Pareto yếu)Qcủa Q nếu y , tức m Q  y0  p và pp 2 ,2MM  R nlàlàmột tậpđa diện được xác định xác định p ≥2 0 . và p  ,  R là một lồi lồi đa diện được xác định một tập tập lồi đa diện được n 0 y  y  sao choyy Q sao cho y >> y, tứcj là Q  y 0 − int p = là ( ) 0  y , tức là Q  3.3.1 Diện 0 . y0       p  å i ai =  y hữu hiệu (t.ư., hữu hiệucyếu)i hệ các bất đẳng> 0; tuyến tính: å  j ; bởi ³ 0,  j thức + 0. (3.3) y , tức  (ii) y 0 p   điểm hữulà Qyếu (hay hữucực tiểuyếu) của Qjtiểu Paretotính: ai , x bi , i 1,..., m điểm hiệu  điểm int hiệu yếui0 . 1 điểm cực nếu = Pareto (hay ) điểm hữu hiệu yếu (hay điểm cực tiểu Pareto yếu) của Q nếu yếu) của Q nếu: =1 c tiểu Pareto yếu) của Q nếu là Tập tất cả các điểm hữutính: toán Q³vài WMinQtơm tập tất cảxcác hệ (3.2) Hệ MinQ 0 Kí hiệu quả 3.1. tập nghiệm hữu hiệu củahiệu củax(LMOP) là rỗng khi và chỉ là véc tơ Bài a đó a1...ab , icác 1,...,là n-chiều, n-chiều, x là vé   trongi , là =hàngvéc (3.2)  y  Q sao cho y  y , tức là Q  y 0  int p  trong đó a1 ,..., am là các véc tơ hàng khi 0 . cột n-chiều và b1....bm là các số thực. m mđiểmhiệu của Q yếu của Q.là tập tất cả các  p hữu hữu hiệu và WMinQ   có p 00 . Kí hiệu MinQ   y0Q sao nghiệm. tức là Q  1 f2i   0 int   y , tức là QKhông int cho  y ,Nếu hệ  y có nghiệm. và 2.3.1.nguyên hiệu (t.ư.,Đặchiệu yếu)khi 0T  yTrong đó y f x   fmx  , nàyx ,...,pf  x các  số Diện hữu ,  2. phữu biệt, hàm  , ...,   là tập tất cả các điểmhữu hiệu của ( số thực.m ,  p...,  ) và phiếm  j 1 1 å  ; Hệ quả 3.1. Tập nghiệm hữu hiệu của Bài toán p Kí hiệu MinQvà tập quy các điểm hữu hiệu của=hiệu yếu là tập tất cả i ³ là0, khi và> 0; hệ: 3.2. Bài toán tất cả hoạch đa å Qavà tuyến j c (LMOP) rỗng  j chỉ khi Q là WMinQ là tập tất cả cácmục hữu WMinQ Q. tính các điểm itiêu j (3.3) 1 tiêu và WMinQ 3.3.1 i cả các ip hiệu (t.ư., hữu hiệu yếu) i =mụccủa Qtuyến = 1 là tập tấtDiện hữu n tuyến tính củalà Q. Bài toán lồi tập tất cảhiệu rỗng và f i  m , xi , c  j 1,2,..., p m hữu hiệu MinQ tập làlàcảtập con lồi đóng khác rỗng trongx  c  a iểm hữu hiệu  Q và tất tập quy đa diện các các điểm hữu Kí hiệu yếu của n WMinQ là hoạch đa khác X 2.2.2. tính ,i Cho X  j c ; i 0,  j 0; (3.3) ểm hữu hiệu yếuncủa Q. Hệ 1n i 3.1. j1 : nghiệm = của Bài toán (LM Cho X là tập con lồi đóng khác rỗng trong i quảvà j f Tập n ® , j hữu 2,..., p là p 1, hiệu p m ỗng toán quytuyến đa mục tiêu tuyến jma 2,..., pcực cấp trên M thì  ai điểm j1;, c2...,cp thì bài toán (3.3) hoạchx tính å C c , x đạt Không có p  n có hệ mỗi nghiệm.(m,i tiểu là ...,nghiệmphiếm . Bài trongtức fvà ) f j Cx với  ,jlàtính trận thực tiểu nghiệm. Nếu cáci hàng làj c cực...,hệm ,  j,có0; p ) nghiệmhàm ( : n j 1, là c 0,  một tuyến tính j= 1 êucác hàm lồi nhận giá trị hữu hạn trên X. Bài toán qui Không có jnghiệm Nếu ainày p  vàj ;  0, ihoạch lồi đa mục  1 đượcj c 1 này có 1 1  j i tiêu phát i Bài toán qui hoạch đa có nghiệm. Nếu trên X.n có nghiệmtính đa mục tiêu ,và được) viết phiếm hàm là các hàm lồimục mục tiêu được 2. Bàitoán quy Khônglồi đatiêu là Bàitính hệ phátBài toán hoạch nhận giátuyến toán qui hoạch tuyến ( , ..., m ,  1  p jvà1 dưới hàm trị hữu hạn này i Cho X là tập con lồi đóngđa mục tiêu được nphát fbiểu như ,sau:p1,2,...,, p đạt cực tiểu nghiệm (...,..., này , và phiếm (hàm (CMOP) được gọi trong qui hoạch lồi khác rỗng và j : tính j 1 là 1 c X , trong hữu hiệu ncủa , j với điều kiện tuyếnKhông có nghiệm. Nếucó này cótrên M thìmỗi điểm 1cótiểup làvà phiếm 1, ..., m , 1 rỗng như sau: (CMOP)Bài1,2,..., p(LMOP). x  X, Không hệ nghiệm. Nếu1,hệ m , cực..., nghiệm nghiệm biểu n và fMin f(x) toán là : cj x (CMOP) ) một dạng: f(x) Cx với điềukiện x n X (LMOP)j 1 j j Min Min với điều kiện  Cho X là tập con lồi đóng khác rỗng trong n và f j : , j 1,2,..., p là hàm lồi nhận giá trị hữu hạn mục tiêu được qui đa tuyến tiêu được phát đạt mục tính tuyến tính p p X. Bài toán qui hoạch lồi đatrên X. Bài toán pháthoạch lồicủa Bài Bàituyếnj , tính cựclà  trên ,Mkhimỗicực tiểu tiểuhệmột mỗi mỗi điểm c j x thì đạt điểm cực trên M, nghiệm đạt cực tiểu trên M thì i) Tập nghiệm hữu hiệu yếuhữu hiệu của toán (LMOP) j tiểu j c x toánj(LMOP). 1 rỗng và chỉ khi là c nhưXsau: nhận f(x)thường ( xtrênxX.fX (tập: fY ( X lồip(y mục vàjf 1phátx X f  x  ,..., f pĐặcT và số khi hàm lồiTrong trị hữu f kiệnta ( Bàixtoán 2 : xhoạch fđóptiêu được nguyên p (3.1) x   biệt, nguyên p 2. Đ u x  , Min Như đó điều lệ,) = gọi, ) , qui (CMOP) đax ) )T : y số x f, x , giá với hạn Trong (CMOP) đó:  Trong f,..., f 2. ) i) Tập nghiệmhữu hiệuyếu của Bàitoán (LMOP) là rỗng khi và chỉ khi hệ 1 hữu  cực 1  x hiệu của là 2 toán (LMOP). điểm tiểu Bàimột nghiệm hữu hiệu của Bài toán pX , j ểuf như sau:f Minsốfnguyên pf≥ kiện và số ,nguyên pn hữutiểucủai)biệt,Tập nghiệm hữuvà f yếu củacmộttoán n 1, 2, với điều  f(x) x tính x  tuyến,...,đó 2. Đặc biệt,ckhix X đạt cực tập lồi(LMOP). khác rỗng 2. Đặc plà Bài ,nghiệm, i là rỗ (CMOP) hiệu T Bài toán khi mỗi điểm hiệu tiểu i , x ci (LMOP) trên iM (LMOP). p cực  x biệt, khi Tx thì j  là tập đa diện  c n set)  bài  x   nvà tập2 ảnh củap tậpåX  j f1 ánh, fxạ x hay2.pxĐặc giá,số ,(outcome i 0, 1, 2,..., ptoán qui là p làx  , Trong  T   lồi  qua   m X  1 làxtập và đa diện khác pp 2.  Đặc= i)iiTập nghiệm ;hữui,hiệupyếu jcủa Bàij cjj ; 1  (3.4) f  x   x  2f ,..., flà x vàa trị nguyên= của ip số nguyên rỗng và fji ( Tập inghiệmkhihiệu yếu của Bàii ai(LMOP) là j toán và chỉ khi hệ  j 0; ) 1 c x 1i j 0; 2  x  ,..., f p    mj= 1 i i) biệt, hữu j c  m toán hoạch lồi đa mục å rỗng(CMOP). f (jx) ; Cx ivới0, i là majchỉ ikhi1 åcấp j= p1 n  có (3.4) tiêu= tức  c ivà a å n  ³ rỗng khi  i trận n hệ:  j  1 và > 0;thực rỗng khi (LMOP) 1 i 0, là tập lồi đa diện khác   = =  , x C khác n là tập i i 1 ci , xkhác 1 không1,2,...,p mc  a nàypcónghiệm (j1,2,...,, p0; cóp p ) và phiếm1  khôngx ,  j ; 10,1 hệ 1  ồi đa diện X  rỗng vài flồixđa diện n , cij rỗngi và cóf inghiệm. Nếu,hệicócnghiệm.i Nếu..., mnày, ..., nghiệm (3.4) , ..., m , 1 , =, các hàng là c1, c2..., ( hàm  c x i   1,2,..., p x f i hữu hiệu ,của,Bài toán,(LMOP). được  i 1 iBài gọij c quii hoạch jtuyến j tính1 đa rỗng và Định nghĩa 3.2. i)cĐiểm chấp nhận được x 0gọiXlàđượcj toánlà nghiệm hữu hiệu j của mục tiêu và đ i(CMOP) 1  1 p tuyến kiện p  c j , x đạt j , x đạt cực tiểu trên M thì mỗi p dạng: Min Cx với điềutính x  X j1(LMOP) cực tiểu trênpM thì mỗi điểm tức ftoán (CMOP)làC làf(x0)trậncấp(p x1n)tínhcác nj c là , hàng, 1 cbàic2...,c thì bài  là một nghiệmj Bài f xx) cấp  C nếu trận thựcđiểmchữu ...,cnghiệm. Nếu hệ ...cp thì , hệ này  ,nghiệm i và ) Cx C n cóma hàng tuyếnn)2 hiệuthì có các c với C là ma trận((thựcCx vớivớilàma trận thực cấp2yếucấpcó Bàicủa tậpc1Y;2nàyjcólàlà rỗng ..., điểmcựcchỉpa)khiphiếm hàm; i 0, là thực x, không p p m toán tức tức Tậppcác hàng(CMOP)c ...,ccủa lệ, tatoán tập: ccó có bài có nghiệm. Nếu (1, m i 1tiểu i)là c1= c2...cvới p bài ma hữu cNhưlà(p gọi là Bài 1hàng toán Y : X  cópvà,y..., f  x  ,j x Xc nghiệm các hiệu thường các không(LMOP)fnghiệm toán khi :1  hệ j j i thực cấp  p  n , có , thì toán là , được thì bài gọi  1 p toán 1 không có nghiệm. Nếutoánnày có nghiệm hữu1, ..., yếu của1BàivàđượcvàNếudưới hàm  ( (3.1 hàng (CMOP) được gọi là Bài hệ qui hoạch tuyến(tính đa m ,  , ...,toán ) viết hệ này có nghiệm , ...,  hiệu mục tiêu có yp (LMOP).  nghiệm. phiếm gọi là Bài (CMOP) hoạchii) tuyến tínhmụcmụcđượcvàtínhX3.3.2toángọivàtoánKhôngdưới hiệu yếu của hữu hiệu của b toán qui được gọi Điểm toán đa hoạchhữu hiệu yếu của đượctiêu làđược EFFI xác định các diện toán qui hoạch là Bài chấp nhận vàtuyếnx viết đa Bài Thuật nghiệm hữu tuyến tính đa qui tiêu tiêu được được viết dưới mục (LMOP). viết p 0  1 dạng: Min Cx với điều kiện dưới dạng: là X ảnh của tuyến viết  j , qui hoạch tuyến Min Cxđa điềukiện x và (LMOP) tậpdướix đạt cựcxạ f haythìlà p điểmjcực tiểu là mộttiểu trên M thì củ tính với mục tiêu tập được tính Xj cqua ánh tiểu trên tính mỗi giá trị (outcome set) mỗ M tập 0 3.3.2 Thuật toán EFFI xácmục các diện hữu hiệu của bài toán qui hoạch tuyến nghiệm tính đa định tiêutuyến  j c , x đạt cực dạng: X Cx với (CMOP)  X f(x ) là điểm mục tiêu (CMOP). ới điều kiện x Min(LMOP) kiện xnếu hoạch lồi đa hữu jhiệu yếu của tập Y.tính định tất cả các cạnh hữu hiệu x bài toán điều (LMOP) 1 và phiếm hàm tuyến j 1 đạt cực tiểu X (LMOP) tính đa mục tiêu Sau đây là thủ tục xác Như thường lệ,lệ, gọigọi tập: Y :p   yếuycủa x0đã ,biết X  hữu cả các đỉnh hữu hiệu kề đỉnh này. m 3.3 Thuật lệ, ta gọi tập: Y afi X =Î bài ;toánxtụcxxácX chấp >tấtcựcđượcmột 1pháttiêu (3.4)hữu nghiệm Như thường ta ta tập: f X (3.1) toán nón pháp tuyến giải hữu: jy3.2. i)quy toán mỗicả các 0; tínhhiệujx=nghiệmmột đỉnh là p y hiệu hiệu Bài x x  :  f p (LMOP). hiệu của Bài toán (LMOP). p å = Định nghĩa là thủtrên Mhoạchvànhận tiểu đa mục được gọi { c  Điểm } tuyến å f ( ³ Î thì  j i) Tập nghiệm hữu từ hữu hiệu :=  Xå y Sau đây=i ), 0, định tất (3.1) cạnh hữu là xuất hiệu yếu của Bài toán (LMOP điểm 0 X fytoán qui hoạch tuyến 1 3.3.2đa mụcyếuProcedurecác diện hữuj=hiệu điều tậpp hoạch )  ta X  ::Xy x  , i =ix  ,(xBài(3.1) j(3.1) toán EFFI xác0) toán EF1;hữu hiệu của bài toán quiY; tuyến p Như thường gọi tập: Y fp   :xy1f  f  y Xét bài  X j = tính Thuật nếu f(x định hiệuMin Cx 1 m của toán 0(CMOP) của Bài là điểm (LMOP). là tập ảnh của tập X quaqua ánh hay hiệu x đã biết và tất tiêu (LMOP): định tập I bàii aii  1,..,  jchiệu,x  là tập ảnh của tập X ánh xạ f xạ f hay giá tập giá 3.3.2 Thuật toánkề đỉnh xácvới toánkiện m :j ;a i 0, b   là tập là trị trị đỉnh hữu các (outcome cả Bước 0. Xác set) của x  EFFI 0 này.   qui định các diện hữu i 0 tính đaii)(outcome set) của bài được x  X1 đượcj gọi là nghiệm hữu mụcĐiểm chấp nhận toán qui i tiêu là tập ảnh set) của bàiqua ánh xạ f hay làđa mục tiêu EF1; bài toán qui hoạch tuyến tính đa mục tiêup của tập X toán qui hoạch lồi tập giá trị Procedure 0 1 1 i tập qua là xạ Mlồi đa trị tập giá trị (outcome set)ma toán ca) Nếu I   không có hàng c ,..., cnày có (outcome hay mục trong đó C một của bàicủa ấ  x tập .f (LMOP)tiêu (CMOP).là của bài t r ậ ntoánpquip  nx với ,cácnghiệm. NếuBước 1. nghiệm ( , ..., xạ fXhay hoạch giá là (outcome set) bài toánđây là thủSauxác địnhf(xcả)tục cạnh hữu hữu hiệu yếu của hữu Y.1 ánh SauXác địnhqui đâyađiểmb hiệu xuất phát từcạnhđỉnh tập 0  n chuyển sang hệ (CMOP). đa mục tiêu (CMOP). (CMOP) nếu tất 0 các xác định tất cả các một hữu tục I x0 làthủ mlà i , x0  hoạch lồi Bước 0. tập   i lại, chuyển ip 1,..,  :  ục tiêu (CMOP).nghĩa  R n i) Điểm chấplồi đađượchiệu toánxác địnhcácphát hữutuyếnđỉnh hữu hiệu jx0tuyếncực tiểutuyến thì mỗ . và Định , M 3.2. là một tập nhận diệnxđược0  X b) Ngược từcác bất đẳng  Bướccủa và tất trên M Định  2nghĩa3.2. i) Điểm chấp nhận được đã biết hiệuđược 1.tuyếnnghiệm này.1thứcquy biếtLấy một tậptính p 0 Є x và tất cả bởi hệ hiệu đỉnh sang jhiệu 2. x0 X nónBước đỉnh 0làmột kềtính hữuthoái đãđạt xuất gọi c ,x không có nghiệm. Nếu 3.3 toán 0có nghiệm chuyển sang Bước,1.kề ..., j p hệ Thuật I  n (1, ...,(x m đỉnh không pháp được gọii là nghiệm hữu hiệu của Bài này (CMOP)x0  cả,các đỉnh hữu hiệu 1,đỉnh này. ) vàhoá): a) Nếu  là giải bài toán phiếm hàm hoạch chỉ Định nghĩa 3.2. b , Điểm chấp ) là điểm (3.2) hiệu của tậpnghiệmtuyến tínhyếu của Bài tiêu (LMOP). Bài toánlàx i) i nếu f(xm 0 nhận được x X được gọi làhoạch hữu hiệu của tính: 00a ,(CMOP) 0hiệu của tập Y; Xét bài toán qui Y;1.1.EF1; hiệu tínhmụccủa tập chỉ số I):Min hệ 1,..., hữu Procedure EF1; hữu tra đa âm toán (LMOP): Giải Cx 2. i) Điểm chấpxnhậnđiểm hữu  X được gọi là nghiệm hiệuhiệu sang Bước(Kiểm nhận được f(x ) Xđược x gọi là nghiệm b) Ngược lại, chuyển của nếu  đượci hữu hữu của Procedure Bước X được . (LMOP) Bước 0. 0C 2. 1,..,tập 0cótnghiệm, định   số được điểm  hiệu của tập 0. trong đóXácnày một i , xtoánrEFFI c ấ lấy pcácchỉ với I hiệu ii) Điểm chấp nhậnf(x0) làx0 Є xhữuM gọi làBước Y;Xác định Nếu xhệama p  tập ndiện hữucác( ng- định 0 hiệuđó a1 ,..., am là các véc tơ hàng n-chiều, đượcvéc Itơ cột n-chiều vàbi  1,..., bm0 là  itínhkhông hiệu n a) tập 3.3.2 Thuật là ậ xác ii) Y; tập nhận được x 0 1. (x0 làx làkhông thoáinghiệmmột tập chỉ sốyếu( x ) với I n 1  đa :mục Bài toán (CMOP) nếu m I iểm hữu trong của tậpĐiểm chấpY; P) nếu f(x ) là điểm hữu hiệu của Bước  X đỉnh gọi là hoá): Lấy hữu tiêub I I của và p  2 , M  Rquay trở lại Bước 1.1. n là một tập lồi đa diện được xác định bởi hệ các bất đẳ Sau đây là thủ tục xác định tất cả các cạnh hữu ii) Điểm chấp nhận được x  X được điểm (Kiểm thực. 0 tính: ,x 1.   các sốbài toán (CMOP) nếu f(x ) làa Bước 1.1.b , i 1,..., m sanghiệu x(3.2) và tất cả các đỉnh hữu hiệu kề đỉnh nà Bước 0 CHÍ KHOA HỌCxQUẢNchuyểncủacủa chỉ sốtoán- SỐ (3.2) với II/2023 31 a)hữu I hữu hiệu của tập bài I): Nếu 0 tra yếu yếu tập Y. , LÝ TẠPgọii là nghiệmhiệuntính âmVÀ CÔNG NGHỆGiải hệ25 QUÝ tập chỉ số I này. 0 n được nhận được x  X được gọi là nghiệm hữu hiệu yếu của Điểm chấp x  X được0 gọi là nghiệm hữu hiệu yếu của 0 i đã biết 3.3.1 0 nếu hữu nón pháp tuyến của a)bài hệ am không có véc Bướchàng n-chiều,) x tiêu khác và Diện f(x ) hiệu hữu hữu hiệu yếu) Ngược quy hoạchtơ trong đó a b) là các sang tuyến tính Procedure EF1; 3.3 Thuật toán là điểm(t.ư.,hiệu yếu giảitập1Y.toán lại, chuyểnnghiệm, lấy2.tập chỉ số Iđa (mụclàI véc 1tơ cột n-chiều Nếu này I x với 0 (CMOP) 0 n 0 ,..., 0 i 0
ệu của bài toán qui hoạch tuyến a) Nếu hệ này không có nghiệm, lấy tập chỉ I Ì I (x 0 ) với I = n - 1 khác và quay Procedure EF1; a) Nếu 0 t0 thì x0 tv là một đỉnh hữu hiệu kề x0 và x0 , x0 tv là một i Bước 2.1. ,  aại x 0 KINH TẾ tập I x0 = ai , x0 = bi QUẢN LÝ Bước một đỉnh hữu u hiệu xuất phát từ0. Xác định ( cạnh {i Î { m}: lại kết quảbnày nếu nó chưa từng được lưu giữ trước đó. Lấy tập ) hữu hiệu. Lưu 1,..., i} này. chỉ số I I ( x0 ) với I n 1 khác và quay trở lại Bước 1.1. a)a) Nếu I (x0 )= n , , chuyển sang Bước 1. Nếu chuyển sang Bước 1. b) Ngược lại, tập chỉ số I này là âm, chuyển sang Bước 2.3. 2.2. (Kiểm tra tính âm của tập chỉ số I): Giải Bước b) Ngược lại, chuyển sang Bước 2. b) Nếu một tậpthì tia (3.1) tv : t tập chỉ số I này. hiệu của bài toán (MLP). Lưu t0 hệ x với 0 là một tia hữu 0 tươngNgược(x là đỉnh không thoáiBước Lấy ứng). (Xác 1. lại, chuyển sang hoá): 2. Bước 2.3.b)Bướcđịnh cạnh và đỉnh hữu hiệu kề tương ứnga) Nếutập này khôngđang 0 nếu hệ chỉ số I có nghiệm, lấy tập chỉ  b  mộti tập chỉ số I I (0x0 ) với I n kết quả. Lấy tập chỉ số I I ( x0 ) với I n 10khác và quay trở lại Bước 2.1. chỉ số 1 quay trở lại Bước 1.1. . là tập chỉ số pháp tuyến).đỉnh không thoái hoá): Lấy một tập chỉ số I Ì I (x ) với I = n - 1 Bước 1. 1.2.1. Xác định hướng v của cạnh này bởi hệ. Bước (x là ố I): Giải hệ (3.2)1.1. (Kiểmchỉtính âm của tập chỉ sốchuyểnđỉnh thoáiNgược Lấy tập chỉ số I này Ilà âm,0chuyểnIsang 1 Bước với tập tra số I này. Bước 2.I): 0Giải b) Ngược lại, I là tập chỉ số âm, (x là sang Bước 1.2 lại, một tập chỉ số b) hoá): I ( x ) với n hệ (3.2) 1.1. (Kiểm tra tính âm của tập chỉ số I):Bước 2.3. (3.2) với tập chỉ số I này. Bước với tập v củaIcạnh này bởi hệ. chỉ số này. Giải hệ chỉ số Xác I ( x0 ) hướng không(I1làkhác vàlấyphápchỉ số với rank{aBước 2.3. (Xác hữu hiệu kềvà đỉnh hữu hiệu kề 1.2.1. I định với I n a) Nếu hệBước 1.2. có nghiệm, số tập tuyến). Xác định cạnh và đỉnh này tập chỉ Bước 2.3.1. Xác định hướng v theo hệ: Bước 2.1. 0, i Î I programming. This object of định cạnh ai , = Tính i v :i I} This paper stidies multi-objective linear the study is a t tập chỉ số I I (tương ứng). n 1 khác và k x ) với I 0 quay trở lại bước 1.1 tương ứng nếu tập chỉ số I đang xét là tập chỉ số pháp b) Ngược lại, là số chỉachuyểnNếuprogrammingi \1.2n  1 ,, v0 = class of multi-objective  I x : , v a) 1, k =; a sang a số I lại, là của cạnh có số âm, chuyểnBước BướcÌ I (x 0 I i ( )  i problems with linear objective  I I 0, icác vectơ b) Ngượchướng vtập Ichỉ tập âm,nghiệm, alấyranksang tuyến).1.2nghĩaa multi-objective- 1này độcvà tuyến tính, chuyển là functions and lập a) Nếu Ihệ này không the constraint set isv polyherdron convex bởiThe purpose)ofvới định n 1. Xác (3.2) với tậplại, Isố 1.2.1. Xácnày bởi hệ. của cạnh này Giải hệ địnhNgược chỉ là tập chỉ số âm, chuyển sang bước 1.2 Bước I này. định hướng tập chỉ set.Bước 2.3.1. Xác I = hướng v theo hệ: hệ. khác b) b) Ngược là I là tập chỉ programming problem issang Bước 1.2 đỉnh hữu hiệu v Bước 1.2. (Ilại, tập chỉlinear phápBước 2.2. Xác định cạnh vàv theo hệ: ai ,kề 0, i I số âm, chuyển to định hướng sốBước tuyến). Xácsimultaneously optimize multiple objective 2.3.1. cạnh sang ihướngđịnh sang Bước 1.20, i hiệu kề Bước b) Ngượctập1, k chỉ0 tập hệI ;số âm,Xác0,v bậc 1.2. (Iklà (I lại, 2.3.1.pháp tuyến). Xác= đỉnh Bước 1.2. là tập sốcủa tuyến). chuyển cạnh ivà chỉ t pháp I  Xác trở a , n1.2. khác tập functions a ( x0 ) và ứng).Bước(Ikề tương ứng). that I 1 lại hiệu là k ( ) Bước 2.3.2. TìmvnghiệmlàIsốx0 chỉ bất a v,  hệ:, v a i , vi  hữu I định số I I tương đỉnh hữu =định,arevindependenteach;nhấton all admissible non-emptyhiệu kề quayvớiBướcBước 1.1.và chỉ\số pháp tuyến).IiXác\ I other cạnh0, đỉnh hữu domains. đẳng thức x 0 I 1, k  theo a of định  0 và I Tìm Bướcb) Ngược lại, lấy một tậpt0thức hệ I (nhất 0I thứckề 2.3.2. Tìm bất đẳng 2.3.2. Tìmbất vớit củanhệ bất đẳng thức lại Bước nghiệm t0 của Xác định chỉ số bậc x ) hữu Bước 2.3.2.chỉ số pháp tuyến). hệ nghiệm cạnh và đỉnh đẳnghiệu 1bậc nhất ương Ngược lại, I là(I là chỉ số The authorcạnh nàysang effective points to comecủa I a linear cone khác và quay b) ứng).Bước ứng). âm, định của âm,theii1.20atv,hệ.b , t bởi1.2,1,..., m1,..., m nghiệm Bước 1.2.1. Xác tập âm, chuyển 0 bởi of Bước Bước up with 1.2. tập hướng v ) , + tv  là i =hoặc  và đỉnh hữu hiệu ( củax hệtuyến)., Xác định cạnh tương ứng với kề hay c lại, I làtương 1.2.1. Xác định sang ax t t::của,xx + tvsangi ,Bước ,1.2i \ I 0 m \ I b) kchỉ số1.2.2.I ĐặtĐặt hướng chuyểni Ngược lại,1.2.2.tập ti msố Bước là 0 t m Bước , cạnh này tv t ,hệ. i tậpBước Bước=chỉ ax iv achuyểnx  b 0 i i i  1,..., uses a concepts i 0 0 b Bước 1.2.1.vXác định I x \algorithmacạnhthe multi-objective linear programming problem. tv bi , i 1,..., m a, 1, k  hướng v 2.1. , v nàyibởi hệ. bậc nhất: a , x tương ứng). = ;của to solve = I 0,  I i 2. Bước 1.2.Đặtlàtuyến).aiXác ,định1,cạnhcạnhđỉnh bởivhệ. 0, i  và đỉnh hữu hiệu kề chỉ sốtập (Ichỉ số pháp m \³ I b  x1,..., m định  (I pháp Xác chỉ hướng Bước tậpt min :  1,..., ; a , cạnh I (I là tập Bước 1.2. nghiệmtđịnha vnàyvkcủaI  và \Xác hữu hiệu kề 1.2.1. này i 0 I k i t0 , 0 0 i0, t.  t0 0 t0 0 Bước 1.2.2. Đặt là tập Đặtsố pháp tuyến). (Kiểmnày Đặtâm,củahoặc 0, tI): Giải thệ0 ứngvới tậpt chỉ số I hay t và 0 Bước 1.2.1. luận hướng v k II x \ I ; nghiệm cạnhhệ tra là tập nghiệm của hệ tương hoặc với tập I xBước;2.2.a , v này ibởi hệ. 0 tập chỉ số này là , (3.1) 0,t tương 0 này. của  tính Keywords: Multi-objective linear programming, linear objective function, linear t ơng ứng).nghiệm 1.2.2.Xácađịnh ]tương0a0,iv  t > 0 .của 0 i k 0 i , v 1, k  \ I0,  0 0 0 0 1.2.2. Đặt max ta) Nếu phận quan trọng của qui hoạch đa mục tiêu là qui hoạch tuyến tính đa hệ x 0 ttv  b, athìv0 ,1, tv0,tv một , t I ứng vớii tm