#include "StdAfx.h"
#include "loa.h"
#include <limits>
#include <vector>
#include <algorithm>
#include "simulation.h"

using namespace std;


loa::loa(void)
{
	vector< vector< double>> vec;
	vector<double> vec1;
	
	vec1.push_back(1);
	vec1.push_back(-1);
	vec1.push_back(1);
	vec.push_back(vec1);

	vec1.clear();
	vec1.push_back(1);
	vec1.push_back(1);
	vec1.push_back(5);
	vec.push_back(vec1);

	vec1.clear();
	vec1.push_back(-2);
	vec1.push_back(1);
	vec1.push_back(2);
	vec.push_back(vec1);

	vec1.clear();
	vec1.push_back(-2);
	vec1.push_back(-1);
	vec1.push_back(0);
	vec.push_back(vec1);
	

	//zeigeMatrix(vec);
/*
	vec1.clear();
	vec1.push_back(0);
	vec1.push_back(1);
	vec1.push_back(1);
	vec1.push_back(6);
	vec.push_back(vec1);

	vec1.clear();
	vec1.push_back(3);
	vec1.push_back(2);
	vec1.push_back(2);
	vec1.push_back(20);
	vec.push_back(vec1);

	vec1.clear();
	vec1.push_back(1);
	vec1.push_back(2);
	vec1.push_back(1);
	vec1.push_back(15);
	vec.push_back(vec1);

	vec1.clear();
	vec1.push_back(4);
	vec1.push_back(0);
	vec1.push_back(1);
	vec1.push_back(10);
	vec.push_back(vec1);

	vec1.clear();
	vec1.push_back(-2);
	vec1.push_back(-3);
	vec1.push_back(-1);
	vec1.push_back(0);
	vec.push_back(vec1);
*/

	
	tableau = vec;
	zeilenAnz = tableau.size();
	spaltenAnz = tableau[0].size();
}

loa::~loa(void)
{
}

loa::loa(vector<vector<double>> simp_tab)
{
	tableau = simp_tab;
	zeilenAnz = tableau.size();
	spaltenAnz = tableau[0].size();
}

void loa::solvePrimal()
{
	CString str;

	optimal = false;
	unloesbar = false;

	vector<int> nichtBasisVariablen( spaltenAnz-1 );//Speichern der Vertauschungen
	vector<int> basisVariablen( zeilenAnz-1 );//Speichern der Vertauschungen
	for(int i=0; i<spaltenAnz-1; i++)//Fuellen der Vektoren mit den Nummern der Variablen
	{
		nichtBasisVariablen[i] = i + 1;
		
	}
	for(int i=0; i<zeilenAnz-1; i++)
	{
		basisVariablen[i] = spaltenAnz + i ;
	}

	//simulation::zeigeVektor(nichtBasisVariablen);
	//simulation::zeigeVektor(basisVariablen);


	while(!optimal && !unloesbar)
	{
		optimal = testeAufOptimalitaet();
		//simulation::zeigeMatrix(tableau);
		
		if(!optimal)
		{
			//AfxMessageBox( "Nicht optimal.", MB_YESNO, 0);
			int pivotspalte = waehlePivotspalte();
			//str.Format("pivotspalte = %d", pivotspalte);
			//AfxMessageBox(str, MB_YESNO, 0);
			unloesbar = fuehreKantentestDurch(pivotspalte);
			

			if(!unloesbar)
			{
				//AfxMessageBox( "Nicht unloesbar.", MB_YESNO, 0);
				int pivotzeile = waehlePivotzeile(pivotspalte);
				
				//str.Format("pivotzeile =%d, pivotspalte=%d",pivotzeile, pivotspalte);
				//AfxMessageBox( str, MB_YESNO, 0);
				
				merkeVertauschungen(pivotzeile, pivotspalte, nichtBasisVariablen, basisVariablen);
				//AfxMessageBox( "Vorm Umrechnen des Tableaus.", MB_YESNO, 0);
				rechneSimplextableauUm(pivotzeile, pivotspalte);
			}

		}
		
	}

	//simulation::zeigeMatrix(tableau);
	//AfxMessageBox( "Hinter Optimierung", MB_YESNO, 0);

	if(optimal)
	{
		//simulation::zeigeVektor(nichtBasisVariablen);
		//simulation::zeigeVektor(basisVariablen);
		//AfxMessageBox( "Vorm Berechnen der Lösung!", MB_YESNO, 0);
		loesung = berechneLoesung(nichtBasisVariablen, basisVariablen);
		zielwert = berechneZielwert();
	}

	simulation::zeigeVektor(loesung);

}


void loa::solveDual()
{
CString str;

	optimal = false;
	unloesbar = false;

	vector<int> nichtBasisVariablen( spaltenAnz-1 );//Speichern der Vertauschungen
	vector<int> basisVariablen( zeilenAnz-1 );//Speichern der Vertauschungen
	for(int i=0; i<spaltenAnz-1; i++)//Fuellen der Vektoren mit den Nummern der Variablen
	{
		nichtBasisVariablen[i] = i + 1;
		
	}
	for(int i=0; i<zeilenAnz-1; i++)
	{
		basisVariablen[i] = spaltenAnz + i ;
	}

	//simulation::zeigeVektor(nichtBasisVariablen);
	//simulation::zeigeVektor(basisVariablen);


	while(!optimal && !unloesbar)
	{
		optimal = testeZulaessigkeitUndOpt();
		//simulation::zeigeMatrix(tableau);
		
		if(!optimal)
		{
			//AfxMessageBox( "Nicht optimal.", MB_YESNO, 0);
			int pivotzeile = waehlePivotzeileDual();
			//str.Format("pivotspalte = %d", pivotspalte);
			//AfxMessageBox(str, MB_YESNO, 0);
			unloesbar = testeKonsistenz(pivotzeile);
			

			if(!unloesbar)
			{
				//AfxMessageBox( "Nicht unloesbar.", MB_YESNO, 0);
				int pivotspalte = waehlePivotspalteDual(pivotzeile);
				
				//str.Format("pivotzeile =%d, pivotspalte=%d",pivotzeile, pivotspalte);
				//AfxMessageBox( str, MB_YESNO, 0);
				
				merkeVertauschungen(pivotzeile, pivotspalte, nichtBasisVariablen, basisVariablen);
				//AfxMessageBox( "Vorm Umrechnen des Tableaus.", MB_YESNO, 0);
				rechneSimplextableauUm(pivotzeile, pivotspalte);
			}

		}
		
	}

	//simulation::zeigeMatrix(tableau);
	//AfxMessageBox( "Hinter Optimierung", MB_YESNO, 0);

	if(optimal)
	{
		//simulation::zeigeVektor(nichtBasisVariablen);
		//simulation::zeigeVektor(basisVariablen);
		//AfxMessageBox( "Vorm Berechnen der Lösung!", MB_YESNO, 0);
		loesung_komplett = berechneLoesung(nichtBasisVariablen, basisVariablen);


		for(int i=0; i < spaltenAnz-1; i++)//Loesung in den urspruenglichen Variablen (Zahlungen) erzeugen
		{
			loesung.push_back(loesung_komplett[i]);
		}

		zielwert = berechneZielwert();
	}

}
//primal
bool loa::testeAufOptimalitaet()
{
	bool opt = tableau[zeilenAnz-1][0] >= 0;
	for(int i=1; i<=spaltenAnz-2 && opt; i++)
	{
		opt = opt && tableau[zeilenAnz-1][i] >= 0;
	}

	return opt;

}

int loa::waehlePivotspalte()
{
	//Da der Optimalitaetstest fehlschlug muss ein Zielfunktionskoeff kleiner Null sein
	double min = 100;
	double minIndex = -77;

	for(int i=0; i<=spaltenAnz-2; i++)
	{
		double aktVal = tableau[zeilenAnz-1][i];
		if( aktVal < 0 && aktVal < min)
		{
			min = aktVal;
			minIndex = i;
		}
	}

	return minIndex;
}

bool loa::fuehreKantentestDurch(int pivotspalte)
{
	unloesbar = tableau[0][pivotspalte] <= 0;
	for(int i=1; i<= zeilenAnz-2; i++)
	{
		unloesbar = unloesbar && tableau[i][pivotspalte] <= 0;
	}
	return unloesbar;
}

int loa::waehlePivotzeile(int pivotspalte)
{
	double min = numeric_limits<double>::infinity();
	int minIndex = -66;

	for(int i=0; i<=zeilenAnz-2; i++)
	{
		double aktValNenner = tableau[i][pivotspalte];
		double aktValZaehler = tableau[i][spaltenAnz-1];
		double aktVal = aktValZaehler/aktValNenner;

		/*
		CString str;
		str.Format("quot = %f",aktVal);
		AfxMessageBox( str, MB_YESNO, 0);
		*/

		if( aktValNenner > 0 && aktVal < min)
		{
			min = aktVal;
			minIndex = i;
		}
	}

	return minIndex;
}





//dual
bool loa::testeZulaessigkeitUndOpt()
{
	bool opt = tableau[0][spaltenAnz-1] >= 0;
	for(int i=1; i<=zeilenAnz-2 && opt; i++)
	{
		opt = opt && tableau[i][spaltenAnz-1] >= 0;
	}

	return opt;

}
int loa::waehlePivotzeileDual()
{
	double min = 100;
	double minIndex = -77;

	for(int i=0; i<=zeilenAnz-2; i++)
	{
		double aktVal = tableau[i][spaltenAnz-1];
		if( aktVal < 0 && aktVal < min)
		{
			min = aktVal;
			minIndex = i;
		}
	}
	return minIndex;

}
bool loa::testeKonsistenz(int pivotzeile)
{
	unloesbar = tableau[pivotzeile][0] >= 0;
	for(int i=1; i<= spaltenAnz-2; i++)
	{
		unloesbar = unloesbar && tableau[pivotzeile][i] >= 0;
	}
	return unloesbar;

}
int loa::waehlePivotspalteDual(int pivotzeile)
{
	double min = numeric_limits<double>::infinity();
	int minIndex = -66;

	for(int i=0; i<=spaltenAnz-2; i++)
	{
		double aktValNenner = tableau[pivotzeile][i];
		double aktValZaehler = tableau[zeilenAnz-1][i];
		double aktVal = aktValZaehler/fabs(aktValNenner);

		/*
		CString str;
		str.Format("quot = %f",aktVal);
		AfxMessageBox( str, MB_YESNO, 0);
		*/

		if( aktValNenner < 0 && aktVal < min)
		{
			min = aktVal;
			minIndex = i;
		}
	}

	return minIndex;
}
//primal und dual
double loa::berechneZielwert()
{
	return (-1) * tableau[zeilenAnz-1][spaltenAnz-1];
}
void loa::merkeVertauschungen(int pivotzeile, int pivotspalte, 
							  vector<int> &nichtBasisVariablen, vector<int> &basisVariablen)
{
	int bv = basisVariablen[pivotzeile];
	int nbv = nichtBasisVariablen[pivotspalte];

	basisVariablen[pivotzeile] = nbv;
	nichtBasisVariablen[pivotspalte] = bv;
}

void loa::rechneSimplextableauUm(int pivotzeile, int pivotspalte)
{
	vector<vector<double>> tab = tableau;

	//AfxMessageBox( "Vor Pivot.", MB_YESNO, 0);
	//Umrechnung des Pivotelements
	tableau[pivotzeile][pivotspalte] = 1 / tab[pivotzeile][pivotspalte];

	//AfxMessageBox( "Vor Pivotzeile.", MB_YESNO, 0);
	//Umrechnung der Pivotzeile
	for(int i=0; i<spaltenAnz; i++)
	{
		if(i != pivotspalte)
		{
			tableau[pivotzeile][i] = tab[pivotzeile][i] / tab[pivotzeile][pivotspalte];
		}
	}

	//AfxMessageBox( "Vor Pivotspalte.", MB_YESNO, 0);
	//Umrechnung der Pivotspalte
	for(int i=0; i<zeilenAnz; i++)
	{
		if(i != pivotzeile)
		{
			tableau[i][pivotspalte] = (-1) * tab[i][pivotspalte] / tab[pivotzeile][pivotspalte];
		}
	}

	//AfxMessageBox( "Vorm Rest.", MB_YESNO, 0);

	//simulation::zeigeMatrix(tab);
	//simulation::zeigeMatrix(tableau);

	//Umrechnung vom Rest
	for(int i=0; i<zeilenAnz; i++)
	{
		if(i != pivotzeile)
		{
			for(int j=0; j<spaltenAnz; j++)
			{
				if(j != pivotspalte)
				{
					/*
					CString str;
					str.Format("%d, %d",i, j);
					AfxMessageBox( str, MB_YESNO, 0);
					*/
			
					tableau[i][j] = (tab[i][j]*tab[pivotzeile][pivotspalte] - 
									 tab[pivotzeile][j]*tab[i][pivotspalte])
									 / tab[pivotzeile][pivotspalte];
					 
			
				}
			}
		}
	}

}

vector<double> loa::berechneLoesung(vector<int> nichtBasisVariablen, vector<int> basisVariablen)
{
	CString str;

	int AnzVar = spaltenAnz+zeilenAnz-2;
	vector<double> loesung(AnzVar);
	for(int i=1; i<= AnzVar; i++)//Durchlaufen aller Variablen
	{
		//str.Format("i=%d",i);
		//AfxMessageBox(str, MB_YESNO, 0);

		//Suchen der Variablen in den beiden Vektoren
		bool gefunden = false;
		//zuerst im Nichtbasisvektor
		int j = 0;
		while(!gefunden && j<spaltenAnz-1)
		{
			gefunden = nichtBasisVariablen[j] == i;
			j++;
		}
		
		if(gefunden)
		{
			//AfxMessageBox("NBV!", MB_YESNO, 0);
			loesung[i-1] = 0;
		}
		else//d.h.: Variable ist im Basisvektor zu finden
		{
			//AfxMessageBox("BV", MB_YESNO, 0);
			int k=0;
			gefunden = false;
			while(!gefunden && k<zeilenAnz-1)
			{
				gefunden = basisVariablen[k] == i;
				k++;
			}

			if(gefunden)
			{
				loesung[i-1] = tableau[k-1][spaltenAnz-1];
			}
			else
			{
				AfxMessageBox("Bei der Berechnung der Loesung im Simplex-Algo ist ein Fehler aufgetreten!", MB_YESNO, 0);
			}
		}	
	}

	//simulation::zeigeVektor(loesung);
	return loesung;
}
