Programowanie liniowe - zmienne znaczenie dual simplex?

Question

Właśnie nauczyłem się prostego sposobu rozwiązywania programów liniowych i próbuję zrozumieć, co reprezentuje problem podwójny.

Rozumiem mechanikę rozwiązywania podwójnego problemu - nie potrzebuję pomocy w tym zakresie. Czego nie mogę uzyskać (nawet po przeczytaniu o nim na Wikipedia) jest rzeczywiste znaczenie zmiennych y w podwójnym.

chciałbym dać przykład razem ze zmiennymi znaczeń w pierwotnej problemu, a co ja zorientowali się, z podwójnym, i zapytać kogokolwiek na tyle uprzejmy, aby wyjaśnić znaczenie w podwójnej:

Primal:

max z = 3*x1 + 5*x2 

subject to: 
      x1   <= 4 
       2*x2 <= 12 
     3*x1 + 2*x2 <= 18 

     x1, x2 >= 0 

W pierwotnej problemu x1 i x2 się ilości produktów i B mają być produkowane. i to odpowiednio ich ceny sprzedaży jednostkowej. Produkty są produkowane na 3 maszynach, M1-M3. Aby wyprodukować pierwszy produkt, potrzebna jest godzina pracy na M1 i 3 godziny na M3. Aby wyprodukować drugą, dwie godziny pracy są potrzebne zarówno na M2 i M3. Maszyny M1, M2, M3 może pracować dla maksymalnie 4, 12 i godzin, odpowiednio. Wreszcie, nie mogę wyprodukować ujemnej ilości żadnego z produktów.

Teraz mogę ustawić podwójny problem:

min z = 4*y1 + 12*y2 + 18*y3 

subject to: 
      y1   + 3*y3 >= 3 
        y2 + 2*y3 >= 5 

      y1, y2, y3 >= 0 

Teraz jedyną rzeczą, myślę, że mogę dowiedzieć się, że ograniczenia myśli: - za godzinę pracy na M1 i 3 godziny na M3, powinienem dostać zapłaci co najmniej 3 jednostki pieniężne - przez dwie godziny pracy na M2 i 2 godziny na M3, powinienem dostać zapłaci co najmniej 5 jednostek pieniężnych

Ale po prostu nie mogę otoczyć się znaczeniami zmiennych y1 i y2. Kiedy w końcu wykonuję minimalizację, wynik w postaci z jest taki sam w pierwotnym (chociaż pierwotny w zwiększaniu dolnej granicy wyniku, podczas gdy dual zmniejsza górną granicę), ale jaka jest funkcja celu podwójnego problem składa się z?

Answer 1

Obiektywną funkcją urządzenia Dual jest zminimalizowanie kosztu Koszt/godzina z 3 maszyn (zasobów).

Zatem funkcja celu dualnego za (4*y1 + 12*y2+ 18*y3) można odczytać jako:

Minimize 4*(cost/hour of Machine1) + 12*(cost/hour of M2) + 18*(cost/hr of M3) 

Od Primal czynienia z maksymalizacji zysków z produkcji, Podwójny mogą być traktowane jako minimalizacja produkcji koszty dla firmy.

(To czasami pomaga myśleć o firmie „wynajem” maszyn M1, M2 i M3). Jeśli mają zamiar wynająć go, co jest najbardziej że powinni płacić [$/h] dla każdej maszyny i nadal produkować z zyskiem x1 i x2?

Znaczenie twoich podwójnych zmiennych y1, y2, and y3 to koszt posiadania/wynajmu na godzinę.

Zmienne o podwójnym problemie y są często nazywane "cenami cienia" zasobów.

Od szukasz wgląd felg bliźniaczych zrozumienie:

1. Jeden trick jest, aby zmniejszyć wymiar podwójny. (Wyobraź sobie, że była tylko jedna Maszyna M1.) Teraz sformukuj podwójną i spróbuj zrozumieć funkcję celu i ograniczenia.
2. Pomaga myśleć w kategoriach "kosztów alternatywnych" w postaci . Jeśli firma produkcyjna musiała wypożyczyć maszyny (zasoby), jaką cenę/godzinę powinna zapłacić? Ewentualnie, gdyby istniało wiele innych (opłacalnych) produktów, przy jakim koszcie/godzinie maszyny zostaną przydzielone do X1 i X2 zamiast do wytwarzania tych innych produktów.
3. Należy pamiętać, że nie wszystkie dwojaki można łatwo "zrozumieć". Można jednak poczuć wiele podwójnych ograniczeń, patrząc na odpowiednią zmienną w prime. Podobnie, możesz uzyskać wgląd w podwójną zmienną, badając odpowiednie podstawowe ograniczenie.