CHƯƠNG 8 : HOẠCH ĐỊNH BẰNG CHƯƠNG TRÌNH TUYẾN TÍNH

8.1 MỞ ĐẦU :
Chúng ta đã nhận thấy rằng là PIC hay PDP là sự dung hòa giữa những
mong muốn và ràng buộc của dịch vụ thương mại và thuc tê cua cac bô phan san
xuat va thu mua. Thông thuong một kế hoạch thỏa mãn tất cà các bên có thể đạt
được sau một quá trình được lặp lại nhiều lần. Và ở giai đọan hoạch định , chúng
ta không tim cách để co duoc kỳ hạn chac chan cho phép bắt đầu quá trình sản
xuất mà là nhung ky han co tinh thuc tê, dua trên nhung du liêu chung ta co duoc
Những dữ liệu này là những dữ liệu mang tính liên kết và tính trung bình (nang
suất hay thời gian họat động trung bình của một cái máy nào đó chẳng hạn ) . Điều
này dân dên :
1 . Nhu cầu tỉ lệ với số lượng sản phẩm, diêu này, do thời gian thay đổi
thiết bị, thời gian cân dê dat duoc su đều đặn…, không còn đúng nữa ở mức độ
khai thác .
2 . Trên một chu kỳ sơ cấp tham khảo , thời gian vận hành các dòng trong
chu kỳ công nghiệp từ trạm đến trạm không duoc tinh dên.
Trong điều kiện đó , mô hình toán học , đặc biệt là chương trình tuyến tính ,
cho phép đẩy nhanh quá trình ra quyết định .Mục đích là tìm ra kế hoạch sản xuất
trong thoi gian hoach dinh, đặc biệt là cac sản phẩm dang thuc hiên và cac thành
phẩm duoc dự trữ.
Vì những lý do mang tính sư phạm , đầu tiên chúng tôi sẽ giới thiệu quá
trình xây dựng một kế hoạch trong một thời kỳ . Sau đó sẽ mở rộng mô hình ra
thành phạm vi nhiều thời kỳ .
8.2. MÔ HÌNH TRONG MỘT THỜI KỲ :
8.2.1. VÍ DỤ GIỚI THIỆU :
Nhà máy Lavarn sản xuất máy giặt thương mại với khoang 50 nhãn hiệu
khác nhau. Để hoạch định một kế hoạch trung hạn , việc sản xuất được phân thành
3 nhóm , tương ứng với 3 chât luong.
- hang kinh tế
- hang trung bình

Phụ trách tài chính :
Chi phi tiêu thụ trung bình được du doan tương ứng là 260F , 300F và 350F

Mô hình hóa :
1. Biến quyết định
Từ các cuộc họp , chúng ta phải biết số lượng cua cac mat hàng cân sản xuất . Từ
đó , chúng ta goi là các giá trị E , M , H .
2
2. Mục tiêu :
Chúng ta muốn tối đa hóa loi nhuân trên chi phí trực tiếp , co nghia là tối đa hiêu
sô cua giá bán và chi phí sản xuất trực tiếp . Ở đây , những người công nhân lanh
lương tháng , chi phí của công nhân sẽ cố định và do đó chi tính vào vat liêu tiêu
thụ . Nói cách khác , điều này dẫn đến tối đa hóa giá trị gia tang.
3. Ràng buộc
Chúng ta có 6 ràng buộc sau đây :
C1. Ở xưởng tôn, mỗi máy phải có 1 bô phân hình ống và chúng ta không thể sản
xuất trên 500 bô phân này trong 1 tháng .
C2. Ở xưởng lắp ráp , yeu câu vê nhân luc (tính trên 1/10h) là bằng (8E + 10M +
12H) , voi khả năng là 6000 (600h)
C3. mỗi máy chât luong trung bình và cao phải có một bô phân lập trình. Gioi han
dự trữ cua bô phân này là 300
C4. Ở xưởng đóng gói , nhu cầu là (2E + 3M + 4H), voi khà năng là 1500 .
C5 và C6. Tôn trọng cac hợp đồng đa ký : phải sản xuất ít nhât 200 máy loai tiết
kiệm và 100 máy cao câp .

3. Mô hình phân tích tương ứng là một chương trình tuyến tính :
Tối đa hóa : (700-260)E + (3000-300)M + (1250-350)H
Với những ràng buộc :
C1. E + M + H ≤ 500
C2. 8E + 30M + 12H ≤ 6000


Hon nua phuong phap toan tu cho ta giá trị của các biến miêu tả độ chênh
lệch và số dôi (thang du). Điều đó cho phép ta biết được sô vât liêu còn lại và giá
lề của chúng.

Ràng buộc Loại Độ lệch/Số dôi Đối ngẫu
C1 ≤ 0,00 100,00
C2 ≤ 1000,00 0,00
C3 ≤ 0,00 0,00
C4 ≤ 0,00 200,00
C5 ≥ 100,00 0,00
C6 ≥ 0,00 -60,00

4
8.2.2 MÔ HÌNH HÓA TRƯỜNG HỢP TỔNG QUÁT :
Ta xét một xí nghiệp chế tạo n sản phẩm i (i=1,…n) ,yêu cầu nằm
trong khoảng [ ] .Lợi tức đem lại trên một đơn vị sản phẩm i là

i
d
ii
dd max,min
i
g
Xí nghiệp sử dụng m tài nguyên k (k=1 m) với số lượng giới hạn là
.Những tài nguyên trên có thể là nhân công (voi luong cố định ), có thể là
những vât liêu cung ứng, và cũng có thể là kha nang các trang thiết bị.Sản
phẩm i cần don vi tài nguyên k.
k
b

=

ii
Xd ≤min
( i=1 n ) co nhâm không, le ra dmax phai lon hon X
ii
Xd ≤max
8.3 QUAN TÂM ĐẾN CÁC NGUỒN TAI NGHUYEN BỔ SUNG :
8.3.1 VÍ DỤ MỞ ĐẦU :
Theo những kết quả đầu tiên ,nguồn vốn ban đầu dự kiến là chưa đủ
.Mọi bô phân hình ống và lập trình đã được sử dụng hêt ,nhân công dong goi
làm việc hết sức mình .Cân tiến hành họp bàn lại , điều này giúp thu nhận các
lời đề nghị mới.
Có thể làm việc thêm giờ, trong giới hạn 10% của giờ bình thường .Giờ
bình thường là 100F ở khâu lắp ráp và 120F ở khâu dong goi.Tăng giá cho
một giờ làm thêm là 30F cho xưởng lắp ráp và 40F cho xưởng đóng gói .
Phòng thu mua đã liên hệ 1 công ty gia công, ho có thể sản xuất tối đa
100 bô phân hình ống. Dĩ nhiên giá các bô phân này đắt hơn giá sản suất
trong xưởng , ước tính đến 20F trên mỗi bô phân hình ống.
Cung co nguồn thứ hai cung cấp bô phân lập trình. Một nhà cung cấp viến
đông đã được liên lạc.Họ yêu cầu đơn hàng tốI thiểu là 100 bô phân lập trình
và có thể giao đến 150 bô phân .Những bô phân lập trình này có đơn giá cao
hơn 5F nếu giao ngay và hơn nữa phí vận chuyển cố định là 1000F
5
Mô hình hoá :
Sử dụng các dữ liệu mới ,chúng ta có được mẫu sau đây:
1. Các biến :
- cung voi các biến liên quan dên cac loai san phâm cân san xuâtg
sản xuất :E,M,H.
-Cân xac dinh số giờ làm thêm bởi cac phân xưởng .Các biến này

-1000 CC –5 PCC

6
Với các ràng buộc :
C1 E+M+H ≤ 500+TST
C2 8E+10M+12H ≤ 600+HsupM
C3 M+H ≤ 300+PCC
C4 2E+3M+4H ≤ 1500+HsupC
C5 H ≥ 100
C6 E ≥ 300
C7 HsupM ≤ 600
C8 HsupC ≤ 150
C9 TST ≤ 100
C10 PCC ≤ 150CC
C11 PCC ≥ 100CC
C12 CC
)1,0(
∈Giải ví dụ trên :
Sau khi giải ta được bảng kết quả ở bên dưới. Hàm mục tiêu có giá trị tối
ưu là 370 766,67 F. So sanh với bảng đầu tiên ,ta có lợi tức tăng thêm :
370 776 F-338 000 F=32 766 F
Biến Giá trị Gia giảm
E 200,00 0,00
M 283,33 0,00
H 100,00 0,00
HSupM 0,00 -3,00
HSupC 150,00 0,00

(k=1,…,m). Một sản phẩm i cân a
i,k
đơn vị tài nguyên k. Tài nguyên k có thể co
được từ những nguồn khác nhau
S
k
l
. Giá (hay gia phu trôi) của một đơn vị là
. Chúng ta có thể chia cac tài nguyên thành 2 nhóm.
S
k
l
c
k
l
1. Các nguồn thuôc nhóm đầu tiên co số lượng gioi hạn
b
.
S
k
l
k
l
2. Đối với nhóm thứ hai, có một số lượng tối thiểu bắt buộc
a
và/hay
có một giá cố định phải trả nếu chúng ta quyết định sử dụng nguồn này.
k
l
k


∑∑∑∑
===
−−
m
k
k
l
k
l
m
kl
k
l
k
l
n
i
ii
ZfYcXgMax
111Chúng ta có các điều kiện sau:
∑∑
≤
= l
k
l
n


Z
k
l
∈ 0,1

8.4 XET DEN SU DA NANG:
Tro lai mô hinh dâu tiên, qua các kết qủa, nhân công trong khâu dong goi
phai làm viêc tôi da, cong nhân khâu lap rap lai còn 100h không dùng đến. Chúng
ta muôn di chuyên cac công nhân không viêc này qua khâu đóng gói. Quyết định
là hình thành một chuong trinh dào tao cho 1 sô công nhân dê làm tang tinh linh
hoat cua công ty. Sau chuong trinh dào tao này, công nhân se co nhiêu kha nang
hon, và tuy tinh hinh cua công ty, co thê làm viêc trong xưởng này hoặc xưởng no.
Vi du cân sử dụng 500 H o khâu lap rap, 100 H khâu dong goi và 150 H cho công
nhân da nang.

Mô hình:

1. Các biến E,M và H không thay đổi. Thêm vào đó, cân quyết định số giờ do cac
công nhân da nang dam nhiêm (gio da tri) trong tùng phân xưởng. Chúng duoc goi
là HpolyM và HpolyC ( don vi 1/10h)
2. Muc tiêu không đổi.
3. Thông số ràng buộc mới thể hiện số giờ da tri là không quá 150.

Chương trình tuyến tính : Chương trình tuyến tính tương ứng là
Tôi da hoa:
440 E + 700 M + 900 H
Với các ràng buộc sau:
C1 : E + M + H ≤ 500
C2 : 8E + 10M + 12H ≤ 5000 + HpolyM


8.5.1 VÍ DỤ MỞ ĐẦU :

O công ty Lavam, cuộc họp hàng tháng có mục đích thiết lập PIC đối với 3 tháng
tới. Ở đây, chúng ta chi tính đến các ràng buôc nhỏ trong ví dụ đầu tiên. Nhưng
chúng ta co thêm những du liêu cho 3 tháng tới.

Phụ trách thương mại Dua trên các don hàng đã biêt trước và các dự kiến. Có thể
lâp du doan cac don hang sap toi. Bảng sau cho các muc bán tối thiểu, trung bình
và cực đại cua một ho san phâm.

Kinh tế Trung bình Cao
Tháng 1
Tháng 2
Tháng 3
80/100/120
90/105/120
100/120/140
90/110/130
120/140/160
100/120/140
120/130/140
100/105/110
130/150/170

Phụ trách nhân sự Tùy vào sô ngày làm việc và sô công nhân, nhân luc cho 3
tháng toi là: lap rap: 500h , 450h và 550h , khâu đóng gói : 100h ,90h và 120h.

Phụ trách sản xuất Cân tinh dên cac khoang ngung hoat dông dê bao tri, và viêc
sản xuất tôi da bô phân hinh trống tuong ung là: 500, 380 và 400 đối với 3 tháng.

Tháng 0 biểu diễn các dự trữ bắt đầu và tháng 3 là các dự trữ con lai ở cuối giai
doan.

2. Muc tiêu
Chúng ta muốn tôi da hiêu sô giữa doanh sô bán và chi phi trực tiếp của việc
chế tạo và sự dự trữ.
Ta duoc hàm muc tiêu sau dây theo chương trình tuyến tính (bài tóan quy
họach tuyến tính):
Tôi da hoa
440 (E1+E2+E3)+700(M1+M2+M3)
+900(H1+H2+H3)
-30(StE0+StE1+StE3)
-45(StM0+StM1+StM2+StM3)
-60(StH0+ StH1+ StH2+ StH3)
-(StTamb0+ StTamb1+StTamb2+StTamb3)
-5(StProg0+ StProg1+ StProg2+ StProg3)

3. Các ràng buộc
Chúng ta lại co, cho mỗi tháng, các ràng buộc ở ví dụ ban đầu.
C2 và C4: ràng buôc không dôi
C1: dôi voi bô phân lâp trinh, ngoài 400 cai nhân duoc môi thang, con thêm
vào tôn kho cua thang truoc do. Sau khi san xuât, nhung cai con lai se duoc
tinh là tôn kho cho thang tiêp theo. Chung ta co:

Tháng 1: M1+H1+SProg1 = 400 + SProg0
Tháng 2: M2+H2+SProg2 = 400 + SProg1
Tháng 1: M3+H3+SProg3 = 400 + SProg2
11
C3: Đối với việc sản xuất bô phân hinh trông (tambour), có khả năng sản
xuất tối đa 500 cái vào tháng 1. Giả sử rằng 1 tháng cần sản xuất 460 máy. Vi ràng

i,j
trong thời kỳ j. Một sản phẩm i đòi hỏi a
i,k
đơn vị của nguồn tài nguyên k.
Nguồn tài nguyên này xếp thành 3 loại.

Thường kỳ:
StE0 = 30
StM0 = 50
StH0 = 10
StTamb0 = 60
StProgr0 = 50

DmdeE1 = 100
DmdeE2 = 105
DmdeE3 = 120

DmdeM1 = 110
12
DmdeM2 = 140
DmdeM3 = 120

DmdeH1 = 130
DmdeH2 = 105
DmdeH3 = 150

Tháng 1 :
8 E1 + 10 M1 + 12 H1 ≤ 5000
2 E1 + 3 M1 + 4 H1 ≤ 1000
E1 + M1 + H1 + StTamb1 ≤ 500 + StTamb0

13
Chi phi dự trữ của 1 đơn vị trong 1 thời kỳ của nguồn tài nguyên k (k ∈ R2
∪ R3) là r
k
và của 1 thành phẩm i là s
i
.

Các biến quyết định là:
– số lượng X
i,j
của sản phẩm i vào thời điểm j
– lượng dự trữ dư SR
k,j
của nguồn tài nguyên k vào cuối thời kỳ j, với (k ∈
R2 ∪ R3)
– lượng dự trữ S
i,j
của 1 thành phẩm i vào cuối thời kỳ j.

Mục tiêu là tối đa hóa lợi nhuận, là hiêu giua doanh sô và chi phi dự trữ:

∑∑∑∑∑∑
∪∈=====
−−
3R2Rk
p
1j
j,kk
n

+=+
∈+=+
∈+≤+
∈≤
−
−
=
−
=
=
∑
∑
∑

Mô hinh này dùng để kiểm tra tính khả thi của một kế hoạch sản xuất dôi
voi một nhu cầu đã biết. Chương trình sẽ đưa ra giải pháp khả thi tối ưu hóa nếu
nó tồn tại, hoặc cho phép chứng minh là các ràng buộc quá chặt che.
Khi đưa ra một mức bán hàng dự kiến X
i,j
trong thời đoạn j, ví dụ trong
khoang [dmin
i,j
, dmax
i,j
], người ta thử nghiệm các dự kiến:
mức chọn lựa thấp: d
i,j
= dmin
i,j


i,j
≤ S
i,j–1
+ X
i,j
, ta có lượng dự trữ dư S
i,j
= (S
i,j–1
+ X
i,j
) – d
i,j
.
Nếu không thì thiếu một lượng P
i,j
= d
i,j
– (S
i,j–1
+ X
i,j
).

Biểu diễn dạng này, mô hình se không con tuyến tính. Thât ra S
i,j
và P
i,j
chỉ
là 2 dạng của một biến chung ký hiệu Y

p
1j
j,kk
n
1i
p
1j
j,ii
n
1i
p
1j
j,ii
P.cpSR.srS.sX.gMax

với các ràng buộc:
()
j,ij,ij,ij,i1j,i
1j,kj,k
n
1i
j,kj,ik,i
1j,kj,k
n
1i
j,kj,ik,i
j,k
n
1i
j,ik,i

i,j
+ P
i,j–1
) = S
i,j
– P
i,jTrong trường hợp tổng quát, ta có α% việc buôn bán duoc hoãn lại và phần
còn lại bị mất. Nhu cầu sẽ tăng αP
i,j–1
. Với cd
i
và cp
i
là giá của một đơn vị hoãn và
mất đi, ta có :
∑∑∑∑
∑∑∑∑∑∑
====
∪∈=====
α−−α−
−−
n
1i
p
1j
j,ii
n

n
1i
j,kj,ik,i
j,k
n
1i
j,ik,i
PSPdXS
)3Rk(SRbSRX.a
)2Rk(SRbSRX.a
)1Rk(bX.a
−=α+−+
∈+=+
∈+≤+
∈≤
−−
−
=
−
=
=
∑
∑
∑ 16