Programare liniara si intreaga - Linear and Integer Programming

Programare liniara si intreaga - Linear and Integer Programming

In cadrul unui proiect mai general de extindere si dezvoltare, conducerea unei firme studiaza oportunitatea construirii unei noi fabrici fie in orasul A, fie in orasul B, poate chiar in amandoua si a cel mult un depozit intr-unul din cele doua orase, alegerea amplasamentului fiind insa conditionata de construirea unei fabrici in localitatea respectiva. In tabelul 1.1. sunt indicate: valoarea prezenta neta a diferitelor alternative, capitalul necesar acestor investitii si capitalul disponibil pentru intregul proiect de dezvoltare.

milioane $

Tabelul 1.1.

Conditiile specificate in proiectul de dezvoltare se formalizeaza astfel:

cel mult un depozit poate fi construit: x₃ + x₄

(deoarece x₃, x₄ nu pot lua decat valorile 0 sau 1, se elimina posibilitatea construirii a doua depozite in ambele orase deoarece x₃ = 1, x₄ = 1 nu satisfac inegalitatea !)

depozitul nu poate fi construit in lipsa unitatii productive: x₃ x₁, x₄ x₂

(este clar ca x₁ = 0 implica cu necesitate x₃ = 0, etc.)

incadrarea in capitalul disponibil: 6 x₁ + 3 x₂ + 5 x₃ + 2 x₄

maximizarea valorii prezente nete totale a obiectivelor care se vor realiza:

9 x₁ + 5 x₂ + 6 x₃ + 4 x₄ max

Rezulta urmatorul model matematic:

Solutia specifica faptul ca firma se incadreaza in capitalul necesar de 10 u.m.,ea va obtine un profit maxim de 14 u.m. fiind ales urmatorul plan de construire a fabricilor:

-se va construi o fabrica in orasul A si una in orasul B.

-nu va fi construit niciun depozit.

2)Problema de transport -Network Modelling

Problema de transport se rezolva cu ajutorul metodei "Simplex" si principalul obiectiv al problemei este de determinare a drumului cu cost de transport minim sau maxim dintre un set de noduri "sursa" si un set de noduri "destinatie".

O firma produce lapte in 3 fabrici diferite pe care il distribuie prin 4 depozite regionale.Capacitatile de productie ale fabricilor si necesarul sunt date in tabelul urmator.

Sa se determine modul de livrare al produselor din fabrici catre depozite pentru a realiza minimizarea costului total de transport, cu respectarea constrangerilor legate de capacitatile de productie ale fabricilor si necesarul depozitelor.

Pentru a rezolva aceasta problema in Winqsb intram in modulul Network Modeling si mergem pe optiunea File iar apoi pe optiunea New din File si apoi ne o caseta de dialog in care trebuie sa specificam urmatoarele elemente:

-tipul problemei in cazul nostrum o problema de transport(Transportation Problem);

-tipul de criteriu pentru functia obiectiv respectiv de minimizare in acest caz pentru functia obiectiv , respectiv de minimizare in acest caz(Objective Criterion:Minimization);

-modul de introducere a datelor (matriceal sau grafic-Data Entry Format:Spread Shett Matrix Form sau Graphic Model Form) la noi in mod matriceal(Spread Shett Matrix Form);

-titlul problemei(Problem Title):Problema de transport;

-numarul de surse si numarul de destinatii, in cazul nostru 3 si respective 4.

In continuare vom introduce costurile de transport, a disponibilului si a necesarului in tabelul creat prin tastarea valorilor in celulele corespunzatoare.Denumirile nodurilor le schimbam utilizand optiunile meniului Edit.

Si apoi introducand valorile obtinem tabelul:

Si apoi vizualizam graful aferent problemei selectand optiunea Format:Switch to Graphic Model.

Iar apoi rezolvam problema alegand din meniul Solve and Analyze: optiunea Solve the Problem.

In urma rezolvarii problemei s-au obtinut urmatoarele rezultate:

Costul total de transport este de minim 2230 Euro daca:

-Fabrica 1 aprovizioneaza depozitul 2 cu 100 de litri de lapte respectiv depozitul 4 cu 20 de litri de lapte;

-fabrica 2 aprovizioneaza depozitul 1 cu 150 de litri lapte si respectiv depozitul 2 cu 100 litri de lapte;

-fabrica 3 aprovizioneaza depozitul 3 cu 240 litri de lapte respectiv depozitul 4 cu 160 de litri lapte;

Se poate face si o analiza de tip "What-If"prin apelarea optiuniiPerform What if Analysis din meniul Results, de exemplu daca costul de transport intre fabrica 2 si depozitul 1 creste de la 1 euro la 5 euro atunci:

Dupa ce a crescut vom rezolva problema si rezultatele obtinute vor fi urmatoarele:

Se poate observa ca prin aplicarea analizei "What-If " ca urmare a cresterii costului de transport dintre fabrica 2 si depozitul 1 costul total de transport va fi 2830 si va creste cu 600 Euro modificandu-se in timp si cantitatile de transportat astfel:

-fabrica 1 aprovizioneaza depozitul 2 cu 100 de litri lapte si depozitul 4 cu 20 de litri lapte;

-fabrica 2 aprovizioneaza depozitul 1 cu 150 de litri lapte si depozitul 2 cu 100 de litri lapte;

-fabrica 3 aprovizioneaza depozitul3 cu 240 de litri lapte

si depozitul 4 cu 160 de litri lapte ;

3) Problema drumului minim

Problema presupune existenta unui singur nod sursa si a unui singur nod destinatie si calcularea drumului minim intre acestea. Rezolvarea se bazeaza pe alg "Labeling".

Transportul unor produse trebuie sa se efectueze intre localitatile Iasi si Oradea folosind cai de comunicatie ce trec prin alte 7 localitati intermediare. Sa se determine drumul minim intre cele doua localitati daca se cunosc distantele intre acestea.

Distantele dintre localitati sunt date in tabelul:

Se apeleaza din Solve and Analyze -> Solve the Problem si are ca efect umatoarea fereastra:

Cel mai scurt drum intre localitatile Iasi si Oradea trecand prin cele 7 orase este 1638 km, traseul fiind urmatorul: Iasi - Deva - Resita - Oradea.