Đ2. PHƯƠNG PHÁP ĐIỀU CHỈNH NHÂN TỬ
2.1 Cơ sở toán học của phương pháp.
Cơ sở toán học để giải bài toán SXĐB là dựa vào bài toán đối ngẫu của nó và định lý độ lệch bù yếu. Tức là, ta đi tìm một phương án (z,xij) của bài toán SXĐB và một phương án (ui,vj) của bài toán đối ngẫu của nó thỏa hệ (*) trong tính chất 2. Ý tưởng phương pháp này giống như thuật toán thế vị trong bài toán vận tải nhưng khác nhau ở trình tự thực hiện như sau:
Phương pháp thế vị
Tìm một phương án cơ bản của bài toán vận tải.
Dựa vào phương án cơ bản bài toán vận tải để tìm hệ thống thế vị (ui,vj).
Nếu hệ thống thế vị này thỏa điều kiện là phương án bài toán đối ngẫu tương ứng thì dừng. (stop)
Nếu hệ thống thế vị chưa thỏa điều kiện là phương án của bài toán đối ngẫu thì quay trở lại điều chỉnh phương án cơ bản bài toán vận tải.
Phương pháp điều chỉnh nhân tử
Tìm hệ thống nhân tử (ui,vj) thỏa điều kiện là phương án bài toán đối ngẫu.
Dựa vào hệ thống nhân tử tìm một “Giả phương án “ của bài toán SXĐB.
Nếu “Giả phương án “ này thỏa điều kiện là phương án của bài toán SXĐB thì dừng.(stop)
Nếu “Giả phương án “ này chưa thỏa điều kiện là phương án của bài toán SXĐB thì quay trở lại điều chỉnh nhân tử.
2.2. Thuật toán điều chỉnh nhân tử:
Bước 1Xây dựng hệ thống nhân tử các ô chọn.
1a) Tìm các nhân tử và ô chọn đầu tiên: Nếu cpq = max cij / i = 1, m
; j =1, n thì
(p,q) là ô chọn đầu tiên, up= cpq, vq= 1. Tiếp theo thực hiện luân phiên hai bước 1b) và 1c).
1b) Tìm nhân tử cột và ô chọn tiếp theo: Nếu hàng k đã có nhân tử tìm trên hàng này ckt thỏa ckt = maxckj : cột j chưa có nhân tử. Khi đó nhân tử cột t xác
định như sau: v
= min
ui : hàng i đã có nhân tử
và c
0 = ux
t
c
it
it
cxt
Ô (x,t) là ô chọn tiếp theo.
1c) Tìm nhân tử hàng và ô chọn tiếp theo: Nếu cột s đã có nhân tử tìm trên cột này crs thỏa crs = maxcis: hàng i chưa có nhân tử. Khi đó nhân tử hàng r
xác định như sau: ur= max crjv j: cột j đã có nhân tử = cryvy
Ô (r,y) là ô chọn tiếp theo.
Hai bước 1b), 1c) được thực hiện cho đến khi mọi hàng và mọi cột đều có nhân tử. Sang bước 2.
Bước 2Tìm một giả phương án (z,xij ) của bài toán SXĐB.
m
ui
Gọi S là tập các ô chọn. Đặt z =
i1 n
v j j1
, tìm xij (i = 1, m
; j =1, n ) thỏa
n x
1, i 1, m
ij
j1
với (i, j) S
m
cijx ijz, j 1, n
i1
Bước 3Kiểm tra tính tối ưu.
x ij
0, với
(i, j)S
Nếu xij0 , (i,j) S thì giả phương án (z,xij) là PATƯ của bài toán SXĐB.
Nếu tồn tại ô (i,j) S mà xij< 0 thì sang bước 4.
Bước 4Điều chỉnh nhân tử để tìm giả phương án mới .
4a) Tìm ô đưa ra: Ô đưa ra là ô có xij< 0 nhỏ nhất. Giả sử đó là ô (io, jo). 4b) Tìm hàng và cột điều chỉnh:
Đánh dấu “+” vào hàng iovà đánh dấu “-“ vào cột jo.
Trên hàng i đã đánh dấu “+”, ta đánh dấu “+” cho cột có ô chọn trên hàng này và chưa được đánh dấu.
Trên cột j đã đánh dấu “+”, ta đánh dấu “+” cho hàng có ô chọn trên cột này và chưa được đánh dấu.
Tiếp tục lặp lại việc đánh dấu này cho đến khi không còn đánh dấu được thêm dấu “+” nào nữa. Tất cả các hàng và cột chưa đánh dấu sẽ được đánh dấu “_”.
4c) Tìm hệ số điều chỉnhvà ô đưa vào:
c
= min
ui ijv j
: (i, j)
là ô được đánh dấu (,), cij 0
=
ui*
ci* j* v j*
, ô (i*,j*) là ô
đưa vào.
4d) Sửa nhân tử :
u
=
' ui , nếu hàng i đánh dấu "-"
i ui , nếu hàng i đánh dấu ""
v
'
j
Trở lại bước 2.
v j , nếu cột j đánh dấu "-"
=
v j , nếu cột j đánh dấu ""
Ví dụ 1 Giải bài toán SXĐB sau đây:
C11 | C21 | C3 1 | |
M1 : 1 | 25 | 71 | 50 |
M2: 1 | 40 | 80 | 53 |
M3 : 1 | 24 | 90 | 60 |
Có thể bạn quan tâm!
-
Quy hoạch toán học - Ngô Hữu Tâm - 16 -
Quy hoạch toán học - Ngô Hữu Tâm - 17 -
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 - 20 -
Cỏc Chỉ Tiờu Thơiứ Gian Đối Với Cỏc Sự Kiện. -
Biểu Đồ Thời Gian- Công Việc ( Sơ Đồ Pert Ngang, Sơ Đồ Gantt)
Xem toàn bộ 192 trang tài liệu này.
Bước 1Xây dựng hệ thống nhân tử các ô chọn.
1a) Ô có cước phí lớn nhất là ô (3,2) với c32 = 90, u3= 90, v2= 1. Ô chọn đầu tiên là ô (3,2).
1b) Trên hàng 3: max c3j : j = 1, 3= 60 = c32. Nhân tử cột 3 là
v3 = min
ui
c
: i 3
90=1,5. Ô chọn thứ hai là ô (3,3).
60
=
i3
1c) Trên cột 2 : max ci2: i = 1, 2= 80 = c22. Nhân tử hàng 2 là u2= max c2jvj: j = 2, 3 = 80 = c22v2. Ô chọn thứ ba là ô (2,2).
1b) Trên hàng 2: max c2j : j = 1= 40 =c21. Nhân tử cột 1 là
v1 = min
ui
c
: i 2, 3
80=2. Ô chọn thứ tư là ô (2,1).
40
=
æ1
1c) Trên cột 3 : max cæ3: i = 1= 50 = c13. Nhân tử hàng 1 là u1= max c1jvj: j = 1, 2, 3 = 75 = c13v3. Ô chọn thứ năm là ô (1,3).
Bước 2Xác định giả phương án
v1 = 2 v2 = 1 v3 = 1,5
u1 =75
C.tiết Máy | C1 1 | C2 1 | C31 |
M1 : 1 | 25 | 71 | 50 |
M2: 1 | 40 | 80 | 53 |
M3 : 1 | 24 | 90 | 60 |
u2 = 80
u3 = 90
z = 75 80 90=
2 1 1,5
490, S =(1,3); (2,1); (2,2); (3,2); (3,3), xij = 0 (i,j) S.
9
Lập hệ phương trình
x13
x21
x32
1
x22 1
x33 1
40x21
80x22
13
50x
90x32
60x33
490 / 9
490 / 9
490 / 9
Giải hệ này ta được : x13 = 1, x33 = 2/27, x32 = 25/27, x22 = -13/36, x21= 49/36.
v1 = 2 v2 = 1 v3 = 1,5
u1 =75
C.tiết Máy | C1 1 | C2 1 | C31 |
M1 : 1 | 25 | 71 | 50 1 |
M2: 1 | 40 49/36 | 80 -13/36 | 53 |
M3 : 1 | 24 | 90 25/27 | 60 2/27 |
u2 = 80
u3 = 90
Bước 3Còn ô (2,2) có x22 = -13/36 < 0 nên giả phương án này chưa là phương án.
Bước 4Điều chỉnh nhân tử.
Ô đưa ra là ô (2,2).
Đánh dấu “+” vào hàng 2, đánh dấu “-“ vào cột 2. Dựa vào hàng 2 và ô chọn (2,1) ta đánh dấu “+” vào cột 1. Các hàng và cột còn lại đánh dấu “-“.
v1 = 2 “+”
= 1,5
v2 = 1 “-“
v3 = 1,5 “-“
u1 =75”-“
C.tiết Máy | C1 1 | C2 1 | C31 |
M1 : 1 | 25 | 71 | 50 1 |
M2: 1 | 40 49/36 | 80 -13/36 | 53 |
M3 : 1 | 24 | 90 25/27 | 60 2/27 |
u2 = 80”+”
= 1,5
u3 = 90”-“
= min
75, 90
= 1,5 =
u1. Ô đưa vào là ô (1,1).
25.2
24.2
c11v1
C.tiết Máy | C1 1 | C2 1 | C31 |
M1 : 1 | 25 x | 71 | 50 x |
M2: 1 | 40 x | 80 | 53 |
M3 : 1 | 24 | 90 x | 60 x |
Nhân u2cho 1,5; nhân v1cho 1,5 ta được hệ thống nhân tử và ô chọn mới là
v1 = 3 v2 = 1 v3 = 1,5
S =(1,3); (2,1); (1,1); (3,2); (3,3)
Bước 2Xác định giả phương án
u1 =75
u2 = 120
u3 = 90
z = 75 120 90=
3 1 1,5
570, xij= 0 (i,j) S. Lập hệ phương trình
11
x11
x21
x32
x13 1
1
x33 1
90x32
25x11
13
50x
40x21
60x33
570 / 11
570 / 11
570 / 11
Giải hệ này ta được : x21 = 1, x11 = 26/55, x13 =29/55 , x33 = 14/33, x32 = 19/33.
Đến đây xij0 (
i 1,3 ,
j 1,3 ) nên giả phương án này là PATƯ bài toán SXĐB.
Vậy PATƯ của bài toán SXĐB là :
C1 1 | C2 1 | C31 | |
M1 : 1 | 25 26/55 | 71 | 50 29/55 |
M2: 1 | 40 1 | 80 | 53 |
M3 : 1 | 24 | 90 14/33 | 60 19/33 |
Tổng sản phẩn sản xuất được trong ca là z =
Ví dụ 2
570.
11
Một công ty may mặc ký hợp đồng giao cho khách hàng 50.000 bộ quần áo (mỗi bộ gồm 1 quần, 1 áo). Công ty có hai xí nghiệp I và II với năng suất trung bình của mỗi xí nghiệp khi sản xuất quần, áo được cho trong bảng sau ( quần/ngày, áo/ngày)
Quần 1 | Áo 1 | |
XN I: 1 | 440 | 420 |
XN II: 1 | 500 | 480 |
a) Hỏi phải phân công thời gian sản xuất của các xí nghiệp như thế nào để trong một ngày tạo ra được nhiều bộ quần áo nhất ? Ước tính thời gian trung bình để công ty sản xuất đủ số quần áo hoàn thành hợp đồng.
b) Trong thực tế của dây chuyền sản xuất, để thuận tiện cho việc cung cấp nguyên vật liệu và tổ chức sản xuất, mỗi xí nghiệp không thể vừa sản xuất quần áo trong tất cả các ngày làm việc, mà phải sản xuất quần (hoặc áo) xong rồi mới chuyển sang sản xuất áo (hoặc quần). Hỏi phải phân công trình tự sản xuất quần áo cho các xí nghiệp như thế nào để thuận tiện cho việc tổ chức sản xuất và hoàn thành hợp đồng sớm nhất?
Giải
Đây là bài toán dạng “Bài toán sản xuất đồng bộ”, mỗi bộ gồm 1 quần và 1 áo.
12
ij
1a) maxc : i 1,2; j 1,2 500 c nên ô chọn đầu tiên là ô (1,2), u 500 , v 1
2 1
1b) Chỉ còn cột 2 chưa có nhân tử nên t 2 và nhân tử cột 2 là
v minu2 500 25
2
c
22
480 24
Ô (2,2) là ô chọn tiếp theo.
1c) Chỉ còn hàng 1 chưa có nhân tử nên
r 1 và nhân tử hàng 1 là
1 j
1
j
u maxc v : j 1,2 440
Ô (1,1) là ô chọn tiếp theo.
Tính được :
z 440 500 22560
460,408
1 25 49
S.Phẩm X.Nghiệp | Quần 1 | Áo 1 | ||||||
XN I: 1 | 440 | x11 1 | 420 | x12 0 | ||||
XN II: 1 | 500 | | 480 | | ||||
x | 2 | x | 47 | |||||
21 | 49 | 22 | 49 | |||||
v1 1 | v 25 2 24 | |||||||
24
u1 440
u2 500
Tính được
x11
10,
x12
0 0,
x21
2 0,
49
x22
470 nên giả phương án này là
49
phương án tối ưu.
Thời gian trung bình để công ty sản xuất đủ số quần áo hoàn thành hợp đồng: T 50000 108,6 ngày
22560
49
b) X 11
x11
T 108,6 ;
X 12
x12
T 0 ;
X 21
x21
T 625 4,43 ;
141
X 22
x22
T 625 104,16
6
Quần 1 | Áo 1 | ||||||
XN I: 1 | 440 | X 11 108,6 | 420 | X12 0 | |||
XN II: 1 | 500 | 480 | |||||
X | 625 4,43 | X | 625 104,16 | ||||
21 | 141 | 22 | 6 |
Phân công trình tự sản xuất quần áo cho các xí nghiệp như sau: Xí nghiệp I chỉ sản xuất quần, (khoảng 108,6 ngày); xí nghiệp II sản xuất áo trước (khoảng 104,16 ngày- đủ 50.000 áo), sau đó chuyển sang sản xuất quần (khoảng 4,43 ngày- cùng xí nghiệp I sản xuất đủ 50.000 quần).
§ 3 TRƯỜNG HỢP TỔNG QUÁT CỦA BÀI TOÁN SẢN XUẤT ĐỒNG BỘ
Trong mục § 1 ta giả thiết rằng mỗi loại máy chỉ có 1 chiếc và mỗi sản phẩm chỉ gồm 1 chi tiết mỗi loại. Trong mục này , ta xét bài toán tổng quát : Máy Micó ri
chiếc ( i = 1, m ) và mỗi sản phẩm cần sjchi tiết Cj( j = 1, n ).
Trường hợp máy Micó richiếc và năng suất 1 máy khi sản xuất chi tiết Cj
M
i
là cij. Khi đó ta xem richiếc máy này như “ một chiếc máy “ 'qui ước có
ij
năng suất là C'= ricij.
Trường hợp mỗi sản phẩm cần sjchi tiết Cj, khi đó ta xem sjchi tiết Cjnhư
“một chi tiết” C' qui ước và năng suất so với trước là C'cij.
j ij s j
j
Kết hợp hai trường hợp trên ta được : Bài toán máy Micó richiếc, mỗi sản phẩm cần sjchi tiết Cj, ma trận năng suất ( cij)mxn được đưa về bài toán
M
i
máy '
có 1 chiếc, mỗi sản phẩm cần 1 chi tiết
C' , ma trận năng suất quy
ước ( C'
)mxn với C'
ri cij
. Tức là, khi nhân hàng i cho rivà chia cột j cho sj
ij ij s j
thì ta đưa bài toán SXĐB tổng quát về bài toán SXĐB mà mỗi máy có đúng 1 chiếc và mỗi sản phẩm cần đúng 1 chi tiết mỗi loại. Phương án tối ưu hai bài toán như nhau.
Ví dụ 3 Giải bài toán sản xuất đồng bộ sau
C1 2 | C2 1 | C3 2 | |
M1 : 1 | 10 | 6 | 8 |
M2 : 3 | 8 | 3 | 6 |
M3 : 2 | 5 | 4 | 7 |
Giải
Trước tiên, ta đưa bài toán về dạng mỗi máy có một chiếc và mỗi sản phẩm cần đúng 1 chi tiết mỗi loại. Nhân hàng 2 cho 3, hàng 3 cho 2 ; chia cột 1 cho 2, cột 3 cho 2 ta được bài toán quy ước.