ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
Vũ Trọng Hiền
MỘT SỐ BÀI TOÁN TỐI ƯU PHI TUYẾN
QUY ĐƯỢC VỀ
BÀI TOÁN QUI HOẠCH TUYẾN TÍNH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2013
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
Vũ Trọng Hiền
MỘT SỐ BÀI TOÁN TỐI ƯU PHI TUYẾN
QUY ĐƯỢC VỀ
BÀI TOÁN QUI HOẠCH TUYẾN TÍNH
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.01.12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học: GS. TS. Trần Vũ Thiệu
Thái Nguyên - 2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
Mục lục
Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1. Kiến thức cơ sở về qui hoạch tuyến tính 4
1.1. Bài toán qui hoạch tuyến tính và tính chất . . . . . . . 4
1.1.1. Nội dung bài toán qui hoạch tuyến tính . . . . . . 4
1.1.2. Tính chất bài toán qui hoạch tuyến tính . . . . . 6
1.2. Qui hoạch tuyến tính đối ngẫu . . . . . . . . . . . . . . . 7
1.2.1. Cặp bài toán đối ngẫu . . . . . . . . . . . . . . . 7
1.2.2. Các quan hệ đối ngẫu . . . . . . . . . . . . . . . 10
1.3. Phương pháp đơn hình . . . . . . . . . . . . . . . . . . . 11

ưu phi tuyến không lồi dạng đặc biệt có thể giải được bằng các phương
pháp của qui hoạch tuyến tính. Phát biểu nội dung bài toán và nêu cách
đưa bài toán về qui hoạch tuyến tính, từ đó có thể áp dụng phương pháp
đơn hình Dantzig để giải bài toán được xét.
Luận văn gồm lời nói đầu, ba chương, kết luận và danh mục các tài
liệu tham khảo.
Chương 1 với tiêu đề "Kiến thức cơ sở về qui hoạch tuyến tính" trình
bày nội dung và các tính chất cơ bản của bài toán qui hoạch tuyến tính,
khái niệm bài toán đối ngẫu và các quan hệ đối ngẫu trong qui hoạch
tuyến tính. Phương pháp đơn hình Dantzig giải bài toán qui hoạch tuyến
tính được nhắc lại ở chương này, với đầy đủ cơ sở lý luận và ví dụ bằng
số để minh họa.
Chương 2 với tiêu đề "Bài toán không lồi dạng đặc biệt" xét một lớp
bài toán tối ưu phi tuyến không lồi dạng đặc biệt: giới thiệu nội dung
và ý nghĩa thực tế của bài toán, trình bày bài toán qui hoạch tuyến tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
tương đương, nêu thuật toán nới lỏng giải bài toán ban đầu và cuối cùng
đưa ra ví dụ số minh họa cho thuật toán giải.
Chương 3 với tiêu đề "Bài toán mở rộng" xét một dạng mở rộng của
bài toán tối ưu phi tuyến không lồi đã đề cập tới ở Chương 2. Nghiên
cứu một số tính chất nghiệm của bài toán và trình bày cách đưa bài toán
về bài toán qui hoạch tuyến tính tương đương. Cuối chương nêu một số
trường hợp riêng của bài toán.
Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn còn có
những thiếu sót nhất định, kính mong quý thầy cô và các bạn đóng góp
ý kiến để tác giả tiếp tục hoàn thiện luận văn này.
Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng
dẫn GS. TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình
làm Luận văn.

n
thỏa mãn điều
kiện



















n

j=1
a
ij
x
j
≤ b

1
+ m
2
+ 1, , m, (1.3)
x
j
≥ 0, j = 1, , n
1
, x
j
≤ 0, j = n
1
+ 1, , n
1
+ n
2
≤ n. (1.4)
sao cho hàm f(x) =
n

j=1
c
j
x
j
đạt cực tiểu. Ở đây a
ij
, b
i
, c

toán không có lời giải.
b) Dạng chính tắc và dạng chuẩn tắc
Người ta thường xét bài toán qui hoạch tuyến tính ở hai dạng sau
đây
• Dạng chính tắc











f(x) ≡
n

j=1
c
j
x
j
→ min,
n

j=1
a
ij

n

j=1
a
ij
x
j
≥ b
i
, i = 1, 2, , m,
x
j
≥ 0, j = 1, , n.
(ràng buộc chính chỉ gồm các bất đẳng thức ≥ đối với bài toán min
hoặc ≤ đối với bài toán max và mọi biến đều không âm).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
Để viết bài toán gọn hơn, ta dùng các ký hiệu véctơ và ma trận sau:
A =





a
11
a
12
· · · a
1n

j
=





a
1j
a
2j
.
.
.
a
mj





, b =





b
1
b



, x =





x
1
x
2
.
.
.
x
n





, 0 =





0
0

tính (dạng bất kỳ) là một tập hợp lồi. Hơn nữa, đó là một tập hợp lồi đa
diện (khúc lồi).
Định lý 1.2. Nếu một qui hoạch tuyến tính có ít nhất một phương
án và hàm mục tiêu bị chặn dưới trong miền ràng buộc (đối với bài toán
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
min) thì bài toán chắc chắn có phương án tối ưu.
Định lý 1.3. Nếu x
0
là một phương án tối ưu của bài toán qui hoạch
tuyến tính (dạng bất kỳ) và nếu x
1
, x
2
(x
1
= x
2
) là phương án thỏa mãn
x
0
= λx
1
+ (1 − λ)x
2
, 0 < λ < 1, thì x
1
, x
2
cũng là các phương án tối ưu.

Định lý 1.6. Nếu bài toán qui hoạch tuyến tính dạng chính tắc có
phương án tối ưu thì cũng có phương án cực biên tối ưu.
1.2. Qui hoạch tuyến tính đối ngẫu
1.2.1. Cặp bài toán đối ngẫu
Cho một qui hoạch tuyến tính, ký hiệu (P ), dưới dạng chuẩn
(P ) f(x) = c
1
x
1
+ c
2
x
2
+ + c
n
x
n
→ min,
a
i1
x
1
+ a
i2
x
2
+ + a
in
x
n

2
y
2
+ + b
m
y
m
→ max,
a
1j
y
1
+ a
2j
y
2
+ + a
mj
y
m
≤ c
j
, j = 1, 2, , n,
y
i
≥ 0, i = 1, 2, , m,
ở đây y = (y
1
, y
2

→ min,
a
i1
x
1
+ a
i2
x
2
+ + a
in
x
n
= b
i
, i = 1, 2, , m,
x
j
≥ 0, j = 1, 2, , n,
là bài toán
g(y) = b
1
y
1
+ b
2
y
2
+ + b
m

Tổng quát, xét bài toán qui hoạch tuyến tính có dạng
f(x) = c
1
x
1
+ c
2
x
2
+ + c
n
x
n
→ min,
a
i1
x
1
+ a
i2
x
2
+ + a
in
x
n
≥ b
i
, i ∈ I
1

≤ b
i
, i ∈ I
3
,
x
j
≥ 0 (j ∈ J
1
), x
j
tùy ý (j ∈ J
2
), x
j
≤ 0 (j ∈ J
3
),
trong đó I
1
∪ I
2
∪ I
3
= {1, , m} , I
i
∩ I
k
= Ø, i, k = 1, 2, 3 (i = k); J
1

y
2
+ + a
mj
y
m
≤ c
j
, j ∈ J
1
,
a
1j
y
1
+ a
2j
y
2
+ + a
mj
y
m
= c
j
, j ∈ J
2
,
a
1j

10
1.2.2. Các quan hệ đối ngẫu
Định lý 1.7.(Đối ngẫu yếu). Nếu x là một phương án bất kỳ của bài
toán gốc (P ) và y là một phương án bất kỳ của bài toán đối ngẫu (Q) thì
f(x) = c
1
x
1
+ c
2
x
2
+ + c
n
x
n
≥ g(y) = b
1
y
1
+ b
2
y
2
+ + b
m
y
m
Hệ quả 1.3.
a) Giá trị mục tiêu của một phương án đối ngẫu bất kỳ là một cận

c) Một qui hoạch có phương án và qui hoạch kia không có phương án.
Khi đó, qui hoạch có phương án sẽ không có phương án tối ưu và hàm
mục tiêu của nó không giới nội trong miền ràng buộc.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Định lý 1.10.(Định lý yếu về độ lệch bù). Một cặp phương án x, y
của hai qui hoạch đối ngẫu (P) và (Q) là những phương án tối ưu khi và
chỉ khi chúng nghiệm đúng các hệ thức:
y
i

n

j=1
a
ij
x
j
− b
i

= 0 với mọi i = 1, 2, , m,
x
j

c
j
−
m


Xét bài toán qui hoạch tuyến tính dạng chính tắc:



c, x → min, (1.5)
Ax = b, (1.6)
x ≥ 0, (1.7)
trong đó A là một ma trận m × n, b ∈ R
m
, c và x ∈ R
n
. Cũng như trước
đây, ta giả thiết:
• Số ràng buộc chính ít hơn số biến của bài toán: m ≤ n;
• Ma trận A có hạng bằng m.
Bài toán qui hoạch tuyến tính được gọi là không suy biến nếu tất cả
các phương án cực biên của nó đều không suy biến, tức là đều có số
thành phần dương bằng m. Bài toán gọi là suy biến nếu có dù chỉ một
phương án cực biên suy biến.
Bây giờ ta giả thiết thêm rằng:
• Bài toán (1.5) - (1.7) không suy biến.
• Biết trước một phương án cực biên x
0
của bài toán.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
Ở cuối bài sẽ nêu cách giải quyết những bài toán không có các giả
thiết này.
Không giảm tổng quát, giả sử phương án cực biên x
0

0
} là độc lập tuyến tính và |J
0
| = m. Hệ véctơ
{A
j
, j ∈ J
0
} gọi là cơ sở của phương án x
0
. Để cho tiện, đôi khi ta cũng
gọi J
0
(với các tính chất như trên) là cơ sở của x
0
. Các véctơ A
j
và các
biến x
j
với j ∈ J
0
được gọi là các véctơ cơ sở và biến cơ sở tương ứng
với x
0
. Còn các véctơ A
j
và các biến x
j
với j /∈ J

z
jk
A
j
= z
1k
A
1
+ z
2k
A
2
+ + z
mk
A
m
, k = 1, 2, , n. (1.8)
Ký hiệu các véctơ cột Z
k
= (z
1k
, z
2k
, , z
mk
)
T
, X
0
B

k
. Mặt khác, ta có
Ax
0
= BX
0
B
= b ⇒ X
0
B
= B
−1
b.
Giá trị hàm mục tiêu tại x
0
bằng
f
0
=

c, x
0

= C
B
X
0
B
= c
1

− c
k
= c
1
z
1k
+ c
2
z
2k
+ + c
m
z
mk
− c
k
, k = 1, 2, , n. (1.10)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
Định lý 1.12. (Dấu hiệu tối ưu). Nếu đối với phương án cực biên x
0
ta có các hệ thức
∆
k
≤ 0, ∀k = 1, 2, , n. (1.11)
thì x
0
là một phương án tối ưu.
Chú ý:
• Nếu A

0
Vì thế trên thực tế, để kiểm tra tối ưu đối với phương án cực biên
hiện có ta chỉ cần kiểm tra điều kiện
∆
k
≤ 0, ∀k /∈ J
0
• Nếu bài toán không suy biến thì (1.11) cũng là điều kiện cần của
tối ưu.
Định lý 1.13. (Dấu hiệu bài toán không có lời giải). Nếu đối với
phương án cực biên x
0
tồn tại k /∈ J
0
sao cho ∆
k
> 0 và z
jk
≤ 0, ∀j ∈ J
0
thì bài toán đã cho không có phương án tối ưu và hàm mục tiêu giảm vô
hạn trong miền ràng buộc của bài toán.
Định lý 1.14. (Cải tiến phương án hiện có). Nếu tồn tại chỉ số s /∈ J
0
sao cho ∆
s
> 0 và z
js
> 0 với ít nhất một j ∈ J
0

θ
0
, j = s
(1.12)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
trong đó số θ
0
được xác định từ hệ thức
θ
0
= min
j∈J
0

x
0
j
z
js
: z
js
> 0

=
x
0
r
z
rs

thành biến phi cơ sở đối với x
1
.
Định lý 1.15. Nếu bài toán qui hoạch tuyến tính có phương án và
mọi phương án cực biên của bài toán đều không suy biến thì thuật toán
đơn hình sẽ có phương án tối ưu (hữu hạn hay vô cực) sau một số hữu
hạn lần thay đổi phương án cực biên.
1.3.2. Thuật toán đơn hình
Thuật toán đơn hình xuất phát từ một đỉnh của tập ràng buộc D.
Tiếp đó kiểm tra xem đỉnh đó đã tối ưu chưa, bằng cách so sánh giá
trị mục tiêu tại đỉnh đó với giá trị mục tiêu tại các đỉnh kề với nó. Nếu
đúng thì dừng tính toán. Trái lại, sẽ tìm một đỉnh (kề với đỉnh trước đó)
có giá trị mục tiêu nhỏ hơn. Quá trình này lặp lại cho tới khi tìm được
đỉnh tối ưu hoặc phát hiện bài toán vô nghiệm. Thuật toán đơn hình
giải qui hoạch tuyến tính gồm các bước sau:
Bước 0. Tìm một phương án cực biên ban đầu x
0
với cơ sở J
0
và
B = {A
j
, j ∈ J
0
} gồm m véctơ cột độc lập tuyến tính của A. Đặt c
B
=
{c
j
: j ∈ J

Bước 2.(Kiểm tra bài toán không có lời giải). Nếu có k /∈ J
0
sao cho
∆
k
> 0 và z
ik
≤ 0, ∀i ∈ J
0
thì hàm mục tiêu của bài toán không bị chặn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
dưới trên tập ràng buộc D (Định lý 1.10): dừng thuật toán. Trái lại,
chuyển sang bước 3.
Bước 3.(Tìm véctơ đưa vào cơ sở). Đưa vào cơ sở véctơ A
s
(s /∈ J
0
)
với
∆
s
= max {∆
k
: k /∈ J
0
} > 0
Bước 4.(Tìm véctơ đưa ra khỏi cơ sở). Loại khỏi cơ sở véctơ thứ r
trong cơ sở B sao cho
z

0
0, j /∈ J
0,
j = s
θ
0
, j = s
Tập chỉ số mới J
1
= (J
0
\ {i
r
}) ∪ {s}. Tính các hệ số khai triển mới theo
z

ik
=

z
ik
−
z
rk
z
rs
z
is
, i = r
z

+ x
5
= 4
2x
1
+ x
2
− x
3
+ x
6
= 3
x
2
+ 4x
3
+ x
4
= 3
x
j
≥ 0, j = 1, 2, , 6.
Bài toán qui hoạch tuyến tính trên có dạng chính tắc. Các vectơ cơ
sở A
5
, A
6
, A
4
là các vectơ đơn vị, nên A

. Phần tử quay là z
52
= 3. Biến đổi bảng
1 theo các quy tắc đã nêu ta nhận được bảng 2.
Trong dòng mục tiêu của bảng 2 còn phần tử dương ở cột x
1
nên
phương án này cũng chưa tối ưu. Biến đưa vào cơ sở x
1
(ứng với δ
1
=
5
3
lớn nhất), biến loại khỏi cơ sở là x
6
. Phần tử quay là z
61
=
5
3
. Biến đổi
bảng 2 theo các quy tắc đã nêu ta nhận được bảng 3.
Trong bảng này mọi δ
k
≤ 0, nên phương án x
2
= (1; 1; 0; 2; 0; 0) là tối
ưu với f
min

trong đó S ⊆ R
n
là một tập lồi đa diện khác rỗng,
X = {x ∈ R
n
: 0 < a ≤ x ≤ A}, Y = {y ∈ R
n
: 0 ≤ b ≤ y ≤ B};
a, A, b, B, c, d ∈ R
n
là các véctơ cho trước (a ≤ A, b ≤ B); α, β là hai số
thực cho trước (α ≤ β); T là ký hiệu chuyển vị (véctơ hay ma trận).
Có thể giải thích mô hình toán học của bài toán (P) như sau. Giả
sử một công ty nông nghiệp cần lập kế hoạch về năng suất và diện tích
của n loại cây trồng, trong đó x
i
và y
i
lần lượt biểu thị năng suất và
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
diện tích cây trồng thứ i cần xác định. Năng suất cây trồng i biến động
trong khoảng [a
i
, A
i
] (tức x ∈ X), còn diện tích cây trồng i biến động
trong khoảng [b
i
, B

bài toán bị phá vỡ và (P) trở thành bài toán tối ưu phi tuyến không lồi
theo các biến x, y và z. Về thực chất (P) có thể xem như bài toán qui
hoạch song tuyến tính với các ràng buộc liên kết (z ∈ S). Mặc dù các kỹ
thuật của tối ưu toàn cục rất đáng được chú ý, nhưng nói chung chúng
không hiệu quả đối với bài toán (P).
Nhờ khai thác cấu trúc riêng biệt của bài toán (P), trong [5] đã chỉ ra
rằng (P) tương đương với bài toán qui hoạch tuyến tính theo các biến z
với ràng buộc z ∈ S và nhiều ràng buộc khác nữa đối với z, thay cho các
ràng buộc (2.1) - (2.2). Tuy nhiên, để giải qui hoạch tuyến tính tương
đương ta không cần biết trước tất cả các ràng buộc của bài toán mà có
thể xây dựng dần từng ràng buộc, khi cần đến trong quá trình giải.
2.2. Bài toán quy hoạch tuyến tính tương đương
Trong mục này ta sẽ nêu cách đưa bài toán (P) về bài toán qui
hoạch tuyến tính tương đương. Muốn thế, ta phân chia các hệ số d
i
(i = 1, 2, , n) thành hai tập con rời nhau:
I
+
= {i : d
i
≥ 0} và I
−
= {i : d
i
< 0} (I
+
∩ I
−
= Ø).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

i
b
i
≥ α. (2.3)
Bổ đề sau giải thích ý nghĩa của giả thiết trên.
Bổ đề 2.1. Có điều kiện (2.3) khi và chỉ khi có ít nhất một y ∈ Y
thỏa mãn α ≤ d
T
y ≤ β.
Chứng minh. Trước hết, giả sử (2.3) đúng. Ký hiệu y
min
là véctơ có
các thành phần b
i
(i ∈ I
+
) và B
i
(i ∈ I
−
) và y
max
là véctơ có các thành
phần B
i
(i ∈ I
+
) và b
i
(i ∈ I

y ≤ β. Nếu trái lại ta có
d
T
y
min
< α ≤ β < d
T
y
max
. (2.4)
Đặt u =
d
T
y
max
− β
d
T
y
max
− d
T
y
min
và v =
d
T
y
max
− α

: a
i
b
i
≤ z
i
≤ A
i
B
i
, i = 1, 2, , n}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
và ký hiệu C là họ tất cả các tập chỉ số I ⊂ {1, 2, , n} sao cho d
i
= 0
với mọi i ∈ I. Tập Z sẽ bị chặn nếu A
i
< +∞ và B
i
< +∞ với mọi
i = 1, 2, , n.
Định lý sau chỉ ra các ràng buộc của qui hoạch tuyến tính tương
đương với bài toán (P).
Định lý 2.1. Bài toán (P) tương đương với qui hoạch tuyến tính sau:
(L) c
T
z → min
với điều kiện z ∈ S ∩ Z và



i∈I
−
\I
d
i
B
i
≤ β, (2.5)

i∈I
+
∩I
d
i
a
i
z
i
+

i∈I
−
∩I
d
i
A
i
z
i

T
y ≤ β. Ta
sẽ chứng tỏ z ∈ S ∩ Z và z thỏa mãn mọi ràng buộc (2.5) - (2.6). Thật
vậy, rõ ràng z ∈ S ∩ Z.
Do x ∈ X nên với i ∈ I
+
ta có
z
i
A
i
≤
z
i
x
i
= y
i
, từ đó
d
i
A
i
z
i
≤ d
i
y
i
và

∩I
d
i
A
i
z
i
+

i∈I
−
∩I
d
i
a
i
z
i
+

i∈I
+
\I
d
i
b
i
+

i∈I

d
i
y
i
+

i∈I
−
\I
d
i
y
i
= d
T
y ≤ β.
(có đẳng thức là do I = (I
+
∩ I) ∪ (I
+
\I) ∪ (I
−
∩ I) ∪ (I
−
\I)).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
Điều này chứng tỏ z thỏa mãn ràng buộc (2.5) với mọi I ∈ C. Bằng
lập luận tương tự, có thể chỉ ra rằng z cũng thỏa mãn ràng buộc (2.6)
với mọi I ∈ C.

≤ B
i

⊆ I
−
. (2.7)
Ta xác định véctơ x
1
∈ X và y
1
∈ Y sao cho z
i
= x
1
i
y
1
i
(i = 1, 2, , n)
và d
T
y
1
≤ β như sau:
a1) với i ∈ I
1
đặt x
1
i
= A

i ∈ I
+
\I
1
);
c1) với i ∈ I
2
đặt x
1
i
= a
i
, y
1
i
=
z
i
a
i
;
d1) với i ∈ I
−
\I
2
đặt x
1
i
=
z

i
(tức y
1
∈ Y ) và z
i
= x
1
i
y
1
i
với mọi i = 1, 2, , n. Cũng dễ thấy rằng
d
T
y
1
≤ β. Thật vậy, có hai khả năng:
+ Nếu I
1
= I
2
= Ø do z thỏa mãn (2.5) với I = Ø nên ta có:
β ≥

i∈I
+
d
i
b
i

y
1
=

i∈I
+
d
i
y
1
i
+

i∈I
−
d
i
y
1
i
≤ β.
+ Nếu trái lại (I
1
∪ I
2
= 0) thì do z thỏa mãn (2.5) với I =
{I
1
∪ I
2

d
i
A
i
z
i
+

i∈I
−
∩I
d
i
a
i
z
i
+

i∈I
+
\I
d
i
b
i
+

i∈I
−

\I
1
d
i
b
i
+

i∈I
−
\I
2
d
i
B
i
= d
T
y
1
≤ β.
(có đẳng thức cuối là theo cách xác định y
1
).
Bằng cách lập luận tương tự, ta có thể tìm được véctơ x
2
∈ X và
y
2
∈ Y sao cho z

=

i ∈ I
−
:
z
i
A
i
≥ b
i

⊆ I
−
và xác định x
2
và y
2
theo cách sau:
a2) x
2
i
= a
i
, y
2
i
=
z
i

c2) x
2
i
= A
i
, y
2
i
=
z
i
A
i
với i ∈ I
4
;
d2) x
2
i
=
z
i
b
i
, y
2
i
= b
i
với i ∈ I

= x
i
y
i
với mọi i = 1, 2, , n. Để làm điều
này ta nhận xét là a
i
y
k
i
≤ x
k
i
y
k
i
= z
i
≤ A
i
y
k
i
với k = 1, 2 và i = 1, 2, , n.
(do x
k
∈ X, y
k
≥ 0). Từ đó
z

i
y
i
nếu y
i
= 0
t ∈ [a
i
, A
i
] nếu y
i
= 0
(∀i = 1, 2, , n) (2.9)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
Từ (2.8) - (2.9) suy ra z
i
= x
i
y
i
và a
i
≤ x
i
≤ A
i
với mọi i = 1, 2, , n,
tức là x = (x


i∈I
+
∩I
d
i
A
i
z
i
+

i∈I
−
∩I
d
i
a
i
z
i
+

i∈I
+
\I
d
i
b
i

i
z
i
+

i∈I
+
\J
d
i
B
i
+

i∈I
−
\J
d
i
b
i
≥ α, ∀J ∈ H
k
, (2.11)
với G
k
, H
k
là các tập con của C (G
1

≥ b
i

∪

i ∈ I
−
:
z
i
a
i
≤ B
i

, (2.12)
M =

i ∈ I
+
: d
i
> 0 và
z
i
a
i
≤ B
i
