409 2

Rozdział 10

Optymalizacja

10.1. Sformułowanie zadania, definicje i postać normalna

Optymalizacja liniowa (czyli programowanie liniowe) jest teorią matematyczną i zespołem ngtod numerycznych obliczania maksimum lub minimum wyrażenia liniowego w obszarze ograniczonym za pomocą układu nierówności (albo równości) liniowych względem zmiennych. Zadania tego typu występują najczęściej w zagadnieniach ekonomicznych, transportowych i produkcyjnych; mają one jednak ważne zastosowania również w telekomunikacji, teorii aproksymacji i innych dziedzinach.

Przykład 10.1.1. W pewnym zakładzie używa się trzech maszyn M_lf M₂, Af₃ do wytwarzania dwóch produktów P_t, P₂. Wyprodukowanie jednego P_t zajmuje 5 minut maszynie M_lf 3 minuty maszynie M_x i 4 minuty maszynie Af₃. Analogiczne wartości dla P₂ wynoszą odpowiednio 1, 4 i 3 minuty'. Czysty' zysk dla jednego P_t wynosi 30 dolarów, & dla jednego P₂ — 20 dolarów (niezależnie od stopnia wykorzystania maszyn). Jak zaplanować produkcję, aby przynosiła maksymalny zysk?

Przypuśćmy, że na godzinę produkuje tię jednostek produktu P_x i x₂ jednostek produktu P₂ .Wtedy zadanie polega na tym, aby znaleźć maksimum wyrażenia

f— 30xi+20.x₂

Przy ograniczeniach (10.U)

5*,+ *2^60 (dla Af,), 3xi+4x₂<60 (dla Mj), 4x₁+3x₂<60 (dla Af₃).

^xi    >0*

x₂>0.

^^Die zilustrowano rysunkiem 10.1.1. Pierwsza nierówność oznacza, że punkt (x_a, xj) Ititć na prostej AB o równaniu Sx₂+x₂ = 6Q lub na Jewo od niej. Tnnc nierówności ^można zinterpretować podobnie. Punkt (x_t, *₂) musi spełniać wszystkie nierówności, ^Włtc musi leżeć na brzegu pięciokąta OABCD lub wewnątrz niego. Wartość maksymalizuj fiuikcji jest proporcjonalna do odległości punktu (*,, x₂) od prostej/^, x₂)=0 Raczonej kreskami i kropkami; jest oczywiste, że największą wartość ma ta funkcja ^k^hołku B. Każdy wierzchołek jest punktem przecięcia dwóch boków pięciokąta.