Programowanie liniowe

[madzia1970]

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

[abrasax]

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]

Dziękują bardzo

[meg58]

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

[abrasax]

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

[meg58]

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

[abrasax]

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]

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

[abrasax]

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]

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.