Simplex-menetelmän laskin

Laskin ratkaisee annetun optimointiongelman simplex-algoritmilla. Se lisää tarvittaessa löysyys-, ylimäärä- ja keinotekoisia muuttujia. Keinotekoisten muuttujien tapauksessa alkuratkaisun määräämiseksi käytetään Big M -menetelmää tai kaksivaihemenetelmää. Ratkaisuvaiheet ovat saatavilla.

Tavoitefunktio:

Maksimoi?

Rajoitteet:

Pilkuilla eroteltu.

Ovatko kaikki muuttujat epänegatiivisia?

Keinotekoinen alkuratkaisumenetelmä:

Jos laskin ei laskenut jotakin tai olet havainnut virheen tai sinulla on ehdotus tai palaute, ole hyvä ja ota meihin yhteyttä.

Syötteesi

Maksimoi $$$Z = 3 x_{1} + 4 x_{2}$$$, ehdolla $$$\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{2} \geq 0 \\ x_{1} \geq 0 \end{cases}$$$.

Ratkaisu

Ongelma kanonisessa muodossa voidaan kirjoittaa seuraavasti:

$$Z = 3 x_{1} + 4 x_{2} \to max$$$$\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{cases}$$

Lisää muuttujia (löysä- tai ylijäämämuuttujia) muuttaaksesi kaikki epäyhtälöt yhtälöiksi:

$$Z = 3 x_{1} + 4 x_{2} \to max$$$$\begin{cases} x_{1} + 2 x_{2} + S_{1} = 8 \\ x_{1} + x_{2} + S_{2} = 6 \\ x_{1}, x_{2}, S_{1}, S_{2} \geq 0 \end{cases}$$

Kirjoita simpleksitaulukko:

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu
$$$Z$$$	$$$-3$$$	$$$-4$$$	$$$0$$$	$$$0$$$	$$$0$$$
$$$S_{1}$$$	$$$1$$$	$$$2$$$	$$$1$$$	$$$0$$$	$$$8$$$
$$$S_{2}$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$1$$$	$$$6$$$

Sisään tuleva muuttuja on $$$x_{2}$$$, koska sillä on Z-rivillä kaikkein negatiivisin kerroin $$$-4$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu	Ratio
$$$Z$$$	$$$-3$$$	$$$-4$$$	$$$0$$$	$$$0$$$	$$$0$$$
$$$S_{1}$$$	$$$1$$$	$$$2$$$	$$$1$$$	$$$0$$$	$$$8$$$	$$$\frac{8}{2} = 4$$$
$$$S_{2}$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$1$$$	$$$6$$$	$$$\frac{6}{1} = 6$$$

Poistuva muuttuja on $$$S_{1}$$$, koska sillä on pienin suhdeluku.

Jaa rivi $$$1$$$ luvulla $$$2$$$: $$$R_{1} = \frac{R_{1}}{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu
$$$Z$$$	$$$-3$$$	$$$-4$$$	$$$0$$$	$$$0$$$	$$$0$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$S_{2}$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$1$$$	$$$6$$$

Lisää rivi $$$2$$$ kerrottuna luvulla $$$4$$$ riviin $$$1$$$: $$$R_{1} = R_{1} + 4 R_{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu
$$$Z$$$	$$$-1$$$	$$$0$$$	$$$2$$$	$$$0$$$	$$$16$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$S_{2}$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$1$$$	$$$6$$$

Vähennä rivi $$$2$$$ rivistä $$$3$$$: $$$R_{3} = R_{3} - R_{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu
$$$Z$$$	$$$-1$$$	$$$0$$$	$$$2$$$	$$$0$$$	$$$16$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$S_{2}$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$- \frac{1}{2}$$$	$$$1$$$	$$$2$$$

Sisään tuleva muuttuja on $$$x_{1}$$$, koska sillä on Z-rivillä kaikkein negatiivisin kerroin $$$-1$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu	Ratio
$$$Z$$$	$$$-1$$$	$$$0$$$	$$$2$$$	$$$0$$$	$$$16$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$	$$$\frac{4}{\frac{1}{2}} = 8$$$
$$$S_{2}$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$- \frac{1}{2}$$$	$$$1$$$	$$$2$$$	$$$\frac{2}{\frac{1}{2}} = 4$$$

Poistuva muuttuja on $$$S_{2}$$$, koska sillä on pienin suhdeluku.

Kerro rivi $$$2$$$ luvulla $$$2$$$: $$$R_{2} = 2 R_{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu
$$$Z$$$	$$$-1$$$	$$$0$$$	$$$2$$$	$$$0$$$	$$$16$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$x_{1}$$$	$$$1$$$	$$$0$$$	$$$-1$$$	$$$2$$$	$$$4$$$

Lisää rivi $$$3$$$ riviin $$$1$$$: $$$R_{1} = R_{1} + R_{3}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu
$$$Z$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$2$$$	$$$20$$$
$$$x_{2}$$$	$$$\frac{1}{2}$$$	$$$1$$$	$$$\frac{1}{2}$$$	$$$0$$$	$$$4$$$
$$$x_{1}$$$	$$$1$$$	$$$0$$$	$$$-1$$$	$$$2$$$	$$$4$$$

Vähennä rivistä $$$2$$$ $$$\frac{1}{2}$$$ kertaa rivi $$$3$$$: $$$R_{2} = R_{2} - \frac{R_{3}}{2}$$$.

Basic	$$$x_{1}$$$	$$$x_{2}$$$	$$$S_{1}$$$	$$$S_{2}$$$	Ratkaisu
$$$Z$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$2$$$	$$$20$$$
$$$x_{2}$$$	$$$0$$$	$$$1$$$	$$$1$$$	$$$-1$$$	$$$2$$$
$$$x_{1}$$$	$$$1$$$	$$$0$$$	$$$-1$$$	$$$2$$$	$$$4$$$

Yksikään Z-rivin kertoimista ei ole negatiivinen.

Optimi on saavutettu.

Saadaan seuraava ratkaisu: $$$\left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right)$$$.

Vastaus

$$$Z = 20$$$A saavutetaan kohdassa $$$\left(x_{1}, x_{2}\right) = \left(4, 2\right)$$$A.

Simplex-menetelmän laskin

Ratkaise optimointiongelmia simplex-menetelmällä

Syötteesi

Ratkaisu

Vastaus