Nejednakosti

Неједнакост је релација поретка у скупу реалних бројева (ℝ), са особинама:

1. a ≤ a, рефлексија,
2. (a ≤ b ∧ b ≤ a) ⇒ (a = b), антисиметрија,
3. (a ≤ b ∧ b ≤ c) ⇒ (a ≤ c), транзитивност,

за све a, b, c ∈ ℝ. Строга неједнакост (a < b) нема особине рефлексивности и антисиметрије (1 и 2), а следећа два су примери релације „поретка“ без транзитивности.

1. Пример. На слици лево је магични квадрат 3×3, чији збир бројева у сваком ретку, у свакој колони и обе дијагонале је 15. У првој, другој и трећој колони су постигнути бодови тимова A, B и C у међусобним дуелима. Тако је у три партије A против B у освојеним бодовима било 4:9, 3:5 и 8:1, што значи да је тим A изгубио од B укупним резултатом 1 : 2.

Према томе, прва колона је скор тима A који је резултатом 1 : 2 изгубио од тима B у другој колони. Тим B је изгубио једнаким резултатом 1 : 2 од тима C у трећој колони. Међутим, та табела показује да тим A побеђује тим C резултатом 2 : 1.

Ово је пример нетранзитивности „релације поретка“, јер пораз A ≪ B и пораз B ≪ C не значи пораз A ≪ C. Недоследности ове врсте типичне су у неким ситуацијама (намерно толерисаним) пребројавања гласова по биралиштима, који се затим групишу и заокружују за више нивое. □

2. Пример. Лакша игра „Камен, папир, маказе“, приказана на слици десно, још један је пример нетранзитивности „релације поретка“. Два играча држе сакривену шаку једне руке иза леђа и одједном је оба покажу. Стиснута шака је „камен“, свих прста испружених су „папир“, а испружена само два значе „маказе“.

Правила игре су следећа: играч који је показао камен побеђује оног који формира маказе („камен ломи маказе”), а губи од оног који има папир („папир прекрива камен”), док играч са маказама побеђује играча са папиром („маказе секу папир”). Уколико оба играча покажу исти елемент, исход је нерешен резултат.

Дакле: ... ≪ папир ≪ маказе ≪ камен ≪ папир ≪ ..., што је нарушавање релације транзитивности. □

Многе релације можемо лакше разумети помоћу графова. Ове нетранзитивности биле би кружно повезан граф, где је „лево од“ нетранзитивна релација „поретка“. Наиме, у низу корака у десно доћи ћемо опет до почетног. Недовољно повезан граф, пак, може представљати ситуацију када имамо повезивање a → b и b → c, али немамо везу a → c и, према томе, немамо транзитивност.

Уопште, релацију дефинишемо и као скуп уређених парова. Тада је ρ = {(a, b), (b, c), (a, c)} једноставан пример транзитивне релације која није рефлексивна, нити је антисиметрична.

1. Неједнакости средина

Универзалне неједнакости често се односе на низове и средње вредности њихових чланова. Нека такав један буде низ позитивних реалних бројева x₁, ..., x_n ∈ ℝ, где је природан број n = 1, 2, 3, ... индекс који нумерише и пребројава чланове низа. Тада имамо следеће средине:

• \( \min = \min(x_1, ..., x_n) \) — минимални члан низа;
• \( H = \frac{1}{\frac{1}{x_1} + ... + \frac{1}{x_n}} \) — хармонијска средина;
• \( G = \sqrt[n]{x_1\cdot ...\cdot x_n} \) — геометријска средина;
• \( A = \frac{x_1 + ... + x_n}{n} \) — аритметичка средина;
• \( Q = \sqrt{\frac{x_1^2 + ... + x_n^2}{n}} \) — квадратна средина;
• \( \max = \max(x_1, ..., x_n) \) — максимални члан.

Увек важе неједнакости min ≤ H ≤ G ≤ A ≤ Q ≤ max, а једнакости важе акко x₁ = ... = x_n. Следе докази.

3. Став. Нека су x и y позитивни (реални) бројеви. Тада важе неједнакости:

\[ \min(x, y) \le \frac{1}{\frac{1}{x} + \frac{1}{y}} \le \sqrt{xy} \le \frac{x + y}{2} \le \sqrt{\frac{x^2 + y^2}{2}} \le \max(x, y), \]

где стоје једнакости ако и само ако x = y.

Доказ: Ставимо 0 ≤ x ≤ y, што не умањује општост доказа. Тада је очигледно:

\[ \frac{1}{\sqrt{xy}} \le \frac{1}{x} \le \frac{1}{y}, \] \[ \frac{2}{\sqrt{xy}} \le \frac{1}{x} + \frac{1}{y} \le \frac{2}{y}, \] \[ \min(x, y) \le \frac{1}{\frac{1}{x} + \frac{1}{y}} \le \sqrt{xy} \le \frac{x + y}{2} \le \max(x, y). \]

Такође је \( 0 \le (a + b)^2 = a^2 + 2ab + b^2 \), одакле \( 2ab \le a^2 + b^2 \), па сменом \( a^2 = x\), \( b^2 = y^2 \), налазимо

\[ \sqrt{xy} \le \frac{x + y}{2}, \]

а то је неједнакост геометријске и аритметичке средине (G ≤ A), горе већ доказана. Овде нам треба за:

\[ x^2 + 2xy + y^2 \le 2x^2 + 2y^2, \quad x^2 + y^2 \le y^2 + y^2, \] \[ \frac{x^2 + 2xy + y^2}{4} \le \frac{x^2 + y^2}{2} \le y^2, \] \[ \frac{x + y}{2} \le \sqrt{\frac{x^2 + y^2}{2}} \le \max(x, y). \]

То су преостале неједнакости A ≤ Q ≤ max. Из поступка лако доказујемо да једнакости важе ако и само ако x = y. ∎

1.1. Лево је цртеж круга центра у тачки O ∈ AB и пречника AB = x + y, са полупречником:

OA = OB = OE = r = (x + y)/2.

Тачка C припада кружници, па је троугао ABC правоугли. Из темена правог угла C спуштена је висина CD = h на хипотенузу, тако да је h² = xy. Наиме, из сличних троуглова ADC ∼ CDB следи пропорција h : x = y : h, а отуда наведено h² = xy.

Из конструкције је очигледна неједнакост

\[ \sqrt{xy} \le \frac{x + y}{2}, \]

тј. h ≤ r, а то је неједнакост геометријске и аритметичке средине (G ≤ A), која постаје једнакост ако и само ако x = y.

1.2. На слици десно је иста претходна слика круга, а без тамошњег правоуглог троугла и са додатим другим правоуглим троугловима. И даље остаје аритметичка средина A = (x + y)/2 делова x и y пречника, а \( G = \sqrt{xy} \) као геометријска средина истих.

Додата је хипотенуза Q, чији је квадрат:

\[ Q^2 = \left(\frac{y - x}{2}\right)^2 + A^2 = \] \[ = \frac{x^2 - 2xy + y^2}{4} + \frac{x^2 + 2xy + y^2}{4}, \]

одакле је Q² = (x² + y²)/2, па је Q квадратна средина. Из правоуглих троуглова доле и лево, ове слике, налазимо:

\[ G^2 = b^2 + H^2, \quad H:G = b:\left(\frac{y-x}{2}\right), \] \[ G^2 = H^2 \left[\frac{H}{G}\left(\frac{y-x}{2}\right)\right]^2 + H^2 = H^2\left( \frac{y^2 - 2yx + x^2}{4xy} + 1 \right)^2 = H^2\left(\frac{y + x}{2}\right)^2, \] \[ H = \frac{G}{A} = \frac{\sqrt{xy}}{\frac{y+x}{2}} = \frac{2}{\frac{1}{x} + \frac{1}{y}}, \]

а то је хармонијска средина.

1.3. Ево још једног геометријског примера. Слика лево приказује квадрате страница x и y поравнате на подлози који се бочно се додирују. Доказаћемо неједнакост аритметичке и квадратне средине.

Половине дијагонала су им DE и EC редом \(x/\sqrt{2}\) и \(y/\sqrt{2}\). Троугао DEC је правоугли, ∠C = 90°, па је квадрат хипотенузе:

\[ CD^2 = DE^2 + EC^2 = \] \[ = \left(\frac{x}{\sqrt{2}}\right)^2 + \left(\frac{y}{\sqrt{2}}\right)^2 = \frac{x^2 + y^2}{2}. \]

Међутим, она је дужи крак трапеза ABCD, где је AB ≤ CD, па је \( (x + y)/2 \le \sqrt{(x^2 + y^2)/2} \), а отуда нам неједнакост аритметичке и квадратне средине (A ≤ Q).

1.4. Свака од ових средина повећа се када низ допунимо бројем већим од ње. Тако из x₁x₂ ≤ x₃², када обе стране помножимо са (x₁x₂)², следи (x₁x₂)³ ≤ (x₁x₂x₃)², а отуда вадећи шести корен из обе стране неједнакости \( \sqrt{x_1x_2} \le \sqrt[3]{x_1x_2x_3} \), што можемо писати G₂ ≤ G₃. Подсећам, сви бројеви са којима овде радимо су позитивни реални.

Када је следећи члан n-торке позитивних бројева већи од њихове геометријске средине G_n, тада је:

\[ x_1\cdot ... \cdot x_n \le x_{n+1}^n, \] \[ (x_1\cdot ... \cdot x_n)^{n+1} \le (x_1\cdot ... \cdot x_n)^n x_{n+1}^n, \] \[ \sqrt[n]{x_1\cdot ... \cdot x_n} \le \sqrt[n+1]{x_1\cdot ... \cdot x_n \cdot x_{n+1}}, \] \[ G_n \le G_{n+1}. \]

То важи и за сваки низ позитивних бројева x₁, ..., x_n ∈ ℝ који је неопадајући (свако x_k ≤ x_k+1, редом када k = 1, 2, ..., n-1), или је строго растући (свако x_k < x_k+1).

Аналогно доказујемо за аритметичку средину. Али то можемо и непосредно из претходног, овако:

\[ \ln G_n \le \ln G_{n+1}, \] \[ \frac{1}{n}(\ln x_1 + ... + \ln x_n) \le \frac{1}{n+1}(\ln x_1 + ... + \ln x_{n+1}), \] \[ \frac{a_1 + ... + a_n}{n} \le \frac{a_1 + ... + a_{n+1}}{n}, \] \[ A_n \le A_{n+1}, \]

када је следећи члан a_n+1 низа већи од аритметичке средине A_n претходних. Логаритам базе веће од 1 је растућа функција, тј. из 0 < x < y следи ln x < ln y, па овај доказ вреди након бирања произвољних a_k па сменом a_k = ln x_k.

Аналогно за n-торке хармонијске (H_n) и квадратне (Q_n) средине доказ пронађите сами, а одговарајуће неједнакости за минимум и максимум низова су очигледне. Уосталом, када боље размислите, запазите да је свака од тих неједнакости већ и интуитивно прихватљива. Такође, да средину смањује од ње мањи нови број у низу.

1.5. Докази наведених неједнакости средина, за дуже n-торке позитивних реалних бројева, нису тешки, нити тривијални, али су занимљиви, као што ћемо видети из следећих. У првом наредном видећемо и корисну методу Кошијеве (Augustin Louis Cauchy, 1789-1857, француски математичар) индукције: свако у низу тврђења T_n је тачно акко је тачно за n = 2, затим ако за произвољно n = 1, 2, 3, ... из тачности T_n следи тачност T_2n потом и тачност T_n-1. Тачност је горњих неједнакости за n = 1 очигледна, па их зато не дискутујемо.

4. Став. За позитивне реалне бројеве x₁, x₂, ..., x_n важи неједнакост (G_n ≤ A_n) између геометријске и аритметичке средине

\[ \sqrt[n]{x_1\cdot x_2 \cdot ... \cdot x_n} \le \frac{x_1 + x_2 + ... + x_n}{n}, \]

где једнакост важи ако и само ако x₁ = x₂ = ... = x_n.

Доказ: Доказ радимо методом Кошијеве индукције. Већ смо доказали да за n = 2 став важи (3. став). У другом кораку индукције, претпостављамо да став важи за n чланова и доказујемо да став важи за 2n чланова:

\[ \sqrt[2n]{x_1\cdot x_2 \cdot ... \cdot x_{2n}} = \] \[ = \sqrt{\sqrt[n]{x_1\cdot x_2 \cdot ... \cdot x_n}\cdot\sqrt[n]{x_{n+1}\cdot x_{n+2}\cdot ... \cdot x_{2n}}} \le \] \[ \le \frac{\sqrt[n]{x_1\cdot x_2 \cdot ... \cdot x_n} + \sqrt[n]{x_{n+1}\cdot x_{n+2} \cdot ... \cdot x_{2n}}}{2} \le \] \[ \le \frac12\left(\frac{x_1 + x_2 + ... + x_n}{n} + \frac{x_{n+1} + x_{n+2} + ... + x_n}{n}\right) = \] \[ \frac{x_1 + x_2 + ... + x_{2n}}{2n}. \]

Дакле, доказали смо импликацију \( G_n \le A_n \implies G_{2n} \le A_{2n} \).

Докажимо сада да из G_n ≤ A_n следи G_n-1 ≤ A_n-1. Користимо супституцију

\[ x_n = \frac{x_1 + x_2 + ... + x_{n-1}}{n-1} \]

тако да је

\[ \frac{x_1 + x_2 + ... + x_{n-1} + \frac{x_1 + x_2 + ... + x_{n-1}}{n-1}}{n} = \frac{x_1 + x_2 + ... + x_{n-1}}{n-1}. \]

Затим имамо:

\[ \sqrt[n]{x_1\cdot x_2\cdot ... \cdot x_{n-1} \frac{x_1 + x_2 + ... + x_{n-1}}{n-1}} = \sqrt[n]{x_1\cdot x_2 ... \cdot x_{n-1}\cdot x_n} \le \] \[ \le \frac{x_1 + x_2 + ... + x_n}{n} = \frac{x_1 + x_2 + ... + x_{n-1}}{n-1}. \]

Отуда је:

\[ x_1\cdot x_2\cdot ... \cdot x_{n-1} \frac{x_1 + x_2 + ... + x_{n-1}}{n-1} \le \left(\frac{x_1 + x_2 + ... + x_{n-1}}{n-1}\right)^n, \] \[ x_1\cdot x_2\cdot ... \cdot x_{n-1} \le \left(\frac{x_1 + x_2 + ... + x_{n-1}}{n-1}\right)^{n-1}, \] \[ \sqrt[n-1]{x_1\cdot x_2\cdot ... \cdot x_{n-1}} \le \frac{x_1 + x_2 + ... + x_{n-1}}{n-1}. \]

Дакле, доказали смо и импликацију \( G_n \le A_n \implies G_{n-1} \le A_{n-1} \). Лако се проверава да неједнакост постаје једнакост акко x₁ = x₂ = ... = x_n. Тиме је став доказан. ∎

5. Став. За позитивне реалне бројеве a₁, ..., a_n важи неједнакост (H_n ≤ G_n) између хармонијске и геометријске средине

\[ \frac{n}{\frac{1}{a_1} + ... + \frac{1}{a_n}} \le \sqrt[n]{a_1\cdot \cdot ... \cdot a_n}, \]

где једнакост важи ако и само ако a₁ = ... = a_n.

Доказ: Користимо 4. став и смене a_k = 1/x_k редом за k = 1, ..., n. Добијамо:

\[ \sqrt[n]{x_1\cdot ... \cdot x_n} \le \frac{x_1 + ... + x_n}{n}, \] \[ \frac{1}{\sqrt{a_1\cdot ... \cdot a_n}} \le \frac{1}{n}\left(\frac{1}{a_1} + ... + \frac{1}{a_n}\right), \] \[ \frac{n}{\frac{1}{a_1} + ... + \frac{1}{a_n}} \le \sqrt[n]{a_1\cdot ... \cdot a_n}. \]

Према томе, \( H_n \le G_n \), где једнакост важи акко a₁ = ... = a_n, што је и требало доказати. ∎

6. Став. За позитивне реалне бројеве x₁, ..., x_n важи неједнакост (A_n ≤ Q_n) између аритметичке и квадратне средине

\[ \left(\frac{x_1 + ... + x_n}{n}\right)^2 \le \frac{x_1^2 + ... + x_n^2}{n}, \]

где једнакост важи ако и само ако x₁ = ... = x_n.

Доказ: Нека је \( f(x) = x^2 \). Други извод ове функције је \(f''(x) = 2 > 0 \), па је она конвексна. Отуда

\[ f\left(\frac{x_1 + ... + x_n}{n}\right) \le \frac{f(x_1) + ... + f(x_n)}{n}, \] \[ \left(\frac{x_1 + ... + x_n}{n}\right)^2 \le \frac{x_1^2 + ... + x_n^2}{n}, \]

односно A_n ≤ Q_n, где стоји једнакост акко x₁ = ... = x_n, а то је оно што је требало доказати. ∎

Очигледно је min(x₁, ..., x_n) ≤ H_n и Q_n ≤ max(x₁, ..., x_n) и имамо све доказе ових неједнакости.

7. Пример. Знамо да је свака од страница a, b, c троугла мања од збира остале две. Колики би могао бити средњи количник збира две странице са трећом?

Решење: Проценимо је аритметичком средином тих односа:

\[ \frac13\left(\frac{a+b}{c} + \frac{b+c}{a} + \frac{c+a}{b}\right) \ge \sqrt[3]{\frac{a+b}{c} \cdot \frac{b+c}{a} \cdot \frac{c+a}{b}} \ge \] \[ \ge \sqrt[3]{\frac{2\sqrt{ab}\cdot 2\sqrt{bc} \cdot 2\sqrt{ca}}{cab}} = 2, \]

где су кориштене неједнакости аритметичке и геометријске средине. За минималну средњу вредност испада да су све три странице једнаких дужина. □

2. Линеано програмирање

Под програмирањем ове подразумевамо тражење оптималне вредности циљне функције

g = g(x₁, ..., x_n)

у условима ограничења системом линеарних релација, датих (не)једначинама:

a₁₁x₁ + a₁₂ + ... + a_1nx_n ≷ b₁
a₂₁x₁ + a₂₂ + ... + a_2nx_n ≷ b₂
...
a_m1x₁ + a_m2 + ... + a_mnx_n ≷ b_m

укључујући изоловане x_i ≥ 0. Треба наћи екстрем функције g уз услове наведене системом.

Не умањује општост претпоставка b_j ≥ 0, редом за све j = 1, 2, ..., m, јер ако је неко b_j < 0 помножимо ту једначину са -1. Може се увести и претпоставка да су све ове релације једначине. То постижемо помоћу варијабле вишка y_j = ±(a_jx_j - b_j), где ставимо знак „плус“ ако је у релацији „веће“, а знак „минус“ ако је у релацији „мање“ (енг. slack variable). Број непознатих таквог новог система једначина већи је од броја непознатих полазних релација за број неједначина у тим релацијама. Горњи систем тада можемо писати матрично Ax = b.

2.1. Конвексан скуп у геометрији је подскуп Еуклидовог простора, чије било које две тачке повезује дуж која је сва у њему. На пример, чврста лопта, коцка, купа или ваљак конвексни су скупови, док све што је шупље или има удубљење као полумесец, није конвексно. Конвексни су празан скуп и сав простор, такође пресек сваке колекције конвексних скупова. Отуда следећа аналитичка дефиниција.

Скуп C је конвексан када линијски сегмент између било које две тачке у том скупу лежи у том скупу. Другим речима, (∀x₁, x₂ ∈ C, ∀θ ∈ [0, 1]) θx₁ + (1 - θ)x₂ ∈ C. Уопште, у конвексном скупу C, када имамо низ n = 1, 2, 3, ... тачака x₁, x₂, ..., x_n ∈ C и ненегативних бројева λ₁ + λ₂ + ... + λ_n чији је укупни збир 1, онда је линеарна комбинација λ₁x₁ + λ₂x₂ + ... + λ_nx_n ∈ C.

2.2. У случају линеарног програмирања, тражимо оптимално решење задате линеарне форме

g = c₁x₁ + ... + c_nx_n.

8. Пример. Творница производи моделе M₁ и M₂ неке робе и то помоћу стројева S₁ и S₂. Први модел стројеви раде 2 и 4 часа, за други модел раде 4 и 2 часа. Зарада по комаду ових модела је 300 и 500 дин и треба организовати рад ових стројева да зарада буде што већа.

• Нека је x₁ број израђених јединица модела M₁ на дан.
• Нека је x₂ број израђених јединица модела M₂ на дан.

То значи да је циљна функција зарада

g = 300x₁ + 500x₂,

при чему су релације

\[ \begin{cases} 2x_1 + 4x_2 \le 24 \\ 4x_1 + 2x_2 \le 24 \\ x_1 \ge 0 \\ x_2 \ge 0 \end{cases} \]

Решење сваке од ових неједначина (d, e, f, c) је затворена полураван у (Oxy) правоуглом систему кооридната (x = x₁, y = x₂), њихов пресек решење је све четири. На слици десно, то је конвексан четвороугао са теменима C(0, 0), D(6, 0), E(4, 4) и F(0, 6). Лако је доказати да се тражене екстремне вредности функције g појављују у теменима.

Њене вредности су редом g(C) = 0, g(D) = 1800, g(E) = 3200 и g(F) = 3000. Дакле, оптимум је постигнут у темену E(4, 4), када је x₁ = 4 и x₂ = 4. Tada се на строју S₁ дневно изради 4 комада робе M₁, а на строју S₂ дневно изради 4 примерка робе M₂. Дневна зарада је 3200 дин. □

Приметимо да се конструкцијом праве 300x + 500y = g са произвољним почетним g, на горњој слици, па њеним паралелним померањем добијају праве неизмењене леве стране њене једначине али разним вредностима g. Када једна од тих паралела садржи теме E(4, 4), онда је g = 3200, баш тражене највеће вредности. Свака од осталих паралела која би секла дати четвороугао имала би мање g од максимума, решења задатка.

То је скица опште методе решавања линеарног програмирања помоћу конвексних скупова. Задан је затворен конвексан скуп C у еуклидском простору ℝⁿ с равним рубом и линеарна форма \( g = \sum_j^n c_jx_j \) чије екстремне вредности тражимо на C. У хиперпростору координата x_j мењамо вредности g, али не и друге стране те једначине, паралелно померајући форму (хипер-раван) до руба C на којем ће g узети тражену екстремну вредност. То је опис геометријске итерације која се зове симплексна метода, јер се своди на конвексне скупове који су у једноставнијим случајевима симплекси (најмањи конвексни скупови који обухтавају задате тачке).

Наравно, може се десити да се нека од паралелних (хипер)равнина поклопи са страницом тела C када ће њених бесконачно много тачака све давати исти оптимум, или да (хипер)раван оде у бесконачност када задатак нема коначног решења.

2.3. Симплекс метода је начин ручног решавања модела линеарног програмирања коришћењем вишка (енг. slack) променљивих, табела и водећих варијабли као средства за проналажење екстрема, решења проблема оптимизације. За то су потребни кораци попут:

1. Стандардна форма;
2. Помоћне варијабле;
3. Креирање листе (табеле);
4. Излазне (водеће) варијабле;
5. Прављење нове листе (табеле);
6. Провера оптималности;
7. Идентификација оптимума.

Ево примера задатка за линеарно програмирање симплекс методом помоћу списка (енг. dictionary). Мимимизирати -g уз дате услове:

\[ -g = -x_1 -2x_2 + x_3, \] \[ \begin{cases} 2x_1 + x_2 + x_3 \le 14 \\ -4x_1 - 2x_2 - 3x_3 \ge -28 \\ 2x_1 + 5x_2 + 5x_3 \le 30 \\ x_1, x_2, x_3 \ge 0 \end{cases} \]

Стандардна форма (1) је основно полазиште свих линеарних програма пре решавања. За оптимално решење она има три захтева:

1. мора бити проблем максимизације,
2. сва линеарна ограничења морају бити у неједнакости мање од или једнако,
3. све варијабле су ненегативне.

Ови захтеви су увек задовољиви трансформацијом било ког датог линеарног програма коришћењем основне алгебре и супституција. Стандардна форма је неопходна јер ствара идеалну полазну тачку за што ефикасније решавање Симплекс методе као и других метода решавања проблема оптимизације.

Трансформишемо минимизирајући линеарни програмски модел у максимизирајући опет линеарни програмски модел, множећи леву и десну страну функције циља са -1 и исто радимо са неједнакошћу веће него. Добијамо:

\[ g = x_1 + 2x_2 - x_3, \] \[ \begin{cases} 2x_1 + x_2 + x_3 \le 14 \\ 4x_1 + 2x_2 + 3x_3 \le 28 \\ 2x_1 + 5x_2 + 5x_3 \le 30 \\ x_1, x_2, x_3 \ge 0 \end{cases} \]

Међу релације уводимо помоћне варијабле (2) y₁, y₂ и y₃:

\[ \begin{cases} 2x_1 + x_2 + x_3 + y_1 = 14 \\ 4x_1 + 2x_2 + 3x_3 + y_2 = 28 \\ 2x_1 + 5x_2 + 5x_3 + y_3 = 30 \\ x_1, x_2, x_3, y_1, y_2, y_3 \ge 0 \end{cases} \]

Да бисмо боље разумели решавање задатка табелирањем погледајмо пре тога списак експлицитно писаних помоћних варијабли:

\[ \begin{cases} y_1 = 14 - 2x_1 - x_2 - x_3 \\ y_2 = 28 - 4x_1 - 2x_2 - 3x_3 \\ y_3 = 30 - 2x_1 - 5x_2 - 5x_3 \\ g = 0 + x_1 + 2x_2 - x_3 \end{cases} \]

Променљиве са леве стране су основне варијабле за овај списак; скуп ових променљивих назива се база. У почетном списку основне варијабле су помоћне променљиве, које се мењају након рачунања. Остале варијабле се називају неосновне. Приметите да смо на дну додали променљиву за функцију циља.

Придружено решење добије се када су све неосновне променљиве нуле и резулти су вредности основних променљивих из списка. За горњи списак придружено решење је:

\[ x_1 = x_2 = x_3 = 0, \quad y_1 = 14, \quad y_2 = 28, \quad y_3 = 30. \]

Придружено решење задовољава услове, али можда не позитивност услова. Када оно задовољава и позитивност услова називамо га изводљивим (енг. feasible ) решењем. Овде је оно изводљиво, јер је програм задат таквим, ненегативним бројевима.

Основна идеја симплекс методе је прелазак са списка на списак уз замену основних решења неким не-основним, тако да циљна функција (g) расте сваким кораком и да списак сваким кораком остаје унутар неког изводљивог решења. Ево како бирамо варијабле за те кораке.

Из доње (g) једначине видимо да повећавањем x₁ и x₂ та циљана функција расте, а повећавањем x₃ она опада. Све те три варијабле морају бити позитивни бројеви, па се тада горње y_k смањују до нуле изнад које морају остати. Зато бирамо највећи коефицијент циљане функције, овде је то 2 уз x₂, па добијамо:

\[ \begin{cases} y_1 = 14 - x_2 \\ y_2 = 28 - 2x_2 \\ y_3 = 30 - 5x_2 \\ g = 0 + 2x_2 \end{cases} \]

Да би помоћне варијабле (ипсилони) били позитивни, x₂ може ићи највише до 6, а то ограничава y₃ и зато ту бирамо за водећу, излазну (енг. exiting) варијаблу. Када има више (истих) излазних варијабли, стандардно правило је да се узме прва од њих, она са најмањим индексом. Бирајући x₂ за улазну, а y₃ за излазну варијаблу и уврштавајући x₂ у горње једначине израчунавамо нови списак:

\[ \begin{cases} x_2 = 6 - \frac25 x_1 - x_3 - \frac15 y_3 \\ y_1 = 8 - \frac85 x_1 + 0 + \frac15 y_3 \\ y_2 = 16 - \frac{16}{5}x_1 - x_3 + \frac25 y_3 \\ g = 12 - \frac15 x_1 - 3x_3 - \frac25 y_3 \end{cases} \]

Придружено решење сада је:

\[ x_1 = x_3 = y_3 = 0, \quad x_2 = 6, \quad y_1 = 8, \quad y_2 = 16, \quad g = 12. \]

Поступимо ли сада на исти начин, са x₂ улазном и овде y₁ излазном варијаблом, уврштавајући у горње једначине, добијамо:

\[ \begin{cases} x_2 = 14 - 2x_1 - x_3 - y_1 \\ y_2 = 0 - x_3 + 2y_1 \\ y_2 = -40 + 8x_1 + 5y_1 \\ g = 28 - 3x_1 - 3x_3 - 2y_1 \end{cases} \]

Придружено решење имало би y₃ = -40, што је нарушавање позитивности! Када се то деси знамо да је негде грешка. У изводивом решењу претходног списка могли смо имати x₁ за улазну, а било y₁ или y₂ за излазну варијаблу. Бирајмо y₁ и израчунавамо:

\[ \begin{cases} x_1 = 5 - \frac58 y_1 + \frac18 y_3 \\ x_2 = 4 - x_3 + \frac14 y_1 - \frac14 y_3 \\ y_2 = 0 - x_3 + 2y_1 \\ g = 13 - 3x_2 - \frac18 y_1 - \frac38 y_3 \end{cases} \]

У овој листи сви коефицијенти доњег (g) реда су негативни, па их морамо мењати нулама. То значи да смо завршили са програмирањем и оптимална, максимална вредност је g = 13. Придружено решење:

\[ x_3 = y_1 = y_3 = 0, \quad x_1 = 5, \quad x_2 = 4, \quad x_3 = 0; \quad g = 13 \]

је коначно, оптимално решење.

2.4. Урадићемо опет исти претходни задатак (2.3) сада симплекс методом помоћу табеле (енг. tableau). Поступак је сличан решавању система линеарних једначина Гаусовом методом елиминације, осим што овде не смемо замењивати места редака табеле. Стандардну форму (1) пишемо:

\[ g = x_1 + 2x_2 - x_3, \] \[ \begin{cases} 2x_1 + x_2 + x_3 \le 14 \\ 4x_1 + 2x_2 + 3x_3 \le 28 \\ 2x_1 + 5x_2 + 5x_3 \le 30 \\ x_1, x_2, x_3 \ge 0 \end{cases} \]

Међу релације уводимо помоћне варијабле (2) y₁, y₂ и y₃ и од неједнакости настаје систем једначина, који бисмо могли писати матрично Ax = b. Функцију циља (g) додајемо испод система:

\[ \begin{cases} 2x_1 + x_2 + x_3 + y_1 = 14 \\ 4x_1 + 2x_2 + 3x_3 + y_2 = 28 \\ 2x_1 + 5x_2 + 5x_3 + y_3 = 30 \\ -x_1 - 2x_2 + x_3 + g = 0 \end{cases} \]

Подразумевају се услови ненегативности \( x_1, x_2, x_3, y_1, y_2, y_3 \ge 0 \) и креирамо табелу (3):

x1	x2	x3	y1	y2	y3	g	b
2	1	1	1	0	0	0	14
4	2	3	0	1	0	0	28
2	5	5	0	0	1	0	30
-1	-2	1	0	0	0	1	0

Најмању (негативну) вредност у доњем реду има подвучени број (-2). Његова, друга колона (x₂) је водећа, а највећи број (5) те је у трећем реду и тај је водећи ред. Водећи ред (a_3.) делимо водећим бројем (5) и множимо бројем (a_j2 = 1, 2, -2) те колоне да би низ одузели од текућег низа, а резултат уврштавамо у текући низ (a_j. - a_j2⋅a_3./5 → a_j.). Тако настаје нова табела:

x1	x2	x3	y1	y2	y3	g	b
8/5	0	0	1	0	-1/5	0	8
16/5	0	1	0	1	-2/5	0	16
2/5	1	1	0	0	1/5	0	6
-1/5	0	3	0	0	2/5	1	12

Нова водећа колона (x₁) је са подвученим бројем (-1/5) у доњем реду. Највећи коефицијент (16/5) те колоне дефинише водећи ред (a_2.). Водећи ред делимо највећим бројем и множимо текућим бројем, да би резултате одузимали од текућег реда и уписивали их као нове у текућем реду (a_j. - a_j1⋅a_2.⋅5/16 → a_j.):

x1	x2	x3	y1	y2	y3	g	b
0	0	-1/2	1	-1/2	5	0	0
1	0	5/16	0	5/16	-1/8	0	5
0	1	7/8	0	-1/8	17/5	0	4
0	0	51/16	0	1/16	7/40	1	13

Нема више негативних вредности у доњем реду и кружни процес израчунавања симплекс методом је завршен. Оптимална, максимална вредност g = 13 постиже се са x₁ = 5, x₂ = 4 и x₃ = 0.

9. Пример. Урадимо и 8. пример помоћу симплекс табеле. Дате услове пишемо као систем:

\[ \begin{cases} 2x_1 + 4x_2 + y_1 = 24 \\ 4x_1 + 2x_2 + y_2 = 24 \\ x_1, x_2, y_1, y_2 \ge 0 \\ -300x_1 - 500x_2 + g = 0 \end{cases} \]

Формирамо прву табелу:

x1	x2	y1	y2	g	b
2	4	1	0	0	24
4	2	0	1	0	24
-300	-500	0	0	1	0

Водећа колона је друга (x₂), а водећи ред први (4 је највећи број) који сав делимо са 4 и множимо бројем водеће колоне актуелног реда да бисмо резултат одузели од актуелног реда. Добијамо другу табелу:

x1	x2	y1	y2	g	b
1/2	1	1/4	0	0	6
3	0	-2	0	0	12
-50	0	125	0	1	3000

Водећа колона је прва (x₁), а водећи ред други (3 је највећи број) који сав делимо са 3 и множимо бројем водеће колоне актуелног реда и резултат одузимамо од тог реда. Добијамо трећу табелу:

x1	x2	y1	y2	g	b
0	1	7/12	0	0	4
1	0	-2/3	0	0	4
0	0	100	0	1	3200

Резултат је да ће максимална зарада g = 3200 дин бити остварена када стројеви раде x₁ = x₂ = 4 комада робе дневно. Исто као у геометријском приказу. □

2.5. За програмирање решења у програмском језику Питон, потребно је да имате инсталиран модул cvxopt (ако немате, из Command Prompt позовите python -m pip install cvxopt).

На пример, минимизирати 2x₁ + x₂ уз услове -x₁ + x₂ ≤ 1, x₁ + x₂ ≥ 2, x₂ ≥ 0, x₁ - 2x₂ ≤ 4. Задатак је постављен у Питону лево, а посебно графичко решење је на слици десно:

from cvxopt import matrix, solvers
A = matrix([ [-1.0, -1.0, 0.0, 1.0], [1.0, -1.0, -1.0, -2.0] ])
b = matrix([ 1.0, -2.0, 0.0, 4.0 ])
c = matrix([ 2.0, 1.0 ])
sol=solvers.lp(c,A,b)

     pcost       dcost       gap    pres   dres   k/t
 0:  2.6471e+00 -7.0588e-01  2e+01  8e-01  2e+00  1e+00
 1:  3.0726e+00  2.8437e+00  1e+00  1e-01  2e-01  3e-01
 2:  2.4891e+00  2.4808e+00  1e-01  1e-02  2e-02  5e-02
 3:  2.4999e+00  2.4998e+00  1e-03  1e-04  2e-04  5e-04
 4:  2.5000e+00  2.5000e+00  1e-05  1e-06  2e-06  5e-06
 5:  2.5000e+00  2.5000e+00  1e-07  1e-08  2e-08  5e-08
Optimal solution found.

print(sol['x'])
[ 5.00e-01]
[ 1.50e+00]

На крају тражимо штампање (print) решења, x₁ = 0,5 и x₂ = 1,5. Дакле, g = 2⋅2,5 + 1,5 = 2,5 је најмања вредност датог збира у захтеваним условима. На посебној слици, горе десно, права 2,5 = 2x₁ + x₂ садржи угаону тачку (0,5; 1,5) зелено шрафираног ограничења.

Циљана функција g = c₁x₁ + ... + c_nx_n линеарног програмирања лако се интерпретира као информација перцепције, јер је сама облика збира производа. Тада вектор c = (c₁, ..., c_n) можемо сматрати на пример иницијативама објекта, а вектор x = (x₁, ..., x_n) реакцијама субјекта, под датим ограничењима.

3. Квадратно програмирање

3.1. Квадратно програмирање се разликује од линеарног само по функцији циља

\[ g = \sum_{j=k}^n c_k x_k + \sum_{j,k = 1}^n d_{jk}x_jx_k \]

чији максимум/минимум тражимо под истим условима релација (Линеарно прог.). Једнако као пре, те релације допуњавањем ненегативним помоћним варијаблама (y_ν) биће системи линеарних једначина, матрично Ax = b. Неопходан услов да функција има екстрем је да њени изводи буду нуле:

\[ \frac{\partial g}{\partial x_k} = \sum_{j=1}^n c_j + 2\sum_{j=1}^n d_{jk}x_j = 0, \quad k = 1, 2, ..., n, \]

а то су додатна (линеарна) ограничења. У међувремену погледајмо још неке познате начине.

10. Пример. Тражимо максималну вредност квадратне функције, без ограничења:

g(x₁, x₂) = -2x₁² - 3x₂² + 8x₁ + 24x₁ - 40 =
= 16 - 2(x₁ - 2)² - 3(x₂ - 4)²,

одакле је g(2, 4) = 16 максимална вредност. Просто речено, постоји глобални максимум јер је функција циља строго конкавна.

На други начин, исти се задатак може решити изједначавањем парцијалних извода нулама:

\[ \frac{\partial g}{\partial x_1} = -4x_1 + 8 = 0, \quad \frac{\partial g}{\partial x_2} = -6x_2 + 24 = 0, \]

а отуда x₁ = 2 и x₂ = 4, а отуда g = 16 максимална вредност. □

11. Пример. Тражимо минималну вредност квадратне функције, са ограничењем:

\[ g(x_1, x_2) = (x_1 - 1)^2 + (x_2 - 1)^2, \] \[ x_1 + x_2 \ge 6. \]

Решење: На слици лево је Декартов правоугли координатни систем (Ox₁x₂) са кружницом средишта S(1, 1) минималног полупречника \(r = 2\sqrt{2}\) која представља циљану функцију g.

Њој је најближа тачка T(3, 3) где је дата гранична права x₁ + x₂ = 6 тангира. Дужина до те границе је полупречник r = ST, дуж окомита на дату праву.

Према томе, минимално решење овог квадратног програма је циљна функција:

\[ g(3, 3) =(3 - 1)^2 + (3 - 1)^2 = 8. \]

Ближе нема куд, а даље није минимум. □

3.2. Непрекидна функција f = f(x) која на неком интервалу расте па опада има (локални) максимум. Њен први извод \( f' = \frac{df}{dx}\) на том интервалу редом је позитиван, нула (у тачки максимум), па негативан, што значи да је то функција чија се вредност смањује. Зато је њен други извод \(f'' = \frac{df'}{dx}\) негативан. Непрекидна функција чији други извод на датом интервалу је негативан има (локални) максимум и испупчена је према горе, тј. конкавна је. Обрнуто, ако је други извод сличне позитиван, функција има (локални) мимнимум и удубљена је, тј, конвексна. Са овим запажањем погледајмо следећи пример квадатног програмирања.

У случају диференцијабилне функције више променљивих, њени други парцијални изводи формирају Хесијанову (Hessian) квадратну матрицу H, чије својствене вредности, ламбда из матричне једначине Hx = λx, говоре о конкавности (λ < 0) и конвексности (λ > 0) функције. Познато је како се иста матрица користи за решавање проблема оптимизације.

12. Пример. Проверити да ли функција g(x₁, x₂) = 2x₁ + 3x₂ - x₁² - x₂² има максимум (минимум).

Решење: Тражимо када је функција g конкавна или конвексна. Налазимо друге изводе:

\[ g'_1 = \frac{\partial g(x_1, x_2)}{\partial x_1} = 2 - 2x_1, \quad g'_2 = \frac{\partial g(x_1, x_2)}{\partial x_2} = 3 - 2x_2, \] \[ g_{11}'' = \frac{\partial g_1}{\partial x_1} = - 2, \quad g''_{12} = g''_{21} = 0, \quad g''_{22} = \frac{\partial g_2}{\partial x_2} = - 2. \]

Формирамо Хесијан матрицу ових других извода:

\[ H = \begin{pmatrix} g''_{11} & g''_{12} \\ g''_{21} & g''_{22} \end{pmatrix} = \begin{pmatrix} -2 & 0 \\ 0 & -2 \end{pmatrix}. \]

Из матричне једначине Hx = λx налазимо њене својствене вредности λ₁ = λ₂ = -2. Зато што је ламбда негативно, дати проблем има конкавну циљну функцију g и та функција има максимум. □

3.3. Општи квадратни програм може бити писан матрично:

\[ g(x) = cx + \frac12x^\top H x, \quad Ax \le b, \ x \ge 0, \]

где треба минимизирати функцију g више променљивих, x = (x₁, ..., x_n) са индексом константом n = 1, 2, 3, ..., а c = (c₁, ..., c_n) је вектор, H је симетрична n×n Хесијан матрица, уз додатне услове једнаке као и у случају линеарног програмирања. Претпостављамо да изводљиво решење постоји и да је област решавања ограничена.

Када је циљна функција g(x) стриктно конвексна за све изводљиве тачке, постоји јединствен локални минимум проблема, који је уједно глобални минимум. Довољан услов за строгу конвексност је да је H позитивно одређенa. Иначе, позитивно дефинитна (одређена) матрица је симетрична матрица чија је свака својствена вредност позитивна.

Даље су потребни Кун-Такерови услови да би решење у нелинеарном програмирању било оптимално. Они су довољни за глобални минимум када је H позитивно одређена; иначе, највише што могу дати је да су неопходни.

Искључујући ненегативне услове, Лагранжова функција за квадратни програм је:

\[ L(x, \mu) = cx + \frac12 x^\top Hx + \mu(Ax - b), \]

где је μ вектор са m компоненти. Наводим и Кун-Такерове услове:

\[ \frac{\partial L}{\partial x_j} \ge 0, \ j = 1, ..., n, \quad c + x^\top Q + \mu A \ge 0, \] \[ \frac{\partial L}{\partial \mu_i} \le 0, \ i = 1, ..., m, \quad Ax - b \le 0, \] \[ x_j\frac{\partial L}{\partial x_j} = 0, \quad x^\top(c^\top + Hx + A^\top \mu) = 0. \]

13. Пример. Функција g(x₁, x₂) која се треба минимизирати, уз дате услове:

\[ g(x) = -8x_1 - 16x_2 + x_1^2 + 4x_2^2, \quad x_1 + x_2 \le 5, \ x_1 \le 3, \ x_1 \ge 0, \ x_2 \ge 0. \]

матрично писан проблем је:

\[ c = \begin{pmatrix} -8 \\ -16 \end{pmatrix}, \quad H = \begin{pmatrix} 2 & 0 \\ 0 & 8 \end{pmatrix}, \quad A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \quad b = \begin{pmatrix} 5 \\ 3 \end{pmatrix}. \]

Не решавамо га овде, јер ручне методе данас замењују лако доступне компјутерске. □

3.4. Ево примера решавања квадратног проблема Питоном. Стандардни облик квадратних програма писаних матрично за Питон је:

\[ \begin{cases} \text{minimise} & g(x) = \frac12 x^\top H x + c^\top x \\ \text{subject to} & Gx \le h, \ Ax = b \end{cases} \]

14. Пример. Минимизирати g = 2x₁² + x₂² + x₁x₂ + x₁ + x₂ у условима x₁, x₂ ≥ 0 и x₁ + x₂ = 1.

Решење: У припреми израчунавамо друге изводе да формирамо H и додатне матрице:

\[ H = \begin{pmatrix} 4 & 1 \\ 1 & 2 \end{pmatrix}, \quad c = \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \quad G = \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}, \quad h = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \quad A_{1\times 2} = \begin{pmatrix} 1 & 1 \end{pmatrix}, \quad b = ( 1 ). \]

from cvxopt import matrix, solvers
H = 2*matrix([ [2, .5], [.5, 1] ])
c = matrix([1.0, 1.0])
G = matrix([[-1.0,0.0],[0.0,-1.0]])
h = matrix([0.0,0.0])
A = matrix([1.0, 1.0], (1,2))
b = matrix(1.0)
sol=solvers.qp(H, c, G, h, A, b)
     pcost       dcost       gap    pres   dres
 0:  1.8889e+00  7.7778e-01  1e+00  2e-16  2e+00
 1:  1.8769e+00  1.8320e+00  4e-02  1e-16  6e-02
 2:  1.8750e+00  1.8739e+00  1e-03  2e-16  5e-04
 3:  1.8750e+00  1.8750e+00  1e-05  1e-16  5e-06
 4:  1.8750e+00  1.8750e+00  1e-07  3e-16  5e-08
Optimal solution found.
print(sol['x'])
[ 2.50e-01]
[ 7.50e-01]

Оптимално решење је g(0,25; 0,75) = 1,875. □

4. Посебне неједнакости

Прва од „посебних“ неједнакости је Јенсенова. Она обухвата неколико мање познатих неједнакости, а названа је по данском математичару Јохану Јенсену, који ју је доказао је 1906. године. Из ње се могу изводити рецимо неједнакости аритметичке и квадратне средине (6. став), Чебишевљева неједнакост, или неједнакост Коши-Шварц-Буњаковског.

4.1. Јенсенова неједнакост генерализује тврдњу да секантна линија конвексне функције лежи изнад криве. На следећој слици је граф конвексне функције f = f(x) и њене две тачке са апсцисама x₁ < x₂ које спаја секанта, дуж на којој је узета произвољна тачка апсцисе x = λ₁x₁ + λ₂x₂, при чему услови λ₁, λ₂ ≥ 0 и λ₁ + λ₂ = 1 гарантују да је x₁ ≤ x ≤ x₂. Очигледно је f(λ₁x₁ + λ₂x₂) ≤ λ₁f(x₁) + λ₂f(x₂).

Када је f(x) конвексна (удубљена) функција, онда је g(x) = -f(x) конкавна (испупчена), па непосредно из претходне неједнакости следи λ₁g(x₁) + λ₂g(x₂) ≤ g(λ₁x₁ + λ₂x₂) за конкавне функције.

Реална функција f више варијабли која је на интервалу I два пута диференцијабилна је конвексна ако и само ако f''(x) ≥ 0 за све x ∈ I. Она је на том интервалу конкавна ако и само ако f''(x) ≤ 0 за све x ∈ I.

15. Став Дата је конвексна реална функција f на интервалу I са варијаблама x₁, ..., x_n ∈ I и константама ω₁, ..., ω_n ≥ 0. Тада је

\[ f\left(\frac{\omega_1x_1 + ... + \omega_nx_n}{\omega_1 + ... + \omega_n}\right) \le \frac{\omega_1f(x_1) + ... + \omega_nf(x_n)}{\omega_1 + ... + \omega_n}. \]

Доказ Нека је збир ω₁ + ... + ω_n = ω и ставимо λ_i = ω_i/ω, редом за i = 1, ..., n. Тада се проблем своди на доказ неједнакости

\[ f\left(\sum_{i=1}^n \lambda_ix_i\right) \le \sum_{i=1}^n \lambda_i f(x_i). \]

У случају n = 1 тврђење је тривијално тачно. Даље доказујемо индукцијом. Нека је:

\[ \mu_i = \frac{\lambda_i}{1 - \lambda_n}, \ i = 1, ..., n-1, \quad \sum_{i=1}^n \mu_i = 1 \]

и претпоставимо да је неједнакост тачна за n - 1. Тада је:

\[ \sum_{i=1}^n \lambda_if(x_i) = \left[ \sum_{i=1}^{n-1} (1-\lambda_n)\mu_if(x_i)\right] + \lambda_nf(x_n) \le \] \[ \le (1 - \lambda_n)f\left(\sum_{i=1}^{n-1}\mu_ix_i\right) + \lambda_n f(x_n) \] \[ \le f\left[(1 - \lambda_n)\left(\sum_{i=1}^{n-1} \mu_ix_i \right) + \lambda_nx_n \right] \] \[ = f\left(\sum_{i=1}^n \lambda_i x_i \right). \]

То значи да је неједнакост тачна за n. Тиме је став доказан. ∎

4.2. Коши-Шварцова неједнакост спада међу најважније неједнакости у математици. Неједнакост за збирове открио је Огистен Луј Коши (1821), а за интеграле први је доказао Виктор Буњаковски (1859) и независно од њега нешто касније Херман Шварц (1888).

16. Став. У просторима са скаларним производом за све векторе u и v је |⟨u, v⟩|² ≤ ⟨u, u⟩⋅⟨v, v⟩, где ⟨*, *⟩ представља унутрашњи производ вектора. Еквивалентно, ова Коши-Шварцова неједнакост се помоћу норме вектора може писати у облику |⟨u, v⟩| ≤ ∥u∥ ∥v∥. Једнакост важи акко су вектори паралелни.

Доказ: Ако је v = 0 једнакост очигледно важи (нула-вектор је паралелан сваком вектору). Узмимо да је даље v ≠ 0 и нека је

\[ z = u - \frac{\langle u, v\rangle}{\langle v, v\rangle} v. \]

Тада је:

\[ \langle z, v\rangle = \left\langle u - \frac{\langle u, v\rangle}{\langle v, v\rangle} v, v \right\rangle = \langle u, v\rangle - \frac{\langle u, v\rangle}{\langle v, v\rangle} \langle v, v\rangle = 0, \]

што значи да су вектори z и v узајамно окомити (z⊥v), па можемо применити Питагорину теорему на

\[ u = \frac{\langle u, v\rangle}{\langle v, v\rangle} v + z \]

одакле:

\[ \|u\|^2 = \left|\frac{\langle u, v\rangle}{\langle v, v\rangle}\right|^2 \|v\|^2 + \|z\|^2 = \left|\frac{\langle u, v\rangle}{\|v\|^2}\right|^2 \|v\|^2 + \|z\|^2 = \frac{|\langle u, v\rangle|^2}{\|v\|^2} + \|z\|^2 \ge \frac{|\langle u, v\rangle|^2}{\|v\|^2}, \]

а отуда ∥u∥ ∥v∥ ≥ ⟨u, v⟩, где једнакост важи акко z = 0, акко су векториu и v линеарно зависни. ∎

Коши-Шварцова неједнакост посебно је занимљива када се скаларни производ интерпретира као информација перцепције. Она \(\vec{u}\cdot\vec{v} \le |\vec{u}||\vec{v}|\) тада каже да узајамна информација (субјекта и објекта) није већа од производа интензитета само-информација (учесника). Другим речима, у опажању објекта, субјекат је увек у нечему закинут.

4.3. Јангову неједнакост (William Henry Young, 1863 – 1942, енглески математичар), која говори о производу два броја, не треба мешати са Јанговом конволуционом неједнакошћу.

17. Став Ако су a, b ≥ 0 и p, q > 1 такви да је 1/p + 1/q = 1, тада је

\[ ab \le \frac{a^p}{p} + \frac{b^q}{q}. \]

Једнакост важи ако и само ако a^p = b^q.

Доказ: Тврђење је очигледно тачно за a = b = 0, па даље претпоставимо a, b > 0. Ставимо t = 1/p, а тада и 1 - t = 1/q. Из тога ln(ta^p + (1 - t)b^q) ≥ t ln(a^p) + (1 - t) ln(b^q) = ln(a) + ln(b) = ln(ab), јер је логаритамска функција конкавна Јенсенова неједнакост. Отуда Јангова неједнакости где очигледно важи једнакост акко a^p = b^q. ∎

4.4. Холдерова неједнакост (Otto Hölder, 1859 – 1937, немачки математичар), је основна неједнакост између интеграла и незаобилазно средство за проучавање L^p простора. За реални број p ≥ 1, имамо p-норму, или L^p-норму, вектора x = (x₁, ..., x_n) дефинисану са ∥x∥_p = (∥x₁∥^p + ... + ∥x_n∥^p)^1/p. Еуклидска норма овде је 2-норма, а 1-норма одговара праволинијском растојању. Када p → ∞, норма L^∞ постаје ∥x∥_∞ = max {|x₁|, ..., |x_n|}. Може се показати да ... ≤ ∥x∥_p ≤ ... ≤ ∥x∥₂ ≤ ∥x∥₁.

Када је S мерљив подскуп ℝⁿ са Лебеговом мером, а f и g су функције са реалним или комплексним променљивим на S, тада Холдерову неједнакост пишемо

\[ \int_S |f(x)g(x)|\ dx \le \left(\int_S |f(x)|^p\ dx\right)^{1/p}\left(\int_S |g(x)|^q \ dx\right)^{1/q}. \]

У случају n-торки реалних или комплексних бројева, Холдерова неједнакост је

\[ \sum_{k=1}^n |x_ky_k| \le \left(\sum_{k=1}^n |x_k|^p\right)^{1/p}\left(\sum_{k=1}|y_k|^q\right)^{1/q}. \]

У простору вероватноћа \( (\Omega, \mathcal{F}, \mathbb{P}) \) је 𝔼 оператор очекивања. За реалне или комплексне варијабле X и Y на Ω Холдерова неједнакост је

\[ \mathbb{E}[|XY|] \le \left(\mathbb{E}[|X|^p]\right)^{1/p}\left(\mathbb{E}[|Y|^q]\right)^{1/q}. \]

18. Став. Ако су p, q ∈ [1, ∞] са 1/p + 1/q = 1, у мерљивом простору, тада за све мерљиве реалне или комплексне функције f и g важи неједнакост ∥fg∥₁ ≤ ∥f∥_p ∥g∥_q.

Доказ: Делећи f и g са ∥f∥_p и ∥g∥_q редом, добијамо ∥f∥_p = ∥g∥_q = 1. Даље користимо Јангову неједнакост за производ два броја. Тако је

\[ |f(x)g(x)| \le \frac{|f(x)|^p}{p} + \frac{|g(x)|^q}{q}. \]

Интегралећи (сабирајући) претходне неједнакости, добијамо:

\[ \|fg\|_1 \le \frac{\|f\|_p^p}{p} + \frac{\|g\|_q^q}{q} = \frac{1}{p} + \frac{1}{q} = 1. \]

Отуда тврђење. ∎

Детаљније, мало другачије, овај и још неке доказе имате и у књизи Квантна Механика (1.3.1 Метрички простор, Теорема 1.3.3). Бројеви p и q које она користи су један другом коњугати Холдера. Специјалан случај p = q = 2 своди је на претходну Коши-Шварцову неједнакост. Холдерова неједнакост важи чак и ако је ‖fg‖₁ бесконачан, када је бесконачна и десна страна. Обрнуто, са f у L^p, а g у L^q, постаје fg тачкасти производ у L¹.

4.5. Неједнакост Минковског (Hermann Minkowski, 1864 – 1909, немачки математичар) утврђује да су L^p простори нормирани векторски простори. Када је S мерљив подпростор ℝⁿ, са 1 ≤ p < ∞, а функције f и g елементи тог простора, тада је f + g такође елеменат тог простора и важи неједнакост троугла

∥f + g∥_p ≤ ∥f∥_p + ∥g∥_p

са једнакошћу ако и само ако су функције f и g позитивно линеарно зависне, што ће бити једино када је f = λg за неко λ ≥ 0 или g = 0. Овде се норма задаје са

\[ \|f\|_p = \left( \int_S |f(t)|^p \ dt \right)^{1/p}. \]

Када p → ∞, онда ова норма постаје есенцијални супремум

∥f∥_∞ = ess sup_{x ∈ S} |f(x)|.

Ово се даље прецизира и поопштава. У књизи Квантна Механика (1.3.1 Метрички простор, Теорема 1.3.4) наћи ћете доказ Минковскијеве неједнакости за p ∈ [1, ∞] у мерљивом простору, да за све реалне или комплексне n-торке бројева из S важи

\[ \left( \sum_{k=1}^n |x_k + y_k|^p \right)^{1/p} \le \left( \sum_{k=1}^n |x_k|^p \right)^{1/p} + \left( \sum_{k=1}^n |y_k|^p \right)^{1/p} \]

са једнакошћу акко су низови x = (x₁, ..., x_n) и y = (y₁, ..., y_n) позитивно линеарно зависни, што значи када је x = λy за неко λ ≥ 0 или је y низ нула. Даље погледајмо аналогно томе у случају интеграбилних функција.

19. Став. Ако је p ∈ [1, ∞] у мерљивом простору, тада за све мерљиве реалне или комплексне интеграбилне функције f и g важи неједнакост

\[ \left( \int_S |f(t) + g(t)|^p \ dt \right)^{1/p} \le \left( \int_S |f(t)|^p \ dt \right)^{1/p} + \left( \int_S |g(t)|^p \ dt \right)^{1/p} \]

са једнакошћу акко су функције f и g позитивно линеарно зависне.

Доказ: Прво погледајмо да збир f + g има коначну p-норму, ако је обе функције имају, што следи из:

\[ |f + g|^p \le 2^{p-1}(|f|^p + |g|^p), \]

Ово је тачно, јер је \( h(x) = |x|^p \) конвексна над ℝ⁺ за p > 1. Наиме, због дефиниције конвексности

\[ |\frac12f + \frac12g|^p \le \frac12|f|^p + \frac12|g|^p, \]

па је онда:

\[ |f + g|^p \le \frac12|2f|^p + \frac12|2g|^p = 2^{p-1}|f| + 2^{p-1}|g|. \]

Дакле, имамо коначну p-норму. Ако је она нула, Минковскијева неједнакост тривијално важи, па даље претпоставимо да та норма, ∥f + g∥_p, није нула. Користећи неједнакост троугла па Холдерову, имамо:

\[ \|f + g\|_p^p = \int |f+g|^p \ dt = \int |f + g|\cdot |f + g|^{p-1} \ dt \le \] \[ \le \int (|f| + |g|)|f + g|^{p-1} \ dt = \int |f||f + g|^{p-1} \ dt + \int |g||f + g|^{p-1} \ dt \] \[ \le \left( \left(\int |f|^p \ dt \right)^\frac{1}{p} + \left( \int |g|^q \ dt \right)^\frac{1}{q} \right)\left( \int |f + g|^{(p-1)\frac{p}{p-1}} \ dt \right)^{1-\frac{1}{p}} \] \[ = (\|f\|_p + \|g\|_p)\frac{\|f+g\|_p^p}{\|f+g\|_p}. \]

Из овога следи тражена неједнакост. ∎

4.6. Бернулијева неједнакост. Јакоб из чувене породице швајцарских математичара (Jacob Bernoulli, 1655 - 1705) открио је по њему названу неједнакост

(1 + x)ⁿ ≥ 1 + nx,   n = 1, 2, 3, ...

која се лако доказује и често користи.

Доказ: У првом кораку математичке индукције закључујемо да је Бернулијева релација (очигледно) тачна када n = 1. У другом кораку индукције, претпостављамо да је тачна и за неко n, па доказујемо тачност за n + 1:

(1 + x)ⁿ⁺¹ = (1 + x)ⁿ(1 + x) ≥ (1 + nx)(1 + x) = 1 + nx + x + nx² ≥ 1 + (n + 1)x,

а отуда та Бернулијева неједнакост. ∎

За n > 1, или x ≠ 0, последња релација је строга неједнакост, па видимо да важи једнакост акко n = 1 или x = 0. Бернулијева неједнакост се лако поопштава на све реалне бројеве n ≥ 1 и све x ≥ -1.

4.7. Неједнакост p-норми. У простору реалних ℝⁿ, или комплексних ℂⁿ низова, n-торки задаје се p-норма низа x = (ξ₁, ξ₂, ..., ξ_n) једнакошћу:

\[ \|x\|_p = \left(|\xi_1|^p + |\xi_2|^p + ... + |\xi_n|^p\right)^{1/p}. \]

Показаћемо да је ∥⋅∥_p опадајућа функција по p, за p ∈ (0, ∞), а погледајте и примене (Lp spaces).

20. Став. За (продужени) реални број 1 ≤ p ≤ ∞ и константан низ x = (ξ₁, ξ₂, ..., ξ_n), пресликавање:

\[ p \to \|x\|_p = \left(\sum_{k=1}^n |\xi_k|^p\right)^{1/p} \]

је монотоно опадајуће. Другим речима, из p > r ≥ 1 следи ∥x∥_p ≤ ∥x∥_r.

Доказ: Ако је α₁, α₂, ..., α_n низ позитивних реалних бројева и 0 < m < 1, онда је:

\[ \left(\sum_{k=1}^n \alpha_k\right)^m \le \sum_{k=1}^n \alpha_k^m. \]

То се лако проверава. Отуда, ако је p > r ≥ 1, односно 0 < r/p < 1, стављајући m = r/p и α_k = |ξ_k|^p, биће:

\[ \left(\sum_{k=1}^n |\xi_k|^p\right)^{r/p} \le \sum_{k=1}^n |\xi_k|^p, \]

а отуда тражени резултат. ∎

У просторима ℓ_p бесконачних конвергентних низова (1.11. Примери) не важе неједнакости ставова који следе, али важе строге инклузије ℓ₁ ⊂ ℓ_p ⊂ ℓ_r ⊂ ℓ_∞ када 1 < p < r < ∞ и претходна неједнакост ∥x∥_r < ∥x∥_p.

21. Став. Важи неједнакост ∥x∥₁ ≤ ∥x∥₂√(n) за низове x ∈ ℂⁿ.

Доказ: Користимо Коши-Шварцову неједнакост:

\[ \|x\|_1 = \sum_{k=1}^n |\xi_k| = \sum_{k=1}^n 1\cdot |\xi_k| \le \left(\sum_{k=1}^n 1^2\right)^{1/2} \left(\sum_{k=1}^n |\xi_k|^2\right)^{1/2} = \sqrt{n}\|x\|_2. \]

Тиме је доказ за низове x = (ξ₁, ξ₂, ..., ξ_n) ∈ ℝⁿ завршен. ∎

22. Став. Када је 1 ≤ p ≤ r ≤ ∞ важи неједнакост ∥x∥_p ≤ ∥x∥_r n^{1/p - 1/r} за низове x ∈ ℂⁿ.

Доказ: Користимо Холдерову неједнакост за низове x = (ξ₁, ξ₂, ..., ξ_n):

\[ \sum_{k=1}^n |a_k||b_k| \le \left(\sum_{k=1}^n |a_k|^s\right)^{\frac{1}{s}} \left(\sum_{k=1}^n |b_k|^{\frac{s}{s-1}}\right)^{1-\frac{1}{s}}. \]

Применимо је на |a_k| = |ξ_k|^p, |b_k| = 1 и s = r/p > 1, редом:

\[ \sum_{k=1}^n |\xi_k|^p = \sum_{k=1}^n |\xi_k|^p \cdot 1 \le \left(\sum_{k=1}^n (|\xi_k|^p)^{\frac{p}{r}}\right)^{\frac{p}{r}} \left(\sum_{k=1}^n 1^{\frac{r}{r-p}}\right)^{1-\frac{p}{r}} = \left(\sum_{k=1}^n |\xi_k|^r\right)^{\frac{p}{r}}n^{1-\frac{p}{r}}. \]

Отуда:

\[ \left(\sum_{k=1}^n |\xi_k|^p\right)^{\frac{1}{p}} \le \left(\left(\sum_{k=1}^n|\xi_k|^r\right)^{\frac{p}{r}}n^{1-\frac{p}{r}}\right)^{\frac{1}{p}} = \left(\sum_{k=1}^n |\xi_k|^r\right)^{\frac{1}{r}} n^{\frac{1}{p}-\frac{1}{r}}, \] \[ \|x\|_p \le n^{1/p - 1/r}\|x\|_r, \quad r \gt p. \]

Ово c = n^{1/p - 1/r} je najбоља могућа константа. Тиме је доказ завршен. ∎

Уопште биће ∥x∥₂ ≤ ∥x∥₁ ≤ √(n) ∥x∥₂ и ∥x∥_p ≤ ∥x∥_r ≤ n^{1/r - 1/p} ∥x∥_p када 1 ≤ r < p. Ако користимо Холдерову неједнакост за интеграбилне функције f(x) на домену x ∈ S, рецимо, коначном интервалу S = I = (a, b), претходни став даје ∥f∥_p ≤ |S|^{1/p - 1/r} ∥f∥_r аналогним поступком доказивања. То је неједнакост p-норми за L_p(S) просторе, поред општег ∥x∥_p ≤ ∥x∥_r када 1 ≤ r < p.