3 công cụ quan trọng của nghiên cứu hoạt động
Bài viết này đưa ra ánh sáng về ba công cụ quan trọng của nghiên cứu hoạt động. Các công cụ là: 1. Lập trình tuyến tính 2. Vấn đề vận chuyển 3. Bài toán chuyển nhượng.
Nghiên cứu hoạt động: Công cụ # 1. Lập trình tuyến tính:
Lập trình tuyến tính là một kỹ thuật toán học có ứng dụng cho hầu hết các loại vấn đề quyết định. Kỹ thuật này được áp dụng để chọn là phương án thay thế tốt nhất trong số các phương án khả thi.
Trong hàm mục tiêu LPP cũng như các ràng buộc có thể được biểu diễn dưới dạng hàm toán học tuyến tính, có thể được sử dụng để giải quyết các vấn đề lập lịch thực tế. Nó là một phương pháp được sử dụng để nghiên cứu hành vi của các hệ thống.
LP chủ yếu liên quan đến việc mô tả mối tương quan của các thành phần của một hệ thống. Kỹ thuật này được thiết kế để giúp các nhà quản lý lập kế hoạch, ra quyết định và phân bổ các nguồn lực. Việc quản lý luôn có xu hướng sử dụng hiệu quả nhất nguồn lực của tổ chức. Tài nguyên bao gồm máy móc nguyên liệu, lao động, kho, thời gian và tiền bạc.
Những tài nguyên này có thể được sử dụng để sản xuất các loại sản phẩm có thể là máy móc, bộ phận / linh kiện, đồ nội thất và thực phẩm, vv Các tài nguyên tương tự có thể được sử dụng để cung cấp dịch vụ như lịch trình vận chuyển, chính sách quảng cáo và quyết định đầu tư.
Tất cả các tổ chức phải đưa ra quyết định về việc phân bổ các nguồn lực hạn chế của họ. Vì vậy, quản lý được yêu cầu liên tục phân bổ các nguồn lực khan hiếm để đạt được các mục tiêu / mục tiêu / mục tiêu của tổ chức.
Tính từ tuyến tính đã được sử dụng để mô tả mối quan hệ giữa hai hoặc nhiều biến. Lập trình liên quan đến việc sử dụng các phương trình toán học nhất định được sử dụng để có được giải pháp tốt nhất có thể cho một vấn đề liên quan đến nguồn lực hạn chế / khan hiếm.
Do đó, lập trình tuyến tính được sử dụng cho các vấn đề tối ưu hóa thỏa mãn điều kiện sau:
(i) Hàm mục tiêu được tối ưu hóa phải được xác định rõ và được biểu thị dưới dạng hàm tuyến tính của các biến.
(ii) Giới hạn nếu có liên quan đến việc đạt được các mục tiêu này cũng được thể hiện dưới dạng chất lượng / bất bình đẳng tuyến tính của biến.
(iii) Một số hành động thay thế cũng có sẵn.
(iv) Các biến quyết định có liên quan đến nhau và không âm.
(v) Tài nguyên có hạn.
Ứng dụng lập trình tuyến tính cho các vấn đề công nghiệp:
(i) Phát triển lịch trình cho các ngành công nghiệp chế biến thực phẩm và cho các nhà máy lọc dầu, v.v.
(ii) Trong các ngành công nghiệp kim loại, nó được sử dụng để tải cửa hàng và để xác định sự lựa chọn giữa mua và sản xuất các bộ phận khác nhau.
(iii) Nó được sử dụng để đánh giá các loại quặng sắt khác nhau trong ngành công nghiệp sắt thép.
(iv) Nó được sử dụng để giảm lượng tổn thất cắt trong các nhà máy giấy.
(v) Nó được sử dụng để tìm định tuyến tối ưu của tin nhắn trong mạng truyền thông.
Định nghĩa lập trình tuyến tính:
Lập trình tuyến tính là một công cụ / kỹ thuật toán học để xác định việc sử dụng tốt nhất các tài nguyên của tổ chức. Lập trình tuyến tính được thiết kế để giúp các nhà quản lý về lập kế hoạch và ra quyết định. Là một công cụ ra quyết định, nó đã cho thấy giá trị của nó trong các lĩnh vực khác nhau như sản xuất; tài chính tiếp thị, nghiên cứu và phân công nhân sự.
Xác định hỗn hợp sản phẩm tối ưu, lịch trình vận chuyển danh mục đầu tư lựa chọn máy; vị trí nhà máy và phân bổ lao động, vv là một số loại vấn đề có thể được giải quyết với sự trợ giúp của lập trình tuyến tính.
Phân tích các vấn đề trong đó một hàm tuyến tính của một số biến sẽ được tối đa hóa (hoặc tối thiểu hóa) khi các biến này chịu số lượng hạn chế dưới dạng tuyến tính trong các đẳng thức., Sam Samelson và Slow
Theo Loomba, lập trình tuyến tính chỉ là một khía cạnh của cái được gọi là phương pháp quản lý hệ thống trong đó tất cả các chương trình được thiết kế và đánh giá theo các tác động cuối cùng của chúng trong việc hiện thực hóa các mục tiêu kinh doanh.
Các vấn đề lập trình tuyến tính-Phương pháp đồ họa:
Các bước của phương pháp đồ họa có thể được tóm tắt như sau:
1. Xây dựng bài toán lập trình tuyến tính.
2. Vẽ các đường giới hạn đã cho coi chúng là phương trình.
3. Từ biểu đồ trên xác định vùng giải pháp khả thi.
4. Xác định vị trí các điểm đến của vùng giải pháp khả thi.
5. Tính giá trị của hàm mục tiêu trên các điểm đến.
6. Bây giờ chọn điểm mà hàm mục tiêu có giá trị tối ưu.
Bài toán lập trình tuyến tính - Giải pháp toán học:
Mặc dù phương pháp đồ họa giải LPP là một trợ giúp có giá trị để hiểu cấu trúc cơ bản của nó. Phương pháp này rất hữu ích trong các vấn đề công nghiệp vì số lượng biến xảy ra ở đó rất lớn, vì vậy một giải pháp toán học khác gọi là phương pháp đơn giản là giải quyết LPP phù hợp với số lượng biến lớn.
Đây là một quy trình lặp có thể giải quyết LPP trong một số bước hữu hạn hoặc đưa ra một dấu hiệu cho thấy có một giải pháp không giới hạn đối với phương pháp L.PR Simplex là một thủ tục đại số để giải quyết các vấn đề lập trình tuyến tính hoặc bao gồm một loạt các bước lặp đi lặp lại đạt được một giải pháp tối ưu.
Nó là một thuật toán lập trình được sử dụng rộng rãi và phổ biến nhất. Về mặt lý thuyết quy trình này có thể giải quyết bất kỳ vấn đề nào bao gồm bất kỳ số lượng biến và ràng buộc nào. Nếu vấn đề bao gồm nhiều hơn ba biến và ba ràng buộc thì việc sử dụng máy tính là bắt buộc. Hình 31.9 cho thấy biểu diễn sơ đồ của thuật toán đơn giản.
Các bước khác nhau trong thủ tục Simplex:
Các bước của thủ tục này được liệt kê dưới đây:
1. Xây dựng vấn đề bằng cách xác định hàm mục tiêu và các ràng buộc.
2. Chuyển đổi các bất đẳng thức thành các đẳng thức để có được dạng chuẩn bằng cách đưa ra thặng dư và biến nhân tạo trong hàm mục tiêu.
3. Chuẩn bị bảng đơn giản ban đầu.
4. Tính toán giá trị z j (tổn thất ròng trên mỗi đơn vị) và giá trị c j - z j (đóng góp ròng) cho giải pháp này.
5. Xác định biến nhập (cột khóa) bằng cách chọn cột có nhiều âm nhất
(z j - c j ).
6. Xác định biến khởi hành (hàng khóa) bằng cách tính cột tỷ lệ từ quy tắc 5 và chọn giá trị không âm nhỏ nhất.
7. Tính hàng thay thế của bảng đơn giản được cải tiến theo quy tắc 6.
8. Tính các hàng còn lại của bảng mới theo quy tắc 7.
9. Tính giá trị c j và z j cho giải pháp này.
10. Nếu có giá trị không âm (c j - z j ) trở về bước 5.
11. Nếu không có giá trị không âm (c j - z j ), giải pháp tối ưu đã thu được.
Ví dụ 1:
Một nông dân có 1000 mẫu đất mà anh ta có thể thu hoạch ngô, lúa mì hoặc đậu nành, Mỗi mẫu ngô có giá Rs. 100 để chuẩn bị, đòi hỏi 7 ngày làm việc và mang lại lợi nhuận là Rup. 30 Một mẫu lúa mì có giá. 120 để chuẩn bị, cần 10 ngày làm việc và mang lại lợi nhuận là Rup. 40.
Một mẫu đất trồng đậu nành có giá 70 Rupee để chuẩn bị đòi hỏi 8 ngày làm việc và mang lại lợi nhuận là Rup. 20 Nếu người nông dân có R. 100.000 để chuẩn bị và tính vào 8000 ngày làm việc. Cần phân bổ bao nhiêu mẫu đất cho mỗi vụ để tối đa hóa lợi nhuận? (MBA Gujarat, 1989)
Dung dịch:
Đặt x mẫu đất được giao cho ngô
mẫu đất được giao cho lúa mì
Mẫu đất z được giao cho đậu tương
Vì mỗi mẫu đất trồng ngô mang lại lợi nhuận là Rs. 30, cho năng suất lúa mì. 40 và đối với đậu tương R. 20. Công thức toán học của LLP là
Tối đa Z = 30x + 40y + 20z + 0S 1, + HĐH 2, + 0S 3
Theo
100 x + 120y + 70z 100000
7x + 10y + 8z ≤ 8000
x + y + z 1000
x, y, z ≥ 0
Chúng ta hãy chuyển đổi các bất đẳng thức thành các phương trình bằng cách đưa ra các biến slack S 1, S 2 và S 3 . Hàm mục tiêu và các ràng buộc có thể được viết là
Trong cột biến cơ bản, các vectơ dành cho biến S 1, (1, 0, 0), S 2, (1, 0, 1) và S 3 (0, 0, 1) giải pháp khả thi ban đầu được đưa ra bởi các biến S 1, S 2 và S 3 đều có tổng lợi nhuận = 0
Bây giờ Z j và C j - Z j, được tính theo Quy tắc 1, 2 và 3. Cột khóa được xác định với cột được đánh dấu bắt đầu và Bảng II đơn giản được chuẩn bị như sau.
Bảng II không cung cấp giải pháp tối ưu, chúng tôi tiến hành thêm để chuẩn bị bảng III đơn giản và cải thiện giải pháp như sau:
Vấn đề tối thiểu hóa bằng phương pháp Big M.
Trong công nghiệp có thể có mục tiêu là giảm thiểu chi phí sản xuất hoặc thời gian sản xuất, tức là chức năng mục tiêu được giảm thiểu trong các trường hợp như vậy, chúng ta có thể tiến hành theo cách tương tự như một vấn đề tối đa hóa bằng cách nhân hai bên của hàm mục tiêu by-1 Trong các tình huống như vậy, tối thiểu hóa Z sẽ là tối đa hóa (-Z).
Trong các trường hợp như vậy vì các biến dư thừa có giá trị âm vi phạm hạn chế không âm, để khắc phục khó khăn này, chúng tôi giới thiệu biến mới được tạo kiểu là biến nhân tạo.
Bây giờ chúng ta gán 3000 hệ số cho các biến dư và + M cho các biến nhân tạo, Để tạo nguồn mà biến nhân tạo không phải là biến cơ bản trong giải pháp tối ưu, chúng ta gán cho chúng chi phí rất cao do đó M được định nghĩa là một số rất lớn, ví dụ Big M hoặc phạt.
Phương pháp này được minh họa với sự giúp đỡ của sau:
Ví dụ 2:
Nghiên cứu hoạt động: Công cụ # 2. Vấn đề vận chuyển:
Vấn đề vận chuyển là một trong những loại LPP trong đó mục tiêu là vận chuyển hàng hóa / sản phẩm với số lượng khác nhau của một mặt hàng / hàng hóa đồng nhất đến các điểm đến khác nhau để giảm thiểu tổng chi phí vận chuyển trong cuộc sống hàng ngày của các tổ chức sản xuất hoặc các cơ sở khác do để xem xét khác nhau lưu trữ các sản phẩm hoặc vật phẩm cuối cùng của họ tại nhiều nơi được gọi là nguồn gốc hoặc kho, nhà khi cung cấp cho người dùng, sau đó các mặt hàng được vận chuyển từ nguồn gốc đến một hoặc nhiều đích, mục đích chung của quá trình này là quyết định chính sách phân phối sao cho tổng chi phí vận chuyển là tối thiểu hoặc thời gian tiêu thụ trong quá trình trung chuyển là tối thiểu.
Sau khi các sản phẩm hoàn chỉnh từ nhà máy sẽ được vận chuyển đến kho theo cách tiết kiệm nhất trong các vấn đề vận chuyển, các tính năng khác nhau của lập trình tuyến tính có thể được quan sát ở đây cũng như các yêu cầu của các trung tâm khác nhau là hữu hạn và là vấn đề vận chuyển tài nguyên hạn chế trong các trường hợp đặc biệt của phương pháp đơn giản.
Ứng dụng trong van vận chuyển sản phẩm từ một số nguồn đến các điểm đến khác nhau, chẳng hạn như:
(i) Đơn vị vận chuyển bị rách đích. Mục tiêu là để giảm thiểu chi phí vận chuyển.
(ii) Tối đa hóa lợi nhuận trong việc vận chuyển các đơn vị đến đích.
Các bước chính liên quan là :
Bước 1:
Xây dựng vấn đề và thiết lập dưới dạng ma trận vận chuyển.
Bước 2:
Có được giải pháp khả thi cơ bản.
Bước 3:
Kiểm tra sự tối ưu của giải pháp.
Bước 4:
Cập nhật giải pháp thông qua cải tiến thành công cho đến khi không thể giảm thêm chi phí vận chuyển.
Các phương pháp thường được sử dụng là:
1. Phương pháp góc tây bắc.
2. Phương pháp chi phí thấp nhất.
3. Phương pháp gần đúng của Vogel.
Các bước tham gia vào Phương pháp Góc Tây Bắc:
Bước 1:
Hạn chế một ma trận tối đa trống hoàn thành với các hàng và cột.
Bước 2:
Chỉ ra tổng số hàng và tổng số cột ở cuối.
Bước 3:
Bắt đầu với (11) ô tại comer phía tây bắc của ma trận phân bổ số lượng / số lượng tối đa có thể, việc phân bổ không thể nhiều hơn số lượng được yêu cầu bởi các nhà kho tương ứng cũng không nhiều hơn số lượng có sẵn tại các trung tâm cung ứng.
Bước 4:
Sau khi thực hiện điều chỉnh số lượng cung và cầu theo phân bổ hàng & cột tương ứng, di chuyển xuống ô đầu tiên và hàng lặp lại bước 3.
Bước 5:
Sau khi nhu cầu của cột đầu tiên được thỏa mãn. Hãy thực hiện đến ô tiếp theo trong cột thứ hai và hàng đầu tiên và chuyển sang bước 3.
Bước 6:
Nếu đối với bất kỳ nguồn cung cấp ô nào bằng với nhu cầu thì phân bổ tiếp theo có thể là chế độ trong các ô trong các hàng và cột tiếp theo.
Bước 7:
Tiếp tục quá trình cho đến khi tổng số lượng có sẵn được phân bổ đầy đủ cho các ô theo yêu cầu
Ví dụ 3:
Giải quyết vấn đề sau bằng NWCM để tính chi phí vận chuyển tối thiểu:
Các bước trong phương pháp nhập chi phí tối thiểu:
Phương pháp này tính đến chi phí thấp nhất và do đó mất ít thời gian hơn để giải quyết vấn đề, các bước khác nhau như sau:
Bước 1:
Chọn ô có chi phí vận chuyển thấp nhất trong số tất cả các hàng và cột trong ma trận. Phân bổ càng nhiều càng tốt để loại bỏ hàng hoặc cột đó làm cạn kiệt nguồn hoặc đầy đủ yêu cầu. Nếu cả hai đều thỏa mãn họ loại bỏ một trong hai. Nếu ô chi phí nhỏ nhất không phải là duy nhất, thì hãy chọn tùy ý bất kỳ ô nào có chi phí thấp nhất.
Bước 2:
Lặp lại quy trình cho tất cả các hàng & cột chưa được mở rộng với ô chi phí nhỏ nhất tiếp theo. Bước 3: Lặp lại quy trình cho đến khi tất cả các nguồn bị cạn kiệt hoặc nhu cầu của tất cả các điểm đến đã được lấp đầy.
Ví dụ 4:
Giải quyết vấn đề sau bằng phương pháp chi phí tối thiểu:
Phương pháp xấp xỉ Vogel:
Phương pháp này là phương pháp phạt hoặc hối tiếc và được ưu tiên hơn hai phương pháp còn lại, giải pháp khả thi cơ bản ban đầu thu được là tối ưu hoặc rất gần với giải pháp tối ưu do đó thời gian cần thiết để tính toán giải pháp tối ưu đã giảm.
Trong phương pháp này, cơ sở của phân bổ là hình phạt chi phí đơn vị, tức là hàng hoặc cột biểu thị mức phạt chi phí đơn vị cao nhất / chênh lệch giữa chi phí thấp nhất và cao nhất tiếp theo được chọn trước tiên cho mục đích phân bổ. Theo cách này, việc phân bổ tiếp theo trong các ô khác cũng được thực hiện để xem mức phạt đơn giá cao nhất.
Việc phân bổ được thực hiện để giảm thiểu chi phí phạt theo các bước khác nhau như sau:
Bước 1:
Tính toán hình phạt cho mỗi hàng & cột được thực hiện bằng cách chỉ lấy chênh lệch giữa chi phí vận chuyển nhỏ nhất và nhỏ nhất tiếp theo trong cùng một hàng & cột, tức là chênh lệch cho thấy hình phạt phải trả nếu việc phân bổ không được thực hiện với chi phí tối thiểu tiêu chí.
Bước 2:
Chọn một hàng hoặc cột có hình phạt lớn nhất và phân bổ càng nhiều càng tốt cho ô có chi phí thấp nhất. Trong trường hợp hòa thì một ô phân bổ tối đa có thể được chọn trước
Bước 3:
Gạch bỏ hàng hoặc cột sau khi đáp ứng nhu cầu hoặc cạn kiệt nguồn cung, hàng hoặc cột còn lại được chỉ định cung hoặc cầu bằng không. Bất kỳ hàng hoặc cột không có cung hoặc cầu không được sử dụng để tính toán thêm.
Bước 4:
Lặp lại các bước 1 và 3 cho đến khi tất cả các nguồn bị cạn kiệt hoặc tất cả các yêu cầu được đáp ứng.
Ví dụ 5:
Một nhà sản xuất muốn vận chuyển 8 tải sản phẩm của mình từ các trung tâm sản xuất X, Y & Z đến các trung tâm phân phối A, B và C, khoảng cách từ nguồn gốc 0 đến đích D là ma trận sau.
Ví dụ 6:
Tìm giải pháp tối ưu cho vấn đề vận chuyển sau bằng cách lấy giải pháp ban đầu với phương pháp xấp xỉ vogets:
Dung dịch:
Hãy để chúng tôi áp dụng phương pháp gần đúng của vogel. Các vấn đề cân bằng như cung = Cầu = 50 đơn vị. Hãy để chúng tôi áp dụng phương pháp của vogel như được đưa ra trong bảng dưới đây.
Chi phí vận chuyển = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 đơn vị.
Kiểm tra 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 cấp phát, có m là số hàng, n là số cột. Ở đây m + n - = 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, nghĩa 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ế của hàng hoặc cột.
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ó 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 trong Bảng 2.
Bây giờ số lượng phân bổ là m + n - 6 = 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ổ. (Bàn số 3)
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 .
Có thể thấy trong 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 - từ Bảng 6 rằng nếu chúng ta phân bổ tại ô (1, 4), 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. Mới bảng phân bổ sẽ trở thành
Chi phí vận chuyển = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 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 tối ưu:
Hãy để 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ủa u i và v j được phân bổ.
Nghiên cứu hoạt động: Công cụ # 3. Bài toán chuyển nhượng:
Bài toán chuyển nhượng là một loại bài toán lập trình tuyến tính đặc biệt liên quan đến việc phân bổ các nguồn lực khác nhau cho các hoạt động khác nhau trên cơ sở một.
Nó thực hiện theo cách mà chi phí hoặc thời gian tham gia vào quá trình là tối thiểu và lợi nhuận hoặc bán hàng là tối đa. Mặc dù có vấn đề có thể được giải quyết bằng phương pháp đơn giản hoặc phương pháp vận chuyển, nhưng mô hình gán cho cách tiếp cận đơn giản hơn cho những vấn đề này.
Trong một nhà máy, một giám sát viên có thể có sáu công nhân có sẵn và sáu công việc để sa thải. Anh ta sẽ phải đưa ra quyết định về công việc nào nên được giao cho công nhân nào. Vấn đề hình thành một đến một cơ sở. Đây là một vấn đề chuyển nhượng.
Mô hình bài tập:
Giả sử có n tạo điều kiện và n việc làm. Rõ ràng là trong trường hợp này, sẽ có n bài tập. Mỗi cơ sở hoặc nói công nhân có thể thực hiện từng công việc, từng công việc một. Nhưng cần có một quy trình nhất định theo đó việc chuyển nhượng nên được thực hiện để lợi nhuận được tối đa hóa hoặc chi phí hoặc thời gian được giảm thiểu.
Trong bảng, Co ij được định nghĩa là chi phí khi công việc thứ j được gán cho công nhân thứ i. Có thể lưu ý ở đây rằng đây là trường hợp đặc biệt của vấn đề vận chuyển khi số lượng hàng bằng số cột.
Công thức toán học:
Bất kỳ giải pháp khả thi cơ bản nào của bài toán Bài tập bao gồm (2n - 1) biến trong đó các biến (n - 1) bằng 0; n là số lượng công việc hoặc số lượng cơ sở.
Do sự thoái hóa cao này, nếu chúng ta giải quyết vấn đề bằng phương pháp vận chuyển thông thường, nó sẽ là một công việc phức tạp và tốn thời gian. Do đó, một kỹ thuật riêng biệt được bắt nguồn cho nó. Trước khi đi đến phương pháp tuyệt đối, việc hình thành vấn đề là rất quan trọng.
Giả sử X ij là một biến được định nghĩa là
Phương pháp giải quyết vấn đề (Kỹ thuật Hungary):
Xem xét chức năng mục tiêu của loại tối thiểu hóa.
Các bước sau đây có liên quan đến việc giải quyết vấn đề chuyển nhượng này:
1. Xác định vị trí 'phần tử chi phí nhỏ nhất trong mỗi hàng của bảng chi phí nhất định bắt đầu bằng hàng đầu tiên. Bây giờ, phần tử nhỏ nhất này được trừ từ mỗi phần tử của hàng đó. Vì vậy, chúng ta sẽ nhận được ít nhất một số 0 trong mỗi hàng của bảng mới này.
2. Đã xây dựng bảng (như bước 1) lấy các cột của bảng. Bắt đầu từ cột đầu tiên xác định phần tử chi phí nhỏ nhất trong mỗi cột. Bây giờ trừ phần tử nhỏ nhất này từ mỗi phần tử của cột đó. Đã thực hiện bước 1 và bước 2, chúng tôi sẽ nhận được ít nhất một số 0 trong mỗi cột trong bảng chi phí giảm.
3. Bây giờ, các bài tập được thực hiện cho bảng rút gọn theo cách sau:
(i) Các hàng được kiểm tra liên tiếp, cho đến khi hàng có chính xác một (một) số không được tìm thấy. Việc gán được thực hiện cho số 0 duy nhất này bằng cách đặt ô vuông □ xung quanh nó và trong cột tương ứng, tất cả các số 0 khác được gạch chéo (x) vì chúng sẽ không được sử dụng để thực hiện bất kỳ phép gán nào khác trong cột này. Bước được tiến hành cho mỗi hàng.
(ii) Bước 3 (i) hiện được thực hiện trên các cột như sau: Các cột được kiểm tra liên tiếp cho đến khi tìm thấy một cột có chính xác một số không. Bây giờ, việc gán được thực hiện cho số 0 duy nhất này bằng cách đặt hình vuông xung quanh nó và đồng thời, tất cả các số 0 khác trong các hàng tương ứng được gạch chéo (x) bước được thực hiện cho mỗi cột.
(iii) Bước 3 (i) và 3 (ii) được lặp lại cho đến khi tất cả các số 0 được đánh dấu hoặc gạch bỏ. Bây giờ, nếu số lượng số không được đánh dấu hoặc các bài tập được thực hiện bằng số lượng hàng hoặc cột, giải pháp tối ưu đã đạt được. Sẽ có chính xác một nhiệm vụ duy nhất trong mỗi hoặc cột mà không có bất kỳ sự phân công nào. Trong trường hợp này, chúng ta sẽ chuyển sang bước 4.
4. Ở giai đoạn này, vẽ số dòng tối thiểu (ngang và dọc) cần thiết để bao phủ tất cả các số không trong ma trận thu được ở bước 3.
Thủ tục sau đây được thông qua:
(i) Đánh dấu (V) tất cả các hàng không có bất kỳ sự phân công nào.
(ii) Bây giờ đánh dấu đánh dấu (V) tất cả các cột có số 0 trong các hàng được đánh dấu.
(iii) Bây giờ đánh dấu đánh dấu tất cả các hàng chưa được đánh dấu và có gán trong các cột được đánh dấu.
(iv) Tất cả các bước tức là 4 (1), 4 (2), 4 (3) được lặp lại cho đến khi không thể đánh dấu thêm hàng hoặc cột nào nữa,
(v) Bây giờ vẽ các đường thẳng đi qua tất cả các hàng không được đánh dấu và các cột được đánh dấu. Cũng có thể nhận thấy rằng trong một ma trận nxn, luôn luôn nhỏ hơn các dòng 'n' sẽ bao gồm tất cả các số không nếu không có giải pháp nào trong số chúng.
5. Trong bước 4, nếu số dòng được vẽ bằng n hoặc số hàng, thì đó là giải pháp tối ưu nếu không, sau đó chuyển sang bước 6.
6. Chọn phần tử nhỏ nhất trong số tất cả các phần tử chưa được khám phá. Bây giờ, phần tử này được trừ khỏi tất cả các phần tử chưa được khám phá và được thêm vào phần tử nằm ở giao điểm của hai dòng. Đây là ma trận cho bài tập mới.
7. Lặp lại quy trình từ bước (3) cho đến khi số lượng bài tập trở thành bằng số lượng hàng hoặc số cột.
