Enkel metodeforklaring. Løsning af et produktionsproblem ved hjælp af den tabulære simplex metode
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. medlem | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. medlem | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S1 = 0 S2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Denne metode er en metode til målrettet at opremse referenceløsninger til problemet lineær programmering. Det giver mulighed for, i et begrænset antal trin, enten at finde en optimal løsning eller at fastslå, at der ikke er nogen optimal løsning.
Hovedindholdet af simplex-metoden er som følger:- Angiv en metode til at finde den optimale referenceløsning
- Angiv metoden til overgang fra en referenceløsning til en anden, hvor værdien af den objektive funktion vil være tættere på den optimale, dvs. angive en måde at forbedre referenceløsningen på
- Indstil kriterier, der giver dig mulighed for omgående at stoppe med at søge efter supportløsninger på den optimale løsning eller følge konklusionen om, at der ikke er nogen optimal løsning.
Algoritme af simplex-metoden til løsning af lineære programmeringsproblemer
For at løse et problem ved hjælp af simplex-metoden skal du gøre følgende:- Tag opgaven med til kanonisk form
- Find den indledende supportløsning med et "enhedsgrundlag" (hvis der ikke er nogen supportløsning, så har problemet ikke en løsning på grund af inkompatibiliteten af systemet af begrænsninger)
- Beregn estimater af vektornedbrydninger baseret på referenceopløsningen og udfyld simplexmetodens tabel
- Hvis kriteriet for den optimale løsnings unikke karakter er opfyldt, slutter løsningen af problemet
- Hvis betingelsen for eksistensen af et sæt af optimale løsninger er opfyldt, så findes alle optimale løsninger ved simpel opregning
Et eksempel på løsning af et problem ved hjælp af simpleksmetoden
Eksempel 26.1Løs problemet ved hjælp af simpleksmetoden:
Løsning:
Vi bringer problemet til kanonisk form.
For at gøre dette introducerer vi en ekstra variabel x 6 med koefficient +1 til venstre side af den første ulighedsbegrænsning. Variablen x 6 er inkluderet i objektivfunktionen med en koefficient på nul (dvs. den er ikke inkluderet).
Vi får:
Vi finder den indledende supportløsning. For at gøre dette sætter vi lighedstegn mellem frie (uløste) variabler til nul x1 = x2 = x3 = 0.
Vi får referenceløsning X1 = (0,0,0,24,30,6) med enhedsbasis B1 = (A4, A5, A6).
Vi beregner estimater af vektornedbrydning betingelser på basis af referenceopløsningen ifølge formlen:
Δ k = C b X k - c k
- C b = (c 1, c 2, ..., c m) - vektor af koefficienter for den objektive funktion for de grundlæggende variable
- X k = (x 1k, x 2k, ..., x mk) - ekspansionsvektor af den tilsvarende vektor A k i henhold til referenceopløsningens basis
- C k er koefficienten for objektivfunktionen for variablen x k.
Estimaterne af de vektorer, der indgår i grundlaget, er altid lig nul. Referenceløsningen, udvidelseskoefficienter og estimater af udvidelser af tilstandsvektorer baseret på referenceløsningen er skrevet ind simplex bord :
Øverst i tabellen, for at lette beregningen af estimater, er koefficienterne for den objektive funktion skrevet. I den første kolonne "B" er de vektorer, der indgår i referenceløsningens basis, skrevet. Rækkefølgen, hvori disse vektorer er skrevet, svarer til antallet af tilladte ukendte i begrænsningsligningerne. I den anden kolonne i tabellen "C b" er koefficienterne for den objektive funktion for de grundlæggende variable skrevet i samme rækkefølge. På korrekte placering Koefficienterne for den objektive funktion i kolonnen "C b" af estimatet af enhedsvektorerne inkluderet i grundlaget er altid lig med nul.
I sidste linje tabeller med estimater af Δ k i kolonnen "A 0" er værdierne af objektivfunktionen på referenceløsningen Z(X 1) skrevet.
Den initiale støtteløsning er ikke optimal, da estimaterne Δ 1 = -2, Δ 3 = -9 for vektorerne A 1 og A 3 i det maksimale problem er negative.
Ifølge sætningen om forbedring af støtteløsningen, hvis mindst én vektor i et maksimalt problem har et negativt estimat, så kan du finde en ny støtteløsning, hvor værdien af den objektive funktion vil være større.
Lad os bestemme, hvilken af de to vektorer, der vil føre til en større stigning i objektivfunktionen.
Forøgelsen af objektivfunktionen findes ved formlen: .
Vi beregner værdierne af parameteren θ 01 for den første og tredje kolonne ved hjælp af formlen:
Vi får θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (Tabel 26.1).
Vi finder stigningen af den objektive funktion, når vi indfører den første vektor ΔZ 1 = - 6*(- 2) = 12 i basis, og den tredje vektor ΔZ 3 = - 3*(- 9) = 27.
For en hurtigere tilgang til den optimale løsning er det derfor nødvendigt at indføre vektor A3 i basis af referenceopløsningen i stedet for den første vektor af basis A6, da minimum af parameteren θ 03 er opnået i den første række ( l = 1).
Vi udfører Jordan-transformationen med elementet X13 = 2, vi opnår den anden referenceløsning X2 = (0,0,3,21,42,0) med basis B2 = (A3, A4, A5). (Tabel 26.2)
Denne løsning er ikke optimal, da vektor A2 har et negativt estimat Δ2 = - 6. For at forbedre løsningen er det nødvendigt at indføre vektor A2 i referenceopløsningens basis.
Vi bestemmer antallet af vektoren afledt af basis. For at gøre dette beregner vi parameteren θ 02 for den anden kolonne, den er lig med 7 for l = 2. Derfor udleder vi den anden basisvektor A4 fra basis. Vi udfører Jordan-transformationen med elementet x 22 = 3, vi får den tredje referenceløsning X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabel 26.3).
Denne løsning er den eneste optimale, da estimaterne for alle vektorer, der ikke er inkluderet i grundlaget, er positive
Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.
Svar: max Z(X) = 201 ved X = (0,7,10,0,63).
Lineær programmeringsmetode i økonomisk analyse
Lineær programmeringsmetode gør det muligt at retfærdiggøre den mest optimale økonomiske løsning under forhold med strenge restriktioner relateret til de ressourcer, der bruges i produktionen (anlægsaktiver, materialer, arbejdskraft). Anvendelse af denne metode i økonomisk analyse giver dig mulighed for at løse problemer primært relateret til planlægning af organisationens aktiviteter. Denne metode hjælper med at bestemme de optimale outputniveauer, såvel som anvisningerne for de fleste effektiv brug produktionsressourcer til rådighed for organisationen.
Ved hjælp af denne metode løses de såkaldte ekstreme problemer, som består i at finde ekstreme værdier, det vil sige maksimum og minimum af funktioner af variable mængder.
Denne periode er baseret på systemets løsning lineære ligninger i tilfælde, hvor de analyserede økonomiske fænomener er forbundet af en lineær, strengt funktionel afhængighed. Den lineære programmeringsmetode bruges til at analysere variable i nærvær af visse begrænsende faktorer.
Det er meget almindeligt at løse det såkaldte transportproblem ved hjælp af den lineære programmeringsmetode. Indholdet af denne opgave er at minimere omkostningerne i forbindelse med driften Køretøj under eksisterende restriktioner med hensyn til antallet af køretøjer, deres bæreevne, varigheden af deres drift, og hvis der er behov for vedligeholdelse maksimal mængde kunder.
Udover, denne metode bruges i vid udstrækning til at løse planlægningsproblemer. Denne opgave består af en sådan fordeling af driftstiden for personalet i en given organisation, som ville være mest acceptabel både for medlemmerne af dette personale og for organisationens kunder.
Denne opgave er at maksimere antallet af klienter, der betjenes under betingelser med begrænsninger af antallet af ledige medarbejdere, såvel som arbejdstidsfonden.
Den lineære programmeringsmetode er således ret almindelig i placerings- og brugsanalyse. forskellige typer ressourcer, såvel som i processen med at planlægge og forudsige organisationers aktiviteter.
Endnu matematisk programmering kan også anvendes på de økonomiske fænomener, hvis forhold ikke er lineært. Til dette formål kan ikke-lineære, dynamiske og konvekse programmeringsmetoder anvendes.
Ikke-lineær programmering er afhængig af den ikke-lineære karakter af den objektive funktion eller begrænsninger eller begge dele. Formerne for den objektive funktion og ulighedsbegrænsninger i disse forhold kan være forskellige.
Ikke-lineær programmering bruges i økonomisk analyse, især ved etablering af forholdet mellem indikatorer, der udtrykker effektiviteten af en organisations aktiviteter og omfanget af denne aktivitet, strukturen af produktionsomkostninger, markedsforhold osv.
Dynamisk programmering er baseret på at konstruere et beslutningstræ. Hvert niveau i dette træ tjener som et trin til at bestemme konsekvenserne af en tidligere beslutning og for at eliminere ineffektive muligheder for denne beslutning. Dermed, dynamisk programmering har en multi-trin, multi-stage karakter. Denne type programmering bruges i økonomisk analyse til at finde optimale muligheder udvikling af organisationen både nu og i fremtiden.
Konveks programmering er en form for ikke-lineær programmering. Denne type programmering udtrykker den ikke-lineære karakter af forholdet mellem resultaterne af en organisations aktiviteter og dens omkostninger. Konveks (alias konkav) programmering analyserer konvekse objektivfunktioner og konvekse begrænsningssystemer (punkter acceptable værdier). Konveks programmering bruges i analysen af økonomiske aktiviteter med det formål at minimere omkostningerne, og konkav programmering med det formål at maksimere indkomsten under eksisterende restriktioner på virkningen af faktorer, der påvirker de analyserede indikatorer på den modsatte måde. Følgelig minimeres konvekse objektivfunktioner med de typer programmering, der er under overvejelse, og konkave objektivfunktioner maksimeres.
Kort teori
Mange forskellige metoder er blevet foreslået til at løse lineære programmeringsproblemer. Simplex-metoden viste sig imidlertid at være den mest effektive og universelle blandt dem. Det skal bemærkes, at når man løser nogle problemer, kan andre metoder være mere effektive. For eksempel for en ZLP med to variable er den optimale metode , og til at løse den bruges den potentielle metode. Simplexmetoden er grundlæggende og anvendelig til enhver PPL i kanonisk form.
I forbindelse med hovedsætningen i lineær programmering opstår naturligvis tanken om den følgende vej OPP-beslutninger med et vilkårligt antal variable. Find på en eller anden måde alle ekstreme punkter i planernes polyeder (der er ikke flere af dem end ) og sammenlign værdierne af den objektive funktion ved dem. Denne løsning selv med relativt et lille antal variabler og begrænsninger er praktisk talt umulige, da processen med at finde ekstreme punkter er sammenlignelig i vanskeligheder med at løse oprindelige problem, desuden kan antallet af ekstreme punkter i planernes polyhedron vise sig at være ret stort. I forbindelse med disse vanskeligheder opstod problemet med rationel opregning af yderpunkter.
Essensen af simplex-metoden er som følger. Hvis et ekstremt punkt og værdien af den objektive funktion ved det er kendt, så er alle ekstreme punkter, hvor den objektive funktion tager værste værdi, er åbenbart ikke nødvendige. Derfor er det naturlige ønske at finde en måde at bevæge sig fra et givet yderpunkt til et bedre, der støder op langs kanten, fra det til et endnu bedre (ikke værre) osv. For at gøre dette skal du have et tegn på, at der er ingen bedre yderpunkter end et givet yderpunkt. Det er hvad generel idé den i øjeblikket mest udbredte simplex-metode (metode til sekventiel forbedring af planen) til løsning af ZLP. Så i algebraiske termer antager simpleksmetoden:
- evnen til at finde en indledende referenceplan;
- tilstedeværelse af et optimalitetstegn referenceplan;
- evnen til at flytte til en ikke-værste referenceplan.
Eksempel på problemløsning
Opgaven
For at sælge tre grupper af varer har en kommerciel virksomhed tre typer begrænsede materielle og monetære ressourcer i mængden af , , , enheder. På samme tid, til salg af 1 gruppe varer for 1 tusind rubler. vareomsætning forbruger ressourcen af den første type i antallet af enheder, ressourcen af den anden type i antallet af enheder, ressourcen af den tredje type i antallet af enheder. Til salg af 2 og 3 grupper af varer for 1 tusind rubler. vareomsætning er brugt i henhold til ressourcen af den første type i mængden af , enheder, ressourcer af den anden type i mængden af , enheder, ressourcer af den tredje type i mængden af , enheder. Fortjeneste fra salg af tre grupper af varer for 1 tusind rubler. omsætningen er henholdsvis , tusind rubler.
- Bestem det planlagte volumen og strukturen af handelsomsætningen, således at fortjenesten for handelsvirksomheden maksimeres.
- For det direkte problem med omsætningsplanlægning, løst ved simplex-metoden, skal du oprette et dobbelt lineært programmeringsproblem.
- Etabler konjugerede par af variabler af de direkte og dobbelte problemer.
- Ifølge de konjugerede par af variable fra løsningen af det direkte problem, få løsningen dobbelt problem, hvor de ressourcer, der bruges på at sælge varer, vurderes.
Hvis din adgang til sessionen afhænger af at løse en blok af problemer, og du hverken har tid eller lyst til at sætte dig ned til beregninger, så brug hjemmesidens muligheder. Bestilling af opgaver tager kun et par minutter. Du kan læse detaljeret (hvordan du indsender en anmodning, priser, vilkår, betalingsmetoder) på siden Køb løsninger til lineære programmeringsproblemer...
Løsningen af problemet
Modelbygning
Lad os betegne omsætningen af henholdsvis 1., 2. og tredje varetype.
Derefter den objektive funktion, der udtrykker det modtagne overskud:
Begrænsninger for materielle og monetære ressourcer:
Derudover efter opgavens betydning
Vi får følgende lineære programmeringsproblem:
Reduktion til den kanoniske form af ZLP
Lad os reducere problemet til kanonisk form. For at omdanne uligheder til ligheder introducerer vi yderligere variabler. Variable er inkluderet i restriktionerne med en koefficient på 1. Vi indfører alle yderligere variable i objektivfunktionen med en koefficient lig med nul.
Begrænsningen har en foretrukken form, hvis højre side er ikke-negativ, venstre side har en variabel, der kommer ind med en koefficient lig med en, og de resterende lighedsbegrænsninger har en koefficient lig nul. I vores tilfælde har 1., 2., 3. restriktioner en foretrukken form med de tilsvarende grundvariable.
Løsning ved hjælp af simpleksmetoden
Vi udfylder simplekstabellen for den 0. iteration.
| BP | Simplex forhold |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Da vi løser problemet maksimalt, indikerer tilstedeværelsen af negative tal i indekslinjen, når vi løser problemet til det maksimale, at vi ikke har opnået den optimale løsning, og at det er nødvendigt at gå videre fra tabellen med 0. iteration til den næste.
Vi fortsætter til næste iteration som følger:
Den forreste kolonne svarer til .
Nøglerækken bestemmes af minimumsforholdet mellem frie vilkår og medlemmer af den førende kolonne (simplekse relationer):
I skæringspunktet mellem nøglekolonnen og nøglerækken finder vi aktiveringselementet, dvs. 7.
Nu begynder vi at kompilere den 1. iteration. I stedet for en enhedsvektor introducerer vi vektoren .
I den nye tabel, i stedet for det aktiverende element, skriver vi 1, er alle andre elementer i nøglekolonnen nuller. Nøglestrengelementerne er opdelt i aktiveringselementet. Alle andre elementer i tabellen beregnes ved hjælp af rektangelreglen.
Vi får tabellen med 1. iteration:
| BP | Simplex forhold |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Nøglekolonnen for 1. iteration svarer til .
Vi finder nøglelinjen, for dette definerer vi:
I skæringspunktet mellem nøglekolonnen og nøglerækken finder vi det aktiverende element, dvs. 31/7.
Vektoren er afledt af basis, og vektoren introduceres.
Vi får tabellen med 2. iteration:
| BP | Simplex forhold |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
I indeksrækken er alle termer ikke-negative, så følgende løsning på det lineære programmeringsproblem opnås (vi skriver det ud fra kolonnen med frie termer):
Således er det nødvendigt at sælge 7,1 tusind rubler. varer af 1. type og 45,2 tusind rubler. varer af 3. type. Det er ikke rentabelt at sælge et produkt af 2. type. I dette tilfælde vil fortjenesten være maksimal og beløbe sig til 237,4 tusind rubler. Ved implementering optimal plan den resterende ressource af den 3. type vil være 701 enheder.
Dobbelt LP problem
Lad os nedskrive en model af det dobbelte problem.
For at konstruere et dobbelt problem skal du bruge følgende regler:
1) hvis det direkte problem er løst til det maksimale, så løses det dobbelte problem til et minimum, og omvendt;
2) i det maksimale problem har ulighedsbegrænsninger betydningen ≤, og i minimeringsproblemet har de betydningen ≥;
3) hver begrænsning af det direkte problem svarer til en variabel i det dobbelte problem, og omvendt svarer hver begrænsning af det dobbelte problem til en variabel i det direkte problem;
4) matricen af systemet af begrænsninger af det dobbelte problem er opnået fra matrixen af systemet af begrænsninger af det oprindelige problem ved transponering;
5) frie vilkår for systemet af begrænsninger af det direkte problem er koefficienter for de tilsvarende variabler for den objektive funktion af det dobbelte problem, og omvendt;
6) hvis en ikke-negativitetsbetingelse pålægges variablen af det direkte problem, så skrives den tilsvarende begrænsning af det dobbelte problem som en ulighedsbegrænsning, hvis ikke, så som en lighedsbegrænsning;
7) hvis en begrænsning af det direkte problem er skrevet som en lighed, pålægges ikke-negativitetsbetingelsen ikke den tilsvarende variabel i det dobbelte problem.
Vi transponerer matrixen af det oprindelige problem:
Lad os reducere problemet til kanonisk form. Lad os introducere yderligere variabler. Vi introducerer alle yderligere variable i objektivfunktionen med en koefficient lig med nul. Vi tilføjer yderligere variabler til venstre for restriktionerne, som ikke har en foretrukken form, og vi opnår ligheder.
Løsning af problemet med dobbelt LP
Overensstemmelse mellem variablerne i det oprindelige og dobbelte problem:
Baseret på simplex-tabellen blev følgende løsning på det dobbelte lineære programmeringsproblem opnået (vi skriver det ud fra den nederste linje):
Således er ressourcen af den første type den mest knappe. Dens score er maksimal og lig med . Ressourcen af den tredje type er redundant - dens dobbelte værdi er nul. Hver ekstra enhed af varer fra den solgte 2. gruppe vil reducere den optimale fortjeneste med
Taget i betragtning grafisk metode løsning af et lineært programmeringsproblem (LPP) med to variable. Der gives et eksempel på opgaven Detaljeret beskrivelse konstruere en tegning og finde en løsning.
Løsning af transportproblemet
Gennemgået i detaljer transport problem, hende matematisk model og løsningsmetoder - at finde referenceplanen ved minimumselementmetoden og søge efter den optimale løsning ved den potentielle metode.
Beslutningstagning under forhold med usikkerhed
Løsningen af et statistisk matrixspil under forhold med usikkerhed overvejes ved at bruge Wald, Savage, Hurwitz, Laplace og Bayes kriterierne. Ved hjælp af et eksempelproblem vises konstruktionen af en betalingsmatrix og en risikomatrix i detaljer.
Trin 0. Forberedende fase.
Vi reducerer LP-problemet til speciel form (15).
Trin 1. Kompilering simplex bord, svarende til den særlige formular:
|
|
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
Bemærk, at denne tabel svarer til en tilladt basisløsning 
problemer (15). Værdien af den objektive funktion på denne løsning 
Trin 2. Optimalitetstjek
Hvis der blandt elementerne i indeksrækken er simplekstabeller 
der er da ikke et eneste positivt element 
, findes den optimale løsning på LP-problemet:. Algoritmen afsluttes.
Trin 3. Uafgørelighedskontrol
Hvis blandt 
der er et positivt element 
, og i den tilsvarende kolonne 
der er ikke et eneste positivt element 
, derefter den objektive funktion L er ubegrænset nedefra på det tilladte sæt. I dette tilfælde er der ingen optimal løsning. Algoritmen afsluttes.
Trin 4. Valg af en ledende kolonne q
Blandt elementerne 
vælg det maksimale positive element 
.Vi erklærer denne kolonne for at være den førende (tilladende) kolonne.
Trin 5. Valg af leadlinje s
Blandt de positive elementer i kolonnen 
find elementet 
, som ligestillingen gælder for
.
Snor s Vi erklærer, at den er førende (tilladende). Element 
Vi erklærer det for at være lederen (tillader det).
Trin 6. Simplex tabelkonvertering
Vi laver en ny simplex tabel, hvor:
a) i stedet for grundvariablen 
Skriv ned 
, i stedet for en ikke-grundlæggende variabel 
Skriv ned 
;
b) det førende element erstattes af den omvendte værdi 
;
c) alle elementer i den forreste kolonne (undtagen 
) gange med 
;
d) alle elementer i den forreste linje (undtagen 
) gange med 
;
e) de resterende elementer i simplekstabellen transformeres i henhold til følgende "rektangel"-skema.
Produktet af tre faktorer trækkes fra elementet:
den første er det tilsvarende element i den førende søjle;
den anden er det tilsvarende element i den førende linje;
det tredje er det ledende elements gensidige 
.
Det transformerede element og de tre faktorer, der svarer til det, er netop toppunkterne i "rektanglet".
Trin 7 Overgangen til næste iteration udføres ved at vende tilbage til trin 2.
2.3. Simplex metodealgoritme til det maksimale problem
Simplexmetodens algoritme for det maksimale problem adskiller sig kun fra algoritmen for minimumsproblemet i fortegnene på indekslinjen for koefficienterne i objektivfunktionen 
, nemlig:
I trin 2:
:
I trin 3
.
Objektiv funktion er ubegrænset ovenfra på det tilladte sæt.
I trin 4:
.
2.4. Et eksempel på løsning af et problem ved hjælp af simpleksmetoden
Løs opgaven skrevet i skemaet (15).
Lad os lave en simplex-tabel:
|
|
|
|
|
|
| |||
|
|
|
Da koefficienterne for linjen af den objektive funktion er ikke-negative, er den initiale basisløsning ikke optimal. Værdien af den objektive funktion for dette grundlag L=0.
Vælg den forreste kolonne - dette er den kolonne, der svarer til variablen 
.
Vælg den forreste linje. For at gøre dette finder vi 
. Derfor svarer den forreste linje til variablen 
.
Vi transformerer simplekstabellen ved at introducere en variabel 
ind i grundlaget og output af variablen 
fra grundlaget. Vi får bordet:
|
|
|
|
|
|
|
| ||
|
|
|
En iteration af metoden er gennemført. Lad os gå videre til en ny iteration. Den resulterende tabel er ikke optimal. Den grundlæggende løsning svarende til tabellen har formen . Værdien af den objektive funktion på dette grundlag L= -2.
Den forreste kolonne her er den kolonne, der svarer til variablen 
. Ledende linje – den linje, der svarer til variablen 
. Efter at have udført transformationerne får vi en simplekstabel:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Endnu en iteration afsluttet. Lad os gå videre til en ny iteration.
Linjen i objektivfunktionen indeholder ikke positive værdier, hvilket betyder, at den tilsvarende basisløsning er optimal, og algoritmen afsluttes.
Et eksempel på løsning af et problem ved hjælp af simplex-metoden samt et eksempel på løsning af et dobbelt problem tages i betragtning.
Opgaven
For at sælge tre grupper af varer har en kommerciel virksomhed tre typer begrænsede materielle og monetære ressourcer i mængden af b 1 = 240, b 2 = 200, b 3 = 160 enheder. På samme tid, til salg af 1 gruppe varer for 1 tusind rubler. vareomsætning, ressourcen af den første type forbruges i mængden af a 11 = 2 enheder, ressourcen af den anden type i mængden af a 21 = 4 enheder, ressourcen af den tredje type i mængden af en 31 = 4 enheder. Til salg af 2 og 3 grupper af varer for 1 tusind rubler. omsætningen forbruges i henhold til ressourcen af den første type i mængden af a 12 = 3, a 13 = 6 enheder, ressourcen af den anden type i mængden af a 22 = 2, a 23 = 4 enheder, ressourcen af den tredje type i mængden af en 32 = 6, en 33 = 8 enheder. Fortjeneste fra salg af tre grupper af varer for 1 tusind rubler. omsætningen er henholdsvis c 1 = 4, c 2 = 5, c 3 = 4 (tusind rubler). Bestem det planlagte volumen og strukturen af handelsomsætningen, således at fortjenesten for handelsvirksomheden maksimeres.
Til det direkte problem med omsætningsplanlægning, løses ved simpleksmetoden, komponere dobbelt problem lineær programmering.
Installere konjugerede par af variable direkte og dobbelte problemer.
Ifølge konjugerede par af variable, fra løsningen af det direkte problem, vi opnår løsning af det dobbelte problem, hvori det er produceret ressourcevurdering, brugt på salg af varer.
Løsning af problemet ved hjælp af simpleksmetoden
Lad x 1, x 2, x 3 være antallet af solgte varer, i tusind rubler, henholdsvis 1, 2, 3 grupper. Så har den matematiske model af problemet formen:F = 4 x 1 + 5 x 2 + 4 x 3 ->maks
0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
Vi løser simpleksmetoden.
Vi introducerer yderligere variable x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 for at transformere ulighederne til ligheder.
Lad os tage x 4 = 240 som grundlag; x 5 = 200; x 6 = 160.
Vi indtaster dataene i simplex bord
Simplex bord nr. 1
Objektiv funktion:
0 240 + 0 200 + 0 160 = 0
Vi beregner estimater ved hjælp af formlen:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Da der er negative skøn, er planen ikke optimal. Laveste score:
Vi introducerer variablen x 2 i grundlaget.
Vi definerer en variabel, der kommer ud fra grundlaget. For at gøre dette finder vi det mindste ikke-negative forhold for x2-kolonnen.
= 26.667
Mindste ikke-negativ: Q 3 = 26,667. Vi udleder variablen x 6 fra grundlaget
Divider 3. linje med 6.
Fra 1. linje trækkes 3. linje fra, ganget med 3
Fra 2. linje trækkes 3. linje fra, ganget med 2
Vi beregner:
Vi får nyt bord:
Simplex bord nr. 2
Objektiv funktion:
0 160 + 0 440/3 + 5 80/3 = 400/3
Vi beregner estimater ved hjælp af formlen:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Da der er et negativt estimat Δ 1 = - 2/3, er planen ikke optimal.
Vi introducerer variablen x 1 i grundlaget.
Vi definerer en variabel, der kommer ud fra grundlaget. For at gøre dette finder vi det mindste ikke-negative forhold for kolonnen x 1.
Mindste ikke-negativ: Q 3 = 40. Vi udleder variablen x 2 fra grundlaget
Divider 3. linje med 2/3.
Fra 2. linje trækkes 3. linje fra, ganget med 8/3
Vi beregner:
Vi får et nyt bord:
Simplex bord nr. 3
Objektiv funktion:
0 160 + 0 40 + 4 40 = 160
Vi beregner estimater ved hjælp af formlen:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Da der ikke er nogen negative vurderinger, er planen optimal.
Løsningen af problemet:
Svar
x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160Det vil sige, at det er nødvendigt at sælge den første type varer i mængden af 40 tusind rubler. Produkter af type 2 og 3 skal ikke sælges. Hvori maksimal profit vil være F max = 160 tusind rubler.
Løsning af det dobbelte problem
Det dobbelte problem har formen:
Z = 240 y 1 + 200 y 2 + 160 y 3 -> min
Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}
Vi introducerer yderligere variabler y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 for at transformere ulighederne til ligheder.
Konjugerede par af variabler af de direkte og dobbelte problemer har formen:
Fra den sidste simplekstabel nr. 3 i det direkte problem finder vi løsningen på det dobbelte problem:
Z min = Fmax = 160;
y1 = A4 = 0; y2 = A5 = 0; y3 = A6 = 1; y4 = Δ1 = 0; y5 = A2 = 1; y6 = A3 = 4;