leichte/schwere Optimierungsprobleme

**csad6896** · 30.06.2005, 12:15

finde keine antwort dazu...

was unterscheidet leichte von schweren Optimierungsproblemen?

plz help!!

**aaaa** · 30.06.2005, 13:20

Bei schweren Optimierungsbeispielen steigt der Rechenaufwand expontial, wenn neue Variabeln hinzu kommen. (ganzzahlige Optimierung)

Bei leichten steigen sie polynom! (lineare Optimierung)

mfg

aaa

**steven83ffm** · 30.06.2005, 13:36

leicht --> lineare optimierung --> reelwertige variablen, lineare (un)gleichungen

schwer --> ganzzahlige optimierung --> ganzzahlige variablen

**aaaa** · 30.06.2005, 13:40

Nein,
Ganzahlig Optimierung:
Travaling Salesman 35!
Rucksackproblem 2^n

mfg

aaa

**gennis** · 30.06.2005, 13:47

ganzzahlig ist doch n!,oder?? und das ist doch dann die ganzzahlige Optimierung! Und ich hab gedacht, die hat immer einen höheren rechenaufwand, deswegne nicht die schwere optimierung?

**aaaa** · 30.06.2005, 13:52

2^n und n! läuft aufs gleiche hinaus und bedeutet ganzzahlig optimierung.

Linerae Optimierung ist , wenn rellwertig Variabeln bzw. lineare Funktionen gegeben sind. (steigen Polynom!)

mfg

aaa

**gennis** · 30.06.2005, 13:54

Zitat von aaaa

Bei schweren Optimierungsbeispielen steigt der Rechenaufwand expontial, wenn neue Variabeln hinzu kommen. (lineare Optimierung)

Bei leichten steigen sie polynom! (Ganzzahlig Optimierung)

mfg

aaa

weil du hier ganzzahlige und lineare dann vertauscht hast oder?

**aaaa** · 30.06.2005, 14:01

weil was?!

Zuerst haben wir im Skript bzw VO. zwei Bsp der linearen Optimierung:
optimales Produktionsprogramm
saisonale Absatzschwankungen

dann zwei ganzzahlige Bsp
Travelling Sales Man
Rucksackproblem

Nach den beiden Kapitel kommt jeweils eine Zusammsenfassung darüber!

Aber wenn du meinst schau ich auch mal nach!

mfg

aaa

**steven83ffm** · 30.06.2005, 14:10

bei linearen Optimierungen steigt der Rechenaufwand polynominal mit dem Problemumfang
Bsp: 5 Maschinen, 10 Erzeugnisse --> 5 Maschinen, 11 Erzeugnisse

bei ganzzahligen Optimierungen steigt der Rechenaufwand exponentiell mit dem Problemumfang --> deshalb sind ganzzahlige Optimierung ab einer gewissen Größe so schwer zu berechnen und benötigen hohe Rechenzeiten. Meist aber gehts eh nur mit Heuristiken, Annäherungsverfahren!
Bsp: Routenplanung --> 30 Standorte -> 30! ---> 31 Standorte -> 31!