Als er maar één beperkende factor is (bijvoorbeeld een schaarse machine), kan met behulp van een oplossing worden gevonden eenvoudige formules(zie link aan het begin van het artikel). Als er meerdere beperkende factoren zijn, wordt de methode toegepast lineair programmeren.
Lineair programmeren is de naam die wordt gegeven aan een combinatie van tools die worden gebruikt in de managementwetenschap. Deze methode lost het distributieprobleem op beperkte middelen tussen concurrerende activiteiten om sommige te maximaliseren of te minimaliseren numerieke grootheden, zoals contributiemarge of kosten. In het bedrijfsleven kan het bijvoorbeeld worden gebruikt voor productieplanning maximale vergroting winst, selectie van componenten om kosten te minimaliseren, selectie van investeringsportfolio om winstgevendheid te maximaliseren, optimalisatie van goederentransport om afstanden te verkleinen, verdeling van personeel om werkefficiëntie te maximaliseren en planning van werken om tijd te besparen.
Notitie downloaden in , tekeningen in formaat
Lineaire programmering omvat de constructie wiskundig model de taak die wordt overwogen. Daarna kan de oplossing grafisch worden gevonden (hieronder besproken), met Excel gebruiken(afzonderlijk te beschouwen) of gespecialiseerde computerprogramma's.
Misschien is de constructie van een wiskundig model het moeilijkste onderdeel van lineair programmeren, waarbij het probleem in kwestie moet worden vertaald naar een systeem van variabelen, vergelijkingen en ongelijkheden - een proces dat uiteindelijk afhangt van de vaardigheden, ervaring, capaciteiten en intuïtie van de samensteller van het model.
Overweeg een voorbeeld van het construeren van een wiskundig model van lineaire programmering
Nikolai Kuznetsov runt een kleine mechanische fabriek. Volgende maand is hij van plan om twee producten te produceren (A en B), waarvoor de specifieke marginale winst wordt geschat op respectievelijk 2.500 en 3.500 roebel.
De fabricage van beide producten vereist de kosten van machinale bewerking, grondstoffen en arbeid (Fig. 1). Voor de vervaardiging van elke eenheid van product A worden 3 uur machinale verwerking, 16 eenheden grondstoffen en 6 eenheden arbeid toegewezen. De overeenkomstige vereisten voor eenheid B zijn 10, 4 en 6. Nikolai voorspelt dat hij volgende maand 330 uur bewerking, 400 eenheden grondstoffen en 240 eenheden arbeid kan leveren. De technologie van het productieproces is zodanig dat er in een bepaalde maand minimaal 12 eenheden van product B moeten worden geproduceerd.
Rijst. 1. Gebruik en verstrekking van middelen
Nikolay wil een model bouwen om het aantal eenheden van producten A en B te bepalen dat hij in de komende maand moet produceren om de marginale winst te maximaliseren.
Het lineaire model kan in vier stappen worden opgebouwd.
Fase 1. Definitie van variabelen
Er is een doelvariabele (laten we het Z noemen) die moet worden geoptimaliseerd, dat wil zeggen gemaximaliseerd of geminimaliseerd (bijvoorbeeld winst, inkomsten of uitgaven). Nikolay probeert de marginale winst te maximaliseren, daarom is de doelvariabele:
Z = totale marginale winst (in roebels) ontvangen in de volgende maand als resultaat van de productie van producten A en B.
Er zijn een aantal onbekende onbekende variabelen (we noemen ze x 1, x 2, x 3, enz.), waarvan de waarden moeten worden bepaald om de optimale waarde te verkrijgen objectieve functie, wat in ons geval de totale marginale winst is. Deze contributiemarge is afhankelijk van de hoeveelheid geproduceerde producten A en B. Deze waarden moeten worden berekend en zijn daarom de variabelen die van belang zijn in het model. Dus laten we aangeven:
x 1 = het aantal geproduceerde eenheden van product A in de volgende maand.
x 2 = aantal geproduceerde eenheden van product B in de volgende maand.
Het is erg belangrijk om alles duidelijk te definiëren variabelen; Speciale aandacht let op de meeteenheden en de tijdsperiode waarop de variabelen betrekking hebben.
Fase. 2. Constructie van de doelfunctie
Een objectieve functie is een lineaire vergelijking die gemaximaliseerd of geminimaliseerd moet worden. Het bevat de doelvariabele uitgedrukt in termen van de gewenste variabelen, dwz Z uitgedrukt in termen van x 1 , x 2 ... als een lineaire vergelijking.
In ons voorbeeld levert elk vervaardigd product A 2500 roebel op. marginale winst, en bij de vervaardiging van x 1 eenheden van product A, zal de marginale winst 2500 * x 1 zijn. Evenzo zal de marginale winst van de productie van x 2 eenheden van product B 3500 * x 2 zijn. Dus de totale marginale winst die in de volgende maand wordt ontvangen als gevolg van de productie van x 1 eenheden van product A en x 2 eenheden van product B, dat wil zeggen, de doelvariabele Z zal zijn:
Z = 2500 * x 1 + 3500 * x 2
Nikolay probeert deze indicator te maximaliseren. De doelfunctie in ons model is dus:
Maximaliseer Z = 2500 * x 1 + 3500 * x 2
Fase. 3. Definitie van beperkingen
Beperkingen zijn een systeem lineaire vergelijkingen en/of ongelijkheden die de omvang van de vereiste variabelen beperken. Ze weerspiegelen wiskundig de beschikbaarheid van middelen, technologische factoren, marketingomstandigheden en andere vereisten. Er zijn drie soorten beperkingen: "kleiner dan of gelijk", "groter dan of gelijk", "strikt gelijk".
In ons voorbeeld hebben producten A en B verwerkingstijd, grondstoffen en arbeid nodig om te produceren, en de beschikbaarheid van deze middelen is beperkt. De productievolumes van deze twee producten (d.w.z. x 1 van 2 waarden) zullen dus worden beperkt door het feit dat de hoeveelheid middelen die nodig is in het productieproces niet groter kan zijn dan wat beschikbaar is. Overweeg de situatie met de verwerkingstijd van de machine. De productie van elke eenheid van product A vereist drie uur machinale verwerking en als x 1 eenheden worden geproduceerd, wordt 3 * x 1 uur van deze grondstof besteed. Voor de productie van elke eenheid van product B is 10 uur nodig, dus als er x 2 producten worden geproduceerd, zijn er 10 * x 2 uur nodig. De totale hoeveelheid machinetijd die nodig is om x 1 eenheden van product A en x 2 eenheden van product B te produceren, is dus 3 * x 1 + 10 * x 2 . Deze totale machinetijd mag niet meer dan 330 uur bedragen. Wiskundig wordt dit als volgt geschreven:
3 * x 1 + 10 * x 2 ≤ 330
Soortgelijke overwegingen gelden voor grondstoffen en arbeid, waardoor nog twee beperkingen kunnen worden opgeschreven:
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Ten slotte moet worden opgemerkt dat er een voorwaarde is volgens welke ten minste 12 eenheden van product B moeten worden vervaardigd:
Fase 4. Het schrijven van de voorwaarden van niet-negativiteit
De gewenste variabelen mogen geen negatieve getallen zijn, die moeten worden geschreven als ongelijkheden x 1 ≥ 0 en x 2 ≥ 0. In ons voorbeeld is de tweede voorwaarde overbodig, aangezien hierboven is bepaald dat x 2 niet kleiner kan zijn dan 12.
Compleet lineair programmeermodel voor productie taak Nicolaas kan worden geschreven als:
Maximaliseren: Z = 2500 * x 1 + 3500 * x 2
Op voorwaarde dat: 3 * x 1 + 10 * x 2 ≤ 330
16 * x 1 + 4 * x 2 ≤ 400
6 * x 1 + 6 * x 2 ≤ 240
Overweeg een grafische methode voor het oplossen van een lineair programmeerprobleem.
Deze methode is alleen geschikt voor problemen met twee vereiste variabelen. Het hierboven gebouwde model zal worden gebruikt om de methode te demonstreren.
De assen in de grafiek vertegenwoordigen de twee onbekende variabelen (Fig. 2). Het maakt niet uit welke variabele langs welke as wordt geplot. Het is belangrijk om een schaal te kiezen waarmee je uiteindelijk een visueel diagram kunt bouwen. Aangezien beide variabelen niet-negatief moeten zijn, wordt alleen het eerste kwadrant getekend.
Rijst. 2. Lineaire programmeergrafiekassen
Beschouw bijvoorbeeld de eerste beperking: 3 * x 1 + 10 * x 2 ≤ 330. Deze ongelijkheid beschrijft het gebied onder de lijn: 3 * x 1 + 10 * x 2 = 330. Deze lijn snijdt de x-as 1 bij x 2 \u003d 0, dat wil zeggen, de vergelijking ziet er als volgt uit: 3 * x 1 + 10 * 0 \u003d 330, en de oplossing: x 1 \u003d 330 / 3 \u003d 110
Op dezelfde manier berekenen we de snijpunten met de x 1- en x 2-assen voor alle randvoorwaarden:
| Regio toegestane waarden | Limiet van toegestane waarden | Snijpunt met x-as 1 | Snijpunt met x-as 2 |
| 3 * x 1 + 10 * x 2 ≤ 330 | 3 * x 1 + 10 * x 2 = 330 | x 1 = 110; X 2 = 0 | x 1 = 0; X 2 = 33 |
| 16 * x 1 + 4 * x 2 ≤ 400 | 16 * x 1 + 4 * x 2 = 400 | x 1 = 25; X 2 = 0 | x 1 = 0; × 2 = 100 |
| 6 * x 1 + 6 * x 2 ≤ 240 | 6 * x 1 + 6 * x 2 = 240 | x 1 = 40; X 2 = 0 | x 1 = 0; × 2 = 40 |
| x 2 ≥ 12 | × 2 = 12 | kruist niet; loopt evenwijdig aan de x-as 1 | x 1 = 0; × 2 = 12 |
Grafisch wordt de eerste beperking getoond in Fig. 3.
Rijst. 3. Constructie van het domein van haalbare oplossingen voor de eerste beperking
Elk punt binnen de geselecteerde driehoek of op de randen ervan voldoet aan deze beperking. Dergelijke punten worden geldig genoemd en punten buiten de driehoek worden ongeldig genoemd.
Evenzo geven we de rest van de beperkingen weer op de kaart (Fig. 4). Waarden x 1 en x 2 op of binnen het gearceerde gebied ABCDE voldoen aan alle modelbeperkingen. Zo'n gebied wordt het domein van toelaatbare oplossingen genoemd.
Rijst. 4. Het gebied van haalbare oplossingen voor het model als geheel
Nu, op het gebied van haalbare oplossingen, is het noodzakelijk om de waarden x 1 en x 2 te bepalen die Z maximaliseren. Om dit te doen, in de objectieve functievergelijking:
Z = 2500 * x 1 + 3500 * x 2
we delen (of vermenigvuldigen) de coëfficiënten vóór x 1 en x 2 met hetzelfde getal, zodat de resulterende waarden binnen het bereik vallen dat in de grafiek wordt weergegeven; in ons geval is zo'n bereik van 0 tot 120; dus de coëfficiënten kunnen worden gedeeld door 100 (of 50):
Z = 25x 1 + 35x 2
wijs Z dan een waarde toe die gelijk is aan het product van de coëfficiënten voor x 1 en x 2 (25 * 35 = 875):
875 = 25x 1 + 35x 2
en zoek ten slotte de snijpunten van de lijn met de assen x 1 en x 2:
Laten we deze doelvergelijking op dezelfde manier in de grafiek uitzetten als de beperkingen (Fig. 5):
Rijst. 5. Toepassing van de doelfunctie (zwart stippellijn) naar het domein van toelaatbare oplossingen
De Z-waarde is constant over de doelfunctielijn. Om de waarden van x 1 en x 2 te vinden die Z maximaliseren, moet je de lijn van de doelfunctie parallel overbrengen naar zo'n punt binnen de grenzen van het gebied van haalbare oplossingen, dat zich bevindt op maximale afstand van de oorspronkelijke lijn van de doelfunctie naar boven en naar rechts, dat wil zeggen naar punt C (fig. 6).
Rijst. 6. De lijn van de doelfunctie heeft zijn maximum bereikt binnen het gebied van haalbare oplossingen (bij punt C)
Dat kan worden geconcludeerd optimale oplossing bevindt zich op een van de uiterste punten van het beslisgebied. In welke, hangt af van de helling van de doelfunctie en van welk probleem we oplossen: maximaliseren of minimaliseren. Het is dus niet nodig om een objectieve functie te tekenen - het enige dat nodig is, is om de waarden van x 1 en x 2 op elk van de extreme punten te bepalen door uit het diagram te lezen of door het overeenkomstige paar vergelijkingen op te lossen. De gevonden waarden van x 1 en x 2 worden vervolgens gesubstitueerd in de doelfunctie om de corresponderende waarde van Z te berekenen. De optimale oplossing is die waarbij de maximale waarde van Z wordt verkregen bij het oplossen van het maximalisatieprobleem, en de minimale bij het oplossen van het minimalisatieprobleem.
Laten we bijvoorbeeld de waarden van x 1 en x 2 in punt C bepalen. Merk op dat punt C op het snijpunt van de lijnen ligt: 3x 1 + 10x 2 = 330 en 6x 1 + 6x 2 = 240. De oplossing van dit stelsel vergelijkingen geeft: x 1 = 10, x 2 = 30. De berekeningsresultaten voor alle hoekpunten van het gebied van haalbare oplossingen staan in de tabel:
| Punt | Waarde x 1 | Waarde x 2 | Z \u003d 2500x 1 + 3500x 2 |
| A | 22 | 12 | 97 000 |
| IN | 20 | 20 | 120 000 |
| MET | 10 | 30 | 130 000 |
| D | 0 | 33 | 115 500 |
| E | 0 | 12 | 42 000 |
Nikolai Kuznets moet dus plannen maken volgende maand productie van 10 producten A en 30 producten B, waarmee hij een marginale winst van 130 duizend roebel kan ontvangen.
In het kort de essentie grafische methode oplossingen lineair programmering kan als volgt worden samengevat:
- Teken twee assen in de grafiek die twee beslissingsparameters vertegenwoordigen; teken alleen het eerste kwadrant.
- Bepaal de coördinaten van de snijpunten van alle randvoorwaarden met de assen, en vervang de waarden x 1 = 0 en x 2 = 0 beurtelings in de vergelijkingen van de randvoorwaarden.
- Teken modelbeperkingslijnen op de grafiek.
- Bepaal het gebied op de grafiek (het toegestane beslissingsgebied genoemd) dat aan alle beperkingen voldoet. Als zo'n regio niet bestaat, heeft het model geen oplossing.
- Bepaal de waarden van de gewenste variabelen op de uiterste punten van het beslissingsgebied en bereken telkens de overeenkomstige waarde van de doelvariabele Z.
- Voor maximalisatieproblemen is de oplossing het punt waarop Z maximaal is; voor minimalisatieproblemen is de oplossing het punt waarop Z minimaal is.
objectieve functie- reële of gehele functie van verschillende variabelen, onderhevig 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 een wiskundig probleem zelf kan zijn. Naast de doelfunctie kunnen variabelen in het optimalisatieprobleem onderhevig zijn aan beperkingen in de vorm van een stelsel van gelijkheden of ongelijkheden. In het algemeen kunnen de objectieve functie-argumenten worden gespecificeerd op willekeurige verzamelingen.
Voorbeelden
Gladde functies en stelsels van vergelijkingen
Het probleem van het oplossen van elk stelsel 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 doelfunctie
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 gradiëntmethoden.
Voor elke gladde doelfunctie kan men de partiële afgeleiden met betrekking tot alle variabelen gelijkstellen aan 0 (\displaystyle 0). De optimale doelfunctie zal een van de oplossingen zijn voor zo'n stelsel vergelijkingen. In het geval van functie (1) (\displaystyle (1)) zal dit een stelsel van kleinste kwadraten (LSM) vergelijkingen zijn. Elke beslissing origineel systeem is een oplossing van het kleinste kwadratenstelsel. Als het oorspronkelijke systeem inconsistent is, maakt het LSM-systeem, dat altijd een oplossing heeft, het mogelijk om een benaderende oplossing van het oorspronkelijke systeem te verkrijgen. Het aantal vergelijkingen van het LSM-systeem valt samen met het aantal onbekenden, wat soms de oplossing van gezamenlijke initiële systemen vergemakkelijkt.
Lineair programmeren
Ander beroemd voorbeeld objectieve functie is een lineaire functie die voorkomt in 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 doelfunctie is de doelfunctie van het handelsreizigersprobleem. Deze functie is gelijk aan de lengte van de Hamiltoniaanse cyclus op de grafiek. Het wordt gegeven op de permutatieset n − 1 (\displaystyle n-1) van graafhoekpunten en wordt bepaald door de randlengtematrix van de graaf. De exacte oplossing van dergelijke problemen komt vaak neer op een opsomming van opties.
Hoofdstuk 1. Verklaring van het belangrijkste probleem van lineair programmeren
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 een lineaire toets. Dergelijke taken vinden uitgebreide toepassingen op verschillende terreinen van menselijke activiteit. Een systematische studie van dit soort problemen begon in 1939-1940. in de werken van L.V. Kantorovitsj.
De wiskundige problemen van lineaire programmering omvatten de studie van specifieke productie- en economische situaties, die op de een of andere manier worden geïnterpreteerd als problemen over optimaal gebruik beperkte middelen.
Het scala aan problemen dat met behulp van lineaire programmeermethoden kan worden opgelost, is vrij breed, bijvoorbeeld:
het probleem van het optimale gebruik van middelen bij de productieplanning;
het probleem van mengsels (planning van de samenstelling van producten);
de taak van het vinden optimale combinatie verschillende soorten producten voor opslag in magazijnen (voorraadbeheer of);
transporttaken (analyse van de locatie van de onderneming, goederenbewegingen).
Lineair programmeren is het meest ontwikkelde en meest gebruikte onderdeel van wiskundig programmeren (daarnaast omvat dit: integer, dynamisch, niet-lineair, parametrisch programmeren). Dit wordt als volgt uitgelegd:
wiskundige modellen een groot aantal economische taken lineair ten opzichte van de vereiste variabelen;
dit soort problemen is momenteel het meest bestudeerd. Voor hem zijn speciale methoden ontwikkeld waarmee deze problemen worden opgelost, en de bijbehorende computerprogramma's;
veel problemen van lineaire programmering, die zijn opgelost, hebben een brede toepassing gevonden;
sommige problemen die niet lineair zijn in de oorspronkelijke formulering, na een reeks aanvullende beperkingen en aannames kunnen lineair worden of kunnen worden teruggebracht tot een zodanige vorm 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 stelsel van lineaire vergelijkingen of ongelijkheden; vereiste van niet-negativiteit van variabelen.
IN algemeen beeld het model is als volgt geschreven:
objectieve functie
(1.1) onder de beperkingen
(1.2) niet-negativiteitsvereisten
(1.3) waar X J– variabelen (onbekenden);
- coëfficiënten van het lineaire programmeerprobleem.
Het probleem is om de optimale waarde van de functie (1.1) te vinden met inachtneming van de beperkingen (1.2) en (1.3).
Het systeem van beperkingen (1.2) wordt de functionele beperkingen van het probleem genoemd, en de beperkingen (1.3) worden directe beperkingen genoemd.
Een vector die voldoet aan de voorwaarden (1.2) en (1.3) wordt een haalbare oplossing (plan) van een lineair programmeerprobleem genoemd. Het plan waarvoor de functie (1.1) zijn maximale (minimum) waarde bereikt, wordt optimaal genoemd.
1.2. Simplexmethode voor het oplossen van lineaire programmeerproblemen
De simplex-methode is ontwikkeld en voor het eerst toegepast om problemen op te lossen in 1947 door de Amerikaanse wiskundige J. Danzig.
Tweedimensionale lineaire programmeerproblemen worden grafisch opgelost. Voor het geval N=3 kunnen we een driedimensionale ruimte beschouwen en de doelfunctie zal zijn optimale waarde bereiken op een van de hoekpunten van het veelvlak.
Een toelaatbare oplossing (een toelaatbaar plan) van het gegeven LP-probleem standaard vorm, is een geordende reeks getallen (x1, x2, ..., xn) die voldoen aan de beperkingen; is een punt in de n-dimensionale ruimte.
De set van toelaatbare oplossingen vormt het gebied van toelaatbare oplossingen (SDR) van het LP-probleem. ODR is een convex veelvlak (polygoon).
In algemene termen, wanneer N-onbekenden bij het probleem betrokken zijn, kunnen we zeggen dat het gebied van haalbare oplossingen gespecificeerd door het systeem van beperkende voorwaarden wordt weergegeven door een convex veelvlak in n-dimensionale ruimte en de optimale waarde van het doel functie wordt bereikt op een of meerdere hoekpunten.
Een oplossing wordt basis genoemd als alle vrije variabelen gelijk zijn aan nul.
Een referentieoplossing is een basis niet-negatieve oplossing. De ondersteuningsoplossing kan niet-gedegenereerd en gedegenereerd zijn. Een ondersteuningsoplossing wordt niet-gedegenereerd genoemd als het aantal niet-nul coördinaten gelijk is aan de rang van het systeem, anders is het gedegenereerd.
Een haalbare oplossing, waarin de doelfunctie zijn uiterste waarde bereikt, wordt optimaal genoemd en aangeduid 
.
Het is erg moeilijk om deze problemen grafisch op te lossen als het aantal variabelen meer dan 3 is. bestaat universele manier het oplossen van lineaire programmeerproblemen, de simplex-methode genoemd.
De simplexmethode is universele methode het oplossen van LP-problemen, wat een iteratief proces is 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 simplex-methode is gebaseerd op het idee van opeenvolgende verbetering van de resulterende oplossing.
De geometrische betekenis van de simplex-methode bestaat uit een sequentiële overgang van het ene hoekpunt van het constraint-veelvlak naar het naburige, waarbij de objectieve functie de beste is (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 eindig optimum heeft).
Dus het hebben van een systeem van beperkingen teruggebracht tot canonieke vorm(alle functionele beperkingen zijn in de vorm van gelijkheden), vind een willekeurige basisoplossing van dit systeem en zorg ervoor dat u deze zo eenvoudig mogelijk vindt. Als de eerst gevonden basisoplossing haalbaar blijkt te zijn, wordt deze gecontroleerd op optimaliteit. Is deze niet optimaal, dan wordt overgegaan naar een andere, noodzakelijkerwijs toelaatbare, basisoplossing. De simplex-methode garandeert dat, met deze nieuwe oplossing, de objectieve functie, als deze het optimum niet bereikt, deze nadert (of er in ieder geval niet vanaf beweegt). Bij een nieuwe toelaatbare basisoplossing wordt hetzelfde gedaan totdat er een optimale oplossing is gevonden.
Het proces van het toepassen van de simplex-methode omvat de implementatie van de drie hoofdelementen:
een methode om een initiële haalbare basisoplossing voor het probleem te bepalen;
de overgangsregel naar de beste (meer precies, niet de slechtste) oplossing;
criterium voor het controleren van de optimaliteit van de gevonden oplossing.
De simplexmethode omvat een aantal stappen en kan worden geformuleerd als een duidelijk algoritme (een duidelijke instructie om sequentiële bewerkingen uit te voeren). Hierdoor kunt u het met succes op een computer programmeren en implementeren. Taken met weinig variabelen en beperkingen kunnen worden opgelost simplex-methode handmatig.
6.1 Inleiding
optimalisatie. Deel 1
Met optimalisatiemethoden kunt u kiezen de beste optie ontwerpen van allemaal opties. IN afgelopen jaren deze methoden werden gegeven 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 grondbeginselen van de optimalisatietheorie, beschouwt 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 optimalisatietheorie
De term "optimalisatie" in de literatuur verwijst naar een proces of reeks bewerkingen waarmee u een verfijnde oplossing kunt krijgen. Hoewel het uiteindelijke doel van optimalisatie het vinden van de beste of "optimale" oplossing is, moet je meestal genoegen nemen met verbeteren bekende oplossingen in plaats van ze te perfectioneren. Daarom wordt optimalisatie eerder opgevat als het streven naar perfectie, wat misschien niet zal worden 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. Zo'n probleem heeft meestal één oplossing. Als m>n, dan wordt het probleem opnieuw gedefinieerd en heeft het in de regel geen oplossing. Eindelijk voor m
Voordat we overgaan tot de bespreking van optimalisatievraagstukken, introduceren we een aantal definities.
Ontwerpparameters
Deze term duidt onafhankelijke variabele parameters aan die het ontwerpprobleem dat wordt opgelost volledig en ondubbelzinnig definiëren. Ontwerpparameters zijn onbekende grootheden waarvan de waarden worden berekend tijdens het optimalisatieproces. Alle basis- of afgeleide grootheden die dienen om het systeem kwantitatief te beschrijven, kunnen als ontwerpparameters dienen. Het kunnen dus onbekende waarden zijn van lengte, massa, tijd, temperatuur. Het aantal ontwerpparameters kenmerkt de mate van complexiteit van dit ontwerpprobleem. Gewoonlijk wordt het aantal ontwerpparameters aangeduid met n, en de ontwerpparameters zelf met x met de bijbehorende indices. Dus zullen n ontwerpparameters van dit probleem worden aangeduid met
X1, x2, x3,...,xn.
objectieve functie
Dit is de uitdrukking waarvan de ingenieur de waarde probeert te maximaliseren of te minimaliseren. Met de doelfunctie kunt u er twee kwantitatief vergelijken alternatieve oplossingen. Vanuit wiskundig oogpunt beschrijft de objectieve functie een (n + 1) - dimensionaal oppervlak. De waarde wordt bepaald door de ontwerpparameters
M=M(x 1 , x 2 ,...,x n).
Voorbeelden van de doelfunctie, vaak aangetroffen in de ingenieurspraktijk, zijn kosten, gewicht, sterkte, afmetingen, efficiëntie. Als er slechts één ontwerpparameter is, kan de doelfunctie worden weergegeven door een kromme in een vlak (Fig. 6.1). Als er twee ontwerpparameters zijn, wordt de doelfunctie weergegeven door een oppervlak in de ruimte met drie dimensies (Fig. 6.2). Met drie of meer ontwerpparameters worden de oppervlakken gespecificeerd door de doelfunctie hyperoppervlakken genoemd en kunnen ze niet worden afgebeeld.
zheniya conventionele middelen. De topologische eigenschappen van het doelfunctie-oppervlak spelen een belangrijke rol in het optimalisatieproces, aangezien de keuze van het meest efficiënte algoritme hiervan afhangt.
De doelfunctie kan in sommige gevallen de meest onverwachte vormen aannemen. Het is bijvoorbeeld niet altijd mogelijk om het in uit te drukken
Fig. 1. Eendimensionale doelfunctie.
Fig.6.2.Tweedimensionale objectieffunctie.
gesloten wiskundige vorm, in andere gevallen kan het
een stuksgewijs gladde functie zijn. Een objectieve functie kan soms een technische gegevenstabel vereisen (bijvoorbeeld een stoomstatustabel) of het kan nodig zijn om een experiment uit te voeren. In sommige gevallen nemen ontwerpparameters alleen gehele waarden aan. Een voorbeeld is het aantal tanden in een tandwiel of het aantal bouten in een flens. Soms hebben ontwerpparameters slechts twee waarden: ja of nee. Kwaliteitsparameters, zoals klanttevredenheid, betrouwbaarheid, esthetiek, zijn moeilijk mee te nemen in het optimalisatieproces, omdat ze bijna niet te kwantificeren zijn. In welke vorm de doelfunctie ook wordt gepresenteerd, het moet echter een eenwaardige functie van de ontwerpparameters zijn.
Bij een aantal optimalisatieproblemen is de introductie van meer dan één doelfunctie vereist. Soms is de een onverenigbaar met de ander. Een voorbeeld is het ontwerp van vliegtuigen, wanneer het nodig is om tegelijkertijd maximale sterkte, minimaal gewicht en minimale kosten te bieden. In dergelijke gevallen moet de ontwerper een systeem van prioriteiten invoeren en een dimensieloze vermenigvuldiger toekennen aan elke doelfunctie. Als gevolg hiervan verschijnt een "compromisfunctie", waarmee één samengestelde doelfunctie kan worden gebruikt in het optimalisatieproces.
Het vinden van het minimum en maximum
Sommige optimalisatie-algoritmen zijn aangepast om het maximum te vinden, andere om het minimum te vinden. Ongeacht het type extremumprobleem dat wordt opgelost, kan echter hetzelfde algoritme worden gebruikt, aangezien het minimalisatieprobleem gemakkelijk kan worden omgezet in een maximaal bevindingsprobleem door het teken van de doelfunctie 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 beperkt is tot een aantal
omstandigheden die verband houden met de fysieke essentie van het probleem. Beperkingen kunnen zo sterk zijn dat de taak er geen heeft
Figuur 6.3 Het teken van de doelfunctie veranderen in het tegenovergestelde
De maximale taak wordt de minimale taak.
bevredigende oplossing. Beperkingen zijn verdeeld in twee groepen: beperkingen - gelijkheden en beperkingen - ongelijkheden.
Beperkingen - gelijkheid
Beperkingen - gelijkheden - is de afhankelijkheid tussen ontwerpparameters waarmee rekening moet worden gehouden bij het vinden van een oplossing. Ze weerspiegelen de natuurwetten, economie, rechten, heersende smaken en beschikbaarheid benodigde 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, kunt u deze parameter uitsluiten van het optimalisatieproces. Dit vermindert het aantal dimensies van de ontwerpruimte en vereenvoudigt de oplossing van het probleem.
Beperkingen - ongelijkheden
Dit is een speciaal soort beperking die tot uiting komt in ongelijkheden. In het algemeen kan er een willekeurig aantal zijn 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 heel vaak de optimale waarde van de doelfunctie niet wordt bereikt wanneer het oppervlak een nulgradiënt heeft. Vaak De beste beslissing komt overeen met een van de grenzen van het ontwerpgebied.
Lokaal optimum
Dit is de naam van het punt in de ontwerpruimte waar de doelfunctie zich bevindt hoogste waarde vergeleken met zijn waarden op alle andere punten in zijn directe omgeving.
Figuur 6.4 Een willekeurige doelfunctie kan er meerdere hebben
lokale optima.
Op afb. Figuur 6.4 toont een eendimensionale doelfunctie met twee lokale optima. Vaak bevat de ontwerpruimte veel lokale optima en moet ervoor worden gezorgd dat de eerste niet wordt aangezien voor de optimale oplossing van het probleem.
Wereldwijd Optimaal
Het globale optimum is de optimale oplossing voor de gehele ontwerpruimte. Het is beter dan alle andere oplossingen die overeenkomen met lokale optima, en dit is waar de ontwerper naar op zoek is. Het geval van meerdere gelijke globale optima gelegen in verschillende delen ontwerp ruimte. Hoe het optimalisatieprobleem wordt gesteld, kan het best worden geïllustreerd aan de hand van een voorbeeld.
Voorbeeld 6.1
Laat het nodig zijn om een rechthoekige container te ontwerpen met een inhoud van 1 m , ontworpen om onverpakte vezels te vervoeren. 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), aangezien dit goedkoper zal zijn. Om de container gemakkelijk met een vorkheftruck te kunnen nemen, moet de breedte minimaal 1,5 m zijn.
Laten we dit probleem formuleren in een vorm die handig is voor het toepassen van het optimalisatie-algoritme.
Ontwerpparameters: x 1 , x 2 , x 3 .
De objectieve functie (die moet worden geminimaliseerd) 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 \u003d x 1 x 2 x 3 \u003d 1m3.
Beperking - ongelijkheid:
Lineaire programmeerproblemen
Lineaire programmering (LP) is een van de secties van wiskundig programmeren - een discipline die extreme (optimalisatie)problemen bestudeert en methoden ontwikkelt om ze op te lossen.
Optimalisatie probleem- Dit wiskundig probleem, die 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 acceptabele waarden (ODV) behoren.
Over het algemeen bestaat de formulering van een extreem probleem van wiskundig programmeren uit het bepalen van de grootste of de kleinste waarde een functie genaamd objectieve functie, onder voorwaarden (beperkingen) , waar en – voorgedefinieerde functies, en krijgen constanten. Tegelijkertijd bepalen beperkingen in de vorm van gelijkheden en ongelijkheden de set (regio) van haalbare oplossingen (ODS), en worden ze genoemd ontwerp parameters.
Afhankelijk van het type functies en problemen van wiskundig programmeren zijn ze onderverdeeld in een aantal klassen (lineair, niet-lineair, convex, integer, stochastisch, dynamisch programmeren en etc.).
IN algemeen beeld LP probleem heeft volgende weergave:
, (5.1)
, , (5.2)
, 
, (5.3)
waar , , constanten zijn.
Functie (5.1) wordt de doelfunctie genoemd; systemen (5.2), (5.3) - door een systeem van beperkingen; voorwaarde (5.4) is de voorwaarde van niet-negativiteit van ontwerpparameters.
De verzameling ontwerpparameters die voldoen aan de voorwaarden (5.2), (5.3) en (5.4) wordt genoemd aanvaardbare oplossing of plan.
De optimale oplossing of optimale planning LP-probleem wordt een haalbare oplossing genoemd, waarin de doelfunctie (5.1) de optimale (maximale of minimale) waarde aanneemt.
Standaard taak LP wordt het probleem genoemd van het vinden van de maximale (minimum) waarde van de doelfunctie (5.1) onder de 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 niet-negativiteitsvoorwaarde, en er zijn geen voorwaarden in de vorm van gelijkheden:
,
, , (5.5)
.
Canonieke (hoofd)taak De LP wordt het probleem genoemd van het vinden van de maximale (minimum) waarde van de doelfunctie (5.1) onder de 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 niet-negativiteitsvoorwaarde, en er zijn geen voorwaarden in de vorm van ongelijkheden:
,
.
Het canonieke LP-probleem kan ook in matrix- en vectorvorm worden geschreven.
matrix vorm canoniek probleem De LP heeft de volgende vorm:
Vectorvorm van het canonieke LP-probleem.
De doelfunctie is een wiskundige weergave van de afhankelijkheid van het optimaliteitscriterium van de gewenste variabelen.2. Gradiëntfunctie.
Een vector waarvan de componenten de waarden zijn van partiële afgeleiden, dat wil zeggen de vector
heet de gradiënt van de functie berekend op een punt.
3. Het algemene probleem van lineaire programmering.
De standaard wiskundige formulering van het algemene lineaire programmeerprobleem ziet er als volgt uit: u moet de uiterste waarde van de prestatie-indicator vinden (objectieve functie)
(lineaire functie van oplossingselementen) onder lineaire beperkende voorwaarden opgelegd aan oplossingselementen:
waar worden getallen gegeven. 
4. Standaard lp-probleem.
In zijn standaardvorm is een lineair programmeerprobleem een maximum (minimum) probleem voor een lineaire doelfunctie. Het systeem van beperkingen bestaat uit één lineaire ongelijkheden typ "<= » или « >= ". Alle taakvariabelen zijn niet negatief.
Elk lineair programmeerprobleem kan worden geformuleerd in termen van standaard vorm. De transformatie van het minimale probleem in het maximale probleem, evenals het waarborgen van de niet-negativiteit van de variabelen, wordt op dezelfde manier uitgevoerd als voorheen. Elke gelijkheid in het systeem van restricties staat gelijk aan een systeem van onderling tegengestelde ongelijkheden:
Er zijn andere manieren om een systeem van gelijkheden te transformeren in een systeem van ongelijkheden, d.w.z. elk lineair programmeerprobleem kan in een standaardvorm worden geformuleerd.
2 antwoordmogelijkheden:
Standaard LP probleem.
of, in matrixnotatie, waar is de matrix van coëfficiënten. De vector wordt de vector van coëfficiënten van de lineaire vorm genoemd, de beperkingsvector.
5. Het canonieke lp-probleem.
IN canonieke vorm het probleem is een probleem voor het maximum (minimum) van een lineaire functie F , het systeem van beperkingen bestaat alleen uit gelijkheden (vergelijkingen). Tegelijkertijd taakvariabelen X 1 , X 2 , ..., X N zijn niet negatief:
|
| |
Elk lineair programmeerprobleem kan worden omgezet in een canonieke vorm.
Een korte samenvatting van het canonieke LP-probleem:
X=(x1, x2, ..., xn), C=(c1, c2, ..., cn).
2 antwoordmogelijkheden:
Het canonieke LP-probleem.
of, in matrixnotatie,
6. Symmetrische en asymmetrische duale problemen.
Het dubbele probleem van lineair programmeren. Beschouw het LP-probleem 
(1) of, in matrixnotatie, (2) Het duale probleem van (1) (het duale probleem) is het LP-probleem in variabelen 
(3) of, in matrixnotatie, (4) waar 
. De regels voor het construeren van probleem (3) volgens de vorm van schrijfprobleem (1) zijn als volgt: in probleem (3)
er zijn evenveel variabelen als rijen in de taakmatrix (1). De beperkingsmatrix in (3) is een getransporteerde matrix. De vector van de rechterkant van de beperkingen in (3) dient als de vector van de coëfficiënten van de lineaire vorm die wordt gemaximaliseerd in (1), terwijl de tekens van de ongelijkheden veranderen in gelijkheid. Integendeel, de objectieve functie in (3) is een lineaire vorm, waarvan de coëfficiënten worden gegeven door de vector van de rechterkant van de beperkingen van probleem (1), terwijl maximalisatie overgaat in minimalisatie. De niet-negativiteitsvoorwaarde wordt opgelegd aan dubbele variabelen. Probleem (1) wordt, in tegenstelling tot het duale probleem (3), direct genoemd. Dualiteitsstelling. Als wederzijds duale problemen (2), (4) toelaatbaar zijn, dan hebben ze allebei een oplossing en dezelfde waarde.
Symmetrische dubbele problemen
Een verscheidenheid aan duale problemen van lineaire programmering zijn duale symmetrische problemen, waarbij het systeem van beperkingen van zowel de oorspronkelijke als de duale problemen wordt gegeven door ongelijkheden, en de niet-negatieve voorwaarde wordt opgelegd aan de duale variabelen.
Om het maximum van de doelfunctie te vinden, gebruikt u de functie maximaliseren, waarvan de indeling maximaliseren(<функция>, <система ограничений>, <опции>);
In dit geval wordt de voorwaarde van niet-negativiteit van variabelen handig aangegeven door de optie NIET-NEGATIEF.
> optimum:=maximaliseren(f,syst_ogr,NONNEGATIEF);
Gebruik de opdracht subs, waarmee u variabele waarden kunt vervangen X 1 en X 2 per functie F.
> fmax:=subs(x1=83/17,x2=19/17,f);
Gebruik de functie evalf om het antwoord weer te geven als een reëel getal met 4 significante cijfers.
> fmax:=elf(fmax,4);
U kunt kennis maken met de variant van het oplossen van het LP-probleem zonder uitleg in de bijlage.
Oplossing van optimalisatieproblemen in een gespecialiseerd pakket SimplexWin. http://www.Simplexwin.Narod.Ru/
Dit programma is ontworpen om lineaire programmeerproblemen op te lossen met behulp van de simplex-methode.
Taak. Zoek variabele waarden X 1 En X 2, waarop
onder beperkingen
Werkorder:
Start het programma SimplexWin en stel de vereiste grootte van de beperkingsmatrix in door de menuopdracht Instellingen - Matrixgrootte te selecteren (Fig. 13).
Rijst. 13. Bepalen van de grootte van de matrix.
Voer de gegevens in (Fig. 14). Als het probleem niet in canonieke vorm wordt geïntroduceerd, dan worden aanvullende variabelen en kunstmatige bases(evenals de objectieve functiecoëfficiënten die daarmee overeenkomen) worden automatisch toegevoegd.
Afb.14. Gegevensinvoer.
II. Het vinden van het optimale plan en de optimale waarde van de doelfunctie.
Rijst. 15. Formulier resultaten.
Klik in het formulier Resultaten op de knop Resultaat, waarmee u het probleem kunt oplossen in automatische modus en laat de nieuwste zien enkelvoudige tafel en het resultaat (fig. 16).
Rijst. 16. De oplossing van het probleem.
Oplossen van optimalisatieproblemen inuitblinken
Beschouw een voorbeeld van bevinding voor het volgende lineaire programmeerprobleem.
Taak. Zoek variabele waarden X 1 En X 2, waarop
onder beperkingen
Werkorder:
I. Registratie van initiële gegevens.
Maak een schermformulier voor het invoeren van de voorwaarden van het probleem (variabelen, objectieve functie, beperkingen) en voer de initiële gegevens erin in (objectieve functiecoëfficiënten, coëfficiënten voor variabelen in de beperkingen, rechterdelen van de beperkingen) (Fig. 17).
Rijst. 17. Schermformulier van de taak (cursor in cel D6).
Opmerking: In het schermformulier in afb. Elke variabele en elke coëfficiënt van de taak wordt toegewezen aan een specifieke cel in Excel. Taakvariabelen komen dus bijvoorbeeld overeen met cellen B3 ( 
), C3 ( 
), komen de objectieve functiecoëfficiënten overeen met cellen B6 ( 
), C6 ( 
), komen de juiste delen van de beperkingen overeen met cellen F10 ( 
), F11 ( 
),F12 ( 
)enz.
Voer de afhankelijkheden van het wiskundige model in het schermformulier in, d.w.z. voer de formule in voor het berekenen van de doelfunctie en de formule voor het berekenen van de waarden van de linkerdelen van de beperkingen.
Afhankelijk van de toestand van het probleem wordt de waarde van de doelfunctie bepaald door de uitdrukking 
. Met behulp van de notatie van de overeenkomstige cellen in Excel kan de formule voor het berekenen van de doelfunctie worden geschreven als som van werken elk van de cellen gereserveerd voor de waarden van de taakvariabelen (B3, C3) naar de overeenkomstige cellen gereserveerd voor de coëfficiënten van de doelfunctie (B6, C6).
Om de afhankelijkheidsformule voor de doelfunctie in te stellen, doet u het volgende :
- plaats de cursor in de cel D6;
- open raam Functiewizard - stap 1 van 2 door op de knop te drukken 
op standaard paneel hulpmiddelen;
- in het raam Functie functie selecteren SUMPRODUCT;
- in het venster dat verschijnt SUMPRODUCT tot een snaar Reeks 1 voer een uitdrukking in € 3: € 3, en in een rij Reeks 2- uitdrukking B6:C6;
- druk op de knop OK.
Rijst. 18. De formule invoeren voor het berekenen van het digitale filter in het venster Functie-assistent.
Na het invoeren van cellen in rijen Reeks 1 En Reeks 2 in het raam SUMPRODUCT zal verschijnen numerieke waarden ingevoerde arrays (Fig. 18), en het schermformulier zal de huidige waarde weergeven die is berekend door de ingevoerde formule, dat wil zeggen 0 (omdat op het moment dat de formule wordt ingevoerd, de waarden van de taakvariabelen nul zijn) (Fig. 19).
Opmerking: Het $-symbool voor het regelnummer betekent dat wanneer u deze formule naar andere plaatsen in het Excel-werkblad kopieert, regelnummer 3 niet verandert. Symbool : betekent dat de formule alle cellen gebruikt die zich tussen de cellen links en rechts van de dubbele punt bevinden.
De linker delen van de probleembeperkingen zijn som van werken elk van de cellen gereserveerd voor de waarden van de taakvariabelen (B3, C3) naar de overeenkomstige cel gereserveerd voor de coëfficiënten van een bepaalde beperking (B10, C10 - 1 beperking; B11, C11 - 2 beperking; B12, C12 - 3 beperking).
De formules die de linkerdelen van de taakbeperkingen definiëren, verschillen van elkaar en van de formule in de doelcel D6 alleen het regelnummer in de tweede array. Dit aantal wordt bepaald door de regel waarop de beperking op het scherm is geschreven. Om afhankelijkheden voor de linkerdelen van de beperking in te stellen, volstaat het om de formule van de doelcel naar de cellen van de linkerdelen van de beperking te kopiëren.
Ga als volgt te werk om de waarden van de linkerdelen van de beperkingen te berekenen:
- plaats de cursor in de cel D6 en kopieer de inhoud van de cel naar het klembord (door op Ctrl + C te drukken);
– plaats de cursor op zijn beurt in de velden van het linkerdeel van elk van de beperkingen, dat wil zeggen D10 ,D11 , D12 en plak de inhoud van de buffer in deze velden (met de toetsen Ctrl + V) (in dit geval verandert het aantal cellen in de tweede matrix van de formule in het nummer van de regel waarin de invoeging is gemaakt van de buffer).
Na het invoeren op het scherm in de velden D10 ,D11 , D12 0 (nulwaarde) verschijnt (Fig. 19).
Rijst. 19. Schermvorm van de taak na water
alle benodigde formules.
Controleer de juistheid van de ingevoerde formules.
Voor deze:
- doe het opeenvolgend dubbele tik de linkermuisknop op de cellen met formules, terwijl de cellen die in de formule worden gebruikt op het scherm worden gemarkeerd (Fig. 20 en Fig. 21).
Rijst. 20
formules in de doelcel D6.
Rijst. 20. Controleren van de juistheid van de inleiding
formules in cel D10 voor de linkerkant van de beperkingen.
Specificeer de doelfunctie en voer beperkingen in het venster in Een oplossing vinden(Afb. 21).
Voor deze:
- plaats de cursor in de cel D6;
- open raam Een oplossing vinden door te selecteren in de werkbalk Gegevens - Een oplossing vinden;
- plaats de cursor in het veld Stel doelcel in;
- voer het adres van de doelcel in $D$6 of maak een enkele klik met de linkermuisknop op de doelcel in het scherm, wat gelijk staat aan het invoeren van het adres via het toetsenbord;
– geef de optimalisatierichting van de doelfunctie aan door eenmaal met de linkermuisknop op de selectieknop te klikken maximale waarde;
- in het raam Beslissingen opzoeken in het veld Veranderende cellen voer cellen in met variabele waarden $B$3:$C$3 door ze in het scherm te selecteren door de linkermuisknop ingedrukt te houden;
Rijst. 21. Het venster Zoeken naar een oplossing.
- druk op de knop Toevoegen;
– in overeenstemming met de toestand van het probleem, selecteer het vereiste teken in het tekenveld, bijvoorbeeld voor 1 beperking is dit het teken 
;
- in het veld Beperking voer bijvoorbeeld het adres in van de cel aan de rechterkant van de beperking in kwestie $ F $ 10;
– leg op dezelfde manier de relatie vast tussen de rechter- en linkerdelen van andere beperkingen ( $D$11
$F$11
,
$D$12
$F$12)
;
– bevestig de invoer van alle vermelde voorwaarden door op de knop te drukken OK(afb. 22 en afb. 23).
Rijst. 22. Een voorwaarde toevoegen.
Opmerking: Als het bij het invoeren van een taakconditie noodzakelijk wordt om de geïntroduceerde beperkingen te wijzigen of te verwijderen, dan kan dit worden gedaan door op de knoppen te klikken Wijziging of Verwijderen.
De actie van het systeem, zijn gedrag wordt niet alleen gekenmerkt door de vaststelling van het feit van het bereiken van het doel, maar ook door de mate van verwezenlijking ervan, bepaald door de objectieve functie.
objectieve functie - is een algemene indicator van het systeem, die de mate kenmerkt waarin het systeem zijn doel bereikt. Het samenstellen van een objectieve functie is er een van kritieke taken bij het ontwerpen van het systeem. Er is echter geen algemene theorie voor het construeren van objectieve functies, er zijn slechts enkele aanbevelingen.
De doelfunctie wordt samengesteld volgens de instructies van de TOR op het optimalisatiecriterium door de externe parameters van het systeem en de beperkingen daarop te analyseren.
De doelfunctie moet in wezen afhankelijk zijn van externe parameters of een deel daarvan. Anders heeft optimalisatie voor deze doelfunctie geen zin. De objectieve functie vertegenwoordigt een vector in M-dimensionale ruimte van externe parameters van het systeem
Meestal wordt de doelfunctie gespecificeerd in scalaire vorm.
De volgende vier doelfunctievormen worden gebruikt.
1. De meest gebruikte objectieve functie van één externe parameter
In dit geval is de objectieve functie eenvoudigweg gelijk aan een van de externe parameters of de reciproque
Ander ( M– 1) externe parameters worden omgezet in een systeem van restricties.
De fysieke betekenis van de objectieve functie van de gereduceerde typen is dat hoe groter (of kleiner) de parameter j i, hoe beter ceteris paribus dit systeem, en de gelijkheid van andere voorwaarden wordt begrepen in de zin van beperkingen op de overige externe parameters. Typische problemen bij de gereduceerde vorm van de doelfunctie: optimalisatie van het systeem in termen van betrouwbaarheid ( j = P(T)), ruisimmuniteit, kosten en andere externe parameters. Zo'n objectieve functie heeft een duidelijke fysieke (technische of economische) betekenis, kenmerkt objectief het systeem en wordt daarom vaak gebruikt. Dat wil zeggen, in dit geval is de doelfunctie een externe parameter van het systeem. Het wordt de objectieve functie van het systeem genoemd. Dit kunnen zijn: nauwkeurigheid, snelheid, tijd, kosten, betrouwbaarheid, gewicht, afmetingen, een soort technologische indicator, enz.
2. De tweede vorm van de doelfunctie is de som van parameters van dezelfde dimensie of de som van functies van deze parameters
Deze vorm is typerend voor optimalisatie volgens economische criteria, volgens complexiteitscriteria, enz.
Bij het minimaliseren van de jaarlijkse huidige kosten van het systeem, is de doelfunctie bijvoorbeeld de som van twee externe parameters: jaarlijkse bedrijfskosten en kapitaalkosten gerelateerd aan de terugverdientijd van het systeem. In dit geval is elk van deze externe parameters van het systeem complexe functie zijn interne (te vinden) parameters.
De objectieve functies van optimalisatieproblemen volgens het complexiteitscriterium hebben ook de tweede vorm, omdat ze worden gepresenteerd als de som van de complexiteit van individuele subsystemen of blokken van het systeem.
3. De derde vorm van de doelfunctie - de gerangschikte vorm - is een geordende set objectieve functies van de eerste vorm met prioriteiten
De eerste doelfunctie is de belangrijkste, de laatste doelfunctie de minst belangrijke.
In een bepaald geval wordt de doelfunctie van dit type als volgt geschreven:
Een voorbeeld van ranking is (bijvoorbeeld) zo'n opeenvolging van objectieve functies: nauwkeurigheid, betrouwbaarheid, kosten. De betekenis van de objectieve functie van de derde vorm is als volgt. De belangrijkste - de eerste in rang - wordt als sommigen erkend i-de parameter van het systeem - j i(bijvoorbeeld nauwkeurigheid). Als een systeem dit heeft i De e parameter is groter dan die van alle andere systemen, en ongeacht de waarden van de andere parameters (als ze maar aan de voorwaarden voldoen), wordt dit systeem als het beste beschouwd. Dan op de tweede parameter, enzovoort.
De optimalisatieprocedure bestaat in dit geval in de regel uit meerdere stappen. Dergelijke optimalisatie wordt vaak onbewust toegepast in technische systemen. Eerst wordt een systeem met de beste nauwkeurigheid gekozen, met dezelfde nauwkeurigheid van meerdere systemen, een betrouwbaarder en dan een goedkopere. Bij elke stap van de optimalisatie wordt slechts één criterium gebruikt, wat niet in tegenspraak is met het concept systeem benadering(optimalisatie door één enkel criterium, zie hieronder).
4. De vierde - de meest algemene - vorm van de doelfunctie is een willekeurige afhankelijkheid van alle of een deel (maar niet minder dan twee) heterogene externe parameters
In dit geval worden heterogene parameters omgezet in dimensieloos (of eendimensionaal) en wordt de objectieve functie gevormd als een bepaalde samenstelling (bijvoorbeeld het rekenkundig gemiddelde) van de verkregen dimensieloze indicatoren.
Een enkele objectieve functie van de vierde vorm kan worden verkregen uit de objectieve functies van de derde vorm door ze te vermenigvuldigen met gewichtscoëfficiënten en vervolgens op te tellen:
Waar F S (j i) - een van de k objectieve functies van de derde vorm;
ω S is de wegingsfactor.
Zoals op dezelfde plaats aangegeven, is het echter erg moeilijk om de gewichten van individuele doelfuncties te bepalen.
De extreme waarde van het ontvangen bedrag wordt als optimaal beschouwd.
Er kan dus worden aangegeven dat in de meeste gevallen (1e en 3e vorm) de kwaliteitsindicatoren van het systeem worden geëvalueerd door de numerieke waarden van de componenten van de vectorobjectieve functie, die worden genoemd functioneel :
- - - - - - - - - - - - - - - - - -
Omdat de systemen onder willekeurige invloeden werken, blijken de waarden van de functionalen vaak willekeurige variabelen te zijn. Dit is onhandig bij het gebruik van functionaliteiten in de vorm van kwaliteitsindicatoren. Daarom worden in dergelijke gevallen meestal de gemiddelde waarden van de overeenkomstige functionalen gebruikt. Bijvoorbeeld: het gemiddeld aantal geproduceerde producten per dienst; gemiddelde productiekosten, enz.
In sommige gevallen zijn kwaliteitsindicatoren de kansen op willekeurige gebeurtenissen. In dit geval wordt de waarschijnlijkheid gekozen als de objectieve functie 
vervulling door het systeem van het gestelde doel (taak)
Bijvoorbeeld de waarschijnlijkheid van doeldetectie door radar, enz.
