❓

what is basic solution (in linear programming)

상태

해결되지 않은 궁금증

생성일

2021/08/10 13:37

Linear programming 에는 세 가지 특성이 있다. (1) 모든 objective function 은 minimization type 이다. (최대화여도 최소화로 돌려풀 수 있음)* (2) 모든 제악조건 (constraints) 는 surplus variable, slack variable을 활용해서 등식으로 표현**할 수 있다. (3) 모든 decision variable 은 양수이다.*** (음수이더라도 두 양수의 차로 바꾸어 생각할 수 있음.)

m 개의 equation 과 n 개의 decision variable 이 있다고 할 때, If m > n, there will be m−n redundant equations which can be eliminated (필요없는 eq 들이 존재하는 것) If n = m, there will be an unique solution or there may not be any solution, If n < m, a case of undetermined set of linear equations, if they have any solution, there may be innumerable solutions

notation 들 정리

Point of n-Dimensional space (n 차원 공간상의 점의 정의) : A point in an n-dimensional space is characterized by an ordered set of values or coordinates. The coordinate of X are also called the component of X

Line segment in n-Dimensions (L) (n차원 공간상의 선분 정의) If coordinates of two pints and are given, the line segment (L) joining these points is the collection of points X(lambda)

Hyperplane In n-dimensional space (n차원 공간상의 초평면의 정의), the set of points whose coordinate satisfy a linear equation* is called a hyperplane

Convex Set (볼록 집합의 정의) : A convex set is a collection of points such that if X1 and X2 are any two points in the collection, the line segment* joining them is also in the collection, which can be defined as follows, if X1 and X2 is element of S, then X is element of S, X is line segment of X1,X2

vertex, extreme point : 기하학에서, 극점(極點, 영어: extreme point)은 어떤 볼록 집합 (Convex Set*) 속의 점 가운데, 다른 두 점의 볼록 선형 결합**으로 나타낼 수 없는 것이다.

그래서, basic solution 은 바로 이거다.

A basic solution is one in which {(n-m variable) are set equal to zero and solution can be obtained for the m number variable} ... 문장이 어려운데, basic solution 은, n-m 개의 변수가 "0이라고 설정" 하고, m 개의 변수들에 의해 등식을 만족시키는 다양한 상황들 중 하나(one in which) 이다. The solution obtain by setting independent variable equal to zero is called basic solution. (이것을 보아, 위에서 말했던 "0이라고 쳐보는" n-m 개의 변수들이 독립변수를 의미하는 듯하다.) 아래 예시* 를 보자.

이 basic solution 이라는 것이 나중에 결국 simplex method 라는 알고리즘에 활용이 된다. what is Simplex Method (in in linear programming)

feasible solution 과의 관계는 Basic feasible solution : is the basic solution that satisfies the non-negativity conditions (‣ ) 와 같다.

basic solution 과 연관된 개념이다.

basis (기저) is The collection of variables not set equal to zero to obtain the basic solution* is called the basis.