Probleme, Lösungen und Anwendungen der linearen Programmierung [mit Beispiel]

Data Science hat viele Anwendungen, eine der bekanntesten unter ihnen ist die Optimierung. Wir alle neigen dazu, uns darauf zu konzentrieren, Dinge zu optimieren. Die Optimierung konzentriert sich darauf, mit den begrenzten Ressourcen, die Ihnen zur Verfügung stehen, die gewünschten Ergebnisse zu erzielen.

Es gibt alle Arten von Optimierungsproblemen, manche sind klein, manche hochkompliziert. Während Sie sie durchgehen, werden Sie eine spezielle Kategorie finden, die als Probleme der linearen Programmierung bezeichnet wird. In diesem Artikel haben wir besprochen, was sie sind und wie Sie daran arbeiten können.

Angenommen, Sie sind ein Obstverkäufer, der entweder Orangen oder Äpfel oder eine bestimmte Kombination aus beidem kaufen kann. Sie haben jedoch nur ein Budget von INR 5.000 und können nur 30 Beutel davon lagern. Jetzt müssen Sie sie so kaufen, dass Sie den höchsten Gewinn erzielen.

Jetzt kostet Sie eine Tüte Orangen 500 INR, während eine Tüte Äpfel 750 INR kostet. Sie können 100 INR mit dem Verkauf einer Tüte Orangen und 200 INR mit dem Verkauf einer Tüte Äpfel verdienen.

Dieses Problem hat verschiedene Möglichkeiten. Sie könnten sich dafür entscheiden, nur Orangen zu kaufen, aber dann hätten Sie nur 10 Beutel in Ihrem Lager und Ihr Gewinn wäre 1000 INR. Ebenso könnten Sie sich dafür entscheiden, nur Äpfel zu kaufen und 1500 INR als Gewinn zu machen. Sie können auch eine Kombination aus beidem kaufen.

Solche Probleme werden lineare Programmierungsprobleme genannt und wir werden sie im Detail besprechen. Lass uns anfangen:

Was ist lineare Programmierung?

Die lineare Programmierung ist eine Methode zur Darstellung komplexer Zusammenhänge durch lineare Funktionen. Unser Ziel bei der linearen Programmierung ist es, die am besten geeigneten Lösungen für diese Funktionen zu finden. Die reale Beziehung zwischen zwei Punkten kann sehr komplex sein, aber wir können sie mit linearer Programmierung einfach darstellen. Lineare Programmierung findet in vielen Branchen Anwendung.

Grundlagen der linearen Programmierung

Hier sind einige grundlegende Begriffe der linearen Programmierung:

Zwang

Die Einschränkungen (oder Einschränkungen) Ihrer Entscheidungsvariablen werden als Einschränkungen bezeichnet. Die meisten Zeitbeschränkungen sind die Einschränkungen, die Sie in Ihren Ressourcen haben, um ein Problem zu lösen.

Entscheidungsvariable

Diese Variablen definieren Ihre Ausgabe. Ihr Ergebnis hängt von diesen Variablen ab, deshalb nennen wir sie „Entscheidungsvariablen“.

Nicht-Negativitätsbeschränkung

Die Entscheidungsvariablen eines linearen Programmierproblems können nur einen nicht negativen Wert haben. Das bedeutet, dass die Werte für Ihre Entscheidungsvariablen nur gleich oder größer als Null sein können.

Zielfunktion

Die Zielfunktion ist das Ziel Ihrer Entscheidungsfindung. Einfach ausgedrückt ist es das Endergebnis Ihres linearen Programmierproblems. Wenn Sie beispielsweise den maximalen Gewinn ermitteln, den Sie mit einem bestimmten Satz von Ressourcen erzielen können, ist der maximale Gewinn die Zielfunktion.

Formulieren linearer Programmierprobleme

Sie sollten wissen, wie man eine lineare Programmierung formuliert, um sie im wirklichen Leben anzuwenden. Angenommen, Sie sind ein Hersteller von Spielzeug und produzieren nur zwei Spielzeuge: A und B. Grob gesagt benötigen Ihre Spielzeuge zwei Ressourcen X und Y zur Herstellung. Hier sind die Anforderungen an Ihr Spielzeug:

• Eine Einheit von Spielzeug A erfordert eine Einheit von Ressource X und drei Einheiten von Ressource Y

• Eine Einheit von Spielzeug B erfordert eine Einheit von Ressource X und zwei Einheiten von Ressource Y

Sie haben fünf Einheiten der Ressource X und 12 Einheiten der Ressource Y. Ihre Gewinnspannen beim Verkauf dieser Spielzeuge betragen:

• INR 6 für jede verkaufte Einheit von Spielzeug A
• INR 5 für jede verkaufte Einheit von Spielzeug B

Wie viele Einheiten jedes Spielzeugs würden Sie produzieren, um den maximalen Gewinn zu erzielen?

Die Lösung

Stellen wir unser lineares Programmierproblem in einer Gleichung dar:

Z = 6a + 5b

Hier steht z für den Gesamtgewinn, a steht für die Gesamtzahl der Spielzeug-A-Einheiten und b steht für die Gesamtzahl der B-Einheiten. Unser Ziel ist es, den Wert von Z (den Gewinn) zu maximieren.

Nun möchte Ihr Unternehmen so viele Einheiten dieser Spielzeuge wie möglich produzieren, aber Sie haben nur begrenzte Ressourcen. Die Einschränkungen unserer Ressourcen sind die Einschränkungen dieses Problems. Wir haben nur insgesamt

a + b 5

Jetzt benötigt jede Einheit von Spielzeug A und B 3 bzw. 2 Einheiten der Ressource Y. Und wir haben insgesamt nur 12 Einheiten der Ressource Y, also würde es mathematisch so aussehen:

3a + 2b 12

Denken Sie daran, dass die Werte für die Einheiten von Spielzeug A nur Ganzzahlen sein können. Das bedeutet, dass wir auch die Einschränkungen von a->0 und b<-0 haben.

Jetzt haben Sie also ein richtiges lineares Programmierproblem. Sie können andere Probleme der linearen Programmierung formulieren, indem Sie diesem Beispiel folgen. Während dieses Beispiel ziemlich einfach war, können LP-Probleme sehr kompliziert werden.

Lesen Sie: Ideen und Themen für lineare Programmierungsprojekte

Schritte zur Formulierung linearer Programmierprobleme

Um ein Problem der linearen Programmierung zu formulieren, gehen Sie folgendermaßen vor:

• Finden Sie die Entscheidungsvariablen
• Finden Sie die Zielfunktion
• Identifizieren Sie die Einschränkungen
• Denken Sie an die Nicht-Negativitätsbeschränkung

Wenn ein Problem die obigen Kriterien erfüllt, handelt es sich um ein lineares Programmierproblem. Es empfiehlt sich, dieses Kriterium im Hinterkopf zu behalten, wenn Sie daran arbeiten, die Art des Problems zu identifizieren.

Lösen von linearen Programmierproblemen mit R

Wenn Sie R verwenden, wird das Lösen linearer Programmierprobleme viel einfacher. Das liegt daran, dass R das Paket lpsolve enthält, das verschiedene Funktionen enthält, die speziell für die Lösung solcher Probleme entwickelt wurden. Es ist sehr wahrscheinlich, dass Sie als Data Scientist sehr häufig R verwenden werden, um LP-Probleme zu lösen. Aus diesem Grund haben wir zwei unterschiedliche Beispiele geteilt, damit Sie die Implementierung besser verstehen:

Beispiel

Beginnen wir mit einem grundlegenden Problem. Eine Organisation hat zwei Produkte mit Verkaufspreisen von 25 INR und 20 INR, die als Produkt A bzw. B bezeichnet werden. Jeden Tag haben sie 1800 Einheiten an Ressourcen, um diese Produkte herzustellen. Produkt A benötigt 20 Ressourceneinheiten und B benötigt 12 Ressourceneinheiten. Die Produktionszeit für diese beiden Produkte beträgt vier Minuten, und die Organisation erhält täglich insgesamt acht Arbeitsstunden. Das Problem ist, wie hoch sollte die Produktionsmenge für jedes dieser Produkte sein, um die Gewinne des Unternehmens zu maximieren?

Lösung:

Wir beginnen mit der Lösung dieses Problems, indem wir seine Zielfunktion definieren:

max(Umsatz) = max( 25 Jahre 1 + 20 Jahre 2 )

Hier sind 25 und 20 die Preise von Produkt A bzw. B, y1 ist die Gesamtzahl der produzierten Einheiten von Produkt A und y2 ist die Gesamtzahl der produzierten Einheiten von Produkt B. Unsere Entscheidungsvariablen sind y1 und y2.

Wir werden jetzt die Einschränkungen für unser Problem festlegen:

Ressourcenbeschränkung:

20 Jahre 1 + 12 Jahre 2 1800

Zeitbeschränkung:

4 Jahre 1 + 4 Jahre 2 8*60

Unser Ziel ist es, die richtige Anzahl von Produkten zu finden, die wir herstellen müssen, um den maximalen Gewinn zu erzielen.

Verwenden von R zum Lösen des Problems:

Wir werden lpsolve verwenden, um dieses LP-Problem zu lösen, und beginnen mit dem Festlegen der Zielfunktion:

> erfordern (lpSolve)

Erforderliches Paket wird geladen: lpSolve

> Ziel.in <- c(25, 20)

> Ziel.in

[1] 25 20

Dann erstellen wir eine Matrix für die Einschränkungen:

> const <- matrix(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> konst

[,1] [,2]

[1,] 20 12

[2,] 4 4

> Zeitbeschränkungen <- (8*60)

> Ressourcenbeschränkungen <- 1800

> Zeitbeschränkungen

[1] 480

> Ressourcenbeschränkungen

[1] 1800

Lassen Sie uns nun die bereits definierten Gleichungen erstellen:

> rhs <- c(resource_constraints, time_constraints)

> rechts

[1] 1800 480

> Richtung <- c(“<=”, “<=”)

> Richtung

[1] „<=“ „<=“

Sobald alle notwendigen Informationen hinzugefügt wurden, können wir beginnen, die optimale Antwort zu finden. Die Syntax für unser Paket lautet:

lp( Richtung, Ziel, const.mat, const.dir, const.rhs )

> optimal <- lp(direction=“max“, objektiv.in, const, direction, rhs)

> optimal

Erfolg: Die Zielfunktion ist 2625

> Zusammenfassung (optimal)

Längenklassenmodus

Richtung 1 -keine- numerisch

x.count 1 -keine- numerisch

Ziel 2 -keine-numerisch

const.count 1 -keine- numerisch

Beschränkungen 8 -keine- numerisch

int.count 1 -keine- numerisch

int.vec 1 -keine- numerisch

bin.count 1 -keine- numerisch

Binär.vec 1 -keine- numerisch

num.bin.solns 1 -keine- numerisch

objval 1 -keine- numerisch

Lösung 2 -keine- numerisch

presolve 1 -keine- numerisch

compute.sens 1 -none- numerisch

Sens.Koef.ab 1 -keine- numerisch

Sens.coef.to 1 -keine- numerisch

duals 1 -keine- numerisch

duals.from 1 -keine- numerisch

duals.to 1 -keine- numerisch

Skala 1 -keine- numerisch

use.dense 1 -none- numerisch

dense.col 1 -keine- numerisch

dense.val 1 -keine- numerisch

dense.const.nrow 1 -keine- numerisch

Dense.ctr 1 -keine- numerisch

use.rw 1 -keine- numerisch

tmp 1 -kein- Zeichen

Status 1 -keine- numerisch

Nachdem Sie den obigen Code ausgeführt haben, können Sie die gewünschten Lösungen für unser Problem erhalten.

Die optimalen Werte für y1 und y2:

Denken Sie daran, dass y1 und y2 die Einheiten von Produkt A und Produkt B waren, die wir herstellen mussten:

> optimale$Lösung

[1] 45 75

Die optimale Verkaufszahl:

Der maximale Gewinn, den wir mit den erhaltenen Werten von y1 und y2 erzielen können, ist:

> optimal$objval

[1] 2625

Lesen Sie auch: Lineare Algebra für maschinelles Lernen

Anwendungen der linearen Programmierung

Wie bereits erwähnt, findet die lineare Programmierung in vielen Branchen Anwendung. Hier sind einige Bereiche, in denen wir es verwenden:

• Mit der steigenden Beliebtheit von Lieferdiensten ist die lineare Programmierung zu einer der beliebtesten Methoden geworden, um die optimalen Routen zu finden. Wenn Sie einen Ola oder Uber nehmen, verwendet die Software eine lineare Programmierung, um die beste Route zu finden. Lieferunternehmen wie Amazon und FedEx verwenden es auch, um die besten Routen für ihre Zusteller zu ermitteln. Sie konzentrieren sich auf die Reduzierung der Lieferzeit und -kosten.
• Das überwachte Lernen des maschinellen Lernens arbeitet an den grundlegenden Konzepten der linearen Programmierung. Beim überwachten Lernen müssen Sie das optimale mathematische Modell finden, um die Ausgabe gemäß den bereitgestellten Eingabedaten vorherzusagen.
• Der Einzelhandel nutzt die lineare Programmierung zur Optimierung der Regalfläche. Bei so vielen verfügbaren Marken und Produkten ist es eine sehr strenge Aufgabe, zu bestimmen, wo sie im Geschäft platziert werden sollen. Die Platzierung eines Produkts im Geschäft kann den Umsatz stark beeinflussen. Große Einzelhandelsketten wie Big Bazaar, Reliance, Walmart usw. verwenden lineare Programmierung zur Bestimmung der Produktplatzierung. Sie müssen die Interessen der Verbraucher im Auge behalten und gleichzeitig die beste Produktplatzierung sicherstellen, um maximalen Gewinn zu erzielen.
• Unternehmen nutzen die lineare Programmierung, um ihre Lieferketten zu verbessern. Die Effizienz einer Lieferkette hängt von vielen Faktoren ab, wie z. B. den gewählten Routen, Zeitplänen usw. Durch die Verwendung der linearen Programmierung können sie die besten Routen, Zeitpläne und andere Ressourcenzuweisungen finden, um ihre Effizienz zu optimieren.

Erfahren Sie mehr über lineare Programmierung und Data Science

Lineare Programmierung ist eines der wichtigsten Konzepte der Datenwissenschaft. Es ist auch ein grundlegendes Thema, das Sie kennen sollten, um ein kompetenter Datenwissenschaftler zu werden. Wie wir besprochen haben, gibt es viele Anwendungen für dieses Konzept und Sie können seine Anwendungsfälle in Ihrem täglichen Leben finden.

In unserem Blog erfahren Sie mehr über Data Science und die damit verbundenen Konzepte. Wir haben viele wertvolle Ressourcen, mit denen Sie mehr erfahren können. Hier sind einige für Ihre weitere Lektüre:

• Die wichtigsten Gründe, Data Scientist zu werden
• Die Algorithmen, die jeder Data Scientist kennen sollte
• So wird man Data Scientist

Auf der anderen Seite können Sie einen Data Science-Kurs besuchen, um von Branchenexperten zu lernen. Sie lernen interaktiv durch Videos, Quiz und Projekte. Die Teilnahme an einem Kurs hilft Ihnen, die notwendigen Fähigkeiten zu erlernen, um ein professioneller Datenwissenschaftler zu werden. Schauen Sie sich das PG-Diplom in Data Science von IIIT-B & upGrad an, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische Workshops, Mentoring mit Branchenexperten, 1-zu-1 mit Branchenmentoren und mehr als 400 Stunden bietet von Lern- und Arbeitsassistenz bei Top-Firmen.