Tổng hợp quy hoạch tuyến tính
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (177.64 KB, 9 trang )
Quy hoạch tuyến tính
TỔNG HỢP QUY HOẠCH TUYẾN TÍNH
Phần I: Bài Toán Quy Hoạch Tuyến Tính với Phương Pháp Đơn Hình.
f(x) = => min (max) (1)
=b
i
(i Є I
1
) (2)
≥(≤)b
i
(i Є I
2
) (3)
Trong đó: f(x) là hàm mục tiêu, còn hệ (2), (3) là hệ phương trình ràng buộc, mỗi
1 phương trình và bất phương trình được gọi là 1 ràng buộc.
- A = |a
ij
|
mxn
là ma trận hệ ràng buộc(ma trận hệ số phân tích).
- A
j
: vectơ cột j của ma trận A – vectơ điều kiện.
- b : vectơ hệ số vế phải của hệ pt ràng buộc.
A. Các tính chất chung của bài toán quy hoạch tuyến tính.
1. Vectơ x thỏa mãn mọi ràng buộc (hệ (2), (3) ) của bài toán thì được gọi là
phương án, thỏa mãn chặt là thỏa mãn với dấu “=” còn thỏa mãn lỏng là
thỏa mãn với dấu bất đẳng thức.
2. Phương Án Cực Biên: là phương án thỏa mãn chặt n ràng buộc độc lập
tuyến tính. PACB thỏa mãn chặt đúng n(số nghiệm của bài toán) ràng
buộc được gọi là PACB không suy biến, còn thỏa mãn chặt hơn n ràng
buộc được gọi là PACB suy biến.
3. Phương Án Tối Ưu: là phương án mà tại đó hàm mục tiêu f(x) đạt cực
tiểu hay cực đại (PATƯ – hay là phương án tốt nhất)
4. Bài toán giải được và không giải được:
- Bài toán giải được là bài toán có PATƯ, tức là có 1 vectơ x thỏa mãn
(1),(2),(3).
- Bài toán không giải được là bài toán không có phương án hoặc có
phương án nhưng hàm mục tiêu không bị chặn (tăng hoặc giảm vô
cùng)
Sinhvienvinh.com hùngbj0
Quy hoạch tuyến tính
5. Sự tồn tại của PACB: 1 PA chỉ là PACB khi và chỉ khi thỏa mãn chặt hệ
đk ràng buộc và hạng của ma trận hệ ràng buộc bằng n = số ẩn số
trong bài toán chính tắc, nếu có PA thì sẽ có PACB vì hạng ma trận hệ
ràng buộc luôn = n.
6. Số PACB của 1 bài toán luôn là hữu hạn.
B. Các dạng bài toán quy hoạch tuyến tính
1. Bài toán dạng tổng quát. (1), (2) & (3).
2. Bài toán dạng chính tắc. (1) & (2) kèm điều kiện x
j
≥0 j .
3. Bài toán dạng chuẩn = bài toán chính tắc kèm thêm điều kiện b
i
≥0 i.
C. Chú ý đặc biệt đối với bài toán dạng chính tắc:
1. Mọi bài toán đều có thể đưa về dạng chính tắc tương đương bằng các
công thức sau:
- ≥(≤)b
i
thì ta lần lượt trừ và cộng thêm ẩn phụ vào 2 vế của
bất pt ràng buộc này.
- Nếu x
j
≤0 thì đặt ẩn thêm ẩn t=- x
j
2. Đặc điểm PACB của bài toán chính tắc: với điều kiện x
j
≥0 của bài toán
này, ta có thể khẳng định 1 PA sẽ là PACB của bài toán chính tắc nếu hệ
vectơ A ={ A
j
: x
j
>0} là hệ độc lập tuyến tính, vì các thành phần PACB
chỉ có thể nhận 2 giá trị =0 hoặc >0 nên hạng của ma trận ràng buộc
trong bài toán chính tắc sẽ bằng m =số thành phần dương trong hệ ẩn của
PACB và hệ vectơ A ={ A
j
: x
j
>0} chính là cơ sở của PACB đó.
Sinhvienvinh.com hùngbj0
Quy hoạch tuyến tính
• Chú ý: với bài toán chính tắc, khi tìm PACB chỉ cần xét hệ ma trận
ràng buộc tương ứng với m thành phần >0 và chứng minh hạng của
ma trận đó =m.
D. Các bước cơ bản giải bài toán QHTT bằng phương pháp đơn hình(đi tìm
PACB tối ưu)
I. Các chú ý cơ bản:
1. Vì chỉ xét bài toán chính tắc nên mọi bài toán QHTT khi bắt đầu giải
đều quy về bài toán dạng chính tắc.
2. Khi có phương án cực biên x
0
và cơ sở J
0
=E thì ma trận hệ số phân tích
sẽ trùng với ma trận điều kiện và các ẩn cơ sở chính là hệ vectơ vế phải
b của hệ pt ràng buộc nên mọi bài toán chính tắc đều quy về dạng
chuẩn có nghĩa là các b đều >0 và vectơ hệ số phân tích của các ẩn cơ
sở tạo nên một ma trận đơn vị.
• Đặc biệt chú ý các ẩn cô lập, tức là ẩn cấu thành hệ vectơ đơn vị,
có thể là ẩn cũ hoặc ẩn phụ thêm vào hoặc ẩn giả.
3. PATƯ duy nhất và tập PATƯ:
- Một PATƯ là duy nhất khi tồn tại
k
<(>)0, k J
0
thì đó là PATƯ duy
nhất.
- Sẽ có tập PATƯ khác khi tồn tại
k
=0, k J
0
:
+ TH1:
k
=0, k J
0
& x
jk
≤0 j J
0
tập PATƯ không bị chặn:
D={x:x=x
0
+ .z
k
; ≥0}
+ TH2:
k
=0, k J
0
& tồn tại x
jk
>0 tập PATƯ bị chặn:
D={x:x=x
0
+ .z
k
;0≤ ≤
0
} với
0
= min{x
0
j
/x
jk
} với đk: j J
0
và x
jk
>0
. z
k
= -x
jk
nếu j J
0
.
z
k
=0 nếu j J
0
và j#k
Sinhvienvinh.com hùngbj0
Quy hoạch tuyến tính
. z
k
=1 nếu j=k
+ Ta sẽ có các PACB tối ưu với dấu “=” của điều kiện =0 và =
0.
II. Các Bước Của PP ĐƠN HÌNH:
1. Tìm PACB nếu có các biến cô lập dựa trên các ẩn phụ và ẩn giả.
- Nếu chỉ cần ẩn phụ tiến hành theo bước 2 bình thường và kết luận
với các ẩn phụ giá trị = 0.(chú ý biến đổi sao cho hệ ẩn cơ sở có ma
trận hệ số phân tích là vectơ đơn vị)
- Nếu có ẩn giả lập bài toán phụ với hàm mục tiêu P(x,x
g
)=
g
i
=>
min và giải bình thường theo PP Đơn Hình cho đến khi tìm được
PACBTƯ (x
0
,x
g
0
).(chú ý các hệ số C khi tính trong bảng đơn hình
có ẩn giả đều =0)
1.1. Nếu trong quá trình biến đổi ta loại được ẩn giả nào thì bước sau
không tính cột ẩn giả đó nữa, và nếu loại hết thì về được bài toán ban
đầu tính lại
k
(với hệ số C như đầu bài)
và giải bình thường từ bước 3.
1.2. Nếu có PACBTƯ (tmãn 3) có P
min
>0 thì bài toán đã cho không
có phương án.
1.3. Nếu có PACBTƯ(tmãn 3) có P
min
=0 thì x
0
PACB của bài toán
gốc tiến hành tính lại các
k
(với hệ số C như đầu bài)
và tiến hành
như sau:
. nếu các ẩn giả đều đã mất (trở thành ẩn phi cơ sở) thì áp dụng
như lúc biến đổi mất hết ẩn giả trong bước 1.1.
. nếu trong hệ cở sở vẫn tồn tại ẩn giả thì bỏ các cột có
P
<0 và
tính lại
k
(với hệ số C như đầu bài)
và giải bình thường với các ẩn bỏ
đi = 0 theo bước 1.1.
2. Lập bảng đơn hình dựa trên PACB đã biết.
3. Kiểm tra dấu hiệu tối ưu:
Sinhvienvinh.com hùngbj0
Quy hoạch tuyến tính
- Nếu
k
≤ (≥)0, k J
0
thì x
0 là
PATƯ dừng bài toán.
- Nếu
k
>(<)0 thì chuyển sang bước 4.
4. Kiểm tra tính không giải được của bài toán:
- Nếu
k
>(<)0 mà x
jk
≤0, j J
0
bài toán không giải được.
- Nếu
k
>(<)0 mà tồn tại ít nhất 1 x
jk
>0 thì chuyển sang bước 5.
5. Lựa chọn ẩn đưa ra và đưa vào cơ sở:
- Chọn Max
k
(Min
k
) =
s
với điều kiện
k
>(<)0 ẩn s được đưa
vào cơ sở mới. – trường hợp Min
k
với điều kiện
k
<0 được áp dụng
trong trường hợp f(x) max.
- Tính
0
= min {x
0
j
/x
js
} với điều kiện x
js
>0 thành phần nào của cơ sở
có
0
min thì đó là ẩn r được đưa ra khỏi cơ sở và thay bằng s.
- Thay đổi cả các hệ số C
r
và C
s
trong bảng đơn hình bước 6.
6. Biến đổi bảng mới: = cách biến các thành phần trong cột ẩn của
phần tử xoay thành cột vectơ đơn vị bao gồm biến đổi cả
k
đối với
các cột khác. lại thực hiện lại từ bước 3 cho đến khi kết thúc: có
PACBTƯ hoặc không giải được.
Sinhvienvinh.com hùngbj0
