Tiểu luận qui hoạch tuyến tính

MỞ ĐẦU
PHẦN I: LÝ DO.
Loài người xuất hiện trên trái đất cách đây hàng triệu năm, nhưng chỉ cách đây khoảng 5 hoặc 6 nghìn năm con người mới bắt đầu có những hoạt động trí óc. Từ khi ngôn ngữ ra đời con người đã biết đến những khái niệm cơ bản ban đầu về toán học. Cùng với sự tiến bộ về kinh tế - xã hội của loài người, đã thút đẩy toán học từng bước phát triển nhảy vọt. Nhất là khi con người biết tạo ra sản phẩm cần thiết để phục vụ cho nhu cầu của đời sống xã hội thì việc trao đổi hàng hóa cần có sự tính toán.
Không những thế, ngay từ khi con người biết suy nghĩ để tìm cách hành động sao cho có lợi nhất cho mình theo những mục đích xác định. Những yêu cầu cấp bách của sự phát triển nền kinh tế và quốc phòng lại càng làm nảy sinh những ý tưởng tương tự. Do đó đã xuất hiện một bài toán cần phải giải quyết, đó là bài toán về tìm phương án tối ưu.
Để giải quyết một cách có hiệu quả bài toán ấy, trước hết cần phải xây dựng một mô hình toán học cho nó, trên đó thể hiện được bản chất của mỗi đối tượng đã được khảo xác và sự liện quan cần phải tôn trọng giữa chúng; ngoài ra, dường như cần phải chỉ rõ mục tiêu mong muốn đạt được. Bài toán tìm quyết định tối ưu với mô hình toán học đã được xây dựng được gọi là bài toán quy hoạch toán học hay bài toán tối ưu. Sự liên quan giữa các đối tượng đã được khảo sát trong quá trình xây dựng mô hình toán học thường được thể hiện dưới dạng một hệ phương trình và bất phương trình, coi đó như là những điều kiện ( hay ràng buộc ) không thể bỏ qua. Nếu tất cả các hàm số có mặt trong bài toán ấy là các hàm tuyến tính thì ta có bài toán quy hoạch tuyến tính.
ở phần quy hoạch tuyến tính này chỉ nghiên cứu về kiến thức ban đầu của phần quy hạch tuyến tính. Đó chính là nội dung của chương I
PHẦN II: NỘI DUNG
1./ CƠ SỞ LÝ LUẬN.
Quy hoạch tuyến tính là một bộ phận cơ bản và có nhiều ứng dụng trong thực tiển của tối ưu hóa. Sự ra đời của quy hoạch tuyến tính nói riêng và quy hoạch toán học nói chung có thể coi vào năm 1939.
Nội dung của môn học nhằm đáp ứng được yêu cầu cung cấp những kiến thức và thuật toán cơ bản của quy hoạch tuyến tính. Phương pháp đơn hình và thuật toán của nó, do Dantzig đề xuất năm 1947, cho đến ngày nay vẫn được coi là phương pháp tổng quát và được sử dụng nhiều nhất để giải bài toán quy hoạch tuyến tính.
Có những phương pháp khác nhau để giải bài toán vận tải, tuy nhiên thuật toán của chúng có tên gọi là thuật toán thế vị.
Các kiến thức của chương I

Dạng tổng quát của bài toán quy hoạch tuyến tính :
Tìm vectơ x* = ( x1, x2, …, xn ) sao cho tại đó


f(x) là hàm mục tiêu; các ràng buộc (2) và (3) là ràng buộc cưỡng bức; ràng buộc (4) là ràng buộc tự nhiên.
Mỗi vectơ x* = ( x1, x2, …, xn ) là một phương án.phương án mà tại đó hàm mục tiêu đạt giá trị nhỏ nhất ( lớn nhất ) gọi là phương án tối ưu. Khi đó x* là giá trị tối ưu của hàm mục tiêu trên tập hợp các phương án.
Đối với bài toán quy hoach tuyến tính đòi hỏi giá trị của hàm mục tiêu đạt giá trị nhỏ nhất ( hoặc lớn nhất ) ta nói bài toán cực tiểu hay bài toán dạng min ( hoặc bài toán cực đại hay bài toán dạng max ). Phương án x* được gọi là phương án tốt hơn phương án x nếu: f(x*) < f(x) đối với bài toán cực tiểu ( f(x*) > f(x) đối với bài toán cực đại )
Giải bài toán quy hoạch tuyến tính được hiểu là tìm được dù chỉ một phương án tối ưu; hoặc là chứng tỏ trên tập phương án hàm mục tiêu không bị chặn, tức là hàm mục tiêu có thể nhận giá trị nhỏ tùy ý đối với bài toán dạng min ( hoặc lớn tùy ý đối với bài toán dạng max )
Ta có thể thấy rằng:


Viết dưới dạng gọn hơn


Đưa ra một số kí hiệu và quy ước:
+ A là ma trân cỡ (m,n) thì Ai = ( ai1,ai2, … , ain ) là vectơ dòng thứ i của A; Aj = ( a1j,a2j, … , amj ) là vectơ cột thứ j của A.
+ Nếu A = ( aij ) và B = ( bij ) là hai ma trận cùng kiểu thì A
B hiểu là aij
bij
i,