QUY HOẠCH RỜI RẠC - CHƯƠNG 2

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

218
lượt xem 42
download

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

NHỮNG KHÁI NIỆM MỞ ĐẦU Trong chương này sẽ trình bày những khái niệm cơ bản về quy hoạch tuyến tính, phương pháp đơn hình bình thường, phương pháp đơn hình đối ngẫu từ vựng, và khái niệm về bài toán quy hoạch tuyến tính nguyên.

Chủ đề:

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

Lưu

Nội dung Text: QUY HOẠCH RỜI RẠC - CHƯƠNG 2

Bùi Thế Tâm II.1 Quy hoạch rời rạc Chương 2 NHỮNG KHÁI NIỆM MỞ ĐẦU Trong chương này sẽ trình bày những khái niệm cơ bản về quy hoạch tuyến tính, phương pháp đơn hình bình thường, phương pháp đơn hình đối ngẫu từ vựng, và khái niệm về bài toán quy hoạch tuyến tính nguyên. 1. NHỮNG KHÁI NIỆM CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 1.1. Bài toán qui hoạch tuyến tính là bài toán có dạng: n ∑ x0 = → m ax c jx (1 ) j j =1 n ∑ = bi , i = 1, 2 , ..., l a ij x (2) j j =1 n ∑ ≤ bi , i = l + 1, ..., m a ij x (3) j j =1 ≥ 0, j = 1, .., n x (4) j Miền xác định: tập hợp các véc tơ x thoả mãn (2) và (4) Phương án bài toán: véc tơ x thoả mãn (2) và (4) n Nếu (x1,…,xn) là phương án của bài toán, x0 = ∑ c j x j thì X = (x0 ,x1,…,xn) gọi j =1 là phương án mở rộng của bài toán (1) – (4). Phương án X * làm cực đại (1) gọi là phương án tối ưu. Phương án mở rộng X gọi là phương án tối ưu mở rộng nếu X* là phương án tối ưu . * Kí hiệu: L - miền xác định của bài toán (1)-(4) ( L, C ) – kí hiệu bài toán qui hoạch tuyến tính (1) - (4) X ( L, C ) – phương án tối ưu của bài toán (1) - (4) X ( L, C ) - phương án tối ưu mở rộng của bài toán (1) - (4) LC là tập hợp các phương án tối ưu của bài toán ( L, C ) Bài toán qui hoạch tuyến tính gọi là giải được nếu tồn tại phương án tối ưu. http://www.ebook.edu.vn
Bùi Thế Tâm II.2 Quy hoạch rời rạc 1.2. Dạng chính tắc của bài toán qui hoạch tuyến tính n ∑ x0 = → m ax c x (5) j j j=1 n ∑ = bi , i = 1, 2 , ..., m a ij x (6) j j =1 ≥ 0, j = 1, 2 , ..., n (7) x j  a1 j   a   2j  Gọi Aj =  .  là véc tơ điều kiện thứ j của bài toán (5)-(7)  .   amj     b1     b2  là véc tơ ràng buộc của bài toán (5)-(7). B= . .  .  b  m Phương án X của bài toán (5)-(7) gọi là tựa nếu các véc tơ điều kiện ứng với các thành phần dương của nó là độc lập tuyến tính. Cơ sở của phương án tựa X là tập hợp { A j | x j > 0 } . Các thành phần của phương án tựa ứng với các véc tơ cơ sở gọi là các thành phần cơ sở (các biến tương ứng gọi là biến cơ sở), các thành phần còn lại gọi là các thành phần phi cơ sở (các biến tương ứng gọi là biến phi cơ sở). Nếu X = ( x1 ,..., xn ) phương án tựa của bài toán quy hoạch tuyến tính, ( A j1 ,..., A jk ) là cơ sở của phương án tựa, B = { j1 ,..., jk } , N = {1,..., n} \ B thì hàm mục tiêu x0 , x1,..., xn có thể biểu diễn qua các biến phi cơ sở: ∑ xi j (− x j ), xi = xi 0 + i = 0,1,..., n j∈N Kí hiệu Qn ={0,1,…,n} B0=B∪{0}, N0=N∪{0} Bảng đơn hình T = xij gọi là bảng đơn hình đầy đủ. i∈Q n , j∈N 0 Phương án tựa bài toán (5) - (7) gọi là không suy biến nếu số ràng buộc của hệ (6) - (7) mà phương án thỏa mãn với dấu bằng bằng đúng n (các ràng buộc này là độc lập tuyến tính). Phương án tựa là suy biến nếu số ràng buộc mà phương án tựa thỏa mãn chặt là lớn hơn n. http://www.ebook.edu.vn
II.3 Bùi Thế Tâm Quy hoạch rời rạc Phương án tựa X của bài toán (5) - (7) là không suy biến nếu các thành phần cơ sở của nó là dương. Cơ sở của phương án tựa không suy biến xác định duy nhất. Ứng với phương án tựa suy biến có nhiều cơ sở. ' ' ' Tiêu chuẩn tối ưu: để cho phương án mở rộng X ' = ( x0 , x1,..., xn ) là tối ưu điều kiện cần và đủ là tồn tại cơ sở B sao cho ∑ xi j (− x j ), xi = xi' + i = 0,1,..., n j∈N x0 j ≥ 0, j∈N Giả sử ràng buộc (6) của bài toán (5) - (7) viết ở dạng: ∑ xi j (− x j ), i = 0,1..., n . xi = xi 0 + j∈N Bảng đơn hình tương ứng T = xij , i∈Q n , j∈N 0 X=(x1 , x2 ,..., xn ) = ( x10 , x20 ,..., xn 0 ), n X = (x 0 , x1,..., xn ) = ( ∑ c j x j , x1,..., xn ). j =1 Nếu xi0 ≥ 0 (i = 1, 2, . . ., n) thì bảng đơn hình T gọi là chấp nhận được, véc tơ X là phương án tựa của bài toán quy hoạch tuyến tính. Nếu x0j ≥ 0 , j∈N thì bảng đơn hình T là chuẩn (đối ngẫu chấp nhận được), véc tơ X gọi là giả phương án, X gọi là giả phương án mở rộng 2. SO SÁNH THEO NGHĨA TỪ VỰNG 2.1. Véc tơ X = ( x1, x2 ,..., xn ) gọi là dương từ vựng X>0 nếu X≠(0,…,0) và thành phần đầu tiên khác 0 là dương. Véc tơ X gọi là không âm từ vựng X ≥ 0 nếu X>0 hay X=0 Véc tơ X gọi là lớn hơn từ vựng véc tơ Y (ký hiệu X > Y) nếu X – Y >0 Véc tơ X ≥ Y (không nhỏ hơn từ vựng) nếu X – Y ≥0 X gọi là âm từ vựng (ký hiệu là X < 0) nếu –X >0 Tương tự ta có các định nghĩa X ≤ 0, X < Y, X ≤ Y. 2.2. Phương án X* (phương án mở rộng X * ) của bài toán (5)- (7) gọi là phương án tối ưu từ vựng (phương án l - tối ưu) nếu đối với mọi phương án mở rộng X ta có X * = ( x0 , x1 ,..., xn ) ≥ X = ( x0 , x1 ,..., xn ) . ** * Định lý 1. Nếu tập hợp các phương án tối ưu của bài toán (5) - (7) khác rỗng và bị chặn thì tồn tại phương án tối ưu từ vựng X* Định lý 2. Nếu X* phương án tối ưu từ vựng của bài toán (5)-(7) thì X* là phương án tựa. http://www.ebook.edu.vn
Bùi Thế Tâm II.4 Quy hoạch rời rạc Bảng đơn hình T = xij gọi là chuẩn từ vựng (hay là l - chuẩn) nếu i∈Q n , j∈N 0  x0 j     x1 j  .  =  > 0 , ∀j∈N R j .    .   xnj    Định lý 3. Để cho phương án tựa X* của bài toán (5) – (7) là l - tối ưu, điều kiện cần và đủ là tồn tại cơ sở B sao cho bảng đơn hình T = xij là l - chuẩn. i∈Q n , j∈N 0 Giả phương án X (giả phương án mở rộng X ) của bài toán (5) – (7) gọi là dương từ vựng nếu bảng đơn hình tương ứng là l - chuẩn, nói gọn lại là l - giả phương án ( l - giả phương án mở rộng). 3. BẢNG ĐƠN HÌNH, PHƯƠNG ÁN, GIẢ PHƯƠNG ÁN Phép biến đổi cơ bản của bảng đơn hình: đưa xk ra khỏi cơ sở, đưa xl vào cơ sở. Phần tử xkl gọi là phần tử quay cơ sở là B, N= {1,..., n} \ B, l ∈ N , k ∈ B, xkl ≠ 0 . Giả sử T = xij , i∈Q n , j∈N 0 Gọi N* = ( N ∪ {k} ) \ {l} , các biến x0, x1, .. , xn có thể biểu diễn qua các biến và cơ sở mới B* = ( B ∪ {l} ) \ {k} . N* và ta được bảng T* = xij * i∈Q n , j∈N* 0 Gọi R j là cột của T, R j* là cột của T* , ta có công thức tính lại như sau * Rl  Rk = − x  kl   R* = R − xkj R ∀j ∈ ( N \ {l} ) ∪ {0} j j l xkl  hay viết ở dạng toạ độ * xil  xik = − x , i = 0,1, 2,..., n.  kl   x* = x − xkj x , ∀j ∈ ( N \ {l}) ∪ {0} , i = 0,1,..., n  ij ij il xkl  http://www.ebook.edu.vn
Bùi Thế Tâm II.5 Quy hoạch rời rạc 4. PHƯƠNG PHÁP ĐƠN HÌNH 4.1. Thuật toán Phương pháp đơn hình cho phép xây dựng dãy hữu hạn các phương án tựa X0, X1, …, X , trong đó Xk là phương án tối ưu của bài toán (5) - (7). Hàm mục tiêu x0 = x0(Xr) k không giảm khi r tăng. Ứng với mỗi phương án tựa Xr có Tr, Br, Nr. Quá trình giải gồm bước lặp xuất phát (xây dựng phương án tựa xuất phát X0) và dãy các bước lặp tổng quát. Bước lặp tổng quát r ≥ 0 có phương án Xr, tương ứng với nó có bảng đơn hình Tr và các tập Br , Nr . Kiểm tra bảng Tr có là chuẩn không (tức là x0 j ≥ 0 ∀j ∈ N r ). Nếu đúng thì Xr là tối ưu, nếu không thì xác định xl đưa vào cơ sở theo công thức : { } x0l = min x0 j | j ∈ Nr Đưa biến xk ra khỏi cơ sở theo tiêu chuẩn x  xk 0 = min  i 0 | i = 1, 2,..., n; xil > 0  xkl  xil  Nếu không có xil (i = 1, 2, ..., n) dương thì bài toán không giải được, hàm mục tiêu tiến ra dương vô cùng. Tính Xr+1, Tr+1, Br+1, Nr+1 theo các công thức ở tiết 3. 4.2. Cách tính phương án xuất phát Giải bài toán phụ ứng với bài toán (5) – (7) có bi ≥ 0 ( i=1,..,m) : n+m ∑ f ( x1, x2 .., xn+ m ) = − x j ⇒ max j = n +1 n ∑ aij x j + xn+i = bi , i = 1, 2,..., m j =1 x j ≥ 0, j = 1, 2,..., n + m Bài toán này có phương án tựa ( x1,..., x n+ m ) = (0, 0,...., 0, b1,..., bm ) . n Dùng phương pháp đơn hình giải bài toán phụ, nếu f ( x1* , x2*.., x*n+ m ) = 0 thì x*n+i = 0 (i = 1, ..., m) và véc tơ ( x1* , x2*.., x*n ) là phương án tựa phải tìm X0. Nếu f * < 0 thì bài toán (5) – (7) không giải được (không có phương án chấp nhận được). Ví dụ. Giải bài toán sau: http://www.ebook.edu.vn
II.6 Bùi Thế Tâm Quy hoạch rời rạc x 0 = x1 + x2 max 2 x1 + 11x2 ≤ 38 x1 + x2 ≤ 7 4 x1 − 5 x2 ≤ 5 x1, x2 ≥ 0 Bài toán được viết lại thành max x 0 = x1 + x2 x3 = 38 − 2 x1 − 11x2 x4 = 7 − x1 − x2 x5 = 5 − 4 x1 − 5 x2 , x j ≥ 0 ( j = 1, ,5) Ta có các bảng đơn hinh như sau: 1 -x1 -x2 1 -x5 -x2 x0 0 -1 -1 x0 5/4 1/4 -9/4 x1 0 -1 0 x1 5/4 1/4 -5/4 x2 0 0 -1 x2 0 0 -1 x3 38 2 11 x3 71/2 -1/2 27/2 x4 7 1 1 x4 23/4 -1/4 9/4* x5 5 4* -5 x5 0 -1 0 1 -x5 -x4 x0 7 0 1 x1 40/9 1/9 5/9 x2 23/9 -1/9 4/9 x3 1 1 -6 x4 0 0 -1 x5 0 -1 0 Vậy phương án tối ưu là (40/9; 23/9; 1; 0 ;0) với trị hàm mục tiêu là 7. Cách trình bày của bảng đơn hình ở trên còn gọi là dạng toạ độ của phương pháp đơn hình. 5. PHƯƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU TỪ VỰNG 5.1. Phương pháp đơn hình đỗi ngẫu xây dựng một dãy hữu hạn các giả phương án X , X1, ... , Xk. Giả phương án cuối cùng Xk là phương án (vì vậy là phương án tối o ưu) của bài toán (5) - (7) . Hàm mục tiêu xo = xo(Xr) không tăng khi r tăng. Mỗi giả phương án Xr ứng với bảng Tr và các tập Br , Nr . http://www.ebook.edu.vn
Bùi Thế Tâm II.7 Quy hoạch rời rạc Quá trình giải gồm bước lặp ban đầu (xây dựng giả phương án xuất phát Xo) và dãy bước lặp tổng quát. 5.2. Tìm cực đại từ vựng của phương án mở rộng ~   n X = ( x o , x1 ,..., x n ) =  ∑ c j x j , x1,..., xn   j =1    với các điều kiện n ∑a x = bi (i = 1, ..., m) ij j j =1 x j ≥ 0 ( j = 1, 2, , n) Ký hiệu bài toán là ( L, C ) hay l - bài toán. Phương pháp đơn hình đỗi ngẫu từ vựng gọi gọn là l - phương pháp. 5.3. Bước lặp r ≥ 0 tổng quát Có l - giả phương án Xr với x0j ≥ 0, j∈ Nr, và tương ứng Tr , Br , Nr, các cột là Rr ( j ∈ Nr ) . 0 j Kiểm tra xem Tr có chấp nhận được hay không (tức là xio≥ 0 với mọi i = 1,..,n). Nếu đúng thì Xr là phương án l - tối ưu. Nếu không thì tìm biến xk loại khỏi cơ sở theo quy tắc: k = min { i | i = 1, ... , n ; xio
Bùi Thế Tâm II.8 Quy hoạch rời rạc R l = l ex min {Rj | j ∈ N } T h ự c hi ệ n m ộ t bướ c bi ế n đ ổ i b ả ng đ ơ n hình theo các công th ứ c c ủ a ti ế t 3 ta nh ậ n đ ượ c b ả ng T o l à l - c hu ẩ n (R j ≥ 0 v ớ i j ∈ N o ) v à ứ ng v ớ i nó ta có các tập Bo và N o: B o = ( B ∪ { l }), N o = ( N ∪ { n + 1})\ { l }. 5.5. Ví dụ bằng số Giải bài toán sau bằng phương pháp đơn hình đối ngẫu. Max x0 = 3 x1 − x2 − 2 x3 2 x1 + 4 x2 − x3 ≤ 10 3 x1 + x2 + x3 ≥ 4 x1 − x2 + x3 =2 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Sau khi thay ràng buộc đẳng thức bằng hai ràng buộc bất đẳng thức bài toán trên trở thành: Max x0 = 3 x1 − x2 − 2 x3 2 x1 + 4 x2 − x3 ≤ 10 − 3 x1 − x2 − x3 ≤ −4 x1 − x2 + x3 ≤2 − x1 + x2 − x3 ≤ −2 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Tiếp theo thêm các biến bù ta được bài toán: Max x0 = 3 x1 − x2 − 2 x3 x4 = 10 − 2 x1 − 4 x2 + x3 x5 = −4 + 3 x1 + x2 + x3 x6 = 2 − x1 + x2 − x3 x7 = −2 + x1 − x2 + x3 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0 Ta có các bảng đơn hình sau khi thêm ràng buộc phụ : http://www.ebook.edu.vn
Bùi Thế Tâm II.9 Quy hoạch rời rạc 1 -x 1 -x2 -x3 x0 0.00000 -3.00000 1.00000 -2.00000 x1 0.00000 -1.00000 0.00000 0.00000 x2 0.00000 0.00000 -1.00000 0.00000 x3 0.00000 0.00000 0.00000 -1.00000 x4 10.00000 2.00000 4.00000 -1.00000 x5 -4.00000 -3.00000 -1.00000 -1.00000 x6 2.00000 1.00000 -1.00000 1.00000 x7 -2.00000 -1.00000 1.00000 -1.00000 x8 100.00000 1.00000* 1.00000 1.00000 Bảng 1 1 -x 8 -x2 -x3 x0 300.00000 3.00000 4.00000 1.00000 x1 100.00000 1.00000 1.00000 1.00000 x2 0.00000 - 0.00001 -1.00000 0.00000 x3 0.00000 - 0.00001 0.00000 -1.00000 x4 -190.00000 -2.00000 2.00000 -3.00000* x5 296.00000 3.00000 2.00000 2.00000 x6 -98.00000 -1.00000 -2.00000 0.00000 x7 98.00000 1.00000 2.00000 0.00000 Bảng 2 1 -x8 -x2 -x4 x0 236.66667 2.33333 4.66667 0.33333 x1 36.66667 0.33333 1.66667 0.33333 x2 0.00000 - 0.00001 -1.00000 0.00000 x3 63.33333 0.66667 - 0.66667 - 0.33333 x4 0.00000 0.00000 0.00000 -1.00000 x5 169.33333 1.66667 3.33333 0.66667 x6 -98.00000 -1.00000* -2.00000 0.00000 x7 98.00000 1.00000 2.00000 0.00000 Bảng 3 http://www.ebook.edu.vn
Bùi Thế Tâm II.10 Quy hoạch rời rạc 1 -x6 -x2 -x4 x0 8.00000 2.33333 0.00000 0.33333 x1 4.00000 0.33333 1.00000 0.33333 x2 0.00000 - 0.00001 -1.00000 0.00000 x3 -2.00000 0.66667 -2.00000* - 0.33333 x4 0.00000 0.00000 0.00000 -1.00000 x5 6.00000 1.66667 0.00000 0.66667 x6 0.00000 -1.00000 0.00000 0.00000 x7 0.00000 1.00000 0.00000 0.00000 Bảng 4 1 -x6 -x3 -x4 x0 8.00000 2.33333 0.00000 0.33333 x1 3.00000 0.66667 0.50000 0.16667 x2 1.00000 - 0.33333 - 0.50000 0.16667 x3 0.00000 0.00000 -1.00000 0.00000 x4 0.00000 0.00000 0.00000 -1.00000 x5 6.00000 1.66667 0.00000 0.66667 x6 0.00000 -1.00000 0.00000 0.00000 x7 0.00000 1.00000 0.00000 0.00000 Bảng 5 Vậy phương án tối ưu là (3, 1, 0, 0, 6, 0, 0) với trị hàm mục tiêu bằng x[0]=-8. 5.6. Chương trình máy tính • Chương trình nhằm giải bài toán quy hoạch tuyến tính có dạng: m x0 = ∑ c j x j → max j =1 m ∑ aij x j ≤ bi , i = 1,..., p j =1 xj ≥ 0, j = 1,2,..., m http://www.ebook.edu.vn
Bùi Thế Tâm II.11 Quy hoạch rời rạc các b[i] có thể dương và âm, phương án xuất phát không đối ngẫu chấp nhận được. Nếu m ∑ aij xi = bi thì ta thay thế bằng hai bất bài toán giải có ràng buộc đẳng thức dạng: j =1 m m ∑ aij xi ≤ bi và ∑ aij xi ≥ bi . đẳng thức: j =1 j =1 • Sau khi thêm biến bù bài toán trên có thể viết ở dạng: m x0 = ∑ (−c j )(− x j ) → max j =1 x j = (−1)(− x j ) j = 1,2,..., m m xm+i = bi + ∑ (− aij )(− x j ) i = 1,2,..., p. j =1 xj ≥ 0 j = 1,2,..., m + p. • Trong chương trình sử dụng các biến và mảng sau: - m: số biến chính, n: số biến chính và biến bù của bài toán (n=m+p), gz là một số dương đủ lớn và thường lấy bằng max { aij , bi , c j } , ss = 1 nếu bảng s là l- chuẩn nhưng không chấp nhận được và = 0 nếu bảng không là l- chuẩn. - Mảng s gồm n + 2 dòng và m+1 cột lúc đầu ghi dữ liệu của bài toán sau đó lưu bảng đơn hình ở mỗi bước. Dòng n+1 để chứa ràng buộc phụ (8). - s[0][0] hàm mục tiêu, cột 0 là cột phương án, dòng 0 là các ước lượng - cs : các biến ở bên trái bảng đơn hình, nc : các biến phi cơ sở • Cách nhập dữ liệu Các dữ liệu ban đầu của bài toán được ghi trong một tệp văn bản, gồm: - n, m,gz, ss. - Mảng s dữ liệu ban đầu bố trí dạng ở dưới và được ghi vào tệp dữ liệu theo từng dòng : http://www.ebook.edu.vn
Bùi Thế Tâm II.12 Quy hoạch rời rạc -x1 -x2 . . . . . . . . –xm x0 0 -c1 -c2 . . . . . . . –cm x1 0 -1 0 .......... 0 x2 0 0 -1 . . . . . . . . . 0 xm 0 0 0 . . . . . . . . . . -1 xm+1 b1 -a11 . . . . . . . . . - a1m xn bp -ap1 . . . . . . . . . .-ap,m - Mảng cs: nhập các số 0,1,2,…,n. - Mảng nc: nhập các số 1,2,…,m. Với dữ liệu bài toán trong mục 5.5 thì tệp dữ liệu DN.SLI có dạng : 7 3 100 0 0 -3 1 -2 0 -1 0 0 0 0 -1 0 0 0 0 -1 10 2 4 -1 -4 -3 -1 -1 2 1 -1 1 -2 -1 1 -1 01234567 123 • Văn bản chương trình. #include #include #include #include #define M 30 #define N 30 double s[N+2][M+1],r,gz; int blap,kgd, kgd2,ss,sb,cmin; int m,n,i,j,k,l,tg,cs[N+2],nc[M+1]; unsigned long far *t; long int t1,t2; char *s1,*s2; FILE *f1,*f2; http://www.ebook.edu.vn
Bùi Thế Tâm II.13 Quy hoạch rời rạc int cotquay(); void biendoi(); void inbang(int cuoi); int dhdoingau(); void main() { clrscr(); t= (unsigned long far *)MK_FP(0,0X46C); t1=*t; printf("\nCo in trung gian hay khong 1/0 ? "); scanf("%d%*c",&tg); // Nhap du lieu ban dau printf("\nVao ten tep so lieu : "); gets(s1); f1= fopen(s1,"r"); fscanf(f1,"%d%d%lf%d",&n,&m,&gz,&ss); for (i=0;i
Bùi Thế Tâm II.14 Quy hoạch rời rạc if (tg==1) fprintf(f2,"\nBang %d, l- chuan dau tien",sb); inbang(0); L1: kgd2= dhdoingau(); if (kgd2==1) { printf("\nBai toan phu khong giai duoc"); if (tg==1) fprintf(f2,"\nBai toan phu khong giai duoc, STOP"); getch(); return; } getch(); } // Phan cac ham int cotquay() { k=0; for (j=1; j
Bùi Thế Tâm II.15 Quy hoạch rời rạc { blap=0; Lap0: blap++; printf("\n-----------------------------------------------------"); printf("\nBuoc lap DHDN %d : ",blap); if (tg==1) { fprintf(f2,"\n-----------------------------------------------------"); fprintf(f2,"\nBuoc lap DHDN %d : ",blap); } l=-1; for (i=1;i
Bùi Thế Tâm II.16 Quy hoạch rời rạc 6. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH NGUYÊN B ài toán sau g ọ i là bài toán qui hoạ ch nguyên : n ∑ c jx j Max x o = ( 8) j=1 n ∑a x = bi , i = 1,..,m (9) ij j j =1 x j ≥ 0 , i = 1,..,n (10) x j - n guyên, j = 1,..., n 1 ( n 1 ≤ n ) (11) N ế u n 1 = n t hì bài toán (8) - (11) g ọ i là bài toán quy ho ạ ch tuy ế n tính nguyên hoàn toàn. N ế u n 1 < n t hì bài toán g ọ i là bài toán quy hoạ ch nguyên bộ p h ậ n. Đ i ề u ki ệ n (11) đ ôi khi vi ế t dướ i d ạ ng: x j nguyên j ∈ J ⊂ { 1,..., n}. Bài toán (8) - (10) ký hi ệ u (L,C), mi ề n xác đ ị nh L, ph ươ ng án t ố i ư u là X(L,C). T ậ p h ợ p các véc t ơ X t ho ả m ãn (9) - (11) g ọ i là mi ề n xác đ ị nh c ủ a bài toán quy ho ạ ch tuy ế n tính nguyên. Vécc tơ X t ho ả ( 9) - (11) đượ c g ọ i là ph ươ ng án (hay l ờ i gi ả i ch ấ p nh ậ n đượ c). Phươ ng án X * l àm c ự c đạ i (8) g ọ i là ph ươ ng án tố i ư u. ∑cjxj N ế u X = (x 1, ..., x n) là ph ươ ng án (hay phươ ng án t ố i ư u) và x o = t hì véc tơ X = ( x o , x1 ,..., x n ) g ọ i là ph ươ ng án m ở r ộ ng (ph ươ ng án t ố i ư u m ở r ộ ng). Ký hi ệ u: LN - m i ề n xác đ ị nh c ủ a bài toán (8) - (11) (L N ,C) là bài toán (8) - (11) X (L N ,C) là ph ươ ng án t ố i ư u. X ( L N , C) ph ươ ng án t ố i ư u m ở r ộ ng. Bài toán quy ho ạ ch tuy ế n tính nguyên gọ i là gi ả i đ ượ c n ế u t ồ n t ạ i ph ươ ng án tố i ư u X *. M ộ t đ a di ệ n L mà t ấ t c ả c ác đỉ nh củ a nó đ ề u là nguyên (m ọ i thành ph ầ n là nguyên) g ọ i là đ a di ệ n nguyên. B ả ng đơ n hình T mà t ấ t c ả các ph ầ n t ử củ a nó đ ề u là nguyên gọ i là b ả ng đ ơ n hình nguyên. http://www.ebook.edu.vn
Bùi Thế Tâm II.17 Quy hoạch rời rạc BÀI TẬP Dùng phương đơn hình hoặc phương pháp đơn hình đối ngẫu từ vựng để giải các bài toán quy hoạch tuyến tính sau. 1. Một xưởng sản xuất hai loại thép đặc biệt g1 và g2. Một đơn vị sản phẩm loại g1 cần 2 h để nấu chảy, 4 h để luyện và 10 h để cắt định hình; loại g2 cần 5 h để nấu chảy, 1 h để luyện và 5 h để cắt định hình. Lợi nhuận mang đến bởi loại g1 là 24$ và loại g2 là 8$. Khả năng của xưởng có thể bố trí 40 h để nấu chảy, 20h để luyện và 60 h để cắt định hình. Xác định phương án sản xuất mỗi loại thép là bao nhiêu để mang đến cho nhà sản xuất lợi nhuận cao nhất. 2. Một nhà sản xuất hai loại đá xây dựng: loại lớn x1, loại bé x2. Loại x1 cần 2 h để nghiền, 5 h để phân loại, 8 h để làm sạch. Loại x2 cần 6 h để nghiền, 3 h để phân loại, 2 h để làm sạch. Lợi nhuận mang lại từ loại x1 và x2 tương ứng là 40$ và 50$. Khả năng cho phép sử dụng thiết bị trong một tuần là : 36 giờ để nghiền, 30 h để phân loại, 40 giờ để làm sạch. Xác định phương án sản xuất có lợi nhuận cao nhất. 3. Một nhà vườn muốn tạo một hỗn hợp phân bón từ hai loại sản phẩm cơ bản sao cho tối thiểu nhận được 15 đơn vị potasses, 20 đv nitrates, 24 đv phosphates. Loại x1 có giá 120 $ cung cấp được 3 đơn vị potasses, 1 đv nitrates, 3 đv phosphates. Loại x2 có giá 60 $ cung cấp được 1 đơn vị potasses, 5 đv nitrates, 2 đv phosphates. Xác định phương án chọn lựa để cực tiểu hóa chi phí của nhà vườn. 4. Một nghệ sỹ rất quan tâm đến sức khỏe, mong muốn mỗi ngày có được tối thiểu 36 đv vitamin A, 28 đv vitamin C, 32 đv vitamin D. Loại thuốc thứ nhất giá 3$ có thể cung cấp 2 đv vitamin A, 2 đv vitamin C, 8 đv vitamin D. Loại thuốc thứ hai giá 4$ có thể cung cấp 3 đv vitamin A, 2 đv vitamin C, 2 đv vitamin D. Xác định lượng thuốc sử dụng để chi phí của nghệ sỹ này bé nhất. 5. Một nhà sản xuất thiết bị âm nhạc có khả năng chế tạo 3 loại: tiêu chuẩn y1, chất lượng cao y2, chất lượng đặc biệt y3. Loại tiêu chuẩn cần 3 h để lắp ráp mạch điện, 1 h để hoàn chỉnh, lợi nhuận đem lại là 15$. Loại chất lượng cao cần 1 h để lắp ráp mạch điện, 5 h để hoàn chỉnh, lợi nhuận đem lại là 20$. Loại chất lượng đặc biệt cần 3 h để lắp ráp mạch điện, 2 h để hoàn chỉnh, lợi nhuận đem lại là 24$. Khả năng xưởng có thể bố trí 120 h để lắp ráp mạch điện, 60 h để hoàn chỉnh. Xác định phương án sản xuất để cực đại lợi nhuận. 6. Chủ doanh nghiệp có 3000 ha đất để trồng 3 loại nông sản A, B, C. Để sản xuất nông sản A cần chi phí về vốn là 300 ngàn đồng/ha, chi phí về lao động là 500 ngàn đồng/ha, sản lượng thu được trị giá 2000 ngàn đồng/ha. Để sản xuất nông sản B cần chi phí về vốn là 350 ngàn đồng/ha, chi phí về lao động là 400 ngàn đồng/ha, sản lượng thu được trị giá 1500 ngàn đồng/ha. Để sản xuất nông sản C cần chi phí về vốn là 400 ngàn đồng/ha, chi phí về lao động là 450 ngàn đồng/ha, sản lượng thu được trị giá 2500 ngàn đồng/ha. Khả năng chi về vốn của doanh nghiệp là 1,2 tỷ đồng, chi về lao động là 1,6 tỷ đồng. Để đảm bảo các hợp đồng đã ký thì nông sản A cần trồng ít nhất là 600 ha. Cần xác định mỗi nông sản cần trồng bao nhiêu ha để sản lượng thu được là nhiều nhất ? 7. Một trại chăn nuôi gia súc cần mua 3 loại thức ăn tổng hợp T1, T2, T3. Trong 1 kg T1 có 3 đơn vị dinh dưỡng D1, 1 đv dinh dưỡng D2. Trong 1 kg T2 có 4 đơn vị dinh dưỡng D1, 2 đv dinh dưỡng D2. Trong 1 kg T3 có 2 đơn vị dinh dưỡng D1, 3 đv dinh dưỡng D2. Giá 1 kg T1, T2, T3 tương ứng là 15, 12, 10 ngàn đồng. Mỗi bữa ăn cho gia http://www.ebook.edu.vn
Bùi Thế Tâm II.18 Quy hoạch rời rạc súc cần tối thiểu 160 đv dinh dưỡng d1, 140 đv dinh dưỡng D2. Cần mua mỗi loại thức ăn T1, T2, T3 bao nhiêu kg để chi phí cho một bữa ăn là nhỏ nhất. 8. Min CX, AX = B, X>=0 243100 152 A= 4 2 3 0 1 0 B = 60 301001 36 C = (-5 -4 -5 -2 -1 -3) 9. Tìm x1, x2, x3, x4, x5, x6, x7 >= 0 sao cho 6x1 + x2 + x3 + 3x4 + x5 + -7x6 + 6x7 -> min -x1 + x2 -x4 +x6 + x7 = 15 -2x1 + x3 -2x6 - x7 = 9 4x1 +2x4 + x5 -3x6 =2 10. Tìm x1, x2, x3, x4, x5 >= 0 sao cho 4x1 + x2 + x3 + 3x4 -> min 2x2 + x3 + x4 = 16 4x2 + 2x5 = 0 sao cho 2x1 + 3x2 - x3 - 4x4 + 6x5 -> max 2x1 + x2 - x3 = 40 5x1 - 2x3 + 2x4 - x5 = 12 3x1 + 2x3 + x4 + 2x5 = 0 sao cho 4x1 + 2x2 + 3x3 + 6x4 + 3x5 + 2x6 ---> MIN 3x1 + 6x3 +2x4 + 3x5 = 30 x2 + x3 - 2x4 + x5 + 3x6 = 14 -x1 + 2x3 - x4 + 12 x6 >= 0 -2x1 + x3 + 3x4 + 2x5 + x6 = 0 sao cho x1 + 3x2 - 2 x3 - 5x4 - 3x5 -----> Max x1 - x3 + 2x4 - x5 = 0 3x1 + 4x2 + 4x4 - 3x5 = 40 x1 + 4x2 + 2x4