Programowanie liniowe

Popyt, podaż, kapitalizacja, rynki finansowe. Mikroekonomia. makroekonomia, finanse itp...
madzia1970
Użytkownik
Użytkownik
Posty: 62
Rejestracja: 18 gru 2006, o 18:45
Płeć: Kobieta
Lokalizacja: Z Polski
Podziękował: 10 razy

Programowanie liniowe

Post autor: madzia1970 » 10 paź 2007, o 19:08

Sprowadźić dany program do postaci gotowej do obliczeń i wyznaczyć pierwsze rozwiązanie dopuszczalne
warunki: min (-2\(\displaystyle{ x_{1}}\)+\(\displaystyle{ x_{2}}\))
4\(\displaystyle{ x_{1}}\)+5\(\displaystyle{ x_{2}}\)≤3
-\(\displaystyle{ x_{1}}\)+3\(\displaystyle{ x_{2}}\)≤2
\(\displaystyle{ x_{1}}\)≥0
\(\displaystyle{ x_{2}}\)≥0
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
abrasax
Gość Specjalny
Gość Specjalny
Posty: 844
Rejestracja: 20 maja 2005, o 13:19
Płeć: Kobieta
Lokalizacja: Zabrze
Podziękował: 1 raz
Pomógł: 161 razy

Programowanie liniowe

Post autor: abrasax » 10 paź 2007, o 21:19

Zadanie trzeba doprowadzić do postaci bazowej - czyli ograniczenia zapisać w postaci równości. W tym przypadku dodamy dwie zmienne swobodne:

\(\displaystyle{ 4x_1+5x_2+x_3=3}\)
\(\displaystyle{ -x_1+3x_2+x_4=2}\)

funkcja celu ma teraz postać:
\(\displaystyle{ min(-2x_1+x_2+0 x_3+ 0 x_4)}\)

pierwsze rozwiązanie bazowe:
\(\displaystyle{ x_3}\) - zmienna bazowa, wartość 3
\(\displaystyle{ x_4}\) - zmienna bazowa, wartość 2
\(\displaystyle{ x_1, \ x_2}\) - zmienne niebazowe, wartość 0

\(\displaystyle{ x=(0,0,3,2)}\)
wartość funkcji celu: \(\displaystyle{ -2 0+0 +0 3+ 0 2=0}\)

kolejne rozwiązania - metda simpleks

madzia1970
Użytkownik
Użytkownik
Posty: 62
Rejestracja: 18 gru 2006, o 18:45
Płeć: Kobieta
Lokalizacja: Z Polski
Podziękował: 10 razy

Programowanie liniowe

Post autor: madzia1970 » 10 paź 2007, o 21:50

Dziękują bardzo

meg58
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 15 paź 2007, o 16:54
Płeć: Kobieta
Lokalizacja: Olsztyn

Programowanie liniowe

Post autor: meg58 » 15 paź 2007, o 17:01

madzia1970 pisze:Sprowadźić dany program do postaci gotowej do obliczeń i wyznaczyć pierwsze rozwiązanie dopuszczalne
warunki: min (-2\(\displaystyle{ x_{1}}\)+\(\displaystyle{ x_{2}}\))
4\(\displaystyle{ x_{1}}\)+5\(\displaystyle{ x_{2}}\)≤3
-\(\displaystyle{ x_{1}}\)+3\(\displaystyle{ x_{2}}\)≤2
\(\displaystyle{ x_{1}}\)≥0
\(\displaystyle{ x_{2}}\)≥0
wydaje mi sie że w pierwszej kolejności powinna być zamiana min na max co wiąże się ze zmianą znaku na przeciwny. Oczywiście po prawej stronie X liczby powinny być z indeksem dolnym
min (-2 x1+ x2)
4 x1+5x2 ≤3
- x1+3 x2 ≤ 2
X1≥0 x2≥0

max (2 x1- x2)
4 x1+5x2 ≤3
- x1+3 x2 ≤ 2
X1≥0 x2≥0
max (2 x1- x2)
4 x1+5x2 +x3=3
- x1+3 x2 +x4=2
X1≥0 x2≥0 x3≥0 x4≥0

Max (2x1-x2+0x3+0x4)
4 x1+5x2 +x3=3
- x1+3 x2 +x4=2
Xi ≥0 i= 1÷4
Powstaje macierz o wymiarach
A= 4 5 1 0
-1 3 0 1
Ostatnio zmieniony 15 paź 2007, o 17:37 przez meg58, łącznie zmieniany 1 raz.

Awatar użytkownika
abrasax
Gość Specjalny
Gość Specjalny
Posty: 844
Rejestracja: 20 maja 2005, o 13:19
Płeć: Kobieta
Lokalizacja: Zabrze
Podziękował: 1 raz
Pomógł: 161 razy

Programowanie liniowe

Post autor: abrasax » 15 paź 2007, o 17:11

a co ma w tym przypadku dać taka zamiana funkcji celu?

meg58
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 15 paź 2007, o 16:54
Płeć: Kobieta
Lokalizacja: Olsztyn

Programowanie liniowe

Post autor: meg58 » 15 paź 2007, o 17:41

abrasax pisze:a co ma w tym przypadku dać taka zamiana funkcji celu?
nasz profesor od ekonometri własnie to zalecał aby zawsze sprowadzać funkcje minimum do funkcji maximum

Awatar użytkownika
abrasax
Gość Specjalny
Gość Specjalny
Posty: 844
Rejestracja: 20 maja 2005, o 13:19
Płeć: Kobieta
Lokalizacja: Zabrze
Podziękował: 1 raz
Pomógł: 161 razy

Programowanie liniowe

Post autor: abrasax » 15 paź 2007, o 17:45

oczywiście, że można, ale w tym zadaniu to nie jest do niczego potrzebne

Słowem "zalecał" a nie bezwzględnie przykazywał. Niektórzy zamieniają max na min, ale i bez tej operacji można sobie doskonale poradzić.

Czy Twoja zmiana funkcji celu wpłynęła na pierwsze rozwiązanie i doprowadzenie zadania do postaci kanonicznej? Taka była treść zadania.

meg58
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 15 paź 2007, o 16:54
Płeć: Kobieta
Lokalizacja: Olsztyn

Programowanie liniowe

Post autor: meg58 » 15 paź 2007, o 17:53

Metoda simpleks wymaga przygotowania PL do obliczeń. Jest to taki program, ż e:
1° funkcja kryterium podana jest w notacji maksimum.
2° warunki ograniczające mają postać układów równań liniowych, zaś jego kolumna wyrazów wolnych
jest nieujemna.
3° wśród kolumn macierzy A występuje blok będący macierzą jednostkową stopnia m (tyle ile jest
wierszy macierzy A).
4° warunek nieujemności zmiennych decyzyjnych dotyczy wszystkich składowych wektora X.
Dany jest program gotowy do obliczeń to znaczy, Ŝe szukamy
maxCX (1)
przy warunkach
AX = b (2)
X � 0 (3)
b � 0, zaś wśród kolumn macierzy A występuje blok będący macierzą jednostkową stopnia m.
Rozwiązanie X spełniające warunek (2) i (3) nazywamy rozwiązaniem dopuszczalnym. Rozwiązanie
optymalne to takie rozwiązanie dopuszczalne dla którego funkcja kryterium CX osiąga maksimum.
Podamy teraz w jaki sposób naleŜy zachować się, jeŜeli nie są spełnione warunki wymienione w
punktach od 1° do 4° włącznie, a chcemy uzyskać program gotowy do obliczeń.
Ad 1°
JeŜeli funkcji kryterium podana jest w notacji minimum czyli
minCX
to zastępujemy tę notację notacją maksimum w następujący sposób
max(-CX )
np.: min(3 5 ) 1 2 x - x
piszemy: max( 3 5 ) 1 2 - x + x

Awatar użytkownika
abrasax
Gość Specjalny
Gość Specjalny
Posty: 844
Rejestracja: 20 maja 2005, o 13:19
Płeć: Kobieta
Lokalizacja: Zabrze
Podziękował: 1 raz
Pomógł: 161 razy

Programowanie liniowe

Post autor: abrasax » 15 paź 2007, o 18:06

Podaj jeszcze autora tej publikacji, to będziemy przerzucać się literaturą

Nie zrozumiałaś polecenia w tym zadaniu. Sformułuj odpowiedź do przedstawionego zadania, to zobaczysz, że moje rozwiązanie i Twoje się pokrywają.

Nie jest prawdą, że algorytm simpleks można stosować tylko i wyłącznie dla zadań maksimum. Tak jak już napisałam wcześniej: niektórzy zalecają zamianę max na min. Czym różnią się te zadania w metodzie simpleks? Jedynie sposobem wyboru zmiennej, którą wyrzucamy z bazy.

Nie mam zamiaru nikogo nawracać, ale nie pisz nieprawdy, że każde zadanie min TRZEBA zamienić na max.

meg58
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 15 paź 2007, o 16:54
Płeć: Kobieta
Lokalizacja: Olsztyn

Programowanie liniowe

Post autor: meg58 » 15 paź 2007, o 18:12

nie jestem w stanie Ci odpowiedzieć bo dopiero sie uczę sie ekonometrii i to zadanie które analizujemy jest na zaliczenie w mojej uczelni. posługiwałam sie przykładem który rozwiazywal profesor zmieniajac tylko dane . Nie staram sie nikogo wprowadzić w błąd . . Nie neguje Twej wiedzy a raczej chyle głowe przed TOBĄ . po prostu nie wiedziałam czy dobrze robilam to zadanie i czy zrozumiałam jak ma być obliczone.

ODPOWIEDZ