SIMPLEKS, Inne

Ćwiczenie:

Firma produkuje dwa wyroby A i B dla wytworzenia, których potrzebne są trzy środki produkcji.

Limity środków są następujące:

1 środek -24 jednostki

2 środek -40 jednostek

3 środek - 27jednostek

Aby wytworzyć 1 sztukę wyrobu A potrzebne są:

3 jednostki środka -1

8 jednostek środka -2

9 jednostek środka -3

Aby wytworzyć 1 sztukę wyrobu B potrzebne są:

6 jednostek środka -1

4 jednostki środka -2

3 jednostki środka -3

Opracować optymalny plan produkcji wiedząc, że zysk na wyrobie A- wynosi 9zł

na wyrobie B- wynosi 6zł

x₁- wielkość produktu A- 9zł

x₂- wielkość produktu B- 6zł

L(x) = 9x₁ + 6x₂ =>max

3x₁ + 6x₂ < 24 3x₁ + 6x₂ + x₃ = 24 3x₁ + 6x₂ + 1x₃ + 0x₄ + 0x₅ = 24

8x₁ + 4x₂ < 40 => 8x₁ + 4x₂ + x₄ = 40 => 8x₁ + 4x₂ + 0x₃+ 1x₄ + 0x₅ = 40

9x₁ + 3x₂ < 27 9x₁ + 3x₂ + x₅ = 27 9x₁ + 3x₂ + 0x₃ + 0x₄ + 1x₅ = 27

x₁, x₂ > 0

L(x) = 9x₁+6x₂+0x₃+0x₄+0x₅ =>max

Zakładamy:

X₁=0, x₂=0

[ 2, 3, 0, 12, 0]

[ 3 , 0 , 15 , 16 , 0 ]

[ x_1,x_2,x_3, x₄, x₅]

Wtedy: [ 0, 0, 24, 40, 27]

Ci	Xi	Cj	9	6	0	0	0	θ
Ci	Xi			B	A₁	A₂	A₃	θ	A₄	A₅
0	A₃	24	3	6	1	0	0	8
0	A₄	40	8	4	0	1	0	5
0	A₅	27	9	3	0	0	1	3
Zj		0	0	0	0	0	0
∆j		*	-9	-6	0	0	0

ZjB = 0*24+0*40+0*27=0

ZjA₁=0*6+0*8+0*9=0

ZjA₂=0*6+0*4+0*3=0

ZjA₃=0*1+0*0+0*0=0

ZjA₄=0*0+0*1+0*0=0

ZjA₅=0*0+0*0+0*1=0

∆= Zj - Cj

Cj	9	6
Zj	0	0
∆j	-9	-6

Jeżeli w ∆ występują ujemne liczby nie ma rozwiązania optymalnego.
Wybieramy kolumnę z największą liczbą ujemną (kolumnę kluczową)

Ci	Xi	Cj	9	6	0	0	0	θ
Ci	Xi			B	A₁	A₂	A₃	θ	A₄	A₅
0	A₃	24	3	6	1	0	0	8
0	A₄	40	8	4	0	1	0	5
0	A₅	27	9	3	0	0	1	3
Zj		0	0	0	0	0	0
∆j		*	-9	-6	0	0	0

Obliczamy:

θ = B: kolumnę kluczową θ=24:3=8

θ=40:8=5

θ=27:9=3

Wybieramy wiersz gdzie jest najmniejsza θ czyli 3

A₅

Element na przecięciu to element rozwiązujący.

ER= 9

Rozwiązanie ulepszamy poprzez wprowadzenie w nowej tablicy zamiast wiersza kluczowego wiersz o symbolu jak miała kolumna kluczowa czyli A₁

Ci	Xi	Cj	9	6	0	0	0	θ
Ci	Xi			B	A₁	A₂	A₃	θ	A₄	A₅
0	A₃
0	A₄
9	A₁	3	1	1/3	0	0	1/9		0	A₅	27	9	3	0	0	1	3
Zj
∆j

ENW=EWK: ER ENW=27:9=3

ENW=9:9=1

ENW=3:9=1/3

ENW=0:9=0

ENW=1:9=1/9

Rysujemy nową tabelę.

Ci	Xi	Cj	9	6	0	0	0	θ	Ci	Xi	Cj		9		6		0		0		0		θ
				B	A₁	A₂	A₃		A₄	A₅					B		A₁		A₂		A₃				A₄	A₅
0	A₃	15	0	5	1	0	-1/3			0	A₃	24		3		6		1		0		0		8
0	A₄	16	0	4/3	0	1	-8/9			0	A₄	40		8		4		0		1		0		5
9	A₁	3	1	1/3	0	0	1/9			0	A₅	27		9		3		0		0		1		3
Zj		27	9	3	0	0	1			Zj			0		0		0		0		0		0
∆j		*	0	-3	0	0	1			∆j			*		-9		-6		0		0		0

[ 3 , 0 , 15 , 16 , 0 ]

Jeżeli jest w wierszu 1 to wszystkie w górę są 0

NE=WE-EWK*EKK:ER=24-27*3:9=15 , 3-9*3:9=0 , 6-3*3/9=5 , 1-0*3:9=1 ,0-0*3:9=0

=40-27*8:9=16

ZjB=0*15+0*16+9*3=27

ZjA₁=0*0+0*0+9*1=9

ZjA₂=0*5+0*4/3+9*1/3=3

ZjA₃=itd.

∆j=Zj-Cj

Nie jest to optymalne rozwiązanie bo ∆j= -3

Kolumnę gdzie jest -3 wybieramy na kolumnę kluczową

Ci	Xi	Cj	9	6	0	0	0	θ
Ci	Xi			B	A₁	A₂	A₃	θ	A₄	A₅
0	A₃	15	0	5	1	0	-1/3	3
0	A₄	16	0	4/3	0	1	-8/9	12
9	A₁	3	1	1/3	0	0	1/9	9
Zj		27	9	3	0	0	1
∆j		*	0	-3	0	0	1

Obliczamy:

θ = B: kolumnę kluczową 15:5=3, 16:4/3=12 , 3:1/9=9

III

Rysujemy nową tabelę, a wiersz gdzie θ jest najmniejsze wymieniamy na wiersz kolumny kluczowej czyli A₂.

Wybieramy wiersz gdzie jest najmniejsza θ czyli 3 na wiersz kluczowy

A₃

-1/3

Element na przecięciu to element rozwiązujący ER=5

Ci	Xi	Cj	9	6	0	0	0	θ
Ci	Xi			B	A₁	A₂	A₃	θ	A₄	A₅
6	A₂	3	0	1	1/5	0	-1/15		0	A₃	15	0	5	1	0	-1/3	3
0	A₄
9	A₁
Zj
∆j

ENW=EWK: ER ENW=15:5=3

ENW=0:5=0

ENW=5:5=1

ENW=1:5=1/5

ENW=0:5=0

ENW=-1/3:5=-1/15

Rysujemy nową tabelę: poprzednią wykorzystujemy do obliczeń

Ci	Xi	Cj	9	6	0	0	0	θ	Ci	Xi	Cj	9	6	0	0	0	θ
Ci	Xi			B	A₁	A₂	A₃	A₄	Ci	Xi	A₅					B	A₁	A₂	A₃	A₄	A₅
6	A₂	3	0	1	1/5	0	-1/15			0	A₃	15	0	5	1	0	-1/3	3
0	A₄	12	0	0	-4/15	1	-4/5			0	A₄	16	0	4/3	0	1	-8/9	12
9	A₁	2	1	0	-1/15	0	2/15			9	A₁	3	1	1/3	0	0	1/9	9
Zj		36	9	6	3/5	0	4/5			Zj		27	9	3	0	0	1
∆j=Zj-Cj		*	0	0	3/5	0	4/5			∆j		*	0	-3	0	0	1