Učebnice: Workshop na řešení úloh lineárního matematického programování. Schopnost přejít z jednoho referenčního plánu do druhého

34. Znak jedinečnosti optimálního plánu, souboru optimálních plánů a absence optimálního plánu při řešení úlohy LP simplexovou metodou.

Při řešení problémů pomocí simplexní metody jsou možné následující typy optimálních řešení:

1. Jedinečnost . Pokud jsou odhady všech volných vektorů striktně negativní, pak je výsledný referenční plán optimální a jedinečný. (viz příklad v předchozím odstavci).

2. Alternativní optimum (množina optimálních řešení).

Pokud je mezi nekladnými odhady volných vektorů alespoň jedna nula, pak bude výsledný referenční plán optimální, ale ne jediný. V tomto případě můžete přejít k dalším referenčním plánům (do základu jsou zavedeny vektory, které odpovídají nulovým odhadům) a poté obecný optimální řešení zapište ve formě konvexní kombinace získaných optimálních referenčních plánů.

3. ZLP nemá optimální řešení, jelikož účelová funkce není zdola omezena . Pokud má simplexní tabulka kladné skóre, a všechny prvky tohoto sloupce jsou záporné a nulové, pak lze tento vektor zavést do základu. Žádný ze základních vektorů však nelze odvodit z báze. Z toho plyne další pokles Objektivní funkce možné při přechodu na nepodpůrný plán.

4. ZLP nemá optimální řešení, protože systém omezení je rozporuplný. Od kdy rozhodnutí PPP obvyklá simplexová metoda musí být původní referenční plán, pak systém lineárních rovnic jistě není nekonzistentní. Při řešení obvyklou simplexovou metodou tedy takový případ nemůže nastat.

5. Pokud se ODZ skládá z jednoho bodu, pak je řešení takového problému triviální a lze jej získat bez použití simplexové metody.

35. V jakých případech se používá metoda umělé báze?

umělý.

36. Konstrukce M-problému v metodě umělé báze

Pokud je problém lineárního programování v kanonická forma ne všechny rovnice však obsahují základní proměnné, tj. chybí původní referenční plán. V tomto případě v těch rovnicích, ve kterých nejsou žádné základní proměnné, je nutné přidat nějakou nezápornou proměnnou s koeficientem +1. Taková proměnná se nazývá umělý.

K účelové funkci musí být přidána umělá proměnná s velmi velkým kladným číslem (protože účelovou funkcí je najít minimum). Toto číslo je označeno Latinské písmeno M. Lze ji považovat za rovnou +∞. V tomto ohledu se metoda umělé báze někdy nazývá M-metoda. Tato transformace původní problém se nazývá konstrukce rozšířeného problému. Pokud řešíte problém s účelovou funkcí k nalezení umělé proměnné, musíte ji přidat k účelové funkci s velmi velkým kladným číslem (protože účelovou funkcí je najít minimum). Toto číslo se označuje latinským písmenem M. Lze jej považovat za rovné +∞. V tomto ohledu se metoda umělé báze někdy nazývá M-metoda. Tato transformace původního problému se nazývá konstrukce rozšířeného problému. Pokud je problém řešen účelovou funkcí k nalezení maxima, pak jsou umělé proměnné zahrnuty do účelové funkce s koeficientem –M.

V rozšířeném problému tedy máme referenční návrh (ačkoli některé základní proměnné jsou umělé).

Je vytvořena počáteční simplexní tabulka.

37. sestrojení indexové čáry metodou umělé báze

Je vytvořena počáteční simplexní tabulka, ve které je řádek indexu rozdělen do dvou řádků, protože odhady se skládají ze dvou členů. Hodnotící člen bez M se zapisuje do horního řádku a koeficienty pro M se zapisují do spodního řádku Znaménko odhadu je určeno znaménkem koeficientu pro M, bez ohledu na hodnotu a znaménko členu bez M, protože M je velmi velké kladné číslo.

Pro určení vektoru, který je zaveden do báze, je tedy nutné analyzovat spodní indexovou linii. Pokud je ze základu odvozen umělý vektor, pak nelze příslušný sloupec v následujících simplexových tabulkách vypočítat, pokud není potřeba získat řešení duální problém(viz další téma).

Po odvození všech umělých vektorů ze základu bude mít spodní řádek všechny nulové prvky kromě skóre odpovídajících umělým vektorům. Budou se rovnat –1. Takovou linii lze vyřadit z úvahy a další řešení lze provést obvyklou simplexovou metodou, není-li potřeba získat řešení duální úlohy (viz další téma).

38. Kritérium optimálnosti v metodě umělé báze. Počáteční stavební znamení referenční plán původní úkol.

39. Algoritmus pro duální simplexovou metodu

Algoritmus duální simplexové metody:

vyplňte první simplexovou tabulku obvyklým způsobem, aniž byste věnovali pozornost znaménkům volných termínů. Předpokládá se, že takový problém musí mít počáteční jednotkový základ.

Vodicí čáru vyberte podle největšího záporného prvku absolutní hodnoty sloupce volných členů A0

Vodicí sloupec je vybrán podle nejmenšího poměru absolutních hodnot prvků indexového řádku k záporným prvkům vodícího řádku.

Přepočítat simplexní stůl podle pravidla úplných Jordanových výluk

zkontrolovat přijatý plán z hlediska přípustnosti. Známkou získání přijatelného referenčního plánu je absence záporných prvků ve sloupci A0. Pokud jsou ve sloupci A0 záporné prvky, přejděte k druhému bodu. Pokud tam nejsou, pak přistoupí k řešení vzniklého problému běžným způsobem.

znamení získání optimálního řešení duální simplexová metoda je kritériem optimality pro konvenční simplexovou metodu.

41. Otevřené a uzavřené dopravní modely. Přechod z otevřeného dopravní model do zavřeno.

Typy přepravních úloh.

Dostupný m dodavatelů homogenních produktů se známými zásobami produktů a n spotřebitelům těchto produktů s daným objemem potřeb. Známé jsou také jednotkové náklady na dopravu.

Pokud se součet objemů zásob výrobků rovná objemu potřeb všech spotřebitelů, pak je takový problém tzv. problém uzavřené dopravy

(tj. pokud ∑ Ai = ∑ Bj), jinak je volán transportní problém OTEVŘENO. Pro řešení dopravní problém musí být zavřeno.

Otevřený transportní problém lze převést na uzavřený následovně.

Nechť ∑Ai > ∑Bj. V tomto případě je nutné zavést fiktivního n+1 spotřebitele s objemem potřeb ∑Ai – ∑Bj Předpokládá se, že jednotkové náklady na dopravu od dodavatelů k fiktivnímu spotřebiteli jsou rovny 0, protože ve skutečnosti taková doprava nebudou realizovány a některé produkty zůstanou dodavatelům.

Pokud ∑Bj > ∑Ai . V tomto případě je nutné zadat fiktivního dodavatele m+1 s objemem zásob ∑Bj – ∑Ai . Předpokládá se, že jednotkové náklady na přepravu od fiktivního dodavatele ke spotřebitelům se rovnají 0, protože ve skutečnosti taková přeprava nebude provedena a spotřebitelé některé produkty neobdrží.

42. Metody konstrukce počátečního rozdělení v dopravní úloze: metoda severozápadního rohu a metoda nejmenšího prvku v matici.

Severozápadní metoda konstrukce referenčního plánu. Podle této metody začíná tvorba přepravních hodnot od severozápadu. rohu stolu, tzn. z buňky x11. Podle tohoto způsobu je nejprve distribuováno zboží prvního dodavatele. Navíc první dodavatel nejprve maximálně uspokojí prvního spotřebitele. Pak, pokud dodavatel stále má zboží,

Metoda nejmenšího prvku v matici.

Podstatou metody je, že do buňky je vždy umístěna maximální možná zásoba, která odpovídá nejnižšímu tarifu v matici.

Nejprve uděláme značky (například znakem ▼) v těch buňkách řádků, ve kterých je pozorována nejnižší cena za řádek. Poté obcházíme tabulku sloupec po sloupci a děláme stejné poznámky do buněk, které obsahují nejnižší cenu ve sloupcích.

Další rozdělení se provádí nejdříve, pokud možno, do buněk se dvěma značkami, poté s jednou a poté se úloha přerovná na (m + n – 1) výplně. Náplně organizujeme pohybem po stole zleva doprava a shora dolů.

43. Vlastnosti dopravních úloh

Transportní problém má některé vlastnosti, které lze odrážet následujícími větami.

Věta 1. Uzavřený dopravní problém má vždy řešení.

Věta 2. Jsou-li objemy zásob produktů a objemy potřeb celá čísla, pak řešení problému dopravy bude také celočíselné.

Věta 3. systém omezení uzavřeného transportního problému je vždy lineárně závislý.

Z této věty vyplývá, že rozdělení uzavřeného transportního problému má vždy m + n – 1 základních proměnných a (m – 1) (n – 1) proměnných volného času.

44. Degenerovaná distribuce v dopravních problémech, zbavení se degenerace. Přeškrtnutá kombinace.

Distribuce se nazývá degenerovaná, pokud je počet buněk menší než m + n – 1.

45. Věty o optimalitě pro dopravní problém.

Teorém. Pokud pro nějaké rozdělení dopravního problému vás

jsou splněny podmínky:

A). ui+vj = сij pro obsazené buňky

b) ui+vj ≤ сij, pro volné buňky,

pak je toto rozložení optimální.

Veličiny ui se nazývají řádkové potenciály a veličiny vj se nazývají sloupcové potenciály.

46. ​​Potenciály a metody jejich výpočtu.

K nalezení potenciálů řádků a sloupců použijte následující úvahu založenou na podmínce a) věty o optimalitě.

Počet rovnic založených na této podmínce je roven m + n – 1 a počet neznámých ui a vj je roven m + n. Že. počet proměnných je větší než počet rovnic a všechny rovnice jsou lineárně nezávislé. Řešení takového systému lineární rovnice není definován, takže jednomu z potenciálů musí být přiřazena libovolná hodnota. V praxi je ui = 0. Získá se soustava m + n – 1 rovnic s m + n – 1 neznámými proměnnými. Tento systém lze vyřešit jakoukoliv metodou. V praxi se pro výpočet potenciálů uvažují obsazené buňky, u kterých je znám jeden z jejich potenciálů, a na základě podmínky a) věty se vypočítají hodnoty zbývajících neznámých potenciálů.

47. výpočet odhadů optimality pro rozdělení přepravních úloh a kritéria optimality.

Na základě vztahu b) věty můžeme napsat následující vzorec pro výpočet odhadů: δ ij= ui +vj – сij. Aby odhady nebyly zaměňovány s objemy přepravy, jsou tyto (odhady) uzavřeny v kroužcích.

Odhady optimality ve volných buňkách TZ představují kritérium optimality, pomocí kterého se kontroluje optimalita rozdělení. Pokud je skóre všech volných buněk menší nebo rovno nule, pak je toto rozdělení optimální.

48. přerozdělení zásob v dopravním problému

Pokud distribuce není optimální, pak je nutné zásoby přerozdělit.

Pro přerozdělení je sestaven cyklus přepočtu. Jako buňka je vybrána buňka s nejvyšším kladným skóre. Tato buňka je označena znaménkem „+“, to znamená, že do ní musí být zapsáno určité množství doručení. Pak se však rovnováha v tomto sloupci naruší, proto musí být jedna z obsazených buněk tohoto sloupce označena znaménkem „-“, to znamená, že objem dodávky musí být snížen o stejnou částku. Pak se ale změní zůstatek na tomto řádku, proto musí být některá obsazená buňka tohoto řádku označena znaménkem „+“. Tento proces pokračuje, dokud se znaménko „-“ nevloží do řádku, kde byla umístěna původní buňka.

Pro každou volnou buňku existuje cyklus přepočtu a navíc jedinečný.

Simplexní metoda pro řešení úloh lineárního programování

Simplexová metoda je analytická metodaŘešení ZLP implementující algoritmus grafická metoda analyticky, bez kreslení výkresu.

Takže pointa je taková simplexní metoda sestává z cíleného vyhledávání přípustná řešení, ve kterém je hodnota účelové funkce v každém kroku lepší než v předchozím. Proces se opakuje, dokud není získáno řešení, které je optimální z hlediska hodnoty účelové funkce.

Simplexovou metodu lze použít k řešení PLP s libovolným počtem neznámých.

Technická realizace Simplexová metoda je spojena s řešením soustav lineárních rovnic, pro které je vyvinuta Gaussova metoda a pravidla pro převod simplexových tabulek.

Simplexová metoda na přírodní bázi platí, pokud je ZLP uveden ve formě kanonické notace a matice v QLP obsahuje jednotkovou podmatici velikosti jsem. Pro jistotu předpokládejme, že první m vektory matice soustavy rovnic jsou matice identity. Poté je počáteční plán vybrán takto:

Optimálnost referenčního plánu se kontroluje pomocí znaménka optimality, přechod na jiný plán se provádí pomocí Jordan-Gaussovy transformace pomocí matematického znaménka optimality. Výsledný referenční plán je opět kontrolován na optimálnost atd.

Matematické kritérium pro optimalitu se skládá z následujících dvou vět:

1. Pokud pro všechny vektory A 1, A 2, …, A n podmínka je splněna kde , pak je výsledný referenční plán optimální. Celkem určit Z júčastnit se m termíny, to znamená, že se na něm nepodílejí všechny koeficienty účelové funkce c j, ale pouze s čísly odpovídajícími číslům aktuálních bázových vektorů A i, jejichž počet je roven m .

2. Je-li pro některý vektor nezahrnutý v bázi podmínka splněna , pak byste měli hledat nový referenční plán, pro který je hodnota CF vyšší než pro aktuální. V tomto případě jsou možné dva případy:

a) jsou-li všechny složky vektoru A k, které mají být zaneseny do základu, jsou nepozitivní, pak LLP nemá řešení (neexistuje žádné konečné optimum);

b) má-li vektor alespoň jednu kladnou složku A k, který má být vložen do základu, pak lze získat nový referenční plán.

Na základě kritéria optimality je do báze zaveden vektor A k, což dalo minimální zápornou hodnotu simplexního rozdílu:

Aby byla splněna podmínka nezápornosti hodnot referenčního plánu, je vektor odvozen ze základu A r, což udává minimální kladný poměr hodnocení

Čára A r, ve kterém se nacházel starý vektor báze, se nazývá průvodce, sloupec A k a prvek a rk- průvodci.

Prvky vodicí čáry v nové simplexní tabulce se vypočítají pomocí vzorců:

a jakékoli další prvky iřádek - podle vzorců:

Hodnoty nového referenčního plánu se vypočítají pomocí podobných vzorců:

,

Proces pokračuje buď dokud není získán optimální plán, nebo dokud není TF neomezená. Pokud mezi rozdíly Aj, j=1, 2, …, n optimálního plánu jsou pouze rozdíly odpovídající základním vektorům nulové, to svědčí o jedinečnosti optimálního plánu. Pokud nulový odhad odpovídá vektoru, který není zahrnut v základu, pak obecný případ Znamená to, že optimální plán ne jediný.

Příklad. Vyřešte ZLP pomocí modelu:

nalézt ,

pod omezeními

Tento ZLP je redukován na kanonickou formu zavedením dalších proměnných x 3 A x 4:

KZLP má požadovaný počet (dva) nula sloupců na x 3 A x 4, to znamená, že má zřejmý počáteční referenční plán (0,0,300,150).

Řešení se provádí simplexovou metodou s přirozeným základem s výpočty formátovanými v simplexních tabulkách:

Simplexní číslo tabulky	Základ	s j	s j					Q
B	A 1	A 2	A 3	A 4
	←A 3
A 4
Δ	-		-2	-3			-
já	→A 2			1/3		1/3
←A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Podívejme se podrobněji na vyplňování simplexních tabulek a podle toho k získání řešení KZLP.

V horní linie obecná tabulka přidané koeficienty cj, j=1, 2, 3, 4 s proměnnými v digitální funkci. První dva řádky nulové simplexní tabulky obsahují sloupcové vektory B, A 1, A 2, A 3, A 4, odpovídající vektorová forma záznamy KZLP. Protože výchozím základem je dvojice vektorů A3, A4, jsou zahrnuty ve sloupci s názvem „Základ“ nulové simplexní tabulky. přičemž A 3 je zahrnuta v prvním řádku, který je určen jednotkou, která je prvním prvkem tohoto vektoru, a vektorem A 4- do druhého řádku, pro tento vektor je jednotka na druhém řádku. Ve sloupci s názvem „ c i” jsou zavedeny koeficienty účelové funkce odpovídající vektorům báze A3, A4, to je c 3, c 4. Oba se rovnají nule. Dále se vypočítají hodnoty rozdílů Δ pro vektory B, A 1, A 2, A 3, A 4 a zapisují se do třetího řádku nulové tabulky. Pro vektor A 1:

pro vektor:

Stejně tak .

Pro vektor B výpočet rozdílu je poněkud zjednodušen, protože neexistuje žádný odpovídající koeficient cj, j=1, 2, 3, 4 v CF:

Ne pro všechny vektory A1, A2, A3, A4 výsledné rozdíly jsou nezáporné, takže námi zvolený referenční plán není optimální. Musíme hledat nový referenční plán, a proto musíme nahradit jeden z vektorů zahrnutých v základu A3, A4.

Abychom určili vektor, který musíme zadat, hledáme vektor, pro který je rozdílová hodnota minimální. Toto je vektor A 2, odpovídá tomu minimální hodnota rozdíl: -3. Tedy index k ze vzorce (8.4) je roven 2. Abychom určili vektor, který budeme muset odvodit ze základu, vypočteme hodnoty Q pro každý řádek podle vzorce (8.5) a zadejte je do posledního sloupce. V v tomto případě v každém řádku potřebujeme hodnotu prvku vector B vydělte velikostí prvku vektoru A 2. V prvním řádku dostaneme 300/3=100, ve druhém: 150/1=150. Poměr v prvním řádku mu odpovídal základní vektor A 3 tedy index r ve vzorci (8.5) se rovná 1, a rk=3 (v tabulce zvýrazněno rámečkem), a vektor odvodíme ze základu A 3(v tabulce označeno šipkou).

Od mezi prvky vektoru A 2, které je nutné zadat do základu, existují kladné, pak lze získat nový referenční plán a v řešení by se mělo pokračovat.

Poté se vyplní druhá simplexní tabulka. K přepočítání vektorových prvků B, A 1, A 2, A 3, A 4 se používají vzorce (8.6)-(8.8). Mírně se liší pro definování prvků vodicí čáry (v našem případě první) a pro definování prvků ostatních čar. Zapišme si výpočty několika prvků:

Ostatní prvky první simplexové tabulky se vypočítají stejným způsobem jako u nulové tabulky. Protože ne všechny rozdíly v první simplexové tabulce jsou nezáporné, je nutné pokračovat ve výpočtech.

Jak vidíme, jako výsledek výpočtů ve druhé simplexní tabulce se základními vektory A2, A1 všechny rozdíly se ukázaly jako nezáporné, což znamená dosažení optimálního plánu (75; 75; 0; 0). Simplexní rozdíl pro vektor V rovná požadované maximální hodnotě CF - 375.

Věta (o konečnosti simplexového algoritmu).Pokud existuje optimální řešení ZLP, pak existuje i základní optimální řešení. Ten lze vždy získat pomocí simplexové metody a můžete začít z jakéhokoli počátečního základu.

Znak optimálnosti referenčního plánu

Pokud jsou v simplexní tabulce obsahující určitý plán podpory všechny prvky řady f (kromě volného termínu) nezáporné, pak je tento plán podpory optimální. Vpusťte řádek f tabulky. 2.b Oj > (i=1, ..., nm). V referenčním plánu x 0 obsaženém v této tabulce jsou hodnoty všech volných proměnných x m+j rovny nule a f(x 0) =b 00. Zvětšíte-li některou z volných proměnných x m+ j, pak, jak je vidět z rovnosti (2.5), v důsledku nezápornosti b 0j začne hodnota f(x) klesat. Následně v x o dosáhne funkce f(x) své největší hodnoty, což znamená, že x 0 je skutečně optimální referenční plán.

Schopnost přejít z jednoho referenčního plánu do druhého

Jak již bylo zmíněno výše, podstata simplexové metody je v procesu dokazování další znamení: pokud je v f-řádku simplexové tabulky obsahující nějaký referenční plán alespoň jeden záporný prvek (bez započítání volného termínu), který odpovídá sloupci s alespoň jedním kladným prvkem, pak můžete transformací přejděte na jiný plán podpory s skvělá hodnota cílová funkce.

Dokažme toto znamení. Stanovme si pravidla pro výběr proměnných pro takovou transformaci počáteční základ B asi s referenčním plánem x 0 do nové základny B1 s referenčním plánem x 1, na kterém; hodnota funkce f roste, tj. f(x i)>f(x 0). Poté je podle pravidla pro přepočet prvků z simplexové tabulky převedeme na nový základ, který nám umožní najít komponenty nového referenčního plánu.

Předpokládejme, že v tabulce. 2.1, například b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) která z proměnných by měla být odstraněna z předchozí báze, aby se uvolnilo místo pro proměnnou x m+s;

2) jakou hodnotu má nabývat nová základní proměnná x m+s v novém referenčním plánu.

K vyřešení položených otázek předpokládejme, že v rovnosti (2.4) jsou všechna x m+j, kromě x m+s, rovna nule. Pak

x i = bio -b je x m+s (i=l, ..., m)

Z těchto rovností je zřejmé, že s rostoucím x m+s se hodnoty těch základních proměnných x i, pro které jsou koeficienty b<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. S narůstajícím x m+s začnou hodnoty těchto proměnných klesat a přijde okamžik, po kterém nabudou záporných hodnot a podmínka (2.3) již nebude splněna. To nelze dovolit. Zjistěme tedy, na jakou mezní hodnotu x m+s lze zvýšit, aniž by byla porušena podmínka nezápornosti základních proměnných. Za tímto účelem vypíšeme ze systému (2.6) ty rovnosti, ve kterých b je >0. Předpokládejme, že se to týká rovností s čísly i=d,…,k,…,p:

x d =b do -- b ds x m+s ,

…………………..

x k = b k0 - b ks x m+s,

………………….

x p =b p0 - bps x m+s.

Základní proměnné x d, ..., x k, ..., x p zůstanou nezáporné, pokud x m+s vyhovuje systému nerovností

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 nebo x m+s< b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s< b po /b ps

tj. při x m+s

Nechť nejmenšímu ze zlomků b io /b odpovídá i = k, tzn.

min ( bio /b je )= b k0 /b ks .

Pak můžeme říci, že pokud x m+s nepřekročí hodnotu b k0 /b ks , tj. x m+s 0, pak se proměnná x k bude rovnat odrážce: x k = b k0 -- b ks b ko /b ks = 0, a tím bude základ transformován B o = (x 1 ; ...; x k ; . .. x m ) do nového základu, ve kterém proměnná x m+s přechází z volné grupy do základních a proměnná x k zaujímá místo x m+s ve volné grupě. Všechny ostatní volné proměnné jsou přitom stále rovny nule a zbývající základní proměnné jsou stále kladné. V důsledku toho bude mít základní plán x 1 v nové bázi B 1 = (x 1 ; ...; x m+s ; ...; x m ) m kladných složek a m-n nula jedniček. V plánu x 1 mohou některé základní proměnné nabývat nulových hodnot ve dvou případech:

1) když v plánu x 0 jsou základní proměnné rovné nule;

2) když nejmenší ze zlomků b io /b je bude odpovídat dvěma nebo více číslům i V našem případě odpovídá pouze i = k.

Proměnná, která má být zahrnuta do základu, je určena záporným prvkem f-řetězce. Z rovnosti f =b oo - b os x m+s je zřejmé, že když b 0s<0 и фиксированном x m+s >0, hodnota f(x) závisí na absolutní hodnotě koeficientu b 0s: čím větší |b 0s |, tím větší hodnotu f(x) získá v novém základu. Ale z této rovnosti je také zřejmé, že hodnota účelové funkce v nové bázi závisí také na hodnotě, kterou nabývá nová bázová proměnná x m+s. Zvolíme proměnnou zavedenou do základu se zaměřením pouze na negativní prvky f-řady. Pokud je tedy v řadě f více záporných prvků, zavedeme do základu proměnnou x m+j odpovídající zápornému prvku s největší absolutní hodnotou. Sloupec koeficientů pro proměnnou zahrnutou do základu se nazývá rozlišení. Volbou proměnné zavedené do báze (nebo volbou rozlišovacího sloupce) na základě záporného prvku f-řádku tedy zajistíme, že funkce f vzroste.

Trochu obtížnější je určit proměnnou, která má být vyloučena ze základu. Za tímto účelem vztahy volných členů k pozitivní prvky rozlišovací sloupec (takové vztahy se nazývají simplexní) a najděte mezi nimi nejmenší, který určuje řádek (rozlišovací) obsahující vyloučenou proměnnou. Volba proměnné vyloučené z báze (resp. volba rozlišovací linie) podle minimálního simplexního vztahu zaručuje pozitivitu složek báze v novém referenčním plánu.

Dokázali jsme tedy, že za podmínek specifikovaných ve znaménku je skutečně možné přejít z jednoho referenčního plánu do druhého s velkou hodnotou účelové funkce f(x).

Všimněte si, že již známe hodnotu nové bazické proměnné x m+s v novém referenčním plánu: rovná se b ko /b ks . Pokud jde o číselné hodnoty zbývajících základních proměnných v novém referenčním plánu a odpovídající hodnotu f(x), lze je zjistit až po změně systému základních proměnných x 1 ;..., x m+s ; ...,x m bude vyjádřeno prostřednictvím upraveného systému volných proměnných x m+1,…,x k,…, x n. Chcete-li to provést, nastavme; pravidla, jimiž se podmínky problému transformují z jednoho základu na druhý.

Koeficient b ks = 0 při x m+s v této rovnici se nazývá rozlišovací prvek. V rovnosti (2.7) je nová základní proměnná x m+s vyjádřena pomocí volných proměnných, mezi kterými se nyní nachází bývalá základní proměnná x k. Proměnné x m+s a x k si tedy vyměnily role.

Vyjádřeme podobně zbývající základní proměnné prostřednictvím nové množiny volných proměnných. Pro tento účel dosadíme ze zbývajících rovností hodnotu x m+s (f označíme x 0, pak bude rovnost zahrnuta do systému v i = 0)

Přivedení systému na nový základ se nazývá simplexní transformace. Pokud je simplexová transformace považována za formální algebraickou operaci, pak si můžeme všimnout, že v důsledku této operace jsou role přerozděleny mezi dvě proměnné zahrnuté v určitém systému lineárních funkcí: jedna proměnná přechází ze závislé na nezávislou a druhá , naopak z nezávislých na závislé . Tato operace je v algebře známá jako Jordanův eliminační krok.

Znak optimálnosti referenčního plánu. Simplexní stůl

Pro řešení problémů se podmínky obvykle zadávají do tabulky zvané simplexní tabulka. Před vstupem je systém omezení zredukován na preferovanou formu.

pod omezeními

Systém omezení pro tento problém má preferovanou formu. Vytvoříme simplexní tabulku.

Nalezení počátečního referenčního plánu

Označme B množinu základních proměnných a B množinu volných proměnných. Pochopitelně v, . Hodnoty se nazývají odhady volných proměnných.

Známka optimálního plánu podpory:

1) Referenční návrh poskytuje minimální hodnotu cílové funkci, pokud jsou všechny odhady volných proměnných pro ni nekladné.

2) Referenční plán plní účelovou funkci maximální hodnota, pokud jsou všechny odhady volných proměnných nezáporné.

Cílový funkční řetězec se nazývá Z-řetězec nebo indexový řetězec. Počáteční referenční plán Xo = (1/2;3/2;0;2;0) a Z(Xo) = -9/2. Protože všechny odhady indexové linie jsou nepozitivní, pak je plán X 0 optimální.

Přechod na noninferiorní referenční plán. Simplexní transformace

Zvažme problém

Počáteční referenční plán

Pokud jsou všechny odhady volné proměnné, pak je plán X 0 optimální. Pokud existují kladné odhady volných proměnných, pak se sloupec, který odpovídá největší hodnotě?j, nazývá rozlišovací. Označme jeho číslo j o a do základu zaveďme hodnotu x jo.

Protože ? jo > 0, tedy beze změny nulové hodnoty ze všech volných proměnných můžete snížit funkci Z zvýšením x jo.

Chcete-li přejít na nový referenční plán, musíte odstranit jednu z proměnných ze základu.

Hodnota xj o musí být zvýšena tak, aby žádná z hodnot základních proměnných x i nebyla záporná. Tito.

Existují dva možné případy.

1) Všechny prvky sloupce rozlišení j o jsou nekladné, tzn. ijo? 0. Pokud při řešení úlohy pro min (max) jsou v řádku indexu kladné (záporné) odhady volných proměnných a ve sloupci proměnné xj o není jediný kladný prvek, pak účelová funkce není zdola (shora) omezen na množinu přípustných plánů problému.

2) Pokud jsou mezi prvky ve sloupci rozlišení kladné, pak lze x jo zvyšovat, dokud není porušen systém nerovností:

Odtud se dostáváme

Nechat tento výraz je splněno, když i=i o , pak

Pokud je podmínka splněna pro několik i, pak lze vybrat libovolné i o. Čára i o se nazývá permisivní, prvek se nazývá permisivní.

Nová hodnota účelové funkce:

V důsledku transformací se účelová funkce snížila. Nyní je potřeba novou základní proměnnou vyjádřit pomocí volných proměnných a dosadit do systému omezení a účelové funkce. Navíc se stará základní proměnná uvolní.

Pravidla simplexní transformace:

1) Najděte největší kladný (nebo záporný) prvek v řádku indexu simplexní tabulky. Sloupec odpovídající tomuto prvku je povolený.

2) Vypočítejte poměr volných členů rovnice ke kladným prvkům kolony rozlišení. Tento postoj se nazývá simplexní relace. Najděte nejmenší z simplexních vztahů, která odpovídá rozlišovacímu řetězci.

3) Na průsečíku rozlišovací řady a rozlišovacího sloupce je rozlišovací prvek. Pokud existuje několik simplexních relací stejné velikosti, vyberte kteroukoli z nich.

4) Neznámé prvky odpovídající aktivačnímu sloupci a řádku jsou prohozeny.

5) Přejděte k další tabulce. Řetězcové prvky rozlišení nový stůl budou rovné

6) Prvky sloupce rozlišení jsou rovny nule, kromě toho, že x jo - základní hodnota.

7) Všechny ostatní prvky se nalézají podle vzorců

Pro vyhledání prvků ve zdrojové tabulce se vybere obdélník, jehož vrcholy jsou prvky potřebné pro výpočet. Diagonála obsahující rozlišovací a hledaný prvek nové tabulky se nazývá hlavní a druhá se nazývá vedlejší. Od součinu úhlových prvků hlavní úhlopříčky se odečte součin úhlových prvků vedlejší úhlopříčky a výsledné číslo se vydělí rozlišovacím prvkem. Toto je pravidlo obdélníku.

8) vypočítat prvky řádku indexu

Chcete-li ovládat výpočty, můžete vypočítat

9) Algoritmus pokračuje, dokud není dosaženo podmínky optimality.

a) Referenční návrh poskytuje minimální hodnotu cílové funkci, pokud jsou všechny odhady volných proměnných pro ni nekladné.

b) Referenční návrh poskytuje maximální hodnotu cílové funkci, pokud jsou všechny odhady volných proměnných nezáporné.

Příklad:Řešení úlohy lineárního programování pomocí simplexní metody

Optimální plán X (7;0;0;42;2) a Z(x)=72.

Příklad problému s umělým základem.

Převeďme problém do kanonické podoby:

Do 2. a 3. rovnice zavádíme umělé proměnné:

Vytvoříme simplexní tabulku:

Tabulkový pohled na PPP. Simplex - tabulky.

JEDNODUCHÁ METODA ŘEŠENÍ ZLP

3.1. obecné charakteristiky a hlavní fáze simplexové metody

Zakladateli simplexové metody jsou sovětský matematik L.V. Kantorovič a americký matematik J. Dantzig.

Pomocí simplexové metody můžete vyřešit jakýkoli problém nebo objevit jeho neřešitelnost. Mnoho speciálních tříd problémů lze řešit jinými metodami, které jsou pro tyto třídy efektivnější. Výhodou simplexové metody je však její univerzálnost. Téměř všechny počítače byly vyvinuty standardní programyřešit ZLP simplexovou metodou.

Pojďme si popsat hlavní myšlenka simplexní metoda.

Věříme, že ZLP je zapsán v kanonická forma a cílovou funkci je třeba minimalizovat. Jak již víme, optimální plán je třeba hledat mezi základními plány ZLP. Simplexová metoda neprochází všemi referenčními plány (což by vzhledem k jejich velkému počtu často nebylo možné), ale počínaje od nějakého počátečního referenčního plánu postupně přechází na další referenční plány s poklesem účelové funkce. Simplexová metoda přestane fungovat, když je buď nalezen optimální referenční plán, nebo je zjištěna neřešitelnost problému.

Při rozhodování ZLP simplexovou metodou lze rozlišit Další kroky:

1) převedení ZLP do kanonické podoby;

2) redukce systému lineárních rovnic na Jordanův tvar s nezápornými pravými stranami při současné kontrole neřešitelnosti LLP kvůli nekonzistenci systému lineárních omezení;

3) studie referenčního plánu optimality;

4) studium ZLP pro nerozhodnutelnost v důsledku neohraničenosti zdola na ODD účelové funkce;

5) přechod na nový, „lepší“ referenční plán.

Pro redukci a organizaci záznamů při řešení problému simplexovou metodou se používají tzv. simplexní tabulky. Pro použití simplexní tabulky je nutné ZLP zredukovat na tabulkovou formu. Dělá se to takhle.

Nechť je ZLP psán v kanonické podobě (2.3-2.5). Pro přinášení PAPů V tabulkové formě musí být systém (2.4) nejprve zredukován na Jordanovu formu s nezápornými pravými stranami. Předpokládejme, že tento Jordanův tvar má tvar (2.6). Vyjádřeme z (2.6) základní proměnné pomocí volných:

Dosazením do účelové funkce (2.3) místo základních proměnných jejich vyjádření prostřednictvím volných proměnných podle vzorců (3.1) tím vyloučíme základní proměnné z účelové funkce. Účelová funkce bude mít tvar:

V tabulková formaúčelová funkce je zapsána takto:

Kde .

Poznámka následující funkce tabulková forma PPP:

a) soustava lineárních rovnic je redukována do Jordanova tvaru s nezápornými pravými stranami;

b) z účelové funkce jsou vyloučeny bazické proměnné a je zapsána ve tvaru (3.3).

Přejděme nyní k popisu simplexní tabulky. Nechť je ZLP zapsán v tabulkové formě:

(3.4)

Hotová simplexová tabulka pak vypadá takto.