Đề thi môn “Quy hoạch rời rạc”

Thời gian làm bài : 120 phút

Không được sử dụng bất kỳ tài liệu mang theo nào

Được dùng máy tính bấm tay, không được dùng laptop

Bài 1. Xây dựng lược đồ khối cho thuật toán Gomory 3 để đảm bảo tất cả các bảng đơn hình đều là số nguyên  

Thuật toán Gomory 1

Chương trình nguồn cho thuật toán Gomory 1 trình bày trong “Giáo trình quy hoạch rời rạc” thuộc Trang “Toán học” của Blog này.

#include

#include

#include

#include

#define M 30

#define N 30

double s[N+2][M+1],r,gz;

int kgd,kgd2,blap,blap2,sb,cmin,x0,ss;

int m,n,i,j,k,l,le,lc,tg,cs[N+2],nc[M+1];

unsigned long far *t; long int t1,t2;

char *s1,*s2; FILE *f1,*f2;

Thuật toán Gomory 3

Chương trình nguồn cho thuật toán Gomory 3  trình bày trong “Giáo trình quy hoạch rời rạc” thuộc Trang “Toán học” của Blog này.

#include

#include

#include

#include

#define M 30

#define N 30

long int s[N+2][M+1],gz,t1,t2,lamda; double r;

int ka,blap,sb,cmin,m,n,i,j,k,l,lc,tg,cs[N+2],nc[M+1],np[M+1];

int hl,hj,trong,zj[M+1],q,is,ss;

unsigned long far *t; char *s1,*s2;

FILE *f1,*f2;  

Thuật toán Dalton

Chương trình nguồn cho thuật toán Dalton trình bày trong “Giáo trình quy hoạch rời rạc” thuộc Trang “Toán học” của Blog này.

#include

#include

#include

#include

#define M 30

#define N 30

double s[N+2][M+1],r,r1,r2,gz,t4,t5;

int kgd,kgd2,blap,blap2,sb,cmin,ss,v[N+1],w[N+1],a[N+1][11];

int m,n,n1,i,j,k,l,le,lc,tg,h,cs[N+2],nc[M+1];

unsigned long far *t; long int t1,t2;

char *s1,*s2; FILE *f1,*f2;   

Thuật toán Gomory thứ hai

Chương trình nguồn cho thuật toán Gomory 2  trình bày trong “Giáo trình quy hoạch rời rạc” thuộc Trang “Toán học” của Blog này.

#include

#include

#include

#include

#define M 30

#define N 30

double s[N+2][M+1],r,gz,t4,t5;

int kgd,kgd2,blap,blap2,sb,cmin,x0,ss;

int m,n,n1,i,j,k,l,le,lc,tg,cs[N+2],nc[M+1];

unsigned long far *t; long int t1,t2;

char *s1,*s2; FILE *f1,*f2;

int ktnguyen(double x);    

Hướng dẫn giải các bài toán tối ưu và thống kê trên Excel

Dùng Excel để giải các bài toán tối ưu và thống kê.
Ấn phím Shift và Click vào đây để Download và xem tài liệu:
Xem tài liệu và Download
Bài này đã được đăng trên trang Web  http://ebook.edu.net.vn

Quy hoạch nguyên và Quy hoạch rời rạc

1. Đây là Bài giảng của Bùi Thế Tâm về Quy hoạch rời rạc trong nhiều năm. Giáo trình này có thể dạy cho sinh viên các năm cuối ngành Toán, cho học sinh cao học Toán. Trong giáo trình có 5 chương trình mẫu về quy hoạch rời rạc viết bằng C++. Download tài liệu

Đường Link thứ hai để Download tài liệu: Download tài liệu 2

2. Bài tập Quy hoạch tuyến tính nguyên. Dùng Excel để giải các bài toán quy hoạch tuyến tính nguyên sau. Download tài liệu

3. Đề thi viết môn Quy hoạch rời rạc, thời gian làm bài 120 phút.Download tài liệu

Quy hoạch tuyến tính

1. Bài tập quy hoạch tuyến tính. Dùng phương pháp đơn hình hoặc đơn hình đối ngẫu từ vựng để giải các bài toán quy hoạch tuyến tính sau. Download tài liệu

2. Hai đề thi môn Quy hoạch toán học: phần Quy hoạch tuyến tính và Bài toán vận tải Download tài liệu . Đây là đề thi dùng cho sinh viên đại học bằng thứ hai của Khoa Toán – Tin – Cơ học, Đại học Khoa học tự nhiên – Đại học quốc gia Hà Nội vào năm 1998.

Bùi Thế Tâm

Chương trình Phương pháp đơn hình cải biên

Chương trình Phương pháp đơn hình cải biên nhằm giải bài toán Quy hoạch tuyến tính có dạng sau:
max {CX | AX = B, X>=0, B>=0}
A – m hàng, n+m cột, m cột cuối chứa ma trận đơn vị (cơ sở xuất phát)
X, C – véc tơ n+m chiều
Nếu các ràng buộc ở dạng >= hay <= thì khi đưa thêm biến bù C[j]=0,
đối với biến giả tạo thì C[j]= -M
Bất kỳ bài toán Quy hoạch tuyến tính nào cũng đưa được về dạng trên, do đó dạng trên là rất tổng quát.

Ưu điểm của chương trình:
1. Phương pháp đơn hình cải biên  viết ở dạng hàm để dễ dùng khi sử dụng
2. Các mảng 2 chiều đều dùng 1 chỉ số giúp chương trình chạy nhanh hơn và dễ sử dụng

Phương pháp đơn hình thường giải quy hoạch tuyến tính và Tạo dữ liệu ngẫu nhiên

Phương pháp đơn hình thường giải Quy hoạch tuyến tính
/*   Min CX:  Ax = b, x >= 0,
Them m bien gia tao vao cuoi, ma tran co so xuat phat la ma tran don vi
A co m hang n cot
S[0..m,0..n] : s[0,0] ham muc tieu,
dong 0 la uoc luong, cot 0 la phuong an
ii[1..m] : chỉ số các bien co so
ep – số dương đủ nhỏ
gz – số dương đủ lớn, hệ số phạt
x[1..n+m] – chứa phương án tối ưu của bài toán
val – giá trị tối ưu hàm mục tiêu
te – biến trung gian để xác định dòng quay