TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 1/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
BÀI TẬP QUI HOẠCH TUYẾN TÍNH
TS. Nguyễn Thò Ngọc Thanh
I. PHƯƠNG PHÁP ĐƠN HÌNH VÀ BÀI TOÁN ĐỐI NGẪU
Giải bài toán qui hoạch tuyến tính sau và tìm phương án tối ưu khác (nếu có ) :
1) f(x) = -x
1
+ 2x
2
- x
3
 max
x
1
- 2x
2
+ x
3 6
-2x
1
+ x
2
- 2x
3
+ 4x
4
 5

= 2
- x
2
+ 3x
3
+ 7x
4
 2
2x
3
+ 3x
4
 5
x
j
 0 ( j = 1,2,3 )
(Chú ý : Đặt x
4
= x
1
4
- x
2
4
. Đáp số : x= (0, 0, 16 , - 9 , 17, 0) ; f(x) = - 25 )
3) f(x) = 3x
1
- x
2
+ 2x

+ 2x
4
+

x
5  9
x
j
 0 ( j = 1,2,3,4,5 )
(Chú ý : Cách chọn ẩn đưa vào trong bảng đơn hình 2.)
Đáp số : x= (0, 17, 37/2 , 9/2 , 0, ) ; f(x) = 31/2 )
4) f(x) = 2x
1
- 3x
2
- 4x
3
+ x
4
 min
3x
1
+ x
2
+ 2x
3
- 4x

3
 min
- x
1
+ x
2
+ 2x
3
= 6
x
1
+ 2x
2
+ (m-2) x
3
 5
3x
1-

x
2
+ 2x
3
= 14
x
j
 0 ( j = 1,2, 3 )

- 2x
4
 - 4
- x
2
+ x
3
+ x
4
= 4
x
j
 0 ( j = 12,3,4 )
TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 2/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
a) Giải bài toán trên khi m = 2.
b) Với giá trò nào của m phương án tối ưu tìm được trong câu a cũng là phương án tối
ưu của bài toán?
c) Với những giá trò nào của m bài toán không có phương án tối ưu ?
( Đ.S : ( 2 , 0 , 4 , 0 , 16 ) ; m

 0 ; m < 0)

7) Cho bài toán qui hoạch tuyến tính sau :
f(x) = (8 + 2)x
1
+ (7 + 7)x
2
+ (3 + 2)x
3

 min
x
1
+ x
2
+ x
3
 6
2x
1
+ x
2
+ x
3
 7
x
1
+ 2x
2
= 5
x
j
 0 ( j = 1,2,3 )
a/ Giải bài toán trên. Tìm phương án tối ưu khác (nếu có)
b) Viết bài toán đối ngẫu. Tìm phương án tối ưu của bài toán đối ngẫu.
(Đs: x
1
= (3,1,0,2,0) ; x
2
= (5,0, 0,1,3) ; y = ( 0, 0 ,1) , fmin = dmax = 5 )

+ 5x
5 = 14
4x
1- 2x
2
- 4x
4
+ 3x
5= 8
x
j
 0 ( j = 1,2,3,4,5 )
a) Giải bài toán trên
b) Viết bài toán đối ngẫu, chỉ các cặp ràng buộc đối ngẫu. Tìm tất cả phương án tối
ưu của bài toán đối ngẫu.
(ĐS: x = (2,0,3,0,0) f(x) = -1
y
1
=1 ; y
2
=t ; y


+ 4x
3 ≤ 6
4x
1+ x
2
+ 5x
3
≥ 2
x
1
 0; x
2
≤ 0

có phương án tối ưu là x= (24/13; 0; -14/13).
TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 3/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
Hãy viết bài toán đối ngẫu, chỉ các cặp ràng buộc đối ngẫu, tìm phương án tối ưu
của bài toán đối ngẫu và giá trò hàm mục tiêu ứng với PATƯ tìm được.
(ĐS Y = (11/13, 0, 7/13) dmax= 58/13 )

11) Cho bài toán qui hoạch tuyến tính sau :
f(x) = x

+ x
3
+ x
4
 1

4
x
j
 0 ( j = 1,2,3,4 )
(ĐS: x
1
=(0,1,0,11) f(x) = 12) x
2
= (11, 1, 0, 0 )
(Nên chuyển về bài toán đối ngẫu để giải )

12 ) Cho bài toán qui hoạch tuyến tính sau :
f(x) = x
1
+ 3x
2
+ 4x
3
 min
3x
1
- x
2
+ 2x

dành để đặt thiết bò có diện tích 166 m
2
. Có 2 loại thiết bò có thể chọn mua :
-Máy loại A: một máy giá 160 tr . đồng , trong 1 giờ hoạt động sản xuất được 110 sản
phẩm , để hoạt động và cung cấp sản phẩm được cần chiếm 1 diện tích là 12m
2

- Máy loại B: một máy giá 180 tr. đồng , trong 1 giờ hoạt động sản xuất được 100 sản
phẩm , để hoạt động và cung cấp sản phẩm được cần chiếm 1 diện tích là 9m
2

Tìm phương án mua thiết bò tối ưu sao cho trong 1 giờ tổng số sản phẩm được sản xuất ra
trong khu vực sản xuất mới là nhiều nhất.
( ĐS: 7máy loại A và 9 máy loại B)

14) Một nhà máy lọc dầu hiện có các loại dầu thô với khối lượng lần lượt là 30000 ,
25000và 42000 đơn vò . Kí hiệu các loại dầu thô lần lượt là A,B,C . Người ta có thể chế biến
thành 3 loại sản phẩm là khí đốt , xăng , dầu theo 3 phương thức chế biến sau đây:
Phương thức chế biến

Kết quả
Khí đốt Xăng Dầu
2A + 1B + 1C (I)
2A + 2B + 1C (II)
1A + 1B + 1C (III)
9
10
6
4
6

Sản phẩm A B C Mức huy động tối đa
Nguyên liệu ( kg )
Vốn ( 1000đ)
Lao động (giờ công)
Lợi nhuận (1000đ)
2
1
4
2
3
3
8
3
3
5
1
5
150
120
100

Xí nghiệp sẽ sản xuất bao nhiêu sản phẩm mỗi loại sao cho trong phạm vi số nguyên
liệu , vốn, giờ công huy động được , xí nghiệp đạt lợi nhuận cao nhất .(Biết rằng SP sản xuất
ra tiêu thụ được hết).
a) Hãy lập mô hình bài toán trên.
b) Giải bài toán tìm phương án sản xuất tối ưu ?
c) Tìm lời giải tối ưu của bài toán đối ngẫu ?
Đ.S : f
max
= 140 (ngàn đồng)

max
= 256.665 ngàn đồng )
19) Một xí nghiệp có thể sản xuất một loại sản phẩm từ hai phân xưởng khác nhau. Căn cứ
vào các nguồn lực hiện có trong 1 tuần phân xưởng 1 có thể sản xuất tối đa 70 sản phẩm ,
phân xưởng 2 sản xuất tối đa là 100 sản phẩm . Tổng số giờ công xí nghiệp có thể sử dụng
trong tuần ở cả hai phân xưởng là 600 giờ . Số giờ công cần thiết để sản xuất một đơn vò sản
phẩm ở phân xưởng 1 là 10 giờ , ở phân xưởng 2 là 5 giờ . Mức sản lượng tối thiểu trong
tuần của xí nghiệp là 80 sản phẩm . Chi phí sản xuất cho một đơn vò sản phẩm ở phân xưởng
1 là 20 ngàn đồng và ở phân xưởng 2 là 30 ngàn đồng .
a) Hãy lập mô hình bài toán QHTT , giải và tìm kế hoạch sản xuất trong tuần đảm bảo tổng
chi phí sản xuất thấp nhất.
b) Trong mô hình a) cho biết bài toán QHTT còn có ý nghóa nữa không ,nếu bỏ ràng buộc
về sản lượng tối thiểu ( 80 sản phẩm ).
c) Cho biết giá bán một đơn vò sản phẩm được ấn đònh là 50 ngàn đồng . Dựa theo năng lực
hiện có và yêu cầu sản lượng tối thiểu trong tuần , mỗi phân xưởng phải sản xuất bao
nhiêu sản phẩm để xí nghiệp đạt lợi nhuận cao nhất ?
d) Viết bài toán QHTT đối ngẫu của bài toán ở phần c. Tìm PATU của bài toán đối ngẫu.
* Đ.S : a) : f
min
= 2000 ngàn đồng ; c) : f
max
= 2300 ngàn đồng )
20) Để sản xuất một hỗn hợp nhiên liệu người ta sử dụng 3 loại thành phần , kí hiệu là
N1,N2,N3. Nhiệt lượng riêng của N1, N2, N3 tương ứng là 7.000, 4.000, 5.000 (Kcal/đvkl).
Đvkl : đơn vò khối lượng . Chi phí sử dụng 1 đvkl nhiên liệu N1, N2, N3 tương ứng là 2, 1, 2
đơn vò tiền tệ.Hãy chọn cơ cấu thành phần hỗn hợp sao cho tổng khối lượng nhiên liệu hỗn
hợp không vượt qúa 3.000 đvkl,tổng chi phí sử dụng không vượt qúa 4.000 đơn vò tiền tệ ,
loại nhiên liệu N3 được sử dụng không qúa 500 đvkl, loại nhiên liệu N1 phải được sử dụng ít
nhất 500 đvkl và đạt được nhiệt lượng tỏa ra tối đa khi sử dụng hết hỗn hợp nhiên liệu thành
phần .

không có 1 đơn vò hàng hóa nào vào đầu tháng 1và mong rằng cũng không còn 1 đơn vò
hàng hóa nào vào cuối tháng 4.
TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 6/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
Hãy lập mô hình xác đònh số đơn vò hàng sản xuất trong giờ và ngoài giờ mỗi tháng để
đáp ứng nhu cầu với chi phí thấp nhất .
23) Một nhà máy lọc dầu hiện có 2 loại xăng dầu cơ bản với các đặc trưng như sau :
Xăng dầu cơ bản

Chỉ số Octan p suất hơi nước Số lượng (thùng)
Loại 1
Loại 2
104
94
5
9
30.000
70.000
Giả sử rằng những loại xăng dầu này có thể pha trộn lại để sản xuất 2 loại sản
phẩm cuối cùng : xăng dùng cho máy bay và xăng dùng cho ô tô với các đặc trưng như sau
SP. Cuối cùng Chỉ số Octan
nhỏ nhất
p suất hơi
nước cao nhất
Mức bán cao
nhất (thùng)
Giá bán
(USD/thùng)
Xăng máy bay
Xăng ô tô

với các dữ liệu cho như sau :
Loại hình quảng cáo

Tivi

Báo

Đài

Chi phí 1 lần quảng cáo (triệu đồng) 2 1,5 0,8
Số lần quảng cáo tối đa trong tháng 65 50 60
Dự đoán số ngươi tiếp nhận quảng cáo
mỗi lần (ngàn người)
10 15 8
Chiến lược quảng cáo xác đònh phải có ít nhất 30 lần quảng cáo trên tivi trong một
tháng. Hãy lập mô hình bài toán để xác đònh kế hoạch quảng cáo tối ưu.
27) Một xí nghiệp sản xuất 3 loại sản phẩm A, B, C với các dữ liệu cho ở bảng sau :
Dữ liệu SP. A SP.B SP.C
Giá bán 1 sản phẩm (ngàn đồng)
Chí phí nguyên liệu cho 1 SP (ngàn đồng)

80
40
160
70
250
120
TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 7/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
Thời gian hoàn tất 1 SP (giờ)

B4
90
92
88
86
25.000
25.000
35.000
40.000
Ma trận chi phí vận chuyển như sau ( ngàn đ/SP )
.
Hãy lập mô hình bài toán xác đònh sản lượng các nhà
máy cần sản xuất và phân phối đến các thò trường trong năm sao cho tổng lợi nhuận thu
được nhiều nhất.
29) Có 3 người và 3 công việc. Chi phí để người i thực hiện công việc j được cho trong bảng
sau ( đơn vò :ngàn đ/người):

Công việc

Người
1 2 3
1 7 4 3
2

5 7 6
3

C =
TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 8/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
30

50 40 30
Do đặc điểm của hàng hoá, thời gian và phương tiện vận chuyển nên không thể chuyển
hàng xa trên 150 km. Theo yêu cầu trạm phát thứ hai phải phát hết hàng
Hãy lập mô hình bài toán tìm phương án vận chuyển thoả mãn các điều kiện nêu ra sao cho
tổng tấn* km là nhỏ nhất.
31) Một công ty thức ăn nhanh dự đònh mở thêm nhà hàng phục vụ. Công ty có hai loại nhà
hàng dòch vụ tuỳ chọn và dòch vụ chọn gói. Một nhà hàng dòch vụ tuỳ chọn có chi phí xây
dựng 1 tỷ đồng, cần 5 nhân viên và doanh thu hàng năm là 4 tỷ đồng. Một nhà hàng dòch vụ
trọn gói có chi phí xây dựng 1,5 tỷ đồng, cần 15 nhân viên và doanh thu là 5 tỷ đồng/ năm.
Công ty hiện có sẵn 24 tỷ đồng để mở thêm nhà hàng. Các hợp đồng lao động chỉ cho phép
công ty thuê thêm nhiều nhất 210 nhân viên, giới hạn đăng ký kinh doanh cho phép công ty
mở thêm nhiều nhất là 20 nhà hàng,
a) Lập mô hình bài toán để công ty có doanh thu lớn nhất.
b) Tìm phương án tối ưu của bài toán.
c) Nếu doanh thu hàng năm của mỗi nhà hàng dòch vụ tuỳ chọn là 2 tỷ đồng thì lời giải
tối ưu sẽ thay đổi như thế nào?
Đ.S : b) X = ( 12, 8 ) f
max
= 88. c) X = (6; 12) f
max
= 72.
32) Một doanh nghiệp có thể sản xuất ra một loại sản phẩm theo 2 quy trình công nghệ khác
nhau: CN

350 9 5
Sản lượng (đv/giờ) 30 35
Hãy lập mô hình bài toán tìm kế hoạch sản xuất sao cho số lượng sản phẩm đạt được
là lớn nhất.
33) Lập mô hình, không giải

Một nhà hàng
-
khách sạn có 4 phòng hội nghò A,
B, C, D ; Ở mỗi phòng có một số vò trí có thể lắp
đặt camera quan sát (xem sơ đồ). Camera lắp ở
vò trí 1 thì chỉ quan sát được phòng A, camera lắp
ở vò trí 2 thì quan sát được phòng A và phòng B,
tương tự cho các camera còn lại. Phòng D là
phòng VIP nên cần ít nhất 2 camera để quan sát,
các phòng còn lại chỉ cần ít nhất 1 camera để
quan sát. Mỗi camera có chi phí lắp đặt là
500USD, tổng số tiền lắp đặt các camera không
vượt quá 2500USD. Hãy xác đònh vò trí lắp đặt
các camera sao cho: tổng số camera lắp đặt là ít
nhất, nhưng vẫn bảo đảm điều kiện về an ninh
và điều kiện về tổng số tiền đầu tư.
TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 9/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
34) Công ty may Sài Gòn có 2 phân xưởng may kí hiệu là M
1
và M
2
cùng sản xuất hai loại
sản phẩm CAT1 và CAT2. Số đơn vò sản phẩm các loại được sản xuất ra và chi phí mỗi giờ


2) a = ( 30 ,40 ,53 ) ; b = ( 40 ,30 ,25 ,28 )
Ma trận chi phí :
ĐS : , fmin ( x) = 1855
3) a = ( 60 ,55 ,50 ) ; b = ( 65 ,45 ,50 ,30 )
Ma trận chi phí :
a) Tìm PAVCTU
b) Tìm PAVCTU sao cho trạm B
3
nhận đủ hàng .
ĐS :a) , fmin ( x) = 1385 b) , fmin (x ) = 1410
4) a = ( 100 ,125 ,155 ) ; b = ( 150 ,90 ,75 )
Ma trận chi phí :
a) Tìm PAVCTU.
b) Tìm PAVCTU và sao cho trạm A
3
phát hết hàng .
ĐS :a) f( x) = 1865 b) f (x ) = 2065
5) a = ( 60 ,30 ,80 ) ; b = ( 70 ,50 ,30 )
Ma trận chi phí :



3 7 4
4 8 10
7 19 9

C =
9 5 9

5 8 3

7 4 6 C =

TÀI TRỌNG NGUYỄN TỐI ƯU HĨA NGUYỄN THỊ NGỌC THANH
[email protected] Trang 10/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
Tìm PAVCTU và sao cho trạm A
1
phát hết hàng.
( ĐS : , fmin = 850)
6) Người ta cần gieo trồng 3 loại luá trên 4 cánh đồng với diện tích tương ứng là :100,150
,100 và 100 ha.Theo kế hoạch sản xuất sản lượng mỗi loại luá phải thu hoạch tương ứng là :
300, 600, 250 ( tấn ).Năng suất trung bình của từng loại luá cho mỗi loại đất bất kỳ là 2
tấn/ha đối với luá 1 ; 3 tấn/ha đối với luá 2 ; 2,5 tấn/ha đối với luá 3.
Tìm phương án gieo trồng sao cho chi phí sản xuất thấp nhất . Biết rằng chi phí cho 1 tấn luá
(từ lúc gieo trồng đến khi thu hoạch) là(ĐV: 100 ngàn đồng/tấn.):

40
60

A2
B1
B3
50
20
A3 B2
B3
30
20
Hãy lập kế hoạch vận chuyển tối ưu sao cho tổng số tấn * km xe không là ít nhất, biết rằng
ma trận khoảng cách giữa các đòa điểm cho như sau ( km): Đòa chỉ vào phần mền giải bài TUH:
Toiuuhoa.googlepages.com hoặc : toiuuhoa.ungdung.goolepages
HẾT
5

6

4

3,5 6,2 3,6
4,5