CCF03252008010

zostałych wierszy. Nowe rozwiązanie bazowe X²: x, = 3, x₃ = 6, x₀ = 9, x, =x₄ = 0 nie jest optymalne, gdyż t₀₂ = 2 > 0. Zmienna x₂ musi być wprowadzona do bazy, z której usuwamy zmienną x₃. Nową postać bazową, odpowiadającą nowej bazie, przedstawiono w tablicy 2.7.

Tablica 2.7

^ci		3	4	0	0
Cl	zmienna bazowa	*i	x2	*3
A		0	i	1/3	-1/3	2
3	*1	1	0	0	1/2	3
^z>		3	a	2/3	5/6	*oi
^l0 i		0	0	-2/3	-5/6	U

Rozwiązanie bazowe X³: x_l = 3, x₂ = 2, x₃ = x₄ = 0, x₀ = 13 jest rozwiązaniem optymalnym zadania (2.55), a tym samym i zadania (2.54). Z końcowej tablicy simpleksowej łatwo także odczytać rozwiązanie optymalne zadania dualnego: y, = z₃ = 2/3, y₂ = r₄ = 5/6.

Z interpretacji zmiennych dualnych wynika, że zwiększenie wyrazu wolnego o jednostkę spowoduje wzrost funkcji celu o y_Ł = 2/3.

BIBLIOGRAFIA

Czerwiński Z., [1984], Matematyka na usługach ekonomii, PWN, Warszawa.

Czerwiński Z. (red.) [1985], ZWdr zadań z ekonometrii, skrypty Akademii Ekonomicznej w Poznańiu, z. 348.    _ ,

Gale D. [1969], Teoria liniowych modeli ekonomicznych, PWN, Warszawa.

Nykowski J. [1986], Programowanie liniowe, PWE, Warszawa.

Rozdział

3

Zagadnienia

transportowe

3.1

Wprowadzenie

Jednym z najbardziej interesujących szczególnych przypadków liniowych zadań decyzyjnych jest zadanie transportowe. Zadaniu temu poświęcamy odrębny rozdział, co uzasadnić można tradycją¹, ale chyba przede wszystkim jego specyfiką, szerokim zastosowaniem i prawie kompletną teorią dotyczącą własności zadań i metod ich rozwiązywania. Zadanie transportowe (ZT) spośród wszystkich liniowych zadań decyzyjnych (LZD) wyróżnia przede wszystkim postać macierzy współczynników układu warunków ograniczających. To dzięki tej postaci udało się udowodnić wiele twierdzeń, które z kolei stanowią podstawę metod rozwiązywania ZT.

Trzeba również wspomnieć o tym, że na teorię dotyczącą zadań transportowych składają się nie tylko elementy teorii programowania liniowego, ale i również teorii grafów, w szczególności zagadnień związanych z sieciami transportowymi². To właśnie ZT — sformułowane i rozwiązane w 1934 r. przez L. Kantorowicza — było jednym z pierwszych rozwiązanycbjroblemów programowania liniowego. Poddane dalszej „obróbce” nosi czasem nazwę problemu Hitchcoca, od nazwiska badacza angielskiego, który w 1941 r. opublikował wersję zadania i algorytmu, znanego dziś pod nazwą klasycznego zadania transportowego.

1

W wielu podręcznikach programowania liniowego znajdzie Czytelnik oddzielne rozdziały lub części poświęcone tylko zadaniu transportowemu i zadaniom pokrewnym.

2

Szczegółowo zagadnienia te omówiono w dalszej części książki poświęconej grafom.

AS