Otsi graafiline meetod maksimaalselt objektiivne funktsioon

F= 2x 1 + 3x 2 ® max

Piirangutega

Lahendus kasutades Exceli tabelid

Ehitame esmalt lehele exceli lahendus ebavõrdsuse süsteemid.

Mõelge esimesele ebavõrdsusele.

Ehitame kahest punktist piirjoone. Tähistage joont (L1) (või rida 1). Koordinaadid X 2 loendame vastavalt valemitele:

Ehitamiseks valige hajusdiagramm

Andmete valimine sirge jaoks

Muutke rea nime:

Valige diagrammi paigutus. Muutke koordinaattelgede nimesid:

Sirge joon (L1) diagrammil:

Range ebavõrdsuse lahenduse saab leida ühe testpunkti abil, mis ei kuulu sirgele (L1). Näiteks kasutades punkti (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

Ebavõrdsus on tõene, seetõttu on võrratuse (1) lahendiks pooltasapind, millel katsepunkt asub (joonisel joone L1 all).

Seejärel lahendame ebavõrdsuse (2) .

Ehitame kahest punktist piirjoone 2. Tähistage joont (L2).

Sirge joon (L2) diagrammil:

Range võrratuse 2 lahenduse saab leida ainsa testpunktiga, mis ei kuulu reale (L2). Näiteks kasutades punkti (0; 0)W(L2).

Asendades punkti koordinaadid (0; 0), saame ebavõrdsuse

2 × 0 + 0< 16 или 0 < 16 .

Ebavõrdsus on tõene, seetõttu on võrratuse (2) lahendiks pooltasapind, millel asub katsepunkt (alloleval joonisel joon L2).

Seejärel lahendame ebavõrdsuse (3) .

Ehitame kahest punktist piirjoone. Tähistage joont (L3).

Sirge joon (L3) diagrammil:

Range võrratuse 2 lahenduse saab leida ainsa testpunktiga, mis ei kuulu reale (L3). Näiteks kasutades punkti (0; 0)W(L3).

Asendades punkti koordinaadid (0; 0), saame ebavõrdsuse

Ebavõrdsus on tõene, seetõttu on võrratuse (3) lahendiks pooltasapind, millel katsepunkt asub (alloleval joonisel joon L3).

Seejärel lahendame ebavõrdsuse (4) .

Ehitame kahest punktist piirjoone. Tähistage joont (L4).

Lisage andmed Exceli lehele

Sirge joon (L4) diagrammil:

Range ebavõrdsuse lahendus 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Asendades punkti koordinaadid (0; 0), saame ebavõrdsuse

Ebavõrdsus on tõene, seetõttu on võrratuse (4) lahendiks pooltasapind, millel asub katsepunkt (joonisel sirgest L4 vasakul).

Lahendades kaks võrratust (5) ja (6)

on 1. kvartal, mis on piiratud koordinaatjoontega ja .

Ebavõrdsuse süsteem on lahendatud. Lahendades võrratuste süsteemi (1) - (6) in see näide on joonise alumises vasakus nurgas olev kumer hulknurk, mis on piiratud joontega L1, L2, L3, L4 ning koordinaatjoontega ja . Hulknurga õiges valimises saate veenduda, kui asendate algsüsteemi igas võrratuses testpunkti, näiteks (1; 1). Asendades punkti (1; 1), saame, et kõik ebavõrdsused, sealhulgas loomulikud piirangud, on tõesed.

Mõelge nüüd sihtfunktsioonile

F= 2x 1 + 3x 2 .

Ehitame funktsiooni väärtuste jaoks tasemeread F=0 Ja F=12 (arvväärtusi valitud suvaliselt). Lisage andmed Exceli lehele

Diagrammi tasemejooned:

Koostame suundade vektori (või gradiendi) (2; 3). Vektori koordinaadid langevad kokku sihtfunktsiooni kordajatega F.

Koostame tasapinnal süsteemi lubatavate lahenduste hulga lineaarsed ebavõrdsused ja geomeetriliselt leida minimaalne väärtus sihtfunktsioon.

Ehitame koordinaatsüsteemis x 1 oh 2 rida

Leiame süsteemi poolt määratud pooltasandid. Kuna süsteemi ebavõrdsused on täidetud iga punkti jaoks vastavast pooltasandist, piisab nende kontrollimisest mis tahes punktis. Kasutame punkti (0;0). Asendame selle koordinaadid süsteemi esimese ebavõrdsusega. Sest , siis defineerib ebavõrdsus pooltasandi, mis ei sisalda punkti (0;0). Samamoodi määratleme ülejäänud pooltasandid. Leiame teostatavate lahenduste komplekti kui üldosa saadud pooltasanditest on varjutatud ala.

Ehitame vektori ja sellega risti oleva nulltaseme sirge.

Liigutades sirget (5) vektori suunas, näeme, et piirkonna maksimaalne punkt saab olema sirge (3) ja sirge (2) lõikepunktis A. Leiame võrrandisüsteemi lahenduse:

Niisiis, saime punkti (13;11) ja.

Liigutades sirget (5) vektori suunas, näeme, et piirkonna minimaalne punkt saab olema sirge (1) ja sirge (4) lõikepunktis B. Leiame võrrandisüsteemi lahenduse:

Niisiis, saime punkti (6;6) ja.

2. Mööblifirma toodab kombineeritud kappe ja arvutilaudu. Nende tootmist piirab tooraine (kvaliteetsed lauad, furnituurid) saadavus ja neid töötlevate masinate tööaeg. Iga kappi jaoks on vaja 5 m2 laudu, laua jaoks - 2 m2. Ühele kapile kulub tarvikud hinnaga 10 dollarit ja ühe laua peale 8 dollarit. Ettevõte saab oma tarnijatelt kuni 600 m2 plaate kuus ja tarvikuid 2000 dollari eest. Iga kapi jaoks on vaja 7 tundi masinatööd, laua jaoks - 3 tundi. Masinat on võimalik kasutada vaid 840 tundi kuus.

Kui palju kombineeritud kappe ja arvutilaudu peaks ettevõte kuus tootma, et maksimeerida kasumit, kui üks kapp toob sisse 100 dollarit ja iga laud 50 dollarit?

• 1. Koosta matemaatiline mudel probleem ja lahendage see simpleksmeetodi abil.
• 2. Koostage matemaatiline mudel kahesugused ülesanded ja kirjutage üles selle lahendus algse lahenduse põhjal.
• 3. Tehke kindlaks kasutatavate ressursside nappuse määr ja põhjendage optimaalse plaani tasuvust.
• 4. Uurige toodangu edasise suurendamise võimalusi, olenevalt iga ressursitüübi kasutusest.
• 5. Hinnake uut tüüpi toote kasutuselevõtu teostatavust - raamaturiiulid, kui ühe riiuli valmistamiseks kulutatakse 1 m 2 tahvleid ja tarvikuid hinnaga 5 dollarit ja masina tööks on vaja 0,25 tundi ning kasum ühe riiuli müügist on 20 dollarit.
• 1. Ehitame selle ülesande jaoks matemaatilise mudeli:

Tähistage x 1 - kappide tootmismaht ja x 2 - laudade tootmismaht. Koostame piirangute süsteemi ja eesmärgifunktsiooni:

Lahendame ülesande simpleksmeetodil. Kirjutame selle kanoonilisel kujul:

Kirjutame ülesande andmed tabeli kujul:

Tabel 1

Sest nüüd on kõik delta Üle nulli, siis on eesmärgifunktsiooni f väärtuse edasine suurendamine võimatu ja oleme saanud optimaalse plaani.

Sissejuhatus

Kaasaegne inimkonna arengujärk erineb selle poolest, et energeetika sajand on asendumas informaatika ajastuga. Kõikides valdkondades toimub intensiivne uute tehnoloogiate kasutuselevõtt inimtegevus. Tõuseb tõeline probleemüleminek infoühiskonnale, mille prioriteediks peaks saama hariduse arendamine. Ühiskonnas muutub ka teadmiste struktuur. Kõik suurem väärtus Sest praktiline elu omandada põhiteadmised, mis aitavad kaasa loominguline areng iseloom. Oluline on ka omandatud teadmiste konstruktiivsus, oskus neid eesmärgipäraselt struktureerida. Teadmiste põhjal uus teabeallikadühiskond. Uute teadmiste kujundamine ja omandamine peaks põhinema rangel metoodikal süsteemne lähenemine, mille sees on omaette koht mudelkäsitlusel. Modelleerimiskäsitluse võimalused on äärmiselt mitmekesised nii kasutatavate formaalsete mudelite kui ka modelleerimismeetodite rakendamise viiside poolest. Füüsiline modelleerimine võimaldab saada usaldusväärseid tulemusi üsna lihtsate süsteemide puhul.

Praegu on võimatu nimetada inimtegevuse valdkonda, kus ühel või teisel määral modelleerimismeetodeid ei kasutataks. See kehtib eriti juhtimisvaldkonnas. erinevaid süsteeme, kus peamisteks on saadud info põhjal otsustusprotsessid.

1. Probleemi avaldus

minimaalne objektiivne funktsioon

Lahendage vastavalt ülesande valikule nr 16 otsustuspolügooniga määratud piirangute süsteemile sihtfunktsiooni miinimumi leidmise ülesanne. Otsustuspolügoon on näidatud joonisel 1:

Joonis 1 - Probleemilahenduste hulknurk

Allpool on toodud piirangute süsteem ja ülesande eesmärk:

Probleemi lahendamiseks on vaja kasutada järgmisi meetodeid:

Graafiline meetod LP-ülesannete lahendamiseks;

Algebraline meetod LP-ülesannete lahendamiseks;

Simpleksmeetod LP-ülesannete lahendamiseks;

LP probleemidele teostatava lahenduse leidmise meetod;

Kahe LP probleemi lahendamine;

"harude ja piiride" meetod täisarvuliste LP-ülesannete lahendamiseks;

Gomory meetod täisarvuliste LP-ülesannete lahendamiseks;

Balashi meetod Boole'i ​​LP-ülesannete lahendamiseks.

Võrrelge lahenduse tulemusi erinevate meetoditega, et teha töö kohta asjakohased järeldused.

2. Graafiline lahendus lineaarse programmeerimise probleemid

Graafilist meetodit lineaarse programmeerimise ülesannete lahendamiseks kasutatakse juhtudel, kui tundmatute arv ei ületa kolme. Mugav jaoks kvalitatiivne uuring lahenduste omadused ja seda kasutatakse koos teiste meetoditega (algebraline, haruline ja seotud jne). Meetodi idee põhineb lineaarse ebavõrdsuse süsteemi graafilisel lahendusel.

Riis. 2 LP-ülesande graafiline lahendus

Madal punkt

Kahte punkti A1 ja A2 läbiva sirge võrrand:

AB: (0;1); (3;3)

Päike: (3;3); (4;1)

CD: (4;1); (3; 0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

piirangutega:

Lineaarse programmeerimise ülesande lahendamine algebralise simpleksmeetodi abil

Algebralise meetodi rakendamine ülesande lahendamisel eeldab LP-ülesande esituse üldistamist. Algne võrratuste kujul antud piirangute süsteem teisendatakse standardmärgistuseks, kui piirangud on antud võrratuste kujul. Piirangusüsteemi teisendamine standardvaade sisaldab järgmisi samme:

Teisenda ebavõrdsused nii, et muutujad ja vabaliikmed on vasakul, 0 aga paremal, s.t. et vasak pool oleks nullist suurem või sellega võrdne;

Võtta kasutusele täiendavad muutujad, mille arv on võrdne piirangute süsteemi ebavõrdsuste arvuga;

Sisenemine täiendavad piirangud lisatud muutujate mittenegatiivsuse kohta asendage ebavõrdsuse märgid rangete võrdsuste märkidega.

LP probleemi lahendamisel algebraline meetod lisatakse tingimus: sihtfunktsioon peab kalduma miinimumini. Kui see tingimus ei ole täidetud, on vaja sihtfunktsiooni sobivalt teisendada (korrutada -1-ga) ja lahendada minimeerimisprobleem. Pärast lahenduse leidmist asendage muutujate väärtused algses funktsioonis ja arvutage selle väärtus.

Ülesande lahendamist algebralise meetodi abil peetakse optimaalseks, kui kõigi põhimuutujate väärtused on mittenegatiivsed ja vabade muutujate koefitsiendid sihtfunktsiooni võrrandis on samuti mittenegatiivsed. Kui need tingimused ei ole täidetud, on ülaltoodud piirangute saavutamiseks vaja ebavõrdsuse süsteemi teisendada, väljendades mõnda muutujat teiste kaudu (vahetades vabasid ja põhimuutujaid). Eeldatakse, et kõigi vabade muutujate väärtus on null.

Algebraline meetod lineaarse programmeerimise ülesannete lahendamiseks on üks kõige enam tõhusad meetodid väikesemõõtmeliste probleemide käsitsi lahendamisel. ei nõua suur hulk aritmeetilised arvutused. Selle meetodi masinrakendus on keerulisem kui näiteks simpleksmeetodi puhul, kuna algebralise meetodi lahendamise algoritm on teatud määral heuristiline ja lahenduse efektiivsus sõltub suuresti isiklikust kogemusest.

vabad muutujad

St lane - lisama. komplekt

Seetõttu leidsime, et mittenegatiivsuse tingimused on täidetud optimaalne lahendus.

3. Lineaarse programmeerimise ülesande lahendamine simplekstabeli abil

Lahendus: Toome ülesande tüüpvormile lahendamiseks simplekstabeli abil.

Taandame kõik süsteemi võrrandid järgmisele kujule:

Ehitame simplekstabeli:

IN ülemine nurk iga tabeli lahtri jaoks sisestame võrrandisüsteemist koefitsiendid;

Valime reas F maksimaalse positiivse elemendi, välja arvatud see, et see on üldine veerg;

Üldise elemendi leidmiseks loome seose kõigi positiivsete elementide jaoks. 3/3; 9/1;- minimaalne suhe real x3. Seega – üldine string ja =3 – üldelement.

Leiame =1/=1/3. Toome sisse lahtri alumise nurga, kus asub üldelement;

Üldrea kõikidesse täitmata alumistesse nurkadesse sisestame lahtri ülanurgas oleva väärtuse korrutise by;

Valige üldjoone ülemised nurgad;

Üldveeru kõikidesse alumistesse nurkadesse sisestame ülanurgas oleva väärtuse korrutis - ja valime saadud väärtused;

Tabeli ülejäänud lahtrid täidetakse vastavate valitud elementide korrutistega;

Seejärel koostame uue tabeli, milles üldise veeru ja rea ​​elementide lahtrite tähistused on vastupidised (x2 ja x3);

Endise üldise rea ja veeru ülemisse nurka kirjutatakse väärtused, mis olid varem alumises nurgas;

Nende lahtrite ülemise ja alumise nurga väärtuste summa eelmises tabelis on kirjutatud ülejäänud lahtrite ülemisse nurka

4. Lineaarse programmeerimise ülesande lahendamine teostatava lahenduse leidmisega

Olgu antud lineaarsete algebraliste võrrandite süsteem:

Võime eeldada, et kõik, muidu me korrutame vastav võrrand poolt -1.

Tutvustame abimuutujaid:

Tutvustame ka abifunktsiooni

Minimeerime süsteemi piirangute (2) ja tingimustel.

TEHTAVA LAHENDUSE LEIDMISE REEGEL: Süsteemile (1) teostatava lahenduse leidmiseks minimeerime vormi (3) piirangute (2) all, vabade tundmatutena võtame põhilisteks xj.

Probleemi lahendamisel simpleksmeetodil võib tekkida kaks juhtumit:

min f=0, siis kõik i peavad olema võrdsed nulliga. Ja saadud xj väärtused on vastuvõetav lahendus süsteemid (1).

min f>0, st. algsel süsteemil pole kehtivat lahendust.

Lähtesüsteem:

Kasutatakse eelmise teema probleemi tingimust.

Lisame täiendavaid muutujaid:

Algülesandele leitakse lubatav lahendus: x1 = 3, x2 = 3, F = -12. Saadud teostatava lahenduse põhjal leiame simpleksmeetodil optimaalse lahenduse algsele probleemile. Selleks koostame ülaltoodud tabelist uue simplekstabeli, kustutades rea ja abiülesande sihtfunktsiooniga rea:

Konstrueeritud simplekstabelit analüüsides näeme, et optimaalne lahendus algülesandele on juba leitud (sihtfunktsioonile vastavad elemendid reas on negatiivsed). Seega kattub abiülesande lahendamisel leitud teostatav lahendus algülesande optimaalse lahendusega:

6. Lineaarse programmeerimise topeltprobleem

Algne piirangute süsteem ja ülesande eesmärkfunktsioon on näidatud alloleval joonisel.

piirangutega:

Lahendus: Toome piirangute süsteemi tüüpvormile:

Selle kahekordne ülesanne näeb välja järgmine:

Kahekordne probleem lahendatakse simpleksmeetodiga.

Teisendame sihtfunktsiooni nii, et minimeerimisülesanne on lahendatud ja kirjutame piirangute süsteemi standardkujul lahendamiseks simpleksmeetodil.

y6 = 1 – (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Koostagem kahese LP probleemi lahendamiseks esialgne simplekstabel.

Simpleksmeetodi teine ​​samm

Seega leiti simpleksmeetodi kolmandas etapis minimeerimisülesande optimaalne lahendus järgmiste tulemustega: y2 = -7 /8, y1 = -11/8, Ф = 12. Selleks et leida duaalprobleemi eesmärkfunktsioon, asendame põhi- ja vabamuutujate leitud väärtused maksimeerimisfunktsiooniga:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Kuna otse- ja duaalülesande sihtfunktsiooni väärtus on sama, leitakse otseülesande lahendus ja see võrdub 12-ga.

Fmin \u003d Fmax \u003d -12

7. Täisarvulise lineaarse programmeerimise ülesande lahendamine “harude ja piiride” meetodil

Muutkem algne probleem selliselt, et tavameetoditega lahendamisel täisarvu tingimus ei ole täidetud.

Täisarvulise programmeerimise ülesande lahenduste esialgne hulknurk.

Teisendatud lahendushulknurga jaoks konstrueerime uus süsteem piiranguid.

Kirjeldame piirangute süsteemi võrduste kujul, lahendamiseks algebralise meetodiga.

Lahenduse tulemusena leiti optimaalne ülesandeplaan: x1 = 9/4, x2 = 5/2, F = -41/4. See lahendus ei vasta ülesandes seatud terviklikkuse tingimusele. Jagame algse lahenduspolügooni kaheks piirkonnaks, jättes sellest välja piirkonna 3

Muudetud ülesannete lahenduste hulknurk

Koostame lahenduspolügooni moodustatud piirkondade jaoks uued piirangute süsteemid. Vasakpoolne ala on nelinurk (trapets). Lahenduse hulknurga vasaku piirkonna piirangute süsteem on esitatud allpool.

Vasaku piirkonna piiramissüsteem

Parem piirkond tähistab punkti C.

Õige otsustuspiirkonna piirangute süsteem on esitatud allpool.

Uued piirangusüsteemid on kaks täiendavat probleemi, mis tuleb lahendada üksteisest sõltumatult. Lahendame lahenduspolügooni vasakpoolse piirkonna täisarvude programmeerimise ülesande.

Lahenduse tulemusena leiti optimaalne ülesandeplaan: x1 = 3, x2 = 3, F = -12. See plaan rahuldab ülesande täisarvuliste muutujate tingimust ja seda võib võtta algse täisarvu lineaarse programmeerimise ülesande optimaalse võrdlusplaanina. Pole mõtet teostada lahendust õige lahenduspiirkonna jaoks. Allolev joonis näitab täisarvulise lineaarse programmeerimise ülesande lahendamise edenemist puu kujul.

Täisarvulise lineaarse programmeerimise ülesande lahendamise käik Gomory meetodil.

Paljudes praktilistes rakendustes pakub suurt huvi täisarvude programmeerimise probleem, milles on antud lineaarsete võrratuste süsteem ja lineaarvorm

On vaja leida süsteemi (1) täisarvuline lahendus, mis minimeerib sihtfunktsiooni F ja kõik koefitsiendid on täisarvud.

Ühe meetodi täisarvulise programmeerimise probleemi lahendamiseks pakkus välja Gomory. Meetodi idee on kasutada pideva lineaarse programmeerimise meetodeid, eelkõige simpleksmeetodit.

1) Simpleksmeetodil määratakse ülesande (1), (2) lahendus, mille puhul on eemaldatud nõue, et lahendus peab olema täisarv; kui lahendus osutub täisarvuks, siis leitakse ka täisarvuülesandele soovitud lahendus;

2) Vastasel juhul, kui mõni koordinaat ei ole täisarv, kontrollitakse saadud ülesande lahendust täisarvulise lahendi olemasolu suhtes (täisarvupunktide olemasolu lubatud hulktahukas):

kui suvalises murdosa vabaliikmega reas osutuvad kõik muud koefitsiendid täisarvudeks, siis pole täisarve, lubatavas hulktahukas punkte ja täisarvude programmeerimise ülesandel pole lahendust;

Vastasel juhul võetakse kasutusele täiendav lineaarne piirang, mis lõikab lubatavast hulktahukast ära osa, mis on vähetõotav täisarvulise programmeerimise probleemile lahenduse leidmiseks;

3) Täiendava lineaarse piirangu konstrueerimiseks vali l-s rida murdosa vabaliikmega ja kirjuta lisapiirang üles

kus ja on vastavalt koefitsientide murdosad ja vabad

liige. Toome piirangusse (3) sisse abimuutuja:

Määrame piirangusse (4) kaasatud koefitsiendid:

kus ja on vastavalt ja lähimad väiksemad täisarvud.

Gomory tõestas, et piiratud arv selliseid samme viib lineaarse programmeerimise probleemini, mille lahendus on täisarv ja seega soovitud.

Lahendus: taandame lineaarsete piirangute süsteemi ja eesmärgifunktsiooni kanoonilisele kujule:

Määrame lineaarsete piirangute süsteemi optimaalse lahenduse, jättes ajutiselt kõrvale täisarvu tingimuse. Selleks kasutame simpleksmeetodit. Allolevates tabelites esitatakse ülesande algne lahendus järjestikku ning ülesande optimaalse lahenduse saamiseks on toodud algse tabeli teisendused:

Boole'i ​​LP-ülesannete lahendamine Balashi meetodil.

Koostage Boole'i ​​muutujatega lineaarse täisarvulise programmeerimise ülesande oma variant, võttes arvesse järgmisi reegleid: ülesanne kasutab vähemalt 5 muutujat, vähemalt 4 piirangut, piirangute koefitsiendid ja sihtfunktsioon valitakse suvaliselt, kuid sellises kuidas piirangute süsteem ühildub. Ülesandeks on lahendada ZCLP Boole'i ​​muutujatega, kasutades Balashi algoritmi ja määrata arvutusliku keerukuse vähenemine seoses ülesande lahendamisega ammendava otsinguga.

Piirangute täitmine

F väärtus

Filtri piirang:

Arvutuse vähendamise määramine

Ülesande lahendus ammendava otsingumeetodiga on 6*25=192 arvutatud avaldist. Ülesande lahendus Balashi meetodil on 3*6+(25-3)=47 arvutatud avaldist. Arvutuste keerukuse täielik vähenemine seoses probleemi lahendamisega ammendava otsingumeetodi abil on.

Järeldus

Uut infotehnoloogiat rakendavate infosüsteemide kujundamise protsessi täiustatakse pidevalt. Järjest keerukamad süsteemid on muutumas süsteemiinseneride tähelepanu keskpunktiks, mis raskendab füüsiliste mudelite kasutamist ning suurendab matemaatiliste mudelite ja süsteemide arvutisimulatsiooni tähtsust. Masinamodelleerimisest on saanud tõhus vahend keerukate süsteemide uurimisel ja projekteerimisel. Matemaatiliste mudelite asjakohasus kasvab pidevalt tänu nende paindlikkusele, reaalsetele protsessidele adekvaatsusele, kaasaegsete personaalarvutite baasil teostamise madalatele kuludele. Üha rohkem võimalusi pakutakse kasutajale ehk arvutitehnoloogia abil süsteemide modelleerimise spetsialistile. Modelleerimise kasutamine on eriti efektiivne automatiseeritud süsteemide projekteerimise algfaasis, kui ekslike otsuste hind on kõige olulisem.

Kaasaegsed arvutusvahendid on võimaldanud oluliselt suurendada süsteemide uurimisel kasutatavate mudelite keerukust, võimalikuks on saanud kombineeritud, analüütiliste ja simulatsioonimudelite koostamine, mis võtavad arvesse kõiki reaalsetes süsteemides toimuvaid tegureid, st uuritavatele nähtustele adekvaatsemate mudelite kasutamine.

Kirjandus:

1. Ljaštšenko I.N. Lineaarne ja mittelineaarne programmeerimine / I. N. Ljaštšenko, E. A. Karagodova, N. V. Tšernikova, N. Z. Shor. - K .: "Kõrgkool", 1975, 372 lk.

2. Juhend eriala "Arvutisüsteemid ja võrgud" täis- ja osakoormusega õppevormide eriala üliõpilaste kursuseprojekti rakendamiseks erialal "Rakendusmatemaatika" / Koostanud: I.A. Balakireva, A.V. Skatkov - Sevastopol: Kirjastus SevNTU, 2003. - 15 lk.

3. Juhend distsipliini "Rakendusmatemaatika" uurimise osa "Globaalse otsingu ja ühemõõtmelise minimeerimise meetodid" / Koost. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU kirjastus, 2000. - 31s.

4. Juhend distsipliini "Rakendusmatemaatika" õppimiseks statsionaarse ja korrespondentõppe õppevormide eriala "Arvutisüsteemid ja võrgud" jaotise "Täisarvuline lineaarse programmeerimise ülesannete lahendamine" üliõpilastele / Koostanud: I.A. Balakireva, A.V. Skatkov - Sevastopol : Kirjastus SevNTU, 2000. - 13 lk.

5. Akulich I.L. Matemaatiline programmeerimine näidetes ja ülesannetes:

6. Proc. üliõpilasmajanduse toetus. spetsialist. ülikoolid.-M.: Kõrg. kool, 1986.- 319s., ill.

7. Andronov S.A. Optimaalsed disainimeetodid: Loengu tekst / SPbGUAP. SPb., 2001. 169 lk.: ill.

Sarnased dokumendid

Algoritm lineaarse programmeerimise ülesannete lahendamiseks simpleksmeetodil. Lineaarse programmeerimisülesande matemaatilise mudeli konstrueerimine. Lineaarse programmeerimise ülesande lahendamine Excelis. Kasumi ja optimaalse tootmisplaani leidmine.

kursusetöö, lisatud 21.03.2012


Graafiline ülesannete lahendamine. Matemaatilise mudeli koostamine. Sihtfunktsiooni maksimaalse väärtuse määramine. Lahendus simpleksmeetodil kanoonilise lineaarse programmeerimise ülesande tehisliku alusega. Lahenduse optimaalsuse kontrollimine.

test, lisatud 04.05.2016


Lineaarse programmeerimise teoreetilised alused. Lineaarse programmeerimise ülesanded, lahendusmeetodid. Optimaalse lahenduse analüüs. Üheindeksilise lineaarse programmeerimise ülesande lahendus. Probleemi avaldus ja andmete sisestamine. Mudeliehitus ja lahendusetapid.

kursusetöö, lisatud 12.09.2008


Matemaatilise mudeli konstrueerimine. Lineaarse programmeerimise otseülesande lahendamise meetodi valik, põhjendus ja kirjeldamine simpleksmeetodil, kasutades simplekstabelit. Duaalülesande sõnastamine ja lahendamine. Tundlikkuse mudeli analüüs.

kursusetöö, lisatud 31.10.2014


Matemaatilise mudeli loomine ettevõtte kasumi maksimeerimiseks, probleemi graafiline lahendus. Probleemide lahendamine lisandmooduli SOLVER abil. Ressursivarude muutuste analüüs. Sihtfunktsiooni koefitsientide muutumise piiride määramine.

kursusetöö, lisatud 17.12.2014


Matemaatiline programmeerimine. Lineaarne programmeerimine. Lineaarse programmeerimise probleemid. Graafiline meetod lineaarse programmeerimise ülesande lahendamiseks. Lineaarse programmeerimise probleemi majanduslik sõnastus. Matemaatilise mudeli konstrueerimine.

kursusetöö, lisatud 13.10.2008


Lineaarse programmeerimise ülesande lahendamine graafilisel meetodil, selle kontrollimine MS Excelis. Probleemilahenduse sisestruktuuri analüüs programmis. Tootmisplaani optimeerimine. Ülesande lahendamine simpleksmeetodil. Mitme kanaliga järjekorrasüsteem.

test, lisatud 05.02.2012


Lineaarse programmeerimise ülesande lahendamine simpleksmeetodil: ülesande püstitamine, majandusliku ja matemaatilise mudeli koostamine. Transpordiprobleemi lahendamine potentsiaalide meetodil: esialgse referentsplaani koostamine, selle optimaalse väärtuse määramine.

test, lisatud 11.04.2012


Mittelineaarse programmeerimise probleemi avaldus. Statsionaarsete punktide ja nende tüübi määramine. Tasemejoonte konstrueerimine, eesmärgifunktsiooni ja piirangute kolmemõõtmeline graafik. Ülesande graafiline ja analüütiline lahendus. Kasutusjuhend ja algoritmskeem.

kursusetöö, lisatud 17.12.2012


Lineaarse programmeerimise ülesande lahenduse analüüs. Simpleksmeetod, kasutades simplekstabeleid. LP-ülesannete modelleerimine ja lahendamine arvutis. Probleemi optimaalse lahenduse majanduslik tõlgendamine. Transpordiprobleemi matemaatiline sõnastus.

TEEMA: LINEAARPROGRAMMEERIMINE

ÜLESANNE 2.A. Lineaarse programmeerimise ülesande lahendamine graafilisel meetodil

Tähelepanu!

Tegemist on teose nr 2073 TUTVUSTUSVERSIOONIGA, originaali hind 200 rubla. Disainitud Microsoft Wordis.

Makse. Kontaktid.

Valik 7. Leia maksimaalne ja minimaalne väärtuslineaarne funktsioonФ \u003d 2x 1 - 2 x 2piirangutega: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Lahendus:

Asendades tinglikult ebavõrdsuse märgid võrdusmärkidega, saame võrrandisüsteemi x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Nende võrrandite järgi konstrueerime sirgjooned, seejärel valime vastavalt ebavõrdsuse märkidele pooltasandid ja saame nende ühisosa - ODE lubatavate lahendite piirkonna - nelinurga MNPQ.

Funktsiooni minimaalne väärtus

tsii - punktis M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Maksimaalne väärtus saavutatakse punktis N (10; 0),

Ф max \u003d 2 10 - 2 0 \u003d 20.

Valik 8. Leia maksimum- ja miinimumväärtused

lineaarfunktsioon Ф \u003d x 1 + x 2

piirangutega: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Lahendus:

Asendades tinglikult ebavõrdsuse märgid võrdusmärkidega, saame võrrandisüsteemi x1 - 4 x2 = 4;

3 x1 - x2 = 0;

Nende võrrandite järgi konstrueerime sirgjooned, seejärel valime vastavalt ebavõrdsuse märkidele pooltasandid ja saame nende ühisosa - ODE lubatavate lahendite piirkonna - piiramata hulknurga MNPQ.

Funktsiooni minimaalne väärtus

sioonid - näiteks sirgel NP

punktis Р(4; 0)

Ф min = 4 + 0 = 4.

ODE ei ole ülalt piiratud, seega Ф max = + ∞.

Valik 10. Leia maksimum- ja miinimumväärtused

lineaarne funktsioon Ф \u003d 2 x 1 - 3 x 2

piirangutega: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

Asendades tinglikult ebavõrdsuse märgid võrdusmärkidega, saame võrrandisüsteemi

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Nende võrrandite järgi konstrueerime sirgjooned, seejärel valime vastavalt ebavõrdsuse märkidele pooltasandid ja saame nende ühisosa - ODE lubatavate lahendite piirkonna - hulknurga MNPQRS.

Konstrueerime vektori Г(2; -3) ja joonistame läbi alguspunkti taseme joon- sirge.

Liigume taseme joont suunas, samal ajal kui F väärtus suureneb. Punktis S(7; 0) saavutab sihtfunktsioon maksimumi Ф max =2·7–3·0= = 14. Nihutame nivoojoont suunas, samal ajal kui Ф väärtus väheneb. Funktsiooni minimaalne väärtus on punktis N(0; 5)

Ф min = 2 0 – 3 5 = –15.

ÜLESANNE 2.B. Lineaarse programmeerimise ülesande lahendamine

analüütiline simpleksmeetod

Valik 7. Minimeerige sihtfunktsioon Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

piirangutega: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Lahendus:

Tundmatute arv n=6, võrrandite arv m=3. Seetõttu võib r = n-m = 3 tundmatut võtta vabaks. Valime x 1 , x 3 ja x 6 .

Avaldame põhimuutujad x 2 , x 4 ja x 5 vabadena ja viime süsteemi ühikupõhisele

x 2 \u003d 2–3 x 1 + 4 x 3–2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Eesmärgi funktsioon näeb välja selline:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Paneme x 1 \u003d x 3 \u003d x 6 \u003d 0, samas kui põhimuutujad võtavad väärtused x 2 \u003d 2; x 4 \u003d 9; x 5 \u003d 6, see tähendab esimene teostatav lahendus (0; 2; 0; 9; 6; 0), sihtfunktsioon Ф 1 \u003d 13.

Muutujad x 3 ja x 6 sisalduvad sihtfunktsioonis negatiivsete koefitsientidega, seetõttu nende väärtuste suurenemisel Ф väärtus väheneb. Võtame näiteks x 6 . Süsteemi 1. võrrandist (*) on näha, et x 6 väärtuse suurendamine on võimalik kuni x 6 \u003d 1 (nii kaua kui x 2 ³ 0). Sel juhul säilitavad x 1 ja x 3 väärtused, mis on võrdsed nulliga. Nüüd võtame põhimuutujatena x 4, x 5, x 6, vabaks - x 1, x 2, x 3. Avaldagem uusi põhimuutujaid uute vabade muutujatena. Hangi

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Määrake vabadele muutujatele nullväärtused, see tähendab x 1 \u003d x 2 \u003d x 3 \u003d 0, samas kui x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, see tähendab kolmas kehtiv lahendus (0; 0; 0; 3; 4; 1). Sel juhul Ф 3 \u003d 6.

Muutuja x 3 sisaldub sihtfunktsioonis negatiivse koefitsiendiga, mistõttu x 3 suurenemine nulli suhtes toob kaasa F vähenemise. 2. võrrandist on näha, et x 3 võib suureneda kuni 1/ 4, alates 3. võrrandist - kuni 2/3 . Teine võrrand on kriitilisem. Muutuja x 3 tõlgime põhiliste arvuks, x 4 vabade arvuks.

Nüüd võtame uuteks vabadeks muutujateks x 1 , x 2 ja x 4. Avaldame nende kaudu uusi põhimuutujaid x 3 , x 5 , x 6. Tutvume süsteemiga

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Eesmärgifunktsioon saab kuju

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Muutujad x 1 ja x 2 sisalduvad sihtfunktsioonis negatiivsete koefitsientidega, seetõttu nende väärtuste suurenemisel Ф väärtus väheneb. Võtame näiteks x 2 . Süsteemi teisest võrrandist on näha, et x 2 väärtuse suurendamine on võimalik kuni x 2 \u003d 5 (nii kaua kui x 5 ³ 0). Sel juhul säilitavad x 1 ja x 4 väärtused nulli, teiste muutujate väärtused on võrdsed x 3 = 3/2; x 5 \u003d 0, x 6 = 3/2, see tähendab neljas kehtiv lahendus (0; 5; 3/2; 0; 0; 3/2). Sel juhul Ф 4 \u003d 5/4.

Nüüd võtame uuteks vabadeks muutujateks x 1 , x 4 ja x 5. Avaldame nende kaudu uusi põhimuutujaid x 2 , x 3 , x 6. Tutvume süsteemiga

x 2 \u003d 5–4 x 1 + x 4–2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Eesmärgifunktsioon saab kuju

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Mõlema muutuja koefitsiendid Ф avaldises on positiivsed, seetõttu on Ф väärtuse edasine vähenemine võimatu.

See tähendab, et minimaalne väärtus Ф min = -5, viimane teostatav lahendus (0; 5; 3/2; 0; 0; 3/2) on optimaalne.

Variant 8. Maksimeerige sihtfunktsioon Ф = 4 x 5 + 2 x 6

piirangutega: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Lahendus:

Võrrandite arv on 4, tundmatute arv 6. Seetõttu saab r = n - m = 6 - 4 = 2 muutujat valida vabaks, 4 muutujat põhiliseks. Vabadeks valime x 5 ja x 6, põhilisteks x 1, x 2, x 3, x 4. Avaldame põhimuutujad vabade kaudu ja taandame võrrandisüsteemi ühikupõhiseks

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Kirjutame sihtfunktsiooni kujul Ф = 4 x 5 + 2 x 6 . Määrame vabadele muutujatele x 5 = x 6 = 0 nullväärtused. Sel juhul saavad põhimuutujad väärtused x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , see tähendab, et saame esimese võimaliku lahendi (12, 30 , 6, 9, 0,) ja Ф 1 = 0.

Mõlemad vabad muutujad sisenevad sihtfunktsiooni positiivsete koefitsientidega, st F-i edasine suurendamine on võimalik. Tõlgime näiteks x 6 põhiliste arvuks. Võrrand (1) näitab, et x 1 = 0 x 5 = 12 korral (2) ÷ (4) x 6 siseneb positiivsete koefitsientidega. Liigume edasi uuele alusele: põhimuutujad - x 6, x 2, x 3, x 4, vabad - x 1, x 5. Avaldame uusi põhimuutujaid uute vabade kaudu

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

Sihtfunktsioon on kujul Ф = 24 - 2 x 1 + 2 x 5 ;

Määrame vabadele muutujatele x 1 = x 5 = 0 nullväärtused. Sel juhul saavad põhimuutujad väärtused x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , see tähendab, et saame teise võimaliku lahendi (0, 42 , 30, 21, 0, 12) ja Ф 2 = 24.

Sihtfunktsioon x 5 siseneb positiivse koefitsiendiga, st F-i edasine suurendamine on võimalik. Liigume edasi uuele alusele: põhimuutujad - x 6, x 5, x 3, x 4, vabad - x 1 , x 2. Avaldame uusi põhimuutujaid läbi new free

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Sihtfunktsioon on kujul Ф = 38 - 7/2 x 1 - 1/3 x 2;

Määrake vabadele muutujatele nullväärtused x 1 = x 2 = 0. Sel juhul saavad põhimuutujad väärtused x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, see tähendab, et saame kolmanda võimaliku lahenduse X 3 = (0, 0, 9, 7/2, 7, 5) ja Ф 3 = 38.

Mõlemad muutujad sisenevad sihtfunktsiooni negatiivsete koefitsientidega, see tähendab, et Ф edasine suurendamine on võimatu.

Seetõttu on viimane teostatav lahendus optimaalne, st Х opt = (0, 0, 9, 7/2, 7, 5) ja Ф max = 38.

Valik 10. Maksimeerige sihtfunktsioon Ф \u003d x 2 + x 3

piirangutega: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Lahendus:

Võrrandisüsteem - piirangud on järjekindel, kuna võrrandisüsteemi maatriksi ja laiendatud maatriksi auastmed on samad ja võrdsed 2-ga. Seetõttu võib kahte muutujat võtta vabana, kahte muud muutujat - põhilist - saab võtta väljendatuna lineaarselt kahe vaba kaudu.

Võtame vabadeks muutujateks x 2 ja x 3. Siis on põhilised muutujad x 1 ja x 2, mida väljendame vabade kujul.

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

Sihtfunktsioon on juba väljendatud x 2 ja x 3 kujul, st Ф = x 2 + x 3 .

Kui x 2 = 0 ja x 3 = 0, on põhimuutujad võrdsed x 1 \u003d 1, x 4 \u003d 2.

Meil on esimene teostatav lahendus X 1 = (1, 0, 0, 2), samas kui Ф 1 = 0.

Ф suurenemine on võimalik, kui suureneb näiteks väärtus x 3, mis sisaldub Ф avaldises positiivse koefitsiendiga (x 2 jääb võrdseks nulliga). Süsteemi esimeses võrrandis (*) on näha, et x 3 saab suurendada 1-ni (tingimusest x 1 ³0), see tähendab, et see võrrand seab piirangu x 3 väärtuse suurendamisele. Süsteemi esimene võrrand (*) on lahenemas. Selle võrrandi alusel läheme uuele alusele, muutes x 1 ja x 3 kohta. Nüüd on põhimuutujad x 3 ja x 4, vabad - x 1 ja x 2. Nüüd väljendame x 3 ja x 4 väärtustega x 1 ja x 2.

Saame: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Võrdsustades vabad muutujad nulliga, saame teise lubatava põhilahenduse X 2 = (0; 0; 1; 4), milles Ф 2 =1.

F suurenemine on võimalik x 2 suurenemisega. Viimase võrrandisüsteemi (**) järgi otsustades ei ole x 2 suurenemine piiratud. Seetõttu võtab Ф kõik suured positiivsed väärtused, st Ф max = + ¥.

Seega ei ole sihtfunktsioon Ф ülalt piiratud, seega pole optimaalset lahendust.

ÜLESANNE 2.D. Kirjutage etteantud probleemiga duaalne ülesanne.

algne ülesanne.

Variant 7. Maksimeerige sihtfunktsioon Ф = 2× x 1 - x 4

piirangutega: x 1 + x 2 \u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Lahendus:

Toome piirangute süsteemi ühele, näiteks kanoonilisele kujule, lisades 2. ja 3. võrrandisse täiendavaid muutujaid

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

Saime 2. tüüpi asümmeetrilise probleemi. Kahekordne probleem näeb välja järgmine:

Minimeeri sihtfunktsioon F = 20 × y 1 + 5 × a 2 + 8 × y 3

y jaoks 1 – y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Valik 8. Maksimeerige sihtfunktsioon Ф \u003d x 2 - x 4 - 3× x 5

piirangutega: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Lahendus:

Meil on algne maksimeerimisprobleem piirangute süsteemiga võrrandite kujul, see tähendab, et duaalülesannete paaril on 2. tüüpi asümmeetriline vorm, mille matemaatiline mudel maatrikskujul on järgmine:

Esialgne probleem: topeltprobleem:

F = S × X max F = B T × Ymin

aadressil A × X \u003d B kohas A T × Y ≥ C T

Algülesandes on sihtfunktsiooni muutujate koefitsientide maatriksrida kujul С = (0; 1; 0; -1; -3; 0),

vabade terminite veerumaatriks ja piirangusüsteemi muutujate koefitsientide maatriks on kujul

B \u003d 2, A = 0 - 4 1 2 -1 0

Leidke transponeeritud koefitsientide maatriks, sihtfunktsiooni muutujate koefitsientide maatriksrida ja vabaliikmete maatriks-veerg

0 1 0 0 V T \u003d (1; 2; 5)

A T = -1 2 0 C T = -1

Kahekordse probleemi saab kirjutada järgmisel kujul:

leida sihtfunktsiooni F = y 1 + 2 minimaalne väärtus × y 2 + 5 × y 3

piirangute korral y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Valik 10. Minimeerige funktsioon Ф = x 1 + x 2 + x 3

piiratud: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Lahendus:

Meil on algne minimeerimisprobleem piirangute süsteemiga ebavõrdsuse kujul, see tähendab, et duaalülesannete paaril on 3. tüüpi sümmeetriline vorm, mille matemaatiline mudel maatrikskujul on järgmine:

Algne probleem Kahekordne probleem

F = S × X min F \u003d B T × Ymax

aadressil A × X ≥ B juures A T × Y ≤ C T

X ≥ 0 Y ≥ 0

Algülesandes on sihtfunktsiooni muutujate koefitsientide maatriks-rida, vabaliikmete maatriks-veerg ja piirangusüsteemi muutujate koefitsientide maatriks kujuga

C \u003d (1; 1; 1), B = 3, A = 6 4 5

Leiame duaalülesande maatriksid

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Kahekordne probleem on sõnastatud järgmiselt:

Maksimeerige sihtfunktsioon F = 2y 1 + 3y 2 + 4y 3

piirangute alusel 3 × y 1 + 6 × a 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

ÜLESANNE 2.C. Lineaarse programmeerimise ülesande lahendamine simplekstabelite abil.

Valik 7. Suurendage sihtfunktsiooni Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

piirangutega: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Lahendus:

Me taandame piirangute süsteemi kanoonilisele kujule

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 + 3 x 3 + x 4 + z 3 = 8. (3)

Meil on 3 võrrandi süsteem 7 tundmatuga. Põhimuutujateks valime x 1, z 1, z 3, vabadeks x 2, x 3, x 4, z 2, põhimuutujaid väljendame nende kaudu.

Alates (2) on meil x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Asendades punktides (1) ja (3), saame

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

Koostage simplekstabel

I iteratsioon Tabel 1

Põhiline AC	Vabadus. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II iteratsioon Tabel 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III iteratsioon Tabel 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

IV iteratsioon Tabel 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

Viimase tabeli indeksireal pole negatiivseid numbreid ehk sihtfunktsiooni avaldises on kõik Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Vastus: Ф max = 149/14,

optimaalne lahendus (0; 0; 25/14; 37/14; 1/2; 0; 0)

Valik 8. Minimeeri sihtfunktsioon Ф = 5 x 1 - x 3

piirangutega: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Lahendus:

Muutujate arv on 4, maatriksi järjestus on ​2, seega on vabade muutujate arv r \u003d 4 - 2 \u003d 2, põhimuutujate arv on samuti 2. Võtame x 3, x 4 vabade muutujatena väljendame põhimuutujad x 1, x 2 vabadena ja toome süsteemi ühikupõhisele:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4

Kirjutame võrrandisüsteemi ja sihtfunktsiooni simplekstabelile sobival kujul, st x 2 + 2 x 4 = 1,

x 1 + 2 x 3 - 3 x 4 = 2

Ф + 11 x 3 - 15 x 4 \u003d 10

Teeme laua

I iteratsioon Tabel 1

Põhiline AC	Vabadus. AC
x1	2	1	0		— 3		1/2
x2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 = 10.

II iteratsioon Tabel 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 = -1.

III iteratsioon Tabel 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

Viimase tabeli indeksireal pole positiivseid arve ehk sihtfunktsiooni avaldises kõik Г i > 0. Meil ​​on juhtum I, seega on viimane põhilahend optimaalne.

Vastus: Ф min = -7/4, optimaalne lahendus (0; 0; 7/4; 1/2)

********************

Valik 10. Minimeerige sihtfunktsioon Ф \u003d x 1 + x 2,

piirangutega: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Lahendus:

Muutujate arv on 5, maatriksi järjestus on ​3, seega on vabade muutujate arv r \u003d 6-3 \u003d 2. Vabade muutujatena võtame x 3 ja x 4, x 1, x 2, x 5 kui põhilised. Kõik süsteemi võrrandid on juba taandatud ühele alusele (põhimuutujad on väljendatud vabadena), kuid need on kirjutatud kujul, mis pole mugav simplekstabelite kasutamiseks. Kirjutame võrrandisüsteemi vormile

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 + 2 x 4 \u003d 1

x 5 + x 3 - x 4 . = 5

Avaldame sihtfunktsiooni vabade muutujate kaudu ja kirjutame selle kujul Ф - 3 x 3 +3 x 4 = 3

Teeme laua

I iteratsioon Tabel 1

Põhiline AC	Vabadus. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 \u003d 3.

tabel 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

Viimase tabeli indeksireal pole positiivseid arve ehk sihtfunktsiooni avaldises kõik Гi > 0. Meil ​​on juhtum 1, seega on viimane põhilahend optimaalne.

Vastus: Ф min = 3/2, optimaalne lahendus on (3/2; 0; 0; 1/2; 11/2).

Jagame kolmanda rea ​​võtmeelemendiga, mis on võrdne 5-ga, saame uue tabeli kolmanda rea.

Alusveerud vastavad üksikutele veergudele.

Ülejäänud tabeli väärtuste arvutamine:

"BP – põhiplaan":

; ;

"x1": ; ;

"x5": ; .

Indeksirea väärtused on mittenegatiivsed, seega saame optimaalse lahenduse: , ; .

Vastus: toodetud toodete müügist saadav maksimaalne kasum, mis on võrdne 160/3 ühikuga, tagatakse ainult teist tüüpi toodete vabastamisega 80/9 ühikut.

Ülesanne number 2

Antud on mittelineaarse programmeerimise probleem. Leia graafianalüütilise meetodi abil sihtfunktsiooni maksimum ja miinimum. Koostage Lagrange'i funktsioon ja näidake seda äärmuslikes punktides piisavad tingimused miinimum (maksimaalne).

Sest šifri viimane number on 8, siis A=2; B=5.

Sest šifri eelviimane number on 1, siis tuleks valida ülesanne number 1.

Lahendus:

1) Joonistame piirkonna, mille võrratuste süsteem defineerib.

See ala on kolmnurk ABC, mille tippude koordinaadid: A(0; 2); B(4; 6) ja C(16/3; 14/3).

Objektifunktsiooni tasemed on ringid, mille keskpunkt on punkt (2; 5). Raadiuste ruudud on sihtfunktsiooni väärtused. Siis on joonisel näha, et sihtfunktsiooni minimaalne väärtus saavutatakse punktis H, maksimaalne väärtus on kas punktis A või punktis C.

Sihtfunktsiooni väärtus punktis A: ;

Sihtfunktsiooni väärtus punktis C: ;

See tähendab, et funktsiooni maksimaalne väärtus saavutatakse punktis A(0; 2) ja see on võrdne 13-ga.

Leiame punkti H koordinaadid.

Selleks kaaluge süsteemi:

ó

ó

Sirg on ringi puutuja, kui võrrandil on kordumatu lahendus. Ruutvõrrand on unikaalne lahendus, kui diskriminant on 0.

Siis ; ; - funktsiooni minimaalne väärtus.

2) Minimaalse lahenduse leidmiseks koostage Lagrange'i funktsioon:

Kell x 1 =2.5; x 2 =4.5 saame:

ó

Süsteemis on lahendus s.t. piisavad äärmuslikud tingimused on täidetud.

Maksimaalse lahenduse leidmiseks koostame funktsiooni Lagrange:

Ekstreemumi jaoks piisavad tingimused:

Kell x 1 =0; x 2 =2 saame:

ó ó

Süsteemil on ka lahendus, st. piisavad äärmuslikud tingimused on täidetud.

Vastus: sihtfunktsiooni miinimum on saavutatud ; ; maksimaalne sihtfunktsioon saavutatakse siis, kui ; .

Ülesanne number 3

Kahele ettevõttele eraldatakse vahendeid summas dühikut. Kui eraldatakse esimesele ettevõttele aastaks x rahaühikuid, millest see tulu annab k 1 xühikut ja kui see eraldatakse teisele ettevõttele y rahaühikut, annab see tulu k 1 yühikut. Esimese ettevõtte rahajääk aasta lõpus on võrdne nx, ja teise jaoks minu. Kuidas jagada kõik vahendid 4 aasta jooksul nii, et kogutulu oleks suurim? Lahendage probleem dünaamilise programmeerimisega.

i = 8, k = 1.

A = 2200; k 1 = 6; k2=1; n = 0,2; m = 0,5.

Lahendus:

Kogu 4-aastane periood on jagatud neljaks etapiks, millest igaüks on võrdne ühe aastaga. Nummerdame etapid alates esimesest aastast. Olgu X k ja Y k vastavalt ettevõtetele A ja B eraldatud vahendid k-ndas etapis. Siis on summa X k + Y k =a k k - selles etapis kasutatud ja eelmisest etapist k jäänud vahendite kogusumma - 1. Esimesel etapil kasutatakse ära kõik eraldatud vahendid ja a 1 = 2200 ühikut. tulu, mis saadakse k - selles etapis, kui eraldatakse X k ja Y k ühikut, on 6X k + 1Y k . olgu viimastel etappidel saadud maksimaalne tulu alates k-st - see etapp on f k (a k) ühikut. Kirjutame optimaalsuse põhimõtet väljendava funktsionaalse Bellmani võrrandi: olenemata algolekust ja esialgne lahendus järgnev lahendus peab olema algolekust tuleneva oleku suhtes optimaalne:

Iga etapi jaoks peate valima väärtuse X k ja väärtuse Y k=ak- Xk. Seda silmas pidades leiame sissetuleku k-ndas etapis:

Funktsionaalne Bellmani võrrand näeb välja järgmine:

Kaaluge kõiki etappe, alustades viimasest.

(kuna lineaarfunktsiooni maksimum saavutatakse lõigu lõpus x 4 = a 4);