Bài giảng quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính - ĐH Kinh tế Kỹ Thuật Công Nghệ

Chia sẻ: Lee Thom | Ngày: | Loại File: PPT | Số trang:73

Thêm vào BST

Báo xấu

1.125
lượt xem 330
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài toán dạng quy tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này mà suy ra phương án tối ưu của bài toán kia ..

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính - ĐH Kinh tế Kỹ Thuật Công Nghệ

Trường Đại học kinh tế kỹ thuật công nghiệp Bộ môn khoa học cơ bản BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH Chương 1: Bài toán quy hoạch tuyến tính
TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP BỘ MÔN KHOA HỌC CƠ BẢN BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH
Chương I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương II: BÀI TOÁN VẬN TẢI Chương III: MÔ HÌNH SƠ ĐỒ MẠNG LƯỚI
CHƯƠNG I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.1. Bài toán quy hoạch tuyến tính tổng quát 1.2. Bài toán dạng chính tắc 1.3. Bài toán dạng chuẩn 1.4. Các tính chất chung 1.5. Phương pháp đơn hình 1.6. Phương pháp đơn hình đối ngẫu
1.1. Bài toán quy hoạch tuyến tính tổng quát n f ( x ) = ∑ c j x j → min (max) j=1 n ∑ a ij x j = b i ( i ∈ I1 )  j=1 n  a x ≥ ( ≤) b ( i ∈ I ) ∑ ij j i 2  j=1 Hàm f(x) gọi là hàm mục tiêu Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc.
■ Một số khái niệm : Phương án: Vectơ x = (x1, x2,..., xn) thoả mãn mọi điều Ph kiện ràng buộc của bài toán gọi là một phương án. n ∑a x = b i thì ràng buộc i gọi là “chặt” đối với -Nếu ij j j=1 phương án x, hoặc phương án x thoả mãn chặt ràng buộc i. n -Nếu ∑ a ij x j > (
1.2. Bài toán dạng chính tắc: n f ( x ) = ∑ c j x j → min (max) j=1 n ∑ a ij x j = b i (i = 1, m)  j=1  x ≥ 0 (j = 1, n ) j  Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia
●Cách đưa bài toán về dạng chính tắc -Nếu xj ≤ 0 thì đổi biến xj’= −xj ≥ 0. n ∑a x ≤ bi -Nếu một nràng buộc có dạng thì có thể ij j thay bằng ∑ j=1 a ij x j + x = b i với x ip ≥ 0 và hệ số của p i j=1 p x x ip i n ∑ ọi Các biến a ij x jg≥ iblà biến phụ. trong f(x) bằng 0. n j=1 ∑ -Nếu mộa ij x j − x = có dạng x ip ≥ 0 p bi buiộc t ràng thì thay j=1 bằng , -Nếu xj không có ràng buộc dấu thì đặt xj = xj’− xj’’,
Ví dụ: Đưa bài toán sau về dạng chính tắc: f(x) = –2x1 + x2 + 3x3 + 5x4 ⇒ min x1 – 3x2 + 5x3 – x4 ≤ 16   2x1 – x2 – 2x3 + 2x4 ≥ – 4    4x1 + 3x2 + x3 + x4 = 9   x1, x2 ≥ 0, x3 ≤ 0  
Các biến phụ sẽ được đánh số tiếp là x5, x6. Đặt x3’= – x3 ≥ 0, x4 = x4’ – x4’’, x4’, x4’’ ≥ 0. Ta được bài toán chính tắc tương đương sau: f(x) = –2x1 + x2 – 3x3’ + 5x4’ – 5x4’’ ⇒ min x – 3x2 – 5x3’ – x4’ + x4’’ + x5 = 16  1   2x – x2 + 2x3’ + 2x4’ – 2x4’’ – x6 = –4 1   4x + 3x2 – x3’ + x4’ – x4’’ =9 1   x1, x2 , x3’, x4’, x4’’, x5, x6 ≥0
1.3. Bài toán dạng chuẩn n f ( x ) = ∑ c j x j → min (max) j=1  x1 + a 1m +1x m +1 + a 1m + 2 x m + 2 + ...... + a 1n x n = b1 x 2 + a 2m +1x m +1 + a 2m + 2 x m + 2 + ...... + a 2n x n = b 2  ...................................................................... x + a mm +1 x m +1 + a mm + 2 x m + 2 + ...... + a mn x n = b m  m  x j ≥ 0 (j = 1, n )  Trong đó: b i ≥ 0, (i = 1, m)
Bài toán dạng chuẩn là bài toán dạng chính tắc có vế phải không âm và mỗi phương trình đều có một biến số với hệ số bằng 1 đồng thời không có trong các phương trình khác (gọi là biến cô lập với hệ số bằng 1). Từ hệ phương trình ràng buộc của bài toán dễ dàng suy ra một phương án đầu tiên: x0 = (b1, b2, …,bm, 0, 0,…, 0), với cơ sở là {A1, A2,…Am} = E, đó là phương án cực biên.
1.4. Các tính chất chung 1. Tính chất 1: Sự tồn tại phương án cực biên: Nếu bài toán có phương án và hạng của ma trận hệ ràng buộc bằng n thì bài toán có phương án cực biên. Hạng của ma trận hệ ràng buộc của bài toán dạng chính tắc luôn luôn bằng n nên nếu bài toán chính tắc có phương án thì phải có phương án cực biên. 2. Tính chất 2: Sự tồn tại phương án tối ưu: Nếu bài toán có phương án và trị số hàm mục tiêu bị chặn trên tập phương án thì bài toán có phương án tối ưu. 3. Tính chất 3: Tính hữu hạn của số phương án cực biên: Số phương án cực biên của mọi bài toán quy hoạch
1.5. Phương pháp đơn hình 1. Nội dung của phương pháp: Xuất phát từ một phương án cực biên đầu tiên, tìm cách đánh giá phương án cực biên ấy, nếu nó chưa tối ưu thì tìm cách chuyển sang một phương án cực biên mới tốt hơn, quá trình được lặp lại vì số phương án cực biên là hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì hàm mục tiêu không bị chặn hoặc sẽ tìm được phương án tối ưu. Phương pháp này chỉ áp dụng được cho những bài toán có phương án cực biên, tuy nhiên mọi bài toán QHTTT đều có thể đưa về bài toán dạng chính tắc, và khi nó đã có phương án thì sẽ có phương án cực biên. Do đó không làm mất tính chất tổng quát từ đây ta sẽ chỉ xét bài toán dạng chính tắc.
2. Cơ sở của phương án cực biên: Định nghĩa: Một hệ vectơ {Aj } độc lập tuyến tính bao hàm hệ thống các vectơ tương ứng với các thành phần dương của phương án cực biên x gọi là cơ sở của phương án cực biên ấy Ký hiệu: J, trong đó: J = {j, Aj nằm trong cơ sở}. Một phương án cực biên không suy biến có đúng m thành phần dương, có một cơ sở duy nhất, đó chính là các vectơ tương ứng với các thành phần dương, còn phương án cực biên suy biến thì có nhiều cơ sở khác nhau, phần chung của chúng là các vectơ tương ứng với các thành phần dương.
3. Thuật toán của phương pháp đơn hình Giả sử đã biết phương án cực biên x0, cơ sở J0. Lập bảng đơn hình tương ứng: Hệ Cơ Phươn c1 c2 … cr … cm cm+1 … ck … cs … cn số sở gán: xJ x x … x … x x … x … x … x 1 2 r m m+1 k s n cJ J c1 x1 x10 1 0 … 0 …0 x1,m+1… x1k … x1s… x1n c2 x2 x20 0 1 … 0 …0 x2,m+1… x2k … x2s … x2n … … … ……………………………………………. cr xr xr0 0 0 … 1 … 0 xr,m+1… xrk … xrs … xrn ……………………………………………………. … … … 0 0…0…1 xm,m+1…xmk …xms ... xmn cm xm xm0 f(x) f(x0) 0 0…0…0 ∆m+1 … ∆k … ∆s … ∆n
Bước 1: Kiểm tra dấu hiệu tối ưu: ∑c x Tính các ước lượng ∆k theo công thức: Δ = − ck k j jk j∈J -Nếu ∆k ≤ 0, (∀k ∉ J0) thì x0 là phương án tối ưu. -Nếu ∆k > 0 thì x0 không phải là phương án tối ưu, chuyển sang bước 2. Bước 2: Kiểm tra tính không giải được của bài toán: -Nếu tồn tại một ∆k > 0 mà xjk ≤ 0 (∀j ∈ J0) thì bài toán không có phương án tối ưu. -Nếu với mỗi ∆k > 0 đều có ít nhất một xjk > 0 thì chuyển sang bước 3.
Bước 3: Chọn vectơ đưa vào cơ sở và xác định vectơ loại khỏi cơ sở: -Giả sử max ∆ k = ∆ s , vectơ As được đưa vào cơ sở, ∆ k >0 x0 j tính θ 0 = min x js j∈J 0 , x js > 0 x0 ( r ∈ J 0 , x rs > 0) -Giả sử θ 0 = r x rs Vectơ Ar bị loại khỏi cơ sở Phần tử xrs gọi là phần tử xoay của phép biến đổi. Lập bảng đơn hình mới, thay xs vào vị trí xr, và cs vào vị trí cr. Chuyển sang bước 4.
tổng quát cho toàn bộ bảng (bao gồm cả hàng ước lượng ∆ k). -Để tính hàng vectơ đưa vào (xs) trong bảng mới ta lấy hàng vectơ loại ra (xr) trong bảng cũ chia cho phần tử xoay. -Để tính hàng xj trong bảng mới, ta lấy hàng xj trong bảng cũ trừ đi hàng xs vừa mới tính được sau khi nhân nó với xjs. Kết quả của quá trình biến đổi sẽ cho ta bảng đơn hình ứng với phương án cực biên mới x1, tốt hơn x0. Đối với x1 quay trở lại bước 1 và quá trình lặp lại sau một số hữu hạn bước sẽ tìm được phương án cực biên tối ưu hoặc kết luận bài toán không giải được vì hàm mục tiêu không bị chặn.
Ví dụ 1: Giải bài toán sau bằng phương pháp đơn hình: f(x) = 2x1 + 3x2 – x3 – 1/2x4 ⇒ min x – x2 + x3 + 1/2x4 = 18 1  x2 – 4x3 + 8x4 ≤ 8    –2x2 + 2x3 – 3x4 ≤ 20   xj ≥ 0 (j =1…4)  