Objectieve functie
Een functie die het doel (de variabele die wordt geoptimaliseerd) relateert aan de gecontroleerde variabelen in een optimalisatieprobleem.
Het is belangrijk dat het criterium altijd van buitenaf wordt geïntroduceerd, en pas daarna wordt gezocht naar een beslisregel die de objectieve functie minimaliseert of maximaliseert.
zie ook
- Burak Ya. I., Ogirko I. V. Optimale verwarming van een cilindrische schaal met temperatuurafhankelijke materiaaleigenschappen // Mat. methoden en fysisch-mechanisch velden. - 1977. - Uitgave. 5. - Blz. 26-30
Wikimedia Stichting. 2010.
- Centraal Onderzoeksinstituut voor Robotica en Technische Cybernetica
- 1885 in het theater
Kijk wat "Doelfunctie" is in andere woordenboeken:
objectieve functie- - [Ya.N.Luginsky, M.S.Fezi Zhilinskaya, Yu.S.Kabirov. Engels-Russisch woordenboek voor elektrotechniek en energietechniek, Moskou, 1999] objectieve functie Bij extreme problemen: een functie waarvan het minimum of maximum moet worden gevonden. Dit… …
Objectieve functie- bij extreme problemen een functie waarvan het minimum of maximum moet worden gevonden. Dit is het sleutelconcept optimale programmering. Nadat ik het extremum van C.f. en daarom, na het bepalen van de waarden van de gecontroleerde variabelen die ernaartoe gaan... ...
objectieve functie- 3.1.8 Bedrijfsfunctie: Een reeks processen die ervoor zorgen dat een specifiek bedrijfsdoel wordt bereikt. Bron: R 50.1.041 2002: Infor... Woordenboek-naslagwerk met termen van normatieve en technische documentatie
objectieve functie- tikslo funkcija statusas T sritis automatika atitikmenys: engl. objectieve functie vok. Zielfunktion, f rus. doelfunctie, f; objectieve functie, f pranc. functie van de cible, f … Automatikos terminų žodynas
Objectieve functie- een functie waarvan de extreme waarde wordt gezocht op een toelaatbare set in wiskundige programmeerproblemen (zie Wiskundig programmeren) ... Grote Sovjet-encyclopedie
DOELFUNCTIE- doelfunctie is de naam van de functie die wordt geoptimaliseerd bij wiskundige programmeerproblemen... Wiskundige encyclopedie
Objectieve functie- (een conventionele naam die relatief correct alleen kan worden toegepast op systemen die door de mens voor een specifiek doel zijn gemaakt), bestaat niet in de objectieve wereld, daar vindt een systeemvormende factor plaats... Theoretische aspecten en fundamenten milieuprobleem: tolk van woorden en ideomatische uitdrukkingen
Consumptie objectieve functie- 1. Deze term, evenals een aantal gelijkwaardige of bijna gelijkwaardige termen (levensstandaardfunctie, welvaartsfunctie, sociale nutsfunctie, consumptiefunctie, etc.) duiden in ... ... Economisch-wiskundig woordenboek
consumptie objectieve functie- 1. Deze term, evenals verschillende gelijkwaardige of bijna gelijkwaardige termen (levensstandaardfunctie, welvaartsfunctie, sociale nutsfunctie, consumptiefunctie, enz.) duiden de doelfunctie aan in theoretische studies... ... Handleiding voor technische vertalers
doelfunctie van een geautomatiseerd medisch systeem- doelfunctie van de AWS Reeks acties van de geautomatiseerde medisch systeem, waardoor de effectieve implementatie van een bepaald medisch programma wordt gegarandeerd. [GOST 27878 88] Onderwerpen van medische systemen en complexen Algemene voorwaarden van systemen en... ... Handleiding voor technische vertalers
Boeken
- Een benadering voor het organiseren van een adaptief leermanagementsysteem gebaseerd op het gebruik van informatietechnologie, A. V. Anastasin. Kwestie van gebruik informatie technologieën V onderwijskundig proces hoger onderwijsinstellingen wordt al lange tijd voortdurend besproken op verschillende niveaus. Dit komt door de snelle...
Doelfunctie. Als de inkomsten uit de verkoop van één tafel gelijk zijn aan MET 1 roebel, daarna uit de verkoop van tafels in het volume X 1 stuk maandinkomen
zal zijn MET 1 X 1 roebel. Op dezelfde manier zal het maandelijkse inkomen uit de verkoop van kasten zijn MET 2 X 2 roebel. Geeft het totale inkomen (in roebels) aan via Z, kunnen we de volgende wiskundige formulering van de doelfunctie geven: bepaal de (toelaatbare) waarden X 1, en X 2 het maximaliseren van het totale inkomen Z = MET 1 X 1 + MET 2 X 2 =
| 2 |
| ∑ |
| j=1 |
C J X J.
Beperkingen. Bij het oplossen van het onderhavige probleem moet rekening worden gehouden met beperkingen op het verbruik van hulpbronnen. Het hout wordt gebruikt om tafels en kasten van te maken. Gaat naar één tafel A 11 (m 3) hout, daarna voor tafels in hoeveelheid X 1 stuk vereist A 11 X 1 (m 3) hout. Om kasten te maken in een hoeveelheid van x 2 stuks heb je nodig A 12 X 2 (m 3) hout. Totaal benodigd hout A 11 X 1 + A 12 X 2 (m3). Het verbruik ervan mag de hoeveelheid niet overschrijden B 1 (m3). Vervolgens schrijven we de beperking op hout als de ongelijkheid
Voor variabele taken X 1 en X 2. De voorwaarden van niet-negativiteit en ondeelbaarheid moeten worden opgelegd, d.w.z. laten we beperkingen invoeren
X 1 ≥ 0, X 2 ≥ 0,
Waar X 1 , X 2 zijn gehele getallen.
Dus, wiskundig model de taken kunnen als volgt worden geschreven: bepaal de maandelijkse productievolumes van tafels X 1 en kasten X 2 waarop dit wordt bereikt
Opgemerkt moet worden dat dit vanuit formeel oogpunt is dit model is lineair omdat alle functies die erin zijn opgenomen (beperkingen en objectieve functie) lineair zijn. Maar de lineaire aard van het geconstrueerde model zou de aanwezigheid van twee eigenschappen moeten veronderstellen: proportionaliteit en additiviteit. Proportionaliteit veronderstelt een direct proportionele relatie tussen de variabele en de objectieve functie en het consumptievolume beperkte middelen. Er zal bijvoorbeeld geen sprake zijn van directe evenredigheid als we het fabrieksinkomen afhankelijk maken van de omvang van de verkochte partij producten. Additiviteit wordt waargenomen in het feit dat de inkomenscomponenten in de objectieve functie onafhankelijk zijn, het totale inkomen is gelijk aan het inkomensbedrag. Als een fabriek twee specifieke soorten producten produceert, waarvan de verkoopstijging bij het ene een negatief effect heeft op het verkoopvolume van het andere, dan heeft een dergelijk model niet de eigenschap van additiviteit.
Om de variabelen van het beschouwde model te bepalen, kunnen lineaire programmeermethoden worden gebruikt. Basismethode LP is een simplexmethode ontwikkeld door G. Danzig. Het LP-probleem kan ook grafisch worden opgelost. Een grafische weergave van de oplossing voor het probleem zal het idee van de simplexmethode helpen begrijpen. Laten we het probleem specificeren door de initiële gegevens in een tabel weer te geven. 3.1 (de gegevens worden voorwaardelijk verstrekt).
Tabel 3.1
| Bronnen | Het verbruik van hulpbronnen per productie-eenheid | Grondstoffenvoorraad |
|
| Tafel | Kast |
||
| Timmerhout (m 3) | 0,06 | 0,07 | 42 |
| Schroeven (kg) | 0,04 | 0,085 | 34 |
| Verf (kg) | 0,035 | 0,12 | 42 |
| Eenheidsprijs (RUB) | 500 | 750 | - |
Laten we het model van het probleem opschrijven met de gegeven gegevens:
In wat volgt zullen we geen rekening houden met beperking (3.5) en een oplossing voor het probleem verkrijgen door de gevonden variabelen van probleem (3.0-3.4) af te ronden.
44 :: 45 :: 46 :: 47 :: Inhoud
47 :: 48 :: 49 :: 50 :: 51 :: Inhoud
3.2.2. Grafische methode PPP-besluiten
Om de oplossing te bepalen ZLP met twee variabelen laten we het doen de volgende acties.
1. Laten we een reeks haalbare oplossingen voor het Ω-probleem construeren. Deze setΩ wordt gevormd als resultaat van de kruising van halve vlakken (beperkingen) (3.1-3.4). In afb. 3.2 De reeks haalbare oplossingen wordt weergegeven als een vijfhoek. De gebieden waarin aan de overeenkomstige beperkingen in de vorm van ongelijkheden wordt voldaan, worden aangegeven door pijlen die zijn gericht op de toegestane waarden van de variabelen. Het resulterende veelvlak Ω wordt een simplex genoemd. Vandaar de naam van de methode om de optimale oplossing te vinden.
2. Laten we een gradiëntvector C construeren, samengesteld uit afgeleiden van de objectieve functie met betrekking tot de probleemvariabelen, die de richting van de toename van de objectieve functie met betrekking tot deze variabelen aangeeft. C = ( MET 1 , MET 2) = (500,750). Het begin van deze vector ligt op het punt met coördinaten (0, 0), en het einde op het punt (500, 750). Een reeks evenwijdige stippellijnen loodrecht op de gradiëntvector vormt een reeks doelen
Functies voor willekeurig gekozen waarden Z. Bij Z= 0 de rechte lijn (objectieve functie) gaat door het punt (0, 0) en de objectieve functie Z neemt de minimumwaarde aan.
Rijst. 3 2 Geometrische interpretatie van de ZLP
3. Laten we de rechte lijn die het inkomen karakteriseert, verplaatsen Z, in de richting van de vectorgradiënt (voor het probleem max Z) totdat deze het gebied binnengaat onaanvaardbare beslissingen. In afb. 3.2 is het duidelijk dat de optimale oplossing overeenkomt met punt X* = ( X 1 *, X 2 *). Aangezien punt X* het snijpunt is van de lijnen (3.1) en (3.2), de waarden X 1* en X 2 * worden bepaald door een stelsel van twee vergelijkingen op te lossen:
Oplossing genoemd systeem vergelijkingen geeft het resultaat X 1 * = 517,4 en X 2 * =156,5. De resulterende oplossing betekent dat het maandelijkse productievolume van tafels 517 stuks moet zijn, en kasten - 156 stuks. Het inkomen dat in dit geval wordt ontvangen, is:
Z= 517 · 500 + 156 · 750 = 375.500 roebel
PLP met veel variabelen kan grafisch worden opgelost als in de canonieke notatie het aantal onbekenden N en het aantal lineair onafhankelijke vergelijkingen M gerelateerd door de relatie n-m≤ 2. Laten we de canonieke vorm van de hierboven beschouwde ZLP schrijven. Om dit te doen, introduceren we nieuwe variabelen X 3 , X 4 en X 5 .
Voor een gegeven PPP: het aantal variabelen N= 5, en het aantal lineair onafhankelijke vergelijkingen M= 3. Deze en andere PPP's in canonieke vorm grafisch op te lossen als n-m ≤ 2.
Laten we er een kiezen M onbekenden en druk ze allemaal uit via de overige ( n-m) variabelen. In ons geval is het handig om variabelen te nemen X 3 , X 4 en X 5 en druk ze uit X 1 en X 2 .
Rekening houdend met de niet-negativiteit van alle variabelen, inclusief X 3 ≥ 0, X 4 ≥ 0 en X 5 ≥ 0, evenals de afhankelijkheid van laatstgenoemde van twee variabelen X 1 en X 2 kunt u de oplossing voor het uitgebreide probleem met projectie op variabelen grafisch weergeven X 1 en X 2. Halfvlak X 3 ≥ 0 (zie figuur 3.2) valt samen met beperking (3.1), halfvlak X 4 ≥ 0 - met beperking (3.2) en het halfvlak X 5 ≥ 0 - met beperking (3.3). Optimaal punt in coördinaten X 1 en X 2 wordt gevormd als gevolg van het snijpunt van halve vlakken X 3 en X 4: X 1 * = 517,4; X 2 = 156,5. Dienovereenkomstig de waarden van de variabelen X 3Ä X 4 zal nul zijn: X 3 * =0; X 4 * = 0. Dan volgt uit (3.9) dat X 5 * = 42 - 0,035 517,4 - 0,12 156,5 = 5,1. De oplossing voor de ZLP (3,6-3,10) zal de vector X* = (517,4; 156,5; 0; 0; 5,1) zijn.
De geometrische weergave van de ZLP weerspiegelt het volgende:
1) de reeks toelaatbare oplossingen Ω is convex;
2) de optimale oplossing bestaat niet als de verzameling Ω leeg of onbeperkt is in de richting van het verplaatsen van de familie van hypervlakken op het niveau van het doel van het zoeken naar het extremum;
3) de oplossing bevindt zich op een van de hoekpunten (hoekpunten) van de reeks toelaatbare oplossingen Ω, de zogenaamde basisoplossingen;
4) voor canonieke ZLP basisoplossingen worden gekenmerkt door de vector X - (X 1 , X 2 ,..., X n), waarin de waarden M variabelen zijn niet nul, waarbij M- het aantal lineair onafhankelijke vergelijkingen van het probleem (het aantal basisvariabelen van het hoekpunt van de verzameling Ω).
Voor de optimale oplossing X* van het beschouwde voorbeeld waren de basisvariabelen de variabelen X 1 , X 2 en X 5. Overige variabelen ( n - m) worden niet-basis of gratis genoemd. Hun waarden op het hoekpunt zijn nul.
Houd er rekening mee dat elke basisvariabele kan worden uitgedrukt in termen van niet-basisvariabelen, en dat de basisvariabele in model (3.6)-(3.10) één keer wordt geschreven met een coëfficiënt van één.
Het bovenstaande probleem van het gebruik van hulpbronnen heeft een zeer eenvoudige formulering en structuur. Het kan eisen omvatten voor het verantwoorden van de vrijgave van producten in een bepaalde verhouding, het rekening houden met hun mogelijke vrijgave met behulp van verschillende technologieën, het rekening houden met de belasting van apparatuur, en andere. Al deze situaties worden vrij goed beschreven door lineaire programmeermodellen.
47 :: 48 :: 49 :: 50 :: 51 :: Inhoud
50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Inhoud
3.2.3. Algebraïsche (simplex) methode voor het oplossen van ZLP
De hierboven besproken grafische methode voor het oplossen van het LP-probleem stelt ons in staat het idee van optimalisatiemethoden te begrijpen, inclusief lineaire programmeermethoden. De essentie van alle methoden van wiskundig programmeren is dat in plaats van een ‘blinde’ opsomming van planopties, een selectieve, georganiseerde opsomming wordt uitgevoerd, gericht op de snelste en in sommige gevallen consistente verbetering van de oplossing.
De extreme oplossing wordt niet bereikt binnen het domein van haalbare oplossingen Ω, maar op de grens ervan (zie figuur 3.2); om nog preciezer te zijn, op een van de hoekpunten van de hoekpunten van een veelhoek die is gevormd als resultaat van het snijpunt van lijnen die aan bepaalde beperkingen zijn gekoppeld, of op een segment tussen twee aangrenzende hoekpunten. Omdat het uiterste noodzakelijkerwijs wordt bereikt op een of twee hoekpunten van toelaatbare plannen, hoeft u alleen maar de waarden van de doelfuncties op alle hoekpunten te berekenen (in ons voorbeeld zijn dat er vijf) en
kies degene met de extreme waarde. Met een groot aantal variabelen en een groot aantal beperkingen wordt het aantal hoekpunten van het veelvlak zo groot dat het berekenen van de waarde van de doelfunctie in elk van hen, het onthouden van deze waarden en het vergelijken ervan met elkaar zeer lastig is. zelfs voor krachtige computers problematisch. Daarom moeten we op zoek naar een andere oplossing.
U kunt het optimale punt opeenvolgend benaderen, waarbij u bijvoorbeeld van het ene hoekpunt naar het aangrenzende punt gaat, telkens vanaf het initiële (referentie)punt X 0 ( X 1 = 0, X 2 = 0) opeenvolgend naar de naburige die X* dichterbij en sneller nadert. De door R. Dantzig voorgestelde simplexmethode maakt de opsomming van oplossingspunten volgens dit schema mogelijk. Voor ons voorbeeld gaan we bij de eerste stap (iteratie) vanaf het referentiepunt X 0 volgens de simplexmethode naar punt X 1 met coördinaten (700, 0) en bij de tweede stap gaan we naar punt X*. Langs het andere pad kan punt X* in slechts drie stappen worden bereikt. Vanuit computationeel oogpunt wordt de simplexmethode geïmplementeerd via de zogenaamde simplextabellen, die voor elk hoekpunt worden berekend, beginnend bij het referentiepunt. Met simplextabellen kunt u de optimaliteit van de genomen beslissing bepalen, de waarden van de variabelen bepalen, resourceparameters (beperkingen) evalueren op hun schaarste, en in het geval van een niet-optimale beslissing aangeven hoe u naar de volgende stap moet gaan punt (de volgende tabel). Vanwege verschillende kenmerken en formuleringen van problemen heeft de LP-methode verschillende aanpassingen: direct, duaal, tweetraps.
Om een van de simplex-methoden te implementeren, is dit noodzakelijk het opstellen van het initiële referentieplan .
Laat het systeem van beperkingen er als volgt uitzien:
Door extra variabelen toe te voegen aan de linkerkant van de ongelijkheid Xn+ik ≥ 0, i = 1, M, verkrijgen we een canoniek (uitgebreid) probleem, strategisch gelijkwaardig aan het oorspronkelijke, met een systeem van beperkingen:
Het initiële referentieplan zal dan de vector zijn
Wat voldoet aan de toelaatbaarheid van de oplossing (het is fundamenteel, aangezien het aantal niet-nul elementen gelijk is aan M, en ondersteunend, omdat Alle XJ≥ 0). Laat het systeem van beperkingen er als volgt uitzien:
Extra variabelen aftrekken van de linkerkant van de ongelijkheid Xn+ik ≥ 0, i = 1, M krijgen we een uitgebreid probleem, strategisch gelijkwaardig aan het oorspronkelijke, met een systeem van beperkingen:
Er zijn nu echter extra variabelen opgenomen linkerkant beperkingen met coëfficiënten gelijk aan min één. Daarom de planning
voldoet niet aan de voorwaarden voor de ontvankelijkheid van een oplossing (het is fundamenteel, maar geen referentie).
In zowel het eerste als het tweede geval worden bij het toevoegen van extra variabelen (ze worden ook basisvariabelen) aan het systeem van beperkingen dezelfde variabelen geïntroduceerd in de objectieve functie met coëfficiënten gelijk aan nul: Cn+ik ≥ 0, i = 1, M, d.w.z. in de objectieve functie zijn er nulcoëfficiënten voor basisvariabelen en coëfficiënten voor niet-basisvariabelen MET J, J = 1, N. Laat de objectieve functie naar een minimum neigen. Vervolgens kan de waarde van de doelfunctie worden verminderd als die variabele in de basis wordt geïntroduceerd X j , waarbij de coëfficiënt MET j van de doelfunctie heeft een minteken. En als alle coëfficiënten in de objectieve functie een plusteken hebben, is het niet mogelijk om de waarde ervan te verlagen. Daarom dienen de coëfficiënten (schattingen) in de objectieve functie voor niet-basisvariabelen als een teken van de optimaliteit van de ZLP-oplossing.
Afhankelijk van de vervulling van de voorwaarden van optimaliteit en ontvankelijkheid, wordt een of ander schema voor het oplossen van de PLP gebruikt.
Methoden voor het oplossen van problemen zijn onderverdeeld in twee groepen:
1) methoden voor opeenvolgende verbetering van de oplossing. Ze zijn gebaseerd op de beweging van het oorspronkelijke punt (elke toelaatbare, maar niet-optimale oplossing voor het probleem in canonieke vorm) naar de optimale.
Wijs een eindig aantal stappen aan (iteraties). Deze groep omvat de directe simplex-methode, de potentiële methode en andere;
2) methoden voor de sequentiële reductie van residuen. Ze zijn gebaseerd op de beweging van het initiële conditioneel optimale punt, dat buiten het gebied van toelaatbare oplossingen ligt, maar voldoet aan het criterium van optimaliteit van de oplossing, naar het optimale en toelaatbare punt. Deze groep omvat de dual simplex-methode, Hongaarse methode en anderen. Alle algoritmen voor het oplossen van het probleem zijn gebaseerd op de canonieke vorm van het probleem. Daarom zal het aantal vereiste variabelen in het canonieke probleem groter zijn dan in het oorspronkelijke probleem.
Bij het kiezen van een algoritme voor het oplossen van het LP-probleem gaan we uit van de volgende gegevens. Laat de ZLP worden teruggebracht tot canonieke vorm, opgelost voor de minimale en vrije coëfficiënten Bi ≥ 0, i = 1, M. Als de objectieve functie van het probleem dan negatieve coëfficiënten heeft (er is niet voldaan aan de voorwaarde voor de optimale oplossing van het probleem) en het oorspronkelijke plan van het probleem geen negatieve waarden van de variabelen heeft (de voorwaarde voor de ontvankelijkheid van het oplossen van het probleem is voldaan), dan moet u om het voorgestelde probleem op te lossen het algoritme van de direct simplex-methode gebruiken (Tabel 3.2). De dual simplex-methode wordt gebruikt als aan de optimaliteitsvoorwaarde voor het oplossen van het probleem is voldaan, maar niet aan de ontvankelijkheidsvoorwaarde. De tweetraps simplex-methode wordt gebruikt als niet aan de voorwaarden voor zowel optimaliteit als haalbaarheid van het oplossen van het probleem is voldaan.
Tabel 3.2
Laat ons nadenken directe simplex-methode LP-problemen oplossen met behulp van het volgende voorbeeld.
Voorbeeld 3.1
Minimaliseer de functie Z = -X 1 - X 2 met beperkingen: 0,5 X 1 + X 2 ≤ 1;
2X 1 + X 2 ≤ 2;
X 1 , X 2 ≥ 0.
Een grafische weergave van het probleem (3.11-3.14) wordt getoond in Fig. 3.3.
Rijst. 3.3. Grafische weergave van het probleem (3.11) - (3.14)
Het initiële basisreferentiepunt van het probleem zal de vector X 0 = (0; 0; 1; 2) zijn. De waarde van de doelfunctie op dit punt Z(X0) = 0.
Laten we de variabele overbrengen naar de doelfunctie (3.11) Z voor het gelijkteken en deze opdracht Laten we het in de vorm van een tabel schrijven. 3.3, een simplextabel genoemd (nul-iteratie).
Tabel 3.3
Andere vormen van simplex-tabelnotatie worden in de literatuur beschreven. Met behulp van de simplextabel kun je altijd zien of de gevonden oplossing optimaal is. IN in dit geval oplossing X 1 = 0; X 2 = 0; X 3 = 1; X 4 = 2 is niet de beste, omdat een van de variabelen in de basis kan worden geïntroduceerd X 1 of X 2 (deze variabelen hebben coëfficiënten met een minteken Met 1 = -1 en Met 2 = - 1), waardoor de waarde van de doelfunctie afneemt. Vervolgens wordt in de basis een van de niet-basisvariabelen geïntroduceerd X 1 of X 2 (waardoor de waarde ervan toeneemt), moet de variabele worden afgeleid van de basis X 3 of X 4 (waardoor de waarde op nul komt). Bij de direct simplex-methode worden de volgende vragen achtereenvolgens behandeld:
overgang naar de nieuwe canonieke vorm van de ZLP (naar de volgende iteratie van de simplextabel).
. Als we een variabele in de basis opnemen X 1, dan betekent dit dat we de waarde ervan verhogen van nul naar bepaalde limieten. Tot wat? Laten we naar afb. 3.3. Extreme waarde voor een variabele X 1 zal één zijn, en de variabele (direct) X 4 in beperking (3.13) zal een waarde aannemen die gelijk is aan nul, dat wil zeggen dat hij de basis zal verlaten X 4 , en zijn plaats zal worden ingenomen door de variabele X 1. Uit vergelijking (3.12) bepalen we de waarde X 3 = 1 - 0,5 1 = 0,5. Bij de volgende iteratie (stap) zal de haalbare oplossing dus de vector X 1 = (1; 0; 0,5; 0) zijn. De waarde van de doelfunctie op dit punt Z(1) = -1.
Zonder toevlucht te nemen tot een grafische weergave van het probleem, het bepalen van de grenswaarde X l en variabele definitie X 4, dat uit de basis moet worden afgeleid, kan worden uitgevoerd op de volgende verdeling. Als je een variabele afleidt van de basis X 3, d.w.z. er moet zijn X 3 = 0, dan volgt uit (3.12). X ik = B 1 /een 1 S= 1/0,5 = 2. Als je een variabele afleidt uit de basis X 4, d.w.z. Doen X 4 = 0, dan vanaf (3.13) X ik = B 2 /een 2 S= 1/1 = 1. Het blijkt dat de waarde X l = 1 of X l = 2. Maar wanneer X l = 2 in variabele van vergelijking (3.13). X 4 = 1 - 2 - 0,5 · 0 = -1, wat in tegenspraak is met de voorwaarde voor de toelaatbaarheid van de oplossing (3.14). Daarom nemen we het op in de basis X l met de kleinste waarde, die wordt bepaald op basis van de tweede beperking. Deze beperking bevat de variabele die van de basis moet worden uitgesloten X 4. Over het algemeen de variabele XS, opgenomen in de basis, kan oplopen tot de waarde
Laat het maximale gehaald worden in de lijn R, d.w.z. XS = BR/Ars, dan wordt in deze regel de basisvariabele nul, d.w.z. is afgeleid van de basis. Snaar R genaamd leidende lijn en het element Ars - leidend element. Als er geen positieve in de leidende kolom staan Ais, dan betekent dit dat de ZLP geen regio heeft met haalbare oplossingen.
Overgang naar de nieuwe canonieke vorm van de ZLP . In tafel Figuur 3.4 toont de overgangen van de nul-iteratie naar daaropvolgende methoden voor het sequentieel elimineren van de nieuw geïntroduceerde basisvariabele uit niet-voorlopende rijen. Een nieuwe rij bij de volgende iteratie met een nieuw geïntroduceerde basisvariabele wordt verkregen door de elementen van de leidende rij te delen door het leidende element; ten opzichte van de resulterende rij wordt de nieuwe basisvariabele vervolgens uitgesloten van andere rijen. In tafel 3.4 bij iteratie 1’ worden de coëfficiënten voor de basisvariabelen aangegeven, waaronder de bijbehorende transitie wordt uitgevoerd. De belangrijkste elementen in de tabel zijn gemarkeerd met een asterisk.
Berekening van coëfficiënten bij de volgende iteratie kan worden gedaan volgens de vierhoeksregel.
Deze tabel bij iteratie 2 komt overeen met de optimale oplossing X* = X 2 = (2/3; 2/3; 0; 0).
Objectieve functiewaarde Z(X*) = -4/3.
Tabel 3.4
Laat ons nadenken dubbele simplex-methode het LP-probleem oplossen met behulp van het volgende voorbeeld.
Voorbeeld 3.2
Maximaliseer de functie Z = -X 1 - X 2 met beperkingen:
0,5X 1 + X 2 ≤ 1;
2X 1 + X 2 ≥ 2;
X 1 , X 2 ≥ 0.
In de canonieke vorm zal de ZLP de vorm aannemen
Een grafische weergave van het probleem wordt getoond in Fig. 3.4.
Rijst. 3.4. Grafische weergave van het probleem (3.15) - (3.18)
Laten we een simplextabel maken 3.5.
Tabel 3.5
Nullijn in de tabel. 3.5 geeft aan dat aan het criterium voor de optimale oplossing van het probleem is voldaan (er zijn geen negatieve coëfficiënten).
De initiële oplossing X 0 = (0; 0; 1; -2) is echter negatief.
Laten we proberen het probleem op te lossen (in tegenstelling tot directe simplex-methode) door opeenvolgende beweging van het aanvankelijke ongeldige punt X 0 naar X *, rekening houdend met de vragen:
zoeken naar een variabele die u van de basis wilt uitsluiten;
zoeken naar een variabele om in de basis op te nemen;
overgang naar nieuw formulier SLP (volgende iteratie van de oplossing).
Het zal zowel optimaal als acceptabel zijn. In ons voorbeeld sluiten we de variabele uit X 4 = -2.
Zoek naar een variabele die u in de basis wilt opnemen . Welke niet-basisvariabele moet in de basis worden opgenomen? X 1 of X 2? In principe kan iedereen in de basis worden opgenomen met als doel zich in de regio van haalbare oplossingen te begeven. Van grafische weergave probleem (zie figuur 3.4) is het duidelijk dat wanneer de variabele in de basis wordt opgenomen X 2 bevinden we ons onmiddellijk op het toelaatbare en optimale punt X*. Uit de literatuur blijkt dat je sneller tot de optimale oplossing kunt komen als je een variabele kiest die je in de basis opneemt XS zodanig dat voor haar de houding CS/|Ars| voor alle elementen Ars de leidende lijn zal minimaal zijn:
Als alle elementen Ar.j· ≥ 0, dan betekent dit dat het probleem geen haalbare oplossingen kent. In ons voorbeeld wordt de minimale verhouding (3,19) voor de variabele bereikt X 1 is gelijk aan 1/2. Laten we het probleem oplossen tabellarische methode(Tabel 3.6).
Tabel 3.6
Optimale oplossing: X* = (1; 0; 1/2; 0;); Z(X*) = -z" = -1.
Laten we aannemen dat we bij het oplossen van het vorige voorbeeld (zie Tabel 3.6) dit niet in de basis zouden opnemen X 1 en de variabele X 2, dan zouden we bij iteratie 1 de volgende tabel krijgen. 3.7.
Tabel 3.7
Nullijn in de tabel. 3.7 geeft aan dat niet aan het optimaliteitscriterium voor het oplossen van het probleem is voldaan en dat de tussenoplossing X 1 = (0; 2; -1; 0) onaanvaardbaar is. Verder kan het probleem worden opgelost met behulp van de tweetraps simplex-methode, de grote boete-methode en andere. Laat ons nadenken tweetraps simplexmethode .
1. We introduceren een extra variabele, waardoor deze fundamenteel wordt, in de vergelijkingen waarin niet aan de ontvankelijkheidsvoorwaarden is voldaan. In ons geval introduceren we de variabele X 5 in regel (1), waarbij u eerst de tekens verandert in de tegenovergestelde tekens (Tabel 3.8) en de kolom daaronder X 5:
3/2 X 1 - X 3 - X 4 + X 5 = 1.
2. We introduceren een nieuwe (fictieve) objectieve functie W als de som van nieuw geïntroduceerde aanvullende variabelen, uitgedrukt in niet-basisvariabelen. In ons geval W = X 5 = 1 - 3/2 X 1 + X 3 + X 4. We voegen extra regel (3) toe aan de tabel. 3.8 met dummy-objectieffunctie - W - 3/2 X 1 + X 3 + X 4 = -1.
3. We gebruiken de direct simplex-methode om het fictieve doel te minimaliseren W met herberekening van alle coëfficiënten. De eerste fase eindigt als het fictieve objectief functioneert W gaat naar nul W= 0, en daarom zijn er ook aanvullende variabelen bij nul waarden. Verder wordt geen rekening gehouden met de rij met de fictieve doelfunctie en kolommen met aanvullende variabelen. Als, als gevolg van het minimaliseren van het doel W we krijgen de optimale waarde W, verschillend van nul W≠ 0, dan betekent dit dat de oorspronkelijke ZLP geen toelaatbare oplossingen heeft.
We gebruiken de direct simplex-methode om de hoofdlijn te optimaliseren
objectieve functie Z. We nemen een variabele op in de basis X 3 in plaats van een variabele X 2. We herberekenen de coëfficiënten bij iteratie 3 en verkrijgen de optimale oplossing: X* = (1; 0; 1/2; 0;); Z(X*) = - z" = -1.
Tabel 3.8
50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Inhoud
61 :: 62 :: 63 :: 64 :: 65 :: 66 :: 67 :: 68 :: 69 :: 70 :: Inhoud
3.2.4. Analyse van een lineair programmeerprobleemmodel
De gegevens in de optimale simplextabel maken een uitgebreide analyse van het lineaire model mogelijk, in het bijzonder een analyse van de gevoeligheid van de optimale oplossing voor veranderingen in de hulpbronnenreserves en variaties in de coëfficiënten van de doelfunctie. Laten we eerst het concept van dualiteit van lineaire programmeerproblemen geven.
Laten we het lineaire programmeringsprobleem (3.20)-(3.22) bekijken, waarbij we het resourcegebruiksprobleem als voorbeeld nemen. Als we voor deze initiële ZLP (laten we het direct noemen) variabelen introduceren ji om de beperkte middelen (3.21) te schatten en de overgang te maken naar de wiskundige formulering van een ander probleem (duaal of omgekeerd) van de vorm (3.23)-(3.25), dan zullen de oplossingen voor de directe en duale problemen wederzijds afhankelijk zijn, uitgedrukt door de overeenkomstige dualiteitsstellingen.
Het is duidelijk dat het dubbele probleem samenvalt met het oorspronkelijke probleem. Daarom is er geen verschil welke als direct wordt geaccepteerd en welke duaal is. Ze praten over een paar onderling dubbele problemen.
waar zijn de vaste kosten die niet afhankelijk zijn van de verwerkingswijze, min;
Hier - voorbereidend - eindtijd voor de operatie, min;
Batchgrootte van verwerkte onderdelen;
Hulpbedrijfstijd, min;
Onderhoudstijd exclusief gereedschapvervangingstijd, min;
Rusttijd van de werknemer, min;
Tijdkosten die gepaard gaan met het vervangen van een saai stuk gereedschap en de overeenkomstige aanpassing van het technologische systeem;
wanneer is het tijd om het gereedschap en de bijbehorende maataanpassing te vervangen;
Diameter en lengte van de verwerkte as;
Coëfficiënt voor het berekenen van de snijsnelheid;
Snijsnelheid;
Diepte van de snede;
Hier zijn de exponenten in de formules voor het berekenen van de snijomstandigheden.
Analyse van de tijdobjectieffunctie maakt het mogelijk om reserves voor extra productiviteitsverhogingen te onthullen en optimale snijomstandigheden te bepalen die minimale kosten voor het uitvoeren van de bewerking garanderen.
Objectieve kostenfunctie Als we het voorbeeld van schachtverwerking gebruiken, ziet het er als volgt uit:
Hier zijn de kosten van het materiaal;
Uitgaven per tijdseenheid voor respectievelijk de werking van apparatuur, apparaten, lonen, rekening houdend met overheadkosten;
Tijd voor gereedschapsvervanging en passende maataanpassing;
De kosten van de tool gedurende de gebruiksperiode.
Het eerste lid van de uitdrukking bepaalt de vaste kosten van het materiaal, de kosten die verband houden met de voorbereidings- en eindtijd en de servicetijd. De tweede term van de uitdrukking bepaalt de kosten van het snijgereedschap en de uitvaltijd bij vervanging ervan. De derde term van de uitdrukking bepaalt de kosten die rechtstreeks verband houden met het snijproces.
Volumeplanning van technologische machinesystemen
Deze en alle daaropvolgende lezingen zijn gewijd aan vragen wiskundige modellering en optimalisatie van technologische machinesystemen.
Volumetrische planning van het werk van het mechanische gedeelte wanneer de maximale belasting van technologische apparatuur is bereikt
Formulering van het probleem. Beschikbaar M– machines ( M– groepen machines) waarop ze kunnen worden vervaardigd N– soorten onderdelen. Complexiteit van verwerking J- oh details op i– m machine is , uur. De bedrijfstijd van elke machine (groep machines) is bekend - B i. De initiële gegevens voor het oplossen van het probleem zijn weergegeven in Tabel 14.1.
Tabel 14.1. Initiële gegevens voor het oplossen van het probleem, gepresenteerd in algemeen beeld
Moet bepalen aantal onderdelen van elk item, tijdens de verwerking waarvan dit wordt bereikt maximale lading uitrusting ter plaatse.
Wiskundig model om het probleem op te lossen zullen we schrijven:
Beperkingen:
Het probleem wordt opgelost met behulp van de lineaire programmeermethode. Houd rekening met het volgende. Het aantal beperkingen van de vorm (14.1) - (14.3) in het wiskundige model moet strikt gelijk zijn aan het aantal machines (groepen machines) van de site. Bij het oplossen van een probleem met behulp van een computer is het aantal machines (groepen machines), evenals de soorten onderdelen, vrijwel onbeperkt en wordt alleen bepaald door de mogelijkheden van de computer en het bijbehorende programma. Bij het handmatig oplossen van een probleem met behulp van de grafisch-analytische methode is het aantal typen machines (groepen machines) ook niet beperkt, maar het vergroten ervan zal uiteraard leiden tot een toename van de rekentijd. Het aantal soorten onderdelen mag niet groter zijn dan twee, omdat anders zal het onmogelijk zijn om de noodzakelijke grafische constructies op het vlak uit te voeren.
Voorbeeld. De brongegevens voor het voorbeeld worden gegeven in Tabel 14.2.
Tabel 14.2. Eerste gegevens voor het oplossen van het probleem
Laten we aangeven met het aantal onderdelen van type D 1, met het aantal onderdelen van type D 2.
Wiskundig model om dit probleem op te lossen, wordt als volgt geschreven:
Beperkingen(afhankelijk van de bedrijfstijd van de apparatuur):
Het is vereist om waarden te vinden die voldoen aan de gegeven beperkingen (14.6) – (14.10) en het maximum van de objectieve functie (14.11) te garanderen. De parameters zijn gecontroleerde parameters in een wiskundig model.
Laten we het grafoprobleem oplossen - analytische methode(zie lezing 6). Een grafische illustratie van de oplossing voor het probleem wordt getoond in Fig. 14.1.
Afb. 14.1. Grafische illustratie van de probleemoplossing
Berekeningen voor het construeren van restricties (14.6) – (14.8):
| X 1 | ||
| x 2 |
| X 1 | ||
| x 2 |
Nadat we een rechte lijn evenwijdig aan deze hebben getrokken, vinden we het raakpunt van de grens ODR - dit is punt A. Om de coördinaten te vinden (de snijpunten van beperkingen 14.7 en 14.8), lossen we op het volgende systeem vergelijkingen:
Die. Eindelijk
Maximale waarde De objectieve functie (maximale belasting van de locatieapparatuur) met optimale waarden van de vereiste parameters zal zijn:
Probleem met minimale apparatuurbelasting
Deze en daaropvolgende problemen worden in deze lezing gepresenteerd op het niveau van het stellen van het probleem en het vormen van een wiskundig model om het op te lossen. Ze worden allemaal opgelost met behulp van lineaire programmeermethoden.
Beschikbaar M machines waarop ze kunnen worden geproduceerd N soorten onderdelen. Prestatie i-de machine bij het vervaardigen van een onderdeel J- soort is C ij. Waarden van geplande taken Een j voor productie J- details en tijdbron B ik werk i-de machine worden gegeven in Tabel 14.3.
Tabel 14.3 Initiële gegevens voor het oplossen van het probleem
Het is vereist, rekening houdend met de bedrijfstijdbronnen van elke machine, om taken zodanig over de machines te verdelen dat totale tijd het werk van alle machines was minimaal.
Laten t ij- voorbereidingstijd J- oh details i- m-machine. Laten we voor elke machine de tijdresourcebeperkingen opstellen:
De oplossing voor het probleem is het minimaliseren van de lineaire objectieve functie (totale tijd)
 | (14.14) |
onder beperkingen (14.12), (14.13) en de voorwaarde dat alle variabelen .
Probleem over optimale verdeling machine onderdelen
Laat een machine bestaan uit verschillende types details, die we nummeren met cijfers. Er zijn verschillende soorten machines en het aantal machines van dit type is gelijk aan . Onderdelen kunnen machinaal worden bewerkt verschillende soorten. De productiviteit van het e type machine bij de productie van het e onderdeel is . Na productie worden de onderdelen verzonden voor montage. Het is vereist om machines zo aan onderdelen te bevestigen dat het maximale aantal machines per tijdseenheid wordt verkregen.
Laat het aantal machines van het e-type zijn waarop het e-onderdeel kan worden geproduceerd. Het is duidelijk dat het aantal machines van het e-type, dat onderdelen van typen produceert, niet groter mag zijn gegeven nummer :
Het totale aantal sets onderdelen dat nodig is om een machine te assembleren is gelijk aan het totale aantal van een bepaald onderdeel, met bijvoorbeeld nummer 1. Daarom is de oplossing voor het probleem het maximaliseren van lineaire functie
 | (14.17) |
onder beperkingen (14.15), (14.16) met de aanvullende voorwaarde dat alle variabelen .
De optimale waarden die voor dit probleem worden gevonden, zijn niet noodzakelijk gehele getallen. Het betekent bijvoorbeeld dat twee machines van het eerste type binnen een tijdseenheid onderdeel nummer 1 zullen produceren, terwijl een derde machine van hetzelfde type slechts de helft van de opgegeven tijd zal werken.
Het probleem van het produceren van producten met beperkte grondstoffenvoorraden
Geproduceerd uit soorten grondstoffen verschillende types producten. De kosten voor de verkoop van gefabriceerde producten van het e-type bedragen . De voorraad grondstoffen van de e soort voor de planperiode is gelijk aan . De behoefte aan dit soort grondstoffen is . De initiële gegevens voor het oplossen van het probleem zijn weergegeven in Tabel 14.4.
Tabel 14.4 Initiële gegevens voor het oplossen van het probleem
Het is voor elk type product vereist om een dergelijk productievolume te bepalen om de maximale verkoopkosten van gefabriceerde producten te garanderen, op voorwaarde dat de reserves aan beschikbare grondstoffen niet worden overschreden.
De beperkingen op de grondstoffenreserves zijn als volgt:
 | (14.18) |
De taak is om de optimale waarden van parameters (variabelen) te bepalen die de productiekosten maximaliseren, d.w.z. doelfunctie
onder beperkingen (14.18) en aanvullende voorwaarden.
Basis theorie in de rij staan
Wachtrijtheorie is een van de takken van de waarschijnlijkheidstheorie. Deze theorie beschouwt probabilistisch problemen en wiskundige modellen (daarvoor beschouwden we deterministische wiskundige modellen). Laten we u eraan herinneren dat:
Deterministisch wiskundig model weerspiegelt het gedrag van een object (systeem, proces) vanuit het perspectief volledige zekerheid in het heden en de toekomst.
Probabilistisch wiskundig model houdt rekening met de invloed van willekeurige factoren op het gedrag van een object (systeem, proces) en evalueert daarom de toekomst vanuit het standpunt van de waarschijnlijkheid van bepaalde gebeurtenissen.
Die. hier wordt, zoals bijvoorbeeld in de speltheorie, rekening gehouden met problemen in omstandigheden van onzekerheid.
Laten we eerst enkele concepten bekijken die ‘stochastische onzekerheid’ kenmerken, wanneer de onzekere factoren in het probleem willekeurige variabelen (of willekeurige functies) zijn, waarvan de probabilistische kenmerken ofwel bekend zijn of uit ervaring kunnen worden verkregen. Dergelijke onzekerheid wordt ook wel ‘gunstig’, ‘goedaardig’ genoemd.
Het concept van een willekeurig proces
Strikt genomen zijn willekeurige verstoringen inherent aan elk proces. Het is gemakkelijker om voorbeelden te geven van een willekeurig proces dan van een “niet-willekeurig” proces. Zelfs bijvoorbeeld het proces van het laten lopen van een klok (het lijkt een strikt gekalibreerd werk te zijn - "werkt als een klok") is onderhevig aan willekeurige veranderingen (vooruitgaan, achterblijven, stoppen). Maar zolang deze verstoringen onbeduidend zijn en weinig effect hebben op de parameters die voor ons van belang zijn, kunnen we ze verwaarlozen en het proces als deterministisch en niet-willekeurig beschouwen.
Laat er een systeem zijn S (technisch apparaat, een groep van dergelijke apparaten, een technologisch systeem - een machine, een site, een werkplaats, een onderneming, een industrie, enz.). In systeem S lekt willekeurig proces, als het zijn toestand in de loop van de tijd verandert (van de ene toestand naar de andere gaat), bovendien op een voorheen onbekende willekeurige manier.
Voorbeelden: 1. Systeem S– technologisch systeem (machinegedeelte). Machines gaan af en toe kapot en worden gerepareerd. Het proces dat in dit systeem plaatsvindt, is willekeurig.
2. Systeem S- een vliegtuig dat op een bepaalde hoogte langs een specifieke route vliegt. Storende factoren - weersomstandigheden, fouten van de bemanning, enz., gevolgen - hobbeligheid, overtreding van het vluchtschema, enz.
Markov willekeurig proces
Een willekeurig proces dat in een systeem plaatsvindt, wordt genoemd Markovsky, al is het maar voor een moment T De probabilistische kenmerken van het proces in de toekomst hangen alleen af van de staat ervan dit moment T 0 en zijn niet afhankelijk van wanneer en hoe het systeem deze status heeft bereikt.
Binnenlaten momenteel t 0 Het systeem bevindt zich in een bepaalde toestand S 0 . We kennen de kenmerken van de toestand van het systeem in het heden en alles wat er in de loop van de tijd is gebeurd T < T 0 (procesgeschiedenis). Kunnen we de toekomst voorspellen (voorspellen), d.w.z. wat zal er wanneer gebeuren T > T 0? Niet precies, maar er kunnen in de toekomst enkele probabilistische kenmerken van het proces worden gevonden. Bijvoorbeeld de kans dat het systeem na enige tijd S In staat tot S 1 of zal in staat blijven S 0, enz.
Voorbeeld. Systeem S- een groep vliegtuigen die deelnemen aan luchtgevechten. Laten X– aantal “rode” vliegtuigen, j– aantal “blauwe” vliegtuigen. Tegen de tijd T 0 aantal overgebleven (niet neergeschoten) vliegtuigen, respectievelijk - X 0 , j 0 . Wij zijn geïnteresseerd in de waarschijnlijkheid dat op een bepaald moment de numerieke superioriteit aan de kant van de ‘rode’ zal liggen. Deze waarschijnlijkheid hangt af van de staat waarin het systeem zich op dat moment bevond T 0, en niet over wanneer en in welke volgorde de neergeschotenen stierven tot op dat moment T 0 vliegtuigen.
In de praktijk kom je Markov-processen in hun pure vorm doorgaans niet tegen. Maar er zijn processen waarbij de invloed van de ‘prehistorie’ kan worden verwaarloosd. En bij het bestuderen van dergelijke processen kunnen Markov-modellen worden gebruikt (de wachtrijtheorie houdt geen rekening met Markov-wachtrijsystemen, maar het wiskundige apparaat dat ze beschrijft is veel complexer).
In operationeel onderzoek zijn Markov-willekeurige processen met discrete toestanden en continue tijd van groot belang.
Het proces wordt genoemd discreet staatsproces, als het mogelijke toestanden zijn S 1 , S 2, ... kan van tevoren worden bepaald, en de overgang van het systeem van staat naar staat vindt vrijwel onmiddellijk ‘in een sprong’ plaats.
Het proces wordt genoemd continu tijdsproces, als de momenten van mogelijke overgangen van toestand naar toestand niet van tevoren vastliggen, maar onzeker en willekeurig zijn en op elk moment kunnen plaatsvinden.
Voorbeeld. Technologisch systeem (sectie) S bestaat uit twee machines die elk op een willekeurig moment kunnen falen (failen), waarna direct de reparatie van de eenheid begint, die ook voor een onbekende, willekeurige tijd doorgaat. De volgende systeemtoestanden zijn mogelijk:
S 0 - beide machines werken;
S 1 - de eerste machine wordt gerepareerd, de tweede werkt;
S 2 - de tweede machine wordt gerepareerd, de eerste werkt;
S 3 - beide machines worden gerepareerd.
Systeemovergangen S van staat tot staat vrijwel onmiddellijk plaatsvinden willekeurige momenten uitval van een bepaalde machine of voltooiing van reparaties.
Bij het analyseren van willekeurige processen met discrete toestanden is het handig om een geometrisch schema te gebruiken - staat grafiek. De hoekpunten van de grafiek zijn de toestanden van het systeem. Grafiekbogen – mogelijke overgangen van staat naar
Afb. 15.1. Systeemstatusgrafiek
staat. Voor ons voorbeeld wordt de toestandsgrafiek getoond in figuur 15.1.
Opmerking. Overgang van staat S 0 inch S 3 is niet aangegeven in de figuur, omdat Er wordt aangenomen dat de machines onafhankelijk van elkaar uitvallen. We verwaarlozen de mogelijkheid van gelijktijdig falen van beide machines.
Gebeurtenisstreams
Gebeurtenisstroom– een opeenvolging van homogene gebeurtenissen die elkaar op willekeurige momenten opvolgen.
In het vorige voorbeeld is dit een stroom van mislukkingen en een stroom van restauraties. Andere voorbeelden: gespreksstroom aan telefoon uitwisseling, klantenstroom in de winkel, etc.
De stroom van gebeurtenissen kan visueel worden weergegeven door een reeks punten op de tijdas Ot- rijst. 15.2.
Afb. 15.2. Weergave van de stroom van gebeurtenissen op de tijdas
De positie van elk punt is willekeurig en hier wordt slechts één implementatie van de stroom weergegeven.
Intensiteit van de gebeurtenisstroom () is het gemiddelde aantal gebeurtenissen per tijdseenheid.
Laten we eens kijken naar enkele eigenschappen (typen) van gebeurtenisstromen.
De stroom van gebeurtenissen wordt opgeroepen stationair, als de probabilistische kenmerken niet afhankelijk zijn van tijd.
Met name de intensiteit van de stationaire stroming is constant. De stroom van gebeurtenissen heeft onvermijdelijk condensaties of zeldzaamheden, maar deze zijn niet regelmatig van aard, en het gemiddelde aantal gebeurtenissen per tijdseenheid is constant en niet afhankelijk van de tijd.
De stroom van gebeurtenissen wordt opgeroepen stromen zonder gevolgen, als voor twee niet-overlappende tijdsperioden (zie figuur 15.2) het aantal gebeurtenissen dat op de ene valt, niet afhangt van het aantal gebeurtenissen dat op de andere valt. Met andere woorden: dit betekent dat de gebeurtenissen die de stroom vormen, op bepaalde tijdstippen verschijnen onafhankelijk van elkaar en worden elk veroorzaakt door hun eigen oorzaken.
De stroom van gebeurtenissen wordt opgeroepen normaal, als gebeurtenissen er één voor één in verschijnen, en niet in groepen van meerdere tegelijk.
De stroom van gebeurtenissen wordt opgeroepen eenvoudigste (of stationaire Poisson), als het drie eigenschappen tegelijk heeft: 1) stationair, 2) gewoon, 3) heeft geen gevolgen.
De eenvoudigste stroom heeft de eenvoudigste wiskundige beschrijving. Hij speelt hetzelfde tussen de streams bijzondere rol zoals de wet normale verdeling onder andere distributiewetten. Het is namelijk voldoende als het wordt toegepast groot nummer onafhankelijke, stationaire en gewone stromingen (in intensiteit vergelijkbaar met elkaar) resulteren in een stroming die de eenvoudigste benadert.
Voor de eenvoudigste stroom met intensiteitsinterval T tussen aangrenzende evenementen heeft een zogenaamde exponentiële verdeling met dichtheid
Objectieve functie- een reële of geheeltallige functie van verschillende variabelen die onderworpen is aan optimalisatie (minimalisatie of maximalisatie) om een optimalisatieprobleem op te lossen. De term wordt gebruikt in wiskundig programmeren, operationeel onderzoek, lineair programmeren, statistische besliskunde en andere gebieden van de wiskunde, voornamelijk van toegepaste aard, hoewel het doel van optimalisatie ook de oplossing van het wiskundige probleem zelf kan zijn. Naast de doelfunctie in het optimalisatieprobleem kunnen beperkingen worden opgegeven voor variabelen in de vorm van een stelsel van gelijkheden of ongelijkheden. Over het algemeen kunnen de argumenten van de doelfunctie worden gespecificeerd op willekeurige sets.
Voorbeelden
Gladde functies en stelsels van vergelijkingen
Het probleem van het oplossen van elk systeem van vergelijkingen
( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\rechts.)
kan worden geformuleerd als een probleem van het minimaliseren van de objectieve functie
S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\som _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots,x_(M))\qquad (1))
Als de functies vloeiend zijn, kan het minimalisatieprobleem worden opgelost met behulp van gradiëntmethoden.
Voor elke gladde objectieve functie kunnen de partiële afgeleiden met betrekking tot alle variabelen gelijkgesteld worden aan 0 (\displaystyle 0). Het optimale van de objectieve functie zal een van de oplossingen zijn voor een dergelijk systeem van vergelijkingen. In het geval van functie (1) (\displaystyle (1)) zal dit een systeem van vergelijkingen zijn dat de kleinste kwadratenmethode (LSM) gebruikt. Elke beslissing origineel systeem is een oplossing voor het kleinste kwadratenstelsel. Als het oorspronkelijke systeem inconsistent is, stelt het kleinste kwadratensysteem, dat altijd een oplossing heeft, ons in staat een benaderende oplossing van het oorspronkelijke systeem te verkrijgen. Het aantal vergelijkingen in het kleinste kwadratensysteem valt samen met het aantal onbekenden, wat soms de oplossing van gezamenlijke initiële systemen vergemakkelijkt.
Lineair programmeren
Een ander bekend voorbeeld van een objectieve functie is een lineaire functie, die ontstaat bij lineaire programmeerproblemen. In tegenstelling tot de kwadratische doelfunctie is optimalisatie van een lineaire functie alleen mogelijk als er beperkingen zijn in de vorm van een systeem van lineaire gelijkheden of ongelijkheden.
Combinatorische optimalisatie
Een typisch voorbeeld van een combinatorische objectieve functie is de objectieve functie van het handelsreizigerprobleem. Deze functie is gelijk aan de lengte van de Hamiltoniaanse cyclus in de grafiek. Het wordt gedefinieerd op basis van de reeks permutaties van n - 1 (\displaystyle n-1) hoekpunten van de grafiek en wordt bepaald door de matrix van grafiekrandlengtes. De exacte oplossing voor dergelijke problemen komt vaak neer op het opsommen van opties.
Hoofdstuk 1. Verklaring van het belangrijkste lineaire programmeerprobleem
Lineair programmeren
Lineair programmeren is een tak van wiskundig programmeren die methoden bestudeert voor het oplossen van extreme problemen die worden gekenmerkt door: lineaire afhankelijkheid tussen variabelen en lineaire test. Dergelijke problemen vinden uitgebreide toepassingen op verschillende gebieden van menselijke activiteit. De systematische studie van dit soort problemen begon in 1939–1940. in de werken van L.V. Kantorovitsj.
Wiskundige problemen van lineaire programmering omvatten studies van specifieke productie- en economische situaties, die in een of andere vorm worden geïnterpreteerd als problemen over het optimale gebruik van beperkte hulpbronnen.
Het scala aan problemen dat met behulp van lineaire programmeermethoden kan worden opgelost, is vrij breed, bijvoorbeeld:
het probleem van het optimale gebruik van hulpbronnen bij de productieplanning;
mengselprobleem (planning van productsamenstelling);
probleem van het vinden optimale combinatie verschillende soorten producten voor opslag in magazijnen (voorraadbeheer of);
transporttaken (analyse van de bedrijfslocatie, verplaatsing van goederen).
Lineair programmeren is het meest ontwikkelde en meest gebruikte onderdeel van wiskundig programmeren (hiernaast omvat dit: geheeltallig, dynamisch, niet-lineair, parametrisch programmeren). Dit wordt als volgt uitgelegd:
groot aantal wiskundige modellen economische taken lineair ten opzichte van de gewenste variabelen;
Dit type probleem is momenteel het meest bestudeerd. Er zijn speciale methoden voor ontwikkeld, met behulp waarvan deze problemen worden opgelost, en bijbehorende computerprogramma's;
veel lineaire programmeerproblemen hebben, nadat ze zijn opgelost, een brede toepassing gevonden;
enkele problemen, die in de oorspronkelijke formulering niet lineair zijn, na een reeks aanvullende beperkingen en aannames kunnen lineair worden of tot een zodanige vorm worden teruggebracht dat ze kunnen worden opgelost door lineaire programmeermethoden.
Het economische en wiskundige model van elk lineair programmeerprobleem omvat: een objectieve functie waarvan de optimale waarde (maximum of minimum) moet worden gevonden; beperkingen in de vorm van een systeem van lineaire vergelijkingen of ongelijkheden; vereiste van niet-negativiteit van variabelen.
Over het algemeen is het model als volgt geschreven:
objectieve functie
(1.1) met beperkingen
(1.2) niet-negativiteitsvereisten
(1.3) waar X J– variabelen (onbekend);
- coëfficiënten van het lineaire programmeringsprobleem.
De taak is om te vinden optimale waarde functie (1.1) onderworpen aan beperkingen (1.2) en (1.3).
Het systeem van beperkingen (1.2) wordt functionele beperkingen van het probleem genoemd, en beperkingen (1.3) worden directe beperkingen genoemd.
Een vector die aan de beperkingen (1.2) en (1.3) voldoet, wordt een toelaatbare oplossing (plan) van een lineair programmeerprobleem genoemd. Het plan waarbij functie (1.1) zijn maximale (minimale) waarde bereikt, wordt optimaal genoemd.
1.2. Simplexmethode voor het oplossen van lineaire programmeerproblemen
De simplexmethode werd in 1947 ontwikkeld en voor het eerst gebruikt om problemen op te lossen door de Amerikaanse wiskundige J. Danzig.
Tweedimensionale lineaire programmeerproblemen worden grafisch opgelost. Voor het geval N=3 kunnen we een driedimensionale ruimte beschouwen en zal de objectieve functie zijn optimale waarde bereiken op een van de hoekpunten van het veelvlak.
Een toelaatbare oplossing (toelaatbaar plan) van het opgegeven LP-probleem standaard vorm, is een geordende reeks getallen (x1, x2, ..., xn) die aan de beperkingen voldoen; het is een punt in de n-dimensionale ruimte.
De reeks toelaatbare oplossingen vormt het gebied van toelaatbare oplossingen (ADS) van het LP-probleem. ODR is een convex veelvlak (polygoon).
Wanneer het probleem betrekking heeft op N-onbekenden, kunnen we in het algemeen zeggen dat het gebied van haalbare oplossingen gedefinieerd door het systeem van beperkende voorwaarden wordt weergegeven door een convex veelvlak in de n-dimensionale ruimte en dat de optimale waarde van de doelfunctie wordt bereikt op één of meer hoekpunten.
Een basisoplossing is een oplossing waarin alle vrije variabelen gelijk zijn aan nul.
Een ondersteunende oplossing is een fundamentele, niet-negatieve oplossing. De ondersteuningsoplossing kan niet-gedegenereerd en gedegenereerd zijn. Een referentieoplossing wordt niet-gedegenereerd genoemd als het aantal niet-nulcoördinaten gelijk is aan de rangorde van het systeem, anders is het gedegenereerd.
Een toelaatbare oplossing waarbij de objectieve functie zijn extreme waarde bereikt, wordt optimaal genoemd en wordt aangegeven 
.
Het is erg moeilijk om deze problemen grafisch op te lossen als het aantal variabelen meer dan 3 bedraagt. Bestaat universele methode het oplossen van lineaire programmeerproblemen, de simplexmethode genoemd.
De simplexmethode is een universele methode voor het oplossen van LP-problemen, een iteratief proces dat begint met één oplossing en, op zoek naar de beste optie, langs de hoekpunten van het gebied van haalbare oplossingen beweegt totdat het de optimale waarde bereikt.
Het kan worden gebruikt om elk lineair programmeerprobleem op te lossen.
De simplexmethode is gebaseerd op het idee van opeenvolgende verbetering van de resulterende oplossing.
De geometrische betekenis van de simplexmethode is een sequentiële overgang van het ene hoekpunt van het beperkingsveelvlak naar het aangrenzende, waarbij de objectieve functie de beste (of, volgens ten minste, niet de slechtste) waarde totdat de optimale oplossing is gevonden - het hoekpunt waar de optimale waarde van de doelfunctie wordt bereikt (als het probleem een uiteindelijk optimale waarde heeft).
Omdat ze dus een systeem van beperkingen hebben dat is teruggebracht tot een canonieke vorm (alle functionele beperkingen hebben de vorm van gelijkheden), vinden ze elke basisoplossing voor dit systeem, waarbij ze er alleen op uit zijn deze zo eenvoudig mogelijk te vinden. Als de eerste gevonden basisoplossing haalbaar blijkt, wordt deze gecontroleerd op optimaliteit. Als het niet optimaal is, wordt overgegaan op een andere, noodzakelijkerwijs toelaatbare, basisoplossing. De simplexmethode garandeert dat met deze nieuwe oplossing de objectieve functie, als deze het optimale niet bereikt, dit zal benaderen (of er in ieder geval niet van af zal bewegen). Hetzelfde wordt gedaan met een nieuwe haalbare basisoplossing totdat er een optimale oplossing is gevonden.
Het proces van het toepassen van de simplexmethode omvat de implementatie van de drie belangrijkste elementen:
een methode voor het bepalen van een initieel haalbare basisoplossing voor een probleem;
de regel van overgang naar de beste (meer precies, niet slechtere) oplossing;
criterium voor het controleren van de optimaliteit van de gevonden oplossing.
De simplexmethode omvat een aantal fasen en kan worden geformuleerd in de vorm van een helder algoritme (een duidelijke instructie voor het uitvoeren van opeenvolgende bewerkingen). Hierdoor kunt u het met succes op een computer programmeren en implementeren. Taken met een klein aantal variabelen en beperkingen kunnen worden opgelost simplex methode handmatig.
6.1.Inleiding
Optimalisatie. Deel 1
Met optimalisatiemethoden kunt u kiezen beste optie ontwerpen van allemaal mogelijke opties. De afgelopen jaren hebben deze methoden veel aandacht gekregen veel aandacht, en als resultaat zijn er een aantal zeer efficiënte algoritmen ontwikkeld om te vinden beste optie ontwerpen met behulp van een computer. Dit hoofdstuk schetst de basisprincipes van de optimalisatietheorie, onderzoekt de principes die ten grondslag liggen aan de constructie van algoritmen voor optimale oplossingen, beschrijft de meest bekende algoritmen en analyseert hun voor- en nadelen.
6.2. Grondbeginselen van de optimalisatietheorie
De term ‘optimalisatie’ verwijst in de literatuur naar een proces of een reeks handelingen die het mogelijk maakt een verfijnde oplossing te verkrijgen. Hoewel het uiteindelijke doel van optimalisatie het vinden van de beste of ‘optimale’ oplossing is, moet men meestal genoegen nemen met het verbeteren van bekende oplossingen in plaats van ze te perfectioneren. Daarom wordt optimalisatie eerder opgevat als een verlangen naar perfectie, wat mogelijk niet wordt bereikt.
Als we een willekeurig systeem beschouwen dat wordt beschreven door m vergelijkingen met n onbekenden, kunnen we drie hoofdtypen problemen onderscheiden. Als m=n, wordt het probleem algebraïsch genoemd. Dit probleem heeft meestal één oplossing. Als m>n is het probleem overgedetermineerd en heeft het in de regel geen oplossing. Tenslotte voor m
Voordat we optimalisatievraagstukken gaan bespreken, introduceren we een aantal definities.
Ontwerpparameters
Deze term duidt op onafhankelijke variabele parameters die volledig en ondubbelzinnig bepalen welk ontwerpprobleem moet worden opgelost. Ontwerpparameters zijn onbekende grootheden waarvan de waarden worden berekend tijdens het optimalisatieproces. Elke basis- of afgeleide grootheid die dient om het systeem kwantitatief te beschrijven, kan als ontwerpparameter dienen. Dit kunnen dus onbekende waarden zijn van lengte, massa, tijd en temperatuur. Het aantal ontwerpparameters karakteriseert de mate van complexiteit van een bepaald ontwerpprobleem. Gewoonlijk wordt het aantal ontwerpparameters aangegeven met n, en de ontwerpparameters zelf met x met de bijbehorende indices. n ontwerpparameters van dit probleem zullen dus worden aangegeven met
X1, x2, x3,...,xn.
Objectieve functie
Het is een uitdrukking waarvan de ingenieur de waarde maximaal of minimaal wil maken. Met de objectieve functie kunt u er twee kwantitatief vergelijken alternatieve oplossingen. Vanuit wiskundig oogpunt beschrijft de objectieffunctie een (n+1)-dimensionaal oppervlak. De waarde ervan wordt bepaald door de ontwerpparameters
M=M(x 1, x 2,...,x n).
Voorbeelden van objectieve functies die vaak in de technische praktijk worden aangetroffen, zijn kosten, gewicht, sterkte, afmetingen en efficiëntie. Als er slechts één ontwerpparameter is, kan de doelfunctie worden weergegeven door een curve in het vlak (Fig. 6.1). Als er twee ontwerpparameters zijn, wordt de objectieffunctie weergegeven als een oppervlak in een driedimensionale ruimte (Fig. 6.2). Bij drie of meer ontwerpparameters worden de door de doelfunctie gespecificeerde oppervlakken hyperoppervlakken genoemd en kunnen ze niet worden afgebeeld.
huwelijk met gewone middelen. De topologische eigenschappen van het oppervlak van de objectieve functie spelen een grote rol in het optimalisatieproces, omdat de keuze van het meest efficiënte algoritme ervan afhangt.
De objectieve functie kan in sommige gevallen de meest onverwachte vormen aannemen. Het is bijvoorbeeld niet altijd mogelijk om dit uit te drukken
Fig. 1. Eendimensionale objectieffunctie.
Figuur 6.2 Tweedimensionale objectieffunctie.
gesloten wiskundige vorm, in andere gevallen kan dat wel
vertegenwoordigen een stuksgewijze gladde functie. Voor het specificeren van een objectieve functie kan soms een tabel met technische gegevens nodig zijn (bijvoorbeeld een tabel met de toestand van waterdamp) of kan een experiment nodig zijn. In sommige gevallen nemen ontwerpparameters alleen gehele waarden aan. Een voorbeeld hiervan is het aantal tanden in een tandwieltrein of het aantal bouten in een flens. Soms hebben ontwerpparameters slechts twee betekenissen: ja of nee. Kwalitatieve parameters, zoals de tevredenheid die wordt ervaren door de koper die het product heeft gekocht, de betrouwbaarheid en de esthetiek, zijn moeilijk in aanmerking te nemen in het optimalisatieproces, omdat ze vrijwel onmogelijk kwantitatief te karakteriseren zijn. Echter, in welke vorm de objectieve functie ook wordt gepresenteerd, het moet een ondubbelzinnige functie van de ontwerpparameters zijn.
Een aantal optimalisatieproblemen vereisen de introductie van meer dan één doelfunctie. Soms blijkt de een onverenigbaar met de ander. Een voorbeeld is het ontwerpen van vliegtuigen, waarbij maximale sterkte, minimaal gewicht en minimale kosten tegelijkertijd vereist zijn. In dergelijke gevallen moet de ontwerper een systeem van prioriteiten invoeren en aan elke objectieve functie een bepaalde dimensieloze vermenigvuldiger toekennen. Als resultaat hiervan verschijnt er een “compromisfunctie”, die het gebruik van één samengestelde objectieve functie tijdens het optimalisatieproces mogelijk maakt.
Het vinden van minimum en maximum
Sommige optimalisatiealgoritmen zijn ontworpen om het maximum te vinden, andere om het minimum te vinden. Ongeacht het type extremumprobleem dat wordt opgelost, kunt u echter hetzelfde algoritme gebruiken, aangezien het minimalisatieprobleem gemakkelijk kan worden omgezet in een maximaal zoekprobleem door het teken van de objectieve functie om te keren. Deze techniek wordt geïllustreerd in figuur 6.3.
Ontwerp ruimte
Dit is de naam van het gebied dat wordt gedefinieerd door alle n ontwerpparameters. De ontwerpruimte is niet zo groot als het lijkt, omdat deze meestal wordt beperkt door een aantal
omstandigheden die verband houden met de fysieke essentie van het probleem. De beperkingen kunnen zo sterk zijn dat het probleem er geen zal zijn
Fig.6.3. Het teken van de objectieve functie naar het tegenovergestelde veranderen
de maximale taak verandert in een minimale taak.
bevredigende oplossing. Beperkingen zijn onderverdeeld in twee groepen: beperkingen - gelijkheid en beperkingen - ongelijkheid.
Beperkingen - Gelijkheid
Beperkingen – gelijkheden – zijn de afhankelijkheden tussen ontwerpparameters waarmee rekening moet worden gehouden bij het vinden van een oplossing. Ze weerspiegelen de wetten van de natuur, de economie, het recht, de heersende smaak en de beschikbaarheid van noodzakelijke materialen. Het aantal beperkingen - gelijkheden kunnen elk zijn. Ze lijken op
C 1 (x 1 , x 2 ,...,x n)=0,
C 2 (x 1, x 2,...,x n)=0,
..................
Cj (x 1 , x 2 ,...,x n)=0.
Als een van deze relaties kan worden opgelost met betrekking tot een van de ontwerpparameters, kan deze parameter worden uitgesloten van het optimalisatieproces. Dit vermindert het aantal afmetingen van de ontwerpruimte en vereenvoudigt de oplossing van het probleem.
Beperkingen - ongelijkheden
Dit is een speciaal soort beperking die tot uiting komt in ongelijkheid. Over het algemeen kunnen er zoveel zijn als je wilt, en ze hebben allemaal de vorm
z 1 r 1 (x 1 , x 2 ,...,x n) Z 1
z 2 r 2 (x 1 , x 2 ,...,x n) Z 2
.......................
z k r k (x 1 , x 2 ,...,x n) Z k
Opgemerkt moet worden dat vanwege beperkingen de optimale waarde van de objectieffunctie heel vaak niet wordt bereikt daar waar het oppervlak een gradiënt van nul heeft. Vaak De beste beslissing komt overeen met een van de grenzen van het ontwerpgebied.
Lokaal optimaal
Dit is de naam van het punt in de ontwerpruimte waar de objectieffunctie heeft hoogste waarde vergeleken met de waarden op alle andere punten in de directe omgeving.
Fig. 6.4. Een willekeurige doelfunctie kan er meerdere hebben
lokale optimale omstandigheden.
In afb. Figuur 6.4 toont een eendimensionale objectieffunctie die twee lokale optima heeft. Vaak bevat de ontwerpruimte veel lokale optima en moet ervoor worden gezorgd dat de eerste niet wordt aangezien voor de optimale oplossing voor het probleem.
Globaal optimaal
Het globale optimale is de optimale oplossing voor de gehele ontwerpruimte. Het is beter dan alle andere oplossingen die overeenkomen met lokale optima, en het is waar de ontwerper naar op zoek is. Het is mogelijk dat er meerdere gelijkwaardige mondiale optima bestaan verschillende delen ontwerp ruimte. Hoe een optimalisatieprobleem wordt gesteld, kan het beste worden geïllustreerd met een voorbeeld.
Voorbeeld 6.1
Stel dat u een rechthoekige container met een volume van 1 m moet ontwerpen, bedoeld voor het transport van onverpakte vezels. Het is wenselijk dat er zo min mogelijk materiaal wordt besteed aan de vervaardiging van dergelijke containers (uitgaande van een constante wanddikte betekent dit dat het oppervlak minimaal moet zijn), omdat het goedkoper zal zijn. Om de container gemakkelijk door een vorkheftruck te kunnen oppakken, moet de breedte minimaal 1,5 m zijn.
Laten we dit probleem formuleren in een vorm die handig is voor het toepassen van het optimalisatiealgoritme.
Ontwerpparameters: x 1, x 2, x 3.
De objectieve functie (die geminimaliseerd moet worden) is het oppervlak van het zijoppervlak van de container:
A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.
Beperking - gelijkheid:
Inhoud = x 1 x 2 x 3 = 1m3.
Beperking - ongelijkheid:
Lineaire programmeerproblemen
Lineaire programmering (LP) is een van de takken van wiskundig programmeren - een discipline die extreme (optimalisatie)problemen bestudeert en methoden ontwikkelt om deze op te lossen.
Optimalisatie probleem is een wiskundig probleem dat bestaat uit het vinden van de optimale (d.w.z. maximale of minimale) waarde van de doelfunctie, en de waarden van de variabelen moeten tot een bepaald bereik van aanvaardbare waarden (APV) behoren.
Over het algemeen bestaat de formulering van een extreem probleem van wiskundig programmeren uit het bepalen van de grootste of kleinste waarde van een zogenaamde functie doelfunctie, onder voorwaarden (beperkingen), waarbij en functies krijgen, en constante waarden krijgen. In dit geval bepalen beperkingen in de vorm van gelijkheden en ongelijkheden de verzameling (oppervlakte) van toelaatbare oplossingen (ADS), en worden deze genoemd ontwerpparameters.
Afhankelijk van het type functies worden wiskundige programmeerproblemen onderverdeeld in een aantal klassen (lineair, niet-lineair, convex, geheel getal, stochastisch, dynamisch programmeren en etc.).
IN algemeen beeld het LP-probleem heeft volgende weergave:
, (5.1)
, , (5.2)
, 
, (5.3)
waarbij , , constante waarden krijgen.
Functie (5.1) wordt de objectieve functie genoemd; systemen (5.2), (5.3) – een systeem van beperkingen; voorwaarde (5.4) – de voorwaarde van niet-negativiteit van ontwerpparameters.
De reeks ontwerpparameters die voldoen aan de beperkingen (5.2), (5.3) en (5.4) wordt genoemd aanvaardbare oplossing of plan.
De optimale oplossing of optimaal plan LP-probleem wordt een toelaatbare oplossing genoemd waarin de objectieve functie (5.1) de optimale (maximale of minimale) waarde aanneemt.
Standaard taak LP is het probleem van het vinden van de maximale (minimale) waarde van de objectieve functie (5.1) onder voorwaarde (5.2) en (5.4), waarbij , , d.w.z. die. beperkingen alleen in de vorm van ongelijkheden (5.2) en alle ontwerpparameters voldoen aan de voorwaarde van niet-negativiteit, en er zijn geen voorwaarden in de vorm van gelijkheden:
,
, , (5.5)
.
Canonieke (hoofd)taak LP is het probleem van het vinden van de maximale (minimale) waarde van de objectieve functie (5.1) onder voorwaarde (5.3) en (5.4), waarbij , , d.w.z. die. beperkingen alleen in de vorm van gelijkheden (5.3) en alle ontwerpparameters voldoen aan de voorwaarde van niet-negativiteit, en er zijn geen voorwaarden in de vorm van ongelijkheden:
,
.
Het canonieke LP-probleem kan ook in matrix- en vectorvorm worden geschreven.
De matrixvorm van het canonieke LP-probleem heeft de volgende vorm:
Vectorvorm van het canonieke LP-probleem.
Taakvariabelen
Laten we een model van het probleem bouwen.
Oplossing
Voordat we een wiskundig model van het probleem construeren, moet ᴛ.ᴇ. schrijf het op met behulp van wiskundige symbolen, is het uiterst belangrijk om de in de aandoening beschreven economische situatie duidelijk te begrijpen. Hiervoor is het uiterst belangrijk vanuit het oogpunt van de economie, en niet vanuit het oogpunt van de wiskunde, beantwoord de volgende vragen:
1) Wat zijn de vereiste hoeveelheden van het probleem?
2) Wat is het doel van het besluit? Welke parameter van het probleem dient als criterium voor de effectiviteit (optimaliteit) van de oplossing, bijvoorbeeld winst, kosten, tijd, enz. In welke richting moet de waarde van deze parameter veranderen (naar max of naar min) om dit te bereiken beste resultaten?
3) Aan welke voorwaarden moet worden voldaan met betrekking tot de vereiste hoeveelheden en middelen van de taak?
Deze voorwaarden bepalen hoe zij zich tot elkaar moeten verhouden verschillende parameters taken, bijvoorbeeld de hoeveelheid middelen die wordt besteed aan de productie en de voorraad in het magazijn; de hoeveelheid geproduceerde producten en de capaciteit van het magazijn waar ze zullen worden opgeslagen; hoeveelheid geproduceerde producten en marktvraag naar deze producten, enz.
Pas na het economische antwoord op al deze vragen kan men beginnen deze antwoorden in wiskundige vorm op te schrijven, ᴛ.ᴇ. om het wiskundige model vast te leggen.
Het probleem vereist dat wordt bepaald hoeveel verf van elk type moet worden geproduceerd. Om deze reden, de gewenste hoeveelheden, en daarom taakvariabelen zijn de dagelijkse productievolumes van elk type verf:
x1 – dagelijks productievolume verf van het 1e type, [t verf/dag];
x2 – dagelijks productievolume verf van het 2e type, [t verf/dag].
In de probleemstelling wordt het doel gesteld om een maximaal inkomen uit de productverkoop te behalen. Die. Het prestatiecriterium is de dagelijkse inkomensparameter, die naar het maximum moet neigen. Om het dagelijkse inkomen uit de verkoop van beide soorten verf te berekenen, is het uiterst belangrijk om het volume van de verfproductie te kennen, ᴛ.ᴇ. x1 en x2 ton verf per dag, evenals groothandelsprijzen voor verven van het 1e en 2e type - volgens de voorwaarden respectievelijk 3 en 2 duizend roebel. voor 1 ton verf. Met andere woorden, de inkomsten uit de verkoop van het dagelijkse productievolume van verf van het 1e type zijn gelijk aan 3 x 1000 roebel. per dag, en uit de verkoop van verf van het 2e type - 2x 2000 roebel. per dag. Om deze reden schrijven we de objectieve functie als de som van de inkomsten uit de verkoop van verven van het 1e en 2e type (uitgaande van de onafhankelijkheid van de verkoopvolumes van elke verf)
Objectieve functie - concept en typen. Classificatie en kenmerken van de categorie "Doelfunctie" 2017, 2018.
HOOFDSTUK 16. EFFICIËNTIE VAN MANAGEMENTCONTROLEVRAGEN 1. Wat veroorzaakte de behoefte aan buitenlandse economische activiteit van de onderneming? 2. Wat bevordert de buitenlandse economische activiteit van een onderneming? 3. Wat is een obstakel voor... .
F(X) = 75X1 + 800/X1 + 78X2 + 1600/X2. De functie is convex als F"(x)>0 voor elke x. Laten we eens kijken: ; ; ; . Dit betekent dat de functie convex is omdat "x>0. Daarom blijkt het kiezen van het optimale aantal treinen op twee secties een convex programmeerprobleem te zijn dat kan worden opgelost... .
In de omstandigheden van een marktsysteem voor het beheren van de productie- en verkoopactiviteiten van ondernemingen en firma's is de basis voor het nemen van zakelijke beslissingen marktinformatie, en de geldigheid van beslissingen wordt door de markt geverifieerd tijdens de verkoop van goederen en diensten. Met deze aanpak...
