Rodzaje programowania liniowego. Rozwiązywanie problemów programowania liniowego metodą graficzną

Adnotacja: Wykład ten ukazuje szereg zagadnień poświęconych programowaniu liniowemu w ramach jednego z działów programowanie matematyczne; w szczególności formułuje główne rodzaje zadań Programowanie liniowe, ujawnia różnice między tymi zadaniami i klasyczne problemy Analiza matematyczna; przedstawia różne formy rejestruje te zadania, ustala je i bada ich strukturę. Najpełniej zbadana jest kwestia rozwiązywania problemów programowania liniowego metodą sympleksową.

1. Pojęcie programowania matematycznego

to dyscyplina matematyczna rozwijająca metody znajdowania wartości ekstremalnych funkcja celu wśród zbioru jego możliwych wartości, określonych przez ograniczenia.

Obecność ograniczeń sprawia, że problemy zasadniczo różnią się od klasycznych problemów analizy matematycznej polegającej na znajdowaniu ekstremalnych wartości funkcji. Metody analizy matematycznej w poszukiwaniach ekstremum funkcji w zadaniach programowanie matematyczne okazać się nieodpowiednie.

Rozwiązywać problemy programowanie matematyczne Opracowano i nadal rozwija się specjalne metody i teorie. Ponieważ rozwiązanie tych problemów wymaga wykonania znacznej ilości obliczeń, kiedy ocena porównawcza metody bardzo ważne przywiązuje się wagę do wydajności i wygody ich realizacji na komputerze.

Można go uznać za zbiór niezależnych sekcji zajmujących się badaniem i rozwojem metod rozwiązywania określonych klas problemów.

W zależności od właściwości funkcji celu i funkcji ograniczenia, wszystkie problemy programowanie matematyczne dzielą się na dwie główne klasy:

problemy programowania liniowego,
zadania programowanie nieliniowe.

Jeśli funkcja celu i funkcje ograniczeń są funkcjami liniowymi, wówczas odpowiadający im problem znalezienia ekstremum jest problemem programowania liniowego. Jeśli chociaż jeden z określone funkcje jest nieliniowy, to odpowiadający mu problem znalezienia ekstremum jest problemem programowanie nieliniowe.

2. Pojęcie programowania liniowego. Rodzaje problemów programowania liniowego

Programowanie liniowe(LP) – jedna z pierwszych i najdokładniej zbadanych sekcji programowanie matematyczne. Dokładnie Programowanie liniowe była sekcją, z której zaczęła się rozwijać sama dyscyplina” programowanie matematyczne„. Termin „programowanie” w tytule dyscypliny nie ma nic wspólnego z terminem „programowanie (czyli kompilacja programu) na komputer” nie ma nic wspólnego z dyscypliną” Programowanie liniowe„powstał jeszcze przed czasem, gdy komputery zaczęto powszechnie stosować do rozwiązywania problemów matematycznych, inżynieryjnych, ekonomicznych i innych.

Termin " Programowanie liniowe" powstało w wyniku niedokładnego tłumaczenia angielskiego "programowania liniowego". Jednym ze znaczeń słowa "programowanie" jest robienie planów, planowanie. Dlatego też poprawne tłumaczenie angielskiego "programowania liniowego" nie byłoby " Programowanie liniowe", oraz "planowanie liniowe", które dokładniej oddaje treść dyscypliny. Jednak terminy Programowanie liniowe, programowanie nieliniowe, programowanie matematyczne itp. zostały powszechnie przyjęte w naszej literaturze i dlatego zostaną zachowane.

Więc, Programowanie liniowe powstały po drugiej wojnie światowej i zaczęły się szybko rozwijać, przyciągając uwagę matematyków, ekonomistów i inżynierów ze względu na możliwość szerokiego zastosowania praktycznego, a także harmonię matematyczną.

Można tak powiedzieć Programowanie liniowe zastosowanie do rozwiązania modele matematyczne te procesy i systemy, które można oprzeć na hipotezie liniowej reprezentacji świata rzeczywistego.

Programowanie liniowe wykorzystywane przy rozwiązywaniu problemów ekonomicznych, w zadaniach takich jak zarządzanie i planowanie produkcji; w problematyce ustalania optymalne umiejscowienie sprzęt na statkach morskich, w warsztatach; w problematyce ustalania optymalnego planu transport ładunków ( problemu transportu); w zadaniach optymalna dystrybucja personel itp.

Problem programowania liniowego(LP), jak już wynika z tego, co zostało powiedziane powyżej, polega na znalezieniu minimum (lub maksimum) funkcja liniowa w ramach ograniczeń liniowych.

Formularz ogólny problem ma postać: znajdź pod pewnymi warunkami

Wraz z forma ogólna również szeroko stosowane kanoniczny I standard formy. Zarówno w formie kanonicznej, jak i standardowej

Te. wszystkie zmienne w każdym możliwym rozwiązaniu problemu muszą przyjmować wartości nieujemne (takie zmienne są zwykle nazywane nieujemne w odróżnieniu od tzw bezpłatny zmienne, których zakres wartości nie podlega takim ograniczeniom). Różnica pomiędzy tymi postaciami polega na tym, że w jednym przypadku I 2 = 0, a w drugim - I 1 = 0.

Problem LP w postaci kanonicznej.

Programowanie liniowe

Programowanie liniowe- dyscyplina matematyczna poświęcona teorii i sposobom rozwiązywania problemów ekstremalnych na zbiorach -wymiarowej przestrzeni wektorowej określonej przez układy równań i nierówności liniowych.

Programowanie liniowe jest szczególnym przypadkiem programowania wypukłego, które z kolei jest szczególnym przypadkiem programowania matematycznego. Jednocześnie stanowi podstawę kilku metod rozwiązywania problemów programowania całkowitoliczbowego i nieliniowego. Jednym z uogólnień programowania liniowego jest programowanie liniowe ułamkowe.

Wiele właściwości problemów programowania liniowego można również interpretować jako właściwości wielościanów, a tym samym formułować i udowadniać geometrycznie.

Fabuła

Metoda punktu wewnętrznego została po raz pierwszy wspomniana przez I. I. Dikina w 1967 roku.

Zadania

Główny (standardowy) problem programowania liniowego nazywa się problemem znalezienia minimum liniowej funkcji celu (postaci liniowej) postaci:

na warunkach

, .

Będzie miał problem z programowaniem liniowym pogląd kanoniczny , jeśli w zadaniu głównym zamiast pierwszego układu nierówności występuje układ równań:

Główny problem można sprowadzić do kanonicznego, wprowadzając dodatkowe zmienne.

Zadania programowania liniowego w najbardziej ogólnej postaci (problemy z ograniczeniami mieszanymi: równości i nierówności, obecność zmiennych wolnych od ograniczeń) można sprowadzić do równoważnych (mających ten sam zestaw rozwiązań) poprzez zastąpienie zmiennych i zastąpienie równości parą nierówności.

Łatwo zauważyć, że problem znalezienia maksimum można zastąpić zadaniem znalezienia minimum poprzez przyjęcie współczynników o przeciwnym znaku.

Przykładowe problemy

Maksymalne dopasowanie

Rozważ problem maksymalnego dopasowania na grafie dwudzielnym: jest kilku chłopców i dziewcząt i dla każdego chłopca i dziewczynki wiadomo, czy są dla siebie atrakcyjni. Musimy poślubić maksymalną liczbę par przy wzajemnej sympatii.

Wprowadźmy zmienne odpowiadające parze -chłopiec i -dziewczyna i spełniające ograniczenia:

z funkcją celu. Można wykazać, że wśród optymalnych rozwiązań tego problemu znajduje się rozwiązanie całkowite. Zmienne równe 1 będą odpowiadać parom, które powinny zawrzeć związek małżeński.

Maksymalny przepływ

Niech będzie graf (z zorientowanymi krawędziami), w którym dla każdej krawędzi jest wydajność. Podano dwa wierzchołki: dren i źródło. Dla każdej krawędzi należy wskazać, ile cieczy przepłynie przez nią (nie więcej niż jej pojemność), aby zmaksymalizować całkowity przepływ od źródła do drenu (ciecz nie może pojawiać się ani znikać we wszystkich wierzchołkach z wyjątkiem drenu i źródła).

Za zmienne przyjmijmy ilość cieczy przepływającej przez żebro. Następnie

gdzie jest pojemność tej krawędzi. Nierówności te należy uzupełnić równością ilości dopływającego i odpływającego płynu dla każdego wierzchołka, z wyjątkiem drenu i źródła. Jako funkcję naturalne jest przyjmowanie różnicy między ilością wypływającego i wpływającego płynu u źródła.

Uogólnieniem poprzedniego problemu jest maksymalny przepływ przy minimalnych kosztach. W tym zadaniu podane są koszty dla każdej krawędzi i spośród maksymalnych przepływów należy wybrać przepływ z minimalny koszt. Problem ten sprowadza się do dwóch problemów programowania liniowego: najpierw należy rozwiązać problem maksymalnego przepływu, a następnie dodać do tego problemu ograniczenie , gdzie jest wartość maksymalnego przepływu i rozwiązać problem Nowa cecha- koszt przepływu.

Problemy te można rozwiązać szybciej niż przy pomocy ogólnych algorytmów rozwiązywania problemów programowania liniowego ze względu na specjalną strukturę równań i nierówności.

Zadanie transportowe

Istnieje pewien jednorodny ładunek, który należy przewieźć z magazynów do fabryk. Dla każdego magazynu wiadomo, ile ładunków zawiera, a dla każdego zakładu znane jest jego zapotrzebowanie na ładunek. Koszt transportu jest proporcjonalny do odległości magazynu od fabryki (znane są wszystkie odległości od magazynu do fabryki). Wymagane jest skompilowanie większości taniego planu transport.

Decydujące zmienne w w tym przypadku to ilości ładunku przewiezionego z th magazynu do th zakładu. Spełniają ograniczenia:

Funkcja celu ma postać: , którą należy zminimalizować.

Gra o sumie zerowej

Istnieje macierz rozmiarów. Pierwszy gracz wybiera liczbę od 1 do , drugi od 1 do . Następnie sprawdzają liczby i pierwszy gracz otrzymuje punkty, a drugi punkty (liczba wybrana przez pierwszego gracza otrzymuje drugi). Musimy znaleźć optymalną strategię dla pierwszego gracza.

Załóżmy na przykład, że w strategii optymalnej pierwszy gracz musi wybrać liczbę z prawdopodobieństwem . Wówczas optymalną strategią jest rozwiązanie następującego problemu programowania liniowego:

, , (),

w którym funkcja ma być maksymalizowana. Wartość w rozwiązaniu optymalnym będzie matematycznym oczekiwaniem wypłaty pierwszego gracza w najgorszym przypadku.

Algorytmy rozwiązań

Najbardziej znaną i powszechnie stosowaną w praktyce metodą rozwiązywania ogólnego problemu programowania liniowego (LP) jest metoda simpleksowa. Pomimo tego, że metoda simplex jest algorytmem dość skutecznym, który wykazał dobre wyniki w rozwiązywaniu stosowanych problemów LP, jest to algorytm o złożoności wykładniczej. Powodem tego jest kombinatoryczny charakter metody simplex, która sekwencyjnie iteruje po wierzchołkach wielościanu dopuszczalne rozwiązania przy poszukiwaniu optymalnego rozwiązania.

Pierwszy algorytm wielomianowy, metoda elipsoidalna, został zaproponowany w 1979 roku przez radzieckiego matematyka L. Khachiyana, rozwiązując w ten sposób problem, który przez długi czas pozostawał nierozwiązany. Metoda elipsoidalna ma zupełnie inny, niekombinatoryczny charakter niż metoda simpleksowa. Jednak z obliczeniowego punktu widzenia metoda ta okazała się mało obiecująca. Jednak sam fakt wielomianowej złożoności problemów doprowadził do powstania całej klasy wydajne algorytmy płyta długogrająca - metody punktów wewnętrznych, z których pierwszym był algorytm N. Karmarkara zaproponowany w 1984 roku. Algorytmy tego typu wykorzystują ciągłą interpretację problemu LP, gdy zamiast wyliczać wierzchołki wielościanu rozwiązań zadania LP, przeprowadza się poszukiwania wzdłuż trajektorii w przestrzeni zmienne problemowe, nie przechodząc przez wierzchołki wielościanu. Metoda punktów wewnętrznych, która w odróżnieniu od metody simpleksowej omija punkty z wnętrza obszaru dopuszczalne wartości, wykorzystuje metody programowania nieliniowego z barierą logarytmiczną opracowane w latach 60. XX wieku przez Fiacco i McCormicka.

Zobacz też

Graficzna metoda rozwiązywania problemu programowania liniowego

Notatki

Literatura

Thomas H. Corman i in. Rozdział 29. Programowanie liniowe // Algorytmy: konstrukcja i analiza = WPROWADZENIE DO ALGORYTMÓW. - wyd. 2 - M.: „Williams”, 2006. - s. 1296. - ISBN 5-8459-0857-4
Akulich I.L. Rozdział 1. Zagadnienia programowania liniowego, Rozdział 2. Specjalne problemy programowania liniowego // Programowanie matematyczne na przykładach i zadaniach. - M.: Szkoła wyższa, 1986. - 319 s. - ISBN 5-06-002663-9
Karmanow V. G. Programowanie matematyczne. - 3. edycja. - M.: Nauka, 1986. - 288 s.
Danzig George Bernard „Wspomnienia z początków programowania liniowego”

Spinki do mankietów

- Bezpłatny pakiet optymalizacyjny przeznaczony do rozwiązywania problemów programowania liniowego, całkowitego i celowego.
Vershik A. M. „O L. V. Kantorowiczu i programowaniu liniowym”
Bolshakova I. V., Kuralenko M. V. „Programowanie liniowe. Podręcznik edukacyjno-metodyczny do testu.”
Barsov A. S. „Co to jest programowanie liniowe”, Popularne wykłady z matematyki, Gostekhizdat, 1959.
M. N. Vyalyi Nierówności liniowe i kombinatoryka. -MCNMO, 2003.

Fundacja Wikimedia. 2010.

Salten, Feliks
Głagów, Martina

Zobacz, co „programowanie liniowe” znajduje się w innych słownikach:

Programowanie liniowe- - programowanie liniowe Dziedzina programowania matematycznego poświęcona teorii i metodom rozwiązywania problemów ekstremalnych charakteryzująca się zależność liniowa między… … Przewodnik tłumacza technicznego

Programowanie liniowe

Programowanie liniowe- dziedzina programowania matematycznego poświęcona teorii i sposobom rozwiązywania problemów ekstremalnych charakteryzujących się liniową zależnością pomiędzy zmiennymi. W najbardziej ogólnej formie problem L.p. można napisać w ten sposób. Są dane… … Słownik ekonomiczny i matematyczny

Programowanie liniowe pojawiło się jako odrębna gałąź matematyki stosowanej w latach 40. i 50. XX wieku. XX wiek dzięki pracy radzieckiego naukowca, zdobywcy Nagrody Nobla L.V. Kantorowicz. W 1939 roku opublikował pracę „Matematyczne metody organizacji i planowania produkcji”, w której wykorzystał matematykę do rozwiązywania problemów ekonomicznych dot. najlepiej pobierz maszyny, cięcie materiałów po najniższym koszcie, dystrybucja ładunku na kilka rodzajów transportu i inne, proponowanie sposobu rozwiązywania mnożników 8.

LV Kantorowicz jako pierwszy sformułował tak powszechnie stosowane koncepcje ekonomiczne i matematyczne, jak optymalny plan, optymalna alokacja zasobów, obiektywnie określone oceny, wskazując liczne obszary ekonomii, w których można je zastosować.

Pojęcie programowania liniowego wprowadził amerykański matematyk D. Dantzig, który w 1949 roku zaproponował algorytm rozwiązywania problemu programowania liniowego, zwany „metodą simpleksową”.

Programowanie matematyczne, do którego zalicza się programowanie liniowe, jest obecnie jednym z obszarów badań operacyjnych. W zależności od rodzaju rozwiązywanych problemów wyróżnia się takie obszary jak programowanie liniowe, nieliniowe, dyskretne, dynamiczne itp. Termin „programowanie” został wprowadzony ze względu na to, że nieznane zmienne będące w trakcie rozwiązywania problemu zazwyczaj determinują program lub plan działania jakiegoś podmiotu gospodarczego.

W klasycznej analizie matematycznej bada się ogólne sformułowanie problemu wyznaczania ekstremum warunkowego. Jednak w związku z rozwojem produkcji przemysłowej, transportu, rolnictwa i sektora bankowego tradycyjne wyniki analiz matematycznych nie wystarczyły. Potrzeby praktyki i rozwój technologii komputerowej spowodowały konieczność określenia optymalnych rozwiązań przy analizie złożonych systemów gospodarczych.

Głównym narzędziem rozwiązywania takich problemów jest modelowanie matematyczne. W takim przypadku najpierw buduje się prosty model, następnie przeprowadza się jego badania, dzięki którym można zrozumieć, które z właściwości całkujących obiektu nie są ujęte w schemacie formalnym, a następnie, komplikując model, zwiększa się jego adekwatność do rzeczywistości jest zapewnione. W wielu przypadkach pierwszym przybliżeniem do rzeczywistości jest model, w którym wszystkie zależności pomiędzy zmiennymi charakteryzującymi stan obiektu mają charakter liniowy. Praktyka pokazuje, że wystarczająca liczba procesów gospodarczych jest w pełni opisana modelami liniowymi. W konsekwencji programowanie liniowe jako narzędzie pozwalające znaleźć ekstremum warunkowe na danym zbiorze równania liniowe i nierówności, odgrywa ważną rolę w analizie tych procesów.

Programowanie liniowe zyskało szeroki rozwój ze względu na fakt, że ustalono, że wiele problemów planowania i sterowania można sformułować w postaci problemów programowania liniowego, do rozwiązania których istnieją skuteczne metody. Według ekspertów około 80–85% wszystkich rozwiązywanych w praktyce problemów optymalizacyjnych to problemy programowania liniowego.

Stworzony aparat matematyczny w połączeniu z programami komputerowymi dokonującymi pracochłonnych obliczeń umożliwia szerokie zastosowanie modeli programowania liniowego w nauce i praktyce ekonomicznej.

Definicja 1 9 . Programowanie liniowe (LP) to dziedzina programowania matematycznego, która jest gałęzią matematyki badającą metody znajdowania ekstremalnych (największych i najmniejszych) wartości funkcji liniowej skończonej liczby zmiennych, których niewiadome podlegają ograniczenia liniowe.

Ta funkcja liniowa nazywana jest funkcją celu, a ograniczenia, które reprezentują ilościowe relacje między zmiennymi wyrażającymi warunki i wymagania problemu ekonomicznego i są zapisane matematycznie w postaci równań lub nierówności, nazywane są systemem ograniczeń.

Szeroki zakres zagadnień planowania procesów gospodarczych sprowadza się do problemów programowania liniowego, w których stawiane jest zadanie znalezienia najlepszego (optymalnego) rozwiązania.

Ogólny problem programowania liniowego (GLP) polega na znalezieniu wartości ekstremalnej (maksimum lub minimum) funkcji liniowej, zwanej celem 10:

z N zmienne X 1 , X 2 , …, X N z nałożonymi ograniczeniami funkcjonalnymi:

(3.2)

i ograniczenia bezpośrednie (wymóg nieujemności zmiennych)

, (3.3)

Gdzie A ja , B I , C J– podane wartości stałe.

W systemie ograniczeń (3.2) znaki „mniejszy lub równy”, „równy” i „większy lub równy” mogą występować jednocześnie.

ZLP w bardziej zwięzłej formie ma postać:

z ograniczeniami:

;

wektor` X = (X 1 , X 2 , …, X N), których składniki spełniają funkcjonalne i bezpośrednie ograniczenia problemu, nazywane są plan(Lub akceptowalne rozwiązanie) ZŁ.

Powstają wszystkie możliwe rozwiązania domena problemy z programowaniem liniowym, lub obszar możliwych rozwiązań (ODR). Rozwiązanie wykonalne, które zapewnia maksimum lub minimum funkcji celu F(`X), nazywany jest optymalnym planem problemu i jest oznaczony F(`X * ), Gdzie ` X * =(X 1 * , X 2 * , …, X N * ).

Inna forma nagrywania PPP:

Gdzie F(`X * ) to wartość maksymalna (minimalna). F(Z, X), przejęła wszystkie rozwiązania zawarte w zestawie możliwe rozwiązania X .

Definicja 2 11 . Matematyczny wyraz funkcji celu i jej ograniczeń nazywany jest matematycznym modelem problemu ekonomicznego.

Aby skompilować model matematyczny, potrzebujesz:

1) zidentyfikować zmienne;

2) stworzyć funkcję celu w oparciu o cel problemu;

3) spisać system ograniczeń, biorąc pod uwagę wskaźniki zawarte w opisie problemu i ich wzorce ilościowe.

Programowanie liniowe uważane jest za rewolucyjne osiągnięcie, które dało człowiekowi możliwość formułowania ogólnych celów i znajdowania optymalnych rozwiązań dla szerokiej klasy za pomocą metody simplex problemy praktyczne podejmowanie decyzji o dużej złożoności.

Programowanie liniowe– dyscyplina matematyczna zajmująca się teorią i metodami rozwiązywania problemów o ekstremach funkcji liniowych na zbiorach N-wymiarowa przestrzeń wektorowa definiowana przez układy równań liniowych i nierówności.

Można tak powiedzieć Programowanie liniowe ma zastosowanie do rozwiązywania modeli matematycznych procesów i systemów, które można oprzeć na hipotezie liniowej reprezentacji świata rzeczywistego.

Problem programowania liniowego(LP), polega na znalezieniu minimum (lub maksimum) funkcji liniowej przy ograniczeniach liniowych.

Programowanie liniowe służy do rozwiązywania następujących problemów ekonomicznych:

1. Problem zarządzania i planowania produkcji.

2. Problemy określenia optymalnego rozmieszczenia sprzętu statki morskie, w warsztatach.

3. Problem ustalenia optymalnego planu transportu ładunku (problem transportu).

4. Problem optymalnego rozmieszczenia kadr.

5. Problemy dotyczące mieszanek, diety (planowania składu produktu) itp.

3. MODEL PROGRAMOWANIA LINIOWEGO I JEGO REPREZENTACJA W TABELACH ELEKTRONICZNYCH MS Excel.

Tradycyjnie nauka o zarządzaniu odnosi się do budowy szczegółowych modeli, w wyniku analizy których podejmowane są decyzje zarządcze. Obecnie do analizy są miliony menedżerów zadania biznesowe używane są arkusze kalkulacyjne. Nowoczesne arkusze kalkulacyjne zawierają wiele zaawansowanych narzędzi, których można używać do dokładniejszej analizy modeli, co skutkuje bardziej zrównoważonymi i bliższymi dopasowaniu modelami. optymalne rozwiązania. Biorąc pod uwagę coraz szersze zastosowanie arkusze kalkulacyjne W procesie zarządzania przyszli specjaliści muszą posiadać profesjonalną umiejętność opracowywania modeli - jak „zaplanować” pusty arkusz tak, aby uzyskać użyteczny i praktyczny model sytuacji biznesowej, bez zagłębiania się w zawiłości algorytmiczne i matematyczne obliczeń.

Główne kroki tworzenia liniowego modelu programowania w programie Excel:

1. Pisanie i testowanie symbolicznego modelu programowania liniowego. Model zapisywany jest na papierze w formie matematycznej.

2. Tworzenie i debugowanie model tabelaryczny Programowanie liniowe. Na podstawie symbolicznego modelu produktu leczniczego tworzona jest jego reprezentacja w programie Excel .

3. Próba optymalizacji modelu z wykorzystaniem dodatku SOLUTION SEARCH.

4. KORZYSTANIE Z DODATKU POSZUKIWANIE ROZWIĄZANIA.

Korzystając z arkuszy kalkulacyjnych, możesz symulować rzeczywiste sytuacje i oceniać wyniki. Inaczej mówiąc, za pomocą arkuszy kalkulacyjnych można analizować wyniki działalności i przewidywać przyszłe perspektywy przedsiębiorstwa. Te zadania w środowisku MS Excel umożliwia rozwiązywanie za pomocą dodatku Search for Solution.

Znalezienie rozwiązania – Jest to dodatek przeznaczony do optymalizacji modeli w obecności ograniczeń. Składa się z dwóch komponenty oprogramowania: programy napisane w Język wizualny Podstawowy, który tłumaczy informacje przedstawione w piśmie roboczym do reprezentacji wewnętrznej, z której korzysta inny program. Drugi program znajduje się w pamięci komputera jako osobny plik moduł oprogramowania. Dokonuje optymalizacji i zwraca znalezione rozwiązanie do pierwszego programu, który wznawia dane w arkuszu. Możesz go użyć do znalezienia optymalna wartość formuła przechowywana w komórce docelowej. Ta procedura działa na grupie komórek, które są bezpośrednio powiązane z formułą w komórce docelowej. Aby uzyskać wynik formuły w komórce docelowej, procedura zmienia wartość w komórkach mających wpływ na wyszukiwanie. Aby zredukować wiele wartości używanych w modelu problemu, stosuje się ograniczenie. Ograniczenia te mogą zawierać odniesienie do innych komórek mających wpływ na wyszukiwanie.

Algorytm ogólny praca z dodatkiem Znalezienie rozwiązania.

W menu Praca wybierz drużynę Znalezienie rozwiązania.
W polu Ustawia komórkę docelową Wprowadź adres komórki zawierającej formułę optymalizującą model.
Aby zmaksymalizować wartość komórki docelowej poprzez zmianę wartości wpływających komórek, ustaw przełącznik na Maksymalna wartość . Aby zminimalizować wartość komórki docelowej poprzez zmianę wartości komórek wpływających, ustaw przełącznik na Minimalna wartość . Aby komórka docelowa uzyskała wartość konkretny numer, ustaw przełącznik w pozycji Oznaczający i wprowadź odpowiedni numer.
W polu Zmiana komórek Wpisz adresy komórek, które zmieniają swoje wartości, oddzielając je przecinkami. Modyfikowane komórki muszą być bezpośrednio lub pośrednio powiązane z komórką docelową. Dozwolona jest instalacja do 200 zmienne komórki.
W polu Ograniczenia wprowadź wszystkie ograniczenia, które są nałożone na poszukiwanie rozwiązania.
Naciśnij przycisk Wykonać.
Aby zapisać znalezione rozwiązanie, wybierz przełącznik w oknie dialogowym Wyniki wyszukiwania rozwiązań na pozycję Zapisz znalezione rozwiązanie. Aby wznowić wprowadzanie danych, ustaw przełącznik w pozycji Przywróć oryginalne wartości.
Aby przerwać poszukiwanie rozwiązania należy nacisnąć klawisz Ess. MS Excel przeliczy arkusz biorąc pod uwagę znalezione wartości komórek, które mają wpływ na wynik.

Algorytm robotyczny z nadbudovą Znalezienie rozwiązania.

5. ROZWIĄZANIE PROBLEMU PROGRAMOWANIA LINIOWEGO PRZY UŻYCIU PROGRAMU MS EXCEL.

Przykład. Cukiernia produkująca trzy rodzaje karmelu A, B, C wykorzystuje trzy główne rodzaje surowców: cukier, melasę i przecier owocowy. Standardowe zużycie cukru do produkcji 1 kg karmelu każdego rodzaju wynosi odpowiednio: 0,8 kg; 0,5kg; 0,6kg; melasa – 04kg; 0,4kg; 0,3kg; przecier owocowy – 0kg; 0,1kg; 0,1 kg. Słodycze można produkować w dowolnych ilościach (sprzedaż gwarantowana), ale podaż surowców jest ograniczona: zapasy cukru – 80 kg, melasa – 60 kg, przecier owocowy – 12 kg. Zysk ze sprzedaży 1 kg karmelu A wynosi 10 UAH, typ W – 11 UAH, typ Z – 12 UAH.

Tabela 1

Ustal plan produkcji karmelu, który zapewnia maksymalny zysk z działalności cukierni.

15. Metody analityczne. Metody programowania liniowego.

15.1. Metody analityczne

Przez całą swoją ewolucję człowiek dokonując pewnych działań, starał się zachowywać w taki sposób, aby wynik osiągnięty w wyniku jakiegoś działania okazał się w pewnym sensie najlepszy. Przechodząc z jednego punktu do drugiego, starał się znaleźć najkrótszą możliwą ścieżkę. Budując mieszkanie, szukał geometrii, która zapewniłaby akceptowalne warunki mieszkaniowe przy jak najmniejszym zużyciu paliwa. Budując statki, starał się nadać im kształt, w którym woda stawiałaby najmniejszy opór. Listę podobnych przykładów można łatwo kontynuować.

Zwykle nazywane są najlepszymi rozwiązaniami problemów w pewnym sensie optymalny. Obecnie żaden problem nie może zostać rozwiązany bez zastosowania zasad optymalizacji. złożony problem. Podczas ustawiania i rozwiązywania problemów optymalizacyjnych pojawiają się dwa pytania: co i jak optymalizować?

Odpowiedź na pierwsze pytanie uzyskuje się w wyniku dogłębnego zbadania problemu, który ma zostać rozwiązany. Identyfikuje się parametr określający stopień doskonałości rozwiązania powstałego problemu. Ten parametr jest zwykle nazywany funkcja docelowa Lub kryterium jakości. Następnie ustalany jest zbiór wielkości wyznaczających funkcję celu. Na koniec sformułowane są wszystkie ograniczenia, które należy wziąć pod uwagę przy rozwiązywaniu problemu. Następnie konstruowany jest model matematyczny, który polega na ustaleniu zależności analitycznej funkcji celu od wszystkich argumentów i analitycznym sformułowaniu ograniczeń związanych z problemem. Następnie zaczynamy szukać odpowiedzi na drugie pytanie.

Niech więc w wyniku sformalizowania zastosowanego problemu zostanie ustalone, że funkcja celu to , gdzie zbiór X jest uogólnieniem ograniczeń, nazywa się go zbiorem możliwych rozwiązań. Istotą problemu optymalizacyjnego jest poszukiwanie takiego rozwiązania na zbiorze X – zbiorze rozwiązań dopuszczalnych
, przy którym funkcja celu F osiąga wartość minimalną lub maksymalną.

Integralną częścią metod optymalizacji jest programowanie liniowe.

15.2. Podstawowe pojęcia programowania liniowego

Pierwsza wzmianka (1938) o metodach matematycznych w efektywnym zarządzaniu produkcją należy do radzieckiego matematyka L. V. Kantorowicza. Rok później, w 1939 r., L. V. Kantorowicz opublikował pracę „Matematyczne metody organizacji i planowania produkcji” i praktycznie zastosował uzyskane wyniki. Termin „programowanie liniowe” wprowadzili amerykańscy matematycy J. Danzig i T. Koopmans pod koniec lat 40. XX wieku. J. Dantzig opracował aparat matematyczny metody simpleksowej do rozwiązywania problemów programowania liniowego (1951). Metoda Simplex służy do rozwiązywania szerokiego zakresu problemów programowania liniowego i nadal jest jedną z głównych metod.

Programowanie liniowe to dziedzina matematyki skupiająca się na znajdowaniu ekstremum (maksimum lub minimum) w problemach opisanych za pomocą równań liniowych. Ponadto równania liniowe opisują zarówno samą funkcję celu, jak i parametry wejściowe (zmienne) warunków ograniczeń Parametry wejściowe. Warunkiem koniecznym problemów programowania liniowego jest obowiązkowe występowanie ograniczeń zasobów (surowców, materiałów, finansów, popytu na wytwarzane produkty itp.). Do innych ważny warunek rozwiązaniem problemu jest wybór kryterium zatrzymania algorytmu, czyli funkcja celu musi być w pewnym sensie optymalna. Optymalizację funkcji celu należy wyrazić ilościowo. Jeśli funkcję celu reprezentuje jedno lub dwa równania, w praktyce takie problemy można rozwiązać dość łatwo. Kryterium zatrzymania algorytmu (lub kryterium optymalności) musi spełniać następujące wymagania:

być jedyną osobą odpowiedzialną za dane zadanie;

mierzone w jednostkach ilości;

liniowo zależą od parametrów wejściowych.

Na podstawie powyższego możemy sformułować problem programowania liniowego w ogólnej postaci:

znajdź ekstremum funkcji celu

pod ograniczeniami w postaci równości:

(2.2)

pod ograniczeniami w postaci nierówności:

(2.3)

oraz warunki nieujemności parametrów wejściowych:

W skrócie problem programowania liniowego można zapisać w następujący sposób:

(2.5)

jeśli się uwzględni

Gdzie
- zmienne wejściowe;

Liczby są dodatnie, ujemne i równe zero.

W postaci macierzowej problem ten można zapisać w następujący sposób:

Problemy programowania liniowego można rozwiązywać analitycznie i graficznie.

15.3. Problem kanonicznego programowania liniowego

, i=1,…,m,

, j=1,…,n.

Główne metody obliczeniowe rozwiązywania problemów programowania liniowego zostały opracowane specjalnie dla problemu kanonicznego.

15.4. Ogólny problem programowania liniowego

Należy maksymalizować (minimalizować) funkcję liniową N zmienne.

pod ograniczeniami

, I=1,…, k,

, I=1+ k,…, M,

, …,

Tutaj k≤ M, R≤ N. Problem standardowy uzyskuje się jako szczególny przypadek ogólnego k= M, R= N; kanoniczny – godz k=0, R= N.

Przykład.

Fabryka cukiernicza produkuje kilka rodzajów słodyczy. Nazwijmy je „A”, „B” i „C”. Wiadomo, że sprzedaż dziesięciu kilogramów słodyczy „A” daje zysk w wysokości 90 rubli, „B” - 100 rubli, a „C” - 160 rubli. Cukierki można wyprodukować w dowolnej ilości (sprzedaż jest gwarantowana), ale zapasy surowców są ograniczone. Należy określić, jakiego rodzaju słodycze i ile kilkudziesięciu kilogramów należy wyprodukować, aby zmaksymalizować łączny zysk ze sprzedaży. Wskaźniki zużycia surowców do produkcji 10 kg słodyczy każdego rodzaju podano w tabeli 1.

Tabela 1. Wskaźniki zużycia surowca

do produkcji

Ekonomiczne i matematyczne sformułowanie problemu ma postać

Znajdź takie wartości zmiennych X=(x1, x2, x3), Do

funkcja celu

zgodnie z warunkami-ograniczeniami: