Metode de rezolvare a prezentării de programare liniară. Prezentare: Programare liniară, rezolvarea problemelor cu o metodă simplăX. Sarcina de minimizare a funcției liniare

Făcând clic pe butonul "Descărcați arhiva", descărcați fișierul de care aveți nevoie complet gratuit.
Înainte de a descărca acest fișier, amintiți-vă aceste eseuri bune, control, cursuri, teză, articole și alte documente care sunt nerevendicate în computerul dvs. Aceasta este munca dvs., ar trebui să participe la dezvoltarea societății și să beneficieze de oameni. Găsiți aceste lucrări și trimiteți la baza cunoștințelor.
Noi și toți studenții, absolvenți, tineri oameni de știință care folosesc baza de cunoștințe în studiile și munca lor, vă vor fi foarte recunoscători.

Pentru a descărca arhiva cu documentul, în caseta de mai jos, introduceți numărul de cinci cifre și faceți clic pe butonul "Descărcați arhiva"

Documente similare

Optimizarea sarcinilor. Restricții privind setul permis. Sarcina de optimizare clasică. Funcția Lagrange. Programare liniară: sarcini de formulare și soluția lor grafică. Metoda algebrică Rezolvarea problemelor. Simplex-metoda, tabelul simplex.

rezumat, adăugat 29.09.2008

Clasificarea sarcinilor de programare matematică. Esența metodei grafice pentru rezolvarea problemelor de programare liniară, algoritmul metodei de tabel simplex. Descrierea structurii logice și a textului programului pentru a rezolva problema cu o metodă grafică.

cursuri, a adăugat 03/27/2011

Sarcini comune de programare liniară. Descrierea algoritmului metodei simplex înregistrate în formă canonică cu constrângeri unilaterale. Algoritmul pentru construirea unui plan de referință inițial pentru a rezolva problema. Algoritm de bază artificială avansată.

cursuri, a fost adăugată 24.10.2012

Bazele matematice de optimizare. Setarea problemei de optimizare. Metode de optimizare. Rezolvarea sarcinii unei metode clasice simplex. Metoda grafică. Rezolvarea sarcinilor folosind Excel. Coeficienții de funcții țintă. Programare liniară, metodă, sarcini.

rezumat, adăugat 08/21/2008

Statutul sarcinii de programare liniară. Rezolvarea sistemului de ecuații simplex-metodă. Dezvoltarea programului de utilizare a metodei simplex. Blocarea diagramelor algoritmilor de bază. Crearea unei interfețe, manual de utilizare pentru aplicarea programului.

lucrări de curs, a fost adăugată 05.01.2015

Esența programării liniare. Formularea matematică a problemei LP și algoritmul soluției sale utilizând metoda simplăX. Dezvoltarea unui program de planificare a producției pentru a asigura profiturile maxime: diagrama bloc, listarea, rezultatele.

lucrări de curs, a fost adăugată 11.02.2011

Conceptul de teorie a optimizării sarcinilor economice. Esența metodei simplex, dualitatea în programarea liniară. Elemente ale teoriei jocurilor și luării deciziilor, soluționarea sarcinii de transport. Caracteristicile de planificare a rețelei și sarcina matricei de grafice.

Introducere

Programarea liniară ca o secțiune a studiului operațiunilor are aproape o istorie de patruzeci de ani. Introducerea echipamentului de calcul a dat un impuls semnificativ cercetării în acest domeniu de matematică. Au fost dezvoltate un număr de algoritmi pentru rezolvarea problemelor de programare liniare, iar în anii următori, programele și pachetele de programe au fost create în principal pentru computere mari. Cea mai mare parte a software-ului de literatură. Programarea liniară în țara noastră a fost lansată în anii '60 - '70. Studiile din acest domeniu (atât teoretice, cât și aplicate) continuând și în prezent.

Metodele de programare liniară au fost foarte eficiente pentru rezolvarea unor sarcini din zona studiului de operațiuni. Cuvântul "programare" înțelegem ca planificare, ceea ce definește natura aplicațiilor luate în considerare. Principalele idei ale programării liniare au apărut în timpul celui de-al doilea război mondial din cauza căutării unor strategii optime la efectuarea de operațiuni militare. De atunci, au găsit o utilizare largă în industrie, comerț și management - atât în \u200b\u200bscări locale, cât și în scalele publice. Aceste metode pot rezolva multe sarcini (deși nu toate) asociate cu utilizarea eficientă a resurselor limitate.

Metodele și modelele matematice sunt bine cunoscute, distribuite și utilizate sub diverse nume - metode matematice în luarea deciziilor; Metode de cercetare a operațiunilor; Metode economice și matematice; Metode de cibernetică economică; Metode de gestionare optimă, matematică aplicată în economia și organizarea producției etc. Într-o varietate de publicații pe această temă (mai mult sau mai puțin incluzive), acestea sunt luate în considerare în anumite combinații.

Operațiuni de cercetare - Disciplina științifică angajată în dezvoltarea și aplicarea practică a metodelor de gestionare cea mai eficientă a diferitelor sisteme organizaționale.

Controlul Orice sistem este implementat ca un proces supus anumitor modele. Cunoștințele lor ajută la determinarea condițiilor necesare și suficiente pentru punerea în aplicare a acestui proces. Pentru aceasta, toți parametrii care caracterizează procesul și condițiile externe trebuie să fie cuantificate, măsurate. În consecință, scopul studiului operațiunilor este o justificare cantitativă a deciziilor organizației de conducere.

Scopul întregii modelare este studiul obiectului la început pe calitate de înaltă calitate și apoi, deoarece informația și dezvoltarea modelului se acumulează și dezvoltarea modelului pentru niveluri cantitative din ce în ce mai precise.

Aceste considerații pot fi ilustrate printr-un exemplu simplu. Am existat (și am) metoda de "teoria probabilității" ca o clasă largă de modele matematice care operează conceptele de "probabilitate", "eveniment aleatoriu", "valoare aleatorie", "așteptarea matematică (valoarea medie) a unei variabile aleatorie "," Dispersie (împrăștiere) "și etc. la granița secolelor XIX și XX. Apare un obiect nou - un sistem de telefonie comutabilă, asociat cu conceptele de "aplicație de aplicare", "refuz", "timp de conectare", "comutator" și alte caracteristici ale sistemului.

În anii 20. A. K. Erlang a conectat această metodă și obiect; Ca rezultat, a fost creat un model matematic teoretic-probabilist al proceselor în rețelele telefonice comutate, care operează conceptele "fluxului de aplicații", "timpul mediu de așteptare", "lungimea medie a coada de așteptare", "dispersia timpului de așteptare" , "probabilitate de eșec" etc. Dezvoltarea în continuare a acestei direcții științifice a arătat fructuositatea bazei conceptuale a acestui model, caracteristicile sale constructive largi. Modelul sa dezvoltat într-o metodă de studiere a sistemelor complexe - "Teoria serviciului de masă", terminologia și baza conceptuală a cărora au fost abstracte de la asociații cu rețele telefonice și au găsit o tehnologie generală. Și acum modele noi pot fi construite prin aplicarea teoriei întreținerii în masă la alte obiecte (procese de producție, sisteme de operare de calculator, fluxuri de trafic etc.).

Astfel, pe de o parte, metoda este determinată dacă este dezvoltat un set omogen de modele, adică metodele de luare a diverselor obiecte într-un aspect, iar pe cealaltă, obiectul este învățat să cunoască mai mult decât cu cât mai mult Sunt dezvoltate modele de obiecte. În același timp, caracterul dual al modelului conduce la dualismul modelului conceptual de modelare, inclusiv comun (din metoda ") și specific (din conceptul" Obiect ").

Studiul operațiunilor este un set de metode matematice aplicate utilizate pentru rezolvarea sarcinilor organizaționale practice (inclusiv economice). Aceasta este o disciplină științifică cuprinzătoare. Gama de probleme studiate de acesta nu este suficientă. Uneori, studiul operațiunilor este înțeles foarte larg, inclusiv o serie de metode pur matematice în ea, uneori, dimpotrivă, foarte îngustă - ca metodologie practică pentru rezolvarea cu ajutorul modelelor economice și matematice de o listă strict definită de sarcini .

Principala metodă de cercetare este o analiză sistemică a acțiunilor vizate (operațiuni) și a unui obiectiv (în special cantitativ) comparativ al rezultatelor posibile ale acestor acțiuni.

Printre cele mai importante clase de sarcini, operațiunile de operațiuni pot fi numite sarcini de gestionare a stocurilor, distribuția resurselor și destinației (sarcini de distribuție), sarcinile de întreținere în masă, sarcinile de înlocuire a echipamentelor, raționalizarea și coordonarea (inclusiv teoria programului), Conteina (de exemplu, Teoria programului) , jocuri), sarcini de căutare și dr. Printre metodele utilizate - Programare matematică (liniară, neliniară etc.), ecuații diferențiale și diferență, teoria graficelor, procesele Markov, teoria jocului, soluțiile de teorie (statistic), teoria imaginii recunoașterea și un număr de alții.

Se crede că studiul operațiunilor a provenit în ajunul celui de-al doilea război mondial, când un grup de specialiști a fost creat în Anglia pe o stație Radar pentru a rezolva problemele tehnice cu ajutorul matematicii. Ei s-au concentrat pe compararea eficacității modalităților de rezolvare a problemelor, căutarea unei soluții optime. Participarea la acest grup de reprezentanți ai diferitelor specialități a predeterminat un complex sau, așa cum este acum obișnuit să vorbim, sistemic, abordare. În prezent, sute de instituții și grupuri de cercetare din zeci de țări lucrează în această direcție. Societatea pentru cercetarea operațiunilor Unite United de către Federația Internațională (IFORS) sunt organizate.

În crearea unui aparat matematic modern și dezvoltarea multor domenii de cercetare a operațiunilor, oamenii de știință din Rusia au contribuit la L.V. Kantorovich, N.P. Blenko, E.S. Ventcel, N.N. Vorobev, N.N. Moiseev, D.B. Yudin și multe altele.

Contribuția semnificativă la formarea și dezvoltarea cercetării operațiunilor făcute de oamenii de știință străini R. Akof, R. Belman, Danzig, Kun, J. Neuman, T. Saha, R. Churchman, A. COFMAN și alții.

Metodele de cercetare a operațiunilor, precum și orice metode matematice, sunt întotdeauna simplificate, reflectând procesele neliniare cu modele liniare, sistemele stochastice - deterministe etc. Prin urmare, nu ar trebui să exagereze valorile metodelor cantitative de cercetare și cel mai mic referitor la exemple de soluții nereușite. Se știe o definiție paradoxală care a dat un specialist american major în acest domeniu.

T. A. Sali: "Studiul operațiunilor este arta de a oferi răspunsuri rele la acele întrebări practice care au chiar și cele mai grave răspunsuri în alte moduri".

Academia Tehnică Interregională Centrală de Tehnologii Sectoriale și Antreprenoriat

Aproba

Adjunct. Director pentru partea academică

"" 200. g. .

SARCINA

pe designul cursului

pentru subiectul "Metode matematice"

Student: Sergeyev Evgeny Anatolyevich.

Subiectul proiectului: "Programare liniară, rezolvarea problemelor cu o metodă simplăX."

Notă explicativă

Introducere
Partea teoretică
Partea practică

Sarcini și soluția lor:

În primul rând:

Rezolva problema metodei simplex:

F \u003d 2x1 + 3x2 → max

3.1.2 Sarcina a doua:

Compania produce produse de două tipuri. Tipuri de materii prime, rezervele sale, rata materiei prime pe y. e. Fiecare tip de produs, profitul de producție din vânzarea de produse este prezentată în tabel:

3.1.3. A treia sarcină:

Compania produce 3 tipuri de produse, în timp ce utilizați 3 tipuri de materii prime. Stocurile de materii prime, normele fluxului său și profitul de la implementarea fiecărui produs sunt prezentate în tabel:

Cum ar trebui să fie planificată problema produsului astfel încât profitul să fie cel mai mare?

3.1.4. Sarcina patra:

Pentru fabricarea a 4 tipuri de produse, sunt utilizate 3 tipuri de materii prime. Stocurile de materii prime, normele fluxului său și profitul de la implementarea fiecărui produs sunt prezentate în tabel:

Cum ar trebui să fie planificată problema produsului astfel încât profitul să fie cel mai mare?

3. Concluzie

4. Bibliografie

Președinte al Comisiei de ciclism / Baranov V.A.

Șeful proiectului de curs / Karpushkin a.g.

Data emiterii de sarcini: Termenul limită:

"" 2007 "" 2007

Metoda simplăX.

Metoda simplă a fost propusă de omul de știință american J. Danzig în 1949, cu toate acestea, în 1939, ideile metodei au fost dezvoltate de oamenii de știință ruși

L. Kantorovici.

Metodă simplă care vă permite să rezolvați orice sarcină de programare liniară, universală. În prezent, este utilizat pentru calculele calculatorului, oricât de simple exemple utilizând metoda simplăX poate fi rezolvată manual.

Pentru a implementa metoda simplă - o îmbunătățire consistentă a soluției - este necesar să stăpânească trei principale

element:

Metoda de determinare a oricărui admisibil inițial

problema soluției de bază;

Regula de tranziție pentru mai bine (mai precis, nu cea mai gravă);

Criteriul pentru verificarea optimității soluției găsite.

Pentru a utiliza metoda simplă, problema de programare liniară trebuie să fie dată formei canonice, adică. Sistemul de restricții trebuie să fie reprezentat sub formă de ecuații.

Excepții obișnuite de Iordania

Luați în considerare sistemul de la ecuațiile liniare cu n necunoscut

a11 X1 + A12 X2 + ... + A1N XN \u003d B1,

aM1 X1 + AM2 X2 + ... + AMN XN \u003d BM.

Noi scriem acest sistem sub forma unei mese


	a11 ... A1J ... A1N
………………..
	aI1 ... AIJ ... AIN
………………..
	am1 ... amj ... amn

Etapa de excepție obișnuită Zhordanov (val), produsă deasupra acestui tabel cu un element de rezoluție AIJ ≠ 0 cu String String și J coloana solubilă, să numim funcționarea de rezolvare a ecuației

bI \u003d AI1 X1 + AI2 X2 + ... + AIJ XJ + ... + AIN XN

În raport cu XJ, substituind această soluție în sistemul original și înregistrarea sistemului nou recepționat sub forma unei noi mese.

Este ușor să verificați dacă se va vizualiza noua tabel


	b11 B12 ... A1J ... B1N
	b21 B22 ... A2J ... B2N
	………………..
	AI1 -A2 ... 1 ... -Ain
	………………..
	bM1 BM2 ... AMJ ... BMN

unde BRS \u003d ARS AIJ - ASJ AIS (I ≠ R, J ≠ s),

mai mult, toate elementele tabelului trebuie împărțite în AIJ.

Astfel, o etapă de excepții de la Iordania (link) traduce tabelul sursă într-o nouă schemă constând din următoarele 5 reguli:

1) Elementul care permite înlocuirea cu una

2) Elementele rămase ale coloanei de rezoluție j rămân neschimbate.

3) elementele rămase ale rândului de rezoluție i schimb doar semnele proprii.

4) Elementele BRS rămase sunt calculate de către BRS \u003d ARS AIJ - AIS AIS

5) Toate elementele noului tabel sunt împărțite într-un element de autorizare AIJ.

Exemplul 1. Pentru masă

Excepții Iordania permit sistemului cartesian luat în mod aleatoriu de avioane de coordonate pentru a merge la noul sistem în care coordonatele punctelor sunt evaziunea lor mai interesantă pentru una sau altă sarcină a sistemului avion.

Au modificat excepțiile Iordania

Dacă sistemul original de ecuații AI1 X1 + AI2 x2 + ... + AI2 X2 + ... + AIN XN \u003d BI, unde i \u003d 1, m,

scrieți în formularul -AI1 (-X1) - AI2 (-X2) - ... - Ain (-XN) \u003d BI

și faceți o masă

care este obținută în conformitate cu regulile 1 - 5 sunt legate de singura modificare pe care regulile 2 și 3 schimbă roluri:

1) elementele rămase ale șirului de rezoluție rămân neschimbate

2) elementele rămase ale coloanei de rezoluție schimbă numai semnele lor

Luați în considerare sistemul

2x1 + 3x2 - 5x3 \u003d 16 \u003d B1,

3x1 - 2x2 + 4x3 \u003d 36 \u003d B2,

5x1 + 7x2 - 11x3 \u003d 44 \u003d B3.

O scriem sub forma unei mese

Funcția liniară extremă

Să luăm în considerare sarcina generală a programării liniare. Baza metodelor de computere a LP este următoarea teoremă fundamentală.

Teorema. Dacă sarcina de programare liniară are o soluție optimă

(Într-o zonă limitată, întotdeauna și într-o regiune nelimitată, în funcție de funcția limitată Z), coincide cel puțin una dintre soluțiile de susținere ale sistemului de ecuații restrictive.

Conform acestei teoreme, în loc să examineze un set infinit de soluții admise pentru a găsi printre acestea soluția optimă dorită, este necesar să se investigheze numai numărul final de soluții de referință.

Această teoremă susține că există cel puțin o soluție optimă de referință, cu toate acestea, pot apărea mai multe soluții optime de referință în sarcini (alternativă la optimă).

În consecință, diagrama schematică a rezolvării problemelor de programare liniară este următoarea:

1. Cu plăcerea vom găsi toate soluțiile de referință ale sistemului.

a11 X1 + A12 X2 + ... + A1N XN \u003d B1,

……...................

aK1 X1 + AK2 X2 + ... + AKN XN \u003d BK,

aK + 1,1 x1 + AK + 1.2 x2 + ... + AK + 1N XN ≤ BK + 1,

……...................

aM1 X1 + AM2 X2 + ... + AMN XN ≤ Bm.

2. Calculați pentru fiecare dintre acestea valoarea funcției Z, determinată de raport.

Z \u003d C1 x1 + C2 x2 + ... + cn xn.

3. Selectați din ele Extreme Z.

Trebuie remarcat faptul că un număr foarte mare de soluții de referință poate fi, deci trebuie să produceți un bust ordonat al soluțiilor de asistență, realizând

fiecare etapă a schimbării monotonate a funcției Z.

O astfel de idee de îmbunătățire consecventă a soluției și este pusă în principala metodă computațională de rezolvare a unei sarcini de programare liniară, care a primit numele metodei simplex.

Metoda simplă bazată pe tabele complete

Stabilind problema determinării gamei optime de produse

Compania poate produce două tipuri de produse A și B, având o resursă limitată pentru materialul din fontă și, respectiv, în cantități de 350 și 392 kg și echipamente în cantitatea de ore de curgere de 408. Datele prezentate sub forma unui tabel caracterizează costurile fiecăruia dintre următoarele trei tipuri de resurse pentru fabricarea unui produs A și V.

Este necesar să se determine cât de multe produse A și B ar trebui să producă o întreprindere pentru a obține cel mai mare profit.

Introducem Necunoscut X1 și X2 dorit, indicând numărul de produse A și B, care ar trebui să producă o întreprindere.

Apoi, matematic, sarcina poate fi formulată după cum urmează.

Printre numeroasele soluții non-negative ale sistemului de inegalitate

14x1 + 5x2 ≤ 350, (1.1)

14x1 + 8x2 ≤ 392,

6x1 + 12x2 ≤ 408,

găsiți o astfel de soluție pentru care funcția

Z \u003d 10 x1 + 5 x2

atinge cea mai mare valoare.

Problema soluției geometrice

În primul rând, construim zona de soluții admise corespunzătoare sistemului de inegalități.

Pentru a face acest lucru, înlocuind fiecare inegalitate de egalitate

14x1 + 5x2 \u003d 350, (1 partea dreaptă),

14x1 + 8x2 \u003d 392, (a doua drept),

6x1 + 12x2 \u003d 408 (3d direct),

construi o linie de frontieră. Având în vedere că x1 ≥ 0 și x2 ≥ 0, obținem o parte umbroasă a planului care formează soluțiile poligonale OABCD (figura 1).

Apoi, construim o linie de nivel 10x1 + 5x2 \u003d 0 și vector (10; 5), care sunt reciproc perpendiculare. Este ușor să arătați că vectorul oferă direcția cea mai mare creștere a funcției liniare.

Într-adevăr

Z0 \u003d 10x10 + 5x20 \u003d 10 * 0 + 5 * 0 \u003d 0,

Za \u003d 10x1a + 5x2a \u003d 10 * 0 + 5 * 34 \u003d 170,

Zd \u003d 10x1d + 5x2D \u003d 10 * 25 + 5 * 0 \u003d 250, etc.

Din toate nivelurile de nivel, selectăm două, dintre care cineva trece prin punctul 0 și dă valoarea min Z, iar cealaltă trece prin punctul C și funcția Z pentru că este nevoie de valoare Mach. Aceste niveluri sunt numite referință.

Smochin. unu

Punctul C este format primul și al doilea drept. În consecință, rezolvarea sistemului de ecuații

14HLL + 5X2 \u003d 350,

14x1 + 8x2 \u003d 392,

vom găsi coordonatele punctului C

X1 \u003d 20, x2 \u003d 14,

În acest caz, Zmax \u003d 10 * 20 + 5 * 14 \u003d 270 de ruble.

Astfel, profitul MAK în 270 de ruble. Se va obține dacă compania produce 20 de produse de tip A și 14 din produsele V. V.

Funcția liniară Găsirea unui maxim

În centrul metodei simplexe de rezolvare a problemelor de programare liniare se află cu unele adăugări, o metodă dezasamblată anterior de excepții succesive, care este o combinație de algoritmi convenabili de calcul construit pe utilizarea secvențială a transformărilor identice (simplex) ale sistemului de ecuații.

Adăugând la partea stângă a inegalităților

14x1 + 5x2 ≤ 350,

14x1 + 8x2 ≤ 392,

6x1 + 12x2 ≤ 408,

unele valori non-negative yj ≥ 0 (i \u003d 1, 2, 3), (1.2)

numit variabila de nivelare sau de bază, transformați-le în ecuații:


	X1 + 5x2 + U1

În acest caz, se poate demonstra că fiecare soluție a sistemului de inegalitate (1.1) corespunde unei singure soluții a sistemului de ecuații (1.3) și inegalități (1.2) și invers.

Fiecare dintre variabilele Y1, U2, U3 intră într-o singură ecuație și depinde de variabilele X1 și X2, pe care le numim gratuit.

Sistemul (1,3) corespunde soluției de bază admisibile inițiale x1 \u003d x2 \u003d 0;

Y1 \u003d 350; Y2 \u003d 392; Y3 \u003d 408 și z \u003d 0.

Realizăm prima transformare a identității sistemului de ecuații (1.3). Selectați coloana de rezoluție corespunzătoare celui mai mic element negativ din rândul Z, pentru că este stabilit teoretic că poate fi de așteptat din alte condiții egale la zoomul mai mare al funcției Z. Partea dreaptă a ecuațiilor se împart la elemente a coloanei de rezoluție și selectați cea mai mică atitudine pozitivă corespunzătoare rezoluției (ecuației). La intersecția dintre coloanele selectate și șirurile permit numărul.

Prima ecuație se divide la rezoluție și scrie ecuația rezultată. Înmulțirea acestei ecuații cu 14, 6 și -10 și scăzând, respectiv, de la ecuațiile a 2-a, 3 și 4 ale sistemului (1.3), vom ajunge la următorul sistem (1.4):

		X2 + 1/4 y1 \u003d 25,

	X2 - 6/14 Y1 + U3

O conversie similară de identitate, în care alegerea rezoluției este făcută de regula specificată, va fi numită conversie simplă.

Astfel, transformarea simplăxă se efectuează în conformitate cu următoarea regulă:

1. Coloana de rezoluție este selectată corespunzătoare celui mai mic element negativ din rândul Z.

2. Rezoluția este selectată, care corespunde celei mai mici pozitive a relației dintre elementele din partea dreaptă a ecuațiilor la elementele corespunzătoare ale coloanei de rezoluție. La intersecția coloanei de rezoluție și șirul permanent este un număr de autorizare.

3. Elementele șirului permanent sunt împărțite într-un număr de autorizare.

4. Elementele celorlalte rânduri sunt calculate prin formula:

Din sistem (1.4) găsim cea de-a doua soluție permisă de bază x2 \u003d yl \u003d 0; X1 \u003d 25; Y2 \u003d 42; Y3 \u003d 258, care corespunde unei noi funcții extinse Z \u003d 250.

Astfel, procesul de transformări consecutive simplex este procesul de îmbunătățire consecventă a soluției. În care:

1. Dacă la linia z - există cel puțin un element negativ și

a) în coloana de rezoluție există cel puțin un element pozitiv, atunci soluția poate fi îmbunătățită;

b) Dacă coloana de rezoluție nu conține elemente pozitive, atunci funcția z crește pe o perioadă nedeterminată.

2. Dacă toate elementele din rândul Z nu sunt negative, se realizează soluția optimă.

Acestea sunt condiții suficiente pentru existența unui plan optim de soluție.

În sistem (1.4), coeficientul de la X2 din Z este o linie negativă, astfel că a doua coloană va fi rezolvată. Găsiți că al doilea șir va fi rezolvat. Apoi, producem conversia simplă a sistemului (1.4) prin consistența specificată:

X1 + 8/42 Y1 - 5/42 Y2 \u003d 20,

X2 - 1/3 Y1 + 1/3 Y2 \u003d 14,

20/7 Y1 - 23/7 Y2 + Y3 \u003d 120,

10/42 Y1 + 20/42 Y2 + Z \u003d 270, (1.5)

Deoarece în linia Z, toate elementele sunt non-negative, acest plan este optim. În acest caz, yl \u003d y2 \u003d 0; X1 \u003d 20; X2 \u003d 14 și zmax \u003d 270.

Implementarea transformărilor simplex este asociată cu calcularea dureroasă și adesea destul de voluminoasă. Aceste calcule pot fi în mare parte simplificate folosind așa-numitele tabele simplex pentru a rezolva problemele.

Fiecare conversie simplă a sistemului este redusă la trecerea de la o masă simplă la alta.

În consecință, sistemul inițial de ecuații (1.3) este primul tabel simplex (Tabelul 1.1).

Tabelul 1.1.

Prima coloană este o coloană variabilă de bază, în a doua coloană Există coeficienți liberi ai părții din dreapta a ecuațiilor (1.3), toate variabilele sunt amplasate în prima linie, ultima coloană este coloana de control și coeficienții din ea sunt egale cu suma tuturor coeficienților de șir.

De la masă. 1.1 Avem prima soluție admisă a sistemului (1.3) x1 \u003d x2 \u003d 0, y1 \u003d 350,

Y2 \u003d 392, Y3 \u003d 408, Z \u003d 0, care corespunde vârfului soluțiilor OABCD admisibile (fig.1).

Tranziția la cea de-a doua masă simplă (Tabelul 1.2) este efectuată în conformitate cu regula specificată în acest paragraf pentru transformările simplex ale sistemelor de ecuații, în timp ce variabila de rezoluție X1 merge la bază în loc de variabila care permite variabila Y1 primim tabelul. 1.2.

Tabelul 1.2.

După umplerea tabelului. 1.2 Este necesar să se verifice corectitudinea umplerii acestuia, pentru care rezumăm factorul de rând și această cantitate ar trebui să fie egală cu coeficienții din celulele coloanei celulare corespunzătoare. De la masă. 1.2 Cea de-a doua soluție admisă va fi x1 \u003d 25, x2 \u003d 0, y1 \u003d 0, y2 \u003d 42, y3 \u003d 258 și z \u003d 250.

Este ușor să vedeți că acest tabel corespunde sistemului (1.4) și soluției de referință

X1 \u003d 25, X2 \u003d 0 corespunde vertexului D (25,0) din soluțiile poligonale.

Deoarece în linia z - există un element negativ, apoi îmbunătățiți soluția, pentru care faceți o filă simplă. 1.3

Tabelul 1. 3

* Notă. Pentru ușurința calculelor, trebuie amintit că în noua tabel de pe site-ul elementelor coloanei de rezoluție (cu excepția elementului de rezoluție) sunt zerouri. Dacă rezoluția este zero în rezoluție, atunci coloanele corespunzătoare sunt transferate la noul tabel neschimbat:

Deoarece nu există elemente negative în z - linia, atunci această soluție va fi optimă.

Masa. 1.3 corespunde sistemului de ecuații (1,5) și soluției optime X1 \u003d 20,

X2 \u003d 14 și Zmax \u003d 270 și Vertex cu soluții OABCD de poligon (20,14).

Astfel de mese alungite care conțin toate variabilele din prima linie datorită prezenței unei coloane de comandă vă permit să controlați corectitudinea umplerii tabelelor și evitați erorile aritmetice.

Metoda simplă bazată pe mese scurtate

Luați în considerare sistemul de ecuații (1.3) și scrieți-l sub formă de tabelul 1.4

Tabelul 1.4.

În prima coloană, scrieți variabilele de bază (BP) și în primele variabile gratuite (SP). Apoi, tranziția la noul tabel 1.5 se efectuează prin regulă:

1) Schimbăm asociațiile mixte și bp

2) Pe site-ul elementului de rezoluție este valoarea lui inversă

3) Elemente ale deșeurilor de rezoluție Împărțirea la numărul permanent

4) Elemente ale coloanei de rezoluție Împărțiți-vă pe permăstarea pură și schimbarea semnului

5) Elementele rămase sunt situate ca capitol "Găsirea unui maxim de funcție liniară" Regula 4 (regula dreptunghiurilor pentru val). Avem masă 1.5.

Tabelul 1.6.

Planul optim Zmax \u003d 270 a fost obținut la X1 \u003d 20, X2 \u003d 14, iar resursele echipamentului au fost în exces în cantitatea de ore de curgere de 120.

Soluție de sarcină de programare liniară

Găsiți funcția maximă țintă

cu restricții

14x + 5Y ≤ 350

Soluția sarcinii utilizând programul Microsoft. Excela.

Atribimați A3 și B3 la valorile variabilelor x și y.

În celula C4, introducem funcția de țintă

În celulele A7: A9 introduc părți stânga ale restricțiilor

Și în celulele B7: B9 - părți dreapta ale restricțiilor.

După aceea, alege echipa Serviciu, Căutați soluții (Instrumente, Solver) și umpleți caseta de dialog Deschidere Soluție de soluție ( Solver) așa cum se arată în fig. 2. După ce faceți clic pe buton A executa (Rezolvați) deschide o fereastră Rezultate Rezultatele căutării. (Rezultatele solverului), care raportează că soluția este găsită (figura 3).

Smochin. 2. Căutați soluții

Smochin. 3. Rezolvarea rezultatelor

Soluție geometrică la program utilizând programul MATHCAD 2000.

Înregistrați în formularul Y \u003d KX + B Ecuațiile directe, limitând zona de valori admise ale variabilelor. Pentru a introduce și a rezolva restricția de 14x + 5Y ≤ 350, introduceți partea stângă a inegalității, apăsați simultan butonul CTRL și apăsați simultan butonul, în timp ce țineți timpul anterior până când se deschide semnul îndrăzneț \u003d, marcați variabila pliabilă Y, faceți clic pe În meniul simbolic (simboluri) de pe linia de rezolvare - rezultatul calculelor va fi afișat în documentul de lucru în partea dreaptă a ecuației; Introduceți numele funcției (în exemplul Y1 (x)) și alocați-l expresia rezultată. Astfel, se determină ecuația unuia dintre direcțiile, limitarea zonei de valori admise. În mod similar, introduceți alte limitări. Introduceți ecuația 10x + 5Y \u003d C Linia de linie (direcționarea directă). Acționează același lucru ca atunci când restricțiile sunt introduse, dar înainte de a permite ecuația la Y, setați orice valoare a constantului C.
Imagine pe diagramă dreaptă corespunzătoare și determină zona de soluții valide ale sistemului.
Schimbarea valorilor constantei C, de exemplu C \u003d 100,150,200,250, ..., urmăriți mișcarea directă a referinței și formulați ieșirea solvabilității problemei.
Dacă sarcina are o singură soluție, găsiți vârful în care Z \u003d Zmax. În exemplul nostru, valoarea maximă a funcției țintă se realizează la punctul de intersecție a Direct 14x + 5Y \u003d 350 și 7x + 14Y \u003d 196. Găsiți coordonatele punctului utilizând funcția de căutare.
Calculați valoarea funcției țintă la punctul găsit.

14x + 5Y \u003d 350 (-14/5) x + 70 Y1 (X): \u003d (-14/5) x + 70

7x + 4Y \u003d 196 (-7/4) x + 49 y2 (x): \u003d (-7/4) x + 49

x + 2Y \u003d 68 (-1/2) x + 34 Y3 (x): \u003d (-1/2) x + 34

10x + 5Y \u003d C -2x + (1/5) C Y4 (x): \u003d -2x + (1/5) C

Smochin. patru.

Găsiți (X, Y) → (20, 14)

f (x, y): \u003d 10x + 5Y

fmin: \u003d F (20, 14)

Soluție analitică la sarcina utilizând programul MATHCAD 2000.

Soluția analitică a sarcinii din MathCAD este mult mai ușoară.

Instalați modul automat de calcul.
Înregistrați sarcina arbitrară X și Y Stabiliți valori arbitrare (valide), astfel încât programul să poată porni contul.

Z (x, y): \u003d 10x + 5Y

14x + 5x ≤ 360

M: \u003d Maximizați (Z, X, Y) M \u003d (20, 14) Z (M0, M1) \u003d 270

Sarcina maximizării funcției liniare în prezența coeficienților liberi negativi

Găsiți o funcție liniară maximă

cu restricții

X1 - X2 ≤ 3,

2x1 - 3x2 ≤ 6,

X1 ≥ 0, x2 ≥ 0.

Noi scriem sistemul în formă

Y1 \u003d -X1 + X2 + 3 ≥ 0

Y2 \u003d x1 + x2 - 5 ≥ 0

Y3 \u003d -2x1 + 3x2 + 6 ≥ 0

Y4 \u003d -x2 + 6 ≥ 0

Faceți o masă.

Continuăm să lucrăm cu șirul 2, deoarece elementul negativ nu a dispărut. Facem Schumen cu rezoluția -2 element admisibil. Avem o masă.

Sarcina de minimizare a funcției liniare

Menținând problema minimizării pentru a maximiza funcția liniară

Am considerat soluționarea metodei simplex-metodă pentru găsirea unui maxim de funcție liniară

W \u003d c1 x1 + c2 x2 + ... + cn xn.

Cu toate acestea, multe sarcini economice necesită un minim de o funcție liniară. Pentru a face acest lucru, este suficient să puneți

W \u003d -Z \u003d -C1 x1 - C2 X2 - ... - CN XN

și rezolvați problema maximizării funcției obținute w sub limitările relevante. Deoarece este clar că

Minimizați funcția liniară

când efectuați restricții

7x1 + 2x2 ≥ 14,

5x1 + 6x2 ≤ 30,

3x1 + 8x2 ≥ 24,

X1 ≥ 0, x2 ≥ 0.

Soluția geometrică a problemei de pe (figura 5) și corespunde soluției optime la punct

C (48/11, 15/11) și în același timp Zmin \u003d -21/11.

Figura 5. Problema soluției geometrice

Introducerea variabilelor de aliniere yi ≥ 0 și funcția w \u003d -z \u003d 2x1 - 5x2 → max, sarcina este înregistrată în formular.

Y1 \u003d 7x1 + 2x2 - 14,

Y2 \u003d -5x1 - 6x2 + 30,

Y3 \u003d 3x1 + 8x2 - 24,

Înregistrați acest sistem sub forma unei mese.

Suntem să scăpăm de membrul liber negativ în linia Y1, făcând sania cu elementul de rezoluție "-50/8", obținem o masă.

Deoarece în linia W și în 1-coloană nu există elemente negative, au obținut soluția optimă x1 \u003d 48/11, x2 \u003d 15/11, wmax - 21/11 sau zmin \u003d -Wmax \u003d -21/11,

Partea practică

1. Rezolva problema metodei simplex.

X1 + 3X2 ≤ 300 F \u003d 2x1 + 3x2 → Max

Decizie

X1 + 3X2 + X3 \u003d 300 F - 2x1 - 3x2 \u003d 0

X1 + X2 + X4 \u003d 150

Răspuns: X1 \u003d 75; X2 \u003d 75; X3 \u003d 0; X4 \u003d 0.

Numărul de sarcină 1.

Compania produce produse de două tipuri. Tipuri de materii prime, rezervele sale, standardele ratei de materii prime la noi. Fiecare tip de produs, profitul de producție din vânzarea de produse este prezentată în tabel.

Decizie

2x1 + 2x2 ≤ 17

X1 + 3X2 + X3 \u003d 20 F - 2x1 - X2 \u003d 0

2x1 + x2 + x4 \u003d 10

2x1 + 2x2 + x5 \u003d 17

Răspuns: x1 \u003d 5; X2 \u003d 0; X3 \u003d 15; X4 \u003d 0; X5 \u003d 7.

Numărul de sarcină 2.

Există trei tipuri de produse la întreprindere, în timp ce sunt utilizate trei tipuri de materii prime. Rezervele de materii prime, normele debitului său și profitul de la implementarea fiecărui produs sunt prezentate în tabel.

Cum ar trebui să fie plantată problema produsului astfel încât profitul întreprinderii să fie cel mai înalt?

Decizie

2x1 + 3x2 + 7x3 ≤ 1250 F \u003d 41x1 + 35x2 + 96x3 → max

5x1 + 3x2 ≤ 900

2x1 + 3x2 + 7x3 + x4 \u003d 1250 F - 41x1 - 35x2 - 96x3 \u003d 0

X1 + X2 + X5 \u003d 250

5x1 + 3x2 + x6 \u003d 900

X1 + 3X2 ≤ 20 F \u003d 2x1 + x2 → max

2x1 + 2x2 ≤ 17

(-1/3)(-1/3)(2/3)

Răspuns: x1 \u003d 0; X2 \u003d 29/5; X3 \u003d 0; X4 \u003d 13/5; X5 \u003d 0; X6 \u003d 0; X7 \u003d 54/5.

Concluzie

Să trăim pe cele mai simple interpretări ale metodei simplex.

Semnificația algebrică a metodei simplex este aceea că, realizând transformări algebrice identice, ne mutăm de la o soluție admisibilă la sistemul de ecuații algebrice față de alta îmbunătățit, atingând soluția optimă la această problemă.

Din punct de vedere geometric, transformările identice din metoda simplex sunt mișcări consecutive de la un vârf al soluțiilor de poligon convex la adiacent, de la acesta la următoarea și astfel la vârful optim pe părțile laterale ale acestui poligon.

Esența economică a metodei simplex este că este o metodă de îmbunătățire consecventă a soluțiilor. Această metodă face posibilă prin selectarea planului de acțiune de susținere a acțiunii, trecerea treptată înainte și, în cele din urmă, la realizarea unui plan optim dacă, desigur, acest lucru există.

Simplex este un poligon convex într-un spațiu n-dimensional cu nodici n + 1 care nu se află pe o hiperplană. Simplexurile sunt evidențiate într-o clasă separată, deoarece simplexul este cel mai simplu poligon, care conține un volum de spațiu n-dimensional.

Se dovedește că, dacă există soluția optimă, aceasta va fi găsită cu siguranță printr-un număr finit de pași (cu excepția așa-numitei "probleme degenerate", în care este posibilă fenomenul "loopingului", adică revenirea multiplă la aceeași poziție).

Programarea liniară este domeniul de programare matematică dedicată teoriei și metodelor de rezolvare a sarcinilor extreme caracterizate printr-o dependență liniară între variabilele.

Programare matematică (programare optimă) - Regiunea Matematică, combinând diferite metode și discipline matematice: programare liniară, programare dinamică, programare convexă etc. Sarcina generală a programării matematice este de a găsi valoarea optimă (maximă sau minimă) a funcției țintă , iar valorile variabilelor trebuie să aparțină unei zone de valori admise.

Lista literaturii utilizate

1) A. S. Shapkin, N. P. Mazeev; Metode matematice și modele de cercetare operațiuni, 2005.

2) N.sh. Kremer, B și Putko, I.m. Trishin, M.N. Friedman.; Operațiuni de cercetare B. economie. - Unitate, 2002.

Descrierea prezentării pe diapozitive individuale:

1 glisați.