[HEEDS] 선형계획법(Linear Programming)

 

표준 선형계획 문제(Standard LP Definition) 

 표준 선형계획 문제는 다음과 같이 세 가지 구성요소가 있습니다. 설계변수(Design Variables), 목적함수(Cost Function), 제약조건(Constraints) 이 그 구성요소 입니다. 아래 예제를 통해 표준 선형계획 문제로 변환하는 방법을 소개합니다.

 1. 설계변수

- 시스템을 나타내는 변수의 집합

- 변수의 수치값이 정해지면 설계 결정

 2. 설계 제약조건

- 자원의 한계, 재료강도, 시스템 응답, 치수 등

- 만족하면 유용시스템(Feasible System)

 3. 목적함수

- 어떤 설계가 더 좋은지 판단 기준

- 원가의 최소화, 경량화

 위와 같이 일반적인 최적설계 문제를 표준 선형계획 문제로 변환하여 알고리즘을 이용하여 풀이가 가능합니다. 

선형계획의 기본개념

 선형계획 문제에서는 모든 함수들이 선형이기 때문에, 등호제약조건이나 부등호 제약조건에 의해서 정의된 유용영역은 볼록(convex) 집합입니다. 또 목적함수도 선형이므로 볼록함수 입니다. 그러므로 선형계획 문제는 볼록계획 문제이고 만일 하나의 최적해가 존재한다면 그것은 전역적 최적해입니다. 또한 선형계획 문제에서 부등호 제약조건의 경우라도 만일 해가 존재한다면 그것은 항상 유용영역의 경계 부분에 존재합니다. 이러한 사실은 비제약 최적해에 대한 필요조건을 적용하여 보면 알 수 있습니다. 모든 선형계획 문제의 최적해는 반드시 유용영역의 경계부분에 있어야 하며, 이것은 최적해가 유용영역 내부에 있는 일반적인 비선형 문제와 다르다는 것을 보여줍니다. 아래 예제는 표준 선형계획 문제의 해가 유용영역의 경계에 존재한다는 것을 보여주고 있습니다. 

심플렉스(Simplex) 방법

 2차원 공간에서 심플렉스는 동일 직선상에 놓여있지 않은 3점에 의해서 형성됩니다. 3차원 공간에서는 동일 평면상에 놓여 있지 않은 4개의 점으로 형성됩니다. 3점은 동일 평면에 있을 수 있지만, 나머지 한 점은 반드시 다른 평면에 있어야 합니다. 일반적으로 n 차원 공간에서의 심플렉스는 한 개의 접평면(hyperplane)에 놓여 있지 않은 (n+1) 점의 볼록면(convex hull) 입니다. (n+1) 점으로 구성된 볼록다면체는 모든 점들을 포함하는 가장 작은 볼록 집합입니다. 따라서 심플렉스는 볼록집합입니다. 

 심플렉스 방법은 기저 유용해에서 계산이 시작됩니다. 즉 볼록 다면체의 꼭지점에서 계산이 시작되고 유용성을 유지하면서 목적함수 값이 감소되는 이웃 꼭지점으로 이동하며 계산해야 합니다. 이러한 과정은 새로운 해가 유용성을 유지하면서 기저 변수를 비기저 변수로 대체함으로써 이루어집니다. 한 정점에서 다른 정점으로 이동할 때 목적함수 값이 감소되어야 합니다. 심플렉스 방법은 이웃하는 정점으로만 이동합니다. 현 정점 주위에는 여러 정점들이 있으므로, 이 점들 중에서 목적함수의 값이 가장 최소화되는 점을 구합니다. 만일 이웃하는 정점들 중에 목적함수의 감소량이 동일한 점들이 있으면 임의로 선택하면 됩니다. 각 계산 단계에서 이미 거쳐온 정점으로는 되돌아가지 않도록 합니다. 따라서 심플렉스 방법에서 다음의 두 가지 의문이 발생합니다. 

1. 현재의 비기저면수에서 어느 것을 기저 변수로 선택할 것인가?

2. 현재의 기저 변수 중에서 어느 것이 비기저로 될 것인가?

다음은 심플렉스 방법을 이용한 이익 극대화의 솔루션입니다. 

이 문제를 매틀랩 코드로 구현하면 아래와 같습니다. 

clear;

 

Noofvariables=2;

C=[400 600];

Info=[1 1;1/28 1/14;1/14 1/24];

b=[16;1;1];

s=eye(size(Info,1));

A=[Info s b];

 

Cost=zeros(1,size(A,2));

Cost(1:Noofvariables)=C;

 

BV=Noofvariables+1:1:size(A,2)-1;

 

ZjCj=Cost(BV)*A-Cost;

ZCj=[ZjCj;A];

SimTable=array2table(ZCj)

 

RUN=true;

iter=0;

while RUN

 

    iter=iter+1;

    if any(ZjCj<0)

        fprintf(' The current BFS is Not optimal \n');

        fprintf('\n-------------- The next iteration results --------------\n');

        disp('OLD basic variable (BV) = ');

        disp(BV);

   

        ZC=ZjCj(1:end-1);

        [EnterCol, pvt_col]=min(ZC);

        fprintf('The Most positive Element in %d corresponding to column %d \n'...

            ,EnterCol,pvt_col);

        fprintf('Entering variable is %d \n',pvt_col);

   

        if all(A(:,pvt_col)<=0)

            error('LPP is unbounded. all enteries  <=0 in column %d',pvt_col);

        else

            sol=A(:,end);

            Column=A(:,pvt_col);

            for i=1:size(Column,1)

                if Column(i)>0

                    ratio(i)=sol(i)./Column(i);

                else

                    ratio(i)=inf;

                end

            end

   

        [MinRatio, pvt_row]=min(ratio);

        fprintf('Minimum ratio corresponding to PIVOT row is %d \n',pvt_row);

        fprintf('Leving varaible is %d \n',BV(pvt_row));

        end

   

        BV(pvt_row)=pvt_col;

        disp('New basic varaibles (BV) =');

        disp(BV);

   

        pvt_key=A(pvt_row, pvt_col);

   

        A(pvt_row,:)=A(pvt_row,:)./pvt_key;

        for i=1:size(A,1)

            if i~=pvt_row

                A(i,:)=A(i,:)-A(i,pvt_col).*A(pvt_row,:);

            end

        end

       

       

        ZjCj=ZjCj-ZjCj(pvt_col).*A(pvt_row,:);

        ZCj=[ZjCj;A];

        TABLE=array2table(ZCj)

 

        BFS=zeros(1,size(A,2));

        BFS(BV)=A(:,end);

        BFS(end)=sum(BFS.*Cost);

        Current_BFS=array2table(BFS)

 

    else

       

        RUN=false;

        fprintf(' ---------------------------\n');

        fprintf(' The Current BFS is optimal \n');

        fprintf(' ---------------------------\n');

    end

end

실행 결과