單純形法
理解完這個(gè)算法后大家也可以打一下，打碼過程中，會(huì)有很多很多的錯(cuò)誤要排查，編碼一小時(shí)从诲，排錯(cuò)三小時(shí)，不過從中可以練習(xí)到蠻多的（運(yùn)行截圖在文末）
-
輸入線性規(guī)劃標(biāo)準(zhǔn)型的數(shù)據(jù)（n個(gè)變量靡羡，m個(gè)約束條件）
- C //價(jià)值系數(shù)向量
- X //決策變量向量
- A //工藝系數(shù)矩陣
- b //資源常數(shù)
- yita //檢驗(yàn)數(shù)
- theta //b除以換入變量在每行的系數(shù)系洛，即單純形表最右端參數(shù)
-
找基可行解
- 簡(jiǎn)單的拿最后m個(gè)決策變量，后期可優(yōu)化
-
判斷是否最優(yōu)解:計(jì)算并判斷是否每一個(gè)檢驗(yàn)數(shù)yita都小于等于0
- 是
- 輸出最優(yōu)解:max z = CX
- 否
- 確定換入變量
- 檢驗(yàn)數(shù)大于0中略步，檢驗(yàn)數(shù)最大的非基變量
- 確定換出變量
- 計(jì)算theta
- 判斷是否線性規(guī)劃結(jié)果為無(wú)界解：theta的系數(shù)是否均小于或等于0
- 是
- 終止運(yùn)算描扯，輸出結(jié)果為無(wú)界解
- 否
- 取theta[i]中大于0且最小的行所對(duì)應(yīng)的基變量作為換出變量
- 是
- 旋轉(zhuǎn)運(yùn)算
- 換入變量的所對(duì)應(yīng)的方程中左右兩邊同除換入變量的系數(shù)
- 再次循環(huán)，重新判斷是否最優(yōu)解
- 確定換入變量
- 是
所有函數(shù)
- void inputNums() //輸入數(shù)據(jù)
- void findBasedVariables() //找基變量
- bool isOptimum() //是否最優(yōu)解
- int getVariableIn() //確定換入變量
- int getVariableOut() //確定換出變量
- void updateVectors() //更新旋轉(zhuǎn)運(yùn)算后的矩陣
- private static void printVector() //輸出系數(shù)矩陣
- void printOptimun() //輸出最優(yōu)解
先在main函數(shù)中寫好主要邏輯纳像，再具體實(shí)現(xiàn)
public static void main(String[] args) {
//輸入數(shù)據(jù)荆烈，為了簡(jiǎn)單起見，我們的數(shù)據(jù)直接在代碼中敲入竟趾，這個(gè)函數(shù)等測(cè)試完后加
inputNums();
//找初始基變量
findBasedVariables();
//判斷是否最優(yōu)解
while (!isOptimum()) {
//找換入變量
idxOfIn = getVariableIn();
printVector();
//找換出變量
idxOfOut = getVariableOut();
//如果idxOfOut返回-1，則該線性規(guī)劃問題有無(wú)界解
if(idxOfOut == -1)
return;
//旋轉(zhuǎn)運(yùn)算宫峦，更新矩陣
updateVectors();
printVector();
System.out.println("\n");
}
//輸出最優(yōu)解
printOptimum();
}
全局變量
private static double A[][] = { { 1, 2, 1, 0, 0 },
{ 2, 1, 0, 1, 0 },
{ 4, 3, 0, 0, 1 } };// 系數(shù)矩陣
private static int m = A.length; //m個(gè)方程
private static int n = A[0].length; //n個(gè)決策變量
private static double C[] = { 3, 2, 0, 0, 0 }; // 價(jià)值系數(shù)
private static double b[] = { 5, 4 ,9}; // 資源常數(shù)
private static double theta[] = new double[m]; //b的檢驗(yàn)數(shù)
private static int basedVar[] = new int[m]; // 基變量岔帽，存基變量的下標(biāo)，從1開始標(biāo)號(hào)（區(qū)別于數(shù)組存儲(chǔ)習(xí)慣）
private static double yita[] = new double[n]; //檢驗(yàn)數(shù)导绷，有n個(gè)決策變量的檢驗(yàn)數(shù)
private static double result = -1; //結(jié)果
private static int idxOfIn = -1; //換入變量的下標(biāo)
private static int idxOfOut = -1; //換出變量的下標(biāo)
inputNums()
// 輸入數(shù)據(jù)犀勒，先在代碼中寫入數(shù)據(jù)，后期再加，先把初始檢驗(yàn)數(shù)賦值為價(jià)值系數(shù)
private static void inputNums() {
for (int i = 0; i < yita.length; i++) {
yita[i] = C[i]; //yita為檢驗(yàn)數(shù)
}
}
findBasedVariables()
// 找基變量贾费，簡(jiǎn)單的拿最后m個(gè)決策變量钦购，后期可優(yōu)化，存儲(chǔ)在basedVar數(shù)組中
private static void findBasedVariables() {
//取n個(gè)決策變量的最后m個(gè)作基變量
for (int i = 0; i < m; i++) {
//basedVar[i] = n-i;
//改變存放順序?yàn)檎龜? basedVar[m-i-1] = n-i ;
}
System.out.println("基變量為：");
for (int i = 0; i < basedVar.length; i++) {
System.out.print("x" + (basedVar[i]) + "\t");
}
System.out.println();
}
isOptimum()
// 判斷是否最優(yōu)解褂萧，并計(jì)算檢驗(yàn)數(shù)yita向量
private static boolean isOptimum() {
//換入變量代替換出變量
if(idxOfIn != -1 && idxOfOut != -1){
//第idxOfOut個(gè)基變量換為x idxOfIn
basedVar[idxOfOut] = idxOfIn+1;
}
//更新檢驗(yàn)數(shù)
for (int i = 0; i < n; i++) {
double temp = yita[i];
for (int j = 0; j < m; j++) {
temp -= A[j][i] * C[basedVar[j] -1];
}
yita[i] = temp;
}
boolean hasPossitiveYita = false;
for (int i = 0; i < yita.length; i++) {
if(yita[i] > 0)
hasPossitiveYita = true;
}
System.out.println("是否最優(yōu)解：" + !hasPossitiveYita);
return !hasPossitiveYita;
}
getVariableIn()
// 確定換入變量押桃，返回?fù)Q入變量的下標(biāo)-1
private static int getVariableIn() {
//遍歷檢驗(yàn)數(shù)
int index = 0;
System.out.println("檢驗(yàn)數(shù)如下：");
for (int i = 0; i < yita.length; i++) {
System.out.print(yita[i] + "\t");
if(yita[i] > yita[index]){
index = i;
}
}
System.out.println();
System.out.println("換入變量是x" + (index+1));
return index;
}
getVariableOut()
// 確定換出變量，返回?fù)Q出變量在基變量向量中的下標(biāo)
private static int getVariableOut() {
System.out.println("theta：");
for (int i = 0; i < m; i++) {
if( Double.compare(A[i][idxOfIn], 0) != 0)
theta[i] = b[i] / A[i][idxOfIn];
else {
theta[i] = 0;
}
System.out.print(theta[i] + "\t");
}
System.out.println();
int index = 0;
for (int i = 0; i < theta.length; i++) {
if(theta[i] <= 0){
System.out.println("該方程有無(wú)界解...");
return -1;
}else {
if(theta[i] < theta[index])
index = i;
}
}
System.out.println("換出變量是:x" + (basedVar[index]));
return index;
}
updateVectors()
// 更新旋轉(zhuǎn)運(yùn)算后的矩陣
private static void updateVectors() {
//m個(gè)方程导犹，n個(gè)變量
//將主元系數(shù)化為1
//防止迭代中主元的值被改變后引起 其它系數(shù)除主元的新值唱凯，將主元的原值存于temp
double temp = A[idxOfOut][idxOfIn];
for (int i = 0; i < n; i++) {
A[idxOfOut][i] /= temp;
}
b[idxOfOut] /= temp;
System.out.println("\n將主元系數(shù)化為1");
printVector();
//主元所在列其余元素系數(shù)要化為0，即：主元列中谎痢，非主元所在行均減去 主元系數(shù)分之一*A[m][n]
for (int i = 0; i < m; i++) {
//若是換出變量所對(duì)應(yīng)行磕昼，則該行不用換算
double temp1 = A[i][idxOfIn]/A[idxOfOut][idxOfIn];
if(i != idxOfOut){
for (int j = 0; j < n; j++) {
A[i][j] -= A[idxOfOut][j]*temp1;
}
b[i] -= b[idxOfOut] * temp1;
}
}
System.out.println("完成一次矩陣旋轉(zhuǎn)運(yùn)算...");
}
printVector()
//輸出系數(shù)矩陣
private static void printVector() {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(A[i][j] + "\t");
}
System.out.println(b[i]);
}
System.out.println("-----------------------------------------------");
}
printOptimum()
//輸出最優(yōu)解
private static void printOptimum() {
result = 0;
for (int i = 0; i < basedVar.length; i++) {
result += C[basedVar[i]-1] * b[i];
}
System.out.println("最優(yōu)解：z = " + result);
}
image.png
image.png
