1629289605

1. Wiadomości wstępne

1.1. Wprowadzenie

Rozpoczniemy od przedstawienia kilku charakterystycznych przykładów zadań optymalizacji liniowej.

Zagadnienie diety.

Jak wymieszać pszenicę, soję i mączkę rybna by uzyskać najtańszą mieszankę zapewniającą wystarczającą zawartość węglowodanów, białka i soli mineralnych dla kurcząt. Zapotrzebowanie, zawartość składników i ceny przedstawia następująca tabela:

	węglowodany	białko	sole mineralne	cena
pszenica	0,8	0,01	0,15	300 zł/t
soja	0,3	0,4	0,1	500 zł/t
mączka	0,1	0,7	0,2	800 zł/t
zapotrzebowanie	0,3	0,7	0,1

Rozpoczynamy od zdefiniowania zmiennych. Niech x* oznacza wagę i-tego składnika w mieszance.

Funkcją celu jest min xo = 300xi + 500x2 + 800x3 - czyli koszt mieszanki.

Ograniczenia są dwojakiego typu

a)    W mieszance musi być wystarczająco każdego ze składników:

0,8xi+0,3x2+ 0,1x3 >0,3

0,01xi + 0,4x2 + 0,7x3 > 0, 7

0,15xi + 0,1x2 + 0,2x3 > 0,1

b)    Waga używanych składników jest nieujemna.

Xi > 0 X2 > 0 X3 > 0

Podsumowując. Szukamy najmniejszej wartości funkcji trzech zmiennych xo : R³ —» R ograniczonej do podzbioru M³ zwanego obszarem dopuszczalnym.

Zadanie to nazywamy liniowym, bo funkcja celu xo zależy liniowo od zmiennych xi,X2,X3 i obszar dopuszczalny opisany jest zbiorem nierówności liniowych.

Zagadnienie transportowe:

Mamy 3 hurtownie i 5 sklepów. Koszt transportu jednostki towaru z i - tej hurtowni do j -tego sklepu przedstawia tabela.

Optymalizacja I © A.Strojnowski, Uniwersytet Warszawski, 2012.