A Karmarkar-algoritmus egy lineáris programozási (LP) módszer, amelyet a lineáris egyenlőtlenségekkel korlátozott optimalizálási problémák megoldására használnak. Az algoritmus egy belső pont módszer, amely iteratívan közelíti meg az optimális megoldást, és hatékony alternatívát kínál a simplex módszerrel szemben.
A lineáris programozási probléma általános alakja: ahol: - (x): változók vektora, - (c): költségtényező vektor, - (A): mátrix, amely korlátozza a megoldást, - (b): a korlátok vektora.
Karmarkar(A, b, c, ε):
Kezdeti belső pont x₀
iteráció = 0
amíg a célfüggvény javulása > ε:
1. Skálázd a mátrixot és a megoldást a belső pontban.
2. Számítsd ki a projektált gradienst.
3. Optimalizáld a lépéshosszt a belső térben.
4. Frissítsd a megoldást: x_{k+1} = x_k + lépésirány.
5. Normalizáld az új megoldást.
iteráció += 1
térj vissza xₖ, mint a közelítő megoldás.
A Karmarkar-algoritmus implementációja egy egyszerű példán keresztül:
import numpy as np
def karmarkar(A, b, c, epsilon=1e-6, max_iter=1000):
# Kezdeti megoldás (belsejében legyen a megoldási térnek)
n = len(c)
x = np.ones(n) / n # Normalizált kezdőpont
for _ in range(max_iter):
# Skálázás és projektált gradiens
D = np.diag(x)
A_tilde = A @ D
c_tilde = D @ c
# Normált keresési irány (gradienselemzés)
pseudo_inv = np.linalg.pinv(A_tilde @ A_tilde.T)
y = pseudo_inv @ A_tilde @ c_tilde
d = -c_tilde - A_tilde.T @ y
# Optimalizált lépéshossz
alpha = min(1, min(-x / d))
# Lépés frissítése
x += alpha * d
x /= np.sum(x) # Normalizálás
# Ellenőrzés: célfüggvény javulása
if np.linalg.norm(c @ x) < epsilon:
break
return x
# Példa bemenet
A = np.array([
,
,
])
b = np.array()
c = np.array()
solution = karmarkar(A, b, c)
print("Optimalizált megoldás:", solution)
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
vector<double> karmarkar(const vector<vector<double>>& A, const vector<double>& b, const vector<double>& c, double epsilon = 1e-6, int max_iter = 1000) {
int n = c.size();
vector<double> x(n, 1.0 / n); // Kezdeti normalizált megoldás
for (int iter = 0; iter < max_iter; ++iter) {
// Skálázás mátrix
vector<vector<double>> D(n, vector<double>(n, 0.0));
for (int i = 0; i < n; ++i) {
D = x;
}
// A_tilde = A * D
vector<vector<double>> A_tilde(A.size(), vector<double>(n, 0.0));
for (int i = 0; i < A.size(); ++i) {
for (int j = 0; j < n; ++j) {
A_tilde = A * D;
}
}
// Gradiens irány számítása
vector<double> grad(n, 0.0);
for (int i = 0; i < n; ++i) {
grad = -c; // Egyszerű lineáris példa
}
// Lépéshossz számítása
double alpha = 1.0;
for (int i = 0; i < n; ++i) {
if (grad < 0) {
alpha = min(alpha, -x / grad);
}
}
// Lépés frissítése
for (int i = 0; i < n; ++i) {
x += alpha * grad;
}
// Normalizálás
double sum_x = 0.0;
for (double val : x) sum_x += val;
for (int i = 0; i < n; ++i) {
x /= sum_x;
}
// Ellenőrzés
double norm_grad = 0.0;
for (double val : grad) {
norm_grad += val * val;
}
if (sqrt(norm_grad) < epsilon) break;
}
return x;
}
int main() {
vector<vector<double>> A = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 10}
};
vector<double> b = {6, 15, 25};
vector<double> c = {1, 2, 3};
vector<double> solution = karmarkar(A, b, c);
cout << "Optimalizált megoldás:" << endl;
for (double val : solution) {
cout << val << " ";
}
cout << endl;
return 0;
}
A Karmarkar-algoritmus a modern optimalizálási technikák fontos eszköze, különösen a lineáris programozás és más konvex optimalizálási problémák területén.