めも

[kanorimon]

include

include

using namespace std;

//xx=変数の数 ,xy=目的関数の数+制約条件の数 int xx,xy;

//simplex tableau double x[10][100];

void print_tableau(){

cout << "***start" << endl;

for(int i=0;i<xy;i++){
    for(int j=0;j<xx;j++){
        cout << x[i][j] << " ";
    }
    cout << endl;
}

cout << "***end" << endl;

}

bool check_optimality(){

bool minus = false;
for(int i=1;i<xx;i++){
    if(x[0][i] > 0){
        minus = true;
        break;
    }
    cout << "check_optimality = " << minus << " " << x[0][i] << endl;
}
return minus;

}

int get_entering_variable(){

int pibot = 0;
for(int i=1;i<xx;i++){
    if(x[0][i] > 0){
        pibot = i;
        break;
    }
}

cout << "pibot = " << pibot << " " << x[0][pibot] << endl;

return pibot;

}

bool check_unbounded(int pibot){ bool minus = false; for(int i=1;i<xy;i++){ if(x[i][0]+x[i][pibot]x[0][pibot] > 0){ minus = true; break; } cout << "check_unbounded = " << minus << " " << x[i][0]+x[i][pibot]x[0][pibot] << endl; } return minus; }

int main(){

//読み込み
cin >> xx >> xy;
for(int i=0;i<xy;i++){
    for(int j=0;j<xx;j++){
        cin >> x[i][j];
    }
}

//現在の辞書を画面表示
print_tableau();

//最適性判定
if(!check_optimality) return 0;

//ピボット列選択
int pibot_row = get_entering_variable();

//非有界判定
if(!check_unbounded(pibot_row)) return 0;

return 0;

}

[kanorimon]

include

include

using namespace std;

//xx=column ,xy=row int xx,xy;

//simplex tableau double x[10][100];

void print_tableau(){

cout << "***start" << endl;

for(int i=0;i<xy;i++){
    for(int j=0;j<xx;j++){
        cout << x[i][j] << " ";
    }
    cout << endl;
}

cout << "***end" << endl;

}

bool check_optimality(){

bool minus = false;
for(int i=1;i<xx;i++){
    if(x[0][i] > 0){
        minus = true;
        break;
    }
    cout << "check_optimality = " << minus << " " << x[0][i] << endl;
}
return minus;

}

int get_entering_variable(){

int pibot = 0;
for(int i=1;i<xx;i++){
    if(x[0][i] > 0){
        pibot = i;
        break;
    }
}

cout << "pibot = " << pibot << " " << x[0][pibot] << endl;

return pibot;

}

bool check_unbounded(int pibot){ bool minus = false; for(int i=1;i<xy;i++){ if(x[i][0]+x[i][pibot]x[0][pibot] > 0){ minus = true; break; } cout << "check_unbounded = " << minus << " " << x[i][0]+x[i][pibot]x[0][pibot] << endl; } return minus; }

int main(){

//load
cin >> xx >> xy;
for(int i=0;i<xy;i++){
    for(int j=0;j<xx;j++){
        cin >> x[i][j];
    }
}

print_tableau();

if(!check_optimality) return 0;

int pibot_row = get_entering_variable();

if(!check_unbounded(pibot_row)) return 0;

return 0;

}

[kanorimon]

include

include

include

using namespace std;

//constant const int MAX_NO = 10;

//valiable int n_cnt; int N[MAX_NO]; int b_cnt; int B[MAX_NO];

//simplex tableau double xf; double c[MAX_NO]; double b[MAX_NO]; double a[MAX_NO][MAX_NO];

void print_tableau(int no){

cout << "(D_" << no << ")" << endl;

cout << "                 ";
for(int i=0;i<n_cnt;i++){
    cout << setw(7) << right << "x" << N[i];
}
cout << endl;

cout << "         ";
cout << setw(8) << right << xf;

for(int i=0;i<n_cnt;i++){
    cout << setw(8) << right << c[N[i]];
}

cout << endl;
for(int i=0;i<b_cnt;i++){
    cout <<  setw(8) << right << "x" << B[i];
    cout <<  setw(8) << right << b[B[i]];
    for(int j=0;j<n_cnt;j++){
        cout <<  setw(8) << right << a[B[i]][N[j]];
    }
    cout << endl;
}

cout << endl;

}

//step1 bool check_optimality(){

bool minus = false;
for(int i=0;i<n_cnt;i++){
    if(c[N[i]] > 0){
        minus = true;
        break;
    }
//  cout << "check_optimality = " << minus << " " << c[N[i]] << endl;
}
return minus;

}

//step2 int get_s(){

int s = 0;
for(int i=0;i<n_cnt;i++){
    //cout << N[i] << " " << x[0][N[i]]  << endl;
    if(c[N[i]] > 0){
        s = N[i];
        break;
    }
}
//cout << "s = " << s << " " << c[s] << endl;
return s;

}

//step3 bool check_unbounded(int pibot_column){ bool minus = false; for(int i=0;i<b_cnt;i++){ if(a[B[i]][pibot_column]-1 > 0){ minus = true; break; } // cout << "check_unbounded = " << minus << " " << a[B[i]][pibot_column]c[pibot_column] << endl; } return minus; }

//step4 int get_r(int s){ int r=0; int mini = 100000; for(int i=0;i<bcnt;i++){ if(a[B[i]][s]*-1 > 0 && b[B[i]]/a[B[i]][s]-1 < mini){ r = B[i]; mini = b[B[i]]/a[B[i]][s]_-1; } } //cout << "r = " << r << " " << b[r] << endl; return r; }

int main(){

/* load */
cin >> n_cnt >> b_cnt;

for(int i=0;i<n_cnt;i++){
    cin >> N[i];
}

for(int i=0;i<b_cnt;i++){
    cin >> B[i];
}

cin >> xf;

for(int i=0;i<n_cnt;i++){
    cin >> c[N[i]];
}

for(int i=0;i<b_cnt;i++){
    cin >> b[B[i]];
    for(int j=0;j<n_cnt;j++){
        cin >> a[B[i]][N[j]];
    }
}

/* simplex method */
int no = 0;
while(true){

    /* print tableau */
    print_tableau(++no);

    /* step1 */
    if(!check_optimality()) return 0;

    /* step2 */
    int s = get_s();

    /* step3 */
    if(!check_unbounded(s)) return 0;

    /* step4 */
    int r = get_r(s);

    /* step5 */
    int tmp_n_i;
    int tmp_b_i;

    for(int i=0;i<n_cnt;i++){
        if(N[i] == s){
            tmp_n_i = i;
            break;
        }
    }

    for(int i=0;i<b_cnt;i++){
        if(B[i] == r){
            tmp_b_i = i;
            break;
        }
    }

    N[tmp_n_i] = r;
    B[tmp_b_i] = s;

    double ars = a[r][s] * -1.0;

    xf = xf + b[r] / ars * c[s];

    for(int j=0;j<n_cnt;j++){
        if(N[j]==r){
            c[N[j]] = -1.0 * 1.0 / ars * c[s];
        }else{
            c[N[j]] = c[N[j]] - (a[r][N[j]] * -1.0 / ars * c[s]);
        }
    }

    for(int i=0;i<b_cnt;i++){
        if(B[i]==s){
            b[B[i]] = b[r] / ars;
        }else{
            b[B[i]] = b[B[i]] - (b[r] / ars * a[B[i]][s] * -1.0);
        }

        for(int j=0;j<n_cnt;j++){
            if(B[i]==s){
                if(N[j]==r){
                    a[B[i]][N[j]] = -1.0 * 1.0 / ars;
                }else{
                    a[B[i]][N[j]] = -1.0 * a[r][N[j]] * -1.0 / ars;
                }
            }else if(N[j]==r){
                if(B[i]==s){
                    a[B[i]][N[j]] = -1.0 * 1.0 / ars;
                }else{
                    a[B[i]][N[j]] = 1.0 / ars * a[B[i]][s] * -1.0;
                }
            }else{
                a[B[i]][N[j]] = -1.0 * ( a[B[i]][N[j]] * -1.0 - (a[r][N[j]] * -1.0 / ars * a[B[i]][s] * -1.0));
            }
        }
    }
}

print_tableau(no);

return 0;

}