Chương 1
BÀI TOÁN
QUY HOẠCH TUYẾN TÍNH
20/6/2012 1MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
NỘI DUNG
1. Bài toán QHTT tổng quát
2. Các dạng của bài toán QHTT
3.
Các
tính
chất
của
bài
toán
QHTT
3.
Các
tính
chất
của
bài
toán
QHTT
4. Phương pháp hình học
5. Phương pháp đơn hình
20/6/2012 2MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Bài toán QHTT tổng quát
Là bài toán có dạng:
=
= →
≤ =
∑
∑
1
( ) max(min)
, 1,..., (1)
n
j j
j
n
f x c x
a x b i p
20/6/2012 3MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
=
=
≤ =
= = +
≥ =
∈ = +
∑
∑
ℝ
1
1
, 1,..., (1)
, 1,..., (2)
0, 1,..., (3)
, 1,..., (4)
ij j i
j
n
ij j i
j
j
j
a x b i p
a x b i p m
x j q
x j q n
Bài toán QHTT tổng quát
trong đó: là nbiến cần tìm ;
các số được cho sẵn.
biểu thức (1),(2) gọi là các ràng buộc(RB) của bài toán;
biểu
thức
(
3
),
(
4
)
gọi
là
RB
(
điều
kiện
)
về
dấu
của
biến
.
=
, 1,...,
j
x j n
= =
, 1,..., ; , , 1,...,
j ij i
c j n a b i m
biểu
thức
(
3
),
(
4
)
gọi
là
RB
(
điều
kiện
)
về
dấu
của
biến
.
20/6/2012 4MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
Bài toán QHTT tổng quát
•GọiD:= {x: thỏa mãn các ràng buộc (1) – (4)} là
tập ràng buộc(hay miền chấp nhậnđược (cnđ))
của bt.
•
Mỗi
gọi
là
phương
án
(PA)
cnđ
.
∈
x D
•
Mỗi
gọi
là
phương
án
(PA)
cnđ
.
•PA cnđthỏa mãn
(đ/v bài toán min)
được gọi là PA tốiưu(PATƯ).
•Giá trị được gọi là giá trị(mục tiêu) tốiưu.
20/6/2012 5MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
*
x
≤ ∀ ∈
*
( ) ( ),
f x f x x D
*
( )
f x