Programowanie liniowe –

przykłady zastosowań

Programowanie liniowe – przykłady zastosowań

WYBÓR PROCESU PRODUKCYJNEGO / MINIMALIZACJA ODPADÓW

W pewnym procesie produkcyjnym należy wytworzyć co najmniej 20 tys. sztuk
elementów A i 55 tys. sztuk elementów B z tworzywa sztucznego. Można wykonywać
je na dwóch rodzajach wtryskarek W1 i W2. W zależności od zastosowanej formy, w
jednym cyklu W1 wytwarzane mogą być 3 elementy A i 4 elementy B lub 2 elementy A
i 5 elementów B. W pojedynczym cyklu W2 można wytworzyć 7 elementów A i 10
elementów B. Czas trwania jednego cyklu wtryskarki wynosi 5 minut dla W1 i 7 minut
dla W2. Jaki powinien być plan produkcyjny minimalizujący czas wykonania
wymaganej liczby elementów?

Jak zmieniłby się model zadania, gdyby wiadomo było, że dostępne są 3 wtryskarki
typu W1 i 2 wtryskarki typu W2?

Programowanie liniowe – przykłady zastosowań

WYBÓR PROCESU PRODUKCYJNEGO / MINIMALIZACJA ODPADÓW

W pewnym procesie produkcyjnym należy wytworzyć co najmniej 300 sztuk ram
kabiny ciągnika rolniczego. Rama pojedynczej kabiny składa się z 7 kształtowników
o długości 0,7 m oraz 4 kształtowników o długości 2,5. Elementy wycinane są
z kształtowników o długości 5,2 m, kupowanych u dostawcy. Jak należy uzyskać
wymaganą liczbę elementów, aby odpad powstały w procesie cięcia była jak
najmniejszy? Ile wyniesie wielkość odpadu przy optymalnym cięciu?

Programowanie liniowe – przykłady zastosowań

PROBLEM MIESZANEK

Do wytopu żeliwa używa się trzech surówek: S1, S2, S3. Surówki te różną się od siebie
składem chemicznym i ceną zakupu, co przedstawia tabela. Wiadomo, że żeliwo
zjednorazowego wytopu w żeliwiaku musi zawierać co najmniej 10,2 kg Si, co najmniej
2,4 kg Mn oraz 2,7 – 4 kg P. Należy też przy wytopie zachować proporcje: na jeden kg
surówki S1 – dwa kilogramy surówki S3. Określić optymalny skład wsadu do
jednorazowego wytopu w żeliwiaku, minimalizujący łączne koszty wytopu żeliwa.

Surówka

Procentowe zawartości pierwiastków

Cena za 1 kg

Si

Mn

P

S1

2,6

0,4

0,6

5 zł

S2

2,1

0,9

0,2

3 zł

S3

2,1

0,6

0,6

4 zł

Programowanie liniowe – przykłady zastosowań

PROBLEM MIESZANEK

Pewna rafineria jest w stanie przetworzyć 1.500.000 baryłek ropy naftowej
dziennie. Końcowe produkty z rafinerii to trzy rodzaje benzyny bezołowiowej o
różnych liczbie oktanowej (ON): regularna (ON = 87), premium (ON = 89) i super
(ON = 92). Proces rektyfikacji obejmuje trzy etapy:
1. wieża destylacyjna, która produkuje surowiec (ON = 82) w ilości 0,2 baryłek
uzyskanych z jednej baryłki ropy naftowej,
2. urządzenie realizujące proces krakingu, które wytwarza zapas benzyny (ON = 98)
wykorzystując część surowca pochodzącego z wieży destylacyjnej uzyskując 0,5
baryłek benzyny z jednej baryłki surowca,
3. urządzenie mieszające, które komponuje produkt z surowców otrzymanych w
poprzednich etapach: surowca z wieży dest. i benzyny z urządzenia do krakingu.
Firma oszacowała zysk za baryłkę benzyny odpowiednio na: 6,70; 7,20 i 8,10 $.
Pojemność wejściowa jednostki do realizacji procesu krakingu wynosi 200.000
baryłek surowca dziennie. Ograniczenia sprzedaży na benzynę regularną, premium
i super to 50.000, 30.000 i 40.000 baryłek dziennie. Opracować model pozwalający
uzyskać optymalny harmonogram produkcji dla rafinerii.

Programowanie liniowe – przykłady zastosowań

PLANOWANIE PRODUKCJI

W pewnym procesie wytwórczym wykorzystuje się trzy urządzenia, realizujące kolejne etapy
procesu dwóch elementów, zamówionych przez producenta samochodów. Jednostkowe czasy
operacji oraz zyski i koszty przedstawiono w tabeli.
Już w tej chwili wiadomo, że wymagana liczba elementów nie może być wykonana ze względu
na brak czasu. Jaki należy przyjąć plan produkcji maksymalizujący zyski przedsiębiorstwa?

Element

Czas realizacji operacji na urządzeniach I, II, III

[min]

Liczba

zamówionych

elementów

I

II

III

A

7

2

5

36

B

3

6

6

50

Limit czasu pracy

maszyn [min]

90

56

240

-

Element

Jednostkowa kara finansowa

[$/szt.]

Zysk jednostkowy [$/szt.]

A

6

5

B

3

4

Programowanie liniowe – przykłady zastosowań

OPTYMALNY PRZYDZIAŁ ZADAŃ I ŚRODKÓW

Na trzech maszynach można wykonywać 2 detale (każde urządzenie może wykonywać
każdy detal). Czas potrzebny na wykonanie detalu na maszynie oraz koszty wykonania
przedstawiono w tabeli.

Jak rozdysponować produkcję między urządzenia, aby wykonać wymaganą liczbę detali
i ponieść minimalne koszty?

Detal

Czas wykonania detalu na maszynach I, II, III Liczba detali do

wykonania

I

II

III

A

7

2

5

36

B

3

6

6

50

Limit czasu pracy

maszyn

90

56

240

-

Detal

Koszt jednostkowy wykonania detalu na maszynie

A

6

2

5

-

B

3

4

1

-

OPTYMALNY PRZYDZIAŁ ZADAŃ I ŚRODKÓW

Przedsiębiorstwo

planuje zatrudnić 3 osoby do wykonywania trzech zadań. Zgłosiły

się 4 chętne osoby, które po przeszkoleniu zostały sprawdzone i okazało się, że czas
potrzebny na wykonanie każdej czynności poszczególnym osobom zabiera:
Których pracowników powinna zatrudnić firma do których zadań, by czas
przeznaczany na ich realizację był jak najmniejszy?

Programowanie liniowe – przykłady zastosowań

Zadanie

Czas wykonania przez pracownika

[min]

A

B

C

D

Montaż fotela samochodowego

20

17

14

10

Montaż reflektora

50

45

51

40

Montaż silnika

52

50

60

55

Programowanie liniowe – przykłady zastosowań

OPTYMALNY PRZYDZIAŁ ZADAŃ I ŚRODKÓW

Firma transportowa posiadająca samochody odpowiednio o ładowności 15t (1 sztuka), 10t (1 sztuka)
i 5t (3 sztuki) musi zaplanować przeglądy profilaktyczne na najbliższe 4 dni. W ciągu tego okresu
każdy samochód musi być wyłączony z pracy na co najmniej 1 dzień. Jak zaplanować plan
przeglądów, aby każdy samochód mógł być poddany wymaganej obsłudze technicznej, a
jednocześnie aby zaspokoić wymagane zobowiązania przewozowe firmy, przedstawione poniżej:

Dzień Wymagana ładowność aut

1

30

2

35

3

30

4

25

Programowanie liniowe – przykłady zastosowań

PRZYKŁAD BUDOWY AUTOSTRADY

Załóżmy, że autostrada ma być zbudowana na nierównym terenie. Przyjmujemy, że
koszt budowy jest proporcjonalny do ilości podłoża dodawanego lub usuwanego.
Niech T oznacza długość drogi i niech c(t) oznacza wyjściową wysokość terenu dla
każdego t



[0,T]. Problem polega na określeniu docelowej wysokości drogi y(t) dla

każdego t



[0,T].

W celu uniknięcia nadmiernych spadków na drodze, maksymalne nachylenie nie może
przekraczać wielkości b1, tj. |y’(t)|



b1.

Ponadto, dla uniknięcia garbów na jezdni, należy ograniczyć szybkość zmian nachylenia
drogi, tj. |y’’(t)|



b2.

Oprócz tego muszą zachodzić warunki początkowe y(0) = a, y(T) = b.
Sformułować zadanie optymalizacyjne jako zadanie programowania liniowego.

Programowanie liniowe – przykłady zastosowań

Trzy nieodkształcalne belki o ciężarach G

1

,G

2

,G

3

podwieszono za pomocą prętów

i obciążono siłami P

1

,P

2

,P

3

(rysunek). Pręty podwieszające na każdym poziomie mają

takie same przekroje poprzeczne, równe odpowiednio x

1

,x

2

,x

3

, oraz odpowiednie

wytrzymałości k

1

,k

2

,k

3

. Należy wyznaczyć przekroje prętów na poszczególnych

poziomach, minimalizujące łączną ich masę, nie przekraczając ich wytrzymałości.
Przekroje poziomów 1 i 3 nie powinny różnić się o więcej niż 25% od przekroju
poziomu 2. Ciężary prętów są dużo mniejsze od ciężarów G

i

oraz sił P

i

.

Teoria i praktyka rozwiązywania zadań
optymalizacji :z przykładami zastosowań
technicznych /Jacek Stadnicki. Warszawa
: Wydawnictwa Naukowo-
Techniczne, 2006

Mamy wirnik, dla którego wyważarka dynamiczna określiła masy korekcyjne M

I

i M

II

,

które mają być umieszczone na płaszczyźnie I-I, II-II, promieniu R i kątach

a

1

,

a

2

.

Jednak konstrukcyjnie przewidziano inne miejsca na dołożenie mas korekcyjnych – na
płaszczyźnie 1-1, 2-2 (w odległości l/2) i na promieniu r. Należy zatem zastąpić masy
wyznaczone przez wyważarkę systemem mas m

i

j

, tak aby ich suma była minimalna

przy zachowaniu właściwości mas M

I

i M

II

:

•

aby oś wirnika przechodziła przez środek jego masy,

•

aby momenty dewiacyjne zerowały się (nie występowały reakcje dynamiczne w
łożyskach)

Programowanie liniowe – przykłady zastosowań

•

Aby oś wirnika przechodziła przez środek jego masy:

•

aby momenty dewiacyjne zerowały się (nie występowały reakcje dynamiczne w
łożyskach):

Programowanie liniowe – przykłady zastosowań

Programowanie liniowe – przykłady zastosowań

• Prostopadłościenny element o długościach boków: a = 1m, b = 1,5m może być wykonany z

jednego lub dwóch materiałów o gęstościach odpowiednio:

r

1

and

r

2

[kg/m

3

]. W przypadku

wytworzenia elementu z dwóch materiałów, należałoby połączyć je jak na rysunku.

• Jaka powinna być wysokość h projektowanego elementu (jak i poszczególnych jego części

składowych h

1

i h

2

), aby uzyskać najlepszy stosunek wytrzymałości na rozciąganie elementu

przypadającą na jednostkę masy, spełniając wymagania:

• całkowita masa elementu nie powinna przekraczać wartości M,
• wytrzymałość elementu na rozciąganie nie może być niższa niż S.

• Zwiększenie wysokości części wykonanej z materiału o gęstości

r

1

o 1 cm powoduje liniowy

wzrost wytrzymałości elementu o wartość a

1

, zaś każdy dodatkowy 1 cm części wykonanej z

materiału o gęstości

r

2

daje przyrost wytrzymałości o a

2

.