Metoda Gomory on-line

Metoda Gomory este folosită pentru a găsi soluții întregi la probleme de programare liniară.
Fie găsit soluția problemei PL :. soluție Li va fi un număr întreg, de exemplu, dacă . i> - partea fracționară noninteger soluție xi optimă. i> - partea fracționară nu este variabile de bază. Acest raport determină tăiere corespunzătoare Gomori (vezi. Figura).

Instrucțiuni. Selectați numărul de variabile și numărul de rânduri (numărul de constrângeri), apoi faceți clic pe Următorul. Soluția obținută este stocată în fișierul Word (vezi. De exemplu soluții metoda Gomori). În plus, pentru a crea un șablon de soluție în format Excel. În acest tip de constrângeri xi ≥ 0 nu se referă la ea.

Tipuri de Gomory algoritm

1. Primul algoritm de soluții Gomory probleme complet întregi.
2. Al doilea algoritm Gomory pentru probleme de programare liniară întregi mixte.

Gomori algoritm pentru toate sarcinile întregi include următoarele etape:

1. Noi rezolva problema de programare liniară, cu excepția întreg.
2. Numerele fracționare suplimentari selectați elementul cu cea mai mare parte fracționată și o constrângere suplimentară este constituită.
3. Inegalitatea este transformată într-o ecuație prin introducerea unei nenegativ variabile suplimentare.
4. Problema rezultată este rezolvată prin metoda duală simplex.

Dacă în procesul de tabel simplex decizia va fi o ecuație care nu face corp comun cu un membru gratuit și coeficienți întregi bi AIJ. atunci această problemă nu are o soluție întreg optimă.

Interpretarea geometrică Gomory cut

Exemplu. asociație științifică-producție „Strela“ este angajată în fabricarea de componente pentru întreprinderile militare. La fabricarea produselor de tip A și de tip B sunt utilizate din oțel și metale neferoase. Procesul tehnologic implică, de asemenea, tratarea produselor pe strunguri și mașini de frezat. Pentru standarde tehnologice privind producția de un singur tip de produs A și un tip de produs într-o anumită cantitate de materie primă și necesită o anumită cantitate de mașini-oră pentru prelucrare în atelier. Procesul procesului de producție a datelor sunt prezentate în tabel.
În cadrul atelierului de lucru luni ONG „Boom“ are resurse pentru materii prime și de muncă de timp în instalațiile de producție limitate (a se vedea. Tabelul). Profit din vânzarea de un singur tip de produs este de 100 de ruble. și de la un singur tip de produs B - 250 ruble.

atelier, mașină de ore

Profitul din vanzarea, freca.