AI + Programare liniara

Teorie, explicatii si HELP pentru cele 7 experimente. Material introductiv pentru anul I, semestrul I.

Deschide simulatorul

1. Teoria de care ai nevoie

Variabile de decizie

Sunt cantitatile pe care le putem alege. Notam cu x si y cele doua activitati. Exemplu: ore de lucru pentru doi roboti.

Functia obiectiv

Exprima ce vrem sa maximizam sau minimizam. De exemplu, Z = 5x + 4y reprezinta un beneficiu total estimat.

Restrictii

Exprima limitele disponibile. 2x + y ≤ 60 inseamna ca cele doua activitati nu pot consuma impreuna mai mult de 60 de unitati dintr-o resursa.

Domeniul admisibil

Este multimea tuturor perechilor (x, y) care respecta simultan toate restrictiile, inclusiv x ≥ 0 si y ≥ 0.

Forma generala a problemelor din simulator

Max Z = c1x + c2y
a11x + a12y ≤ b1
a21x + a22y ≤ b2
x ≥ 0, y ≥ 0

Interpretare: c sunt beneficiile pe unitate, a sunt consumurile de resurse pe unitate, iar b sunt resursele disponibile. Toate cele 7 probleme sunt de maxim cu doua variabile.

De ce cautam optimul in varfuri?

Pentru o problema liniara cu domeniu admisibil nevid si marginit, exista cel putin un varf al domeniului in care se atinge optimul. Pot exista si mai multe solutii optime, de exemplu de-a lungul unei laturi.

  1. Deseneaza dreptele obtinute prin inlocuirea semnului ≤ cu =.
  2. Identifica semiplanele care satisfac fiecare restrictie.
  3. Gaseste intersectia lor in primul cadran.
  4. Calculeaza Z in varfurile domeniului.
  5. Alege varful cu valoarea Z cea mai mare.
Atentie: In simulator, x si y pot lua valori fractionare. Daca x si y ar reprezenta obiecte indivizibile, ar fi nevoie de un model cu variabile intregi.

2. Cum folosesti simulatorul - HELP

  1. Alege unul dintre cele 7 experimente din butoanele de sus.
  2. Citeste povestea si identifica semnificatia variabilelor x si y.
  3. Urmareste coeficientii functiei obiectiv si cele doua resurse disponibile.
  4. Apasa pe un punct al graficului: simulatorul iti spune daca solutia este admisibila.
  5. Incearca sa anticipezi optimul. Apoi apasa Gaseste optimul.
  6. Modifica un singur parametru si observa cum se schimba domeniul si solutia.
  7. Foloseste Reseteaza pentru datele initiale si Experiment surpriza pentru alte valori.

Cum citesti graficul?

Zona albastra: solutii admisibile.
Punctul albastru: alegerea ta.
Punctul verde: solutia optima, dupa calcul.
Liniile portocalie si mov: limitele celor doua resurse.

Ce poti modifica?

Scor x / scor y: schimba functia obiectiv, nu domeniul admisibil.
Resursa 1 / resursa 2: schimba domeniul admisibil, nu beneficiul pe unitate.

De ce un punct poate fi respins?

Fiindca nu respecta cel putin una dintre restrictii. Verifica numeric ambele expresii din stanga si compara-le cu limitele din dreapta.

Ce inseamna restrictie activa?

O restrictie este activa intr-un punct daca este satisfacuta cu egalitate. De exemplu, daca 2x + y = 60, resursa respectiva este folosita integral.

Este intotdeauna mai bine sa crestem o resursa?

La o problema de maxim, marirea unei limite de tip ≤ nu poate reduce valoarea optima, dar poate sa nu o creasca deloc. Cealalta resursa poate ramane blocajul principal.

De ce spunem ca sunt aplicatii AI?

Un sistem AI poate estima scoruri, riscuri sau durate, iar programarea liniara poate alege cum sa aloce resursele. Aceste exemple descriu etapa de decizie/optimizare, nu invatarea completa a unui model AI.

3. Explicatiile celor 7 experimente

Alege un experiment pentru a vedea modelul, interpretarea si un exercitiu ghidat.

4. Experimente spectaculoase pentru seminar

Surpriza 1

Cel mai bun scor nu inseamna alegere exclusiva

In experimentul cu robotii, A are scor 5, iar B are scor 4. Totusi, combinatia celor doi poate produce un rezultat mai bun decat folosirea exclusiva a robotului A.

Surpriza 2

Mai multe resurse, acelasi optim

Creste numai o resursa pana cand cealalta devine singura limita importanta. Vei observa ca resursa suplimentara nu mai ajuta.

Surpriza 3

Optimumul se poate muta brusc

Schimba treptat unul dintre scoruri. Domeniul ramane neschimbat, dar varful optim poate sari la un alt varf.

Surpriza 4

Mai multe solutii la fel de bune

La roboti, pune scorurile x = 2 si y = 1. Functia obiectiv devine paralela cu prima restrictie. Pe o latura admisibila pot exista infinit de multe solutii optime.

5. Test rapid de verificare

1. Daca modific scorurile c1 si c2, se modifica domeniul admisibil?

Nu. Se modifica doar functia obiectiv.

2. Daca maresc b1, valoarea optima poate sa scada?

Nu, in aceste probleme de maxim, deoarece toate solutiile anterior admisibile raman admisibile.

3. Poate un punct din interiorul domeniului sa fie optim unic?

Nu, daca functia obiectiv este liniara neconstanta si domeniul are interior. Optimul unic se gaseste pe frontiera, intr-un varf.

4. Este obligatoriu sa fie utilizate complet ambele resurse?

Nu. Unele restrictii pot fi inactive la optim.

5. Programarea liniara este acelasi lucru cu inteligenta artificiala?

Nu. Este o metoda matematica de optimizare, care poate fi folosita ca parte a unui sistem AI.

Mergi la cele 7 experimente interactive