Sự cạnh tranh trong hoạt động sản xuất kinh
doanh luôn đòi hỏi các nhà quản lý doanh
nghiệp phải thường xuyên lựa chọn phương án
để đưa ra các quyết định nhanh chóng, chính
xác và kịp thời với những ràng buộc và hạn chế
về các điều kiện liên quan tới tiềm năng của
doanh nghiệp, điều kiện thị trường, hoàn cảnh
tự nhiên và xã hội
33 trang |
Chia sẻ: Mr Hưng | Lượt xem: 1744 | Lượt tải: 1
Bạn đang xem trước 20 trang nội dung tài liệu Kinh tế học - Chương 7: Bài toán tối ưu tuyến tính, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1Chương 7
BÀI TOÁN
TỐI ƯU
TUYẾN
TÍNH
Sự cạnh tranh trong hoạt động sản xuất kinh
doanh luôn đòi hỏi các nhà quản lý doanh
nghiệp phải thường xuyên lựa chọn phương án
để đưa ra các quyết định nhanh chóng, chính
xác và kịp thời với những ràng buộc và hạn chế
về các điều kiện liên quan tới tiềm năng của
doanh nghiệp, điều kiện thị trường, hoàn cảnh
tự nhiên và xã hội Việc lựa chọn phương án
nào là tối ưu theo mục tiêu định trước là hết sức
quan trọng. Nếu tất cả các yếu tố (biến số) liên
quan đến khả năng, mục đích và quyết định lựa
chọn đều có mối quan hệ tuyến tính thì ta có thể
sử dụng mô hình tối ưu tuyến tính hay quy
hoạch tuyến tính (QHTT) để mô tả, phân tích và
tìm lời giải tối ưu của vấn đề đặt ra.
2Trong môn học Toán kinh tế việc giải bài toán QHTT
thường được thực hiện bằng thuật toán đơn hình.
Trong phần mềm Excel bài toán QHTT được giải
nhanh chóng qua công cụ cài thêm là Solver.
5.1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QHTTT
1. Bài toán lập kế hoạch sản xuất:
Một xí nghiệp dự định sản xuất hai loại sản phẩm là S1
và S2 từ vật liệu V1 và V2. Số liệu được cho ở bảng
sau:
Hỏi xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm
S1 và S2 để tổng thu nhập là lớn nhất?`
3Mô hình toán học. Gọi x1, x2 lần lượt là số đơn vị sản
phẩm S1, S2 cần sản xuất.
Tổng thu nhập của xí nghiệp (cần làm cực đại) sẽ là
f = 50000*X1 + 30000*X2.
Vậy bài toán đặt ra được phát biểu thành: Tìm các biến
số x1 và x2 sao cho
f = 50000 * X1 + 30000 * X2 max,
với các điều kiện
4x1 + 3x2 1.200,
5x1 + 2x2 1.080, (1.1)
x1 0, x2 0.
42. Bài toán xác định khẩu phần thức ăn
Khẩu phần thức ăn/ 1 bửa ăn của một xí nghiệp chăn
nuôi như sau:
Hỏi xí nghiệp cần mua bao nhiêu kg T1, T2 cho mỗi
bữa ăn, sao cho vừa đảm bảo tốt dinh dưỡng cho bữa
ăn của gia súc, vừa để tổng số tiền chi mua thức ăn là
nhỏ nhất?
5Mô hình toán học. Gọi x1, x2 lần lượt là số kg thức
ăn T1, T2 cần mua cho mỗi bữa ăn.
Số tiền chi mua thức ăn (cần làm cực tiểu) bằng
f = 20x1 + 15x2 (ngàn đồng).
Vậy bài toán nêu trên được phát biểu thành: Tìm các
biến số x1 và x2 sao cho:
f = 20x1 + 15x2 min,
với các điều kiện
3x1+ x2 60,
x1 + x2 40, (1.2)
x1 + 2x2 60,
x1 0, x2 0.
63. Bài toán vận tải
Cần vận chuyển xi măng từ 3 kho K1, K2, K3 tới 4
công trường xây dựng T1, T2, T3, T4. Số liệu cho ở
bảng sau:
Vấn đề là tìm kế hoạch vận chuyển xi măng từ các
kho tới các công trường sao cho mọi kho phát hết
lượng xi măng có, mọi công trường nhận đủ lượng xi
măng cần và tổng chi phí vận chuyển là nhỏ nhất?
7Mô hình toán học. Gọi xij là lượng xi măng cần vận
chuyển từ kho Ki (i = 1, 2, 3) tới công trường Tj
(j = 1, 2, 3, 4).
Ham muc tieu : Tổng chi phí vận chuyển be nhat:
f = 20x11 + 18x12 + 22x13 + 25x14 + 15x21 + 25x22 +
30x23 + 15x24 + 45x31 + 30x32 + 40x33 + 35x34=>
min
Vậy bài toán nêu trên được phát biểu thành:
8Tìm các biến số xij sao cho:
f min,
với các điều kiện
x11 + x12 + x13 + x14 = 170,
x21 + x22 + x23 + x24 = 200,
x31 + x32 + x33 + x34 = 180,
x11 + x21 + x31 = 130, (1.3)
x12 + x22 + x32 = 160,
x13 + x23 + x33 = 120,
x14 + x24 + x34 = 140,
xij 0, i = 1, 2, 3; j = 1, 2, 3, 4.
95.2. CÁC DẠNG BÀI TOÁN QHTTT
Qui hoạch tuyến tính là bài toán tìm cực tiểu (hay cực
đại) của một hàm tuyến tính thỏa mãn các phương trình
và/hoặc bất phương trình tuyến tính.
1. Bài toán tổng quát
Bài toán này có dạng: Tìm các biến số x1, x2,..., xn sao
cho:
Thỏa mãn các điều kiện:
1
( ) min ( max) (1.4)
n
j j
j
f x c x hay
n
ij j i
j=1
j 1
a x = b , i=1,2,...,m, (1.5)
x 0, j=1,2,...,n n. (1.6)
10
f gọi là hàm mục tiêu,
(1.5) là các ràng buộc chính (các PT và/hoặc bpt
tuyến tính).
(1.6) là các ràng buộc về biến (có thể không âm,
không dương hay tùy ý).
Điểm x = (x1, x2, ..., xn) R
n thỏa mãn (1.5), (1.6)
gọi là phương án của bài toán. Tập hợp tất cả các
phương án, ký hiệu là D, gọi là miền ràng buộc
hay miền chấp nhận được.
Một phương án thoả mãn (1.4) gọi là một phương
án tối ưu hay lời giải của bài toán đã cho.
11
2. Bài toán dạng chính tắc
(ràng buộc chính chỉ là các đẳng thức và mọi biến
đều không âm).
Ví dụ: mô hình bài toán vận tải nêu ở (1.1) có dạng
chính tắc.
12
3. Bài toa ́n dạng chuâ ̉n tắc
(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).
Ví dụ: mô hình bài toán xác định khẩu phần thức
ăn hay mô hình bài toán lập kế hoạch sản xuất đã
xét ở (1.1) có dạng chuẩn tắc.
13
Giải quy hoạch tuyến tính trên EXCEL
Để giải các bài toán QHTT, phần mềm Excel cung cấp
cho ta một công cụ khá hữu ích là Solver trong Menu
Tools của Excel. Các bài toán QHTT dạng chính tắc và
dạng chuẩn chỉ là trường hợp riêng của bài toán QHTT
dạng tổng quát. Vì thế ở đây ta sẽ xem xét cách giải
quyết bài toán QHTT dạng tổng quát.
Ví dụ: Xét bài toán QHTT sau:
f (x) = x1 + 4x2 + x3 min
Các ràng buộc:
-5x1 + x2 - 2x3 -12
x1 + 2x2 - x3 2
-x1 + 4x2 - 2x3 1
2x1 + 3x2 + 4x3 ≥ 20
x1, x2, x3 ≥ 0.
14
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) có thể không chấp
nhận được.
Bước 2:
Tính giá trị hàm mục tiêu tại ô E3 bằng công thức:
E3 =SUMPRODUCT($B$2:$D$2;B3:D3)
Copy công thức từ ô E3 sang dãy các ô E4:E7 để
tính giá trị vế trái của 4 ràng buộc của bài toán.
15
Bước 3: Dùng lệnh Tools | Solver, xuất hiện hộp thoại
Solver Parameters:
Mục Set Target Cell: chọn ô đích (chứa giá trị hàm
mục tiêu), trong ví dụ chọn ô E3.
Mục Equal To: chọn Max nếu cực đại hàm mục tiêu;
chọn Min nếu cực tiểu hàm mục tiêu; chọn Value of
và nhập giá trị nếu muốn ô đích bằng 1 giá trị nhất
định, trong ví dụ chọn Min.
16
Mục By Changing Cells: chọn các ô chứa các biến
của bài toán, trong ví dụ chọn khối ô B3:D2. Nháy nút
Add để nhập tất cả các ràng buộc vào khung Subject
to the Contraints.
Sau khi nhập xong các ràng buộc , nháy nút options,
hiện hộp thoại Solver Options, đánh dấu kiểm vào
mục Assume Linear Model (khẳng định mô hình của
ta là tuyến tính.)
17
Bước 4: Trong hộp thoại Solver Parameters, nháy
vào nút Solver để bắt đầu giải bài toán. Giải xong bài
toán xuất hiện hộp thoại Solver Results.
Chọn mục Keep Solver Solution (giữ lại lời giải),
nháy OK, kết quả giải bài toán nằm ở các ô B2:D2.
Kết quả ta có phương án tối ưu là x* = (0,5; 0; 4,75),
và trị tối ưu là fmin = 5,25.
18
5.3. BÀI TOÁN VẬN TẢI
1. Nội dung bài toán: Giả sử cần vận chuyển một
loại hàng thuần nhất (vật tư, lương thực, ...) từ m địa
điểm cung cấp (điểm phát) A1, A2, ..., Am đến n địa
điểm tiêu thụ (điểm thu) B1, B2, ..., Bn. Biết rằng :
Số lượng hàng có ở Ai là ai (i = 1,..., m),
Số lượng hàng cần ở Bj là bj (j = 1,..., n),
Chi phí vận chuyển một đơn vị hàng từ Ai đến Bj là
cij (i = 1,...,m; j = 1,...,n).
Vấn đề đặt ra: Lập kế hoạch vận chuyển hàng từ các
điểm phát đến các địa điểm thu để tổng chi phí vận
chuyển bé nhất và thoả mãn nhu cầu thu phát.
19
Đây là một trong những bài toán điển hình và có
nhiều ứng dụng nhất của QHTT. Bài toán này không
có gì phức tạp nếu mạng lưới giao thông tương đối
đơn giản và số địa điểm cung cấp, tiêu thụ không
nhiều lắm.
Tuy nhiên với những mạng
lưới đường giao thông phức
tạp thì bằng kinh nghiệm và
trực giác khó có thể tìm ra
được phương án tối ưu. Khi
ấy, cần sử dụng các phương
pháp, dựa vào tính chất đặc
thù của bài toán để tìm
phương án tối ưu.
20
Mô hình toán học của bài toán:
Gọi xij là số lượng hàng cần vận chuyển từ Ai đến Bj.
Ta có:
1 1
: Toång chi phí vaän chuyeån,
m n
ij ij
i j
c x
1
i
: Soá löôïng haøng chôû ñi töø A ,
n
ij
j
x
1
j
: Soá löôïng haøng chôû tôùi B ,
m
ij
i
x
Mô hình toán học của bài toán là:
21
1 1
1 2
1 2
0 1 2 1 2
n
ij
j=1
m
ij
i=1
ij
( ) min (cöïc tieåu toång chi phí vaän chuyeån)
x , , ,..., ,
x , , ,..., ,
, , ,..., ; , ,..., .
m n
ij ij
i j
i
j
f x c x
a i m
b j n
x i m j n
Bài toán vận tải là một dạng đặc biệt của qui hoạch
tuyến tính, do đó có thể sử dụng PP đơn hình để giải.
Tuy nhiên do bài toán có cấu trúc đặc biệt nên người
ta đã đề ra nhiều phương pháp giải khác có hiệu quả
hơn.
22
Giải Bài toán vận tải trên EXCEL
Ví dụ: Cần vận chuyển gạo từ 4 kho A1, A2, A3, A4
đến 5 cửa hàng B1, B2, B3, B4, B5. Cho biết lượng gạo
có ở mỗi kho, lượng gạo cần ở mỗi cửa hàng và giá
cước vận chuyển (ngàn đồng) 1 tạ gạo từ mỗi kho tới
mỗi cửa hàng như sau:
Hãy lập kế hoạch vận chuyển gạo từ các kho tới các
cửa hàng sao cho mọi kho phát hết gạo có, mọi cửa
hàng nhận đủ gạo cần và tổng chi phí vận chuyển là bé
nhất ?
23
Các bước thực hiện giải bài toán bằng Solver:
Bước 1: Nhập dữ liệu bài toán vào bảng tính dưới
dạng sau:
Trong đó: Khối B2:F5 là ma trận chi phí vận chuyển.
Khối B8:F11 là phương án vận chuyển (giá trị ban đầu
cho tất cả nằng 1). Khối H8:H11 là khả năng của các
điểm phát. Khối B13:F13 là nhu cầu của các điểm thu.
24
Bước 2:
Tính giá trị hàm mục tiêu trong ô H3 theo công thức:
H3 =SUMPRODUCT(B8:F11; B2:F5)
Tính lượng hàng phát của điểm phát A1 tại ô G8 theo công
thức: G8 =SUM(B8:F8), sao chép công thức vào các ô
G9:G12.
Tính lượng hàng nhận được của điểm thu B1 tại ô B12 theo
công thức: B12 =SUM(B8:B11), sao chép công thức vào
các ô C12:F12.
25
Bước 3: Dùng lệnh Tools | Solver với các lựa chọn
hàm mục tiêu và các ràng buộc:
Sau khi nhập xong các ràng buộc, nháy nút options,
hiện hộp thoại Solver Options, đánh dấu kiểm vào
mục Assume Linear Model.
26
Bước 4: Trong hộp thoại Solver Parameters, nháy
vào nút Solver để bắt đầu giải bài toán. Giải xong bài
toán xuất hiện hộp thoại Solver Results, chọn mục
Keep Solver Solution, nháy OK. Kết quả nhận được:
Giá trí tối ưu hàm mục tiêu bằng fmin = 2420 (đvcp).
Phương án vận chuyển tối ưu: x[1,1] = 35, x[1,4] = 40,
X[2,2]=40, X[2,3]=60, X[3,3]=25, X[3,5]=40, X[4,1]=40, X[4,2] =20.
Kết quả trong bảng tính:
27
BAØI TAÄP
5.1. Lập mô hình toán học và giải các bài toán sau:
1. Công ty may mặc Long Vũ hiện đang lập kế hoạch
sản xuất 3 mặt hàng Áo Jaket, Áo Chemis và Áo
Bludong. Được biết chi phí giờ công sản xuất của
từng mặt hàng qua 3 công đoạn cắt, may, hoàn chỉnh
như sau:
Năng lực tối đa của các bộ phận như sau:
- Bộ phận cắt : 1250 giờ công
- Bộ phận may : 1650 giờ công
- Bộ phận hoàn chỉnh : 540 giờ công
Chemi
s
Bludon
g
Jaket
Giờ công bộ phận cắt 0.2 0.4 0.3
Giờ công bộ phận may 0.3 0.5 0.4
Giờ công bộ phận hoàn
chỉnh
0.1 0.2 0.1
Đơn giá (USD)/1SP 2.3 3.6 2.8
28
Tối thiểu trong một tháng mỗi loại phải sản xuất 200
sản phẩm.
Hãy tính kế hoạch sản xuất mỗi loại sản phẩm bao
nhiêu để đạt tổng giá trị sản phẩm lớn nhất và vẫn
bảo đảm các điều kiện về năng lực sản phẩm và quy
định số lượng sản phẩm tối thiểu.
2. Nhà máy sản xuất thiết bị nghe nhìn điện tử Hanel
lắp ráp thành phẩm máy thu hình TV, Stereo và Loa
thùng từ các bộ phận khác nhau. Tên các bộ phận và
số lượng còn trong kho của chúng được bộ phận
KHO cung cấp trong bảng sau:
29
Tên bộ phận Kho
Số lượng bộ phận sử dụng khi lắp ráp
TV Stereo Loa thùng
Khung 450 1 1 0
Đèn hình 250 1 0 0
Loa 800 2 2 1
Nguồn 450 1 1 0
Hệ thống điện 600 2 1 1
Lợi nhuận đơn vị ($) 75 50 35
Tìm giải pháp lắp ráp số lượng máy thu hình TV,
Stereo, Loa thùng từ số bộ phận còn trong kho để
đem lại tổng lợi nhuận cao nhất?
30
5.2. Giải các bài toán quy hoạch tuyến tính sau:
1. f = -x1 - 2x2 - 3x3 + x4 min,
x1 + 2x2 + 3x3 = 15,
2x1 + x2 + 5x3 = 20,
x1 + 2x2 + x3 + x4 = 10,
xj 0 (j = 1,...,4).
2. f = x1 + 2x2 - x3 max,
-x1 + 4x2 - 2x3 6,
x1 + x2 + 2x3 6,
2x1 - x2 + 2x3 = 4,
x1 0, x2 0, x3 0.
3. f = -x1 - x2 + 1 max,
x1 - x2 -1,
3x1 + 2x2 6,
-3x1 - x2 -9,
x1 0, x2 0.
31
5.3. Lập mô hình toán học và giải bài toán sau:
Cần vận chuyển xi măng từ 4 kho K1, K2, K3, K4 đến 5
công trường T1, T2, T3, T4, T5. Cho biết số lượng xi
măng có ở mỗi kho, số lượng xi măng cần ở mỗi công
trường và giá cước vận chuyển (ngàn đồng) 1 bao xi
măng từ mỗi kho tới mỗi công trường như sau:
Hãy lập kế hoạch vận chuyển xi măng từ các kho tới các
công trường sao cho mọi kho phát hết xi măng có, mọi
công trường nhận đủ xi măng cần và tổng chi phí vận
chuyển là bé nhất ?
32
5.4. Giải các bài toán sau:
1. Một công ty vận tải biển cần 110 người để bố trí 10
máy trưởng, 25 thợ máy 1, 30 thợ máy 2 và 45 thợ máy
3. Phòng tổ chức công ty tìm được 90 người, gồm 25
kỹ sư máy, 20 trung cấp kỹ thuật và 45 công nhân.
Phòng tổ chức đánh giá khả năng của cán bộ theo công
việc như ở bảng sau:
Vậy cần bố trí sao cho sử dụng hết năng lực của mọi
người.
Công việc
Trình độ
cán bộ
Hệ số đánh giá năng lực (qij)
máy trưởng máy 1 máy 2 máy 3
Kỹ sư 5 4 0 0
Trung cấp 3 5 4 0
Công nhân 0 1 5 4
33
Ghi chú: Giả thiết đánh giá năng lực cán bộ theo thang
điểm 5, tức là qij = 5: cán bộ i có năng lực hoàn thành
xuất sắc công việc j, qij = 4,3,2,1 tương ứng với các
mức độ khác nhau, còn qij = 0 là cán bộ i hoàn toàn
không thể làm công việc j.
2. Một đội làm rau gồm 23 lao động nữ, chia làm 3
loại: loại A và B có 10 người; loại C có 3 người. Đội đó
cần bố trí 3 người đi hái rau, 8 người làm cỏ rau và 12
người trồng rau. Năng suất lao động của từng loại được
cho trong bảng sau:
Vậy phải phân công
như thế nào để năng
suất đạt được cao nhất?
Các file đính kèm theo tài liệu này:
- chuong_7_quy_hoach_tuyen_tinh_1525.pdf