Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên i
MỤC LỤC

Nội dung
Trang
Mục lục
i
Danh mục các chữ viết tắt
iv
Danh mục các hình
v
MỞ ĐẦU
1
Chương 1. Tổng quan về quy hoạch toán học
3
1.1. Phát biểu bài toán Quy hoạch toán học
3
1.1.1. Bài toán Quy hoạch toán học tổng quát
3
1.1.2. Phân loại bài toán
4
1.2. Phát biểu bài toán đối ngẫu và phân tích nghiệm của bài
toán đó.
5
1.2.1. Cách thành lập bài toán đối ngẫu
5
1.2.2. Các tính chất và định lý đối ngẫu

30
2.2.1. Tập nghiệm của bất phương trình tuyến tính
30
2.2.2. Vấn đề phương án cực biên và cơ sở xuất phát giai
đoạn I
32
2.3 Các hàm mục tiêu
35
2.3.1. Ý nghĩa kinh tế của hàm mục tiêu
35
2.3.2. Hàm mục tiêu của một số mô hình lập kế hoạch
sản xuất thực tế
36
2.4. Các phương pháp giải
38
2.4.1. Phương pháp đơn hình giải bài toán quy hoạch
tuyến tính
38
2.4.2. Giải bài toán quy hoạch tuyến tính hai biến bằng
phương pháp hình học
44
2.5. Phân tích phương án tối ưu
45
2.5.1. Phương án
45
2.5.2. Phương án cực biên
45
2.5.3. Phương án tối ưu
45
2.5.4. Sự tồn tại phương án tối ưu

3.3.1. Sơ đồ thuật toán
56
3.3.2. Cài đặt phần mềm
58
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
63
TÀI LIỆU THAM KHẢO
64 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên iv
DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT

Stt
Từ viết tắt
Ý nghĩa
Trang
1

≤, =, ≥
3
2



Quan hệ trội hơn


Quy hoạch rời rạc
4
11
QHN
Quy hoạch nguyên
4
12
QHĐMT
Quy hoạch đa mục tiêu
5
13
NNLG
Người nhận lời giải
14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên v
DANH MỤC CÁC HÌNH

Stt
Hình
Nội dung
Trang
1
2.1
Sơ đồ thuật toán đơn hình
43


- 1 -
MỞ ĐẦU
Trong giai đoạn kinh tế thị trường, sự cạnh tranh hàng hoá quyết liệt xẩy ra
thường xuyên thì một phương án sản xuất cần phải được cân nhắc kỹ càng trước khi
nó được thực thi. Một phương án sản xuất thường phụ thuộc rất nhiều vào các yếu
tố như lao động, nguyên vật liệu, sức tiêu thụ, …Vì vậy một phương án sản xuất
cần phải được bao hàm các hạn chế trên, đồng thời phải đảm bảo được mức tổng lãi
(hoặc chi phí) tốt nhất.
Đặc biệt, khi một tổng công ty có nhiều công ty con, mỗi công ty đều muốn
có phương án sản xuất tốt nhất của mình nhưng phải nằm trong mục tiêu của tổng
công ty. Vì vậy, phương án sản xuất tốt kết hợp giữa tổng công ty và các công ty
con cần phải được nghiên cứu. Do đó tôi tiến hành nghiên cứu đề tài: “Lập kế hoạch
sản xuất tối ưu giữa tổng công ty và các công ty con trên cơ sở lý thuyết quy hoạch
toán học”. Với nội dung nghiên cứu:
 Mục tiêu nghiên cứu và tính cấp thiết của đề tài
Ứng dụng quy hoạch tuyến tính để hỗ trợ các nhà lập kế hoạch và quản lý
kinh tế ra những quyết định chính xác và tốt nhất có thể, nó là một công cụ
đáng tin cậy để phân tích và dự đoán hướng phát triển có mục tiêu của các cơ
sở kinh tế nói chung và của các công ty và tổng công ty nói riêng.
 Phạm vi nghiên cứu và ứng dụng
- Nghiên cứu về quy hoạch tuyến tính đơn mục tiêu và đa mục tiêu – phương
pháp tối ưu kiểu pareto.
- Nghiên cứu một số phương pháp lập kế hoạch dựa trên các quy trình công
nghệ đã cho như: hàm sản xuất tuyến tính dạng X = AX, trong đó:
+ A là ma trận công nghệ.
+ X là phương án sản xuất
 Ý nghĩa khoa học
Trên cơ sở tối ưu pareto để tìm ra các phương án sản xuất cho tổng công ty
và các công ty con dựa trên phương pháp cạnh tranh và bù đắp.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 3 -
CHƢƠNG 1
TỔNG QUAN VỀ QUY HOẠCH TOÁN HỌC
1.1. Phát biểu bài toán Quy hoạch toán học tổng quát
Khi tiến hành lập kế hoạch sản xuất, điều khiển các hệ thống và thiết kế kỹ thuật
mà biết dựa trên các nguyên tắc cực trị sẽ tiết kiệm được vật tư, tiền vốn, tài
nguyên, sức lao động, thời gian và tăng được hiệu quả giải quyết các vấn đề đặt ra.
Những cơ sở lý thuyết và các phương pháp thực hành để giải quyết các vấn đề
nằm trong môn học Tối ưu hóa hay còn gọi là Quy hoạch toán học…
1.1.1. Bài toán Quy hoạch toán học tổng quát
Một bài toán Quy hoạch toán học tổng quát được phát biểu như sau:
Cực đại hóa (cực tiểu hóa) hàm:
f(x) → max (min)
(1.1)
Với các điều kiện:
}),,{(,1,)(  mibxg
ii

(1.2)
n
RXx 

(1.3)
Bài toán (1.1)


*
xf
được gọi là giá
trị tối ưu 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 - 4 -
1.1.2. Phân loại các bài toán
Một trong những phương án hiển nhiên nhất để giải bài toán đặt ra là phương
pháp điểm diện: tính giá trị hàm mục tiêu trên tất cả các phương án, sau đó so
sánh các giá trị tính được để tìm ra giá trị tối ưu và phương pháp tối ưu của bài toán.
Tuy nhiên cách giải quyết này khó có thể thực hiện được, ngay cả khi kích thước
của bài toán (số biến n và số ràng buộc m) là không lớn, bởi vì tập D thông thường
gồm một số rất lớn các phần tử, trong nhiều trường hợp còn không đếm được.
Vì vậy cần phải có những nghiên cứu về mặt lý thuyết để có thể tách ra từ bài
toán tổng quát những bài toán “dễ giải”. Các nghiên cứu lý thuyết đó thường là:
- Nghiên cứu các tính chất của các thành phần bài toán (hàm mục tiêu, các
ràng buộc, các biến số, các hệ số…);
- Các điều kiện tồn tại lời giải chấp nhận được;
- Các điều kiện cần và đủ của cực trị;
- Tính chất của các đối tượng nghiên cứu.
Các tính chất của các thành phần của bài toán và đối tượng nghiên cứu giúp ta
phân loại các bài toán. Một số bài toán tối ưu (quy hoạch toán học) được gọi là:
- Quy hoạch tuyến tính (QHTT) nếu hàm mục tiêu và tất cả các hàm
ràng buộc là tuyến tính. Một trường hợp riêng quan trọng
của QHTT là bài toán vận tải (BTVT);
- Quy hoạch tham số (QHTS) nếu các hệ số trong biểu thức của hàm mục tiêu

)()(










njx
mibxa
j
n
j
ijij
,1,0
,1,
1

Ta gọi bài toán này là bài toán gốc. Dựa vào bài toán gốc (I), ta xây dựng
một bài toán quy hoạch tuyến tính khác gọi là bài toán đối ngẫu của bài toán (I) có
dạng sau:



m
i
ii

~
yf
→ Min và hệ ràng buộc của bài toán đối ngẫu có
dạng “≥”.

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 6 -
- Số ràng buộc (không kể ràng buộc dấu) trong bài toán này bằng số biến số
trong bài toán kia, từ đó thấy tương ứng với một ràng buộc của bài toán này
là một biến số của bài toán kia.
- Hệ số trong hàm mục tiêu của bài toán này là vế phải của hệ ràng buộc trong
bài toán kia.
- Ma trận điều kiện trong hai bài toán là chuyển vị của nhau.
- Các biến số trong bài toán đối ngẫu không có ràng buộc về dấu.
Khi phân tích quan hệ của hai bài toán đối ngẫu cần sử dụng một khái niệm quan
trọng:
Cặp ràng buộc đối ngẫu: Ta gọi 2 ràng buộc bất đẳng thức (kể cả ràng buộc dấu)
trong hai bài toán cùng tương ứng với một chỉ số là một cặp ràng buộc đối ngẫu.
Trong hai bài toán (I) và (I
’
) có n cặp ràng buộc đối ngẫu:



m
i
jiiji
njcyax

,1,0
,1,)(
1

Đưa bài toán về dạng chính tắc, ký hiệu là (II
~
):
)()(
1
MaxMinxcxf
n
j
jj














mnjx
mibxxa
j







miy
njcya
i
n
j
jiij
,1,0
,1,)(
1
.
Ký hiệu bài toán này là (II
’
). Do đặc điểm cấu trúc của hai bài toán, ta gọi (II) và
(II
’
) là cặp bài toán đối ngẫu đối xứng . Hai bài toán này có n + m cặp rằng buộc đối
ngẫu sau:






n

n
j
ijij
mibxa
1
,1,




n
j
ijij
mibxa
1
,1,)(




n
j
ijij
mibxa
1
,1,)(

j
x
không ràng buộc về dấu.


miy
i
,1,0 


m
i
jiij
njcya
1
,1,




m
i
jiij
njcya
1
,1,)(




m

yfxf 
thì x
*
và y
*
tương ứng là hai phương án tối ưu.
b. Các định lý
 Định lý 1: Nếu một trong hai bài toán đối ngẫu giải được thì bài toán kia
cũng giải được và khi đó với mọi cặp phương án tối ưu x
*
và y
*
ta luôn có
)()(
*
~
*
yfxf 
.
 Định lý 2: Điều kiện cần và đủ để hai phương án x và y của một cặp bài toán
đối ngẫu tối ưu là trong các ràng buộc đối ngẫu nếu một ràng buộc thoả mãn
với dấu bất đẳng thức thực sự (lỏng) thì ràng buộc kia phải thoả mãn với dấu
bằng (chặt).
Ví dụ: Quy hoạch đối ngẫu của bài toán là quy hoạch: 1.3. Giới thiệu một số phƣơng pháp giải điển hình của quy hoạch toán học

- Phương pháp nhượng bộ dần
- Phương pháp thoả hiệp TAMM
- Phương pháp Người – Máy (của Geoffrion, Dyer, Fienberg)
- Phương pháp từng bước Benayoun
- Thuật toán thích nghi ổn định tối ưu hoá vectơ
- Phương pháp giải theo dãy mục tiêu đã được xắp xếp
- Phương pháp ràng buộc

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 10 -
- Phương pháp trọng số
- Phương pháp so sánh, sắp xếp phương án bài toán quy hoạch đa mục tiêu
- Phương pháp đồ thị
1.3.1. Mô hình và một số phƣơng pháp giải bài toán quy hoạch đa mục tiêu
a. Mô hình bài toán quy hoạch đa mục tiêu
max(min))( XY
(1.5)
n
RDX 
(1.6)
k
k
RXYXYXY  ))(), ,(()(
1
(1.7)
gọi là vectơ mục tiêu
X gọi là phương án. D là tập các phương án.
Y

nhận lời giải. Hàm U có thể cho dưới dạng tường minh hoặc dạng ẩn (tức là biểu
hiện rằng: các phương án có thể so sánh được với nhau theo một nghĩa “hơn”
“kém” “không phân biệt” nào đó).
ki ,1

ki ,1Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 11 -
Bài toán quy hoạch đa mục tiêu kết hợp với lợi ích của người nhận lời giải
trong trường hợp hàm U tường minh có thể viết:

DX
XYMaxU

))((

b. Một số phƣơng pháp giải bài toán quy hoạch đa mục tiêu.
 Phƣơng pháp nhƣợng bộ dần
Phương pháp này dẫn đến việc tìm một lời giải thoả hiệp tốt nhất tức là tìm
nghiệm X
*
mà theo ý thích của người nhận lời giải thì
XXDX 
*
:
hoặc

1
)

Y
k
(X
1
)
X
2Y
2
0 …

X
k

Y
k

0
và Y
2
*
bắt Y
2
phải nhượng bộ một
lượng Y
2
và giải bài toán:
(1.10)
(1.11)

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 12 -

2
0
22
1
0
11
3
)(
)(
)(max
YYXY
YYXY

1
0
11
)(

)(
)(
)(max





kkk
k
YYXY
YYXY
YYXY
DX
XY

Nghiệm của bài toán cuối cùng này lấy làm nghiệm cho bài toán xuất phát.
 Phƣơng pháp thoả hiệp của TAMM
Giải bài toán

DX
XY

)(max


Bước 2: Giải bài toán: min W (1.15)
(1.12)
(1.13)

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 13 -
),1(
)(
kiW
M
XYM
i
ii


(1.16)
DX 
(1.17)
Từ đó tìm được nghiệm tối ưu

WvàX

Ở đây hàm “lợi ích” U tỷ lệ với độ lệch tương đối chung. Còn
21
XX 
nếu độ lệch
tương đối chung của X
1

I
là giá trị max Y
I
(X)
X  D
Ta viết

'
d
là metric đã thay đổi.
D
i
là miền chấp nhận được. Khi i = 0 thì D
0
 D.
Thuật toán giải như sau:
Bước 1: Xây dựng bảng “thưởng phạt” xác định M
I
và m
I
(giá trị max và min
của Y
I
(X)) ở cột I.
Bước 2: Tìm các trọng số
Xác định 
I
để tính 
I
:

j
là các hệ số của hàm mục tiêu thứ I. Đặt i = bước sang bước 3.
Bước 3: Tính 
I
:



I
I
I



(1.21)
và giải bài toán i.
Bước 4: Giả sử nghiệm của bài toán I là X(i). Đưa cho người nhận lời giải
nghiệm X(i). Người nhận lời giải phân tích kết quả và xảy ra:
1) Nếu người nhận lời giải (NNLG) chấp nhận X(i) thì thuật toán kết thúc.
2) Nếu NNLG không chấp nhận X(i) và nếu chỉ số i < k-1 thì sang bước 5.
3) Nếu NNLG không thoả mãn X(i) và i = k – 1 thì chọn cách giải khác.
Bước 5 : NNLG phân tích kết quả và tìm ra mục tiêu I
*
có thể nhượng bộ.
NNLG cho một nhượng bộ I
*
và sang bước 6.
Bước 6 : Xác nhận miền chấp nhận mới D
(i+1)


Bài toán quy hoạch đa mục tiêu được hiểu như là bài toán tối ưu hoá vectơ:

)(), ,(
1
XYXY
RDX
k
n


Các Y
1
(X) biểu hiện độ tốt xấu của X theo nghĩa nào đó.

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 15 -
Ta xét bài toán max.
Giả thiết
DX 
0
là vectơ tối ưu đối với người nhận lời giải. Yêu cầu người
nhận lời giải ước lượng giá trị mà mình thích nhất: Y
0
v
, (
kv ,1
) với điều kiện:


v
,1)())((
00



 bài toán
DX
XYE
vv

 min)}({{
02


hay 



k
v
v
v
v
XYYE
1
20
min}))({(



, i  I. Trong đó V
i

tập hợp các giá trị có thể có của tham số X
i
.

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 16 -
Định nghĩa 1.3.1: Nếu (pr
ij
S)  (v
i
x v
j
) và (pr
ji
S)  (v
j
x v
i
) không phải là ánh
xạ thì X
i
và X
j
gọi là độc lập, nếu ngược lại thì X
j

i
và X
j
có tồn tại hay không. Do đó sẽ thích hợp hơn nếu ta định
nghĩa:

ijG
v


Trong đó v
ij
 L là mức độ phụ thuộc giữa X
i
và X
j
, còn L là vành với ánh xạ
tự đẳng cấu N và có phần tử lớn nhất I
L
và phần tử nhỏ nhất là O
L
. Khi đó
),( ji
G

=
v
ij
xác định một quan hệ mờ G  I x I. Từ quan điểm đại số này quan hệ này biểu thị
một hệ trừu tượng phản ánh một hệ thống S.


X
i
 X  (Y
i1
, Y
i2
, … ,Y
ik
) với
ni ,1

Dựa trên việc so sánh hàm lợi ích tìm cách phân lớp sắp xếp các phương án đó
với qui ước:
- Hai phương án tốt ngang nhau sẽ được xếp cùng một chỉ số thứ tự
- Hai phương án, phương án nào trội hơn sẽ được ghi ở chỉ số thứ tự nhỏ hơn.
nếu X
i
phụ thuộc vào X
j
nếu

ngược lạiSố hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 17 -
Các phương án này xem như các tham số cho trước và chúng có mối liên hệ với


Các tham số trong cùng một lớp là tương đương nhau và giữa các lớp có một
quan hệ thứ tự:

jijjiiji
XXXXXXXX  :, 

hay
jijjii
XXXXXX :, 


}~:|{)( YXXXXYXX
ijjji


Vậy vấn đề cần xác định R
i
từ quan hệ mờ G. Sau đây ta xác định R
i
và chỉ ra
một cách cho ước lượng d.
- Xác định quan hệ R
i

Với mỗi tham số X
i
đều tồn tại tập J
i
với hàm liên thuộc:

i
)
j
= G(j, i)
nếu i  S(J
k
)
nếu ngược lại

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 18 -
Bổ đề 1.3.3: nếu quan hệ G là bắc cầu và thoả mãn: G(i, j) = G(k, j) lúc đó
S(J
k
) = S(J
i
). Tương tự như vậy mỗi tham số X
i
được thay bằng tập mờ T
i
= I
i
 J
i

trong đó S(T
i
)  I.

=T
i
x T
i
là quan hệ phản xạ và cho (P
i
”
)(m,m) = I
L
và (P
i
”
)(m,n) = 0
L
với
m khác n.
Định nghĩa 1.3.6
P
i
= P
i
’
 P
i
”

là quan hệ phản xạ và bắc cầu
R
i
= G  P


Định nghĩa 1.3.7
E
i
= P
i
’
 P
i
”

Bổ đề 1.3.7
Ta luôn có:
a) (E
i
)(i, i) = I
L

b) (E
i
)(m, n) = 0
L
với m  n

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 19 -
c) (E
i

’
 R
i
”

Bổ đề 1.3.8
a) R
i
”
= P
i
”

b) F
i

= E
i

c) R
i
= R
i
’
 P
i
”

- Một cách cho ƣớc lƣợng không âm (d)
Xét đẳng cấu : L → [0, 1]

) = d(P
i
’
) + d(P
i
”
) – d(E
i
)
c) Nếu L = [0, 1] thì

tự đẳng cấu, số d(A) =

Ux
Ax
trong trường hợp này
có nghĩa là mật độ tổng quát của tập mờ A.
1.3.2. Bài toán quy hoạch phi tuyến và một số phƣơng pháp giải
a. Phát biểu bài toán
Bài toán quy hoạch phi tuyến tổng quát có thể diễn tả dưới dạng:

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên - 20 -






.
Nếu hàm f(x), {g
i
(x)} và {h
j
(x)} là những hàm lồi thì ta có quy hoạch lồi, là
một trường hợp riêng quan trọng của quy hoạch phi tuyến. Nếu hàm f(x) là một
dạng toàn phương, còn các ràng buộc là tuyến tính thì ta có quy hoạch toàn phương
lại là một trường hợp riêng của quy hoạch lồi.
Nhiều khi người ta biến đổi bài toán có ràng buộc về bài toán không có ràng buộc
bằng cách dùng một hàm bổ trợ. Hàm bổ trợ này biểu diễn qua các hàm số của bài
toán và bản thân nó trở thành hàm mục tiêu có các cực tiểu không điều kiện trong
một miền nào đấy. Người ta thay đổi dần thông số, và chính bằng cách đó làm tăng
ảnh hưởng của các ràng buộc lên hàm bổ trợ và như vậy, người ta xây dựng được
một dãy bài toán không có ràng buộc mà nghiệm của chúng hội tụ đến nghiệm của
bài toán xuất phát. Để đơn giản ta nêu ra tư tưởng cơ bản một cách hình thức. Xét
bài toán:
(1.28) m1,i 0 )(g
(1.27) R xf(x);min
i
n


x

Hàm bổ trợ điển hình không có ràng buộc có thể viết dưới dạng:



