Avatar billede coldplay Nybegynder
10. januar 2004 - 22:37 Der er 36 kommentarer og
2 løsninger

Matematisk optimeringsproblem

Spørgsmål: hvordan opnås færrest mulige opkald med længst mulig samtaletid på et taletidskort?

Eksempel: Man har et taletidskort på 100 kr med en opkaldsafgift på 25 øre og minutpris på 4,00 kr.

Hvordan får man mest ud af sine 100 kr. ud fra ovenstående kriterier?

Jeg vil gerne implementere kompetente løsningsforslag i noget c++ kode.

Arbejder selv på en løsning, men ved ikke om jeg er på rette spor.

Er der nogen derude med matematisk flair?
Avatar billede arne_v Ekspert
10. januar 2004 - 22:42 #1
Har jeg misforstået noget (igen) ?

Man får vel mest ud af det med kun 1 opkald ?
Avatar billede erikjacobsen Ekspert
10. januar 2004 - 22:42 #2
Skifter til www.telmore.dk  -  er der virkelig nogen der betaler 4 kr i minutpris i disse dage ;(
Avatar billede arne_v Ekspert
10. januar 2004 - 22:43 #3
Strengt taget er det vel et lineært optimerings problem som kan løses med
simplex, men uanset priser må 1 opkald vel altid give flest minutters
taletid.
Avatar billede akany_ Nybegynder
10. januar 2004 - 23:01 #4
Gider du prøve at forklare lidt nærmere, hvor du vil henad coldplay?

  Som arne siger kan det ikke rigtigt være andet end 1 opkald hvis dit mål er færrest mulige opkald med maximal udnyttelse af taletiden...
Avatar billede unsigned Nybegynder
10. januar 2004 - 23:23 #5
Arne_v har allerede givet svaret. Men alligevel.

Vi laver en funktion, der på grundlag af antal opkald, beregner mængden af taletid.

y = f(x) = 100 - (x * 0.25), x = 1, 2, 3...398, 399, 400.

Vi ser at det er en linear funktion. Vi kan derfor indsætte nøjes med at indsætte grænseværdierne, x=1 og x=400, og se hvad der giver størst mængde af y. Vi ser at x=1 giver 99.75 y, og x=400 giver 0 y. Vi konkluderer at x=1 giver størst mængde taletid.
Avatar billede unsigned Nybegynder
10. januar 2004 - 23:24 #6
'derfor indsætte nøjes' der skal stå 'derfor nøjes'.
Avatar billede coldplay Nybegynder
10. januar 2004 - 23:28 #7
arne_v--> Grrrrrrrrrrrrrrr....

Du har ikke misforstået noget. Jeg skulle have skrevet "flest mulige opkald med længest mulig samtaletid"...

Det begrunder sikkert din forvirring.

Sorry..:(
Avatar billede akany_ Nybegynder
10. januar 2004 - 23:29 #8
Denne ligning kan hvor tiden for en opringning (t) angives som en funktion af antal opkald (x)
(100-x*0,25)/4 = t
Så vil den samlet tid for alle opringningerne (ts)være angivet med ligningen

ts = x*t

Nu kan vi trække de 2 ligninger sammen så vi vil få:

((100-0,25*x)/4)*x = ts
(25-0,625*x)*x = ts

-0,625(x^2) + 25x=ts

  Ovenstående er ligningen for at beregne den samlede taletid(ts) som funktion af antal opkald(x).
Avatar billede arne_v Ekspert
10. januar 2004 - 23:31 #9
Der er ikke rigtigt noget som hedder flest opkald *og* mest samtale tid.

flere opkald => mindre samtale tid

færre opkald => mere samtale tid
Avatar billede coldplay Nybegynder
10. januar 2004 - 23:34 #10
akany_-->Jeg så ikke dit indlæg da jeg kommenterede indlægget fra arne_v...

Du er med...
Avatar billede arne_v Ekspert
10. januar 2004 - 23:36 #11
Du kan ikke finde det optimale alene udfra den sammenhæng.

Du bliver bødt til at ligge nogle præferancer ind også.
Avatar billede arne_v Ekspert
10. januar 2004 - 23:37 #12
nødt
Avatar billede akany_ Nybegynder
10. januar 2004 - 23:38 #13
Nu kan manfristes til at sige at detteher kan løses ved hjælp af toppunktsformlen med det vil komme til at give et negativt tal ved den ene af dem så vi må begrænse vores virkefelt lidt endnu
Avatar billede arne_v Ekspert
10. januar 2004 - 23:43 #14
akany>

Problemet er altså lineært - ikke kvadratisk !

(100-x*0,25)/4 = t er forkert - det er (100-x*0,25)/4 = ts
Avatar billede unsigned Nybegynder
10. januar 2004 - 23:44 #15
Hvis man skal programmerer noget, der skal kunne finde yderpunkter for en kurve, så kommer man ud i noget meget indviklet matematik. Finite element og den slags. Nemmere er det at give c++ programmet alle x-værdierne, og så gemme alle y-værdierne, og så finde yderpunkter blandt y-værdierne. Med passende intervaller.
Avatar billede akany_ Nybegynder
10. januar 2004 - 23:45 #16
arne: når du siger (100-x*25)/4 beregner du taletiden for 1 opkald. Med ts siger jeg den samlede tid for et opkald
Avatar billede unsigned Nybegynder
10. januar 2004 - 23:46 #17
Det er x-værdierne, der skal have passsende intervaller.
Avatar billede akany_ Nybegynder
10. januar 2004 - 23:46 #18
mener alle opkald
Avatar billede arne_v Ekspert
10. januar 2004 - 23:47 #19
akany>

Nej.

Du kan ikke bruge de 100 kr. mere end 1 gang.
Avatar billede coldplay Nybegynder
10. januar 2004 - 23:49 #20
n: antal opkald

p: pris pr. opkald (kr)

q: minutpris (kr/min)

T: samlet taletid (min)

t: samtaletid pr. opkald (min)

s: samlet udgift (kr)


s = n*p + n*q*t = n*(p + qt)

Spørgsmål: hvordan opnås flest mulige opkald
                        =====
med længst mulig samtaletid?
    ======

Eksempel: Man har et taletidskort på 100 kr med en opkaldsafgift på 25 øre og minutpris på 4,00 kr.

Hvordan får man mest ud af sine 100 kr. ud fra ovenstående kriterier?

s(t) = n(t) * (p + qt) <==>

n(t) = s(t) / (p + qt)

hvor n(t) er antallet af opkald som funktion af samtaletiden t og s(t), p og q natur-ligvis er konstante størrelser.

Hvad siger I til at n(t) viser en hyperbel, hvor tangenthældningen er lig 1, og det er netop i dette punkt, hvor man får flest opkald med længest ligelige fordelt samtaletid pr. opkald?

Hvorfor fyrer godt og vel alle 25 minutter af på en gang.
Avatar billede arne_v Ekspert
10. januar 2004 - 23:49 #21
x=16 opkald
pris for opkald=4 kr.
tilbage til samtaler=96 kr.
antal minutter ialt=24
antal minutter per samtale=1.5
Avatar billede akany_ Nybegynder
10. januar 2004 - 23:52 #22
arne: kan godt se det nu. Godt min matematiklærer ikke så den :)
Avatar billede coldplay Nybegynder
10. januar 2004 - 23:52 #23
Tangenthældning = -1
Avatar billede coldplay Nybegynder
11. januar 2004 - 00:04 #24
Rigtigt svar:

5 opkald * 4,9375 min = 24,6875 min
Avatar billede arne_v Ekspert
11. januar 2004 - 00:12 #25
For det første kan man vel ikke tale om tangent hældning for en funktion
som kun returnerer enkelt punkter (opkald er heltal).

For det andet - selvom man kunne - hvad skulle der så være optimalt
ved tangent hældning -1 ?
Avatar billede unsigned Nybegynder
11. januar 2004 - 00:14 #26
-> Du har et begreb, der hedder 'længst ligeligt fordelt samtaletid'. Men det er en modstrid. Du vil optimerer 2 ting samtidig. Længst samtaletid fås ved et opkald, ca. 25 min. Ved to opkald fås ca. 12 min (og det er mere end 4,9375). Ved 399 opkald fås en meget kort liglig fordelt samtaletid.
Avatar billede coldplay Nybegynder
11. januar 2004 - 00:17 #27
akany_ du forstår diplomatiets svære kunst...
Avatar billede coldplay Nybegynder
11. januar 2004 - 00:20 #28
Jeg skal nok komme med en fyldestgørende
redegørelse i løbet af den kommende søndag...

Rolig nu...

Slut herfra indtil videre.... :)
Avatar billede unsigned Nybegynder
11. januar 2004 - 00:49 #29
Det er korrekt at, s = n*(p + qt).

Men så er der en fejl. Du siger:

s(t) = n(t) * (p + qt)

Det korrekte er:

s(t) = n*(p + qt)

og

s = n*(p + qt) <=>

n = s / (p + qt), deraf følger

n(t) = s / (p + qt)
Avatar billede coldplay Nybegynder
11. januar 2004 - 12:58 #30
n: antal opkald

p: pris pr. opkald (kr)

q: minutpris (kr/min)

T: samlet taletid (min)

t: samtaletid pr. opkald (min)

s: samlet udgift (kr)


s = n*p + n*q*t = n*(p + qt)


Spørgsmål: hvordan opnås flest mulige opkald med længst mulig
samtaletid pr. opkald på et taletidskort?

Eksempel: Man har et taletidskort på 100 kr med en opkaldsafgift på
25 øre og minutpris på 4,00 kr.

Hvordan får man mest ud af sine 100 kr. ud fra ovenstående kriterier?

************REDEGØRELSE********************

s(t), p og q er konstanter og n(t) er en funktion. Der er ikke tale om et lineært
problem.

Begrundelse: venstre side er med s(t) konstant og højre side har n(t) som faktor i
begge led. Altså

s(t) = n(t) * (p + qt) <==> n(t) = s(t) / (p + qt) .      1)

Der er klart tale om en hyperbel, hvor:

n(t)-> uendelig for t->0, og

n(t)->0 for t-> uendelig

Det er indenfor disse ekstreme ydergrænser, at der findes netop et og kun et
punkt, hvor både n(t) og t - hver for sig, men naturlig ikke uafhængige af
hinanden - antager hver sit maximum i forhold til hinanden. Det punkt, vi søger
er et punkt som er røringspunkt for en tangent med hældningen -1:

n(t) = s(t) / (p + qt) differentieres mht. t, så

n'(t) = -(s(t)*q) / (p +q*t)^2 .

Med den ønskede tangenthælding har vi så:

(s(t_o)*q) / (p + q*t_o)^2 = 1 <==> (p + q*t_o)^2 = s(t_o)*q , hvor

t_o er røringspunktet 1. koordinat.


Vi tager kvadratroden af sidstnævnte udtryk på begge sider:

s(t_o)*q = (p + q*t_o)^2 ==> sqrt(s(t_o)*q) = p + q*t_o    2)

Nu kan vi bestemme t som tangentens 1. koordinat ud fra ligning 2):

t_o = (( sqrt(s(t_o)*q) ) - p) / q .

Vi omskriver lige ligning 1) og indsætter t_o, så:

n(t_o) = s(t_o) / (p + qt_o) <==> s(t_o) / n(t) = p + q*t_o.  3)

Sammenhold ligning 2) og 3). For optimeringspunktets 1. og 2. koordinat
og kun for dette koordinat er venstresiderne for ligning 2) og 3) ens:

sqrt(s(t_o)*q) = s(t_o) / n(t_o) <==> n(t_o) = s(t_o) / sqrt(s(t_o)*q) .  4)

Ligning 4) kan yderligere reduceres, så:

n(t_o) = s(t_o) / sqrt(s(t_o)*q) <==> n(t_o) = sqrt( s(t_o) / q)

***********************************************
Avatar billede arne_v Ekspert
11. januar 2004 - 13:54 #31
Du sætter differential kvotentien for en ikke diferentierbar funktion
til en tilfældig værdi og løser ligningen.

Sikkert god øvelse i lignings løsning. Men ikke nogen løsning
på problemet.
Avatar billede akany_ Nybegynder
11. januar 2004 - 16:57 #32
Efter hvad jeg kan regne ud er der overhovedet ikke noget svar på dit spørgsmål.
Avatar billede arne_v Ekspert
11. januar 2004 - 16:59 #33
Problem-stillingen er velkendt fra mikroøkonomi. Og en løsning kræver
en nytte-funktion.
Avatar billede unsigned Nybegynder
13. januar 2004 - 06:59 #34
-> coldplay

n: antal opkald
p: pris pr. opkald (kr)
q: minutpris (kr/min)
T: samlet taletid (min)
t: samtaletid pr. opkald (min)
s: samlet udgift (kr)



Som jeg har vist, så er

s(t) = n*(p + qt) og n(t) = s / (p + qt)

De funktioner er kun gyldige som funktioner af en variabel. Hvis vi for eksempel vil beregne udgiften på grundlag n og t, så skal funktionen hedde:

s(t,n) = n*(p + qt)

Hvis vi vil beregne antal opkald, på grundlag t og s, så skal funktionen hedde:

n(t,s) = s / (p + qt)



Så arbejder du med en funktion, der hedder:

n(t) = s(t) / (p + qt)

Indsætter vi s(t) i funktionen, får vi:

n(t) = (n*(p + qt) ) / (p + qt) = n



Med "n(t) = s(t) / (p + qt)" som grundlag, siger du:

  Der er klart tale om en hyperbel, hvor:
  n(t)-> uendelig for t->0, og
  n(t)->0 for t-> uendelig

Det korrekte er (stadig med "n(t) = s(t) / (p + qt)" som grundlag) :

Vi har tidligerer vist at "n(t) = s(t) / (p + qt) = n". Det giver, for t's grænseværdier:

  for n(t) = n,  n(t) -> n, for t->0 og t->uendelig.



Så skriver du:
Det er indenfor disse ekstreme ydergrænser, at der findes netop et og kun et
punkt, hvor både n(t) og t - hver for sig, men naturlig ikke uafhængige af
hinanden - antager hver sit maximum i forhold til hinanden. Det punkt, vi søger
er et punkt som er røringspunkt for en tangent med hældningen -1:

Hvis du vil regne på n og t samtidig, så skal du bruge en funktion af to variable. Det kunne fx være: T(n,t) = n*t.



 
I det følgende differentierer du n(t) med hensyn til t.

Du har: n(t) = s(t) / (p + qt) <=> n'(t) = -(s(t)*q) / (p +q*t)^2

Her differentierer du som om s(t) er en konstant. Men s afhænger af t, så beregningen er forkert, og dermed værdiløs.



Du prøver på at opstille en funktion for n, som funktion af s, p, q og t. Derefter holder du s, p og q konstante og differentierer. Så siger du: Der hvor n'(t) = -1, der er løsningen til mit problem. Men hvad er så specielt ved -1? Jeg kan ikke se noget specielt ved det tal.
Avatar billede coldplay Nybegynder
18. januar 2004 - 21:56 #35
Er det svært at acceptere antallet af mulige opkald n(t) som funktion af tiden?

Altså:

s = n(t)*(p + q*t) <==> n(t) = s / (p + q*t), hvor

s er f.eks s = 100 kr. taletid ( s(t) = 100*t^0 = 100*1) .

Er der ikke tale om en hyperbel, når:

n(t) = s / (p + q*t) (altså på formen f(x) = a / (b + c*x)) ?

************************************************

Tangenthældningen på -1 er noget vrøvl! Hældningen kan
selvfølgelig ikke fastsættes på forhånd...

Ligeledes gælder min påstand om:

n(t) -> uendelig for t ->0, og

n(t) -> 0 for t -> uendelig

som er kun gælder for p = 0.

***************************************************

n(t): antal opkald som funktion af tiden

p: pris pr. opkald (kr)

q: minutpris (kr/min)

t: samtaletid pr. opkald (min)

s: taletidskortets pris (kr)


s = n(t)*p + n(t)*q*t = n(t)*(p + qt)


Spørgsmål: hvordan opnås flest mulige opkald med længst mulig
samtaletid pr. opkald på et taletidskort?

Eksempel: Man har et taletidskort på 100 kr med en opkaldsafgift på
25 øre og minutpris på 4,00 kr.

Hvordan får man mest ud af sine 100 kr. ud fra ovenstående kriterier?

****************LØSNINGSFORSLAG****************

s, p og q er konstanter og n(t) er en funktion.

Altså:

s = n(t) * (p + qt) <==> n(t) = s / (p + qt) .      1)

n(t) har et skæringspunkt på y-aksen for t = 0:

n(0) = s / (p + q*0) = s / p .

Dette skæringspunkt ligger over optimeringspunktet og udtrykker det max.
antal af opkald uden nogen samtaletid overhovedet.

Desuden er der et punkt, som ligger under optimeringspunktet. Dette
punkt gælder for n(t) = 1, altså et opkald og dermed maximalt brug af kortets
taletid:

n(t) = s / (p + q*t) <==>

p + q*t = s / n(t) <==>

t = ((s / n(t)) - p) / q <==>

t = ((s / 1) - p) / q = (s - p) / q .

Gennem disse to punkter (punktet over og punktet under optimeringspunktet) går
der en sekant, hvis hælding svarer til den tangent, som tangerer det søgte
optimeringspunkt. Sekantens og dermed tangentens hælding er givet ved:

((s / p) - 1) / (0 - t_s) = - (((s / p) - 1) / t_s) .    2)

Differentieres ligning 1) fås:

n(t) = s / (p + q*t) ==> n'(t) = - ((s*q) / (p + q*t)^2) .  3)

Ligning 2) er sekantens hældning og ligning 3) er tangentens ditto. Altså:

((s / p) - 1) / t_s = (s*q) / (p + q*t_t)^2 ,      4)

hvor t_s er sekantens 1. koordinat under optimeringspunktet og
t_t er tangentens 1. koordinat for selve optimeringspunktet.

Tilbage står at finde t_t ud fra ligning 4):

((s / p) - 1) / t_s = (s*q) / (p + q*t_t)^2 <==>

(p + q*t_t)^2 = (s*q*t_s) / ((s / p) - 1) ==>

p + q*t_t = sqrt[ (s*q*t_s) / ((s / p) - 1) ]

.
.
.

Sammenhold iøvrigt venstresiden med ligning 1), så kan n(t_t) bestemmes.

n(t) har to asymptoter: en vandret og en lodret. Den vandrette giver sig selv, mens
den lodrette kan findes ved at sætte nævneren i ligning 1 lig 0:

p + q*t = 0 <==> t = -p / q. Altså:

n(t) -> uendelig for t -> -p / q, og

n(t) -> 0 for t -> uendelig.

***********************************************************************
Avatar billede arne_v Ekspert
18. januar 2004 - 22:05 #36
Da antal opkald skal være heltal kan du ikke differentiere.

Det du har er en restriktion - for at kunne finde en optimal løsning
er du nødt til at have personens nytte funktion.

Ja - løsningen afhænger af personen.
Avatar billede coldplay Nybegynder
22. januar 2004 - 14:14 #37
Tak for kommentaren, arne_v.

Der er tale om en funktion, som er kontinuert i hele sin definitionsmængde. Denne defintionsmængde omhandler alle reelle tal, og som konsekvens heraf er muligheden for et resultat med et antal heltallige opkald meget lille.

Har du iøvrigt forsøgt at regne på den bagved liggende matematik, hvis ikke, så synes jeg, at du drager en lidt for hastet konklusion.

Prøv at regn lidt på sagen, og kom gerne tilbage med en kommentar.

I mellemtiden (?) tager jeg mine 185 point tilbage.

Jeg har lige lært hvordan ;-)

Derfor er det ikke noget krav
Avatar billede coldplay Nybegynder
22. januar 2004 - 14:15 #38
Tak for kommentaren, arne_v.

Der er tale om en funktion, som er kontinuert i hele sin definitionsmængde. Denne defintionsmængde omhandler alle reelle tal, og som konsekvens heraf er muligheden for et resultat med et antal heltallige opkald meget lille.

Har du iøvrigt forsøgt at regne på den bagved liggende matematik, hvis ikke, så synes jeg, at du drager en lidt for hastet konklusion.

Prøv at regn lidt på sagen, og kom gerne tilbage med en kommentar.

I mellemtiden (?) tager jeg mine 185 point tilbage.

Jeg har lige lært hvordan ;-)
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester