UCBL, MIM Mastery, Operational Research Linear Programming

1.1 Ce este programarea liniară

1.1.1 Exemplu: problema dietei lui Polly [1, p.3]

• Cerințe zilnice: Energie 2000 kcal Proteine ​​55g Calciu 800 mg
• Mâncare disponibilă

  Porţiune	Energie (kcal)	Proteine ​​(g)	Calciu (mg)	Preț/porție
  Cereale	28g	110	4	2	3
  Pui	100g	205	32	12	24
  Ouă	2 mari	160	13	54	13
  Tot laptele	237cc	160	8	285	9
  Plăcintă	170g	420	4	22	20
  Carne de porc și fasole	260g	260	14	80	19

Ce alegeri pentru Polly ?

• Constrângeri: cereale cel mult 4 porții pe zi Pui cel mult 3 porții pe zi Ouă cel mult 2 porții pe zi Lapte cel mult 8 porții pe zi Plăcintă cel mult 2 porții pe zi Carne de porc și fasole cel mult 2 porții pe zi

Cum să formalizăm problema? (modelare)

Ce face problema atât de specifică ?

Știi cum să rezolvi probleme similare ?

1.1.2 Forma standard a unei probleme de programare liniară

Sub constrângeri: 2 * x1 + 3 * x2 + x3

4 * x1 + x2 + 2 * x3

3 * x1 + 4 * x2 + 2 * x3

Minimizează: 3 * x1 - x2

Sub constrângeri: - x1 + 6 * x2 - x3 + x4> = -3

7 * x2 + 2 * x4 = 5

Sub constrângeri:

O alegere de variabile (x 1, ..., x n) se numește soluție a problemei.

O soluție este fezabilă dacă verifică constrângerile.

z se numește funcție obiectivă. Cu fiecare soluție asociază o valoare.

O soluție este optimă dacă este fezabilă și maximizează funcția obiectivă.

---