134 lines
3.7 KiB
C++
134 lines
3.7 KiB
C++
#include <algorithm>
|
|
#include <iostream>
|
|
#include "tools/matrix.h"
|
|
#include "tools/math.h"
|
|
|
|
enum solver_state {
|
|
unbounded,
|
|
bounded
|
|
};
|
|
|
|
struct Result {
|
|
solver_state state;
|
|
ColumnVector *solution;
|
|
double objective_function_value;
|
|
};
|
|
|
|
struct FracturedMatrix {
|
|
Matrix A;
|
|
ColumnVector C;
|
|
ColumnVector b;
|
|
int pivot_column_index;
|
|
int pivot_row_index;
|
|
FracturedMatrix();
|
|
FracturedMatrix(const FracturedMatrix& other) : A(other.A), C(other.C), b(other.b), pivot_column_index(other.pivot_column_index), pivot_row_index(other.pivot_row_index) {}
|
|
FracturedMatrix(Matrix A, ColumnVector C, ColumnVector b, int pivot_column_index, int pivot_row_index) : A(A), C(C), b(b), pivot_column_index(pivot_column_index), pivot_row_index(pivot_row_index) {}
|
|
FracturedMatrix& FracturedMatrix::operator=(const FracturedMatrix& other) {
|
|
A = other.A;
|
|
C = other.C;
|
|
b = other.b;
|
|
pivot_column_index = other.pivot_column_index;
|
|
pivot_row_index = other.pivot_row_index;
|
|
return *this;
|
|
}
|
|
};
|
|
|
|
Result Simplex(ColumnVector C, Matrix A, ColumnVector b, double eps = 0.01, bool maximize=true) {
|
|
|
|
std::cout << "C: " << C << std::endl;
|
|
std::cout << "A: " << A << std::endl;
|
|
std::cout << "b: " << b << std::endl;
|
|
|
|
int n = C.getRows();
|
|
int m = A.getColumns();
|
|
|
|
while (b[0] < eps) {
|
|
//3
|
|
int pivot_column_index = 0;
|
|
pivot_column_index = Math::max_index(C);
|
|
|
|
//4
|
|
ColumnVector ratio_vector(m);
|
|
for (int i = 0; i < m; i++) {
|
|
ratio_vector[i] = b[i] / A[i][pivot_column_index];
|
|
}
|
|
int pivot_row_index = Math::min_index(ratio_vector);
|
|
|
|
//5
|
|
struct FracturedMatrix fractured_matrix();
|
|
fractured_matrix = eleminate(A, C, b, pivot_column_index, pivot_row_index);
|
|
}
|
|
|
|
/*
|
|
Result result;
|
|
std::vector<int> basicVars(A.getColumns() - A.getRows());
|
|
basicVars[0] = -1;
|
|
|
|
for (int i = 1; i < basicVars.size(); i++) {
|
|
basicVars[i] = static_cast<int>(basicVars.size()) + i;
|
|
}
|
|
|
|
int kc = 0;
|
|
double temp = A[0][0];
|
|
for (int j = 0; j< A.getColumns(); j++) {
|
|
if (A[0][j] < temp) {
|
|
temp = A[0][j];
|
|
kc = j;
|
|
}
|
|
}
|
|
|
|
if (A[0][kc] >= 0) {
|
|
result.state = unbounded;
|
|
result.solution = new ColumnVector(C.getRows());
|
|
for (int i = 0; i < C.getRows(); i++) {
|
|
result.solution->operator[](i) = 0;
|
|
}
|
|
for (int i = 1; i < basicVars.size(); i++) {
|
|
if (basicVars[i] <= C.getRows()) {
|
|
(*result.solution)[basicVars[i]] = b.getRows() - 1;
|
|
}
|
|
}
|
|
result.objective_fucntion_value = b[0];
|
|
|
|
}
|
|
*/
|
|
}
|
|
|
|
/*
|
|
Function_name(C, A, b, eps = eps_default)
|
|
|
|
Input:
|
|
- C: A vector of coefficients of the objective function
|
|
- A: A matrix of coefficients of the constraint functions
|
|
- b: A vector of right-hand side values
|
|
- eps: Approximation accuracy (optional, default = eps_default)
|
|
|
|
Steps:
|
|
1. Print the optimization problem:
|
|
- max (or min) z = C[0] * x1 + C[1] * x2 + ... + C[n] * xn
|
|
- subject to the constraints:
|
|
- A[0] * x <= b[0]
|
|
- A[1] * x <= b[1]
|
|
- ...
|
|
- A[m] * x <= b[m]
|
|
|
|
2. Initialize:
|
|
- Form the initial tableau by introducing slack variables to convert inequalities into equalities.
|
|
|
|
3. Iteratively apply the Simplex method:
|
|
- Step 1: Identify the entering variable (most negative coefficient in the objective row).
|
|
- Step 2: Identify the leaving variable (smallest positive ratio of RHS to pivot column).
|
|
- Step 3: Perform pivot operations to update the tableau.
|
|
|
|
4. Check for optimality or unboundedness:
|
|
- If all coefficients in the objective function row are non-negative, the solution is optimal.
|
|
- If no leaving variable exists, the problem is unbounded.
|
|
|
|
5. Return:
|
|
- solver_state: {solved, unbounded}
|
|
- x*: Optimal vector of decision variables (if solved)
|
|
- z: Maximum (or minimum) value of the objective function (if solved)
|
|
|
|
End Function
|
|
*/
|