CCF03252008002

1)    w zadaniu dualnym jest tyle zmiennych, ile nierówności w zadaniu pierwotnym (każdemu warunkowi ZP odpowiada jedna zmienna ZD),

2)    w zadaniu dualnym jest tyle warunków, ile zmiennych w zadaniu pierwotnym,

3)    wagi funkcji celu zadania pierwotnego są wyrazami wolnymi w zadaniu dualnym,

4)    wyrazy wolne zadania pierwotnego są wagami funkcji celu w zadaniu dualnym,

5)    macierz współczynników zadania dualnego jest transpozycją macierzy współczynników zadania pierwotnego,

6)    jeżeli zadanie pierwotne jest na maksimum, to dualne jest na minimum, i odwrotnie.

Zauważmy ponadto, że jeżeli zadanie pierwotne jest przedstawione w postaci standardowej, to zadanie dualne jest zapisywane także w tej postaci. Jeżeli natomiast zadanie pierwotne nie ma postaci standardowej, to podobnie jest z zadaniem dualnym (ZD odbiega na tyle od postaci standardowej, na ile odbiega od niej ZP).

W przypadku ogólnym stosujemy ponadto następujące, dodatkowe reguły tworzenia zadania dualnego:

1)    jeżeli w ZP i-ty warunek jest równością, to odpowiadająca mu zmienna y_; nie ma ograniczeń,

2)    jeżeli w ZP i-ty warunek jest nietypową nierównością, to w ZD zmienna y_t < 0,

3)    jeżeli w ZP na zmienną x, nie nałożono ograniczeń, to j-ty warunek ZD ^:'st równością,

4)    jeżeli w ZP zmienna Xj ^ 0, to w ZD j-ty warunek jest nietypową nierównością.

PRZYKŁAD 2.7

Mamy następujące zadanie pierwotne o postaci standardowej:

*Lx j 4- 3x₂ 4- x₃ -> min, 4xj - 6x₂ + 5x₃ ^ 4, x_{ 4- 2x₂ 4- 4x₃ ^ 7,

W zadaniu dualnym będą oczywiście dwie zmienne y_u y₂ (co zaznaczono przy ZP), a samo zadanie dualne ma postać:

4y_i + ly₂ -* max, 4j>i + y₂ ^ 2,

— 6yi + 2_v₂ ^ 3,

5jZj 4- 4j<₂ ^ 1,

y„ y₂ > 0-

2.4.2

Twierdzenia o dualności

Między rozwiązaniami zadania pierwotnego (2.34) i zadania dualnego (2.35) zachodzą zależności, które można sformułować w postaci następujących twierdzeń:

TWIERDZENIE 1 (o istnieniu)

Jeżeli ZP i ZD mają rozwiązania dopuszczalne, to obydwa mają rozwiązania optymalne. Jeżeli natomiast chociaż jedno z nich nie ma rozwiązania dopuszczalnego, to obydwa nie mają rozwiązań optymalnych.

TWIERDZENIE 2

Jeżeli x₁,x₂,...,x„ jest rozwiązaniem dopuszczalnym zadania pierwotnego (prymalnego), a y_l,y₂,-,y_m — rozwiązaniem dopuszczalnym zadania dualnego, to między wartościami funkcji celu zachodzi nierówność:

n    rn

X Cj^xj < I    (2.36)

i= i    "'=»

Dla rozwiązań dopuszczalnych wartość funkcji celu ZP nie może być większa od wartości funkcji celu ZD.

TWIERDZENIE 3 (o optymalności)

Jeżeli istnieją dwa takie rozwiązania dopuszczalne x₁₍x₂, ...,x„ (ZP) i yi>y₂>->Pm (^ZD)> ^że:

29

Wyszukiwarka

Podobne podstrony:
PROJEKT SOCJALNY „ Człowiek jest tyle wart, ile może dać drugiemu człowiekowi ”Tytuł:
PROJEKT SOCJALNY „ Człowiek jest tyle wart, ile może dać drugiemu człowiekowi”Tytuł:
File0612 Narysuj tyle kółek, ile jest sylab, i tyle kresek, ile jest głosek w nazwach przedmiotów pr
Ćwiczenia dla 5 6 latków  (2) Policz sylaby w nazwach warzyw i owoców oraz zamaluj tyle kratek, il
karta pracyX Ola kończy osiem lat. Narysuj świeczki na torcie, oraz podziel tort na tyle kawałków, i
IMGE59 142 Franęois Truffaut prawdy: film wart jest tyle, ile wart jest ten, kto go zrealizował Nare
Kangurek 2008 zadania 026 Matematyka z wesołym ‘Kangurkiem 10.    Ania i Piotrek mają
karta pracyX Ola kończy osiem lat. Narysuj świeczki na torcie, oraz podziel tort na tyle kawałków, i
skanowanie0027 2 Zadanie 46 Narysuj tyle motyli, ile wskazuje liczba.GD GD Zadanie 47 Pokoloruj na c
skanowanie0063 2 Zadanie 127 Zamaluj tyle koralików, ile wskazuje liczba. 5    -OOOOO
skanuj0057 2 Nazwij obrazek. Zamaluj okienko odpowiadające głosce k. Narysuj tyle kropek, ile jest s
SKMBT?500712270947032 CZĘŚĆ II * DZIAŁANIE Personalizm ten nic tyle jest kolejną ideologią, ile zes

więcej podobnych podstron