Zarządzanie i Inżynieria Produkcji	Wydział Inżynierii Materiałowej i Metalurgii	Studia niestacjonarne I stopnia
Specjalność:
Przedmiot: B A D A N I A O P E R A C Y J N E
Jednostka prowadząca przedmiot: Katedra Zarządzania Procesami Technologicznymi.
Odpowiedzialny za przedmiot: dr hab. inż. Bolesław MACHULEC
	W	ĆW.
Sem. IV	15

Wykład:

Semestr IV.

Wprowadzenie do badań operacyjnych. Zagadnienie optymalizacji jako model matematyczny procesu podejmowania decyzji. Podstawowe pojęcia i definicje teorii optymalizacji matematycznej, klasyfikacja liniowych i nieliniowych zagadnień optymalizacji, optymalizacja jedno i wielo- kryterialna. Wybrane modele zagadnień programowania liniowego w zarządzaniu, przemyśle, technologii chemicznej, rolnictwie i transporcie - optymalny podział środków oraz wybór asortymentu produkcji, problem mieszanek, optymalny wybór procesu technologicznego, zagadnienia transportowe. Interpretacja geometryczna zadań optymalizacji liniowej. Zagadnienie dualne oraz jego interpretacja ekonomiczna. Elementy teorii grafów - modele sieciowe i drzewa decyzyjne. Gry dwuosobowe. Programowanie dynamiczne. Wprowadzenie do teorii procesów stochastycznych – systemy obsługi masowej, modele zapasów, procesy odnowy,

Laboratorium:

Semestr IV.

Tematy zajęć

Rozwiązywanie zagadnień optymalizacji liniowej i nieliniowej z wykorzystaniem algorytmów zawartych w opcji SOLVER arkusza kalkulacyjnego Excel. Budowa modelu matematycznego zagadnienia decyzyjnego. Optymalny wybór asortymentu produkcji. Zagadnienie optymalnego sporządzania mieszanin. Zagadnienia cięcia oraz minimalnego odpadu. Zagadnienia transportowe i sieciowe. Programowanie liniowe w teorii gier. Zagadnienia optymalizacji wielokryterialnej. Modele symulacyjne systemów obsługi masowej.

Warunki zaliczania przedmiotu:

Wykład:

Uzyskanie zaliczenia z ćwiczeń oraz sprawdzian z zakresu wiedzy teoretycznej i umiejętności formułowania modeli matematycznych dla typowych zadań problemów decyzyjnych.

Laboratorium:

Na podstawie sprawdzianów przeprowadzanych w trakcie ćwiczeń polegających na samodzielnym rozwiązywaniu zadań z wykorzystaniem komputera.

Literatura:

1. Borucki W. Ignasiak E, Marcinkowski J.,Sikora W.: Badania operacyjne, praca zbiorowa pod redakcją E. Ignasiaka. PWE. Warszawa 2001,

2. Szapiro T.. Kuszewski T., Nykowski L, Dubnicki W. Gąsiorowski P.. Ożdżeński W.: Decyzje menedżerskie z Excelem_s praca zbiorowa pod red. T. Szapiro, PWE, Warszawa 2000.

3. Jędrzcjczyk Z., Skrzypek 1, Kukuła K., Walkosz A.: Badania operacyjne w przykładach i zadaniach, PWN, Warszawa 2004.

4. Mitchell G.H.: Badania operacyjne. Metody i przykłady, praca pod red. G.H.Milchella, WNT, Warszawa, 1977.

5. Sadowski W.: Teoria podejmowania decyzji. Wstęp do badań operacyjnych, PWE, Warszawa, 1976,

6. Zitek F.: Stracony czas. Elementy teorii obsługi masowej, PWN, Wrocław/Poznań, 1973

1. Wstęp.

Efekty działalności gospodarczo-społecznej zmuszają nas do wnikliwej analizy powstałych sytuacji decyzyjnych polegających na rozpatrzeniu wszystkich możliwych strategii działania i skutków wynikających z ich realizacji. Sama intuicja, rozsądek i bogate doświadczenie nie wystarczają do podejmowania racjonalnych decyzji. Pomocne mogą być naukowe metody podejmowania decyzji oparte na badaniach operacyjnych, których podstawowym pojęciem jest model decyzyjny będący mniej lub bardziej dokładnym obrazem analizowanej sytuacji decyzyjnej [1].

Badania operacyjne (ang. operations research) należą do nauk o zarządzaniu, które mają określony własny przedmiot dociekań, jak również posługują się specyficznymi metodami ilościowymi. Można powiedzieć, że badania operacyjne są dziedziną nauki zajmującą się analizą celowych działal­ności (operacji), generowaniem i oceną ilościową różnych decyzji kierow­niczych ,taktycznych lub strategicznych [2]. Podstawowym przedmiotem badań operacyjnych są decyzje. Przy ich analizowaniu w badaniach operacyjnych posługujemy się metodami matematycznymi (szczególnie zaś optymalizacyjnymi), oraz symulacją komputerową. Do analizy tych decyzji niezbędna jest informacja, której przetwarzanie ułatwia technika komputerowa, stąd jej związek z bada­niami operacyjnymi. Nie należy jednak utożsamiać badań operacyjnych z techniką obliczeniową. Pełni ona jedynie rolę służebną wobec badań operacyjnych. Decyzje podejmujemy w wielu różnych sytuacjach.

Sytuacje te nazywamy sytuacjami decyzyjnymi, a osobę podejmującą decyzję – decydentem . Warunki, w jakich działa decydent, nie pozwalają na wybór dowolnej decyzji. Decyzję zgodną z warunkami ograniczającymi nazywamy decyzją dopuszczalną.

Nie każda decyzja dopuszczalna jest równie dobra. W świetle celów, jakie stawia sobie decydent, jedne decyzje mogą być lepsze, a inne gorsze. Wynika stąd problem wyboru decyzji najlepszej, zwanej decyzją optymalną. Wybór decyzji optymalnej wymaga przyjęcia określonego kryterium, według którego oceniamy decyzje jako lepsze i gorsze. Kryterium to nazywamy kryterium wyboru (oceny).

Opis określonej sytuacji decyzyjnej nazywamy problemem (zagadnieniem) decyzyjnym. Zapis problemu decyzyjnego w języku matematycznym to formułowanie modelu matematycznego. Model matematyczny problemu decyzyjnego nazywamy zadaniem decyzyjnym. Warunki ograniczające najczęściej opisywane są za pomocą układów równań lub nierówności. W równaniach tych ( lub nierównościach ) występować będą pewne wielkości dane, zwane parametrami, oraz wielkości, które należy ustalić, zwane zmiennymi decyzyjnymi.

Oprócz warunków ograniczających w zadaniu decyzyjnym mogą także występować warunki dotyczące znaku zmiennych ( np. warunek nieujemności ) lub typu zmiennych ( np. warunek ich ciągłości, całkowitoliczbowości lub binarności ).

Decyzje dopuszczalne utożsamiać będziemy z takim układem wartości zmiennych ( układem liczb ), które spełniają wszystkie warunki opisujące badaną sytuację . Rolę kryterium wyboru będzie pełnić pewna funkcja zmiennych decyzyjnych mierząca cel, który chce osiągnąć decydent. Funkcję tę nazywa się funkcją celu ( funkcja – kryterium ).

Wybór decyzji optymalnej polega na ustaleniu takiej decyzji dopuszczalnej, przy której funkcja celu osiąga wartość najkorzystniejszą, tzn. w zależności od badanej sytuacji wartość maksymalną lub minimalną.

Jeżeli przez:

D - oznaczymy zbiór decyzji dopuszczalnych,

x ∈ D – dowolną decyzję dopuszczalnych,

f – funkcję celu,

to zadanie decyzyjne można zapisać następująco:

znajdź taką decyzję dopuszczalną , że

dla - jeżeli zależy nam na maksymalizacji funkcji celu

dla - jeżeli zależy nam na minimalizacji funkcji celu.

Częściej (ale mniej dokładnie) zapisuje się to w postaci:

f(x) → max lub f(x) → min

dla x ∈ D

Opisanie sytuacji decyzyjnej w postaci modelu matematycznego ma na celu sprowadzenie zagadnienia podejmowania decyzji do rozwiązania pewnego zadania matematycznego. Aby rozwiązanie umożliwiło wybór decyzji, trzeba je tak sformułować, aby jak najlepiej opisywało sytuację decyzyjną.

Etapy budowy modelu matematycznego:

1. zdefiniowanie zmiennych decyzyjnych– należy ustalić jakie wielkości mają być wyznaczone i odpowiednio je oznaczyć, (tzn. należy oznaczyć zmienne decyzyjne).

2. ustalenie parametrów zadania– polega na zebraniu wszystkich interesujących wielkości związanych z danym zagadnieniem decyzyjnym zmiennym, np. wskaźniki techniczno-ekonomiczne, wielkości limitów, normy jakościowe, ceny, koszty i zyski jednostkowe związane z określoną działalnością,

3. określenie postaci warunków ograniczających i warunków brzegowych – polega na sformułowaniu układu równań i nierówności, jakie muszą spełniać zmienne decyzyjne; warunki brzegowe to warunki nakładane na zmienne decyzyjne, np. że dana zmienne nie może być ujemna.

4. określenie funkcji celu i kryterium optymalizacji (max czy min)– należy sformułować cel jaki chce osiągnąć decydent w postaci funkcji zmiennych określającej stopień osiągnięcia celu, oraz ustalenie jej wartości optymalnych w zbiorze decyzji dopuszczalnych przy uwzględnieniu także warunków brzegowych.

Opisane zagadnienie nazywa się zagadnieniem optymalizacji matematycznej z ograniczeniami lub inaczej zagadnieniem programowania matematycznego. Przez termin programowania matematycznego rozumie się sposób przedstawienia zagadnienia decyzyjnego jako zadania optymalizacji matematycznej. Programowanie matematyczne oznacza ustalenie takiego planu (programu), który pozwala osiągnąć dany cel w sposób najbardziej efektywny. Metody optymalizacji są dziedziną matematyki stosowanej, która znalazła szerokie zastosowanie przy podejmowaniu decyzji zarówno w zagadnieniach inżynierskich w technice, w ekonomi i w zarządzaniu.

, Włączenie do arkusza kalkulacyjnego Excel skutecznych procedur obliczeniowych oraz prostota jego obsługi stworzyło szerokie możliwości dokonywania obliczeń optymalizacyjnych. Obszar zastosowań optymalizacji matematycznej rozszerza się w sposób lawinowy i sprzyja temu rozpowszechnienie komputerów oraz oprogramowania, których zastosowanie dawno przekroczyło progi pracowni naukowych oraz uczelni. Wdrażanie matematycznych metod optymalizacji w praktyce stwarza pewne trudności ponieważ jeszcze stosunkowo do niedawna większość podręczników z tego zakresu zawiera raczej podstawy teoretyczne, niż konkretne metody i przykłady ich rozwiązywania. Ważną rolę odgrywa modelowanie matematyczne, którego zadaniem jest opis rzeczywistości w języku matematyki i logiki formalnej. Uniwersalizm tego języka sprawia, że taki sam model może opisywać systemy różniące się w sposób zasadniczy między sobą lub dotyczące zupełnie różnych dziedzin.

Ogólne sformułowanie zadań programowania matematycznego .

Niech będą dane funkcje oraz .

Zadanie programowania matematycznego polega na znalezieniu wektora x* należącego do zbioru

rozwiązań dopuszczalnych

D = {x∈Rⁿ: g_i(x)≤0,  i=1,2, …,m} (1)

takiego, że

∀ x ∈ D  f(x^*)≤f(x)

Zadanie to jest równoważne poszukiwaniu wektora x^* ∈ D takiego, że

f(x^*) = f(x) (2)

Uwaga:

Każde zadanie maksymalizacji może być sprowadzone do zadania minimalizacji:

(3)

Funkcję nazywana jest funkcją celu (lub wskaźnikiem jakości),

Funkcje nazywamy funkcjami ograniczeń lub krócej ograniczeniami,

Zbiór D nazywa się zbiorem rozwiązań dopuszczalnych.

Zadania programowania dzielą się na dwie podstawowe grupy:

1. zadania programowania liniowego;

(2) zadania programowania nieliniowego.

Spośród w/w modeli optymalizacyjnych duże znaczenie praktyczne mają modele liniowe, prowadzące do zadań programowania liniowego (ZPL). Znaczenie praktyczne ZPL wynika z tego, że można efektywnie rozwiązywać zadania w których liczba zmiennych i ograniczeń jest bardzo duża i może osiągać rząd setek tysięcy. Przy rozwiązywaniu ZPL za pomocą arkusza kalkulacyjnego dopuszczalna liczba zmiennych i ograniczeń jest znacznie mniejsza i jednym z ograniczeń jest liczba pól. W praktyce dla większości zastosowań wielkość ta jest zupełnie wystarczająca i pozwala na rozwiązywanie zadań optymalizacyjnych w których liczba zmiennych nie przekracza 200

Zadania programowania liniowego są szczególnymi odmianami zadań programowania matematycznego w którym funkcja celu jest liniowa i funkcje ograniczeń , są funkcjami liniowymi. Zadanie programowania liniowego można przedstawić następująco:

minf(x) = c₁x₁ + c₂x₂ +  …+c_nx_n

g_i(x) = a_i1x₁ + a_i2x₂ +  …+a_inx_n − b_i ≤ 0 , i = 1, 2,  … , m (4)

x_j ≥ 0 , j = 1, 2,  …,n

Ogólną postać zagadnienia programowania liniowego można przedstawić w zapisie wektorowym:

minf(x) = c • x

g_i(x) = a_i • x−b_i ≤ 0 , i = 1, 2,  … , m (5)

x ≥ 0

gdzie:

x  ∈ Rⁿ - wektory (nx1)

c,  a_i – wektory w postaci wiersza (1xn)

, i = 1, 2,  … , m

Ważną rolę przy formułowaniu zadań programowania liniowego jak i ich rozwiązywaniu odgrywają dwie postacie szczególne: tzw. postać standardowa i postać kanoniczna.

Zadaniem PL o postaci standardowej nazywamy zadanie w którym wszystkie ograniczenia są nierównościami typu ≤ dla zadań na maksimum lub nierównościami typu ≥ dla zadań na minimum, oraz wszystkie zmienne muszą być nieujemne.

$\sum_{j = 1}^{n}{c_{j} \bullet x_{j}} \rightarrow \max{\ (\min)}$

$\sum_{j = 1}^{n}{a_{\text{ij}} \bullet x_{j} \leq b_{\text{i\ }}( \geq )}$ dla   i = 1, 2,  …,m (6)

x_j ≥ 0 dla (j = 1, 2,  …,n

Nierówność ≤ dla zadania na maksimum oraz nierówność ≥ dla zadania na minimum nazywamy nierównościami typowymi.

Zadaniem PL o postaci kanonicznej nazywamy zadanie, w którym wszystkie warunki ograniczające są równościami, oraz na wszystkie zmienne nałożone są warunki dotyczące ich nieujemności.

W zapisie macierzowym zagadnienie programowania liniowego o postaci standardowej (6) można przedstawić następująco:

c^T • x → max (min)

A • x ≤ B  (≤) (7)

x ≥ 0

gdzie:

$\mathbf{A} = \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{\text{mn}} \\ \end{bmatrix}$ - macierz (mxn) parametrów modelu,

B= $\begin{bmatrix} b_{1} \\ \vdots \\ b_{m} \\ \end{bmatrix}$ - wektor wyrazów wolnych,

x= $\begin{bmatrix} x_{1} \\ \vdots \\ x_{n} \\ \end{bmatrix}$ - wektor (nx1) zmiennych decyzyjnych,

c= [c₁, x₂,  …,c_n] - wektor (1xn) wag funkcji celu

0= $\begin{bmatrix} 0 \\ \vdots \\ 0 \\ \end{bmatrix}\mathbf{\in}R^{n}$ - wektor zerowy (nx1) w przestrzeni Rⁿ

Analogicznie, zadanie PL o postaci kanonicznej w zapisie macierzowym można przedstawić następująco:

c • x → max (min)

A • x = b (8)

x ≥ 0

Zadaniem programowania nieliniowego nazywamy zadanie programowania matematycznego w którym funkcja celu f lub przynajmniej jedna z funkcji g_i będącej ograniczeniem (1) jest nieliniowa.

Przykłady zadań liniowych:

Przykład .1.1

Ograniczenia:

,

Punkt startowy:

,

Przykład .1.2 (Karlin, s.185)

Ograniczenia:

,

,

(n=20)

Przykłady zadań nieliniowych.

Zad. 1.4

Zagadnienie optymalizacji nieliniowej z ograniczeniami równościowymi

i nierównościowymi [1] :

Liczba zmiennych: 3

Ograniczenia: 1 ograniczenie równościowe, nieliniowe

1 ograniczenie równościowe, liniowe

3 graniczenia dla zmiennych niezależnych

Min

z ograniczeniami:

Punkt startowy nie będący rozwiązaniem dopuszczalnym:

Rozwiązanie:

Zad.1.5.

Zagadnienie optymalizacji nieliniowej z ograniczeniami [1]:

Liczba zmiennych: 5

Liczba ograniczeń: 6 ograniczeń nieliniowych, nierównościowych

10 ograniczeń dla zmiennych niezależnych

Uwaga: zmienne nie występują w definicji funkcji celu

Funkcja celu:

Min: =

Ograniczenia:

Punkt startowy będący rozwiązaniem dopuszczalnym:

Rozwiązanie:

Punkt startowy nie będący rozwiązaniem dopuszczalnym:

Rozwiązanie:

dla jak wyżej

1. ZAGADNIENIE WYBORU ASORTYMENTU PRODUKCJI.

Zagadnienie to polega na określeniu, które wyroby i w jakich ilościach powinno produkować przedsiębiorstwo, aby nie przekraczając dostępnych środków produkcji oraz spełniając inne dodatkowe ograniczenia zrealizować założony cel działalności. Do środków produkcji należą: surowce które są limitowane, praca ludzi, praca maszyn, energia itp.. Celem zagadnienia tego typu jest najczęściej maksymalizacja zysku lub przychodu ze sprzedaży.

Załóżmy, że przedsiębiorstwo może wytwarzać n różnych wyrobów: W₁, W₂,  … , W_n .

Skala produkcji tych wyrobów jest wielkością szukaną, dlatego zmienne decyzyjne określamy następująco: x_i - wielkość produkcji wyrobu W_i.

Wielkość produkcji poszczególnych wyrobów jest ograniczona zasobami m środków produkcji: S₁, S₂,  …,S_m. Oznaczmy zatem przez b₁, b₂,  …,b_m limity tych środków.

Ponadto oznaczmy przez: a_ij (i = 1, 2,  …,m ; j = 1, 2,  …,n) – nakłady jednostkowe środka produkcji S_i na wytworzenie jednostki wyrobu W_j, oraz przez c₁, c₂,  … , c_n – zysk jednostkowy z produkcji wyrobów W₁, W₂,  … , W_n bądź inne kategoria w zależności od tego co jest celem działalności przedsiębiorstwa, np. maksymalizacja przychodu ze sprzedaży lub jakieś inne kryterium.

Całość zagadnienia można przedstawić w postaci tablicy:

Środki produkcji	Nakłady środków produkcji na wyprodukowanie jednostki wyrobu	Zasoby środków prod.
	W1	W2
S1	a11	a12
S2	a21	a22
...	...	...
Sm	am1	am2
Zysk (Cena)	c1	c2

Model matematyczny:

...

warunki brzegowe:

funkcja celu:

Warunki ograniczające mówią, że zużycie danego środka produkcji nie może przekroczyć zasobów tego środka.

Warunki brzegowe stanowią, że wielkość produkcji nie może być ujemna.

Wartość funkcji celu przedstawia łączy zysk z produkcji lub przychód ze sprzedaży, który ma być maksymalizowany.

W niektórych przypadkach mogą także występować inne dodatkowe ograniczenia, np.:

– wielkość produkcji wyrobu W_i musi być większa lub równa od pewnej dolnej granicy d_i

– wielkość produkcji wyrobu W_i musi być mniejsza lub równa od pewnej górnej granicy g_i

- wielkość produkcji wyrobu W_i jest ograniczona z dołu i z góry.

Jeszcze inny typ ograniczeń może dotyczyć struktury produkcji, np.:

– stosunek wielkości produkcji wyrobów W₁ do W₂ ma się tak jak p : q.

Ograniczenie to sprowadzamy najczęściej do postaci liniowej i zapisujemy następująco:

qx₁ − px₂ = 0

Przykład 2.1.1

Zakład może produkować i sprzedawać 3 wyroby A, B, C. Do produkcji tych wyrobów zużywane są 2 surowce s₁ i s₂, których zasób jest ograniczony, nakłady jednostkowe oraz ceny wyrobów podane są w tabeli:

Surowce	Nakłady środków produkcji na wyprodukowanie jednostki wyrobu	Zasoby surowców
	A	B
S1	30	24
S2	4	8
Zysk	64	68

Analiza rynku ustaliła, że liczba produkowanych jednostek wyrobu A nie może przekroczyć 20, natomiast wyrobu C powinna być 3 razy większa niż wyrobu B. Kryterium celu jest maksymalizacja zysku.

Model matematyczny:

– wielkość produkcji wyrobów A, B, C

Warunki ograniczające:

- limit produkcji wyrobu A:

→ - struktura produkcji

- warunki brzegowe:

Funkcja celu:

- sumaryczny zysk.

Przykład 2.1.2.

Fabryka mebli produkuje cztery wyroby: stoły, krzesła, biurka i regały na książki. Do produkcji tych wyrobów używa dwa rodzaje su­rowca, które są dostępne w ograniczonych ilościach. Ograniczone są również zasoby siły roboczej. W tablicy podano normy techniczne zużycia surowców i siły roboczej, ich zasoby oraz zysk przypadający na każdą jed­nostkę wyprodukowanego wyrobu.

TABLICA

Należy ustalić strukturę produkcji maksymalizującą zysk fabryki i uwzględniającą żądanie, aby liczba biurek wynosiła co najmniej 30 sztuk, regałów co najmniej 10 sztuk, a liczba wyprodukowanych krzeseł i stołów była w stosunku jak 6 : 1.

Przykład .2.1.3

Odlewnia przyjęła zamówienie na produkcję 500 t stopu zawierającego: Sn ≥ 30%, Cu ≥ 60%, Ni ≤ 5%. Do realizacji zamówienia odlewnia może zakupić 4 gatunki złomu: Z₁, Z₂, Z₃, Z₄. Skład chemiczny oraz ceny poszczególnych gat. złomu zamieszczono w tablicy:

Pierwiastek		Skład chemiczny, %
	Z1	Z2	Z3
Sn	30	25	40
Cu	60	70	55
Ni	reszta	reszta	reszta
Cena, zł/kg	24	27	38

Z powodu zgaru pierwiastków w trakcie wytopu do stopu przechodzi 95% Sn, 97% Cu oraz 98% Ni. Ze względu na strukturę dostaw zużycie każdego ze złomów nie może być mniejsze niż 50t. Określić wielkość zakupu poszczególnych gatunków złomu aby wyprodukować stop o pożądanym składzie chemicznym mającym na uwadze minimalizację kosztów.

Pezykład .2.1.3

Rafineria ropy naftowej typu paliwowo – olejowego zakupuje do przerobu dwa gatunki ropy : R1 i R2, w cenach odpowiednio 7 i 14 zł za jednostkę przerobową. Wycinkowy proces technologiczny odbywający się w wieży rektyfikacyjnej daje trzy produkty. Z jednostki przerobowej ropy R1 otrzymuje się 16hl benzyny, 20hl oleju napędowego i 24hl pozostałości. Z jednostki przerobowej ropy R2 otrzymuje się 48hl benzyny, 10hl oleju napędowego oraz 14hl pozostałości. Ile należy zakupić R1 oraz R2, aby wyprodukować co najmniej 48000hl benzyny oraz 20000hl oleju napędowego przy minimalnym koszcie nabycia surowca?

Należy także wziąć pod uwagę, że zdolność przerobowa wieży rektyfikacyjnej mierzona łączną objętością wszystkich produktów wynosi 154 000hl.

Zad. 2.1.4

W fabryce należy wyprodukować stop o następujących właściwościach:

a. ciężar właściwy ≤1

b. zawartość składnika S ≥10%

c. temperatura topnienia ≥500

Stop może być produkowany z surowców P₁, P₂, P₃, których własności są następujące:

Właściwość	P1	P2	P3
Ciężar właściwy	0.90	0.95	1.02
Zaw. składnika s, %	8	12	15
Temp. topnienia, ^0C	550	500	490
Cena, zł/t	100	300	50

Określić udział surowców P₁,P₂,P₃ w mieszance, aby otrzymać stop o w/w właściwościach zakładając minimalny koszt produkcji.

Budując model matematyczny przyjąć upraszczające założenie o addytywności temperatury topnienia.

2.3. Zagadnienie wyboru procesu technologicznego.

Najogólniej rzecz biorąc problem wynika z faktu, że produkcja wyrobów (wyrobu) może odbywać się przy zastosowaniu różnych technologii. Zagadnienie polega na określeniu w jakiej skali (ilości, intensywności) należy stosować poszczególne rodzaje procesów technologicznych, aby wytworzyć określone ilości wyrobów przy możliwie najniższych kosztach. Kryterium celu może być również maksymalizacja zysku, lub maksymalizacja przychodu ze sprzedaży. Załóżmy, że przedsiębiorstwo może stosować n różnych procesów technologicznych T₁, T₂,  …,T_n do produkcji m wyrobów W₁, W₂,  …, W_m. Ponieważ skala (ilość, intensywność) zastosowania poszczególnych procesów technologicznych jest wielkością szukaną definiujemy zmienne decyzyjne następująco:

x_j - skala (ilość, intensywność) z jaką należy prowadzić proces technologiczny

T_j, j = 1, 2,  …,n.

Ilość poszczególnych wyrobów jaką przedsiębiorstwo powinno wytworzyć oznaczamy następująco: b₁, b₂,  …,b_m. Przez a_ij (i = 1, 2,  …,m ; j = 1, 2,  …,n) oznaczamy ilość wyrobu W_i jaką uzyskuje się w wyniku zastosowania procesu technologicznego T_j, a przez c₁, c₂,  …,c_n oznaczamy koszty jednostkowe, jakie ponosi się przy zastosowaniu w skali jednostkowej procesu technologicznego T_n, (j = 1, 2,  …,n). Parametry c_j mogą oznaczać również zyski jednostkowe z zastosowania poszczególnych procesów technologicznych w przypadku gdy kryterium celu jest maksymalizacja zysku .

Całość zagadnienia można przedstawić w postaci tablicy:

Wyroby	Ilość wyprodukowanych wyrobów Wj w wyniku zastosowania procesu Tj	Plan produkcji
	T1	T2
W1	a11	a12
W2	a21	a22
...	...	...
Wm	am1	am2
Koszt jednostkowy (zysk jednostkowy)	c1	c2

Model matematyczny:

( ≥ b₁)

( ≥ b₂)

...

( ≥ b_m)

warunki brzegowe:

funkcja celu:

Warunki ograniczające mówią, że wielkość produkcji poszczególnych wyrobów W_j powinna być zgodna z planem. Warunki brzegowe stanowią, że skala produkcji (ilość, intensywność) zastosowania poszczególnych procesów T_j nie może być ujemna. Wartość funkcji celu przedstawia sumaryczny koszt produkcji, ewentualnie sumaryczny zysk . Niekiedy warunki ograniczające (ale tylko w przypadku minimalizacji funkcji celu) zapisuje się w formie nierówności typu (≥), gdyż dopuszcza się przekroczenie planu produkcji.

Najczęściej spotykanym wariantem zagadnienia wyboru procesu technologicznego jest tzw. problem rozkroju. Problem pojawia się wtedy, gdy z pewnego surowca (kłody drewna, papieru, blachy, drutu) należy wykroić pewną ilość elementów o określonych wymiarach (np. deski o określonej długości, detale o określonych wymiarach). Surowiec można ciąć różnymi sposobami otrzymując przy tym różną ilość pożądanych elementów i jednocześnie pewną ilość odpadu. Odpad ten jest kosztem, który chcemy minimalizować. A zatem zagadnie sprowadza się do ustalenia w jakiej skali należy stosować poszczególne sposoby rozkroju (liczbę jednostek surowca jaką należy pociąć danym sposobem), aby otrzymać żądaną liczbę elementów przy najmniejszym odpadzie surowca.

Przykład 1

Zakład stolarski otrzymał zamówienie na dostarczenie 100 kompletów desek. Komplet składa się z jednej deski długiej (o długości ), jednej deski średniej (o długości ) i dwóch desek krótkich (o długości ). W hurtowni można nabyć deski o wymaganym przekroju i długości 3m. W jaki sposób należy zrealizować zamówienie, aby odpad powstały w procesie cięcia był minimalny ?

Rozwiązanie:

1. Sposoby rozkroju:

2. Zmienne decyzyjne:

x_i - liczba zastosowań sposobu rozkroju T_i,  i = 1, 2,  …,5

1. Model matematyczny:

Warunki ograniczające:

x₁ + x₂                                        ≤ 100 (deski o dł. 1.8 m, szt.)

x₁ +      2x₃ + x₄                      ≤ 100    (deski o dł. 1.1 m, szt.)

x₂ + x₃ + 2x₄ + 3x₅    ≤ 200 (deski o dł. 0.8 m, szt.)

Warunki brzegowe:

x₁, x₂,  …,x₅ ≥ 0

x₁, x₂, …, x₅ ∈ C

Funkcja celu:

F(x₁,x₂,…,x₅) = 0.1x₁ + 0.4x₂ +  0.3x₄ + 0.6x₅ → min

Przykład 2.

Zakład otrzymał 150 arkuszy tektury , z których wycinane są trzy rodzaje elementów: E₁^, E₂,E₃. Pięć sposobów rozkroju jednego arkusza, które zastosowano, oraz jednostkowe zyski ze sprzedaży poszczególnych elementów podano w tabeli. Ile razy należy zastosować możliwe sposoby cięcia, aby zmaksymalizować zysk ze sprzedaży elementów, biorąc pod uwagę, że elementów E₃ powinno być dwa razy więcej niż elementów E₁.

Przykłąd 3.

Zakład produkujący puszki do konserw otrzymał surowiec w postaci dwóch rodzajów blachy: blachy o szerokości i 14000 blachy o szerokości . Z blachy wycinane są potrzebne elementy: denka i ściany boczne. Stosowane sposoby rozkroju blachy podano w tablicy poniżej. Zmaksymalizować liczbę otrzymanych puszek, pamiętając, że każda puszka ma dwa denka i jedną ścianę boczną. W jakim stopniu zostanie wykorzystana blacha obydwu rodzajów.

Tablica

Elementy	Sposoby rozkroju blachy
	Szerokość –
	I
Denka	70
Ściany boczne	-

Przykład. 4

Przedsiębiorstwo żeglugowe dysponuje barkami o ładowności 8 i 10 t. Klient dostarczył 625 t drobnicy w opakowaniach 2.5 t, 930 t w opakowaniach 3 t i 2025 t w opakowaniach 4.5 t. Zoptymalizować przewóz drobnicy przy maksymalnym wykorzystaniu ładowności barek, jeśli wiadomo, że maksymalna liczba użytych barek o ładowności 8 t nie może przekroczyć 30.

Wskazówka:

6. Zagadnienia transportowe.

Zagadnienie transportowe zostało sformułowane po raz pierwszy w 1941 roku przez F.L.Hitchocka jako problem opracowania planu przewozu pewnego jednorodnego produktu z kilku różnych źródeł zaopatrzenia do kilku punktów zgłaszających zapotrzebowanie na towar. Zagadnienia transportowe należą do jednych z najczęstszych zastosowań programowania liniowego. Znaczenie zagadnienia transportowego jest tym większe, że wiele problemów praktycznych, często nie mających nic wspólnego z transportem posiadają taką samą strukturę matematyczną jak zagadnie. Są to m.in.:

- zagadnienia transportowo-produkcyjne,

- zagadnienia lokalizacji produkcji,

- zagadnienie minimalizacji pustych przebiegów,

- zagadnienie przydziału zadań produkcyjnych.

W celu sformułowania zagadnienia transportowego w postaci ogólnej wprowadzamy następujące oznaczenia:

D_i - dostawcy pewnego jednorodnego produktu (np. kopalnie, cementownie, cukrownie),

i = 1, 2,  …,m,

O_j - odbiorcy tego produktu (np. składy budowlane, hurtownie sklepy), j = 1, 2,  …,n

gdzie:

   m, n - liczba dostawców i odbiorców

Każdy dostawca D_i może dostarczyć produkt w ilości a_i dla  i = 1, 2,  …,m . Wielkości te umownie będziemy nazywać podażą. Każdy odbiorca O_j posiada określone zapotrzebowanie b_j, j = 1, 2,  …, n.

Wielkości te będziemy umownie nazywać popytem. Ponadto dane są jednostkowe koszty transportu c_ij od każdego dostawcy D_i do każdego odbiorcy O_j, (i = 1, 2,  …,m ,j = 1, 2,  …,n).

Wymienione informacje można przedstawić w postaci tablicy:

Dostawcy	Koszty transportu cij  od dostawcy Di do odbiorcy Dj	Możliwości dostawców
	O1	O2
D1	c11	c12
D2	c21	c22
...	...	...
Dm	cm1	cm2
Możliwości odbiorców	b1	b2

Zadanie transportowe sprowadza się do wyznaczenia ilości towaru jakie należy przewieźć od każdego z dostawców do poszczególnych odbiorców. Dlatego zmienne decyzyjne definiujemy następująco:

x_ij - ilość towaru przewożona od dostawcy D_i do odbiorcy O_j, (i = 1, 2,  …,m ,j = 1, 2,  …,n).

Model matematyczny zagadnienia transportowego zależy od relacji pomiędzy sumaryczną podażą:

$\sum_{i = 1}^{m}a_{i}$,

, a sumarycznym popytem:

$\sum_{j = 1}^{n}b_{j}$

Zagadnienie transportowe może być:

1. zbilansowane (zamknięte), gdy sumaryczna podaż jest równa sumarycznemu popytowi, tzn.:

$\sum_{i = 1}^{m}a_{i} = \sum_{j = 1}^{n}b_{j}$

W takiej sytuacji zarówno warunki ograniczające dla dostawców jak i odbiorców są równaniami:

$\sum_{j = 1}^{n}{x_{\text{ij}} = a_{i}}$ (i = 1, 2,  …,m), - warunki dla dostawców, (6.1)

$\sum_{i = 1}^{m}{x_{\text{ij}} = b_{j}}$ (j = 1, 2,  …,n), - warunki dla odbiorców, (6.2)

x_ij ≥ 0 (i = 1, 2,  …,m ,j = 1, 2,  …,n) - warunki brzegowe (6.3)

Funkcja celu:

$\sum_{i = 1}^{m}{\sum_{j = 1}^{n}{c_{\text{ij}} \bullet x_{\text{ij}}}} \rightarrow min$ (6.4)

Zapis (6.1) oznacza, że każdy dostawca wyśle dokładnie tyle towaru ile posiada, a zapis (6.2), że zapotrzebowanie każdego z odbiorców zostanie w pełni zaspokojone.

Warunki (6.3) oznaczają, że ilość towaru przesyłana na poszczególnych trasach od dostawcy D_i do odbiorcy O_j nie może być ujemna.

Funkcja celu wyraża sumaryczny koszt transportu towaru na wszystkich trasach.

1. Niezbilansowane (otwarte), gdy sumaryczna popyt nie jest równy sumarycznej podaży. W tym przypadku można wyróżnić dwa przypadki:

B1. Sumaryczna podaż jest większa niż sumaryczny popyt, tj.:

$\sum_{i = 1}^{m}a_{i} > \sum_{j = 1}^{n}b_{j}$ (6.5)

W takiej sytuacji u dostawców zostanie pewna ilość towaru, natomiast zapotrzebowanie wszystkich odbiorców zostanie w pełni zaspokojone, zatem postać modelu jest następująca:

$\sum_{j = 1}^{n}{x_{\text{ij}} \leq a_{i}}$ (i = 1, 2,  …,m), - warunki dla dostawców, (6.6)

$\sum_{i = 1}^{m}{x_{\text{ij}} = b_{j}}$ (j = 1, 2,  …,n), - warunki dla odbiorców, (6.7)

x_ij ≥ 0 (i = 1, 2,  …,m ,j = 1, 2,  …,n) - warunki brzegowe (6.8)

Funkcja celu:

$\sum_{i = 1}^{m}{\sum_{j = 1}^{n}{c_{\text{ij}} \bullet x_{\text{ij}}}} \rightarrow min$ (6.9)

B2. Sumaryczna podaż jest mniejsza niż sumaryczny popyt, tj.:

$\sum_{i = 1}^{m}a_{i} < \sum_{j = 1}^{n}b_{j}$ (6.10)

W takiej sytuacji dostawcy wyślą cały posiadany towar, natomiast zapotrzebowanie odbiorców nie zostanie w pełni zaspokojone , zatem postać modelu jest następująca:

$\sum_{j = 1}^{n}{x_{\text{ij}} = a_{i}}$ (i = 1, 2,  …,m), - warunki dla dostawców, (6.11)

$\sum_{i = 1}^{m}{x_{\text{ij}} \leq b_{j}}$ (j = 1, 2,  …,n), - warunki dla dostawców, (6.12)

x_ij ≥ 0 (i = 1, 2,  …,m ,j = 1, 2,  …,n) - warunki brzegowe (6.13)

Funkcja celu:

$\sum_{i = 1}^{m}{\sum_{j = 1}^{n}{c_{\text{ij}} \bullet x_{\text{ij}}}} \rightarrow min$ (6.14)

Przykład 1

Istnieje trzech dostawców D₁,  D₂, D₃ pewnego produktu o możliwościach dostarczenia tego towaru w ilościach (t): a₁ = 90,   a₂ = 70,  a₃ = 130, oraz trzech odbiorców: O₁, O₂, O₃ o zapotrzebowaniu (t): b₁ = 80,  b₂ = 120,  b₃ = 60. Jednostkowe koszty transportu (w zl/t) podane są w tablicy. Tablica uzupełniona jest informacją dot. wielkości podaży dostawców oraz wielkości popytu odbiorców.

Określić rozmiary dostaw od poszczególnych dostawców do poszczególnych odbiorców tak, aby sumaryczny koszt transportu był minimalny.

Rozwiązanie:

Zmienne decyzyjne definiujemy następująco:

x_ij - ilość towaru przewożona od dostawcy i do odbiorcy j, t , (i = 1, 2, 3 ; j = 1, 2, 3).

Przed przystąpieniu do budowy modelu należy sprawdzić, czy model jest zbilansowany, czy nie?

Z danych zamieszczonych w tablicy wynika, że sumaryczna podaż jest większa od sumarycznego popytu, ponieważ:

$\sum_{i = 1}^{m}{a_{i} = 290} > \sum_{j = 1}^{n}{b_{j} = 260}$

zatem postać modelu jest następująca:

Warunki dla dostawców:

x₁₁ + x₁₂ + x₁₃ ≤ 90 (D₁)

x₂₁ + x₂₂ + x₂₃ ≤ 70 (D₂)

x₃₁ + x₃₂ + x₃₃ ≤ 130 (D₃)

Warunki dla odbiorców:

x₁₁ + x₂₁ + x₃₁ = 80 (O₁)

x₁₂ + x₂₂ + x₃₂ = 120 (O₂)

x₁₃ + x₂₃ + x₃₃ = 60 (O₃)

Warunki brzegowe:

x_ij ≥ 0,  i = 1, 2, 3; j = 1, 2, 3

Funkcja celu:

F(x) = 5x₁₁ + 9x₁₂ + 6x₁₃ +  

                 +                  …               +

                  + 11x₃₁ + 2x₃₂ +  9x₃₃ → min

6.1 Sposób bilansowania otwartego zagadnienia transportowego.

Każde zagadnienie niezbilansowane (otwarte) można sprowadzić do postaci zbilansowanej (zamkniętej). Sposób bilansowania modelu jest odmienny w zależności od tego, czy sumaryczna podaż jest większa niż sumaryczny popyt, czy też przeciwnie.

W przypadku gdy spełniona jest zależność (6.5) tzn. sumaryczna podaż jest większa od popytu w celu zbilansowania modelu należy wprowadzić tzw. „fikcyjnego odbiorcę”, który „przyjmie” nadmiar towaru. Oznaczmy więc:

O_n + 1 - fikcyjny odbiorca,

b_n + 1 – zapotrzebowanie fikcyjnego odbiorcy,

x_{i, n + 1} - ilość towaru „przewożona” od i - tego dostawcy do fikcyjnego odbiorcy O_n + 1,

( i = 1, 2,  …,m)

Ponieważ zachodzi (6.5) zapotrzebowanie fikcyjnego odbiorcy określamy tak, aby spełniona była równość:

$\sum_{i = 1}^{m}{a_{i} = \sum_{j = 1}^{n}{b_{j} + b_{n + 1}}}$

, zatem

b_n + 1= $\sum_{i = 1}^{m}{a_{i} - \sum_{j = 1}^{n}b_{j}}$ (6.15)

W rzeczywistości nie przewozi się towaru od poszczególnych dostawców do odbiorcy fikcyjnego. W związku z tym wielkość x_{i,   n + 1} należy rozumieć jako ilość towaru, która pozostanie u dostawcy D_i.

Ponieważ na trasach fikcyjnych nie ma przewozu, więc koszty transportu na tych trasach są równe 0.

W przypadku, gdy zachodzi (6.10), tj. sumaryczna podaż jest mniejsza niż sumaryczny popyt i zapotrzebowanie odbiorców nie zostanie w pełni zaspokojone dla zbilansowania modelu wprowadzamy „fikcyjnego dostawcę”, który „pokryje” niezaspokojone zapotrzebowanie odbiorców.

Oznaczmy więc:

D_m + 1 - fikcyjny dostawca,

a_m + 1  - możliwości fikcyjnego dostawcy,

x_{m + 1, j} - ilość towaru „przewieziona” od fikcyjnego dostawcy D_m + 1 do j - ego odbiorcy,

        j = 1, 2,  …, n

Ponieważ zachodzi (6.10) możliwości fikcyjnego dostawcy określamy tak, aby spełniona była równość:

$\sum_{i = 1}^{m}{a_{i} + a_{m + 1} = \sum_{j = 1}^{n}b_{j}}$

zatem,

$a_{m + 1} = \sum_{j = 1}^{n}b_{j} - \sum_{i = 1}^{m}a_{i}$ (6.16)

W rzeczywistości na trasach fikcyjnych nie przewozi się towaru, zatem wielkości x_{m + 1, j} należy rozumieć jako ilość towaru jakiej zabraknie do zaspokojenia odbiorców.

Przykład.2

Cztery zakłady dziewiarskie: Z₁, Z₂, Z₃ i Z4 zaopatrują się we włóczkę w trzech hurtowniach: H₁, H₂ i H₃. Zapotrzebowanie zakładów wynosi kolejno: 600, 500, 400 i 700 kg włóczki miesięcznie, natomiast poszczególne hurtownie mają na składzie 1200, 800 i 1000 kg włóczki. Jednostkowe koszty transportu pomiędzy hurtowniami, a zakładami zestawiono w tablicy poniżej:

Hurtownie	Zakłady
	Z1
H1	6
H2	5.5
H3	5

Włóczka, która nie została sprzedana w miesiącu, będzie magazynowana w hurtowniach, przy czym jednostkowe koszty magazynowania wynoszą odpowiednio 2, 1 i 2 zł miesięcznie.

Podać optymalny plan transportu i magazynowania włóczki, minimalizujący łączne koszty transportu i magazynowania. Podać łączną wysokość kosztów oraz dokonać ich rozliczenia na transport i magazynowanie.

Rozwiązanie:

W rozpatrywanym przykładzie sumaryczna podaż jest większa od popytu, tj.

$\sum_{i = 1}^{3}{a_{i} = 3000 > \sum_{j = 1}^{4}{b_{j} = 2200}}$ ,kg

W celu sprowadzenia w/w zagadnienia do zamkniętego zadania transportowego wprowadzamy fikcyjnego odbiorcę F, który „przyjmie” nadwyżkę włóczki, która jest w hurtowniach. Na podstawie (6.15) zapotrzebowanie fikcyjnego odbiorcy wynosi, kg:

b₅ = 3000 − 2200 = 800

Zamknięte zagadnienie transportowe przedstawione jest w tablicy poniżej:

Należy zwrócić uwagę, że wielkość transportu z poszczególnych hurtowni do odbiorcy fikcyjnego F

reprezentuje towar na który niema zapotrzebowania i pozostanie w magazynie. Dlatego w powyższej tablicy „koszty transportu” włóczki z poszczególnych hurtowni do odbiorcy fikcyjnego są równe kosztom magazynowania włóczki w hurtowniach.

Zmienne decyzyjne:

x_ij - wielkość transportu z hurtowni H_i do poszczególnych odbiorców Z₁,  … , Z₄, F , kg,

(i = 1, 2, 3; j = 1, 2, 3, 4, 5)

Warunki dla dostawców:

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ = 1200 (H₁)

x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ = 800 (H₂)

x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ = 1000 (H₃)

Warunki dla odbiorców:

x₁₁ + x₂₁ + x₃₁ = 600 (Z₁)

x₁₂ + x₂₂ + x₃₂ = 400 (Z₂)

… …

x₁₅ + x₂₅ + x₃₅ = 800 (F)

Warunki brzegowe:

x_ij ≥ 0 , (i = 1, 2, 3 ; j = 1, 2, 3, 4, 5)

Funkcja celu:

F(x) = 6x₁₁ + 4x₁₂ + 3.5x₁₃ + 5x₁₄ + 2x₁₅+

+ … +

+ 5x₃₁ + 8.5x₃₂ + 2.5x₃₃ + 8x₃₄ + 2x₃₅ → min

Funkcja celu F(x) stanowi sumaryczny koszt transportu i magazynowania.

Koszt magazynowania wynosi: M(x) = 2x₁₅ + x₂₅ + 2x₃₅

Koszt transportu wynosi: T(x) = F(x) − M(x)

6.2. Zagadnienie transportowo-produkcyjne.

W zagadnieniu tansportowo-produkcyjnym (ZT-P) dostawcami są producenci towaru a nie magazyny. Model można scharakteryzować następująco: m - producentów pewnego jednorodnego produktu, z których każdy ma zdolność produkcyjną a_i jednostek towaru (i = 1, 2,  …,m), zaopatruje n odbiorców. Każdy odbiorca zgłasza zapotrzebowanie na b_j jednostek (j = 1, 2,  …,n). Zakłada się, że łączne zdolności produkcyjne zakładów przekraczają łączne zapotrzebowanie. Dane są ponadto jednostkowe koszty transportu towaru z i-tego zakładu do j-tego odbiorcy – c_ij , oraz jednostkowe koszty produkcji w i -tym zakładzie - h_i . Towar nie został jeszcze wyprodukowany i należy podjąć decyzję gdzie go produkować i jak rozsyłać do odbiorców, aby łączne koszty produkcji i transportu (oraz ewentualnie magazynowania nadwyżek ) były możliwie najniższe.

Zadanie ZT-P można łatwo sprowadzić do zamkniętego zagadnienia transportowego (ZZT) poprzez skonstruowanie macierzy łącznych kosztów transportu i produkcji:

k_ij = h_i + c_ij ,( i = 1, 2,  …,m ; j = 1, 2,  …, n)   (6.17)

W ZT-P zmienne decyzyjne określamy następująco:

x_ij - ilość towaru wyprodukowana w i-tym zakładzie i dostarczona do j-tego odbiorcy.

W przypadku, gdy należy uwzględnić koszty magazynowania nadwyżek produkcji w poszczególnych zakładach należy zastosować przedstawiony w punkcie (6.1) sposób bilansowania otwartego modelu ZT poprzez wprowadzić fikcyjnego odbiorcę, który będzie reprezentować nie wykorzystane zdolności produkcyjne poszczególnych producentów (x_{i,   n + 1}) i którego zapotrzebowanie jest różnicą pomiędzy sumą zdolności produkcyjnych wytwórców i sumą zapotrzebowań odbiorców, tzn.:

b_n + 1 =

Oprócz kosztów transportu i produkcji w macierzy kosztów (6.17) należy dodatkowo uwzględnić koszty produkcji i magazynowania towaru, na który nie ma zapotrzebowania i który jest magazynowany:

k_{i, n + 1} = τ_i + c_ij (6.18)

gdzie:

τ_i - koszt magazynowania w zakładzie Z_i, i = 1, 2,  …,m

Przykład 3.

Trzy kopalnie: K₁, K₂, K₃ dostarczają węgiel do pięciu składów opału położonych w różnych miejscowościach. Każdy ze składów może przy­jąć 400 t węgla miesięcznie, natomiast możliwości wydobywcze kopalń wyno­szą: K₁ - 600 t, K₂ i K₃ - po 700 t miesięcznie. Koszty wydobycia l t węgla w kopalniach wynoszą odpowiednio: 108, 96 i 102 zł, natomiast jednostkowe koszty transportu w zl/t (zależne od odległości) zawiera tablica:

Kopalnie	Składy opału
	S1
K1 K2 K3	14 30 9

Ustalić plan przewozu węgla, mający na celu minimalizację łącznych kosztów wydobycia i transportu węgla.

Wskazówka:

Zadanie sprowadzamy do klasycznego zagadnienia transportowego w którym koszty wydobycia węgla i jego transportu, a także dane dot. podaży i popytu zamieszczone są w tablicy:

6.4. Zagadnienie lokalizacji produkcji.

W modelu transportowo-produkcyjnym zakłada się, że lokalizacja zakładów produkcyjnych jest już ustalona i pozostaje tylko problem wyrobu wielkości produkcji w poszczególnych zakładach i jej przewozu do odbiorców. Natomiast zagadnienie lokalizacji produkcji oparty jest na założeniu, że dla zaspokojenia zapotrzebowania odbiorców trzeba uruchomić nowe zakłady i wyznaczyć ich lokalizację.

Danych jest n punktów zapotrzebowania na pewien towar oraz m punktów, w których możliwa jest lokalizacja zakładów produkujących ten towar. Zapotrzebowanie na towar w j-tym punkcie wynosi b_j jednostek (j = 1, 2,  …,n), a potencjalna zdolność produkcyjna w i-tym punkcie a_i (i = 1, 2,  …,m). Oszacowane jednostkowe koszty produkcji w j-tym punkcie wynoszą h_i, a oszacowane koszty transportu towaru z punktu i do odbiorcy O_j wynoszą c_ij . A zatem k_ij = h_i + c_ij są oszacowanymi jednostkowymi kosztami produkcji i transportu. Zagadnienie to rozpatruje się przy następujących założeniach:

1.

2. a_i <

Założenie 1 przyjmuje się dlatego, iż w przypadku zbilansowania potencjalnych zdolności produkcyjnych zakładów z zapotrzebowaniem odbiorców nie ma problemu lokalizacji, ponieważ dla zaspokojenia zapotrzebowania odbiorców trzeba bowiem wybudować wszystkie zakłady. Nie byłoby również problemu lokalizacji, gdybyśmy założyli, że zakłady będą w pełni wykorzystywać swoje zdolności produkcyjne, a nadwyżkę ponad zapotrzebowanie odbiorców magazynować. Założenie 2 wyklucza możliwość zaspokojenia zapotrzebowania przez budowę zakładu produkcyjnego tylko w jednym punkcie.

Należy ustalić, w których punktach trzeba zlokalizować zakłady, ile w każdy zakładzie produkować i jak przewozić towar, aby zaspokoić zapotrzebowanie odbiorców przy minimalnych łącznych kosztach transportu i produkcji. Zmienne decyzyjne x_{i j} to wielkości produkcji w i-tym punkcie dostarczane j-temu odbiorcy.

Zagadnienie to sprowadza się do zamkniętego zagadnienia transportowego tak samo jak zagadnienie transportowo- produkcyjne, przy czym fikcyjny odbiorca reprezentuje łączne nie wykorzystane zdolności produkcyjne we wszystkich potencjalnych punktach produkcji.

Przykład 4

Projektowana jest budowa 1-3 zakładów mleczarskich mających zaopatrywać w masło cztery miejscowości: P, R, S i T. Zakłady mogą powstać w miejscowościach P, R lub S . Dzienne zdolności produkcyjne zakładów A_i, zapotrzebowanie miast na masło B_j (w kg) oraz oszacowane przyszłe jednostkowe koszty produkcji h_i i przewozu masła c_{i j} (w zł za kg) podano w tablicy:

ci j	P	R	S	T	Ai	hi
P R S	0 1 0,5	0,4 0 0,5	0,5 0,8 0	1 0,6 0,8	3000 2000 2500	8 9 8,4
Bj	1000	2000	1000	1000

Zaproponować lokalizację zakładów, dzięki której całkowite koszty produkcji i transportu mleka będą możliwe najniższe.

Rozwiązanie Spełnione są obydwa założenia modelu lokalizacji produkcji, bowiem

1. , a więc istnieje problem lokalizacji

2. . A₁ = 3000 < , . A₂ = 2000 < , . A₃ = 2500 <

Po sprowadzeniu problemu do zagadnienia zamkniętego i uwzględnieniu kosztów produkcji w poszczególnych zakładach tabela przybierze postać:

ci j	P	R	S	T	F	Ai
P R S	8,0 10,0 8,9	8,4 9,0 8,9	8,5 9,8 8,4	9,0 9,6 9,2	0 0 0	3000 2000 2500
Bj	1000	2000	1000	1000	2500

Zmienne decyzyjne x_{i j} oznaczają wielkość produkcji masła w i-tej miejscowości dostarczoną do miejscowości j-tej, przy czym x_{i 5} (i = 1,2,3) to nie wykorzystane zdolności produkcyjne zakładów poszczególnych miejscowościach.

Model

1. warunki ograniczające dla zakładów produkcyjnych

2. warunki ograniczające dla miejscowości odbiorców

przy czym ostatni z nich bilansuje zdolności produkcyjne z zapotrzebowaniem (określa łączną nie wykorzystaną zdolność produkcyjność)

x_{i j} 0 dla i = 1,2,3: j = 1,2,...,5.

1. funkcja celu

K(x) = 8,0x₁₁ + 8,4x₁₂ + 8,5x₁₃ + 9,0x₁₄ + 0x₁₅

+ 10,0x₂₁ + 9,0x₂₂ + 9,8x₂₃ + 9,6x₂₄ + 0x₂₅

+ 8,9x₃₁ + 8,9x₃₂ + 8,4x₃₃ + 9,2x₃₄ + 0x₃₅ min

6.5. Zagadnienie rozdziału zadań produkcyjnych pomiędzy miejscami produkcji

Zakłada się, że n wyrobów (czynności) można wykonywać w m miejscach produkcji (w zakładach, na stanowiskach pracy, na maszynach). Należy rozdzielić produkcję wyrobów (wykonywanie czynności) pomiędzy miej­sca produkcji. Konkretna postać modelu zależy od charakteru podanych parametrówa_ij.

Model 1

Dane są wydajności miejsc przy wykonywaniu poszczególnych wyrobów, ograniczone zdolności produkcyjne poszczególnych miejsc pracy, a często także zadania planowe w zakresie produkcji poszczególnych wyrobów. A zatem parametrami w tym modelu są:

a_ij - wydajność i-tego miejsca przy wykonywaniu j-ego wyrobu,

c_j (j = 1, 2,  …,n) - założona wielkość produkcji j-ego wyrobu,

b_i (i = 1, 2,  …,m) - dopuszczalny czas pracy i-ego miejsca.

Należy przydzielić produkcję wyrobów do poszczególnych miejsc pracy tak, aby np. zminimalizować czas lub koszty produkcji albo też zmaksymalizować efekty (wielkość produkcji). Jeżeli znane są wydajności w jednostce czasu, to przydział będzie polegał na określeniu czasu pracy i-tego miejsca przy wykonywaniu j-ego wyrobu – x_ij. Należy zatem rozwiązać zadanie optymalizacji w którym warunkami ograniczającymi są:

x₁₁ + x₁₂ +  …+x_1n ≤ b₁

x₂₁ + x₂₂ +  …+x_2n ≤ b₂

…

x_m1 + x_m2 +  …+x_mn ≤ b_m

(tzn. nie można przekroczyć dopuszczalnych czasów pracy poszczególnych miejsc);

a₁₁x₁₁ + a₂₁x₂₁ + … + a_m1x_m1 ≥ c₁

a₁₂x₁₂ + a₂₂x₂₂ + … + a_m2x_m2 ≥ c₁

…

a_1N x_1N + a_2N x_2N + ... + a_PN x_PN =

(należy wytworzyć planowane – potrzebne- ilości)

x_ij 0 dla i = 1,2,...,P; j = 1,2,...,N.

F(x) = x₁₁ + x₁₂ + ... + x_1N +

.................................

+ x_P1 + x_P2 + ... + x_PN = min

(minimalizacja łącznego czasu pracy wszystkich miejsc przy produkcji wszystkich wyrobów)

Przykład 4.

Do produkcji swych wyrobów przedsiębiorstwo zużywa m.in. pięć elementów. Elementy te muszą być wytwarzane na maszynach, których przedsiębiorstwo nie posiada, dlatego korzystano z dostaw kooperan­ta. Dostawca postanowił zmienić profil swej produkcji i wycofał się ze współpracy. Zobowiązał się jedynie do wydzierżawienia trzech maszyn, na których elementy mogą być produkowane, jednak nie dłużej niż na 180 godz. w ciągu miesiąca każdą. Każdy podzespół może być produkowany na dowol­nej maszynie. Maszyny różnią się wydajnością przy produkcji poszczególnych elementów, co ilustruje tablica:

Maszyna	Wydajność maszyny (w szt./godz.) przy produkcji podzespołu
	1	2
I II III	0,8 0,75 1,25	1 0,6 1,20

Wiedząc, że l godz. pracy maszyny I kosztuje 30 zł, l godz. pracy maszyny II - 42 zł i l godz. pracy maszyny III - 36 zł, należy rozdzielić miesięczną produkcję elementów pomiędzy maszyny tak, aby wyprodukować co najmniej po 90 szt. elementów l, 2 i 3 oraz co najmniej po 75 szt. elementów 4 i 5 przy możliwie najniższych kosztach dzierżawy (pracy) maszyn.

Rozwiązanie

Jeżeli są dane wydajności maszyn przy produkcji po­szczególnych elementów (w szt./godz.), to aby rozdzielić produkcję elementów pomiędzy maszyny, należy określić czas pracy (w godz.) i-tej maszyny (i= l,2,3) przy produkcji j-ego podzespołu (j= l,2,...,5)-i to będą zmienne decyzyjne x_ij. Zmienne decyzyjne powinny spełniać dwie grupy warunków. Po pierw­sze, ograniczony jest dopuszczalny czas pracy maszyn. I tak, maszyna I przy produkcji wszystkich elementów może pracować nie dłużej niż 180 godz., zatem

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ ≤ 80

i analogicznie maszyny II i III

x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ ≤ 180

x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ ≤ 180

Po drugie, określone są zadania planowe w zakresie poszczególnych elementów. Na tych trzech maszynach należy wyprodukować łącznie co najmniej 90 szt. elementów l, czyli

0,8x₁₁ + 0,75x₂₁ + 1,25x₃₁ ≥ 90

i analogicznie dla pozostałych elementów:

1,0x₁₂ + 0,6x₂₂ + 1,2x₃₂ ≥ 90

0,4x₁₃ + 0,5x₂₃ + 0,375x₃₃ ≥ 90

2,0x₁₄ + 1,875x₂₄ + 1,5x₃₄ ≥ 75

0,625x₁₅ + 0,6x₂₅ + 0,5x₃₅ ≥ 75

Oczywiście x_{i j} ≥ 0 (i = 1,2,3; j = 1,2,...,5)

W funkcji celu należy zminimalizować łączne koszty pracy (dzierżawy) maszyn, czyli

F(x_{i j} ) = 30(x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅) +

+ 42(x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅) +

+ 36(x₃₁ + x₃₂ + x₃₃ + x₃₄ + x₃₅ ) min

Model 2

Dane są czasy pracy poszczególnych miejsc (stanowisk) przy wykonywa­niu poszczególnych wyrobów, zadania planowe w zakresie produkcji poszcze­gólnych wyrobów, a często także ograniczone moce produkcyjne miejsc pracy. A zatem parametrami w tym modelu są:

a_ij – czas pracy i-tego miejsca przy wykonywaniu j-ego wyrobu,

C_j (j = l, 2,..., N) - założona wielkość produkcji j-ego wyrobu,

B_i (i=1,2,..., P) - dopuszczalny czas pracy i-ego miejsca.

Należy przydzielić produkcję wyrobów do poszczególnych miejsc pracy, tak aby np. zminimalizować czas (koszty produkcji) albo też zmaksymalizować efekty (łączną wielkość lub wartość produkcji). Jeżeli znane są jednostkowe czasy pracy, to przydział będzie polegał na określeniu x_ij - ilości j-ego wyrobu, jaką należy wytworzyć w i-tym miejscu. Należy zatem rozwiązać zadanie:

a₁₁ x₁₁ + a₁₂ x₁₂ + ... + a_1N x_1N ≤ B₁

…………………………………….

a_P1 x_P1 + a_P2 x_P2 + ... + a_PN x_PN ≤ B_P

(dopuszczalne czasy pracy poszczególnych miejsc nie mogą być przekroczone);

x₁₁ + x₂₁ + ... + x_P1 =

………………………………….

x_1N + x_2n + ... + x_PN =

(należy wykonać planowane ilości wyrobów);

x_{i j} ≥ 0 (i = 1,2,...,P; j = 1,2,...,N)

F(x_{i j} ) = c₁₁ x₁₁ + c₁₂ x₁₂ + ... + c_1N x_1N +

................................................

+ c_P1 x_P1 + c_P2 x_P2 + ... + c_PN x_PN = max

(minimalizacja łącznego czasu pracy wszystkich miejsc przy produkcji wszystkich wyrobów)

Przykład 5.

Do produkcji pięciu elementów (A, B, C, D i E) przedsiębior­stwo musi wydzierżawić trzy maszyny. Każdy podzespół może być produkowany na każdej maszynie, maszyny różnią się jednak nakładem czasu pracy niezbęd­nego dla wyprodukowania poszczególnych elementów, co ilustruje tablica

Maszyna	Zużycie czasu pracy maszyny na produkcję podzespołu (w min)
	A
I II III	75 80 48

Rozdzielić miesięczną produkcję elementów pomiędzy maszyny tak, aby wyprodukować co najmniej po 90 szt. elementów A, B i C oraz co najmniej po 75 szt. elementów D i E przy możliwie najniższych kosztach dzierżawy (pracy) maszyn. Wiadomo, że każdą z maszyn można wydzierżawić na co najwyżej 180 godz. (10 800 min) w ciągu miesiąca i że l godz. pracy maszyny I kosztuje 30 zł, l godz. pracy maszyny II - 42 zł i l godz. pracy maszyny III - 36 zł.

Rozwiązanie

Podobnie jak w przykładzie 4 należy tak rozdzielić produkcję pięciu elementów pomiędzy trzy maszyny, aby nie przekroczyć dopuszczalnych czasów pracy maszyn i wyprodukować planowane liczby elementów. Ponieważ podane parametry a_ij określają obecnie zużycie czasu pracy i-tej maszyny na jednostkę j-ego podzespołu, zatem zmienne decyzyjne x_{i j} określać będą ilość j-ego podzespołu (j=1,..., 5) wytwarzaną na i-tej maszynie (i= 1,2,3)

Warunki dotyczące limitów czasu pracy maszyn przybierają obecnie postać:

75x₁₁ + 60x₁₂ + 150x₁₃ + 30x₁₄ + 96x₁₅ ≤ 10800

80x₂₁ +100 x₂₂ + 120x₂₃ + 32x₂₄ + 100x₂₅ ≤ 10800

48x₃₁ + 50x₃₂ + 160x₃₃ + 40x₃₄ + 120x₃₅ ≤ 10800

a warunki dotyczące zadań produkcyjnych:

x₁₁ + x₂₁ + x₃₁ ≥ 90 dla elementu A

i dla pozostałych

x₁₂ + x₂₂ + x₃₂ ≥ 90

x₁₃ + x₂₃ + x₃₃ ≥ 90

x₁₄ + x₂₄ + x₃₄ ≥ 75

x₁₅ + x₂₅ + x₃₅ ≥ 75

Oczywiście x_{i j} ≥ 0 (i = 1,2,3; j = 1,2,...,5), a w funkcji celu należy zminimalizować koszty pracy maszyn, przy danych kosztach jednostkowych (1 godz.)

F(x_{i j} ) = 30(75x₁₁ + 60x₁₂ + 150x₁₃ + 30x₁₄ + 96x₁₅) +

+ 42(80x₂₁ + 100x₂₂ +120x₂₃ + 32x₂₄ +100x₂₅) +

+ 36(48x₃₁ + 50x₃₂ + 160x₃₃ + 40x₃₄ + 120x₃₅ ) min

Zad.1

W elektrociepłowni pracują trzy agregaty: A1,A2 i A3, które wykorzystują dwa rodzaje paliwa.

W tablicy poniżej podano uzysk energii cieplnej z 1 t paliwa.

Tablica

Agregaty	Uzysk energii w Gcal/t paliwa
	I
A1	5
A2	6
A3	6

Plan produkcyjny zakłada wytworzenie co najmniej 4200 Gcal, przy czym ze względów technicznych dokładnie połowa wytworzonej energii powinna pochodzić z agregatu pierwszego. Ponadto wiadomo, że każdego rodzaju paliwa nie można nabyć więcej niż 330 t, a ceny nabycia 1 t paliwa wynoszą odpowiednio 440 i 650 zł. Opracować optymalny plan zakupu paliwa oraz przydziału do poszczególnych agregatów, minimalizujący koszty zakupu paliwa.

Zad.2

Cztery zakłady produkcyjne wytwarzają ten sam wyrób. Zdolności produkcyjne poszczególnych zakładów wynoszą: a₁ = 800 jednostek, a₂ = 300 jednostek, a₃ = 500 jednostek, a₄ = 400 jednostek. Na wytwarzany wyrób zgłasza zapotrzebowanie trzech odbiorców. Zapotrzebowanie poszczególnych odbiorców wynosi odpowiednio: b₁ = 400 jednostek, b₂ = 700 jednostek, b₃ = 900 jednostek. Jednostkowe koszty wytworzenia wyrobu w poszczególnych zakładach wynoszą odpowiednio (tyś zł/jednostkę) : k₁ = 20, k₂ = 19, k₃ = 18, k₄ = 21. Dane dotyczące kosztów transportu (zł/jednostkę) zamieszczone są w tablicy:

Odbiorcy Dostawcy	O1	O2	O3
D1	800	300	200
D2	700	200	800
D3	400	100	700
D4	100	200	600

Określić plan produkcji i transportu, aby łączny koszt był minimalny.

Zad 3.

Wydział obróbki skrawaniem ma do dyspozycji trzy obrabiarki: Ol, O2 i O3, na których mogą być wykonywane cztery rodzaje elementów: El, E2, E3 i E4. Czas pracy obrabiarek przy produkcji poszczególnych elementów podano w tablicy:

	Czas potrzebny na wykonanie 1-go elementu
Obrabiarki	E1
O1	5
O2	10
O3	15
Plan, szt	300

Dopuszczalne czasy obrabiarek wynoszą odpowiednio, godz.: Ol - 42 , 02 - 180, 03 - 42. Zadania planowe w zakresie poszczególnych elementów wynoszą: El - 300 szt., E2 - 700 szt., E3 - 600 szt. Rozdzielić produkcję elementów pomiędzy obrabiarki tak, aby nie przekraczając limitów czasu pracy maszyn, zrealizować zadania planowe przyjmując za kryteriom minimalizację łącznego czasu pracy obrabiarek.

Zad.4.

Trzy rodzaje koparek mogą wykonywać cztery rodzaje prac ziemnych. W tablicy poniżej podano wydajności koparek przy wykonywaniu poszczególnych prac (m³/dzień), liczby koparek jakimi przedsiębiorstwo dysponuje w ciągu dnia, oraz minimalne zadania planowe w zakresie poszczególnych prac.

Tablica

Koparki Typ	Wydajność (w m^3/dzień) przy wykonywaniu wykopu	Dysponowane liczby koparek
	I	II
A	25	15
B	30	10
C	24	18
Minimalne dzienne zadania planowe, m^3	220	90

Dokonać przydziału koparek do wykonania poszczególnych prac ziemnych tak, aby dzienne koszty ich eksploatacji były możliwie najniższe. Wiadomo, że dzienne koszty eksploatacji 1 koparki typu A wynoszą 190 zł, 1 koparki typu B - 130 zł, 1 koparki typu C - 280 zł.

Zad.6

W trzech warsztatach można wytwarzać 5 elementów: A, B, C, D i E. W tabeli podano wydajność warsztatów przy produkcji poszczególnych elementów w ciągu jednej zmiany roboczej, minimalne liczby elementów które należy wyprodukować, oraz ceny uzyskiwane ze sprzedaży elementów.

Przydzielić produkcję elementów pomiędzy poszczególne warsztaty tak, aby zmaksymalizować miesięczną wartość produkcji, biorąc pod uwagę, że warsztaty pracują na trzy zmiany ( miesiąc - 23 dni robocze.)

Warsztaty	Wydajność ( w szt / zmianę) przy produkcji elementu
	A
I II III	20 22 19
Minimalne liczby elementów	800
Ceny elementów (w zł)	20

Zad.7

Spółka węglowa produkuje węgiel w trzech kopalniach i wysyła go do 4-ch odbiorców. Jednostkowe koszty produkcji węgła, zawartość popiołu i siarki, oraz zdolności produkcyjne kopalń przedstawiono w tablicy 1:

Tablica 1.

Kopalnia	Koszt wyd. zł/t	Zdolność prod., t	Popiół %	Siarka %
1	140	120	8	0.5
2	150	100	6	0.4
3	170	140	4	0.3

Zapotrzebowanie poszczególnych odbiorców, oraz jednostkowe koszty transportu (zł/t) zamieszczono w tablicy 2.:

Tablica 2.

Kopalnia	Odbiorca
	1
1	4
2	9
3	8
Zapotrz., t	80

Zawartość popiołu i siarki w dostarczanym do odbiorców węglu nie może przekraczać odpowiednio: 6 i 0.35 %. Opracować plan dostaw węgla do poszczególnych odbiorców mając na uwadze minimalizację kosztów.

3. Geometryczna interpretacja zadań optymalizacji liniowej.

Zadania programowania liniowego posiada naturalną interpretację geometryczną, którą można przedstawić w przestrzeni R² (na płaszczyźnie)., gdy w modelu optymalizacyjnym występują tylko dwie zmienne decyzyjne. Ilustracja graficzna umożliwia poglądową prezentację ogólnych własności zadań optymalizacji liniowej.

1. Geometryczna interpretacja zbioru rozwiązań dopuszczalnych w przestrzeni R².

Rozpatrzmy następujący przykład zadania optymalizacji liniowej w przestrzeni R²:

Przykład 1.

- funkcja celu:

f(x) = 480x₁ + 210x₂ → max (3.1)

- warunki ograniczające:

2x₁  +  1.2x₂ ≤ 6 (1) (3.2)

40x₁  +  60x₂ ≤ 240 (2) (3.3)

100x₁ + 200x₂ ≥ 400 (3) (3.4)

x₁                           ≥ 0 (4) (3.5)

x₂ ≥ 0 (5) (3.6)

Ponieważ zmienne x = [x₁ x₂] ϵ R² zadanie (3.1÷3.6) można przedstawić na płaszczyźnie w układzie współrzędnych Ox₁x₂. Z warunków nieujemności (3.5),(3.6) wynika, że zbiór rozwiązań dopuszczalnych znajduje się w tzw. „pierwszej ćwiartce” układu Ox₁x₂, czyli tam gdzie znajdują się punkty, których obie współrzędne są nieujemne.

Warunki nieelementarne (3.2÷3.4) są nierównościami liniowymi. Ilustracją graficzną zbioru rozwiązań każdej z nich jest półpłaszczyzna położona po odpowiedniej stronie swego brzegu. Opisem analitycznym brzegu jest zbiór rozwiązań równania otrzymanego z nierówności definiującej dany warunek. Aby ustalić po której stronie brzegu znajduje się obszar określony przez daną nierówność najprościej jest wybrać dowolny punkt poza brzegiem i sprawdzić, czy jego współrzędne spełniają tę nierówność. Wygodnym w tym przypadku jest punkt O(0,0) (początek układu współrzędnych). Na rys. 3.1 przedstawiono obszar spełniający nierówność (3.1), wraz z warunkami brzegowymi (3.5),(3.6), tzn. spełniający układ nierówności:

2x₁  +  1.2x₂ ≤ 6

x₁                           ≥ 0 (3.8)

x₂ ≥ 0

Obszar rozwiązań układu nierówności (3.2) znajduje się po tej stronie swego brzegu po której leży punkt O(0, 0), ponieważ jego współrzędne spełniają tę nierówność:

L_3.2(0,0) = 2 • 0 + 1.2 • 0 = 0 ≤ 6 = P_3.2(0, 0)

gdzie:

L_3.2(0,0),  P_3.2(0, 0) – wartość lewej i prawej strony nierówności (3.2).

W analogiczny sposób wyznaczamy położenie obszarów reprezentujących rozwiązania nierówności (3.3) i (3.4). Ostatecznie ilustracją zbioru D rozwiązań układu nierówności (3.2)÷(3.6) stanowi część wspólna obszarów ilustrujących rozwiązania poszczególnych nierówności tego układu. Ilustrację graficzną zbioru D przedstawiono na rys. 3.2.

Rys. 3.1.

Geometryczna interpretacja w przestrzeni R² obszaru reprezentującego układ

nierówności (3.8) (obszar zacieniony). Strzałki wskazują po której stronie

swego brzegu znajduje się obszar reprezentujący daną nierówność.

Rys. 3.2.

Geometryczna interpretacja w przestrzeni R² zbioru rozwiązań dopuszczalnych

zadania optymalizacji liniowej (3.1) ÷ (3.6).

Z rys. (3.2) wynika, że w interpretacji geometrycznej zbiór rozwiązań dopuszczalnych D

jest czworobokiem o wierzchołkach:

$A\left( 0,4 \right),\ \ B\left( 1,\ \frac{10}{3} \right),\ C\left( \frac{18}{7},\frac{5}{7} \right),\ D\left( 0,2 \right).$

Wymienione wierzchołki są punktami przecięcia się brzegów odpowiednich obszarów. Współrzędne wierzchołków muszą zatem spełniać układ równań brzegów, które wyznaczają dany wierzchołek. Zatem, współrzędne wierzchołka A(0, 4) są rozwiązaniem układu równań:

40x₁  +  60x₂ = 240

x₁                  = 0

, a współrzędne wierzchołka $B(1,\frac{10}{3})$ spełniają układ równań:

2x₁  +  1.2x₂ = 6

40x₁  +  60x₂ = 240

W analogiczny sposób wyznaczamy współrzędne wierzchołków C i D.

3.2. Geometryczna interpretacja funkcji celu w przestrzeni R².

Dla zilustrowania zmienności wartości funkcji celu w zbiorze rozwiązań dopuszczalnych D wykorzystujemy warstwice funkcji celu będące zbiorami punktów x ∈ R² dla których funkcja celu f przyjmuje stałą wartość k . Ogólne równanie warstwic wyrażające tę własność jest:\

f(x) = k

W przypadku funkcji liniowej 2-ch zmiennych (3.1) równanie warstwic przyjmuje postać:

480x₁ + 210x₂ = k (3.9)

Przy zmiennym  z ∈ R wyznacza ono rodzinę prostych równoległych względem siebie. Na Rys. 3.3 przedstawiono linią przerywaną wykresy warstwic (3.9) przechodzących przez punkty leżące na osi Ox₁ o współrzędnych (1,0), (2,0), (3,0), (4,0) dla których k = 480, 960, 1440 i 1920. Z Rys. 3.3 wynika, że maksymalna wartość funkcji celu (3.1) na zbiorze D odpowiada warstwicy przechodzącej przez wierzchołek C. Zatem rozwiązaniem optymalnym zadania optymalizacji liniowej (3.1) ÷ (3.6) jest punkt $\mathbf{x}^{\mathbf{C}} = \left( \frac{18}{7},\frac{5}{7} \right)$ w którym funkcja celu osiąga maksymalną wartość: $f\left( \mathbf{x}^{\mathbf{C}} \right) = 480 \bullet \frac{18}{7} + 210 \bullet \frac{5}{7} \approx 1384.3$

Rys. 3.3

Rodzina prostych równoległych będących warstwicami funkcji celu (3.1).

3.3. Geometryczna interpretacja zagadnienia optymalizacji liniowej w przestrzeni Rⁿ.

W przestrzeni Rⁿ ograniczenia o postaci standardowej przyjmują postać:

a_i1x₁ + a_i2x₂ +  …+a_inx_n ≤ b_i

,a w zapisie wektorowym:

a_i•x≤b_i, (3.9)

gdzie:

$\mathbf{a}_{\mathbf{i}} = \begin{bmatrix} a_{i1} & a_{i2}\text{\ \ \ \ }\begin{matrix} \ldots & a_{\text{in}} \\ \end{matrix} \\ \end{bmatrix}$ - i - ty wiersz macierzy ograniczeń.

Zbiór punktów $\mathbf{x} = (\begin{matrix} x_{1} & x_{2} \\ \end{matrix}\ \ \ldots\ \ x_{n})$^T ∈ Rⁿ spełniających nierówność (3.9) nazywany jest zamkniętą półprzestrzenią. Jeśli nierówność w (3.9) jest przeciwna, to zbiór punktów x ∈ Rⁿ spełniających warunek:

a_i•x≥b_i,

jest również zamkniętą półprzestrzenią.

W przestrzeni R² zamkniętą półprzestrzenią jest półpłaszczyzna oraz jej brzeg będące zbiorem rozwiązań odpowiedniej nierówności liniowej dwóch zmiennych, np. zamknięta półprzestrzeń w R² spełniająca nierówność (3.2)

2x₁  +  1.2x₂ ≤ 6

można zapisać następująco:

$\mathbf{H} = \left\{ \mathbf{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ \end{bmatrix} \in \mathbf{R}^{2}:\ \begin{bmatrix} 2 & 1.2 \\ \end{bmatrix} \bullet \begin{bmatrix} x_{1} \\ x_{2} \\ \end{bmatrix} \leq 6 \right\}$

Analogicznie jak w R² można przedstawić w sposób graficzny półprzestrzeń H w przestrzeni R³.

Przykład 2.

Warunek ograniczający z trzema zmiennymi:

4x₁ + 2x₂ + 5x₃ ≤ 20

definiuje półprzestrzeń zamkniętą:

$\mathbf{H} = \left\{ \text{\ \ }\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix} \in \mathbf{R}^{3}:\begin{bmatrix} 4 & 2 & 5 \\ \end{bmatrix} \bullet \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \end{bmatrix}\ \leq 20 \right\}$ (3.10)

Aby przedstawić w sposób graficzny półprzestrzeń zamkniętą (3.10) w przestrzeni R³ wyznaczamy płaszczyznę będącą brzegiem półprzestrzeni H:

4x₁ + 2x₂ + 5x₃ = 20 (3.11)

,a następnie przeprowadzamy test w celu ustalenia po której stronie brzegu leży półprzestrzeń H. W tym celu wyznaczamy proste będące przecięciami płaszczyzny (3.11) z odpowiednimi płaszczyznami utworzonymi prze osie układu współrzędnych: x₁Ox₂, x₁Ox₃,   x₂Ox₃. Podstawiając w (3.11) x₃ = 0, otrzymujemy prostą leżącą na płaszczyźnie x₁Ox₂:

4x₁ + 2x₂ = 20

Podobnie podstawiając x₂ = 0 otrzymujemy prostą na płaszczyźnie x₁Ox₃:

4x₁ + 5x₃ = 20

, oraz x₁ = 0, prostą na płaszczyźnie x₂Ox₃:

2x₂ + 5x₃ = 20

Na rys. 3.4 przedstawiono wyznaczone powyżej proste oraz położenie płaszczyzny (3.11) w układzie Ox₁x₂x₃. Początek układu współrzędnych O(0, 0, 0) nie leży na tej płaszczyźnie, zatem może być wykorzystany do testu na podstawie którego można ustalić, że należy on do zamkniętej półprzestrzeni (3.10).

Rys. 3.4

Zamknięta półprzestrzeń (3.10) w R³ odpowiadająca warunkowi ograniczającemu:

4x₁ + 2x₂ + 5x₃ ≤ 20.

Dla większej niż 3 liczbie zmiennych (n > 3), nie jest możliwe przedstawienie w sposób graficzny zamkniętej półprzestrzeni. Jednakże można wykorzystać model o mniejszej liczbie wymiarów dla wyobrażenia geometrii zamkniętej półprzestrzeni w Rⁿ.

Typowe ograniczenie zadań programowania liniowego o postaci kanonicznej w postaci równości:

a_i • x=b_i (3.12)

jest hiperpłaszczyzną w Rⁿ. Dla zamkniętej półprzestrzeni będącej zbiorem punktów spełniających warunek ograniczający nierównościowy (3.9) hiperpłaszczyzna (3.12) jest jej brzegiem.

Hiperpłaszczyzna określona przez (3.12) dzieli przestrzeń Rⁿ na dwie zamknięte półprzestrzenie:

H₁ = {x∈Rⁿ: a_i•x≤b_i }

oraz

H₂ = {x∈Rⁿ: a_i•x≥b_i }

Należy zauważyć, że przekrój H₁ ∩ H₂ = H jest hiperpłaszczyzną (3.12). Zbiorem rozwiązań dopuszczalnych w przestrzeni Rⁿ jest zbiór punktów, który spełnia wszystkie warunki ograniczające zadania optymalizacji. Wynika stąd, że zbiór rozwiązań dopuszczalnych jest częścią wspólną (przekrojem) wszystkich zamkniętych półprzestrzeni wyznaczonych przez poszczególne ograniczenia.

Przykład 3.

Rys. 3.5

Zbiór rozwiązań dopuszczalnych jako część wspólna zamkniętych półprzestrzeni w R³

odpowiadających poszczególnym warunkom ograniczającym.

1. Podstawowe właściwości zadań optymalizacji liniowej.

Spróbujmy teraz określić gdzie w zbiorze rozwiązań dopuszczalnych D można znaleźć punkt w którym funkcja celu przyjmuje wartość optymalną. Pokażemy najpierw, że jeśli x₁, x₂ ∈ Rⁿ są dwoma rozwiązaniami dopuszczalnymi, to dowolny punkt leżący na odcinku łączącym te dwa punkty jest również rozwiązaniem dopuszczalnym. Odcinek łączący punkty x₁, x₂ definiuje się następująco:

{x∈Rⁿ: x=(1−λ)x₁+λx₂,  0≤ λ≤1} (4.1)

Należy zauważyć, że punktom x₁ i  x₂  będącymi początkiem i końcem odcinka (4.1) odpowiadają parametry 𝜆 = 0 i 𝜆 = 1. Punktom wewnętrznym odcinka odpowiadają parametry 0  < λ < 1.

Załóżmy teraz, że x₁ i x₂ są rozwiązaniami dopuszczalnymi zagadnienia programowania liniowego. Oznacza to, że punkty te spełniają warunki ograniczające:

a_i • x₁ ≤ b_i

a_i • x₂ ≤ b_i

Dowolny punk leżący wewnątrz odcinku (4.1) spełnia również to ograniczenie :

a_i • ((1−λ)x₁+λx₂)= (1−λ)a_ix₁+λa_ix₂≤(1−λ)b_i + λb_i = b_i

Identyczne rozważania można przeprowadzić dla ograniczeń równościowych. Oznacza to, że dowolny punkt odcinka łączącego punkty x₁, x₂ należy do zbioru rozwiązań dopuszczalnych.

Załóżmy ponownie, że x₁, x₂ są rozwiązaniami dopuszczalnymi zagadnienia programowania liniowego w którym funkcja celu jest postaci: c • x . Jeśli punkty x₁, x₂ należą do warstwicy funkcji celu, tzn. funkcja celu przyjmuje tę samą wartość k w tych punktach, czyli :

cx₁ = cx₂ = k

to łatwo jest pokazać, że funkcja celu osiąga tę samą wartość w dowolnym punkcie odcinka (4.1):

c• ((1−λ)x₁+λx₂)= (1−λ)cx₁+ λcx₂ = (1−λ)k + λk = k

W przypadku gdy wartości funkcji celu w tych punktach są różne, tzn.:

c•x₁ < c•x₂

, to dla dowolnego punktu x leżącego wewnątrz odcinka (4.1) mamy:

c • x= c• ((1−λ)x₁+λx₂)= (1−λ)c•x₁+λc•x₂<(1−λ)cx₂+λc•x₂=c•x₂

Wynika stąd, że wartość funkcji celu w dowolnym punkcie leżącym wewnątrz odcinka jest mniejsza od wartości w jednym z punktów zewnętrznych. W taki sam sposób można pokazać, że wartość funkcji celu w dowolnym punkcie wewnętrznym odcinka jest większa od wartości funkcji celu w jednym z punktów zewnętrznych. Podsumowując możemy wywnioskować, że na odcinku łączącym dwa punkty będące rozwiązaniami dopuszczalnymi funkcja celu osiąga albo stałą wartość, albo przyjmuje wartość maksymalną na jednym końcu, a wartość minimalną na drugim. Ta własność sprawia, że odcinek łączący dwa punkty posiada duże znaczenie w teorii programowania liniowego. Wynika stąd poniższa definicja.

DEFINICJA 4.1

Zbiorem wypukłym S ⊂ Rⁿ nazywamy taki zbiór, w którym odcinek łączący dwa jego dowolne punkty należy również do zbioru S.

Korzystając z zapisu (4.1) zbioru punktów przestrzeni Rⁿ leżących na odcinku łączącym dwa punkty x₁, x₂ ∈ Rⁿ, definicję zbioru wypukłego możemy zapisać następująco:

Zbiór S nazywamy zbiorem wypukłym, jeżeli:

∀ x₁, x₂ ∈ S ∀ 0 ≤ λ ≤ 1   (1−λ)x₁ + λx₂ ∈ S (4.2)

Przykład 4.1

Na rys. 4.1 i 4.2 przedstawiono przykłady zbiorów wypukłych w przestrzeni R². Na rys. 4.1 przedstawiono przykłady zbiorów wypukłych ograniczonych, a na rys. 4.2 przedstawiono przykłady zbiorów nieograniczonych. Na rys. 4.3 przedstawiono przykłady zbiorów w przestrzeni R² które nie są wypukłe.

Rys. 4.1.

Przykłady zbiorów wypukłych ograniczonych w przestrzeni R².

Rys. 4.2

Przykłady zbiorów wypukłych nieograniczonych w przestrzeni R².

Rys. 4.3.

Przykłady zbiorów w przestrzeni R² które nie są wypukłe.

TWIERDZENIE 4.1 Zamknięta półprzestrzeń jest zbiorem wypukłym.

Dowód:

Niech  H₁ ∈ Rⁿ będzie zamkniętą półprzestrzenią określoną następująco:

H₁ = {x∈Rⁿ: a₁•x≤b₁ }

, oraz niech x₁, x₂ ∈ H₁.

Dla dowolny punktu: x = (1−λ)x₁ + λx₂,   (0 ≤  λ ≤ 1) mamy:

a₁•x=a₁•((1−λ)x₁+λx₂)=(1−λ)a₁x₁+λa₁x₂

Ponieważ  λ ≥ 0 , oraz 1 − λ ≥ 0, zatem mamy:

a₁•x≤(1−λ)b₁ + λb₁ = b₁

co oznacza, że x∈H₁

TWIERDZENIE 4.2 Przekrój (część wspólna) skończonej liczby zbiorów wypukłych jest zbiorem wypukłym.

Dowód:

Załóżmy, że S₁,  S₂,  …, S_n są zbiorami wypukłymi, tzn.:

∀ x₁, x₂ ∈ S_i ∀ 0 ≤ λ ≤ 1   (1−λ)x₁ + λx₂ ∈ S_i ,

oraz niech $S = \bigcap_{i = 1}^{n}S_{i}$

∀ x₁, x₂ ∈ S x₁, x₂ ∈ S_i  dla  i = 1, 2,  …,n

, zatem

∀ 0 ≤ λ ≤ 1   (1−λ)x₁ + λx₂ ∈ S_i dla i = 1, 2,  …,n

,a to oznacza, że (1−λ)x₁ + λx₂ ∈ S

WNIOSEK. 4.2.1 Hiperpłaszczyzna jest zbiorem wypukłym.

Dowód:

Hiperpłaszczyzna H jest zbiorem punktów przestrzeni Rⁿ, takich, że

H = {x∈Rⁿ: a_i•x=b_i }

i dzieli przestrzeń Rⁿ na dwie zamknięte półprzestrzenie:

H₁ = {x∈Rⁿ: a_i•x≤b_i },

H₂ = {x∈Rⁿ: a_i•x≥b_i }

Hiperpłaszczyzna H jest przekrojem półprzestrzeni H₁ i H₂, tzn.: H = H₁ ∩ H₂, a więc na podstawie twierdzenia 4.2 jest zbiorem wypukłym.

TWIRDZENIE 4.3 Zbiór rozwiązań dopuszczalnych D w zadaniach optymalizacji liniowej (programowania liniowego) jest zbiorem wypukłym.

Dowód:

Niech x₁,x₂ ∈ D będą dwoma rozwiązaniami dopuszczalnymi. Oznacza to, że spełniają warunki ograniczające:

Ax₁ = B Ax₂ = B

x₁ ≥ 0 x₂ ≥ 0

Wykażemy, że

∀ 0 ≤  λ ≤1 punk x = λx₁ + (1 − λ)x₂ ∈ D (jest zbiorem dopuszczalnym):

Ax= A • (λx₁+(1−λ)x₂)=λ Ax₁+(1-λ)Ax₂=λB+(1−λ)B = B,

oraz ponieważ x₁,   x₂ ≥ 0, x ≥ 0.

Spośród zbiorów wypukłych można wyodrębnić tzw. wielościenne zbiory wypukłe będące zbiorem punktów , które spełniają wszystkie warunki ograniczające zadania programowania liniowego. Każdemu warunkowi ograniczającemu w postaci nierówności odpowiada zamknięta półprzestrzeń, a warunkowi ograniczającemu równościowemu odpowiada hiperpłaszczyzna będąca przekrojem zamkniętych półprzestrzeni. Wielościenne zbiory wypukłe są zatem częścią wspólną (przekrojem) zamkniętych półprzestrzeni związanymi z danymi warunkami ograniczającymi. Z twierdzeń 4.1 ÷ 4.3 wynika, że jeśli zbiór rozwiązań dopuszczalnych zadania programowania liniowego nie pusty, to jako część wspólna skończonej liczby zamkniętych półprzestrzeni jest zbiorem wypukłym.

DEFINICJA 4.2. Punkt x ∈ Rⁿ nazywamy wypukłą kombinacją punktów x₁, x₂, … ,x_n 

przestrzeni Rⁿ jeśli istnieją pewne liczby c₁,  c₂,  … ,  c_r dla których:

$\sum_{i = 1}^{r}{c_{i} = 1\ \ \ ,oraz\ \ c_{i} \geq 0\ \ \text{dla}\text{\ \ }}$ 1 ≤ i ≤ r

takie, że

$\mathbf{x} = \sum_{i = 1}^{r}{c_{i}\mathbf{x}_{\mathbf{i}}}$

Twierdzenie 4.4. Zbiór wszystkich wypukłych kombinacji skończonej liczby punktów w przestrzeni Rⁿ jest zbiorem wypukłym.

Dowód:

Ćwiczenie …

DEFINICJA 4.3. Punkt u w zbiorze wypukłym S nazywamy punktem wierzchołkowym zbioru S jeśli nie jest on punktem wewnętrznym dowolnego odcinka zawartego w S. Zatem punkt u jest punktem wierzchołkowym, jeśli nie istnieją dwa różne punkty x₁, x₂ ∈ S takie, że

u = λx₁ + (1 − λ)x₂ dla 0 < λ < 1

Przykład 4.2

Rys.4.4

Punktami wierzchołkowymi zbioru ABCDE w przestrzeni R² są punkty A,B,C,D,E.

TWIERDZENIE 4.4

Niech S będzie wypukłym zbiorem w przestrzeni Rⁿ to punk u∈S jest punktem wierzchołkowym wtedy i tylko wtedy, gdy nie jest wypukłą kombinacją innych punktów ze zbioru S.

Dowód:

Ćwiczenie

Własności zadań optymalizacji liniowej:

WŁASNOŚĆ 1. W zadaniach optymalizacji liniowej zbiór D rozwiązań dopuszczalnych jest zawsze wielościennym zbiorem wypukłym o skończonej liczbie wierzchołków.

WŁASNOŚĆ 2. Jeżeli zadanie optymalizacji liniowej posiada rozwiązanie optymalne, to musi je reprezentować co najmniej jeden z wierzchołków zbioru D.

WŁASNOŚĆ 3. Jeżeli x^A i x^B są rozwiązaniami optymalnymi zadania programowania liniowego, to rozwiązaniem optymalnym jest każdy wektor:

x^w = (1−λ)x^A+λx^B dla 0 ≤ λ ≤ 1

WŁASNOŚĆ 4. Pomno

5.. Szczególne przypadki zadań optymalizacji liniowej.

Przedstawiony w pkt. 3.1 przykład (Przykład 1) dotyczył zadania optymalizacji liniowej w którym rozwiązaniem optymalnym był jeden punkt. W wielu zadaniach optymalizacji możemy się spotkać z przypadkami w których istnieje więcej niż jedno rozwiązanie optymalne, a także zadania, które nie posiadają rozwiązania. Odwołując się do interpretacji geometrycznej zadań optymalizacji liniowej w przestrzeni R² przedstawione zostaną przykłady tego typu zadań.

5.1. Zadania optymalizacji liniowej z nieskończoną liczbą rozwiązań optymalnych.

Przykład A1.

f(x) = −1.5x₁ + 2x₂ → min

przy warunkach:

5x₁ + 4x₂ ≥ 20 (1)

-3x₁ + 4x₂ ≥ 4 (2)

x₁              ≤ 3  (3)

x₁                  ≥ 0 (4)

x₂ ≥ 0 (5)

Interpretacja geometryczna zadania optymalizacji z przykładu A1 przedstawiona jest na rys. 5.1. Z rys.5.1 wynika, że zbiór rozwiązań dopuszczalnych jest nieograniczonym czworobokiem o wierzchołkach:

A(5,0),  B(2, 2.5),  C(3, 3.25).

Warstwicami funkcji celu jest rodzina prostych o równaniach: −1.5x₁ + 2x₂ = k.

Warstwice są równoległe do prostej −3x₁ + 4x₂ = 4 na której znajduje się bok BC zbioru rozwiązań dopuszczalnych D i która pokrywa się z warstwicą odpowiadającą najmniejszej wartości funkcji celu na zbiorze D. Każdy zatem punkt odcinka BC jest rozwiązaniem optymalnym tego zadania. Zbiór rozwiązań optymalnych można zapisać za pomocą średnich ważonych punktów x^B = (2, 2.5),   x^C = (3, 3.25) następująco:

D^opt. = {x⁰∈D: x⁰=(1−w)x^B+wx^C dla 0≤w≤1 }=

      = {x⁰∈D: x⁰=(1−w)(2, 2.5)+w(3, 3.25)) dla 0≤w≤1 }

Każdy wektor x⁰ ∈ D^opt. wyznacza optymalną wartość funkcji celu, która wynosi:

f(x⁰) = 2 = f^min

Rys. 5.1

Interpretacja graficzna zadania z przykładu A1.

Przykład A2.

f(x) = −1.5x₁ + 2x₂ → min

przy warunkach:

5x₁ + 4x₂ ≥ 20 (1)

-3x₁ + 4x₂ ≥ 4 (2)

x₁                  ≥ 0 (3)

x₂ ≥ 0 (4)

Ilustracja graficzna zbioru rozwiązań dopuszczalnych w R² przedstawiono na rys. 5.2.

Usunięcie ograniczenia x₁ ≤ 3 powiększyło zbiór rozwiązań dopuszczalnych. Od dołu zbiór rozwiązań D ograniczony jest półprostą o początku w wierzchołku B i przechodzącą przez punkt C. W zadaniu mamy nieskończony i nieograniczony zbiór rozwiązań optymalnych, a ich geometryczną reprezentacją jest półprosta wyznaczona przez punkty B i C. Półprosta ta pokrywa się z warstwicą funkcji celu o najmniejszej wartości f^min = 2.

Zbiór rozwiązań optymalnych dla tego zadania można zapisać następująco:

$D^{\text{opt.}} = \left\{ \mathbf{x}^{0} \in D:\ \mathbf{x}^{0} = \mathbf{x}^{B} + w \bullet \overrightarrow{\mathbf{\text{BC}}}\ \ dla\ \ w \geq 0\ \right\}$ =

= {x⁰∈D: x⁰=(2,2.5)+w•(3−2,  3.25−2.5) dla w≥0}

Rys. 5.2

Interpretacja graficzna zadania z przykładu A2 o nieskończonym i nieograniczonym zbiorze

rozwiązań D^opt.

5.2. Zadania optymalizacji liniowej bez rozwiązań optymalnych.

Jeśli zadanie optymalizacji liniowej nie posiada rozwiązania optymalnego, to zachodzi jeden z dwóch przypadków:

- występuje niesprzeczny, ale i nieograniczony zbiór rozwiązań optymalnych D, co powoduje, że „optymalna” wartość funkcji celu na tym zbiorze jest nieograniczona, tzn. przy kryterium maksymalizacji funkcja celu f wzrasta nieograniczenie (f^max = +∞), a przy kryterium minimalizacji funkcja f maleje nieograniczenie (f^min = −∞).

- występuje sprzeczny układ warunków ograniczających zadania, co oznacza, że zbiór rozwiązań dopuszczalnych D jest pusty (D = ⌀).

Poniżej przedstawiono dwa przykłady zadań, które nie posiadają rozwiązań optymalnych.

Przykład B1

f(x) = −1.5x₁ + 2x₂ → max

przy warunkach:

5x₁ + 4x₂ ≥ 20 (1)

-3x₁ + 4x₂ ≥ 4 (2)

x₁              ≤ 3  (3)

x₁                  ≥ 0 (4)

x₂ ≥ 0 (5)

Rys. 5.3.

Geometryczna interpretacja zadania B1, które nie posiada rozwiązania optymalnego,

ponieważ zbiór D^B1 jest nieograniczony, a maksymalna wartość funkcji celu f^max → +∞.

Przykład B2

f(x) = −1.5x₁ + 2x₂ → max

przy warunkach:

5x₁ + 4x₂ ≤ 20 (1)

-3x₁ + 4x₂ ≥ 4 (2)

x₁              ≥ 3  (3)

x₁                  ≥ 0 (4)

x₂ ≥ 0 (5)

Rys. 5.4

Geometryczna interpretacja zadania B2, które nie posiada rozwiązania optymalnego,

ponieważ zbiór rozwiązań dopuszczalnych jest pusty (D^B2 = ⌀ ).

Literatura:

1. Bielecki J., Kozubski J., Krzysztofiak M. Kulawczuk T.: Ekonometria, praca zbiorowa pod redakcją naukową Mirosława Krzysztofiaka, PWE, Warszawa, 1978.

2. Borucki W. Ignasiak E, Marcinkowski J.,Sikora W.: Badania operacyjne, praca zbiorowa pod redakcją E. Ignasiaka. PWE. Warszawa 2001,

3. Praca zbiorowa pod redakcją Tomasza Szapiro: Decyzje menadżerskie z Exelem, PWE, Warszzawa 2000

4. Stark R., Nicholls R.L.: Matematyczne podstawy projektowania inżynierskiego, W-wa,

1979,

5. Sadowski W.: Teoria podejmowania decyzji. Wstęp do badań operacyjnych, PWE, Warszawa, 1976,

6. Himmelblau D.M.: Applied nonlinear programming, Mc Graw-Hill Book Company, 1972

7. Karlin S.: Mathematic Methods and theory in games. Programming, and theory, Stanford

University, Pergamon Press, London-Paris, 1959

8. Matlab – Optimization Toolbox

2. Zbigniew Jędrzejczyk, Jerzy Skrzypek, Karol Kukuła, Anna Walkosz.: Badania operacyjne w przykładach i zadaniach, PWN, W-wa 1999 (są nowsze wydania),

3.Edmund Ignasiak: Badania operacyjne, PWE, Warszawa 2001

Dodatek

PODSTAWOWE POJĘCIE I DEFINICJE

PRZESTRZEŃ WEKTOROWA– przestrzeń wektorowa Z jest zbiorem elementów zwanych wektorami przy czym w zbiorze tym określone są dwie operacje:

• dodawanie dla

• mnożenie wektora przez skalar, które dla dowolnych i

Operacje dodawania i mnożenia przez skalar w przestrzeni Z posiadają następujące własności:

• (prawo przemienności dodawania)

• (prawo łączności dodawania)

W przestrzeni Z istnieje wektor zerowy, taki że

Dla każdego

Przykład 1:

Przykładem przestrzeni wektorowej jest zbiór liczb rzeczywistych. W przestrzeni tej dodawanie jest zwykłym arytmetycznym dodawaniem i mnożeniem przez skalary rzeczywiste definiowane jako zwykłe mnożenie arytmetyczne liczb, wektor zerowy jest rzeczywistą liczbą 0.

Przykład 2:

Przykładem przestrzeni wektorowej może być n– wymiarowa rzeczywista przestrzeń.

Wektory tej przestrzeni składają się z n– składowych postaci liczb rzeczywistych. Wektor taki ma postać:

gdzie: x_k– k–ta wektora x

wektor zerowy jest definiowany następująco:

oznaczając: i

definiujemy dodawanie następująco:

mnożenie wektora przez skalar określa się jako wektor 0 składanych iloczynowi sklara:

dla tak określonych działań w przyjętym zbiorze Rⁿ spełniona jest definicja przestrzeni wektorowej.

WIELOPŁASZCZYZNA– n– wymiarowej, zbiór wszystkich punktów x=[x₁, x₂, ...x_n] w przestrzeni Rⁿ spełniających równanie liniowe:

przy czym:

nazywa się wielopłaszczyzną.

Przykład 1

W przestrzeni dwuwymiarowej R₂ równań wielopłaszczyny przyjmuje postać:

jest to znane równanie prostej:

gdzie:

Taka postać równania pozwala na łatwe wyznaczenie prostej w układzie współrzędnym prostokątnym.

Odległość prostej od początku układu współrzędnych wyraża się wzorem:

Przykład 2

Równanie hiperpłaszczyzny w przestrzeni R₃ przedstawia płaszczyznę o równaniu

Analogicznie otrzymuje się równania odcinkowe płaszczyzny otrzymuje się przez podzielenie obu równań przez b

odległość płaszczyzny od początku układu współrzędnych:

Każda płaszczyzna dzieli przestrzeń na dwie współprzestrzenie.

Definicja w formie liniowej:

Funkcją liniową n zmiennych w postaci:

nazywa się formą liniową gdzie: stałe XXX

Dla (x₁, x₂, ...x_n) leżących na hiperpłaszczyźnie forma liniowa przyjmuje wartość b.

Zwiększając wartość b hiperpłaszczyzna oddala się od początku układu współrzędnych w kierunku wektora

Definicja dodatniej kombinacji liniowej wektora:

Dodatnią kombinację liniową n wektorów nazywa się wektor x taki, że:

gdzie:

Zbiór wszystkich kombinacji liniowych nazywa się stożkiem.

Przykład:

Niech:

i

gdzie: a₁, a₂>0

Definicja wypukłej kombinacji liniowej n wektorów:

Dodatnią kombinacją wypukłą nazywamy A₁, A₂, ...A_n nazywa się wektor x taki:

gdzie:

Przykład:

Dla dwóch punktów na płaszczyźnie wypukła kombinacja liniowa przedstawia odcinek łączący te punkty

Gdzie: i

PODSTAWOWE POJĘCIA PRZESTRZENI „n” WYMIAROWEJ n– LINIOWEJ

Wektorowa przestrzeń n– wymiarowa Rⁿ to zbiór wektorów, dla których podane zostały podane pojęcia sumy i iloczynu przez liczby

)

niech x₁, x₂, ...x_n będą wektorami w przestrzeni Rⁿ oraz niech λ₁, λ₂,... λ_n skalarami (liczby rzeczywistej), wówczas wektor:

i taki wektor nazywamy kombinacją liniową wektorów x₁, x₂, ...x_n.

Jeżeli x, y są kombinacjami liniowymi , takimi, że:

wówczas:

oraz

jest również kombinacją liniową wektorów x₁, x₂, ...,x_n.

DŁUGOŚĆ WEKTORA W PRZESTRZENI Rⁿ

Jeżeli to długość wektora X określamy następująco:

ILOCZYN SKALARNY WEKTORA

Jeżeli to iloczyn skalarny tych wektorów określamy następująco:

Przy pomocy iloczynu skalarnego możemy określić kąt między wektorami x, y z zależności:

Jeżeli dla niezależnych wektorów iloczyn skalarny x·y=0 to mówimy, ze wektory x, y są prostopadłe.

Prostopadłościanem P w przestrzeni Rⁿ nazywamy zbiór:

gdzie: a,b– dane wektory w Rⁿ

Kulą K o środku x_o i promieniu r w przestrzeni Rⁿ nazywam zbiór punktów:

NIEZALEŻNOŚĆ LINIOWA WEKTORÓW

Zbiór wektorów dla nazywamy liniowo zależnymi, gdy chociaż jeden z nich jest liniową kombinacją pozostałych wektorów tego zbioru w szczególności na płaszczyźnie. Są liniowo zależne ponieważ jeden z nich można wyrazić jako kombinację liniową pozostałym; jeśli żaden z wektorów nie jest kombinacją liniową wektorów pozostałych to wtedy wektory te są liniowo niezależne.

Warunkiem koniecznym i wystarczającym niezależności wektorów jest aby spełniana była zależność:

na odwrót zbiór wektorów jest zależny liniowo gdy istnieją takie liczby nie wszystkie równe zero, dla których zachodzi zależność:

Przykładem wektorów liniowo niezależnych są wektory skierowane wzdłuż osi układu współrzędnych o posiadające długość. Nazywamy je wektorami jednostkowymi lub wersalami i są wektorami niezależnymi.

W przestrzeni r– wymiarowej wektory jednostkowe o kierunkach osi układy przedstawiamy następująco:

...

twierdzenie 1

Jeśli wektory stanowią kombinacje liniowe wektorów to wtedy są liniowo zależne.

dla k=1 twierdzenie jest oczywiste

k>1 dowód przez indukcję

twierdzenie 2

Każdy układ (n+1) wektorów w n– wymiarowej przestrzeni stanowi układ liniowo zależny; jeśli wektor y stanowi kombinację liniową wektorów to mówimy często, że wektory wyraża się liniowo przez układ

definicja

Układ wektorów wyraża się liniowo przez układ jeśli każdy wektor y_i dla i=1,2,...n stanowi kombinację liniową układu .

Dwa układy wektorów nazywa się równoważnymi jeżeli każdy z nich wyraża się liniowo przez drugi.

twierdzenie 3

Jeżeli w n– wymiarowej przestrzeni wektorowej dane są dwa układy wektorów

z których każdy jest liniowo niezależny i wyraża się przez drugi, to liczba wektorów nie jest większa niż w 2, tj. z twierdzenia wynika wniosek: każde dwa równoważne układy wektorów niezależnych zawierają jednostkową liczbę wektorów.

BAZA PRZESTRZENI WEKTOROWEJ

W trójwymiarowej przestrzeni dowolne 3 wektory nie leżące w jednej płaszczyźnie (liniowo niezależne) tworzą bazę tej przestrzeni. Oznacza to, ze każdy dowolny wektor przestrzeni może być rozłożony na składowe wg wektorów tzn. wyrażony w postaci ich kombinacji liniowej.

W trójwymiarowej przestrzeni istnieje wiele 3 niezależnych wektorów, lecz każde 4 są liniowo zależne w przestrzeni n– wymiarowej.

Układ wektorów jednostkowych:

jest układem wektorów n– niezależnych, przy czym dowolny wektor przestrzeni:

stanowi kombinację liniowa a mianowicie:

Każdy układ wektorów o liczbie większej od n jest w przestrzeni n– wymiarowej układem wektorów n– niezależnych.

Uogólniając bazę przestrzeni nazywamy taki zbiór liniowo niezależnych wektorów tej przestrzeni, że dowolny wektor stanowi kombinację liniową tego zbioru.

definicja:

zbiorem wypukłym nazywamy jeśli do dowolnych punktów tej przestrzeni wektorów wynika, że wszystkie punkty postaci: , gdzie należy do W.

Zbiorem wypukłym nazywamy zbiór, którego każdy odcinek łączący dwa punkty całkowicie zawiera się w nim.

Przykłady: punkty, figury jednowymiarowe, figury płaskie (koło, elipsa), figury trójwymiarowe( kula, czworościan)

definicja:

punktem brzegowym nazywa się punkt zbioru jeśli każda kula w środku w tym punkcie zawiera punkty należące do zbioru i nienależące.

Zbiór punktów brzegowych nazywamy brzegiem jeżeli powierzchnia zbioru wypukłego jest utworzona z ..................... płaskich to taki zbiór nazywamy wielościanem wypukłym.

definicja wierzchołka zbioru wypukłego:

punktem wierzchołkowym nazywa się punkt tego zbioru nie będący punktem wewnętrznym odcinka łączącego 2 punkty tego zbioru.

Zbiór wypukły może nieć ograniczoną lub nieograniczona liczbę punktów wierzchołkowych.

Część wspólna zbiorów wypukłych jest zbiorem wypukłym.

Zad.1.2

Ograniczenia:

Punkt startowy:

,