PrzykÅ‚ad wykorzystania dodatku SOLVER1 w arkuszu Excel do rozwiÄ…zywania zadaÅ„ programowania matematycznego Firma produkujÄ…ca samochody zaciÄ…gnęła kredyt inwestycyjny w wysokoÅ›ci 5 mln zÅ‚ na zainstalowanie nowoczesnych linii montażowych: niemieckiej (N), szwedzkiej (S) i polskiej (P). Dobowe zdolnoÅ›ci montażowe (w sztukach), w zależnoÅ›ci od wysokoÅ›ci nakÅ‚adów inwestycyjnych przeznaczonych na zainstalowanie linii montażowych danego typu, przedstawiono w tabeli. Analiza rynku pokazaÅ‚a, że każda z linii montażowych pozwala uzyskać jednakowe zyski w przeliczeniu na 1 samochód. Należy zdecydować o podziale kredytu pomiÄ™dzy poszczególne programy inwestycyjne, tak aby firma osiÄ…gnęła maksymalnÄ…, dobowÄ… zdolność montażowÄ…, zakÅ‚adajÄ…c, że można kredyt podzielić w częściach caÅ‚kowitych, czyli na 6 części: 0, 1, 2, 3, 4 lub 5 mln zÅ‚. Tabela Dane do przykÅ‚adu NakÅ‚ady (w mln zÅ‚) 0 1 2 3 4 5 ZdolnoÅ›ci N 0 6 8 12 10 7 montażowe linii S 0 5 8 11 14 17 (w szt.) P 0 4 7 12 12 13 RozwiÄ…zanie Zbudujemy najpierw model matematyczny naszego zagadnienia. Przyjmijmy nastÄ™pujÄ…ce oznaczenia: n - liczba linii montażowych; m - liczba możliwych części kredytu, które można przeznaczać na poszczególne programy inwestycyjne; A =[aij] - macierz, której elementy aij stanowiÄ… wartość n×m zdolnoÅ›ci montażowych i-tej linii, przy i =1,n , j = 0,m -1 zainwestowaniu j-tej części kredytu ( ); xij - binarna zmienna decyzyjna, która przyjmuje wartość 1 jeżeli na i-tÄ… liniÄ™ montażowÄ… przeznaczono j-tÄ… część kredytu, 0 - w przeciwnym przypadku. 1 UWAGA !!! Dodatek Solver nie jest instalowany przy standardowej instalacji Excel'a. Jeżeli w menu NarzÄ™dzia nie jest dostÄ™pna opcja Solver wówczas należy wybrać z menu NarzÄ™dzia polecenie Dodatki, po czym z listy dostÄ™pnych dodatków wybrać opcjÄ™ Solver. JeÅ›li Solver nie znajduje siÄ™ na liÅ›cie, Excel zapyta, czy chcemy go zainstalować. Po zainstalowaniu Solver dostÄ™pny bÄ™dzie w menu NarzÄ™dzia, opcja Solver. Zauważmy, iż można przyjąć, że indeks j oznacza (w mln zÅ‚) j = 0,m -1 przydzielonÄ… wartość części kredytu, wiÄ™c . W takim ujÄ™ciu m-1 oznacza wartość kredytu. Ponumerujemy również linie montażowe od 1 do 3 przyjmujÄ…c, że linia N ma numer 1, linia S - numer 2, a linia P - numer 3. Zadanie podziaÅ‚u kredytu miÄ™dzy linie montażowe bÄ™dzie miaÅ‚o zatem postać: n m-1 ""a Å" xij max ij (*) i=1 j=0 przy ograniczeniach: m-1 "x d"1 i = 1,n ij (**) , j=0 n m-1 ""j Å" xij = m -1 (***) i=1 j=0 xij "{0,1} i =1,n , j = 0,m -1 (****) , Funkcja celu (*) maksymalizuje zdolnoÅ›ci montażowe firmy po przydzieleniu odpowiednich części kredytu do poszczególnych rodzajów linii. Zestaw ograniczeÅ„ postaci (**) wymusza, że dla każdej z linii montażowych zostanie przydzielona nie wiÄ™cej niż jedna część kredytu. Ograniczenie (***) gwarantuje, że Å‚Ä…czna suma części kredytu przydzielonych do poszczególnych linii montażowych bÄ™dzie równa wartoÅ›ci kredytu. Ograniczenie (****) stanowi warunek na binarność zmiennych decyzyjnych. Zauważmy, że dla naszego zadania mamy nastÄ™pujÄ…ce dane: " n=3; " m=6; " macierz A =[aij] ma postać: n×m 0 6 8 12 10 7 îÅ‚ Å‚Å‚ ïÅ‚0 A = 5 8 11 14 17śł ïÅ‚ śł ïÅ‚ śł ðÅ‚0 4 7 12 12 13ûÅ‚ Zadanie decyzyjne bÄ™dzie miaÅ‚o zatem nastÄ™pujÄ…cÄ… postać: 3 5 ""a Å" xij max ij (*) i=1 j=0 przy ograniczeniach: 5 "x d"1 i =1,3 ij (**) , j=0 3 5 j Å" xij = 5 "" (***) i=1 j=0 xij "{0,1} i =1,3 , j = 0,5 (****) , czyli 0Å" x10 + 6Å" x11 + 8Å" x12 +12Å" x13 +10Å" x14 + 7Å" x15 + + 0Å" x20 + 5Å" x21 + 8Å" x22 +11Å" x23 +14Å" x24 +17Å" x25 + (*) + 0Å" x30 + 4Å" x31 + 7Å" x32 +12Å" x33 +12Å" x34 +13Å" x35 max przy ograniczeniach: x10 + x11 + x12 + x13 + x14 + x15 d"1 x20 + x21 + x22 + x23 + x24 + x25 d"1 (**) x30 + x31 + x32 + x33 + x34 + x35 d"1 0Å" x10 +1Å" x11 + 2Å" x12 + 3Å" x13 + 4Å" x14 + 5Å" x15 + + 0Å" x20 +1Å" x21 + 2Å" x22 + 3Å" x23 + 4Å" x24 + 5Å" x25 + (***) + 0Å" x30 +1Å" x31 + 2Å" x32 + 3Å" x33 + 4Å" x34 + 5Å" x35 = 5 xij "{0,1} i =1,3 , j = 0,5 (****) , Aby rozwiÄ…zać to zadanie posÅ‚użymy siÄ™ Solver'em z arkusza kalkulacyjnego Excel. W tym celu, w komórkach arkusza zdefiniowano opisywany problem (patrz Rysunek 8.1): " macierz A znajduje siÄ™ w komórkach B4:G6; " zmienne decyzyjne xij znajdujÄ… siÄ™ w komórkach B10:G12; " funkcja celu znajduje siÄ™ w komórce D1 i jest zapisana za pomocÄ… formuÅ‚y: =SUMA.ILOCZYNÓW(B4:G6*B10:G12) ; " lewe strony zestawu ograniczeÅ„ (**) znajdujÄ… siÄ™ w komórkach B16:B18, tzn. w komórce B16 znajduje siÄ™ formuÅ‚a : =SUMA(B10:G10) , w komórce B17 formuÅ‚a : =SUMA(B11:G11) , a w komórce B18 formuÅ‚a : =SUMA(B12:G12) ; " lewa strona ograniczenia (***) znajduje siÄ™ w komórce B20, tzn. znajduje siÄ™ tam formuÅ‚a: =B10*0+C10*1+D10*2+E10*3+F10*4+G10*5+B11*0+C11* 1+D11*2+E11*3+F11*4+G11*5+B12*0+C12*1+D12*2+E12* 3+F12*4+G12*5 . Rysunek 8.1 Zdefiniowanie problemu podziaÅ‚u kredytu inwestycyjnego miÄ™dzy linie montażowe Aby dokoÅ„czyć definicjÄ™ naszego zadania oraz je rozwiÄ…zać należy: " W menu NarzÄ™dzia wybrać polecenie Solver. Zostanie wyÅ›wietlone okno Solver-Parametry (patrz Rysunek 8.2); " W polu Komórka celu wpisać D1 lub zaznaczyć w arkuszu komórkÄ™ D1 (funkcja celu). Wybrać opcjÄ™ Maks; " W polu Komórki zmieniane wpisać B10:G12 lub zaznaczyć w arkuszu komórki B10:G12 (zmienne decyzyjne); Rysunek 8.2 Zdefiniowane zadanie wyznaczania maksymalnych zdolnoÅ›ci montażowych fabryki przy zadanych ograniczeniach " Kliknąć przycisk Dodaj. Pojawi siÄ™ okno dialogowe Dodaj warunek ograniczajÄ…cy (por. Rysunek 8.3). W polu Adres komórki wpisać A14 lub zaznaczyć komórkÄ™ B16. Komórka B16 musi być mniejsza lub równa 1. DomyÅ›lnÄ… relacjÄ… w polu Ograniczenia jest <= (mniejsze lub równe) i nie trzeba jej zmieniać. W polu obok relacji wpisać adres komórki D16. Kliknąć przycisk Dodaj. Rysunek 8.3 WyglÄ…d okna dialogowego dodawania ograniczeÅ„ " W polu Adres komórki wpisać B17 lub zaznaczyć komórkÄ™ B17. Komórka B17 musi być mniejsza lub równa 1. DomyÅ›lnÄ… relacjÄ… w polu Ograniczenia jest <= (mniejsze lub równe) i nie trzeba jej zmieniać. W polu obok relacji wpisać adres komórki D17. Kliknąć przycisk Dodaj. W polu Adres komórki wpisać B18 lub zaznaczyć komórkÄ™ B18. Komórka B18 musi być mniejsza lub równa 1. DomyÅ›lnÄ… relacjÄ… w polu Ograniczenia jest <= (mniejsze lub równe) i nie trzeba jej zmieniać. W polu obok relacji wpisać adres komórki D18. Kliknąć przycisk Dodaj. W polu Adres komórki wpisać B20 lub zaznaczyć komórkÄ™ B20. Komórka B20 musi być równa 5. Zmienić relacjÄ™ w polu Ograniczenia na = (równe). W polu obok relacji wpisać adres komórki D20. Kliknąć przycisk Dodaj. W polu Adres komórki wpisać B10:G12 lub zaznaczyć komórki B10:G12. Komórki B10:G12, zawierajÄ…ce zmienne decyzyjne, muszÄ… mieć wartoÅ›ci binarne. Zmienić warunek w polu Ograniczenia na bin (binarna). Kliknąć przycisk Ok. " Otrzymamy zdefiniowane zadanie w oknie Solver-Parametry (patrz Rysunek 8.2) powiÄ…zane z modelem zapisanym w arkuszu z Rysunku 8.1. Po klikniÄ™ciu przycisku Rozwiąż Solver rozwiąże nasze zadanie przypisujÄ…c optymalne wartoÅ›ci zmiennym decyzyjnym jak na Rysunku 8.4. Rysunek 8.4 Optymalny podziaÅ‚ kredytu inwestycyjnego na linie montażowe maksymalizujÄ…cy zdolnoÅ›ci montażowe firmy Z Rysunku 8.4 odczytujemy, że wartoÅ›ci trzech zmiennych decyzyjnych sÄ… * * * x11 =1 x21 =1 x33 =1 niezerowe, a mianowicie: , , . PozostaÅ‚e zmienne majÄ… wartość 0. Wartość funkcji celu dla rozwiÄ…zania optymalnego odczytujemy z komórki D1 i wynosi ona 23. Jest to maksymalna możliwa zdolność montażowa fabryki po rozdysponowaniu zaciÄ…gniÄ™tego kredytu inwestycyjnego w wysokoÅ›ci 5 mln zÅ‚ miÄ™dzy linie montażowe w sposób nastÄ™pujÄ…cy * (odczytujemy te wartoÅ›ci z interpretacji zmiennych decyzyjnych): x11 =1 * oznacza, że na liniÄ™ nr 1 (N) przydzielamy 1 mln zÅ‚, x21 =1 oznacza, że na liniÄ™ * nr 2 (S) przydzielamy również 1 mln zÅ‚, x33 =1 oznacza, że na liniÄ™ nr 3 (P) przydzielamy 3 mln zÅ‚. Uwagi koÅ„cowe Należy dodać, że dodatek Solver może być wykorzystany do rozwiÄ…zywania zarówno zadaÅ„ liniowych, jak i nieliniowych oraz ciÄ…gÅ‚ych i dyskretnych. Rodzaj funkcji (liniowa, nieliniowa) jest rozpoznawany przez Excel a i automatycznie dobierana jest odpowiednia metoda rozwiÄ…zania. Natomiast warunki, co do typu zmiennych decyzyjnych ustala użytkownik poprzez wprowadzenie ich w oknie dialogowym Dodaj warunek ograniczajÄ…cy (Rysunek 1.3.4). Mianowicie w oknie tym znajduje siÄ™ lista rozwijana (por. Rysunek 8.3), na której znajdujÄ… siÄ™ nastÄ™pujÄ…ce elementy: <= , = , >= , int , bin . Wybranie int oznacza, że zmienna decyzyjna, której adres komórki wpisano w polu Adres komórki bÄ™dzie miaÅ‚a wartoÅ›ci caÅ‚kowitoliczbowe, a wybranie bin oznacza, że zmienna decyzyjna, której adres komórki wpisano w polu Adres komórki bÄ™dzie miaÅ‚a wartoÅ›ci binarne.