một nhà máy điện có thể dùng 4 loại than để sản xuất điện. Biết - lượng điện năng yêu cầu hàng năm của nhà máy :A[MWh] - suất tiêu hao than của loại than thứ i là qi - Giá thành sản xuất điện năng của loại than i là ci [đ/MWh] (i=1,2,3,4) - Lượng than loại i cung cấp hàng năm để sản xuất điện không được vượt quá Qi - Tổng lượng than của cả 4 loại cung cấp hàng năm để sản xuất điện không được vượt quá Q∑ Cần xác định lượng điện năng được. | Chương 6 Bài toán dạng chính tắc bài toán dạng mở rộng Hãy trình bày phương pháp quy hoạch số nguyên I- Quy hoạch tuyến tính 1. Đặt bài toán Một nhà máy điện có thể dùng 4 loại than để sản xuất điện. Biết - lượng điện năng yêu cầu hàng năm của nhà máy A MWh - suất tiêu hao than của loại than thứ i là qi - Giá thành sản xuất điện năng của loại than i là Ci đ MWh i 1 2 3 4 - Lượng than loại i cung cấp hàng năm để sản xuất điện không được vượt quá Qi - Tổng lượng than của cả 4 loại cung cấp hàng năm để sản xuất điện không được vượt quá Qỵ Cần xác định lượng điện năng được sản xuất hàng năm từ từng loại than để đạt cực tiểu về chi phí sản xuất điện năng. 2. Lời giải Nếu gọi lượng điện năng được sản xuất hàng năm từ loại than thứ i là xi MWh i 1 2 3 4 . bài toán có thể được trình bày như sau - Xác định X xb x2 x3 x4 sao cho f X c1x1 c2x2 c3x3 c4x4 min - Với các ràng buộc X1 X2 x3 x4 A qiXi q2X2 q3X3 q4X4 Qs qiXi Q1 q2X2 Q2 q3X3 Q3 q4X4 Q4 Xi 0 i 1 2 3 4 3. Các dạng bài toán quy hoạch tuyến tính A-Dạng tồng quát j 1 .n Tìm X x thỏa mãn đồng thời các điều kiện 1 f X É cjxj min maX 2 g X ịa xJ b i ĩm Trong đó - f X là hàm mục tiêu - Xj là các ẩn - Cj aịj bi là những hằng số tự do B-Dạng chính tắc Tìm X Xj j 1 . n thỏa mãn đồng thời các điều kiện sau 1 f X É c min maX 2 gi X ÉaijXj bi i 1 m J 1 3 Xj 0 bi 0 trong đó cj ajj bj là các hằng số tự do Người ta có thể đưa dạng tổng quát về dạng chính tắc nếu gặp các trường hợp sau n 1- 2 a jXj bi Thêm vào vế trái phương trình một lượng ẩn xn i 0 ta có n n 2 aijXj bi 2 aiJXJ Xn i bi j 1 j 1 n 2- 2 a x - bi bớt vào vế trái của phương trình một lượng ẩn xn i 0 ta có nn 2 aijxj - bi 2 aijxj - Xn i bi j 1 j 1 3- Trường hợp Xj 0 th ì đ ặt tj - Xj 0 4- Trường hợp không biết dấu của ẩn Xj thì đặt Xj Xj1 - Xj2 trong đ ó Xj1 - 0 Xj2 - 0 Bài toán dạng tổng quát sẽ trở thành bài toán dạng chính t ắc C-Dạng chuẩn tắc là bài toán có dạng sau T ìm X x j 1 . n thỏa mãn đồng thời các điều k 2 cjXj min maX j 1 1- F X n-m __ Xi 2 a m hXm h b i .
