Download miễn phí Giáo trình Toán rời rạc - Lý thuyết cơ bản về quy hoạch tuyến tính
Tổng quát những bài toán quy hoạch tuyến tính cụthểtrên, một bài toán quy
hoạch tuyếntính là một mô hình toán tìm cực tiểu (min) hay cực đại (max) của hàm
mục tiêu tuyến tính với các ràng buộc là bất đẳng thức và đẳng thức tuyến tính. Dạng
tổng quát của một bài toán quy hoạch tuyến tính là :
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
sản phẩm làai1x1+ai2x2+...+ainxn
Vì lượng nguyên liệu thứ i=1→m dùng để sản xuất các loại sản phẩm không thể
vượt quá lượng được cung cấp là bi nên :
ai1x1+ai2x2+...+ainxn ≤ bi (i=1,2,...,m)
Vậy theo yêu cầu của bài toán ta có mô hình sau đây :
nn2211
n
1j
jj xc......xcxc xczmax +++== ∑
=
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
=≥
≤+++
≤+++
≤+++
n)1,2,...,(j 0x
bxa...xaxa
..........................................
bxa...xaxa
bxa...xaxa
j
mnmn22m11m
2nn2222121
1nn1212111
3- Bài toán vận tải
Người ta cần vận chuyển hàng hoá từ m kho đến n cửa hàng bán lẻ.
Lượng hàng hoá ở kho i là si (i=1,2,...,m) và nhu cầu hàng hoá của cửa hàng j là dj
LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
9
(j=1,2,...,n). Cước vận chuyển một đơn vị hàng hoá từ kho i đến của hàng j là cij ≥ 0
đồng.
Giả sử rằng tổng hàng hoá có ở các kho và tổng nhu cầu hàng hoá ở các cửa
hàng là bằng nhau, tức là :
∑∑
==
=
n
1j
j
m
1i
i ds
Bài toán đặt ra là lập kế hoạch vận chuyển để tiền cước là nhỏ nhất, với điều
kiện là mỗi cửa hàng đều nhận đủ hàng và mỗi kho đều trao hết hàng.
Gọi xij ≥ 0 là lượng hàng hoá phải vận chuyển từ kho i đến cửa hàng j. Cước
vận chuyển chuyển hàng hoá i đến tất cả các kho j là :
∑
=
n
1j
ijijxc
Cước vận chuyển tất cả hàng hoá đến tất cả kho sẽ là :
∑∑
= =
=
m
1i
n
1j
ijijxcz
Theo yêu cầu của bài toán ta có mô hình toán sau đây :
⎪⎩
⎪⎨
⎧
==≥
==
=
∑
∑∑
=
= =
n)1,1,...,(j m)1,2,...,(i 0x
n)1,2,...,(j dx
xcz min
ij
m
1i
jij
m
1i
n
1j
ijij
II- QUY HOẠCH TUYẾN TÍNH TỔNG QUÁT VÀ
CHÍNH TẮC
1- Quy hoạch tuyến tính tổng quát
Tổng quát những bài toán quy hoạch tuyến tính cụ thể trên, một bài toán quy
hoạch tuyến tính là một mô hình toán tìm cực tiểu (min) hay cực đại (max) của hàm
mục tiêu tuyến tính với các ràng buộc là bất đẳng thức và đẳng thức tuyến tính. Dạng
tổng quát của một bài toán quy hoạch tuyến tính là :
LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
10
( )
( )
( )⎪
⎪⎪
⎪⎪
⎪
⎩
⎪⎪
⎪⎪
⎪⎪
⎨
⎧
⎪⎩
⎪⎨
⎧
∈
∈≤
∈≥
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
∈≥
∈≤
∈=
=
∑
∑
∑
∑
=
=
=
=
3j
2j
1j
3i
n
1j
jij
2i
n
1j
jij
1i
n
1j
jij
n
1j
jj
Jj tùy ý x
(III) Jj 0x
Jj 0x
)I(i bxa
(II) )I(i bxa
)I(i bxa
(I) xcz maxmin/
Trong đó :
• (I) Hàm mục tiêu
Là một tổ hợp tuyến tính của các biến số, biểu thị một đại lượng nào đó mà ta
cần quan tâm của bài toán.
• (II) Các ràng buộc của bài toán
Là các phương trình hay bất phương trình tuyến tính n biến số, sinh ra từ điều
kiện của bài toán.
• (III) Các các hạn chế về dấu của các biến số
Người ta cũng thường trình bày bài toán quy hoạch tuyến tính dưới dạng ma
trận như sau :
[ ]
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
==
mnm21m
2n2221
1n1211
ij
a ... a a
......................
a ... a a
a ... a a
aA
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
m
2
1
n
2
1
n
2
1
b
...
b
b
b
c
...
c
c
c
x
...
x
x
x
Gọi ai (i=1→m) là dòng thứ i của ma trận A, ta có :
LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
11
( )
( )
( )⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
⎪⎩
⎪⎨
⎧
∈
∈≤
∈≥
⎪⎩
⎪⎨
⎧
∈≥
∈≤
∈=
=
3j
2j
1j
3ii
2ii
1ii
T
Jj tùy ý x
(III) Jj 0x
Jj 0x
)I(i bxa
(II) )I(i bxa
)I(i bxa
(I) xc)x(zin/max m
Người ta gọi :
- A là ma trận hệ số các ràng buộc.
- c là vectơ chi phí (cT là chuyển vị của c)
- b là vectơ giới hạn các ràng buộc.
2- Quy hoạch tuyến tính dạng chính tắc
Bài toán quy hoạch tuyến tính chính tắc là bài toán quy hoạch tuyến tính mà
trong đó các ràng buộc chỉ có dấu = và các biến số đều không âm.
⎪⎪⎩
⎪⎪⎨
⎧
=≥
==
=
∑
∑
=
=
(III) n)1,2,...,(j 0x
(II) )m1,2,...,(i bxa
(I) xczmin/max
j
i
n
1j
jij
n
1j
jj
( m≤ n )
rang(A)=m
⎪⎩
⎪⎨
⎧
≥
=
=
(III) 0x
(II) bAx
(I) xc)x(z min/max T
Người ta có thể biến đổi bài toán quy hoạch tuyến tính dạng tổng quát thành
bài toán quy hoạch tuyến tính dạng chính tắc nhờ các quy tắc sau đây :
- Nếu gặp ràng buộc i có dạng ≤ thì người ta cộng thêm vào vế trái của ràng
buộc một biến phụ xn+i ≥ 0 để được dấu = .
LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
12
- Nếu gặp ràng buộc i có dạng ≥ thì người ta trừ vào vế trái của ràng buộc một
biến phụ xn+i ≥ 0 để được dấu = .
Các biến phụ chỉ là những đại lượng giúp ta biến các ràng buộc dạng bất đẳng
thức thành đẳng thức, nó phải không ảnh hưởng gì đến hàm mục tiêu nên không xuất
hiện trong hàm mục tiêu.
- Nếu biến xj ≤ 0 thì ta đặt xj = -x’j với x’j ≥ 0 rồi thay vào bài toán.
- Nếu biến xj là tuỳ ý thì ta đặt jjj xxx ′′−′= với jj x , x ′′′ đều ≥ 0 rồi thay vào
bài toán.
- Trong trường hợp trong số các ràng buộc có dòng mà vế phải của dòng đó là
giá trị âm thì đổi dấu cả hai vế để được vế phải là một giá trị không âm.
Dựa vào các phép biến đổi trên mà người ta có thể nói rằng bài toán quy
hoạch tuyến tính chính tắc là bài toán quy hoạch tuyến tính mà trong đó các ràng
buộc chỉ có dấu = , vế phải và các biến số đều không âm.
Ví dụ :
Biến đổi bài toán quy hoạch tuyến tính sau đây về dạng chính tắc :
⎪⎪
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎪⎪
⎨
⎧
⎪⎪⎩
⎪⎪⎨
⎧
≤
≥
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=+−+
≥++
−≥++
≤+++−
−++−=
tùy ý x , x
0x
0x , x
20xx2xx
10x3xx2
1xx2x
7xx2xx2x
x2xx2xx2)x(z min
32
4
51
4321
543
432
54321
54321
Bằng các thay thế :
)0x,x( xxx
)0x,x( xxx
)0x( xx
33333
22222
444
≥′′′′′−′=
≥′′′′′−′=
≥′′−=
ta được :
LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
13
0x,x, x, x, x, x, x, x, x , x
20x)xx(2)xx(x
10xx3x)xx(2
1xx)xx(2)xx(
7xxx2)xx()xx(2x
x2x)xx(2)xx(x2)x(z min
4332287651
433221
85433
743322
65433221
5433221
≥′′′′′′′
⎪⎪⎩
⎪⎪⎨
⎧
=′−′′−′−′′−′+
=−+′−′′−′
−=−+′′−′+′′−′
=++′−′′−′+′′−′−
−′−′′−′+′′−′−=
hay :
0x,x, x, x, x, x, x, x, x, x
20x)xx(2)xx(x
10xx3x)xx(2
1xx)xx(2)xx(
7xxx2)xx()xx(2x
x2x)xx(2)xx(x2)x(z min
4332287651
433221
85433
743322
65433221
5433221
≥′′′′′′′
⎪⎪⎩
⎪⎪⎨
⎧
=′−′′−′−′′−′+
=−+′−′′−′
=+−′′−′−′′−′−
=++′−′′−′+′′−′−
−′−′′−′+′′−′−=
3- Phương án
Xét bài toán quy hoạch tuyến tính chính tắc :
(P)
⎩⎨
⎧
≥
=
=
0x
bAx
xc)x(z min/max T
• x=[x1 x2 ... xn] T là một phương án của (P) khi và chỉ khi Ax =
b.
• x=[x1 x2 ... xn] T là một phương án khả thi của (P) khi và chỉ
khi Ax = b và x ≥ 0 .
• Một phương án tối ưu của (P) là một phương án khả thi của (P)
mà giá trị của hàm mục tiêu tương ứng đạt min/max.
LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
14
III- ĐẶC ĐIỂM CỦA TẬP HỢP CÁC PHƯƠNG ÁN
1- Khái niệm lồi và các tính chất
a- Tổ hợp lồi
- Cho m điểm xi trong không gian Rn . Điểm x được gọi là tổ hợp lồi của các
điểm xi nếu :
1.... 0,....,,
x...xx xx
n21n21
m
m
2
2
1
1
m
1i
i
i
=α++α+α≥ααα
α++α+α=α= ∑
=
- ...