Mô Hình Bài Toán Tối Ưu Hóa và Ứng Dụng Trong Kinh Doanh | Tối ưu rời rạc | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
Khái niệm tối ưu hóa nguồn lực được xuất phát từ Chiến tranh thế giới thứ 2. Trong chiến tranh, người Anh và sau đó là quản lý quân sự Hoa Kỳ đã sử dụng một số lượng lớn các nhà nghiên cứu để áp dụng các phương pháp khoa học nhằm đối phó với các vấn đề nguồn lực khan hiếm cho các hoạt động quân sự khác nhau. Tài liệu được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!
Môn: Tối ưu rời rạc (HUS) 10 tài liệu
Trường: Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội 687 tài liệu
Tác giả:
Preview text:
Chương I:
LẬP MÔ HÌNH BÀI TOÁN TỐI ƯU HÓA
Chương 1 cung cp một số ví d v
ụ ề cách lập mô hình bài toán tối ưu hóa từ tình hu ng ố s n x ả u t kinh doanh th c
ự tế và giới thiệu định nghĩa bài toán tối ưu hóa tổng quát.
Sau khi hc xong chương này, ngưi h c có kh ả : năng
Lập mô hình bài toán tối ưu hóa từ nh ng t ữ ình hu ng s ố ản xu t kinh doanh th c ự tế
Hiểu về mô hình bài toán tối ưu hóa
1.1. Giới thiệu về bài toán tối ưu hóa
Khái niệm tối ưu hóa nguồn lực được xuất phát từ Chiến tranh thế giới thứ 2. Trong chiến tranh,
người Anh và sau đó là quản lý quân sự Hoa Kỳ đã sử d ng
ụ một số lượng lớn các nhà nghiên
cứu để áp dụng các phương pháp khoa học nhằm i
đố phó với các vấn đề nguồn lực khan hiếm cho các hoạt ng độ quân s
ự khác nhau. Trong thực tế, họ được yêu cầu thực hiện nghiên cứu về
các hoạt động quân sự. Những nhóm các nhà khoa h c
ọ này là những đội tối ưu hóa (hay còn gọi
là các đội nghiên cứu vận hành) đầu tiên. Bằng cách phát triển hiệu quả phương pháp sử d ng ụ công c
ụ mới của radar, các đội này góp phần lớn trong chiến thắng trong trận chiến trên không
của Anh. Thông qua nghiên c u
ứ về cách quản lý tốt hơn các hoạt động của đoàn tàu và chống tàu
ngầm, họ cũng đóng một vai trò quan tr ng
ọ trong chiến thắng trận chiến Bắc Đại Tây Dương và ở Thái Bình Dương.
Khi chiến tranh kết thúc, thành công của nghiên c u
ứ vận hành trong chiến tranh cũng thúc đẩy sự
quan tâm đến việc áp dụng tối ưu hóa bên ngoài quân đội. Khi s ự bùng n
ổ của nền công nghiệp
sau chiến tranh diễn ra, các vấn đề gây ra bởi sự phức tạp và chuyên môn hóa ngày càng tăng
trong các tổ chức lại m t
ộ lần nữa được đặt lên hàng đầu. Để giải quyết các vấn đề đó, số lượng
các chuyên gia tư vấn kinh doanh áp d ng
ụ tối ưu hóa ngày càng tăng, về cơ bản họ đang giải
quyết những vấn đề tương tự mà quân đội phải đối mặt nhưng trong một bối cảnh khác. Đến đầu
những năm 1950, những cá nhân này đã giới thiệu việc sử dụng tối ưu hóa cho nhiều tổ chức
trong kinh doanh, công nghiệp và chính phủ. Sự phát triển mạnh mẽ của nghiên c u ứ vận hành
hay tối ưu hóa được xuất phát từ hai nguyên nhân chính. Lý do đầu tiên là do các nghiên cứu về lĩnh vực này có nh ng
ữ tiến bộ vượt bậc. M t
ộ ví dụ điển hình là phương pháp đơn hình để giải Page | 1
quyết các vấn đề quy hoạch tuyến tính, được phát triển bởi George Dantzig vào năm 1947. Bên
cạnh đó, nhiều công cụ khác c a ủ nghiên c u
ứ vận hành như quy hoạch tuyến tính, quy hoạch
động, lý thuyết xếp hàng và lý thuyết hàng t n
ồ kho đã được phát triển tương đối tốt vào cu i ố
những năm 1950. Lý do thứ hai tạo động lực lớn cho sự phát triển của lĩnh vực này là sự bùng nổ của cu c
ộ cách mạng máy tính. M t
ộ nhà nghiên cứu vận hành cần giải quyết vấn đề thông qua
một số lượng lớn tính toán mà làm bằng tay sẽ rất t n
ố thời gian. Do đó, sự phát triển của máy tính điện tử k t
ỹ huật số, với khả năng thực hiện các phép tính s
ố học nhanh hơn hàng triệu lần so với con người là m t
ộ lợi ích to lớn cho nghiên cứu vận hành. M t
ộ sự thúc đẩy hơn nữa đến vào
những năm 1980 với sự phát triển của các máy tính cá nhân ngày càng mạnh mẽ kèm theo các
gói phần mềm tốt để thực hiện giải bài toán tối ưu hóa. Điều này giúp nghiên c u ứ vận hành dễ
dàng tiếp cận nhiều người hơn và tiến trình này tiếp tục tăng tốc vào những năm 1990 và sang
thế kỷ XXI. Ngày nay, hàng triệu cá nhân đã sẵn sàng truy cập vào phần mềm tối ưu hóa để giải
quyết các vấn đề sản xuất kinh doanh c a
ủ doanh nghiệp với các thuật toán kh ng ổ lồ.
Tại Việt Nam hiện nay, kiến thức dùng mô hình toán để giải quyết các tình huống sản xuất kinh doanh th c
ự tế thường xuất hiện ở các khóa học như sau:
Toán tối ưu hóa/Toán ứng d ng
ụ (Mathematical Optimization hay Applied Mathematics).
Vận trù học, Nghiên cứu vận hành (Operations Research viết tắt là OR). Khoa h c
ọ quản lý (Management Science viết tắt là MS).
Quy hoạch tuyến tính (Linear Programming).
Dù được sử dụng với tên gọi nào thì các h c
ọ giả vẫn luôn tập trung vào việc sử d ng ụ các thuật
toán để giải bài toán thực tế. Trước hết là người đọc cần phải biết cách lập mô hình bài toán t i ố ưu hóa từ các tình hu ng
ố sản xuất kinh doanh. Một số ví dụ ở mục 1.2 sẽ giúp người đọc tiếp cận vấn đề đó.
1.2. Một số ví dụ về l p
ậ mô hình bài toán tối ưu
Ví dụ 1.1: Bài toán l p ậ kế ho c ạ h s n ả xu t ấ
Nhân dịp Tết Trung Thu, Công ty bánh kẹo X muốn sản xuất 3 loại bánh: bánh thập cẩm,
bánh dẻo và bánh đậu xanh để phục vụ Tết. Công ty có nguyên vật liệu như sau: 500 kg đường,
300 kg đậu, các nguyên vật liệu khác không giới hạn. Định mức tiêu hao NVL và lãi thu được
khi bán một cái bánh được cho ở bảng sau: Page | 2 NVL Thập c m ẩ Dẻo Đậu xanh Đường (kg) 0,04 0,07 0,06 Đậu xanh (kg) 0 0,04 0,08 Lãi (đồng) 1700 1800 2000
Yêu cầu: Hãy lập mô hình kế hoạch sản xuất các loại bánh sao cho không bị động về đường, đậu
xanh và tiền lãi thu được là lớn nhất. Bài giải Gọi x , x , 1 2 3
x lần lượt là số lượng bánh thập cẩm, bánh dẻo, bánh đậu xanh cần sản xuất ( x , x , 1 2 3 x 0).
Mô hình: Tìm x , x , 1 2 3 x th a ỏ :
f (x) 1700x 1800x 2000x max 1 2 3
0,04x 0,07x 0,06x 500 { 1 2 3
0,04x 0,08x 300 2 3 x j j 0,( 1,3) Lưu ý:
- Đề bài yêu cầu tìm cái gì thì chúng ta sẽ đặt ẩn ở đó, cụ thể ở ví dụ này, đề yêu cầu “lập
mô hình kế hoạch sản xuất các loại bánh”, vì thế ta đặt các ẩn là số bánh các loại cần sản xuất.
- Đề yêu cầu “không bị động về đường, đậu xanh” nghĩa là phải lên kế hoạch sản xuất
lượng bánh sao cho không sử dụng vượt quá lượng đường, đậu xanh có sẵn. Vì vậy, trong ràng
buộc về đường và đậu xanh, ta sử d ng
ụ dấu “ ” để thỏa yêu cầu đề bài.
Ví dụ 1.2: Bài toán xác định kh u ẩ ph n ầ thức ăn Để nuôi m t ộ loại gia cầm trong m t
ộ ngày (24 giờ) cần có khối lượng tối thiểu các chất Protit,
Gluxit, Lipit tương ứng là: 70 gam, 420 gam và 30 gam. Trên thị trường hiện có bán 2 loại th c ứ ăn A và B với t
ỷ lệ các chất trong 1 gam thức ăn được cho ở bảng sau (đơn vị là gam): Page | 3 Thức ăn P (g) L(g) G(g) A 0,1 0,1 0,7 B 0,1 0,2 0,6
Biết chi phí để mua thức ăn A, B tương ứng là 40.000 đồng/kg, 60.000 ng đồ /kg. Hãy lập mô
hình bài toán tìm phương án mua thức ăn các loại A, B sao cho đảm bảo được nhu cầu dinh
dưỡng tối thiểu với chi phí thấp nhất. Bài giải Gọi x , x , 1 2
x lần lượt là lượng thức ăn loại A, B cần mua. ( 1 2 x 0)
Mô hình: Tìm x , x , 1 2 3 x th a ỏ :
f (x) 40.000x 60.000x min 1 2
0,1x 0,1x 70 1 2
{0,7x 0,6x 420 1 2
0,1x 0,2x 30 1 2 x j j 0,( 1,2) Lưu ý:
- Thứ tự Protit, Gluxit, Lipit ở phần “khối lượng t i
ố thiểu các chất” và trong bảng tỷ lệ các
chất trong 1g thức ăn không giống nhau → Đọc kĩ đề trước khi làm bài.
Ví dụ 1.3: Bài toán phân bổ vốn đầu tư
Một người có 500 triệu đồng mu n c ố
ho vay theo các loại hình sau đây: 1. Tiết kiệm không k ỳ hạn: lãi suất 4%
2. Tiết kiệm có kỳ hạn: lãi suất 10 %
3. Mua tín phiếu: lãi suất 13% Page | 4
4. Cho tư nhân vay: lãi suất 16%.
Thời gian đáo hạn như nhau. Mỗi loại hình đều có rủi ro, để giảm thiểu rủi ro nhà đầu tư theo các
chỉ dẫn sau đây của nhà tư vấn:
- Không cho tư nhân vay quá 20% số v n ố .
- Số lượng cho vay trong tín phiếu không vượt quá t ng
ổ số cho vay trong ba lĩnh vực kia.
- Ít nhất 30% cho vay là tiết kiệm có kỳ hạn và tín phiếu.
- Tỷ lệ cho vay không kỳ hạn so với có kỳ hạn không quá 1/3. Người ta mu n c ố ho vay toàn bộ s t
ố iền. Yêu cầu: Hãy lập kế hoạch đầu tư sao cho lợi nhuận tối đa. Bài giải
Gọi x , x , x , 1 2 3 4
x lần lượt là lượng tiền gửi tiết kiệm không kỳ hạn; tiền gửi tiết kiệm có kỳ hạn;
tiền mua tín phiếu; tiền cho tư nhân vay. ( x , x , x , 1 2 3 4
x 0; đơn vị: 100.000 VND)
Mô hình: Tìm x , x , x , 1 2 3 4 x thỏa:
f (x) 4%x 10%x 13%x 16%x max 1 2 3 4 3 1 x 2 x 0 x x 150 2 3 x 3
x1 x2 x4 0 x 100 4 {x 1
x2 x3 x4 500 x j j 0,( 1,4) Lưu ý:
- Người ta yêu cầu dùng hết 500 triệu để đầu tư, vì vậy ta phải có ràng buộc t ng ổ
x x x x 500 . 1 2 3 4
- Đề yêu cầu lập kế hoạch đầu tư sao cho lợi nhuận tối đa, đối với bài toán đầu tư, “lợi
nhuận” được hiểu là phần tiền lãi sinh ra từ v n
ố , vì vậy hàm mục tiêu chỉ bao gồm t ng ổ các phần
lãi, không bao gồm cả lãi và vốn. Page | 5
Ví dụ 1.4: Bài toán c t
ắ vật liệu
Một xí nghiệp may cần sản xuất 2000 quần và ít nhất 1000 áo. Mỗi tấm vải có 6 cách cắt với
số lượng quần áo tương ứng được cho ở bảng dưới. Yêu cầu: Hãy lập mô hình bài toán tìm
phương án cắt quần áo sao cho t ng
ổ số tấm vải sử dụng là ít nhất. Cách cắt 1 2 3 4 5 6 Quần (cái) 9 8 7 6 12 0 Áo (cái) 3 5 7 8 0 10 Bài giải Gọi x j l x j j 0,( 1,6) j ( 1,6) ần lượt là s
ố vải sử dụng tương ứng cho 6 cách cắt,
Mô hình: Tìm x , x , x , x , x , x 1 2 3 4 5 6 th a ỏ :
f (x) x x x x x x min 1 2 3 4 5 6
9x 8x 7x 6x 12x 2000 { 1 2 3 4 5 3 1 x 5 2 x 7 3 x 8 4 x 10 6 x 1000 x j j 0,( 1,6) Lưu ý:
Đề yêu cầu “sản xuất 2000 quần và ít nhất 1000 áo” nghĩa là số quần phải sản xuất bằng đúng
2000 cái và số áo sản xuất phải lớn hơn hoặc bằng 1000 cái.
1.3. Định nghĩa bài toán tối ưu hóa
Mô hình bài toán tối ưu hóa tổng quát được trình bày như sau:
Cho bài toán (P) sau đây: Tìm x (x , x ,..., xn) 1 2 sao cho: Page | 6 n
F (x) c x j j min (max) (1) j1 n a x i m ij j b ( 1, ) (2) i j1 0 x 0 (3) j . k . h c
Để viết được mô hình bài toán, người h c
ọ cần lưu ý theo các bước sau:
Bước 1: Gọi các giá trị cần tìm là các biến (ẩn)
Bước 2: Viết hàm m c
ụ tiêu (1) và các ràng bu c ộ (2)
Cần xác định rõ mục tiêu của bài toán là bài toán cực tiểu hay cực đại để viết hàm m c ụ tiêu
chính xác. Ví dụ bài toán yêu cầu t i
ố thiểu hóa chi phí thì hàm m c
ụ tiêu của bài toán là Fmin; bài
toán yêu cầu tối đa hóa lợi nhuận hay doanh thu thì m c ụ tiêu c a ủ bài toán là Fmax. (1) g i là hàm m c ụ tiêu; c g j (j
1,n) ọi là các hệ số hàm m c ụ tiêu
Hàm ràng buộc là các yêu cầu của bài toán được diễn giải thành các bất phương trình, phương
trình thể hiện các hạn chế trong sản xuất kinh doanh.
(2) gi là hàm ràng bu c ộ c a ( ủ P) b (i 1,m) ủ ộ i
gọi là các hệ số vế phải c a ràng bu c a ệ ố ràng buộc ij (i
1, m; j 1,n) gọi là các h s
A (a ) gọi là ma trận hệ số ràng buộc ij m n
Bước 3: Viết điều kiện về dấu c a
ủ biến (hay còn gi là ràng bu c ộ biến) (3)
Biến trong mô hình có thể ≥ 0; hoặc ≤ 0; hoặc không hạn chế (còn được viết tắt là k.h.c)
Nếu như x (x , x ,. .,x ) th 1 2 n
ỏa (2) và (3) thì x gọi là phương án (PA) của (P) Page | 7
- X = {các PA của (P)} gọi là miền phương án hay miền xác định của (P)
- Phương án thỏa (1) gọi là phương án tối ưu (PATƯ) và F(x) gọi là giá trị tối ưu của bài toán. 1.4. Bài t p ậ Bài t p ậ 1.1
Một người thợ cắt thanh sắt dài 3m thành: 200 đoạn dài 1,2m; 300 đoạn dài 0,9m; 600 đoạn dài 0,8m. M i
ỗ thanh sắt 3m phải mua với giá 50.000 đồng. Số sắt thừa sau khi cắt có thể đem
bán 5000 đồng/1m. Hãy lập mô hình bài toán tìm phương án cắt sắt sao cho th a ỏ mãn nhu cầu về
các đoạn sắt cần cắt và tổng chi phí mua sắt sau khi khấu trừ số tiền bán sắt thừa là ít nhất.
Cách cắt 1 2 3 4 5 6 7 8 1,2 m 2 1 1 1 0 0 0 0 0,9 m 0 2 1 0 3 2 1 0 0,8 m 0 0 1 2 0 1 2 3 Thừa (m) 0,6 0 0,1 0,2 0,3 0,4 0,5 0,6 Bài giải Gọi x j lần lượt là s
ố thanh sắt 3m dùng để cắt theo 8 cắt, x j j 0,( 1,8) j ( 1,8)
Mô hình: Tìm x , x , x , x , x ,x , x , 1 2 3 4 5 6 7 8 x th a ỏ : 8 f (x) 50000
x 5000.(0,6x 0,1x 0,2x 0,3x 0, 4x 0,5x 0,6x ) min j 1 3 4 5 6 7 8 j1
2x x x x 200 1 2 3 4
2x x 3x 2x x 300 2 3 5 6 7
{ x 2x x 2x 3x 600 3 4 6 7 8 x j j 0,( 1,8) Page | 8 Bài t p ậ 1.2 Một hộ nông dân tr ng
ồ 2 loại cây ngô và sắn trên 3 khu đất A, B, C có diện tích tương ứng
là: 40 ha, 50 ha, 30 ha. Mùa vụ này, yêu cầu sản lượng c a
ủ ngô và sắn tương ứng là: 240 tạ, 1260
tạ. Chi phí sản xuất (triệu đồng/ha) và năng suất (tạ/ ha) là khác nhau và được cho ở bảng sau: Loại cây Khu đất Ngô Sắn Chi phí Năng suất Chi phí Năng suất A 1 8 0,6 12 B 1,2 9 0,8 15 C 1,5 10 0,9 16
Hãy lập mô hình bài toán tìm phương án phân phối đất trồng sao cho bảo đảm yêu cầu sản
lượng và chi phí thấp nhất. Bài gi i ả Gọi x j lần lượt là: j ( 1,6) 1
x là phần đất khu A dùng để trồng ngô
x4 là phần đất khu A dùng để tr ng ồ sắn 2
x là phần đất khu B dùng để trồng ngô
x5 là phần đất khu B dùng để trồng sắn x x
3 là phần đất khu C dùng để trồng ngô
6 là phần đất khu C dùng để trồng sắn x j Đơn vị: ha, j 0,( 1,6) Mô hình: Tìm x j th a ỏ : j ( 1,6)
f (x) x 1,2x 1,5x 0,6x 0,8x 0,9x min 1 2 3 4 5 6 Page | 9 x x 40 1 4 2 x 5 x 50 x x 30 3 6 8 1
x 9x2 10x3 240
{12x 15x 16x 1260 4 5 6 x j j 0,( 1,6) Lưu ý:
Nếu đề không nêu cụ thể “lập phương án phân phối đất trồng sao cho chi phí thấp nhất”
mà chỉ nói đại khái “lập phương án sao cho chi phí thấp nhất” thì nên đặt ẩn là gì? Đối với dạng
bài tập có quá nhiều đối tượng như bài tập 1.2 (khu đất, năng suất, chi phí, 2 loại sản phẩm), ta
có nhiều cách đặt ẩn, một cách đặt ẩn được gợi ý cho dạng bài này là: trước khi đặt ẩn hãy quan
sát đơn vị của các đối tượng, ở bài 1.2 ta có các đơn vị như triệu đồng/ha; tạ/ha, hãy chọn đối
tượng ở mẫu số (ha - diện tích đất) làm ẩn của mô hình. Tuy nhiên các cách g i ọ ẩn khác vẫn
được chấp nhận nếu như các hàm mục tiêu, ràng bu c ộ viết chính xác. Bài t p ậ 1.3:
Một xí nghiệp sản xuất một loại sản phẩm gồm có 3 dạng: thường, tốt, siêu hạng với các dữ kiện sau: Dạng sản phẩm Thường Tốt Siêu hạng
Giá bán một đơn vị sản phẩm 80 160 240 (1.000 đồng)
Chi phí nguyên liệu cho một đơn vị 40 70 110 sản phẩm (1000 đồng)
Thời gian hoàn tất 1 đơn vị sản phẩm 0,2 0,3 0,6 (giờ) Page | 10
Nhu cầu tối đa trong một tuần 1000 500 200 (đơn vị)
Xí nghiệp có lực lượng lao động là 6 người, làm việc 40 giờ/tuần, trả lương 400.000
đồng/tuần/người dù họ có làm việc đủ 40 giờ hay không. Hãy lập mô hình bài toán tìm kế hoạch
sản xuất sao cho tổng lợi nhuận là cực đại. Bài giải Gọi x j l x j j 0,( 1,3) j ( 1,3) ần lượt là s
ố sản phẩm thuộc 3 loại: thường, tốt, siêu hạng,
(Kí hiệu: P: giá bán; C: chi phí; W: tiền lương; Đơn vị: 1000 đồng)
Mô hình: Tìm x , x , 1 2 3 x th a ỏ : f ( )
x P x C x W x x x j j j j 6 40 90 130 2400 max 1 2 3 0,2 1 x 0,3 2 x 0,6 3x 240 x 1 000 1 x 2 500 { 3 x 2000 x j j 0,( 1,3) Lưu ý:
Ràng buộc 0,2x 0,3x 0,6x 240 là ràng bu c ộ về th 1 2 3
ời gian, trong đó, “240” là tổng s ố
giờ làm việc của 6 công nhân trong 1 tuần, vì đề không yêu cầu 6 công nhân phải làm đúng 40 tiếng/tuần/người (h
ọ có thể làm ít hơn mức này), ta cho thời gian sản xuất 3 loại sản phẩm ít hơn
hoặc bằng tổng thời gian làm việc định mức của 6 công nhân. Bài tập 1.4
Anh (chị) hãy lập mô hình toán h c
ọ của bài toán sau đây (chỉ l p m ậ
ô hình, không giải).
Một nhà đầu tư có 200 tỷ đồng, muốn đầu tư vào 4 lĩnh vực: chứng khoán, gửi tiết kiệm,
bất động sản, đầu tư mạo hiểm. Biết rằng đầu tư vào chứng khoán sau 3 năm sẽ có lãi suất là
65%, đầu tư vào gửi tiết kiệm có lãi suất hàng năm là r% (với 5% ≤ r% p ≤ 8%), đầu tư vào bất Page | 11
động sản sau 3 năm sẽ có lãi suất là 80%, đầu tư mạo hiểm sau 3 năm sẽ có lãi suất là 90%.
Ngoài ra, để giảm thiểu rủi ro nhà đầu tư quyết định: s
ố tiền gửi tiết kiệm phải ít nhất là 30%
tổng vốn đầu tư, số tiền đầu tư vào chứng khoán không vượt quá 25% tổng vốn đầu tư, số tiền
đầu tư mạo hiểm không vượt quá 20% t ng
ổ vốn đầu tư. Hãy lập mô hình bài toán xác định kế
hoạch đầu tư trong 3 năm sao cho tổng lợi nhuận lớn nhất. Giả sử rằng tiền lãi (gửi tiết kiệm)
được sử dụng để đầu tư tiếp và nhà đầu muốn đầu tư hết toàn bộ s t ố iền. Cách gi i ả
Gọi xj (j = 1,4) lần lượt là số tiền đầu tư vào chứng khoán, gửi tiết kiệm, bất động sản, đầu tư
mạo hiểm (xj ≥ 0, j = 1,4)
Xét phần lãi tiết kiệm c a
ủ khoản tiền gửi tiết kiệm: Gốc Lãi Năm 1 x x 2 r% 2 Năm 2 x (1 r%)
r%x (1 r%) 2 2 Năm 3 2 x (1 r%)
r%x (1 r%) 2 2 2 Cuối năm 3 thu về: 3 x (1 r%) 2 (khoản tiền lãi + g c ố của riêng năm 3) Lãi suốt 3 năm: 3 3
x (1 r%) x x (1 r%) 1 2 2 2
Mô hình: tìm xj (j = 1,4) thỏa: 3
f (x) 65%x x (1 r%) 1 80%x 90%x max 1 2 3 4 x 30%*200 2 x 25%*200 1 ĐVT: tỷ đồng x 20%*200 4
x x x x 200 1 2 3 4
x 0( j 1,4), 5% r % 8% j Page | 12
Lưu ý: Một cách khác để tính ph n l
ầ ãi tiền tiết kiệm từ 3 năm là c ng các ộ kho n l ả ãi t ừ 3 năm l i ạ
đã phân tích trong bảng, sau đó biến đổi biểu thức để có d ng r ạ
út gn gợi ý trong bài gi i ả . Bài tập 1.5:
Anh (chị) hãy lập mô hình toán h c
ọ của bài toán sau đây (chỉ l p m ậ
ô hình, không giải). Một công ty s ử d ng
ụ 4 loại nguyên liệu N ,1 N2, N3, N4 để sản xuất ra 3 loại sản phẩm
SP1, SP2, SP3. Biết lợi nhuận của mỗi đơn vị sản phẩm (không phụ thu c
ộ vào số gi sản xut và
số sản phẩm được sản xut), số lượng nguyên liệu hiện có, định mức tiêu hao các loại nguyên
liệu và lượng sản phẩm làm ra trong m t
ộ giờ được cho trong bảng sau:
Định mức tiêu hao nguyên liệu Số lượng nguyên Nguyên liệu (đơn vị) trong 1 giờ liệu hiện có SP1 SP2 SP3 N1 250 (đơn vị) 4 5 2 N2 350 (đơn vị) 7 8 8 N3 150 (đơn vị) 6 5 7 N4 300 (đơn vị) 11 12 9
Sản lượng (sản phẩm/giờ) 10 10 9
Lợi nhuận (đồng/sản phẩm) 15.000 13.000 16.000
Sản phẩm của xí nghiệp sản xuất ra đều có thể tiêu thụ hết với điều kiện tiêu thụ là số sản phẩm
SP2 và SP3 phải có tỷ lệ 1:3. Hãy lập mô hình toán học tìm kế hoạch sản xuất sao cho lợi nhuận lớn nhất. Cách gi i ả Cách 1:
Gọi xj (j = 1,3) lần lượt là s
ố giờ SP1, SP2, SP3 được sản xuất (xj ≥ 0, j = 1,3)
Phân tích đề: Page | 13
Trong 1 giờ tốn 4 đơn vị nguyên liệu cho SP1 Ràng bu c
ộ N1: {Trong 1 giờ tốn 5 đơn vị nguyên liệu cho SP2
Trong 1 giờ tốn 2 đơn vị nguyên liệu cho SP3 Áp d ng ụ tam suất:
Trong x1 giờ tốn 4x1 đơn vị nguyên liệu cho SP1 Ràng bu c
ộ N1: {Trong x2 giờ tốn 5x2 đơn vị nguyên liệu cho SP2
Trong x3 giờ tốn 2x3 đơn vị nguyên liệu cho SP3
(Tương tự cho các nguyên liệu còn lại)
Lợi nhuận SP1: Trong 1 giờ sản xuất 10 đơn vị sản phẩm → Lợi nhuận = 10*15.000 đồng
Trong x1 giờ sản xuất 10*x1 đơn vị sản phẩm → Lợi nhuận = 10*x1*15.000 đồng
(Tương tự cho lợi nhuận từ các sản phẩm còn lại)
Mô hình: tìm xj (j = 1,3) thỏa:
f (x) 150.000 1 x 130.000 2 x 144.000 3x max 4 1 x 5x2 2 3 x 250
7x 8x 8x 350 1 2 3 6 1 x 5x2 7 3 x 150 ĐVT: giờ 1 1 1 x 12 2 x 9 3x 300
30x 9x 0 1 3 x j j 0( 1,3) Cách 2:
Gọi xj (j = 1,3) lần lượt là s
ố sản phẩm SP1, SP2, SP3 được sản xuất. (xj ≥ 0, j = 1,3) Phân tích đề:
10 đơn vị SP1 có định mức tiêu hao nguyên liệu là 4 đơn vị Ràng bu c ộ N :
1 {10 đơn vị SP2 có định mức tiêu hao nguyên liệu là 5 đơn vị (Trong 1 giờ)
9 đơn vị SP3 có địn mức h
tiêu hao nguyên liệu là 2 đơn vị Áp d ng ụ tam suất: Page | 14
x1 đơn vị SP1 có địn mức tiê h u hao nguyên liệu là 4 x 10 1 đơn vị Ràng bu c ộ N :
1 x2 đơn vị SP2 có địn mức tiê h u hao nguyên liệu là 5 x (Trong 1 giờ) 10 2 đơn vị
{ x3 đơn vị SP3 có định mức tiêu hao nguyên liệu là 2 x 9 3 đơn vị
(Tương tự cho các nguyên liệu còn lại)
Mô hình: tìm xj (j = 1,3) thỏa:
f (x) 15000 1 x 13000 2 x 16000 3 x max 4 5 2 x x x 250 1 2 3 10 10 9 7 8 8 x x x 350 1 2 3 1 0 10 9 6 5 7 x x x 150 ĐVT: đồng 1 2 3 1 0 10 9 11 12 x x x 300 1 2 3 10 10 3x x 0 1 3 x j j 0( 1,3)
1.5. Tóm tắt chương 1
Trong chương 1, nhóm tác giả đã giới thiệu về quá trình hình thành và phát triển c a ủ ngành h c ọ
tối ưu hóa và trình bày một số ví dụ về việc lập mô hình bài toán tối ưu hóa từ các tình huống sản
xuất kinh doanh. Các tình huống này đã được đơn giản hóa từ các tình hu ng ố thực tế, tuy nhiên
về bản chất cách lập mô hình không thay đổi. Tình hu ng
ố thực tế rất đa dạng, phong phú nên các
cách lập mô hình không giống nhau, tuy nhiên về bản chất các bạn cần nhớ “cái gì chúng ta c n ầ
tìm, chúng ta sẽ gi chúng là biến”. Trong mỗi ví dụ và bài tập đưa ra, nhóm tác giả đã trình bày
cách giải, cũng như các lưu ý khi giải để người đọc có thể hạn chế các lỗi sai khi làm bài. Page | 15