Đồ án Thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị của H.P. Benson

x2+ 733x3+ 610x4+ 305x5. Ngoài ra ta còn có các ràng (R) buộc sau: Đối với bếp : Đối với phòng ăn : Đối với phòng tắm : Đối với sảnh : Đối với phòng ngủ 1: Đối với phòng ngủ 2: Đối với phòng ngủ 3: Ràng buộc hình học (R): và . Chúng ta có bài toán tối ưu hai mục tiêu sau: Tìm sao cho max S(x1,x2,x3) min C(x1,x2,x3,x4,x5) với các ràng buộc R tức là với . Ví dụ 2.1.2. (Lập chế độ ăn kiêng) Giả sử cho trước danh sách các món ăn chính như thịt, cá, rau với những hàm lượng dinh dưỡng như đạm, mỡ, vitamin, lượng calo và giá cả...Chúng ta phải xác định khẩu phần để cực tiểu chi phí ăn uống, cực tiểu lượng calo và cực đại ngon miệng. Lập bài toán: Kí hiệu x1, x2, x3 là lượng thịt, cá, rau (tính bằng gram) cho mỗi khẩu phần. Hàm lượng dinh dưỡng, calo và giá cả của mỗi gram thức ăn nói trên được biết như sau Đạm Mỡ Vitamin Calo Giá Thịt P1 l1 v1 c1 Cá P2 l2 v2 c2 Rau P3 l3 v3 c3 Gọi G là chi phí cho mỗi khẩu phần: . Gọi C là số calo cho mỗi khẩu phần cung cấp: . Đối với sự ngon miệng T thường được đánh giá bởi tỷ lệ thịt cá so với rau: Ta nói khẩu phần (x1, x2, x3) ngon nếu , hay Khẩu phần (x1, x2, x3) ngon hơn khẩu phần (y1, y2, y3) nếu (x1-y1, x2-y2, x3-y3) bảo đảm tỷ lệ trên. Những ràng buộc đối với lượng dinh dưỡng (D): lượng đạm : lượng mỡ : lượng vitamin: Như vậy chúng ta có bài toán tối ưu đa mục tiêu sau: minG, minC, maxT với các ràng buộc D. Nhận xét: Trong hai ví dụ trên có mục tiêu đối kháng (như diện tích sử dụng và giá cả). Mục tiêu T ở ví dụ 2 không dễ xử lý vì không phải 2 phương án nào cũng so sánh được. 2.2. Mô hình toán học và cấu trúc tập nghiệm Một bộ phận quan trọng của qui hoạch đa mục tiêu là Qui hoạch tuyến tính đa mục tiêu, trong đó các hàm mục tiêu là tuyến tính và tập ràng buộc X là tập lồi đa diện. Bài toán qui hoạch tuyến tính đa mục tiêu được phát biểu như sau Vmax , (MOLP) trong đó C là ma trận cấp với , với các hàng và X là tập lồi đa diện trong . Trong bài toán qui hoạch tuyến tính (LP) thông thường như xét ở Chương I, hàm mục tiêu là hàm tuyến tính c: . Không gian giá trị (Outcome Space) của nó là R (tập các số thực) nên việc so sánh 2 giá trị nào đó chỉ đơn giản là việc so sánh 2 số thực. Ta luôn có hoặc hoặc . Nhưng với bài toán (MOLP) ta phải xét đồng thời p hàm mục tiêu c1, c2,…,cp, tức là xét toán tử tuyến tính C: . Không gian giá trị của bài toán (MOLP) là Rp không được sắp thứ tự toàn phần, tức là 2 phần tử v và w bất kỳ thuộc Rp không phải lúc nào cũng được so sánh với nhau. Do đó, nghiệm tối ưu thông thường không còn thích hợp. Thay vào đó, người ta đưa ra khái niệm nghiệm hữu hiệu dựa trên thứ tự từng phần. 2.2.1 Không gian với thứ tự từng phần Quan hệ 2 ngôi: Cho E là một tập hợp bất kỳ. Quan hệ 2 ngôi trên E là một cách chỉ ra phần tử có quan hệ với phần tử . Hình thức đó mà nói cho tập con B trong tập , khi đó x có quan hệ với y nếu . Cho B là một quan hệ 2 ngôi trong E ta nói B là phản xạ nếu với mọi , bắc cầu nếu và thì . Thứ tự từng phần: Cho E là một tập khác rỗng. Thứ tự từng phần trên E là một quan hệ 2 ngôi B có tính phản xạ, bắc cầu. Ta sẽ viết hoặc đơn giản nếu với B là thứ tự từng phần trên E. Khi ấy thay vì B ta viết thứ tự trên E. Nếu như E là một không gian tuyến tính và là một thứ tự từng phần trên E thì ta nói thứ tự này tuyến tính nếu kéo theo với mỗi và với mỗi . Người ta thường dùng thứ tự từng phần sau Cho 2 véc tơ & thuộc . Ta viết nếu , nếu , xọy nếu . 2.2.2 Nghiệm hữu hiệu, nghiệm hữu hiệu yếu. Định nghĩa 2.2.1 Một điểm được gọi là nghiệm hữu hiệu của bài toán (MOLP), nếu không tồn tại sao cho . Một điểm được gọi là nghiệm hữu hiệu yếu của bài toán (MOLP), nếu không tồn tại Cx ọ. Kí hiệu(tư, ) là tập tất cả các nghiệm hữu hiệu (tư, hữu hiệu yếu). Gọi (tư, ) là tập nghiệm hữu hiệu (tư, tập nghiệm hữu hiệu yếu) của bài toán qui hoạch tuyến tính đa mục tiêu. Cấu trúc của tập nghiệm hữu hiệu và tập nghệm hữu hiệu yếu được mô tả bởi Mệnh đề 2.2.1 Mệnh đề 2.2.1 (Xem Đ.T. Luc [4]) Tập nghiệm hữu hiệu (tập nghiệm hữu hiệu yếu) của bài toán qui hoạch tuyến tính đa mục tiêu là liên thông đường gấp khúc, bao gồm một số diện đóng của tập lồi đa diện ràng buộc X. 2.3 Lý do giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Việc giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian quyết định (decision space), tức là xác định một phần hoặc toàn bộ tập nghiệm hữu hiệu XE (hữu hiệu yếu XWE) bằng các phương pháp toán học mà không có bất cứ sự tham gia nào của người ra quyết định. Cho đến nay, đã có rất nhiều phương pháp đưa ra để giải bài toán này như: phương pháp vô hướng hoá, phương pháp tham số, phương pháp đơn hình đa mục tiêu và các dạng cải biên, phương pháp nón pháp tuyến…(xem [6, 7, 8-9, 12, 17, 18, 19, 21-22 và 24-25]). Như đã biết (theo Mệnh đề 2.2.1), tập nghiệm hữu hiệu (tư, hữu hiệu yếu) tuy luôn là liên thông đường gấp khúc, bao gồm một số diện đóng của tập lồi đa diện ràng buộc X , nhưng nói chung nó là tập không lồi và có cấu trúc rất phức tạp. Đó là lý do dẫn đến: Khối lượng tính toán để sinh ra một phần hoặc toàn bộ tập nghiệm hữu hiệu (tư, hữu hiệu yếu) tăng rất nhanh khi kích thước bài toán (tức số chiều n trong không gian quyết định Rn, số ràng buộc biểu diễn tập lồi đa diện X và số hàm mục tiêu p) tăng. Người ra quyết định khó chọn được nghiệm thích hợp nhất đối với họ trong tập nghiệm hữu hiệu đã được đưa ra. Trong những năm gần đây thay vì việc tìm trực tiếp tập nghiệm hữu hiệu XE trong không gian quyết định, một số tác giả đã nghiên cứu giải bài toán (MOLP) trong không gian giá trị Rp (xem [11, 27-28 và 32-35]) để tìm tập . Tiếp cận này dựa trên 3 lí do sau Trong các bài toán thực tế, thông thường pÚn (tức số chiều không gian giá trị nhỏ hơn nhiều so với số chiều của không gian quyết định ). Do đó tập luôn nhỏ hơn và có cấu trúc đơn giản hơn nhiều so với (xem [11, 27-28, 32-35]). Vì vậy, người ta hy vọng rằng việc xác định tất cả hay một phần sẽ đơn giản hơn việc xác định tất cả hay một phần . Kinh nghiệm thực tế cho thấy rằng, người ra quyết định sẽ dễ dàng hơn trong việc tìm nghiệm thích hợp với mình trong (xem [26-28]). ánh xạ C có thể biến nhiều điểm trong XE thành một điểm trong (xem [36-38]). 2.4 Kết luận Trong chương này, em đã trình bày về: mô hình toán học, khái niệm nghiệm hữu hiệu, hữu hiệu yếu của bài toán qui hoạch tuyến tính đa mục tiêu. Lý do giải bài toán (MOLP) trong không gian giá trị. Trong Chương III, em sẽ trình bày thuật toán xấp xỉ ngoài của H. P. Benson giải bài toán này. Chương III bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị Chương này dành để trình bày thuật toán xấp xỉ ngoài do Benson [5] đề xuất để giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Xét bài toán qui hoạch tuyến tính đa mục tiêu Vmax , (MOLP) trong đó: C là ma trận cấp với , là đa diện khác rỗng (tức tập lồi đa diện bị chặn), , A là ma trận cấp , . Tập giá trị (outcome set) của X trong không gian giá trị là . (1) Khi đó là đa diện khác rỗng (xem [43]). Định nghĩa 3.1.1 Một điểm được gọi là giá trị hữu hiệu của bài toán (MOLP) nếu . Kí hiệu là tập tất cả các giá trị hữu hiệu của bài toán (MOLP). Ta gọi là tập giá trị hữu hiệu. Mệnh đề 3.1.1 Nếu X là đa diện khác rỗng thì và được xác định bởi . (2) 3.1. Tương đương hữu hiệu Xét tập được xác định như sau , trong đó là véc tơ thoả mãn , với i=1, 2,…, p. Ví dụ 3.1.1: Xét , giả sử ta có tập . Hình 6. Ta xây dựng được tập như Hình 6 thoả mãn , ở đây . Định nghĩa 3.1.2 Một điểm được gọi là điểm hữu hiệu của Y khi và không tồn tại . Kí hiệu là YE là tập tất cả các điểm hữu hiệu của Y. Kết quả sau đây rất hữu ích cho việc xác định tập giá trị hữu hiệu YE (xem [32]). Định lý 3.1.1 Tập Y là một đa diện khác rỗng trong không gian , với thứ nguyên đầy (dimY=p). Hơn nữa, . Vì nên ta gọi đa diện Y là tương đương hữu hiệu với đa diện . Theo Định lý 3.1.1, Y là một đa diện khác rỗng trong , về lý thuyết thì luôn tồn tại ma trận D cấp và véc tơ , sao cho . (3) Giả sử ta biết được biểu diễn của Y theo (3) thì có thể áp dụng được các thuật toán giải bài toán qui hoạch tuyến tính đa mục tiêu đã có (xem [8-9, 12, 15, 18, 22 và 25]) giải bài toán Vmax (*) để tìm . Tuy nhiên, nói chung ta không xác định được ma trận D và véc tơ d như ở biểu diễn (3). Vì vậy, việc giải bài toán (*) theo hướng này vẫn là một câu hỏi. Phần còn lại của chương này dành để trình bày thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu trên để tìm . Đặt (tư, ) là tập tất cả các đỉnh của (tư, Y). Khi đó Định lý 3.1.2 (Xem Benson [32]) Đặt . Khi đó . Nhận xét 3.1.1 Theo Định lý 3.1.2 nếu biết được tập tất cả các đỉnh của Y thì dễ dàng nhận được tập tất cả các đỉnh hữu hiệu của tập giá trị hữu hiệu trong bài toán (MOLP). Để làm điều đó, đơn giản là loại trừ từ tập đỉnh của tập Y những điểm y sao cho có ít nhất một với i=1,..,p. Từ nhận xét này đưa đến việc xây dựng thuật toán xấp xỉ ngoài tìm tập đỉnh giá trị hữu của bài toán qui hoạch tuyến tính đa mục tiêu. 3.2 Cơ sở lý thuyết. Theo Định lý 3.1.2, ta có thể dễ dàng nhận được tập dỉnh hữu hiệu của tập trong không giá trị nếu biết tập tất cả các đỉnh của đa diện tương đương hữu hiệu Y. Việc xác định tập dỉnh của Y được tiến hành nhờ các kỹ thuật chính sau - Kỹ thuật xấp xỉ ngoài. - Kỹ thuật tìm tập đỉnh của một đa diện mới, đa diện này nhận được từ đa diện cũ trước đó (đã biết toàn bộ tập đỉnh) bằng cách thêm một ràng buộc mới. - Kỹ thuật phân hoạch đa diện bởi các đơn hình. 3.2.1 Kỹ thuật xấp xỉ ngoài. Kỹ thuật xấp xỉ ngoài là một kỹ thuật rất quen thuộc trong tối ưu toàn cục. Sau đây là thuật toán xấp xỉ ngoài tìm cực tiểu một hàm lõm trên một tập lồi đa diện. Cho là một đa diện khác rỗng, có thứ nguyên đầy (dimZ=q) , (4) trong đó F là ma trận cấp , . Giả sử rằng g là hàm lõm , ở đây G là tập lồi mở trong Rq và . Xét bài toán min. (CLP) Như đã biết, nghiệm của bài toán này đạt trên đỉnh của Z. Dưới đây là mô tả vắn tắt thuật toán xấp xỉ ngoài giải bài toán (CLP). Thuật toán 3.2.1 Bước khởi tạo: * Xác định . * Xây dựng đa diện khác rỗng có cấu trúc đơn giản (đơn hình, siêu hộp...) sao cho và dễ xác định được tập đỉnh V(Q0) của Q0. * Xác định argmin. * Đặt . * Gán k:=0 và chuyển tới Bước lặp k. Bước lặp k: (k=0,1,2,…) Bước k1: + Nếu thì dừng thuật toán: là nghiệm cực tiểu của g trên Z. + Ngược lại, tiếp tục. Bước k2: Tìm giá trị sao cho thuộc biên của Z. Bước k3: + Đặt , ở đây là hàng thứ của ma trận F, thoả mãn . + Tính tập đỉnh V(Qk+1) của đa diện . Bước k4: + Xác định argmin. + Đặt . + Gán k:=k+1, quay lại Bước lặp k. Chú ý Trong Bước k2, nếu thì . Độ dài đoạn thẳng . Để thì độ dài là nhỏ nhất. Tức ta xét bài toán sau min, với điều kiện , hay min, với điều kiện . (Ch) (Ch), i=1,...,h , i=1,...,h , i=1,...,h. Đặt , thì phải thoả mãn . Do đó . Trong mỗi bước lặp có một bất đẳng thức tuyến tính của (4) được đưa vào trong Bước k3. Và với mỗi bước lặp k là một bất đẳng thức tuyến tính khác nhau (xem [34, 35]). Do đó, phương pháp xấp xỉ ngoài là hữu hạn. Trong trường hợp xấu nhất, nó sẽ dừng sau h bước lặp với , và là giá trị nhỏ nhất của g trên Z. Trong trường hợp này V(Qk+1) chứa toàn bộ các đỉnh của Z. Bài toán cơ bản của Thuật toán 3.2.1 là việc xác định tập đỉnh V(Qk+1) của đa diện , trong đó , với hàm affine và tập đỉnh của đa diện đã biết. Vấn đề này sẽ được trình bày trong phần 3.2.2. 3.2.2 Bài toán tìm đỉnh của tập lồi đa diện Một cách tổng quát ta xét tập lồi đa diện xác định bởi hệ bất đẳng thức tuyến tính có dạng , (4) trong đó và . Giả sử ta đã biết: U- là tập đỉnh của M, V- là tập phương các cạnh vô hạn của M, nghĩa là ta có thể biểu diễn M=convU+coneV. Giả thiết rằng (tập lồi M có đỉnh), còn V có thể rỗng (khi M là đa diện lồi). Cho hàm afine: . Đặt , (5) khi đó N cũng là một tập đa diện. Bài toán đặt ra là xác định tập đỉnh P của N. Để giải quyết bài toán này , kí hiệu , (6) , (7) Các mệnh đề sau tạo cơ sở lý luận cho việc giải quyết bài toán. Mệnh đề 3.2.1 Giả sử . Khi đó N=M, nghĩa là P=U. Chứng minh Theo giả thiết thì thì thì , mà ta có thể biểu diễn , trong đó , tức là Ngược lại nếu hay . Do vậy N=M. Mệnh đề 3.2.2 Giả sử . Khi đó: Nếu thì , nghĩa là . Nếu thì . Chứng minh Do và có nghĩa là và , với mỗi ta có . Vậy . Do và có nghĩa là và . Vì thế nghĩa là . Do vậy , hay . Chứng tỏ trong trường hợp này N là một diện của M. Cho nên mỗi đỉnh của N cũng là đỉnh của M. Do vậy ta có . Mệnh đề 3.2.3: Giả sử và khi đó . Mỗi đỉnh là giao điểm của siêu phẳng H với một cạnh hữu hạn của M (nối liền một đỉnh thuộc và một đỉnh thuộc ) hoặc với một cạnh vô hạn của M xuất phát từ một đỉnh () và đi theo một phương thuộc (). Chứng minh a) Mọi sẽ không thuộc N (do ), nên càng không thuộc P. Trái lại, sẽ thuộc N (do ), nên vẫn còn là đỉnh của N do vậy . b) Giả sử thì w thoả mãn chặt n ràng buộc độc lập tuyến tính trong đó có h0(w)=0. Kí hiệu I là tập chỉ số n-1 ràng buộc còn lại: . Khi đó là diện nhỏ nhất của M chứa w. Vì nên . Vì thế dimF(w) =1, và F(w) là một cạnh của M. Xét 2 khả năng: *) Hoặc với F(w) là một cạnh hữu hạn của M. Chẳng hạn, với , thì . Khi đó với , thì . Do đó . *) Hoặc với F(w) là một cạnh vô hạn của M. Chẳng hạn, , . Khi đó với w=u+tv, t>0 thì . Suy ra do đó ta được điều cần chứng minh. Dựa trên mệnh đề 3.2.3, ta có thể tìm được đỉnh (thuộc P\U) mới của N trong trường hợp và như sau Qui tắc tìm tập đỉnh mới của N Với mỗi cặp ta tính điểm . Với mỗi cặp ta tính điểm . Với mỗi điểm w được xác định theo a) hoặc b) kí hiệu . Có thể thấy rằng trong trường hợp a) , còn trong trường hợp b) . Nếu hoặc tồn tại một đỉnh (trong trường hợp a) hoặc (trong trường hợp b) sao cho với mọi , w không thể là đỉnh của N nghĩa là . Ngược lại w là đỉnh của N sao cho . Trường hợp M là đa diện lồi () thì dĩ nhiên N cũng là đa diện lồi và việc tìm tập đỉnh P của N được đơn giản hơn nhiều. Cụ thể ta có: Hệ quả Cho M là một đa diện lồi với tập đỉnh U và N nhận được từ M theo (5) với tập đỉnh P. Khi đó với U+, U- xác định theo (6), (7) ta có: Nếu thì N=M, nghĩa là P=U. Nếu thì , nghĩa là , khi và khi . Nếu , . Khi đó và với mỗi là giao điểm của siêu phẳng h0(x)=0 với một cạnh của M nối liền một đỉnh thuộc U- và một đỉnh thuộc U+. Trong phần phụ lục, em sẽ giới thiệu chương trình tìm đỉnh của tập lồi đa diện trong trường hợp M là đa diện lồi. Ví dụ 3.2.1 Giải bài toán qui hoạch lõm , là tập nghiệm của hệ (D) áp dụng kỹ thuật xấp xỉ ngoài để giải bài toán qui hoạch lõm trên. Trong lời giải em sẽ sử dụng chương trình ở phần Phụ lục để tìm tập đỉnh của đa diện lồi. Hình 7. Giải : Bước khởi tạo: D=conv(G, H, C, D, E, F). Gán . Xây dựng đơn hình Q0=conv, với tập ràng buộc , với tập đỉnh . f(O)=0, f(B)=-300, f(A)=-200. LB0:=-300, z0=(10,0). Bước lặp 1: . (loại), (loại), (loại), , (loại), (ràng buộc ) (loại). (ràng buộc ) . =conv. Xác định bằng chương trình với: - Tập ràng buộc . - Tập đỉnh . - Hàm affine . Kết quả . f(O)=0, f(A)=-200, f(E)=-165, f(D)=-48. LB1:=-200, z1=(0,10). Bước lặp 2: . (loại), (loại), =0.6315, (loại), (loại), (loại). . =conv. Xác định bằng chương trình với: - Tập ràng buộc . - Tập đỉnh . - Hàm affine . Kết quả . f(O)=0, f(G)=-32, f(E)=-165, f(F)=-120, f(D)=-48. LB2:=-165, z2=(7,3). Bước lặp 3: , z2=(7,3) là nghiệm của bài toán, dừng thuật toán. fmin(x)=-165. 3.2.3 Phân hoạch đa diện bởi các đơn hình Kỹ thuật phân hoạch các đa diện thành các đơn hình đóng vai trò cơ bản trong thuật toán xấp xỉ ngoài để tìm các giá trị hữu hiệu YE. Mục này dành để trình bày kỹ thuật phân hoạch đơn hình của Ban (xem [39-40]). Trước hết xin nhắc lại khái niệm phân hoạch và phép chia đôi (xem [41]). Định nghĩa 3.2.1 Cho là một đa diện khác rỗng, có thứ nguyên đầy đủ (dimZ=q), và I là tập hữu hạn các chỉ số. Tập các tập con gọi là một phân hoạch của Z nếu , và , trong đó là biên của Qi, . Định nghĩa 3.2.2 Cho là q-đơn hình (dimM=q) với tập đỉnh . Giả sử , trong đó . Gọi M1 (tư, M2) là đơn hình mà tập đỉnh thu được từ M bằng cách thay thế up (tư, ut) bởi v. Khi đó được gọi là phép chia đôi M tương ứng với v. Ví dụ 3.2.2 Trong không gian 2 chiều, xét đơn hình M có các đỉnh u1, u2, u3. Đặt , . Hình 8 mô tả phép chia đôi đơn hình M thành 2 đơn hình . Tập đỉnh u3 M1 v M2 u1 u2 Hình 8. Nhận xét 3.2.1 Rõ ràng phép chia đôi M thành bởi v trong Định nghĩa 3.2.2 là một phân hoạch của M trong Định nghĩa 3.2.1 (xem [41]). Khái niệm một đơn hình là tầm thường với một đa diện dưới đây rất hữu ích trong kỹ thuật phân hoạch đơn hình của Ban. Định nghĩa 3.2.3 Cho là q-đơn hình với tập đỉnh . Khi đó M được gọi là tầm thường (trivial with respect to Z) với Z nếu với mỗi k=1,2,…,h thì với mọi . Ví dụ 3.2.3: Trong , Hình 9a) và 9b) mô tả M là tầm thường với Z. Trong Hình 9c) thì M là không tầm thường với Z . Z M M Z M Z a) b) c) Hình 9. Mệnh đề 3.2.4 (xem [40]). Cho là q-đơn hình với tập đỉnh . Nếu M là tầm thường với Z thì là diện (đơn hình con) của M và . Ví dụ 3.2.4 Cho đa diện Z và đơn hình M như Hình 8. u2 M u1 M u2 u3 Z u3 Z u1 a) b) Hình 10. Theo Mệnh đề 3.2.4 thì trong Hình 10a: . Hình 10b: . Mục đích của thuật toán Ban là xây dựng một phân hoạch tập Z, trong đó mỗi đều là các đơn hình tầm thường với . ý tưởng của thuật toán có thể mô tả như sau +) Trước hết xây dựng một q-đơn hình . +) Lặp lại phép chia đôi đơn hình, phân hoạch bởi các q-đơn hình con, trong đó mỗi q-đơn hình con này là tầm thường với Z. +) Cuối cùng, ta sẽ nhận được một phân hoạch của Z cũng gồm các đơn hình con có dạng , trong đó M là một q-đơn hình con trong phân hoạch cuối cùng của . Thuật toán 3.2.2 (Thuật toán phân hoạch Z thành các đơn hình). Bước khởi tạo. + Xây dựng q-đơn hình . + Đặt . + Gán k:=1, chuyển tới Bước lặp k. Bước lặp k , () Bước k1: Tìm một q-đơn hình MPM0 thoả mãn M có một cặp đỉnh sao cho . (8) + Nếu không tìm được đơn hình nào như vậy thì * Nếu thì (loại đơn hình M ra khỏi PM0). * Gán k:=k+1. * Chuyển tới Bước k4. + Nếu tìm được M thì * . * Chuyển tới Bước k2. Bước k2: + Tìm giá trị , , thoả . + Gán . Bước k3: + Gán , trong đó là hai đơn hình con nhận được từ việc chia đôi M bởi điểm chia v . + Quay lại Bước k1. Bước k4: + Nếu , quay lại Bước lặp k. + Ngược lại, dừng thuật toán. Nhận xét 3.2.2 +) Nếu không tìm được các cặp đỉnh thoả (8) có nghĩa là mọi đơn hình con thuộc đều nằm về một phía nào đó của siêu phẳng . +) Bất đẳng (8) có nghĩa là hai đỉnh nằm ở hai phía của ràng buộc thứ k của Z. Ví dụ 3.2.5 Giả sử tập Z, M0 được cho như Hình 11. Hình 11. *) Đa diện . *) Đơn hình . Dễ thấy Z là tập nghiệm của 4 bất đẳng thức . Hiển nhiên . Bước lặp 1 (Tức xét ràng buộc thứ (1)). Đơn hình M0 có các đỉnh O, M, N. Cặp đỉnh O, M nằm 2 phía của ràng buộc (1) nên . Tìm được điểm P. Chia M0 bởi P được , . Khi đó . Xét đơn hình có các đỉnh M, P, N. Cặp đỉnh M, N nằm 2 phía của ràng buộc (1). Do vậy và ta tìm được điểm Q chia thành , . Khi đó . Xét không có cặp đỉnh nào thoả (8). Xét không có cặp đỉnh nào thoả (8) và , do đó . Xét không có cặp đỉnh nào thoả (8). Chuyển qua Bước lặp 2. Bước lặp 2,3,4 Đối với các ràng buộc (2), (3), (4) thì cũng không có cặp đỉnh nào thoả (8). Kết thúc thuật toán thu được , là tầm thường với Z. Định lý 3.2.1 Kỹ thuật phân hoạch đơn hình là hữu hạn, và thuật toán dừng với phân hoạch của Z, trong đó J là tập hữu hạn các chỉ số, và là các q-đơn hình trong phân hoạch PM0 của M0 tại thời điểm thuật toán dừng. Mỗi là tầm thường với Z. Mỗi đỉnh là một đỉnh của một q-đơn hình trong tập mà . Chứng minh ở đây chỉ trình bày chứng minh phần b) của Định lý 3.2.1. Chứng minh phần a) có thể xem trong [40]. Lấy . Theo phần a) của Định lý, ta có thể chọn một q-đơn hình sao cho và M là tầm thường với Z. Giả sử là các đỉnh của M. Chọn tập chỉ số I sao cho . Theo Mệnh đề 3.2.4 ta có . (9) Giả sử rằng, với mỗi . Vì nên từ (9) ta có , , và có ít nhất 2 phần tử của là dương. Do đó không phải là đỉnh của Z. Điều này mâu thuẫn với giả thiết phản chứng, ta nhận được điều cần chứng minh. Nhận xét 3.2.3 Theo Định lí 3.2.1, kỹ thuật phân hoạch đơn hình được sử dụng như là một phương pháp hữu hạn để tìm tất cả các đỉnh của Z. Khi kết thúc thuật toán phân hoạch đơn hình thì thu được tập các q-đơn hình . Do đó, với mỗi ta phải kiểm tra xem mỗi đỉnh u của Mj có phải là đỉnh của Z không. Với mỗi đỉnh u của q-đơn hình là đỉnh của Z khi và chỉ khi u thoả mãn chặt (tức thoả với dấu “=”) q hay nhiều hơn ràng buộc trong biểu diễn (4). Theo phần b) Định lý 3.2.1, tất cả các đỉnh của Z đều có thể tìm được theo cách này. Chú ý Trong Bước k2 của Thuật toán 3.2.2 thì được tính bởi công thức . Vấn đề quan trọng trong kỹ thuật phân hoạch đơn hình là xác định được q-đơn hình trong bước khởi tạo. Mục đích của thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu (MOLP) trong không gian giá trị (như sẽ trình bày chi tiết ở phần sau), là tìm tập đỉnh hữu hiệu của tập giá trị . Nhắc lại . là tập hữu hiệu và là tập đỉnh của . Kết quả sau đây chỉ ra cách xây dựng q-đơn hình và , trong đó Y là đa diện tương đương hữu hiệu với . Kí hiệu (tất cả các thành phần của e đều bằng 1), ta có Định lý 3.2.2 (Xem Benson [32]). Đặt . Với mỗi , véc tơ được xác định bởi trong đó . Đặt . Khi đó S là p-đơn hình trong Rp với tập đỉnh và . Hơn nữa S có biểu diễn . (10) Ví dụ 3.2.6 Giả sử ta đã xây dựng được tập Y như Hình 12, là nghiệm của hệ Ta xây dựng đơn hình như sau Hình 12. Đặt , . Bài toán qui hoạch tuyến tính , đạt nghiệm tại (2,5) và giá trị cực đại . Theo Định lý 3.2.2 thì Như vậy . Rõ ràng S là đơn hình trong R2 với tập đỉnh , hơn nữa S có thể biểu diễn Định lý 3.2.3 cho phép: +) Kiểm tra một điểm có thuộc đa diện tương đương hữu hiệu Y không +) Cho điểm trên biên của Y. Xác định một bất phương trình tuyến tính trong biểu diễn (10) mà phụ thuộc vào w. Định lý 3.2.3 (Xem Benson [32]) Cho . Đặt h(w) là giá trị tối ưu của bài toán qui hoạch tuyến tính max t, (Qw) với điều kiện , Ax=b, , trong đó nếu miền ràng buộc là tập rỗng. Khi đó a) Nếu , thì khi và chỉ khi . Trong trường hợp này . b) Nếu và w là điểm biên của Y, thì với mọi , , ở đây và là nghiệm tối ưu của bài toán qui hoạch tuyến tính đối ngẫu của bài toán (Qw). 3.3. Thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị. Thuật toán xấp xỉ ngoài sử dụng các kết quả của phần 3.2 để tìm tập là tập tất cả các đỉnh hữu hiệu của tập giá trị của bài toán qui hoạch tuyến tính đa mục tiêu (MOLP). Theo Định lý 3.1.2 thì tập E được xác định . Dưới đây là thuật toán xấp xỉ ngoài xác định tập E. Thuật toán 3.3.1 Thuật toán xấp xỉ ngoài. Bước khởi tạo. * Xác định . * Xây dựng p-đơn hình , mô tả ở như Định lý 3.2.2. * Tìm tập đỉnh và các bất đẳng thức ràng buộc như ở (10). * Gán và k:=0. * Chuyển tới Bước lặp k. Bước lặp k, . Bao gồm từ Bước k1 tới Bước k6: Bước k1: Nếu với mọi thoả mãn thì chuyển tới Bước k6. Ngược lại, chọn sao cho và tiếp tục. Bước k2: Tìm giá trị , sao cho thuộc biên của Y. Bước k3: Gán . Trong đó là nghiệm tối ưu của bài toán qui hoạch đối ngẫu của bài toán với (xem Định lý 3.2.2). Bước k4: Tính tập đỉnh nhờ và ràng buộc . Bước k5: * Gán k:=k+1. * Quay lại Bước lặp k. Bước k6: Gán . Dừng thuật toán, E là tập tất cả các đỉnh hữu hiệu của . Chú ý Điểm trong Bước khởi tạo có thể được tìm nhờ bài toán qui hoạch tuyến tính . Chẳng hạn, nếu ta đặt , trong bài toán (Qw). Trong đó, với mỗi , , thì với một nghiệm tối ưu của bài toán , có thể chỉ ra rằng, nếu là tổ hợp lồi chặt của và thì . Điều này cho phép ta xác định những điểm trong intY. Trong Bước k1, áp dụng Định lý 3.2.3 a) với để kiểm tra mỗi điểm có thuộc Y không. Trong Bước k2, giá trị có thể được tìm tương tự như tìm giá trị ở Bước k2 trong Thuật toán 3.2.1 (kỹ thuật xấp xỉ ngoài). Trong Bước k4, tập đỉnh được tìm nhờ 1 trong 2 phương pháp: áp dụng kỹ thuật xấp xỉ ngoài để tìm tập đỉnh nhờ biết tập ràng buộc Qk, tập đỉnh và hàm affine . áp dụng Thuật toán 3.2.2 (thuật toán phân hoạch đơn hình) đối với . Đặt là phân hoạch đơn hình của Z sau khi dừng thuật toán. Sử dụng , áp dụng Định lý 3.2.1 kết hợp Nhận xét 3.2.3 để xác định . Định lý 3.3.1 Thuật toán xấp xỉ ngoài là hữu hạn. Khi thuật toán dừng thì thu được tập E, là tập tất cả các đỉnh hữu hiệu của tập giá trị của bài toán (MOLP). Chứng minh Trong Bước k4, bao giờ cũng xác định được , khi biết trước tập ràng buộc Qk, tập đỉnh và một ràng buộc . Trong Bước khởi tạo, việc xây dựng p-đơn hình chứa Y, là hoàn toàn có thể thực hiện theo Định lý 3.2.2. Từ Định lý 3.2.3 b), với mỗi thì véc tơ được đưa ra trong bước k3 thoả với mọi , và ở đây là điểm biên của Y tìm được trong Bước k2. Như vậy thuật toán xấp xỉ ngoài là hữu hạn. Trong trường hợp xấu nhất, sau một số hữu hạn bước lặp , thì tập thu được từ thuật toán xấp xỉ ngoài sẽ bằng Y. Với kết quả này, thì trong Bước k1 của thuật toán thì với mọi đều thoả và chuyển tới Bước k5. Thuật toán dừng tại đây và thu được tập E (theo Định lý 3.1.2)- là tập tất cả các đỉnh hữu hiệu của . 3.3 Kết luận Trong chương này, em đã trình bày thuật toán xấp xỉ ngoài xác định tập đỉnh hữu hiệu của bài toán qui hoạch tuyến tính đa mục tiêu. Kết luận chung Trong đồ án tốt nghiệp này, em đã trình bày thuật toán xấp xỉ ngoài giải bài toán qui hoạch tuyến tính đa mục tiêu nhằm xác định tập đỉnh hữu hiệu của tập giá trị. Như đã biết có thể giải bài toán này trong không gian quyết định để xác định một phần hoặc toàn bộ tập nghiệm hữu hiệu. Nhưng nói chung khi sử dụng các phương pháp này thường gặp phải những khó khăn như: Khối lượng tính toán tăng nhanh khi kích thước của bài toán tăng. Mặc dù tập nghiệm hữu hiệu là liên thông đường gấp khúc và bao gồm một số diện đóng của tập ràng buộc nhưng nói chung nó là tập không lồi và rất khó cho người ra quyết định chọn được nghiệm thích hợp. Phụ lục Cho tập lồi đa diện xác định bởi hệ bất đẳng thức tuyến tính có dạng , trong đó và . Giả sử ta đã biết: U- là tập đỉnh của M và hàm affine . Đặt , khi đó N cũng là một tập đa diện. Bài toán đặt ra là xác định tập đỉnh P của N. Bài toán này thường đóng vai trò quan trọng trong tối ưu toàn cục, đặc biệt trong các phương pháp xấp xỉ ngoài: như giải bài toán qui hoạch lõm, bài toán tìm lớp tương đương hữu hiệu... ở đây em chỉ mới viết chương tìm đỉnh của đa diện lồi (nghĩa là đối với trường hợp tập lồi đa diện bị chặn). Đối với trường hợp tập lồi đa diện, em sẽ tiếp tục nghiên cứu trong thời gian tới. Sau đây là phần giới thiệu chương trình và ví dụ được chạy trên máy. Chương trình tìm đỉnh của tập lồi đa diện được viết bằng ngôn ngữ lập trình Delphi 6.0 chạy trên máy tính PC. Giao diện của chương trình: Sau khi khởi động, chương trình chạy hiện ra: Trong chương trình này có 2 menu: File: New Input (tạo số liệu mới), Open Input (Mở số liệu từ một file có trước), Save Input (Lưu số liệu nhập vào), Save Input as (Lưu số liệu vào một tên file khác), Run (chạy để tìm kết quả khi đã nhập số liệu vào), Close (đóng công việc giải toán), Exit (thoát khỏi chương trình). Help: Intruction (Giới thiệu về bài toán), How to use (Cách sử dụng chương trình), About. Sau khi nhập số liệu xong (hoặc mở từ một file có sẵn): Lấy số liệu của Ví dụ 3.2.1 (ở Bước lặp 1). Kích chuột vào "Kết quả" hoặc kích File-Run. Form kết quả hiện ra: Thu được tập đỉnh (0,0), (0,10), (4,0), (7,3). Chương trình nguồn Unit Unit1; Interface Uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,Dialogs, Grids, StdCtrls, ExtCtrls,strutils, unit2,unit3, Menus, ComCtrls,ToolWin; Const max=30; Type intmt=array[1..max] of integer; mt=array[1..max, 1..max]of double; vt=array[1..max] of double; Tf1 = class(TForm) grdAB: TStringGrid; gridaffine: TStringGrid; grdDinh: TStringGrid; Label1: TLabel; txtn: TEdit; txtm: TEdit; Label2: TLabel; Label3: TLabel; Label4: TLabel; Label5: TLabel; Label6: TLabel; txtsd: TEdit; grdb: TStringGrid; grdb0: TStringGrid; ButtonKetqua: TButton; Buttonthoat: TButton; MainMenu1: TMainMenu; File1: TMenuItem; NewInput1: TMenuItem; OpenInput1: TMenuItem; SaveInput1: TMenuItem; Saveas1: TMenuItem; N1: TMenuItem; Run1: TMenuItem; N2: TMenuItem; Exit1: TMenuItem; Help1: TMenuItem; Introduction1: TMenuItem; Howtouse1: TMenuItem; N3: TMenuItem; About1: TMenuItem; OpenDialog1: TOpenDialog; SaveDialog1: TSaveDialog; OpenDialog2: TOpenDialog; Close1: TMenuItem; Redit1: TRichEdit; Redit2: TRichEdit; procedure grdABClick(Sender: TObject); procedure gridaffineClick(Sender: TObject); procedure grdDinhClick(Sender: TObject); procedure grdbClick(Sender: TObject); procedure grdb0Click(Sender: TObject); procedure ButtonKetquaClick(Sender: TObject); procedure ButtonthoatClick(Sender: TObject); procedure NewInput1Click(Sender: TObject); procedure OpenInput1Click(Sender: TObject); procedure SaveInput1Click(Sender: TObject); procedure Saveas1Click(Sender: TObject); procedure Show1Click(Sender: TObject); procedure Run1Click(Sender: TObject); procedure Exit1Click(Sender: TObject); procedure Close1Click(Sender: TObject); procedure About1Click(Sender: TObject); Private { Private declarations } Public { Public declarations } End; Var f1: Tf1; m,n,sd:integer; A,D:mt; Ud,Ua:intmt; A0,b,a1:vt; b0:real; TenKetqua,Tenfile: String; IdData: Integer; {0- NewData; 1-OldData} implementation {$R *.dfm} {---------------------------------------------} procedure Tf1.grdABClick(Sender: TObject); var i:integer ; begin n:=strtoint(txtn.Text); m:=strtoint(txtm.Text); grdAB.ColCount:=n+1; grdAB.RowCount:=m+1 ; grdAB.Cells[0,0]:='A'; for i:= 1 to n do grdAB.Cells[i,0]:=inttostr(i); for i:= 1 to m do grdAB.Cells[0,i]:=inttostr(i); end; procedure Tf1.gridaffineClick(Sender: TObject); var i:integer; begin gridaffine.ColCount:=n; for i:=0 to n-1 do gridaffine.Cells[i,0]:='a'+inttostr(i); end; {-----------------------------------------------------} procedure Tf1.grdDinhClick(Sender: TObject); var i:integer; begin sd:=strtoint(txtsd.Text); grdDinh.ColCount:=n+1; grdDinh.RowCount:=sd+1; grdDinh.Cells[0,0]:='d'; for i:= 1 to n do grdDinh.Cells[i,0]:=inttostr(i); for i:= 1 to sd do grdDinh.Cells[0,i]:=inttostr(i); end; {-------------------------------------------------} procedure Tf1.grdbClick(Sender: TObject); var i:integer; begin grdb.RowCount:=m; for i:=0 to m-1 do grdb.Cells[0,i]:='b'+ inttostr(i+1)+' ='; end; {----------------------------------------------} procedure Tf1.grdb0Click(Sender: TObject); begin grdb0.Cells[0,0]:='b0 =' end; {---------------------------------------------} Procedure dinh_thu_k(d:mt;k:integer;var x:vt); Var i:integer; Begin For i:=1 to n do x[i]:=d[k,i]; End; {---------------------------------------------} Function tich(x1,x2:vt):real; Var i:integer; v:real; Begin v:=0; for i:=1 to n do v:=v+x1[i]*x2[i]; tich:=v; End; Function Ha(x:vt):real; Var j:integer; v:real; Begin v:=0; For j:=1 to n do v:=v+a0[j]*x[j]; ha:=v-b0; End; {-----------------------------------------------} Function t(u1,u2:vt):real; Begin t:=Ha(u2)/(Ha(u2)-Ha(u1)); End; {-------------------------------------------------} Procedure Tinh_tap_U(d:mt;var Ua,Ud:intmt;var j,k:integer); Var d1:vt; i:integer; Begin j:=1;k:=1; For i:=1 to sd do Begin dinh_thu_k(d,i,d1); If Ha(d1)>0 then begin Ud[j]:=i; j:=j+1; end; if ha(d1)<0 then begin Ua[k]:=i; k:=k+1; end; End; End; {-----------------------------------------------} procedure Tf1.ButtonKetquaClick(Sender: TObject); Var Ud,Ua:intmt; vt1,vt2,vt3,w:vt; j,k,i,i1,i2,i3,i4,i5,bi,tt:integer; gt:real; Begin f2.grdkq.Show; f2.l1.Hide; for i:=1 to m do for j:=1 to n do A[i,j]:=strtofloat(grdAB.Cells[j,i]); for i:= 0 to m-1 do b[i+1]:=strtofloat(grdb.Cells[1,i]); for i:= 0 to n-1 do A0[i+1]:=strtofloat(gridaffine.Cells[i,1]); b0:=strtofloat(grdb0.Cells[1,0]); for i:= 1 to sd do for j:=1 to n do d[i,j]:=strtofloat(grdDinh.Cells[j,i]); f2.grdkq.ColCount:=n+1; f2.grdkq.RowCount:=m+sd; f2.grdkq.DefaultColWidth:=80; for i:=0 to (m+sd) do for j:=0 to n do f2.grdkq.Cells[j,i]:=''; f2.Show; tinh_tap_U(d,Ua,Ud,j,k); If j=1 then {điều kiện Ud bằng rỗng} Begin f2.l1.Hide; for i1:=1 to sd do begin f2.grdkq.Cells[0,i1-1]:='d '+inttostr(i1); for i2:=1 to n do f2.grdkq.cells[i2,i1- 1]:=floattostr(d[i1,i2]); end; End; If k=1 then {điều kiện Ua bằng rỗng} begin i5:=1; if j-1=sd then {điều kiện Ud=U} begin f2.grdkq.Hide; f2.l1.show; end else begin f2.l1.Hide; For i:=1 to sd do Begin for i1:=1 to j-1 do if Ud[i1]=i then begin tt:=i1;{đề phòng phần tử Ud[1]=i} break; end else tt:=i1; if tt=j-1 then if iUd[tt] then begin f2.grdkq.Cells[0,i5- 1]:='d '+inttostr(i5); for i2:=1 to n do f2.grdkq.cells[i2,i5-1]:=floattostr(d[i,i2]); i5:=i5+1; end; End; End; end; If (j1) and (k1) then {Dieu kien Ua & Ud khac rong} Begin f2.l1.Hide; i5:=1; For i:=1 to sd do Begin for i1:=1 to j-1 do if Ud[i1]=i then begin tt:=i1; break ; end else tt:=i1; if tt=j-1 then if iUd[tt] then begin f2.grdkq.Cells[0,i5-1]:='d '+inttostr(i5); for i2:=1 to n do f2.grdkq.cells[i2,i5- 1]:=floattostr(d[i,i2]); i5:=i5+1; End; End; for i1:=1 to k-1 do for i2:=1 to j-1 do begin dinh_thu_k(d,Ua[i1],vt1); dinh_thu_k(d,Ud[i2],vt2); gt:=t(vt1,vt2); for i:=1 to n do w[i]:=gt*d[Ua[i1],i]+(1- gt)*d[Ud[i2],i]; i4:=0; for i:=1 to m do begin for i3:=1 to n do vt3[i3]:=a[i,i3]; if abs(tich(w,vt3)-b[i]) <0.001 then i4:=i4+1; end; if i4=n-1 then begin f2.grdkq.Cells[0,i5-1]:='d' +inttostr(i5); for i:=1 to n do f2.grdkq.cells[i,i5-1] :=floattostr(w[i]); i5:=i5+1; end; end; End; end; {-------------------------------------------------} procedure Tf1.ButtonthoatClick(Sender: TObject); begin close; end; {---------------------------------------------------}; procedure Tf1.NewInput1Click(Sender: TObject); var i,j:integer; begin redit1.Visible:=false; redit2.Visible:=false; { Show bằng edit new data} txtn.Text:=''; txtm.Text:=''; txtsd.Text:=''; for i:=1 to 10 do for j:=1 to 10 do grdab.Cells[i,j]:=''; for i:=1 to 10 do for j:=1 to 10 do grddinh.Cells[i,j]:=''; for j:=0 to 10 do grdb.Cells[1,j]:=''; for i:=0 to 10 do gridaffine.Cells[i,1]:=''; grdb0.Cells[1,0]:=''; end; {-------------------------------------------------} procedure Tf1.OpenInput1Click(Sender: TObject); var f:textfile; i,j:integer; begin {open file} If OpenDialog1.execute then Tenfile:= OpenDialog1.FileName; assignfile(f,tenfile); reset(f); readln(f,n,m,sd); grdAB.ColCount:=n+1; grdAB.RowCount:=m+1 ; grdAB.Cells[0,0]:='A'; for i:= 1 to n do grdAB.Cells[i,0]:=inttostr(i); for i:= 1 to m do grdAB.Cells[0,i]:=inttostr(i); grdb.RowCount:=m; for i:=0 to m-1 do grdb.Cells[0,i]:='b'+ inttostr(i+1)+' ='; gridaffine.ColCount:=n; for i:=0 to n-1 do gridaffine.Cells[i,0]:='a'+inttostr(i); grdDinh.ColCount:=n+1; grdDinh.RowCount:=sd+1; grdDinh.Cells[0,0]:='d'; for i:= 1 to n do grdDinh.Cells[i,0]:=inttostr(i); for i:= 1 to sd do grdDinh.Cells[0,i]:=inttostr(i); redit1.Visible:=false; redit2.Visible:=false; txtn.Text:=inttostr(n); txtm.Text:=inttostr(m); txtsd.Text:=inttostr(sd); for i:=1 to m do begin for j:=1 to n do read(f,a[i,j]); readln(f,b[i]); end; for i:=1 to n do read(f,a0[i]); readln(f,b0); for i:=1 to sd do begin for j:=1 to n do read(f,d[i,j]); readln(f); end; closefile(f); {Hiện ma trận ràng buộc} for i:=1 to m do for j:=1 to n do grdab.Cells[j,i]:=floattostr(a[i,j]); for i:=0 to m-1 do grdb.Cells[1,i]:=floattostr(b[i+1]); {Hiện hàm affine} for i:=0 to n-1 do gridaffine.Cells[i,1]:=floattostr(a0[i+1]); grdb0.Cells[1,0]:=floattostr(b0); {Hiện ma trận tập dỉnh} for i:=1 to sd do for j:=1 to n do grddinh.Cells[j,i]:=floattostr(d[i,j]); {Show data trong Tenfile} end; procedure Tf1.SaveInput1Click(Sender: TObject); var f:textfile; i,j:integer; begin {If Tenfile '' then save data vao Tenfile else dung save as } {If SaveDialog1.Execute then Tenfile:=SaveDialog1.FileName; SaveDialog1.FileName:=tenfile; {Save data vao ten file} if tenfile='' then if savedialog1.Execute then tenfile:=savedialog1.FileName; assignfile(f,tenfile); rewrite(f); n:=strtoint(txtn.Text); m:=strtoint(txtm.Text); sd:=strtoint(txtsd.Text); writeln(f,n,m:6,sd:6); for i:=1 to m do for j:=1 to n do a[i,j]:=strtofloat(grdab.Cells[j,i]); for i:=0 to m-1 do b[i+1]:=strtofloat(grdb.Cells[1,i]); for i:=0 to n-1 do a0[i+1]:=strtofloat(gridaffine.Cells[i,1]); b0:=strtofloat(grdb0.Cells[1,0]); for i:=1 to sd do for j:=1 to n do d[i,j]:=strtofloat(grddinh.Cells[j,i]); for i:=1 to m do begin for j:=1 to n do write(f,a[i,j]:10:2); writeln(f,b[i]:10:2); end; for i:=1 to n do write(f,a0[i]:10:2); writeln(f,b0:10:2); for i:=1 to sd do begin for j:=1 to n do write(f,d[i,j]:10:2); writeln(f); end; closefile(f); end; procedure Tf1.Saveas1Click(Sender: TObject); Var f:textfile; i,j:integer; begin If SaveDialog1.Execute then Tenfile:=SaveDialog1.FileName; SaveDialog1.FileName:=tenfile; assignfile(f,tenfile); rewrite(f); n:=strtoint(txtn.Text); m:=strtoint(txtm.Text); sd:=strtoint(txtsd.Text); writeln(f,n,m:6,sd:6); for i:=1 to m do for j:=1 to n do a[i,j]:=strtofloat(grdab.Cells[j,i]); for i:=0 to m-1 do b[i+1]:=strtofloat(grdb.Cells[1,i]); for i:=0 to n-1 do a0[i+1]:=strtofloat(gridaffine.Cells[i,1]); b0:=strtofloat(grdb0.Cells[1,0]); for i:=1 to sd do for j:=1 to n do d[i,j]:=strtofloat(grddinh.Cells[j,i]); for i:=1 to m do begin for j:=1 to n do write(f,a[i,j]:10:2); writeln(f,b[i]:10:2); end; for i:=1 to n do write(f,a0[i]:10:2); writeln(f,b0:10:2); for i:=1 to sd do begin for j:=1 to n do write(f,d[i,j]:10:2); writeln(f); end; closefile(f); end; {---------------------------------------------------} procedure Tf1.Show1Click(Sender: TObject); begin If OpenDialog2.Execute then TenKetqua:=Opendialog2.FileName; { Show Ket qua} end; {------------------------------------------------} procedure Tf1.Run1Click(Sender: TObject); var Ud,Ua:intmt; vt1,vt2,vt3,w:vt; j,k,i,i1,i2,i3,i4,i5,bi,tt:integer; gt:real; begin f2.grdkq.Show; f2.l1.Show; for i:=1 to m do for j:=1 to n do A[i,j]:=strtofloat(grdAB.Cells[j,i]); for i:= 0 to m-1 do b[i+1]:=strtofloat(grdb.Cells[1,i]); for i:= 0 to n-1 do A0[i+1]:=strtofloat(gridaffine.Cells[i,1]); b0:=strtofloat(grdb0.Cells[1,0]); for i:= 1 to sd do for j:=1 to n do d[i,j]:=strtofloat(grdDinh.Cells[j,i]); f2.grdkq.ColCount:=n+1; f2.grdkq.RowCount:=m+sd; f2.grdkq.DefaultColWidth:=80; for i:=0 to (m+sd) do for j:=0 to n do f2.grdkq.Cells[j,i]:=''; f2.Show; tinh_tap_U(d,Ua,Ud,j,k); If j=1 then {điều kiện Ud bằng rỗng} Begin f2.l1.Hide; for i1:=1 to sd do begin f2.grdkq.Cells[0,i1-1]:='d '+inttostr(i1); for i2:=1 to n do f2.grdkq.cells[i2,i1-1] :=floattostr(d[i1,i2]); end; End; If k=1 then {điều kiện Ua bằng rỗng} begin i5:=1; if j-1=sd then {điều kiện Ud=U} begin f2.grdkq.Hide; f2.l1.Show; end else begin f2.l1.Hide; For i:=1 to sd do Begin for i1:=1 to j-1 do if Ud[i1]=i then begin tt:=i1; {đề phong phần tử Ud[1]=i} break; end else tt:=i1; if tt=j-1 then if iUd[tt] then begin f2.grdkq.Cells[0,i5-1] :='d '+inttostr(i5); for i2:=1 to n do f2.grdkq.cells[i2,i5-1]:=floattostr(d[i,i2]); i5:=i5+1; end; End; End; end; If (j1) and (k1) then {điều kiện Ua & Ud khác rỗng} Begin f2.l1.Hide; i5:=1; For i:=1 to sd do Begin for i1:=1 to j-1 do if Ud[i1]=i then begin tt:=i1; break ; end else tt:=i1; if tt=j-1 then if iUd[tt] then begin f2.grdkq.Cells[0,i5-1]:='d ' +inttostr(i5); for i2:=1 to n do f2.grdkq.cells[i2,i5-1] :=floattostr(d[i,i2]); i5:=i5+1; End; End; for i1:=1 to k-1 do for i2:=1 to j-1 do begin dinh_thu_k(d,Ua[i1],vt1); dinh_thu_k(d,Ud[i2],vt2); gt:=t(vt1,vt2); for i:=1 to n do w[i]:=gt*d[Ua[i1],i]+(1-gt) *d[Ud[i2],i]; i4:=0; for i:=1 to m do begin for i3:=1 to n do vt3[i3]:=a[i,i3]; if abs(tich(w,vt3)-b[i]) <0.001 then i4:=i4+1; end; if i4=n-1 then begin f2.grdkq.Cells[0,i5-1]:='d ' +inttostr(i5); for i:=1 to n do f2.grdkq.cells[i,i5-1] :=floattostr(w[i]); i5:=i5+1; end; end; End; end; {-------------------------------------------} procedure Tf1.Exit1Click(Sender: TObject); begin close; end; {---------------------------------------------} procedure Tf1.Close1Click(Sender: TObject); begin redit1.Visible:=true; redit2.Visible:=true; end; {---------------------------------------------} procedure Tf1.About1Click(Sender: TObject); begin f3.Show; end; End. unit Unit2; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids; type Tf2 = class(TForm) grdkq: TStringGrid; Button1: TButton; l1: TLabel; procedure Button1Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var f2: Tf2; implementation {$R *.dfm} procedure Tf2.Button1Click(Sender: TObject); begin f2.Hide; end; end. unit Unit3; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ComCtrls, jpeg, ExtCtrls,StrUtils; type Tf3 = class(TForm) Button1: TButton; Re2: TRichEdit; Timer1: TTimer; Lbl7: TLabel; procedure Button1Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure Timer1Timer(Sender: TObject); private { Private declarations } public { Public declarations } end; var f3: Tf3; implementation {$R *.dfm} procedure Tf3.Button1Click(Sender: TObject); begin f3.Hide; end; procedure Tf3.FormCreate(Sender: TObject); begin timer1.Interval:=150; end; procedure Tf3.Timer1Timer(Sender: TObject); var x,y:string; begin x:=leftstr(lbl7.Caption,1); y:=rightstr(lbl7.Caption,length(lbl7.Caption)-1); lbl7.Caption:=y+x; end; end. program TTTD; uses Forms, Unit1 in 'Unit1.pas' {f1}, Unit2 in 'Unit2.pas' {f2}, Unit3 in 'Unit3.pas' {f3}; {$R *.res} begin Application.Initialize; Application.CreateForm(Tf1, f1); Application.CreateForm(Tf2, f2); Application.CreateForm(Tf3, f3); Application.Run; end. Tài liệu trích dẫn BùI MINH TRí, Qui hoạch toán học, Nhà xuất bản khoa học và kỹ thuật. Hà Nội, 2002. lê dũng mưu, Nhập môn các phương pháp tối ưu, Nhà xuất bản khoa học và kỹ thuật. Hà Nội, 1998. trần vũ thiệu, Về hai bài toán trên tập lồi đa diện, Tạp chí khoa học tính toán và điều khiển, Số 1, Tập 1 (1985), 9-15. Đinh thế lục, Giáo trình tối ưu hoá đa mục tiêu, Viện Toán học. Hà Nội, 1998. BENSON, H. P., Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space, Jota: Vol. 98, NO. 1, July, 1998. N.T.B. KIM and D.T. LUC, Normal Cones to a Polyhedral Convex Set and Generating Efficient Faces in Linear Multiobjective Programming, Acta Math. Vietnam 25(1), pp. 101-124, 2000. N.T.B. KIM and D.T. LUC, Normal Cones Method in Solving Linear Multiobjective Programs, J.Statis. Management System, V1, 1-18, 2002. ARMAN, P., Finding All Maximal Efficient Faces in Multi-objective Linear Programming, Mathematicial Programming, Vol. 61, pp. 357-375, 1993. ARMAN, P., and MALIVERT, C,. Determination of the efficient Decision Set in Multi-objective Linear Programming, Journal of Optimization Theory and Applications, Vol. 70, pp. 467- 489, 1991. BENSON, H. P., Finding an Initial Efficient Extreme Point for a Linear Multipleobjective Program, Journal of the Operational Research Socite, Vol. 32, pp. 495- 498, 1981. BENSON, H. P., Generating the Efficient Outcome Set in Multi-objective Linear Programs: The Bicriteria Case, Acta Mathematica Vietnamica, Vol. 22, pp. 29-51, 1997. Ecker, J. G., HEGNER, N. S., and KOUADA, I. A., Generating All Maximal efficient Faces for Multi-objective Linear Programs, Journal of Optimization Theory and Applications, Vol. 30, pp. 353-381, 1980. Ecker, J. G., and KOUADA, I. A., Finding All Efficient Extreme points for Multi-objective Linear Programs, Mathematicial Programming, Vol. 14, pp. 249-261, 1978. EVANS, J. P., and STEUER, R. E., Generating Efficient Extreme Points in Multi-objective Linear Programming: Two Aglorithms and Computing Experience, Multi-Criteria Decision Making, Edited by J. L. Cochrane and M. Zeleny, University of South Carolia Press, Columbia, South Caloria, pp. 349-365, 1973. GAL, T., A Gerenal Method for Determining the Set of All Efficient Solutions to a Linear Vector Maximum Problem, European Journal of Operational Reseach, Vol. 1, pp.307-322, 1977. Goicoechea, a., Hansen, D. R., and duckstein, L., Multi-objective Decision Analysis with Engineering and Bussiness Applications, John Wiley and Sons, New York, New York, 1982. PHILIP, J., Aglorithm for the Vector Maximization Problem. Mathematicial Programming, Vol. 2, pp. 207-229, 1972. SAYIN, S., An Aglorithm Based on Facial Decomposition for Finding the Efficient Set in Multi-objective Linear Programming, Operations Reseach Letters, Vol. 19, pp. 87-94, 1996. STEUER, R.E., Multiple-criteria Optimization: Theory, Computation, and Application, John Wiley and Sons, New York, New York, 1986. STRIJBOSCH, L. W. G., VAN DOORNE, A. G. M and SELEN, W. J., A simplified MOLP Algorithm: The MOLP-S Procedure, Computer and Operations Reseach, Vol. 18, pp. 709-716, 1991. YU, P. L., Multiple-criteria Decision Making, Plenum, New York, New York, 1985. YU, P. L., and ZELENY, M., The Set of All Nondominated Solution in Linear Case and a Multicriteria Simplex Method, Journal of Mathematical Analysis and Applications, Vol. 49, pp. 430-468, 1975. ZELENY, M., Linear Multiobjective Programming, Springer Verlag, New York, New York, 1974. ZELENY, M., Multi-Criteria Decision Making, McGraw-Hill, New York, New York, 1982. ISERMAN, H., The Enumeration of the Set of All Efficient Solutions for a Linear Multi-objective Program, Operational Research Quarterly, Vol. 28, pp. 711-725, 1977. BENSON, H, P., and SAYIN, S., Towards Finding Global Representation of the Efficient Set in Multiple-Objective Mathematical Programming, Naval Reseach Logistics, Vol. 44, pp. 47-67, 1997. DAUER, J. P., and LIU, Y. H., Solving Multiple-Objective Linear Programs in Objective Space, European Journal of Operational Reseach, Vol. 46, pp. 350-357, 1990. DAUER, J. P., and SALEH, O, A., Constructing the Set of Efficient Objective Values in Multiple-Objective Linear Programs, European Journal of Operational Reseach, Vol, 46, pp. 358-365, 1990. MORSE, J. N., Reducing the Zise the Nondominated Set: Prunting by Clustering, Computer and Operations Reseach, Vol, 7. pp, 55-66, 1980. STEUER, R. E., Multiple- Objective Linear Programming with Interval Criterion Weights, Management Science, Vol. 23, pp. 305-316, 1997. STEUER, R. E., and HARRIS, F. W., Intra-Set Point Generation and Filtering in Decision and Criterion Space, Computers and Operations Reseach, Vol, 7, pp. 41-53, 1980. BENSON, H, P., An Outer Approximation Algorith for Generating All Efficien Extreme Point in the Outcom Set of a Multiple-Objective Linear Programming Problem, Working Paper, Warrington College of Businss Administration, University of Florida, Gainesville, Florida, 1997. GALLAGHER, R. J., and SALEH, O. A., A Representation of an Efficient Equivalent Polyhydron for the Objective Set of a Multiple-objective Linear Program, Eurepean Journal of Operational Reseach, Vol. 80, pp. 204-212, 1995. DAUER, J. P., and GALLAGHER, R. J., A Combined Constraint- Space Approach for Determining High-Dimensional Maximal Efficient Faces of Multiple-objective Linear Programs, Eurepean Journal of Operational Reseach, Vol. 88, pp. 368-381, 1996. JAHN, J., On the Determination of Minimal Facets and Edges of a Polyhydral Set, Journal of Multicriteria Decision Analysis (to appear). ARMANN, R., Solving Multiobjective Progamming Problems by Representation, Optimization, Vol. 20, pp. 483-492, 1989. BENSON, H. P., A Geometrical Analysis of the Efficient Outcom Set in Multiple-Objective Convex Programs with linear Criterion Functions, Journal of Global Optimization, Vol. 6, pp. 231-251, 1995. DAUER, J. P., Analysis of the Objecitve Space in Multiple-Objective Linear Programming, Journal of Mathematical Analysis and Applications, Vol. 126, pp. 579-593, 1987, BAN, V., A Finite Algorithm for Minimizing a Concave Function under Linear Constraints and Its Application, IFIP Working Conference on Recent Advances on System Modeling and Optimization, Hanoi, Vietnam, 1993. TUY, H., and HORST., Convergence and Restart in Branch-and-Bound Algorithm for Global Optimization: Application to Concave Minimization and D. C. Optimization Problems, Mathematical Programming, Vol. 41, pp. 161-183.1988. HORST., and TUY, H., Global Optimization: Deterministic Approaches, 2nd Edition, Springer Veriag, Berlin, Germany, 1993. HORST., and PADOLOS, P., Editor, Handbook of Global Optimiation, Kluwer Academic Publishers, Dordrecht, Holland, 1995. ROCKAFELLAR, R. T,. Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.