intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Chương 1: Bài toán quy hoạch tuyến tính - bài 3

Chia sẻ: Lê Văn Nhứt | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
329
lượt xem 88
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'chương 1: bài toán quy hoạch tuyến tính - bài 3', 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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 1: Bài toán quy hoạch tuyến tính - bài 3

  1.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc (đầy đủ) f ( x)  c1 x1  c2 x2  ...  cn xn  max (min)  a 11 x1  a 12 x 2  ...  a 1 n x n  b1   a 21 x1  a 22 x 2  ...  a 2 n x n  b 2 (I)   .......... .........  a x  a x  ...  a x  b  m1 1 m2 2 mn n m  x i  0 ( i  1, n ) 1  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc (rút gọn) n f ( x)   ci xi  max (min) i 1  n  a ji xi  b j ( j  1, m) (II)  i 1  x  0 (i  1, n)  i 2 1
  2.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Ma trận điều kiện & Vector điều kiện a11 a12 ... a1n  a1i  a a ... a  a  A   21 22 2n  Ai   2 i  .............................  ...      am1 am 2 ... amn  ami  3  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Định lý: Cho BTQHTT dạng chính tắc như dạng (I) hoặc dạng (II), điều kiện cần & đủ để PA x*  ( x1* , x2* ,..., xn* ) là 1 PACB của  bài toán là hệ vector điều kiện Ai xi  0 *  độc lập tuyến tính. 4 2
  3.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Biến đổi bài toán về dạng chính tắc Ràng buộc chính Cách biến đổi n n a i 1 x  bj ji i a i 1 x  xn  k  b j ji i n n a i 1 x  bj ji i a i 1 x  xn  k  b j ji i Điều kiện: xnk  0 5  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc @ Biến đổi bài toán về dạng chính tắc Ràng buộc dấu Cách biến đổi bj  0 Nhân 2 vế của ràng buộc chính với -1 & đổi dấu. xi  0 xi   xi' ( xi'  0) xi  xi  xi  x  0 ''  x  0  ' ' xi có dấu tuỳ ý i '' i 6 3
  4.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc *** CHÚ Ý: - Bài toán đã cho được gọi là BT gốc; BT mới biến đổi (có ẩn phụ) được gọi lài BT phụ. - BT phụ có hay không có PATU thì BT gốc cũng có hay không có PATU. - Nếu BT phụ có PATU thì PATU của BT gốc sẽ được rút ra bằng cách bỏ đi phần ẩn phụ và đổi các trị số của biến mới về các biến cũ theo các công thức biến đổi đã dùng. 7  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc Vd1: Biến đổi BT sau về dạng chính tắc: f ( x)  2x1  x2  2x3  x4  2x5  min  x1  2 x2  x3  2 x4  x5  7  x  2 x  x  1  2 3 4 2 x3  x4  3x5  10   x1  x2  2 x3  x4  20 x , x  0  1 5  x4  0 8 4
  5.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc Vd1: Biến đổi BT sau về dạng chính tắc:  x4   x4'   2 x  x '  x '' Đặt 2 2   3 x  x 3 '  x '' 3  x ' , x ' ' , x ' , x '' , x '  0  2 2 3 3 4 9  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc Vd1: Biến đổi BT sau về dạng chính tắc: f (x)  2x1 (x2'  x2' ' )  2(x3'  x3' ' )  x4' 2x5  min x1 2(x2'  x2' ' ) (x3'  x3' ' ) 2x4'  x5  x6  7  ' (x2  x2 ) 2(x3  x3 )  x4  x7  1 '' ' '' '  ' '' 2(x3  x3 )  x4 3x5  x8  10 '  x1  ( x ' 2  x '' 2 )  2 (x3 '  x '' 3 )  x ' 4  20 x , x ' , x ' ' , x ' , x ' ' , x ' , x , x , x , x  0 1 2 2 3 3 4 5 6 7 8 10 5
  6.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 1. BTQHTT dạng chính tắc Vd2: Biến đổi BT sau về dạng chính tắc: f ( x)  2x1  x2  x3  3x4  8  max 2x1  3x2  x3  2x4  4  x  2 x  5x  9 1 2 3  2x2  3x3  x4  2 x , x  0 1 3 11  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc n f (x)  ci xi  max (min) i 1  nm xk  akm j xm j  bk (k  1, m; j 1, n  m)  j 1 x  0 (i 1, n) i x k : Ẩn cơ bản x j : Ẩn tự do 12 6
  7.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc @ Ma trận điều kiện: 1 0 ... 0 a1m1 a1m2 ... a1n  0 1 ... 0 a a ... a  A  2m1 2m2 2n     0 0 ... 1 amm1 amm2 ... amn  A chứa một ma trận đơn vị cấp m 13  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc Vd: Xét BTQHTT sau: f ( x)  5x1  2 x2  4 x3  x4  max  x1  2 x2  x 4  7 3 x  x  x  5  2 3 4 2 x  3 x  x  3  2 4 5  x  0 (i  1,5)  i 14 7
  8.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc 1  2 0 1 0 A  0 3 1  1 0  0 2 0  3 1 * Ẩn CB: x1, x3, x5; Ẩn tự do: x2, x4 * PACB xuất phát: x = (7, 0, 5, 0, 3) 15  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc @ Biến đổi bài toán về dạng chuẩn Từ dạng chính tắc, ta biến đổi về dạng chuẩn tắc như sau: + Cộng một ẩn giả (không âm) vào vế trái của ràng buộc chặt không có ẩn cơ bản. + Trong hàm mục tiêu, ẩn giả sẽ có hệ số là –M (nếu là BT cực đại) hay +M (nếu là BT cực tiểu) với M là một số dương lớn tuỳ ý. 16 8
  9.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc Vd1: Biến đổi bài toán về dạng chuẩn f ( x)  2 x1  x2  3x3  x4  max x1  2x2  x3  4 2x  x  3x  4  1 2 4  x2  2x3  x4  1 x1, x2 , x3 , x4  0 17  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc Kết quả biến đổi: f ( x)  2x1  x2  3x3  x4  M ( x5  x6  x7 )  max x1  2 x2  x3  x5  4 2 x  x  3x  x  4  1 2 4 6 x  2 x  x  x  1  2 3 4 7 x  0 (i  1,7)  i 18 9
  10.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc Vd2: Biến đổi bài toán về dạng chuẩn f ( x)  2 x1  x2  3 x3  x4  min  x1  2 x2  x3  4 2 x  x  3 x  4  1 2 4   x2  2 x3  x4  1  x1 , x2 , x3 , x4  0 19  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc  x1  2 x2  x3  x5  4 2 x  x  3 x  x  4  1 2 4 6  x  2 x  x  x  1  2 3 4 7  x  0 (i  1,7)  i 20 10
  11.  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT 2. BTQHTT dạng chuẩn tắc Bài toán có dạng chuẩn như sau: f ( x)  2 x1  x2  3 x3  x4  Mx8  min  x1  2 x2  x3  x5  x8  4 2 x  x  3 x  x  4  1 2 4 6  x  2 x  x  x  1  2 3 4 7  x  0 (i  1,8)  i 21  CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT **** CHÚ Ý: + BT có ẩn giả được gọi là BT mở rộng hay BT “M”. + Do ẩn giả có xuất hiện trong hàm mục tiêu cho nên BT gốc & BT “M” không tương đương. + Nếu BT “M” không có PATU thì BT gốc cũng không có PATU. + Nếu BT “M” có PATU mà tất cả các ẩn giả đều nhận giá trị 0 thì BT gốc có PATU bằng cách bỏ đi phần ẩn giả. + Nếu BT “M” có PATU mà tồn tại ít nhất 1 ẩn giả nhận giá trị dương thì BT gốc không có PATU. 22 11
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2