Bài tập Quy hoạch tuyến tính | Đại học Công nghiệp Thành phố Hồ Chí Minh

Bài tập Quy hoạch tuyến tính | Đại học Công nghiệp Thành phố Hồ Chí Minh. Tài liệu gồm 111 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!

Môn:
Thông tin:
111 trang 5 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Bài tập Quy hoạch tuyến tính | Đại học Công nghiệp Thành phố Hồ Chí Minh

Bài tập Quy hoạch tuyến tính | Đại học Công nghiệp Thành phố Hồ Chí Minh. Tài liệu gồm 111 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!

61 31 lượt tải Tải xuống
Bài giảng: Quy
hoạch tuyến tính
Lớp Toán VB2-K2-Mr.Trung
BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HCM
Nguyễn Đức Phương
Bài giảng
Quy hoạch tuyến tính
MSSV: . . . . . . . . . . . . . . . . . . . . . . . . . . .
Họ tên: . . . . . . . . . . . . . . . . . . . . . . . . . . .
TP. HCM Ngày 22 tháng 12 năm 2010
Lớp Toán VB2-K2-Mr.Trung
Mục lục
Mục lục iii
1 Giới thiệu quy hoạch tuyến tính 1
1.1 Một số dụ dẫ n đến bài toán quy hoạch tuyến tính . . . . . 1
1.2 Các dạng của bài toán quy hoạch tuyến tính . . . . . . . . . . 5
1.2.1 Bài to án quy hoạch tuyến tính dạng tổng quát . . . . . 5
1.2.2 Bài to án quy hoạch tuyến tính dạng chuẩn . . . . . . . 5
1.2.3 Bài to án quy hoạch tuyến tính dạng chính tắc . . . . . 6
1.3 Quan hệ dạng chun và chính tắ c . . . . . . . . . . . . . . . . 8
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc . . . . . . . 8
1.3.2 Biến không ràng buộc . . . . . . . . . . . . . . . . . . 9
1.3.3 Quan hệ dạng chuẩn, chính tắc . . . . . . . . . . . . . 10
1.4 Dạng ma t rận của bài toán quy hoạch . . . . . . . . . . . . . 13
1.5 Phương án chấp nhận được . . . . . . . . . . . . . . . . . . . 14
1.6 Ý nghĩa nh học của bài toán quy hoạch tuyến tính . . . . . 16
1.6.1 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . 16
1.6.2 Tính chất của tập phươ ng án chấp nhận được . . . . . 17
1.7 Điểm cực biên . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Phương án bản chấp nhận được . . . . . . . . . . . . . . . 22
1.8.1 Nghiệm bản của Ax D b . . . . . . . . . . . . . . . 23
1.8.2 Thành lập phương án cực biên . . . . . . . . . . . . . . 25
1.8.3 Phương án cực biên và phương án tối ưu . . . . . . . . 30
Lớp Toán VB2-K2-Mr.Trung
MỤC LỤC ii
1.9 Bài tậ p chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . 31
2 Phương pháp đơn hình 33
2.1 Phương pháp đơn hình cho bài to án quy hoạch dạng chuẩn . . 33
2.1.1 Phương án cực biên ban đầu . . . . . . . . . . . . . . . 36
2.1.2 Dấu hiệu tối ưu . . . . . . . . . . . . . . . . . . . . . . 37
2.1.3 Chọn biến vào sở . . . . . . . . . . . . . . . . . . . 40
2.1.4 Chọn biến ra khỏi sở . . . . . . . . . . . . . . . . . 4 1
2.1.5 Lập bảng đơn hình mới . . . . . . . . . . . . . . . . . . 42
2.2 Thuật toán đơn hình cho bài toán min . . . . . . . . . . . . . 50
2.3 Bài to án chính tắc không sẵ n ma t rận đơn vị . . . . . . . . 52
2.4 Bài tậ p chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . 58
3 thuyết đối ngẫu 63
3.1 dụ dẫn đến bái toán đối ngẫu . . . . . . . . . . . . . . . . 63
3.1.1 Bài to án đối ngẫu của bài toán max . . . . . . . . . . . 65
3.1.2 Bài to án đối ngẫu của bài toán min . . . . . . . . . . . 67
3.2 Các định l ý về đối ngẫu . . . . . . . . . . . . . . . . . . . . . 70
3.3 Bài tậ p chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . 77
4 Bài toán vận tải 80
4.1 Bài to án vn tải cân bằng thu phát . . . . . . . . . . . . . . . 80
4.2 Phương án cực biên của bài to án vận tải . . . . . . . . . . . . 82
4.3 Các phương pháp thành lập phương án cực biên . . . . . . . . 86
4.3.1 Phương pháp cước phí thấp nhất . . . . . . . . . . . . 86
4.3.2 Phương pháp c Tây - Bắc . . . . . . . . . . . . . . . 87
4.3.3 Phương pháp Vogel (Fogel) . . . . . . . . . . . . . . . 87
4.4 Thuật toán thế vị giải bài toán vận tải . . . . . . . . . . . . . 89
4.4.1 Thuật toán quy không cước phí ô chọn . . . . . . . . . 89
4.4.2 y dựng phương án cực biên mới . . . . . . . . . . . 93
Lớp Toán VB2-K2-Mr.Trung
MỤC LỤC iii
4.5 Một số trường hợp đặc biệt của bài toán vận tải . . . . . . . . 98
4.5.1 Bài to án vận tải không cân bằ ng thu phát . . . . . . . 98
4.5.2 Bài to án vận tải ô cấm . . . . . . . . . . . . . . . . 100
4.6 Bài to án vn tải cực đại cước phí . . . . . . . . . . . . . . . . 101
4.7 Bài tậ p chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . 103
Tài liệu tham khảo 106
Lớp Toán VB2-K2-Mr.Trung
Chương 1
Giới thiệu quy hoạch tuyến tính
1.1 Một số dụ dẫn đến bài toán quy hoạch tuyến tính
dụ 1.1 (Bài toán l p kế hoạch sản xuất). Một trại cưa các khúc gỗ thành
các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng tro ng y
dựng. Giả sử, đối với:
Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10 m ván.
Ván xây dưng cần 3 giờ để cưa và 3 giờ để bào 10m vá n.
y cưa làm việc tối đa 8 giờ trong ngày, và y bào làm việc tối đa 15 giờ
trong ngày. Nếu lợi nhuận của 10m ván thành phẩm 120 (ngàn đồng), và
lợi nhuận của 10m ván xây dựng 100 (ngàn đồng). Trong ngày, trại cưa
phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất ?
Giải.
Lớp Toán VB2-K2-Mr.Trung
1.1 Một số dụ dẫn đến bài toán quy hoạch tuyến tính 2
dụ 1.2 (Bài toán khẩu phầ n ăn). Chuyên gi a dinh dưỡng định thành lập
một thực đơn gồm 2 loại t hực phẩm chính A và B. Cứ một (tră m g ram):
Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate và 4 đơn
vị prot ein.
Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydr ate và 3 đơn
vị prot ein.
Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) và một (trăm g ram)
thực phẩm B giá 25 (ngàn đồng). Nhà dinh dưỡng muốn thức ăn phải cung
cấp ít nhất 18 đơn vị chất béo, 12 đơn vị carbohydrate và 24 đơn vị protein.
Bao nhiêu (trăm gram) thực phẩm mỗi loại để giá nhỏ nhất nhưng vn
cung cấp đủ dinh dưỡng?
Giải.
Lớp Toán VB2-K2-Mr.Trung
1.1 Một số dụ dẫn đến bài toán quy hoạch tuyến tính 3
dụ 1.3 (Bài toán vận tải). Một nhà sản xuấ t 2 nhà máy: Một nhà
y Vĩnh Phúc và một nhà máy Bình Dương. 3 kho hàng phân phối
sản phẩm đặt Nội, TP. HC M và Cần Thơ. Nhà y Vĩnh phúc; Bình
Dương, khả năng cung cấp tối đa 100; 140 tấn mỗi tuần. Lượng cầ u của
các k ho Nội, TP. HCM và Cần Thơ lần lượt từ 100; 60 và 80 tấ n trở
lên. Chi phí vận chuyển (trăm ngàn) mỗi tấn cho như bả ng bên dưới. H i
cần vận chuyển bao nhiêu tấn hàng hóa từ nhà sản xuất đến các kho hàng
Nội, TP. HCM và cần thơ để chi phí nhỏ nhất nhưng vẫn đáp ứng đủ
nhu cầu?
Giải.
Lớp Toán VB2-K2-Mr.Trung
1.1 Một số dụ dẫn đến bài toán quy hoạch tuyến tính 4
Trạm phát
Trạm thu
Nội TP. HCM Cần thơ
W
1
:100 W
2
:60 W
3
:80
Vĩnh Phúc-Q
1
: 100 5 7 9
Bình Dương-Q
2
:140 8 7 10
Lớp Toán VB2-K2-Mr.Trung
1.2 c dạng của bài toán quy hoạch tuyến tính 5
1.2 Các dạng của bài toán quy hoạch tuyến tính
1.2.1 Bài toán quy hoạch tuyến tính dạng tổng quát
Từ các dụ mục 1 .1, bài toán quy hoạch tuyến tính tổng quát được phát
biểu như sau: Tìm x
1
; x
2
; : : : ; x
n
sao cho
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max .hay min/ (1.1)
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
./.D/ b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
./.D/ b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
./.D/ b
m
(1.2)
Hàm t uyến tính (1 .1) gọi m mục tiêu. Hệ bất phương trình tuyến nh
(1.2) gọi là các r àng buộc. Vế trái của các r àng buộc các hàm tuyến t ính
với x
1
; x
2
; : : : ; x
n
các bi ến số.
1.2.2 Bài toán quy hoạch tuyến tính dạng chuẩn
Chúng ta i bài to án quy hoạch tuyến tính dạ ng chuẩn nếu dạng
như sau: Tìm x
1
; x
2
; : : : ; x
n
sao cho
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max; .hay min/ (1.3)
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
b
m
(1.4)
x
j
0; j D 1; 2; : : : ; n (1.5)
Lớp Toán VB2-K2-Mr.Trung
1.2 c dạng của bài toán quy hoạch tuyến tính 6
1.2.3 Bài toán quy hoạch tuyến tính dạng chính tắc
Chúng ta i bài toán quy hoạch tuyến tính dạng chính tắc
nếu
dạng như sau: Tìm x
1
; x
2
; : : : ; n sao cho
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max; .hay min/ (1.6)
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
D b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
D b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
D b
m
(1.7)
x
j
0; j D 1; 2; : : : ; n (1.8)
dụ 1.4. Cho biết dạng của các bài toán quy hoạch tuyến tính sau:
a. z D 3x
1
C 2x
2
! m in
Với các ràng buộc
2x
1
C x
2
4
3x
1
2x
2
6
x
1
0; x
2
0
b. z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2x
2
3x
3
4
2x
1
C 3x
2
C 2x
3
6
3x
1
x
2
C 2x
3
8
x
1
0; x
2
0; x
3
0
c. z D 3x
1
C 2x
2
C 3x
3
2x
4
! max
Với các ràng buộc
8
<
:
2x
1
C 6x
2
C 2x
3
4x
4
D 7
3x
1
C 2x
2
5x
3
C x
4
D 8
6x
1
C 7x
2
C 2x
3
C 5x
4
4
x
1
0; x
2
0; x
3
0; x
4
0
d. z D 2x
1
C 5x
2
C x
3
C x
4
C 4x
5
! min
Một số sách định nghĩa khác v dạng chuẩn và dạng chính tắc. Các bạn cần đọc kỹ định nghĩa khi
tham khảo các tài liệu khác.
Lớp Toán VB2-K2-Mr.Trung
1.2 c dạng của bài toán quy hoạch tuyến nh 7
Với các ràng buộc
3x
1
C 2x
2
x
3
C 2x
5
D 4
4x
1
C 5x
2
C 3x
3
C 2x
4
D 7
x
1
0; x
2
0; x
3
0; x
4
0; x
5
0
e. z D 2x
1
C 5x
2
! m ax
Với các ràng buộc
3x
1
C 2x
2
6
2x
1
C 9x
2
8
x
1
0
f. z D 2x
1
C 3x
2
! m in
Với các ràng buộc
8
<
:
2x
1
C x
2
x
3
D 4
3x
1
C 2x
2
C x
3
D 8
x
1
x
2
D 6
x
1
0; x
2
0
Chú ý. i t oán tìm giá trị nhỏ nhất của hàm mục tiêu thể viết thành bài
toán tìm giá tr lớn nhất của hàm mục tiêu và ngược lại. Điều này các bạn
sẽ thấy qua quan hệ:
min
n
X
j D1
c
j
x
j
D max
0
@
n
X
j D1
c
j
x
j
1
A
(1.9)
tương đương
min z D max.z/ (1.10 )
Do đó, không mất tính tổng quát trong phần thuyết ta chỉ phát biểu bài
toán t ìm g iá trị lớn nhất của hàm mục tiêu .max z/. Bài toá n tìm giá trị nhỏ
nhất hàm mục t iêu .minz/ thì thể sử dụng (1.10).
dụ 1.5. C huyển các bài toán quy hoạch tuyến t ính tìm max m mục
tiêu thành tìm min hàm mục tiêu hay ngược lại
a. z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2x
2
3x
3
4
2x
1
C 3x
2
C 2x
3
6
3x
1
x
2
C 2x
3
8
x
1
0; x
2
0; x
3
0
Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 8
b. z D 3x
1
C 2x
2
! m in
Với các ràng buộc
2x
1
C x
2
4
3x
1
2x
2
6
x 0; y 0
Giải.
1.3 Quan hệ dạng chuẩn và chính tắc
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc
Nếu ta nhân hai vế của bất phương trình
k
1
x
1
C k
2
x
2
C C k
n
x
n
b
với 1 ta được bất phương trình
k
1
x
1
k
2
x
2
k
n
x
n
b
Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 9
dụ 1.6. Chuyển bài toán quy hoạch tuyến nh sau sang dạng chuẩ n:
z D 2x
1
C 3x
2
C 4x
3
! m ax
Với các ràng buộc
8
<
:
3x
1
C 2x
2
3x
3
4
2x
1
C 3x
2
C 2x
3
6
3x
1
x
2
C 2x
3
8
x
1
0; x
2
0; x
3
0
Giải.
1.3.2 Biến không ràng buộc
Giả sử x
j
không ràng buộc, chúng ta thể thay x
j
bằng hai biến x
C
j
và
x
j
x
j
D x
C
j
x
j
trong đó x
C
j
0 và x
j
0: Điều này nghĩa một số bất kỳ chính hiệu
của ha i số không â m. Với cách này chúng ta thể chuyển bài toá n không
ràng buộc về biến thành bài toán ràng buộc v biến.
dụ 1.7. Chuyển bài toán quy hoạch tuyến nh sau sang dạng chuẩ n
z D 2x
1
C 5x
2
! max (1.11 )
Với các ràng buộc
3x
1
C 2x
2
6
2x
1
C 9x
2
8
(1.12 )
x
1
0 (1.13 )
Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 10
Giải.
Nhận x ét. Mọi bài toán quy ho ch tuyến tính đều thể chuyển đổi thành
dạng chuẩn bằng các cách như trên.
1.3.3 Biến đổi bài toán quy hoạch dạng chuẩn thành d ạng chính
tắc
Xét ràng buộc t hức i trong i toán quy hoạch tuyến nh dạng chuẩn
a
i1
x
1
C a
i2
x
2
C C a
i n
x
n
b
i
(1.14 )
Chúng ta thể chuyển ràng buộc (1.14) thành phương trình tuyến tính bằng
cách thêm vào biến phụ x
nCi
0; và
a
i1
x
1
C a
i2
x
2
C C a
i n
x
n
C x
nCi
D b
i
(1.15 )
Bài toán quy hoạch tuyến tính dạng chuẩn chuyển thành dạng c nh tắc
dạng như sau
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C C a
1n
x
n
C x
nC1
D b
1
a
21
x
1
C C a
2n
x
n
C x
nC2
D b
2
:
:
:
:
:
:
:
:
:
a
m1
x
1
C C a
mn
x
n
C x
nCm
D b
m
x
1
0; : : : ; x
n
0; x
nC1
0; : : : ; x
nCm
0
Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 11
dụ 1.8. Chuyển bài toán quy hoạch tuyến nh sau sang dạng chính tắ c
z D 120x
1
C 100x
2
! m ax
Với các ràng buộc
2x
1
C 3x
2
8
5x
1
C 3x
2
15
x
1
0; x
2
0
Giải.
dụ 1.9. Chuyển các bài toán quy hoạch t uyến tính sau sang dạng chính
tắc
a. z D 3x
1
C 2x
2
! m in
Với các ràng buộc
2x
1
C x
2
4
3x
1
2x
2
6
x
1
0; x
2
0
Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 12
b. z D 2x
1
C 3x
2
C 4x
3
! max
Với các ràng buộc
8
<
:
3x
1
C 2x
2
3x
3
4
2x
1
C 3x
2
C 2x
3
6
3x
1
x
2
C 2x
3
8
x
1
0; x
2
0; x
3
0
c. z D 3x
1
C 2x
2
C 3x
3
2x
4
! max
Với các ràng buộc
8
<
:
2x
1
C 6x
2
C 2x
3
4x
4
D 7
3x
1
C 2x
2
5x
3
C x
4
D 8
6x
1
C 7x
2
C 2x
3
C 5x
4
4
x
1
0; x
2
0; x
3
0; x
4
0
d. z D 2x
1
C 5x
2
! m ax
Với các ràng buộc
3x
1
C 2x
2
6
2x
1
C 9x
2
8
x
1
0
Lớp Toán VB2-K2-Mr.Trung
1.4 Dạng ma trận của bài toán quy hoạch 13
e. z D 2x
1
C 3x
2
! m in
Với các ràng buộc
8
<
:
2x
1
C x
2
x
3
D 4
3x
1
C 2x
2
C x
3
D 8
x
1
x
2
D 6
x
1
0; x
3
0
1.4 Dạng ma trận của bài toán quy hoạch
Xét bài toán quy hoạch dạng chuẩn:
z D c
1
x
1
C c
2
x
2
C C c
n
x
n
! max
Với các ràng buộc
8
ˆ
ˆ
ˆ
<
ˆ
ˆ
ˆ
:
a
11
x
1
C a
12
x
2
C C a
1n
x
n
b
1
a
21
x
1
C a
22
x
2
C C a
2n
x
n
b
2
:
:
:
:
:
:
:
:
:
:
:
:
a
m1
x
1
C a
m2
x
2
C C a
mn
x
n
b
m
x
j
0; j D 1; 2; : : : ; n
Lớp Toán VB2-K2-Mr.Trung
1.5 Phương án chấp nhận được 14
Đặt
A D
0
B
B
B
@
a
11
a
12
a
1n
a
21
a
22
a
2n
:
:
:
:
:
:
:
:
:
a
m1
a
m2
a
mn
1
C
C
C
A
; x D
0
B
B
B
@
x
1
x
2
:
:
:
x
n
1
C
C
C
A
; b D
0
B
B
B
@
b
1
b
2
:
:
:
b
m
1
C
C
C
A
; c D
0
B
B
B
@
c
1
c
2
:
:
:
c
n
1
C
C
C
A
Chúng ta t hể viết bài toán quy hoạch trên thành dạng ma trận: Tìm
x 2 R
n
sao cho
z D c
T
x ! max
Với các ràng buộc
Ax b
x 0
dụ 1.10. Viết bài toá n quy hoạch tuyến nh sau dưới dạng ma trận.
z D 120x
1
C 100x
2
! m ax
Với các ràng buộc
2x
1
C 3x
2
8
5x
1
C 3x
2
15
x
1
0; x
2
0
Giải.
1.5 Phương án chấp nhận đưc
Định nghĩa 1.1 (Phương án chấp nhận được). Véct ơ x 2 R
n
thỏa tất c
các ràng buộc của bài toá n quy hoạch tuyến tính được gọi phươn g án chấp
nhận được.
Lớp Toán VB2-K2-Mr.Trung
1.5 Phương án chấp nhận được 15
dụ 1.11. Cho i toán q uy hoạch tuyến tính:
z D 120x
1
C 100x
2
! m ax
Với các ràng buộc
2x
1
C 3x
2
8
5x
1
C 3x
2
15
x
1
0; x
2
0
và c phương án:
x
1
D
1
2
; x
2
D
2
1
; x
3
D
1
3
; x
4
D
2
2
Phương án o phương án chấp nhận được?
Giải.
Định nghĩa 1.2 (Phương á n tối ưu). Phương án chấp nh n được làm cho
hàm mục tiêu có giá trị lớn nhất (nế u bài toán ma x) hay nh nhất (nếu
bài toá n min) thì được gọi l à phương án tối ưu.
Lớp Toán VB2-K2-Mr.Trung
| 1/111

Preview text:


Bài giảng: Quy
hoạch tuyến tính Lớp Toán VB2-K2-Mr.Trung BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HCM
Nguyễn Đức Phương Bài giảng
Quy hoạch tuyến tính
MSSV: . . . . . . . . . . . . . . . . . . . . . . . . . . .
Họ tên: . . . . . . . . . . . . . . . . . . . . . . . . . . .
TP. HCM – Ngày 22 tháng 12 năm 2010 Lớp Toán VB2-K2-Mr.Trung Mục lục Mục lục iii
1 Giới thiệu quy hoạch tuyến tính 1
1.1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính . . . . . 1
1.2 Các dạng của bài toán quy hoạch tuyến tính . . . . . . . . . . 5
1.2.1 Bài toán quy hoạch tuyến tính dạng tổng quát . . . . . 5
1.2.2 Bài toán quy hoạch tuyến tính dạng chuẩn . . . . . . . 5
1.2.3 Bài toán quy hoạch tuyến tính dạng chính tắc . . . . . 6
1.3 Quan hệ dạng chuẩn và chính tắc . . . . . . . . . . . . . . . . 8
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc . . . . . . . 8
1.3.2 Biến không ràng buộc . . . . . . . . . . . . . . . . . . 9
1.3.3 Quan hệ dạng chuẩn, chính tắc . . . . . . . . . . . . . 10
1.4 Dạng ma trận của bài toán quy hoạch . . . . . . . . . . . . . 13
1.5 Phương án chấp nhận được . . . . . . . . . . . . . . . . . . . 14
1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính . . . . . 16
1.6.1 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . 16
1.6.2 Tính chất của tập phương án chấp nhận được . . . . . 17
1.7 Điểm cực biên . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Phương án cơ bản chấp nhận được . . . . . . . . . . . . . . . 22
1.8.1 Nghiệm cơ bản của Ax D b . . . . . . . . . . . . . . . 23
1.8.2 Thành lập phương án cực biên . . . . . . . . . . . . . . 25
1.8.3 Phương án cực biên và phương án tối ưu . . . . . . . . 30 Lớp Toán VB2-K2-Mr.Trung MỤC LỤC ii
1.9 Bài tập chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . 31 2 Phương pháp đơn hình 33
2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn . . 33
2.1.1 Phương án cực biên ban đầu . . . . . . . . . . . . . . . 36
2.1.2 Dấu hiệu tối ưu . . . . . . . . . . . . . . . . . . . . . . 37
2.1.3 Chọn biến vào cơ sở . . . . . . . . . . . . . . . . . . . 40
2.1.4 Chọn biến ra khỏi cơ sở . . . . . . . . . . . . . . . . . 41
2.1.5 Lập bảng đơn hình mới . . . . . . . . . . . . . . . . . . 42
2.2 Thuật toán đơn hình cho bài toán min . . . . . . . . . . . . . 50
2.3 Bài toán chính tắc không có sẵn ma trận đơn vị . . . . . . . . 52
2.4 Bài tập chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . 58 3 Lý thuyết đối ngẫu 63
3.1 Ví dụ dẫn đến bái toán đối ngẫu . . . . . . . . . . . . . . . . 63
3.1.1 Bài toán đối ngẫu của bài toán max . . . . . . . . . . . 65
3.1.2 Bài toán đối ngẫu của bài toán min . . . . . . . . . . . 67
3.2 Các định lý về đối ngẫu . . . . . . . . . . . . . . . . . . . . . 70
3.3 Bài tập chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . 77 4 Bài toán vận tải 80
4.1 Bài toán vận tải cân bằng thu phát . . . . . . . . . . . . . . . 80
4.2 Phương án cực biên của bài toán vận tải . . . . . . . . . . . . 82
4.3 Các phương pháp thành lập phương án cực biên . . . . . . . . 86
4.3.1 Phương pháp cước phí thấp nhất . . . . . . . . . . . . 86
4.3.2 Phương pháp góc Tây - Bắc . . . . . . . . . . . . . . . 87
4.3.3 Phương pháp Vogel (Fogel) . . . . . . . . . . . . . . . 87
4.4 Thuật toán thế vị giải bài toán vận tải . . . . . . . . . . . . . 89
4.4.1 Thuật toán quy không cước phí ô chọn . . . . . . . . . 89
4.4.2 Xây dựng phương án cực biên mới . . . . . . . . . . . 93 Lớp Toán VB2-K2-Mr.Trung MỤC LỤC iii
4.5 Một số trường hợp đặc biệt của bài toán vận tải . . . . . . . . 98
4.5.1 Bài toán vận tải không cân bằng thu phát . . . . . . . 98
4.5.2 Bài toán vận tải có ô cấm . . . . . . . . . . . . . . . . 100
4.6 Bài toán vận tải cực đại cước phí . . . . . . . . . . . . . . . . 101
4.7 Bài tập chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . 103 Tài liệu tham khảo 106 Lớp Toán VB2-K2-Mr.Trung Chương 1
Giới thiệu quy hoạch tuyến tính
1.1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính
Ví dụ 1.1 (Bài toán lập kế hoạch sản xuất). Một trại cưa các khúc gỗ thành
các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây
dựng. Giả sử, đối với:
Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m ván.
Ván xây dưng cần 3 giờ để cưa và 3 giờ để bào 10m ván.
Máy cưa làm việc tối đa 8 giờ trong ngày, và máy bào làm việc tối đa 15 giờ
trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn đồng), và
lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa
phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất? Giải. Lớp Toán VB2-K2-Mr.Trung
1.1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính 2
Ví dụ 1.2 (Bài toán khẩu phần ăn). Chuyên gia dinh dưỡng định thành lập
một thực đơn gồm 2 loại thực phẩm chính A và B. Cứ một (trăm gram):
Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate và 4 đơn vị protein.
Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydrate và 3 đơn vị protein.
Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) và một (trăm gram)
thực phẩm B giá 25 (ngàn đồng). Nhà dinh dưỡng muốn thức ăn phải cung
cấp ít nhất 18 đơn vị chất béo, 12 đơn vị carbohydrate và 24 đơn vị protein.
Bao nhiêu (trăm gram) thực phẩm mỗi loại để có giá nhỏ nhất nhưng vẫn
cung cấp đủ dinh dưỡng? Giải. Lớp Toán VB2-K2-Mr.Trung
1.1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính 3
Ví dụ 1.3 (Bài toán vận tải). Một nhà sản xuất có 2 nhà máy: Một nhà
máy ở Vĩnh Phúc và một nhà máy ở Bình Dương. Có 3 kho hàng phân phối
sản phẩm đặt ở Hà Nội, TP. HCM và Cần Thơ. Nhà máy ở Vĩnh phúc; Bình
Dương, có khả năng cung cấp tối đa 100; 140 tấn mỗi tuần. Lượng cầu của
các kho ở Hà Nội, TP. HCM và Cần Thơ lần lượt từ 100; 60 và 80 tấn trở
lên. Chi phí vận chuyển (trăm ngàn) mỗi tấn cho như bảng bên dưới. Hỏi
cần vận chuyển bao nhiêu tấn hàng hóa từ nhà sản xuất đến các kho hàng ở
Hà Nội, TP. HCM và ở cần thơ để chi phí nhỏ nhất nhưng vẫn đáp ứng đủ nhu cầu? Giải. Lớp Toán VB2-K2-Mr.Trung
1.1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính 4
❵❵❵❵❵❵❵❵ Trạm thu Hà Nội TP. HCM Cần thơ ❵❵❵❵ Trạm phát ❵❵❵ W :100 :60 :80 1 W2 W3 Vĩnh Phúc-Q : 100 5 7 9 1 Bình Dương-Q :140 8 7 10 2 Lớp Toán VB2-K2-Mr.Trung
1.2 Các dạng của bài toán quy hoạch tuyến tính 5
1.2 Các dạng của bài toán quy hoạch tuyến tính
1.2.1 Bài toán quy hoạch tuyến tính dạng tổng quát
Từ các ví dụ mục 1.1, bài toán quy hoạch tuyến tính tổng quát được phát
biểu như sau: Tìm x1; x2; : : : ; xn sao cho
z D c1x1 C c2x2 C C cnxn ! max .hay min/ (1.1) Với các ràng buộc 8 ˆ a ˆ 11x1 C a12x2 C C a1nxn ./.D/ b1 ˆ
< a21x1 C a22x2 C C a2nxn ./.D/ b2 : (1.2) : :: :: :: ˆ : : : : ˆ ˆ
: am1x1 C am2x2 C C amnxn ./.D/ bm
Hàm tuyến tính (1.1) gọi là hàm mục tiêu. Hệ bất phương trình tuyến tính
(1.2) gọi là các ràng buộc. Vế trái của các ràng buộc là các hàm tuyến tính với x là các biến số. 1; x2; : : : ; xn
1.2.2 Bài toán quy hoạch tuyến tính dạng chuẩn
Chúng ta nói bài toán quy hoạch tuyến tính có dạng chuẩn nếu nó có dạng như sau: Tìm x sao cho 1; x2; : : : ; xn
z D c1x1 C c2x2 C C cnxn ! max; .hay min/ (1.3) Với các ràng buộc 8 ˆ a ˆ 11x1 C a12x2 C C a1nxn b1 ˆ
< a21x1 C a22x2 C C a2nxn b2 : (1.4) : :: :: :: ˆ : : : : ˆ ˆ : am1x1 C am2x2 C C amnxn bm xj 0; j D 1; 2; : : : ; n (1.5) Lớp Toán VB2-K2-Mr.Trung
1.2 Các dạng của bài toán quy hoạch tuyến tính 6
1.2.3 Bài toán quy hoạch tuyến tính dạng chính tắc
Chúng ta nói bài toán quy hoạch tuyến tính có dạng chính tắc nếu nó có
dạng như sau: Tìm x1; x2; : : : ; n sao cho
z D c1x1 C c2x2 C C cnxn ! max; .hay min/ (1.6) Với các ràng buộc 8 ˆ a ˆ 11x1 C a12x2 C C a1nxn D b1 ˆ
< a21x1 C a22x2 C C a2nxn D b2 : (1.7) : :: :: :: ˆ : : : : ˆ ˆ : am1x1 C am2x2 C C amnxn D bm xj 0; j D 1; 2; : : : ; n (1.8)
Ví dụ 1.4. Cho biết dạng của các bài toán quy hoạch tuyến tính sau: a. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2 4 3x1 2x2 6 x1 0; x2 0 b. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0
c. z D 3x1 C 2x2 C 3x3 2x4 ! max Với các ràng buộc 8 2x < 1 C 6x2 C 2x3 4x4 D 7 3x1 C 2x2 5x3 C x4 D 8 : 6x1 C 7x2 C 2x3 C 5x4 4 x1 0; x2 0; x3 0; x4 0
d. z D 2x1 C 5x2 C x3 C x4 C 4x5 ! min
Một số sách có định nghĩa khác về dạng chuẩn và dạng chính tắc. Các bạn cần đọc kỹ định nghĩa khi
tham khảo các tài liệu khác. Lớp Toán VB2-K2-Mr.Trung
1.2 Các dạng của bài toán quy hoạch tuyến tính 7 Với các ràng buộc 3x1 C 2x2 x3 C 2x5 D 4 4x1 C 5x2 C 3x3 C 2x4 D 7 x1 0; x2 0; x3 0; x4 0; x5 0 e. z D 2x1 C 5x2 ! max Với các ràng buộc 3x1 C 2x2 6 2x1 C 9x2 8 x1 0 f. z D 2x1 C 3x2 ! min Với các ràng buộc 8 2x < 1 C x2 x3 D 4 3x1 C 2x2 C x3 D 8 : x1 x2 D 6 x1 0; x2 0
Chú ý. Bài toán tìm giá trị nhỏ nhất của hàm mục tiêu có thể viết thành bài
toán tìm giá trị lớn nhất của hàm mục tiêu và ngược lại. Điều này các bạn sẽ thấy qua quan hệ: 0 1 n n min X X cj xj D max @ cj xj A (1.9) j D1 j D1 tương đương min z D max. z/ (1.10)
Do đó, không mất tính tổng quát trong phần lý thuyết ta chỉ phát biểu bài
toán tìm giá trị lớn nhất của hàm mục tiêu .max z/. Bài toán tìm giá trị nhỏ
nhất hàm mục tiêu .min z/ thì có thể sử dụng (1.10).
Ví dụ 1.5. Chuyển các bài toán quy hoạch tuyến tính tìm max hàm mục
tiêu thành tìm min hàm mục tiêu hay ngược lại a. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0 Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 8 b. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2 4 3x1 2x2 6 x 0; y 0 Giải.
1.3 Quan hệ dạng chuẩn và chính tắc
1.3.1 Đổi chiều bất đẳng thức của các ràng buộc
Nếu ta nhân hai vế của bất phương trình k1x1 C k2x2 C C knxn b
với 1 ta được bất phương trình k1x1 k2x2 knxn b Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 9
Ví dụ 1.6. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn: z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0 Giải.
1.3.2 Biến không ràng buộc
Giả sử x không có ràng buộc, chúng ta có thể thay bằng hai biến và j xj xC j xj xj D xC x j j
trong đó xC 0 và x 0: Điều này có nghĩa là một số bất kỳ chính là hiệu j j
của hai số không âm. Với cách này chúng ta có thể chuyển bài toán không có
ràng buộc về biến thành bài toán có ràng buộc về biến.
Ví dụ 1.7. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn z D 2x1 C 5x2 ! max (1.11) Với các ràng buộc 3x1 C 2x2 6 (1.12) 2x1 C 9x2 8 x1 0 (1.13) Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 10 Giải.
Nhận xét. Mọi bài toán quy hoạch tuyến tính đều có thể chuyển đổi thành
dạng chuẩn bằng các cách như trên.
1.3.3 Biến đổi bài toán quy hoạch dạng chuẩn thành dạng chính tắc
Xét ràng buộc thức i trong bài toán quy hoạch tuyến tính dạng chuẩn a (1.14) i1x1 C ai 2x2 C C ai nxn bi
Chúng ta có thể chuyển ràng buộc (1.14) thành phương trình tuyến tính bằng
cách thêm vào biến phụ xnCi 0; và a (1.15)
i1x1 C ai 2x2 C C ai nxn C xnCi D bi
Bài toán quy hoạch tuyến tính dạng chuẩn chuyển thành dạng chính tắc có dạng như sau z D c1x1 C c2x2 C C cnxn ! max Với các ràng buộc 8 ˆ a ˆ 11x1 C C a1nxn C xnC1 D b1 ˆ < a21x1 C C a2nxn C xnC2 D b2 :: :: :: ˆ : : : ˆ ˆ : am1x1 C C amnxn C xnCm D bm
x1 0; : : : ; xn 0; xnC1 0; : : : ; xnCm 0 Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 11
Ví dụ 1.8. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chính tắc z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 8 5x1 C 3x2 15 x1 0; x2 0 Giải.
Ví dụ 1.9. Chuyển các bài toán quy hoạch tuyến tính sau sang dạng chính tắc a. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2 4 3x1 2x2 6 x1 0; x2 0 Lớp Toán VB2-K2-Mr.Trung
1.3 Quan hệ dạng chuẩn và chính tắc 12 b. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 8 3x < 1 C 2x2 3x3 4 2x1 C 3x2 C 2x3 6 : 3x1 x2 C 2x3 8 x1 0; x2 0; x3 0
c. z D 3x1 C 2x2 C 3x3 2x4 ! max Với các ràng buộc 8 2x < 1 C 6x2 C 2x3 4x4 D 7 3x1 C 2x2 5x3 C x4 D 8 : 6x1 C 7x2 C 2x3 C 5x4 4 x1 0; x2 0; x3 0; x4 0 d. z D 2x1 C 5x2 ! max Với các ràng buộc 3x1 C 2x2 6 2x1 C 9x2 8 x1 0 Lớp Toán VB2-K2-Mr.Trung
1.4 Dạng ma trận của bài toán quy hoạch 13 e. z D 2x1 C 3x2 ! min Với các ràng buộc 8 2x < 1 C x2 x3 D 4 3x1 C 2x2 C x3 D 8 : x1 x2 D 6 x1 0; x3 0
1.4 Dạng ma trận của bài toán quy hoạch
Xét bài toán quy hoạch dạng chuẩn: z D c1x1 C c2x2 C C cnxn ! max Với các ràng buộc 8 ˆ a ˆ 11x1 C a12x2 C C a1nxn b1 ˆ
< a21x1 C a22x2 C C a2nxn b2 :: :: :: :: ˆ : : : : ˆ ˆ : am1x1 C am2x2 C C amnxn bm xj 0; j D 1; 2; : : : ; n Lớp Toán VB2-K2-Mr.Trung
1.5 Phương án chấp nhận được 14 Đặt 0 1 0 1 0 1 0 1 a11 a12 a1n x1 b1 c1 B a C B x C B b C B c C A 21 a22 a2n 2 2 2 D B C B C B C B C B :: ::
:: C ; x D B :: C ; b D B :: C ; c D B :: C @ : : : A @ : A @ : A @ : A am1 am2 amn xn bm cn
Chúng ta có thể viết bài toán quy hoạch trên thành dạng ma trận: Tìm x 2 Rn sao cho z D cT x ! max Với các ràng buộc Ax b x 0
Ví dụ 1.10. Viết bài toán quy hoạch tuyến tính sau dưới dạng ma trận. z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 8 5x1 C 3x2 15 x1 0; x2 0 Giải.
1.5 Phương án chấp nhận được
Định nghĩa 1.1 (Phương án chấp nhận được). Véctơ x 2 Rn thỏa tất cả
các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được. Lớp Toán VB2-K2-Mr.Trung
1.5 Phương án chấp nhận được 15
Ví dụ 1.11. Cho bài toán quy hoạch tuyến tính: z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2 8 5x1 C 3x2 15 x1 0; x2 0 và các phương án: 1 2 1 2 x1 D ; x ; x ; x 2 2 D 1 3 D 3 4 D 2
Phương án nào là phương án chấp nhận được? Giải.
Định nghĩa 1.2 (Phương án tối ưu). Phương án chấp nhận được làm cho
hàm mục tiêu có giá trị lớn nhất (nếu là bài toán max) hay nhỏ nhất (nếu là
bài toán min) thì được gọi là phương án tối ưu. Lớp Toán VB2-K2-Mr.Trung