Ô đưa ra là ô (3,3) và lượng điều chỉnh là cước phí” các ô chọn ta được:
x33 200 . Lập phương án mới rồi “quy 0
Xí nghiệp Sản phẩm | B1 1600 | B2 2000 | B3 2400 |
A1:2800 | 0 1600 | 0 1000 | 0,5 M 200 |
A2:2200 | 1 M | 1 M | 0 2200 |
A3: 1000 | 0,5 | 0 1000 | 0 0 |
Có thể bạn quan tâm!
-
Thuật Toán “ Quy 0 Cước Phí Các Ô Chọn” Giải Bài Toán Vận Tải Hàm Mục Tiêu Cực Đại: -
Thuật Toán Thế Vị Giải Bài Toán Vận Tải Hàm Mục Tiêu Cực Đại -
Quy hoạch toán học - Ngô Hữu Tâm - 16 -
Nội Dung Và Mô Hình Toán Học Của Bài Toán. -
Quy hoạch toán học - Ngô Hữu Tâm - 19 -
Quy hoạch toán học - Ngô Hữu Tâm - 20
Xem toàn bộ 192 trang tài liệu này.
cho
r1 0
r2 0,5 M
r3 0
s1 0
s2 0
s3 M 0,5
Tính lại “cước phí” các ô
B1 1600 | B2 2000 | B3 2400 | |||
A1:2800 | 0 | 1600 | 0 | 1000 | 0 200 |
A2:2200 | 1,5 | 1,5 | 0 2200 | ||
A3: 1000 | 0,5 | 0 | 1000 | M 0,5 0 | |
Tất cả các ô đều có cước phí không âm nên phương án cơ bản nà tối ưu. Vì ô cấm
(3,3) nhận giá trị 0 nên bài toán có phương án tối ưu là:
B1 1600 | B2 2000 | B3 2400 | ||||
A1:2800 | 7 | 1600 | 7,5 | 1000 | 8 | 200 |
A2:2200 | 8 | 0 | 8,5 | 0 | 7,5 | 2200 |
Tổng chi phí bé nhất:
10.000 đoàng)
f min 11600 7,5 1000 8 200 7,5 2200 =27200(đôn vò tính
Ví dụ 7
272000 (đôn vò tính 1.000 đoàng)
272000000
đoàng
272 (triệu đồng)
Một công ty may mặc cần phân phối 2200 đơn vị sản phẩm may mặc loại A1, 2800 đơn vị sản phẩm may mặc loại A2vào ba xí nghiệp B1, B2, B3để sản xuất, với năng lực sản xuất (số đơn vị sản phẩm loại A1hay sản phẩm loại A2) lần lượt là 1600, 2400, 2000 đơn vị sản phẩm. Chi phí (đơn vị tính 10.000 đồng/1đơn vị sản phẩm) sản xuất của công ty khi phân phối mỗi đơn vị sản phẩm cho các xí nghiệp sản xuất được cho trong bảng sau
B1 1600 | B2 2400 | B3 2000 | |
A1:2200 | 8 | 8 | 8,5 |
A2:2800 | 7,5 | 9 | 8 |
Vì chiến lược phát triển công ty, nên xí nghiệp B2phải thu đủ 2400 đơn vị sản phẩm để sản xuất. Hỏi phải phân phối sản phẩm cho các xí nghiệp sản xuất như thế nào để tổng chi phí thấp nhất và tính tổng chi phí thấp nhất đó?
Giải
Bài tốn này có dạng bài tốn vận tải không cân bằng thu phát với lượng phát ít hơn
lượng thu là
(1600 2400 2000) (2200 2800) 1000 . Lập thêm trạm giả
A3với
lượng cần phát
a3 1000 . Để trạm
B2thu đủ thì lượng hàng giả trạm
A3 không được
phát vào trạm
B2nên ô
(3,2)
là ô cấm, vì cần tổng chi phí thấp nhất nên đây là bài
toán
f min
do đó “cước phí” ô (3,2)
là M (với M là số dương lớn tùy ý).
Lần lượt phân phối như sau: ô (2,1)
ô (3,3) 800
1600 ; ô (1,2)
2200; ô (2,3)
1200; ô (3,2)
200;
Xí nghiệp Sản phẩm | B1 1600 | B2 2400 | B3 2000 | |||
A1:2200 | 8 | 8 | 2200 | 8,5 | ||
A2:2800 | 7,5 | 1600 | 9 | 8 | 1200 | |
A3: 1000 | 0 | M | 200 | 0 | 800 | |
Sau khi phân phối xong ta được phương án cơ bản ban đầu không suy biến, rồi tiếp theo “quy 0 cước phí” các ô chọn ta được:
r1 M
cho
r2 0
r3 8
s1 7,5
Tính lại “cước phí” các ô
s2 M 8
s3 8
B1 1600 | B2 2400 | B3 2000 |
M+0,5 | 0 2200 | M+0,5 | |
A2:2800 | 0 1600 | -M+1 Đưa vào | 0 1200 |
A3: 1000 | 0,5 | 0 Đưara 200 | 0 800 |
Còn ô (2,2) có “cước phí” âm nên phương án cơ bản hiện có không tối ưu. Ô đưa vào là ô (2,2).
Vòng điều chỉnh là V (2,2), (2,3), (3,2), (3,3), V L(2,2), (3,3),V C(2,3), (3,2).
Ô đưa ra là ô (3,2)
và lượng điều chỉnh là
x32 200 . Lập phương án mới rồi “quy 0
Xí nghiệp Sản phẩm | B1 1600 | B2 2400 | B3 2000 |
A1:2200 | M+0,5 | 0 2200 | M+0,5 |
A2:2800 | 0 1600 | -M+1 200 | 0 1000 |
A3: 1000 | 0,5 | 0 0 | 0 1000 |
cước phí” các ô chọn ta được:
r1 M 1
cho
r2 0
r3 0
s1 0
Tính lại “cước phí” các ô
s2 M 1
s3 0
Xí nghiệp Sản phẩm | B1 1600 | B2 2400 | B3 2000 | |||
A1:2200 | 1,5 | 0 | 2200 | 1,5 | ||
A2:2800 | 0 | 600 | 0 | 200 | 0 | 1000 |
A3: 1000 | 0,5 | M-1 | 0 | 0 | 1000 | |
r1 M 1
cho
r2 0
r3 0
s1 0
s2 M 1
s3 0
Tất cả các ô đều có cước phí không âm nên phương án cơ bản nà tối ưu. Vì ô cấm
(3,2)
nhận giá trị 0 nên bài toán có phương án tối ưu là:
B1 1600 | B2 2400 | B3 2000 | ||||
A1:2200 | 8 | 0 | 8 | 2200 | 8,5 | 0 |
A2:2800 | 7,5 | 1600 | 9 | 200 | 8 | 1000 |
Tổng chi phí bé nhất: f min 8 2200 7,5 1600 9 200 8 1000 =39400(đôn vò tính 10.000 đoàng)
39400 (đôn vò tính 1.000 đoàng)
394000000
đoàng
394 (triệu đồng)
Chú yù Có thể giải bằng thuật toán thế vị ( gọn hơn thuật toán quy 0 cước phí 2 bảng vận tải).
Ví dụ 8
Một công ty cần bán 120 đơn vị sản phẩm loại A1, 45 đơn vị sản phẩm loại A2, 85 đơn vị sản phẩm loại A3thông qua bốn đại lý B1, B2, B3, B4với khả năng bán (số đơn vị sản phẩm loại A1hay sản phẩm loại A2hay sản phẩm loại A3) lần lượt là 60, 90, 70, 50 đơn vị sản phẩm. Lợi nhuận (đơn vị tính 500.000 đồng/1sản phẩm) khi bán mỗi sản phẩm thông qua mỗi đại lý được cho trong bảng sau
B160 | B290 | B3 70 | B4 50 | |
A1:120 | 3 | 4 | 4 | 5 |
A2:45 | 4 | 6 | 5 | 4,5 |
A3:85 | 6 | 6 | 7 | 8 |
Vì chiến lược phát triển kinh doanh của công ty, nên đại lý B1phải thu đủ 60 đơn vị sản phẩm để bán. Hỏi phải phân phối sản phẩm cho các đại lý bán như thế nào để tổng lợi nhuận lớn nhất và tính tổng lợi nhuận lớn nhất đó?
Giải
Bài toán này có dạng bài toán vận tải không cân bằng thu phát với lượng phát ít hơn
lượng thu là
(60 90 70 50) (120 45 85) 20 . Lập thêm trạm giả
A4 với lượng
cần phát
a4 20 . Để trạm
B1thu đủ thì lượng hàng giả trạm
A4không được phát
vào trạm
B1nên ô
(4,1)
là ô cấm, vì cần tổng lợi nhuận lớn nhất nên đây là bài toán
f max
do đó
C41 M
(với M là số dương lớn tùy ý).
Lần lượt phân phối như sau: ô (3,4)
50 ; ô (3,3)
35; ô
(2,2)
45; ô (1,2)
45; ô (1,3)
35 ; ô (1,1) 40 ; ô (4,1) 20.
B1 60 | B2 90 | B3 70 | B450 | |
A1:120 | 3 40 | 4 45 | 4 35 | 5 |
A2:45 | 4 | 6 45 | 5 | 4,5 |
A3:85 | 6 | 6 | 7 35 | 8 50 |
A4:20 Trạm giả | M 20 | 0 | 0 | 0 |
Sau khi phân phối xong ta được phương án cơ bản ban đầu không suy biến, tìm các thế vị hàng và các thế vị cột rồi tiếp theo tính kij ui+ vj- cij ta được được:
Đại lý Sản phẩm | B1 60 | B2 90 | B3 70 | B450 | ||||||||
A1:120 | 3 | | 0 40 | 4 | | 0 45 | 4 | | 0 35 | 5 | 0 | |
A2:45 | 4 | 1 | 6 | | 0 45 | 5 | 1 | 4,5 | 2,5 | |||
A3:85 | 6 | 0 | 6 | 1 | 7 | | 0 35 | 8 | | 0 50 | ||
A4:20 Trạm giả | M 0 Đưa ra 20 | 0 | 1 M Đưa vào | 0 | 1 M | 0 | 2 M | |||||
cho
u
1 0
u2 2
u3 3
u4 M 3
v1 3
v2 4
v3 4
v4 5
Ô (4,2)
ô (4,2).
có
k42 1 M 0
nên phương án cơ bản hiện có không tối ưu. Ô đưa vào là
Đại lý Sản phẩm | B1 60 | B2 90 | B3 70 | B450 | ||||||||
A1:120 | 3 | | 0 60 | 4 | | 0 25 | 4 | | 0 35 | 5 | 0 | |
A2:45 | 4 | 1 | 6 | | 0 45 | 5 | 1 | 4,5 | 2,5 | |||
A3:85 | 6 | 0 | 6 | 1 | 7 | | 0 35 | 8 | | 0 50 | ||
A4:20 | M | M 1 | 0 | 0 20 | 0 | 0 | 0 | 1 | ||||
cho
u
v1 3
v2 4
v3 4
v4 5
1 0
u2 2
u3 3
u4 4
Tất cả các ô đều có
kij 0 nên phương án cơ bản này tối ưu. Vì ô cấm (4,1)
nhận giá
trị phân phối
x41 0
nên bài toán ban đầu có phương án tối ưu là:
B160 | B290 | B3 70 | B4 50 | |
A1:120 | 3 60 | 4 25 | 4 35 | 5 |
A2:45 | 4 | 6 45 | 5 | 4,5 |
A3:85 | 6 | 6 | 7 35 | 8 50 |
Tổng lợi nhuận lớn nhất:
f max [3 60 4 25 4 35 6 45 7 35 8 50] 500.000 đoàng
= 1335 500.000 đoàng = 667500000 đoàng
Chú ý: Có thể giải bằng thuật toán quy 0 cước phí.
....................................................................................................................................
Bài tập
Bài 3.1Tìm phương án cơ bản ban đầu ( f
min)
B1 60 | B2 90 | B3 55 | B4 45 | |
A1: 100 | 3 | 4 | 3,5 | 5 |
A2: 70 | 4 | 6 | 5 | 4,5 |
A3: 80 | 5 | 5,5 | 6 | 4,5 |
a) Trường hợp
f min
b) Trường hợp
f max
Bài 3.2Giải bài toán vận tải ( f
min)
B1 70 | B2 80 | B3 65 | B4 85 | |
A1: 100 | 5 | 4 | 6 | 7 |
A2: 50 | 8 | 5 | 5 | 6,5 |
A3: 60 | 5,5 | 6,5 | 7 | 7,5 |
A4: 90 | 6 | 7 | 4 | 5 |
Bài 3.3Cho bài toán vận tải ( f
min)
B1 60 | B2 90 | B3 70 | B4 50 | |
A1: 80 | 3 | 4 | 4 | 5 |
A2: 45 | 4 | 6 | 5 | 4,5 |
A3: 85 | 5 | 5 | 6 | 7 |
a) Giải bài toán trên.
b) Giải bài toán trên với điều kiện trạm B3thu đủ hàng.
Bài 3.4Cho bài toán vận tải ( f
max)
B1 60 | B2 90 | B3 70 | B4 50 | |
A1: 80 | 3 | 4 | 4 | 5 |
A2: 45 | 4 | 6 | 5 | 4,5 |
A3: 85 | 5 | 5 | 6 | 7 |
a) Giải bài toán trên.
b) Giải bài toán trên với điều kiện trạm B1thu đủ hàng.
Bài 3.5Một nông trường có 3 khu đất A1, A2, A3có diện tích tương ứng 250, 1400, 350 ha. Nông trường định trồng 4 loại cây B1, B2, B3, B4với diện tích dự định là 500, 400, 600, 500 ha. Lợi nhuận khi trồng loại cây Bjtrên một ha đất Ailà cij (triệu đồng) được cho trong bảng sau:
B1 500 | B2 400 | B3 600 | B4 500 | |
A1:250 | 22 | 25 | 20 | 18 |
A2:1400 | 30 | 32 | 25 | 28 |
A3:350 | 29 | 28 | 25 | 23 |
Hãy lập kế hoạch trồng cây của nông trường sao cho tổng lợi nhuận cao nhất.
Đáp soá
Khu đất A1trồng 250 ha loại cây B3.
Khu đất A2trồng 500 ha loại cây B1, 400ha loại cây B2, 500 ha loại cây B4.
Khu đất A3trồng 350 ha loại cây B3.
Tổng lợi nhuận lớn nhất là: 55 550 000 000 đồng.
Bài 3.6Một xí nghiệp có 200 công nhân gồm : 50 loại A1, 70 loại A2, 80 loại A3 . Xí nghiệp lại có 200 máy gồm : 40 loại B1, 60 loại B2, 100 loại B3.Khi sản xuất mỗi công nhân sử dụng một máy để tạo ra cùng một loại sản phẩm. Công nhân lọai A3 không sử dụng được máy lọai B1. Năng suất của mỗi loại công nhân khi sử dụng mỗi loại máy được cho trong bảng sau (sản phẩm/ giờ ). Hỏi phải phân công lao độngnhư thế nào để trong 1 giờ tạo ra được nhiều sản phẩm nhất?
B1 40 | B2 60 | B3 100 | |
A1: 50 | 4 | 4 | 7 |
A2: 70 | 5 | 10 | 9 |
A3: 80 | -- | 6 | 5 |
Bài 3.7Một xí nghiệp có 30 công nhân loại I, 20 công nhân loại II và 10 công nhân loại III. Xí nghiệp có 10 máy A, 25 máy B, 25 máy C. Năng suất của mỗi công nhân đối với mỗi loại máy ( sản phẩm/ giờ) được cho trong bảng sau đây.