Giáo trình Toán kinh tế (Nghề: Kế toán doanh nghiệp) - CĐ Cơ Giới Ninh Bình

Chia sẻ: Calliope09 Calliope09 | Ngày: | Loại File: DOCX | Số trang:58

Thêm vào BST

Báo xấu

19
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình Toán kinh tế cung cấp cho người học các kiến thức: Đại số tuyến tính; Phương pháp đơn hình và bài toán đối ngẫu; Toán xác suất; Thống kê toán. Mời các bạn cùng tham khảo để nắm chi tiết nội dung giáo trình.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Toán kinh tế (Nghề: Kế toán doanh nghiệp) - CĐ Cơ Giới Ninh Bình

BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN TRƯỜNG CAO ĐẲNG CƠ GIỚI NINH BÌNH GIÁO TRÌNH MÔN HỌC: TOÁN KINH TẾ NGHỀ: KẾ TOÁN DOANH NGHIỆP TRÌNH ĐỘ: CAO ĐẲNG Ban hành kèm theo Quyết định số: /QĐTCGNB ngày…….tháng….năm 2017 của Trường cao đẳng nghề Cơ giới Ninh Bình
Ninh Bình, năm 20
TUYÊN BỐ BẢN QUYỀN Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. 3
LỜI NÓI ĐẦU Toán học và kinh tế là hai lĩnh vực có mối quan hệ gắn bó với nhau. Kinh tế là nguồn cảm hứng cho toán học thực hiện khả năng tiềm năng của mình, còn toán học là công cụ giúp cho việc phân tích, giải quyết các vấn đề kinh tế một cách chặt chẽ, hợp lý và hiệu quả. Toán kinh tế là việc nghiên cứu để mô tả các vấn đề kinh tế dưới dạng mô hình toán học thích hợp và từ góc độ toán học sẽ tìm ra lời giải cho mô hình đó, từ đó giúp các nhà kinh tế tìm ra các giải pháp tối ưu cho bài toán kinh tế. Để đáp ứng nhu cầu giảng dạy và học tập môn Toán kinh tế cho sinh viên hệ Cao đẳng, chúng tôi đó biên soạn cuốn giáo trình này. Giáo trình không đi sâu vào các vấn đề lý luận và các kỹ thuật toán học phức tạp mà chỉ tập trung trình bày những nội dung cơ bản và các thuật toán chính của lý thuyết tối ưu tuyến tính. Nhằm giúp sinh viên rèn luyện kỹ năng trong giáo trình có đầy đủ các ví dụ cụ thể mô tả từng tình huống, hướng dẫn tỉ mỉ toàn bộ quá trình giải quyết vấn đề. Nội dung giáo trình gồm 4 chương: Chương 1: Đại số tuyến tính Chương 2: Phương pháp đơn hình và bài toán đối ngẫu Chương 3: Toán xác suất Chương 4: Thống kê toán Mặc dù có nhiều cố gắng, nhưng giáo trình này chắc chắn không tránh khỏi những thiếu sót. Chúng tôi rất mong được bạn đọc góp ý để cuốn sách ngày càng hoàn thiện. Các tác giả An Thị Hạnh Đỗ Quang Khải Phạm Thị Hồng 4
MỤC LỤC GIÁO TRÌNH MÔN HỌC Tên môn học: Toán kinh tế Mã số môn học: MH 16 Vị trí, tính chất, ý nghĩa và vai trò của môn học: Vị trí: Môn học được bố trí giảng dạy sau các môn học chung. Tính chất: Là môn học giúp người học vận dụng tốt các môn học chuyên môn của nghề. Ý nghĩa và vai trò của môn học: + Chương trình trang bị cho sinh viên những kiến thức cơ bản về các mô hình kinh tế, các phương pháp tiếp cận khác nhau để lý giải sự tồn tại và vận động của quá trình kinh tế xã hội. + Trang bị cho sinh viên những kỹ năng tính toán thông qua việc giải quyết các bài toán, dựa vào bài toán có thế tiến hành phân tích và dự báo biến động trong nhiều lĩnh vực khác nhau như giá cả và tài chính. + Giúp cho sinh viên có những nhận thức cơ bản, có phương hướng đúng đắn và tự tin trong công tác tài chính thực tiễn sau khi tốt nghiệp ra trường. 5
+ Ngoài ra học sinh còn có năng lực để theo học liên thông lên các bậc học cao hơn để phát triển kiến thức và kỹ năng nghề. Mục tiêu môn học: Về kiến thức: + Trình bày được các kiến thức cơ bản về kinh tế học và công cụ toán học để xây dựng mô hình bài toán kinh tế; + Trình bày mối liên hệ định tính, định lượng giữa các biến số kinh tế trong nhiều lĩnh vực và sử dụng các phương pháp như: Phân tích cân bằng, phân tích tối ưu, quy hoạch tuyến tính, thống kê toán.... Về kỹ năng: + Xây dựng được mô hình bài toán kinh tế và phân tích được mô hình; + Giải được bài toán quy hoạch tuyến tính, xác suất và thống kê toán; + Kiểm định được các giả thuyết thống kê toán. Về năng lực tự chủ và trách nhiệm: Có phẩm chất đạo đức, kỷ luật tốt, có ý thức tự rèn luyện để nâng cao trình độ. Nội dung môn học: CHƯƠNG 1: ĐẠI SỐ TUYẾN TÍNH Mã chương: TKT 01 Giới thiệu: Trang bị cho người học những kiến thức chung về vectơ, ma trận, hướng dẫn người học các cách xác định giá trị định thức và phương pháp giải bài toán quy hoạch tuyến tính. Mục tiêu: Trình bày được khái niệm Vectơ n chiều và khái niệm về ma trận; Trình bày được các phép toán vectơ; Trình bày được cách xác định giá trị định thức; Giải được hệ phương trình và bài toán quy hoạch tuyến tính; Có ý thức học tập nghiêm túc, cẩn thận, chính xác. 6
Nội dung chính: 1. Vectơ n chiều và các phép tính 1.1. Định nghĩa Véc tơ là một đoạn thẳng được cấu thành bởi 2 yếu tố là độ dài véctơ và hướng. Véctơ n chiều là một bộ gồm n số thực được sắp xếp có thứ tự và ký hiệu là X = (x1, x2, ..., xn ) = {xj }; j = 1 n VD: X1 = (1, 4, 0) X2 = (3, 1, 2, 1, 5) Mỗi số xj gọi là thành phần hoặc toạ độ thứ j của x. x1 gọi là thành phần thứ 1 x2 gọi là thành phần thứ 2 ... xn gọi là thành phần thứ n Véctơ 0 là véctơ mà tất cả các thành phần đều bằng 0 Véctơ đối của véctơ X là X = ( x1, x2, ..., xn ) Véctơ bằng nhau: 2 véctơ có cùng thành phần được gọi là bằng nhau khi và chỉ khi các thành phần tương ứng của chúng bằng nhau từng đôi một. X = (x1, x2, ..., xn ); Y = (y1, y2, ..., yn ) Ta có X = Y x1 = y1 x2 = y2 ... xn = yn Như vậy, 2 véctơ bằng nhau là 2 véctơ có các thành phần giống hệt nhau Véctơ hàng là n số thực được sắp xếp theo hàng. Véctơ cột là n số thực được sắp xếp theo cột. Véctơ đơn vị là véctơ có 1 thành phần bằng 1 còn các thành phần còn lại đều bằng 0. 1.2. Các phép toán vectơ 1.2.1. Phép cộng 2 véctơ có cùng thành phần Ta gọi tổng của 2 véctơ n chiều X và Y là một véctơ n chiều Z mà các thành phần của nó là tổng các thành phần tương ứng của X và Y, nghĩa là: X + Y = Z; zj = xj + yj ; j = 1 n 7
Như vậy, phép cộng chỉ thực hiện được trên những véctơ có cùng số chiều và thực chất là qui về phép cộng các số, do đó nó cũng có đầy đủ các tính chất của phép cộng các số. 1.2.2. Phép nhân vectơ với một số Ta gọi tích của một vectơ n chiều X với 1 hằng số k là một vectơ n chiều ký hiệu kX mà các thành phần của nó là các thành phần tương ứng của X được nhân lên với k, nghĩa là: kX = kxj (j = 1 n) Thực chất của phép tính này cũng quy về phép tính trên các số. Các tính chất cơ bản của 2 phép tính trên: Tính giao hoán: X + Y = Y + X kX = Xk Tính kết hợp: (X + Y) + Z = Y + (X+ Z) k 1 (k2 X) = k 1 k2 X = (k 1 k2 ) X Luật phân bố: k (X + Y) = kY + kX (k 1 + k2) X = k 1X + k2 X X+ (X) = 0 X + 0 = X 1.2.3. Tích vô hướng của hai vectơ Ta gọi tích vô hướng của hai vectơ n chiều X và Y là một số thực được xác định bởi tổng các tích của các thành phần tương ứng của X và Y, ký hiệu (X, Y) (X, Y) = x1 y1 + x2 y2 + ... + xn yn = x j yj 1.3. Độc lập và phụ thuộc tuyến tính Cho một hệ thống m vectơ n chiều X1 , X2 , ..., Xm (I) Ta có đẳng thức vectơ: k1 X1 + k2 X2 + ...+ km Xm = 0 (*) xảy ra khi ta tìm được m số thực k1 ,k2 ,..., km Nếu có ít nhất một số k khác 0 thì Hệ (I) được gọi là phụ thuộc tuyến tính. Nếu k1 = k2 =...= km thì Hệ (I) được gọi là độc lập tuyến tính. Ví dụ: Có 4 vectơ: X1 = (1, 7, 3) X3 = (7, 9, 2) 8
X2 = (2, 4, 5) X4 = (1, 6, 8) Và tồn tại 4 số thực k1 ,k2 , k3, k4. Hệ độc lập hay phụ thuộc tuyến tính? LG: Ta xét: k1 X1 + k2 X2 + k3 X3 + k4 X4 = 0 k1 +2k2 + 7 k3 k4 = 0 7k1+ 4 k2 + 9k3 + 6 k4 = 0 3k1 5 k2 + 2k3 + 8 k4 = 0 Ta thấy, ứng với mỗi một k 4 thì cho một k1,k2 ,k3. Do đó, có ít nhất 1 k 0 nên hệ phụ thuộc tuyến tính 2. Ma trận 2.1. Các khái niệm cơ bản Bảng m và n số thực được xếp thành m hàng và n cột là ma trận cấp m n A = (aij)m n = a11 a12 ... a1n (i= 1 m) a21 a22 ... a2n (j = 1 n) ..................................... am1 am2 ... amn Mỗi số nằm trong cấu thành của ma trận gọi là một phần tử của ma trận aij là phần tử nằm ở hàng thứ i và cột thứ j của ma trận aii là đường chéo của ma trận * Một số ma trận đặc biệt: Ma trận 0: Là ma trận mà mọi phần tử đều bằng 0 Ma trận vuông: Là ma trận có số hàng bằng số cột (m=n) khi đó ta gọi là ma trận vuông cấp n Ma trận tam giác: Là ma trận vuông mà mọi phần tử nằm về một phía của đường chéo đều bằng 0 Ma trận đường chéo: Là ma trận vuông mà mọi phần tử nằm ngoài đường chéo đều bằng 0 Ma trận đơn vị: Là ma trận đường chéo mà mọi phần tử trên đường chéo đều bằng 1, ký hiệu E Ma trận chuyển vị: Nếu ta đổi hàng thành cột và cột thành hàng thì ta dược ma trận chuyển vị của ma trận đã cho. 9
2.2. Các phép tính ma trận 2.2.1. Phép cộng 2 ma trận Cho hai ma trận A, B cùng cấp m n. Tổng của hai ma trận là ma trận C cấp m n mà các phần tử của nó là tổng các phần tử tương ứng của A và B A = (aij)m n B = (bij)m n C = (cij)m n = (aij + bij) m n Ví dụ: A = 1 3 B = 2 1 4 7 8 3 A + B = 3 4 12 10 2.2.2. Phép nhân ma trận với một số thực Ta gọi tích của ma trận A = (aij)m n với một số thực k là ma trận cấp m n , ký hiệu là k.A mà các phần tử của nó là các phần tử tương ứng của A được nhân lên với k. Khi đó: C = (k.A) = (k. aij)m n Ví dụ: A = 1 3 k = 3 4 7 C = (k.A) = 3 9 12 21 * Trường hợp hiệu hai ma trận cùng cấp có thể được coi là phép cộng của một ma trận với ma trận đối của ma trận kia: A B = A + (B) 2.2.3. Phép nhân hai ma trận Cho A = (aij)m n ; B = (bjk)n k Phép nhân A với B là một ma trận C = (c ik)m p mà phần tử nằm trên hàng i cột k của nó được xác định bởi tổng các tích của các phần tử nằm trên hàng i của ma trận A (đứng trước) với các phần tử nằm trên cột k của ma trận B (đứng sau) nghĩa là: Cik = aij. bjk (i= 1 m; k = 1 p) 10
Phép nhân ma trận có điều kiện: Số cột của ma trận đứng trước phải bằng số hàng của ma trận đứng sau. Do đó, phép nhân hai ma trận không có tính chất giao hoán. Ví dụ: A = 2 1 1 ; B = 3 1 3 0 1 2 1 1 0 C = A.B = 9 3 103 3. Định thức 3.1. Cách xác định giá trị định thức +) Xác dịnh giá trị định thức cấp 2 A = a11 a12 = a11 . a22 a21a12 a21 a22 Ví dụ: A = 2 3 = 14 12 =2 4 7 +) Xác định giá trị định thức cấp 3 A = a11 a12 a13 = a11 a22 a33 + a23 a12a31 + a13 a21 a32 a11 a23 a32 a21 a22 a23 a21 a12a33 a13 a22 a31 a31 a32 a33 Ví dụ: A = 1 2 3 1 5 2 = 59 4 3 2 +) Xác định giá trị định thức cấp n Phần bù: Mij là phần bù của A khi ta xoá di dòng i và cột j của A Phần bù đại số của phần tử aij của định thức Alà: Aij = (1)i+jMij Ví dụ: A = 0 1 2 1 11
1 1 2 0 2 1 3 1 1 2 4 5 Phần bù đại số của A là A21 M21 = 1 2 1 = 3 1 3 1 2 4 5 A21 = (1) 2+1 (3) = 3 + Cách 1: Khai triển định thức Ví dụ: Khai triển định thức A A = 0.A11 + 1.A12 + 2. A13 + 1. A14 = 7 + 24 9 = 22 + Cách 2: Biến đổi định thức về dạng tam giác A = a11 a12 ...a1n = a11a22....ann 0 a22.. .a2n 0 0... ann 3.2. Tính chất của định thức Định thức của một ma trận vuông bằng định thức của ma trận chuyển vị của nó. Nếu có một dòng hoặc một cột gồm toàn số 0 thì giá trị định thức bằng 0 Nếu có hai dòng hoặc hai cột giống nhau thì giá trị định thức bằng 0 Nếu có hai dòng hoặc hai cột tỷ lệ với nhau thì giá trị định thức bằng 0 Nhân một dòng hoặc một cột của định thức với k thì giá trị định thức gấp lên k lần. Nếu ta đổi chỗ hai dòng hoặc hai cột của định thức cho nhau, còn các dòng và cột khác vẫn giữ nguyên vị trí thì giá trị định thức sẽ đổi dấu. Nếu ta cộng vào một dòng hay một cột của định thức với một dòng hay một cột khác sau khi đã nhân với một số thì giá trị định thức không thay đổi. 12
4. Ma trận nghịch đảo 4.1. Định nghĩa Cho ma trận A là ma trận vuông cấp n. Nếu hạng của ma trận bằng n thì ta nói là ma trận A không suy biến. Điều kiện để có ma trận nghịch đảo: Ma trận không suy biến. Do đó, ma trận vuông A không suy biến nếu A 0 * Định nghĩa: Ma trận A cấp n không suy biến bao giờ cũng tồn tại một ma trận cùng cấp A1 sao cho: A.A1 = A1.A = E A1 được gọi là ma trận nghịch đảo của A và là ma trận nghịch đảo duy nhất. 4.2. Cách tìm ma trận nghịch đảo Viết ma trận A/E Trên các hàng của ma trận này thực hiện các phép biến đổi sơ cấp 2 và 3 biến đổi sao cho A trở thành E, khi đó E sẽ trở thành A1 Nếu A không thể biến đổi thành E thì ma trận A suy biến và không tồn tại A1 Ví dụ: Tìm ma trận nghịch đảo của ma trận: A = 1 3 2 2 5 1 1 0 5 Thành lập ma trận A E và biến đổi như sau: 1 3 2 1 0 0 1 3 2 1 0 0 2 5 1 0 1 0 0 1 3 2 1 0 1 0 5 0 0 1 0 3 7 1 0 1 1 0 7 5 3 0 1 0 0 25/2 15/2 7/2 0 1 3 2 1 0 0 1 0 11/2 7/2 3/2 0 0 2 5 3 1 0 0 1 5/2 3/2 1/2 Như vậy: A1 = 25/2 15/2 7/2 11/2 7/2 3/2 5/2 3/2 1/2 13
5. Hệ phương trình tuyến tính 5.1. Khái niệm Hệ phương trình tuyến tính tổng quát gồm m phương trình và n ẩn có dạng: a11x1+ a12x2 +...+ a1nxn = b1 a21x1+ a22x2 +...+ a2nxn = b2 am1x1+ am2x2 +…+ amnxn = bm Ký hiệu: +) aij là hệ số của ẩn số xj trong phương trình i (i= 1 m; j = 1 n) A = (aij)m n gọi là ma trận hệ số của phương trình +) B = (b1, b2, …, bm) là vectơ vế phải của hệ phương trình +) X = (x1, x2,.., xn) là vectơ ẩn số của hệ phương trình +) A = A B là ma trận mở rộng của hệ phương trình +) Aj là vectơ cột j của ma trận A Hệ phương trình có thể viết dưới dạng: A.X = B X = A1.B Vectơ X thoả mãn mọi phương trình của hệ gọi là một nghiệm của hệ. Một hệ có ít nhất một nghiệm gọi là hệ có nghiệm hay hệ tương thích. Một hệ có một nghiệm duy nhất gọi là hệ xác định hay hệ Cramer. Một hệ có hơn một nghiệm gọi là hệ vô định hay không xác định. Một hệ không có nghiệm gọi là hệ vô nghiệm. 5.2. Phương pháp giải 5.2.1. Phương pháp Cramer Hệ có n phương trình n ẩn số thì hệ có nghiệm duy nhất gọi là hệ Cramer dj xj = (j = 1 n) d Trong đó: d : Định thức của ma trận hệ số dj : Định thức có cột thứ j là cột số hạng tự do, còn tất cả các cột còn lại như của định thức d. Aj được suy ra từ A bằng cách thay cột j của A bằng B Ví dụ: Giải hệ phương trình: x + y + 2z = 1 14
2x y + 2z = 4 4x + y + 4z = 2 LG: ta có: A = 1 1 2 = 6 ; A1 = 1 1 2 = 6 2 1 2 4 1 2 4 1 4 2 1 4 A2 = 1 1 2 = 12 ; A3 = 1 1 1 = 12 2 4 2 2 1 4 4 2 4 4 1 2 x = 1 ; y = 2 ; z =2 5.2.2. Dùng phương pháp biến đổi sơ cấp Đổi chỗ hai dòng hoặc hai cột cho nhau. Nhân tất cả các phần tử của một dòng hoặc một cột của ma trận với một hằng số khác 0. Nhân tất cả các phần tử của một dòng (cột) của ma trận với một hằng số khác 0 rồi cộng vào một dòng (cột) khác. VD1: Giải hệ phương trình: x1 + 5 x2 + 3 x3 = 0 x1 – 4 x2 + 2x3 = 9 3x1 – 12 x2 2x3 = 11 Thành lập ma trận mở rộng và biến đổi như sau: A = 1 5 3 0 1 5 3 0 1 5 3 0 1 4 2 9 0 1 5 9 0 1 5 9 3 12 2 11 0 3 7 11 0 0 8 16 Ta có: 8 x3 = 16 x3 = 2 x2 = 9 5 x3 = 1 ; x1 = 5x2 + 3 x3 = 1 Hệ phương trình có nghiệm duy nhất là: x = (1, 1, 2) VD2: Giải hệ phương trình: x1 + 2 x2 + 3 x3 – x4 = 8 3x1 – x2 5x3 + 4 x4 = 11 15
6x1 + 5 x2 + 4 x3 + x4 = 13 Thành lập ma trận mở rộng và biến đổi như sau: 1 2 3 1 8 1 2 3 1 8 1 2 3 1 8 A = 3 1 5 4 11 0 7 14 7 35 0 7 14 7 35 6 5 4 1 13 0 7 14 7 35 0 0 0 0 0 Như vậy, phương trình (3) bị loại khỏi hệ. Từ phương trình (2) giữ lại ẩn x2, chuyển x3 và x4 sang vế phải làm ẩn tự do, ta được: x2 = 5 2 x3 + x4 ; x1 = 2 + x3 x4 Vậy hệ phương trình có nghiệm tổng quát: (2 + x3 x4 ; 5 2 x3 + x4 ; x3 ; x4 ) Hệ vô định, cho các ẩn tự do những trị số tuỳ ý, ví dụ: x3 = 1 ; x4 = 2 nghiệm cụ thể ( 3, 5, 1, 2) 16
CHƯƠNG 2: PHƯƠNG PHÁP ĐƠN HÌNH VÀ BÀI TOÁN ĐỐI NGẪU Mã chương: LTTCTT 02 Giới thiệu: Trang bị cho người học những kiến thức cơ bản về phương pháp đơn hình,bài toán đối ngẫu, qua đó ứng dụng để giải các bài toán quy hoạch tuyến tính. Mục tiêu: Trình bày được phương pháp đơn hình để giải các bài toán quy hoạch tuyến tính; Trình bày được bài toán đối ngẫu; Giải được các bài toán bằng phương pháp đơn hình; Viết được bài toán đối ngẫu từ bài toán gốc; Có ý thức học tập nghiêm túc, cẩn thận và chính xác. Nội dung chính: 1. Các khái niệm, tính chất chung của bài toán quy hoạch tuyến tính 1.1. Một số ví dụ thực tế dẫn đến bài toán quy hoạch tuyến tính 1.1.1. Bài toán khẩu phần thức ăn Giả sử có một đội sản xuất chăn nuôi 1 loại gia súc, đội có 2 loại thức ăn I, II. Trong 2 loại thức ăn đều có chứa 3 chất dinh dưỡng A, B, C. Số đơn vị chất dinh dưỡng trong khẩu phần thức ăn và nhu cầu tối thiểu về số đơn vị chất dinh dưỡng trong khẩu phần thức ăn được cho trong bảng: DD A B C 17
Loại TA I 2 5 1 II 7 3 4 Nhu cầu tối 16 14 12 thiểu Biết rằng: Giá bán của một đơn vị thức ăn I là 1000đ Giá bán của một đơn vị thức ăn II là 2000đ Yêu cầu: Hãy xác định lượng thức ăn mỗi loại cần có trong khẩu phần thức ăn hàng ngày để đảm bảo yêu cầu về chất dinh dưỡng (Gia súc phát triển bình thường) và có chi phí về thức ăn là nhỏ nhất. Gọi X1, X2 lần lượt là số đơn vị thức ăn loại I, II cần cho khẩu phần thức ăn mỗi ngày (X1, X2 0) Chi phí về khẩu phần thức ăn là: 1 X1 + 2 X2 Yêu cầu về chất dinh dưỡng A: 2 X1 + 7 X2 Yêu cầu về chất dinh dưỡng B: 5 X1 + 3 X2 Yêu cầu về chất dinh dưỡng C: 1 X1 + 4 X2 Điều kiện phải có: Hàm mục tiêu chi phí nhỏ nhất: X1 + 2 X2 Min Yêu cầu tối thiểu về chất dinh dưỡng: 2 X1 + 7 X2 16 5 X1 + 3 X2 14 1 X1 + 4 X2 12 X1, X2 0 Giải bài toán ta sẽ tìm được X1, X2 thể hiện khối lượng thức ăn cần phải sử dụng để vừa có chi phí tối thiểu, vừa đủ nhu cầu về dinh dưỡng cho gia súc phát triển tốt. 1.1.2. Bài toán đặt kế hoạch sản xuất Một nhà máy có nhiệm vụ sản xuất 2 loại sản phẩm A, B. Những sản phẩm này được chế tạo từ 3 nguyên liệu I, II, III. Số đơn vị nguyên liệu dự trữ từng loại và số đơn vị nguyên liệu mỗi loại để sản xuất một loại sản phẩm được cho trong bảng: Sản phẩm I II III Nguyên liệu A 1 3 2 18
B 3 2 1 Nguyên liệu dự trữ 18 19 12 Cho biết lợi nhuận thu được trên một đơn vị sản phẩm A là 20; một đơn vị sản phẩm B là 30. Xác định số sản phẩm mỗi loại cần sản xuất sao cho lãi được nhiều nhất trong khuôn khổ về nguồn nguyên liệu dự trữ. Gọi X1, X2 là khối lượng sản phẩm A, B được tạo ra: (X1, X2 0) Lợi nhuận là: 20 X1 + 30X2 Max Trong khuôn khổ nguyên liệu I: 1 X1 + 3 X2 18 II: 3 X1 + 2 X2 19 III: 2 X1 + X2 12 X1, X2 0 Trên đây là 2 ví dụ đơn giản để minh họa mô hình toán học các vấn đề nảy sinh trong thực tế. Các bài toán trên có thể hiểu là bài toán tìm cực trị của một hàm tuyến tính xác định trên tập hợp nghiệm của một hệ thống hỗn hợp các phương trình và bất phương trình tuyến tính gọi là bài toán quy hoạch tuyến tính . 1.2. Bài toán qui hoạch tuyến tính và các dạng đặc biệt 1.2.1. Bài toán qui hoạch tuyến tính và các khái niệm 1.2.1.1. Bài toán qui hoạch tuyến tính Tìm vectơ X = xj: j = 1 n thoả mãn: aijxj = bi (i = 1, m1) aijxj bi (i = m1 + 1, m2) aijxj bi (i = m2 + 1, m) xj 0 (j = 1, p) xj 0 (j = p + 1, q) xj không có điều kiện dấu (j = q + 1, n) Sao cho: f(x) = Cjxj max 1.2.1.2. Một số khái niệm Ràng buộc: Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc. Hàm mục tiêu f(x) thể hiện mục tiêu mình cần đạt được. 19
Phương án: Là một vectơ x nào đó thoả mãn mọi ràng buộc của bài toán gọi là một phương án. Tập phương án : Là tập hợp tất cả những phương án có thể có của bài toán. Đôi khi tập phương án người ta còn dùng với nghĩa miền ràng buộc. Ký hiệu D. Phương án tối ưu (phương án tốt nhất): Là một phương án mang lại cực trị cho hàm mục tiêu hay là một phương án mà tại đó trị số hàm mục tiêu đạt cực đại hoặc cực tiểu. D = : Bài toán không có phương án nên không có phương án tối ưu. D : Có phương án . Có hai khả năng: + Không có phương án tốt nhất. + Có thể tìm được phương án tốt nhất. Một bài toán có phương án tốt nhất gọi là bài toán giải được. Nếu không có phương án tốt nhất gọi là bài toán không giải được: Trị số hàm mục tiêu không bị chặn trên tập phương án hay nói cách khác là trị số hàm mục tiêu giảm (tăng) vô hạn trên tập phương án. 1.2.2. Các dạng đặc biệt 1.2.2.1. Dạng chính tắc Tìm vectơ X = xj: j = 1 n thoả mãn: aijxj = bi (i = 1, m) xj 0 (j = 1, n) Sao cho: f(x) = Cjxj max (min) Hay có thể viết dưới dạng ma trận với hệ ràng buộc: A.X = B X 0 Hệ ràng buộc gồm 2 nhóm: 1 nhóm là các ràng buộc dạng phương trình, còn nhóm ràng buộc bất phương trình trở thành các ràng buộc về dấu đối với các biến (mọi biến đều không âm) * Mệnh đề: Mọi bài toán qui hoạch tuyến tính đều có thể qui về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong 2 bài toán là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu của bài toán kia. 20