선형 계획 - 단순 형 알고리즘

1. 선형 계획 의 표준화
(1) 목표 함수: max
(2) 제약 조건: 등식
(3) 변수 제약: 비 마이너스 xj > = 0
(4) 자원 한정: 비 마이너스 bj > = 0
2. 비 표준 형의 표준화 (이하 변수 뒤의 괄호 에서 모두 아래 표)
(1) min 을 max 로 변환
min Z = CX  --->    max Z = -CX
(2) 부등식 을 등식 제약 으로 전환한다.
∑a( i,j )x( j )  <= b( i )   ------>  ∑a( i,j ) x( j ) + x( n+1 ) = b( i )                x (n + 1) 는 이완 변수 이다.
∑a( i,j )x( j )  >= b( i )   ------>  ∑a( i,j ) x( j ) - x( n+1 ) = b( i )                x (n + 1) 는 이완 변수 이다.
(3) 변수 제약 변환
만약 x (j) < = 0, x (j) = - x (j) 라면 x (j) > = 0;
만약 x (j) 가 제한 이 없다 면, 령 x (j) > = 0, x (j) > = 0 이면 x (j) = x( j_ )-x( j__ )；
만약 a < = x (j) < = b, 령 x (j) = x (j) - a, 그러면 x (j) >= 0,
x (j) < = b - a, 이렇게 하면 부등식 제약 이 됩 니 다. 즉, x (j) + x (j) 입 니 다. <= b-a，x( j__ )  >= 0。
(4) b (i) 를 <= 0 을 b (i) 로 변환 > = 0
방정식 양쪽 을 1 - 1 로 곱 하면 된다.
자세히 보면 모든 부등식 이 포함 되 어 있 는 것 과 같다 는 것 을 알 수 있다. 선형 계획 이 최 우수 치 를 구 하 는 것 이 반드시 정수 가 아니 기 때문에 작 게 보 는 것 은 차이 가 크 지 않다.
단순 형 알고리즘 코드 첨부:

#include 
#define eps 1e-3
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1005;
/*
0:    
1:   
2:  
m1:       
m2:      
m3:       
n1:          
n2:  、    、       
*/
class LinearProgram
{
public :
    int n, m, m1, m2, m3, n1, n2;
    int basic[maxn], nonbasic[maxn];
    double a[maxn][maxn];
    void init ( )
    {
        n1 = n+m3;
        n2 = n1+m1;
        for ( int i = 0; i <= n1; i ++ )
            for ( int j = 0; j <= m+1; j ++ )
                a[i][j] = 0.0;
        for ( int i = m1+m2+1, j = m+1; i <= m; i ++, j ++ )
        {
            a[i][j] = -1;       //          
            a[m+1][j] = -1;
        }
        for ( int i = 1; i <= n1; i ++ )
            nonbasic[i] = i;    //     (0)
        for ( int i = 1; i <= m; i ++ )
            basic[i] = n1+i;    //    
    }
    void pivot ( int row, int col ) //    ,         
    {
        for ( int j = 0; j <= n1; j ++ )
            if ( j != col )
                a[row][j] = a[row][j]/a[row][col];
        a[row][col] = 1.0/a[row][col];
        for ( int i = 0; i <= m+1; i ++ )
        {
            if ( i != row )
            {
                for ( int j = 0; j <= n1; j ++ )
                {
                    if ( j != col )
                    {
                        a[i][j] = a[i][j]-a[i][col]*a[row][j];
                        if ( fabs ( a[i][j] ) < eps )
                            a[i][j] = 0.0;
                    }
                }
                a[i][col] = -a[i][col]*a[row][col];
            }
        }
        swap ( basic[row], nonbasic[col] );
    }
    int selectCol ( int row )
    {
        int res = 0;
        for ( int i = 1; i <= n1; i ++ )
            if ( nonbasic[i] <= n2 && a[row][i] > eps )
            //       ,            ,    (      0)
            {
                res = i;
                break ; //Bland      
            }
        return res;
    }
    int selectRow ( int col )
    {
        double tmp = INF;
        int res = 0;
        for ( int i = 1; i <= m; i ++ )
            if ( a[i][col] > eps && tmp > a[i][0]/a[i][col] )
            {
                tmp = a[i][0]/a[i][col];
                res = i;
            }
        return res;
    }
    int select ( int r )
    {
        for ( int col, row; ; )
        {
            col = selectCol ( r );
            if ( col > 0 )
                row = selectRow ( col );
            else
                return 0;
            if ( row > 0 )
                pivot ( row, col );
            else            // col      ,            
                return 1;   //           ,     
        }
    }
    int phase1 ( )
    {
        int res = select ( m+1 );
        if ( res > 0 )
            return res;
        for ( int i = 1; i <= m; i ++ )
        {
            if ( basic[i] > n2 )
            {
                if ( a[i][0] > eps )
                    return 2;
                for ( int j = 1; j <= n1; j ++ )
                {
                    if ( fabs ( a[i][j] ) > eps )
                    {
                        pivot ( i, j );
                        break ;
                    }
                }
            }
        }
        return 0;
    }
    int phase2 ( )
    {
        return select ( 0 );
    }
    int compute ( )
    {
        if ( m != m1 )
        {
            int res = phase1 ( );
            if ( res != 0 )
                return res;
        }
        return phase2 ( );
    }
} lp;
double ans[maxn];
void print ( )
{
    memset ( ans, 0, sizeof ( ans ) );
    for ( int i = 1; i <= lp.m; i ++ )
    {
        if ( lp.basic[i] <= lp.n )
            ans[ lp.basic[i] ] = lp.a[i][0];
        printf ( "%d
", lp.basic[i] );
    }
    for ( int i = 1; i <= lp.n; i ++ )
        printf ( "%.2lf ", ans[i] );
    printf ( "
" );
}
void solve ( )
{
    char op[15];
    int sign;
    //freopen ( "in2.txt", "r", stdin );
    while ( ~ scanf ( "%d", &lp.n ) )
    {
        scanf ( "%d%d%d", &lp.m1, &lp.m2, &lp.m3 );
        lp.m = lp.m1+lp.m2+lp.m3;
        lp.init ( );
        scanf ( "%s", op );
        if ( strcmp ( "max", op ) == 0 )
            sign = 1;
        else
            sign = -1;
        double x;
        for ( int i = 1; i <= lp.n; i ++ )
        {
            scanf ( "%lf", &x );
            lp.a[0][i] = x*sign;
        }
        scanf ( "%lf", &x );
        lp.a[0][0] = x*sign;
        for ( int i = 1; i <= lp.m; i ++ )
        {
            for ( int j = 1; j <= lp.n; j ++ )
                scanf ( "%lf", &lp.a[i][j] );
            scanf ( "%lf", &lp.a[i][0] );
        }
        for ( int j = 1; j <= lp.n; j ++ )
        {
            x = 0;
            for ( int i = lp.m1+1; i <= lp.m; i ++ )
                x += lp.a[i][j];
            lp.a[lp.m+1][j] = x;
        }
        switch ( lp.compute ( ) )
        {
            case 0 :
                print ( );
            break ;
            case 1 :
                printf ( "   
" );
            break ;
            case 2 :
                printf ( "  
" );
        }

    }
}
int main ( )
{
    solve ( );
    return 0;
}
/*
6 0 3 0                     6:      0:    3:    0:  
max 0 -1 3 0 -2 0 0
1 3 -1 0 2 0 7              [x+3x^2-x^3+2x^4 = 7]
0 -2 4 1 0 0 12
0 -4 3 0 8 1 10
ans:0 4 5 0 0 11

4 2 1 1
max 1 1 3 -1 0
1 0 2 0 18
0 2 0 -7 0
1 1 1 1 9
0 1 -1 2 1
ans:0 3.5 4.5 1

4 3 0 0
max 0.75 -20 0.5 -6 0
0.25 -8 -1 9 0
0.5 -12 -0.5 3 0
0 0 1 0 1
ans:1 0 1 0
*/