tailieunhanh - TS. Mai Thị Thu qh-4

Chương I: BÀI TOÁN 4. PHƯƠNG PHÁP ĐƠN . Giới thiệu chung: Ta xét bt QHTT CT: (1) f ( x ) = ��. c, x min. (2) Ax = b. (3) x 0Với Ax = x1 A + x2 A + + xn A. 1 2 nHoặc viết bt trên dưới dạng chi tiết:.(1) f ( x) = c1 x1 + c2 x2 + + cn xn min. a11 x1 + a12 x2 + . + a1n xn = b1. a21 x1 + a22 x2 + . a2 n xn = b2.(2). . . . am1 x1 + am 2 x2 + . amn xn = bm.(3) x j 0 j = 1, n.­Giả sử cho trước PA x, nếu biết x là .PATƯ nhờ một cách nào đó thì ta kết thúc .bt. .­Nếu biết x chưa TƯ thì ta tìm PACB khác .tốt hơn, (tức là PA làm cho giá trị hàm .mục tiêu nhỏ hơn).Ý tưởng tìm PA mới .là: ta đi xây dựng một cơ sở mới bằng .PP thay thế một véctơ trong cơ sở cũ .bởi một véctơ nằm ngoài cơ sở cũ. . Giả sử bt trên có một PACB dạng: x = ( x10 ; x20 ;; xm 0 ;0;0;;0), x j 0 > 0, j = 1, m. đó:.­Hệ vectơ liên kết (cơ sở) của x: A ,., A{ 1 m. }. ­Từ (2) ta có: b = x10 A + x20 A + + xm 0 A. 1 2 m. (đây cũng là biểu diễn b qua cs của . x0) ểu diễn vt cột Aj của A qua cs, giả sử: . ­Bi. A = x1 j A + x2 j A + + xmj A , ∀j =1,n. j 1 2 ký hiệu các chỉ số biểu diễn là véctơ. x = ( x1 j ; x2 j ;; xmj ). jVí dụ 1: Xét bt f ( x) = x1 + 6 x2 + 9 x3 min. x1 + 2 x3 = 6. + x2 + x3 = 8. xj 0, j = 1, 2, trước PACB: x0=(6,8,0)Ta có: m=2, n=3 và. 1 0. �� 2 �� 3 �� ��2 6. A = ��A = ��A = ��b = ��. 1. , , ,. 0. �� 1. �� 1 8. �� �� x = ( x10 ; x20 ;0) = (6,8,0). x có cơ sở liên kết là: { A , A }. 0 1 2.•Khi đó ta kiểm chứng được:. 1. �� �� �� 0 6. 6 A + 8 A = b � 6 �� 8 �� ��. 1 2. + =. 0 1. �� � � � � 8.•Biểu diễn vt cột Aj qua cs của x để tìm xj x1 j A + x2 j A = A , j = 1, 2,3. 1 2 jj = 1: x11 A + x21 A = A. 1 2 1 1 0. �� �� �� 1. + =. � x11 �� x21 �� ��. 0 1. �� �� �� 0 x 1. �11 � ��. � x = � � ��. 1. = ,. x 0. �21 � ��j = 2 : x12 A + x22 A = A. 1 2 2 1. �� 0 0. �� ��. + =. � x12 �� x22 �� ��. 0. �� 1 1. �� ��. x 0. �12 � ��. � x = � � ��. 2. = ,. x 1. �22 � ��j = 3 : x13 A + x23 A = A. 1 2 3 1. �� 0 2. �� ��. + =. � x13 �� x23 �� ��. 0. �� 1 1. �� ��. x 2. �13 � ��. � x = � � ��. 3. =. x 1. �23 � ��Vậy,. A = 1. A + 0. A. 1 1 2. � x = (1,0). 1. A = 0. A + 1. A. 2 1 2. � x = (0,1). 2. A = 2. A + 1. A. 3 1 2. � x = (2,1). 32. Thuật toán đơn hình giải btct: Từ hai .véctơ: x 0 = ( x ; x ;; x ;0;0;;0),. 10 20 m0 x = ( x1 j ; x2 j ;; xmj ). jĐặt: . ∆ j = c1 x1 j + c2 x2 j + L + cm xmj − c j. = �� − c j ,

• Ngân hàng - Tín dụng