Maandelijks archief: mei 2018

Extremumbepaling zonder afgeleide

Geplaatst op door

Bij een extremumvraagstuk denken we al snel aan het berekenen van de afgeleide functie. Maar sommige extremumproblemen kunnen ook opgelost worden met een methode die geïnspireerd is door de lineaire programmatie. We spreken van niet-lineaire programmatie.

We bespreken een voorbeeld: Bepaal de afmetingen van de rechthoek met maximale oppervlakte waarvan de omtrek constant ( =2a) is.

Noem x en y de afmetingen van de rechthoek. Dan zoeken we naar het maximum van f(x,y)=xy onder de randvoorwaarden:
\begin{cases} x>0 \\ y>0\\ 2(x+y)=2a \end{cases}

Het ‘gunstig gebied’ is het lijnstuk AB. De niveaulijnen zijn rechthoekige hyperbolen van de vorm y=\frac{k}{x}.
We zien enkele van die hyperbolen getekend, voor k=1 ( rood), voor k=4 (blauw). We gaan op zoek naar die hyperbool die nog net raakt aan het lijnstuk AB. Daarvoor moet het stelsel : \begin{cases} xy=k\\ x+y=a \end{cases} een dubbele oplossing hebben.  Met andere woorden de vergelijking x^2-ax+k=0 heeft een dubbele oplossing. Hiervoor moet de discriminant nul zijn : D=a^2-4k=0 of k=\frac{a^2}{4}. Die dubbele wortel is dan x=\frac{a}{2}. Voor een maximale oppervlakte moeten dus lengte en breedte allebei gelijk zijn aan x=\frac{a}{2}.

De Euler-phi functie

Geplaatst op door

De Euler-phi functie, ook wel totiënt functie of indicator genoemd, telt het aantal positieve natuurlijke getallen kleiner dan of gelijk aan n, die onderling ondeelbaar zijn met n. Notatie: \varphi(n).

Zo is bijvoorbeeld \varphi(10)=4, want de enige getallen die onderling ondeelbaar zijn met 10 en kleiner zijn dan 10, zijn 1,3,7 en 9.

Enkele eigenschappen:

  • \varphi(1)=1.
  • Als p een priemgetal is dan is \varphi(p)=p-1.
  • Als p een priemgetal is dan is \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).
  • Als n=p_1^{k_1}.p_2^{k_2}.\cdots.p_r^{k_r} de priemontbinding is van n, dan geldt \varphi(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1). Dit kan je ook schrijven als :

        \[\varphi(n)= n.\prod_{p|n}(1-\frac{1}{p})\]

    Hierbij doorloopt p alle priemdelers van n.

  • \sum_{d|n}\varphi(d)=n
  • De indicator geeft ook de omvang aan van de multiplicatieve groep van natuurlijke getallen modulo n

Lineaire programmatie

Geplaatst op door

Een mooie toepassing op de studie van lineaire vergelijkingen en ongelijkheden met 2 onbekenden is de lineaire programmering ( LP). Het gaat hier over  optimaliseringsproblemen waarin de doelfunctie en de randvoorwaarden allen lineair zijn. De methode van de lineaire programmering werd in 1939 voor het eerst door de Sovjet-Russische wiskundige Leonid Kantorovitsj besproken in zijn boek “Wiskundige methoden in de organisatie en planning van de productie“.

Mede voor dit werk kreeg Kantorovitsj in 1975 de Nobelprijs in de Economie. Bekijken we eens een voorbeeld:

Bepaal de extreme waarden van f(x,y)=3x+y met als randvoorwaarden

(1)   \begin{equation*} f(k)= \begin{cases} x \geq 0 \\y \geq 0 \\2x+3y \leq 6 \end{cases} \end{equation*}

Eerst bepalen we grafisch de koppels (x,y) die aan de randvoorwaarden voldoen. Dit gebied noemen we het aanvaardingsgebied. We vinden een rechthoekige driehoek ( donkerblauw gekleurd)
Vervolgens worden enkele niveaulijnen van de functie f(x,y) getekend. Dit zijn lijnen die alle punten (x,y), met een zelfde functiewaarde, met elkaar verbinden. Voor een lineaire functie f zijn deze niveaulijnen altijd evenwijdige rechten. Bij het zoeken van de extreme waarden voor f moeten we rekening houden met de randvoorwaarden. Grafisch betekent dit dat de lijnen door het aanvaardingsgebied moeten gaan. In onderstaande tekening hebben we 3x+y=0 en 3x+y=2 getekend ( rode rechten). Maar 3x+y=9 ( groene lijn ) is die lijn, onder alle evenwijdige lijnen, die het aanvaardingsgebied het meest naar rechts snijdt. Bijgevolg is 9  de maximale waarde voor de functie f onder de gegeven randvoorwaarden.

 

De Chinese reststelling

Geplaatst op door

Naast lineaire congruenties , kan je ook werken met stelsels van lineaire congruenties. Zoals bijvoorbeeld:

Volgens de Chinese reststelling geldt dan: Als elke a_i en m_i onderling ondeelbaar zijn en als alle m_i twee aan twee onderling ondeelbaar zijn, dan heeft dit stelsel een unieke oplossing modulo m_1.m_2.\cdots.m_n.

Los op:
\begin{cases} x\equiv 2 \text{ mod }5 \\3x\equiv 1 \text{ mod }8 \end{cases} of  \begin{cases} x\equiv 2 \text{ mod }5 \\x\equiv 3 \text{ mod }8 \end{cases}

Dit betekent dat x=2+5k=3+8l. Dus 5k \equiv 1 \text{ mod } 8 of k \equiv 5 \text{ mod } 8. Hieruit volgt dat k=5+8p en dus is x=2+5(5+8p)=27+40p.

De unieke oplossing van het gegeven stelsel is x=27 \text{ mod } 40.

Lineaire congruenties

Geplaatst op door

Naast lineaire vergelijkingen , kunnen we ook lineaire congruenties bekijken:

    \[ax \equiv b \text{ mod } m \text{ met } a,b,m\in \mathbb{Z}\]

Hier is de vraag of er een gehele x te vinden is zodat  ax-b deelbaar is door m. Het is duidelijk dat als x_0 een oplossing is, dan zijn alle getallen uit de restklasse x_0 \text{ mod } m ook oplossingen. De oplossingsverzameling verandert ook niet als we a en b veranderen in andere getallen uit hun restklasse mod m. Onder een oplossing van een lineaire congruentie verstaat men dus een restklesse mod m.

  • Wanneer is een congruentie oplosbaar?  Dat is zo als en slechts als de grootste gemene deler van a en m een deler is van b. Als a en m onderling ondeelbaar zijn, bestaat het inverse element van a mod m en is dus x=a^{-1}b \text{ mod } m. Als de grootste gemene deler d van a en m niet 1 is , dan delen we eerst door d en dan krijgen we vorige situatie.
  • In het geval dat ggd(a,m) = 1 hebben we een unieke oplossing. Als echter ggd(a,m) = d , dan hebben we d oplossingen. We krijgen immers 1 oplossing mod \frac{m}{d} en deze geeft precies volgende verschillende restklassen mod m: x_0, x_0+\frac{m}{d},x_0+2\frac{m}{d},\cdots, x_0+(d-1)\frac{m}{d}.

Los op : 6x \equiv 8 \text{ mod }10 .

  • Delen door de ggd(6,10) = 2 geeft 3x \equiv 4 \text{ mod } 5 .
  • Omdat 3.2 = 6 \equiv 1 \text{ mod } 5 is 3^{-1} =2
  • En dus is x\equiv 2.4 \equiv 3 \text{ mod } 5.
  • Alle oplossingen zijn dus de restklassen 3 en 8 modulo 10. De oplossingsverzameling is:

        \[\{3+10k, 8+10l \text{ met } k,l\in \mathbb{Z}\}\]