改变单纯形算法，尽量减少对目标函数不能最大化 [英] Alter Simplex Algorithm to Minimize on objective function NOT maximize
问题描述
我已经创建了下面的单纯形算法最大化目标函数。我想相反的情况发生。在这个例子中有两个变量的算法必须找出在这里（13.0和23.0）通过，以获得设定的限制内的最大可能结果乘以这两个变量。我想算法计算出的最低可能的结果吧。
I have created the following Simplex Algorithm that maximises on the objective function. I want the opposite to happen. In this example there are two variables and the algorithm must figure out what to multiply these two variables here (13.0 and 23.0) by in order to get the maximum possible result within the constraints set. I want the algorithm to figure out the lowest possible result instead.
我的code：
import java.util.*;
public class Simplex
{
private static final double EPSILON = 1.0E-10;
private double[][] tableaux;
private int numOfConstraints;
private int numOfVariables;
private int[] basis;
/**
* Constructor for objects of class Simplex
*/
public Simplex()
{
double[][] thisTableaux = {
{ 5.0, 15.0 },
{ 4.0, 4.0 },
{ 35.0, 20.0 },
};
double[] constraints = { 480.0, 160.0, 1190.0 };
double[] variables = { 13.0, 23.0 };
numOfConstraints = constraints.length;
numOfVariables = variables.length;
tableaux = new double[numOfConstraints+1][numOfVariables+numOfConstraints+1];
//adds all elements from thisTableaux to tableaux
for(int i=0; i < numOfConstraints; i++)
{
for(int j=0; j < numOfVariables; j++)
{
tableaux[i][j] = thisTableaux[i][j];
}
}
//adds a slack variable for each variable there is and sets it to 1.0
for(int i=0; i < numOfConstraints; i++)
{
tableaux[i][numOfVariables+i] = 1.0;
}
//adds variables into the second [] of tableux
for(int j=0; j < numOfVariables; j++)
{
tableaux[numOfConstraints][j] = variables[j];
}
//adds constraints to first [] of tableaux
for(int k=0; k < numOfConstraints; k++)
{
tableaux[k][numOfConstraints+numOfVariables] = constraints[k];
}
basis = new int[numOfConstraints];
for(int i=0; i < numOfConstraints; i++)
{
basis[i] = numOfVariables + i;
}
//show();
//optimise();
//assert check(thisTableaux, constraints, variables);
}
public void optimise() {
while(true) {
int q = findLowestNonBasicCol();
if(q == -1) {
break;
}
int p = getPivotRow(q);
if(p == -1) throw new ArithmeticException("Linear Program Unbounded");
pivot(p, q);
basis[p] = q;
}
}
public int findLowestNonBasicCol() {
for(int i=0; i < numOfConstraints + numOfVariables; i++)
{
if(tableaux[numOfConstraints][i] > 0) {
return i;
}
}
return -1;
}
public int findIndexOfLowestNonBasicCol() {
int q = 0;
for(int i=1; i < numOfConstraints + numOfVariables; i++)
{
if(tableaux[numOfConstraints][i] > tableaux[numOfConstraints][q]) {
q = i;
}
}
if(tableaux[numOfConstraints][q] <= 0) {
return -1;
}
else {
return q;
}
}
/**
* Finds row p which will be the pivot row using the minimum ratio rule.
* -1 if there is no pivot row
*/
public int getPivotRow(int q) {
int p = -1;
for(int i=0; i < numOfConstraints; i++) {
if (tableaux[i][q] <=0) {
continue;
}
else if (p == -1) {
p = i;
}
else if((tableaux[i][numOfConstraints+numOfVariables] / tableaux[i][q] < tableaux[p][numOfConstraints+numOfVariables] / tableaux[p][q])) {
p = i;
}
}
return p;
}
public void pivot(int p, int q) {
for(int i=0; i <= numOfConstraints; i++) {
for (int j=0; j <= numOfConstraints + numOfVariables; j++) {
if(i != p && j != q) {
tableaux[i][j] -= tableaux[p][j] * tableaux[i][q] / tableaux[p][q];
}
}
}
for(int i=0; i <= numOfConstraints; i++) {
if(i != p) {
tableaux[i][q] = 0.0;
}
}
for(int j=0; j <= numOfConstraints + numOfVariables; j++) {
if(j != q) {
tableaux[p][j] /= tableaux[p][q];
}
}
tableaux[p][q] = 1.0;
show();
}
public double result() {
return -tableaux[numOfConstraints][numOfConstraints+numOfVariables];
}
public double[] primal() {
double[] x = new double[numOfVariables];
for(int i=0; i < numOfConstraints; i++) {
if(basis[i] < numOfVariables) {
x[basis[i]] = tableaux[i][numOfConstraints+numOfVariables];
}
}
return x;
}
public double[] dual() {
double[] y = new double[numOfConstraints];
for(int i=0; i < numOfConstraints; i++) {
y[i] = -tableaux[numOfConstraints][numOfVariables];
}
return y;
}
public boolean isPrimalFeasible(double[][] thisTableaux, double[] constraints) {
double[] x = primal();
for(int j=0; j < x.length; j++) {
if(x[j] < 0.0) {
StdOut.println("x[" + j + "] = " + x[j] + " is negative");
return false;
}
}
for(int i=0; i < numOfConstraints; i++) {
double sum = 0.0;
for(int j=0; j < numOfVariables; j++) {
sum += thisTableaux[i][j] * x[j];
}
if(sum > constraints[i] + EPSILON) {
StdOut.println("not primal feasible");
StdOut.println("constraints[" + i + "] = " + constraints[i] + ", sum = " + sum);
return false;
}
}
return true;
}
private boolean isDualFeasible(double[][] thisTableaux, double[] variables) {
double[] y = dual();
for(int i=0; i < y.length; i++) {
if(y[i] < 0.0) {
StdOut.println("y[" + i + "] = " + y[i] + " is negative");
return false;
}
}
for(int j=0; j < numOfVariables; j++) {
double sum = 0.0;
for(int i=0; i < numOfConstraints; i++) {
sum += thisTableaux[i][j] * y[i];
}
if(sum < variables[j] - EPSILON) {
StdOut.println("not dual feasible");
StdOut.println("variables[" + j + "] = " + variables[j] + ", sum = " + sum);
return false;
}
}
return true;
}
private boolean isOptimal(double[] constraints, double[] variables) {
double[] x = primal();
double[] y = dual();
double value = result();
double value1 = 0.0;
for(int j=0; j < x.length; j++) {
value1 += variables[j] * x[j];
}
double value2 = 0.0;
for(int i=0; i < y.length; i++) {
value2 += y[i] * constraints[i];
}
if(Math.abs(value - value1) > EPSILON || Math.abs(value - value2) > EPSILON) {
StdOut.println("value = " + value + ", cx = " + value1 + ", yb = " + value2);
return true;
}
return true;
}
private boolean check(double[][] thisTableaux, double[] constraints, double [] variables) {
return isPrimalFeasible(thisTableaux, constraints) && isDualFeasible(thisTableaux, variables) && isOptimal(constraints, variables);
}
}
如果您需要任何更多的信息只问。任何帮助AP preciated感谢。
If you need any more info just ask. Any help appreciated thanks.
推荐答案
如果要最大限度地减少F（X），这相当于最大化-f（x）的，因此，如果您贴code正确地解决了最大化的问题，你可以用它来尽量减少任何目标函数f（x）仅仅通过最大限度地发挥其加法逆-f（x）的。
If you want to minimize f(x), this is equivalent to maximizing -f(x), so if your posted code solves maximization problems correctly, you can use it to minimize any objective function f(x) simply by maximizing its additive inverse -f(x).
请注意，您的不的修改限制，只有目标函数。
Note that you do not change the constraints, only the objective function.
例如，最小化函数f（x）= 3×+ 5中，x> = 1相当于最大化-f（x）的= -3x -5中，x> = 1
For example, minimizing f(x) = 3x + 5, x >= 1 is equivalent to maximizing -f(x) = -3x -5, x >= 1.
分钟[F（X）中，x> = 1] = F（1）= 8 = - （ - 8）= - [ - F（1）] = -max [-f（X）中，x> = 1。
min[f(x), x>=1] = f(1) = 8 = -(-8) = -[-f(1)] = -max[-f(x), x>=1].
在一般情况下，分并[f（x）的] = F（Xmin时）= - [ - F（Xmax的）] = -max [-f（x）的]和在Xmin = Xmax的
In general, min[f(x)] = f(Xmin) = -[-f(Xmax)] = -max[-f(x)] and Xmin = Xmax.
在上面的例子中，最小[F（X）〕= -max [-f（x）的] = 8和在Xmin = Xmax的= 1
In the above example, min[f(x)] = -max[-f(x)] = 8 and Xmin = Xmax = 1.
在你给的特殊的例子，你只需要更改行
In the particular example you give, you would simply need to change the line
double[] variables = { 13.0, 23.0 };
到
double[] variables = { -13.0, -23.0 };
返回然后应是相同的情况下的最低限度，其中
The values of the variables returned should then be the same as for the minimum of the case where
double[] variables = { 13.0, 23.0 };
和乘以-1的目标函数的值将得到目的的最小值的情况下
and multiplying the value of the objective function by -1 will give the minimum of the objective for the case where
double[] variables = { 13.0, 23.0 };
这篇关于改变单纯形算法，尽量减少对目标函数不能最大化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
