Từ một số mô hình thực tế, chúng tôi đưa ra định nghĩa của bài toán quy hoạch tuyến tính tổng quát và một số dạng thông dụng của nó. Để sinh viên tiếp thu được một cách dễ dàng, chúng tôi đưa ra phương pháp đồ thị để giải bài toán quy hoạch tuyến tính hai biến | Bài giảng quy hoạch toán Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH PHƯƠNG PHÁP HÌNH HỌC . Các bài toán thực tế . Bài toán lập kế hoạch sản xuất a Ví dụ Để sản xuất kẹo và bánh cần 2 thứ nguyên liệu chính là đường và bột mì với trữ lượng hiện có là 0 9kg đường và 1 1 kg bột mì. 1kg kẹo cần 0 5 kg đường và 0 3 kg bột mì 1kg bánh cần 0 2kg đường và 0 4 kg bột mì. Giá 1kg kẹo là 10000đ 1kg bánh là 20000đ. Hãy lập kế hoạch sản xuất sao cho tổng giá trị sản phẩm lớn nhất. Gọi x1 là số kg kẹo được sản xuất x2 là số kg bánh được sản xuất. Có mô hình toán học f x 10000x1 20000x2 max x1 x2 0 b Tổng quát Để sản xuất n loại sản phẩm khác nhau cần m loại yếu tố sản xuất với trữ lượng hiện có là bi b2 . bm Hệ số hao phí yếu tố i i cho 1 đơn vị sản phẩm j j là ữy. Giá 1 đơn vị sản phẩm j là Oj j . Hãy lập kế hoạch sản xuất trên cơ sở các yếu tố sản xuất hiện có sao cho tổng giá trị sản phẩm lớn nhất. Gọi xj là số sản phẩm j được sản xuất f x là tổng doanh thu ứng với kế hoạch sản xuất x x1 x2 . xn . Có mô hình toán học n f x cjxj max j 1 n Eaiỉxỉ b i 1--m j 1 xy 0 j Bài giảng quy hoạch toán . Bài toán vận tải Có m kho hàng chứa cùng 1 loại hàng hóa với số lượng ở kho i là ai i . Đồng thời có n cửa hàng với nhu cầu ở cửa hàng j là bj j . Chi phí vận chuyển 1 đơn vị hàng từ kho i đến cửa hàng j là cij. Hãy lập kế hoạch vận chuyển sao cho thỏa mãn nhu cầu các cửa hàng và chi phí vận chuyển thấp nhất. Gọi Xjj là số lượng hàng chuyển từ kho i đến cửa hàng j f x là tổng chi phí theo kế hoạch vận chuyển x. Mô hình toán học m n f x X X cijxij min i 1 j 1 n X xij ai i 1 m j 1 m . iX x bj j 1-n i 1 xij 0 i j . Bài toán xác định khẩu phần Có n loại thức ăn gia súc giá 1 đơn vị thức ăn j là c j . Gia súc cần m chất dinh dưỡng với nhu cầu tối thiểu chất i là bị i . Biết hàm lượng chất i có trong 1 đơn vị thức ăn j là ữy. Hãy xác định khẩu phần thức ăn cho gia súc sao cho chi phí thấp nhất đồng thời đảm bảo
