The Assignment Problem is studied in this article to observe its resistance to uncertainty in its data, the cost matrix, which is prone to subjectivity. The rigor of the resolution method contrasts with data uncertainty, which may hide its effect on the optimum sought. We assess this effect through a Monte Carlo methodology by subjecting the cost matrix to a symmetric triangular distribution perturbation. We solve the problem on a freely accessible web page where the user can change the data. The algorithm used is the simplex method, instead of the related Hungarian method, for generality. The computation is in Python with the Web language PHP and ‘gnuplot’, and runs on the server side, dispensing with any software installation or operating system match. This study, running on a Linux platform, is also an illustration for many other technical works. We have advocated the Web to solve problems, and the programs used can be the same as classical ones. This little regarded practice, which would make publications more useful, also facilitates the academia industry link, inviting technology transfer.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Assignment Problem: A Linear Programming Application with Uncertain Data, Running on the Web

  • Miguel Casquilho,
  • Pedro Pacheco,
  • Manuel Monteirinho,
  • Rui Galhano,
  • Sandro Carvalho,
  • João Bordado

摘要

The Assignment Problem is studied in this article to observe its resistance to uncertainty in its data, the cost matrix, which is prone to subjectivity. The rigor of the resolution method contrasts with data uncertainty, which may hide its effect on the optimum sought. We assess this effect through a Monte Carlo methodology by subjecting the cost matrix to a symmetric triangular distribution perturbation. We solve the problem on a freely accessible web page where the user can change the data. The algorithm used is the simplex method, instead of the related Hungarian method, for generality. The computation is in Python with the Web language PHP and ‘gnuplot’, and runs on the server side, dispensing with any software installation or operating system match. This study, running on a Linux platform, is also an illustration for many other technical works. We have advocated the Web to solve problems, and the programs used can be the same as classical ones. This little regarded practice, which would make publications more useful, also facilitates the academia industry link, inviting technology transfer.