TRƯỜNG…………………
Khoa………………….

[\[\
Giáo trình tối ưu hoá
ứng dụng
1Lời nói đầu

Các bài toán tối u nhằm nghiên cứu giải bài toán cực trị của một hàm dới những
ràng buộc nào đó. Các phơng pháp tối u là một công cụ hữu hiệu giúp chúng ta có những
giải pháp tốt nhất để giải quyết một vấn đề. Ngày nay, với sự phát triển của kỹ thuật tin học,
phạm vi ứng dụng của tối u hóa ngày càng mở rộng.


2
Mục lục
Lời nói đầu
Mục lục
Chơng 1: Cơ sở của đại số tuyến tính
1.1. Ma trận và các phép tính ma trận
1.2. Định thức và các tính chất của chúng
1.3. Ma trận nghịch đảo và hạng của ma trận
1.4. Hệ phơng trình tuyến tính
Chơng 2: Khái niệm về các bài toán tối u hóa
2.1. Bài toán tối u hóa tổng quát
2.2. Các bài toán tối u
Chơng 3: Bài toán tối u tuyến tính
3.1. Một số ví dụ về bài toán tối u
3.2. Phát biểu bài toán
3.3. Tính đối ngẫu và định lý cơ bản của tối u tuyến tính
3.4. Các phơng pháp giải bài toán tối u tuyến tính
3.5. Thuật toán đơn hình giải bài toán tối u tổng quát
Chơng 4: Bài toán tối u nguyên tuyến tính
4.1. Bài toán tối u nguyên tuyến tính

2
3
3
4
5
7
9
9
9
11
11
11
12
13
18
21
21
21
25
25
26
33
39
41
41
41
42
45
49
49

2na
m1
a
m2
a
mn Phần tử của ma trận ký hiệu a
ij
, chỉ số thứ nhất ký hiệu chỉ số hàng, chỉ số thứ hai chỉ
số cột của ma trận chứa phần tử a
ij
.
Số hàng (m) và số cột (n) của ma trận xác định kích thứơc của ma trận, ta nói ma trận
có kích thớc m.n.
Ma trận gồm các phần tử a
ij
thờng đợc ký hiệu bằng chữ in hoa: A.
Ma trận có nhiều ký hiệu khác nhau. Ma trận A có thể đợc viết dới dạng:
A=









mn2n1n
m22212
m12111
a a a

a a a
a a a
(1.2)
1.1.2. Các dạng ma trận:
Ma trận chỉ có một cột đợc gọi là vectơ cột, còn ma trận chỉ có một hàng gọi là
vectơ hàng. Ma trận vuông có dạng:













n
2
1
0 0

0 0 0 1

Hai ma trận bằng nhau chỉ trong trờng hợp chúng có cùng kích thớc và các phần
tử tơng ứng bằng nhau.
Nếu ma trận A có định thức

khác không thì đợc gọi là ma trận không kỳ dị (không
suy biến). Trong trờng hợp ngợc lại ma trận A đợc gọi là ma trận kỳ dị hoặc là ma trận
suy biến.
1.1.3. Phép tính đối với ma trận
Muốn nhân ma trận với một hằng số (vô hớng) ta nhân mỗi phần tử của ma trận với
số đó.
A =










mnm21
2n2221
1n1211
a a a

a a a
a a a







mnm2m1
2n2221
1n1211
b b b

b b b
b b b
=










+++
+++
+++
a a a

a a a

(1.5)
ở đây a
i1
, a
i2
, a
in
là các phần tử hàng thứ i của ma trận A; còn b
1j
, b
2j
, b
nj
là các phần tử
cột thứ j của ma trận B.
1/ Tích ma trận không có tính chất giao hoán, tức là nói chung:
AB BA;
2/ (AB)C = A(BC) (luật kết hợp);
3/ (A+B)C = AC + BC;
C (A+B) = CA + CB (luật phân bố);
4/ (AB) = (A)B = A(B);
5/ AE = EA = A;
Phép chuyển vị ma trận có tính chất sau:
1/ (A + B)
T
= A
T
+ B
T


j
với i < j.
Số các nghịch thế trong hoán vị I = (
1
,
2
, ,
n
) bằng: k
1
+ k
2
+ + k
n-1

ở đây k
s
là số trờng hợp
s
lớn hơn
s+1
,
s+2
,
n
(s = 1, 2, , n-1) trong hoán vị I.
Hoán vị đợc gọi là hoán vị chẵn nếu số nghịch thể trong hoán vị I là số chẵn, và
đợc gọi là hóan vị lẻ nếu số các nghịch thể là số lẻ. Ví dụ đối với hoán vị 5, 2, 3, 4,1 thì
số tất cả các nghịch thế bằng:
k

n
n
a
aaa
aaa
aaa
1
21
22221
11211
|

=
(1.7)
Các phần tử, các hàng, các cột và cấp của ma trận A tơng ứng với các phần tử, các
hàng, các cột và cấp của định thức |A|.
Ví dụ: ta tính định thức cấp 3 theo quy tắc vừa nêu ra:

3
=
333231
232221
131211
aaa
aaa
aaa
= a

11
a
23
a
32

Ba số hạng đầu lấy dấu cộng, còn ba số hạng sau lấy dấu trừ, bởi vì hoán vị 1,2,3;
2,3,1 và 3,1,2 là chẵn (số nghịch thể tơng ứng là 0, 2 và 2) còn các hóan vị 3,2,1 ; 2,1,3 và
1,3,2 là hóan vị lẻ (số nghịch thể tơng ứng là 3,1 và 1).
Ví dụ:

3
=
3 2- 1
1- 0 3
1 4 2
= 2.0.3 + 4(-1) .1 +1.3(-2) -[1.0.1+4.3.3+2(-1).(-2)] = -50.
1.2.2. Định thức con và phần phụ đại số:
Định thức cấp (n-1) có từ định thức cấp n (
n
) bằng cách bỏ hàng i cột j đợc gọi là
định thức con ứng với phần tử a
ij
của định thức
n
và đợc ký hiệu là M
ij
.
Ta coi định thức cấp n:


a a a a a
a a a a a
+
+
+
+
+

Ví dụ: định thức con của phần tử a
22
của định thức:

3
=
3 2- 1
1- 0 3
1 4 2
sẽ là: M
22
=
2 1
1 2
= 2.3 -1.1 = 6-1 = 5
Định thức con của phần tử a
ij
nhân với (-1) với số mũ bằng tổng các chỉ số của phần
tử đó (i + j) đợc gọi là phần phụ đại số của phần tử a
ij
và đợc ký hiệu là A
ij

-1
=
||
*
A
A
(1.18)
Đôi khi ma trận A
*
đợc gọi là ma trận phụ hợp của ma trận A.
Phần tử hàng i cột j của ma trận A
*
là phần phụ đại số của phần tử a
ij
của ma trận A.
Từ đó:
A
-1
=


















1 3
1 2 1
2 3 2

Trớc khi đi tính ma trận nghịch đảo, cần xác định ma trận A cho ở đây không phải
là ma trận suy biến, tức là định thức của nó khác không.
Định thức của ma trận đó sẽ bằng:
| A | = 2.2.1 +3.1.3 +2.1.1 - 2.2.3 -3.1.1 - 2.1.1= -2
Sau đó ta tính các phần phụ đại số của các phần tử của ma trận
A
11
= ( -1)
1+1

1 1
1 2
= 2.1-1.1 =1
A
12
= ( -1)
1+2

1 3
1 1

=










1/2- 0 1/2
7/2 2 1 -
5/2 1- 1/2-

áp dụng quy tắc nhân ma trận, đem nhân ma trận A với ma trận A
-1
vừa tìm đợc ta
dễ dàng thấy đợc kết quả là một ma trận đơn vị. Và có thể dùng cách này để kiểm tra việc
tính ma trận nghịch đảo có đúng không.
Ma trận nghịch đảo của ma trận đơn vị cũng là ma trận đơn vị. Điều này suy ra từ
việc nhân ma trận bất kỳ với ma trận đơn vị đợc đúng ma trận đó. Dùng các quy tắc đã nêu
ở trên ta nhân hai ma trận đơn vị với nhau.
EE =









0 0 0
0 1 0
0 0 1

Từ đó suy ra rằng E
-1
= E
Cũng có thể chứng minh điều đó bằng cách tính trực tiếp ma trận nghịch đảo theo
công thức (1.18).
1.4. Hệ phơng trình tuyến tính
1.4.1. Dạng của hệ phơng trình tuyến tính:
Dạng tổng quát của hệ phơng trình tuyến tính đợc viết nh sau:
a
11
x
1
+ a
12
x
2
+ a
1n
x
n
= b
1
a
21

AX = B (1.20a)
ở đây A là ma trận đợc thành lập từ các hệ số của các biến: A = (a
ij
) với i = 1,2, , m; j = 1,
2, , n.
X - là véctơ cột của các biến
X =










n
x
x
x
.
2
1
(1.21)
B - là véctơ cột các số hạng tự do
B =




Nếu hệ phơng trình là xác định thì ta đi tìm nghiệm duy nhất của nó.
1.4.2. Giải hệ phơng trình tuyến tính:
Khi giải hệ phơng trình tuyến tính có thể xảy ra hai trờng hợp: n =m và n m.
Trớc hết là ta xét trờng hợp n = m. Lúc đó ma trận A sẽ có dạng:
A =










nnn2n1
2n2221
1n1211
a a a

a a a
a a a

Giả thiết ma trận A không suy biến, tức là | A| 0, khi đó sẽ tồn tại ma trận nghịch
đảo A
-1
.
Ta nhân vế trái và vế phải của đẳng thức (1.20a) với A
-1
về bên trái. Ta sẽ đợc:

x
.
2
1
=
||
1
A










+++
+++
+++
nnnnn
nn
nn
bAbAbA
bAbAbA
bAbAbA

. . .


1
A
(A
1i
b
1
+ A
2i
b
2
+ A
ni
b
n
) (1.23a)

x
n
=
||
1
A
(A
1n
b
1
+ A
2n
b
2


m
b
b
mnm2m1
11n1211
a a a

a a a
(1.26)
Từ đó, ta có định lý Crônecke - Capeli: Để hệ phơng trình tuyến tính là tơng thích,
điều kiện cần và đủ là hạng của ma trận cơ sở và ma trận mở rộng bằng nhau. Nếu hạng
của chúng bằng nhau và số ẩn bằng hạng của ma trận cơ sở thì hệ có nghiệm duy nhất. Nếu
hạng của ma trận A nhỏ hơn số ẩn thì hệ có vô số nghiệm.
Hệ phơng trình tuyến tính thuần nhất luôn luôn tơng thích, bởi vì luôn luôn có
nghiệm không, đợc gọi là nghiệm tầm thờng.
Nếu hạng của ma trận bằng số ẩn thì hệ thuần nhất chỉ có duy nhất một nghiệm là
không. Muốn hệ tồn tại nghiệm khác không thì hạng của ma trận cơ sở phải nhỏ hơn số ẩn.

9
Chơng 2: Khái niệm về các bài toán tối u hoá

2.1. Bài toán tối u hoá tổng quát
2.1.1. Phát biểu:
Tìm trạng thái tối u của một hệ thống sao cho đạt đợc mục tiêu mong muốn về chất
lợng theo một nghĩa nào đó.
2.1.2. Các yếu tố của một bài toán tối u hoá:
Một bài toán tối u hoá có ba yếu tố cơ bản sau:
* Trạng thái: mô tả trạng thái của hệ thống cần tối u hoá.
* Mục tiêu: đặc trng cho tiêu chuẩn hoặc hiệu quả mong muốn (chi phí ít nhất, hiệu

, b
2
, , b
m
]
T
.
Bài toán:

Tìm trạng thái tối u x
*
= [x
*
1
, x
*
2
, , x
*
n
]
T
của trạng thái (2.1) với các ràng buộc
(2.3) sao cho hàm mục tiêu (2.2) đạt giá trị nhỏ nhất (Min) hoặc giá trị lớn nhất (Max).
2.2.2. Bài toán quy hoạch phi tuyến:
Hệ thống ở trạng thái tĩnh. Tìm trạng thái tối u x
*
khi hàm mục tiêu đợc diễn đạt
bởi một hàm phi tuyến f(x) hoặc có ít nhất một ràng buộc phi tuyến:
g

2

1
.
==
Ràng buộc có thể là các hàm phi tuyến, các phơng trình đại số hoặc các phơng
trình vi phân.
2.2.4. Bài toán điều khiển tối u:
* Đối với hệ liên tục:
Hệ thống ở trạng thái động, trạng thái đợc mô tả bởi hệ phơng trình vi phân:

x
&
= f(t,x,u); t - thời gian
trong đó
x
&
= [
n21
x
,
x
,
x
&&&
]
T
;
x
&

); x(0) = x
0
, x(N,T
0
) = x
N
X
Mục tiêu có dạng:
J(u) =
)u,x(f
kk
1
N
0k
0


=
min; u
k

Bài toán đặt ra:
Cần phải tìm điều khiển tối u u
*
và trạng thái tối u x
*
để hệ thống chuyển từ trạng
thái đầu đến trạng thái cuối sao cho mục tiêu J(u) đạt Min hoặc Max.
Các bài toán tối u có trạng thái tĩnh đợc gọi là bài toán tối u hoá tĩnh, các bài toán
có trạng thái phụ thuộc thời gian đợc gọi là bài toán tối u hoá động. Trạng thái của hệ


11
Chơng 3: bài toán tối u tuyến tính

3.1. Một số ví dụ về bài toán tối u tuyến tính
3.1.1. Bài toán vận tải:
Có m điểm sản xuất cùng 1 loại sản phẩm a và n điểm tiêu thụ b. Cho rằng trong 1
đơn vị thời gian lợng cung và cầu bằng nhau:

==
=
n
1j
j
m
1i
i
ba
Gọi x
ij
0 và c
ij
lần lợt là lợng sản phẩm và chi phí vận chuyển từ điểm i đến j
Tìm phơng án chuyên chở

ij
, (i = 1 ữm; j = 1 ữ n) sao cho hoàn thành khối lợng trong quỹ thời gian cho
phép với chi phí ít nhất, nghĩa là:
Hàm mục tiêu Z =

==
n
1j
m
1i
c
ij
x
ij
min
Các điều kiện ràng buộc:


==
ữ==
n
1j
m
1j
ijjij iij
.0x ; b ; m 1 i ; ax


3.1.3. Bài toán thực đơn:
Loại thức ăn

a
32

N
4
b
4
a
41
a
42

Giá tiền đơn vị thức ăn

c
1
c
2

Tiền thức ăn hàng ngày: Z = c
1
x
1
+ c
2
x
2
.
Tìm lợng x
1

3.2. Phát biểu bài toán
3.2.1. Định nghĩa:
Bài toán tối u tuyến tính chuyên nghiên cứu phơng pháp tìm giá trị nhỏ nhất (Min)
hoặc giá trị lớn nhất (Max) của một hàm tuyến tính theo một số biến, thoả mãn một số hữu
hạn ràng buộc đợc biểu diễn bằng hệ phơng trình và bất phơng trình tuyến tính.
3.2.2. Hai dạng cơ bản của bài toán tối u tuyến tính:
1. Dạng chính tắc: ràng buộc ở dạng đẳng thức.
12
Đặt A =








mnm
n
aa
aa
1
111

A đợc gọi là ma trận hệ số của các ràng buộc.
x =



mn
j
n
b
b
c
c
c
x
x
x
.
b
b ;
.
c ;0;
.
x
2
1
2
1
2
1

Tìm các giá trị tối u x
*
= [x
*

]
T

Khi đó A.x b A.x + E.w = b ; E: ma trận đơn vị.
Ví dụ:

21
21
2
1
21
21
74
0 x; 0x
9 x
12
18 30,5x
15 2x
xxZ
x
x
x
+=



+
+

6321

=

n
1j
ijij
bxa khi đó ta có: A
1
.x B
1
3. Nếu ràng buộc ở dạng đẳng thức: A.x = b có thể thay bằng hai ràng buộc bất đẳng
thức A.x b và -A.x -b.
3.2.4. Quan hệ giữa bài toán Min và bài toán Max:
Trong bài toán min: Z = c.x Min
Nếu đặt Z
1
= - c.x Max.
Gọi x
*
là trạng thái tối u Z
1
tức là - c.x
*
= Max(Z
1
) khi đó:
- c.x
*
- c.x hay c.x
*
c.x





0 x
bAx

Ta có bài toán đối ngẫu tơng đơng với bài toán dạng chuẩn:
Tìm y = [y
1
, ,y
m
]
T
để hàm mục tiêu V = b.y Min
Với ràng buộc:





0y
cy.A
T

Chuẩn
Sơ đồ đối ngẫu: x
1
x
2

5
]
T
n = 5
Các ràng buộc:





=++
=
=++
3535131
1515111
a
3 m

bxax
bxaxa

do đó nghiệm tối u có 3 biến khác không x
*
= [*, *, *, 0, 0]
T
.
3.4. Các phơng pháp giải bài toán tối u tuyến tính
3.4.1. Phơng pháp đồ thị:
Phơng pháp này đợc dùng khi số biến số 3.
1. Bài toán phẳng:


a
21
x
1
+ a
22
x
2
b
2

x
1
0, x
2
0
Giải:

Vẽ miền chấp nhận đợc (miền D mà x thoả mãn các ràng buộc hình 3.1):
+ Nếu ràng buộc là đẳng thức thì miền chấp nhận đợc là điểm A, giao điểm của
đờng N
1
M
1
và N
2
M
2
.

b
1
a
21
a
22
a
2n
b
2

a
m1
a
m2
a
mn
b
m

Min
c
1
c
2
c
n
Max
+ Nghiệm cực đại đợc xác định bởi toạ độ điểm A.
+ Nếu đờng cùng mục tiêu tiếp xúc một đỉnh thì nghiệm tối u là đơn trị.
+ Nếu đờng cùng mục tiêu tiếp xúc 2 đỉnh (1 cạnh) thì nghiệm là đa trị.
+ Nếu miền chấp nhận đợc nh hình 2.2 thì toạ độ điểm A xác định giá trị cực tiểu.
Hình 2.1 Hình 2.2
2. Mở rộng:
Đối với bài toán có n biến x
1
, , x
n
, chịu m ràng buộc:
1/ Nghiệm tối u là toạ độ của một đỉnh hay nhiều đỉnh của miền cho phép. Miền cho
phép là một đa diện lồi (n - m) chiều.
2/ Nghiệm là đơn trị nếu 1 đỉnh của đa diện cho phép tiếp xúc với mặt cùng mục tiêu.
3/ Nghiệm là đa trị nếu tiếp xúc tại k đỉnh (k >1); k đỉnh này tạo nên 1 đơn hình (k-1)
chiều. Do đó có thể lấy (k-1) giá trị các biến tuỳ ý, còn n - (k-1) biến khác là hàm tuyến tính
của (k-1) biến tuỳ ý. Đó sẽ là cơ sở của phơng pháp đơn hình.
Chú ý:
Đơn hình là 1 hình có số đỉnh nhiều hơn 1 so với số chiều của không gian. Thí
dụ, trong không gian 2 chiều thì đơn hình là tam giác, trong không gian 3 chiều thì đơn hình
là tứ diện.

x
2
+ a
rm
x
m
= b
r
; r = 1, 2 , , m.
x
2

N
2N
1x
2
*

x
2
=z
9
/
c


x
2
*

x
2
=z
9
/
c
1
-
(
c
1
/
c
2
)
x
1
O x
1
* M
2
M
1
x
1

(
)0
(
m
)0
(
2
)0
(
1
.
3) Chọn nghiệm thử thứ 2:
a) Thử thêm vào biến x
m+1
, lúc này ràng buộc có dạng:

{
rmmrmrmrr
bxaxaxaxa
=
+
+++
++ 11,2211
; r = 1, 2, , m (3.3)
Hệ (3.3) gồm m phơng trình với m+1 biến, (3.3) có nghiệm đơn trị khi các phơng trình
tạo thành hệ phụ thuộc, do đó cột cuối cùng phụ thuộc tuyến tính vào các cột còn lại với hệ số y
i
:
a
r,m+1

y
,
,
y
,
y
.
b) Lấy các số hạng tơng ứng của phơng trình (3.3) trừ đi bội số của (3.4) ký hiệu
bội số đó là > 0, ta có:
a
r1
(x
1
- y
1
) + a
r2
(x
2
- y
2
) + + a
rm
(x
m
- y
m
) + a
r,m+1
= b

x
1
(0)
+ c
2
x
2
(0)
+ , + c
m
x
m
(0)

Z
1
= c
1

1
)0()0()0(
2
)0(
22
)0(
1
)0(
1
).( ).().(
+

=
)0()0(
22
)0(
11

mm
ycycyc +++[]
11 ++

mm
yc
đợc gọi là hiệu suất. (3.7)
Có ba trờng hợp xảy ra:
* Z
1
= 0: nghiệm xuất phát và nghiệm mới tốt nh nhau. Suy ra có hai đỉnh tiếp xúc
giữa đa diện cho phép và mặt cùng mục tiêu.
* Z
1
< 0: nghiệm mới xấu hơn nghiệm xuất phát.
* Z
1
> 0: nghiệm mới tốt hơn nghiệm xuất phát.
** Khi đã chọn đợc nghiệm mới bằng hoặc tốt hơn (Z
1
0) ta đa nó vào cơ sở và

(0)
j
)0
(
j
>

(3.9)
Từ đó suy ra phải loại trừ biến nào ứng với > 0 và nhỏ nhất:
16
0 < = Min
)0(
i
)0
(
i
y
x

4) Thực hiện liên tục các thuật toán ở trên: đa vào biến cha dùng m+2, m+3 , tính
Z
2
, Z
3
, cho đến khi thử hết các biến cơ sở.
Z
1
= [c
m+1
-

tại cả những biến có hại tức là hệ số c
1
< 0. Điều đó giúp ích cho nghiên cứu và không ảnh
hởng đến bớc giải.
3.4.3. Một số thí dụ giải trực tiếp:
Ví dụ: (Z
i
< 0 , i).
Tìm x
*
(x
1
, x
2
, x
3
, x
4
) sao cho hàm mục tiêu:
Z = x
1
+ 2x
2
- 3x
3
+ 4x
4
Max
với các ràng buộc:


= 0:
(x
1
, x
2
, 0, 0)
2. Tìm nghiệm xuất phát: thay biến cơ sở vào phơng trình ràng buộc:




=+
=
800x3x2
100
x
x
21
21

giải đợc: x
1
(0)
= 220; x
2
(0)
= 120
do đó nghiệm xuất phát là:
(220, 120, 0, 0) và Z
0

7
21
21
yy
yy

giải đợc
3y ; 4
(0)
2
)0(
1
==y

Tính hiệu suất của x
3
:
3
= 2
y
2
y
y
c
y
c
)0
(
2
)0

=+
800x10x3x2
100
x
x
x
421
421

từ đó:



=+
=
10y3y2
1
y
y
21
21

6,1y ; 6,2
(0)
2
)0(
1
==y

Tính hiệu suất của x

=
TT
xx ]0,0,120,220[]0,0,,[
*
2
*
1
=

Hàm mục tiêu: Z
*
= 220 + 2.120 = 460
3.4.4. Phơng pháp lập bảng:
Dùng phép xoay (Pivotage) của đại số tuyến tính.
Ví dụ:
Tìm (x
1
, x
2
, x
3
, x
4
) sao cho hàm mục tiêu:
Z = 500x
1
+ 300x
2
+ 200x
3

2000x 10xx5,285
1800 x 5,6x 1,2x 58
2000 x 2x 4x 510
74521
64321
54321
xx
xx
xx

Z - 500x
1
- 300x
2
- 200x
3
- 280x
4
+ 0x
5
+ 0x
6
+ 0x
7
= 0
Lập bảng 1
:
Chọn một biến khác để đa vào cơ sở:
Bảng 1.
s (cột xoay)

Z -500 -300 -200 -280 0 0 0 0
Trên dòng Z, chọn một cột nào có giá trị < 0 và trị số lớn nhất, gọi là cột s (cột xoay).
a
is

a
rs

10
5

18
Xét các tỷ số:
400
5
2000
;225
8
1800
;200
10
2000
===
dòng nào có tỷ số nhỏ nhất gọi là
dòng r (dòng xoay).
a
rs
= 10: gọi là phần tử xoay (pivot).
Lập bảng 2:


Bảng 2.
Biến cơ
sở
x
1
x
2
x
3
x
4
x
5
x
6
x
7

dòng chính x
1
1 0,5 0,4 0,2 0,1 0 0 200
x
6
0 1 -2 -0,8 1 0 200

x
7
0 5,5 0,5 9 -0,5 0 1 1000
Z 0 -50 0 -180 50 0 0 100000


Z 0 -5 -90 0 1,4 4,5 0 109000

Lập bảng 4
: Bảng 4.
Biến cơ
sở
x
1
x
2
x
3
x
4
x
5
x
6
x
7

x
1
1 1,125 0 0 0,001 0,175 0,1 135
x
4
0 0,575 0 1 -0,07 0,025 0,1 105
dòng chính x
3
0 0,65 1 0 -0,26 0,45 0,2 110

5
= -
19
f (x) = ., ,2,1; njMinxc
j
ji
=


Các ràng buộc:
.m
,
,2
,
1i ;b
x
a
1
j
ijij
=


.mm
,
,2m
,
1mi ;b
x
a

i
ta phải thêm biến bù x
n+i
0
Đối với các ràng buộc: a
ij
x
j
= b
i
ta phải thêm biến giả tạo x
n+i
0
Đối với các ràng buộc: a
ij
x
j
b
i
ta phải thêm biến giả tạo rồi biến bù.
Biến bù ứng với ràng buộc: đợc đánh từ số n+1 đến n+m
1
; các biến giả tạo ứng
với ràng buộc và = đợc đánh số từ n+m
1
+1 đến n+m; các biến bù ứng với ràng buộc
đợc đánh số từ n+m+1 đến n+m+m
2
.
Trong hàm mục tiêu, các hệ số ứng với biến bù x

1
+ 2x
2
24000
4) x
1
1000
5) x
2
1000
6) 3x
1
- x
2
0
7) 2,5x
1
+ 2x
2
10000

Giải:

Trong thuật toán, ta đa bài toán về dạng chính tắc bằng cách thêm các biến bù x
3
, x
4
,
x
5

+x
5
= 24000
4) x
1
-x
6
+x
10
= 1000
5) x
2
-x
7
+x
11
= 1000
6) 3x
1
- x
2
-x
8
+x
12
= 0
7) 2,5x
1
+2x
2

+0x
13

chọn M 24000.
Sau khi giải bài toán chính tắc ta đợc:
x
1
=6000, x
2
=4000, x
5
=1000, x
10
=5000, x
11
=3000, x
12
=14000, x
13
=13000, Z=360000.
20
Nh− vËy nghiÖm tèi −u cña bµi to¸n lµ:
x
*
1
= 6000; x
*
2
= 4000
Z


2
1
21
21

⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
=≥
=++
=++
=++
1,2, ,6 i ;0x
12 x- 2x x4x3
8 x-x
2
3
xx
6
x
-
x
x

9
28
;0 ;0 ;
9
8
;
3
10
]
T
;
Z
*
= 12
9
23. 4.
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=≥
=+−−
=++−
=+−+

x
1000
21
21
2
1Z = 2x
1
- 3x
4
+ x
5
+ 2x
6
→ min Z = 30x1 + 45x2 → max
Tr¶ lêi : kh«ng cã nghiÖm tèi −u. Tr¶ lêi : x
*
= [6000,4000]T
Z
*
= 360000.


, , x
p
), y = (y
1
, y
2
, , y
q
), p >0 và q 0. D là tập hợp hữu hạn
các vectơ; f, g
i
là những hàm cho trớc của p+q = n biến số. Khi f, g
i
là các hàm tuyến tính
và D là tập hợp các điểm nguyên thì ta có bài toán nguyên tuyến tính, còn nếu D là tập các
vectơ p thành phần 0 hay 1 thì ta có bài toán nguyên 0 - 1 hay còn gọi là biến binary.
Ta thấy bất kỳ bài toán với các biến số chỉ nhận một số hữu hạn các giá trịcho trớc,
đều có thể quy đợc về bài toán trong đó các biến chỉ nhận các giá trị nguyên. Ví dụ, biến x
biểu thị công suất của một nhà máy điện cần đợc xây dựng chỉ có thể lấy đợc một trong
các giá trị cho sẵn N
1
, N
2
, , N
k
. Khi đó bằng cách đặt:
x = u
1
N
1

2,5m và 50 đoạn dài 1,6m, nên cắt nh thế nào cho tiết kiệm.
Có 3 mẫu cắt nh sau:
Mẫu 1: 2 đoạn 2,5m còn thừa 1m
Mẫu 2: 1 đoạn 2,5m và 2 đoạn 1,6m, còn thừa 0,3m
Mẫu 3: 3 đoạn 1,6m, còn thừa 1,2m.
Gọi x
1
, x
2
, x
3
lần lợt là số thanh cần cắt theo mẫu 1, 2 và 3, ta có bài toán:
x
1
+ 0,3x
2
+ 1,2x
3
Min
Thỏa mãn các ràng buộc:
2x
1
+ x
2
= 30
2x
2
+ x
3
= 50

n
ij
jij
bxa =

=
i = 1, 2, , n (4.2)
x
ij
0 và nguyên, j = 1, 2, , n.
2. Bài toán lập thứ tự gia công các chi tiết máy:
Giả sử cần gia công n. trên m, mỗi chi tiết đều đợc gia công trên các máy theo thứ
tự: 1, 2, , m. Cho biết thời gian gia công chi tiết tứ j trên máy thứ i là t
ij
.
Bài toán đặt ra là lập thứ tự gia công các chi tiết trên các máy để thời gian gia công
các chi tiết là ngắn nhất với điều kiện các chi tiết đợc gia công liên tục, không có khoảng
thời gian gián đoạn khi chuyển từ máy này sang máy khác. Sau đây ta xét bài toán
Sau đây ta xét bài toán: có n chi tiết gia công trên hai máy A và B (giả sử gia công
trên A trớc rồi tới B). Mỗi máy chỉ có thể gia công từng chi tiết một. Cho biết thời gian gia
công chi tiết j trên máy A là a
j
và trên máy B là b
j
. Tìm thứ tự gia công các chi tiết để việc
gia công tất cả các chi tiết trên 2 máy là ngắn nhất.
Mỗi một thứ tự gia công sẽ tơng ứng với một hoán vị = (s
1
, s
2

Min{ t
B
(): P}.
Để giải bài toán này ta có thể dùng thuật toán Johnson với định lý sau:
Dịnh lý Johnson: t
B
() đạt giá trị nhỏ nhất khi thứ tự gia công = (s
1
, s
2
, , s
n
) thỏa
mãn:
Min(
1
,
+kk
ss
ba ) Min(
11
,
++ kk
ss
ba ) (4.4)
Với mọi k = 1, 2, , n-1.
Dựa vào định lý trên ta có thuật toán để tìm thứ tự gia công theo yêu cầu:
1) Ghi lại thời gian công các chi tiết trên mỗi máy vào bảng thời gian gia công:
Chi tiết 1 2 n
Máy A

Máy A
Máy B
1 5 3 4
2 3 2 5

Thứ tự tối u đợc xếp nh sau: Số nhỏ nhất trong bảng là 1, nằm ở hàng máy A, nên chi tiết
I đợc xếp gia công đầu tiên. Bây giờ xóa đi cột chi tiết I. Nh vậy số nhỏ nhất bây giờ là 2,
nằm ở hàng máy B, nên chi tiết III đợc xếp gia công sau cùng. Tơng tự số nhỏ nhất bây
giờ là 3, nằm trên hàng B, nên chi tiết II đợc xếp trớc chi tiết III. Còn lại là chi tiết IV.
Thứ tự gia công tối u là: I, IV, II, III.
3. Bài toán điều công-ten-nơ:
Có n loại hàng đợc xếp xếp lên các công-ten-nơ nh nhau với tải trọng của mỗi
công-ten-nơ là T và dung lơng la K. Hàng loại j có trọng lợng a
j
, thể tích b
j
và số lợng
cần vận chuyển là s
j
(j= 1, 2, , n). Hãy tìm cách xếp tất cả số hàng này lên các công-ten-nơ
sao cho sử dụng ít công-ten-nơ nhất.
Giả sử số công-ten-nơ có sẵn là m, gọi x
ij
là số hàng lọai j đợc chở trên công-ten-nơ
thứ i, y
i
là biến nhận giá trị 1 khi công-ten-nơ thứ i đợc dùng, ngoài ra thì nhận giá trị 0. Bài
toán đa đến mô hình:
Z =
Miny

=1
, j =1, 2, , n
y
i
{0, 1}

Bài tập
1. Một xởng mộc sản xuất 3 loại ghế dựa khác nhau A, B, c. Mỗi loại ghế cần trải qua các
nguyên công đánh bóng, đánh màu và đánh vécni. Ngoài ra ghế loại C còn phải thêm
nguyên công bọc nệm. Bảng dới đây cho biết thời gian cần thiết (tính theo số giờ/tháng) để
thực hiện các nguyên công và tiền lãi của mỗi loại ghế. Cần sản xuất bao nhiêu ghế mỗi loại
để thu đợc nhiều lãi nhất.
Loại ghế Bóng Màu Vécni Nệm
(giờ)
Tiền lãi (đồng)
A
B
C
1.0 0.5 0.7 0
1.2 0.5 0.7 0
0.7 0.3 0.3 0.7
100.000
130.000
80.000
Thời gian có
Mỗi tháng
600 300 300 140
2. một xởng dự định mua hai loại máy để in hình lên vải. Máy A có thể in 100m/ph và
chiếm 50m
2