23
Chương II
GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
BẰNG PHƯƠNG PHÁP ĐƠN HÌNH

1. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BTQHTT DẠNG CHÍNH TẮC
1.1. Ví dụ . Xét BTQHTT: Max z = 8x
1
+ 6x
2
,
với các ràng buộc
4x
1
+ 2x
2
≤ 60
2x
1
+ 4x
2
≤ 48
x
1
, x
2
≥ 0
Đưa BTQHTT
dạng chuẩn tắc trên về dạng chính tắc bằng các biến bù không
âm x

, x
2
, x
3
, x
4
≥ 0.
Chú ý. BTQHTT có dạng chính tắc là BTQHTT với các biến không âm, các ràng
buộc có dấu “=”, hệ số vế phải của các ràng buộc không âm. Ngoài ra, mỗi phương trình
bắt buộc phải có một biến đứng độc lập với hệ số +1.

Cách lập và biến đổi các bảng đơn hình
Để giải BTQHTT dạng chính tắc trên đây, cần lập một số bảng đơn hình như
trong bảng II.1. Trước hết, cần điền số liệu của bài toán đã cho vào bảng đơn hình bước 1:
– Cột 1 là cột hệ số hàm mục tiêu ứng với các biến cơ sở đã chọn. Phương án
xuất phát có thể chọn là x
1
= x
2
= 0 (đây chính là điểm gốc toạ độ O(0, 0) trên hình II.1),
do đó x
3
= 60, x
4
= 48. Như vậy tại bước này chúng ta chưa bước vào sản xuất, nên
trong phương án chưa có đơn vị sản phẩm loại I hay loại II nào được sản xuất ra (chỉ
“sản xuất” ra các lượng nguyên liệu dư thừa, ta cũng nói là các “sản phẩm” loại III và
IV), và giá trị hàm mục tiêu z tạm thời bằng 0. Các biến bù có giá trị lớn hơn 0 có nghĩa
là các nguyên liệu loại tương ứng chưa được sử dụng h
ết. Ta gọi các biến x

3
= 0 c
4
= 0
Hệ số hàm
mục tiêu c
j

Biến cơ sở Phương án
x
1
x
2
x
3
x
4

Bảng đơn hình bước 1
0
0
x
3

x
4

60
48
4

= 6 Δ
3
= 0 Δ
4
= 0
Bảng đơn hình bước 2
8
0
x
1
x
4

15
18
1
0
1/2
3
1/4
–1/2
0
1
Hàng z z
0
= 120 z
1
= 8 z
2
= 4 z

6
1
0
0
1
1/3
–1/6
–1/6
1/3
Hàng z z
0
= 132 8 6 5/3 2/3
Hàng Δ
j
= c
j
– z
j

0 0 –5/3 –2/3

Phân tích bảng đơn hình bước 1
– Hệ số ứng với biến x
1
trên hàng thứ nhất là a
11
= 4 có nghĩa là tỷ lệ thay thế
riêng giữa một đơn vị sản phẩm loại I và một đơn vị sản phẩm loại III là 4 (giải thích:
xét phương trình (hay ràng buộc) thứ nhất 4x
1


vào phương án sản xuất mới. Còn z
0
là giá trị của hàm mục tiêu đạt được tại phương án
đang xét: z
0
= (cột hệ số của hàm mục tiêu)× (cột phương án) = 0×60 + 0 × 48 = 0.
– Trên hàng Δ
j
cần ghi các giá trị Δ
j
, j = 1, 2, 3, 4, tính theo công thức Δ
j
= c
j
–
z
j
= lợi nhuận / đơn vị sản phẩm – chi phí / đơn vị sản phẩm. Vậy Δ
j
là "lãi biên" / một
đơn vị sản phẩm khi đưa một thêm một đơn vị sản phẩm loại x
j
vào phương án sản xuất
mới. Nếu Δ
j
> 0 thì hàm mục tiêu còn tăng được khi ta đưa thêm các sản phẩm loại j vào
phương án sản xuất mới. Có thể chứng minh được Δ
j
chính là đạo hàm riêng

vào làm biến cơ sở mới.
Bước 2: Chọn hàng xoay để xác định đưa biến nào ra khỏi tập các biến cơ sở (vì
tại mỗi bước số biến cơ sở là không thay đổi). Để chọn hàng xoay, ta thực hiện quy tắc
“tỷ số dương bé nhất” bằng cách lấy cột phương án (60, 48)
T
chia tương ứng cho cột
xoay (4, 2)
T
để chọn tỷ số bé nhất. Một điều cần chú ý là ta chỉ xét các tỷ số có mẫu số
dương.
Vì Min {60/4, 48/2} = 60/4 đạt được tại hàng đầu, nên hàng xoay là hàng đầu
(hàng tương ứng với biến x
3
). Do đó cần đưa x
3
ra khỏi tập các biến cơ sở.
Bước 3: Chọn phần tử xoay nằm trên giao của hàng xoay và cột xoay.
Bước 4: Xoay sang bảng đơn hình mới, xác định các biến cơ sở mới để điền vào
cột biến cơ sở, đồng thời thay các giá trị trong cột hệ số hàm mục tiêu. Sau đó, tính lại
các phần tử của hàng xoay bằng cách lấy hàng xoay cũ chia cho phần tử xoay để có
hàng mới tương ứng.
Bước 5: Các phần tử còn lại của bảng đơn hình mới tính theo quy tắc “hình chữ
nhật”: (1)
mới
= (1)
cũ
– (2)
cũ
× (4)
cũ

2
+ (1/4)x
3
= 15 (2.1’)
0x
1
+ 3x
2
– (1/2)x
3
+ x
4
= 18 (2.2’)
bằng cách lấy phương trình (2,1) chia cho 4 (phần tử xoay) để có (2,1’), rồi lấy
(2,2) trừ bớt 2× (2.1)/4 để có (2,2’). Đây chính là nội dung của bước 4 và bước 5. Còn
việc thực hiện bước 3 sẽ đảm bảo rằng giá trị của các biến cơ sở mới không âm (x
1
= 15,
x
4
= 18).
Áp dụng thủ tục xoay cho các phần tử nằm trên hàng 1 và 2 của bảng đơn hình
bước 1, sau đó tính các giá trị trên hàng z
j
và Δ
j
tương tự như khi lập bảng đơn hình
bước 1, chúng ta sẽ nhận được bảng đơn hình bước 2.
(1)
(2)

2
= 2 > 0
nên còn có thể cải thiện hàm mục tiêu bằng cách đưa biến x
2
vào làm biến cơ sở mới.
Thực hiện các bước xoay sang phương án cực biên kề tốt hơn, chúng ta sẽ có bảng đơn
hình bước 3.
Phân tích bảng đơn hình bước 3
Tại bảng đơn hình bước 3 ta thấy điều kiện tối ưu đã được thoả mãn (Δ
j
≤ 0, ∀j
=
1, 4 ) nên không còn khả năng cải thiện phương án. Phương án tối ưu đã đạt được tại x
1

= 12, x
2
= 6, x
3
= 0, x
4
= 0, tức là tại điểm cực biên B(12, 6) với giá trị z
max
= 132.
Một số chú ý
– Điều kiện tối ưu cho các BTQHTT dạng Max là Δ
j
≤ 0, ∀j .
– Đối với các BTQHTT cần cực tiểu hoá hàm mục tiêu thì điều kiện tối ưu (hay
tiêu chuẩn dừng) là Δ

Bước 1: Kiểm tra điều kiện tối ưu. Nếu điều kiện tối ưu Δ
j
= c
j
– z
j
≤ 0, ∀j =
1, n đã được thoả mãn thì in / lưu trữ kết quả của bài toán và chuyển sang bước kết thúc.
Bước 2: Nếu tồn tại một chỉ số j sao cho Δ
j
> 0 thì tiến hành thủ tục xoay gồm
năm bước đã biết, tính lại các Δ
j
, ∀j = 1, n và quay lại bước 1 (Chú ý: Trong trường hợp

27
ta tìm được cột xoay mà không tìm được hàng xoay thì kết luận hàm mục tiêu không bị
chặn, in / lưu trữ kết quả của bài toán và chuyển sang bước kết thúc).
Bước kết thúc. Dừng.
1.2. Thuật toán đơn hình cho BTQHTT dạng chính tắc
Xét BTQHTT sau (xem thêm giáo trình của Nguyễn Hải Thanh, Tối ưu hoá,
Nxb Bách Khoa, 2007):
z = f(x) = c
1
x
1
+ c
2
x
2

2n
x
n
≤ b
2

a
m1
x
1
+ a
m2
x
2
+ + a
mn
x
n
≤ b
m
x
1
, x
2
, , x
n
≥ 0 (điều kiện không âm).
Đưa BTQHTT trên về dạng chính tắc:
z = f(x) = c
1

= b
1

a
21
x
1
+ a
22
x
2
+ + a
2n
x
n
+ x
n+2
= b
2

a
m1
x
1
+ a
m2
x
2
+ + a
mn

1
1=
=c
c
n
n
+
+
1
1
=
=0
0
,
,.
.
.
.
,
,t
t
ứ
ứ
c
cl
l
à
àc
c
B
B=
=
–
–Đ
Đ
ặ
ặ
t
tc
c
h
h
ỉ
ỉs
s
ố
ốc


r
r
(
(
1
1
)
)=
=n
n+
+1
1
,
,.


m
m
.
.

–
–G
G
á
á
n
nx
x
r
r
(
(
i
i
)

Đ
Đ
ặ
ặ
t
tf
f
l
l
a
a
g
g=
=2
2
.
.C
C

c
c1
1
:
:–
–T
T
í
í
n
n
h
hc
c
T
T
x
x

+
+.
.
.
.
.
.+
+d
d
m
m
x
x
r
r
(
(
m
m
)
)

m
p
jp
p1
ad
=
∑
,
,∀
∀
j
j=
=1, n m
+
.
.–
–


Δ
B
B
]
]=
=[
[
T
N
c
–
–
T
B
c
B
B
–
–
1
1
N
N
,

r
o
o
n
n
g
gđ
đ
ó
óΔ
Δ
B
B=
=0
0
.
.


j–
–z
z
j
j
,
,v
v
ớ
ớ
i
iz
z
j
j=

{
1
1
,
,2
2
,
,…
…
,
,n
n+
+m
m
}

(
m
m
)
)
}
}v
v
à
àΔ
Δ
j
j=
=c
c
j
j



B
B=
={
{
r
r
(
(
1
1
)
)
,
,…
…
,
,r

z
N
N=
=
T
B
c
B
B
–
–
1
1
N
Nv
v
à
àz
z
B
B

ư
ớ
ớ
c
c2
2
:
:

N
N
ế
ế
u
ut
t
ồ
ồ
n
n



N
Ns
s
a
a
o
oc
c
h
h
o
oΔ
Δ
j
j>
>


nt
t
h
h
ủ
ủt
t
ụ
ụ
c
cx
x
o
o
a
a
y
y
.
.



x
x
o
o
a
a
y
y
:
:c
c
h
h
ọ
ọ
n
nc
c
ộ
ộ
t
t



m
m
ộ
ộ
t
tc
c
h
h
ỉ
ỉs
s
ố
ốj
jc
c
ó

>0
0
.
.

T
T
h
h
ô
ô
n
n
g
gt
t
h
h
ư
ư
ờ

v
ớ
ớ
i
iΔ
Δ
j
j>
>0
0l
l
ớ
ớ
n
nn


n
n
g
g
ẫ
ẫ
u
un
n
h
h
i
i
ê
ê
n
n
.
.–
–X

o
a
a
y
yq
qt
t
h
h
e
e
o
oq
q
u
u
y
yt


b
b
é
én
n
h
h
ấ
ấ
t
t
:
:r(q) r(i)
is
qs is
xx
Min , a 0
aa
⎧⎫
=∀>
⎨⎬
⎩⎭
.


h
h
ợ
ợ
p
pk
k
h
h
ô
ô
n
n
g
gt
t
ồ
ồ
n
nt

tf
f
l
l
a
a
g
g=
=0
0v
v
à
àc
c
h


k
k
ế
ế
t
tt
t
h
h
ú
ú
c
c
.
.–
–X
X
á
á
c

x
o
o
a
a
y
ya
a
q
q
s
s
.
.–
–T
T
í
í
n
n
h

ns
s
a
a
n
n
g
gb
b
ả
ả
n
n
g
gđ
đ
ơ
ơ
n
n


:
=
=b
b
q
q
/
/
a
a
q
q
s
s
,
,a
a
q
q
j
j:

.∀
∀i
i≠
≠q
qt
t
í
í
n
n
h
hl


b
b
q
q
*
*
a
a
i
i
s
sv
v
à
àa
a
i
i
j
j:

s
,
,∀
∀
j
j
.
.

–
–Đ
Đ
ặ
ặ
t
tl
l
ạ

i
ế
ế
n
nc
c
ơ
ơs
s
ở
ở
:
:r
r
(
(
q
q
)
)


,v
v
à
àx
x
r
r
(
(
i
i
)
)=
=b
b
i
i


ề
ềb
b
ư
ư
ớ
ớ
c
c1
1
.
.B
B
ư
ư
ớ
ớ
c
c∀
∀
j
j∈
∈N
Nt
t
h
h
ì
ìđ
đ
ặ
ặ
t
t

u
u
y
y
ể
ể
n
ns
s
a
a
n
n
g
gb
b
ư
ư
ớ
ớ
c
c
k
k
ế
ế
t
tt
t
h
h
ú
ú
c
c
:
:G
G
h
h
i
il
l

v
v
à
à
o
oc
c
ủ
ủ
a
aB
B
T
T
Q
Q
H
H
T
T
T
Tc
c
ù
ù
n
n
g
g
.
.N
N
ế
ế
u
uf
f
l
l
a
a
g
g

ậ
ậ
n
nB
B
T
T
Q
Q
H
H
T
T
T
Tc
c
ó
óh
h
à
à

g
gb
b
ị
ịc
c
h
h
ặ
ặ
n
nt
t
r
r
ê
ê
n
n
.
.
1
1t
t
h
h
ì
ìk
k
ế
ế
t
tl
l
u
u
ậ
ậ
n
n

n
n
g
gá
á
n
nt
t
ố
ố
i
iư
ư
u
uđ
đ
ã
ã

.
.

2. PHƯƠNG PHÁP ĐƠN HÌNH HAI PHA GIẢI BTQHTT TỔNG QUÁT
Từ trước tới nay, chúng ta luôn giả sử rằng BTQHTT được xem xét luôn có
phương án và có thể biết được một phương án (cực biên) ban đầu của nó để khởi tạo
quá trình giải. Trong mục này chúng ta sẽ đi xét các trường hợp khi chưa biết BTQHTT
có phương án hay không, cũng như chưa biết được phương án cực biên ban đầu. Đối
với những trường hợp này có thể sử dụng phương pháp đơn hình hai pha. Chúng ta sẽ
trình bày phươ
ng pháp đơn hình hai pha thông qua ví dụ sau.
2.1. Ví dụ . Max z = 8x
1
+ 6x
2
, với các ràng buộc
12
12
12
4x 2x 60
2x 4x 48
x,x 0.
+≤
⎧
⎪
+≥
⎨

Pha 1. Tìm một phương án cực biên xuất phát bằng cách xét BTQHTT sau đây:
Min
ω = x
5
, với các ràng buộc
29
123
1245
12345
4x 2x x 60
2x 4x x x 48
x,x,x,x,x 0.
++=
⎧
⎪
+−+=
⎨
⎪
≥
⎩
(2.3)

Bảng II.2. Các bảng đơn hình giải bài toán pha 1
0 0 0 0 1
Hệ số hàm mục
tiêu
Biến cơ

0
–1
0
+1
Hàng ω ω
0
= 48 ω
1
= 2 ω
2
= 4 ω
3
= 0 ω
4
= –
1
ω
5
=
1
Hàng Δ
jΔ
1
= –2
Δ
2
= –

= 0
0 0 0 0 0
Hàng Δ
j

0 0 0 0 1

Mục đích của pha 1 là để giải BTQHTT với các ràng buộc (2.3) hay còn gọi
là bài toán
ω. Nếu tìm được phương án tối ưu của bài toán ω với các biến giả đều
nhận giá trị bằng 0 thì điều này chứng tỏ BTQHTT ban đầu có phương án. Trong
trường hợp đó dễ dàng tìm được một phương án cực biên của nó (xem bảng II.2).
Tại bảng đơn hình cuối cùng, ta thấy
Δ
j
≤ 0, ∀j, nên phương án tối ưu đã đạt
được với x
2
= 12, x
3
= 36, x
1
= x
4
= x
5
= 0 và ω
min
= 0.
Do đó chúng ta đưa ra kết luận là BTQHTT ban đầu có phương án x

x,x,x,x 0.
++=
⎧
⎪
+−=
⎨
⎪
≥
⎩

Nhận xét. Kết quả giải ví dụ trên bằng phương pháp đơn hình hai pha cũng
giống với kết quả đạt được khi giải bằng phương pháp đơn hình mở rộng. Tuy nhiên,
khi sử dụng phương pháp đơn hình hai pha, chúng ta tránh được sự phiền phức trong
việc khai báo giá trị dương đủ lớn của tham số M như trong phương pháp đơn hình mở
rộng.

30
Bảng II.3. Các bảng đơn hình giải bài toán pha 2
8 6 0 0
Hệ số hàm
mục tiêu
Biến cơ sở Phương án
x
1
x
2
x
3
x
4

4
=–3/2
Hàng Δ
jΔ
1
= 5 Δ
2
= 0 Δ
3
= 0 Δ
4
= 3/2
0
6
x
4

x
2

72
30
6
2
0
1
1

x
j
→ Min/ Max

n
ij j i
j1
n
ij j i
j1
n
ij j i
j1
j
i1,m
1
im1,mm
112
imm 1,mm m
12 123
j1,nm m m
123
ax b ( )
ax b ( )
ax b ( )
x0 ( )
=
=
=
=

ràng buộc) và = (m
3
ràng buộc).
- Nhập số biến: n biến.
- Nhập véc tơ hệ số hàm mục tiêu: C = [ c
1
, c
2
, . . ., c
n
].
- Nhập véc tơ hệ số vế phải: b = [ b
1,
b
2,
. . ., b
m
].
- Nhập ma trận hệ số ràng buộc: A = [a
i j
]
m x n
.
Bước 2:
Đưa bài toán về dạng chính tắc: dạng Max đưa về dạng Min.
Đưa thêm biến bù thiếu: m
1
biến x
n+i
,

Nếu m
2
+ m
3
≠ 0, giải bài toán theo hai pha bằng cách chuyển
sang bước 3.

31
Sơ đồ thuật giải (cho BTQHTT gốc là bài toán Max)

∀
k
,

Δ
k
≤
0 ?
Y
N
Kết thúc
Xuất kết quả
Tính Max Δ
k
, Δ
k
>
0
Tìm cột
Hàm mục tiêu không
bị chặn, BT vô nghiệm
Tìm phần tử
Chuyển đổi
cơ sở
N
Y
Tìm hàng xoay
Tính
f(
)

Xóa biến giả
Pha I
Pha II
Sơ đồ thuật giải đơn hình hai pha

32

123
m2*m m
ij j i 1 2 3
j1
j123
ax b (i 1,m m m)
x0 j1,(nm2*mm).
++
=
⎧
⎪
==++
⎪
⎨
⎪
≥∀= + + +
⎪
⎩
∑

Kết thúc pha 1: Xảy ra ba trường hợp sau:
–
Phương án tối ưu không có biến giả, lấy đó làm phương án xuất phát,

3.1. Giải BTQHTT
Xét bài toán quy hoạch c
1
x
1
+ c
2
x
2
+ …+ c
n
x
n
= f(x) → max / min
a
11
x
1
+ a
12
x
2
+ … + a
1n
x
n
Q b
1

a

x
j
≥ 0, j = 1, . . . , n nguyên hoặc nhị phân 0–1.

33
Trong đó Q là một trong các phép toán quan hệ
≥ , ≤ hoặc = , thứ tự các phép
toán quan hệ trong các ràng buộc là tuỳ ý. Như vậy bài toán trên có thể là BTQHTT
thông thường, quy hoạch tuyến tính nguyên hay quy hoạch 0–1. Cách bố trí dữ liệu cho
trên bảng tính:

c[1] c[2] . . . . . . c[n]
Σ c[j] x[j]

a[1,1] a[1,2] . . . . . . a[1,n]
Σ a[1,j] x[j]
b[1]
a[2,1] a[2,2] . . . . . . a[2,n]
Σ a[2,j] x[j]
b[2]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a[m,1] a[m,2] . . . . . . a[m,n]
Σ a[m,j] x[j]
b[m]
x[1] x[2] . . . . . . x[n]

Hàng cuối cùng là các giá trị ban đầu của các biến để các công thức của Excel
hoạt động, có thể lấy giá trị của tất cả các biến bằng 1.
Xét bài toán:
x

≤ 2
x
1
+4x
2
–2x
3
≤1
x
1
, x
2
, x
3
≥
0
Các bước thực hiện để giải bài toán:
Bước 1. Nhập dữ liệu bài toán vào bảng tính dưới dạng sau: Phương án ban đầu X = (1, 1, 1), nó có thể không chấp nhận được.
Bước 2. Tính giá trị hàm mục tiêu tại ô E2 bằng công thức =
SUMPRODOCT($B$7 : $D$7, B2 : D2) Hàm Sumproduct cho tích vô hướng của hai
dãy ô. Copy công thức từ ô E2 sang dãy các ô E3 : E6 nhằm tính giá trị vế trái của bốn
ràng buộc bài toán (1).
Bước 3. Dùng lệnh Tools / Solver, xuất hiện hộp thoại Solver Parameters.

34

Mục Set Target Cell: chọn ô đích (chứa giá trị hàm mục tiêu), có thể nháy vào

}.
Để giải bài toán quy hoạch phi tuyến bằng Solver ta cần xác định khối ô để chứa
các biến (x[1], x[2], . . . , x[n]), một ô chứa giá trị hàm mục tiêu f(x), khối m ô chứa giá
trị các hàm g
i
(x) .
Ví dụ. Giải bài toán quy hoạch toàn phương:
– x
1
–2x
2
+0,5x
1
2
+0,5x
2
2
→Min
2x
1
+3x
2
+ x
3
=6
x
1
+4x
2
+ x

– The maximum time limit was reached, continue anyway ? thời gian chạy vượt
quá thời gian tối đa ngầm định. Ta có thể sửa giá trị trong mục Max Time trong gộp
thoại Solver Options.
Chú ý, nếu các lệnh Solver và Data Analysis không có trong menu Tools ta phải
cài đặt bổ sung từ đĩa CD: dùng lệnh Tools / Add-Ins, hiện hộp thoại, chọn mục Solver
Add in và Analysis ToolPak.

36
3.3. Một số ví dụ khác
Bài 1. Giải BTQHTT nguyên bộ phận:
z=5x
1
+x
2
+x
3
+2x
4
+3x
5
→min
–x
2
+5x
3
–x
4
–2x
5
≤ 2

+38x
4
+20x
5
+6x
6
+8x
7
+19x
8
+10x
9
+11x
10
→max
15x
1
+12x
2
+9x
3
+27x
4
+15x
5
+5x
6
+8x
7
+20x

2
+14x
4
–x
5
2
+18x
5
–180 →Min
–x
1
–2x
2
+x
3
+2x
4
+3x
5
≤ 85
–7x
1
+9x
2
–5x
3
+33x
4
–11x
5

4
+x
5
≤ 300
x
1
, x
2
, x
3
, x
4
, x
5
≥0
Đáp số. Với phương án ban đầu X = (50, 50, 50, 50, 50) dùng Solver có phương
án tối ưu là X = (0, 190, 0, 0, 110) và trị tối ưu hàm mục tiêu là - 45640.

4. GIẢI BTQHTT TRONG LINGO
LINGO cho phép giải rất nhiều loại toán tối ưu, trong đó có BTQHTT (biến liên
tục cũng như biến nguyên). Để giải bài toán này, chúng ta cần cài đặt Lingo vào trong
máy tính. Nhấn vào biểu tượng Lingo trên màn hình để vào cửa sổ Lingo. Sau đó thực
hiện các lệnh Lingo:
Menu > New > <Untitle> và gõ vào các dữ liệu của bài toán.
Nhập bài toán
max = 8*x1+6*x2;
4*x1+2*x2<=76;

37
2*x1+5*x2<=52;

X1 17.00000 -5.600000
X2 3.600000 0.0000000E+00
Row Slack or Surplus Dual Price
1 157.6000 1.000000
2 0.8000000 0.0000000E+00
3 0.0000000E+00 1.200000 38
Kết quả chạy bài toán khi các biến đều nguyên
Rows= 3 Vars= 2 No. integer vars= 2 ( all are linear)
Nonzeros= 8 Constraint nonz= 4( 0 are +- 1) Density=0.889
Smallest and largest elements in absolute value= 2.00000 76.0000
No. < : 2 No. =: 0 No. > : 0, Obj=MAX, GUBs <= 1
Single cols= 0
Optimal solution found at step: 7
Objective value: 156.0000
Branch count: 2
Variable Value Reduced Cost
X1 18.00000 -8.000000
X2 2.000000 -6.000000
Row Slack or Surplus Dual Price
1 156.0000 1.000000
2 0.0000000E+00 0.0000000E+00
3 6.000000 0.0000000E+00
5. GIẢI BTQHTT BẰNG PHẦN MỀM QHTT
Sử dụng phần mềm QHTT trên mạng giáo dục edu.net.vn, dễ dàng nhập được
dữ liệu BTQHTT và có đáp số với toàn bộ các bảng trung gian. Tuy nhiên phần mềm
này chỉ áp dụng cho các biến liên tục và vẫn còn sai sót.


4
là biến bù
x
1
>=0, x
2
>=0, x
3
>=0, x
4
>=0

C
i
X
i
Y
i
X
1
X
2
X
3
X
4

Lamda
0
X


Lamda
8
X
1

15 1 1/2 1/4 0 30
0
X
4

18 0
3
-1/2 1 6
F(x) 120 0
-2

2 0

D

C
i
X
i
Y
i
X
1
X