Controleren op Optimaliteit

Optimaliteitstest kan worden uitgevoerd als aan twee voorwaarden is voldaan, dwz

1. Er zijn m + n - 1 toewijzingen, waarvan m het aantal rijen is, n is het aantal kolommen. Hier m + n - 1 = 6. Maar het aantal toewijzingen is vijf.

2. Deze toewijzingen m + n - 1 moeten op onafhankelijke posities plaatsvinden. Dwz dat het niet mogelijk zou moeten zijn om elke toewijzing te verhogen of te verlagen zonder de positie van de toewijzingen te wijzigen of de rij- of kleurbeperkingen te schenden.

Een eenvoudige regel voor toewijzingen om in onafhankelijke posities te zijn, is dat het onmogelijk is om van elke toewijzing terug te reizen, door een reeks horizontale en verticale stappen van de ene bezette cel naar de andere, zonder een directe omkering van de route. Er kan worden gezien dat in het huidige voorbeeld allocatie op onafhankelijke posities is omdat er geen gesloten lus kan worden gevormd op de toegewezen cellen.

Daarom is de eerste voorwaarde niet vervuld en daarom zullen we om aan de eerste voorwaarde te voldoen een kleine hoeveelheid E moeten toewijzen aan de lege cellen met de laagste transportkosten. Er kan worden gezien dat t kan worden toegewezen in cel (2, 2) met een kostprijs van 7 eenheden en toch blijven de toewijzingen op onafhankelijke positie zoals hieronder beschreven:

Het aantal toewijzingen is nu m + n- = 6 en ze bevinden zich op onafhankelijke posities.

Noteer kostenmatrix op toegewezen cellen.

Initiële kostenmatrix voor toegewezen cellen.

Schrijf ook de waarden van u _i en v _j zoals eerder uitgelegd.

Celevaluatiematrix

Uit tabel 5 is te zien dat celevaluatie in cel (1, 4) negatief is, dwz -4, dus door toewijzing aan cel (1, 4) worden transportkosten verder verlaagd. Laten we de oorspronkelijke toewijzingen en de voorgestelde nieuwe toewijzing noteren.

Uit tabel 6 is te zien dat als we toewijzen aan cel (1, 4) een lus wordt gevormd zoals getoond en we 10 eenheden toewijzen zodat toewijzing bij cel (2, 4) verdwijnt zoals hieronder in tabel 7 wordt getoond.

Nieuwe toewijzingstabel wordt

Transportkosten = 5X ₂ + 10X ₁ 1 + 10X ₇ + 15X9 + 5X ₄ + 18 + 5 = 435 eenheden. dat wil zeggen dat de transportkosten zijn gedaald van 475 eenheden naar 435 eenheden.

Controleer op Optimaity:

Laten we eens kijken of deze oplossing is optima! of niet? Daarvoor moeten opnieuw twee voorwaarden worden gecontroleerd, dwz

Aantal toewijzingen = m + n - 1 = 6 (tevreden)

Toewijzing op onafhankelijke positie (voldaan omdat gesloten lus voor toegewezen cellen niet is gevormd)

Schrijf kosten op de toegewezen alls en waarden van u _i en v _j

Voorbeeld 2:

(Onevenwichtige levering en vraag). Los het volgende transportprobleem op

Totale aanvoer = 200 eenheden, vraag = 185 eenheden.

Oplossing:

Aangezien vraag en aanbod niet gelijk zijn, is het probleem niet in evenwicht. Om het probleem te compenseren, moet een dummy colour worden toegevoegd, zoals hieronder wordt getoond. De vraag naar die dummy coloumn (winkel) zal 15 eenheden zijn.

Eenvoudige haalbare oplossing:

We zullen de benaderingsmethode van Vogel's gebruiken om de aanvankelijk haalbare oplossing te vinden.

De aanvankelijk haalbare oplossing wordt gegeven door de volgende matrix:

Optimaliteitstest:

Uit de bovenstaande matrix vinden we dat:

(a) Aantal toewijzingen = m + n - 1 = 4 + 5-1 = 8

(b) Deze toewijzingen m + n - 1 bevinden zich in onafhankelijke posities.

Daarom kan een optimalietest worden uitgevoerd. Dit bestaat uit de eerder toegelichte substappen, zoals weergegeven in de onderstaande tabellen:

Omdat celwaarden + ve zijn, is de eerste haalbare oplossing optimaal. Aangezien tabel 6 nulinvoer bevat, bestaan ​​er alternatieve optimale oplossingen. Het praktische belang van een vraag die 15 eenheden minder is dan het aanbod, is dat het bedrijf de productie van 15 eenheden in de fabriek kan verminderen, waar het niet economisch is.

Het optimale (minimum) transport plus productiekosten.

Z = Rs. (4 x 25 + 6 x 5 + 8 x 20 +10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)

= Rs. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1.465.

Voorbeeld 3:

Los het volgende transportprobleem op voor het maximaliseren van de winst. Wegens verschillen in grondstofkosten en transportkosten, verschilt de winst voor eenheid in roepies, zoals weergegeven in de onderstaande tabel:

Los het probleem op voor het maximaliseren van de winst.

Oplossing:

Probleem is uit balans en daarom moet een dummy rij worden toegevoegd om het in evenwicht te brengen.

Vind Initial Basic Feasible-oplossing:

We zullen de approximatiemethode van vogel gebruiken om de aanvankelijk haalbare oplossing te bepalen.

Merk op dat we te maken hebben met een maximalisatieprobleem. Daarom zullen we het verschil invoeren tussen de hoogste en de een na hoogste elementen in elke rij rechts van de rij en het verschil tussen de hoogste en de tweede hoogste elementen in elke kolom onder de corresponderende kolom.

Elk van deze verschillen staat voor de verloren winst per eenheid voor niet toewijzen aan de cel met de hoogste winst. Terwijl we toewijzingen maken, selecteren we eerst cel (2, 3) met de hoogste invoer in rij 2, wat overeenkomt met het hoogste verschil van [45].

Optimaliteitstest:

Vereist aantal toewijzingen = m + n - 1 = 3 + 4 - 1 = 6

Werkelijk aantal toewijzingen = 5.

Daarom wijzen we een klein positief cijfer € toe aan cel (1, 3) (cel met maximale winst uit lege cellen) zodat het aantal toewijzingen 6 wordt. Deze 6 toewijzingen bevinden zich in onafhankelijke posities. Daarom kan een optimalietest worden uitgevoerd.

Aangezien alle celwaarden negatief of nul zijn (maximalisatieprobleem), is de aanvankelijke basisuitvoerbare oplossing optimaal. De vraag op de eerste bestemming is 'ontevreden gelaten door 5 eenheden. De winst is

Z _max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]

= Rs. 31.600.