探討線性規劃中限制式係數的改變與應用

Abstract

為了因應時代的快速變遷，科技的日新月異，傳統的線性規劃必須正視資源耗用矩陣(resource consumption matrix)的改變，也就是限制式係數的改變，而不能再將之忽略；因為一旦考慮限制式係數的變化之後，可以讓維持最佳解的思考開闊起來，找出另外一個可行的方向，藉此突破傳統上目標式係數與資源量其敏感度分析的習慣領域。

本篇論文利用Kuhn-Tucker Condition處理線性問題，藉此求得限制式係數其可接受變動的範圍，只要變動後的係數值在此範圍內，則最佳基底結構(structure of optimal basis)與原來的相同，亦即在變動後的最終單形表中，目標列與右端值其每個位置大於零(>0)或等於零(=0)的結構與原始最終表相同；且求得當多個限制式係數同時變動時，其係數之間可變動範圍的相依關係，如此得到有用的資訊，供管理者使用。

另外，當限制式係數發生變動時，可以透過調整變數(adjustable variables)調整其餘未變動的限制式係數，讓目標值至少維持在相同的值。可處理的問題包括(1)限制式係數超過其可變範圍的變動，或是其可變範圍內，目標值降低的問題，即藉由調整變數的調整，以及各類活動水準的變動，讓整體系統維持以往的最佳目標值。(2)延續(1)的問題，但考量調整限制式係數變動的成本與提供變動的預算。(3)當資源的可用水準發生變動時，在特定的範圍內，適當地調整限制式係數亦可讓最佳解維持在相同的目標值。

The rapid changes of the technology and the world make it necessary for us to confront the changes of constraint coefficients parameters in linear programming in the real world. By considering the changes of constraint coefficients and possible application we can explore a new concept of maintaining the optimality structure. As a consequence, we break through the traditional thinking, a habitual domain, of sensitivity analysis which focuses mainly on the change of the coefficients of the objective function and/or in the right hand side of the constraints.

By applying the Kuhn-Trucker condition to linear programming we obtain the tolerance domain of the selected constraint coefficients such that, as long as the selected coefficients are within the tolerance domain, the structure of optimality basis will remain the same as the original one. We also explore the interdependence of the changes of the coefficients. For the process, we clarify the differences between maintaining the optimal basis and maintaining the basis structure of optimality. The tolerance domain of maintaining the basis structure of optimality is a subset of that of maintaining the optimal basis.

When some constraint coefficients have changed to outside of their tolerance domain, we can still adjust the unchanged constraint coefficients as to keep the objective function value unchanged. The method introduced can be applied to the following problems. (i)When the changed coefficients are outside of their tolerance domain or the objective function value has been decreased, even the coefficient changes are still within their tolerance domain. We want to keep the original objective function value. (ii)When the cost and the budget for adjusting the coefficients are given, how to solve the problems stated in (i). (iii)When the right hand side coefficients change, we could still keep the objective function value, without adding extra resources, by adjusting constraint coefficients.