Matematyczne techniki zarządzania 83-208-0045-5 [PDF]

Zitiervorschau

Władysław Radzikowski

matematyczne techniki zarządzania Państwowe Wydawnictwo Ekonomiczne

Państwowe Wydawnictwo Ekonomiczne Warszawa 1980

Opracowanie graficzne Andrzej Pilich Redaktor Alicja Rutkowska

© Copyright by Państwowe Wydawnictwo Ekonomiczne Warszawa 1980

ISBN 83-208-0045-5

Spis treści

Od A u to r a ...................................................................................... 7 W prowadzenie............................................................................... 10 Algebra m a cierzy .........................................................................26 Analiza przepływów m ięd zy g a łę z io w y c h ...........................36 Analiza strukturalna . .............................................. 44 Badania o p e r a c y jn e .................................................................. 49 « Gromadzenie danych liczbow ych........................................54 Posługiwanie się modelami matematycznymi . . . 57 Drzewo d ecyzyjn e.................................................................. 62 Metoda PATTERN.................................................................. 66 Deterministyczna odmiana metody programowania dyna­ micznego ......................................................................... . . . 71 Dynamiczny model analizy przepływów międzygałęziowych 83 E k o n o m e tr ia ............................................................................... 89 Ekonometryczne modele analizy kosztów . . . . 98 Funkcja produkcji.................................................................. 102 Matematyczna teoria g i e r ..................................................... 104 Gry dwuosobowe z sumąz e r o ....................................... 106 Gry dwuosobowe o sumied ow oln ej..................................112 Gry wieloosobowe . . ......... .......................................115 Metody badania rozwoju zjawisk w c z a sie ...........................116 Wyodrębnianie tendencji rozwojowej, wahań perio­ dycznych i lo s o w y c h ............................................................ 120 Adaptacyjne modele prognozowania krótkookresowego 128 Metody sieciowe d eterm in isty czn e........................................132 Metoda C P M ......................................................................... 136 Metoda P E R T ......................................................................... 140

5

Programowanie linipwe . . . . . . . . . 142 Metoda dupleks programowania liniowego . . . . 150 Programowanie liniowe b i n a r n e ........................................158 Programowanie liniowe parametryczne................................. 166 Programowanie liniowe w liczbach całkowitych . . . 181 Metoda L an d a -D o ig a............................................................185 Metoda Gomory’e g o ............................................................188 Programowanie liniowe — zadanie transportowe . . . 193 Zadanie produkcyjno-transportowe................................. 199 Programowanie nieliniowe k w a d r a t o w e ...................... 204 Programowanie s t o c h a s t y c z n e .......................................... 21 i Modele jednoetapow e............................................................214 Modele d w u e ta p o w e ............................................................217 Programowanie w y p u k łe ............................................................225 Stochastyczne metody sieciowe. Metoda GERT . . . 233 Stochastyczna odmiana metody programowania dynamicz­ . .. 242 nego ............................................................................... . .. . S y m u la c ja ...................................................................... ... Metody M o n te-C a rlo .................................... . . . . 261 Języki symulacyjne . . . . . . . .. ..268 Dynamika systemów zarządzania .. . . . . 274 Symulacyjne gry kierownicze ........................................ 277 Teoria korelacji i r e g r e s j i ..................................................... 281 Regresja l i n i o w a ........................................ ...... 290 Korelacja w i e l o r a k a ..................................................... ...... 293 Wielochodowe gry nieantagonistyczn e................................. 297 Wyznaczanie ekstremum funkcji jednej zmiennej . . . 306 Wyznaczanie ekstremum warunkowego funkcji jednej zmiennej . ................................................................ ... . . 311 Wyznaczanie ekstremum funkcji n zmiennych . .. 315 Wyznaczanie ekstremum warunkowego funkcji « zmien­ nych 320

Od Autora

Przedstawione w książce m etody matematyczne, staty ­ styczne i sym ulacyjne (zwane dalej w skrócie metodami m atem atycznym i) traktow ane są jako matem atyczne techniki zarządzania 1 i analizowane z punktu widzenia ich przydatności do celów zarządzania. Tego rodzaju podejście nie jest w nauce o organizacji i zarządzaniu ani nowe, ani też odosobnione. Na przykład J. Ziele­ niewski przez techniki zarządzania rozumiał przede wszystkim matem atyczne metody optym alizacji decyzji, w sensie technik optymalizacji działania, spośród któ­ rych zwracał szczególną uwagę na 2: — techniki programowania liniowego, — techniki iteracyjne (matematyczne techniki rozwią­ zywania typowych zagadnień), — techniki rachunku macierzowego i grafów skiero­ wanych. Podobne podejście zastosowałem w pracy: Techniki za­ i W rezultacie takiego podejścia terminy „metody m atematyczne” i „ma­ tematyczne techniki zarządzania” przyjmujemy za synonim y i używamy zamiennie w zależności od kontekstu omawianych problemów. * J. Zieleniewski, Organizacja i zarządzanie, wyd. 5, Warszawa 1976, s. 486—491.

7

rządzania (PWE, Warszawa 1974). Obecna książka sta­ nowi pewnego rodzaju rozwinięcie Technik zarządzania, ale równocześnie różni się od tam tej pracy zarówno zakresem problemowym, jak i konstrukcją wykładu. Ograniczyłem się bowiem do przedstawienia wyłącznie w ybranych m atem atycznych technik zarządzania w szerszym niż poprzednio zakresie, rezygnując z oma­ wiania .innych technik (np. informatycznych), które bę­ dą przedmiotem rozważań w następnych książkach cyklu wydawniczego: M etody i techniki organizator­ skie. K ryterium wyboru technik m atem atycznych była ocena ich przydatności w organizacji i zarządzaniu, oparta na znanych powszechnie i wielokrotnie opisywanych przykładach zastosowania ich w praktyce oraz na moim własnym doświadczeniu zbieranym przez ponad 20 lat. Dzięki tej koncentracji tematycznej mogłem omówić nieco szczegółowiej w ybrane m atem atyczne techniki zarządzania. Zrezygnowałem przy tym świadomie z przedstawiania istniejących algorytmów realizacji po­ szczególnych metod matem atycznych, z w yjątkiem kilkunastu algorytmów szczególnie interesujących. Współcześnie dysponujem y bowiem dziesiątkami róż­ nych algorytmów realizujących jedną i tę samą m e­ todę, np. programowania liniowego. Zwróciłem nato­ m iast uwagę na dokładniejszy opis form alny poszcze­ gólnych metod matem atycznych, w tym szczególnie modeli m atem atycznych aproksym ujących (przybliża­ jących) poszczególne problemy zarządzania3 („co to je st”), oraz na ch arak tery sty k ę. dziedzin zastosowania tych m etod („do czego służy”). Podaję również przykła­ dy zastosowania m atem atycznych technik zarządzania w praktyce. Wiele innych m atem atycznych technik zarządzania * Przez „problem zarządzania” będziemy rozumieć jakikolwiek problem decyzyjny rozwiązywany przez zarządzającego.

8

omawiam w książce: M etody matematyczne i staty­ styczne w przedsiębiorstwie (wyd. 2, PWE, Warszawa 1976). Pozostałe techniki opisywane są w pracach in­ nych autorów, do których odsyłam Czytelników. Ni­ niejsza książka jest więc swego rodzaju przewodnikiem po obszernej problematyce matem atycznych technik za­ rządzania. Serdecznie dziękuję doc. dr hab. inż. E. Nawareckiemu za przejrzenie maszynopisu. Wnikliwe Jego uwagi po­ mogły m i ulepszyć kształt i treść książki. Władysław Radzikowski

Książkę tę poświęcam Mojej Żonie

Wprowadzenie

Klasyfikację matem atycznych technik zarządzania prze­ prowadzamy przede wszystkim z punktu widzenia ro­ dzaju sytuacji decyzyjnej, w której rozwiązywane są poszczególne problemy zarządzania, i charakteru tych problemów. Za A. Newell’em i H. A. Simonem przyj­ mujemy, że poszczególne problemy zarządzania mogą b y ć 1: — dobrze ustrukturalizowane (dobrze określone), czyli dające się sformułować ilościowo (w liczbach lub symbolach) i zmierzyć, — nie ustrukturalizowane (nie określone), czyli dające się przedstawić tylko jakościowo (w postaci opisu słownego) ze względu na brak ilościowych zależno­ ści pomiędzy elementami, — słabo ustrukturalizowane (słabo określone), czyli mieszane, zawierające zarówno elem enty jakościo­ we, jak i ilościowe, z przewagą elementów jakościo­ wych. Poszczególne problemy zarządzania rozwiązywane są 1 A. Newell, H. A. Simon, Heu ris tic Problem Solving: Th e N ew Advance in Operatio n Research, „Operation Reasearch” 1958, vol. 4.

w różnorodnych sytuacjach decyzyjnych. Za J. Mothesem rozpatryw ać będziemy następujące rodzaje znacz­ nie różniących się od siebie sytuacji decyzyjnych 2: — sytuacje deterministyczne, w których na skutki w pływ ają jedynie param etry całkowicie określone, — sytuacje losowe, których zmiany mogą być w pew­ nym sensie przewidziane, a więc gdy param etry m ają znane rozkłady prawdopodobieństwa; decyzję podejm uje się w sytuacji „(lub przestrzeni) losowej, — sytuacje niepewne, gdy wpływ na skutki m ają pa­ ram etry niepewne, których zmian nie można prze­ widzieć; decyzje podejm uje się w' sytuacji (lub przestrzeni) niepewnej, — sytuacje konfliktowe, charakteryzujące się tym, że param etry wpływające na skutki decyzji są lub mo­ gą być kontrolowane przez przeciwników; decyzje podejm uje się w sytuacji (lub przestrzeni) konflik­ towej. W konsekwencji tych założeń wyodrębniam y metody matem atyczne (matematyczne techniki zarządzania) sto­ sowane: 1) w sytuacjach determ inistycznych do rozwiązywania problemów dobrze ustrukturalizow anych; są to n a­ stępujące grupy metod matem atycznych (tablica 1): — m etody bilansowe, — metody ekstremalne, — deterministyczne metody optym alizacyjne oparte na statycznych modelach m atem atycznych3, * J. Mothes, S ytu acje niepewne a pode jm owan ie de cy zji w przemyśle, Warszawa 1972. * Z reguły będą to ab strakc yjn e modele m atem atyczne należące do tzw. modeli teoretycznych (nazywanych także modelami heurystycznymi). „Mianem modelu teoretycznego określa się zwykle model nominalny zbudowany jako hipotetyczna konstrukcja myślowa, będąca uproszczo­ nym obrazem badanego fragmentu rzeczywistości, opartym na elimina­ cji myślowej jego elementów (cech, relacji) nieistotnych dla danego celu lub w danym etapie badania. Zakres dokonanych eliminacji my­ ślowych i uproszczeń wyrażają założenia, czyli tzw. warunki począt­ kowe modelu; przy założeniu tych warunków (często mających cha­

11

— determ inistyczne metody optym alizacyjne oparte na dynamicznych modelach matematycznych; 2) w sytuacjach losowych, niepewnych i konfliktowych do rozwiązywania problemów słabo ustrukturalizowanych; są to następujące grupy m etod m atem a­ tycznych (tablica 1): — niedeterm inistyczne metody optym alizacyjne oparte na modelach statycznych, — niedeterm inistyczne metody optym alizacyjne oparte na modelach dynamicznych, — metody stochastyczne, — metody symulacyjne, — metody badań operacyjnych. Rozpatrując poszczególne matem atyczne techniki za­ rządzania, rozróżniamy także modele, w których zmia­ ny wartości zmiennych decyzyjnych mogą być ciągłe lub dyskretne (nieciągłe, całkowitoliczbowe). Zgodnie z koncepcją przyjętą dla całego cyklu: Metody i techniki organizatorskie w kartach charakterystyk poszczególnych metod zamieszczono: — nazwę metody, — symbol metody, wskazujący grupę metod, do której dana metoda należy (zob. tablica 1), — klasę trudności, a mianowicie: I — metoda może być opanowana w w yniku k rót­ kotrwałego treningu (łatwa), II — do opanowania metody potrzebny jest dłuż­ szy trening i doświadczenie praktyczne (śred­ nio trudna), III — metoda jest stosowana efektywnie pod wa­ runkiem zdobycia odpowiednich wiadomości i umiejętności oraz przynajm niej kilkuletnie­ go doświadczenia praktycznego (trudna). rakter idealizacji stanu faktycznego i wartość fikcji heurystycznej) przedstawia się w modelu strukturę badanego fragmentu rzeczywistości i docieka się prawidłowości w nim zachodzących”, W ie lk a Efncyklopedi c Powszechna, PWN, Warszawa 1965, t. 7, s. 394.

12

— klasę zastosowań według kryterium : p — określania celów i zadań, pp — prognozowania, pr — programowania, pl - planowania, 0 — organizacji, ba — analizy organizacyjnej, oo — optymalizacji organizacyjnej, op — projektowania rozwiązań organizacyjnych, o w --- wdrażania rozwiązań organizacyjnych, od — organizacji działania, k — kontroli, analizy i oceny, m — motywowania, z — zarządzania (w sensie ogólnym), u — zastosowania uniwersalnego, — — — — — —

zastosowanie metody (rozwiązywane problemy), opis, schemat metody, efektywność i koszty metody, sposób nauczania lub posługiwania się metodą, literaturę, praktyczne przykłady stosowania metody.

Opisując przykłady praktycznego zastosowania poszcze­ gólnych metod matematycznych, kierowano się k ry te­ rium ich przydatności do realizacji poszczególnych funkcji zarządzania przedsiębiorstw em 4. W literaturze przedm iotu najwięcej miejsca poświęca się matem atycznym technikom zarządzania stosowanym do planowania działania, dużo mniej technikom przy­ datnym do kierowania bieżącym działaniem, najm niej zaś technikom wykorzystywanym do kontroli i oceny efektów działania. Dość w iernie oddaje to stan teorii i praktyki w tej dziedzinie. Stan ten można stosunkowo łatwo zmienić przez wprowadzenie technik zarządzania * Nie ogranicza to zbytnio ogólności rozważań ze względu na fakt, że

przedsiębiorstwo traktujemy jako organizację gospodarczą.

18

stosowanych dotychczas do modelowania problemów planowania także do: 1. Sterowania bieżącym działaniem, wykorzystując po­ szczególne techniki ex ante, czyli na bieżąco. Na przy­ kład bieżąca obserwacja realizacji jakiegoś przedsię­ wzięcia prowadzona za pomocą metod sieciowych umo­ żliwia szybkie stwierdzenie powstających zmian (np. opóźnień) i określenie ich wpływu na końcowy term in wykonania przedsięwzięcia. Pozwala również podejmo­ wać odpowiednio szybko decyzje korygujące przebieg realizacji przedsięwzięcia w razie pojawienia się nie­ przewidzianych trudności i zahamowań. Dzięki użyciu metod sieciowych łatwo uzyskujem y więcej inform acji, gdyż harm onogram y realizacji poszczególnych przed­ sięwzięć opracowuje się nie tylko w fazie planowania, ale także aktualizuje i zmienia w trakcie realizacji tych przedsięwzięć, a więc na bieżąco. 2. Kontroli i oceny efektów działania, w ykorzystując poszczególne techniki ex post, czyli po fakcie. Posłu­ giwanie się metodami m atem atycznym i do kontroli i oceny polega, ogólnie biorąc, na przeprowadzeniu obli­ czeń prognostycznych, programowych i planistycznych na podstawie rzeczywistych param etrów , a nie p ara­ metrów zakładanych w prognozach, program ach i pla­ nach. Na przykład jeżeli wiem y z ewidencji i sprawoz­ dawczości, jakie rzeczywiście uzyskano surowce i w ja­ kich ilościach, jakie rzeczywiście były nakłady pracy na 1 sztukę produkowanych wyrobów itp., to możemy opracować „retrospektyw ny” plan produkcji przedsię­ biorstwa i wykazać (przez porównanie planu „retro­ spektywnego” z rzeczywistymi wynikami), jak przed­ siębiorstwo napraw dę zagospodarowało posiadane za­ soby pracy, m ateriały i surowce, moce produkcyjne itp. W ydaje się, że większość prezentowanych w tej książ­ ce m atem atycznych technik zarządzania można stoso­ wać nie tylko na etapie planowania działania, ale także 19

kierowania bieżącym działaniem oraz kontroli i oceny efektów działania. Przydatność nowoczesnych technik matem atycznych w praktyce zarządzania jest ciągle jeszcze przedmiotem kontrow ersji i nie kończących się dyskusji. Zwolennicy stosowania tych technik twierdzą, że bez w ykorzysta­ nia takich działów m atem atyki, jak rachunek różnicz­ kowy, rachunek prawdopodobieństwa (i statystyka ma­ tematyczna), programowanie liniowe, teoria gier, pro­ gram owanie dynamiczne itp., nie można efektywnie zarządzać współczesnym przedsiębiorstwem, planować i kontrolować wyników jego działalności. Przeciwnicy są zdania, że chodzi tu ta j tylko o nową „modę”. Wska­ zują, że im głębiej bada się procesy podejmowania decyzji, tym lepiej dostrzega się, jak skomplikowane jest „doskonałe” (tzn. uwzględniające wszystkie impe­ ratyw y ekonomiczne, techniczne, socjalne, finansowe itp. składające się na politykę przedsiębiorstwa) po­ staw ienie problemów zarządzania, uchwycenie ich ele­ m entów i czynników niewymiernych, jak trudno zde­ finiować cele działania. Wiadomo jednak, że dyrektor musi podejmować decyzje, dlatego też tnie rozpatrując argum entacji za i przeciw matem atycznym technikom zarządzania, skoncentrujem y się na jego codziennych, praktycznych potrzebach w tej dziedzinie. Oczywiście potrzeby w zakresie korzystania z m ate­ matycznych technik zarządzania są iróżne, bo uw arun­ kowane odmienną wiedzą, doświadczeniem, uzdolnie­ niami, motywacją, stosunkiem do ryzyka itp. Wiadomo natom iast, że każdy zarządzający dysponuje s: — centralnym system em sterowania, na który składa się określona liczba pamięci zawierających różne rodzaje symbolizowanych informacji, powiązanych relacjam i porządkującym i lub skojarzeniowymi, —- określoną liczbą procedur przetwarzania informacji, * Proces de cyzy jn y, Warszawa 1973.

20

które umożliwiają operowanie inform acjam i znaj­ dującym i się w pamięciach, . — ściśle określonym układem reguł pozwalających łą­ czyć procesy przetw arzania inform acji w kompletne programy. A. Newell, D. Shaw i H. A. Simon za inform acje uw a­ żają zarówno dopływające do zarządzającego nowe wiadomości, jak też jego intuicję, rozsądek i doświad­ czenie. Chociaż czynniki te w ydają się ze sobą nie w ią z a n e , to jednak są form ą informacji, którą można zastosować w procesie decyzyjnym. Podejm ujący de­ cyzję zmierza (często podświadomie) do w yjaśnienia lub określenia współzależności między dostępnym i m u środkam i działania (alternatyw am i decyzji) a oczeki­ w anym i rezultatam i końcowymi, ocenia prawdopodob­ ne skutki swej decyzji na podstawie intuicji, rozsądku i doświadczenia. W praktyce oznacza to sięganie do zdobytej wiedzy i zgromadzonego doświadczenia. Jak dalece może on w ykorzystać swoje obserwacje z przesz­ łości do oceny i przewidywania przyszłości, tak dalece jego doświadczenie w pływ a na jakość decyzji 8. M ate­ matyczne techniki zarządzania mogą być przydatne za­ rządzającem u wtedy, gdy: 1) umożliwiają „panowanie” nad większą niż dotych­ czas liczbą inform acji i wzbogacają zasób inform a­ cji o nowe, dodatkowe relacje porządkujące lub skojarzeniowe, 2) uspraw niają i przyspieszają przetw arzanie inform a­ cji, a dzięki tem u ułatw iają zarządzającemu aktyw ­ ne operowanie inform acjami zaw artym i w pamięci, 3) wzbogacają zasób reguł, za pomocą których zarzą­ dzający przetwarza inform acje w kompleksowe pro­ gram y działania. Praktyczna przydatność technik zarządzania dla dyrek­ tora przedsiębiorstwa to tylko jeden z w arunków ich • Tamże.

21

stosowania. Inne nie m niej istotne w arunki można sformułować następująco: 1. Zarządzający (np. dyrektor przedsiębiorstwa) ma możliwość dokonywania wyboru celu (szczegółowych zadań) lub działania (technicznych sposobów produk­ cji) albo zarówno celu, jak i działania, w związku z czym musi podejmować określone decyzje. W prak­ tyce często zarządzający przecenia własne możliwości dokonywania wyboru celu lub działania i próbuje po­ dejmować decyzję w spraw ach zastrzeżonych dla in­ nych ośrodków decyzyjnych. Jeszcze częściej spotyka­ my się z zachowaniem krańcowo przeciwnym, a mia­ nowicie zarządzający nie docenia własnych możliwości i obiektywnie istniejącej potrzeby podejmowania decy­ zji, np. dyrektor przedsiębiorstwa zasugerowany faktem braku swobody przy wyznaczaniu celów (tzn. szczegó­ łowych zadań przedsiębiorstwa), rezygnuje z możliwej i potrzebnej optymalizacji działania (tzn. z wyboru n aj­ lepszego zestawu technicznych sposobów realizacji usta­ lonych celów). 2. Swoboda podejmowania decyzji przez zarządzającego (np. dyrektora przedsiębiorstwa) jest ograniczona. W praktyce kierowania przedsiębiorstwami trudno by­ łoby znaleźć przykład całkowitej swobody decyzji. Najczęściej zarówno >na cel, jak ii na działanie „nołożone są” różnorodne ograniczenia organizacyjne, kadro­ we, surowcowe itp. 3. Co najm niej pewna część warunków ograniczających swobodę podejmowania decyzji przez zarządzającego jest wymierna, a więc może być kw antyfikowana , w znanych jednostkach miary, co w ynika w prost z w ymierności (co najm niej częściowej) celu i działania. W praktyce kierowania przedsiębiorstwami zarządza­ jący muszą uwzględniać nie tylko aspekty techniczne, ekonomiczne czy organizacyjne celu lub działania, ale również aspekty socjalne, hum anitarne i inne. Mate-^ 22

matyczne metody optymalizacji decyzji trudno byłoby z pozytywnym efektem zastosować np. do rozwiązy­ wania problemów czysto socjalnych. Większość w arun­ ków ograniczających swobodę podejmowania decyzji przez zarządzającego może być jednak kw antyfikow ana w znanych jednostkach miary. 4. Zarządzającemu zależy na wyborze decyzji najko­ rzystniejszej, czyli optym alnej, a m iarą optym alizacji decyzji jest albo m aksym alny stopień realizacji celu, albo maksymalna efektywność działania. Nie ma sensu stosowanie metod m atem atycznych do optymalizacji decyzji, jeżeli zarządzający nie jest zainteresowany w wyborze decyzji najkorzystniejszej, np. zakłada z góry nieoptymakiość decyzji, dążąc do ukrycia rezerw w zasobach produkcyjnych. P raktyka kierowania przed­ siębiorstwam i dowodzi jednak przekonująco, że wszel­ kiego rodzaju chomikarstwo, partykularyzm lub w y­ godnictwo jest — na dłuższą m etę — nieefektyw ne dla samego zarządzającego (nie mówiąc o szkodliwości ogólnogospodarczej i ogólnospołecznej takiego postępo­ wania). Na podstawie sformułowanych wyżej uwag ogólnych można następnie rozpatryw ać różne problem y szczegó­ łowe, m. in. dotyczące celów ekonomicznych i działań techniczno-organizacyjnych. W tym przypadku postę­ powanie nasze oparte jest na następujących zasadach: a) dla każdego działania można znaleźć najlepsze w y­ konanie, co osiąga się raczej przez systematyczną analizę niż dzięki intuicji, doświadczeniu, naślado­ w aniu innych itp. b) sposób analityczny rozwiązywania problemu polega na: — stwierdzeniu istnienia jakiegoś problemu i jego określeniu m erytorycznym i form alnym (mate­ matycznym), konieczne jest także ustalenie stanu faktycznego problemu (zgromadzenia danych) 23

i pogrupowanie faktów według ich znaczenia dla problemu (próba znalezienia przyczyn poszcze­ gólnych faktów), — opracowaniu modelu matematycznego aproksymującego (przybliżającego) dany problem decy­ zyjny, — znalezieniu rozwiązania problemu na podstawie opracowanego modelu, przy czym ważne jest dostarczenie podejmującemu decyzję wielu wa­ riantów rozwiązania i zapoznanie go ze zbiorem rozwiązań suboptymalnych, gdyż stw arza to wa­ runki do analizy w ielu możliwych w yników koń­ cowych decyzji i chroni przed jednostronnością, — sprawdzeniu modelu i rozwiązania, co jest ko­ nieczną weryfikacją zarówno definicji problemu, jak też hipotezy roboczej modelu; nie można również zapominać o konieczności sprawdzenia form alnej poprawności samego rozwiązania (odpowiednimi m etodam i numerycznymi), — opracowaniu system u reagowania na wszelkie zmiany, aby można było szybko podejmować decyzje korygujące; dużym uproszczeniem było­ by bowiem przyjęcie założenia, że w arunki, z których wychodzimy przy rozwiązywaniu pro­ blemu, nie będą ulegać zmiamom, c) podejmowanie decyzji na podstawie m ateriałów analitycznych przygotowanych w sposób przedsta­ wiony wyżej chroni zarządzającego przed szkodli­ wym w oluntaryzm em lub zwykłym optymizmem; również przy tzw. decyzjach pow tarzalnych potrzeb­ ne byłoby stosowanie odpowiednich metod anali­ tycznych. Wśród warunków stosowania m atem atycznych technik zarządzania w praktyce wymienia się często — i słusz­ nie — konieczność dysponowania właściwymi, obiek­ tyw nym i inform acjami oraz systemami przetwarzania 24

inform acji szybko, w odpowiednich term inach i nie­ wielkim kosztem. Zapewnienie tego rodzaju „możli­ wości inform acyjnych” napotyka różnorodne przeszko­ dy n atu ry psychologicznej (motywacja) i techniczno-organizacyjnej (organizacja zbierania i obiegu infor­ macji). Jest jednak uzasadnione twierdzenie, że — ogólnie rzecz ujm ując — optymalizacja decyzji gospo­ darczych za pomocą metod matem atycznych jest efek­ tyw na dopiero w w arunkach dostatecznej inform atyza­ cji gospodarki narodowej. Oznacza to właściwy obieg 'informacji w układzie funkcjonalnym gospodarki naro­ dowej, który jest niemożliwy bez odpowiedniej ilości środków autom atyzacji przetw arzania inform acji i uporządkowania źródeł informacji. Jak wiadomo, pro­ ces inform atyzacji naszej gospodarki narodowej został zapoczątkowany dopiero przed niewielu laty. ♦Przystą­ pienie do projektow ania i budowy Systemu Państw o­ wej Inform acji Statystycznej (SPIS) i innych rządo­ wych systemów inform atycznych zapowiada korzystną zmianę dotychczasowej sytuacji.

Ł

Algebra m acierzy Symbol: 1-BA Klasa trudności: I Klasa zastosowań: pi, op, k

Z asto so w an ie m etody (ro zw ią zy w a n e problem y)

Słowo „macierz” oznacza tyle samo co „porządek”, „uporządkowanie”. Zostało ono zdefiniowane na po­ czątku XIX wieku w pracach angielskich m atem aty­ ków — W. R. Hamiltona i J. J. Sylwestra. W ykorzystanie algebry macierzy w przygotowaniu decyzji d planowaniu ma już ponad pięćdziesięcioletnią tradycję. Po raz pierwszy zastosowaino ją do m iędzygałęziowego badania produkcji i podziału produktu społecznego w sporządzonym przez C entralny Urząd Statystyczny bilansie gospodarki narodowej ZSRR dla lat 1923/24. Opublikowane w 1926 r. m ateriały na ten tem at obejmowały bilanse naturalne 38 wyrobów prze­ mysłowych i rolniczych oraz tablice wartościowe za­ w ierające bilans produkcji i jej podziału w przekroju gałęziowym, bilanse mocy produkcyjnych i nakładów inwestycyjnych (w budownictwie), charakterystykę do­ chodu narodowego oraz macierz międzygałęziowego obrotu środkami produkcji w przemyśle. Mimo że for­ ma bilansu dla lat 1923/24 odbiegała od obecnie przy­ jętej, znacznie ułatw iającej czynności obliczeniowe, to zaw ierał on wszystkie dane niezbędne do przedstawie­

n ia go w postaci matematycznego modelu macierzo­ wego. Uczeni radzieccy sformułowali w następnych latach podstawowe zasady m etodyczne badania powią­ zań międzygałęziowych i proporcji charakteryzujących gospodarkę narodową, opracowali sposoby ujęcia w uni­ w ersalnej . „tablicy .ekonomicznej” procesu produkcji i podziału produktu społecznego oraz określili istotę i znaczenie współczynników bezpośrednich nakładów m aterialnych. W latach trzydziestych pod kierownictwem W. Leontiefa prowadzono w Stanach Zjednoczonych teoretycz­ ne i praktyczne badania w dziedzinie modeli między­ gałęziowych. Zyskały one rozgłos pod nazwą analizy nakładów i w yników (input-output analysis).

Opis, schem at m etody

Jeżeli danych jest m X n wielkości a{j (liczb), uporząd­ kowanych według prostokątnego schem atu w ten spo­ sób, że wielkość atj znajduje się w i-tym wierszu i j-tej kolumnie, to takie uporządkowanie wielkości atj okre­ ślamy mianem macierzy i oznaczamy:

[aa] = A =

au a 2i

a l2

a ln

&22

®2n

Jhnl

a m2

...

^mn

Poszczególne wielkości atj nazywamy elementami ma­ cierzy. Dla operami rachunkow ych przeprowadzanych na macierzach duże znaczenie m ają liczby m wierszy i n kolumn macierzy, stanowiące jej charakterystykę. Na przykład przy m = n mówimy o macierzy kwadratowej stopnia n. 27

Dla każdej macierzy [a^] można skonstruować macierz transponowaoią do niej, czyli macierz [a#]: On

a 2i

^ln

®ml Otn2

(2)

&mn

Macierz, w której poszczególne elem enty uporządkowa­ ne są w postaci jednej kolum ny o m składowych, okre­ ślamy mianem m-wymiarowego wektora kolumnowego i oznaczamy:

b2 b =

(3)

Może to być j-ta kolumna macierzy i.w tedy dany wek­ tor kolumnowy oznaczamy jako [b*] = b*. Natomiast macierz, której poszczególne elem enty uporządkowane są w postaci jednego wiersza o n składowych, okre­ ślam y mianem n-wymiarowego wektora wierszowego i oznaczamy: c' = [C i c2 . . . C„].

(4)

Jeżeli jest to ż-ty wiersz macierzy, to dany w ektor wierszowy możemy oznaczyć jako [c/] = c/. Macierz kwadratową, której wszystkie elem enty a{j po­ za główną przekątną (i =£ j) są równe zero, nazywamy macierzą diagonalną. Elementy niezerowe macierzy diagonalnej mogą przyjmować różne wartości. Jeżeli wszystkie elementy niezerowe macierzy diagonalnej m ają wartość 1, czyli:

o o

0 1 O

o o 1

o o

0

0

0

1

1

1=

0“

(5)

to mówimy o macierzy jednostkowej. W yznacznik kwadratowej macierzy A, oznaczany jako I A | lub det A, to pew na liczba związana z tą macierzą kwadratową. Liczbę tę otrzym ujem y, ogólnie biorąc, przy zastosowaniu tzw. rozwinięcia Laplace’a, a mia­ nowicie: — przy rozwinięciu w edług i-tego wiersza: M I = a411

| + Oł2 1ilł2 | + . . . + Oin | Ałn | (i = 1 , 2 , . . . , n),

W

— przy rozwinięciu w edług j-tej kolumny: *1 A | = au | A\j | + a%) | Azj 1 4 " . . . 4 " anj | A nj | (j = 1, 2, . . . , n),

(?)

gdzie wyrażenie: a ii a u . . . ^i,*-i tti^+i . . . aln

t

®nl On2 • • • a n,j—1 a n,j+1 • • • ®nn

29

określane mianem dopełnieniar algebraicznego | A {j |, pow staje w w yniku pomnożenia przez znak plus lub m inus — w zależności od tego, jaka będzie wartość w yrażenia (—1)*+* — podwyznacznika Dtj, odpowiada­ jącego elementowi atj i otrzymanego z wyznacznika danej macierzy kw adratow ej stopnia n przez w ykreśle­ nie ż-tego wiersza oraz j-tej kolumny; widać to w y­ raźnie po praw ej stronie rów nania (8). W ykorzystując wprowadzone określenia wyznacznika i dopełnienia algebraicznego można zdefiniować dalsze pojęcia: 1) rządem macierzy A nazywam y stopień największej macierzy kw adratow ej zawartej w A, której w y­ znacznik jest różny od zera, 2) nieosobliwa macierz kwadratowa A to macierz, któ­ rej wyznacznik jest różny od zera. Jeżeli natomiast wyznacznik | A | = 0, to daną macierz kwadratową nazywam y macierzą osobliwą, 3) macierzą odwrotną nieosobliwej kw adratow ej m a­ cierzy A nazywamy taką macierz A-1, dla której: A -i =

.

(9)

IA | Dla każdej nieosobliwej macierzy A istnieje jedna i tylko jedna macierz odw rotna A-1 spełniająca relację: A A -i = A-1 A = 1.

(10)

Macierze osobliwe nie m ają macierzy odwrotnych, ze względu na | A j = 0. Mnożenie dwóch macierzy A i B jest określone (mo­ żliwe) tylko wtedy, gdy liczba kolumn macierzy A jest rów na liczbie wierszy macierzy B. W yjaśnia to tzw. schemat Falka [2] przedstawiony na rysunku 1. .30

Rysunek 1 S chem at Falka mnożenia macierzy przez macierz

P* =

M, m 2 M3 m 4 M5 m 6 m 7 m 8 m 9 M10 Mn Mn Mi Ci

0 10 0

C2 0 10

0 5

5 0

0 10 0 10

0 5

5 0

0 10 10

0

10

0 10

0

4. Z tablicy 2, po uwzględnieniu postaci macierzy C zapisanej w tablicy 3, możemy obliczyć podział nakła­ dów pracy według stanowisk Ri—R5 w poszczególnych jednostkach cyklu (tablica 5). Liczby zawarte w tabli­ cy 5 oznaczymy jako macierz C*. Za pomocą prostej operacji mnożenia macierzy przez macierz: C* p* — t (13) możemy obliczyć obciążenie poszczególnych stanowisk i?i— R 5 w 1980 r. w związku z produkcją wyrobu Pi (zob. tablica 6). 34

Tablica 5 Rl Rz

r3 s r4

Rs

2 2 15 0 7

2 6 5 6 0

26

19

T ab lica 6

Mie­ siące

M, m 2 m 3 m 4 m 5 m 6 m 7 m 8 m 9 m 19 Mn m 12

Mi

Ri

10 20 20 10

10

20

20 10

10

10

20

10

190

r2

10 60 20 30

10

60

20 30

10

60

20

60

390

r3

75 50 150 25

75

50 150 25

75

50 150

50

925

0 30

0

60

0 70 0

35

0

r4

r5

Z

0 60 35

0 30

0

60

0

60

300

0

35

0

70

0

315

70

130 190 260 95 130 190 260 95 130 180 260 180 2120

Analiza p rzep ływ ó w m iędzygałęziow ych Symbol: 2 - BA Klasa trudności: I Klasa zastosowań: pr, pl, k

Z asto so w an ie m etody (ro zw iązyw an e problem y)

Za pomocą tej metody można opisywać i badać nie tylko przepływy dóbr między gałęziami gospodarki n a­ rodowej, ale także między poszczególnymi branżami, podbranżami i grupam i wyrobów oraz jednostkam i’ organizacyjnymi gospodarki narodowej: zakładami pro­ dukcyjnymi, przedsiębiorstwami, kombinatami, zjedno­ czeniami, resortam i itp. Metoda była początkowo sto­ sowana głównie ex post przez urzędy statystyczne różnych krajów. W ostatnim dwudziestoleciu wyko­ rzystyw ana jest także do programowania i planowania działania. Opis, schem at m etody

Analiza nakładów i wyników stosowana do opisu i ba­ dania problemów zarządzania w skali gospodarki naro­ dowej nazywana jest analizą przepływów międzygałęziowyćh. Przedstawiam y poniżej najprostszy w ariant metody analizy przepływów międzygałęziowych. 1. Załóżmy, że gospodarka narodowa dzieli się na n gałęzi i-tych (i = 1, 2, . . . , n), z których każda w ytw a36

rza pewną produkcję globalną X t. Produkcja globalna X* dzieli się na: — produkcję końcową (i = 1, 2, . . ri) przeznaczoną na cele nieprodukcyjne, np. spożycie indywidualne i społeczne, wzrost zapasów, inwestycje itp., — bieżące spożycie produkcyjne w n gałęziach j-tych (j = 1, 2, ..., ti), oznaczone jako x xj (i, j = 1, 2, ..., n). Związki między wielkościami X i} y i oraz xi3- wyrażają równania: Xi = x n + x 12 -f .. . + x ln + y\ X 2 = ^21 4“ ^22 4“ . • . X 2n + y Xn

.

x n±H- x n 2 "ł- . . . "ł~ x nn ~ł~ y n

2. Jak widać z układu rów nań (1), w analizie przepły­ wów międzygałęzionych zakładamy proporcjonalną (li­ niową) zależność między bieżącym spożyciem produk­ cyjnym (x^ ) i produkcją globalną poszczególnych ga­ łęzi (X t). Związek ten wyraża się za pomocą współ­ czynników technicznych ali} będących współczynnikami nakładów bezpośrednich: (2).

Xj

z czego wynika: (3)

Xii = Qri]Xj.'

Po podstawieniu do praw ej strony rów nań z układu (1) wartości x ij z wzoru (3) i odpowiednim przekształceniu formalnym układu rów nań (1) otrzymamy: (Xi o11X 1) a2iXj + (X2 dn\X-y

an2X2

a 12X 2 — . . . a22X 2) ... . . . *ł" (Xn

alnX n — y x a2nX n = y 2 flnnX n)

yn

Równania te można napisać również w następującej postaci: (1

dn)Xi (1

d\2^-2

•• •

^ 2 2 )^ 2

d 2 ^ X i "h

^n2-^2

...

n-^n •••

"h (1

nXn

ttnn)Xn

V\ ^/2

Vn

albo w symbolice macierzowej: ( I - A ) X = Y,

(6)

gdzie: (I - A) — macierz strukturalna, I — macierz jednostkowa stopnia n, Y — wektor produkcji końcowej o składowych y i (i = 1, 2, . .., n), A — macierz współczynników technicznych (i, j = 1, 2, . .., n), X — wektor produkcji globalnej o składowych Xt (i = 1, 2, ..., n). 3. Zależności (6) pozwalają określić wielkość i stru k ­ tu rę produkcji końcowej Y na podstawie danych doty­ czących wielkości produkcji globalnej X i współczyn­ ników technicznych atj. I odwrotnie: znając wielkość produkcji końcowej Y oraz współczynniki dxj możemy obliczyć wielkość produkcji globalnej X — w ykorzy­ stując przekształcony nieco wzór (6): X = (I - A)-1 Y,

(7)

gdzie: (I — A)-1 — macierz odwotna do macierzy stru k tu ral­ nej (I — A), stanowiąca macierz współ­ czynników pełnego, czyli „ciągnionego” nakładu, które uwzględniają nakłady bez­ pośrednie i pośrednie wszystkich gałęzi. 38

^

Analizę przepływów międzygałęziowych na podstawie wzorów (6) i (7) można prowadzić zarówno w jednostkach fizycznych, jak też w jednostkach pieniężnych. E fe k ty w n o ś ć i ko szty m etody

Analiza przepływów międzygałęziowych sprawdziła się już wielokrotnie w przeszłości jako wartościowe na­ rzędzie opisu i badania problemów zarządzania, zarów­ no na etapie programowania i planowania, jak też kon­ troli i oceny efektów działania. Kilkadziesiąt lat tem u najbardziej kosztowną opeiracją obliczeniową było od­ wracanie macierzy strukturalnej (I — A) do postaci (I — A)-1. Współczesne kom putery wyposażone są w tzw. biblioteczne program y odwracania macierzy i w ykonują tę operację obliczeniową stosunkowo szyb­ ko i tanio, nawet gdy stopień macierzy n jest duży. Metoda wymaga istnienia odpowiednio dużych zbiorów danych liczbowych (wartości współczynników a^). Sposób nauczania lub posług iw an ia się m etod ą

Jak w przypadku analizy strukturalnej.

LITERATURA

[1] Antosik K., Doświadczenia Głównego Urzędu Statystycznego w dziedzinie opracowywania bilansów przepływów między­ gałęziowych, referat na VIII Międzynarodowe Sympozjum Gospodarki Materiałowej, Warszawa 1973. [2] Czechowski T., Wstęp matematyczny do analizy przepływów międzygałęziowych, PWE, Warszawa 1958. [3] Czerwiński Z., Matematyka na usługach ekonomii, wyd. 4, PWN, Warszawa 1977, rozdział 3.1. [4] Sulmicki P., Przepływy między gałęziowe, PWG, Warszawa 1959.

39

Przykład zastosow ania m etody

Doświadczenie Głównego Urzędu Statystycznego w dziedżinie wykorzystania analizy przepływów międzygałę­ ziowych na szczeblu całej gospodarki narodowej (w po­ staci tzw. bilansów przepływów międzygałęziowych) opisuje K. Antosik [1]. 1. Bilans przepływów międzygałęziowych jako rozwi­ nięta forma bilansu tworzenia i podziału produktu globalnego i dochodu narodowego: — pozwala na szczegółową charakterystykę rzeczywi­ stego procesu rozszerzonej reprodukcji socjalistycz­ nej, przedstawia podstawowe proporcje ekonomiczne i międzygałęziowe współzależności występujące w gospodarce narodowej oraz umożliwia analizę po­ niesionych nakładów i osiągniętych wyników, — stanowi ważne narzędzie doskonalenia i rozwoju metodologii planowania gospodarki narodowej oraz stw arza szerokie możliwości zastosowania w plano­ waniu współczesnych metod matem atycznych i elek­ tronicznej techniki obliczeniowej, — wpływ a na doskonalenie i rozwój sprawozdawczości i statystyki ekonomicznej. 2. W Polsce zostały wypracowane dwa rodzaje badań przepływów międzygałęziowych. Pierw szy z nich po­ lega na przeprowadzeniu co kilka lat jednorazowego, 'specjalnego badania przepływów międzygałęziowych, umożliwiającego zestawienie szczegółowego bilansu przepływów międzygałęziowych. Natom iast drugi ro­ dzaj badań polega na opracowywaniu bilansów prze­ pływów międzygałęziowych o ograniczonej szczegóło­ wości na podstawie bieżącej sprawozdawczości, niektó­ rych materiałów badań jednorazowych i opracowań ekspertów. 3. Model bilansu ma formę szachownicy. W główce tablicy zastosowano klasyfikację podmiotową (na pod­ 40

t

stawie Klasyfikacji Gospodarki Narodowej), a w bocz­ ku tablicy — klasyfikację przedmiotową (opartą na System atycznym Wykazie W yrobów, Klasyfikacji Usług i Klasyfikacji Obiektów Budowlanych). W w yniku ta­ kich ustaleń przepływ x lJ oznacza zużycie dobra ma­ terialnego pochodzącego z gałęzi i-tej przez przedsię­ biorstwa zaliczane do gałęzi j-tej, a nie zużycie dobra i-tego na wyprodukowanie dobra j-tego. 4. W bilansie można wyróżnić cztery podstawowe czę­ ści. Część I przedstawia tzw. bieżące przepływ y dóbr ma­ terialnych pochodzenia krajowego i zagranicznego w ram ach sfery produkcji m aterialnej. Część II ujm uje przepływy dóbr m aterialnych związa­ ne z zaspokojeniem popytu końcowego (spożycie przez ludność dóbr m aterialnych z dochodów osobistych, spożycie pozostałe, nakłady na inwestycje zwiększające wartości środków trw ałych i rem onty kapitalne, zmia­ ny w stanach zapasów rzeczowych środków obrotowych i rezerw oraz eksport). Część III zawiera dane o tworzeniu produktu global­ nego (wielkość nakładów pracy uprzedmiotowionej ogółem i nakładów pracy żywej w poszczególnych ga­ łęziach produkcji m aterialnej) oraz dane o podziale pierwotnym produkcji czystej (dochodu narodowego). Część IV przeznaczona jest na inform acje o w tórnym podziale dochodu narodowego. Część ta nie jest wy­ pełniana. 5. Dane liczbowe zawarte w bilansie przepływów mię­ dzygałęziowych wyceniane są według faktycznych, bie­ żących cen istniejących w danym roku. Ze względu na sposób wyceny danych opracowywane są dwa wa­ rianty bilansu przepływów międzygałęziowych. Wariant I ujm uje dane w cenach *płaconych przez ostatecznych odbiorców. Dotyczą one zarówno dóbr 41

wyprodukowanych w kraju, jak i pochodzących z im­ portu. Wariant II zawiera dane w cenach uzyskiwanych przez producentów. Również i w tym przypadku obejmują one dobra wyprodukowane w kraju i pochodzące z im­ portu. Przepływ wi} (wariant I) różni się od przepływu x tj (w ariant II) o wartość m arży mł3- zrealizowanej na do­ stawach dóbr m aterialnych wyprodukowanych w ga­ łęzi i-tej bądź pochodzących z im portu „uzupełniają­ cego” produkcję tej gałęzi, a zużytych przez gałąź j-tą. Dobra m aterialne pochodzące z im portu zestawiane są w formie tablicy szachownicowej, opracowywanej w e­ dług tych samych zasad klasyfikacyjnych, co bilans przypływów międzygałęziowych. Dane o podziale wartości usług m aterialnych wykazy­ w ane są w odpowiednich wierszach bilansu przepły­ wów międzygałęziowych, najczęściej łącznie z danymi 0 podziale wartości wyrobów. 6. Bilans przepływów międzygałęziowych w gospodar­ ce narodowej Polski dla 1971 r. opracowano w ukła­ dzie 40 X 40 gałęzi w następujących wariantach: — w cenach płaconych przez ostatecznych odbiorców w w ersji bez wydzielania przepływów dóbr m ate­ rialnych pochodzących z importu, — w cenach uzyskiwanych przez producentów w w er­ sji bez wydzielania przepływów dóbr m aterialnych pochodzących z importu, — w cenach uzyskiwanych przez producentów w w er­ sji z wydzieleniem przepływów dóbr materialnych pochodzących z importu. Bilans uzupełniają szachownicowe tablice im portu 1 m arży oraz dane dotyczące m ajątku trwałego, m ająt­ ku obrotowego i zatrudnienia. 7. Opracowywany jest także bilans przepływów mię42

dzygałęziowych uwzględniający układ organizacyjny. Można w nim wyróżnić pięć części. Część I ujm uje na głównej przekątnej produkcję glo­ balną, im port i marżę. Część II przedstawia działy sfery produkcji m aterial­ nej, w ram ach działów — ważniejsze resorty, a w ra ­ mach resortów — ważniejsze gałęzie. Część III jest taka sama jak w norm alnym bilansie przepływów międzygałęziowych, tj. zawiera popyt koń­ cowy (spożycie przez ludność dóbr m aterialnych z do­ chodów osobistych, pozostałe spożycie, nakłady inwe­ stycyjne zwiększające wartość środków trw ałych i n a­ kłady na rem onty kapitalne, zmiany w stanach zapa­ sów rzeczowych środków obrotowych i rezerw oraz eksport). Część IV prezentuje działy sfery produkcji m aterialnej, w ram ach działów — ważniejsze resorty, a w ram ach resortów — ważniejsze gałęzie; ma więc taki sam układ jak część II. Część V ujm uje na głównej przekątnej produkcję glo­ balną. Ponadto w bilansie wykazywane są dane doty­ czące importu, m ajątku trwałego i zawodowo czynnych. Dobra m aterialne pochodzące z im portu przedstawiono w takim układzie, jak w bilansie, ale tylko w odnie­ sieniu do części I, II i III. f

Analiza strukturalna Symbol: 3-BA Klasa trudności: II Klasa zastosowań: pr, pl, k

* Z asto so w an ie m etody (ro zw iązyw an e pro b lem y)

Analiza strukturalna może być efektywnie stosowana do rozwiązywania deterministycznych problemów za­ rządzania na etapie programowania i planowania, a także kontroli i oceny. W tym ostatnim przypadku za pomocą tej metody można obliczyć i ocenić rzeczy­ w isty wpływ (ciągnione konsekwencje) poszczególnych czynników produkcji na jej ostateczne efekty. O pis, sch em at m etody

Analiza nakładów i wyników przybiera różne nazwy v/ zależności od dziedziny zastosowań. W przypadku gdy za jej pomocą opisuje się strukturę pewnych ukła­ dów lub procesów, nosi ona nazwę analizy stru ktu ­ ralnej. Analizę strukturalną przeprowadza się na podstawie drzewa nakładów, które pomaga określić całkowite nakłady jednego rodzaju na jednostkę produkcji dru­ giego. rodzaju przez zsumowanie jednostkowych nakła­ dów bezpośrednich ii nakładów pośrednich wszystkich ■rzędów (rysunek 1). 44

Rysunek 1 Schem at nakładów bezpośrednich i pośrednich energii elektrycznej na produkcję maszyn

(naWady pośrednie I I I rzędu)

(nakłody pośrednie II rzędu)

(nokłaęly pośrednie I rzędu)

(nakłady bezpośrednie)

(produkcja maszyn w tonoch)

Pn

*01

Pi

Sumowanie takie dokonywane metodami tradycyjnym i jest kłopotliwe i pracochłonne, gdy obejmuje wiele rodzajów produkcji i nakładów. Stosunkowo proste drzewo nakładów rozrasta się (wydłuża i rozgałęzia) w sposób nie ograniczony. Z drugiej jednak strony sumowanie tego rodzaju jest niezbędne zarówno w po­ szczególnych przedsiębiorstwach, jak i całej gospodarce narodowej, pozwala bowiem na opracowywanie planów zbilansowanych i w ewnętrznie zgodnych. Zastosowanie analizy strukturalnej upraszcza, ułatwia i przyspiesza niezbędne obliczenia, co chcemy pokazać na przykła­ dzie wziętym z przedsiębiorstwa przemysłowego. 1. Załóżmy, że między produktam i poszczególnych faz procesu technologicznego zachodzą powiązania przed­ stawione na rysunku 2, odzwierciedlające strukturę produkcji pewnego przedsiębiorstwa [2]: — w fazie I wytw arzane są części (detale) 1—4, — w fazie II z części-tych montowane są zespoły kon­ strukcyjne 5, 8 i 7, — w fazie III z poszczególnych zespołów i części mon­ tuje się wyroby gotowe 8, 9 i 10. 2. Macierz D tzw. współczynników bezpośredniego zużycia, przedstawiona w postaci tablicy 1, charakte­ 45

ryzuje ilościowo powiązania między produktam i po­ szczególnych faz procesu technologicznego. Na przy­ kład można z niej odczytać, że: Rysunek 2 Drzewo powiązań wyrobów i ich ele­ mentów składowych Części Zespoły konstrukcyjne Wyroby gotowe

— część 1 wchodzi bezpośrecłnio do zespołu 5 w ilości 1 szt., do zespołu 6 w ilości 1 szt. oraz do wyrobu gotowego 8 w ilości 2 szt.; — część 2 wchodzi bezpośrednio do zespołu 5 w ilości 2 szt. oraz do zespołu 7 w ilości 1 szt. T a b lic a 1 M a cie rz w sp ó łc zy n n ik ó w b e z p o ś r e d ­ n ie g o z u i y c i a

Produkty | 1

2

3

4

5

6

7

8 9

10

1 2 3 4

0 U 0 0

0 0 0 0

0 0 0 0

0 0 0 0

1 2 0 0

1 0 1 0'

0 1 2 1

2 0 0 0

0 0 0 0

0 0 0 1

5 6 7

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

1 0 1

1 1 0

2 0 1

8 9 10

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

3. Jeżeli teraz macierz D odejmiemy od macierzy jed­ nostkowej I, tego samego stopnia co macierz D, to otrzym am y tzw. macierz strukturalną (I — D). 46

t

Macierz odwrotna 1 do macierzy (I — D), czyli macierz (l — D)-1, przedstawiona w tablicy 2, zawiera współ­ czynniki pełnego (ciągnionego) zużycia produktów po­ szczególnych faz technologicznych. Na przykład z tab­ licy 2 możemy odczytać, że do wyrobu gotowego 10 zużywa się 2 szt. części 1, 5 szt. części 2, 2 szt. części 3, 2 szt. części 4, 2 szt. zespołu 5 itp. T a b lic a 2 M a c ie rz w sp ó łc zy n n ik ó w ( c iq g n io n e g o ) z u ż y c i a ^

p e łn e g o

1

2

3

4

5

C

7

8

9

10

1 2 3 4

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

1 2 0 0

1 0 1 0

0 1 2 1

3 3 2 1

2 2 1 0

2 5 2 2

5 6 7

0 0 0

0 0 0

0 0 0

0 0 0

1 0 0

0 1 0

0 0 1

1 0 1

1 1 0

2 0 1

8 9 10

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

0 0 0

1 0 0

0 1 0

0 0 1

Korzyści z dysponowania macierzą (I D)-1 mogą być wielorakie: — po pomnożeniu jej praw ostronnie przez kolumno­ wy wektor produkcji sprzedawanej na zewnątrz przedsiębiorstwa uzyskam y w ektor tzw. produkcji globalnej, zawierający liczby sztuk wszystkich pro­ duktów poszczególnych faz procesu technologicz­ nego, — po pomnożeniu tego wektora lewostronnie przez wierszowy w ektor kosztów jednostkowych otrzy­ m amy wartość kosztów własnych produkcji itp. * Jedną z metod odwracania macierzy omówiono w pracy [3J.

47

E fe k ty w n o ś ć i ko szty m etody

W szystkie obliczenia konieczne do przeprowadzenia 1 analizy strukturalnej wykonywane są za pomocą kom­ putera szybko i tanio. Odpowiednie dane liczbowe z re­ guły zawarte są w dokumentacji techniczno-produk­ cyjnej i ekonomicznej przedsiębiorstwa. Sposób nauczania lub po sług iw ania się m eto dą

Znajomość różnych algorytmów odwracania macierzy nie jest , potrze,bna do matematycznego modelowania problemów zarządzania opisywanych i badanych za pomocą analizy strukturalnej, konieczna jest natomiast bardzo dobra orientacja w m erytorycznych (np. tech­ niczno-ekonomicznych) aspektach rozwiązywanych pro­ blemów. Podstawy algebry macierzy można sobie przy­ swoić w trakcie nauki w szkole średniej.

LITERATURA

[1] Czerwiński Z., Matematyka na usługach ekonomii, wyd. 4, PWN, Warszawa 1977, rozdział 3.1. [2] Matrizen und elektronische Rechenautomaten bei der Planung in Industriebetrieben, Zentralinstitut fur Automatisierung, Drezno 1964. [31 Radzikowski W., Metody matematyczne i statystyczne w przedsiębiorstwie, wyd. 2, PWE, Warszawa 1976, roz­ dział 8. [4] Tieriechow L., Metody ekonomiczno-matematyczne, PWE* Warszawa 1970, rozdziały I i II.

Badania operacyjne Symbol: 4 - BI Klasa trudności: II Klasa zastosowań: pp, pr, pl, op, k

Z asto so w an ie m eto dy (ro zw ią zy w a n e p roblem y) /

Badania operacyjne służą do rozwiązywania problemów zarządzania przede wszystkim w losowych, niepewnych i konfliktowych 1 sytuacjach decyzyjnych, kiedy to nie jest rzeczą łatw ą właściwie określić: — dane zjawisko, gdyż w przedsiębiorstwie istnieje wiele zjawisk i wielkości, których nie można od razu i po prostu ustalić (np. wielkości nierówno­ miernie w ystępujące w czasie czy powtarzające się periodycznie), — ciężar gatunkowy poszczególnych zjawisk, a więc ich rolę i znaczenie. Zastosowanie badań operacyjnych pozwala na możliwie najbardziej obiektywne odzwierciedlenie zachodzących w przedsiębiorstwie procesów i zjawisk, dzięki czemu stw arza obiektywne przesłanki podejmowania decyzji. W zasadzie większość problemów zarządzania można by próbować rozwiązywać metodam i badań operacyjnych. 1 Z tego względu w badaniach operacyjnych częściej wykorzystuje się metody statystyczne i rachunek prawdopodobieństwa, m etody progra­ mowania stochastycznego, stochastyczne metody sieciowe, teorię gier, metody sym ulacyjne itp., rzadziej natomiast metody optymalizacyjne programowania matematycznego (np. programowanie liniowe). 4 Matematyczne techniki zarządzania

49

W praktyce ustaliły się jednak pewne typow e dziedziny ich zastosowania. Badania operacyjne na ogół klasyfikuje się według po­ niższych typów modeli matematycznych: — model zapasów („ile” i „kiedy” produkować, kupo­ wać, magazynować itp.), — model alokacji, czyli rozmieszczenia („czego”, „ile” i „gdzie” produkować, przewozić itp.), — model oczekiwania (długość kolejek, harmonogramy przybyć, obsługa maszyn itp.), — model marszruty (transportowy) („w jaki sposób” najlepiej i najtaniej można „odwiedzić” kilka m iej­ scowości i wrócić do punktu wyjściowego), — model renowacji, czyli odnowienia („kiedy” wymie­ nić stare urządzenia na nowe itp.), — model konkurencji (najlepsza polityka zakupów i sprzedaży, rozmieszczenie produkcji w warunkach konkurencji itp.), albo też według dziedzin zastosowania, np.: a) obliczenie norm atywów wielkości odpadów w pro­ cesie produkcji na podstawie danych o rozmiarach odpadów produkcyjnych w okresie ubiegłym, b>) ustalenie najbardziej ekonomicznych metod staty­ stycznej kontroli jakości, c) określenie liczby inżynierów — organizatorów pro­ dukcji potrzebnych do wykonania projektowanego rozm iaru prac, d) operatywne kierowanie produkcją, kontrola i regu­ lowanie wielkości środków materiałowo-technicz­ nych, a mianowicie: — obliczenie obciążenia urządzeń zapewniającego ich pełne wykorzystanie, — określenie zapotrzebowania na produkowane w y­ roby na podstawie wyrywkowego badania zbytu, — kontrola zamówień (zleceń) na wykonywane de­ tale w celu ustalenia najmniejszych rozmiarów 50

zapasów niezbędnych do normalnego przebiegu procesu produkcji, — rozstrzyganie problemu celowości tworzenia za­ pasu produkcji w toku, stosowania pracy w go­ dzinach nadliczbowych lub wprowadzenia dodat­ kowej zmiany, — opracowanie planów zapewniających minim alne koszty produkcji, e) rem ont maszyn i urządzeń produkcyjnych, a więc określenie: — najbardziej ekonomicznego kosztorysu wykona­ nia zapobiegawczego rem ontu urządzeń, — ekonomicznie uzasadnionego stosunku liczbowego personelu remontowego do liczby urządzeń, — dostatecznie wczesne terminów zakończenia mon­ tażu lamp elektronowych, maszyn itp., — liczby części zam iennych w magazynie niezbęd­ nej do zapewnienia normalnego i ekonomicznego procesu produkcji. Opis, schem at m etody

Określenie badania operacyjne jest dosłownym tłum a­ czeniem angielskiego pojęcia Operutions Research. Naj­ lepiej byłoby przetłumaczyć je jako analiza operacji, chodzi bowiem o analizę i dokładne określenie (za po­ mocą metod matematycznych) zjawisk i procesów za­ chodzących w przedsiębiorstwie. Badania operacyjne m ają wybitnie wojskowy rodowód. W czasie drugiej w ojny światowej przy niektórych sztabach alianckich sił zbrojnych utworzono specjalne grupy zajmujące się badaniem operacji wojennych, np. niszczenia okrętów podwodnych przeciwnika, ochrony konwojów okrętów, obrony przeciwlotniczej. Na pod­ 51

staw ie badania doświadczeń nagromadzonych w toku działań wojennych i ich naukowej analizy grupy te dawały wskazówki co do odpowiedniego rozmieszcze­ nia sił i środków oraz wyboru najbardziej efektywnych metod prowadzenia operacji. Istota badań operacyjnych polega na gromadzeniu (za pomocą obserwacji lub badań) liczbowych m ateria­ łów inform acyjnych o pracach ważnych dla przedsię­ biorstwa i na tej podstawie szukaniu takich organiza­ cyjnych rozwiązań, które pozwolą osiągnąć w ynik optymalnie odpowiadający wybranem u kryterium. W tym celu stosuje się analizę matematyczną, szuka podstawowych zasad prowadzenia działań i dochodzi do wniosków o prawdopodobnych wynikach różnorod­ nych działań. Wnioski końcowe m ają najczęściej formę alternatywną, zamiast jednego „właściwego” wyniku końcowego. Metoda ta jest stosowana z największym pożytkiem przy problemach kom pleksowych, w których trzeba uwzględnić wiele czynników, a części składowe problemu można w sposób kw antytatyw ny mierzyć i opisać.

E fe k ty w n o ś ć i koszty m etody

W arunkiem uzyskania optym alnych rozwiązań i m aksy­ m alnych korzyści jest rozpatrywanie i rozwiązywanie zagadnień ekonomiczno-organizacyjnych w ujęciu mo­ żliwie najbardziej kompleksowym. Inaczej zdarzyć się może, że wprawdzie w jednej części przedsiębiorstwa osiągnie się zysk, ale w innej powstaną straty prze­ wyższające zysk. Koszty stosowania badań operacyj­ nych trudno nieraz określić. Są one jednak z reguły wysokie ze względu na indywidualne rozważanie każ­ dego problemu zarządzania w unikalnych, zwykle nie­ pow tarzalnych w arunkach. 52

Sposób nauczania lub posługiwania się metodą Stosowanie badań operacyjnych jest z natu ry rzeczy wynikiem pracy zespołu specjalistów o różnorodnej wiedzy i doświadczeniu zawodowym. Badania przepro­ wadza się zawsze w konkretnym przedsiębiorstwie, zjednoczeniu itp. Zespoły robocze badań operacyjnych muszę więc ustosunkować się do istniejącej sytuacji, która jest dziełem ludzi zatrudnionych w tych jednost­ kach organizacyjnych. Niestety, często ułożenie współ­ pracy między członkami zespołów przeprowadzających badania a pracownikami jest trudne. Kłopoty zaczynają się czasem jeszcze przed rozpoczęciem badań, a niekie­ dy już po ich zakończeniu. Bardzo często trudno roz­ poznać, co jest przyczyną powstałej sytuacji konflik­ towej, a co jej skutkiem. W arto więc pam iętać o pew­ nych zasadach współpracy z ludźmi, które obowiązują członków zespołów roboczych badań operacyjnych. 1. Należy upewnić się, czy proponowane usprawnienia organizacyjno-techniczne nie wywołują niekorzystnych w tórnych efektów emocjonalnych u pracowników ba­ danych jednostek organizacyjnych, co mogłoby zniwe­ czyć całą wartość i użyteczność tych usprawnień. Duże znaczenie ma wyprzedzająca działalność wyjaśniająca i m otywacyjna kierownictwa badanych jednostek orga­ nizacyjnych, która powinna zapobiegać powstawaniu niedomówień i nieporozumień wśród załogi. 2. Członkowie zespołów roboczych badań operacyjnych nie powinni zachowywać się jak kontrolerzy. lub pro­ kuratorzy. Wiadomo przecież powszechnie, jak duże obawy i opory załóg wzbudza wszystko, co w najm niej­ szym naw et stopniu przypom ina kontrolę. 3. Nie wolno członkom zespołów roboczych badań ope­ racyjnych nadużywać terminologii m atem atycznej lub informatycznej, czy też stosować żargonu niezrozumia­ łego dla „zwykłego człowieka” — pod groźbą u traty 53

kontaktu i współpracy z załogami badanych jednostek organizacyjnych. 4. Warto, aby specjaliści od badań operacyjnych pa­ miętali, że stosowanie matematycznych symboli nie może być w żadnym przypadku dowodem tn!ieomylnego m yślenia i prawidłowości wniosków końcowych. 5. Nie wolno zapominać, że badania operacyjne są tylko narzędziem pomocniczym, a nie jeszcze jednym elementem systemu inakazów ,i zakazów, które i tak obowiązują zarządzającego.

LITERATURA

[1] Ambroziak T., Spratek L., Wiak M., Wybrane problemy i metody prognozowania, OBRI, Warszawa 1973. [2] Chorobiński A., Metoda P ATT ERN: programowanie i pla­ nowanie prac badawczych, „Przegląd Organizacji” 1973, nr 3. [3] Gottner R , Badania operacyjne. Oczekiwania i zastosowa­ nia, PWE, Warszawa 1975. [4] Kaufman A., Faure R., Badania operacyjne na co dzień, PWE, Warszawa 1969. [5] Proces decyzyjny, OBRI-INFORNA, Warszawa 1973. [6] Radzikowski W., Metody matematyczne i statystyczne w przedsiębiorstwie, wyd. 2, PWE, Warszawa 1976. [7] Sadowski W., Teoria podejmowania decyzji, wyd. 6, PWE, Warszawa 1976. [8] Trocki M., Ocena elementów w metodzie PATTERN, „Prze­ gląd Organizacji” 1973, nr 6.

Gromadzenie danych liczbowych W badaniach operacyjnych ważną rolę odgrywa zbie­ ranie danych liczbowych o procesach będących przed­ miotem analizy. Brak wiarygodnych, kompletnych in­ form acji utrudnia bowiem podejmowanie decyzji kie­ rownikowi przedsiębiorstwa. Jest więc rzeczą ważną wiedzieć, jak szybko można zdobyć właściwe i dosta­ 54

tecznie dokładne dane liczbowe o działalności przed­ siębiorstwa. W bardzo wielu przypadkach w ystarcza­ jąco dokładne dane liczbowe otrzym ujem y za pomocą badań wyryw kow ych. Zbędne jest wówczas sięganie do wyczerpujących badań statystycznych. Właściwe przeprowadzenie badań wyrywkowych jest sztuką, któ­ rej trzeba i można się nauczyć. Nie będziemy szcze­ gółowo omawiać w tym miejscu metody badań wy­ rywkowych, ale podamy kilka podstawowych wskazó­ wek. Przypuśćmy, że interesuje nas sprawa wykorzystania czasu pracy robotników. Nie musim y przeglądać wszy­ stkich np. 40 000 kart pracy z całego roku, lecz wy­ starczy w ybranie 4000 spośród nich. Próba musi być pobrana w taki sposób, aby jej struktura była dokład­ nie taka sama, jak wszystkich kart. Najwłaściwszym sposobem postępowania, który pozwala w maksymalnie możliwym stopniu uniknąć systematycznie pow tarzają­ cych się błędów badania wyrywkowego, jest przypad­ kow y wybór próbki. Dokładność badania wyrywkowego można znacznie zwiększyć przy tych samych kosztach, jeżeli przestrze­ ga się zasady rozwarstwienia materiału badanego: Na przykład badając geograficzny rozkład sprzedaży okre­ ślonego wyrobu konsumpcyjnego (np. radioodbiorni­ ków), musimy osobno rozpatrywać tereny wiejskie i m iasta (na wsi różnice w konsumpcji są mniejsze niż W mieście), aby wyciągnąć właściwe wnioski co do dal­ szej produkcji (i sprzedaży) tego wyrobu. W celu zwiększenia dokładności badania wyrywkowego przy tych samych kosztach można stosować wielostop­ niowe plany badania, np. do statystycznej kontroli ja­ kości wyrobów. Plany wielostopniowe polegają na tym, że w partii wyrobów pobiera się kolejno w kilku eta­ pach próbki o tej samej liczebności n. Zależnie od liczby wybrakowanych sztuk znalezionych w próbce 55

pierwszego stopnia albo uznaje się partię za złą lub dobrą, albo pobiera drugą próbkę. Jeżeli i teraz nie nastąpi rozstrzygnięcie, to pobiera się trzecią próbkę" itp. aż do rozstrzygnięcia. Budowę odpowiednich reguł wnioskowania o param et­ rach pewnej zbiorowości statystycznej na podstawie zbadania jej części zajmuje się dział statystyki zwany teorią estym a cji2 lub teorią szacowania. Podamy przy­ kład charakteryzujący zastosowanie tej teorii w prak­ tyce. Porównujem y dwa procesy technologiczne produkcji wyrobu P w celu rozstrzygnięcia, który z nich daje produkt lepszej jakości. Zakładamy, że każda sztuka wyrobu P może być albo dobra, albo zła, a jakość produktu określa udział sztuk złych w całej zbioro­ wości. Przeprowadzenie wyczerpujących badań staty­ stycznych jest w tym przypadku niemożliwe, gdyż trzeba było zbadać dwie zbiorowości statystyczne nie­ skończone, a mianowicie zbiory wszystkich jednostek produktu P otrzymanych-przy zastosowaniu technologii pierwszej i drugiej. Niezbędne jest więc przeprowa­ dzenie badań wyrywkowych, np. zbadania dwóch dziesięcioelementowych próbek: pierwszą może stanowić 10 kolejnych sztuk produktu P wykonanych za pomocą technologii pierwszej (Pi), drugą — 10 kolejnych sztuk produktu P wykonanych za pomocą technologii dru­ giej (P2). Wyniki badania wyrywkowego (w tym przy­ padku chodzi o wyniki produkcji próbnej) przedstawio­ no w tablicy 1. Analiza wyników wskazuje, że drugi proces technolo­ giczny daje produkt P o lepszej jakości (20% sztuk złych) niż pierwszy (30% sztuk złych). Tego rodzaju hipotezę statystyczną trzeba zweryfikować np. przez zwiększenie liczebności próbki. Należy również zauwa1 Teorię estymacji i jej zastosowania praktyczne omówiono w pracy [7]*.

56

T ablic Numer sztuki

1 2 3 4 5 6 7 8 9 10

Wy nik i b a d a ń p r o d u k ji p r ó b n e ! Jakość sztuki Pi

dobra dobra zła dobra dobra zła zła dobra dobra dobra

Udział złych sztuk P,

w % 0 0 33 25 20 33 43 38 33 30

Jakość sztuki P t

Udział złych sztuk Pf

f zła dobra dobra dobra dobra dobra dobra zła dobra dobra

w% 100 50 33 25 20 17 15 25 22 20

Źródło: [7].

żyć, że liczebność próbki nie może być zbyt mała. Na przykład ograniczając się do zbadania tylko dwóch sztuk w każdej z obu próbek, wyżej ocenilibyśmy pierwszy proces technologiczny (0% sztuk złych), co jak się później okazuje byłoby wnioskiem fałszy­ wym. Umiejętne stosowanie metody badań wyrywkowych pozwala na gromadzenie m ateriałów liczbowych dosta­ tecznie dokładnych do celów badań operacyjnych. Dys­ ponowanie kompletnym, wyczerpującym m ateriałem statystycznym (wiarygodna ewidencja) ma oczywiście zawsze duże znaczenie.

Posługiwanie się modelami matem atycznym i Na podstawie zebranego i opracowanego m ateriału licz­ bowego możemy zbudować model matematyczny, który będzie odpowiadać badanym procesom przedsiębior­ stwa. 57

K onstruując ten model musimy korzystać z pewnych schematów. Jak długo jednak model obejmuje istotną treść badanego procesu, tak długo świadczy wartościo­ we usługi — nawet gdy nie uwzględnia i nie oddaje wiernie wszystkich szczegółów procesu. Uzyskany w y­ nik będzie zawsze dokładniejszy niż stosowane przy podejmowaniu decyzji „przewidywanie” lub decydowa­ nie się na „wyczucie”. W wielu przypadkach zupełnie wystarczy posługiwanie się znanymi ze statystyki ma­ tematycznej najprostszymi rozkładami prawdopodo­ bieństwa. O zmiennej X mówimy, że ma rozkład nor­ m a lny, jeżeli jej gęstość prawdopodobieństwa f (a;) jest określona wzorem:

a y 2n

(x — m)2 2o2

( 1)

gdzie: exp (x) — funkcja ex, e — podstawa logarytmów naturalnych (e = 2,71828 . ..), m — średnia, o — odchylenie standardowe. Rozkład normalny można zastosować w następującym procesie. W jednej ze stalowni produkuje się belki sta­ lowe o długości 12 m. Do ich wytworzenia potrzebne są wlewki staliwne o możliwie jednakowym ciężarze, które następnie są rozwalcowywane. Długości powsta­ jących w ten sposób belek rozkładają się w sposób normalny. Praktycznie oznacza to, że dokładnie orien­ tujem y się w długościach poszczególnych jednostek tej zbiorowości, jeżeli znamy średnią długość i odchylenia standardowe. W ystarczy to do optymalnego zaplano­ wania (zorganizowania) danego procesu i jego reali­ zacji. Z normalnymi lub logarytmiczno-normalnymi rozkła­ 58

d a m i3 mamy do czynienia wtedy, kiedy jakaś wielkość stale się zmienia i jest mierzalna (jak długość owych belek). Często spotykamy się jednak w przedsiębior­ stwie z procesami, przy których może być mowa tylko o liczeniu, a nie mierzeniu. Również w tej dziedzinie statystyka matematyczna dysponuje pożytecznymi „na­ rzędziami pracy”. Francuski m atem atyk Poisson opracował w 1837 r. wzór na rozkład częstości występowania rzadkich zja­ wisk: P (x — r) = —-— e~ \ x !

(2 )

gdzie: / = n •p x — liczba realizacji zdarzenia losowego o prawdopo­ dobieństwie p, r — liczba całkowita nie mniejsza od 0, p — prawdopodobieństwo jakiegoś zdarzenia, e — podstawa logarytmów naturalnych (e = 2,71828 ...), n — liczba doświadczeń. Wzór Poissona może być stosowany np. do określenia ilości (liczby sztuk) m ateriału (części) rzadko używane­ go przez brygadę remontową, jaką trzeba mieć stale w podręcznym magazynie, aby awaria mogła być na­ tychmiast zlikwidowana. Jednym z bardzo pożytecznych tego rodzaju uogólnień jest ujem ny rozkład dwum ianowy (binomialny) Pascala. O zmiennej losowej X , której funkcja rozkładu prawdo­ podobieństwa dana jest następującym wzorem: k v p q ’

(3)

s Bardzo często dla ułatwienia zamiast pierwotnych zmiennych rozpa­ truje się ich logarytmy.

gdzie: x k v p q

— — — — —

zmienna losowa, wartość przeciętna, w ariancja zaobserwowanego rozkładu, prawdopodobieństwo jakiegoś zdarzenia, prawdopodobieństwo, zdarzenia przeciwnego,

mówimy, że ma ujem ny rozkład dwumianowy. Rozkład ten jest stosowany m.in. do badania częstości wypad­ ków w przedsiębiorstwie. Wymienione rozkłady prawdopodobieństwa wystarczają w wielu przypadkach jako modele procesów przedsię­ biorstwa. Niekiedy jednak nie można za ich pomocą właściwie określić badanych procesów i przewidzieć w pływu określonych zjawisk. Trzeba w tedy posługiwać się innym i tego typu „narzędziami” matematycznymi. Na przykład w prognozowaniu stosuje się różnorodne funkcje matematyczne (rysunek 1), a mianowicie: — funkcja liniowa: y = a + bt, — funkcja paraboliczna: y = a + bt + ci2, — funkcje potęgowe: y — a + bta; y = a + bt + ct“, — funkcje wykładnicze: y = aeat; y = a + be(at_^ S), a — funkcje logistyczne: y = -------------- , 1 4- be~at — ln (* °) y ~ 1 + be-«‘ ’ gdzie: t — zmienna czasowa, e — podstawa logarytmów naturalnych (e = 2,71828 ...), a, b, c — pewne stałe param etry, a, /3 — wykładniki potęgi.

60

\

Rysunek 1 Przykłady różnych ty p ó w funkcji ekstrapołujących

y = a + bt

t

Ś

D rze w o decyzyjne W w yniku -badań nad procesami podejmowania decyzji (prowadzonych w latach pięćdziesiątych przez C. W. Churchmana, R. L. Ackoffa, E. D. Arnoffa i ich współ­ pracowników) powstała koncepcja drzewa powiazań. W zależności od funkcji, jaką spełnia, przyjm uje ono nazwę drzewa decyzji, drzewa celów itp. Na przykład w metodzie PATTERN prognozowania normatywnego istotnym elementem jest drzewo celów (zob. s. 66). Drzewo decyzyjne jako metoda prognozowania n o r - v matywnego im plikuje następujący model podstawo­ wy [5]: — osoba podejmująca decyzję w ybiera jeden kierunek działania spośród wielu możliwych, — działanie w obranym kierunku prowadzi do w ystą­ pienia jakiegoś zdarzenia, jednego spośród wielu możliwych, -— wystąpienie tego zdarzenia jest zmienną przypadko­ wą o określonym a priori prawdopodobieństwie, — zbiór takich możliwych zdarzeń losowych (zmien­ nych przypadkowych) i ich prawdopodobieństwa zależą od wybranego uprzednio kierunku dzia­ łania, — losowy skutek decyzji pociąga za sobą następną de­ cyzję itp., co prowadzi do wytworzenia się długiej serii; często więc sporządza się podobny do drzewa w ykres sieciowy, aby przedstawić ciąg decyzji, przy­ padków losowych i różnych ich kombinacji. K onstrukcję i interpretację drzewa decyzyjnego przed­ stawimy na przykładzie. Badane przedsiębiorstwo ma aktualnie sprzyjające warunki wejścia na nowy rynek. Kierownictwo musi więc najpierw zdecydować się na jedną spośród czterech następujących możliwości: 1) zaangażować się w produkcję na dużą skalę i po­ nieść koszty marketingu, 62

2) wejść na rynek z niewielką produkcją, 3) przeprowadzić badanie rynku i próbny m arketing, a następnie na podstawie uzyskanych wyników zde­ cydować, czy wejść na rynek i na jaką skalę, 4) zrezygnować z nadarzającej się okazji, nie wchodzić na rynek. Załóżmy, iż bieżąca wartość netto m ajątku przedsię­ biorstwa wynosi 10 min doi. Całkowita inwestycja związana z wejściem na rynek na małą skalę wymagać będzie 5 min doi., a na dużą skalę — 10 min doi. Wartość dochodów netto, które mogłyby być osiągnięte w związku z wejściem na nowy rynek, zależy od skali operacji przedsiębiorstwa i wielu innych okoliczności, na które przedsiębiorstwo nie ma wpływu. Załóżmy, że te okoliczności powodują poprawę lub pogorszenie wa­ runków rynkowych. W ynikające z tego przychody netto (według ich wartości w chwili obecnej) kształtują się jak w tablicy 2: Tablica 2 Wpływ okoliczności niezależnych od przedsiębiorstw a na jego dochody Warunki rynkowe

Skala operacji przedsiębiorstwa w min doi. mała

duża

Dobre

8

20

Złe

3

5

ŹFÓdło: 15].

Planiści obliczyli również, że badanie rynku, próbna działalność marketingowa itp., będą kosztować 250 tys. doi. Wynikiem tego będzie korzystna, obojętna lub nie­ korzystna prognoza rynkowa. Nie jest ona jednak cał­ kowicie dokładna. W zależności od wyników badania rynku i skali ope­ 63

racji prawdopodobieństwo, że w arunki rynkowe okażą się rzeczywiście dobre czy złe zostało ocenione tak, jak w tablicy 3: Tablica 3 Praw dopodobieństw o wystqpienia dobrych lub złych w arunków rynkowych Skala operacji

Wyniki badania rynku

korzystne obojętne niekorzystne korzystne obojętne niekorzystne

Duża Duża Duża Mała Mała Mała

Prawdopodob:ieństwo, że warunki rynli;owe będą: dobre

złe

0,8 0,6 0,3 0,7 0,5 0,2

0,2 0,4 0,7 0,3 0,5 0,8

Źródło: [5].

Oszacowano ponadto, że istnieje 30% szans na pomyślny wynik próbnego m arketingu, 40% na rezultat obojętny oraz 30% na niekorzystny. Zakładając, że przeprowa­ dzenie badania nie w płynie na finalne w arunki rynko­ we, można obliczyć prawdopodobieństwo dobrych i złych warunków rynkowych (nie znając rezultatu badania rynku) z powyższych danych. Wyniki przed­ stawiono w tablicy 4: Tablica 4 Praw dopodobieństw o wysłqpienia dobrych lub złych w arunków rynkowych Skala operacji

dobre

złe

Duża

0,57

0,43

Mała

0,47

0,53

Źródło: [5].

64

prawdopodobieństwo, że warunki rynkowe będą:

Celem przedsiębiorstwa jest maksymalizowanie długo^ terminowo zaplanowanego wzrostu na podstawie w ar­ tości netto m ajątku przedsiębiorstwa. Celowi temu (pod pew nym i w arunkami, które w rozpatrywanym przykładzie stanowią dopuszczalne założenia) odpowia­ da funkcja korzyści: U = lo g —£ 7 - , v1

(4)

gdzie: V ! — początkowa wartość m ajątku przedsiębiorstwa, V A — wartość ma jątku przedsiębiorstwa (netto) w chwi­ li obecnej, po podjęciu decyzji. Kierownictwo przedsiębiorstwa podejmuje decyzje, któ­ re maksymalizują spodziewaną wartość tej funkcji. Na rysunku 2 (na końcu książki) przedstawiamy drze­ wo decyzyjne dla podanego przykładu. Pokazujem y na aiim wszystkie kombinacje decyzji i zdarzeń losowych (wyników rynkowych); każdej kombinacji odpowiada jeden punkt końcowy z praw ej strony wykresu. De­ cyzje i zdarzenia losowe tworzące tę kombinację od­ zwierciedlone są przez różne połączenia i ścieżki wią­ żące punkty początkowe z odpowiednimi punktam i końcowymi. Wysokość położenia każdego punktu na wykresie wskazuje odpowiadającą mu korzystność. Osoba podejmująca decyzję postępuje następująco: w każdym pufikcie decyzyjnym w ybiera właściwą ścieżkę tak, aby „wspiąć się” jak najw yżej po osiąg­ nięciu punktu końcowego. Z rysunku 2 można odczytać optymalną strategię de­ cyzji: „przade wszystkim przeprowadź badania rynku i próbny marketing, a jeśli wyniki będą korzystne lub obojętne, wejdź na rynek na wielką skalę, jeśli nato­ miast okażą się niekorzystne — nie angażuj się abso­ lutnie w tę spraw ę”. Szczególnie godne uwagi jest to, że naw et jeśli wynik testowania jest tylko obojętny, 5 Matematyczne techniki zarządzania

65

przedsiębiorstwo już powinno wejść na rynek na dużą skalę, w^brew intuicyjnym odczuciom, naw et mimo ko­ nieczności podjęcia ryzyka i znacznych inwestycji. Realizacja celu omawianego przedsiębiorstwa, tj. dłu­ gofalowo zaplanowanego wzrostu, wymaga podjęcia ta­ kiego ryzyka.

M etod a PATTERW Metodę PATTERN (Planning Assistance Trough Technical Evaluation on Relevance Numbers — wspomaga­ nie planowania techniczną ewaluacją wskaźników względnej, ważności) przedstawimy w skrócie na pod­ stawie prac A. Chorobińskiego [2] i M. Trockiego [8], Do podstawowych elementów metody zalicza się: — scenariusz, — drzewo celów, — wskaźniki względnej ważności, — wskaźniki stanu i terminu, — wskaźniki wzajemnej użyteczności. Rysunek 3 PATTERN

66

P o d staw o w e elementy system u informacyjnego

Wraz z innym i elementami (np. komputerem) składają się one na system inform acyjny PATTERN przedsta­ wiony na rysunku 3. Omówimy obecnie każdy z wymienionych elementów. Scenariusz. W systemie PATTERN scenariusz stanowi podstawę prawidłowego określenia celów. Obejm uje on długoterminowe prognozy rozwoju społeczeństwa i go­ spodarki, zarówno typu m akro (ogólna sytuacja na świecie itp.), jak i mikro (np. wybrane problemy tech­ niczne). Drzewo celów. Wskazuje ono zależności logiczne i stru k­ turę celów. Drzewo celów „buduje się” od góry do dołu, tzn. od finalnego celu strategicznego do celów podporządkowanych. Natomiast w praktyce system realizuje się z dołu do góry: problem wyższego pozio­ mu może zostać rozwiązany dopiero po rozwiązaniu problemów niższego poziomu (zob. rysunek 4). Wskaźniki względnej ważności elementów drzewa ce­ lów. Wszystkie elementy drzewa celów ocenia się ilo­ ściowo przez ustalenie wskaźników ich względnej waż­ ności rih gdzie: i — num er poziomu drzewa celów (na rysunku 4 i = A, B, . . . , G), j — num er elementu drzewa celów, na poziomie ż-tym (na rysunku 4 wska­ zujemy, że na każdym z poziomów drzewa celów jest różna liczba elementów; np. przy i = D mam y j = 1, 2, . .., p). Na wartość wskaźników rló nakłada się pewne ograni­ czenia, a mianowicie 0 ^ ^ 1 oraz 2 r tj = 1. Wartość nadaje się wskaźnikom rtj w kilku fazach me­ todą delficką. Do oceny ważności elementów poszcze­ gólnych poziomów drzewa celów stosuje się różne kry ­ teria. Załóżmy, że dla elementów poziomu 1 istnieje x = a, . . . , v kryteriów, których wagę (znaczenie) określa się jako qx = qa , q fi, ..., qv . Budujemy nastę­ pującą macierz wskaźników S jx udziału elementu j-tego 67

w spełnieniu warunków wynikających z kryterium x (tablica 5): Tablica 5 Kryte­ rium . X

Elementy poziomu t

Waga kryte­ rium

1

Qx

a

1. Pozostała ilość y — n — x ton pszenicy jest sprzedawana za h(y) = h(n — y) złotych, gdzie funkcja My) jest monotonicznie rosnąca (im więcej się sprze­ daje, tym większy uzyskuje się dochód). Jeżeli rolnik chce wyprzedać wszystką pszenicę po N kolejnych zbio­ rach, to jaką politykę sprzedaży i zasiewu powinien za­ stosować, aby zmaksymalizować swój całkowity dochód w rozważanym okresie. Rozwiązanie tego problemu mo­ żna znaleźć w pracy [1]. Jak łatwo zauważyć, podobny problem powstaje przy określaniu, jaka część dochodu narodowego powinna być przeznaczona na inwestycje. 2. Przyjm ijm y, że maksymalna pojemność statku wy­ nosi n ton, a jego ładunek ma się składać z pewnych ilości N różnych towarów. Wprowadźmy następujące oznaczenia: Ki — wartość sztuki i-tego towaru, w t — ciężar sztuki i-tego towaru, Xi — liczba sztuk i-tego towaru, który się ładuje. / Wyznaczenie ładunku o największej wartości polega na zmaksymalizowaniu funkcji liniowej: *

N

L n(t ) = ^ x,K, 1=1

(1)

przy następujących ograniczeniach: N

(Xi

= 0, 1, 2, ...).

(2)

1=1 Równanie rekurencyjne przyjm uje postać: f N(n) = max { x NK N + f N- i (n — nNW N)}, gdzie f N(ri) = max {L N(x)}. 72

(3)

Rozwiązanie problemu polega na wyznaczeniu wartości Kt, w u x t [2]. 3. Rozważmy jedną maszynę, która daje określony przychód co rok, wymaga pewnego nakładu na kon­ serwację i może być zastąpiona przez nowoczesną m a­ szynę w każdej chwili. Załóżmy, że przychód, koszt konserwacji i dopłata przy wymianie zależą od wieku maszyny w znany sposób. Przyjm ijm y dalej, że decy­ zje podejmowane są tylko w momentach t — 0, 1, 2, . . . i w każdej takiej chwili możemy bądź zachować starą maszynę (decyzja K), bądź nabyć nową (decyzja P). Niech teraz funkcja f(t) stanowi całkowity przychód w ciągu pewnego czasu, gdy na początku mamy ma­ szynę w wieku t i stosujem y politykę optymalną. Wprowadzamy czynnik dyskontujący a (jednostka przychodu o jeden okres później jest w arta a jednostek w chwili obecnej). Równanie funkcyjne będzie mieć w tym przypadku postać [2]: fm =

f(t)

„ „ \P ■ m o(0) - c(t) + a/(l)] m ax . r({) _ a(f) af( nł+1 = a(xt) + b(2/.)

(dla i = 1, 2, . . N ~ 1) (10)

oraz 0 < Xi < n,

(dla i = 1, 2, . . N).

(11)

Ostatni w arunek oznacza, że liczba maszyn przezna­ czonych do wykonywania pierwszej czynności nie może być ujem na i przekraczać liczby wszystkich maszyn będących w dyspozycji na początku każdego etapu pro­ cesu. Oznaczmy przez fn(ri) maksym alny całkowity dochód otrzym any po N etapach opisanego wyżej procesu, przy założeniu, że liczba maszyn będących w dyspozycji na początku tego procesu wynosiła n. Jeżeli proces jest złożony z jednego tylko etapu, to wyrażenie fi{n), okre­ ślające maksym alny dochód, można zapisać: fi(n) = max [g(x) + h(n — a:)]. 0 0

am nx n ^ ( j - 1, 2....... n)

(3.1)

— zad anie dualne programowania liniowego:

f(y) " yfii +

+ —+ ym&m min

y tau + y tatt + ... + y mami > ct ................................................................................

(4.i) (5.1)

yi°in + y*0*n + ••• y-mO-mn^ Cn y i> 0

(ł - 1, 2 , .. ., m )

(6.1)

143

(5)

y' > o.

(6)

Przez rozwiązanie dopuszczalne zadania wyjściowego programowania liniowego będziemy określać wektor x spełniający w arunki (2) i (3), natomiast przez rozwią­ zanie optymalne zadania wyjściowego (prymalnego) programowania liniowego — wektor x°, będący takim rozwiązaniem dopuszczalnym, dla którego funkcja (1) osiąga wartość maksimum. Analogicznie, przez rozwiązanie dopuszczalne zadania dualnego programowania liniowego oznaczać będziemy w ektor y' spełniający w arunki (5) i (6), natom iast przez rozwiązanie optymalne zadania dualnego — wektor y°, będący takim rozwiązaniem dopuszczalnym tego zada­ nia, dla którego funkcja (4) osiąga wartość minimum. W ektory b oraz y' są wektorami m-wymiarowymi (b 6 Rm, y' € Rm), natom iast wektory x i c są wekto­ ram i n-wymiarowymi (x e R n, c e Rn). Każda para dualnych zadań programowania liniowego i rozwiązania optym alne tych zadań m ają konkretną interpretację prakseologiczną. O. Lange [2] potraktow ał teorię programowania m ate­ matycznego jako część prakseologii, czyli nauki o ra ­ cjonalnym działaniu. Zajm ując się jedną z podstawo­ wych zasad prakseologii, a mianowicie zasadą racjonal­ nego gospodarowania, O. Lange rozpatryw ał jej dwa ekw iw alentne w arianty: zasadę maksymalnego efektu (zwaną również zasadą maksymalnej wydajności) i za­ sadę minimalnego nakładu środków (zwaną także za­ sadą oszczędności środków). W konsekwencji O. Lange mówił o dwóch ekwiwalentnych zadaniach optymaliza­ cyjnych: 1) o zadaniu wyjściowym (prymalnym), w któ­ rym chodzi o wyznaczenie maksimum funkcji wyników przy danym nakładzie środków oraz 2) o zadaniu dual­ 144

nym, w którym chodzi o wyznaczenie minimum funkcji nakładów przy danym wyniku. Podstawowe znaczenie w teorii programowania linioL.wego ma twierdzenie o dualności: a) jeżeli zadania {Ax b |x ^ 0} i {y'A ^ c '|y ' ^ 0} m ają rozwiązania dopuszczalne, to istnieją również rozwiązania optymalne x° i y° oraz spełnione jest rów nanie c'x° = y°b,

(7)

b) jeżeli zadanie (A x ^ b | x ^ 0} ma rozwiązanie do­ puszczalne, to max c'x = + oo

(8)

osiągane jest wtedy i tylko wtedy, gdy zadanie {y'A ^ c' | y ^ 0} nie ma rozwiązań dopuszczalnych, c) jeżeli zadanie {y'A ^ c | y ^ 0), ma rozwiązanie dopuszczalne, to min y'b = — co

(9)

osiągane jest wtedy i tylko wtedy, gdy zad&nia {A x b I x ^ 0} nie ma rozwiązań dopuszczalnych. Dotychczas opracowano kilkadziesiąt efektywnych algo­ rytmów* m etody programowania liniowego, ale najczę­ ściej opisywany jest algorytm simpleksów Dantzinga 2 jako najbardziej poglądowy i „dydaktyczny”. E fe k ty w n o ś ć i koszty m eto d y

Podstawowe algorytm y metody programowania linio­ wego są od dawna realizowane komputerowo, co po­ zwala wyznaczać optymalne rozwiązania zadań (1)—(3) oraz (4)—(6) stosunkowo m ałym nakładem czasu i kosz­ tów. Dużym ograniczeniem efektywności tej metody jest podstawowe założenie o liniowej postaci wszyst­ * Zob. W. Sadowski [6], rozdział HI. 10 Matematyczne techniki zarządzania

145

kich funkcji nakładów i wyników, mało przystające do rzeczywistości gospodarczej. Metoda wymaga korzysta­ nia z dużych zbiorów danych liczbowych. Sposób nauczania lub p o słu giw an ia się m etodą

Do opisu i badania problemów zarządzania metodą pro­ gramowania liniowego nie jest konieczna znajomość licznych algorytmów tej metody. Podstaw y teoretyczne programowania liniowego wykładane są na studiach uniwersyteckich, technicznych i ekonomicznych. Ob­ szerne i bardziej kompleksowe modele programowania liniowego konstruowane są z reguły przez zespoły spe­ cjalistów.

LITERATURA

£1] Czerwiński Z., Matematyka na usługach ekonomii, wyd. 4, PWN, Warszawa 1977, rozdział 2.1. [2] Lange O., Optymalne decyzje. Zasady programowania, PWN, Warszawa 1964. [3] Metody matematyczne w organizacji i ekonomice przedsię­ biorstwa, praca zbiorowa, PWG, Warszawa 1960. [4] Optymalizacja planów, praca zbiorowa pod red. M. Lesza, PWE, Warszawa 1968. [5] Radzikowski W., Programowanie liniowe i nieliniowe 'dla ekonomistów, PWE, Warszawa 1971. [6] Sadowski W., Teoria podejmowania decyzji. Wstęp do badań operacyjnych, wyd. 6, PWE, Warszawa 1076.

Przykład zasto so w an ia m etody

1. Planowanie asortymentu produkcji („Ile i czego”) Problem. Przedsiębiorstwo dysponuje czynnikami pro­ dukcji (surowce, roboczogodziny, maszynogodziny itp.) w ograniczonych ilościach s1} s2, . . . , sm. W tych w arun­ 146

kach może ono produkować n wyrobów (produktów I końcowych) x lf x 2, . . x n. Jednostka wyprodukowanego 1 wyrobu Xj może przynieść zysk P). Powstaje pytanie, ' ile i jakich wyrobów wyprodukować przy danych ogra­ niczeniach czynników produkcji, aby osiągnąć maksy­ malny zysk? Opis formalny. Znaleźć takie wielkości x u x 2, . .. , x ny dla których: m m Z = £ XjPj -> max

(10)

•

i=l

przy następujących ograniczeniach: n

V x jaij < st i x, > 0 i

(i = 1, 2, . . m), (j = 1, 2, . .

n),

(11) (12)

gdzie: aa — wielkość zużycia czynników produkcji i na jed­ nostkę wyrobu j, st — dysponowana wielkość czynników produkcji i. 2. W ybór wariantu technologicznego („Ile i jaką m e­ todą”) Problem. Wyrób A można produkować na podstawie n rodzajów technologii (metod produkcji). Poszczególne w arianty technologiczne w lt w 2, . .. , w n w różnym stopniu zużywają czynniki produkcji slf s2, . . sm (su­ rowce, roboczogodziny, maszynogodziny itp.). Koszt jednostkowy wykonania wyrobu A jest różny dla każdego w ariantu technologicznego i wynosi k l t k 2 i___ _ kn. Należy w ybrać taki w ariant (lub kombinację w arian­ tów), aby zminimalizować koszty wykonania w yrobu A. 147

^

Opis formalny. Znaleźć takie wielkości w ly w 2, . .. . wn, dla których: n Q = ^ Wjkj -> min (13) i“ i

przy następujących ograniczeniach: n x jaij > st 2=1 > o

(i = 1, 2, . . ., m),

(14)

(j = 1, 2, . .

(15)

n),

gdzie aij i st jak w zadaniu 1. 3. Dobór mieszanki („Ile i z czego”) Problem. Plan produkcyjny na okres N przewiduje wytw arzanie pewnego stopu 0. Stop ten możemy pro­ dukować z posiadanych surowców elf e2, . . eky z któ­ rych każdy jest w różny sposób zanieczyszczony pier­ wiastkami ru r2, . . rw. Maksymalny stopień zanieczy­ szczenia stopu 0 pierwiastkiem r t wynosi Ri (i = 1, 2, .. w). Zastosowanie każdego z surowców ej daje pe­ wien efekt ekonomiczny Zj (j — 1, 2, . . k) na poziomie jednostkowym. Chodzi o taki dobór mieszanki (surow­ ców e^, aby zapewnić maksymalny efekt globalny przy nieprzekroczeniu dopuszczalnego stopnia zanieczyszcze­ nia stopniu 0 pierwiastkam i r t. Opis formalny. Znaleźć takie wielkości elf e2, . . ek, dla których: k

E = ^

ejZj —>■ max

(16)

j»i

przy następujących ograniczeniach: k

^ j=i

148

Cij6j < Rł

(i = 1, 2, ..

w),

(17)

e,

> o

(j = 1, 2........ Tc),

(18)

gdzie ctj oznacza współczynnik zanieczyszczenia surow ­ ca ej pierwiastkiem r t. * 4. Terminowanie produkcji („Ile i kiedy”) Problem. Założone w planie rocznym n wyrobów z u z2t . . zn możemy produkować w każdym z 4 kwartałów. Ze względów technicznych i organizacyjnych zużycie czasu pracy na jednostkę wyrobu Zj w każdym z 4 kw artałów jest różne i wynosi (i = 1, 2, 3, 4). Ograniczenie zdolności produkcyjnej posiadanych m a­ szyn i urządzeń powoduje, iż w każdym kw artale urzą­ dzenia te (jednorodne i nawzajem zamienne) mogą przepracować co najwyżej Ui godzin. Różne koszty pro­ dukcji i koszty magazynowania wyrobu r,- w poszcze­ gólnych kw artałach powodują, że jednostkowy zysk Ci, jest również różny dla każdego kw artału. Należy tak podzielić produkcję n wyrobów między poszczególne kw artały, aby ogólny w ynik był maksymalny. Opis form alny. Znaleźć takie wielkości Z i}, dla których: n

E =

4

^ j“ l

z ^ j -> max

(19)

i=l

przy następujących ograniczeniach: ^ z .jU .^ U ,

(i = 1,2, 3, 4),

(20)

j=l

>0

1, 2, . . to; t = 1, 2, 3, 4).

(21)

Kombinacje tych czterech przykładowo wymienionych, prostych zadań prowadzą do zadań bardziej skompliko­ wanych, które praktycznie obejm ują wszystkie prawie zagadnienia techniczno-ekonomiczne i organizacyjne w ystępujące w przedsiębiorstwie przemysłowym. 149

M etod a dupleks program ow ania liniow ego Spośród wielu nowych algorytmów programowania li­ niowego na specjalną uwagę zasługuje metoda dupleks, opracowana przez szwajcarskiego m atem atyka H. P. Kunzi. Metoda ta jest szczególnie efektywna przy roz­ wiązaniu dużych zadań optymalizacyjnych programo­ wania liniowego, w których w ystępuje wielka liczba w arunków ubocznych. Metoda dupleks obejm uje dwa etapy postępowania. W etapie pierwszym wyznacza się ten w arunek ubocz­ ny: (L\X\ “f" a 2x 2 • • . "ł” b, (22) którem u odpowiada hiperpłaszczyzna zawierająca na pewno wierzchołek optym alny x° (rozwiązanie). W eta­ pie drugim bada się poszczególne wierzchołki hiperpłaszczyzny i znajduje wierzchołek optym alny x°, w y­ korzystując w tym celu np. metodę simpleks. Takie podejście radykalnie zmniejsza liczbę operacji oblicze­ niowych koniecznych do znalezienia rozwiązania (wierz­ chołka) optymalnego x°. Metodę tę w arto przedstawić nieco szczegółowiej ze względu na jej dużą praktyczną użyteczność. Etap I Załóżmy, że chcemy wyznaczyć maksimum funkcji wy­ ników: /(x) = 20 +

z j { - Xj)

(23)

poddanej ograniczeniom: n Xn+j = bt +

x i) > 0 i“ i

150

(i = !>2> • • •> n)>

(24)

oraz > 0

(j = 1, 2, . . n)

(25)

gdzie: m ij Z0 = V JCiXi, i=l

x t — zmienne rozwiązania bazowego, xj — pozostałe zmienne, ct — współczynniki w funkcji wyników, odpowiada­ jące zmiennym rozwiązania bazowego, Cj — pozostałe współczynniki w funkcji wyników, ci{j — współczynniki techniczne (np. zużycia dobra i-tego na jednostkę produktu j-tego), bt — dysponowana wielkość czynnika i-tego (ograni­ czenie). Szukając pierwszego rozwiązania zadania (23)—(25), należy przyjąć Xj = 0 (j = 1, 2, . .. , n), naw et jeżeli byłoby to ze względu na w arunek (24) niedopuszczalne. Szukaną hiperpłaszczyznę zawierającą na pewno punkt optym alny x° wyznacza się za pomocą wzoru: n

mm l< 0; a (s) ile i

b(s) a{f> < 0; — < /

1

ih

•

(29)

a (s)

ifc

Możliwe są przy tym następujące cztery przypadki: 1. Jeżeli o istnieje i zostaje osiągnięte dla i = p, to zmienną x zamieniamy na zmienną x w i kontynu­ ujem y proces obliczeniowy, powracając do kroku 1. W tym kroku ^ostaje spełniony co najm niej jeden na­ ruszony w arunek uboczny (na ogół więcej). Wartość funkcji (23) ulega jednak odpowiedniemu zmniejszeniu. 2. Jeżeli wszystkie 0 dla b(r) < 0 i 1 nie istnieje, to przy { — zj?)} > 0 nie istnieje skończone rozwiązanie zadania (23)—(25). 3. Jeżeli o nie istnieje, natomiast istnieje X oraz za­ chodzi przynajm niej jedna relacja: a(J> < 0),

(30)

to zmienną zastępujem y zmienną x g( >i kontynu­ ujemy proces przechodząc ponownie do kroku 1. 4. Jeżeli w poprzednim przypadku nie można spełnić w arunku (30) dla co najm niej jednego i, to wracamy do kroku 1, wyłączając jednak teraz j = k. Jeżeli nie istnieje żadne j, takie że { — z ^ } > 0 i istnieje X, ani takie, że przynajm niej dla jednego i zachodzi: b(s) < 0

oraz

a[JJ < 0,

(31)

to ograniczenia (24) są wzajemnie sprzeczne. W tablicy simpleks znajduje się w tedy co najm niej jeden wiersz, w którym b(s) < 0 oraz a (|} ^ 0 (j = 1, 2, .. ., ri). 153

Zbieżność metody dupleks wynika bezpośrednio ze zbieżności metody simpleks. Poniższy przykład liczbo­ wy jest dobrą ilustracją procesu obliczeniowego w me­ todzie dupleks. Przykład liczbowy Niech będzie dane następujące zadanie, które należy rozwiązać za pomocą metody dupleks: /(x) = l l x i + 10x2 -> max, x3 = 0,8 + 0,5Xi x 4 = 10,7 —4xt x 5 — 15,4 —6Xi x 6 = 13,4 — 6xi x 7 = 8,7 — 4xt x 8 = 10,0-— 5^! Xi > 0 ,

— l,3x2^ 0, — x 2 ^ 0, — x 2 ^ 0, + x2 > 0 , + x2 > 0 , + 3 x 2 ^ 0,

x 2 ^ 0.

(32)

(33)

(34)

W etapie pierwszym określamy — korzystając z wzo­ rów (26) i (27) — że r = 4 i fc = 1. Zmienne bazowe m ają obecnie następujące wartości: x3 = 2,14 — 0,13x4 — Xj = 2,67 — 0,25x4 — x s = — 0,65 + 1,50x4 + 0,50x2, x6 = 2,65 + 1,50^4 + x 7 =

-

x8 = —

l,43x2, 0,25x2, 2,50x2,1’'

2,00

+ l,0 0 x 4 +

2 , 0 0 x 2,

3,37

+ 0,13x 4 +

4,25x2.

Zmienne niebazowe x4, x 2 = 0, natom iast wartość funk­ cji wyników wynosi: /(x) = 29,4 - 2,75x4 - 7,25x2 = 29,4.

(32.1)

Okazuje się, że naruszone są cztery w arunki uboczne z (33), a mianowicie w arunki odpowiadające wierszom, w których zmienne swobodne m ają indeksy i = 5, i = = 6, i = 7 oraz i = 8. 154

Przechodzimy teraz do etapu drugiego. W kroku 1 w y­ znaczamy maksymalną wartość wyrażenia (27.1); otrzy­ mujemy k = 2. W kroku 2 stwierdzamy, że r = 3. Na­ stępnie określam y wartości zmiennych bazowych: x 2 = 1,5 —0,09x4 —0,70x3, x t = 2,3 —0,23x4 + l,75x3, x 5 = 0,1 + l,46x4 - 0,35x3, Xq = 1,1 + l,28x4 - l,75x3, x7 = 1,0 + 0,82x4 — l,40x3, x 8 = 3,0 + 0,88x4 — 2,98x3.

1

'

%

Zmienne niebazowe x4, x 3 = 0, a wszystkie warunki (33) i (34) są spełnione, czyli otrzymaliśmy rozwiązanie optymalne, w którym zmienne decyzyjne przybierają wartości Xj = 2,3 oraz x 2 = 1,5. Funkcja (32) ma w ar­ tość maksymalną: 11 • 2,3 + 10 • 1,5 = 40,3. 1. Układ w arunków ubocznych (33) można sformułować w sposób następujący: (1) (2) (3) (4) (5 ) (6)

— 0 ,5 x j + 1,3x 2 < 0,8, 4 ,0 X i + l,0x2 < 10,7, 6 , 0 x i + l,0x2 < 1 5 ,4 , 6,0x! — l,0x2 < 13,4, 4,0xj — l,0x2 < 8,7, 5,0x! — 3,0x2 < 10,0

przez wyeliminowanie zm iennych swobodnych x3—x 8 oraz przeniesienie wyrażeń bt (i = 1, 2, . . . , 6) na p ra­ wą stronę każdej nierówności. 2. Ilustrację geometryczną zadania (32), przedstawia rysunek 1. W arunki uboczne gowe (34) wyznaczają pewien wielokąt K nych rozwiązań dla x t i x 2. Na wielokącie zmaksymalizować wartość funkcji (32).

(34) i (35) (35) i brze­ dopuszczal­ tym trzeba

3. W ektor c = [ci c2] = [11 10] wskazuje zwiększania wartości funkcji (32).

kierunek

155

Rysunek 1 Interpretacja geom etryczna zada­ nia (32), (34) i (35)

156

4. W etapie pierwszym procesu obliczeniowego metody dupleks określiliśmy w arunek (2), wyznaczając pro­ stą © na rysunku 1, na której na pewno leży wierz­ chołek optymalny x°. Z w arunkiem tym związana jest zmienna swobodna x 4. W etapie drugim procesu obli­ czeniowego badaliśmy wartości funkcji (32) dlą dwóch wierzchołków leżących na prostej © : a. Pierwszy wierzchołek (rozwiązanie) otrzymaliśmy dla x t — 2,67 oraz x 2 = 0, co widać w układzie (33.1). Wierzchołek ten oznaczono na rysunku 1 jako punkt Pi (2,67; 0). Dla wierzchołka Pt funkcja (32) miała w ar­ tość 29,4 (2,67 • 11 + 0 • 10 = 29,4). Jednak punkt Pt leży poza wielokątem K dopuszczalnych rozwiązań dla x x i x 2. Widać to na rysunku 1, a potwierdzeniem tego są wartości ujemne zmiennych swobodnych x s—x 8 w układzie (33.1). b. Drugi wierzchołek (rozwiązanie) otrzymaliśmy dla Xi = 2,3 oraz x 2 = 1,5, co uwidoczniono w układzie (33.2). Wierzchołek tesn, oznaczony na rysunku 1 jako P2, daje wartość funkcji (32) równą 40,3 (2,3 • 11 + 1,5 • • 10 = 40,3). Wierzchołek P 2 (2,3; 1,5) należy do wielo­ kąta K dopuszczalnych rozwiązań dla x± i x 2, stanowi więc rozwiązanie dopuszczalne. Równocześnie jest on rozwiązaniem optymalnm zadania (34), gdyż wyznacza maksymalną wartość funkcji (32).

*

Program ow anie liniow e binarne Symbol: 12-BC Klasa trudności: li Klasa zastosowań: pr, pl, op

Z asto so w an ie m eto dy (ro zw ią zy w a n e p roblem y)

Programowanie liniowe binarne stosowane jest do roz­ wiązywania problemów zarządzania, których opis i ba­ danie w liczbach niecałkowitych jest w ogóle pozbawio­ ne sensu. W programowaniu liniowym binarnym przyj­ mujemy, że wartość zmiennej decyzyjnej x } — 1 za­ chodzi w przypadku np. realizacji j-tego przedsięwzię­ cia, natomiast x t = 0 w przypadku np. rezygnacji z re­ alizacji j-tego przedsięwzięcia. Pozwala to łatwo za­ pisać zbiór odpowiednich warunków ubocznych i funk­ cję wyników. es:

O pis, schem at m eto dy

Programowanie liniowe binarne, zwane także progra­ mowaniem liniowym zerojedynkow ym , jest szczegól­ nym przypadkiem programowania liniowego w liczbach całkowitych (zob. s. 181). Model zadania optymaliza­ cyjnego ma następującą postać: — wyznaczyć ekstrem um funkcji wyników: /(X ) = c 'x

158

(1)

— poddanej ograniczeniom: Ax R B,

(2 ) (3)

x e D c,

(4)

gdzie: R — oznacza relacje „ = Dc — zbiór liczb całkowitych.

lub

W arunki (3) i (4) orzekają, że poszczególne zmienne de­ cyzyjne (j = 1, 2, . . n) mogą przyjmować wartości tylko 0 lub 1. Efektywną metodą wyznaczania rozwiązań w zadaniach typu (1)—(4) jest m.in. metoda Landa-Doiga i jej od­ miana, tzw. metoda enum eracyjna, opisana przez J. K u­ charczyka [1]. W metodzie enumeracyjnej zakładamy, że rozwiązuje­ my zadanie optym alizacyjne aproksymowane (przybli­ żone) następującym modelem: Z =

c ix i

n ń 11’

(5 )

1 n

(6) = 0 lub 1 gdzie C] > 0

(j = 1, 2, . . . , n),

(7)

(j = 1, 2, .. ., n).

Do modelu (5)—(6) można sprowadzić — przez odpo­ wiednie przekształcenia form alne — każde zadanie pro­ gramowania liniowego binarnego, a także każde zadanie programowania liniowego w liczbach całkow itych1. 1 W przypadku sprawdzania zadań programowania liniowego w licz­ bach całkowitych do postaci (5)—(7) trzeba jeszcze podać górne granice wartości dla Xj.

159

Metoda enumeracyjna polega na [1]: — systematycznym badaniu wartości funkcji wyników (5) we wszystkich punktach binarnego obszaru roz­ wiązań dopuszczalnych, określonego przez warunki ‘(6) i (7), — stosowanie grupy testów pozwalających na skutecz­ ne „odcinanie” nieodpowiednich części binarnego obszaru rozwiązań dopuszczalnych. i

E fe k ty w n o ś ć i ko szty m etody

Stosowanie programowania liniowego binarnego wyma­ ga opracowania wielu w ariantów przedsięwzięć produk­ cyjnych, organizacyjnych, badawczych itp., spośród których jedne wybiera się do rozwiązania optymalnego (Xj = 1), inne zaś odrzuca (xf = 0). Na przykład spo­ rządzenie wariantów w ytwarzania produkcji (konieczne do zdefiniowania zmiennych decyzyjnych Xj zadania optymalizacyjnego) wymaga ustalenia obiektu planowa­ nia, którym może być grupa przedsiębiorstw rozpatry­ wana jako całość, poszczególne przedsiębiorstwa lub wydziały, odcinki czy agregaty w przedsiębiorstwach. Po określeniu obiektów planowania opracowuje się wa­ rianty kierunków rozwoju, a więc zmianę łącznej mocy przedsiębiorstwa, specjalizacji, technologii lub organi­ zacji pracy i produkcji, kombinowanie, różne sposoby przydzielenia do bazy surowcowej oraz wykorzystania zasobów (surowców, materiałów, pracy, sprzętu, energii itp.), różne term iny przeprowadzenia rekonstrukcji przedsiębiorstw itp. Możliwe są także połączenia tych kierunków rozwoju. Każdy z takich w ariantów przed­ siębiorstwa charakteryzują określone wskaźniki ekono­ miczne (wysokość nakładów bieżących i inw estycyj­ nych, pracochłonność itp.). Jak widać, przygotowanie niezbędnych wariantów roz­ wiązań techniczno-produkcyjnych i organizacyjnych 160

może być kosztowne i długotrwałe. Natomiast niezbęd­ ne obliczenia można przeprowadzić niewielkim kosztem, dzięki temu, że algorytm y programowania liniowego binarnego realizuje się za pomocą komputerów, korzy­ stając z tzw. bibliotecznych programów obliczeń num e­ rycznych. Efektywność liniowego programowania binar­ nego bywa znaczna; zob. m ’in. pracę M. Lesza [2]. Sposób nauczania fozh p osłu giw ania się m eto d ą

Wyodrębnienie sensownych, merytorycznie uzasadnio­ nych w ariantów rozwiązań wymaga bardzo dużej wie­ dzy fachowej i z reguły jest dziełem nie jednej osoby, ale grupy odpowiednich specjalistów. Konieczny zasób wiedzy form alnej (matematycznej) nie wykracza poza program wykładów z programowania liniowego. Zbęd­ ne jest studiowanie możliwych algorytmów liniowego programowania binarnego, które i tak realizowane są komputerowo.

LITERATURA

[1] Kucharczyk J., Implicit Enumeration Algorithm for Solving Zero-One Integer Linear Programs, „Zastosowanie Ma­ tematyki” 1972. [2] Lesz M., Matematyczne podstawy rekonstrukcji przemysłu, PWE, Warszawa 1967. [3] Problemy rozwoju i rekonstrukcji branży, KNiT, Warszawa 1966. [4] Radzikowski W., Zastosowanie simpleksowej metody pro­ gramowania liniowego, „Organizacja, Samorząd, Zarządza­ nie” 1961, nr 7.

11 Matematyczne techniki zarządzania

161

Przykład zastoso w an ia m etody

1. Problem lokalizacji Problem. Dany jest planowany „obrót” bjt z wydziału j do wydziału i oraz odległości cj{ między pomieszcze­ niem fabrycznym j a pomieszczeniem i. Należy tak roz­ lokować w budynkach fabrycznych n wydziałów (od­ działów) produkcyjnych przedsiębiorstwa, aby niezbęd­ ne przewozy surowców, półfabrykatów i wyrobów go­ towych między poszczególnymi wydziałami (oddziała­ mi) były jak najmniejsze. Opis formalny. Znaleźć takie [cJt] i [b^], dla których: sp CA' BA = min

(8)

przy ograniczeniach: J o )t = l

0 = 1 .2 ........n),

(9)

i=l

] h 0jl = l

( t = 1, 2,

n)

(10)

(przyporządkowanie jednego wydziału tylko do jednego pomieszczenia), = (j (ii) (zapewnienie rozwiązania w liczbach całkowitych), gdzie: sp C — suma elementów na głównej przekątnej ma­ cierzy [cjt], B — macierz [bJt], A — macierz [o#], z założeniem, że: 1, jeżeli wydział j znajduje się w pomieszczeniu i,

(

0 w pozostałych przypadkach.

162

2. Transport wewnątrzzakładowy (obwodowy) problem. Opracowując wzorcowy harmonogram tran s­ portu wewnątrzzakładowego (obwodowego), ustalono, że środek transportu (wózek elektryczny itp.) powinien „odwiedzić” n stanowisk pracy i w końcu wrócić do punktu wyjściowego. Koszt transportu z miejsca (sta­ nowiska) i do miejsca (stanowiska) j wynosi c^ (i, j = = 1 , 2 n; i ¥= j). Chodzi o ustalenie trasy najm niej kosztownej. Opis formalny. Znaleźć takie wielkości cy, dla których: n

n

i= l

j= l

= min

(dla i # j),

(12)

przy ograniczeniach: n (j = 1, 2........n), (13)

71

(i =' 1, 2........n) (każde stanowisko należy odwiedzić tylko raz), A*'AA* = W, 71 (? = 1, 2........n), t=i

(14)

71

(i = 1 , 2 , . . . , n) j= i

(nie mogą wystąpić cykle krótsze; środek transportu musi wrócić do punktu wyjściowego), (15) (zapewnienie rozwiązania w liczbach całkowitych), 163

gdzie: A — macierz niewiadomych oih A* — „przeszeregowana” (zmiana kolejności wyrazów) macierz niewiadomych oijt W — macierz „właściwego uszeregowania”. 3. Planowanie obciotżenia maszyn („ile, gdzie i kiedy”) Problem. Przedsiębiorstwo posiada m różnorodnych maszyn, na których w tym samym czasie m usi zostać podjęta produkcja n wyrobów i to w taki sposób, aby zapewnić możliwie ciągłe wykorzystanie maszyn oraz wykonać program produkcji możliwie jak najszybciej. Dane są czasy t jt, potrzebne do wykonania wyrobu i na maszynie j, a następnie (jeżeli to jest konieczne) kolejność obróbki wyrobu na poszczególnych maszy­ nach. Opis formalny. Przede wszystkim dzielimy czas na wy­ godne „okresy obliczeniowe” (1/4 godziny, 1/2 godziny, 1 godzina itp.) i wszystkie czasy tjt wyrażamy jako wielokrotność tych „okresów”. W ogóle rozpatrujem y T takich okresów. Dlatego definiujemy m • n • T zmiennych: 1, jeżeli maszyna j używana jest do om = produkcji wyrobu i w okresie t, 0 w pozostałych przypadkach. Następnie w ybieram y znaczenia (wagi) cjit > 0, gdzie: c ^ + i > cjit tego rodzaju, żeby różnice (ciM+1 — cjit) wy­ kazywały straty dla zakładu wynikające z „uwolnienia” (odciążenia) maszyny o jeden okres później. Zadanie brzm i wtedy: znaleźć takie wielkości ojit, dla których: m

n

T

j=l

i=l

t=l

(16)

164

. przy ograniczeniach: m (i = l, 2,

t = 1,2,

T)

(17)

j=1

(wyrób i może być w tym samym czasie jednocześnie obrabiany tylko na jednej maszynie), n

Y, °i“
t

min,

(i = 1 , 2 ,. . ., n), x > 0,

(1)

(2) (3)

1 Parametrami modelu są zawsze te jego elementy, które przyjmują taką samą wartość dla szeregu kolejnych operacji obliczeniowych (w modelach statystycznych) lub punktów czasowych (w modelach dynamicznych).

167

gdzie: Cj = dj + X d , X — badany param etr; l e < q , v > , djt d'. , atj, bt — stałe param etry (i = 1, 2, m; j — = 1,2, n). Zakładamy, że zadanie jest niezdegenerowane i ma pierwsze rozwiązanie bazowe. Stosując metodę simpleks rozwiązujem y zadanie dla X = q i albo istnieje rozwią­ zanie (przypadek A), albo go nie ma (przypadek B). Dla A Abv istniało rozwiązanie, musi być spełniony w arunek Zj ~ ^ < 0. Ponieważ ct jest liniową funkcją X, to można założyć, że Zj — Cj tworzy też liniową zależność od X. Niech Zj — Cj = a} + Xp5 ^ 0. Zachodzi to, gdy dla

P;o,

(4)

ai -

(5)

A Określamy, w jakich granicach musi zawierać się X, aby istniało rozwiązanie zadania; max ( — — ^ , P } < o, > > Pi /

(6 )

lub — oo, gdy §j ^ 0,

max iH/ ’ Pj>o, (V~ " Pi

(7)

lub + oo, gdy fij ^ 0. Dla skończonych w&rtości X wyznaczamy (metodą sim ­ pleks programowania liniowego) kolejne rozwiązania zadania (1)— (3) dopóki oie osiągniemy X= q dla_A^A^A i r = I 168

Dla B Ponieważ mamy znaleźć rozwiązanie optym alne dla X = q, to wektor, który nie ma wejść do bazy, nie może być wprowadzony do niej, gdyż wszystkie jego składowe są niedodatnie. Niech pk będzie tym w ektorem to ak + X($k > 0 i x ik^.O. Zachodzą dwie sytuacje: 1) jeżeli (3k 0, to zagadnienie nie ma rozwiązań dla żadnego X, 2) jeżeli 0 jest spełnione dla: . dla

X e < q , X\ >

(8)

i żadne rozwiązanie nie jest skończone. Jeżeli wszystkie a} + X określone wzorem:

^ 0, to istnieje rozwiązanie

Rozwiązanie jest ważne dla X'1 ^ X ^ X^ Oznacza to, że: — można badać i rozwiązywać zagadnienie o jednoparam etrow ej funkcji celu stosując metodę sim­ pleks, — jeżeli jest dane rozwiązanie skończone, to można wyznaczyć zbiór rozwiązań charakterystycznych i odpowiednie wartości charakterystyczne dla wszy­ stkich możliwych wartości param etru, — rozwiązanie jest minimalne w domkniętym prze­ dziale param etrów; przedział ten jest spójny. E fe k ty w n o ś ć i koszty m eto d y

Koszty obliczeń metodą programowania liniowego pa­ rametrycznego są proporcjonalne do kosztów obliczeń programowania liniowego, co pozwala powtarzać je 169

wielokrotnie — szybko i tanio. Dużo trudniej jest ze­ brać odpowiednie dane liczbowe (nowe wartości para­ metrów) charakteryzujące rozwiązywany problem za­ rządzania w losowej i niepewnej sytuacji decyzyjnej. Analiza stabilności (wrażliwości) otrzymanych rozwią­ zań optym alnych w badaniach programowania liniowe­ go jest z reguły bardzo efektywna. *

Sposób nauczania lub p o sługiw ania się m eto d ą

Jak w przypadku metody programowania liniowego.

LITERATURA

[,1] Harasymowicz J., Piętka B., Rozwiązanie programu linio­ wego za pomocą algorytmu simplex na maszynie cyfrowej ICT (seria 1900), OBRI, Warszawa 1972. [2] Radzikowski W., Programowanie liniowe i nieliniowe w organizacji i zarządzaniu, Uniwersytet Warszawski, War­ szawa 1978. [3] Stopyra J., Programowanie parametryczne, Uniwersytet Warszawski, Warszawa 1978. [4] Szczur M. A., Analiza warunków stosowania programowania liniowego do optymalizacji struktury produkcji branży, Instytut Planowania, Warszawa 1975.

Przykład zastosow ania m etody

Najlepiej opracowane są metody badania możliwości i konsekwencji zmian wartości param etrów funkcji wy­ ników, czyli współczynników có (j = 1, 2, . .., n), oraz zmiany wartości param etrów bt (i = 1, 2, . .., m), czyli elementów wektora ograniczeń zasobów b. Na przykład 170

firmowe p ak iety 2 oprogramowania komputerów ICL pod nazwą XDL4 i XDL8 pozwalają na dokonanie od­ powiednich obliczeń także za pomocą polskich kompu­ terów serii ODRA 1300, co zilustrujem y przykładem opracowania nowego planu przedsiębiorstwa przemy­ słowego. 1. Zadanie opracowania NOWEGO PLANU przedsię­ biorstwa sprowadza się do zadania programowania li­ niowego, w którym dane są: — macierz współczynników o n kolumnach i m wier-, szach: \ _ t„ 1 _ A = [Gij] =

a21a22 0>mn

—- wektor ograniczeń o m składowych: ‘

“ bi " b2

b =

(11)

funkcja liniowa zwana funkcją wyników: 72

(j = 1,2, . .., n),

(12)

gdzie: Cj — współczynniki funkcji funk< wyników, Xj — zmienne decyzyjne. ! P r z y w y k o r z y s t a n iu p a k ie t ó w X D L 4 i X D L 8 o b li c z e n ia o p t y m a liz a ­ c y j n e p r o w a d z o n e są m e to d ą s im p le k s z r ó w n o c z e s n y m w y z n a c z e n ie m r o z w ią z a ń w z a d a n ia c h d u a ln y c h (zob. s. 143).

Zadanie programowania liniowego oparte n a danych (10)—(12) można sformułować następująco: znaleźć takie rozwiązanie a?i x2 X=

(13) 3Cn

układu nierówności ^ a ^ R b i (i = 1,2, . . . , m; j = 1,2, . . n), i gdzie R oznacza równanie albo relację lub aby przy założeniu x, > 0

(j = 1 , 2 , . . . , )

(14)

(15)

funkcja wyników (12) osiągnęła wartość ekstrem alną (minimum lub maksimum). Wśród nierówności zapisanych w układzie (14) zazwy­ czaj znajdują się również relacje typu dj < Xj ^ qjf gdzie dj ^ 0 oznacza dolną, minimalną wielkość pro­ dukcji wyrobu Xj, natom iast gj < oo oznacza górną, m aksym alną wielkość produkcji wyrobu X] (j = 1, 2, .. ., n). Niekiedy w ystępuje również żądanie, aby zmien­ na Xj przybierała wartości całkowitoliczbowe, czego tutaj nie rozpatrujem y. 2. Program y komputerowe XDL4 i XDL8 pozwalają na przeprowadzenie prób realokacji zasobów (a więc i wykazania możliwości wykonania nowego planu pro­ dukcji w ram ach posiadanych zasobów) dzięki określo­ nym procedurom. NEXT B. Wprowadzenie nowej wersji w ektora b ogra­ niczeń zasobów. Może być kilka takich w ersji wartości składowych bt wektora b deklarowanych przez użyt­ kownika (zob. przykład poniżej). 172

DUAL SOLUTION. Rozwiązanie y = [yt] zadania dual­ nego wskazuje, o ile mogłaby wzrosnąć wartość funkcji wyników w przypadku zmiany dysponowanej ilości za­ sobu i-tego (i = 1, 2, . . m). Dla poszczególnych yi m am y przedział ważności At = = (bt + Abi, — Abi), gdzie Abt ^ 0 oraz Abt ^ 0. Zmienne yi określają wielkość „nacisku”, jaki wywiera na ograniczenie bt pewnego zasobu struktura związków przyjętych w modelu (13)—(15) w punkcie optym al­ nym. Rozwiązanie dualne v = [vó] dla zmiennych x t ograni­ czonych relacjam i gj (j = 1, 2, . . . , n) infor­ muje nas o tym, które z ograniczeń brzegowych jest istotne — dolne czy górne — i jaki jest „koszt” utrzy­ mywania produkcji wyrobu X } na poziomie dj lub gj. COST RANGING (II). Podanie granicy odchyleń dla współczynników funkcji wyników, przy których bieżące rozwiązanie pozostaje optymalne (analiza stabilności rozwiązania). Chodzi o jednoczesne zmiany układów współczynników funkcji wyników, oznaczone jako Ac. Dla każdego współczynnika c3- (j — 1, 2, . .. , n) mamy: Ac =

cj 0

dla dla

j e n, j 6 (n — n),

(16)

spełniający — w pewnych w arunkach [3] — układ nie­ równości: (cD + (oc)D) D_1aj — (Cj + ocj) ^ 0 dla (cD + (oc)D) D -idj - Cj < 0 dla

j e n,

j e (n - rc),

(17)

który w pełni opisuje obszar dopuszczalnych zmian współczynników funkcji wyników. W układzie tym D — macierz w yjęta z macierzy A = = [aij]> utworzona z kolumn dj odpowiadających zmien­ nym Xj składającym się na rozwiązanie; cD — w ektor 173

w yjęty z wektora c o współczynnikach c} odpowiadaj ąjących zmiennym x jy które tworzą rozwiązanie; D - 1 — macierz odwrotna do macierzy D ; oc — w ektor o składo­ wych acJt n e n — zbiór indeksów j odpowiadających tym współczynnikom funkcji wyników, których jedno­ czesne zmiany nas interesują. Wartości poszczególnych oc oblicza kom puter w trakcie wyznaczania optym al­ nego rozwiązania zadania (13)—(15). RHS RANGING (II). Określenie maksym alnych i mi­ nim alnych wartości ograniczeń zasobów, dla których bieżące rozwiązanie pozostanie optym alne (analiza sta­ bilności rozwiązania). W tym przypadku chodzi również o jednoczesne zmiany układu ograniczeń na poszczególne zasoby b* (i — 1, 2, . . . , m ).^ Niech m e m będzie zbiorem indeksów i odpowiadają­ cych tym ograniczeniom b{ dysponowanych zasobów, których równoczesne zmiany nas interesują. Dla tych zmian oznaczonych Ab mamy relację: Ab

°J 0

dla dla

je m ’ _ j e (m — m),

(18)

spełniającą — w pewnych w arunkach [3] — układ nie­ równości: diO + di ^5 0 di (ob + d) ^ 0

dla dla

ie m , — i e ( m — m),

(19)

(gdzie di oznacza i-ty wiersz macierzy D - 1 ), który w pełni opisuje obszar dopuszczalnych zmian. Wartości poszczególnych ob kom puter oblicza w trakcie wyzna­ czania optymalnego rozwiązania zadania (13)—(15). Procedury powyższe czynią z metod programowania liniowego użyteczne narzędzie planowania, co chcemy 174.

zilustrować przykładem 3 zaczerpniętym z pracy J. Ha­ rasymowicz i B. Piętki [1]. Przykład liczbowy Załóżmy, że posiadamy 3 urządzenia produkcyjne n a­ wzajem zamienne Y lt Y2, Y3. Na tych urządzeniach mo­ żemy produkować 4 wyroby X±, X2, X3, X 4. Maszynochłonność jednostkowa ay (i = 1, 2, 3 oraz j = 1, 2, 3, 4) jest to norm a czasu pracy urządzenia i-tego n a 1 sztukę wyrobu j-tego. Dysponowany fundusz czasu pracy urzą­ dzenia Y{ (i = 1, 2, 3) oznaczymy przez bu natom iast cenę zbytu wyrobu X j (j = 1, 2, 3, 4) — c}. Opracowu­ jąc plan stawiamy sobie za cel osiągnięcie maksimum wartości produkcji towarowej. Odpowiednio do (10), (11) i (12) możemy zapisać: A

[ay]

0,5

o

:5

2 3

2 2

2 0

'

200 200 200

b == [b j = ,

c' = [c,r = [4

3

r 0 5

(10.1)

" (11.1)

i 20

30],

(20)

co pozwala nam sformułować zadanie wyjściowe pro­ gramowania liniowego. Określić takie wielkości produkcji Xj poszczególnych wyrobów X J- (j = 1, 2, 3, 4), aby zmaksymalizować wartość produkcji towarowej: 4

^

CjXj = 4x1 + 3x2 + 20x3 + 30x4 ->■ m ax

(21)

3=1

* Jest to przykład uproszczony, nie zawiera bowiem ograniczeń typu Xj > dj oraz Xj < gj (gdzie j = 1, 2,..., n, dj — dolna minimalna wielkość produkcji wyrobu X j , gj — górna, maksymalna wielkość produkcji w y ­ robu X j) . Uproszczenie to zastosowano celowo, aby nie odwracać uwagi

Czytelnika od głównych problemów realokacji zasobów.

175

przy ograniczeniach: 0,5Xi + 0x2 + 3 x 3 2x1 + 2 x 2 ■+ 2x% 3X i +

2x 2 +

0x3

+ + +

lx 4 ^ 200, 0 x 4 ^ 2 0 0 , (2 2 ) 5xi ^

200

oraz zachowaniu w arunków brzegowych: Xi>0

(j = 1,2, 3, 4).

(23)

W ykorzystując dane liczbowe zapisane przez (10.1), (11.1) i (20), możemy sformułować również zadanie dualne do zadania (21)— (23). Określić takie wielkości y% zużycia czasu poszczególnych urządzeń Yt (i = 1, 2, 3), aby zminimalizować łączną maszynochłonność produkcji: 3

^

= 200t/i + 200y2 + 200yz = min

(24)

i= l

przy ograniczeniach: 0,5yi Oyi 3yi ly i

4* + + +

2y2 21/2 2y 2 0^/2

+ 3yz > 4, + 2y3 > 3, + 0y3 > 2 0 , + 5y3 > 3

'

'

oraz przy zachowaniu w arunków brzegowych: j/t > 0

(i = l, 2, 3)

(26)

W artość zmiennych decyzyjnych y% w rozwiązaniu za­ dania dualnego będzie nas interesować przy analizie wyników obliczeń. W yniki te uzyskano dzięki wykorzystaniu do obliczeń kom putera ODRA 1305. Rozwiązanie optymalne x± = 0, x 2 — 0, 176

x 3 = 53,333, x 4 = 40,000, /(x) = 2266,667. Oznacza to, że należy produkować tylko w yroby X3 i X 4 w ilościach x3 = 53,333 i i 4 = 40,000, w tedy wartość produkcji towarowej wyniesie 2266,667 jednostek pie­ niężnych i będzie w danych w arunkach maksymalna. Zmienne swobodne n = y2 = 93,333, 7* = 0. Oznacza to niewykorzystanie 93,333 jednostek czasu pracy urządzenia Y2. Urządzenia Y 1 oraz Y3 są wyko­ rzystane w pełni („wąskie gardła”). Rozwiązanie zadania dualnego yi = 6,667, 2/2

= 0,

yz = 4,667. Interpretacja wartości zmiennych optymalnego rozwią­ zania zadania dualnego jest następująca: 1) jeżeli fun­ dusz czasu pracy urządzenia Ylf będącego „wąskim gardłem” w procesie produkcji, zwiększymy o 1 jed­ nostkę, to uzyskamy wzrost wartości funkcji celu (czyli wzrost wartości produkcji towarowej) o 6,667 jednostek pieniężnych oraz 2) jeżeli zwiększymy fundusz czasu pracy urządzenia Y3 (stanowiącego „wąskie gardło”) o 1 jednostkę, to uzyskamy wzrost wartości funkcji celu (wartości produkcji towarowej) o 4,667 jednostek pie­ niężnych. Wynika z tego, że powiększanie funduszu czasu pracy urządzenia Yj jest bardziej korzystne niż powiększanie funduszu czasu pracy urządzenia Y3. Fakt 12 Matematyczne techniki zarządzania

177

ten możemy wykorzystać do realokacji zasobów (fun­ duszy czasu pracy urządzeń produkcyjnych Y1} Y2, Y3): a. Wiemy, że urządzenie Y2 nie jest wykorzystane w pełni, wykazuje bowiem rezerw y w ilości 93,333 jed­ nostek czasu pracy. Ponieważ — co założyliśmy — urzą­ dzenia produkcyjne są naw zajem zamienne, to rezerwę jednostek czasu pracy możemy rozdysponować między urządzeniami Yi oraz Y3 w proporcjach wynikających z analizy otrzymanego rozwiązania optymalnego: 2/i: 2/s = 6 , 6 6 7 -.4,667 = 10 : 7.

b. Przy realokacji zasobów we wskazany sposób musi­ my uwzględnić jeszcze w yniki uzyskane z procedury RHS RANGING (II), podającej maksymalne i mini­ malne wartości ograniczeń bt (i = 1, 2, 3), dla których otrzymane rozwiązanie pozostaje rozwiązaniem opty­ malnym (analiza stabilności rozwiązania). W naszym przypadku naw et bardzo małe zmiany war­ tości ograniczeń bt powodują wyznaczenie nowego roz­ wiązania, gdyż kom puter wyliczył dopuszczalne granice zmian następująco:

b1 bo i>3

dopuszczalne zmiany granicy dolnej

dopuszczalne zmiany granicy górnej

1,86265-s 0 3,72529-s

0 0 0

c. To rozwiązanie będzie wykazywało NOWE WIĘK­ SZE ilości produkcji poszczególnych wyrobów Xj (j = = 1, 2, 3, 4) oraz NOWĄ WIĘKSZĄ wartość funkcji wyników, co jest oczywiste i nie wymaga szczegółowej analizy. d. W ykorzystanie procedury COST RANGING (II), po­ dającej granice odchyleń wartości współczynników funkcji wyników, dla których uzyskane rozwiązanie 178

pozostaje rozwiązaniem optymalnym, pozwala na ana­ lizę cenowej stabilności rozwiązania. Dopuszczalne gra­ nice zmian komputer określił następująco: dopuszczalne zmiany granicy dolnej

dopuszczalne zmiany granicy górnej

oc‘

0

0

oCt

0

0

oCs oCt

1 9

1 12

Okazuje się, że w naszym przykładzie naw et znaczne zmiany wartości współczynnika c4 nie zmieniają w ar­ tości otrzymanego rozwiązania optymalnego. Współ­ czynnik c3 jest bardziej w rażliwy 0

(3)

x e D,

(4)

oraz w arunku: gdzie: R — jedna z relacji „ = ”, D -r- zbiór przeliczalny, x — wektor n-wymiarowy. Jeżeli zbiór przeliczalny D będzie zbiorem liczb całko­ witych (całkowitych dodatnich, całkowitych ujemnych i zero), to zapiszemy nowy warunek: xeDc,

gdzie Dc jest zbiorem liczb całkowitych. 1 Od łacińskiego discretus — rozdzielony, przerywany.

182

(4.1)

O zadaniu zapisanym przez (1)—(3) i (4.1) powiemy, że jest zadaniem programowania w liczbach całkow itych2. Gdy albo funkcja wyników (1) albo co najm niej jedna spośród m funkcji nakładów (2) jest nieliniowa, wów­ czas brak metod wyznaczania rozwiązań optymalnych w zadaniu (1)—(3) i (4.1). Niekiedy rozwiązanie zadania optymalizacyjnego w liczbach całkowitych można uzys­ kać w sposób najprostszy, choć zarazem tryw ialny — przez zaokrąglenia ułamków (występujących w rozwią­ zaniu) do liczb całkowitych. Najczęściej jednak postę­ powanie takie nie jest możliwe. Jedynym zbadanym dotychczas przypadkiem progra­ mowania w liczbach całkowitych jest programowanie liniowe w liczbach całkowitych, którego model można zapisać w sposób podobny do przedstawionego wyżej: — wyznaczyć ekstrem um funkcji wyników: /(x) = c'x

(1*1)

— poddanej ograniczeniom: Ax 0

(3) (4.1)

x e Dc

gdzie c jest wierszowym wektorem współczynników funkcji wyników (np. wektorem cen). Większość metod rozwiązywania zadań programowania liniowego w liczbach całkowitych przewiduje dwa etapy wyznaczania rozwiązania optymalnego: 1) wyznacza się rozwiązanie zadania (1.1), (2.1), (3), (4.1) na podstawie jednej z metod programowania linio­ wego, np. metody simpleks, 2) sprowadza się rozwiązanie w liczbach ułamkowych do rozwiązania w liczbach całkowitych przez iriody1 Jeżeli warunek (4.1) spełniony jest nie przez wszystkie Xj e x (j = = 1,2, ..., n), ale tylko przez niektóre z nich, to mówimy wówczas o programowaniu częściowo w liczbach całkowitych.

183

fikację wyjściowego zadania (1.1), (2.1), (3) i (4.1), a następnie znów rozwiązuje się je metodą sim­ pleks. E fe k ty w n o ś ć i koszty m eto d y

Podstawowe algorytm y programowania liniowego w liczbach całkowitych są realizowane komputerowo. Uwzględnienie w arunku całkowitoliczbowości pozwala opisać i badać wiele problemów zarządzania w sposób bardziej odpowiadający ich naturze, a więc efektyw­ niej. Koszty przygotowania danych do obliczeń (warian­ ty rozwiązań) mogą być wysokie. Sposób nauczania lub p o sługiw ania się m eto d ą

Programowanie liniowe w liczbach całkowitych jest tak samo proste pojęciowo, jak zwykłe programowanie liniowe i także w ykładane w szkołach wyższych. Rów­ nież w przypadku stosowania programowania liniowego w liczbach całkowitych decydujące znaczenie dla m a­ tematycznego modelowania problemów zarządzania ma znajomość merytorycznych aspektów tych problemów.

LITERATURA

[1] Korbut A. A., Finkelsztejn, Programowanie dyskretne, PWN, Warszawa 1974. [2] Kiinzi H. P., Tan S. T., Lineare Optimierung Grosser Systeme, Springer Verlag, Heidelberg 1966. [3] Land A. H., Doig A. G., An Automatic Method for Solving Discrete Programming Problems, „Econometrica” 1960, nr 28. [4] Radzikowski W., Programowanie liniowe i nieliniowe w organizacji i zarządzaniu, Uniwersytet Warszawski, War­ szawa 1978. [5] Tieriechow L., Metody ekonomiczno-matematyczne, PWE, Warszawa 1970, rozdział III.

184

SVl@toda Landa-Boiga Metoda Landa-Doiga przew iduje dwuetapowe postępo­ wanie optymalizacyjne. Zilustrujem y je prostym przy­ kładem liczbowym Dane jest zadanie: /(x) =

+ c2x 2 -> min,

(5)

+ a12x 2 > bj 1 &21'M &22X2 ^ b2 j (j = l, 2), w liczbach całkowitych (j = 1, 2)

(7) (8)

Treść tego zadania przedstawiono na rysunku 1. Wa­ runki uboczne (6) i brzegowe (7) wyznaczają wypukły obszar K rozwiązań dopuszczalnych dla x t i x 2. Na obszarze tym należy wyznaczyć minimum funkcji (5). Rysunek 1 Schem atyczne przedstaw ienie tre ś c i zadania (5 )-(8 )

185

Załóżmy, że na etapie pierwszym wyznaczyliśmy wierz­ chołek optym alny (rozwiązanie optymalne) x°, który przew iduje następujące wartości dla x x i x 2: 2< a:i< 3'

m

1

W




y,

(11)

gdzie y = inf f(x)Q w liczbach całkowitych; y > j:(x)0. Każde powiększenie wartości y przesuwa prostą f(x)0 coraz dalej do wnętrza obszaru K. Zgodnie ze schema­ tem metody Landa-Doiga postępujem y w tedy w okre­ ślony sposób. Wyznaczamy metodą simpleks w k iteracjach rozwią­ zanie x k zadania (5)—(8), bez uwzględniania w arunku całkowitoliczbowości zmiennych x k rozwiązania (i = 1, 2, . . . , m). W pewnych (szczęśliwych) przypadkach może się zdarzyć, że x k będzie rozwiązaniem całko witoliczbowym, w tedy kończymy postępowanie. Jeżeli jednak x k zawiera zmienne o wartości ułamkowej, to przechodzimy do iteracji k rf 1. Krok 1. Dokonujemy takiego oszacowania y, że w arun­ ki (6) i (7) wyznaczają zbiór K°, dla którego y = inf f(x)k w liczbach całkowitych, y > f(x)k. W arunek y oznacza więc najmniejszą liczbę całkowitą nie mniejszą od j:(x)k. Krok 2. Bierzemy pierwszą w kolejności współrzędną niecałkowitą wektora x k (zmienną x k) i dzielimy ob­ szar K° na dwa podobszary K° i K°; K° = K° U K° = { x \ x e K ° , x 8 < x k}, K ° = { x | x e K ° , xs > x k}. Krok 3. Wyznaczamy m etodą simpleks rozwiązania dwóch zadań programowania liniowego typu (5)—(8) przy {f(x ) = m in | x e K ° } i {f(x) = min j x e K° }. Dla obu rozwiązań obliczamy y° i y°, a następnie wyzna­ czamy y = min {j>°, y°}. Zgodnie z wyznaczonym y obieramy kolejne rozwią­ zanie jako x k+1. Jeżeli x k+1 jest rozwiązaniem całkowitoliczbowym, to kończymy postępowanie. W przeciw­ nym przypadku wracamy do kroku 1 i dokonujemy na­ stępnej iteracji aż do skutku. 187

Metoda Gomory‘ego Metoda Gomory’ego przewiduje dwuetapowe postępo­ wanie optymalizacyjne: 1) za pomocą jednej z m etod programowania liniowego np. metody simpleks wyznacza się wierzchołek opty­ m alny x°, którem u odpowiadają zmienne wyrażone (najczęściej) w liczbach ułamkowych; dla przypadku dwuwymiarowego (rysunek 2) wierzchołek x° może być przedstawiony np. jako punkt Plt 2) do układu warunków ubocznych zadania dodaje się pewien nowy w arunek (i pewną dodatkową zmien­ ną), w wyniku czego obszar K zostaje zmiejszony; na rysunku 2 zmniejszenie obszaru K uzyskano przez zastąpienie prostej (b) prostą (b'); nowe za­ danie ma już rozwiązanie w liczbach całkowitych. Rysunek 2 Przykład postępow ania w y ­ znaczającego rozwiązanie w liczbach całkowitych zadania program ow ania liniowego

Opis m etody Gomory1'ego pochodzi z pracy [5]. W k — 1 iteracjach wyznaczamy metodą simpleks roz­ wiązanie x k zadania typu (5)—(8) bez uwzględniania w arunku całkowitoliczbowośei zmiennych x k rozwiąza­ nia (i = 1, 2, . . m). Może się przypadkowo zdarzyć, że x k będzie rozwiązaniem w liczbach całkowitych, wtedy uznam y x k za rozwiązanie optym alne i zakoń­ czymy postępowanie. W przeciwnym przypadku prze­ chodzimy do iteracji k. Krok 1. W ybieramy składową x k wektora x k, która w y­ różnia się najm niejszą częścią ułamkową (i ^ r ^ m). K onstruujem y dodatkowe równanie typu (6), w którym zmienna x k wyrażona jest przez część stałą plus linio­ wa funkcja zmiennych niebazowych x £ (j = m + 1, m + 2, .. m + n); m +n

x* = b * + £

a* x f ,

(11)

j=m+l

z czego wynika 3: m +n

b*+ V a % x * = 0

(12)

j= m + l

albo m +n

£

( - « * ) * * = bf , .

(13)

j= m + 1

* Wprowadźmy pojęcia kongruencji liczb i ułamkowej części liczby [5, s. 185]. Liczba a jest kongruentna do liczby b wtedy i tylko wtedy, gdy różnica (a—b) jest liczbą całkowitą. Kongruencję oznaczamy za po­ mocą trzech poziomych kresek np. 5/3 = 2/3, bo 5/3 — 2/3 = 1. Czę­ ścią u ła m k o w ą liczby a będziemy nazywać najmniejszą liczbę nieujemną kongruentną do liczby a. Część ułamkową liczby a oznaczamy za pomocą symbolu

(a + b) = (na) = "• n cp (a).

189

Krok 2. Z części ułamkowych a*, i bk występujących w w yrażeniu (13) konstruujem y równanie: m+n

^ 9 ?( " " a ?j) X3= ^ ( b?)

(14)

j=m+l

oraz przy uwzględnieniu w arunku całkowitoliczbowości zmiennych x } nierówność: m+ n

^ [ 9 ? ( - a ^ ) ] x,>ę?(b*).

(15)

j=m+l

Krok 3. Nierówność (15) włączamy — po przekształce­ niu na równanie — do zadania typu (5) i (8) i rozwią­ zujemy je metodą simpleks bez uwzględniania w arunku całkowi toliczbowości zmiennych rozwiązania. Jeżeli x k+l jest rozwiązaniem w liczbach całkowitych, to po­ stępowanie kończymy. W przeciwnym przypadku w ra­ camy do kroku 1 i dokonujem y następnej iteracji. Przykład liczbowy Dane jest zadanie: f(x) = 7xi + 3x2->m ax,

(16)

!

(17)

i , , x 2 > 0,

(18)

Xj i x2 w liczbach całkowitych.

(19)

Wprowadzenie zmiennych swobodnych x 3 i x 4 pozwala przekształcić nierówności (17) i zapisać całe zadanie następująco: f(x) — 7Xi -f 3x2 + 0x3 + 0x4 5Xi + 2x2 + lx 3 = 20 \ 8xj + 4x 2 + lx 4 = 38 | 190

max,

(16.1) 1

;

x ,> 0