Giả sử các sản phẩm sản xuất ra đều có thể bán hết với lợi nhuận là 620 USD đối với mỗi sản phẩm S1và 570 USD đối với mỗi sản phẩm S2. Hỏi mỗi tuần phải sản xuất bao nhiêu sản phẩm S1và bao nhiêu sản phẩm S2để nhà máy có lợi nhuận lớn nhất?
Bài 1.12Một phân xưởng cơ khí có 3 loại máy G1, G2, G3dùng để sản xuất 3 loại chi tiết C1, C2, C3. Năng suất của mỗi loại máy sản xuất từng loại chi tiết được cho như sau ( số chi tiết /1ca ):
C1 3 | C2 1 | C3 3 | |
G1:2 | 0 | 15 | 18 |
G2: 3 | 50 | 20 | 30 |
G3:1 | 60 | 40 | 45 |
Có thể bạn quan tâm!
-
Quy hoạch toán học - Ngô Hữu Tâm - 1 -
Quy hoạch toán học - Ngô Hữu Tâm - 2 -
Quy Tắc Vàng Khi Lập Mô Hình Toán Học Bài Toán Thực Tế Và Khái Niệm Tối Ưu: -
Các Bước Giải Bài Toán Qhtt Hai Biến Bằng Phương Pháp Hình Học -
Định Lý 3 (Dấu Hiệu Bài Toán Có Thể Điều Chỉnh Để Được Pa Tốt Hơn) -
Quy hoạch toán học - Ngô Hữu Tâm - 7
Xem toàn bộ 192 trang tài liệu này.
Các chi tiết sau khi sản xuất được lắp ráp thành sản phẩm. Mỗi sản phẩm bao gồm 3 chi tiết C1, 1 chi tiết C2và 3 chi tiết C3.
Hãy tìm phương án phân công thời gian làm việc cho các máy sao cho số sản phẩm
được lắp ráp trong một ca sản xuất là nhiều nhất. Biết rằng phân xưởng có 2 máy G1, 3 máy G2và 1 máy G3.
Bài 1.13Một công ty may mặc có 3 xí nghiệp I, II, III. Công ty ký hợp đồng giao cho đối tác 1500 bộ gồm áo veston và quần tây, nếu có lẻ bộ thì đối tác lấy thêm quần tây chứ không lấy thêm áo. Tổng số vải và giờ công lao động mà công ty có thể huy động được từ 3 xí nghiệp mỗi tháng là 10 000 m và 52 000 giờ. Mức tiêu hao vải và giờ công lao động để sản xuất một áo hoặc một quần tại mỗi xí nghiệp (XN) được cho trong bảng sau:
I | II | III | |
Áo veston | 3,5 m và 20 giờ | 4m và 16 giờ | 3,8m và 18 giờ |
Quần tây | 2,8 m và 10 giờ | 2,6m và 10 giờ | 2,5m và 15 giờ |
Giả sử nếu đầu tư 10 triệu đồng vào xí nghiệp I ( để mua nguyên liệu, máy móc và đầu tư vào hoạt động sản xuất ) sẽ thu được 35 áo veston và 45 quần tây, vào xí nghiệp II sẽ thu được 40 áo veston và 42 quần tây, vào xí nghiệp III sẽ thu được 43 áo veston và 30 quần tây. Hãy lập mô hình toán học của bài toán lập kế hoạch đầu tư vào mỗi xí nghiệp bao nhiêu tiền để thực hiện được hợp đồng và tổng số tiền đầu tư vào các xí nghiệp ít nhất.
Bài 1.14Một công ty sử dụng 2 loại nguyên liệu N1, N2 để sản xuất ra 1 loại sản phẩm theo 2 công nghệ khác nhau là CN1, CN2. Biết lượng nguyên liệu mỗi loại hiện có; định mức tiêu hao các loại nguyên liệu, chi phí sản xuất, lượng sản phẩm làm ra trong một giờ được cho trong bảng sau:
Số lượng nguyên liệu hiện có (đv) | Định mức tiêu hao nguyên liệu trong 1 giờ | ||
CN1 | CN2 | ||
N1 | 300 | 2 | 4 |
N2 | 400 | 3 | 2 |
Sản lượng (sản phẩm/giờ) | 7 | 8 | |
Chi phí (USD/giờ) | 120 | 150 | |
Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho giá thành sản phẩm là thấp nhất.
Bài 1.15Hãy lập mô hình toán học của bài toán sau đây. Một công ty may mặc ký hợp đồng giao cho khách hàng 248.000 bộ quần áo trong thời gian 1 tháng. Công ty có ba xí nghiệp A, B, C và quần áo phải được sản xuất và đóng gói thành bộ tại mỗi xí nghiệp. Năng lực sản xuất trong một tháng và lợi nhuận đối với mỗi bộ quần áo (sau khi đã trừ tất cả các chi phí) của các xí nghiệp trong thời gian thường trong thời gian tăng ca được cho trong bảng sau:
Xí nghiệp A | Xí nghiệp B | Xí nghiệp C | ||||
Năng lực sản xuất | Lợi nhuận | Năng lực sản xuất | Lợi nhuận | Năng lực sản xuất | Lợi nhuận | |
Thời gian thường | 90.000 bộ/tháng | 8.000 đồng/bộ | 50.000 bộ/tháng | 7.500 đồng/bộ | 80.000 bộ/tháng | 8.000 đồng/bộ |
Thời gian tăng ca | 40.000 bộ/tháng | 7.200 đồng/bộ | 20.000 bộ/tháng | 6.500 đồng/bộ | 30.000 bộ/tháng | 7.500 đồng/bộ |
Biết rằng số bộ quần áo sản xuất tại hai xí nghiệp A và B phải ít nhất là 152.000 bộ. Hỏi phải phân công sản xuất cho các xí nghiệp như thế nào để hoàn thành hợp đồng với lợi nhuận lớn nhất.
Bài 1.16(bài toán qui hoạch phân tuyến tính) Một công ty sử dụng 3 loại nguyên liệu N1, N2, N3để sản xuất ra một loại sản phẩm tại hai xí nghiệp khác nhau là XN1, XN2. Do trình độ chuyên môn, trình độ quản lý, trang thiết bị sản xuất của hai xí nghiệp khác nhau nên định mức tiêu hao nguyên liệu và năng suất của hai xí nghiệp cũng khác nhau. Biết lượng nguyên liệu mỗi loại hiện có, định mức tiêu hao các loại nguyên liệu, chi phí sản xuất, lượng sản phẩm làm ra trong một giờ được cho trong bảng sau:
Số lượng nguyên liệu hiện có (đv) | Định mức tiêu hao nguyên liệu trong 1 giờ | ||
XN1 | XN2 | ||
N1 | 3500 | 40 | 39 |
N2 | 3200 | 27 | 30 |
N3 | 5600 | 45 | 43 |
Sản lượng (sản phẩm/giờ) | 112 | 100 | |
Chi phí (USD/giờ) | 165 | 162 | |
Ban giám đốc công ty yêu cầu xí nghiệp 2 phải sản xuất ít nhất 1000 sản phẩm. Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho giá thành sản phẩm là thấp nhất.
Bài 1.17Một công ty sử dụng 4 loại nguyên liệu N1, N2, N3, N4 để sản xuất ra 3 loại sản phẩm SP1, SP2, SP3. Biết lợi nhuận của mỗi đơn vị sản phẩm (không phụ thuộc vào số giờ sản xuất và số sản phẩm được sản xuất), số lượng nguyên liệu hiện có, định mức tiêu hao các loại nguyên liệu và lượng sản phẩm làm ra trong một giờ được cho trong bảng sau:
Số lượng nguyên liệu hiện có | Định mức tiêu hao nguyên liệu (đôn vò) trong 1 giờ | |||
SP1 | SP2 | SP3 | ||
N1 | 350 (đôn vò) | 2 | 3 | 4 |
N2 | 650 (đôn vò) | 6 | 8 | 9 |
N3 | 600 (đôn vò) | 3 | 5 | 7 |
N4 | 900 (đôn vò) | 8 | 10 | 9 |
Sản lượng (sản phẩm/giờ) | 12 | 10 | 9 | |
Lợi nhuận (đồng/sản phẩm) | 10.000 | 12.000 | 13.000 | |
Sản phẩm của xí nghiệp sản xuất ra đều có thể tiêu thụ hết với điều kiện tiêu thụ là số sản phẩm SP2và SP3phải có tỷ lệ 1:2. Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho lợi nhuận lớn nhất.
Bài 1.18Một công ty sử dụng 4 loại nguyên liệu N1, N2, N3, N4để sản xuất ra một loại sản phẩm tại ba xí nghiệp khác nhau là XN1, XN2, XN3. Do trình độ chuyên môn, trình độ quản lý, trang thiết bị sản xuất của ba xí nghiệp khác nhau nên định mức tiêu hao nguyên liệu và năng suất của ba xí nghiệp cũng khác nhau. Biết lượng nguyên liệu mỗi loại hiện có, định mức tiêu hao các loại nguyên liệu, chi phí sản xuất, lượng sản phẩm làm ra trong một giờ của mỗi xí nghiệp được cho trong bảng sau:
Số lượng nguyên liệu hiện có (đv) | Định mức tiêu hao nguyên liệu trong 1 giờ của mỗi xí nghiệp | |||
XN1 | XN2 | XN3 | ||
N1 | 36000 | 38 | 37 | 39 |
N2 | 35000 | 31 | 32 | 31 |
N3 | 63000 | 45 | 43 | 44 |
N4 | Không hạn chế | 68 | 72 | 70 |
Sản lượng (sản phẩm/giờ) | 117 | 114 | 118 | |
Chi phí (USD/giờ) | 170 | 165 | 168 | |
Hãy lập mô hình toán học bài toán tìm kế hoạch sản xuất sao cho giá thành sản phẩm là thấp nhất, biết xí nghiệp I phải sản xuất ít nhất 1200 sản phẩm.
§ 2. CÁC DẠNG BÀI TOÁN QUI HOẠCH TUYẾN TÍNH
2.1. Bài toán qui hoạch tuyến tính tổng quát
Tìm x = (x1, x2,…, xn) n sao cho:
n
(1) f(x) = c jx j
j1
min ( max)
n
(2) aijx j
b i
b i
, i = 1, 2, …, m
j1
(3) xj
b i
0
0 , j = 1, 2, …, n
tùy ý
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 ở (2) gọi là một ràng buộc. Vậy có m ràng buộc.
(3) gọi là ràng buộc về dấu của các ẩn số.
Tập D trong nthỏa (2) và (3) gọi là miền ràng buộc hay miền phương án.
Mỗi vectơ x = (x1, x2,…, xn) nthỏa (2) và (3) gọi là một phương án (PA).
Phương án xthỏa (1) gọi là phương án tối ưu (PATƯ) và f (x) gọi là giá trị tối ưu của bài toán; tức là f (x) f(x) xD đối với bài toán f min, f (x) f(x) xD đối với bài toán f max.
Việc giải bài toán QHTT là tìm PATƯ và giá trị hàm mục tiêu ứng với PATƯ
đó; hoặc chỉ rõ bài toán không có phương án tối ưu.
Nhận xétf(x) min tương đương với -f(x) max. Do đó, mọi bài toán có hàm mục tiêu min đều có thể chuyển về bài toán có hàm mục tiêu max và ngược lại.
Ví dụ 1Tìm x = (x1,x2,x3) 3 sao cho
(1) f(x) = 2x1-x2 + x3 min (max)
x1
(2) 2x
2x2
2x
x3 2
x 3
1 2 3
x1
x2
x3 4
(3) x1tùy ý, x20, x30
Ví dụ 2Tìm x = (x1,x2,x3,x4,x5) 5 sao cho
(1) f(x) = 3x1-x2 +2 x3 +x4 +5x5 max (min)
2x1
4x
x2
2x
x3
x
2x4
x5
17
18
(2) 1 2 3
x1
x1
x2
x2
2x3
2x3
x4
x5
20
100
(3) x1, x40; x2, x30 ; x5tùy ý
Ví dụ 3Cỏc bài toỏn lập ở vớ dụ 3, 4, 5 bài Đ1 đều cú dạng tổng quỏt.
2.2. Bài toán qui hoạch tuyến tính dạng chính tắc:(Canonical form) Tìm x = (x1, x2,…, xn) n sao cho:
n
(1) f(x) = c jx j
j1
min ( max)
n
(2) aijx jbi
j1
, i = 1, 2, …, m
(3) xj 0 , j = 1, 2, …, n
Không mất tính tổng quát, có thể giả sử m ràng buộc ở (2) là độc lập tuyến tính. Tức là, nếu A là ma trận bổ sung của hệ phương trình tuyến tính (2) thì r( A ) = m.
Bất kỳ bài toán QHTT nào cũng có thể đưa về bài toán QHTT dạng chính tắc bằng các phép biến đổi tương đương ( đưa thêm vào các ẩn phụ) như sau:
n
Biến đổi 1Mỗi ràng buộc là bất phương trình dạng aijx jbiđược đưa về
j1
phương trình bằng cách cộng vế trái với một ẩn phụ xn+k 0 ( k1,2,3,...).
n
Nghĩa là nó tương đương với aijx j
j1
+ xn+k = bi. Hệ số của ẩn phuù xn+k trong
hàm mục tiêu là 0.
n
Biến đổi 2Mỗi ràng buộc là bất phương trình dạng aijx j
j1
biđược đưa về
phương trình bằng cách trừ vế trái với một ẩn phụ xn+k 0 ( k1,2,3,...). Nghóa
n
là nó tương đương với aijx j
j1
- xn+k = bi. Hệ số của ẩn phuù xn+k trong hàm mục
tiêu là 0.
j
Biến đổi 3Mỗi biến xj 0 thì được thay bởi xj = - x'
x
j
, với '
x
0.
x
j
Biến đổi 4Mỗi biến xjtùy ý thì được thay bởi xj= '
- x", với '
0 ,
x" 0.
j
j
j
Ví dụ 4Đưa bài toán QHTT sau đây ( bài toán (P)) về dạng chính tắc:
(1) f(x) = 2x1-x2 + x3 min (max)
x1
(2) 2x
2x2
2x
x3 2
x 3
1 2 3
x1
x2
x3 4
(3) x1tùy ý, x20, x30
Giải
Để đưa bài tốn về dạng chính tắc, ta phải đưa các ràng buộc bất phương trình về phương trình, đồng thời tất cả các ẩn số đều phải không âm. Như vậy, ta cần thực hiện các phép biến đổi sau:
Cộng vế trái ràng buộc thứ nhất ẩn phụ x40 và hệ số trong hàm mục tiêu của x4là 0.
x
x
x
-
Trừ vế trái ràng buộc thứ hai ẩn phụ x50 và hệ số trong hàm mục tiêu của x5là 0.
Thay x1 =
' x" , với
' 0 ,
x" 0. Thay x3 = -
x' , với '
0.
1
1
3
x
1
x
1
1
3
1
3
Ta có bài toán chính tắc ( P ) tương ứng với bài toán (P) là:
3
(1’) f ( x ) = 2
' - 2 x" -x2 - '
min (max)
x
1
1
' x"
2x2
x'
x4 2
1
3
(2’)
2x' 2x"
2x2
x' x5 3
1
x
1
x
' "
x
1
1
x2
x' 4
3
(3’)
' 0 ,
x" 0, x2 0, '
0, x4 0, x5 0
1
x
3
Nhận xét( liên hệ giữa bài toán tổng quát và bài toán chính tắc)
Gọi D là miền phương án của bài tốn tổng quát (P) và D là miền phương án của bài tốn chính tắc ( P ). Vì f(x) = f ( x ), xD và x D nên ta có:
Bài toán (P) có phương án khi và chỉ khi ( P ) có phương án. (vì D D )
Nếu bài tốn ( P ) không có PATƯ thì bài tốn (P) không có PATƯ.
Rõ ràng, ( x', x",x2, x', x4, x5) là phương án tối ưu của bài tốn ( P ) khi và chỉ
1 1 3
khi ( x'- x",x2, - x') là phương án tối ưu của bài tốn (P).
1 1 3
Vì các phép biến đổi để đưa bài tốn QHTT tổng quát về bài tốn QHTT chính tắc đều là phép biến đổi tương đương nên ta có kết luận sau.
Kết luận
Mọi bài toán QHTT tổng quát đều có thể đưa về bài toán QHTT dạng chính tắc.
Bài toán tổng quát (P) có phương án khi và chỉ khi bài tốn chính tắc ( P ) có phương án.
Bài toán tổng quát (P) có PATƯ khi và chỉ khi bài toán chính tắc ( P ) có PATƯ.
Như vậy, ta chỉ cần giải bài toán QHTT dạng chính tắc.
2.3. Bài toán qui hoạch tuyến tính dạng chuẩn (còn gọi là dạng chính tắc khả giải)
2.3.1 Bài toán dạng chuẩn
Bài toán sau đây gọi là bài toán QHTT dạng chuẩn Tìm x = (x1, x2,…, xn) nsao cho :
n
(1) f(x) = c jx j
j1
min ( max)
n
(2) aijx jbi
j1
, i = 1, 2, …, m
(3) xj 0 , j = 1, 2, …, n
Trong đó hệ phương trình tuyến tính (2) là hệ phương trình chuẩn và các hệ số vế phải bi0 , i = 1, m .
Nhận xét
Bài toán QHTT dạng chuẩn là trường hợp đặc biệt của bài toán QHTT dạng chính tắc.
Vì bi 0, i = 1, m
thỏa (3).
2.3.2 Phương án cơ bản
nên mỗi nghiệm cơ bản của hệ phương trình chuẩn (2) cũng
Mỗi nghiệm cơ bản của hệ phương trình chuẩn (2) gọi là một phương án cơ bản (PACB) hay phương án cực biên của bài toán QHTT dạng chuẩn. Nói cách khác, một phương án mà các ẩn không cơ bản đều bằng 0 gọi là phương án cơ bản.
Một PACB mà tất cả các ẩn cơ bản đều nhận giá trị dương gọi là PACB không suy biến (bi> 0, i = 1, m ) . Ngược lại, một PACB mà có ít nhất một ẩn cơ bản nhận giá trị 0 gọi là PACB suy biến.
Vì số nghiệm cơ bản của một hệ phương trình chuẩn là hữu hạn nên số PACB của một bài toán QHTT dạng chuẩn cũng hữu hạn.
Ví du 5Các bài toán QHTT sau đây có dạng chuẩn.
a) (1) f(x) = 2x1+ x2-3x3 +x4 +x5 min (max)
x1
(2) x2
10x4
15x4
x3 3x4
2x5 1
3x5 2
7x5 3
(3) xj 0, j 1,5
Phương án (x1, x2, x3,x4,x5) = (1;2;3;0;0) là PACB không suy biến.
b) (1) f(x) = 2x1+3 x2-3x3 +5x4 +x5 –x6 min (max)
2x1
(2) 3x
x2
2x x
3x4
2x
x5 2
4
1 2 3 4
x1
3x2
x4
x6 3
(3) xj 0, j 1,6
Phương án (x1, x2, x3,x4,x5,x6) = (0;0; 4;0;2; 3) là PACB không suy biến. c) (1) f(x) = 2x1+8 x2+3x3-5x4+x5+x6min (max)
2x1
(2) 3x
x2
2x x
3x4
2x
x5 0
4
1 2 3 4
x x x
x 3
1 2 4 6
(3) xj 0, j 1,6
Phương án (x1, x2, x3,x4,x5,x6) = (0; 0; 4; 0; 0; 3) là PACB suy biến.
n
d) (1) f(x) = c jx j
j1
min (max)
x1
(2) x2
a1 m1 xm1
a2 m1 xm1
xm am m1 xm1
, với bi
0, i =1, 2, …, m
| a1n xn | b1 |
| a2n xn | b2 |
| | |
| amn xn | bm |
(3) xj 0 , j = 1, 2, …, n
Phương án (x1, ..., xm, xm+1,...,xn) = (b1,..., bm,0, ..., 0) là PACB. Nếu bi> 0, i = 1, m
thì PACB này không suy biến; nếu bi= 0 thì PACB này suy biến.
Chú ýMọi bài toán QHTT dạng chuẩn đều có thể đánh số lại các ẩn để được bài toán có dạng như trong ví dụ 5.d) này.
2.3.3 Đưa bài toán QHTT dạng chính tắc về bài toán QHTT dạng chuẩn
Cho bài toán QHTT dạng chính tắc ( P ):
n
(1) f(x) = c jx j
j1
min ( max)
n
(2) aijx jbi
j1
, i = 1, 2, …, m
(3) xj 0 , j = 1, 2, …, n
Nếu ( P ) chưa có dạng chuẩn thì ta có thể đưa ( P ) về dạng chuẩn bằng các phép biến đổi sau:
Trong các ràng buộc ở (2) của ( P ), nếu ràng buộc nào có hệ số tự do ở vế phải âm thì ta đổi dấu hai vế để được bi> 0.