Sledeči program po korakih izvaja simpleksno metodo.
def spremenljivke(n, zacetek=0, predpona="x", ciljna="z"):
"""
Nastavi želeno število spremenljivk s podano predpono.
"""
var(" ".join("%s%d" % (predpona, i) for i in range(zacetek, n+1)))
var(ciljna)
def izpisi_enacbe(enacbe):
"""
Uredi in ustrezno izpiše enačbe.
"""
enacbe.sort(key=lambda e: str(e.lhs()))
for e in enacbe:
r = e.rhs()
c = r.subs([v == 0 for v in r.variables()])
rr = r - c
s = str(rr)
if c == 0:
c = znak = ""
elif s[0] == "-":
s = s[1:]
znak = " - "
else:
znak = " + "
print("%s == %s%s%s" % (e.lhs(), c, znak, s))
print("")
return enacbe
def simpleksna_metoda(enacbe, *spremenljivke):
"""
Za podani začetni slovar izvaja podane zamenjave baznih in nebaznih spremenljivk.
"""
enacbe = izpisi_enacbe(enacbe)
for vstopna, izstopna in spremenljivke:
sol = next(e for e in enacbe if e.lhs() == izstopna).solve(vstopna)[0]
enacbe = izpisi_enacbe([sol if e.lhs() == izstopna else e.subs(sol) for e in enacbe])
Funkcija izpisi_enacbe
je pomožna. S funkcijo spremenljivke
si pripravimo želeno število spremenljivk, funkcijo simpleksna_metoda
pa uporabimo tako, da kot prvi argument podamo slovar enačb, za tem pa naštevamo pare vstopnih in izstopnih spremenljivk.
spremenljivke(6)
simpleksna_metoda([
x4 == 5 - 2*x1 - 3*x2 - x3,
x5 == 11 - 4*x1 - 3*x2 - x3,
x6 == 8 - 3*x1 - 4*x2 - 2*x3,
z == 5*x1 + 4*x2 + 3*x3
], (x1, x4), (x2, x1))
x4 == 5 - 2*x1 - 3*x2 - x3 x5 == 11 - 4*x1 - 3*x2 - x3 x6 == 8 - 3*x1 - 4*x2 - 2*x3 z == 5*x1 + 4*x2 + 3*x3 x1 == 5/2 - 3/2*x2 - 1/2*x3 - 1/2*x4 x5 == 1 + 3*x2 + x3 + 2*x4 x6 == 1/2 + 1/2*x2 - 1/2*x3 + 3/2*x4 z == 25/2 - 7/2*x2 + 1/2*x3 - 5/2*x4 x2 == 5/3 - 2/3*x1 - 1/3*x3 - 1/3*x4 x5 == 6 - 2*x1 + x4 x6 == 4/3 - 1/3*x1 - 2/3*x3 + 4/3*x4 z == 20/3 + 7/3*x1 + 5/3*x3 - 4/3*x4
Preverite, ali so vaše rešitve pravilne. Prav tako lahko poizkušate, kaj se zgodi, če izberete napačno vstopno ali izstopno spremenljivko.
Pri prvi fazi dvofazne metode ugotavljamo dopustnost problema z n spremenljivkami tako, da rešujemo problem z $n+1$ spremenljivkami. Če je $n = 2$, si povezavo med problemoma lahko tudi predstavljamo.
nastavitve = {'plot_points': 1000, 'incol': 'lightblue', 'bordercol': 'gray'}
spremenljivke(5, 0, ciljna="w z")
omejitve = [
x1 - x2 <= -1,
-x1 - x2 <= -3,
2*x1 + x2 <= 4
]
pozitivnost = [x1 >= 0, x2 >= 0, x0 >= 0]
meje = [(x1, -0.1, 3), (x2, -0.1, 7), (x0, 0, 3)]
region_plot(omejitve + pozitivnost[:2], *meje[:2], **nastavitve)
implicit_plot3d(max_symbolic(*([e.lhs() - e.rhs() - x0 for e in omejitve] +
[-e.lhs() for e in pozitivnost])), smooth=False, *meje)
simpleksna_metoda([x == e.rhs() + x0 - e.lhs() for x, e in zip([x3, x4, x5], omejitve)] +
[w == -x0, z == x1 + x2],
(x0, x4), (x2, x0), (x1, x3), (x4, x5))
w == -x0 x3 == -1 + x0 - x1 + x2 x4 == -3 + x0 + x1 + x2 x5 == 4 + x0 - 2*x1 - x2 z == x1 + x2 w == -3 + x1 + x2 - x4 x0 == 3 - x1 - x2 + x4 x3 == 2 - 2*x1 + x4 x5 == 7 - 3*x1 - 2*x2 + x4 z == x1 + x2 w == -x0 x2 == 3 - x0 - x1 + x4 x3 == 2 - 2*x1 + x4 x5 == 1 + 2*x0 - x1 - x4 z == 3 - x0 + x4 w == -x0 x1 == 1 - 1/2*x3 + 1/2*x4 x2 == 2 - x0 + 1/2*x3 + 1/2*x4 x5 == 2*x0 + 1/2*x3 - 3/2*x4 z == 3 - x0 + x4 w == -x0 x1 == 1 + 2/3*x0 - 1/3*x3 - 1/3*x5 x2 == 2 - 1/3*x0 + 2/3*x3 - 1/3*x5 x4 == 4/3*x0 + 1/3*x3 - 2/3*x5 z == 3 + 1/3*x0 + 1/3*x3 - 2/3*x5
Za katere vrednosti parametra $a$ je sledeči problem dopusten? Pomagajte si z @interact
.
x, y = var("x y")
meje = [(x, 0, 2), (y, 0, 2)]
@interact
def _(a=slider(0, 2, default=0, step_size=0.01, label='$a$'),
k=slider(0, 2, default=1, step_size=0.01, label='$k$')):
show(region_plot([x + y >= a, 2*x + y >= 1, x + 2*y <= 1], *meje, **nastavitve) +
implicit_plot(x + y - k, *meje))
SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIF8gYXQgMHg4NjgyYTZiYz4gd2l0aCAyIHdpZGdldHMKICBhOiBUcmFuc2Zvcm1GbG9hdFNsaWRlcih2YWx1ZT0wLjAsIGRlc2NyaXB0aW/igKY=
Pri izbiri vstopnih in izstopnih spremenljivk upoštevaj naslednji pravili:
Kaj opaziš?
spremenljivke(7)
simpleksna_metoda([
x5 == -1/2*x1 + 11/2*x2 + 5/2*x3 - 9*x4,
x6 == -1/2*x1 + 3/2*x2 + 1/2*x3 - x4,
x7 == 1 - x1,
z == 10*x1 - 57*x2 - 9*x3 - 24*x4
], (x1, x5), (x2, x6), (x3, x1), (x4, x2), (x5, x3), (x1, x4), (x3, x7))
x5 == -1/2*x1 + 11/2*x2 + 5/2*x3 - 9*x4 x6 == -1/2*x1 + 3/2*x2 + 1/2*x3 - x4 x7 == 1 - x1 z == 10*x1 - 57*x2 - 9*x3 - 24*x4 x1 == 11*x2 + 5*x3 - 18*x4 - 2*x5 x6 == -4*x2 - 2*x3 + 8*x4 + x5 x7 == 1 - 11*x2 - 5*x3 + 18*x4 + 2*x5 z == 53*x2 + 41*x3 - 204*x4 - 20*x5 x1 == -1/2*x3 + 4*x4 + 3/4*x5 - 11/4*x6 x2 == -1/2*x3 + 2*x4 + 1/4*x5 - 1/4*x6 x7 == 1 + 1/2*x3 - 4*x4 - 3/4*x5 + 11/4*x6 z == 29/2*x3 - 98*x4 - 27/4*x5 - 53/4*x6 x2 == x1 - 2*x4 - 1/2*x5 + 5/2*x6 x3 == -2*x1 + 8*x4 + 3/2*x5 - 11/2*x6 x7 == 1 - x1 z == -29*x1 + 18*x4 + 15*x5 - 93*x6 x3 == 2*x1 - 4*x2 - 1/2*x5 + 9/2*x6 x4 == 1/2*x1 - 1/2*x2 - 1/4*x5 + 5/4*x6 x7 == 1 - x1 z == -20*x1 - 9*x2 + 21/2*x5 - 141/2*x6 x4 == -1/2*x1 + 3/2*x2 + 1/2*x3 - x6 x5 == 4*x1 - 8*x2 - 2*x3 + 9*x6 x7 == 1 - x1 z == 22*x1 - 93*x2 - 21*x3 + 24*x6 x1 == 3*x2 + x3 - 2*x4 - 2*x6 x5 == 4*x2 + 2*x3 - 8*x4 + x6 x7 == 1 - 3*x2 - x3 + 2*x4 + 2*x6 z == -27*x2 + x3 - 44*x4 - 20*x6 x1 == 1 - x7 x3 == 1 - 3*x2 + 2*x4 + 2*x6 - x7 x5 == 2 - 2*x2 - 4*x4 + 5*x6 - 2*x7 z == 1 - 30*x2 - 42*x4 - 18*x6 - x7
Zgornji linearni program reši še s pomočjo Blandovega pravila (tako vstopne kot izstopne spremenljivke izbiraš glede na leksikografsko ureditev).
Nato poiščite še optimalno rešitev v primeru, da sta $x_1$ in $x_2$ celoštevilski spremenljivki.
Nazadnje poiščite isto optimalno rešitev še na roke, torej tako, da ne izkoristite tega, da zna Sage reševati tudi celoštevilske probleme.
def problem(integer=False):
p = MixedIntegerLinearProgram(maximization=True)
x = p.new_variable(integer=integer)
p.set_objective(3*x[1] + 4*x[2])
p.add_constraint(2*x[1] + x[2] <= 6)
p.add_constraint(2*x[1] + 3*x[2] <= 9)
p.add_constraint(x[1] >= 0)
p.add_constraint(x[2] >= 0)
opt = p.solve()
return (opt, p.get_values(x))
# Linearni program
problem(integer=False)
(12.75, {1: 2.2499999999999996, 2: 1.5000000000000004})
# Celoštevilski linearni program
problem(integer=True)
(12.0, {1: 0.0, 2: 3.0})
spremenljivke(2)
meje = [(x1, 0, 3), (x2, 0, 3)]
tocke = sum(circle((i, j), 0.02, fill=True, rgbcolor='red') for i in range(meje[0][1], meje[0][2]+1)
for j in range(meje[1][1], meje[1][2]+1))
@interact
def _(k=slider(0, 15, default=0, step_size=0.01, label='$k$')):
show(region_plot([2*x1 + x2 <= 6, 2*x1 + 3*x2 <=9], *meje, **nastavitve) + tocke +
implicit_plot(3*x1 + 4*x2 - k, *meje))
SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIF8gYXQgMHg4MDdlNWI4Yz4gd2l0aCAxIHdpZGdldAogIGs6IFRyYW5zZm9ybUZsb2F0U2xpZGVyKHZhbHVlPTAuMCwgZGVzY3JpcHRpb27igKY=
Rešite problem 0-1 nahrbtnika z volumnom 10 in naslednjimi predmeti:
volumen | cena |
---|---|
2 | 30 |
4 | 60 |
6 | 50 |
3 | 40 |
V = 10
v = [2, 4, 6, 3]
c = [30, 60, 50, 40]
resitev = [Set()] # seznam optimalnih rešitev pri dani omejitvi volumna
cena = [0] # seznam cen optimalnih rešitev pri dani omejitvi volumna
for i in range(1, V+1):
r = resitev[-1]
t = cena[-1]
for j, (vj, cj) in enumerate(zip(v, c)):
if vj > i or j in resitev[i - vj]:
continue
nova = cena[i - vj] + cj
if nova > t:
r = resitev[i - vj] | Set([j])
t = nova
resitev.append(r)
cena.append(t)
print("Volumen %d, rešitev %s, cena %d" % (i, r, t))
Volumen 1, rešitev {}, cena 0 Volumen 2, rešitev {0}, cena 30 Volumen 3, rešitev {3}, cena 40 Volumen 4, rešitev {1}, cena 60 Volumen 5, rešitev {0, 3}, cena 70 Volumen 6, rešitev {0, 1}, cena 90 Volumen 7, rešitev {1, 3}, cena 100 Volumen 8, rešitev {1, 3}, cena 100 Volumen 9, rešitev {0, 1, 3}, cena 130 Volumen 10, rešitev {0, 1, 3}, cena 130