bài toán tìm cực đại (hoặc cực tiểu) của hàm mục tiêu là một hàm tuyến tính trên một tập hợp xác định bởi một hệ những bất phương trình tuyến tính:
xj 0 (j=1,2…,n)
trong đó cj, aij và bi là những số cho trước. Đây là trường hợp riêng của quy hoạch toán học. QHTT là mô hình toán học thường gặp trong nhiều bài toán kinh tế, kĩ thuật. Vấn đề là lựa chọn một phương án có thể có, chẳng hạn để trả lời câu hỏi: trong những điều kiện nhất định của thị trường, sản xuất những sản phẩm nào với số lượng bao nhiêu để tổng tiền lãi thu được là lớn nhất. Có thể cụ thể hoá một trường hợp điển hình như sau: Với cơ sở công nghệ sẵn có, ta có thể sản xuất n loại sản phẩm khác nhau từ m loại yếu tố sản xuất. Lượng yếu tố i (i = 1, 2,…, m) hiện có là bi; hệ số tiêu hao yếu tố i để sản xuất một đơn vị sản phẩm j là aij (i = 1, 2,…, m; j = 1, 2,…, n). Mỗi đơn vị sản phẩm j sẽ cho một số tiền lãi là cj (j = 1, 2,…, n). Hãy lập một phương án sản xuất trong phạm vi hiện có của các yếu tố sản xuất sao cho tổng tiền lãi thu được là lớn nhất.
Gọi xj (j = 1, 2,…, n) là số lượng sản phẩm j được sản xuất, khi đó tổng tiền lãi thể hiện dưới dạng một hàm của các biến xj là
f(x) =
Hàm này phải đạt trị số cực đại. Đồng thời tổng lượng tiêu hao yếu tố i là không vượt lượng hiện có bi, nghĩa là:
Cuối cùng sản phẩm j có thể được sản xuất hoặc không sản xuất, nên xj 0 (j = 1, 2,…, n). Tóm lại vấn đề nêu trên dẫn tới bài toán:
f(x) = (max)
xi 0 (j=1,2…,n)
Đó là một bài toán QHTT.
Bài toán QHTT tổng quát có dạng:
f(x) = min (max) (1)
(2)
Hai bộ phận cấu thành quan trọng của bài toán là: hàm f(x)(1) gọi là hàm mục tiêu, vì nó thể hiện cái đích ta cần đạt tới và hệ (2) gọi là hệ ràng buộc, chúng thể hiện những điều kiện hạn chế, trở ngại đối với việc đạt tới cái đích đó.
Mọi bài toán QHTT đều có thể quy về dạng chính tắc sau:
f(x) = min
xj 0 (j=1,2…,n
Ý nghĩa kinh tế của bài toán vượt khỏi phạm vi lựa chọn các phương án tác nghiệp nếu nó mô phỏng quá trình sản xuất của toàn bộ nền kinh tế quốc dân. Khi đó lời giải sẽ mang nhiều sắc thái định tính và xu thế hơn là chỉ rõ giải pháp cụ thể. Chẳng hạn có thể hiểu nội dung của bài toán dạng chính tắc như sau: giả sử trong nền kinh tế có n công nghệ sản xuất khác nhau, nếu dùng một đơn vị cường độ (mức độ sử dụng có thể đo bằng thời gian, công suất…) công nghệ j (j = 1, 2,…, n), tương ứng với một chi phí sản xuất là cj, để sản xuất loại sản phẩm i (i = 1, 2,…, m) ta sẽ thu được một lượng sản phẩm loại i là aij. Yêu cầu của xã hội về sản phẩm i là bi (i = 1, 2,…, m). Hãy xác định cường độ sử dụng xj các công nghệ j sao cho đáp ứng yêu cầu về sản phẩm với tổng chi phí nhỏ nhất.
