Metoda Simpleks - Matlab


Do rozwiązywania problemów programowania liniowego służy wbudowana funkcja Matlaba linprog.

Ogólna forma funkcji:

[x,fval,exiflag,output,lambda] = linprog(f, A, b, Aeq, beq, lb, ub, x0, options)

Argumenty wejściowe:

f wektor kolumnowy stałych współczynników funkcji celu
A macierz ograniczeń liniowych nierównościowych
b kolumnowy wektor współczynników ograniczeń liniowych nierównościowych
Aeq macierz ograniczeń liniowych równościowych
beq kolumnowy wektor współczynników ograniczeń liniowych równościowych
lb dolne ograniczenie na wartości zmiennych niezależnych x
ub górne ograniczenie na wartości zmiennych niezależnych x
x0 punkt startowy poszukiwań
options decyduje o ilości informacji wyświetlanych na ekranie (wartość -1 blokuje wyświetlanie ostrzeżeń)

Argumenty wyjściowe:

x wektor zmiennych
fval wartość funkcji celu w punkcie minimum
exitflag informacja obliczeniowa
output informacja o rezultatach optymalizacji
lambda wartości współczynników Lagrange'a w punkcie optymalnym

Funkcja optimset

Do wyświetlenia standardowych parametrów funkcji linprog służy:

`optimset('linprog')`

Zadanie 1

Sprawdzić poprawność obliczeń zadania nr.1 z zestawu pierwszego. Poniżej tabelka z danymi:

Zużycie surowca (dkg)
na 1 szt. produktu
Zapas w magazynie
(dkg)
P1 P2 P3
mąka
cukier
słonecznik
1
1
0
2
1
1
1
1
2
5
4
1
Cena (zł) 1 3 2 max

Ważne:

Standardowo funkcja linprog liczy minimum funkcji celu, dlatego aby otrzymać maksimum wektor f powinien zawierać znak minus.

Zadanie 2

Rozwiąż zadanie programowania liniowego:

f(x) = -5x1 - 4x2 - 6x3
z ograniczeniami:

x1 - x2 + x3 <= 20
3x1 + 2x2 + 4x3 <= 42
3x1 + 2x2 <= 30
x1>=0, x2>=0, x3>=0

Sprawdź ile iteracji zostało wykonane oraz jaki algorytm został użyty do rozwiązania zadania.

Odpowiedź: x1= 0, x2=15, x3 = 3, wartość minimalna funkcji celu wynosi -78.0.

Zadanie 3 Zagadnienie podziału pól (rozkroju)

Plan zagospodarowania przestrzennego zawiera siedem działek (P1 do P7) przeznaczonych do podziału pod zabudowę jednorodzinną. Działki te mają jednakowe wymiary; 225 m długości na 30 m szerokości. Przyjąć że nie ma możliwości scalenia tych działek ze względu na ukształtowanie terenu. Wydzielanie działek po budowę domów jednorodzinnych z przedstawionych pól o podanych wymiarach stwarza wcześniejszą konieczność wydzielania z każdego pola pasa o szerokości 4 m pod infrastrukturę drogową, by zapewnić każdej uzyskanej działce niezależny dostęp do drogi publicznej. Z pól o wymiarach 225 m na 26 m, należy wydzielić poszukiwane działki budowlane. Sytuacja została zilustrowana na rysunku poniżej.

Celem zadania jest dokonanie podziału pól na mniejsze działki według zgłoszonego zapotrzebowania:

Z siedmiu jednakowych pól o długości 225 m i szerokości 26 m każde, należy wydzielić działki budowlane A, B i C w liczbie nie mniejszej niż wynosi zapotrzebowanie. Podziału należy dokonać w taki sposób, by zminimalizować łączną powierzchnie niewykorzystaną (odpad), która zostaje po podziale każdego z pól.

  1. Sprawdzić czy zadanie jest wykonywalne
  2. Na podstawie podanych w tabeli danych zdefiniować funkcję celu i warunki ograniczające:
Liczba działek Sposoby podziału pola
S1 S2 S3 S4 S5 S6 S7 S8
A (26x31)
B (26x46)
C (26x58)
7
0
0
1
4
0
0
1
3
5
0
1
4
2
0
0
2
2
2
1
2
0
3
1
Pozostałość po podziale
(m²)
208 260 130 338 78 338 26 754

Przez x1, x2, ... x8 oznaczymy zmienne decyzyjne modelu oznaczające liczbę pól podzielonych na działki budowlane sposobem S1, S2, ... S8.

Znaleźć optymalne rozwiązanie za pomocą funkcji linprog

Odpowiedź: Łączna niewykorzystana powierzchnia wynosi: 338 m2, należy podzielić 3 razy sposobem nr.5 oraz 4 razy sposobem nr.7.

Zadanie 4 Optymalny wybór asortymentu produkcji

Asortyment zakładu produkującego meble stanowią ławki, stoły i krzesła drewniane. Produkcja każdego odbywa się na trzech stanowiskach - obróbki wstępnej drewna, w stolarni i wykańczalni, których dopuszczalny czas pracy wynosi odpowiednio: 960, 800 oraz 320 godzin.W tablicy podano czas obróbki każdego wyrobu na poszczególnych stanowiskach oraz zyski uzyskane przez zakład ze sprzedaży wyrobów.

Nakład czasu pracy na jednostkę wyrobu w godz.
Zysk jednostkowy
(zł)
Obróbka wstępna drewna Stolarnia Wykańczalnia
Ławka
Stół
Krzesło
8
6
1
8
4
3
4
3
1
60
30
20
Czas pracy (godz.) 960 800 320 max

Obliczyć optymalne rozwiązanie dla tego problemu.

Odpowiedź: a) x1= 40, x2=0, x3=160, koszt obróbki: 5600
b) tak
c) x1= 100, x2=x3=0, koszt obróbki: 6000

Zadanie 5 Wybór technologii produkcji

Przedsiębiorstwo ma dostarczyć 3 różne detale w ilościach b1=2000, b2=1000, b3=4000. Ma możliwość zastosowania 4 różnych procesów technologicznych obróbki tych detali. Ilość detali uzyskiwanych w wyniku zastosowania poszczególnych sposobów obróbki detali w jednostce czasu oraz jednostkowe koszty obróbki podane są w tabeli poniżej. Jakie procesy technologiczne powinno zastosować przedsiębiorstwo aby dostarczyć detale w wymaganej ilości, minimalizując koszty ich produkcji ?

Detale Proces technologiczny
Plan produkcji
P1 P2 P3 P4
D1
D2
D3
25
15
40
40
8
32
40
20
25
10
5
3
2000
1000
4000
Koszt obróbki (zł) 420 380 450 200 max

Odpowiedź: x1= 100, x2=x3=x4=0, koszt obróbki: 42000

Zadanie 6 Optymalizacja składu mieszanin

W celu otrzymania stopu ołowiu, cyny i cynku wykorzystuje się surowiec będący mieszaniną pięciu stopów tych metali. Stopy te różnią się zawartością poszczególnych metali i kosztem uzyskania 1 kg stopu. Dane przedstawia tabela poniżej. Należy określić, jaki powinien być udział stopu każdego rodzaju w mieszaninie stanowiącej gotowy wyrób, aby otrzymać po minimalnym koszcie mieszaninę zawierającą 20% ołowiu, 30% cynku i 50% cyny.

Metale Stopy
S1 S2 S3 S4 S5
ołów
cyna
cynk
10
10
80
10
30
60
40
50
10
60
30
10
30
20
50
Koszt 1kg 4 4,5 5,8 6 7,5

Odpowiedź: x1=x2=x3 = 0.333, x4=x5 = 0, zysk wynosi: 4.7667.