Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 1 -

Chương Mở đầu TỐI ƯU HÓA
I/ KHÁI NIỆM:
1.1 Đònh nghóa: Bài toán tối ưu hóa là bài toán tìm giá trò cực tiểu (hay cực đại) của một
hàm số phụ thuộc nhiều biến số tên tập hợp các biến số thỏa mãn những điều kiện nhất
đònh. Các mô hình và phương pháp tối ưu có nhiều ứng dụng rộng rãi và đa dạng trong
thực tiễn, đặc biệt trong kinh tế và kỹ thuật.
Trong các bài toán tối ưu thì quan trọng nhất và đáng chú ý trước nhất là các bài
toán tối ưu tuyến tính, hay còn gọi là bài toán qui hoạch tuyến tính, tức là bài toán tìm cực
tiểu (hay cực đại) của một hàm tuyến tính với các biến số thỏa mãn các phương trình
hoặc bất phương trình tính toán. Qui hoạch tuyến tính là bài toán tối ưu đơn giản nhất,
được ứng dụng rộng rãi nhất trong nhiều lónh vực khác nhau của kinh tế, đời sống và quốc
phòng. Đây cũng là lớp bài toán được nghiên cứu đây đủ và hoàn chỉnh nhất, cả về mặt
lý thuyết tổng quát và về mặt tính toán. Hơn nữa qui hoạch tuyến tính còn được sử dụng
trong nhiều bài toán tối ưu khác, với tư cách như một bài toán con (subroutine).
1.2 Bài toán tối ưu tổng quát:
Bài toán tối ưu tổng quát có dạng như sau: Tìm tập hợp các biến số x = (x
1
, x
2
, ,
x
n
) ∈ R
n
thỏa mãn
f(x) = f(x
1
, x

n
, (1.4)
trong đó f, các g
i
(i = 1, , m), h
j
(j = 1, , p) là những hàm số cho trước, X là tập hợp
cho trước nào đó. Chẳng hạn, X ≡
n
R
+
= { x ∈ R
n
: x ≥ 0} hoặc X = Z
n
(tập hợp các điểm
nguyên tong R
n
).
Bài toán (1.1) - (1.4) còn được gọi là bài toán qui hoạch toán học. Hàm f(x) được
gọi là hàm mục tiêu, các hàm g
i
(i = 1, , m) và h
j
(j = 1, , p) được gọi là các hàm ràng
buộc, mỗi ràng buộc (1.3) là ràng buộc đẳng thức. Tập hợp
D = {x ∈ X : g
i
(x) ≤ 0, i = 1, , m; h
j

g
i
(x), i = 1, , m; h
j
(x) = 0, j = 1, , p, đều là tuyến tính và X là một tập hợp lồi đa
diện. Một số trường hợp riêng quan trọng của bài toán qui hoạch tuyến tính là bài toán
vận tải, bài toán sản xuất đồng bộ
• Qui hoạch tham số nếu các hệ số trong biểu thức của hàm mục tiêu hay trong các hàm
ràng buộc phụ thuộc vào một hay nhiều tham số. Đơn giản nhất là bài toán qui hoạch
tuyến tính tham số với các hệ số ở hàm mục tiêu hay ở vế phải các ràng buộc phụ
thuộc nào một tham số.
• Qui hoạch động nếu đối tượng được xét là các quá trình có thể chia ra thành nhiều giai
đoạn hoặc các quá trình phát triển theo thời gian. Trong nhiều trường hợp bài toán qui
hoạch động lại có thể diễn đạt như một bài toán tónh và thường được đưa về dạng bài
toán qui hoạch tuyến tính với kích thước lớn.
• Qui hoạch phi tuyến nếu hàm mục tiêu f(x) là một trong các hàm ràng buộc g
i
(x), h
j
(x)
không phải là tuyến tính hay X không phải là một tập hợp lồi đa diện (Chẳng hạn khi
X là tập hợp các điểm rời rạc hay X là một tập hợp không lồi).
• Qui hoạch lồi nếu hàm mục tiêu cần tìm cực tiểu là lồi (hay hàm cần tìm cực tiểu là
lõm) và miền ràng buộc D là một tập lồi. Đây là lớp bài toán qui hoạch phi tuyến
được nghiên cứu nhiều nhất. Một trường hợp riêng quan trọng của qui hoạch lồi là qui
hoạch toán phương, trong đó xét bài toán tìm cực tiểu của một hàm lồi bậc hai với các
ràng buộc tuyến tính.
• Qui hoạch lõm nếu hàm mục tiêu cần tìm cực tiểu là lõm và miền ràng buộc D là một
tập lồi. Đây là lớp bài toán điển hình trong lớp các bài toán qui hoạch phi tuyến không
lồi đã được nghiên cứu khá kỹ. Đơn giản nhất là bài toán tìm cực tiểu của một hàm

2
, , x
n
) được
gọi là một véctơ n chiều. Các số x
i
(i = 1, , n) gọi là 2 thành phần của véctơ x. Ví dụ: x
= (1, -2, 0, 3) là véctơ 4 chiều. Xét hai véctơ x = (x
1
, x
2
, , x
n
), y = (y
1
, y
2
, , y
n
), và một
số thực α.
• Hai véctơ x, y được gọi là bằng nhau, ta viết x = y, nếu x
n
= y
n
, ∀i = 1, 2, , n.
• Phép toán cộng các véctơ x, y và nhân véctơ x với số α được đònh nghóa như sau:
x+y = (x
1
+ y

x
2
+ + α
k
x
k
(α
i
∈ R) gọi là một tổ hợp tuyến tính
của các véctơ x
1
, x
2
, , x
k
.
Hơn nữa, nếu α
i
≥ 0, ∀i = 1, 2, , k và α
1
+ α
2
+ + α
k
= 1 thì x gọi là một tổ hợp lồi
của các véctơ x
1
, x
2
, , x

Nếu hệ véctơ { x
1
, , x
n
} độc lập (hoặc phụ thuộc) tuyến tính, ta cũng nói các véctơ
x
1
, x
2
, , x
n
độc lập (hoặc phụ thuộc) tuyến tính.
Trong R
n
số véctơ độc lập tối đa là n. Mỗi hệ gồm n véctơ độc lập tuyến tính của R
n

gọi là một cơ sở của nó. Giả sử { a
1
, a
2
, , a
n
} là một cơ sở của R
n
thì bất kỳ véctơ x ∈
R
n
đều là tổ hợp tuyến tính của các véctơ a
1

0
||→ 0.
Hình cầu tâm a  R
n
bán kính r là tập hợp các điểm x ∈ R
n
cách a không quá r. Ta ký
hiệu nó là S ={x : ||x - a|| ≤ r}. Hình cầu này tạo nên một r lân cận của điểm a.
Một điểm x ∈ C ⊂ R
n
gọi là điểm trong của C nếu một r lân cận nào đó của x nằm
trọn trong C. Nếu trong lân cận bất kỳ của x đều có các điểm thuộc C và các điểm không
thuộc C thì X gọi là điểm biên của C. Tập hợp tất cả các điểm biên của C gọi là biên của
C.
Một tập hợp C ⊂ R
n
gọi là giới nội nếu nó chứa trong một hình cầu tâm O nào đó, tức
là tồn tại số r đủ lớn để cho ||x|| ≤ r, ∀x ∈ C.
0
lim
xx
k
k
=
∞→
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 4 -

>< xx,
Một tập hợp C ⊂ R

n
, ký hiệu < x, y >, là số thực
<x,y> = x
1
y
1
+ x
2
y
2
+ + x
n
y
n
.
<x,y> = 0 thì ta nói hai véctơ x, y là trực giao nhau.
Các tính chất của tích vô hướng:
(a) <x,y> = <y,x> giao hoán
(b) <x
1
+ x
2
,y> = <x
1
,y> + <x
2
,y> phân phối đối với phép cộng
(c) <λx,y> = <x,λy> = λ <x,y>
(d) <x,x> ≥ 0 dấu bằng xảy ra khi và chỉ khi x = 0. Dễ thấy rằng ||x|| =
2.3 Đường thẳng, đoạn thẳng và siêu phẳng:

) ∈ R
n
thoả mãn phương trình bậc nhất (tuyến tính)
c
1
x
1
+ c
2
x
2
+ + c
n
x
n
= α được gọi là một siêu phẳng trong R
n
, ký hiệu H(c, α ).
Siêu phẳng H(c, α) là giao của hai tập hợp {x

∈ R
n
: <a, x> ≤ α}và{x

∈ R
n
: <a, x> ≥ α},
ký hiệu lần lượt là H
-
(c, α), H

k
x
lim
∞→
k
k
x
lim
∞→
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 5 -

y
x
x
y
y
x
Đa diện lồi
Khúc lồi
không giới nội

Các tập hợp lồi Các tập hợp không lồi
Cho trước một tập hợp tuỳ ý C ⊂ R
n
, bao giờ cũng tồn tại một tập hợp lồi nhỏ nhất bao
hàm C ( giao của tất cả các tập hợp lồi bao hàm C), đó là tập hợp tất cả các tổ hợp lồi của

∑
=
p
i
i
i
u
1
λ
với λ
i
≥ 0, ∑λ
i
= 1, u
i
(i = 1, , p) là các đỉnh của C.
b) Với khúc lồi C không giới nội, mỗi x ∈ C có thể biểu diễn dưới dạng một tập hợp lồi
của các đỉnh của C cộng với một tổ hợp tuyến tính không âm của các phương cực biên
của C, nghóa là :
x ∈ C → x =
j
Jj
j
Ii
i
i
u
νμλ
∑∑
∈∈

,
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 6 -

trong đó c = (c
1
+ c
2
+ + c
n)
∈ R
n
cho trước tuỳ ý. Dó nhiên, với mọi x, y ∈ R
n
và mọi số
thực
λ ta có f(x+y) = f(x) + f(y), f(λx) = λf(x).
Một hàm tuyến tính afin là một hàm số có dạng
f(x) = <c,x> + α,
trong đó c = (c
1
+ c
2
+ + c
n)
∈ R
n
, α∈R cho trước tuỳ ý. Nếu f(x) là hàm tuyến tính afin
thì với mỗi x, y
∈ R

C. Điểm x
0
∈ C gọi là điểm cực tiểu đòa phương của f nếu tồn tại số ε > 0 sao cho f(x
0
) ≤
f(x), với mọi x ∈ C thỏa mãn ||x - x
0
|| < ε.
Các khái niệm điểm cực đại đòa phương và cực đại tuyệt đối (hay cực đại toàn cục)
được đònh nghóa tương tự. Đònh lý sau đây nói lên một tính chất rất đáng chú ý là: bất kỳ
điểm cực tiểu đòa phương nào của một hàm lồi trên một tập hợp lồi cũng là điểm cực tiểu
tuyệt đối.
Đònh lý 2.2: Cho f(x) là một hàm lồi xác đònh trên một tập hợp lồi C. Nếu x
0
∈ C là một
điểm cực tiểu đòa phương của f thì x
0
cũng là điểm cực tiểu toàn cục của f trên C.
Hệ quả: Bất cứ điểm cực đại đòa phương nào của một hàm lõm trên một tập hợp
lồi cũng là điểm cực đại tuyệt đối.


Lao động h/chiếc 1 2 40 h
Tiền lời đồng 4 5
Sản lượng Chiếc x
1
x
2

Vậy mỗi ngày nên sản xuất bao nhiêu đôn sứ và bao nhiêu bình bông để tiền lời
cao nhất.
Giải
a. Đặt tên biến:
Gọi x
1
là số lượng bình bông
Gọi x
2
là số lượng đôn sứ
b. Hàm mục tiêu: MaxZ = 4x
1
+ 5x
2

c. Các ràng buộc: 4x
1
+ 3x
2
≤ 120
1x
1
+ 2x

Hàm mục tiêu: Z = 80 = 4x
1
+ 5x
2→ (x
1
= 0 ; x
2
= 16) ; (x
1
= 20 ; x
2
= 0)
Z = 160 = 4x
1
+ 5x
2

→ (x
1
= 0 ; x
2
= 32) ; (x
1
= 40 ; x
2
= 0)
Z = 120 = 4x

= 120
(2) 1x
1
+ 2x
2
≤ 40 → 1x
1
+ 2x
2
+ s
2
= 40
x
1
,x
2
≥ 0
s
1
,s
2
: biến bổ sung (Slack Variable)
Thử dần tìm được x
1
= 5B ; x
2
= 10Đ
(1) 4.5 + 3.10

+ s


+ s
1
= 120
s
1
= 120 - 80 = 40 kg đất sét

→ (2) 1.20 + 2.0

+ s
2
= 40
s
2
= 40 - 20 = 20 h lao động
Lời giải ứng với 3 điểm A, B, C:
20
0
16
(2)
(1)
A
10
40
32
30
50
504020
30

1. Lời giải tối ưu thường rơi vào một trong những điểm góc A, B, C của vùng lời giải
chấp nhận được OABC.(Feasible solution)
2. Các đường thẳng của hàm mục tiêu Z đều song song nhau.
3. Cần chọn đường thẳng Z xa nhất đối với điểm O và song song các đường thẳng Z
khác.
4. MaxZ đi qua điểm B (điểm giao của 2 đường thẳng (1) và (2)).
HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH QSB
+

BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (LP) – PHƯƠNG PHÁP ĐƠN HÌNH
Chương trình này giải những bài toán quy hoạch tuyến tính. Độ lớn của bài toán
phụ thuộc vào bộ nhớ máy tính của bạn. Bạn có thể xác đònh bài toán bằng cách dùng
dạng thức như sau để vào số liệu:
Hàm mục tiêu Max 4X
1
+ 5X
2

Ràng buộc (1) 4X
1
+ 3X
2
< 120
(2) 1X
1
+ 2X
2
< 40
(biến số được giả thiết là số không âm)
Bạn có thể đònh dạng bài toán theo dạng chuẩn hay tự do khi đưa vào các công

2
= 0 0 0
Z = 100 MaxZ=136 120
0
5040
20
30
40
x
2
(Đ) Đôn sứ
30
10
10
B
8
24
20
giờ công
Đất sét
A
C
x
1
(B) Bình bông
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 10 -

Xuất hiện một số hướng dẫn về phần nhập liệu và các câu hỏi cần phải trả lời cho bài
toán:

Màn hình xuất hiện bảng nhập số liệu (hệ số được nhập gồm các hệ số trong hàm mục
tiêu và trong các ràng buộc)
Enter the Coefficients of the LP Model Page: 1
Max 4_______X1 5_______X2
Subject to
(1) 4_______X1 3_______X2 ≤ 120_____
(2) 1_______X1 2_______X2 ≤ 40______
Màn hình bảng xác nhận điều kiện biên và tính nguyên của các biến số
Integrality and Bounds Page: 1
Var. no. Name Integrality(C/I/B) Lower bound Upper bound
1 X1 < C > <+0 > <+1.0E+30>
2 X2 < C > <+0 > <+1.0E+30>
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 11 -

Trong QSB
+
có 3 loại biến số:
C (Continuos): biến thực
I (Integer): biến nguyên
B (Binary): biến nhò phân
Gõ ENTER để xác nhận là biến số có giới hạn dưới là 0, giới hạn trên là 1E+30 và có thể
là số nguyên hay không nguyên.
Nhấn nút Space Bar để tiếp tục. Màn hình xuất hiện lại Function Menu, chọn số 5 để giải
bài toán. Màn hình xuất hiện Option Menu For Solving

Option Menu for Solving vidu1
When solving a problem, you have the option to display steps of the
simplex method. This option is permissible only when your problem is small,
that is, when N+N1+N2+N3*2 ≤ 9, where N is the number of variables, N1 is
Option Menu to Show the Final Solution of vidu1
You have the following options available to show the final solution.
If you want to print the solution, make sure that the printer is ready.
Option

1 Display the final solution
2 Display the final solution and sensitivity analysis
3 Display/print the solution
4 Display/print the solution and sensitivity analysis
5 Print the final tableau
6 Save the final solution in an ASCII file
7 Print the combined analysis
8 Return to the function menu

Chọn số 1 để đọc kết quả của bài toán, xuất hiện lời giải
Summarized Results for vidu1 Page : 1
Variables Opportunity Variables Opportunity
No. Names
Solution
Cost No. Names
Solution
Cost
1 X1 +24.000000 0 3 S1 0 +.60000002
2 X2 +8.0000000 0 4 S2 0 +1.6000000
Maximized OBJ. function = 136 Iters. = 2
I.2/ Cực tiểu hóa hàm mục tiêu
Ví dụ 2: Một nông dân cần mua phân bón cho mùa trồng trọt tới. Có 2 loại phân
đóng gói 10 kg do hãng A và B sản xuất, với các thành phần đạm và lân trong bảng sau:

+ 4x
2
≥ 24
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 13 - I,J,K :Là số nguyên và gần gốc O.

Đáp số : x
1
= 0 gói phân hãng (A); x
2
= 6 gói phân hãng (B)
MinZ = 6.0 + 3.6 = 18 đ
Nhận xét: (1) 3x
1
+ 6x
2
= 16
(2) 7x

căn nhà mỗi kiểu? và loại máy nào giới hạn số lượng nhà xây dựng được?
Giải
a. Đặt tên biến: Gọi x
1
số căn nhà kiểu A
x
2
số căn nhà kiểu B
b. Hàm mục tiêu: MaxZ = x
1
+ x
2

c. Các ràng buộc: (1) 1.x
1
+ 1.2x
2
≤ 150.2 = 300 ca máy đào
(2) 6.5x
1
+ 6x
2
≤ 150.15 = 2250 ca cần trục
x
1
,x
2
≥ 0, x
1
,x


1.33
2.67
5.33
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 14 -

Đáp số: x
1
= 300 nhà A
x
2
= 0 nhà B
s
1
= 0 (Không dư ca máy đào)
s
2
= 300 (Dư 300 ca cần trục)
2/. Nếu công ty xây lắp muốn tận dụng hết khả năng của xe máy thi công đã đưa
đến hiện trường thì công ty xây lắp có thể xây dựng được bao nhiêu căn nhà mỗi kiễu A
& B? (nếu máy nào thiếu thì có thể làm 2 ca/ngày).
Giải
a. Đặt tên biến: Gọi x
3
số ca máy đào dư thừa
x
4
số ca cần trục dư thừa
b. Hàm mục tiêu: MinZ = x

2
+1x
4
- s
2
= 2250
Đáp số: x
1
= 346 x
4
= 0
x
2
= 0 s
1
= 46 (Thiếu 46 ca máy đào)
x
3
= 0 s
2
= 0
Máy đào phải làm 2 ca/ngày trong 23 ngày và tăng được 346 - 300 = 46 căn.
3/. Nếu giá thành xây dựng kiểu nhà A là 45 triệu đồng, kiểu nhà B là 40 triệu
đồng. Nên xây dựng bao nhiêu nhà mỗi kiểu để giá thành thi công thấp nhất đồng thời
tận dụng hết được năng lực thi công cơ giới của công ty.
Giải
a. Đặt tên biến: Gọi x
1
số căn nhà kiểu A
x

1
= 300
(2) 6.5x
1
+ 6x
2
- s
2
= 2250
Đáp số: x
1
= 0 nhà A
x
2
= 375 nhà B
s
1
= 150 (Thiếu 150 ca máy đào, cần bổ sung 1 máy đào.
s
2
= 0 (Tận dụng hết số ca cần trục)
MinZ = 45x
1
+ 40x
2
= 15.000 triệu = 15 tỷ
Ví dụ 4: Một xưởng mộc đònh nhận hợp đồng đóng 30 chiếc bàn và tủ trong thời
hạn nhất đònh một tuần.

Bài giảng môn học: Chuyên Đề Thi Công


c. Các ràng buộc: 3.x
1
+ 4x
2
≥ 100 (1)
5x
1
+ 3x
2
≤ 120 (2)
x
1
+ x
2
= 30 (3)
x
1
≤ 12 (4)
→ 3.x
1
+ 4x
2
- s
1
= 100 (1)
5x
1
+ 3x
2

s
2
= 6 công → dư 6 công lao động
s
3
= 0
MaxZ = 400x
1
+ 200x
2
= 8.400 đ
I.3/ Bài Toán Đối Ngẫu: (The dual)
Ví dụ 5:
Một xưởng mộc sản xuất bàn và tủ. Lượng sản phẩm sản xuất ra được phụ thuộc
vào số công lao động, gỗ và diện tích mặt bằng. Nhu cầu sử dụng tài nguyên để sản xuất
ra tủ và bàn cũng như lượng tài nguyên tối đa cung cấp hàng ngày được trình bày trong
bảng sau:
Nhu cầu của
Tài nguyên
Bàn Tủ
Lượng tài nguyên
cung cấp hàng ngày
Lao động (công) 2 4 40
Gỗ (dm
3
) 18 18 216
Mặt bằng (m
2
) 2,4 1,2 24
Bài giảng môn học: Chuyên Đề Thi Công

+ 4x
2
≤ 40 (1)
18x
1
+ 18x
2
≤ 216 (2)
2.4x
1
+ 1.2x
2
≤ 24 (3)
2x
1
+ 4x
2
+ s
1
= 40 (1)
18x
1
+ 18x
2
+ s
2
= 216 (2)
2.4x
1
+ 1.2x

Gọi y
3
là giá cho thuê một m
2
mặt bằng
2/ Hàm mục tiêu: MinZ = 40y
1
+ 216 y
2
+ 24y
3
3/ Ràng buộc: 2y
1
+ 18y
2
+ 2,4y
3
≥ 160
4y
1
+ 18y
2
+ 1,2y
3
≥ 200
Đáp số: y
1
= 20 đ/công lao động

y

lý khi cần phải đưa ra quyết đònh, nhiều khi không phải tiền lời hay doanh thu làm nhà
quản lý bận tâm mà chính các tài nguyên hàng ngày mới là mối bận tâm của các nhà
Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 17 -

quản lý (công nhân đau bệnh xin nghỉ việc, vật liệu xấu hao hụt, thiết bò giảm). Trò
giá các tài nguyên y
i
cũng là các thông tin quan trọng để nhà quản lý quyết đònh nên
hay không nên đảm bảo sản xuất, để tồn trữ nhiều tài nguyên hơn và phải chi thêm
bao nhiêu tiền cho các tài nguyên dự trữ này. Nếu như nhà quản lý thấy cần phải đảm
bảo sản xuất (Z, x
1
, x
2
) bằng dự trữ tài nguyên thì nảy sinh vấn đề: Việc này ảnh
hưởng thế nào đến lời giải ban đầu?. Vùng lời giải chấp nhận được đã xác đònh được
bởi các trò vế phải nay có thể thay đổi. Hậu quả của các thay đổi này đến lời giải thế
nào thì sẽ nói trong phần phân tích cảm biến.
I.4/ Phân Tích Cảm Biến: (Sensitivity Analysis)
Xét ví dụ 5:
( c
1
) (c
2
)
MaxZ = 160 x
1
+ 200 x
2

2
≤ 12 (2) điều kiện giới hạn về gỗ
2.x
1
+ x
2
≤ 20 (3) điều kiện giới hạn về mặt bằng
AB: Điều kiện về công lao động (1)
BC: Điều kiện về vật liệu gỗ (2) x
1
= 0; x
2
= 12
CD: Điều kiện về công lao động (3) x
2
= 0; x
1
= 12
Điểm A: x
1
= 0; x
2
= 10
Điểm D: x
1
= 10; x
2
= 0
11.2
A
320x
1
+ 200x
2
= 2800
160x
1
+ 200x
2
= 2240
D
12
6
4
20
x
1
+ 2x
2
= 20 (1)
x
1
+ x
2
= 12 (2)
2x
1
+ x

1
, c
2
; b
1
, b
2
, b
3

1/. Xét khi c
1
, c
2
thay đổi (Giá bán thay đổi)
Điểm B Điểm C
x
1
= 4 bàn x
1
= 8 bàn
x
2
= 8 tủ x
2
= 4 tủ
Z = 2240 đ Z = 2800 đ
s
1
= 0 công s

2
= 8.33đ/dm
3

y
3
= 0 đ/m
2
y
3
= 41.66 đ/m
2

2/. Điều kiện để kế hoạch sản xuất không thay đổi:
c
min
< c
j
< c
max

160 ≤ c
1
≤ 320
100 ≤ c
2
≤ 200
Xét khi b
1
, b


Điểm B(b
1
= 40) Điểm B’(b
1
=44) Điểm B”(b
1
=48)
x
1
= 4 bàn x
1
= 2 bàn x
1
= 0 bàn
x
2
= 8 tủ x
2
= 10 tủ x
2

2
= 20 (3)
2x
1
+ 4x
2
= 40 (1)
2x
1
+ 4x
2
= 48
x
1
+ x
2
= 12 (2)
320x
1
+ 200x
2
= 2800
8
B
C
2x
1
+ 4x
2
= 44

< b
i
< b
max

32 ≤ b
1
≤ 48
180 ≤ b
2
≤ 240  Chưa ảnh hưởng đến đường CD
HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH QSB
+

BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (LP) – PHÂN TÍCH CẢM BIẾN
Enter the Coefficients of the LP Model Page: 1
Max 160_______X1 200_______X2
Subject to
(1) 2 _______ X1 4 _______ X2
≤ 40 ____
(2) 18 _______ X1 18 _______ X2
≤ 216 ____
(3) 2.4 _______ X1 1.2 _______ X2
≤ 24 ____
Sử dụng bài toán LP của QSB
+
giải bài toán.
Sau khi đã giải bài toán, nhấn nút bất kỳ để tiếp tục. Xuất hiện Option Menu to Show the
Final Solution. Chọn số 2 để trình bày kết quả và phân tích cảm biến.
Option Menu to Show the Final Solution of vidu1

Variable Min. C(j) Original Max. C(j) Variable Min. C(j) Original Max. C(j)
X1 +100.000 +160.000 +200.000 X2 +160.000 +200.000 +320.000
Kết quả này trình bày phạm vi thay đổi các hệ số của hàm mục tiêu mà không làm ảnh
hưởng đến kết quả bài toán.
100
≤ c
1
≤ 200 và 160 ≤ c
2
≤ 320
Sensitivity Analysis for RHS Page : 1
Constrnt Min. B(i) Original Max. B(i) Constrnt Min. B(i) Original Max. B(i)
1 +32.0000 +40.0000 +48.0000 3 +19.2000 +24.0000 +Infinity
2 +180.000 +216.000 +240.000
Kết quả tình bày phạm vi thay đổi các giá trò b
i
của ràng buộc
32
≤ b
1
≤ 48 và 180 ≤ b
2
≤ 240 và 19.2 ≤ b
3
≤ ∞
II/ QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN (ILP Integer Linear Programming)
II.1/ Mô hình thuần nguyên:
Ví dụ 6: Để phát triển sản xuất chủ xưởng gia công cơ khí dự đònh mua thêm một
số máy gồm: máy dập và máy tiện. Số lượng các máy phụ thuộc vào Mặt bằng, Kinh phí
có sẵn của xưởng.

+ 4.000 x
2
≤ 40.000
Đáp số: 1/. Kết quả giải bằng LP cho ta:
x
1
= 2.22 máy dập
x
2
= 5.55 máy tiện
MaxZ = 1054.5 đ
→ x
1
= 2; x
2
= 6 → 1.5 x 2

+ 3 x 6

= 21 > 20 Không thỏa

→ x
1
= 3; x
2
= 5 → 8000 x 3

+ 4000 x 5

= 44.000 > 40.000 Không thỏa
Note: Use option F to specify if you do not have an IBM graphics printer or color/graphics
adapter. This will make screen/outputs less confusing.
Programs 1 to 4 are in QSB+(I), Programs 5 to E are in QSB+(II).
Press the up or down key to locate the desired option. Then press ENTER.
Welcome to your Integer Linear Programming (ILP) Decision Support System!
The options available for ILP are as follows.
If you are a first-time user, you might benefit from option 1.
Option Function
1 Overview of ILP Decision Support System
2 Enter new problem
3 Read existing problem from disk(ette)
4 Show input data
5 Solve problem
6 Save problem on disk(ette)
7 Modify problem
8 Show final solution
9 Return to the program menu
0 Exit from QSB+
Press the up or down key to locate the desired option. Then press ENTER.
Welcome to QSB+ (Quantitative Systems for Business Plus)!
You may choose from following management science decision support systems:
Code Code Press any key to return to the function menu.
LP Model Entry for vidu6
Please observe the following conventions when entering a problem:
(1) You may choose a free or fixed format to enter your data. Bound
constraints can be entered separately.
(2) For the fixed format entry, you may correct errors by pressing the
BACKSPACE key to move the cursor to the correct position and follow the
instruction at the bottom of screen to proceed to the previous/next page.
Scientific numeric notation is allowed for the fixed format such that
100, 100.0, +100, and 1.0E+2 are the same. >=, >, =>, and ≥ are the same;
and <=, <, =<, and≤ are the same for constraint directions.
(3) For the free format entry, refer to the help information for direction.
(4) You can modify the entered problem using option 7 of the function menu.
Maximize (1) or minimize (2) the objective? (Enter 1 or 2) < 1 >
Number of variables (excluding slacks/artificials): < 2 >
Number of constraints (excluding bounds): < 4 >
Approximate percentage of non-zeros (default 5%): < >
Use the default variable names (X1, ,Xn) (1(Yes), 0(No)): < 1 >
Use the free format to enter data (1(Yes), 0(No)): < 1 >
Use the fixed format to enter bounds/integrality (1(Yes), 0(No)): < 1 >
Press the SPACE BAR to continue if your entries are correct. Overview of ILP Decision Support System
ILP solves integer linear programming problems. The size of the problems
solved by this program depends on the memory in your computer. You may set

6 Return to the function menu
Press the up or down key to locate the desired option. Then press ENTER.
Option Menu to Show the Final Solution of vidu6
You have the following options available to show the final solution.
If you want to print the solution, make sure that the printer is ready.
Option
1 Display the final solution
2 Print the final solution
3 Save the final solution in an ASCII file
4 Return to the function menu
Press the up or down key to locate the desired option. Then press ENTER.
Summarized Results for vidu6 Page : 1
Variables Obj. Fnctn. Variables Obj. Fnctn.
No. Names
Solution
Coefficient No. Names
Solution
Coefficient
1 X1 +1.0000000 +100.00000 2 X2 +6.0000000 +150.00000
Maximized objective function = 1000 No. of iterations = 9
Nhận xét: Trong mô hình có các ràng buộc ≤ và các hệ số ràng buộc đều dương thì phải
làm tròn các trò kết quả về phía nhỏ hơn mới có lời giải chấp nhận được.
Khi làm tròn các trò kết quả lại nảy sinh vấn đề là còn một lời giải số nguyên nào
cho ta tiền lời lớn hơn.
II.2/ Mô hình số nguyên hỗn hợp:
Ví dụ 7:
Ông Ba có 250.000đ đònh đầu tư vào 3 dự án sau:
• Mua xe ôtô chở khách, mỗi xe giá 50.000đ, cuối năm cho tiền lời 5.000đ.
• Mua đất vườn, mỗi ha đất giá 12.000đ, cuối năm cho tiền lời 1.500đ.
• Mua tín phiếu kho bạc, mỗi phiếu giá 8.000đ, cuối năm lãnh tiền lời 1.000đ.

x
1
≤ 4
x
2
≤ 30
x
3
≤ 20
(Chú ý: x
2
∈ C; x
1
, x
3
∈ I; x
1
, x
2
,

x
3
≥ 0

)
1/. Kết quả giải bằng ILP cho ta:
x
1
= 0 xe

Vậy Trường hợp mô hình số nguyên hỗn hợp nên kiểm tra bằng cả LP và ILP.

HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH QSB
+

Enter the Coefficients of the LP Model Page: 1
Max 5000____X1 1500____X2 1000____X3
Subject to
(1) 50000___X1 12000___X2 8000____X3 ≤ 250000__
(2) 1_______X1 ________X2 ________X3 ≤ 4_______
(3) ________X1 1_______X2 ________X3 ≤ 130_____
(4) ________X1 ________X2 1_______X3 ≤ 20______
Màn hình xuất hiện bảng xác nhận điều kiện biên và tính nguyên của các biến số:
Integrality and Bounds Page: 1
Var. no. Name Integrality (C/I/B) Lower bound Upper bound
1 X1 <I> <+0 > <+1.0E+30>
2 X2 <I> <+0 > <+1.0E+30>
3 X3 <I> <+0 > <+1.0E+30>
Biến X1, X3 là nguyên (khai báo I); biến X2 là không nguyên (khai báo C)
Lời giải cho bài toán áp dụng mô hình quy hoạch tuyến tính số nguyên là: Bài giảng môn học: Chuyên Đề Thi Công
Biên soạn: Th.S Nguyễn Việt Tuấn Trang - 25 -

Summarized Results for vidu5 Page : 1
Variables Obj. Fnctn. Variables Obj. Fnctn.
No. Names
Solution
Coefficient No. Names

bằng cần thiết
(ha)
Hồ bơi 300 3.5 0.6
Sân quần vợt 150 1 0.1
Sân điền kinh 400 2.5 1.2
Nhà thi đấu 250 4 0.4
Tổng mặt bằng dành cho các công trình không được vượt quá 2 ha.
Tổng kinh phí xây dựng chỉ có 10 tỷ. Chỉ có một khu đất có đòa thế thích hợp có
thể dùng để xây dựng hoặc hồ bơi hoặc sân quần vợt. Chính quyền nên xây dựng những
công trình nào để dân trong thành phố có thể sử dụng được nhiều nhất.
Giải
a. Đặt tên biến:
Gọi x
1
là dự án hồ bơi
x
2
là dự án sân quần vợt
x
3
là dự án sân điền kinh
x
4
là dự án nhà thi đấu
b. Hàm mục tiêu: MaxZ = 300x
1
+ 150x
2
+ 400x
3

x
1
, x
2
, x
3
, x
4
∈ B (0, 1) (Binary number)