Direkt zum Inhalt

lineare Optimierung

Definition

Teilgebiet des Operations Research (OR), das sich im Wesentlichen mit dem theoretischen Hintergrund von mathematischen Optimierungssystemen mit zugehörigen Rechenverfahren sowie mit dem Einsatz derartiger Systeme zur Unterstützung ökonomischer Entscheidungsprozesse befasst.

GEPRÜFTES WISSEN
Über 200 Experten aus Wissenschaft und Praxis.
Mehr als 25.000 Stichwörter kostenlos Online.
Das Original: Gabler Wirtschaftslexikon

zuletzt besuchte Definitionen...

    Ausführliche Definition

    Inhaltsverzeichnis

    1. Allgemein
    2. Grundlegende Fragestellungen
    3. Spezielle Strukturen
    4. Erweiterungen
    5. Ökonomische Anwendung

    lineare Planungsrechnung, lineare Programmierung, Linear Programming.

    Allgemein

    1. Begriff: Teilgebiet des Operations Research (OR), das sich mit dem theoretischen Hintergrund, der Modellierung mit und der Lösung von mathematischen Optimierungssystemen der Form

    befasst. In dem linearen Optimierungsproblem (1)-(3) gehören die Parameter c1, c2, ... ,cn, a11, a12, ... , amn, b1, b2, ... , bm zur Zielfunktion, Koeffizientenmatrix bzw. "rechten Seite"; die Variablen x1, x2, ..., xn sind so zu bestimmen, dass sämtliche Restriktionen von (2) erfüllt sind, und die Zielfunktion (1) maximiert oder minimiert wird.

    Die Lösungsmenge beschreibt ein Polyeder. Jeder Lösung aus dieser Lösungsmenge ist durch die Zielfunktion eine Zahl x0 (Zielfunktionswert) zugeordnet, die in Verbindung mit einer der Vorschriften von (3) (Zielvorschrift) eine Beurteilung der Güte der betreffenden Lösung erlaubt. Die Zielvorschrift x0 → Max! besagt dabei, dass eine Lösung mit einem größeren Zielfunktionswert besser ist als jede andere Lösung mit einem kleineren Zielfunktionswert. Eine solche Lösung nennt man optimal.

    Der Begriff linear erklärt sich dadurch, dass die Zielfunktion (1) und sämtliche Restriktionen (2) linear sind (lineare Zielfunktion, lineare Restriktionen).

    Es ist bekannt, dass für ein lineares Optimierungsproblem genau eine der drei Alternativen gilt: (a) das Problem ist unbeschränkt, d.h. zu jeder zulässigen Lösung findet man stets eine zulässige Lösung mit besserem Zielfunktionswert, oder (b) das Problem ist unzuläassig, d.h. es existiert überhaupt keine Lösung, die alle Restriktionen erfüllt, oder (c) es existiert eine optimale Lösung mit endlichem Zielfunktionswert. Im Fall (c) wird der optimale Zielfunktionswert in einer Ecke des Lösungspolyeders angenommen, von denen es nur endlich viele gibt und was das sog. Simplexverfahren nahe legt.

    Grundlegende Fragestellungen

    1. Optimale Lösung: Im Zusammenhang mit linearen Optimierungsproblemen drängt sich die Frage auf, welche Lösung von (2) den durch (1) definierten Zielwert x0 maximiert (oder minimiert) bzw. wie man ggf. erkennt, dass eine solche optimale Lösung nicht existiert. Zur Beantwortung derartiger Fragen wurden eine ganze Reihe von Verfahren (Simplexmethode, Innere-Punkte-Verfahren, Ellipsoid-Methode) entwickelt und in entsprechende Standardsoftware eingebettet, die geeignet ist, auch sehr große Probleme der Praxis (d.h. Probleme mit vielen Variablen und Restriktionen) zu lösen.

    2. Beim Einsatz linearer Optimierungsprobleme in der Praxis besteht häufig Ungewissheit über die tatsächlichen numerischen Werte der Koeffizienten c1, ..., cn, a11, ..., amn, b1, ..., bm; z.T. ist sogar unklar, ob bestimmte Restriktionen von (2) überhaupt auftreten. Wie man im Hinblick auf derartige Situationen – ausgehend von einer ersten optimalen Lösung – auf einem möglichst einfachen Wege Alternativrechnungen (postoptimale Rechnungen) durchführen kann, ist eine weitere Problemstellung.

    3. Vor dem gleichen Hintergrund untersucht man im Rahmen von Sensitivitätsanalysen, wie sich bestimmte Koeffizienten (v.a. die Koeffizienten c1, ..., cn der Zielfunktion (1) bzw. die rechten Seiten b1, ..., bm der Restriktionen (2)) ändern dürfen, ohne dass eine gefundene optimale Lösung (bzw. eine gefundene kanonische Form des Optimierungssystems) die Eigenschaft der Optimalität verliert.

    4. Die parametrische lineare Optimierung befasst sich mit der noch erweiterten Fragestellung, welche optimalen Lösungen sich jeweils ergeben, wenn gewisse Koeffizienten (Koeffizienten der Zielfunktion und/oder die rechten Seiten der Restriktionen) in Abhängigkeit von einem oder mehreren Parametern schwanken können.

    5. Die Dualitätstheorie der linearen Optimierung untersucht den Zusammenhang zwischen gewissen Paaren von linearen Optimierungssystemen. Ihre Erkenntnisse sind für die Entwicklung von Rechenverfahren von Bedeutung.

    6. Die bei Anwendung in der Praxis vorkommenden linearen Optimierungssysteme sind i.d.R. sehr groß (Millionen Variablen, hundertausende Restriktionen), lassen sich aber i.A. relativ schnell optimal lösen. 

    Spezielle Strukturen

    Optimierungssysteme der Praxis zeichnen sich i.d.R. nicht nur durch dünn besetzte Koeffizientenmatrizen aus (d.h. nur verhältnismäßig wenige von null verschiedene Koeffizienten), diese sind außerdem oft nach einem gewissen Schema angeordnet, z.B. weil nicht alle Variablen in allen Restriktionen auftauchen. Derartige speziell strukturierte Systeme ergeben sich etwa bei der mathematischen Formulierung von Transportproblemen und Zuordnungsproblemen, von Wege- und Flussproblemen in Graphen (Netzplantechnik). Sie lassen sich mit traditionellen Simplexmethoden lösen, daneben gibt es aber Lösungsverfahren, die durch eine Ausnutzung der jeweiligen speziellen Koeffizientenstruktur erhebliche Vorteile in Bezug auf Rechenzeit und Speicherbedarf erzielen.

    Erweiterungen

    Durch bestimmte Umformungen und Techniken lassen sich die Methoden der linearen Optimierung z.T. auch zur Untersuchung von Fragen über solche Optimierungssysteme einsetzen, deren Struktur nur unvollständig mit der des Systems ((1), (2)) übereinstimmt:

    1. Gewisse (d.h. mind. eine, möglicherweise aber auch alle) Variablen dürfen nur ganze Zahlen (ganzzahliges Optimierungsproblem) bzw. nur die Werte Null oder Eins annehmen (binäres Optimierungsproblem).

    2. Gewisse Probleme der nicht-linearen Optimierung lassen sich ebenfalls mit linearen bzw. geringfügig modifizierten linearen Methoden lösen. Hierzu gehört u.a. die Bestimmung von optimalen Lösungen für quadratische Optimierungsprobleme und bestimmte separable Optimierungsprobleme.

    3. Im Rahmen der linearen Optimierung bei mehrfacher Zielsetzung stehen solche linearen Optimierungssysteme im Mittelpunkt, bei denen den Lösungen des Restriktionssystems (2) anhand verschiedener Zielfunktionen gleichzeitig mehrere Zielwerte zugeordnet sind. Nur in ganz seltenen Ausnahmefällen existiert jetzt noch eine Lösung, die im Hinblick auf alle Zielfunktionen und -vorschriften gleichzeitig optimal ist. Die für diese Optimierungssysteme entwickelten Verfahren bezwecken deshalb nicht die Ableitung einer in diesem Sinn idealen Lösung, sondern es geht vielmehr um die Ableitung von allen oder einigen effizienten Lösungen bzw. bei interaktiven Verfahren um die Ermittlung einer für den Entscheidungsträger akzeptablen Kompromisslösung.

    Ökonomische Anwendung

    Von allen Methoden des Operations Research haben diejenigen der linearen Optimierung (neben denen der Netzplantechnik) die weiteste Verbreitung in der ökonomischen Praxis gefunden und sich bewährt. Empirischen Untersuchungen zufolge liegen ihre Einsatzschwerpunkte in der Grundstoff-, der chemischen, der Eisen- und Stahl- sowie der Nahrungs- und Genussmittelindustrie. Bez. der betrieblichen Funktionsbereiche sind in erster Linie Anwendungen im Produktionsbereich (zur Lösung von Problemen der Produktionsprogrammplanung, Produktionssteuerung und Zuschnittplanung), im Absatzbereich (Transportproblem), in der Lagerhaltung (Bestimmung optimaler Lagerbestände) sowie im Beschaffungsbereich (Transportproblem, Mischungsproblem, Bestellmengenproblem) anzuführen.

    In stärkerem Maße setzen sich schließlich auch integrierte Modelle zur simultanen Planung verschiedener Funktionsbereiche (Produktions- und Absatzbereichs) durch.

    zuletzt besuchte Definitionen...

      Mindmap lineare Optimierung Quelle: https://wirtschaftslexikon.gabler.de/definition/lineare-optimierung-39312 node39312 lineare Optimierung node46854 Operations Research (OR) node39312->node46854 node46645 Produktionstheorie node50044 Transportproblem node36931 mathematisches Optimierungsproblem node36931->node39312 node36931->node50044 node36386 Extremwert node33875 Extremwertbestimmung node36386->node33875 node33875->node39312 node41013 lineare Aktivitätsanalyse node28725 Aktivität node31300 Aktivitätsanalyse node31300->node39312 node31300->node46645 node31300->node41013 node31300->node28725 node40139 Netzplantechnik node46854->node40139 node49155 Verbrauchsfunktion node30244 Betriebsmodell node30244->node39312 node30244->node49155 node47840 Warteschlangentheorie node47840->node46854 node48102 vollständige Enumeration node48102->node46854 node35403 Ersatzprobleme node35403->node46854 node40139->node39312 node40463 mathematische Optimierung node40463->node36931
      Mindmap lineare Optimierung Quelle: https://wirtschaftslexikon.gabler.de/definition/lineare-optimierung-39312 node39312 lineare Optimierung node46854 Operations Research (OR) node39312->node46854 node30244 Betriebsmodell node30244->node39312 node31300 Aktivitätsanalyse node31300->node39312 node33875 Extremwertbestimmung node33875->node39312 node36931 mathematisches Optimierungsproblem node36931->node39312

      News SpringerProfessional.de

      • Exportentwicklung Werkzeugmaschinen

        Ein aktueller Quest Report verbindet Exportmärkte und Durchschnittswerte von Werkzeugmaschinen in Euro und die Wirkung auf die Exporte nach China seit 2008. Steigende Durchschnittswerte von Werkzeugmaschinen gehen demnach mit rückläufigen Exporten nach China einher.

      • Banken genießen großes Vertrauen ihrer Kunden

        72 Prozent der Bankkunden in Deutschland gehen davon aus, dass Kreditinstitute mit ihren persönlichen Daten sorgsam umgehen. Keine andere Branche genießt einer aktuellen Umfrage zufolge höheres Vertrauen.

      • Neue Aufgaben für die Zentrale der Zukunft

        Unternehmen müssen agil und innovativ sein. Das althergebrachte Headquarter, von dem aus alles zentral gesteuert werden soll, scheint dazu nicht passen zu wollen. Muss die Unternehmenszentrale neu erfunden werden? 

      • So geht erfolgreiches Lead Nurturing im B2B-Segment

        Wenn nicht nur Leads, sondern in Folge auch Käufer generiert werden, ist von Lead Nurturing die Rede. Im B2B-Bereich müssen E-Mail-Marketer dafür besonders strategische sowie kontinuierliche Beziehungsarbeit leisten.

      • Globales E-Invoicing ist Herausforderung für Unternehmen

        Unternehmen sind aufgrund staatlicher Vorgaben zunehmend dazu verpflichtet, ihre Rechnungen elektronisch zu erstellen. Doch in jedem Land gelten andere rechtliche Regelungen. Entsprechend komplex gestalten sich die Prozesse. Erster Teil des Gastbeitrags.

      • Auf dem Rechtsweg ins Verderben

        Wer seinen Markt als Eigentum betrachtet und Neueinsteiger juristisch bekämpfen will, kann nur verlieren, meint Springer-Autor und Zukunftsmanager Heino Hilbig. Denn die Klage eines Taxifahrers gegen Moia wird neue Verkehrskonzepte nicht verhindern. 

      • Mit Location Based Marketing auf Neukundenfang

        Deutsche Marketing-Manager sehen in standortbasierter Werbung die Brücke, um Konsumenten online wie offline anzusprechen. Vor allem für die Neukundengewinnung setzen sie auf das Marketinginstrument.

      • Wie der Arbeitsplatz von morgen aussehen wird

        Während der Industrialisierung wanderte die Arbeit aus dem Haushalt in die Fabrik. Heute klopft sie wieder an die Haustür. Die Möglichkeit zu mehr zeitlicher und örtlicher Flexibilität, beispielsweise zur Arbeit im Homeoffice, macht vor keiner Branche mehr halt.

      • Java und JavaScript sind die beliebtesten Programmiersprachen

        Die meisten Softwareingenieure setzen auf Java und JavaScript, wenn es um die Entwicklung von Unternehmensanwendungen geht. Die angeblichen "In"-Programmiersprachen Python & Co. liegen in der Beliebtheitsskala teils weit abgeschlagen hinter den Klassikern.

      • Diese digitalen Marken sind top

        Digitale Dienste dominieren immer stärker die Markenwelt. In den Top 25 der relevantesten Marken Deutschlands machen sich analoge Marken eher rar.

      Autoren der Definition und Ihre Literaturhinweise/ Weblinks

      Prof. Dr. Marco Lübbecke
      RWTH Aachen, Lehrstuhl für Operations Research
      Lehrstuhlinhaber

      Literaturhinweise SpringerProfessional.de

      Springer Professional - Die Flatrate für Fachzeitschriften und Bücher
      Dieses Kapitel bietet eine Einführung in die Optimierung linearer Zielfunktionen unter Nebenbedingungen. Aufbauend auf einer fundierten Einführung in Notation und grafische Interpretierbarkeit linearer Probleme wird mit der Simplex-Methode nach …
      In der Analysis behandelte Optimierungsaufgaben, also die Suche nach Maxima oder Minima einer Funktion unter Nebenbedingungen, fordern die Einhaltung von Gleichheiten in Nebenbedingungen, wie etwa bei der Lagrange-Multiplikatorregel. Es ist im …
      Die lineare Optimierung (Synonyme: lineare Planungsrechnung, lineare Programmierung) (operation research) ist in den letzten Jahrzehnten, auch aufgrund der rasanten Entwicklung im Computerbereich, zu einem Standardverfahren in der …

      Sachgebiete