tailieunhanh - Bài giảng toán tin 3

Max z = 8x1 + 6x2, với các ràng buộc ⎧4x 1 + 2x 2 ≤ 60 ⎪ ⎨2x 1 + 4x 2 ≥ 48 ⎪x , x ≥ 0. ⎩ 1 2 Ta thêm hai biến bù x3 (slack variable) mang dấu +, x4 (surplus variable) mang dấu – để có hệ điều kiện ràng buộc (mang dấu =) | trong đó gj x gu x với gij x Cij x 1 .xC . i 1 Tất cả các hệ số cio cũng như Cij được giả thiết là dương. Đối chiếu với ví dụ 20 ta có - Với i0 2 thì c2 3 a2i 1 3 a22 1 4 và a23 -1 7. - Với j 2 thì gi2 x 1 5 X1-1 2X23 4 và ci2 1 5 ai2i -1 2 ai22 3 4 và ai23 0. Để trình bày phương pháp giải BTQHHH một cách dễ hiểu trước hết chúng ta nhắc lại một số bất đẳng thức. - Bất đẳng thức Cô - si U1 u2 . UN . 1 N vớ ui U2 . UN 0. N 1 2 N - Bất đẳng thức Cô - si có trọng số . 1 a1U1 a2U2 . aNUN u ai u 2 2 . u njN ai - aN với Ui U2 . UN 0. a1 a2 . aN Đặt a1 a2 . aN Ầ thì 1 aiui Hua ỵ . Ầ i 1 1 1 a N N N Từ đó nếu ký hiệu - yi cũng có yi 1 và yiui nuy . i 1 i 1 i 1 N N í U Y N Đặt Ui yiui thì có Ui Hl. 1 với điều kiện yi 1 đây là bất đẳng thức i 1 i 1 I y J 1 1 Cô - si với các trọng số yi đã chuẩn hoá . Cũng có thể viết bất đẳng thức này dưới dạng íx U i ni U i I đây là bất đẳng thức Cô - si với các trọng số ai chưa chuẩn hoá . t i 1 Ai J Ví dụ 21. Xét BTQHHH không có ràng buộc Min z X1 1x2 1x3 1 2x2x3 x1x3 4x1x2 với điều kiện x1 x2 x3 0. Đặt U1 x1-1x2-1 x3-1 U2 2x2x3 U3 x3x1 U4 4x1x2 thì z U . í x-1x21x31 Ỵ1 12x2x3 Ỵ2 l x3x1 Ỵ3 l 4x1x2 Ỵ4 á i I y1 J I y2 J I y3 J I y4 J í 2 ìy2 í 1 í Ỵ4 l y2 J I y3 J I y4 J x - y1 y3 y4 - y1 y2 y . - y1 y2 y3 x2 x3 Cần chọn yi i 1 2 3 4 sao cho 130 -Yi y3 y4 0 -Yi y2 y4 0 -yi y2 y3 0 . yi y2 y3 y4 1 y1 2 5 y2 1 5 y3 1 5 y4 1 5. Chú ý. Điều kiện được gọi là điều kiện chuẩn. Nếu số biểu thức tích trong hàm mục tiêu là N n 1 với n là số các biến xi và các phương trình của điều kiện chuẩn là độc lập tuyến tính thì hệ có nghiệm duy nhất. Còn nếu N n 1 thì việc giải hệ khó khăn hơn. Tuy nhiên có thể chứng minh được rằng các biến yj sẽ được xác định một cách duy nhất tương ứng với giá trị zmin. 5 2 5 Tiếp tục giải ví dụ 14 ta có z I 2 I 10 1 5 5 1 5 20 1 5 5 X 21 5. Dấu xảy ra khi U1 2 . kỉ Ui y U z_ 5 X 21 5 y1 y2 . y4 Yì 1 Ui min Từ đó có hệ sau X-1x-1X-1 2 X 5 X 22 5 26 5 X1 X2 X3 5 X 5 X 2 2 2X2x3 1X 5 X 21 5 21 5 2 3 5 1 X3X4