Cây bao trùm T=(E,F) của đồ thị G=(D,C)
- Là một đồ thị có hướng
- Là một đồ thị liên thông và có n-1 cạnh
- Là một đồ thị có n đỉnh như đồ thị G
- Là một đồ thị không chứa chu trình
Bài toán quy hoạch toán học là bài toán
- Có hàm mục tiêu là hàm số tuyến tính của các biến số
- Có ràng buộc được thể hiện dưới dạng các phương trình, các bất phương trình của các biến số
- Các biến số phải là những số không âm
- Luôn có thể tìm được phương án tối ưu
Phương pháp tối ưu trong kinh doanh
- Có thể hỗ trợ nhà quản trị ra quyết định trong việc phân bổ các nguồn lực của doanh nghiệp
- Có thể hỗ trợ nhà quản trị lựa chọn phương án sản xuất kinh doanh tối ưu với những ràng buộc hạn chế
- Có thể hỗ trợ nhà quản trị xác định nhu cầu của thị trường về sản phẩm của doanh nghiệp
- Có thể hỗ trợ nhà quản trị xác định lượng dự trữ nguyên vật liệu tối ưu
Sơ đồ mạng của một dự án (sơ đồ PERT)
- Luôn có đường găng
- Có thể có nhiều đường găng
- Đường găng là đường có độ dài ngắn nhất đi từ sự kiện khởi công dự án đến sự kiện kết thúc dự án
- Đường găng là đường có độ dài dài nhất đi từ sự kiện khởi công dự án đến sự kiện kết thúc dự án
Mạng
- Là một đồ thị vô hướng
- Có một đỉnh duy nhất không có cung đi vào
- Có một đỉnh duy nhất không có cung đi ra
- Mỗi cung ( i,j ) của mạng đều gắn với một khả năng thông qua C(i,j)
Khi sử dụng bài toán vận tải để lựa chọn địa điểm xây dựng cơ sở sản xuất cho doanh nghiệp đã chú ý đến
- Chi phí để sản xuất và vận chuyển một đơn vị sản phẩm từ những địa điểm dự định lựa chọn đến các đại lý
- Giá bán một đơn vị sản phẩm tại các địa điểm tiêu thụ
- Các chi phí khác liên quan đến việc xây dựng cơ sở sản xuất tại những địa điểm dự định lựa chọn
- Khả năng nâng cao công suất sản xuất sản phẩm tại những cơ sở sản xuất đã có
Khi sử dụng thuật toán gán nhãn để tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v của một đồ thị liên thông thì
- Phải gán nhãn cho các đỉnh trong quá trình giải
- Nhãn l(x) của đỉnh x cho biết giới hạn trên của chiều dài đường đi từ định u đến đỉnh x
- Khi nhãn l(x) của đỉnh x không giảm được nữa thì đỉnh x trở thành đỉnh cố định
- Thuật toán có thể không tìm được đường đi ngắn nhất
Khi sử dụng phương pháp đơn hình để giải bài toán quy hoạch tuyến tính để tìm Max :
- Phương án tối ưu là phương án có các số kiểm tra ∆_j<0 , j b. 1,2,….,n c. Phương án tối ưu là phương án có các số kiểm tra ∆_j>0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j
- 0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j≥0 , j
Cây là một đồ thị vô hướng
- Có n đỉnh và có n cạnh (n là số đỉnh của đồ thị)
- Luôn liên thông và chứa chu trình
- Không liên thông và không chứa chu trình
- Liên thông và có n-1 cạnh
Phương pháp tối ưu
- Là các phương pháp để giải các bài toán tối ưu
- Là kết quả nghiên cứu của Lý thuyết tối ưu
- Hỗ trợ nhà quản trị tìm phương án án tối ưu khi giải quyết các vấn đề trong kinh doanh
- Không phụ thuộc vào mục tiêu cần đạt được và những ràng buộc khi giải quyết vấn đề
Khi sử dụng bài toán vận tải để phân công công việc đã chú ý đến điều kiện :
- Một người có thể đảm nhận thực hiện nhiều công việc
- Một công việc có thể do nhiều người đảm nhận thực hiện
- Mỗi người chỉ đảm nhận một công việc và mỗi công việc chỉ do một người đảm nhận
- Chất lượng công việc sau khi hoàn thành
Mệnh đề nào dưới đây là mệnh đề đúng:
- Mọi bài toán quy hoạch tuyến tính đều có phương án
- Mọi bài toán quy hoạch tuyến tính đều có phương án cực biên
- Nếu bài toán quy hoạch tuyến tính có phương án thì nó phương án cực biên
- Mọi phương án cực biên đều có đúng m thành phần dương (m là số các ràng buộc của bài toán quy hoạch tuyến tính)
Khi sử dụng phương pháp đơn hình để giải bài toán quy hoạch tuyến tính để tìm Min
- Phương án tối ưu là phương án có các số kiểm tra ∆_j<0 , j b. 1,2,….,n c. Phương án tối ưu là phương án có các số kiểm tra ∆_j≤0 , j d. 1,2,….,n e. Phương án tối ưu là phương án có các số kiểm tra ∆_j>0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j≥0 , j
- 1,2,….,n
Khi sử dụng bài toán phụ để tìm phương án cực biên của bài toán quy hoạch tuyến tính :
- Bài toán phụ là bài toán tìm Max
- Bài toán phụ luôn có m biến
- Nếu giá trị nhỏ nhất của hàm mục tiêu của bài toán phụ dương thì bài toán chính không có phương án cực biên
- Cần tính toán số kiểm tra cho các cột ứng với biến giả trong suốt quá trình giải
Sử dụng Bài toán lập kế hoạch sản xuất để xác định số lượng từng loại sản phẩm mà doanh nghiệp sẽ sản xuất trong kỳ kế hoạch đã :
- Quan tâm đến giới hạn cầu của thị trường về từng loại sản phẩm của doanh nghiệp trong kỳ kế hoạch
- Quan tâm đến việc bổ sung các nguồn lực cho doanh nghiệp trong kỳ kế hoạch
- Quan tâm đến lượng sản phẩm các loại còn tồn đọng từ kỳ kế hoạch trước
- Quan tâm đến sự thay đổi định mức sử dụng các nguồn lực khi sản xuất sản phẩm trong kỳ kế hoạch
Bài toán cực đại hóa lợi ích tiêu dùng của hộ gia đình:
- Đã quan tâm đến hạn chế về tài chính của hộ gia đình khi tiêu dùng các loại hàng hóa
- Đã quan tâm đến sự thay thế các loại hàng hóa trong tiêu dùng của hộ gia đình
- Đã quan tâm đến mức tiêu dùng tối thiểu cần phải có đối với từng loại hàng hóa của hộ gia đình
- Đã quan tâm đến sự thay đổi giá cả hàng hóa trên thị trường
Bài toán nhiều máy gia công hai loại chi tiết
- Để tìm phương án tối ưu cần chuyển về bài toán sản xuất đồng bộ điển hình
- Để tìm phương án tối ưu cần xác định những chi tiết chỉ do một máy sản xuất
- Để tìm phương án tối ưu cần xác định chi tiết được hai máy tham gia sản xuất
- Để tìm phương án tối ưu cần xác định một máy tham gia sản xuất cả hai loại chi tiết
Sử dụng Bài toán lập tiến độ sản xuất đã
- Quan tâm đến khối lượng sản phẩm doanh nghiệp cần cung cấp cho khách hàng trong từng tháng
- Quan tâm đến sự thay đổi năng lực sản xuất của doanh nghiệp trong từng tháng
- Quan tâm đến sự thay đổi chi phí sản xuất, chi phí lưu kho cho một đơn vị sản phẩm theo từng tháng
- Quan tâm đến sự thay đổi khả năng tiêu thụ sản phẩm của doanh nghiệp trong từng tháng
Bài toán sản xuất đồng bộ tổng quát
- Luôn giả thiết rằng với mỗi loại máy doanh nghiệp chỉ có một máy
- Luôn giả thiết rằng sản phẩm của doanh nghiệp được lắp ráp từ nhiều loại chi tiết và mỗi loại cần một chi tiết
- Luôn tìm được phương án tối ưu
- Trong nhiều trường hợp không tìm được phương án tối ưu
Bài toán quy hoạch tuyến tính là bài toán
- Có hàm mục tiêu là hàm số tuyến tính của các biến số
- Có ràng buộc là các phương trình, bất phương trình tuyến tính của các biến số
- Có thể là bài toán tìm Max hoặc bài toán tìm Min
- Luôn tồn tại lời giải tối ưu
Với cây bao trùm bé nhất T của đồ thị G thì mỗi cạnh (u,v) của G nhưng không thuộc T
- Đều tạo ra với những cạnh của T một chu trình duy nhất
- Cạnh (u,v) là cạnh có độ dài lớn nhất so với những cạnh của chu trình mà nó tạo ra với những cạnh của T
- Cạnh (u,v) là cạnh có độ dài nhỏ nhất so với những cạnh của chu trình mà nó tạo ra với những cạnh của T
- Cạnh (u,v) vẫn có thể trở thành một cạnh của một cây bao trùm bé nhất khác của đồ thị G
Bài toán cực đại hóa giá trị sản lượng của doanh nghiệp:
- Mới chỉ quan tâm đến việc sản xuất một loại sản phẩm
- Đã quan tâm đến giới hạn của các nguồn lực khi tiến hành sản xuất sản phẩm
- Đã quan tâm đến cầu của thị trường về sản phẩm của doanh nghiệp
- Đã quan tâm đến lợi nhuận mà doanh nghiệp thu được khi tiêu thụ sản phẩm
Sử dụng phương pháp sơ đồ mạng để điều hành dự án cần
- Xác định thời gian cần thiết để thực hiện các công việc của dự án
- Xác định đường găng của sơ đồ
- Xác định thời gian dự trữ của các công việc
- Xác định chi phí các nguồn lực cần thiết để thực hiện các công việc của dự án
Mệnh đề nào là sai trong những mệnh đề sau:
- Không có vấn đề thì không có quyết định
- Không giải quyết được vấn đề thì không có quyết định
- Giải quyết được vấn đề thì chắc chắn có quyết định
- Ra quyết định là một quá trình lựa chọn có ý thức
Mọi bài toán quy hoạch tuyến tính đều có lời giải tối ưu nếu :
- Có phương án
- Có phương án cực biên
- Hàm mục tiêu bị chặn
- Có phương án và hàm mục tiêu bị chặn
Điều kiện cần và đủ để bài toán vận tải có phương án tối ưu duy nhất là
- Tất cả các ô của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn đẳng thức u_i+v_j
- c_ij
- Tất cả các ô của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức
- Tất cả các ô có hàng của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức u_i+v_j
- Tất cả các ô không có hàng của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức u_i+v_j
Nếu giả thiết chi phí để thực hiện công việc ( i,j ) là hàm số tuyến tính của thời gian thực hiện công việc t_(i j) thì bài toán cực tiểu thời gian hoàn thành dự án
- Là một bài toán quy hoạch tuyến tính
- Có biến số là thời điểm đạt tới các sự kiện và thời gian cần thiết để hoàn thành công việc của dự án
- Có biến số là thời gian cần thiết để hoàn thành dự án
- Phải biết được tổng chi phí được phép để thực hiện dự án
Bài toán sản xuất đồng bộ điển hình
- Luôn yêu cầu mỗi máy phải sản xuất được mọi loại chi tiết để lắp ráp sản phẩm
- Với mục tiêu là xác định số lượng sản phẩm được sản xuất trong một giờ để giá trị sản lượng lớn nhất
- Với mục tiêu là xác định số lượng sản phẩm được sản xuất trong một giờ để tổng chi phí sản xuất sản phẩm nhỏ nhất
- Với mục tiêu là xác định số lượng sản phẩm lắp ráp được trong một giờ là lớn nhất
Sử dụng bài toán tối ưu để giải quyết các vấn đề thực tế trong kinh doanh cần
- Xác định vấn đề cần phải giải quyết
- Xác định mục tiêu cần đạt được khi giải quyết vấn đề
- Xác định những ràng buộc khi giải quyết vấn đề
- Không cần phải kiểm định lại kết quả thu được sau khi áp dụng phương pháp tối ưu để giải bài toán
Bài toán nhiều máy gia công hai loại chi tiết
- Là bài toán sản xuất đồng bộ tổng quát
- Để tìm phương án tối ưu cần phải tính tỉ số năng suất của từng máy khi sản xuất hai loại chi tiết
- Để tìm phương án tối ưu cần xác định một máy tham gia sản xuất cả hai loại chi tiết
- Luôn tìm được phương án tối ưu
Bài toán sản xuất đồng bộ điển hình
- Không phải là một bài toán quy hoạch tuyến tính
- Luôn giả thiết là với mỗi loại máy doanh nghiệp chỉ có một máy
- Luôn giả thiết là mỗi sản phẩm được lắp ráp từ nhiều loại chi tiết và cần một chi tiết cho mỗi loại
- Luôn giả thiết là năng suất của mỗi máy khi sản xuất từng loại chi tiết là không thay đổi
Bài toán sản xuất đồng bộ điển hình
- Luôn yêu cầu các máy đều phải sản xuất được tất cả các loại chi tiết
- Chỉ sử dụng để phân công sản xuất cho các máy trong một giờ
- Khi năng suất của các máy khi sản xuất từng loại chi tiết đều được tăng lên k lần thì phương án tối ưu sẽ không thay đổi
- Khi năng suất của các máy khi sản xuất từng loại chi tiết đều được tăng lên k lần thì phương án tối ưu sẽ thay đổi
Bài toán sản xuất đồng bộ tổng quát
- Chỉ xác định được việc sản xuất đồng bộ của các máy trong một giờ
- Chỉ có thể được giải bằng phương pháp đơn hình
- Luôn có phương án tối ưu
- Phương án tối ưu là duy nhất
Điều kiện cần và đủ để một phương án của bài toán vận tải là phương án tối ưu là
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô không có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j≤c_(ij ) ở những ô không có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô có hàng và u_i+v_j≤c_ij ở những ô không có hàng
Bài toán sản xuất, vận chuyển và tiêu thụ
- Là bài toán vận tải thông thường như đã phát biểu trong mục 3.1.1.
- Phương án tối ưu luôn cho chúng ta tổng chi phí vận chuyển trong kỳ kế hoạch là nhỏ nhất
- Phương án tối ưu luôn cho chúng ta tổng chi phí sản xuất trong kỳ kế hoạch tại các cơ sở sản xuất là nhỏ nhất
- Phương án tối ưu luôn cho chúng ta tổng lợi nhuận thu được tại các cơ sở tiêu thụ trong kỳ kế hoạch là lớn nhất
Cây bao trùm của một đồ thị vô hướng n đỉnh
- Luôn liên thông
- Không chứa chu trình
- Cứ thêm vào 1 cạnh thì thu được đúng một chu trình
- Chỉ có n-1 đỉnh
Phương án cực biên của bài toán vận tải:
- Luôn tồn tại
- Luôn bao gồm m+n-1 ô có hàng
- Các ô có hàng của phương án cực biên luôn tạo thành chu trình
- Luôn là phương án tối ưu
Bài toán cực tiểu hóa chi phí sản xuất của doanh nghiệp:
- Đã quan tâm đến mức sản lượng để đáp ứng nhu cầu của khách hàng theo hợp đồng
- Đã quan tâm đến giới hạn của các yếu tố đầu vào khi tiến hành sản xuất
- Đã quan tâm đến sự thay thế các yếu tố đầu vào khi tiến hành sản xuất
- Đã quan tâm đến giới hạn nhu cầu của thị trường về sản phẩm của doanh nghiệp
Bài toán cực tiểu hóa chi tiêu của hộ gia đình
- Đã quan tâm đến giá cả hàng hóa trong tiêu dùng của hộ gia đình
- Đã quan tâm đến lợi ích tiêu dùng tối thiểu mà hộ gia đình cần phải đảm bảo
- Đã quan tâm đến những hàng hóa cơ bản tạo ra lợi ích tiêu dùng của hộ gia đình
- Đã quan tâm đến mức tiêu dùng tối thiểu cần phải đảm bảo đối với từng loại hàng hóa
Mọi bài toán quy hoạch tuyến tính đều có thể chuyển về bài toán dạng chính tắc nhờ:
- Đổi dấu các hệ số của hàm mục tiêu
- Loại bỏ những ràng buộc dạng bất đẳng thức
- Sử dụng các biến bù với hệ số của các biến bù trong hàm mục tiêu bằng 0
- Sử dụng cả A và B
Bài toán sản xuất đồng bộ tổng quát
- Luôn giả thiết rằng doanh nghiệp có nhiều loại máy và với mỗi loại có thể có nhiều máy
- Luôn giả thiết rằng sản phẩm của doanh nghiệp được lắp ráp từ nhiều loại chi tiết và mỗi loại có thể cần nhiều chi tiết
- Luôn có thể chuyển về bài toán sản xuất đồng bộ điển hình
- Luôn có phương án tối ưu duy nhất
Nếu giả thiết chi phí để thực hiện công việc ( i,j ) là hàm số tuyến tính của thời gian thực hiện công việc t_(i j) thì bài toán cực tiểu chi phí hoàn thành dự án
- Là một bài toán quy hoạch tuyến tính
- Có biến số là thời điểm đạt tới các sự kiện và thời gian cần thiết để hoàn thành công việc của dự án
- Có biến số là tổng chi phí cần thiết để hoàn thành dự án
- Phải biết được khoảng thời gian cho phép phải hoàn thành dự án
Bài toán vận tải :
- Không phải là bài toán quy hoạch tuyến tính
- Tổng lượng hàng của các điểm phát luôn bằng tổng lượng hàng của các điểm thu
- Luôn có lời giải tối ưu
- Lời giải tối ưu là những số nguyên dương
Bài toán hai máy gia công nhiều loại chi tiết
- Là bài toán sản xuất đồng bộ tổng quát
- Để tìm phương án tối ưu phải tính tỉ số năng suất của hai máy khi sản xuất từng loại chi tiết
- Để tìm phương án tối ưu cần xác định một chi tiết mà cả hai máy cùng tham gia sản xuất
- Luôn tìm được phương án tối ưu
Khi sử dụng bài toán vận tải để xác định khối lượng sản phẩm sản xuất, vận chuyển và tiêu thụ cho doanh nghiệp đã không chú ý đến
- Chi phí sản xuất một đơn vị sản phẩm tại các cơ sở sản xuất
- Giá bán một đơn vị sản phẩm tại các cơ sở tiêu thụ
- Chi phí vận chuyển một đơn vị sản phẩm từ các cơ sở sản xuất đến các cơ sở tiêu thụ
- Sự thay đổi chi phí sản xuất và giá bán đơn vị sản phẩm tại các cơ sở sản xuất và tại các cơ sở tiêu thụ sản phẩm trong kỳ kế hoạch
Bài toán hai máy gia công nhiều chi tiết
- Để tìm phương án tối ưu cần phải chuyển về bài toán sản xuất đồng bộ điển hình
- Để tìm phương án tối ưu cần phải xác định máy tham gia sản xuất hai loại chi tiết
- Để tìm phương án tối ưu cần phải xác định chi tiết được cả hai máy cùng tham gia sản xuất
- Trong nhiều trường hợp không tìm được phương án tối ưu
Bài toán xe không
- Là bài toán vận tải với điểm phát và điểm thu sản phẩm như đã phát biểu trong mục 3.1.1.
- Là bài toán vận tải với bảng vận tải mà điểm phát trở thành điểm thu và ngược lại
- Là bài toán vận tải với bảng vận tải trong đó chi phí vận chuyển một đơn vị sản phẩm từ điểm phát i đến điểm thu j được thay bằng khoảng cách giữa điểm thu j đến điểm phát i
- Là bài toán vận tải với hàm mục tiêu là cực tiểu số tấn x km chạy xe không tải cho một hợp đồng vận chuyển
Khi sử dụng phương pháp đơn hình ở bảng cuối cùng ứng với phương án tối ưu có những số kiểm tra ∆_k=0 ứng với những véc tơ phi cơ sở thì điều đó cho thấy :
- Bài toán có vô số phương án tối ưu
- Phương án tối ưu là không duy nhất
- Bài toán không có lời giải vì hàm mục tiêu không bị chặn
- Phương án tối ưu không phải là phương án cực biên
Bài toán xe không
- Đã quan tâm đến chi phí vận chuyển một đơn vị sản phẩm từ các điểm phát đến các điểm thu
- Nhằm xác định kế hoạch vận chuyển tối ưu sản phẩm từ các điểm phát đến các điểm thu
- Nhằm xác định tổng chi phí vận chuyển nhỏ nhất cho hợp đồng vận chuyển
- Nhằm xác định số tấn x km chạy xe không tải cho hợp động vận chuyển là nhỏ nhất
Sử dụng phương pháp đơn hình để giải Bài toán pha cắt vật liệu đã :
- Quan tâm đến số lượng những tấm vật liệu có kích thước nhỏ hơn cần thiết để phục vụ cho kế hoạch sản xuất sản phẩm
- Quan tâm đến số tấm vật liệu cần phải có để phục vụ cho kế hoạch sản xuất sản phẩm
- Quan tâm đến số tấm vật liệu có kích thước nhỏ hơn tồn đọng từ các kế hoạch sản xuất trước
- Quan tâm đến việc sử dụng những tấm vật liệu có kích thước nhỏ hơn cho các kế hoạch sản xuất tiếp theo
Bài toán sản xuất đồng bộ tổng quát
- Luôn giả thiết rằng với mỗi loại máy doanh nghiệp chỉ có một máy
- Luôn giả thiết rằng sản phẩm của doanh nghiệp được lắp ráp từ nhiều loại chi tiết và mỗi loại cần một chi tiết
- Luôn tìm được phương án tối ưu
- Trong nhiều trường hợp không tìm được phương án tối ưu
Bài toán quy hoạch toán học là bài toán
- Có hàm mục tiêu là hàm số tuyến tính của các biến số
- Có ràng buộc được thể hiện dưới dạng các phương trình, các bất phương trình của các biến số
- Các biến số phải là những số không âm
- Luôn có thể tìm được phương án tối ưu
Phương pháp tối ưu
- Là các phương pháp để giải các bài toán tối ưu
- Là kết quả nghiên cứu của Lý thuyết tối ưu
- Hỗ trợ nhà quản trị tìm phương án án tối ưu khi giải quyết các vấn đề trong kinh doanh
- Không phụ thuộc vào mục tiêu cần đạt được và những ràng buộc khi giải quyết vấn đề
Cây bao trùm T=(E,F) của đồ thị G=(D,C)
- Là một đồ thị có hướng
- Là một đồ thị liên thông và có n-1 cạnh
- Là một đồ thị có n đỉnh như đồ thị G
- Là một đồ thị không chứa chu trình
Bài toán cực đại hóa lợi ích tiêu dùng của hộ gia đình:
- Đã quan tâm đến hạn chế về tài chính của hộ gia đình khi tiêu dùng các loại hàng hóa
- Đã quan tâm đến sự thay thế các loại hàng hóa trong tiêu dùng của hộ gia đình
- Đã quan tâm đến mức tiêu dùng tối thiểu cần phải có đối với từng loại hàng hóa của hộ gia đình
- Đã quan tâm đến sự thay đổi giá cả hàng hóa trên thị trường
Mệnh đề nào dưới đây là mệnh đề đúng:
- Mọi bài toán quy hoạch tuyến tính đều có phương án
- Mọi bài toán quy hoạch tuyến tính đều có phương án cực biên
- Nếu bài toán quy hoạch tuyến tính có phương án thì nó phương án cực biên
- Mọi phương án cực biên đều có đúng m thành phần dương (m là số các ràng buộc của bài toán quy hoạch tuyến tính)
Sử dụng bài toán tối ưu để giải quyết các vấn đề thực tế trong kinh doanh cần
- Xác định vấn đề cần phải giải quyết
- Xác định mục tiêu cần đạt được khi giải quyết vấn đề
- Xác định những ràng buộc khi giải quyết vấn đề
- Không cần phải kiểm định lại kết quả thu được sau khi áp dụng phương pháp tối ưu để giải bài toán
Khi sử dụng bài toán vận tải để lựa chọn địa điểm xây dựng cơ sở sản xuất cho doanh nghiệp đã chú ý đến
- Chi phí để sản xuất và vận chuyển một đơn vị sản phẩm từ những địa điểm dự định lựa chọn đến các đại lý
- Giá bán một đơn vị sản phẩm tại các địa điểm tiêu thụ
- Các chi phí khác liên quan đến việc xây dựng cơ sở sản xuất tại những địa điểm dự định lựa chọn
- Khả năng nâng cao công suất sản xuất sản phẩm tại những cơ sở sản xuất đã có
Khi sử dụng phương pháp đơn hình để giải bài toán quy hoạch tuyến tính để tìm Max :
- Phương án tối ưu là phương án có các số kiểm tra ∆_j<0 , j b. 1,2,….,n c. Phương án tối ưu là phương án có các số kiểm tra ∆_j>0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j
- 0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j≥0 , j
Khi sử dụng thuật toán gán nhãn để tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v của một đồ thị liên thông thì
- Phải gán nhãn cho các đỉnh trong quá trình giải
- Nhãn l(x) của đỉnh x cho biết giới hạn trên của chiều dài đường đi từ định u đến đỉnh x
- Khi nhãn l(x) của đỉnh x không giảm được nữa thì đỉnh x trở thành đỉnh cố định
- Thuật toán có thể không tìm được đường đi ngắn nhất
Bài toán sản xuất đồng bộ điển hình
- Luôn yêu cầu mỗi máy phải sản xuất được mọi loại chi tiết để lắp ráp sản phẩm
- Với mục tiêu là xác định số lượng sản phẩm được sản xuất trong một giờ để giá trị sản lượng lớn nhất
- Với mục tiêu là xác định số lượng sản phẩm được sản xuất trong một giờ để tổng chi phí sản xuất sản phẩm nhỏ nhất
- Với mục tiêu là xác định số lượng sản phẩm lắp ráp được trong một giờ là lớn nhất
Bài toán sản xuất đồng bộ tổng quát
- Chỉ xác định được việc sản xuất đồng bộ của các máy trong một giờ
- Chỉ có thể được giải bằng phương pháp đơn hình
- Luôn có phương án tối ưu
- Phương án tối ưu là duy nhất
Bài toán cực tiểu hóa chi phí sản xuất của doanh nghiệp:
- Đã quan tâm đến mức sản lượng để đáp ứng nhu cầu của khách hàng theo hợp đồng
- Đã quan tâm đến giới hạn của các yếu tố đầu vào khi tiến hành sản xuất
- Đã quan tâm đến sự thay thế các yếu tố đầu vào khi tiến hành sản xuất
- Đã quan tâm đến giới hạn nhu cầu của thị trường về sản phẩm của doanh nghiệp
Bài toán nhiều máy gia công hai loại chi tiết
- Để tìm phương án tối ưu cần chuyển về bài toán sản xuất đồng bộ điển hình
- Để tìm phương án tối ưu cần xác định những chi tiết chỉ do một máy sản xuất
- Để tìm phương án tối ưu cần xác định chi tiết được hai máy tham gia sản xuất
- Để tìm phương án tối ưu cần xác định một máy tham gia sản xuất cả hai loại chi tiết
Nếu giả thiết chi phí để thực hiện công việc ( i,j ) là hàm số tuyến tính của thời gian thực hiện công việc t_(i j) thì bài toán cực tiểu chi phí hoàn thành dự án
- Là một bài toán quy hoạch tuyến tính
- Có biến số là thời điểm đạt tới các sự kiện và thời gian cần thiết để hoàn thành công việc của dự án
- Có biến số là tổng chi phí cần thiết để hoàn thành dự án
- Phải biết được khoảng thời gian cho phép phải hoàn thành dự án
Phương pháp tối ưu trong kinh doanh
- Có thể hỗ trợ nhà quản trị ra quyết định trong việc phân bổ các nguồn lực của doanh nghiệp
- Có thể hỗ trợ nhà quản trị lựa chọn phương án sản xuất kinh doanh tối ưu với những ràng buộc hạn chế
- Có thể hỗ trợ nhà quản trị xác định nhu cầu của thị trường về sản phẩm của doanh nghiệp
- Có thể hỗ trợ nhà quản trị xác định lượng dự trữ nguyên vật liệu tối ưu
Bài toán quy hoạch tuyến tính là bài toán
- Có hàm mục tiêu là hàm số tuyến tính của các biến số
- Có ràng buộc là các phương trình, bất phương trình tuyến tính của các biến số
- Có thể là bài toán tìm Max hoặc bài toán tìm Min
- Luôn tồn tại lời giải tối ưu
Bài toán cực tiểu hóa chi tiêu của hộ gia đình
- Đã quan tâm đến giá cả hàng hóa trong tiêu dùng của hộ gia đình
- Đã quan tâm đến lợi ích tiêu dùng tối thiểu mà hộ gia đình cần phải đảm bảo
- Đã quan tâm đến những hàng hóa cơ bản tạo ra lợi ích tiêu dùng của hộ gia đình
- Đã quan tâm đến mức tiêu dùng tối thiểu cần phải đảm bảo đối với từng loại hàng hóa
Khi sử dụng phương pháp đơn hình để giải bài toán quy hoạch tuyến tính để tìm Min
- Phương án tối ưu là phương án có các số kiểm tra ∆_j<0 , j b. 1,2,….,n c. Phương án tối ưu là phương án có các số kiểm tra ∆_j≤0 , j d. 1,2,….,n e. Phương án tối ưu là phương án có các số kiểm tra ∆_j>0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j≥0 , j
- 1,2,….,n
Khi sử dụng bài toán vận tải để xác định khối lượng sản phẩm sản xuất, vận chuyển và tiêu thụ cho doanh nghiệp đã không chú ý đến
- Chi phí sản xuất một đơn vị sản phẩm tại các cơ sở sản xuất
- Giá bán một đơn vị sản phẩm tại các cơ sở tiêu thụ
- Chi phí vận chuyển một đơn vị sản phẩm từ các cơ sở sản xuất đến các cơ sở tiêu thụ
- Sự thay đổi chi phí sản xuất và giá bán đơn vị sản phẩm tại các cơ sở sản xuất và tại các cơ sở tiêu thụ sản phẩm trong kỳ kế hoạch
Mọi bài toán quy hoạch tuyến tính đều có lời giải tối ưu nếu :
- Có phương án
- Có phương án cực biên
- Hàm mục tiêu bị chặn
- Có phương án và hàm mục tiêu bị chặn
Bài toán sản xuất, vận chuyển và tiêu thụ
- Là bài toán vận tải thông thường như đã phát biểu trong mục 3.1.1.
- Phương án tối ưu luôn cho chúng ta tổng chi phí vận chuyển trong kỳ kế hoạch là nhỏ nhất
- Phương án tối ưu luôn cho chúng ta tổng chi phí sản xuất trong kỳ kế hoạch tại các cơ sở sản xuất là nhỏ nhất
- Phương án tối ưu luôn cho chúng ta tổng lợi nhuận thu được tại các cơ sở tiêu thụ trong kỳ kế hoạch là lớn nhất
Bài toán sản xuất đồng bộ điển hình
- Luôn yêu cầu các máy đều phải sản xuất được tất cả các loại chi tiết
- Chỉ sử dụng để phân công sản xuất cho các máy trong một giờ
- Khi năng suất của các máy khi sản xuất từng loại chi tiết đều được tăng lên k lần thì phương án tối ưu sẽ không thay đổi
- Khi năng suất của các máy khi sản xuất từng loại chi tiết đều được tăng lên k lần thì phương án tối ưu sẽ thay đổi
Với cây bao trùm bé nhất T của đồ thị G thì mỗi cạnh (u,v) của G nhưng không thuộc T
- Đều tạo ra với những cạnh của T một chu trình duy nhất
- Cạnh (u,v) là cạnh có độ dài lớn nhất so với những cạnh của chu trình mà nó tạo ra với những cạnh của T
- Cạnh (u,v) là cạnh có độ dài nhỏ nhất so với những cạnh của chu trình mà nó tạo ra với những cạnh của T
- Cạnh (u,v) vẫn có thể trở thành một cạnh của một cây bao trùm bé nhất khác của đồ thị G
Mệnh đề nào là sai trong những mệnh đề sau:
- Không có vấn đề thì không có quyết định
- Không giải quyết được vấn đề thì không có quyết định
- Giải quyết được vấn đề thì chắc chắn có quyết định
- Ra quyết định là một quá trình lựa chọn có ý thức
Khi sử dụng bài toán vận tải để phân công công việc đã chú ý đến điều kiện :
- Một người có thể đảm nhận thực hiện nhiều công việc
- Một công việc có thể do nhiều người đảm nhận thực hiện
- Mỗi người chỉ đảm nhận một công việc và mỗi công việc chỉ do một người đảm nhận
- Chất lượng công việc sau khi hoàn thành
Khi sử dụng bài toán phụ để tìm phương án cực biên của bài toán quy hoạch tuyến tính :
- Bài toán phụ là bài toán tìm Max
- Bài toán phụ luôn có m biến
- Nếu giá trị nhỏ nhất của hàm mục tiêu của bài toán phụ dương thì bài toán chính không có phương án cực biên
- Cần tính toán số kiểm tra cho các cột ứng với biến giả trong suốt quá trình giải
Bài toán hai máy gia công nhiều loại chi tiết
- Là bài toán sản xuất đồng bộ tổng quát
- Để tìm phương án tối ưu phải tính tỉ số năng suất của hai máy khi sản xuất từng loại chi tiết
- Để tìm phương án tối ưu cần xác định một chi tiết mà cả hai máy cùng tham gia sản xuất
- Luôn tìm được phương án tối ưu
Sử dụng Bài toán lập tiến độ sản xuất đã
- Quan tâm đến khối lượng sản phẩm doanh nghiệp cần cung cấp cho khách hàng trong từng tháng
- Quan tâm đến sự thay đổi năng lực sản xuất của doanh nghiệp trong từng tháng
- Quan tâm đến sự thay đổi chi phí sản xuất, chi phí lưu kho cho một đơn vị sản phẩm theo từng tháng
- Quan tâm đến sự thay đổi khả năng tiêu thụ sản phẩm của doanh nghiệp trong từng tháng
Cây là một đồ thị vô hướng
- Có n đỉnh và có n cạnh (n là số đỉnh của đồ thị)
- Luôn liên thông và chứa chu trình
- Không liên thông và không chứa chu trình
- Liên thông và có n-1 cạnh
Phương án cực biên của bài toán vận tải:
- Luôn tồn tại
- Luôn bao gồm m+n-1 ô có hàng
- Các ô có hàng của phương án cực biên luôn tạo thành chu trình
- Luôn là phương án tối ưu
Sơ đồ mạng của một dự án (sơ đồ PERT)
- Luôn có đường găng
- Có thể có nhiều đường găng
- Đường găng là đường có độ dài ngắn nhất đi từ sự kiện khởi công dự án đến sự kiện kết thúc dự án
- Đường găng là đường có độ dài dài nhất đi từ sự kiện khởi công dự án đến sự kiện kết thúc dự án
Sử dụng Bài toán lập kế hoạch sản xuất để xác định số lượng từng loại sản phẩm mà doanh nghiệp sẽ sản xuất trong kỳ kế hoạch đã :
- Quan tâm đến giới hạn cầu của thị trường về từng loại sản phẩm của doanh nghiệp trong kỳ kế hoạch
- Quan tâm đến việc bổ sung các nguồn lực cho doanh nghiệp trong kỳ kế hoạch
- Quan tâm đến lượng sản phẩm các loại còn tồn đọng từ kỳ kế hoạch trước
- Quan tâm đến sự thay đổi định mức sử dụng các nguồn lực khi sản xuất sản phẩm trong kỳ kế hoạch
Mọi bài toán quy hoạch tuyến tính đều có thể chuyển về bài toán dạng chính tắc nhờ:
- Đổi dấu các hệ số của hàm mục tiêu
- Loại bỏ những ràng buộc dạng bất đẳng thức
- Sử dụng các biến bù với hệ số của các biến bù trong hàm mục tiêu bằng 0
- Sử dụng cả A và B
Bài toán xe không
- Là bài toán vận tải với điểm phát và điểm thu sản phẩm như đã phát biểu trong mục 3.1.1.
- Là bài toán vận tải với bảng vận tải mà điểm phát trở thành điểm thu và ngược lại
- Là bài toán vận tải với bảng vận tải trong đó chi phí vận chuyển một đơn vị sản phẩm từ điểm phát i đến điểm thu j được thay bằng khoảng cách giữa điểm thu j đến điểm phát i
- Là bài toán vận tải với hàm mục tiêu là cực tiểu số tấn x km chạy xe không tải cho một hợp đồng vận chuyển
Bài toán xe không
- Đã quan tâm đến chi phí vận chuyển một đơn vị sản phẩm từ các điểm phát đến các điểm thu
- Nhằm xác định kế hoạch vận chuyển tối ưu sản phẩm từ các điểm phát đến các điểm thu
- Nhằm xác định tổng chi phí vận chuyển nhỏ nhất cho hợp đồng vận chuyển
- Nhằm xác định số tấn x km chạy xe không tải cho hợp động vận chuyển là nhỏ nhất
Nếu giả thiết chi phí để thực hiện công việc ( i,j ) là hàm số tuyến tính của thời gian thực hiện công việc t_(i j) thì bài toán cực tiểu thời gian hoàn thành dự án
- Là một bài toán quy hoạch tuyến tính
- Có biến số là thời điểm đạt tới các sự kiện và thời gian cần thiết để hoàn thành công việc của dự án
- Có biến số là thời gian cần thiết để hoàn thành dự án
- Phải biết được tổng chi phí được phép để thực hiện dự án
Bài toán vận tải :
- Không phải là bài toán quy hoạch tuyến tính
- Tổng lượng hàng của các điểm phát luôn bằng tổng lượng hàng của các điểm thu
- Luôn có lời giải tối ưu
- Lời giải tối ưu là những số nguyên dương
Cây bao trùm của một đồ thị vô hướng n đỉnh
- Luôn liên thông
- Không chứa chu trình
- Cứ thêm vào 1 cạnh thì thu được đúng một chu trình
- Chỉ có n-1 đỉnh
Điều kiện cần và đủ để bài toán vận tải có phương án tối ưu duy nhất là
- Tất cả các ô của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn đẳng thức u_i+v_j
- c_ij
- Tất cả các ô của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức
- Tất cả các ô có hàng của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức u_i+v_j
- Tất cả các ô không có hàng của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức u_i+v_j
Sử dụng phương pháp sơ đồ mạng để điều hành dự án cần
- Xác định thời gian cần thiết để thực hiện các công việc của dự án
- Xác định đường găng của sơ đồ
- Xác định thời gian dự trữ của các công việc
- Xác định chi phí các nguồn lực cần thiết để thực hiện các công việc của dự án
Bài toán sản xuất đồng bộ tổng quát
- Luôn giả thiết rằng doanh nghiệp có nhiều loại máy và với mỗi loại có thể có nhiều máy
- Luôn giả thiết rằng sản phẩm của doanh nghiệp được lắp ráp từ nhiều loại chi tiết và mỗi loại có thể cần nhiều chi tiết
- Luôn có thể chuyển về bài toán sản xuất đồng bộ điển hình
- Luôn có phương án tối ưu duy nhất
Bài toán sản xuất đồng bộ điển hình
- Không phải là một bài toán quy hoạch tuyến tính
- Luôn giả thiết là với mỗi loại máy doanh nghiệp chỉ có một máy
- Luôn giả thiết là mỗi sản phẩm được lắp ráp từ nhiều loại chi tiết và cần một chi tiết cho mỗi loại
- Luôn giả thiết là năng suất của mỗi máy khi sản xuất từng loại chi tiết là không thay đổi
Điều kiện cần và đủ để một phương án của bài toán vận tải là phương án tối ưu là
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô không có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j≤c_(ij ) ở những ô không có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô có hàng và u_i+v_j≤c_ij ở những ô không có hàng
Mạng
- Là một đồ thị vô hướng
- Có một đỉnh duy nhất không có cung đi vào
- Có một đỉnh duy nhất không có cung đi ra
- Mỗi cung ( i,j ) của mạng đều gắn với một khả năng thông qua C(i,j)
Sử dụng phương pháp đơn hình để giải Bài toán pha cắt vật liệu đã :
- Quan tâm đến số lượng những tấm vật liệu có kích thước nhỏ hơn cần thiết để phục vụ cho kế hoạch sản xuất sản phẩm
- Quan tâm đến số tấm vật liệu cần phải có để phục vụ cho kế hoạch sản xuất sản phẩm
- Quan tâm đến số tấm vật liệu có kích thước nhỏ hơn tồn đọng từ các kế hoạch sản xuất trước
- Quan tâm đến việc sử dụng những tấm vật liệu có kích thước nhỏ hơn cho các kế hoạch sản xuất tiếp theo
Mọi bài toán quy hoạch tuyến tính đều có lời giải tối ưu nếu
- Bài toán có vô số phương án tối ưu
- Phương án tối ưu là không duy nhất
- Bài toán không có lời giải vì hàm mục tiêu không bị chặn
- Phương án tối ưu không phải là phương án cực biên
Bài toán nhiều máy gia công hai loại chi tiết
- Là bài toán sản xuất đồng bộ tổng quát
- Để tìm phương án tối ưu cần phải tính tỉ số năng suất của từng máy khi sản xuất hai loại chi tiết
- Để tìm phương án tối ưu cần xác định một máy tham gia sản xuất cả hai loại chi tiết
- Luôn tìm được phương án tối ưu
Bài toán hai máy gia công nhiều chi tiết
- Để tìm phương án tối ưu cần phải chuyển về bài toán sản xuất đồng bộ điển hình
- Để tìm phương án tối ưu cần phải xác định máy tham gia sản xuất hai loại chi tiết
- Để tìm phương án tối ưu cần phải xác định chi tiết được cả hai máy cùng tham gia sản xuất
- Trong nhiều trường hợp không tìm được phương án tối ưu
Bài toán cực đại hóa giá trị sản lượng của doanh nghiệp:
- Mới chỉ quan tâm đến việc sản xuất một loại sản phẩm
- Đã quan tâm đến giới hạn của các nguồn lực khi tiến hành sản xuất sản phẩm
- Đã quan tâm đến cầu của thị trường về sản phẩm của doanh nghiệp
- Đã quan tâm đến lợi nhuận mà doanh nghiệp thu được khi tiêu thụ sản phẩm
Phương án cực biên của bài toán vận tải:
- Luôn tồn tại
- Luôn bao gồm m+n-1 ô có hàng
- Các ô có hàng của phương án cực biên luôn tạo thành chu trình
- Luôn là phương án tối ưu
Bài toán xe không
- Là bài toán vận tải với điểm phát và điểm thu sản phẩm như đã phát biểu trong mục 3.1.1.
- Là bài toán vận tải với bảng vận tải mà điểm phát trở thành điểm thu và ngược lại
- Là bài toán vận tải với bảng vận tải trong đó chi phí vận chuyển một đơn vị sản phẩm từ điểm phát i đến điểm thu j được thay bằng khoảng cách giữa điểm thu j đến điểm phát i
- Là bài toán vận tải với hàm mục tiêu là cực tiểu số tấn x km chạy xe không tải cho một hợp đồng vận chuyển
Bài toán sản xuất đồng bộ tổng quát
- Luôn giả thiết rằng với mỗi loại máy doanh nghiệp chỉ có một máy
- Luôn giả thiết rằng sản phẩm của doanh nghiệp được lắp ráp từ nhiều loại chi tiết và mỗi loại cần một chi tiết
- Luôn tìm được phương án tối ưu
- Trong nhiều trường hợp không tìm được phương án tối ưu
Bài toán nhiều máy gia công hai loại chi tiết
- Để tìm phương án tối ưu cần chuyển về bài toán sản xuất đồng bộ điển hình
- Để tìm phương án tối ưu cần xác định những chi tiết chỉ do một máy sản xuất
- Để tìm phương án tối ưu cần xác định chi tiết được hai máy tham gia sản xuất
- Để tìm phương án tối ưu cần xác định một máy tham gia sản xuất cả hai loại chi tiết
Khi sử dụng bài toán vận tải để lựa chọn địa điểm xây dựng cơ sở sản xuất cho doanh nghiệp đã chú ý đến
- Chi phí để sản xuất và vận chuyển một đơn vị sản phẩm từ những địa điểm dự định lựa chọn đến các đại lý
- Giá bán một đơn vị sản phẩm tại các địa điểm tiêu thụ
- Các chi phí khác liên quan đến việc xây dựng cơ sở sản xuất tại những địa điểm dự định lựa chọn
- Khả năng nâng cao công suất sản xuất sản phẩm tại những cơ sở sản xuất đã có
Nếu giả thiết chi phí để thực hiện công việc ( i,j ) là hàm số tuyến tính của thời gian thực hiện công việc t_(i j) thì bài toán cực tiểu chi phí hoàn thành dự án
- Là một bài toán quy hoạch tuyến tính
- Có biến số là thời điểm đạt tới các sự kiện và thời gian cần thiết để hoàn thành công việc của dự án
- Có biến số là tổng chi phí cần thiết để hoàn thành dự án
- Phải biết được khoảng thời gian cho phép phải hoàn thành dự án
Mọi bài toán quy hoạch tuyến tính đều có lời giải tối ưu nếu :
- Có phương án
- Có phương án cực biên
- Hàm mục tiêu bị chặn
- Có phương án và hàm mục tiêu bị chặn
Bài toán vận tải :
- Không phải là bài toán quy hoạch tuyến tính
- Tổng lượng hàng của các điểm phát luôn bằng tổng lượng hàng của các điểm thu
- Luôn có lời giải tối ưu
- Lời giải tối ưu là những số nguyên dương
Cây bao trùm của một đồ thị vô hướng n đỉnh
- Luôn liên thông
- Không chứa chu trình
- Cứ thêm vào 1 cạnh thì thu được đúng một chu trình
- Chỉ có n-1 đỉnh
Bài toán sản xuất đồng bộ điển hình
- Luôn yêu cầu mỗi máy phải sản xuất được mọi loại chi tiết để lắp ráp sản phẩm
- Với mục tiêu là xác định số lượng sản phẩm được sản xuất trong một giờ để giá trị sản lượng lớn nhất
- Với mục tiêu là xác định số lượng sản phẩm được sản xuất trong một giờ để tổng chi phí sản xuất sản phẩm nhỏ nhất
- Với mục tiêu là xác định số lượng sản phẩm lắp ráp được trong một giờ là lớn nhất
Khi sử dụng bài toán phụ để tìm phương án cực biên của bài toán quy hoạch tuyến tính :
- Bài toán phụ là bài toán tìm Max
- Bài toán phụ luôn có m biến
- Nếu giá trị nhỏ nhất của hàm mục tiêu của bài toán phụ dương thì bài toán chính không có phương án cực biên
- Cần tính toán số kiểm tra cho các cột ứng với biến giả trong suốt quá trình giải
Phương pháp tối ưu
- Là các phương pháp để giải các bài toán tối ưu
- Là kết quả nghiên cứu của Lý thuyết tối ưu
- Hỗ trợ nhà quản trị tìm phương án án tối ưu khi giải quyết các vấn đề trong kinh doanh
- Không phụ thuộc vào mục tiêu cần đạt được và những ràng buộc khi giải quyết vấn đề
Sử dụng Bài toán lập kế hoạch sản xuất để xác định số lượng từng loại sản phẩm mà doanh nghiệp sẽ sản xuất trong kỳ kế hoạch đã :
- Quan tâm đến giới hạn cầu của thị trường về từng loại sản phẩm của doanh nghiệp trong kỳ kế hoạch
- Quan tâm đến việc bổ sung các nguồn lực cho doanh nghiệp trong kỳ kế hoạch
- Quan tâm đến lượng sản phẩm các loại còn tồn đọng từ kỳ kế hoạch trước
- Quan tâm đến sự thay đổi định mức sử dụng các nguồn lực khi sản xuất sản phẩm trong kỳ kế hoạch
Với cây bao trùm bé nhất T của đồ thị G thì mỗi cạnh (u,v) của G nhưng không thuộc T
- Đều tạo ra với những cạnh của T một chu trình duy nhất
- Cạnh (u,v) là cạnh có độ dài lớn nhất so với những cạnh của chu trình mà nó tạo ra với những cạnh của T
- Cạnh (u,v) là cạnh có độ dài nhỏ nhất so với những cạnh của chu trình mà nó tạo ra với những cạnh của T
- Cạnh (u,v) vẫn có thể trở thành một cạnh của một cây bao trùm bé nhất khác của đồ thị G
Cây là một đồ thị vô hướng
- Có n đỉnh và có n cạnh (n là số đỉnh của đồ thị)
- Luôn liên thông và chứa chu trình
- Không liên thông và không chứa chu trình
- Liên thông và có n-1 cạnh
Sử dụng Bài toán lập tiến độ sản xuất đã
- Quan tâm đến khối lượng sản phẩm doanh nghiệp cần cung cấp cho khách hàng trong từng tháng
- Quan tâm đến sự thay đổi năng lực sản xuất của doanh nghiệp trong từng tháng
- Quan tâm đến sự thay đổi chi phí sản xuất, chi phí lưu kho cho một đơn vị sản phẩm theo từng tháng
- Quan tâm đến sự thay đổi khả năng tiêu thụ sản phẩm của doanh nghiệp trong từng tháng
Khi sử dụng bài toán vận tải để xác định khối lượng sản phẩm sản xuất, vận chuyển và tiêu thụ cho doanh nghiệp đã không chú ý đến
- Chi phí sản xuất một đơn vị sản phẩm tại các cơ sở sản xuất
- Giá bán một đơn vị sản phẩm tại các cơ sở tiêu thụ
- Chi phí vận chuyển một đơn vị sản phẩm từ các cơ sở sản xuất đến các cơ sở tiêu thụ
- Sự thay đổi chi phí sản xuất và giá bán đơn vị sản phẩm tại các cơ sở sản xuất và tại các cơ sở tiêu thụ sản phẩm trong kỳ kế hoạch
Bài toán quy hoạch toán học là bài toán
- Có hàm mục tiêu là hàm số tuyến tính của các biến số
- Có ràng buộc được thể hiện dưới dạng các phương trình, các bất phương trình của các biến số
- Các biến số phải là những số không âm
- Luôn có thể tìm được phương án tối ưu
Bài toán sản xuất đồng bộ tổng quát
- Chỉ xác định được việc sản xuất đồng bộ của các máy trong một giờ
- Chỉ có thể được giải bằng phương pháp đơn hình
- Luôn có phương án tối ưu
- Phương án tối ưu là duy nhất
Sử dụng bài toán tối ưu để giải quyết các vấn đề thực tế trong kinh doanh cần
- Xác định vấn đề cần phải giải quyết
- Xác định mục tiêu cần đạt được khi giải quyết vấn đề
- Xác định những ràng buộc khi giải quyết vấn đề
- Không cần phải kiểm định lại kết quả thu được sau khi áp dụng phương pháp tối ưu để giải bài toán
Sử dụng phương pháp đơn hình để giải Bài toán pha cắt vật liệu đã :
- Quan tâm đến số lượng những tấm vật liệu có kích thước nhỏ hơn cần thiết để phục vụ cho kế hoạch sản xuất sản phẩm
- Quan tâm đến số tấm vật liệu cần phải có để phục vụ cho kế hoạch sản xuất sản phẩm
- Quan tâm đến số tấm vật liệu có kích thước nhỏ hơn tồn đọng từ các kế hoạch sản xuất trước
- Quan tâm đến việc sử dụng những tấm vật liệu có kích thước nhỏ hơn cho các kế hoạch sản xuất tiếp theo
Phương pháp tối ưu trong kinh doanh
- Có thể hỗ trợ nhà quản trị ra quyết định trong việc phân bổ các nguồn lực của doanh nghiệp
- Có thể hỗ trợ nhà quản trị lựa chọn phương án sản xuất kinh doanh tối ưu với những ràng buộc hạn chế
- Có thể hỗ trợ nhà quản trị xác định nhu cầu của thị trường về sản phẩm của doanh nghiệp
- Có thể hỗ trợ nhà quản trị xác định lượng dự trữ nguyên vật liệu tối ưu
Bài toán cực tiểu hóa chi phí sản xuất của doanh nghiệp:
- Đã quan tâm đến mức sản lượng để đáp ứng nhu cầu của khách hàng theo hợp đồng
- Đã quan tâm đến giới hạn của các yếu tố đầu vào khi tiến hành sản xuất
- Đã quan tâm đến sự thay thế các yếu tố đầu vào khi tiến hành sản xuất
- Đã quan tâm đến giới hạn nhu cầu của thị trường về sản phẩm của doanh nghiệp
Sơ đồ mạng của một dự án (sơ đồ PERT)
- Luôn có đường găng
- Có thể có nhiều đường găng
- Đường găng là đường có độ dài ngắn nhất đi từ sự kiện khởi công dự án đến sự kiện kết thúc dự án
- Đường găng là đường có độ dài dài nhất đi từ sự kiện khởi công dự án đến sự kiện kết thúc dự án
Sử dụng phương pháp sơ đồ mạng để điều hành dự án cần
- Xác định thời gian cần thiết để thực hiện các công việc của dự án
- Xác định đường găng của sơ đồ
- Xác định thời gian dự trữ của các công việc
- Xác định chi phí các nguồn lực cần thiết để thực hiện các công việc của dự án
Khi sử dụng phương pháp đơn hình để giải bài toán quy hoạch tuyến tính để tìm Min
- Phương án tối ưu là phương án có các số kiểm tra ∆_j<0 , j b. 1,2,….,n c. Phương án tối ưu là phương án có các số kiểm tra ∆_j≤0 , j d. 1,2,….,n e. Phương án tối ưu là phương án có các số kiểm tra ∆_j>0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j≥0 , j
- 1,2,….,n
Mạng
- Là một đồ thị vô hướng
- Có một đỉnh duy nhất không có cung đi vào
- Có một đỉnh duy nhất không có cung đi ra
- Mỗi cung ( i,j ) của mạng đều gắn với một khả năng thông qua C(i,j)
Mệnh đề nào dưới đây là mệnh đề đúng:
- Mọi bài toán quy hoạch tuyến tính đều có phương án
- Mọi bài toán quy hoạch tuyến tính đều có phương án cực biên
- Nếu bài toán quy hoạch tuyến tính có phương án thì nó phương án cực biên
- Mọi phương án cực biên đều có đúng m thành phần dương (m là số các ràng buộc của bài toán quy hoạch tuyến tính)
Nếu giả thiết chi phí để thực hiện công việc ( i,j ) là hàm số tuyến tính của thời gian thực hiện công việc t_(i j) thì bài toán cực tiểu thời gian hoàn thành dự án
- Là một bài toán quy hoạch tuyến tính
- Có biến số là thời điểm đạt tới các sự kiện và thời gian cần thiết để hoàn thành công việc của dự án
- Có biến số là thời gian cần thiết để hoàn thành dự án
- Phải biết được tổng chi phí được phép để thực hiện dự án
Khi sử dụng thuật toán gán nhãn để tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v của một đồ thị liên thông thì
- Phải gán nhãn cho các đỉnh trong quá trình giải
- Nhãn l(x) của đỉnh x cho biết giới hạn trên của chiều dài đường đi từ định u đến đỉnh x
- Khi nhãn l(x) của đỉnh x không giảm được nữa thì đỉnh x trở thành đỉnh cố định
- Thuật toán có thể không tìm được đường đi ngắn nhất
Mọi bài toán quy hoạch tuyến tính đều có thể chuyển về bài toán dạng chính tắc nhờ:
- Đổi dấu các hệ số của hàm mục tiêu
- Loại bỏ những ràng buộc dạng bất đẳng thức
- Sử dụng các biến bù với hệ số của các biến bù trong hàm mục tiêu bằng 0
- Sử dụng cả A và B
Khi sử dụng bài toán vận tải để phân công công việc đã chú ý đến điều kiện :
- Một người có thể đảm nhận thực hiện nhiều công việc
- Một công việc có thể do nhiều người đảm nhận thực hiện
- Mỗi người chỉ đảm nhận một công việc và mỗi công việc chỉ do một người đảm nhận
- Chất lượng công việc sau khi hoàn thành
Điều kiện cần và đủ để bài toán vận tải có phương án tối ưu duy nhất là
- Tất cả các ô của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn đẳng thức u_i+v_j
- c_ij
- Tất cả các ô của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức
- Tất cả các ô có hàng của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức u_i+v_j
- Tất cả các ô không có hàng của bảng vận tải cuối cùng ứng với phương án tối ưu đều thỏa mãn bất đẳng thức u_i+v_j
Bài toán sản xuất, vận chuyển và tiêu thụ
- Là bài toán vận tải thông thường như đã phát biểu trong mục 3.1.1.
- Phương án tối ưu luôn cho chúng ta tổng chi phí vận chuyển trong kỳ kế hoạch là nhỏ nhất
- Phương án tối ưu luôn cho chúng ta tổng chi phí sản xuất trong kỳ kế hoạch tại các cơ sở sản xuất là nhỏ nhất
- Phương án tối ưu luôn cho chúng ta tổng lợi nhuận thu được tại các cơ sở tiêu thụ trong kỳ kế hoạch là lớn nhất
Bài toán hai máy gia công nhiều loại chi tiết
- Là bài toán sản xuất đồng bộ tổng quát
- Để tìm phương án tối ưu phải tính tỉ số năng suất của hai máy khi sản xuất từng loại chi tiết
- Để tìm phương án tối ưu cần xác định một chi tiết mà cả hai máy cùng tham gia sản xuất
- Luôn tìm được phương án tối ưu
Bài toán cực tiểu hóa chi tiêu của hộ gia đình
- Đã quan tâm đến giá cả hàng hóa trong tiêu dùng của hộ gia đình
- Đã quan tâm đến lợi ích tiêu dùng tối thiểu mà hộ gia đình cần phải đảm bảo
- Đã quan tâm đến những hàng hóa cơ bản tạo ra lợi ích tiêu dùng của hộ gia đình
- Đã quan tâm đến mức tiêu dùng tối thiểu cần phải đảm bảo đối với từng loại hàng hóa
Bài toán sản xuất đồng bộ tổng quát
- Luôn giả thiết rằng doanh nghiệp có nhiều loại máy và với mỗi loại có thể có nhiều máy
- Luôn giả thiết rằng sản phẩm của doanh nghiệp được lắp ráp từ nhiều loại chi tiết và mỗi loại có thể cần nhiều chi tiết
- Luôn có thể chuyển về bài toán sản xuất đồng bộ điển hình
- Luôn có phương án tối ưu duy nhất
Khi sử dụng phương pháp đơn hình ở bảng cuối cùng ứng với phương án tối ưu có những số kiểm tra ∆_k=0 ứng với những véc tơ phi cơ sở thì điều đó cho thấy :
- Bài toán có vô số phương án tối ưu
- Phương án tối ưu là không duy nhất
- Bài toán không có lời giải vì hàm mục tiêu không bị chặn
- Phương án tối ưu không phải là phương án cực biên
Mệnh đề nào là sai trong những mệnh đề sau:
- Không có vấn đề thì không có quyết định
- Không giải quyết được vấn đề thì không có quyết định
- Giải quyết được vấn đề thì chắc chắn có quyết định
- Ra quyết định là một quá trình lựa chọn có ý thức
Bài toán nhiều máy gia công hai loại chi tiết
- Là bài toán sản xuất đồng bộ tổng quát
- Để tìm phương án tối ưu cần phải tính tỉ số năng suất của từng máy khi sản xuất hai loại chi tiết
- Để tìm phương án tối ưu cần xác định một máy tham gia sản xuất cả hai loại chi tiết
- Luôn tìm được phương án tối ưu
Bài toán cực đại hóa lợi ích tiêu dùng của hộ gia đình:
- Đã quan tâm đến hạn chế về tài chính của hộ gia đình khi tiêu dùng các loại hàng hóa
- Đã quan tâm đến sự thay thế các loại hàng hóa trong tiêu dùng của hộ gia đình
- Đã quan tâm đến mức tiêu dùng tối thiểu cần phải có đối với từng loại hàng hóa của hộ gia đình
- Đã quan tâm đến sự thay đổi giá cả hàng hóa trên thị trường
Cây bao trùm T=(E,F) của đồ thị G=(D,C)
- Là một đồ thị có hướng
- Là một đồ thị liên thông và có n-1 cạnh
- Là một đồ thị có n đỉnh như đồ thị G
- Là một đồ thị không chứa chu trình
Khi sử dụng phương pháp đơn hình để giải bài toán quy hoạch tuyến tính để tìm Max :
- Phương án tối ưu là phương án có các số kiểm tra ∆_j<0 , j b. 1,2,….,n c. Phương án tối ưu là phương án có các số kiểm tra ∆_j>0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j
- 0 , j
- 1,2,….,n
- Phương án tối ưu là phương án có các số kiểm tra ∆_j≥0 , j
Bài toán quy hoạch tuyến tính là bài toán
- Có hàm mục tiêu là hàm số tuyến tính của các biến số
- Có ràng buộc là các phương trình, bất phương trình tuyến tính của các biến số
- Có thể là bài toán tìm Max hoặc bài toán tìm Min
- Luôn tồn tại lời giải tối ưu
Bài toán sản xuất đồng bộ điển hình
- Luôn yêu cầu các máy đều phải sản xuất được tất cả các loại chi tiết
- Chỉ sử dụng để phân công sản xuất cho các máy trong một giờ
- Khi năng suất của các máy khi sản xuất từng loại chi tiết đều được tăng lên k lần thì phương án tối ưu sẽ không thay đổi
- Khi năng suất của các máy khi sản xuất từng loại chi tiết đều được tăng lên k lần thì phương án tối ưu sẽ thay đổi
Bài toán cực đại hóa giá trị sản lượng của doanh nghiệp:
- Mới chỉ quan tâm đến việc sản xuất một loại sản phẩm
- Đã quan tâm đến giới hạn của các nguồn lực khi tiến hành sản xuất sản phẩm
- Đã quan tâm đến cầu của thị trường về sản phẩm của doanh nghiệp
- Đã quan tâm đến lợi nhuận mà doanh nghiệp thu được khi tiêu thụ sản phẩm
Bài toán sản xuất đồng bộ điển hình
- Không phải là một bài toán quy hoạch tuyến tính
- Luôn giả thiết là với mỗi loại máy doanh nghiệp chỉ có một máy
- Luôn giả thiết là mỗi sản phẩm được lắp ráp từ nhiều loại chi tiết và cần một chi tiết cho mỗi loại
- Luôn giả thiết là năng suất của mỗi máy khi sản xuất từng loại chi tiết là không thay đổi
Bài toán xe không
- Đã quan tâm đến chi phí vận chuyển một đơn vị sản phẩm từ các điểm phát đến các điểm thu
- Nhằm xác định kế hoạch vận chuyển tối ưu sản phẩm từ các điểm phát đến các điểm thu
- Nhằm xác định tổng chi phí vận chuyển nhỏ nhất cho hợp đồng vận chuyển
- Nhằm xác định số tấn x km chạy xe không tải cho hợp động vận chuyển là nhỏ nhất
Điều kiện cần và đủ để một phương án của bài toán vận tải là phương án tối ưu là
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô không có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j≤c_(ij ) ở những ô không có hàng
- Tìm được m số u_i và n số v_j sao cho u_i+v_j
- c_ij ở những ô có hàng và u_i+v_j≤c_ij ở những ô không có hàng
Bài toán hai máy gia công nhiều chi tiết
- Để tìm phương án tối ưu cần phải chuyển về bài toán sản xuất đồng bộ điển hình
- Để tìm phương án tối ưu cần phải xác định máy tham gia sản xuất hai loại chi tiết
- Để tìm phương án tối ưu cần phải xác định chi tiết được cả hai máy cùng tham gia sản xuất
- Trong nhiều trường hợp không tìm được phương án tối ưu
