Quy hoạch tuyến tính

Bài Giảng Quy Hoạch Tuyến Tính Lời Giới Thiệu Trong Quá Trình Công Nghiệp Hóa, Hiện Đại Hóa Nền Kinh Tế, Việc Giải Quyết Các Bài Toán Kinh Tế Bằng Cách Tăng Cường Và Hợp Lí Hóa Quá Trình Sản Xuất, Đòi Hỏi Phải Áp Dụng Rộng Rãi ...

Tổng này càng nhỏ càng tốt Từ phân tích trên, mô hình của bài toán này là F(x) = 5x 11 + 7x 12 + 2x 13 + 4x 21 + 3x 22 + 6x 23  min x 11 + x 12 + x 13 = 20 x 21 + x 22 + x 23 = 40 x 11 + x 21 = 15 x 12 + x 22 = 20 x 13 + x 23 = 25 x ij ≥ 0 với i = 1,2; j = 1, 3 1.1.2. ...

Nếu phương án x = (x 1 , x 2 , . . . , x n ) có các thành phần đều ≥ 0 thì nó là phương án cực biên ứng với cơ sở B và B được gọi là cơ sở của bài toán của bài toán QHTT dạng chính tắc trên. Các biến x j  J B được gọi là biến ...

F(x) = 3x 1 – (x ’ – x ) + 2x - 5(x ’ – x ) - 2x ’  min 2 2 3 4 4 5 4 4 5 6 2x 1 - x 3 + 3(x ’ – x ) - 4x ’ - x = 5 (x ’ – x ) + 3x - (x ’ – x ) + x = -2 2 2 3 4 4 7 4 4 5 x 1 - 5(x ’ – x ) + x ’ = 3 4x 1 - (x ’ – x ) + 3x + 3x ’ + x = 8 2 2 3 5 8 x 1 ...

M  j =  c i a ij  c j i  1 = Cột hệ số nhân với véc tơ cột thứ j trừ đi hệ số c j của ẩn x j (  j gọi là ước lượng thứ j) Bước 2 : Kiểm tra tính tối ưu  Nếu  j  0  j thì phương án đang xét là phương án tối ưu ...

Ví dụ 5 : Giải bài toán QHTT sau: f(x) = 3x 1 + x 2 - 5x 3 + 2x 4  max x 1 3x 2 - + 2x 2 + 3x 4 x 4 = 4  2 x 2 2x 2 + + x 3 - 2x 4 x 4  5  3 Dạng chuẩn của bài toán trên là: x j  0 , (j = 1, 2, . . . , 4) g(x) = - f(x) = - 3x 1 - x 2 + 5x 3 - 2x 4  min x 1 - 2x 2 ...

 Bài toán mở rộng có phương án tối ưu là: x * = (0, 1, 0, 4/3, 0, 19/3, 0, 17/3) Vì ẩn giả x 8 = 17/3 khác không nên bài toán ban đầu không có phương án tối ưu. 1.3.3. Phương pháp đơn hình hai pha Xét bài toán QHTT dạng chính tắc sau (gọi là ...

B(  ) = b + m k   k p k  1 Trong đó; P k = ( k = 1, m ) là các vectơ độc lập tuyến tính bất kỳ và  > 0 đủ nhỏ Định lý:   > 0 đủ nhỏ để cho     0,   ta có: D  = { x | Ax = b(  ): x ≥ 0} là không suy biến ...

1.20. f(x) = - 3x 1 + 2x 2 – x 3 + 4x 4  max  2x  x  3x  3  1 2 4 3  3x 1  2x 2  x  3x 4  6   4x  3x  2x    7  1 2 3 x 1 , x 4  0 ; x 2  0 ; x 3 tuỳ ý ĐƯA VỀ BÀI TOÁN M CÁC BÀI TOÁN QHTT SAU: 1.21. f(x) = - 3x 1 + x 3 - 4x ...

Ví dụ 1: Lập bài toán đối ngẫu của bài toán sau: 3 x 1 + 2x 2 - 5x 3 - 3x 4 ≤ 6 -2 x 1 + x 2 + x 3 + 2x 4 = - 7 x 1 - 3x 2 + 4x 3 + x 4 ≥ 9 f(x) = 3x 1 - 2x 2 - 5x 3 + 4x 4 → min (P) x 1 , x 3 ≥ 0; x 2 tùy ý; x 4 ≤ 0 Giải: * Trước hết lấy vế phải của ràng ...

C) Tìm nghiệm của bài toán gốc (P) Theo định lý 2, ta có: y 1 (x 1 + 2) = 0 y 2 (2x 1 + 4x 2 + 3x 3 - 6) = 0 y 3 (4x 1 + 2x 2 - 4) = 0 y 4 (x 2 + 2) = 0 y 5 (x 3 - 3) = 0 x 1 (y 1 + 2y 2 + 4y 3 - 52) = 0 x 2 (4y 2 + 2y 3 + y 4 - 60) = 0 x 3 (3y 2 + y 5 - 36) = 0 mà y = (0 , 34/3 , ...

Ta thấy các ẩn cơ bản đều nhận giá trị dương  PATƯ Kết luận: - PATƯ là x * = (x 1 , x 2 , x 3 , x 4 ) = (0, 7, 6, 1) - Giá trị tối ưu đạt được là: f(x * ) = - g(x * ) = 2 Chú ý 2: Từ bảng thứ 2 của bảng đơn hình đối ngẫu, ta nên tính ...

Hệ số Ẩn CB Giả PA 0 3 -4 -1 -8 4 1  i  i (M) x 0 x 1 x 2 x 3 x 4 x 5 x 6 0 X 0 0 1 1 0 0 0 1 1 1 3 X 1 -7 0 0 1 0 0 -1 1 -1 -4 X 2 2 0 0 0 1 0 1 1 -2 -1 X 3 8 0 1 0 0 1 2 -1 1  k 0 0 0 0 -1 -4 3 1 X 6 0 1 1 0 0 0 1 1 1 3 X 1 -7 1 1 1 0 0 0 2 0 -4 X 2 2 2 2 0 1 0 3 3 0 -1 X 3 8 -1 ...

2.5. f(x) = - 3x 1 + x 3 - 4x 4  max  x  x  9x  5x   3  1 2 3 4 3  3x 1  2x 2  x  3x 4  8  x  3x  2x  x   5  1 2 3 4 x 2 , x 3  0 ; x 4  0 ; x 1 tuỳ ý 2.6. f(x) = - 3x 1 + 2x 2 – x 3 + 4x 4  min  2x  x  3x  3  ...

Ví dụ 1 : Tìm phương án cơ bản ban đầu B j A i B 1 = 76 B 2 = 62 B 3 = 88 B 4 = 45 B 5 = 40 A 1 = 79 10 19 15 6 7 A 2 = 102 13 11 8 7 4 A 3 = 70 12 17 10 5 3 A 4 = 60 12 18 18 9 10 Bảng 1 Đây là bài toán cân bằng thu phát ∑ a i = ∑ b j = 311 Nhìn trên toàn bảng 1, ...

Nhỏ nhất bằng nhau thì chọn lấy một ô cước phí nhỏ nhất bất kỳ ), ta được vòng V duy nhất. Đánh dấu + và - trên vòng V, ta được bảng sau: 2 5 6 0 20 4 5 0 30 7 0 5 0 0 - + 35 10 5 -1 0 -1 0 + - * 20 5 Ta thấy các ô đánh dấu - có lượng hàng ...

10 34 19 15 6 45 7 u 1 = -2 13 11 44 8 58 7 4 u 2 = -7 12 17 10 30 5 3 40 u 3 = -5 12 42 18 18 18 9 10 u 4 = 0 v 1 = 12 v 2 = 18 v 3 = 15 v 4 = 8 v 5 = 8 Lặp lần 2 : Tính các Δ ij = u i + v j - c ij tại các ô loại Δ 21 = -8 ; Δ 31 = -5 ; Δ 12 = -3 ; Δ 32 = -6 Δ 13 = -2 ; Δ 43 = ...

1 30 5 4 3 0 2 10 3 3 1 40 -1 4 1 60 M 2 0 0 10 0 10 0 60 0 1 -1 -1 -1 0 u i v j 0 30 4 3 3 0 10 1 1 0 40 3 0 60 M-1 2 0 10 0 10 0 60 1 Kết luận: x* =  30 0 0 0     10 0 0 40    0 60 0 0   f(x*) = 30*1 + 10*2 + 60*1 + 40*1 = 150 BÀI TẬP CHƯƠNG 3 GIẢI BÀI ...

3.21. Giải bài toán vận tải sau bằng phương pháp quy O ô chọn B A 50 90 80 30 30 Ô cấm 4 5 2 70 2 1 3 1 30 6 5 2 Ô cấm Đáp số: f(x*) = 190 3.22. Giải bài toán vận tải sau bằng phương pháp quy O ô chọn B A 50 90 80 30 30 1 Ô cấm 5 2 70 2 1 4 1 30 6 5 2 6 ...