Simplex_Method
一晩かかりました。
シンプレックス法を使って線形計画問題を解くプログラムです。
これを提出すればＢくらいはくれるのでは・・・
と思い作ってみました。
誤差が結構出るので、複雑な問題には使い物になりません。
max 2x + 3y s.t. x + 2y > 14 x + y > 8 3x + y > 18
このくらいの問題ならば何とかなります。
はぁ・・・・また徹夜だ・・・・・orz
久しぶりにSTLを使ってC++を書きました。
でも、自分用に行列計算ライブラリとかベクトルライブラリがあったら楽だなぁって思いました。
夏休みはそういった数学ライブラリでも作ってみましょうか・・・・。
今回のベクトルの演算もせめて演算子のオーバーロード位使えよって話ですが、まぁ時間もなかったし仕方がないということで許してくだせぇｗｗ
つかれた・・
#include <iostream>
#include <vector>
#include <iomanip>
#include <fstream>
#include <string>
using namespace std;
#define LOOP_MAX 50
void print(vector<vector<double> > &mat, int n)
{
cout << endl;
cout << endl;
cout << "[定数項 ] ";
for(int i = 1; i < n ; i++){
cout << "[" << setw(7) << "X" << i << "] ";
}
cout << endl;
for(unsigned int i = 0; i < mat.size(); i++){
for(unsigned int j = 0; j < mat[i].size(); j++){
cout << "[" << setw(8) << mat[i][j] << "]" << " ";
}
cout << endl;
}
}
vector<double> sub(vector<double> s1, vector<double> s2)
{
vector<double> return_val;
return_val.resize(s1.size());
for(unsigned int i = 0; i < s1.size(); i++)
return_val[i] = s1[i] - s2[i];
return return_val;
}
vector<double> mul(vector<double> s1, double val)
{
vector<double> return_val;
return_val.resize(s1.size());
for(unsigned int i = 0; i < s1.size(); i++)
return_val[i] = s1[i] * val;
return return_val;
}
bool keeploop(vector<vector<double> > &mat)
{
for(unsigned int i = 0; i < mat[0].size(); i++){
if(mat[0][i] < 0)
return true;
}
return false;
}
int main()
{
int n; //変数の数
int st; //制約式の数
double min;
double min2;
int min_index;
int min2_index;
int loop_count = 0;
string filename;
ifstream fin;
vector<vector<double> > mat; //行列
vector<double> temp1, temp2; //行列から行のみをとって格納する。ピボットに使用。
cout << "シンプレックス法による最適解" << endl;
cout << "変数の数はいくつですか --->" ;
cin >> n;
cout << "制約式の数はいくつですか --->" ;
cin >> st;
cout << "入力ファイル名を入れてください --->";
cin >> filename;
fin.open(filename.c_str());
mat.resize(st + 1);
temp1.resize(n + st + 1);
temp2.resize(st);
//シンプレックス表の初期化
for(unsigned int i = 0; i < mat.size(); i++){
mat[i].resize(n + st + 1);
unsigned int j;
for(j = 0; j < mat[i].size() - st; j++){
//cin >> mat[i][j];
fin >> mat[i][j];
}
//スラック変数の場所を1にする。
if(i != 0){
mat[i][n + i] = 1;
}
}
while(keeploop(mat)){
//イテレーションごとに出力
print(mat, n + st + 1);
//目的関数の係数から最小値を見つける
min = mat[0][0];
for(unsigned int i = 1; i < mat[0].size(); i++){
if(mat[0][i] <= min){
min = mat[0][i];
min_index = i;
}
}
//定数項/列要素
for(int i = 0; i < st; i++){
temp2[i] = mat[i + 1][0] / mat[i + 1][min_index];
}
//その中から最小値を探す
min2 = temp2[0];
for(unsigned int i = 0; i < temp2.size(); i++){
if(temp2[i] <= min2){
min2 = temp2[i];
min2_index = i + 1;
}
}
//選択された行に割り算を施す
double temp = mat[min2_index][min_index];
for(unsigned int i = 0; i < mat[min2_index].size(); i++){
mat[min2_index][i] = mat[min2_index][i] / temp;
}
temp1 = mat[min2_index];
//自分以外の行から自分の行を引く
for(int i = 0; i < st + 1; i++){
if(i != min2_index)
mat[i] = sub(mat[i], mul(temp1, mat[i][min_index]));
}
loop_count++;
if( loop_count > LOOP_MAX)
break;
}
//最後の表を出力
if(!keeploop(mat))
print(mat, st + n + 1);
else{
cout << "誤差またはLOOP_MAX回のイテレーションを繰り返したため、終了します。" << endl;
}
}
シンプレックス表は以下のようにテキストファイルで作成する max 2x + 3y s.t. x + 2y > 14 x + y > 8 3x + y > 18 の場合 0 -2 -3 14 1 2 8 1 1 18 3 1 とする
