pentru programare liniară. Aceasta este cea mai veche formalizare a acestui timp

Doză/zi în funcție de limită 0 x 1 4 0 x 2 3 0 x 3 2 0 x 4 8 0 x 5 2 0 x 6 2 În funcție de necesitățile zilnice 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 Aici luăm în considerare faptul că nu putem consuma o cantitate negativă sau prea mult dintr-un aliment și am rezumat valoarea nutrițională din acestea. În cele din urmă, costul dietei poate fi exprimat prin variabilele introduse și constantele date: 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 După aceasta, descrierea matematică a problemei dietei este următoarea: min 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 x 1 4 x 2 3 x 3 2 x 4 8 x 5 2 x 6 2 x 1, x 2, x 3, x 4, x 5, x 6 0 De obicei prin programare liniară ne referim la următoarele probleme:

Desigur, variabilele x 4, x 5, x 6 pot lua doar o valoare non-negativă, altfel inegalitățile inițiale nu ar fi satisfăcute. Deci, încercați să măriți x 1 astfel încât valoarea variabilelor x 4, x 5, x 6 să rămână non-negativă; deci, desigur, există limite la x 1; (1) x 1 5 2 (2) x 1 11 4 (3) x 1 8 3 Deoarece (1) oferă cea mai puternică constrângere, o nouă soluție este: x 1 = 5/2, x 2 = 0, x 3 = 0, x 4 = 0, x 5 = 1, x 6 = 1/2, z = 25/2. Din (1) obținem x 1 exprimat ca: x 1 = 5 2 3 2 x 2 1 2 x 3 1 2 x 4 (1) Înlocuiți acest lucru în (2) și (3): x 5 = 11 4 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) x 2 2x 3 (2) x 6 = 8 3 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) 4x 2 2x 3 (3) z = 5 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) + 4x 2 + 3x 3 x 1 = 5 2 3 2 x 2 1 2 x 3 1 2 x 4 (1) x 5 = 1 + 5x 2 + 2x 4 (2) x 6 = 1 2 + 1 2 x 2 1 2 x 3 + 3 2 x 4 (3) z = 25 2 7 2 x 2 + 1 2 x 3 5 2 x 4 Apelați variabilele pe stânga, x 1, x 5 și x 6, bază. Variabilele din afara bazei iau 0. Valoarea funcției obiective este constanta prezentată aici, deci z = 25/2. Acum nu ar merita să creșteți x 2 și x 4 deoarece acest lucru ar reduce funcția obiectivă z. Selectăm x 3 și vedem cât timp poate fi mărit. 6

Dovadă. Este evident din cele spuse până acum. Definiție. Două dicționare sunt echivalente dacă toate soluțiile (reale arbitrare) ale sistemului de ecuații pe care le descriu și valorile corespunzătoare ale funcției lor obiective sunt aceleași. Propunerea 2 Transformarea unui dicționar folosit în exemplu duce la un dicționar echivalent cu cel anterior. Dovadă. Este evident, deoarece manipulările algebrice aplicate (rearanjarea unei ecuații, înmulțirea acesteia cu un număr diferit de zero sau substituirea variabilelor) nu schimbă soluțiile sistemului de ecuații. Notă: Există o relație strânsă între soluțiile posibile ale unei probleme standard de LP și soluțiile non-negative ale dicționarelor formate din aceasta, deoarece natura non-negativă a variabilelor artificiale înseamnă îndeplinirea inegalităților LP-ului original. Dacă x 1. x n este o posibilă soluție a LP, atunci x 1. x n este completat de diferența dintre laturile stânga și dreapta ca x n + 1. Cu valorile variabilelor x n + m, dicționarul oferă o soluție non-negativă. În schimb, omiterea variabilelor artificiale dintr-o soluție non-negativă din dicționar oferă o posibilă soluție LP-ului original. 9

Lectura 2 În exemplul nostru am văzut că algoritmul simplex poate fi împărțit practic în următoarele etape principale: 1. Inițializare (pornire) 2. Iterare (aproximare) 3. Încheiere (finalizare) Până acum am ignorat în mod intenționat dificultățile și posibilitățile de ramificare a algoritmului. Problema inițializării va fi discutată în următoarea clasă, dar problemele iterației și terminării vor fi clarificate acum. 1. Inițializare max cjxja ij xjb (i = 1, 2. m) xj 0 (j = 1, 2. n) x n + i = bina ij xj (i = 1, 2. m) z = cjxj Dacă toate bi 0, atunci (0, 0. 0) este o posibilă soluție. În caz contrar, nu putem începe iterația. Deci, pentru a începe procesul nostru, vom avea nevoie de un dicționar care să definească o posibilă soluție. 2. Iterație z = z + c j x j, j N unde z este valoarea instantanee a funcției obiective; N este setul de variabile care nu sunt de bază, B este setul de variabile de bază. 10

Să presupunem că situația actuală este următoarea: x 2 = 5 + 2x 3 x 4 3x 1 x 5 = 7 3x 4 4x 1 z = 5 + 3x 3 x 4 x 1 Este recomandabil să măriți valoarea x 3 astfel încât x 2 și x 5 nu trebuie să fie negative. Cu toate acestea, niciuna dintre cele două ecuații de mai sus nu dă o constrângere (limita superioară) la x 3, funcția obiectivă a problemei poate lua o valoare arbitrar mare. Pe măsură ce continuăm, se pot întâmpla următoarele: a) În dicționar, toți coeficienții aparținând variabilei pivot sunt 0, adică nu există nicio constrângere. Atunci soluția nu este limitată. b) Coeficienții variabilelor funcției obiective nu sunt pozitivi. Atunci suntem la optim. c) Mai multe variabile pot intra în bază în același timp; în consecință, trebuie să alegem una dintre ele. d) Valoarea variabilelor de intrare nu poate fi mărită și funcția obiectivă nu crește. Apoi spunem că a avut loc degenerarea. Definiție. zero. Exemplu: Un dicționar este degenerat dacă conține valoarea unei variabile de bază xi x 4 = 1 2x 3 x 5 = 3 2x 1 + 4x 2 6x 3 x 6 = 2 + x 1 3x 2 4x 3 z = 2x 1 x 2 + 8x 3 A variabila care iese din bază nu este clar definită, deoarece toate cele trei ecuații dau o constrângere 1/2 asupra valorii variabilei x 3. Degenerare 11

prin care putem cădea într-o capcană deosebit de neplăcută, așa-numitul poate apărea ciclizarea. Exemplu: x 5 = 1 2 x 1 + 11 2 x 2 + 5 2 x 3 9x 4 x 6 = 1 2 x 1 + 3 2 x 2 + 1 2 x 3 x 4 x 7 = 1 x 1 z = 10x 1 57x 2 8x 3 24x 4 Ecuațiile 1 și 2 (exprimând x 5 și x 6) dau cea mai puternică limită superioară (x 1 = 0), deci să spunem că x 5 este înlocuit cu x 1 variabilă. x 1 = 11x 2 + 5x 3 18x 4 2x 5 x 6 = 4x 2 2x 3 + 8x 4 + x 5 x 7 = 1 11x 2 5x 3 + 18x 4 + 2x 5 z = 53x 2 + 41x 3 204x 4 20x 5 Ecuația 2 (exprimând x 6) dă cea mai puternică limită superioară (în 1: niciunul, în 2: x 2 = 0, în 3: x 2 1/11), deci x 6 este înlocuit cu baza este variabila x 2. x 2 = 1 2 x 3 + 2x 4 + 1 4 x 5 1 4 x 6 x 1 = 1 2 x 3 + 4x 4 + 3 4 x 5 11 4 x 6 x 7 = 1 + 1 2 x 3 4x 4 3 4 x 5 11 4 x 6 z = 29 2 x 3 98x 4 27 4 x 5 53 4 x 6 12

Ecuațiile 1 și 2 (exprimând x 2 și x 1) dau cea mai puternică limită superioară (în 1, 2: x 3 = 0, în 3: niciuna), deci să spunem x Înlocuiți 1 în bază cu variabila x 3. x 3 = 2x 1 + 8x 4 + 3 2 x 5 11 2 x 6 x 2 = x 1 2x 4 1 2 x 5 + 5 2 x 6 x 7 = 1 x 1 z = 29x 1 + 18x 4 + 15x 5 93x 6 Ecuația 2 (exprimând x 2) dă cea mai puternică limită superioară (în 2: x 4 = 0, în 1, în 3: niciuna), deci variabila x 4 este înlocuită de variabila x 4. x 4 = 1 2 x 1 1 2 x 2 1 4 x 5 + 5 4 x 6 x 3 = 2x 1 4x 2 1 2 x 5 + 9 2 x 6 x 7 = 1 x 1 z = 20x19x2 + 21 2 x 5 141 2 x 6 Ecuațiile 1 și 2 (exprimând x 4 și x 3) dau cea mai puternică constrângere (în 1 și 2: x 5 = 0, în 3: niciuna), deci să spunem că x 3 este înlocuit cu x 5 în bază . 13

x 5 = 4x 1 8x 2 2x 3 + 9x 6 x 4 = 1 2 x 1 3 2 x 2 + 1 2 x 3 x 6 x 7 = 1 x 1 z = 22x 1 93x 2 21x 3 + 24x 6 A 2. ecuația (exprimând x 4) dă cea mai puternică limită superioară (în 2: x 4 = 0, în 1, în 3: niciuna), deci x 4 este înlocuit cu x 6 în bază. x 6 = 1 2 x 1 + 3 2 x 2 + 1 2 x 3 x 4 x 5 = 1 2 x 1 + 11 2 x 2 + 5 2 x 3 9x 4 x 7 = 1 x 1 z = 10x 1 57x 2 8x 3 24x 4 Aceasta ne aduce înapoi la dicționarul de la care a început exemplul nostru. S-a produs ciclizarea. Teorema 1 Dacă metoda simplex nu se oprește, ciclizează. Dovadă. Este ușor de văzut că există 3 baze posibile de ales în (n + m) m moduri. Adică, dacă procedura continuă la nesfârșit, mai devreme sau mai târziu va reapărea o bază care a fost prezentă anterior. Vom vedea că o bază definește clar dicționarul corespunzător, deci repetarea bazelor este și repetarea dicționarelor. Să presupunem că în două dicționare bazele sunt aceleași: Dicționar 1: (2.1) 3 Amintiți-vă că () n k = n!, Scăpați n sub k, dați numărul k! (N k)! câte modalități putem selecta k elemente dintr-un set de n elemente. 14

xi = bia ij xj (i B) j B z = v + j B cjxj Dicționar 2: (2.2) xi = bij B a ij xj (i B) z = v + j B cjxj Conform propunerii 1, cele două dicționare este echivalent, deci conform definiției 4, dicționarul (2.1) este orice x 1, x 2. xn, xn + 1. Soluția lui x n + m, z este, de asemenea, soluția dicționarului (2.2) și invers. Mai exact, pentru orice variabilă non-bază xk și fii t un număr real: xk = t, Atunci xj = 0 (j B, jk) xi = bia ik t (i B), z = v + ckt Aceasta oferă o soluție din (2.1), care trebuie să satisfacă și (2.2) pe baza celor de mai sus, deci bia ik t = bia ikt i B și v + ckt = v + c kt 15

Deoarece t a fost un număr real arbitrar, acest lucru este posibil numai dacă a ik = a ik i B b i = b i v = v c k = c k k N Deci cele două dicționare sunt cu adevărat aceleași, iar teorema rezultă din aceasta. Metode de evitare a ciclizării: 1. perturbare sau metodă lexicografică (vezi practica) 2. Metoda Bland sau metoda cel mai puțin indexată Notă: Existența ciclizării este într-adevăr doar confuză în teorie, aproape niciodată nu apare în practică. Degenerarea este un fenomen mult mai frecvent și, în unele cazuri, poate crește inconfortabil durata de funcționare a algoritmului. Asa numitul metoda de perturbare oferă, de asemenea, o anumită protecție împotriva acestui lucru. 16

și z = v + c s y. Deoarece funcțiile obiective trebuie să se potrivească, v + csy = v + c sy + i B ci (bia este y) Ne rearanjăm că (cscs + cia este) y = cibii B i B Deoarece y a fost arbitrar, acest lucru este posibil numai (de asemenea, cscs + i B cia) = 0 și deci, desigur, i B cibi = 0. Deoarece variabila care introduce xxt în baza dicționarului xsa D este cs> 0. Pe de altă parte, variabila care intră în bază în xsa dicționar D și s 0. Deoarece xta este un element de bază în dicționarul D, ct> 0, și astfel cta ts> 0, adică xt și xr sunt variabile diferite și r este 0. D și D dau același lucru soluţie. În mod specific, valoarea lui xr nu se modifică în timpul iterațiilor și, deoarece baza din D nu este xr = 0 și, astfel, desigur, a luat și valoarea zero în D, br = 0. Atunci baza lui D a trebuit să fi xr, nu xt. ar fi plecat și asta contrazice presupunerea noastră. Astfel, odată cu aplicarea regulii Bland, nu există ciclizare și astfel, datorită teoremei 1, metoda simplex este terminată. 18

Cursul 3 Metoda simplex în două faze Scopul nostru este totuși să rezolvăm problema LP adusă la forma standard. Problemă LP Dicționare max n c i x i x n + i = b i n a ij x j Ax b z = n c j x j x 0 Anterior, am făcut față cu succes posibilelor capcane ale iterației și terminării. Cu toate acestea, este de conceput că nu putem începe nici iterația, deoarece dicționarul nostru inițial nu codifică o soluție posibilă, adică pentru unii i b i 0, y i = 0 ori de câte ori a ij x j 0). Indicați setul de indici de variabile libere de F. Rețineți că LP este în formă standard dacă și numai dacă E = și F =. Combinația liniară a condițiilor na ij xjbi (i I) și na ij xj = bi (i E) este următoarea inegalitate: (m) ma ij yixjbiyi dacă y 1, y 2. ym sunt reale și yi 0 dacă i I .Combinația liniară este, desigur, suma inegalităților amyi (na ij xj) mbiyi și o (ma ij yi) xj = m (na) ij xj) yi identitate. Mai mult, dacă numerele y 1, y 2. y n sunt astfel încât m a ij y i c j ha j R și a m a ij y i = c j ha j F 40