Lineare Programmierung bezieht sich auf optimale Programmiertechniken. Lineares Programmierkonzept. Arten von linearen Programmierproblemen

Lineare Programmierung entstand in den 40er bis 50er Jahren als eigenständiger Zweig der angewandten Mathematik. XX Jahrhundert Dank der Arbeiten des sowjetischen Wissenschaftlers, Nobelpreisträgers L.V. Kantorowitsch. 1939 veröffentlichte er das Werk "Mathematische Methoden der Organisation und Planung der Produktion", in dem er mit Hilfe der Mathematik wirtschaftliche Probleme über die beste Beladung von Maschinen, das Schneiden von Materialien mit den niedrigsten Kosten, die Verteilung der Güter auf mehrere Verkehrsträger, und andere, die eine Methode zur Auflösung von Faktoren vorschlagen 8 ...

L. V. Kantorowitsch war der erste, der so weit verbreitete ökonomische und mathematische Konzepte wie optimale Planung, optimale Ressourcenallokation, objektiv festgelegte Schätzungen formulierte und zahlreiche Bereiche der Wirtschaftswissenschaften aufzeigte, in denen sie angewendet werden können.

Das Konzept der linearen Programmierung wurde von dem amerikanischen Mathematiker D. Danzig eingeführt, der 1949 einen Algorithmus zur Lösung eines linearen Programmierproblems vorschlug, der als "Simplex-Methode" bezeichnet wird.

Die mathematische Programmierung, zu der auch die lineare Programmierung gehört, gehört derzeit zu den Bereichen des Operations Research. Je nach Art der zu lösenden Probleme werden darin solche Bereiche unterschieden in linear, nichtlinear, diskret, dynamische Programmierung ua Der Begriff "Programmierung" wurde aufgrund der Tatsache eingeführt, dass unbekannte Variablen, die gerade dabei sind, ein Problem zu lösen, normalerweise das Programm oder den Arbeitsplan eines Wirtschaftsobjekts bestimmen.

In der klassischen mathematischen Analysis wird die allgemeine Formulierung des Problems der Bestimmung eines bedingten Extremums untersucht. Aufgrund der Entwicklung der Industrieproduktion, des Verkehrs, des agroindustriellen Komplexes und des Bankensektors erwiesen sich die traditionellen Ergebnisse der mathematischen Analyse jedoch als unzureichend. Die Bedürfnisse der Praxis und die Entwicklung der Computertechnik haben dazu geführt, optimale Lösungen bei der Analyse komplexer Wirtschaftssysteme zu finden.

Das wichtigste Werkzeug zur Lösung solcher Probleme ist die mathematische Modellierung. Gleichzeitig wird zuerst ein einfaches Modell erstellt, dann wird seine Untersuchung durchgeführt, die es ermöglicht zu verstehen, welche der integrierenden Eigenschaften des Objekts nicht vom formalen Schema erfasst werden Modells ist seine größere Realitätsnähe gewährleistet. In vielen Fällen ist die erste Annäherung an die Realität ein Modell, bei dem alle Abhängigkeiten zwischen den den Zustand des Objekts charakterisierenden Variablen linear sind. Die Praxis zeigt, dass eine ausreichende Anzahl von ökonomischen Prozessen durch lineare Modelle hinreichend beschrieben wird. Folglich spielt die lineare Programmierung als eine Vorrichtung, die es ermöglicht, ein bedingtes Extremum auf einer durch lineare Gleichungen und Ungleichungen gegebenen Menge zu finden, eine wichtige Rolle bei der Analyse dieser Prozesse.

Die lineare Programmierung hat eine breite Entwicklung erfahren, da festgestellt wurde, dass eine Reihe von Planungs- und Steuerungsproblemen in Form von linearen Programmierproblemen formuliert werden können, für deren Lösung es wirksame Methoden gibt. Etwa 80–85 % aller in der Praxis gelösten Optimierungsprobleme beziehen sich Experten zufolge auf Probleme der linearen Programmierung.

Der geschaffene mathematische Apparat, kombiniert mit Computerprogrammen, die arbeitsintensive Berechnungen durchführen, ermöglicht eine breite Anwendung linearer Programmiermodelle in der Wirtschaftswissenschaft und -praxis.

Definition 1 9 . Lineare Programmierung (LP) ist ein Gebiet der mathematischen Programmierung, das ein Zweig der Mathematik ist und Methoden zum Finden von Extremwerten (Maximum und Minimum) einer linearen Funktion einer endlichen Anzahl von Variablen untersucht, deren Unbekannten lineare Beschränkungen auferlegt werden .

Diese lineare Funktion wird als Ziel bezeichnet, und die Nebenbedingungen, die quantitative Beziehungen zwischen Variablen darstellen, die die Bedingungen und Anforderungen des ökonomischen Problems ausdrücken und mathematisch in Form von Gleichungen oder Ungleichungen geschrieben sind, werden als Nebenbedingungen bezeichnet.

Ein breites Themenspektrum der Planung wirtschaftlicher Prozesse wird auf Probleme der linearen Programmierung reduziert, bei denen es um das Finden der besten (optimalen) Lösung geht.

Das allgemeine lineare Programmierproblem (LPP) besteht darin, den Extremwert (Maximum oder Minimum) einer linearen Funktion zu finden, die als Ziel 10 bezeichnet wird:

von n Variablen x 1 , x 2 , …, NS n mit auferlegten Funktionseinschränkungen:

(3.2)

und direkte Nebenbedingungen (Erfordernis der Nicht-Negativität von Variablen)

, (3.3)

wo ein ij , B ich , C J- konstante Werte angegeben.

Im Restriktionssystem (3.2) können die Zeichen "kleiner gleich", "gleich", "größer gleich" gleichzeitig vorkommen.

ZLP hat in kürzerer Schreibweise die Form:

,

mit Einschränkungen:

;

.

Vektor ` NS = (x 1 , x 2 , …, NS n), deren Komponenten die funktionalen und direkten Randbedingungen des Problems erfüllen, heißen planen(oder akzeptable Entscheidung) ZLP.

Alle zulässigen Lösungen bilden Domain lineare Programmierprobleme, oder Palette an praktikablen Lösungen (ODR). Eine zulässige Lösung, die das Maximum oder Minimum der Zielfunktion liefert F(`x), heißt optimaler Plan des Problems und wird mit . bezeichnet F(`x * ), wo ` NS * =(x 1 * , x 2 * , …, NS n * ).

Eine andere Form des Schreibens von LPP:

,

wo F(`x * ) ist der maximale (minimale) Wert F(MIT, NS) alle im Set enthaltenen Lösungen übernommen mögliche Lösungen NS .

Definition 2 11 ... Der mathematische Ausdruck der Zielfunktion und ihrer Grenzen wird als mathematisches Modell des ökonomischen Problems bezeichnet.

Um ein mathematisches Modell zu erstellen, müssen Sie:

1) benennen Sie Variablen;

2) eine Zielfunktion basierend auf dem Ziel der Aufgabe zusammenstellen;

3) Notieren Sie das Beschränkungssystem unter Berücksichtigung der Indikatoren für den Zustand des Problems und ihrer quantitativen Muster.

2. Das Konzept der linearen Programmierung. Arten von linearen Programmierproblemen

Lineare Programmierung (LP) ist einer der ersten und am gründlichsten untersuchten Bereiche der mathematischen Programmierung. Es war die lineare Programmierung, aus der sich die eigentliche Disziplin der "mathematischen Programmierung" zu entwickeln begann. Der Begriff „Programmieren“ im Namen der Disziplin hat nichts mit dem Begriff „Programmieren (also ein Programm schreiben) für einen Computer“ zu tun, da Die Disziplin der "linearen Programmierung" entstand noch vor der Zeit, als Computer weit verbreitet waren, um mathematische, technische, wirtschaftliche und andere Probleme zu lösen.

Der Begriff „Linear Programming“ entstand aus einer ungenauen Übersetzung des englischen „Linear Programming“. Eine der Bedeutungen des Wortes "Programmierung" ist Pläne machen, planen. Daher wäre die korrekte Übersetzung des englischen „linear Programming“ nicht „lineare Programmierung“, sondern „lineare Planung“, was den Inhalt der Disziplin genauer widerspiegelt. Die Begriffe lineare Programmierung, nichtlineare Programmierung, mathematische Programmierung usw. in unserer Literatur haben sich durchgesetzt und werden daher erhalten bleiben.

So entstand nach dem Zweiten Weltkrieg die lineare Programmierung und begann sich schnell zu entwickeln, und zog die Aufmerksamkeit von Mathematikern, Ökonomen und Ingenieuren aufgrund der Möglichkeit einer breiten praktischen Anwendung sowie der mathematischen Harmonie auf sich.

Wir können sagen, dass die lineare Programmierung für die Lösung mathematischer Modelle dieser Prozesse und Systeme anwendbar ist, die auf der Hypothese einer linearen Darstellung der realen Welt basieren können.

Lineare Programmierung wird verwendet, um wirtschaftliche Probleme zu lösen, beispielsweise in der Verwaltung und Produktionsplanung; bei den Aufgaben, die optimale Platzierung von Ausrüstung auf Schiffen zu bestimmen, in Werkstätten; bei den Aufgaben der Ermittlung des optimalen Plans für den Warentransport (Transportproblem); bei Problemen der optimalen Personalverteilung etc.

Das Problem der linearen Programmierung (LP) besteht, wie bereits aus dem oben Gesagten klar wird, darin, das Minimum (oder Maximum) einer linearen Funktion unter linearen Randbedingungen zu finden.

Es gibt mehrere Methoden zur Lösung von LP-Problemen. In diesem Beitrag werden einige von ihnen betrachtet, insbesondere:

Grafische Methode zur Lösung des LP-Problems;

Simplex-Methode;

Lösung des LP-Problems mit Hilfe eines Excel-Tabellenkalkulationsprozessors;

3. Das Konzept der nichtlinearen Programmierung

Bei den meisten technischen Problemen kann die Konstruktion eines mathematischen Modells nicht auf ein lineares Programmierproblem reduziert werden.

Mathematische Modelle in den Entwurfsproblemen realer Objekte oder technologischer Prozesse sollen reale physikalische und in der Regel in ihnen vorkommende nichtlineare Prozesse widerspiegeln. Die Variablen dieser Objekte oder Prozesse sind durch physikalische nichtlineare Gesetze wie die Gesetze der Massen- oder Energieerhaltung miteinander verbunden. Sie werden durch die Grenzbereiche begrenzt, die die physikalische Machbarkeit eines bestimmten Objekts oder Prozesses sicherstellen. Daher sind die meisten mathematischen Programmierprobleme, die in Forschungsprojekten und bei Entwurfsproblemen auftreten, Probleme der nichtlinearen Programmierung (NP).

In dieser Arbeit betrachten wir eine solche Methode zur Lösung von NP-Problemen als die Methode der Lagrange-Multiplikatoren.

Mit der Lagrange-Multiplikatormethode können Sie das Maximum (oder Minimum) einer Funktion unter Gleichheitsbeschränkungen ermitteln. Die Hauptidee der Methode besteht darin, vom Problem des bedingten Extremums zum Problem des Auffindens des unbedingten Extremums einer bestimmten konstruierten Lagrange-Funktion überzugehen.

4. Dynamische Programmierung

Dynamische Programmierung ist ein mathematisches Gerät, mit dem Sie schnell die optimale Lösung finden können, wenn die analysierte Situation keine Unsicherheitsfaktoren enthält, aber es gibt große Menge Verhaltensweisen, die unterschiedliche Ergebnisse bringen, unter denen das Beste ausgewählt werden muss. Die dynamische Programmierung nähert sich der Lösung einer bestimmten Klasse von Problemen, indem sie sie in Teile, kleine und weniger komplexe Probleme zerlegt. Im Prinzip lassen sich solche Probleme lösen, indem man alle aufzählt Möglichkeiten und die besten unter ihnen auszuwählen, aber oft ist eine solche Aufzählung sehr schwierig. In diesen Fällen kann der Prozess der optimalen Entscheidung in Schritte (Stufen) zerlegt und mit der Methode der dynamischen Programmierung untersucht werden.

Die Lösung von Problemen durch Methoden der dynamischen Programmierung erfolgt auf der Grundlage des von R.E. Bellman formulierten Optimalitätsprinzips: optimales Verhalten hat die Eigenschaft, dass egal was Originalzustand Systemen und der Anfangsentscheidung sollte die Folgeentscheidung das optimale Verhalten in Bezug auf den als Ergebnis der Anfangsentscheidung erhaltenen Zustand bestimmen.

Daher sollte die Planung jedes Schrittes unter Berücksichtigung des Gesamtnutzens erfolgen, der am Ende des gesamten Prozesses erzielt wird, wodurch das Endergebnis gemäß dem ausgewählten Kriterium optimiert werden kann.

Die dynamische Programmierung ist jedoch keine universelle Lösungsmethode. Fast jedes mit dieser Methode gelöste Problem zeichnet sich durch seine eigenen Eigenschaften aus und erfordert die Suche nach dem akzeptablesten Methodensatz für seine Lösung. Darüber hinaus führen die großen Volumina und der Arbeitsaufwand bei der Lösung von mehrstufigen Problemen mit vielen Zuständen dazu, dass niedrigdimensionale Probleme ausgewählt oder komprimierte Informationen verwendet werden müssen.

Dynamische Programmierung wird verwendet, um solche Probleme zu lösen, wie: Verteilung knapper Kapitalinvestitionen auf neue Nutzungsbereiche; Entwicklung von Regeln für das Management von Nachfrage und Lagerbeständen; Ausarbeitung Kalenderpläne laufende und größere Reparaturen von Geräten und deren Austausch; Suche nach kürzesten Entfernungen im Verkehrsnetz usw.

Der Optimierungsprozess sei in n Schritte unterteilt. Bei jedem Schritt müssen zwei Arten von Variablen definiert werden - die Zustandsvariable S und die Steuervariable X. Die Variable S bestimmt, in welchen Zuständen sich das System befinden kann dieses k-th Schritt. Abhängig von S kann man in diesem Schritt einige Kontrollen anwenden, die durch die Variable X gekennzeichnet sind. Die Anwendung der Kontrolle X im k-ten Schritt liefert ein Ergebnis Wk (S, Xk) und überführt das System in einen neuen Zustand S "(S , Xk) Für jeden möglichen Zustand in der k-ten Stufe wird unter allen möglichen Steuerungen eine optimale Steuerung X * k so gewählt, dass das Ergebnis, das in Schritten von k-te zu n-ter erreicht wird, optimal ausfällt dieses Ergebnis wird Bellman-Funktion Fk (S) genannt und hängt von der Schrittzahl k und dem Zustand des Systems S ab.

Alle Lösungen des Problems sind in zwei Phasen unterteilt. In der ersten Stufe, die als bedingte Optimierung bezeichnet wird, werden die Bellman-Funktion und optimale Kontrollen für alle möglichen Zustände in jedem Schritt, beginnend mit dem letzten, gefunden.

Nachdem die Bellman-Funktion und die entsprechenden optimalen Kontrollen für alle Schritte vom n-ten bis zum ersten gefunden wurden, wird die zweite Stufe der Problemlösung durchgeführt, die als uneingeschränkte Optimierung bezeichnet wird.

V Gesamtansicht das dynamische Programmierproblem wird wie folgt formuliert: Es ist erforderlich, eine Steuerung X * zu definieren, die das System vom Anfangszustand S0 in den Endzustand Sn überführt, bei dem die Zielfunktion F (S0, X *) die größte (kleinste) ) Wert.

Die Merkmale des mathematischen Modells der dynamischen Programmierung sind wie folgt:

das Optimierungsproblem wird als abschließender mehrstufiger Steuerprozess formuliert;

die Zielfunktion ist additiv und gleich der Summe der Zielfunktionen jedes Schrittes

die Wahl der Steuerung Xk bei jedem Schritt hängt nur vom Zustand des Systems für diesen Schritt Sk-1 ab und hat keinen Einfluss auf die vorherigen Schritte (no Rückmeldung);

der Zustand des Systems Sk nach jedem Regelschritt hängt nur vom vorherigen Zustand des Systems Sk-1 und dieser Regelaktion Xk ab (keine Nachwirkung) und kann in Form der Zustandsgleichung geschrieben werden:

bei jedem Schritt hängt die Steuerung Xk von einer endlichen Anzahl von Steuerungsvariablen ab, und der Zustand des Systems Sk hängt von einer endlichen Anzahl von Variablen ab;

optimale Steuerung X * ist ein Vektor, der durch eine Folge optimaler schrittweiser Steuerungen bestimmt wird:

X * = (X * 1, X * 2, ..., X * k, ..., X * n),

deren Anzahl bestimmt die Anzahl der Schritte in der Aufgabe.

Bedingte Optimierung. Wie oben erwähnt, auf diese Phase die Bellman-Funktion und optimale Steuerungen werden für alle möglichen Zustände bei jedem Schritt gefunden, beginnend mit dem letzten gemäß dem Rückwärts-Sweep-Algorithmus. Auf letzte nth Schritt ist es nicht schwierig, die optimale Steuerung X * n und den Wert der Bellman-Funktion Fn (S) zu finden, da

Fn (S) = max (Wn (S, Xn)),

wobei das Maximum über alle möglichen Werte von Xn gesucht wird.

Weitere Berechnungen werden gemäß der Rekursionsbeziehung durchgeführt, die die Bellman-Funktion in jedem Schritt mit derselben Funktion verbindet, aber im vorherigen Schritt berechnet wurde:

Fk (S) = max (Wk (S, Xk) + Fk + 1 (S "(S, Xk))). (1)

Dieses Maximum (oder Minimum) wird über alle möglichen Werte der Regelgröße X für k und S bestimmt.

Bedingungslose Optimierung. Nachdem die Bellman-Funktion und die entsprechenden optimalen Kontrollen für alle Schritte vom n-ten bis zum ersten gefunden wurden (im ersten Schritt k = 1, ist der Zustand des Systems gleich seinem Anfangszustand S0), die zweite Stufe der Lösung des Problems durchgeführt wird. Im ersten Schritt X1 wird eine optimale Steuerung gefunden, deren Anwendung das System in den Zustand S1 (S, x1 *) bringt, da wir wissen, dass wir mit den Ergebnissen der bedingten Optimierung die optimale Steuerung im zweiten Schritt finden können , und so weiter bis zum letzten n-ten Schritt.

Labor arbeit# 1 (Problem der linearen Programmierung)

Führen Sie für eine gegebene mathematische Formulierung des LP-Problems unter der zusätzlichen Bedingung der Nicht-Negativität der Variablen die folgenden Aktionen aus:

Lösen Sie das Problem grafisch;

Bringen Sie die Aufgabe in die kanonische Form der Notation;

Erstellen Sie eine Simplex-Tabelle;

Das Problem lösen Simplex-Methode von Hand oder mit einem Computer;

Inszenierung durchführen Doppelaufgabe LP;

Besorgen Sie sich eine Lösung des dualen Problems aus der zuvor erhaltenen Simplex-Tabelle und analysieren Sie die erhaltenen Ergebnisse;

Überprüfen Sie die Lösungsergebnisse in einer Excel-Tabelle;

Erstellen Sie einen Bericht, der die Ergebnisse für jedes Element zusammenfasst.

Grafische Methode. Um das Lösungspolygon zu konstruieren, transformieren wir das ursprüngliche System

, wir bekommen

Wir stellen die Grenzlinien dar.

Lineare Funktion F = f (x) ist die Geradengleichung c1x1 + c2x2 = const. Erstellen wir einen Graphen der Zielfunktion mit f (x) = 0. Um eine Gerade 3x1 + 4x2 = 0 zu bilden, konstruieren wir den Radiusvektor N = (3; 4) und ziehen durch den Punkt 0 eine Gerade senkrecht dazu. Die konstruierte Gerade F = 0 wird parallel zu sich selbst in Richtung des Vektors N verschoben.

Aus Abbildung 1 folgt, dass diese Gerade die Stütze bezüglich des konstruierten Lösungspolygons am Punkt B wird, wo die Funktion F ihren maximalen Wert annimmt. Punkt B liegt im Schnittpunkt der Geraden 0,7x1 + 2x2 ≤ 13,1 und 2,3x1 + 2x2 = 23 / Um seine Koordinaten zu bestimmen, lösen wir das Gleichungssystem:

Optimaler Plan des Problems: х1 = 6,187; x2 = 4,38, wenn wir die Werte von x1 und x2 in die Zielfunktion einsetzen, erhalten wir Fmax = 3 * 6,187 + 4 * 4,38 = 36,08.

Um den maximalen Gewinn von 36,06 USD zu erzielen, müssen Sie also die Produktion von 6 Einheiten planen. Produkte P1 und 4 Einheiten. P2-Produkte.

Die kanonische Form des LP-Problems. Schreiben wir das Ressourcenallokationsproblem in kanonischer Form auf. Addiert man zu dem ursprünglichen System von Beschränkungen nicht negative Variablen x3 0, x4 ≥ 0, x5 ≥ 0, so erhalten wir:

LP-Simplex-Tabelle. Bei Basisvariablen (x3, x4, x5) sieht die anfängliche Simplex-Tabelle wie folgt aus:

Tabelle 1.

Er entspricht bereits dem Basisplan x (0) = T (Spalte der freien Mitglieder).

Diese Methode ist eine Methode zur gezielten Aufzählung von Unterstützungslösungen eines linearen Programmierproblems. Es erlaubt in endlich vielen Schritten entweder die optimale Lösung zu finden oder festzustellen, dass es keine optimale Lösung gibt.

1. Geben Sie einen Weg an, um die optimale Support-Lösung zu finden
2. Geben Sie die Übergangsmethode von einer Trägerlösung zu einer anderen an, bei der der Wert der Zielfunktion näher am optimalen liegt, d. h. einen Weg zur Verbesserung der Supportlösung aufzeigen
3. Legen Sie Kriterien fest, die es Ihnen ermöglichen, die Suche nach Unterstützungslösungen zur optimalen Lösung rechtzeitig zu stoppen oder der Schlussfolgerung über das Fehlen einer optimalen Lösung zu folgen.

Algorithmus der Simplex-Methode zur Lösung linearer Programmierprobleme

1. Bringen Sie das Problem in die kanonische Form
2. Finden Sie die anfängliche Supportlösung mit einer "Einheitenbasis" (wenn es keine Supportlösung gibt, hat das Problem keine Lösung aufgrund der Inkompatibilität des Systems der Einschränkungen)
3. Berechnen Sie die Schätzungen der Vektorentwicklungen in der Basis der Stützlösung und füllen Sie die Tabelle der Simplexmethode aus
4. Ist das Kriterium für die Eindeutigkeit der optimalen Lösung erfüllt, dann endet die Lösung des Problems
5. Ist die Bedingung für die Existenz einer Menge optimaler Lösungen erfüllt, so werden durch einfache Aufzählung alle optimalen Lösungen gefunden

Ein Beispiel für die Lösung eines Problems mit der Simplex-Methode

Lösen Sie das Problem mit der Simplex-Methode:

Lösung:

Wir bringen das Problem in eine kanonische Form.

Dazu führen wir auf der linken Seite der ersten Ungleichungsbedingung eine zusätzliche Variable x 6 mit einem Koeffizienten von +1 ein. Die Variable x 6 ist in der Zielfunktion mit einem Koeffizienten von Null enthalten (dh sie ist nicht enthalten).

Wir bekommen:

Finden Sie die erste Support-Lösung. Dazu werden freie (unaufgelöste) Variablen mit Null x1 = x2 = x3 = 0 gleichgesetzt.

Wir bekommen Referenzlösung X1 = (0,0,0,24,30,6) mit Einheitsbasis B1 = (A4, A5, A6).

Wir berechnen Vektorexpansionsschätzungen Bedingungen auf Basis der Referenzlösung nach der Formel:

k = CbXk - ck

• C b = (c 1, c 2, ..., c m) ist der Koeffizientenvektor der Zielfunktion für die Basisvariablen
• X k = (x 1k, x 2k, ..., x mk) ist der Expansionsvektor des entsprechenden Vektors A k in der Basis der Stützlösung
• C k - Koeffizient der Zielfunktion bei der Variablen x k.

Die Schätzungen der in der Basis enthaltenen Vektoren sind immer Null. Die Stützlösung, die Expansionskoeffizienten und die Abschätzungen der Entwicklungen der Bedingungsvektoren in der Basis der Stützlösung werden in geschrieben Simplex-Tabelle:

Oberhalb der Tabelle sind die Koeffizienten der Zielfunktion zur Vereinfachung der Berechnung von Schätzungen angegeben. Die erste Spalte "B" enthält die Vektoren, die in der Basis der Referenzlösung enthalten sind. Die Schreibreihenfolge dieser Vektoren entspricht der Anzahl der zulässigen Unbekannten in den Beschränkungsgleichungen. In der zweiten Spalte der Tabelle "C b" sind die Koeffizienten der Zielfunktion mit den Basisvariablen in derselben Reihenfolge aufgeführt. Bei korrekter Anordnung der Zielfunktionskoeffizienten in der Spalte "C b" sind die Schätzungen der in der Basis enthaltenen Einheitsvektoren immer gleich Null.

Die letzte Zeile der Tabelle mit Schätzungen Δ k in der Spalte "A 0" zeichnet die Werte der Zielfunktion auf die Referenzlösung Z (X 1) auf.

Die initiale Supportlösung ist nicht optimal, da im Maximumproblem die Abschätzungen Δ 1 = -2, Δ 3 = -9 für die Vektoren А 1 und А 3 negativ sind.

Nach dem Theorem über die Verbesserung der Stützlösung kann, wenn im Maximumproblem mindestens ein Vektor eine negative Schätzung hat, eine neue Stützlösung gefunden werden, auf der der Wert der Zielfunktion größer ist.

Lassen Sie uns bestimmen, welcher der beiden Vektoren zu einem größeren Inkrement der Zielfunktion führt.

Das Inkrement der Zielfunktion ergibt sich aus der Formel:.

Wir berechnen die Werte des Parameters θ 01 für die erste und dritte Spalte mit der Formel:

Wir erhalten θ 01 = 6 mit l = 1, θ 03 = 3 mit l = 1 (Tabelle 26.1).

Das Inkrement der Zielfunktion ermitteln wir, indem wir den ersten Vektor ΔZ 1 = - 6 * (- 2) = 12 in die Basis einführen und den dritten Vektor ΔZ 3 = - 3 * (- 9) = 27.

Für eine schnellere Annäherung an die optimale Lösung ist es daher erforderlich, anstelle des ersten Vektors der Basis A6 den Vektor A3 in die Basis der Stützlösung einzuführen, da das Minimum des Parameters θ 03 in der ersten Zeile erreicht wird (l = 1).

Wir führen die Jordan-Transformation mit dem Element X13 = 2 durch, wir erhalten die zweite Stützlösung X2 = (0,0,3,21,42,0) mit der Basis B2 = (A3, A4, A5). (Tabelle 26.2)

Diese Lösung ist nicht optimal, da der Vektor A2 eine negative Schätzung Δ2 = - 6 hat. Um die Lösung zu verbessern, ist es notwendig, den Vektor A2 in die Basis der Stützlösung einzuführen.

Bestimmen Sie die Nummer des von der Basis abgeleiteten Vektors. Berechnen Sie dazu den Parameter θ 02 für die zweite Spalte, er ist gleich 7 für l = 2. Daher leiten wir aus der Basis den zweiten Basisvektor A4 ab. Führen wir die Jordan-Transformation mit dem Element x 22 = 3 durch, erhalten wir die dritte Referenzlösung X3 = (0.7,10,0.63.0) B2 = (A3, A2, A5) (Tabelle 26.3).

Diese Lösung ist die einzig optimale, da für alle Vektoren, die nicht in der Basis der Schätzung enthalten sind, positiv

1 = 7/2, 4 = 2, Δ 6 = 7/2.

Antworten: max Z (X) = 201 bei X = (0.7,10,0.63).

Lineare Programmiermethode in der Wirtschaftsanalyse

Lineare Programmiermethode ermöglicht es, die optimale wirtschaftliche Lösung unter Bedingungen strenger Einschränkungen in Bezug auf die in der Produktion verwendeten Ressourcen (Sachanlagen, Materialien, Arbeitsressourcen) zu begründen. Die Verwendung dieser Methode in der Wirtschaftsanalyse ermöglicht es Ihnen, Probleme zu lösen, die hauptsächlich mit der Planung der Aktivitäten der Organisation zusammenhängen. Diese Methode hilft, die optimalen Werte der Produktionsleistung sowie die Richtungen der meisten zu bestimmen effektiver Einsatz der Organisation der Produktionsmittel zur Verfügung stehen.

Mit Hilfe dieser Methode wird die Lösung der sogenannten Extremprobleme durchgeführt, die darin besteht, die Extremwerte, dh die maximalen und minimalen Funktionen variabler Größen, zu finden.

Dieser Zeitraum basiert auf der Lösung des Systems lineare Gleichungen in Fällen, in denen die analysierten Wirtschaftsphänomene durch lineare, streng funktionale Abhängigkeiten verbunden sind. Die Methode der linearen Programmierung wird verwendet, um Variablen beim Vorhandensein bestimmter einschränkender Faktoren zu analysieren.

Die Lösung des sogenannten Transportproblems mit der Methode der linearen Programmierung ist weit verbreitet. Inhalt dieser Aufgabe ist es, die Kosten im Zusammenhang mit dem Betrieb von Fahrzeugen unter den Bedingungen der bestehenden Beschränkungen der Anzahl der Fahrzeuge, ihrer Tragfähigkeit, der Dauer ihres Betriebs zu minimieren, wenn ein maximaler Wartungsbedarf besteht Anzahl der Kunden.

Neben, diese Methode findet breite Anwendung bei der Lösung des Scheduling-Problems. Diese Aufgabe besteht in einer solchen Verteilung der Arbeitszeit des Personals einer bestimmten Organisation, die sowohl für die Mitglieder dieses Personals als auch für die Kunden der Organisation am annehmbarsten wäre.

Diese Aufgabe besteht darin, die Zahl der Kunden zu maximieren, die angesichts der Beschränkungen der Zahl der verfügbaren Mitarbeiter sowie des Arbeitszeitbudgets bedient werden.

Daher ist die lineare Programmierungsmethode bei der Analyse von Platzierung und Verwendung weit verbreitet. verschiedene Typen Ressourcen sowie bei der Planung und Prognose der Aktivitäten von Organisationen.

Dennoch kann die mathematische Programmierung auf solche ökonomischen Phänomene angewendet werden, deren Beziehung nicht linear ist. Dazu können nichtlineare, dynamische und konvexe Programmiermethoden verwendet werden.

Die nichtlineare Programmierung beruht auf der nichtlinearen Natur der Zielfunktion oder der Nebenbedingungen oder auf beidem. Die Formen der Zielfunktion und Ungleichungen von Nebenbedingungen können unter diesen Bedingungen unterschiedlich sein.

Die nichtlineare Programmierung wird in der Wirtschaftsanalyse verwendet, insbesondere wenn die Beziehung zwischen Indikatoren, die die Wirksamkeit der Aktivitäten einer Organisation ausdrücken, und dem Umfang dieser Aktivitäten, der Struktur der Produktionskosten, der Marktbedingungen usw.

Die dynamische Programmierung basiert auf der Konstruktion eines Entscheidungsbaums. Jede Stufe dieses Baums dient als Stufe, um die Konsequenzen der vorherigen Entscheidung zu bestimmen und ineffektive Optionen für diese Entscheidung zu eliminieren. Somit hat die dynamische Programmierung eine mehrstufige, mehrstufige Natur. Diese Art der Programmierung wird in der Wirtschaftsanalyse verwendet, um die besten Optionen für die Entwicklung einer Organisation jetzt und in Zukunft zu finden.

Die konvexe Programmierung ist eine Form der nichtlinearen Programmierung. Diese Art der Programmierung drückt die nichtlineare Natur der Beziehung zwischen den Ergebnissen der Aktivitäten einer Organisation und den dadurch verursachten Kosten aus. Die konvexe (auch konkave) Programmierung analysiert konvex Zielfunktionen und konvexe Zwangssysteme (Punkte akzeptable Werte). Die konvexe Programmierung wird bei der Analyse der Wirtschaftstätigkeit verwendet, um die Kosten zu minimieren, und die konkave Programmierung wird verwendet, um das Einkommen unter den Bedingungen bestehender Beschränkungen der Wirkung von Faktoren zu maximieren, die die analysierten Indikatoren in entgegengesetzter Weise beeinflussen. Folglich werden bei den betrachteten Programmierarten konvexe Zielfunktionen minimiert und konkave maximiert.