Luận văn Phương pháp số cho bài toán động học cơ cấu khớp thấp hụt dẫn động

PHƯƠNG PHÁP GIẢM GRADIENT TỔNG QUÁT TRONG KỸ THUẬT ROBOT Vì cơ cấu chuyển hướng không gian sử dụng toàn khớp thấp như đề cập đến trong chương 1 sẽ được tác giả xem như một robot hụt dẫn động. Công cụ hiệu quả nhất cho bài toán động học của đối tượng này là phương pháp GRG [6]. Chương 2 này sẽ trình bày các vấn đề cơ bản nhất về phương pháp GRG làm cơ sở cho chương 3. 2.1 Khái niệm Gradient Trong giải tích vectơ, gradient của một trường vô hướng là một vectơ có chiều hướng về phía mức độ tăng lớn nhất của trường vô hướng: y= f (x1,, xn) (2.1) Theo định nghĩa, gradient là một vectơ cột mà thành phần là đạo hàm theo tất cả các biến củaf: 1 1 ,..., T n n y y f x x           (2.2) *Ý nghĩa của gradient Ví dụ, nhiệt độ trong một căn phòng được cho bởi một trường vô hướng t, sao cho tại mỗi điểm (x; y; z) nhiệt độ là t(x; y; z) (giả thiết rằng nhiệt độ không thay đổi theo thời gian). Trong trường hợp này, tại mỗi điểm trong căn phòng, gradient của t tại điểm đó cho biết hướng mà theo đó nhiệt độ tăng lên nhanh nhất. Độ lớn của gradient quyết định nhiệt độ thay đổi nhanh đến mức nào nếu ta đi theo hướng đó. Trong một ví dụ khác, một ngọn đồi có độ cao so với mực nước biển tại điểm (x; y) là H(x; y) . Gradient của H tại mỗi điểm là một vector chỉ theo hướng dốc nhấttại điểm đó. Độ dốc của dốc này được cho biết bởi độ lớn của vector gradient. 13 Gradient còn có thể được dùng để đo sự thay đổi của một trường vô hướng theo những hướng khác, không chỉ hướng có sự thay đổi lớn nhất, bằng cách lấy tíchđiểm. Trong ví dụ ở trên, giả sử dốc lên đồi dốc nhất là 40%. Nếu một con đường đi thẳng lên đồi thì đoạn dốc nhất trên con đường đó cũng là 40%. Nếu thay vì đi thẳng, con đường này đi vòng quanh đồi theo một góc, nó sẽ kém dốc hơn[8]. 2.2 Phương pháp giảm Gradient (Reduced Gradient) Trong toán tối ưu, chúng ta thường xuyên phải tìm giá trị nhỏ nhất (hoặc đôi khi là lớn nhất) của một hàm số nào đó. Nhìn chung, việc tìm giá trị nhỏ nhất của các hàm là rất phức tạp, thậm chí là bất khả thi. Thay vào đó, người ta thường cố gắng tìm các điểm cực tiểu, và ở một mức độ nào đó, coi đó là nghiệm cần tìm của bài toán. Các điểm cực tiểu là nghiệm của phương trình mà tại đó đạo hàm bằng 0. Nếu bằng một cách nào đó có thể tìm được toàn bộ (hữu hạn) các điểm cực tiểu, ta chỉ cần thay từng điểm cực tiểu đó vào hàm số rồi tìm điểm làm cho hàm có giá trị nhỏ nhất. Tuy nhiên, trong hầu hết các trường hợp, việc giải phương trình đạo hàm bằng 0 là bất khả thi. Nguyên nhân có thể đến từ sự phức tạp của dạng của đạo hàm, từ việc các điểm dữ liệu có số chiều lớn, hoặc từ việc có quá nhiều điểm dữ liệu. Hướng tiếp cận phổ biến nhất là xuất phát từ một điểm mà chúng ta coi là gần với nghiệm của bài toán, sau đó dùng một phép toán lặp để tiến dần đến điểm cần tìm, tức đến khi đạo hàm gần với 0. Giảm Gradient và các biến thể của nó là một trong những phương pháp được dùng nhiều nhất. [7][8]Phương pháp giảm Gradient có thể được xem như là sự mở rộng của phương pháp Gradient đối với bài toán tối ưu có ràng buộc(Linearly Constrained optimization (LC)). Xét bài toán lồi có ràng buộc tuyến tính sau: (LC) min f (x) Sao cho Ax = b, x ≥ 0 (2.3) Các giả thuyết:  f làkhả vi và liên tục; 14  Mỗi tập con của m cột của ma trận A cỡ là độc lập tuyến tính;  Mỗi điểm cực trị của tập khả thi có ít nhất m phần tử dương (giả thuyết không suy biến). Hoàn toàn chứng minh được rằng theo giả thuyết không suy biến, mỗi có ít nhất m phần tử dương. Nếu , gọi một tập gồm m cột B của A là một cơ sở nếu thì cột i là một cột của B. Chia xthành biếncơ sở và các biến không cơ sở sao cho các biến cơ sở tương ứng với các cột của B. Chú ý rằng không bắt buộc bằng 0. Để đơn giản các ký hiệu, giả thiết rằng có thể phân chia ma trận Athành A = [B, N] và phân chia x cho phù hợp, với . Do đó ta có thể viết lại Ax = b thành: (2.4) Do đó (2.5) ( tồn tại theo giả thuyết) Với , chúng ta sẽ chọn B là các cột tương ứng với các thành phần lớn nhất m của x. Các biến cơ sở bây giờ có thể bị loại bỏ khỏi bài toán (2.3) để có được bài toán cực tiểu: Sao cho: , Trong đó . Chú ý rằng bất kỳ hướng khả thi s đối với bài toán (LC) trong (2.3) đều phải thỏa mãn As = 0. Nếu chúng ta viết đối với một cơ sở B cho trước, điều kiện As = 0 có thể viết lại thành: 15 Giải phương trình này được: (2.6) Chọn hướng tìm kiếm Nhắc lại rằng s là một hướng giảm của f tại khi và chỉ khi , điều này tương đương với Với là gradient tương ứng với các biến cơ sở, thay từ (2.6) có: Gọi: (2.7) là gradient giảm của f tại x đối với B cơ sở. Như vậy: Nói cách khác, gradient giảm r đóng vai trò tương tự trong bài toán giảm như gradient đã làm trong bài toán gốc (LC). Trên thực tế, gradient giảm chính xác là gradient của hàm với trong bài toán giảm. Bên cạnh đó chứng minh được rằng , trong đó: . Nhắc lại rằng phương pháp gradient sử dụng hướng tìm kiếm . Tương tự, ý tưởng cơ sở cho phương pháp giảm gradient là sử dụng gradient giảm âm như hướng tìm kiếm cho các biến , và sau đó tính hướng tìm kiếm đối với các biến từ (2.8) Tại phép lặp k của thuật toán chúng ta thực hiện một thuật toán line search nhằm tìm sao cho: Trong đó là một cận trên trên chiều dài bước khả thi tối đa và được cho bởi: 16 = (2.9) Sự lựa chọn này đối với bảo đảm rằng và Những hiệu chỉnh cần thiết đối với hướng tìm kiếm Nếu chúng ta chọn , khi đó có thể xảy ra và tại phép lặp i nào đó.Trong trường hợp này và chúng ta không thể thực hiện được bước tìm kiếm. Một nghiệm với tập các phần tử không cơ sở có thể có các tình huống sau: (2.10) Chú ý rằng điều này tránh được các bước 0 và các bước rất nhỏ. Kết quả hội tụ Vì phương pháp giảm gradient có thể được xem là một sự mở rộng của phương pháp gradient, không có gì là bất ngờ rằng các kết quả hội tụ ở phương pháp giảm gradient tương tự như đối với phương pháp gradient. Giả định rằng phương pháp giảm gradient phát sinh các giá trị lặp: Định lý 2.1Hướng tìm kiếm tại luôn là một hướng giảm có thể khả thi trừ khi . Nếu , thì là một điểm KKT của bài toán (LC). (Điều kiện tối ưu Karush-Kuhn-Tucker (KKT)) So sánh điều này với phương pháp gradient trong đó, theo định nghĩa, khi và chỉ khi là một điểm dừng ( Thuật toán giảm gradient: tóm tắt 1. Sự khởi tạo Chọn một điểm bắt đầu sao cho Ax = b. Đểk = 0 2.Bước chính [1.1] Hình thành B từ những cột của A tương ứng với các thành phần lớn nhất mcủa . 17 Xác định Nlà các cột còn lại của A, xác định là các phần tử của tương ứng với B,và xác định tương tự. [1.2] Tính gradient giảm r từ (2.7) [1.3] Tính từ (2.10) và từ (2.8). Hình thành từ và . [1.4] Nếu , DỪNG LẠI ( là một điểm KKT) 3. Line search [2.1] Tính từ (2.9) [2.2] Thực hiện thuật toánline search [2.3] Đặt và thay k bằng k + 1. [2.4] Lặp lại bước chính. Nhận xét:  Trong toàn bộ thuật toán, nghiệm không nhất thiết phải là một nghiệm cơ sở, do đó các tọa độ dương trong có thể xuất hiện. Các biến này thường được đề cập đến như là các biến siêu cơ sở.  Nhớ lại rằng chúng ta đã đưa ra một giả thuyết không suy biến khó kiểm tra trong thực tiễn. Nếu suy biến xảy ra trong thực tế, các kỹ thuật tương tự như trong trương hợp tối ưu tuyến tính được áp dụng để giải quyết suy biến và ngăn chặn chu kỳ.  Phương pháp đơn hình lồi thu được như là sự chuyển hóa của sơ đồ giảm gradient ở trên nếu định nghĩa hướng tìm kiếm được sửa đổi. Chúng ta chỉ cho phép một tọa độ j của khác 0 và được xác định theo: . Phần còn lại của tọa độ được xác định bằng 0 và , trong đó là cột thứ j của ma trận A. 18  Phương pháp đơn hình của LO thu được như một sự chuyên môn hóa của Phương pháp đơn hình lồi. Người ta giả thuyết rằng hàm mục tiêu là tuyến tính và nghiệm đầu tiên là một nghiệm cơ sở. 2.3 Phương pháp giảm Gradient tổng quát Trước khi phát triển thuật toán giảm Gradient tổng quát, vài phương pháp quy hoạch phi tuyến đã chỉ có thể được giải quyết trong những trường hợp đặc biệt. Năm 1963 và 1967, Wolfe đã phát triển một thuật toán mà có thể giải quyết các bài toán với hàm mục tiêu phi tuyến và ràng buộc tuyến tính. Sự mở rộng của phương pháp của Wolfe để giải một dạng tổng quát của bài toán quy hoạch phi tuyến, với tên gọi là Generalized Reduced Gradient (GRG) đã được trình bày bởi Abadie và Carpentier vào năm 1967. Phương pháp giảm gradient có thể được tổng quát hóa cho bài toán tối ưu có ràng buộc phi tuyến. Tương tự với trường hợp có ràng buộc tuyến tính, chúng ta xét bài toán với các ràng buộc là đẳng thức và các biến không âm như sau: min f(x) Sao cho (2.11) , Trong đó các hàm f, h1,...,hmđược cho là khả vi và liên tục. Ý tưởng cơ sở là thay thế các phương trình phi tuyến bằng phép xấp xỉ Taylor tuyến tính của chúng tại giá trị hiện tại của x, và sau đó áp dụng thuật toán giảm gradient để cho kết quả bài toán. Giả định rằng gradient của các hàm ràng buộc là độc lập tuyến tính tại mọi điểm , và do đó mỗi x khả thi có ít nhất m phần tử dương. Những giả định này bảo đảm rằng chúng ta có thể luôn áp dụng thuật toán giảm gradient đối với bài toán tuyến tính hóa. Khó khăn thêm ở đây là vìvùng khả thi không phải là lồi. Quy trình nàycó thể tạo ra phép lặp nằm ngoài , và sau đó cần bổ sung một số yếu tố cần thiết để khôi phục lại tính khả thi.Cho một nghiệm khả thi với với tất cả j đã cho. Theo giả thuyết ma trận Jacobian của các ràng buộc 19 tại mỗi có đủ hạng, để đơn giản tại điểm sẽ được biểu thị bởi . Giả định rằng tìm đượcmột B cơ sở,với . Sau đó xây dựng tương tự như áp dụngtrong trường hợp tuyến tính. Chúng ta tạo ra một hướng tìm kiếm giảm gradient bằng cách giữ gần hết những ràng buộc tuyến tính hóa hợp lệ. Bằng cách xây dựng theo hướng này sẽ được trong không gian rỗng của A. Cụ thể, đối với các ràng buộc tuyến tính hóa ta có: Từ đây ta có Và vì b = nên Do đó các biến cơ sở có thể bị loại khỏi tuyến tính hóa của bài toán (2.11). Bài toán lúc này trở thành: min sao cho . Trong đó . Sử dụng ký hiệu: Gradient của gọi là gradient giảm có thể được biểu diễn như sau: Từ bước tiếp theo sự hình thành hướng tìm kiếm s tiếp tục theo cách tương tựnhư trong trường hợp bị ràng buộc tuyến tính. Do tính phi tuyến của các ràng buộc nhìn chung sẽ không cố định. Do đó cần phải tiến hành thêm vài bước để khôi phục tính khả thi. Cần chú ý đặc biệt đến kiểm soát kích cỡ bước. Kích cỡ bước lớn hơn có thể cho phép sự cải tiến lớn hơn của mục tiêu nhưng mặt khác, lại dẫn đến tính không khả thi lớn hơn của các ràng buộc. 20 Trong các phiên bản cũ của phương pháp GRG, phương pháp Newton được áp dụng đối với hệ đẳng thức phi tuyếnH(x) = 0 từ điểm ban đầu để tạo ra một phép lặp khả thi tiếp theo. Trong những bổ sung gần đây, hướng giảm gradient được kết hợp bởi một hướng từ không gian con trực giao (miền không gian của AT) và sau đó thuật toánline search (rời rạc, phi tuyến) đã hiệu chỉnh được tiến hành. Các sơ đồ này khá phức tạp và không được thảo luận chi tiết tại đây. 2.4 Ảnh hưởng của phép tính sai phân đến độ chính xác của bài toán Vì là phương pháp có sử dụng đạo hàm theo phân loại bài toán tối ưu nên ảnh hưởng của đạo hàm đến độ chính xác kết quả cũng như tốc độ tìm kiếm cần được bàn luận. Trước hết chúng ta nhắc lại cách tính đa thức nội suy của Newton dưới dạng tổng quát như sau: Trên đoạn a x b  cho một lưới các điểm chia ix , i = 0, 1, 2,.., n: 1 2, ,..., na x x x b  (2.12) Tại các nút ix cho giá trị của hàm số y = f(x) là ( )i iy f x , i = 1, 2,...,n Bảng 2.1. Dữ liệu nội suy đa thức Newton x x0 x1 x2 ... xn-1 xn y y0 y1 y2 ... yn-1 yn Hãy xây dựng một đa thức bậc n:   n n 1n 0 1 n 1 np x a x a x a x a       Sao cho  np x trùng với f(x) tại các nút px nghĩa là:  n i ip x y , i = 0, 1, 2,..., n Tỉ hiệu cấp 1 của y tại xi, xj là:     i j i j i j y y y x ,x x x       (2.13) Tỉ hiệu cấp hai của y tại xi, xj, xk là:     i j j k i j k i k y x ,x y x ,x y x ,x ,x x x             (2.14) 21 v.v... Các tỉ hiệu này có tính đối xứng: i j j iy x , x y x , x       i j k k j iy x , x , x y x , x , x       Với y(x) = Pn(x) là một đa thức bậc n thì tỉ hiệu cấp một tại x, x0 là:         n n 0 n 0 0 P x P x P x,x x x     (2.15) Là một đa thức bậc n – 1, tỉ hiệu cấp hai tại x, x0, x1 là:          n 0 n 0 1 n 0 1 1 P x,x P x ,x P x,x ,x x x    (2.16) Là một đa thức bậc n – 2, và tới tỉ hiệu cấp n + 1 thì:  n 0 nP x,x ,...,x 0 (2.17) Từ định nghĩa của các tỉ hiệu ta suy ra:                                 n n 0 0 n 0 n 0 n 0 1 1 n 0 1 n 0 1 n 0 1 2 2 n 0 1 2 n 0 n 1 n 0 1 n n n 0 n P x P x x x P x,x P x,x P x ,x x x P x,x ,x P x,x ,x P x ,x ,x x x P x,x ,x ,x ................. P x,x ,..., x P x ,x ,..., x x x P x,x ,..., x             (2.18) Vì  n 0 nP x,x ,...,x 0 , nên từ đó ta có                     n n 0 0 n 0 1 0 1 n 0 1 2 0 n 1 n 0 n P x P x x x P x ,x x x x x P x ,x ,x x x x x P x ,...,x            (2.19) Nếu Pn(x) = pn(x) là đa thức nội suy của hàm y = f(x) thì:      n i n i i iP x p x f x y , i 0,1,..., n.     Do đó các tỉ hiệu từ cấp một đến cấp n của Pn và của y ở (2.19) là trùng nhau. Vì vậy thay cho (2.19) ta có: 22                     n 0 0 0 1 0 1 0 1 2 0 1 n 1 0 n p x y x x y x ,x x x x x y x ,x ,x x x x x x x y x ,...,x               (2.20) Đa thức này là đa thức Newton tiến xuất phát từ nút xn của hàm y = f(x).Đa thức sau đây là đa thức Newton lùi xuất phát từ nút xn của hàm y = f(x):                     n n n n n 1 n n 1 n n 1 n 2 n n 1 1 n 0 P x y x x y x ,x x x x x y x ,x ,x x x x x x x y x ,...,x                   (2.21) Giả sử các nút xi cách đềuxi = x0 + ih, i = 0,1,..,nkhi đó h gọi là bước nội suy. Sai phân tiến cấp một tại i: i i 1 iy y y   Sai phân tiến cấp hai tại i:  2 i i i 2 i 1 iy y y 2y y        Sai phân tiến cấp n tại i là:  n n 1i iy y    Khi đó ta có:         0 0 1 2 0 0 1 2 2 n 0 0 n n y y x ,x h y y x ,x ,x 2h .................... y y x ,..., x n!h       (2.22) Bây giờ đặt x = x0 + ht trong đa thức Newton tiến (2.20) ta được:         0 2 n n 0 0 0 0x x ht t t 1 t t 1 t n 1 p x y t y y y 2! n!              (2.23) Gọi là đa thức Newton tiến xuất phát từ x0 trong trường hợp nút cách đều. Với n = 1 ta có:   0 1 0 0x x ht p x y t y      (2.24) Với n = 2 ta có:     0 2 2 0 0 0x x ht t t 1 p x y t y y 2t        (2.25) Một cách tương tự, sai phân lùi tại i: 23     i i i 1 2 i i i i 1 i 2 n n 1 i i y y y y y y 2y y ........... y y                   (2.26) Đa thức nội suy Newton lùi xuất phát từ xn trong trường hợp nút cách đều:         0 2 n n n n n nx x ht t t 1 t t 1 t n 1 p x y t y y y 2! n!              (2.27) Với bài toán có các ràng buộc tuyến tính thay đổi chậm như bài toán tối ưu động học robot với hàm mục tiêu ở dạng Banana Rosenbrock và dùng thuật toán GRG để giải quyết thì sai phân tiến sẽ cho độ chính xác kết quả cao hơn, cần phải lưu ý điều này khi tính toán và lập trình. Sai phân lùi chỉ được dùng trong trường hợp các ràng buộc của hàm mục tiêu biến đổi nhanh và khi thuật toán báo không thể cải tiến kết quả thu được. Minh chứng cho vấn đề này độc giả có thể tự kiểm chứng ngay trên trình solver của excel bằng cách giữ nguyên các tùy chọn của bài toán, chỉ thay đổi cách tính đạo hàm từ forward sang central. Độ chính xác của lời giải sẽ tăng lên đáng kể sau khi thay đổi xảy ra. 2.5 Trình tối ưu Solver của Excel Bài toán động học ngược là căn cứ chính để xây dựng lập trình mạch chuyển vị điều khiển động học robot, trong bài toán này nếu điều khiển online lượng dữ liệu tức thời sinh ra từ việc giải lặp lại bài toán ngược nhiều lần là rất lớn và đòi hỏi tốc độ xử lý nhanh. Đó là lý do cần có một phương pháp thực sự hiệu quả cho vấn đề này, nhìn chung tất cả các phương pháp nói ở trên đều rất khó vận dụng vì đòi hỏi người vận dụng có trực giác toán học tốt để đánh giá mỗi một biến đổi. Trong mục này giới thiệu công cụ cho phương pháp tối ưu hàm phi tuyến và thảo luận đầy đủ các khả năng của phương pháp này trong ứng dụng thực tế. Thông thường những ứng dụng toán học được định hướng chủ yếu với Matlab và mapple nhưng các thực nghiệm cụ thể cho thấy những hàm chuẩn của các công cụ này không hiệu quả khi giải bài toán tối ưu dưới dạng hệ phương trình siêu việt hoặc tối ưu hóa hàm siêu việt bị ràng buộc giống như mô hình bài toán giới thiệu ở đây. 24 Giải thuật được sử dụng ở đây là phương pháp giảm gradient tổng quát về bản chất là một phương pháp có sử dụng đạo hàm. Do các tìm kiếm được thực hiện theo hướng hàm giảm giá trị mạnh nhất, là hướng ngược với hướng của véc tơ gradient nên kết quả được cải thiện mạnh nhất sau mỗi vòng lặp. Chương trình ứng dụng cụ thể là gói Solver được tích hợp kèm theo Excel của MS OFFICE. Chương trình này sẵn có trên bất cứ máy tính nào, tuy nhiên solver là gói tùy chọn trong khi cài đặt nên nếu không lựa chọn cài đặt ngay từ đầu có thể cần cài bổ sung khi muốn sử dụng. Bước 1: Kiểm tra tùy chọn Solver trong Excel xem đã được cài đặt chưa Hình 2.1. Cài đặt bổ sung gói Solver cho ứng dụng tối ưu Bước 2: Hoàn thành việc xây dựng hệ phương trình bài toán động học ngược cho robot bằng một ứng dụng nào đó, chẳng hạn matlab để lấy số liệu khai báo form cho bài toán ngược trên Excel. Bước 3: Khởi tạo giao diện cho bài toán tối ưu từ Excel theo thứ tự như sau Hình 2.2. Giao diện bài toán để nhập số liệu 25 Các nhãn q1 đến q6 tượng trưng cho biến khớp, là nơi để xuất kết quả khi bài toán giải xong. Các ô trong hàng 3 chỉ là nhãn, trong quá trình thao tác nó chỉ gợi nhớ các địa chỉ nằm ở dòng 3 trong cùng cột chính là giá trị thực của nó. Ví dụ ở bước thứ nhất thường gán tất cả các biến bằng 0, khi giải bài toán kết quả được xuất ra đây, trong giao diện này khi nhập chỉ nhập giá trị vào dòng 6 là các tọa độ khâu tác động cuối trong không gian công tác. Các nhãn ny, ..,pz là các địa chỉ nhập không gian công tác, số liệu lấy từ các ma trận tọa độ thực khi cần giải bài toán. Các địa chỉ f1 đến f6 là nơi khai báo từng tọa độ lý thuyết theo ma trận tọa độ lý thuyết, hàm mục tiêu f là tổng bình phương tất cả các hàm từ f1 đến f6 để hạn chế độ dài tối đa theo quy định của Excel về độ dài biểu thức không quá 255 ký tự. Cách làm này còn cho biết thêm một thông tin về mức độ thỏa mãn mục tiêu của từng bậc tự do so với khả năng di động tối đa của nó đã đáp ứng tác vụ đang thực hiện hay chưa. Bước 4: khai báo các tọa độ lý thuyết vào giao diện chính Hình 2.3. Nhập dữ liệu theo địa chỉ đã khởi tạo sẵn Trong hình 2.3 có thể thấy để chỉ sin(q1) người dùng cần đặt con trỏ vào ô B4 nằm bên dưới giá trị q1 chứ không gõ q1 từ bàn phím, khi đó phần mềm tự duy trì một liên kết động tới ô này để thực hiện nhập/ xuất số liệu theo địa chỉ. Mỗi hàm f là một số hạng dạng (px – a14)2 lấy từ hàm mục tiêu L ở trên. Trong đó hàm f được định nghĩa là tổng các địa chỉ f1 đến f6 26 Hình 2.4. khai báo hàm mục tiêu qua các địa chỉ f1 đến f6 Bước 5: Khai báo các ràng buộc và kiểu mục tiêu của bài toán tối ưu Đặt con trỏ vào ô B13 là địa chỉ mục tiêu sau đó chọn Tools/ Solver để xuất hiện hộp thoại solver. Hình 2.5. Hộp thoại Solver Ở mục Set Target Cells kích chuột vào biểu tượng con trỏ màu đỏ để xuất hiện chỉ định vị trí của ô mục tiêu trên màn hình giao diện chính. Trong hộp thoại này chọn mục tiêu của bài toán cần giải là min trong mục Equal to. 27 Hình 2.6. chỉ định mục tiêu bằng chuột Sau khi chỉ định mục tiêu bằng chuột trong thẻ solver parameters có thể thấy địa chỉ của mục tiêu được hiển thị. Bước 6: Khai báo địa chỉ các biến khớp Từ hình 16 trong mục By Changing Cells, chọn biểu tượng con trỏ màu đỏ để con chuột biến thành con trỏ chọn, quét các ô là địa chỉ biến khớp trên giao diện chính để đánh dấu các điểm xuất dữ liệu kết quả bài toán ngược mỗi khi hoàn thành bài toán. Hình 2.7. Chỉ định các địa chỉ biến khớp bằng con trỏ Bước 7: Khai báo các ràng buộc về biên của bào toán tối ưu Từ hình 16 trong hộp thoại solver, đặt con trỏ vào ô Subject to the Constraints và chọn Add để khai báo ràng buộc với các biến khớp, thông tin cho mục này lấy từ Catalog của robot, nó bao gồm giới hạn chuyển động cụ thể của mỗi bậc tự do quay hoặc tịnh tiến. 28 Hình 2.8. Khai báo các loại ràng buộc với biến khớp Khi hoàn thành công việc này giới hạn biến thiên của từng bậc tự do được cập nhật vào mô hình như hình 19, có thể sửa chữa hay xóa bỏ các ràng buộc này như thấy trên hình 19. Bước 8: Khai báo các tùy chọn tối ưu khác Hình 2.9. Khai báo các tùy chọn khác cho bài toán Các tùy chọn khác như thấy trong hình 2.9 bao gồm: - Max time: thời gian tối đa cho một lần chạy chương trình, nếu quá giá trị này chương trình chưa tìm thấy giá trị mục tiêu tối ưu, nó sẽ báo ra kết quả ở vòng lặp sau cùng. 29 - Iteration: số lần lặp tối đa cho một lần chạy chương trình, nếu quá giá trị này chưa tìm được giá trị tối ưu chương trình báo ra kết quả ở lần lặp sau cùng. - Tolerance: Mức độ sai lệch các giá trị ở 5 vòng lặp liên tiếp nếu không vượt quá giá trị này sẽ được coi là tối ưu. - Convergence: Tính hội tụ Đây là các tham số cơ bản, các tùy chọn khác để hiểu và sử dụng đúng cần có hiểu biết về bài toán tối ưu. Bảng 2.2. Các thuật ngữ của công cụ Solver trên giao diện chương trình Thuật ngữ ý nghĩa Set target cell Ô chứa hàm mục tiêu (ô đích) Equal to max Chọn mục này khi cần tìm max của hàm mục tiêu Equal to min Chọn mục này khi cần tìm min của hàm mục tiêu Equal to value of Chọn mục này và nhập giá trị vào ô hình chữ nhật bên cạnh nếu muốn ô đích bằng một giá trị nhất định. By changing cells Chọn các ô chứa các biến của bài toán Subject to the constrains Mục này dùng để nhập các ràng buộc của bài toán Add Hiển thị hộp thoại Add constraint để thêm các ràng buộc Change Hiển thị hộp thoại Change Constraint để thay đổi ràng buộc Delete Để xóa ràng buộc đã chọn Guess Để đoán các giá trị trong các ô không chứa công thức do công thức trong ô đích (target cell) trỏ đến. Solve Thực hiện việc giải bài toán Close Đóng hộp thoại Solver parameters mà không tiến hành giải bài toán 30 Thuật ngữ ý nghĩa Option Hiển thị hộp thoại Solver options để ghi mô hình bài toán, nạp lại mô hình đã ghi hoặc nhập các lựa chọn khác cho việc giải bài toán Reset all Xóa các thiết lập cho bài toán hiện tại và khôi phục các thiết lập ngầm định Help Hiển thị trợ giúp cho Solver Bảng 2.3. Ý nghĩa của tự chọn trong Option của cụng cụ Solver Tùy chọn ý nghĩa Max time Thời gian giải bài toán, ngầm định là 100 s, giá trị tối đa là 32767 s iteration Số lần lặp, ngầm định là 100, số lần tối đa là 32767. Precision Độ chính xác. Giá trị này luôn nằm trong khoảng [0,1] để điều chỉnh sai số cho các ràng buộc. Giá trị càng gần 0 càng đòi hỏi độ chính xác cao của các ràng buộc. Tolerance Giá trị này tính bằng (%) và có tác dụng đối với các bài toán có ràng buộc nguyên. Giá trị lựa chọn càng lớn thì bài toán càng giải nhanh Convergence Mức độ hội tụ của hàm mục tiêu. Giá trị này nằm trong khoảng [0, 1]. Lựa chọn này chỉ có ý nghĩa đối với bài toán quy hoạch phi tuyến. Sau 5 lần lặp cuối cùng, nếu thay đổi trong giá trị hàm mục tiêu nhỏ hơn giá trị này thì Solver dừng quá trình tính toán.Giá trị này càng nhỏ thì thời gian tính toán càng dài. Assume Linear Model Giả thiết mô hình tuyến tính. Chọn mục này đối với bài toán quy hoạch tuyến tính. Assume Non - Negative Giả thiết các biến không âm. Chọn mục này khi cú ràng 31 Tùy chọn ý nghĩa buộc về dấu của các biến. Use Automatic Scale Chọn mục này khi giá trị đầu vào và kết quả có độ lớn khác nhau. Ví dụ tìm tối đa hóa lợi nhuận khi đầu tư tính bằng triệu dolla Show Iteration Result Chọn mục này khi muốn Solver hiển thị các kết quả trung gian của mỗi bước lặp. Estimates: - Tangent - Quadratic Chỉ thị cho Solver cách ước lượng giá trị theo một phương tìm kiếm. Tangent: Ngoại suy sử dụng xấp xỉ bậc nhất. Quadratic: Ngoại suy sử dụng xấp xỉ bậc hai. Lựa chọn này cho độ chính xác cao hơn đối với các bài toán quy hoạch phi tuyến. Derivatives: - Forward - Central Chỉ thị cho Solver cách tính đạo hàm riêng phần cho