Kiểm tra tính tối ưu

Kiểm tra tối ưu có thể được thực hiện nếu hai điều kiện được thỏa mãn, tức là

1. Có m + n - 1 phân bổ, có m là số hàng, n là số cột. Ở đây m + n - 1 = 6. Nhưng số lượng phân bổ là năm.

2. Các phân bổ m + n - 1 này phải ở các vị trí độc lập. Tức là không thể tăng hoặc giảm bất kỳ phân bổ nào mà không thay đổi vị trí của phân bổ hoặc vi phạm các hạn chế hàng hoặc coloumn.

Một quy tắc đơn giản để phân bổ ở vị trí độc lập là không thể đi từ bất kỳ phân bổ nào, trở lại chính nó bằng một loạt các bước ngang và dọc tạo thành một ô chiếm chỗ khác, mà không có sự đảo ngược trực tiếp của tuyến đường. Có thể thấy rằng trong ví dụ hiện tại, phân bổ ở các vị trí độc lập vì không có vòng lặp kín nào có thể được hình thành tại các ô được phân bổ.

Do đó, điều kiện đầu tiên không được thỏa mãn và do đó để thỏa mãn điều kiện đầu tiên, chúng tôi sẽ phải phân bổ một lượng nhỏ E tại các ô trống có chi phí vận chuyển thấp nhất. Có thể thấy rằng t có thể được phân bổ tại ô (2, 2) có chi phí là 7 đơn vị và các phân bổ sẽ vẫn ở vị trí độc lập như được mô tả dưới đây:

Bây giờ số lượng phân bổ là m + n- = 6 và chúng ở các vị trí độc lập.

Viết ma trận chi phí tại các ô được phân bổ.

Ma trận chi phí ban đầu cho các ô được phân bổ.

Cũng viết các giá trị của u i và v j như đã giải thích trước đó.

Ma trận đánh giá tế bào

Có thể thấy từ bảng 5 rằng việc đánh giá ô tại ô (1, 4) là âm tức là -4, do đó bằng cách phân bổ tại ô (1, 4) chi phí vận chuyển sẽ giảm hơn nữa. Hãy để chúng tôi viết ra phân bổ ban đầu và phân bổ mới được đề xuất.

Có thể thấy trong bảng 6 rằng nếu chúng ta phân bổ tại ô (1, 4) thì một vòng lặp được hình thành như được hiển thị và chúng ta phân bổ 10 đơn vị để phân bổ tại ô (2, 4) biến mất như trong bảng 7.

Bảng phân bổ mới sẽ trở thành

Chi phí vận chuyển = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 đơn vị. tức là chi phí vận chuyển đã giảm từ 475 đơn vị xuống còn 435 đơn vị.

Kiểm tra Optimaiity:

Hãy cho chúng tôi xem liệu giải pháp này là tối ưu! hay không? Đối với điều đó một lần nữa hai điều kiện phải được kiểm tra tức là

Số phân bổ = m + n - 1 = 6 (hài lòng)

Phân bổ tại vị trí độc lập (thỏa mãn vì vòng kín cho các ô được phân bổ không được hình thành)

Viết chi phí tại tất cả các giá trị và giá trị được phân bổ của u i và v j

Ví dụ 2:

(Cung và cầu không cân bằng). Giải quyết vấn đề vận chuyển sau

Tổng cung = 200 đơn vị, Nhu cầu = 185 đơn vị.

Dung dịch:

Vì cung và cầu không bằng nhau nên vấn đề không cân bằng. Để cân bằng vấn đề, một coloumn giả phải được thêm vào như hình dưới đây. Nhu cầu tại cửa hàng giả đó (cửa hàng) sẽ là 15 chiếc.

Giải pháp khả thi cơ bản:

Chúng ta sẽ sử dụng phương pháp gần đúng của Vogel để tìm giải pháp khả thi ban đầu.

Giải pháp khả thi ban đầu được đưa ra bởi ma trận sau:

Kiểm tra tính tối ưu:

Từ ma trận trên, chúng ta thấy rằng:

(a) Số lượng phân bổ = m + n - 1 = 4 + 5-1 = 8

(b) Các phân bổ m + n - 1 này ở các vị trí độc lập.

Do đó kiểm tra sự tối ưu có thể được thực hiện. Điều này bao gồm các bước phụ được giải thích trước đó như được hiển thị trong Bảng bên dưới:

Vì các giá trị ô là + ve giải pháp khả thi đầu tiên là tối ưu. Vì bảng 6 chứa các mục không, nên tồn tại các giải pháp tối ưu thay thế. Ý nghĩa thực tế của nhu cầu là 15 đơn vị ít hơn nguồn cung là công ty có thể cắt giảm việc sản xuất 15 đơn vị tại nhà máy nơi không kinh tế.

Vận chuyển tối ưu (tối thiểu) cộng với chi phí sản xuất.

Z = R. (4 x 25 + 6 x 5 + 8 x 20 +10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)

= R. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = R. 1.4565.

Ví dụ 3:

Giải quyết vấn đề vận chuyển sau đây để tối đa hóa lợi nhuận. Do sự khác biệt về chi phí nguyên vật liệu và chi phí vận chuyển, lợi nhuận cho đơn vị tính bằng rupee khác nhau được đưa ra trong bảng dưới đây:

Giải quyết vấn đề tối đa hóa lợi nhuận.

Dung dịch:

Vấn đề là không cân bằng và do đó một hàng giả phải được thêm vào để làm cho nó cân bằng.

Tìm giải pháp khả thi cơ bản ban đầu:

Chúng ta sẽ sử dụng phương pháp gần đúng của vogel để xác định giải pháp khả thi ban đầu.

Lưu ý rằng chúng tôi đang xử lý vấn đề tối đa hóa. Do đó, chúng ta sẽ nhập chênh lệch giữa các phần tử cao nhất và cao thứ hai trong mỗi hàng ở bên phải của hàng và chênh lệch giữa các phần tử cao nhất và cao thứ hai trong mỗi cột bên dưới cột tương ứng.

Mỗi sự khác biệt này đại diện cho lợi nhuận đơn vị bị mất vì không phân bổ cho tế bào lợi nhuận cao nhất. Do đó, trong khi thực hiện phân bổ, đầu tiên chúng tôi chọn ô (2, 3) với mục nhập cao nhất trong hàng 2 tương ứng với mức chênh lệch cao nhất là [45].

Kiểm tra tính tối ưu:

Số lượng phân bổ cần thiết = m + n - 1 = 3 + 4 - 1 = 6

Số phân bổ thực tế = 5.

Do đó, chúng tôi phân bổ số dương nhỏ € cho ô (1, 3) (ô có lợi nhuận tối đa từ các ô trống) để số phân bổ trở thành 6. 6 phân bổ này ở các vị trí độc lập. Do đó kiểm tra sự tối ưu có thể được thực hiện.

Vì tất cả các giá trị ô là âm hoặc bằng 0 (bài toán tối đa hóa), giải pháp khả thi cơ bản ban đầu là tối ưu. Nhu cầu tại điểm đến đầu tiên là 'không được thỏa mãn bởi 5units. Lợi nhuận là

Tối đa Z = R. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]

= R. 31.600.