import static java.lang.System.*;
import static java.lang.Math.*;
public class Program {
/*
* n - общее количество переменных
* m - количество базисных переменных
* M - +бесконечность
*
* c - коэффициенты из целевой функции
* a - коэффициенты из ограничений
* cB - коэффициенты при базисных переменных
* bV - базисные переменные
* bD - базисное решение
* delta - оценки
* min - отношения элементов разрешающего столбца и базисного решения
*/
final static int n = 4;
final static int m = 2;
final static double M = Double.POSITIVE_INFINITY;
static double[] c = new double[n];
static double[][] a = new double[m][n];
static double[] cB = new double[m];
static int[] bV = new int[m];
static double[] bD = new double[m];
static double[] delta = new double[n];
static double[] min = new double[m];
static void init() {
c[0] = -1; c[1] = 2; c[2] = -1; c[3] = -1;
a[0][0] = -1; a[0][1] = 1; a[0][2] = 1; a[0][3] = 0;
a[1][0] = 1; a[1][1] = 1; a[1][2] = 0; a[1][3] = 1;
cB[0] = -1;
cB[1] = -1;
bV[0] = 2;
bV[1] = 3;
bD[0] = 2;
bD[1] = 4;
}
/**
* Симплекс-метод. Подсчет минимума.
*/
static void simplexMin() {
out.println("\n\nПоиск минимума\n\n");
int i, j, r = -1, s = -1;
double[][] tmpA = new double[m][];
double[] tmpBD = new double[m];
init();
int k = 0;
while (true) {
++k;
// Считаем дельты, выделяем разрешающий столбец
// (столбец с минимальной оценкой)
double deltaMin = Double.POSITIVE_INFINITY;
r = -1;
for (j = 0; j < n; ++j) {
double z = 0;
for (i = 0; i < m; ++i) {
z += cB[i] * a[i][j];
}
delta[j] = c[j] - z;
if (deltaMin > delta[j]) {
deltaMin = delta[j];
r = j;
}
}
// Условие выхода (все оценки неотрицательны)
if (deltaMin >= 0 || k > 100) {
break;
}
// Определяем разрешающую строку (с минимальным отношением
// bD[i] / a[i][r])
double minRow = Double.POSITIVE_INFINITY;
s = -1;
for (i = 0; i < m; ++i) {
min[i] = bD[i] / a[i][r];
if (min[i] < 0) {
min[i] = Double.NaN;
}
if (minRow > min[i]) {
minRow = min[i];
s = i;
}
}
//out.println("Разрешающий столбец: r = " + r);
//out.println("Разрешающая строка: s = " + s);
//printTable();
// Разрешающий элемент (на пересечении разрешающих строки и столбца)
double element = a[s][r];
// Сохраняем содержимое массивов (т.к. их значения в ходе
// вычисления изменяются, но остаются нужными для этих вычислений
// ну как-то так :)
for (i = 0; i < m; ++i) {
tmpA[i] = new double[n];
for (j = 0; j < n; ++j) {
tmpA[i][j] = a[i][j];
}
tmpBD[i] = bD[i];
}
// Вносим переменную в базис,
// Пересчитываем базисное решение и коэффицетов переменных -
// - в разрешающей строке
bV[s] = r;
cB[s] = c[r];
for (j = 0; j < n; ++j) {
a[s][j] /= element;
}
bD[s] /= element;
// - в остальных строках
for (i = 0; i < m; ++i) {
// разрешающая строка уже пересчитана
if (i == s) {
continue;
}
// элемент разрешающего столбца
double air = tmpA[i][r];
// пересчет коэфициентов
for (j = 0; j < n; ++j) {
a[i][j] -= (air * tmpA[s][j]) / element;
}
// пересчет базисного решения
bD[i] -= (air * tmpBD[s]) / element;
}
//printDelta();
///out.println("----------------------------------------------------");
}
//out.println("Разрешающий столбец: r = " + (r + 1));
//out.println("Разрешающая строка: s = " + (s + 1));
//printTable();
//printDelta();
printDecision();
}
/**
* Симплекс-метод. Подсчет максимума.
*/
static void simplexMax() {
out.println("\n\nПоиск максимума\n\n");
out.println();
int i, j, r = -1, s = -1;
double[][] tmpA = new double[m][];
double[] tmpBD = new double[m];
init();
int k = 0;
while (true) {
++k;
// Считаем дельты, выделяем разрешающий столбец
// (столбец с максимальной оценкой)
double deltaMax = Double.NEGATIVE_INFINITY;
r = -1;
for (j = 0; j < n; ++j) {
double z = 0;
for (i = 0; i < m; ++i) {
z += cB[i] * a[i][j];
}
delta[j] = c[j] - z;
if (deltaMax < delta[j]) {
deltaMax = delta[j];
r = j;
for (i = 0; i < m; ++i) {
if (r > 0 && a[i][r] < 0) {
r = -1;
}
}
}
}
// Условие выхода (все оценки неположительны)
if (deltaMax <= 0 || k > 100) {
break;
}
// Определяем разрешающую строку (с минимальным отношением
// bD[i] / a[i][r])
double minRow = Double.POSITIVE_INFINITY;
s = -1;
for (i = 0; i < m; ++i) {
min[i] = bD[i] / a[i][r];
if (min[i] < 0) {
min[i] = Double.NaN;
}
if (minRow > min[i]) {
minRow = min[i];
s = i;
}
}
//out.println("Разрешающий столбец: r = " + r);
//out.println("Разрешающая строка: s = " + s);
//printTable();
// Разрешающий элемент (на пересечении разрешающих строки и столбца)
double element = a[s][r];
// Сохраняем содержимое массивов (т.к. их значения в ходе
// вычисления изменяются, но остаются нужными для этих вычислений
// ну как-то так :)
for (i = 0; i < m; ++i) {
tmpA[i] = new double[n];
for (j = 0; j < n; ++j) {
tmpA[i][j] = a[i][j];
}
tmpBD[i] = bD[i];
}
// Вносим переменную в базис,
// Пересчитываем базисное решение и коэффицетов переменных -
// - в разрешающей строке
bV[s] = r;
cB[s] = c[r];
for (j = 0; j < n; ++j) {
a[s][j] /= element;
}
bD[s] /= element;
// - в остальных строках
for (i = 0; i < m; ++i) {
// разрешающая строка уже пересчитана
if (i == s) {
continue;
}
// элемент разрешающего столбца
double air = tmpA[i][r];
// пересчет коэфициентов
for (j = 0; j < n; ++j) {
a[i][j] -= (air * tmpA[s][j]) / element;
}
// пересчет базисного решения
bD[i] -= (air * tmpBD[s]) / element;
}
//printDelta();
//out.println("----------------------------------------------------");
}
//out.println("Разрешающий столбец: r = " + (r + 1));
//out.println("Разрешающая строка: s = " + (s + 1));
//printTable();
//printDelta();
printDecision();
}
/**
* Печатает решение
*/
static void printDecision() {
int i,j;
out.println("Все оценки неположительны, подсчет завершен.");
out.print("Решение x = (");
boolean f;
for (j = 0; j < n; ++j) {
f = false;
for (i = 0; i < m; ++i) {
if (bV[i] == j) {
out.print(round(bD[i],2));
f = true;
break;
}
}
if (! f) {
out.print("0");
}
if (j < n - 1) {
out.print(", ");
}
}
out.print(")");
}
/**
* Печатает строку оценок
*/
static void printDelta() {
out.print("\t\t\t\t");
for (int j = 0; j < n; ++j) {
out.print(round(delta[j],2) + "\t");
}
out.println("delta[j]");
}
/**
* Печатает таблицу
*/
static void printTable() {
int i,j;
// вывод: строка коэффициентов
out.print("\t\t\t\t");
for (j = 0; j < n; ++j) {
out.print(round(c[j],2) + "\t");
}
out.println("C[j]");
// вывод: ряд x
out.print("\tcB\tbV\tbD\t");
for (j = 0; j < n; ++j) {
out.print("x[" + j + "]\t");
}
out.println("bD[i] / a[i][r]");
for (i = 0; i < m; ++i) {
out.print("\t" + round(cB[i],2) + "\tx[" + (bV[i]+1)
+ "]\t" + round(bD[i],2) + "\t");
for (j = 0; j < n; ++j) {
out.print(round(a[i][j],2) + "\t");
}
out.println(round(min[i],2));
}
}
static String round(double n, int p) {
if (Double.isNaN(n)) {
return "NaN";
}
if (Double.isInfinite(n)) {
return "\u221E";
}
double d = pow(10, p);
return (Math.round(n * d) / d) + "";
}
public static void main(String[] args) {
simplexMin();
simplexMax();
}
}