Bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị

các khái niệm khi được đưa vào ở các chương sau. Phương pháp đơn hình là một trong nhiều phương pháp được sử dụng rỗng rãi để giải bài toán qui hoạch tuyến tính cũng được trình bày ở đây. Chương Ii bài toán qui hoạch tuyến tính đa mục tiêu 2.1. Thế nào là tối ưu đa mục tiêu Như đã biết, nhiều bài toán ứng dụng trong các lĩnh vực khác nhau của khoa học kỹ thuật cũng như thực tiễn cuộc sống của con người, có thể mô hình hoá như bài toán tối ưu một hàm mục tiêu duy nhất theo những điều kiện nhất định. Ví dụ bài toán qui hoạch tuyến tính như đã mô tả ở Chương I là tối ưu một hàm tuyến tính trên một tập lồi đa diện . Tuy nhiên, thực tế cùng một lúc người ta thường phải theo đuổi nhiều mục tiêu khác nhau. Ví dụ khi lựa chọn mua nhà ở, chúng ta phải tính đến nhiều yếu tố như giá cả, môi trường, tiện nghi. Thường nhà rẻ hơn thì môi trường hoặc tiện nghi kém hơn. Điều đó dẫn đến mô hình bài toán tối ưu nhiều mục tiêu (qui hoạch đa mục tiêu). Để hiểu rõ hơn về bài toán này ta xét 2 ví dụ dưới đây. Ví dụ 2.1.1.(Tối ưu phương án thiết kế nhà ở) Giả sử trong thiết kế nhà ở như Hình 5, cách bố trí các phòng cũng như một số thông số và ràng buộc được cho trước. Vấn đề phải xác định các thông số còn lại nhằm cực đại diện tích sử dụng và cực tiểu chi phí xây dựng. x1 x2 x3 2.45 Phòng ăn 1.83 Wc 3.35 Phòng ngủ 1 3.98 Phòng ngủ 2 Sảnh x43.05 Bếp x5 Phòng ngủ 3 Hình 5. Chi phí xây dựng được cho bảng dưới đây Loại phòng Diện tích min (m2) Diện tích max (m2) Giá (USD) Bếp 5 12 200 Phòng ngủ 10 18 100 Phòng ăn 15 20 300 Sảnh 1,83 7,2 324,7 Tắm 4,5 6,5 324,7 Lập bài toán: Gọi S là diện tích sử dụng thì S là hàm số của x1, x2, x3 theo công thức: S(x1, x2, x3, x4, x5)=7,33(x1+ x2+ x3). Gọi C là chi phí xây dựng thì C hàm số của x1, x2, x3, x4, x5 theo công thức: C=(4,28x1).300+ (2,45x2)324,7+ (1,83x2)324,7+ (3,05x4)200+ (3,05x5+ 3,35x3+ 3,98x3)100 = 1284x1+1389,716x2+ 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.