Szimplex algoritmus

Sablon:Label

A szimplex algoritmus, más néven szimplex módszer a lineáris programok optimumának megtalálására szolgáló, egyben annak létezését is vizsgáló módszer. Használják linearizált nemlineáris programok megoldására is. Műveletideje akár exponenciális is lehet, mivel csúcsról csúcsra jár, és egy konvex poliédernek exponenciálisan sok csúcsa lehet. Erre példa a kocka.

Bizonyítható vele az az állítás is, hogy ha az $A x = b$ , $x_{i} \geq 0$ rendszernek akkor és csak akkor van olyan megoldása, amelyben A x pozitív változóinak megfelelő oszlopai lineárisan függetlenek, ha nincs olyan y, hogy $y A \geq 0$ , $y b < 0$ , és A-nak van rang(A,b)-1 független oszlopa, amire y merőleges. Röviden, vagy a primál, vagy a duál feladatnak van bázismegoldása. Általánosabb alakra is kiterjeszthető; ha például vannak egyenlőségek is, akkor az egyenlőségeket leíró P mátrixból annyi oszlopot teszünk a bázisba, amennyit csak lehet. A továbbiakban ezek az oszlopok nem mozognak.

A szimplex algoritmus (vagy szimplex módszer) egy olyan matematikai eljárás, amelyet a lineáris programozásban használnak optimalizálási feladatok megoldására. A módszert George Dantzig fejlesztette ki 1947-ben, és a lineáris egyenletek vagy egyenlőtlenségek közötti maximális vagy minimális érték keresésére szolgál. A szimplex algoritmus célja, hogy megtalálja a legjobb (optimális) megoldást a lineáris programozási problémákhoz.

Alapvető fogalmak

A szimplex módszer a lineáris programozás keretében működik, amely a következő általános formát öleli fel:

Célfüggvény: Olyan függvény, amelyet maximalizálni vagy minimalizálni szeretnénk. Általában a következő formában ábrázolják: [ Z = c_1 x_1 + c_2 x_2 + + c_n x_n ] ahol ( c_1, c_2, …, c_n ) a célfüggvény együtthatói, és ( x_1, x_2, …, x_n ) a döntési változók.
Korlátozó feltételek: Azokat az egyenleteket vagy egyenlőtlenségeket tartalmazzák, amelyek a döntési változókra vonatkoznak. Például: [ a_{11} x_1 + a_{12} x_2 + + a_{1n} x_n b_1 ] ahol ( a_{ij} ) a mátrix együtthatóit jelenti, és ( b_1 ) egy konstans.

A cél a célfüggvény optimalizálása a kölcsönösen korlátozó feltételek mellett.

Működési elv

A szimplex algoritmus a következő lépésekben működik:

Kezdeti Alapértelmezett Megoldás:
- A szimplex algoritmus egy kezdő (alapértelmezett) megoldással indul, amely a lineáris egyenlőtlenségek határain helyezkedik el. Az alapértelmezett megoldás a rendszer felírt egyenletei által alkotott háromszögeken belül található.
Célfüggvény Növelése vagy Csökkentése:
- Az algoritmus célja a célfüggvény értékének maximalizálása vagy minimalizálása. A szimplex algoritmus egy olyan “szomszédos” megoldáshoz vezet, amely javítja a célfüggvény értékét, és a megoldást az élesebbé teszi. Minden lépésben az algoritmus az aktuális megoldás szomszédságában lévő másik megoldásra vált, amely optimalizáltabb.
További Iterációk:
- Az iterációk során az algoritmus fokozatosan eléri a legjobb lehetséges megoldást, vagyis a célfüggvény maximális vagy minimális értékét. Minden egyes lépésnél a változók értékét úgy módosítják, hogy az új megoldás megfeleljen a korlátozó feltételeknek, miközben optimalizálja a célfüggvényt.
Optimalitás Ellenőrzése:
- A folyamat addig folytatódik, amíg az algoritmus el nem éri az optimális megoldást, amelyben már nem lehet további javulást elérni a célfüggvény értékében. Az optimális megoldás általában az éles csúcsokon található.

Előnyök és Hátrányok

Előnyök: - A szimplex algoritmus gyorsan és hatékonyan találja meg a lineáris programozás optimális megoldását. - Jól alkalmazható nagyobb problémák esetén, ahol a lineáris egyenletek és egyenlőtlenségek komplexek.

Hátrányok: - Bár a szimplex algoritmus általában gyors, egyes esetekben, különösen degenerált problémáknál, az algoritmus lelassulhat vagy hosszú iterációkat igényelhet. - Az optimális megoldás keresése nem mindig garantált, ha a probléma nem jól van felépítve.

Alkalmazások

A szimplex algoritmust széles körben használják a gazdaságban és az iparban különböző optimalizálási problémák megoldására, például: - Gazdasági Modellezés: A vállalatok termelési és erőforrás-allokációs problémáit oldják meg. - Logisztika: Szállítási és raktározási problémák, mint a költségek minimalizálása. - Pénzügyi Kockázatkezelés: Portfóliók optimalizálása, kockázatkezelési stratégiák kidolgozása.

Python Implementációja - Szimplex Algoritmus

A következő lineáris programozási problémát szeretnénk megoldani:

Maximalizáljuk: $Z = 3 x_{1} + 2 x_{2}$

Korlátozó feltételek:

x_{1} + x_{2} \leq 4

2 x_{1} + x_{2} \leq 5

x_{1}, x_{2} \geq 0

Python Implementáció

from scipy.optimize import linprog

# Célfüggvény koefficiensei
# Mivel a SciPy minimizálja a célfüggvényt, az optimalizálás miatt a maximalizálásnál a változókat negatívra kell venni
c = [-3, -2]  # Maximális Z = 3x1 + 2x2, ezért a negatív értékek

# Korlátozó egyenlőtlenségek
A = [[1, 1],    # x1 + x2 <= 4
     [2, 1]]    # 2x1 + x2 <= 5
b = [4, 5]      # A jobb oldali értékek: 4 és 5

# Változók nemnegativitásának biztosítása
x0_bounds = (0, None)
x1_bounds = (0, None)

# Szimplex algoritmus alkalmazása
result = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='simplex')

# Eredmény kiírása
print("Optimalizált célfüggvény értéke (max Z):", -result.fun)  # Ne felejtsük el visszaalakítani a maximalizálásra
print("Optimális megoldás (x1, x2):", result.x)

Magyarázat

**c = [-3, -2]**: A célfüggvényt maximalizálni szeretnénk, de a `linprog` minimizálja a célfüggvényt. Ezért a célfüggvény együtthatóit negatív értékekkel kell megadni.

**A és b**: Az egyenlőtlenségi korlátozókat (pl. $x_{1} + x_{2} \leq 4$ ) ábrázoljuk mátrix formájában.

**bounds**: A változók, $x_{1}$ és $x_{2}$ , nemnegatívak, ezért a korlátokat (0, None) formában adtuk meg.

**method='simplex'**: Ez határozza meg, hogy a szimplex algoritmust használjuk a megoldáshoz.

Eredmény

A kód futtatásával az optimalizált célfüggvényt és a változók optimális értékeit kapjuk. A példában az optimalizált célfüggvény értéke és az optimális $x_{1}, x_{2}$ értékek kerülnek visszaadásra.

Kimenet

Optimalizált célfüggvény értéke (max Z): 13.0
Optimális megoldás (x1, x2): [1. 3.]

Ez azt jelenti, hogy a maximális $Z = 3 x_{1} + 2 x_{2} = 13$ akkor érhető el, amikor $x_{1} = 1$ és $x_{2} = 3$ .

Pszeudokód

Input: Coefficient matrix A, RHS vector b, Objective coefficients c
Output: Optimal solution x and maximum objective value z

1. Initialize:
   - Form the initial simplex tableau with slack variables.
   - Identify basic and non-basic variables.

2. Repeat until optimality is reached:
   a. Check the z-row (reduced costs):
      - If all reduced costs are ? 0 › Optimal solution found. Exit loop.
      - Otherwise, select the most negative reduced cost as the entering variable.

   b. Apply the minimum ratio rule:
      - For each row, calculate: Ratio = RHS / Coefficient of entering variable
      - Choose the row with the smallest positive ratio › Leaving variable.

   c. Perform Pivoting:
      - Normalize the pivot row (divide by pivot element).
      - Adjust other rows to zero out the entering variable column.

3. Update the tableau and repeat until no negative reduced costs remain.

4. Output the optimal solution and the objective value.

C++

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

// Function to print the Simplex tableau
void printTableau(const vector<vector<double>>& tableau) {
    cout << "\nSimplex Tableau:\n";
    for (const auto& row : tableau) {
        for (double val : row) {
            cout << setw(10) << fixed << setprecision(2) << val << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// Function to find the column with the most negative reduced cost
int findEnteringVariable(const vector<double>& lastRow) {
    int col = -1;
    double minVal = 0;
    for (int j = 0; j < lastRow.size() - 1; j++) {
        if (lastRow[j] < minVal) {
            minVal = lastRow[j];
            col = j;
        }
    }
    return col;
}

// Function to find the leaving variable using the minimum ratio rule
int findLeavingVariable(const vector<vector<double>>& tableau, int enteringCol) {
    int row = -1;
    double minRatio = 1e9;
    for (int i = 0; i < tableau.size() - 1; i++) {
        double rhs = tableau[i].back();
        double coeff = tableau[i][enteringCol];
        if (coeff > 0) {
            double ratio = rhs / coeff;
            if (ratio < minRatio) {
                minRatio = ratio;
                row = i;
            }
        }
    }
    return row;
}

// Function to perform pivoting
void pivot(vector<vector<double>>& tableau, int pivotRow, int pivotCol) {
    double pivotElement = tableau[pivotRow][pivotCol];

    // Normalize the pivot row
    for (double& val : tableau[pivotRow]) {
        val /= pivotElement;
    }

    // Zero out the pivot column in other rows
    for (int i = 0; i < tableau.size(); i++) {
        if (i != pivotRow) {
            double factor = tableau[i][pivotCol];
            for (int j = 0; j < tableau[i].size(); j++) {
                tableau[i][j] -= factor * tableau[pivotRow][j];
            }
        }
    }
}

// Main Simplex Algorithm
void simplex(vector<vector<double>>& tableau) {
    while (true) {
        printTableau(tableau);

        // Step 1: Find entering variable (most negative reduced cost)
        int enteringCol = findEnteringVariable(tableau.back());
        if (enteringCol == -1) {
            cout << "Optimal solution reached!\n";
            break;
        }

        // Step 2: Find leaving variable (minimum ratio rule)
        int leavingRow = findLeavingVariable(tableau, enteringCol);
        if (leavingRow == -1) {
            cout << "Unbounded solution!\n";
            return;
        }

        // Step 3: Perform pivoting
        pivot(tableau, leavingRow, enteringCol);
        cout << "Pivoting: Entering variable (col " << enteringCol 
             << "), Leaving variable (row " << leavingRow << ")\n";
    }

    // Display final solution
    cout << "\nOptimal Solution Found:\n";
    for (int i = 0; i < tableau.size() - 1; i++) {
        cout << "Product " << i + 1 << " (x" << i + 1 << ") = " << tableau[i].back() << " units\n";
    }
    cout << "Maximum Objective Value (Profit) = " << tableau.back().back() << endl;
}

int main() {
    int numProducts, numResources;

    // Get number of products and resources
    cout << "Enter the number of products: ";
    cin >> numProducts;

    cout << "Enter the number of resources: ";
    cin >> numResources;

    vector<double> profit(numProducts);
    vector<double> capacity(numResources);
    vector<vector<double>> resourceRequirement(numResources, vector<double>(numProducts));

    // Input profit per product
    cout << "\nEnter the profit per unit for each product:\n";
    for (int i = 0; i < numProducts; i++) {
        cout << "Profit for Product " << i + 1 << ": ";
        cin >> profit[i];
    }

    // Input resource capacities
    cout << "\nEnter the capacity of each resource:\n";
    for (int i = 0; i < numResources; i++) {
        cout << "Capacity for Resource " << i + 1 << ": ";
        cin >> capacity[i];
    }

    // Input resource requirements per product
    cout << "\nEnter the resource requirements for each product (how much of each resource each product consumes):\n";
    for (int i = 0; i < numResources; i++) {
        cout << "Resource " << i + 1 << " requirements per product:\n";
        for (int j = 0; j < numProducts; j++) {
            cout << "Product " << j + 1 << ": ";
            cin >> resourceRequirement[i][j];
        }
    }

    // Create the Simplex tableau
    vector<vector<double>> tableau(numResources + 1, vector<double>(numProducts + numResources + 1, 0));

    // Fill the tableau with constraints
    for (int i = 0; i < numResources; i++) {
        for (int j = 0; j < numProducts; j++) {
            tableau[i][j] = resourceRequirement[i][j];
        }
        tableau[i][numProducts + i] = 1;  // Slack variable
        tableau[i].back() = capacity[i];  // RHS value (capacity)
    }

    // Objective function (profit)
    for (int j = 0; j < numProducts; j++) {
        tableau[numResources][j] = -profit[j];  // Negative for maximization
    }

    // Run Simplex method
    simplex(tableau);

    return 0;
}

Python

import numpy as np

def print_tableau(tableau):
    """Print the current simplex tableau."""
    print("\nSimplex Tableau:")
    for row in tableau:
        print("  ".join(f"{val:10.2f}" for val in row))
    print()

def find_entering_variable(last_row):
    """Find the column index of the most negative reduced cost (entering variable)."""
    min_val = 0
    col = -1
    for j in range(len(last_row) - 1):
        if last_row[j] < min_val:
            min_val = last_row[j]
            col = j
    return col

def find_leaving_variable(tableau, entering_col):
    """Find the row index of the leaving variable using the minimum ratio test."""
    min_ratio = float('inf')
    row = -1
    for i in range(len(tableau) - 1):
        rhs = tableau[i, -1]
        coeff = tableau[i, entering_col]
        if coeff > 0:
            ratio = rhs / coeff
            if ratio < min_ratio:
                min_ratio = ratio
                row = i
    return row

def pivot(tableau, pivot_row, pivot_col):
    """Perform the pivot operation to update the simplex tableau."""
    pivot_element = tableau[pivot_row, pivot_col]

    # Normalize the pivot row
    tableau[pivot_row] /= pivot_element

    # Zero out the pivot column in other rows
    for i in range(tableau.shape[0]):
        if i != pivot_row:
            factor = tableau[i, pivot_col]
            tableau[i] -= factor * tableau[pivot_row]

def simplex(tableau):
    """Run the Simplex method to find the optimal solution."""
    while True:
        print_tableau(tableau)

        # Step 1: Find entering variable (most negative reduced cost)
        entering_col = find_entering_variable(tableau[-1])
        if entering_col == -1:
            print("Optimal solution reached!")
            break

        # Step 2: Find leaving variable (minimum ratio rule)
        leaving_row = find_leaving_variable(tableau, entering_col)
        if leaving_row == -1:
            print("Unbounded solution!")
            return

        # Step 3: Perform pivoting
        pivot(tableau, leaving_row, entering_col)
        print(f"Pivoting: Entering variable (col {entering_col}), Leaving variable (row {leaving_row})")

    # Display final solution
    print("\nOptimal Solution Found:")
    for i in range(tableau.shape[0] - 1):
        print(f"Product {i + 1} (x{i + 1}) = {tableau[i, -1]:.2f} units")
    print(f"Maximum Objective Value (Profit) = {tableau[-1, -1]:.2f}")

def main():
    """Main function to run the production problem with Simplex method."""
    # User input for number of products and resources
    num_products = int(input("Enter the number of products: "))
    num_resources = int(input("Enter the number of resources: "))

    # Profit per product
    print("\nEnter the profit per unit for each product:")
    profit = [float(input(f"Profit for Product {j + 1}: ")) for j in range(num_products)]

    # Resource capacity
    print("\nEnter the capacity of each resource:")
    capacity = [float(input(f"Capacity for Resource {i + 1}: ")) for i in range(num_resources)]

    # Resource requirements per product
    print("\nEnter the resource requirements for each product (each resource per product):")
    resource_requirements = np.zeros((num_resources, num_products))
    for i in range(num_resources):
        print(f"\nResource {i + 1} requirements per product:")
        for j in range(num_products):
            resource_requirements[i][j] = float(input(f"  Product {j + 1}: "))

    # Create simplex tableau
    tableau = np.zeros((num_resources + 1, num_products + num_resources + 1))

    # Fill the tableau with constraints
    for i in range(num_resources):
        tableau[i, :num_products] = resource_requirements[i]
        tableau[i, num_products + i] = 1  # Slack variable
        tableau[i, -1] = capacity[i]      # RHS (capacity)

    # Objective function row (profit)
    tableau[-1, :num_products] = -np.array(profit)  # Negative for maximization

    # Solve using Simplex method
    simplex(tableau)

if __name__ == "__main__":
    main()

Sablon:Hunl

Szimplex algoritmus

Tartalomjegyzék

Alapvető fogalmak

Működési elv

Előnyök és Hátrányok

Alkalmazások

Python Implementációja - Szimplex Algoritmus

Python Implementáció

Magyarázat

Eredmény

Kimenet

Pszeudokód

C++

Python

Navigációs menü

Szimplex algoritmus

Alapvető fogalmak

Működési elv

Előnyök és Hátrányok

Alkalmazások

Python Implementációja - Szimplex Algoritmus

Python Implementáció

Magyarázat

Eredmény

Kimenet

Pszeudokód

C++

Python

Navigációs menü

Keresés