104 105 2

104

Programowanie liniowe

Rozwiązanie optymalne

Rozwiązanie zadania otrzymujemy za pomocą programu PARAM.EXE. Interesujący nas przedział [-5,5] zostaje podzielony na cztery następujące pod-przedziały:

A, = [-5;-2,5], A₂ = [—2,5; - 1], A, = [-l; 1,67], A₄=[l,67;5|.

Rozwiązanie w zależności od wartości parametru t podane jest w tablicy 1.50.

Tablica 1.50

Przedział	Wartości optymalne								Wartość funkcji celu
	x,			X*	X>	X*	*7	•*»
A,	0	0	0	0	0	100	0	0	500+ 100/
a2	0	0	0	0	116,7	30	0	0	616,7+146,7/
A,	0	0	0	0	0	30	175	0	675 + 205/
a4	0	78,6	0	0	0	14,3	135,7	0	635,7 + 228,6/

&

Interpretacja rozwiązania

Przy ustalonej wartości t optymalne wielkości produkcji i wartość optymalnego zysku odczytujemy z tablicy 1.50.

2L Programowanie caftewitolicztowe

2.1. Wprowadzenie

Rozwiązując w poprzednim rozdziale przykładowe zadanie programowania produkcji (przykład 1.1), uzyskaliśmy rozwiązanie optymalne jc, =4, x₂ = 2. Obydwie składowe rozwiązania są liczbami całkowitymi. Powiemy w takim przypadku, że otrzymaliśmy rozwiązanie całkowitoliczbowe. Może się jednak zdarzyć, że otrzymane rozwiązanie nie ma tej właściwości. W wielu sytuacjach możemy wykorzystać założenie podzielności w stosunku do niektórych lub wszystkich zmiennych. Oznacza ono możliwość przyjęcia przez daną zmienną dowolnych wartości niecałkowitej. Gdyby przykładowo w zadaniu programowania produkcji okazało się, że mamy x_t =4,25, x₂ = 1,895, przy czym produkcja wyrażona jest w tonach, to otrzymane rozwiązanie interpretujemy następująco: należy wytworzyć 4250 kg produktu 1 i 1895 kg produktu 2. Nie zawsze jednak zastosowanie założenia podzielności jest uzasadnione.

Przykładem braku możliwości przyjęcia tego założenia jest zagadnienie ustalania godzin pracy kasjerek w banku, tak aby — z jednej strony — w kolejnych godzinach dostosować liczbę czynnych okienek do zmieniającej się w zależności od pory dnia liczby klientów, a z drugiej — aby zapewnić kasjerkom ciągłość pracy. Trudno byłoby zinterpretować rozwiązanie, w którym np. zaleca się zatrudnienie 3'/₂ kasjerki w godzinach popołudniowych. Podobnie, planując produkcję wyrobów liczoną w sztukach, nie zaakceptujemy rozwiązania nie wyrażającego się liczbami całkowitymi. Widzimy więc, że w pewnych sytuacjach naturalne staje się dodatkowe wymaganie, aby wszystkie (lub niektóre) zmienne w analizowanym modelu przyjęły wartości całkowite. Takie ograniczenie nazywa się warunkiem całkowitoliczbowości, nałożonym na daną zmienną decyzyjną. Powiemy przy tym, że jeżeli warunki całkowitoliczbowości nałożono na wszystkie zmienne, to mamy czyste zadanie programowania całkowitoliczbowego, natomiast gdy warunki te dotyczą jedynie części zmiennych, zadanie takie nazwiemy mieszanym zadaniem programowania całkowitoliczbowego.

Pojawia się pytanie, czy i w jaki sposób omówione w rozdziale 1 metody rozwiązywania zadań programowania liniowego, prymalną i dualną metodę simp-