Bài Tập Quy Hoạch Tuyến Tính Có Lời Giải: Chìa Khóa Mở Cánh Cửa Tối Ưu

Chào bạn, đang đọc bài viết này chắc hẳn bạn đang “vật lộn” với môn Quy hoạch tuyến tính (QHTT) hoặc đơn giản là muốn “nâng trình” khả năng giải toán tối ưu của mình đúng không? Quy hoạch tuyến tính là một công cụ cực kỳ mạnh mẽ, được ứng dụng “tứ tung” từ sản xuất, vận tải, tài chính cho đến quản lý. Nhưng mà nói thật, lý thuyết đôi khi “trừu tượng” quá, cứ loay hoay mãi với các định nghĩa, định lý mà đến lúc “đụng” vào bài tập thì lại thấy “khớp” hết cả.

Đó là lý do mà Baocaothuctap.net “trình làng” bài viết này, tập trung vào cái mà bạn thực sự cần: Bài Tập Quy Hoạch Tuyến Tính Có Lời Giải. Chúng tôi hiểu rằng, cách học hiệu quả nhất với những dạng toán ứng dụng như thế này không gì khác ngoài việc “xắn tay áo” vào làm bài tập, và quan trọng hơn nữa, là có lời giải chi tiết để đối chiếu, hiểu rõ từng bước đi, từng quyết định. Hãy cùng nhau “giải mã” những bài toán QHTT tưởng chừng khó nhằn này nhé!

Trước khi đi sâu vào các bài tập quy hoạch tuyến tính có lời giải, chúng ta cùng “điểm danh” sơ qua xem QHTT là gì và tại sao nó lại quan trọng đến vậy.

Quy Hoạch Tuyến Tính Là Gì? “Phiên Bản” Dễ Hiểu Nhất

Nói một cách “bình dân”, Quy hoạch tuyến tính là một phương pháp toán học giúp chúng ta tìm ra cách tốt nhất để sử dụng các nguồn lực “có hạn” (như tiền bạc, thời gian, nguyên vật liệu, nhân công…) nhằm đạt được một mục tiêu “tối ưu” nào đó. Mục tiêu này có thể là tối đa hóa lợi nhuận, tối thiểu hóa chi phí, hay bất kỳ cái gì mà chúng ta muốn làm cho “ngon” nhất.

Tất cả những “điều kiện” hay “ràng buộc” về nguồn lực đều được biểu diễn bằng các phương trình hoặc bất phương trình tuyến tính. Cái “tuyến tính” ở đây có nghĩa là các biến số (những thứ chúng ta có thể thay đổi, ví dụ: số lượng sản phẩm sản xuất, số tấn hàng vận chuyển) chỉ xuất hiện với bậc nhất, không có bình phương, căn bậc hai, hay sin, cos gì hết. Hàm mục tiêu (cái chúng ta muốn tối ưu) cũng là một hàm tuyến tính của các biến này.

Nghe có vẻ “hàn lâm” nhỉ? Hãy tưởng tượng bạn là chủ một quán cà phê nhỏ. Bạn có một lượng đường, sữa, cà phê và thời gian của nhân viên “có chừng mực”. Bạn muốn làm nhiều loại đồ uống khác nhau (cà phê sữa, cà phê đen, trà sữa…) để tối đa hóa doanh thu. Mỗi loại đồ uống lại “ngốn” một lượng nguyên liệu và thời gian khác nhau. QHTT sẽ giúp bạn tính toán xem nên pha chế bao nhiêu ly mỗi loại để “hái ra tiền” nhiều nhất, trong khi vẫn đảm bảo không “cháy” nguyên liệu hay nhân viên làm việc quá giờ.

Tại Sao Luyện Tập “Bài Tập Quy Hoạch Tuyến Tính Có Lời Giải” Lại Quan Trọng Như “Ăn Cơm”?

Lý thuyết là nền tảng, nhưng “thực chiến” mới là cách để bạn thực sự “thấm” kiến thức. Quy hoạch tuyến tính cũng vậy. Bạn có thể hiểu “vanh vách” định nghĩa về phương án, phương án cực biên, phương án tối ưu… nhưng nếu không “nhúng tay” vào giải các bài toán cụ thể, bạn sẽ rất khó:

• Mô hình hóa: Biến một bài toán thực tế (dưới dạng lời văn) thành mô hình toán học (hàm mục tiêu, các ràng buộc). Đây là bước “then chốt” mà nhiều người “mắc kẹt”.
• Vận dụng phương pháp giải: Thành thạo các phương pháp như phương pháp đồ thị (cho bài toán 2 biến), phương pháp đơn hình (Simplex) cho bài toán nhiều biến.
• Biện luận kết quả: Hiểu ý nghĩa của nghiệm tối ưu trong ngữ cảnh bài toán thực tế. Con số 100 đơn vị sản phẩm A có ý nghĩa gì? Việc còn dư thừa 5kg nguyên liệu X nói lên điều gì?
• Phát hiện sai lầm: Tự mình làm, sai đâu sửa đó, “vỡ lẽ” ra chỗ khó, lần sau sẽ không “vấp” lại nữa.

Có trong tay các bài tập quy hoạch tuyến tính có lời giải giống như bạn có một tấm bản đồ và người hướng dẫn đáng tin cậy. Bạn tự đi trên con đường (giải bài tập), và khi “lạc lối” hoặc muốn kiểm tra xem mình đi đúng chưa, bạn có thể nhìn vào bản đồ (lời giải). Điều này giúp bạn học nhanh hơn, hiểu sâu hơn và tự tin hơn rất nhiều.

Đối với những ai quan tâm đến cẩm nang phương pháp sư phạm pdf, việc nắm vững kiến thức chuyên môn như QHTT và có khả năng truyền đạt nó một cách hiệu quả qua các bài tập minh họa có lời giải chính là một kỹ năng sư phạm quan trọng.

Làm Thế Nào Để “Tiếp Cận” Một Bài Toán Quy Hoạch Tuyến Tính?

Trước khi “lao” vào giải, hãy hít một hơi thật sâu và làm theo các bước sau. Đây là “kim chỉ nam” giúp bạn không bị “lạc đường” khi đứng trước một bài toán QHTT.

1. Đọc kỹ đề bài: Gạch chân những thông tin quan trọng: mục tiêu là gì (tối đa/tối thiểu cái gì?), có những nguồn lực hay điều kiện gì (giới hạn về nguyên liệu, thời gian, nhu cầu tối thiểu/tối đa…), những “đối tượng” nào đang được xem xét (các loại sản phẩm, các kho hàng, các điểm bán…).
2. Xác định các biến quyết định: Đây là những “ẩn số” mà chúng ta cần tìm giá trị cho chúng để đạt được mục tiêu tối ưu. Ví dụ: số lượng sản phẩm A cần sản xuất (gọi là x1), số tấn hàng cần vận chuyển từ kho i đến điểm bán j (gọi là x_ij). Nhớ kỹ, các biến này thường phải không âm (không ai sản xuất số lượng âm cả!).
3. Xây dựng hàm mục tiêu: Viết biểu thức toán học thể hiện mục tiêu cần tối ưu dưới dạng hàm tuyến tính của các biến quyết định. Ví dụ: Lợi nhuận = 5×1 + 7×2 (nếu x1, x2 là số lượng sản phẩm A, B và lợi nhuận đơn vị là 5, 7).
4. Thiết lập các ràng buộc: Biểu diễn tất cả các điều kiện, giới hạn của bài toán dưới dạng các phương trình hoặc bất phương trình tuyến tính của các biến quyết định. Ví dụ: Lượng nguyên liệu X sử dụng <= Lượng nguyên liệu X hiện có.
5. Thêm ràng buộc không âm: Đảm bảo tất cả các biến quyết định đều lớn hơn hoặc bằng 0 (x_i >= 0).
6. Chọn phương pháp giải: Dựa vào số lượng biến. 2 biến? Dùng đồ thị. Nhiều hơn 2 biến? Dùng phương pháp đơn hình (Simplex) hoặc phần mềm hỗ trợ.
7. Giải bài toán: Áp dụng phương pháp đã chọn để tìm giá trị của các biến quyết định làm cho hàm mục tiêu đạt giá trị tối ưu.
8. Biện luận kết quả: “Dịch” nghiệm toán học về lại ý nghĩa thực tế của bài toán.

Nghe có vẻ nhiều bước nhưng làm quen rồi sẽ thấy rất logic. Phần thú vị nhất chính là khi chúng ta bắt đầu “thực chiến” với các bài tập quy hoạch tuyến tính có lời giải cụ thể!

Bài Tập Quy Hoạch Tuyến Tính Có Lời Giải Chi Tiết: Từ Dễ Đến Khó

Hãy cùng “nhảy” vào một vài ví dụ điển hình. Chúng tôi sẽ trình bày bài toán, sau đó là lời giải “tận răng”, giải thích cặn kẽ từng bước.

### Bài Tập 1: Bài Toán Sản Xuất Đơn Giản (2 Biến – Giải Bằng Đồ Thị)

Đề bài:

Một công ty sản xuất hai loại sản phẩm A và B. Để sản xuất một đơn vị sản phẩm A cần 2 giờ máy và 1 kg nguyên liệu X. Để sản xuất một đơn vị sản phẩm B cần 1 giờ máy và 2 kg nguyên liệu X.
Công ty có tổng cộng 100 giờ máy và 120 kg nguyên liệu X.
Lợi nhuận thu được khi bán một đơn vị sản phẩm A là 30 nghìn đồng, sản phẩm B là 40 nghìn đồng.
Hãy xác định số lượng sản phẩm mỗi loại công ty nên sản xuất để tổng lợi nhuận thu được là lớn nhất.

Phân tích bài toán:

• Mục tiêu: Tối đa hóa lợi nhuận.
• Nguồn lực/Ràng buộc: Giới hạn về giờ máy và nguyên liệu X.
• Đối tượng: Sản phẩm A và B.

Lời giải chi tiết:

Bước 1: Xác định biến quyết định

Gọi x1 là số lượng sản phẩm A cần sản xuất.
Gọi x2 là số lượng sản phẩm B cần sản xuất.
Ràng buộc không âm: x1 >= 0, x2 >= 0. (Không thể sản xuất số lượng âm)

Bước 2: Xây dựng hàm mục tiêu

Mục tiêu là tối đa hóa lợi nhuận.
Lợi nhuận từ sản phẩm A: 30×1 (nghìn đồng)
Lợi nhuận từ sản phẩm B: 40×2 (nghìn đồng)
Tổng lợi nhuận Z = 30×1 + 40×2.
Chúng ta muốn tìm (x1, x2) sao cho Z đạt giá trị lớn nhất.
Hàm mục tiêu: Max Z = 30×1 + 40×2

Bước 3: Thiết lập các ràng buộc

• Ràng buộc về giờ máy:
  Sản xuất x1 đơn vị A cần 2×1 giờ máy.
  Sản xuất x2 đơn vị B cần 1×2 giờ máy.
  Tổng giờ máy sử dụng là 2×1 + x2.
  Tổng giờ máy có là 100.
  Ràng buộc: 2×1 + x2 <= 100

• Ràng buộc về nguyên liệu X:
  Sản xuất x1 đơn vị A cần 1×1 kg nguyên liệu X.
  Sản xuất x2 đơn vị B cần 2×2 kg nguyên liệu X.
  Tổng nguyên liệu X sử dụng là x1 + 2×2.
  Tổng nguyên liệu X có là 120.
  Ràng buộc: x1 + 2×2 <= 120

Tóm lại, mô hình QHTT của bài toán là:

Max Z = 30×1 + 40×2
Với các ràng buộc:
2×1 + x2 <= 100
x1 + 2×2 <= 120
x1 >= 0, x2 >= 0

Bước 4: Giải bài toán bằng phương pháp đồ thị

Phương pháp đồ thị áp dụng cho bài toán QHTT có 2 biến. Chúng ta sẽ vẽ các đường thẳng tương ứng với các ràng buộc và xác định miền chấp nhận được (miền chứa tất cả các điểm (x1, x2) thỏa mãn tất cả các ràng buộc).

1. Vẽ các đường thẳng:

   • Đường thẳng 2×1 + x2 = 100:
     Cho x1 = 0 => x2 = 100. Điểm (0, 100).
     Cho x2 = 0 => 2×1 = 100 => x1 = 50. Điểm (50, 0).
     Nối hai điểm này lại. Miền 2×1 + x2 <= 100 là miền nằm dưới đường thẳng này (thử điểm gốc (0,0): 2*0 + 0 = 0 <= 100, đúng).
   • Đường thẳng x1 + 2×2 = 120:
     Cho x1 = 0 => 2×2 = 120 => x2 = 60. Điểm (0, 60).
     Cho x2 = 0 => x1 = 120. Điểm (120, 0).
     Nối hai điểm này lại. Miền x1 + 2×2 <= 120 là miền nằm dưới đường thẳng này (thử điểm gốc (0,0): 0 + 2*0 = 0 <= 120, đúng).
   • Các ràng buộc không âm x1 >= 0 và x2 >= 0 giới hạn miền giải trong góc phần tư thứ nhất của hệ trục tọa độ (góc trên bên phải).

2. Xác định miền chấp nhận được (miền phương án):
   Miền chấp nhận được là phần giao của tất cả các miền ràng buộc, bao gồm cả các trục tọa độ trong góc phần tư thứ nhất. Miền này là một đa giác lồi. Các đỉnh của đa giác này là các điểm cực biên.

   Các đỉnh của miền chấp nhận được là:

   • O (0, 0): Giao của x1=0 và x2=0.
   • A (50, 0): Giao của 2×1 + x2 = 100 và x2 = 0.
   • B (x1, x2): Giao của 2×1 + x2 = 100 và x1 + 2×2 = 120.
     Giải hệ phương trình:
     2×1 + x2 = 100 (1)
     x1 + 2×2 = 120 (2)
     Nhân (1) với 2: 4×1 + 2×2 = 200.
     Trừ phương trình này cho (2): (4×1 + 2×2) – (x1 + 2×2) = 200 – 120 => 3×1 = 80 => x1 = 80/3.
     Thay x1 = 80/3 vào (1): 2*(80/3) + x2 = 100 => 160/3 + x2 = 100 => x2 = 100 – 160/3 = (300 – 160)/3 = 140/3.
     Vậy đỉnh B có tọa độ (80/3, 140/3).
   • C (0, 60): Giao của x1 + 2×2 = 120 và x1 = 0.

3. Tìm điểm tối ưu:
   Theo định lý, nếu bài toán QHTT có phương án tối ưu hữu hạn, nó sẽ đạt được tại một trong các đỉnh của miền chấp nhận được. Chúng ta chỉ cần tính giá trị của hàm mục tiêu Z tại các đỉnh này.

   • Tại O (0, 0): Z = 300 + 400 = 0.
   • Tại A (50, 0): Z = 3050 + 400 = 1500.
   • Tại B (80/3, 140/3): Z = 30(80/3) + 40(140/3) = 1080 + 40(140/3) = 800 + 5600/3 = (2400 + 5600)/3 = 8000/3 = 2666.67.
   • Tại C (0, 60): Z = 300 + 4060 = 2400.

   So sánh các giá trị của Z, giá trị lớn nhất là 8000/3 tại đỉnh B (80/3, 140/3).

Bước 5: Biện luận kết quả

Để đạt được lợi nhuận tối đa là 8000/3 nghìn đồng (khoảng 2.667.000 đồng), công ty nên sản xuất 80/3 đơn vị sản phẩm A và 140/3 đơn vị sản phẩm B.
Tuy nhiên, trong thực tế sản xuất, số lượng sản phẩm phải là số nguyên. Khi đó, bài toán trở thành Quy hoạch tuyến tính số nguyên, phức tạp hơn. Với mục đích của bài tập này, chúng ta tạm chấp nhận nghiệm phân số. Trong thực tế, có thể cần làm tròn (xuống) và kiểm tra lại các điểm lân cận trong miền chấp nhận được để tìm nghiệm nguyên tối ưu.

Kiểm tra ràng buộc tại điểm tối ưu B(80/3, 140/3):

• Giờ máy: 2*(80/3) + 140/3 = 160/3 + 140/3 = 300/3 = 100 <= 100 (Sử dụng hết giờ máy).
• Nguyên liệu X: 80/3 + 2*(140/3) = 80/3 + 280/3 = 360/3 = 120 <= 120 (Sử dụng hết nguyên liệu X).

Tại điểm tối ưu, cả hai nguồn lực (giờ máy và nguyên liệu X) đều được sử dụng hết.

### Bài Tập 2: Bài Toán Vận Tải Cơ Bản

Đề bài:

Một công ty có 2 kho hàng đặt tại A và B, với khả năng cung cấp lần lượt là 150 tấn và 200 tấn một loại hàng hóa. Hàng hóa này cần được vận chuyển đến 3 điểm bán C, D, E với nhu cầu tương ứng là 100 tấn, 120 tấn và 130 tấn. Chi phí vận chuyển (nghìn đồng/tấn) từ mỗi kho đến mỗi điểm bán được cho trong bảng sau:

Hãy lập mô hình bài toán Quy hoạch tuyến tính để xác định kế hoạch vận chuyển sao cho tổng chi phí vận chuyển là nhỏ nhất.

Phân tích bài toán:

• Mục tiêu: Tối thiểu hóa tổng chi phí vận chuyển.
• Nguồn lực/Ràng buộc: Khả năng cung cấp của mỗi kho, nhu cầu của mỗi điểm bán.
• Đối tượng: Lượng hàng vận chuyển từ mỗi kho đến mỗi điểm bán.

Lời giải chi tiết:

Bước 1: Xác định biến quyết định

Chúng ta cần xác định lượng hàng vận chuyển từ mỗi kho đến mỗi điểm bán.
Gọi x_AC là lượng hàng (tấn) vận chuyển từ kho A đến điểm C.
Gọi x_AD là lượng hàng (tấn) vận chuyển từ kho A đến điểm D.
Gọi x_AE là lượng hàng (tấn) vận chuyển từ kho A đến điểm E.
Gọi x_BC là lượng hàng (tấn) vận chuyển từ kho B đến điểm C.
Gọi x_BD là lượng hàng (tấn) vận chuyển từ kho B đến điểm D.
Gọi x_BE là lượng hàng (tấn) vận chuyển từ kho B đến điểm E.

Ràng buộc không âm: x_AC, x_AD, x_AE, x_BC, x_BD, x_BE >= 0.

Bước 2: Xây dựng hàm mục tiêu

Mục tiêu là tối thiểu hóa tổng chi phí vận chuyển. Chi phí vận chuyển từ mỗi cặp (kho, điểm bán) bằng lượng hàng vận chuyển nhân với chi phí đơn vị tương ứng trong bảng.

Tổng chi phí Z = 5x_AC + 4x_AD + 6x_AE + 7x_BC + 6x_BD + 5x_BE.
Chúng ta muốn tìm các giá trị x_ij sao cho Z đạt giá trị nhỏ nhất.
Hàm mục tiêu: Min Z = 5x_AC + 4x_AD + 6x_AE + 7x_BC + 6x_BD + 5x_BE

Bước 3: Thiết lập các ràng buộc

Có hai loại ràng buộc chính: ràng buộc về khả năng cung cấp của kho và ràng buộc về nhu cầu của điểm bán.

• Ràng buộc về khả năng cung cấp (tại mỗi kho, tổng lượng hàng đi ra không vượt quá khả năng cung cấp):

  • Tại kho A: Lượng hàng đi từ A đến C, D, E không vượt quá 150 tấn.
    x_AC + x_AD + x_AE <= 150
  • Tại kho B: Lượng hàng đi từ B đến C, D, E không vượt quá 200 tấn.
    x_BC + x_BD + x_BE <= 200

• Ràng buộc về nhu cầu (tại mỗi điểm bán, tổng lượng hàng nhận được phải đủ nhu cầu):

  • Tại điểm C: Lượng hàng từ A và B đến C phải đủ 100 tấn.
    x_AC + x_BC = 100
  • Tại điểm D: Lượng hàng từ A và B đến D phải đủ 120 tấn.
    x_AD + x_BD = 120
  • Tại điểm E: Lượng hàng từ A và B đến E phải đủ 130 tấn.
    x_AE + x_BE = 130

Lưu ý quan trọng: Tổng khả năng cung cấp (150 + 200 = 350 tấn) bằng tổng nhu cầu (100 + 120 + 130 = 350 tấn). Đây là bài toán vận tải cân bằng. Khi bài toán cân bằng, các ràng buộc cung cấp cũng có thể viết dưới dạng dấu bằng, vì tổng lượng hàng đi ra từ các kho buộc phải bằng tổng lượng hàng cần đến các điểm bán. Tuy nhiên, viết dưới dạng <= vẫn đúng và tổng quát hơn cho cả bài toán không cân bằng (khi đó sẽ có kho thừa hoặc điểm thiếu hàng).

Tóm lại, mô hình QHTT của bài toán vận tải là:

Min Z = 5x_AC + 4x_AD + 6x_AE + 7x_BC + 6x_BD + 5x_BE
Với các ràng buộc:
x_AC + x_AD + x_AE <= 150 (hoặc = 150, do cân bằng)
x_BC + x_BD + x_BE <= 200 (hoặc = 200, do cân bằng)
x_AC + x_BC = 100
x_AD + x_BD = 120
x_AE + x_BE = 130
x_AC, x_AD, x_AE, x_BC, x_BD, x_BE >= 0

Bước 4: Giải bài toán

Bài toán này có 6 biến (nhiều hơn 2), nên không thể giải bằng phương pháp đồ thị. Chúng ta cần sử dụng phương pháp đơn hình (Simplex Method) hoặc các thuật toán chuyên biệt cho bài toán vận tải (như phương pháp góc tây bắc, chi phí nhỏ nhất, hay phương pháp bước nhảy).

Để giải chi tiết bằng phương pháp đơn hình sẽ rất dài và phức tạp, vượt ra ngoài khuôn khổ trình bày chi tiết từng bước cho một bài tập mẫu trong bài viết này. Tuy nhiên, mô hình đã được lập hoàn chỉnh. Việc còn lại là “nhập” mô hình này vào một công cụ giải QHTT (phần mềm như Solver trong Excel, các thư viện toán học trong Python/R, hoặc phần mềm chuyên dụng như LINGO, CPLEX…) hoặc áp dụng thuật toán Simplex một cách cẩn thận.

Kết quả sau khi giải bằng phần mềm hoặc thuật toán chuyên dụng (được tính toán ngoài luồng trình bày chi tiết Simplex tại đây):

Một phương án tối ưu có thể là:
x_AC = 100
x_AD = 50
x_AE = 0
x_BC = 0
x_BD = 70
x_BE = 130

Bước 5: Biện luận kết quả

Phương án vận chuyển tối ưu để tổng chi phí nhỏ nhất là:

• Vận chuyển 100 tấn từ kho A đến điểm C.
• Vận chuyển 50 tấn từ kho A đến điểm D.
• Vận chuyển 0 tấn từ kho A đến điểm E. (Tức là không vận chuyển từ A đến E)
• Vận chuyển 0 tấn từ kho B đến điểm C. (Tức là không vận chuyển từ B đến C)
• Vận chuyển 70 tấn từ kho B đến điểm D.
• Vận chuyển 130 tấn từ kho B đến điểm E.

Kiểm tra ràng buộc:

• Kho A cung cấp: 100 + 50 + 0 = 150 tấn (đủ khả năng cung cấp).
• Kho B cung cấp: 0 + 70 + 130 = 200 tấn (đủ khả năng cung cấp).
• Điểm C nhận: 100 + 0 = 100 tấn (đủ nhu cầu).
• Điểm D nhận: 50 + 70 = 120 tấn (đủ nhu cầu).
• Điểm E nhận: 0 + 130 = 130 tấn (đủ nhu cầu).
• Tất cả x_ij đều không âm. Các ràng buộc đều được thỏa mãn.

Tính tổng chi phí tối thiểu:
Z = 5100 + 450 + 60 + 70 + 670 + 5130
Z = 500 + 200 + 0 + 0 + 420 + 650
Z = 1770 (nghìn đồng)

Vậy, tổng chi phí vận chuyển tối thiểu là 1.770.000 đồng.

### Bài Tập 3: Bài Toán Pha Trộn (Hỗn Hợp)

Đề bài:

Một công ty sản xuất thức ăn gia súc cần pha trộn hai loại nguyên liệu X và Y để tạo ra một loại thức ăn hỗn hợp.
Thành phần dinh dưỡng của mỗi loại nguyên liệu và chi phí như sau:

Loại thức ăn hỗn hợp cần đáp ứng các yêu cầu dinh dưỡng tối thiểu: chứa ít nhất 18% Protein và ít nhất 15% Chất béo.
Công ty muốn sản xuất 1000 kg thức ăn hỗn hợp.
Hãy xác định lượng mỗi loại nguyên liệu cần sử dụng để tổng chi phí sản xuất 1000 kg thức ăn hỗn hợp là nhỏ nhất.

Phân tích bài toán:

• Mục tiêu: Tối thiểu hóa chi phí sản xuất 1000 kg hỗn hợp.
• Ràng buộc: Tổng khối lượng là 1000 kg, yêu cầu dinh dưỡng tối thiểu.
• Đối tượng: Lượng nguyên liệu X và Y sử dụng.

Lời giải chi tiết:

Bước 1: Xác định biến quyết định

Gọi x là lượng nguyên liệu X cần sử dụng (kg).
Gọi y là lượng nguyên liệu Y cần sử dụng (kg).
Ràng buộc không âm: x >= 0, y >= 0.

Bước 2: Xây dựng hàm mục tiêu

Mục tiêu là tối thiểu hóa tổng chi phí để sản xuất 1000 kg hỗn hợp.
Chi phí sử dụng x kg nguyên liệu X là 8x (nghìn đồng).
Chi phí sử dụng y kg nguyên liệu Y là 10y (nghìn đồng).
Tổng chi phí Z = 8x + 10y.
Chúng ta muốn tìm (x, y) sao cho Z đạt giá trị nhỏ nhất.
Hàm mục tiêu: Min Z = 8x + 10y

Bước 3: Thiết lập các ràng buộc

• Ràng buộc về tổng khối lượng:
  Tổng khối lượng nguyên liệu X và Y phải bằng 1000 kg.
  x + y = 1000

• Ràng buộc về thành phần dinh dưỡng (Protein):
  Trong 1000 kg hỗn hợp, lượng Protein từ nguyên liệu X là 20% của x = 0.20x (kg).
  Trong 1000 kg hỗn hợp, lượng Protein từ nguyên liệu Y là 15% của y = 0.15y (kg).
  Tổng lượng Protein trong 1000 kg hỗn hợp là 0.20x + 0.15y.
  Lượng Protein này phải đạt ít nhất 18% của tổng khối lượng 1000 kg, tức là 0.18 * 1000 = 180 kg.
  Ràng buộc Protein: 0.20x + 0.15y >= 180

• Ràng buộc về thành phần dinh dưỡng (Chất béo):
  Trong 1000 kg hỗn hợp, lượng Chất béo từ nguyên liệu X là 10% của x = 0.10x (kg).
  Trong 1000 kg hỗn hợp, lượng Chất béo từ nguyên liệu Y là 18% của y = 0.18y (kg).
  Tổng lượng Chất béo trong 1000 kg hỗn hợp là 0.10x + 0.18y.
  Lượng Chất béo này phải đạt ít nhất 15% của tổng khối lượng 1000 kg, tức là 0.15 * 1000 = 150 kg.
  Ràng buộc Chất béo: 0.10x + 0.18y >= 150

Tóm lại, mô hình QHTT của bài toán pha trộn là:

Min Z = 8x + 10y
Với các ràng buộc:
x + y = 1000
0.20x + 0.15y >= 180
0.10x + 0.18y >= 150
x >= 0, y >= 0

Bước 4: Giải bài toán

Đây là bài toán có 2 biến (x và y), có thể giải bằng phương pháp đồ thị. Tuy nhiên, ràng buộc x + y = 1000 là một phương trình, không phải bất phương trình. Điều này có nghĩa là miền chấp nhận được không phải là một miền đa giác, mà là một đoạn thẳng (phần của đường thẳng x + y = 1000 nằm trong góc phần tư thứ nhất và thỏa mãn các ràng buộc khác).

1. Vẽ đường thẳng x + y = 1000:
   Cho x = 0 => y = 1000. Điểm (0, 1000).
   Cho y = 0 => x = 1000. Điểm (1000, 0).
   Nối hai điểm này.

2. Vẽ và xác định miền thỏa mãn các bất phương trình:

   • Bất phương trình 0.20x + 0.15y >= 180:
     Vẽ đường thẳng 0.20x + 0.15y = 180. Tương đương 20x + 15y = 18000, hay 4x + 3y = 3600.
     Cho x = 0 => 3y = 3600 => y = 1200. Điểm (0, 1200).
     Cho y = 0 => 4x = 3600 => x = 900. Điểm (900, 0).
     Nối hai điểm này. Miền 0.20x + 0.15y >= 180 là miền nằm trên đường thẳng này (thử điểm gốc (0,0): 0 >= 180, sai, vậy miền giải nằm phía đối diện gốc tọa độ).
   • Bất phương trình 0.10x + 0.18y >= 150:
     Vẽ đường thẳng 0.10x + 0.18y = 150. Tương đương 10x + 18y = 15000, hay 5x + 9y = 7500.
     Cho x = 0 => 9y = 7500 => y = 7500/9 = 2500/3 ~ 833.33. Điểm (0, 2500/3).
     Cho y = 0 => 5x = 7500 => x = 1500. Điểm (1500, 0).
     Nối hai điểm này. Miền 0.10x + 0.18y >= 150 là miền nằm trên đường thẳng này (thử điểm gốc (0,0): 0 >= 150, sai, vậy miền giải nằm phía đối diện gốc tọa độ).

3. Xác định miền chấp nhận được:
   Miền chấp nhận được là phần của đoạn thẳng x + y = 1000 (trong góc phần tư thứ nhất) mà cũng thỏa mãn cả hai bất phương trình Protein và Chất béo.
   Chúng ta cần tìm giao điểm của đường thẳng x + y = 1000 với hai đường thẳng 4x + 3y = 3600 và 5x + 9y = 7500. Các giao điểm này sẽ là các “đầu mút” của đoạn thẳng miền chấp nhận được.

   • Giao điểm của x + y = 1000 và 4x + 3y = 3600:
     Từ x + y = 1000 => y = 1000 – x.
     Thay vào 4x + 3y = 3600: 4x + 3(1000 – x) = 3600 => 4x + 3000 – 3x = 3600 => x = 600.
     y = 1000 – 600 = 400.
     Điểm giao là (600, 400). Kiểm tra: x=600, y=400 thỏa mãn x,y>=0.
     0.20600 + 0.15400 = 120 + 60 = 180 >= 180 (thỏa mãn Protein).
     0.10600 + 0.18400 = 60 + 72 = 132. 132 >= 150 (KHÔNG thỏa mãn Chất béo).
     Vậy điểm (600, 400) không thuộc miền chấp nhận được. Nó nằm trên ranh giới Protein nhưng nằm dưới ranh giới Chất béo.

   • Giao điểm của x + y = 1000 và 5x + 9y = 7500:
     Từ x + y = 1000 => y = 1000 – x.
     Thay vào 5x + 9y = 7500: 5x + 9(1000 – x) = 7500 => 5x + 9000 – 9x = 7500 => -4x = 7500 – 9000 => -4x = -1500 => x = 1500/4 = 375.
     y = 1000 – 375 = 625.
     Điểm giao là (375, 625). Kiểm tra: x=375, y=625 thỏa mãn x,y>=0.
     0.20375 + 0.15625 = 75 + 93.75 = 168.75. 168.75 >= 180 (KHÔNG thỏa mãn Protein).
     Vậy điểm (375, 625) không thuộc miền chấp nhận được. Nó nằm trên ranh giới Chất béo nhưng nằm dưới ranh giới Protein.

   Vậy miền chấp nhận được trên đường thẳng x + y = 1000 là đoạn thẳng nằm giữa hai điểm P và Q, trong đó P và Q là các điểm “góc” được tạo bởi sự giao nhau của đường thẳng x+y=1000 với các đường biên của bất phương trình (hoặc các trục tọa độ nếu có).

   Chúng ta cần tìm các điểm trên đường x + y = 1000 thỏa mãn cả hai:
   0.20x + 0.15(1000-x) >= 180 => 0.20x + 150 – 0.15x >= 180 => 0.05x >= 30 => x >= 600.
   0.10x + 0.18(1000-x) >= 150 => 0.10x + 180 – 0.18x >= 150 => -0.08x >= -30 => 0.08x <= 30 => x <= 30/0.08 = 3000/8 = 375.

   Ồ, kết quả là x >= 600 và x <= 375. Điều này mâu thuẫn! x không thể vừa lớn hơn hoặc bằng 600 lại vừa nhỏ hơn hoặc bằng 375 được.

   Kiểm tra lại phép tính:
   Ràng buộc Protein: 0.20x + 0.15y >= 180 => 4x + 3y >= 3600. Với y = 1000 – x => 4x + 3(1000-x) >= 3600 => 4x + 3000 – 3x >= 3600 => x >= 600.
   Ràng buộc Chất béo: 0.10x + 0.18y >= 150 => 10x + 18y >= 15000 => 5x + 9y >= 7500. Với y = 1000 – x => 5x + 9(1000-x) >= 7500 => 5x + 9000 – 9x >= 7500 => -4x >= -1500 => 4x <= 1500 => x <= 375.

   Hmm, có vẻ như với tổng khối lượng cố định là 1000 kg, không có sự pha trộn nào từ X và Y có thể đồng thời đáp ứng cả hai yêu cầu dinh dưỡng tối thiểu 18% Protein và 15% Chất béo.

   Giả định lại đề bài hoặc kết luận về tính khả thi: Có hai khả năng:
   a) Đề bài có thể có sai sót về số liệu (ví dụ: yêu cầu dinh dưỡng quá cao so với nguyên liệu).
   b) Hoặc kết luận của bài toán là: Không có phương án nào thỏa mãn tất cả các ràng buộc. Miền chấp nhận được là rỗng. Công ty không thể sản xuất 1000 kg thức ăn hỗn hợp đáp ứng yêu cầu chỉ bằng hai loại nguyên liệu X và Y với tỷ lệ như vậy.

   Để bài toán có lời giải khả thi, chúng ta sẽ điều chỉnh nhẹ yêu cầu hoặc số liệu. Giả sử yêu cầu Protein là 16% thay vì 18%.

   Điều chỉnh đề bài (Giả định để có lời giải): Yêu cầu Protein tối thiểu là 16%. Ràng buộc Protein mới: 0.20x + 0.15y >= 0.16 * 1000 = 160.
   Hay 20x + 15y >= 16000 => 4x + 3y >= 3200.
   Với y = 1000 – x => 4x + 3(1000-x) >= 3200 => 4x + 3000 – 3x >= 3200 => x >= 200.

   Ràng buộc Chất béo (giữ nguyên): 5x + 9y >= 7500. Với y = 1000 – x => 5x + 9(1000-x) >= 7500 => 5x + 9000 – 9x >= 7500 => -4x >= -1500 => x <= 375.

   Vậy với đề bài điều chỉnh, các ràng buộc là:
   x + y = 1000
   x >= 200 (từ Protein)
   x <= 375 (từ Chất béo)
   x >= 0, y >= 0

   Từ x + y = 1000 và x >= 0, y >= 0, ta có 0 <= x <= 1000 và 0 <= y <= 1000.
   Kết hợp với x >= 200 và x <= 375, ta có miền chấp nhận được cho x là [200, 375].
   Vì x + y = 1000, khi x tăng thì y giảm.
   Khi x = 200, y = 800. Điểm (200, 800).
   Khi x = 375, y = 625. Điểm (375, 625).
   Miền chấp nhận được trên đường thẳng x + y = 1000 là đoạn thẳng nối hai điểm (200, 800) và (375, 625).

4. Tìm điểm tối ưu:
   Chúng ta cần tối thiểu hóa Z = 8x + 10y trên đoạn thẳng này.
   Thay y = 1000 – x vào hàm mục tiêu:
   Z = 8x + 10(1000 – x) = 8x + 10000 – 10x = 10000 – 2x.
   Để Z nhỏ nhất, chúng ta cần 2x lớn nhất, tức là x lớn nhất trong miền chấp nhận được.
   Miền chấp nhận được cho x là [200, 375].
   Giá trị lớn nhất của x trong miền này là x = 375.

   Khi x = 375, y = 1000 – 375 = 625.
   Điểm tối ưu là (375, 625).

Bước 5: Biện luận kết quả (với đề bài đã điều chỉnh Protein 16%)

Để sản xuất 1000 kg thức ăn hỗn hợp với chi phí nhỏ nhất, công ty nên sử dụng 375 kg nguyên liệu X và 625 kg nguyên liệu Y.

Kiểm tra ràng buộc tại điểm tối ưu (375, 625):

• Tổng khối lượng: 375 + 625 = 1000 kg (đúng).
• Protein: 0.20375 + 0.15625 = 75 + 93.75 = 168.75 kg. Tỷ lệ Protein = (168.75 / 1000) * 100% = 16.875%. 16.875% >= 16% (thỏa mãn).
• Chất béo: 0.10375 + 0.18625 = 37.5 + 112.5 = 150 kg. Tỷ lệ Chất béo = (150 / 1000) * 100% = 15%. 15% >= 15% (thỏa mãn).
• x >= 0, y >= 0 (thỏa mãn).

Tính tổng chi phí tối thiểu:
Z = 8375 + 10625
Z = 3000 + 6250
Z = 9250 (nghìn đồng)

Vậy, tổng chi phí sản xuất 1000 kg thức ăn hỗn hợp với yêu cầu Protein 16% và Chất béo 15% là 9.250.000 đồng, sử dụng 375 kg nguyên liệu X và 625 kg nguyên liệu Y.

Bài toán pha trộn ban đầu với yêu cầu Protein 18% đã cho thấy một điều quan trọng: không phải bài toán nào đặt ra cũng có phương án giải khả thi. Việc mô hình hóa và giải toán giúp chúng ta phát hiện ra những “nút thắt” hay những mục tiêu “bất khả thi” dựa trên các ràng buộc hiện có.

Bạn có thể tìm hiểu thêm về đồ án kết cấu thép – một lĩnh vực khác đòi hỏi việc tính toán kỹ lưỡng và tối ưu hóa, dù là về vật liệu hay cấu trúc, và đôi khi cũng có thể áp dụng các nguyên tắc của tối ưu hóa.

Các “Bí Kíp” Khi Luyện “Bài Tập Quy Hoạch Tuyến Tính Có Lời Giải”

“Học thầy không tày học bạn”, mà học lý thuyết không tày học làm bài tập. Để “nuốt trôi” QHTT, ngoài việc làm các bài tập quy hoạch tuyến tính có lời giải, bạn nên:

• Hiểu rõ ý nghĩa từng dòng trong mô hình: Biến x1 đại diện cho cái gì? Bất phương trình 2×1 + x2 <= 100 nói lên điều gì trong bài toán thực tế? Hàm mục tiêu Z = 30×1 + 40×2 thể hiện cái gì cần tối ưu? Nắm chắc điều này giúp bạn mô hình hóa chính xác và biện luận kết quả đúng đắn.
• Vẽ đồ thị (nếu có 2 biến) thật cẩn thận: Đây là cách trực quan nhất để hiểu về miền chấp nhận được và tại sao phương án tối ưu lại nằm ở các đỉnh. Một nét vẽ sai có thể “dẫn bạn đi một dặm”.
• Làm quen với phương pháp đơn hình: Dù có phần mềm hỗ trợ, hiểu nguyên lý của Simplex giúp bạn “kiểm soát” quá trình giải và hiểu ý nghĩa của các bảng đơn hình trung gian. Ban đầu có thể thấy “choáng ngợp”, nhưng cứ làm đi làm lại vài bài mẫu có lời giải chi tiết, bạn sẽ quen dần.
• Sử dụng phần mềm: Khi gặp bài toán lớn, nhiều biến, việc giải tay bằng Simplex là “bất khả thi”. Hãy tập dùng Solver trong Excel hoặc các công cụ khác. Tuy nhiên, đừng “lạm dụng” nó khi mới bắt đầu. Hãy chắc chắn bạn hiểu cách mô hình hóa trước khi dùng phần mềm.
• Đừng nản lòng khi “bí”: Gặp một bài toán khó, “vò đầu bứt tai” mãi không ra là chuyện thường tình. Hãy xem lời giải (nếu có) hoặc hỏi bạn bè, thầy cô. Quan trọng là hiểu được tại sao mình sai và cách sửa.
• Tập tự mình đặt ra bài toán: Dựa trên các cấu trúc bài toán mẫu (sản xuất, vận tải, pha trộn…), hãy thử thay đổi số liệu, thêm bớt ràng buộc để tạo ra bài toán của riêng bạn rồi tự giải. Điều này giúp bạn nắm vững cấu trúc mô hình.

“Quy hoạch tuyến tính không chỉ là tìm con số tối ưu. Quan trọng hơn là quá trình tư duy để chuyển một vấn đề phức tạp trong thực tế thành một mô hình toán học rõ ràng. Việc luyện tập bài tập có lời giải chính là cách rèn luyện khả năng mô hình hóa và giải quyết vấn đề này.” – PGS.TS. Nguyễn Văn An, Chuyên gia Tối ưu hóa.

Lời khuyên từ chuyên gia “đã chứng kiến” không ít người “toát mồ hôi hột” với QHTT càng khẳng định tầm quan trọng của việc thực hành.

Những “Cạm Bẫy” Thường Gặp Khi Giải Bài Tập Quy Hoạch Tuyến Tính

Đi trên con đường chinh phục QHTT, bạn có thể “sa chân” vào một vài “hố” phổ biến:

• Mô hình hóa sai: Đây là “tai họa” lớn nhất. Sai ngay từ bước đặt biến, viết hàm mục tiêu hay ràng buộc thì mọi công sức phía sau đều “đổ sông đổ biển”. Thường gặp là nhầm lẫn dấu của bất phương trình (<= thay vì >= hoặc ngược lại), hoặc bỏ sót ràng buộc không âm.
• Sai sót trong tính toán: Khi giải bằng đồ thị (tìm giao điểm) hay bằng Simplex (các phép biến đổi dòng, cột), chỉ cần một phép tính sai là “hỏng” cả bài. Sự cẩn thận, tỉ mỉ là cực kỳ cần thiết.
• Nhầm lẫn phương pháp giải: Cố gắng dùng đồ thị cho bài toán 3 biến, hoặc dùng Simplex khi chưa hiểu rõ nguyên lý đều có thể khiến bạn “loay hoay” không lối thoát.
• Biện luận sai kết quả: Tìm ra x1=50, x2=0 là tối ưu, nhưng lại không giải thích được ý nghĩa của con số này trong ngữ cảnh bài toán sản xuất ban đầu (ví dụ: chỉ nên sản xuất 50 sản phẩm A, không sản xuất sản phẩm B để tối đa lợi nhuận).

Việc xem xét kỹ lưỡng các bài tập quy hoạch tuyến tính có lời giải giúp bạn thấy được những sai lầm tiềm ẩn trong quá trình giải của chính mình và học hỏi cách “né tránh” chúng.

Quy Hoạch Tuyến Tính Có “Gần Gũi” Với Đời Sống Không?

Đừng nghĩ QHTT chỉ “ẩn mình” trong sách vở hay các phần mềm phức tạp. Nó xuất hiện “nhan nhản” quanh ta đấy:

• Lập kế hoạch sản xuất: Như ví dụ trên, các nhà máy dùng QHTT để quyết định sản xuất bao nhiêu loại sản phẩm khác nhau với nguồn lực (máy móc, nhân công, nguyên liệu) có hạn để đạt lợi nhuận cao nhất.
• Phân bổ ngân sách: Các công ty, chính phủ dùng QHTT để phân bổ tiền cho các dự án khác nhau sao cho hiệu quả nhất.
• Lập thực đơn (Diet Problem): Xác định lượng mỗi loại thực phẩm cần ăn để đạt đủ dinh dưỡng cần thiết với chi phí thấp nhất (hoặc ngon nhất!).
• Quản lý logistics và chuỗi cung ứng: Tối ưu hóa việc vận chuyển hàng hóa từ kho đến cửa hàng, xác định vị trí kho bãi, lập lịch trình giao hàng để giảm chi phí và thời gian.
• Tối ưu hóa danh mục đầu tư: Các nhà phân tích tài chính sử dụng QHTT để chọn tỷ lệ đầu tư vào các loại tài sản khác nhau nhằm tối đa hóa lợi nhuận kỳ vọng với mức rủi ro chấp nhận được.

Ngay cả việc lập kế hoạch ôn thi, phân bổ thời gian học cho các môn đề thi hsg sinh 8 hay các môn khác cũng có thể “mô hình hóa” thành bài toán tối ưu, dù có thể không dùng QHTT một cách “chuẩn sách giáo khoa”. Ý tưởng cốt lõi vẫn là phân bổ nguồn lực (thời gian, năng lượng) có hạn để đạt mục tiêu (điểm cao nhất) dựa trên các ràng buộc (lịch học, khả năng tiếp thu).

Hay như việc tính toán khi nào là ngày đẹp tháng 9 năm 2021 để làm việc gì đó cũng là một dạng “chọn lựa tối ưu” dựa trên các tiêu chí nhất định, dù không phải là bài toán tuyến tính. Tư duy logic và cấu trúc vấn đề là điểm chung.

Ngay cả trong một bài toán tưởng chừng đơn giản như giải phương trình lượng giác sin x + cos x =, chúng ta cũng đang đi tìm giá trị của biến (x) thỏa mãn một ràng buộc nhất định (phương trình). Dù khác về bản chất toán học, tinh thần tìm kiếm “nghiệm” hoặc “phương án” vẫn là trung tâm.

Kết Bài: Hành Trình Chinh Phục QHTT Tiếp Tục Với “Bài Tập Quy Hoạch Tuyến Tính Có Lời Giải”

Quy hoạch tuyến tính là một công cụ tuyệt vời, nhưng để sử dụng thành thạo, bạn không thể chỉ dừng lại ở việc hiểu lý thuyết. Việc “cày” các bài tập quy hoạch tuyến tính có lời giải chính là con đường ngắn nhất để bạn biến kiến thức sách vở thành kỹ năng thực tế.

Bài viết này đã cùng bạn đi qua những khái niệm cơ bản, cách tiếp cận bài toán và “mổ xẻ” chi tiết một vài dạng bài tập quy hoạch tuyến tính có lời giải điển hình. Hy vọng rằng, với những ví dụ minh họa cụ thể và lời giải “cầm tay chỉ việc”, bạn đã cảm thấy QHTT bớt “đáng sợ” hơn và có thêm động lực để tiếp tục luyện tập.

Hãy coi mỗi bài tập là một thử thách nhỏ để bạn rèn luyện khả năng mô hình hóa, tính toán và biện luận. Đừng ngại sai, vì sai là cơ hội để học. Càng làm nhiều, càng va vấp nhiều, bạn sẽ càng “nhạy bén” hơn, khả năng “nhìn thấu” bản chất bài toán sẽ càng được nâng cao.

Nếu bạn có bài tập nào “hóc búa” hoặc muốn thảo luận sâu hơn về một khía cạnh nào đó của QHTT, đừng ngần ngại tìm kiếm thêm tài nguyên hoặc trao đổi với bạn bè, thầy cô. Baocaothuctap.net sẽ luôn cố gắng mang đến những nội dung hữu ích, giúp bạn trên con đường học tập và nghiên cứu.

Chúc bạn thành công trên hành trình chinh phục bài tập quy hoạch tuyến tính có lời giải và ứng dụng nó một cách hiệu quả trong học tập cũng như công việc sau này!