Operációkutatás I.

Bajalinov, Erik

Nyíregyházi Főiskola, Matematika és Informatika Intézete

Bekéné Rácz, Anett

Debreceni Egyetem, Informatikai Kar

Új Széchenyi Terv logó.

Lektorálta: Dr. Mala József, egyetemi docens, Corvinus Egyetem

A tananyag a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-magyarországi Informatika Tananyag Tárház projekt keretében készült. A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával valósult meg.

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

2010


Tartalom

1. Bevezetés
1.1. Optimumszámítási feladatok. A matematikai programozás feladata
1.2. A lineáris programozási feladat és alakjai
1.2.1. Általános lineáris programozási feladat
1.2.2. Standard lineáris programozási feladat
1.2.3. Kanonikus lineáris programozási feladat
1.2.4. Átalakítás
1.3. A lineáris programozási feladat geometriája
1.4. Gyakorlat
1.4.1. Gyakorló feladatok
1.4.2. Ellenőrző kérdések
2. Szimplex módszer
2.1. A szimplex módszer elméleti háttere
2.1.1. Fő definíciók
2.1.2. Optimalitási kritérium
2.2. Szimplex tábla és műveletek
2.3. Gyakorlat
2.3.1. Minta
2.3.2. Gyakorló feladatok
2.3.3. Ellenőrző kérdések
3. Induló lehetséges bázismegoldás előállítása
3.1. Nagy M módszer
3.2. Kétfázisú szimplex módszer
3.3. Gyakorlat
3.3.1. Minta
3.3.2. Gyakorló feladatok
3.3.3. Ellenőrző kérdések
4. Szimplex módszer - folytatás
4.1. Általános séma
4.2. Degeneráció
4.3. Kiválasztó szabályok
4.3.1. Bevezető szabályok
4.3.2. Kivezető szabályok
4.4. Gyakorlat
4.4.1. Minta
4.4.2. Gyakorló feladatok
4.4.3. Ellenőrző kérdések
5. Dualitás
5.1. A duális feladat fogalma
5.2. Dualitási tételek
5.3. Árnyékárak
5.4. Gyakorlat
5.4.1. Minta
5.4.2. Gyakorló feladatok
5.4.3. Ellenőrző kérdések
6. Érzékenységi analízis
6.1. A jobboldal változása
6.2. Változások a célfüggvényben
6.3. Gyakorlat
6.3.1. Minta
6.3.2. Gyakorló feladatok
6.3.3. Ellenőrző kérdések
7. Szállítási feladat
7.1. A feladat fő alakjai
7.2. Hurokszerkesztéses szimplex módszer
7.3. Induló lehetséges megoldás előállítása
7.3.1. Északnyugati sarok módszer
7.3.2. Minimális költség módszer
7.3.3. Vogel módszer
7.4. Gyakorlat
7.4.1. Minta
7.4.2. Gyakorló feladatok
7.4.3. Ellenőrző kérdések
8. Szállítási feladat speciális esetei
8.1. Összetett szállítási feladat
8.2. Hozzárendelési feladat és magyar módszer
8.2.1. Modell (Munkák optimális kiosztása)
8.2.2. Magyar módszer
8.3. Gyakorlat
8.3.1. Minta
8.3.2. Gyakorló feladatok
8.3.3. Ellenőrző kérdések
9. Egészértékű programozás
9.1. Diszkrét, egészértékű, 0/1 LP feladatok, átalakítás
9.2. Korlátozás és szétválasztás módszere
9.3. Gomory módszer
9.4. Gyakorlat
9.4.1. Minta
9.4.2. Gyakorló feladatok
9.4.3. Ellenőrző kérdések
10. Bevezetés a hiperbolikus programozásba
10.1. A feladat alakjai és a grafikus módszer
10.1.1. Hiperbolikus gyártási feladat
10.1.2. HP feladatok alakjai
10.1.3. Grafikus módszer
10.2. Charnes és Cooper transzformáció
10.3. Dinkelbach módszer
10.4. Gyakorlat
10.4.1. Minta
10.4.2. Gyakorló feladatok
10.4.3. Ellenőrző kérdések
11. Szimplex módszer a hiperbolikus programozásban
11.1. A szimplex módszer "hiperbolikus" változata
11.2. Induló lehetséges bázismegoldás előállítása
11.2.1. Nagy M módszer
11.2.2. Kétfázisú szimplex módszer
11.3. Gyakorlat
11.3.1. Minta
11.3.2. Gyakorló feladatok
11.3.3. Ellenőrző kérdések
12. Dualitás a hiperbolikus programozásban
12.1. Duális feladat
12.2. Dualitási tételek
12.3. Duális változók értelmezése
12.4. Gyakorlat
12.4.1. Minta
12.4.2. Gyakorló feladatok
12.4.3. Ellenőrző kérdések
13. Érzékenységi analízis hiperbolikus programozásban
13.1. A jobboldal változása
13.2. Változások a célfüggvény számlálójában
13.3. Változások a célfüggvény nevezőjében
13.4. Gyakorlat
13.4.1. Minta
13.4.2. Gyakorló feladatok
13.4.3. Ellenőrző kérdések
14. Szoftverek
14.1. Solver
14.2. LinGo
14.3. Gyakorlat
14.3.1. Minta
14.3.2. Gyakorló feladatok
14.3.3. Ellenőrző kérdések
Irodalomjegyzék

A táblázatok listája

2.1. Szimplex táblázat
3.1. Induló szimplex tábla a (3.1)-(3.3) feladathoz.
3.2. Nagy M módszer - Induló szimplex tábla
7.1. Szállítási szimplex táblázat
7.2. Szállítási feladat - Vannak hurkok
7.3. Szállítási feladat - Nincsenek hurkok
7.4. Északnyugati sarok módszer - Eredeti és 1. tábla
7.5. Északnyugati sarok módszer - 2. és 3. tábla
7.6. Északnyugati sarok módszer - 4. és 5. tábla
7.7. Északnyugati sarok módszer - 6. és 7. tábla
7.8. Vogel módszer - 1. tábla
7.9. Vogel módszer - 2. tábla
7.10. Vogel módszer - Végső tábla
8.1. Összetett szállítási tábla
11.1. HP szimplex tábla
11.2. Nagy M módszer - Induló táblázat
11.3. Nagy M módszer - Az első iteráció eredménye
11.4. Nagy M módszer - Az második iteráció eredménye
11.5. Nagy M módszer - Optimális táblázat

Az egyenletek listája

1.1.
1.2.
1.3.
1.4.
1.5.
1.6.
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
2.8.
2.9.
2.10.
2.11.
2.12.
2.13.
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
3.9.
3.10.
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
5.7.
5.8.
5.9.
5.10.
5.11.
5.12.
5.13.
5.14.
5.15.
5.16.
5.17.
5.18.
5.19.
5.20.
5.21.
5.22.
5.23.
5.24.
5.25.
5.26.
5.27.
5.28.
5.29.
5.30.
6.1.
6.2.
6.3.
6.4.
6.5.
6.6.
6.7.
6.8.
6.9.
6.10.
6.11.
6.12.
6.13.
6.14.
7.1.
7.2.
7.3.
7.4.
7.5.
7.6.
7.7.
7.8.
7.9.
7.10.
7.11.
7.12.
7.13.
7.14.
7.15.
8.1.
8.2.
8.3.
8.4.
8.5.
8.6.
8.7.
8.8.
8.9.
8.10.
9.1.
9.2.
9.3.
9.4.
9.5.
10.1.
10.2.
10.3.
10.4.
10.5.
10.6.
10.7.
10.8.
10.9.
10.10.
10.11.
10.12.
11.1.
11.2.
11.3.
11.4.
11.5.
11.6.
11.7.
11.8.
11.9.
11.10.
11.11.
11.12.
11.13.
11.14.
12.1.
12.2.
12.3.
12.4.
12.5.
12.6.
12.7.
12.8.
12.9.
12.10.
12.11.
12.12.
12.13.
12.14.
12.15.
12.16.
12.17.
12.18.
12.19.
12.20.
12.21.
12.22.
12.23.
12.24.
12.25.
13.1.
13.2.
13.3.
13.4.
13.5.
13.6.
13.7.
13.8.
13.9.
13.10.
13.11.
13.12.
13.13.
13.14.
13.15.
13.16.
13.17.
13.18.
13.19.
13.20.
13.21.
13.22.
13.23.
14.1.
14.2.