Badania operacyjne

Temat: Optymalizacja liniowa - program SOLVER z MS Excel 

Program Solver z Microsoft Excel może służyć do rozwiązywania zadań programowania liniowego (ZPL) oraz  zadań całkowitoliczbowego programowania liniowego (ZPLC). Aby ułatwić zrozumienie zasad posługiwania się tym narzędziem, w instrukcji zostanie pokazana droga od sformułowanego ZPL do uzyskania jego optymalnego rozwiązania. Instrukcja ta ma za zadanie tylko ułatwić posługiwanie się programem w czasie laboratorium i nie powinna być traktowana jako instrukcja do ćwiczenia. Wyjaśnia sposoby wpisywania wcześniej sformułowanego zadania, a nie sposób jego formułowania. Postać graficzna ilustracji zależy od wersji programy Ms Excel (oraz od wersji Windows).

Przykładowe zadanie programowania liniowego:

Zapisanie zadania w arkuszu:

Zadanie z p. 1 można zapisać w arkuszu jak na poniższym rysunku:

W poszczególnych komórkach lub zakresach komórek umieszczono następujące wielkości:

C3:D3 – zmienne problemu (wpisano wartości początkowe, równe 1; będą one zmieniane przez Solver);

D6 – funkcję celu (w komórce wpisano formułę wyznaczającą wartość funkcji celu dla zmiennych z C3 i D3);

D9:D12 – lewe strony ograniczeń (wpisano odpowiednie formuły wyznaczające ich wartości dla zm. z C3 i D3);

E9:E12 – prawe strony ograniczeń (wpisano ich wartości stałe).

W komórkach A2:C2, A3, A6, A8:A12, D5 oraz D8:E8 umieszczono nazwy wyrażeń i zmiennych (tekst).

Zdefiniowanie problemu w Solverze:

Zaznaczyć komórkę zawierającą wartość optymalizowanej funkcji celu.

Z menu Narzędzia wybrać polecenie Solver. Zostaje wyświetlone okno o nazwie
Solver-Parametry, składające się z następujących pól:

Komórka celu - adres bezwzględny komórki zawierającej wartość optymalizowanej funkcji celu ($D$6 w arkuszu z p. 2); jeżeli komórka ta została zaznaczona przed wywołaniem opcji Solver, to adres ten jest wskazywany w oknie dialogowym; można go także wpisać lub wskazać myszą.

Równa - trzy przyciski „radiowe” umożliwiające wybranie jednego z trzech wariantów optymalizacji funkcji celu: Maks - maksymalizacja, Min - minimalizacja, Wartość - nadanie funkcji celu określonej wartości.

Komórki zmieniane - zakres komórek, których wartości Solver będzie zmieniać w czasie optymalizacji; komórki te zawierają wartości zmiennych ZPL (zakres komórek można wpisać lub wskazać myszą); w przykładzie jest to zakres B3:C3, zaznaczony w oknie jako $B$3:$C$3.

Warunki ograniczające - warunki ograniczające występujące w zadaniu; przycisk Dodaj - definiowanie nowych warunków ograniczających, przyciski Zmień, Usuń - po zaznaczeniu odpowiedniego warunku, jego zmiana lub usunięcie.

Zdefiniować warunki ograniczające: W polu Warunki ograniczające okna
Solver - Parametry przycisnąć przycisk Dodaj. Zostanie wyświetlone okno o nazwie
Dodaj warunek ograniczający, składające się z następujących pól:

Adres komórki - adres komórki, której wartość ma być ograniczona; można tu wpisać lub wskazać myszą zarówno adres pojedynczej komórki, jak zakres komórek;

pole operatora - operator ograniczający wartość komórki lub określający relację między nią a wartością innej komórki, możliwe operatory: <=, = , >=, int - liczba całkowita, bin - liczba ze zbioru {0,1}.

Warunek ograniczający - warunek ograniczający komórkę; może nim być liczba, adres komórki, zakres komórek lub formuła (adres komórki i zakres komórek można wskazać myszą).

Po zdefiniowaniu warunku ograniczającego można:

przystąpić do definiowania następnego warunku - przycisk Dodaj,

zatwierdzić wszystkie dotychczasowe warunki - przycisk OK,

zrezygnować - przycisk Anuluj.

Przykładowy wygląd okna Solver - Parametry po zdefiniowaniu zadania jest przedstawiony poniżej:

Uwaga. Warunki ograniczające sformułowano tu w odniesieniu do zakresów komórek.

Rozwiązywanie problemu:

Nacisnąć przycisk Rozwiąż w oknie Solver - Parametry. Od tego momentu Solver rozpoczyna poszukiwania optymalnego rozwiązania.

Jeżeli Solver znajdzie rozwiązanie, zostaje wyświetlone okno Solver - Wyniki i komunikat stwierdzający znalezienie rozwiązania. W oknie znajdują się dwie opcje:

Przechowaj rozwiązanie - komórki zmiennych będą miały przypisane znalezione wartości,

Przywróć wartości początkowe - komórki zmiennych zachowają wartości, które miały przed rozpoczęciem rozwiązywania.

Dodatkowo w polu Raporty można określić, jakie raporty z wynikami mają być utworzone na osobnym arkuszu.

Jeżeli Solver nie znajdzie rozwiązania, podaje odpowiedni komunikat, z którego można wywnioskować, co jest tego przyczyną, i ewentualnie usunąć błąd albo zmienić parametry Solvera.

Przy ponownym rozwiązywaniu tego samego problemu Solver pamięta strukturę zadania, tj. położenie zmiennych (komórek zmienianych); funkcji celu i ograniczeń. Przy wielokrotnym rozwiązywaniu wariantów tego samego zadania, różniących się np. wartością jednego parametru, można po zmianie parametru wywołać Solver i od razu przystąpić do rozwiązywania problemu. Proces rozwiązywania oczywiście trzeba powtórzyć, gdyż zmiany wartości niektórych komórek arkusza wywołane wprowadzeniem przez nas nowej wartości zmienianego parametru odnoszą się do poprzedniej wartości zapamiętanego rozwiązania (zapamiętanego w komórkach zmienianych), natomiast Solver musi dopiero wyznaczyć nowe rozwiązanie odpowiadające nowej wartości parametru.

Uwagi:

Uwaga, przy rozwiązywaniu zadań liniowych warto poinformować Solver, że rozwiązywane zadanie jest liniowe. W tym celu należy nacisnąć przycisk Opcje w oknie dialogowym Solver - Parametry i zaznaczyć (uaktywnić) opcję: Przyjmij model liniowy. Zadania liniowe są wówczas rozwiązywane szybciej i dokładniej. Można dodatkowo zaznaczyć opcję: Przyjmij nieujemne.

Raporty tworzone przez Solver zawierają cenne informacje dotyczące znalezionego rozwiązania. Można z nich odczytać, które ograniczenia są spełnione równościowo, a które nie; które parametry zadania można zmieniać nie powodując zmiany rozwiązania optymalnego i w jak dużym zakresie itp.

Zadania

1. Decyzyjny problem plecakowy

Dany jest plecak o objetosci v = 10 oraz 6 przedmiotów ponumerowanych od 0 do 5. Każdy

przedmiot ma określoną wartość W_i i objetosc V_i. Należy zapakować plecak sposród przedmiotów ponumerowanych od 0 do 5 w taki sposób, aby wartość przedmiotów w nim zgromadzonych była największa. Wartości i objetości przedmiotów określone są w poniższej tabeli:

Polecenie:zbuduj liniowy model decyzyjny i rozwiąż w programie Solver

Odp: W plecaku o maksymalnej wartosci znajda sie przedmioty 1,2,3,4 o wartosci 26.

1. Fabryka produkuje dwa modele: A i B. Każdy model musi kolejno przejść przez dwie

maszyny I i II. Dla wykonania każdego egzemplarza A maszyna I musi pracowac jedną godzine, a maszyna II - 2.5 godziny. Dla wykonania modelu B maszyny I i II muszą pracować odpowiednio 4 godziny i 2 godziny. Maszyna I może być w ruchu najwyżej 8 godzin dziennie, a maszyna II -12 godzin. Każdy model A przynosi 120 złotych zysku, natomiast każdy model B przynosi 160 złotych zysku. Ilu sztuk każdego modelu powinna produkować dziennie fabryka, aby zysk ze sprzedaży był możliwie najwiekszy?

Odp: Zysk ze sprzedazy bedzie najwiekszy i wyniesie 640 złotych, jezeli fabryka wyprodukuje

dziennie 4 sztuki modelu A i 1 sztuke modelu B.

1. Wytwórca mebli produkuje stoły, krzesła, biurka i szafy biblioteczne. Do produkcji wykorzystuje dwa typy desek. W magazynie wytwórca posiada 1500 m pierwszego typu desek i 1000 m drugiego. Dysponuje kapitałem 860 godzin roboczych na wykonanie całej pracy. Przewidywane zapotrzebowanie plus potwierdzone zamówienia wymagaja wykonania co najmniej 40 stołów, 130 krzeseł, 30 biurek i nie wiecej niz 10 szaf bibliotecznych. Każdy stół, krzesło, biurko i szafa biblioteczna wymaga odpowiednio 5, 1, 9 i 12 m desek pierwszego typu i 2, 3, 4 i 1 m desek drugiego typu. Na wykonanie stołu potrzebne są 3 godziny pracy, krzesła 2 godziny, biurka 5 godzin i szafy bibliotecznej 10 godzin. Przy sprzedaży jednego stołu, krzesła, biurka i szafy bibliotecznej wytwórca osiaga zysk odpowiednio 48 złotych, 20 złotych, 60 złotych i 40 złotych.

Zaplanować produkcje mebli w ten sposób, aby wytwórca wywiazał sie z przyjetych zamówień i osiagnał maksymalny zysk.

Odp. Wytwórca otrzyma maksymalny zysk 11600 złotych, jezeli wyprodukuje 150 stołów, 130

krzeseł i 30 biurek.