Zakładamy, że zadania pierwotne są typu Max.

Ad 1). Niech w zadaniu P1 j- tą nierówność zgodną z typem mnożymy przez liczbę r≠0. Wtedy w zadaniu dualnym j- ta kolumna zostanie pomnożona przez tę samą liczbę r. Zastępując w zadaniu dualnym zmienną yj:=r⁢yj′ otrzymamy ten sam rezultat. Ponadto znak j- tej nierówności zmienia się taj samo jak znak nierówności ryj≥0. W przypadku nierówności niezgodnej z typem lub równania rezultat jest analogiczny.

Ad 2). Niech w zadaniu P1 j- ta nierówność ma postać ∑i=1n⁢ai⁢xi≤b zaś w równoważnym zadaniu P2 będzie zastąpiona parą

⁡∑i=1n⁢ai⁢xi+xn+1=bxn+1≥0⁢.

Wtedy w zadaniach dualnych: W zadaniu D1 zmienna yj≥0 zaś w zadaniu D2 zmienna yj∈R i dochodzi nowa nierówność, wyznaczona przez n+1- szą kolumnę zadania P2, jest nią yj≥0. Zatem otrzymujemy to samo zadanie.

Ad 3,4). Niech w zadaniu P1 j- ta równość ma postać ∑i=1n⁢ai⁢xi=b zaś w zadaniu P2 j- ta równość została zastąpiona parą:

⁡∑i=1n⁢ai⁢xi≤b∑i=1n-ai⁢xi≤-b⁢.

Wtedy w zadaniach dualnych: W zadaniu D1 zmienna yj∈R jest nieograniczona zaś w zadaniu D2 zmienna yj została zastąpiona parą yj+≥0,⁢yj-≥0. Ponadto w zadaniu P2 dodatkowa nierówność ma współczynniki przeciwne do j- tej więc zadanie D2 można uzyskać z zadania D1 podstawiając yj=yj+-yj-⁢0.

Ad 5). Ponieważ każdy automorfizm afiniczny jest złożeniem automorfizmu liniowego i przesunięcia, dowód rozbijemy na dwie części osobno dla automorfizmu liniowego i osobno dla przesunięcia. Przyjmijmy, że zadanie pierwotne ma postać P1=M⁢a⁢x⁢⁢x0=c⁢xT+b0⁢|⁢A⁢xT≤bT. wtedy zadanie dualne ma postać D1=M⁢i⁢n⁢⁢y0=b⁢yT+b0⁢|⁢AT⁢yT=cT,⁢y≥0.

10 Niech f będzie automorfizmem liniowym zadanym macierzą B. Wtedy f⁢xT=B⁢xT i zadanie

Zatem zadanie dualne ma postać

Zadanie D2 powstało z zadania D1 przez operacje elementarne na wierszach ( równaniach ).

20 Niech f⁢x=x+d dla pewnego d∈Rn. Wtedy

Zatem zadanie dualne ma postać

Zadania D1 i D2 są równoważne ponieważ w obszarze dopuszczalnym AT⁢yT=cT co po przemnożeniu przez d daje d⁢AT⁢yT=d⁢cT=c⁢dT.

Niech p i q będą punktami dopuszczalnymi zadań P i Q odpowiednio. Wówczas:

A⁢pT≤bT    AT⁢qT≥cT

p≥0      q≥0

co możemy zapisać jako:

A⁢pT-bT≤θ=00⋮    AT⁢qT-cT≥θ=00⋮

p≥0      q≥0

Mnożąc na krzyż otrzymujemy;

q⁢A⁢pT-bT≤0∈R     p⁢AT⁢qT-cT≥0∈R

Wyliczamy

q⁢A⁢pT≤q⁢bT     p⁢AT⁢qT≥p⁢cT

Co daje

c⁢pT=p⁢cT≤p⁢AT⁢qT=q⁢A⁢pT≤q⁢bT=b⁢qT

Część druga

c⁢pT=b⁢qT to ∀x z obszaru dopuszczalnego c⁢xT≤b⁢qT=c⁢pT⇒p optymalny i z drugiej strony identycznie b⁢yT≥c⁢pT=b⁢qT⇒q optymalny

Przypuśćmy że D nie jest sprzeczne ⇒ istnieje q w obszarze dopuszczalnym zadania D

∀x dopuszczalnego c⁢xT≤b⁢qT⇒P ograniczone

Przypuśćmy że 1) i 2) mają rozwiązania x0 i y0. Wtedy

x0≥0 i y0⁢A≥θ więc y0⁢A⁢x0T≥0. Ale y0⁢A⁢x0T=y0⁢bT<0. Sprzeczność.

Przypuśćmy że 1) nie ma rozwiązania. Stosujemy pierwszą fazę z dwufazowej metody sympleks.

Rozwiązujemy zadanie opisane tablicą 0⁢…⁢01⁢…⁢10AIbT,

gdzie zapisane wierszami A=w1w2⋮wt i bT=b1b2⋮bt.

Końcowa tablica ma postać d1⁢…⁢dnk1⁢…⁢ktb0A′Db′⁢T, gdzie
wiersz d1⁢…⁢dn≥0 i b0<0. Ale wiersz ten jest kombinacją liniową wierszy macierzy A. Oznacza to, że istnieje ciąg y=y1,y2,…,yt taki, że d1⁢…⁢dn=∑i=1t⁢yi⁢wi oraz b0=∑i=1t⁢yi⁢bi. Otrzymaliśmy rozwiązanie 2) y⁢A≥0∧b⁢yT<0.

Niech B=w1w2⋮wj będzie macierzą pochodzącą od pierwszych j nierówności. Wówczas p nie jest punktem optymalnym wtedy i tylko wtedy gdy kiedy istnieje wektor α taki, że p+α∈W i x0⁢p+α>x0⁢p. Ponieważ długość wektora α nie gra roli to tylko j pierwszych nierówności opisujących W ma znaczenie. Przekształćmy warunki:

⁡w1∙p+α⁢≤b1=w1∙pw2∙p+α⁢≤b2=w2∙p⋮wj∙p+α≤bj=⁢wj∙p⁢

c∙p+α>c∙p do:

B⁢αT≤0 i c⁢αT>0.

Przyjmując oznaczenia A=BT i y=-α otrzymujemy:

y⁢A≥0∧c⁢yT<0 czyli drugi układ z lematu Farkasa.

A zatem układ A⁢xT=cT∧x≥0 nie ma rozwiązań. Oznacza to, że nie istnieje ciąg liczb nieujemnych r1≥0,r2≥0,…,rj≥0 taki, że dla x=r1,r2,…,rj x⁢B=c czyli c≠∑i=1j⁢ri⁢wi.

Przyjmijmy, że zadanie pierwotne P:

M⁢a⁢x⁢⁢x0=c⁢xT⁢|⁢A⁢xT≤bT ma punkt optymalny p taki, że wi∙p⁢=bi, dla i=1,2,…,j oraz wi∙x⁢<bi, dla i>j, gdzie A=w1w2⋮wt∈Rtn. Wówczas na mocy poprzedniego twierdzenia istnieje ciąg liczb nieujemnych r1≥0,r2≥0,…,rj≥0 taki, że c=⁢∑i=1j⁢ri⁢wi.

Zadaniem dualnym jest D: M⁢i⁢n⁢⁢y0=b⁢yT⁢|⁢AT⁢yT=cT,⁢y≥0.

Niech q=r1,r2,…,rj,0,0,…,0∈Rt. Wówczas q≥0

i q⁢A=r1,r2,…,rj,0,0,…,0⁢w1w2⋮wt=∑i=1j⁢ri⁢wi=c. Więc AT⁢qT=cT, co oznacza, że q jest punktem dopuszczalnym zadania D.

Ale y0⁢q=b⁢qT=∑i=1t⁢bi⁢ri=∑i=1j⁢bi⁢ri=∑i=1j⁢wi⁢pT⁢ri==∑i=1j⁢ri⁢wi⁢pT=c⁢pT=x0⁢p.

Teraz ze słabego twierdzenia o dualności wynika optymalność punktu q.

Niech p będzie punktem optymalnym zadania P. Wówczas na mocy silnego twierdzenia o dualności (twierdzenia 8.5) istnieje rozwiązanie q optymalne dla zadania D. Podobnie jak w dowodzie słabego twierdzenia o dualności ( twierdzenie 8.3) uzyskujemy podwójną równość.

q⁢bT=q⁢A⁢pT=c⁢pT.

Z pierwszej wyciągając q przed nawias otrzymujemy q⁢A⁢pT-bT=0,

zaś z drugiej wyciągając pT przed nawias otrzymujemy q⁢A-c⁢pT=0.

Podkreślmy, jeżeli p jest punktem optymalnym zadania P a q jest punktem optymalnym zadania D to spełnione są warunki równowagi q⁢A⁢pT-bT=0 i q⁢A-c⁢pT=0.

Przypuśćmy, że zachodzą warunki 1) i 2)

wtedy z  1) otrzymujemy qT⁢A⁢p=bT⁢q

2) otrzymujemy cT⁢p=qT⁢A⁢p. Zatem

⇒bTq=cTp i na mocy słabego twierdzenia o dualności p i q optymalne.

Ad 1,2) Jeżeli qj>0 to j - tą nierówność zadania P jest zgodna z typem co daje qj⁢wj⁢pt-bj≤0. Zaś gdy qj< to j - tą nierówność zadania P jest niezgodna z typem co daje qj⁢wj⁢pT-bj≤0. (wj oznacza j-ty wiersz macierzy A).

Teraz q⁢A⁢pt-bT=∑j=1t⁢qj⁢wj⁢pT-bj=0 jest sumą liczb niedodatnich. Oznacza to, że każdy składnik musi być zerem czyli qj=0 lub wj⁢pT=bj. Daje to warunki 1) i 2).

Punkty 3) i 4) można analogicznie wyprowadzić z drugiego warunku równowagi.