Abstract
整數規劃問題之應用在現今社會中應用得相當廣，而目前常用以解整數規劃問題之演算法有割面法(cutting plane)、分枝界定法(branch-and-bound)、列舉法 (enumeration) 三種，然而，若原來的整數問題是無解的，均無法以這三個演算法事先得知，亦即必需完全處理完才知道該整數問題是否無解，這無非是一種浪費。因此希望能找出這些無解的整數規劃問題之特性，以期能在尚未去解這個問題以前便知道是否有解。雖然，已有一些研究說明了在實數系上線性規劃之無解結構，然而，在實數系上有解並不代表在整數系上有解，是以，我們須獨立探討整數規劃之無解結構。如果是有解的整數規劃問題，我們可以用上述之演算法直接去找出最佳解，如果是無解的問題呢﹖如何在不失原題特性下去修正這無解系統而為有解系統呢﹖這也是我們想要討論的問題。因此，在這篇論文分為兩個部份來討論：第一部份：探討無解結構：此乃就一整數規劃問題之限制式在何種結構下會無可行解域(空集)而言，首先就限制矩陣(constraintmatrix) 均為非負者做一探討，希望能找出判斷這類問題有解與否之充要條件及判斷方法；並將此一判斷法則應用於其它限制矩陣不是非負的問題上。第二部份：介紹一個修正模式以使這些無解問題在最小修正(minimal calibration) 下存在至少一組解，在同時考慮原最佳化的目標式下，介紹一種方法來解這一多目標問題 。Integer Linear Programming models have been applied to a greatvarieties of problems and can be solved by enumeration, branch-and-bound or cutting plane methods. However, no matter whichmethod is employed, solving an ILP system is a time-consumingtask. In particular, if the systems are inconsistent they arenoted after complete operations. It is certainly a waste.Althought, there are some studies proposed the inconsistentstructures of LP systems but there is a solution on LP does notimply that is consistent on ILP. That is the reason why we mustdiscuss the inconsistent structure on ILP individually. Themain purposes of this study are to identify the discreteinconsistent systems and to develop a calibration method forproviding at least one solution. In this study, Chapter 1introduces the motivation and purposes. Part 1 contains fourchapters. We investigate the inconsistent structure of ILPs andprovide consistent and inconsistent properties for theNonnegative ILP systems. In Chapter 2, we introduce theliterature review of this paper, and in Chapter 3, we presentthe inconsistent structure of ILP systems which is for theNonnegative Integer Linear Programming and in the Chapter 4 weextend the properties in the Chapter 3 into most generalsystems. In Chapter 5, we summarize the properties of theinconsistent stuctures. Part 2 contains one chapter, Chapter 6.In Chapter 6, we develop a model and a solution method forproviding at least one solution. Finally, we summarize thewhole study in Chapter 7.