Tham khảo tài liệu 'bài giảng toán tin 8', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Vậy ta có x2 x1 - X . Cần chọn g x2 -1 2 IIM -p2 X sao cho đạt được Min f x1 - X ĩipc. cT x1 - X j pc với các ràng buộc A x1 - X c b IPCI r n n ì x2 x1 - X jie E1 jxe Rn gi- i -p ẳ Xi -1 -p ị. pc i 1 V 1 J i 1 Ràng buộc đã được thỏa mãn do cách chọn d1. Để thỏa mãn phải có Do X1 1 Vi 1 n nên có X2 Pc IM 2 - p2 hay X - p. Vậy có thể chọn X p. Bằng cách làm như trên chúng ta đã xây dựng được điểm trong tiếp theo là x2 x1 - p với p 1. IIPCI Ví dụ 16 tiếp . Với x1 1 1 1 1 và p 0 995 ta có -1 110 AAt -1 10 1 1 3 0 0 1 3 A 1 P I - At AAt -1A 1 3 0 -1 3 1 3 -1 3 0 1 3 -1 3 -1 3 Pc -2 3 -1 3 -1 3 2 3 0 1 1 3 -1 3 0 2 3 1 3 1 PCI 1 290994 x2 T x1 Pc Ỵ pl PCI 1 257 1 514 0 229 0 743 . Hình chiếu của điểm x2 trên Ox1x2 được thể hiện bởi điểm x2ịOx x trên hình . Trường hợp 2 Ta có bài toán xấp xỉ Min f x cTx với các ràng buộc Ax b x e E2 2 -0 Y. Y2 I Jx e Rn gl -AI -p2 ị. i 1 V xi J 180 Sau đây ta đi tìm hướng cải thiện cho trường hợp E2 có dạng ellipsoid có tâm tại x2 với không phải tất cả các tọa độ đều bằng 1 như trong trường hợp đang xét của ví dụ 16 với n 4 . Lúc này trở thành E2 Jx e R4 4 f x -x Ỵ p2 x2 J p x1 -1 257 2 x2 -1 514 2 X3 - 0 229 2 x4 - 0 743 2 2 o _o-----1----. _ . .0---1---_ _ _ ------1---_ _ . ---- p . 1 2572 1 5142 0 2292 0 7432 Chúng ta tìm một phép biến đổi định lại tỷ lệ affine affine rescaling để đưa ellipsoid E2 trên đây về dạng cầu. Đó là phép biến đổi x1 1 257 0 0 0 xí 1 x2 0 1 514 0 0 X x2 x3 0 0 0 229 0 x3 l_x4 J L 0 0 0 0 734 L x4 J Có thể viết phép định lại tỷ lệ dưới dạng x X2x trong đó X2 là ma trận đường chéo cấp n X2 diag x2 x2 . x2 với các phần tử trên đường chéo chính là các tọa độ của x2. Lúc này bài toán ellipsoid xấp xỉ có dạng Min f x cTX2 x với các ràng buộc rAX2x b ly e E2 Jx e R4 x -1 2 p21. 1 J T 2 T 2 Nếu đặt c X c và AX A thì ta đã đưa được trường hợp 2 về trường hợp 1. Tương tự như biến đổi ta có công thức tìm x3 căn cứ x2 như sau p r x 3 í2r 3 2 c _ . 3 2 c x
