Huiswerk # 1, TW2020/Besliskunde 1 2014/2015 Opgaven uit het

Huiswerk # 1, TW2020/Besliskunde 1 2014/2015
Opgaven uit het boek
Hoofdstuk 1:
• 1.3
Hoofdstuk 2:
• 2.7: Hint: Start in een basisoplossing waarbij variabele xq in de basis zit met
waarde 0. Laat zien dat bij elke pivot de relatieve kosten c¯q van xq alleen maar
groter worden.
Overige opgaven
Opgave 1.
Een bedrijf produceert vier verschillende legeringen van 2 soorten metaal. Het percentage van de twee soorten metaal in de legeringen, de verkoopprijs in Euro per
kg legering en de hoeveelheid metaal beschikbaar per dag worden gegeven in onderstaande tabel. Het percentage van metaal 1 in legering 1 (“a” in de tabel) moet tussen
48 en 52 zijn. Het bedrijf heeft zich verplicht om tenminste 100 kg van legering 1 te
maken.
Welke productieschema maximaliseert de inkomsten? Geef een LP-formulering
om dit probleem op te lossen. Je hoeft het probleem niet op te lossen, alleen te
formuleren.
Percentage metaal
in legering
1
2
3
4
Metaal
1
2
Verkoopprijs (EUR)
per kg legering
a
100-a
60
40
30
70
10
90
0.01
0.015
0.018
0.04
Hoeveelheid (kg)
metaal beschikbaar
per dag
6000
4000
Opgave 2. Gegeven is een n-dimansionale geheeltallige rij-vector a en een geheel
getal b. Laat zien dat de verzameling H = {x ∈ Rn | ax ≤ b} convex is.
Opgave 3. Bepaal, met behulp van het Simplexalgoritme, alle optimale oplossingen
van het volgende probleem:
max z =
o.d.v.
2x1
2x1
x1
x1 ,
+
+
x2
3x2
2x2
x2 ,
+
−
+
+
x3
x3
x3
x3
x3
≤
≥
=
≥
9
4
6
0
Opgave 4. Beschouw het volgende lineaire optimaliseringsprobleem (NB! alleen ´e´en
voorwaarde behalve de niet-negatieviteitseisen). Veronderstel dat b, a1 , . . . , an 6= 0.
min
n
X
cj xj
j=1
o.d.v.
n
X
aj xj
= b
xj
≥ 0
j=1
voor iedere j = 1, . . . , n .
(a) Ontwerp een test om te controleren of het probleem toegelaten oplossingen heeft.
(b) Ontwerp een test om te controleren of het probleem onbegrensd is.
(c) Ontwerp een eenvoudige methode (niet het Simplexalgoritme!) om snel een optimale oplossing te bepalen. Beargumenteer ook waarom de verkregen oplossing
optimaal is.
2

Download Report