Rovnice v celých číslech. Najděte celočíselná řešení soustavy rovnic s více neznámými než rovnice

Obvykle v úkolech lineární programování Souřadnice plánu nemusí být celá čísla. V praxi se však často setkáváme s problémy, ve kterých musí být souřadnice optimálních plánů celá čísla, a takové problémy se nazývají problémy . Při řešení úloh lineárního programování pomocí grafické metody a simplexové metody není zaručeno, že souřadnice optimálního plánu budou celá čísla.

V některých případech mohou být výsledky zaokrouhleny. Pokud například optimální plán stanoví, že by se mělo vyrobit 499683,3 vozů, pak je ekonomicky oprávněné zaokrouhlit výsledek na 499683 nebo dokonce na 500 000.

Existují však problémy, kdy takové zaokrouhlování může způsobit velkou chybu. Pokud například optimální plán stanoví, že by se mělo postavit 0,67 elektrárny, pak je formální zaokrouhlení na 0 nebo 1 nepřijatelné.

Proto skvělé praktický význam mít metody pro řešení problémů lineárního programování, se kterými můžete najít optimální plán, jehož souřadnice jsou celá čísla. Úkoly celočíselné programování jsou řešeny právě těmito metodami.

Li problém celočíselného programování stanovené v kanonická forma, je formulován takto:

najít maximum účelové funkce (lineární forma)

pod systémem omezení

Tedy úkol celočíselné programování a odpovídající problém lineárního programování se liší pouze podmínkou, že neznámé jsou celé číslo.

Stejně jako problémy lineárního programování, problémy celočíselného programování vyžadují, aby optimální plán maximalizoval účelovou funkci (lineární formu).

Gomoriho metoda pro řešení problémů celočíselného programování

Gomoriho metoda je univerzální metodařešení úloh celočíselného programování, s jejichž pomocí po konečném počtu iterací najdete optimální plán nebo se ujistíte, že problém nemá řešení. Praktická hodnota Gomoriho metody je však velmi omezená, protože při řešení problémů je potřeba provést poměrně hodně iterací.

Při řešení úloh celočíselného programování pomocí Gomoriho metody jsou z množiny optimálních plánů úlohy lineárního programování postupně odstraněny podmnožiny, které neobsahují celočíselné plány.

V první iteraci musíte vyřešit problém lineárního programování pomocí simplexní metody. Pokud nalezené neznámé splňují celočíselný požadavek, je problém celočíselného programování vyřešen. Pokud mezi neznámými neznámými je alespoň jedna zlomkové číslo, pak by se mělo skládat dodatečná podmínka(jak jej poskládat - více níže) a připojit jej k systému omezení problému celočíselného programování. Ze sady plánů je tedy odstraněna podmnožina, která neobsahuje celočíselné plány. Pokud je optimální plán takto rozšířeného problému celočíselný, je problém celočíselného programování vyřešen. Proces řešení pokračuje, dokud se v nějaké iteraci nenajde celočíselný optimální plán nebo se neověří, že problém nemá řešení.

Nyní si povíme, jak zmíněnou dodatečnou podmínku vytvořit. To, další podmínka, se získá z jedné z rovnic systému omezení z koeficientů neznámých a samotných neznámých podle vzorce

, kde ve složených závorkách jsou zlomkové části volného členu a koeficienty neznámých, resp.

Například od simplexní stůl dostaneme následující rovnici:

.

Zlomkovou část volného členu získáme odečtením jeho celé části od samotného čísla takto:

Podobně získáme zlomkové části koeficientů pro neznámé:

(na X3 ),

(na X4 ).

A obecné pravidlo nález zlomkové části je: celá část reálné číslo A Největší celé číslo se nazývá [ A], nepřesahující A; zlomková část reálného čísla A nazývaný rozdíl {A} = A - [A] samotné číslo A a celá jeho část [ A] .

.

V našem příkladu s použitím výše uvedeného vzorce získáme následující rovnici:

.

Příklad 1. Vyřešte následující problém celočíselného programování pomocí Gomoriho metody. Najděte maximum Objektivní funkce

pod systémem omezení

Řešení. Úlohu řešíme simplexovou metodou. Od té doby, co máme lekce řešení úloh lineárního programování simplexovou metodou, nebude zde vysvětlována samotná metoda, ale budou uvedeny pouze simplexní tabulky.

Další neznámé X3 A X4 Berme to jako základní. Vyjádřeme základní neznámé a cílovou funkci pomocí nebázických proměnných:

Vytvořme simplexní tabulku z koeficientů:

Sestavujeme následující tabulky, dokud nezískáme optimální plán:

Tabulka 3
Základní neznámé	Volní členové	Volné neznámé		Pomocné koeficienty
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
S	65/7	10/7	1/7	1/2

Z tabulky 3 najdeme optimální plán . Protože tento optimální plán nesplňuje celočíselnou podmínku, musíme vytvořit další podmínku. Zlomková část souřadnice je číslo a zlomková část souřadnice je číslo.

První rovnice založená na tabulce bude zapsána takto:

.

Po určení zlomkových částí koeficientů pro neznámé a volné členy získáme následující další podmínku:

nebo zavedením další proměnné,

.

Dostaneme nový řádek v simplexové tabulce získané z tabulky 3 a sečtením koeficientů z právě získané rovnice:

Tabulka 4
Základní neznámé	Volní členové	Volné neznámé		Pomocné koeficienty
		X3	X4
X1	19/7	4/7	-1/7	-1/2
X2	4/7	-1/7	2/7
X5	-5/7	-4/7	-6/7
S	65/7	10/7	1/7	1/2

Dokončíme krok simplexní metody a získáme tabulku:

Tabulka 5
Základní neznámé	Volní členové	Volné neznámé		Pomocné koeficienty
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
S	55/6	4/3	1/6	-1/7

Dostali jsme optimální plán . Tento plán, stejně jako předchozí, nesplňuje celočíselnou podmínku. Proto je opět vyžadována další podmínka. V v tomto případě můžete použít první nebo třetí rovnici. Dostáváme další podmínku:

.

Vytvořme následující tabulku:

Tabulka 6
Základní neznámé	Volní členové	Volné neznámé		Pomocné koeficienty
		X3	X4
X1	17/6	2/3	-1/6	1/7
X2	1/3	-1/3	1/3	-2/7
X4	5/6	2/3	-7/6
X6	-5/6	-2/3	-5/6
S	55/6	4/3	1/6	-1/7

Optimální plán vycházíme z následující finálové tabulky:

Tabulka 7
Základní neznámé	Volní členové	Volné neznámé		Pomocné koeficienty
		X3	X6
X1	3	4/5	-1/5	1/6
X2	0	-3/5	2/5	-1/3
X4	2	8/5	-7/5	7/6
X5	1	4/5	-6/5
S	9	6/5	1/5	-1/6

Protože nalezený optimální plán splňuje celočíselnou podmínku, je problém celočíselného programování vyřešen. Souřadnice X5 A X6 lze ignorovat, protože počáteční podmínky problému obsahují pouze čtyři neznámé. Proto bude konečný optimální plán napsán takto:

,

a maximum cílové funkce je 9.

Metoda větví a vazeb pro řešení úloh celočíselného programování

Metoda větvení a vazby je vhodná pro řešení problémů celočíselného programování, ve kterých je počet neznámých malý nebo se celočíselné požadavky nevztahují na všechny neznámé. Podstatou metody větví a vazeb je, že pro ty neznámé, na které se vztahuje celočíselný požadavek, je nutné určit hranice, ve kterých mohou ležet hodnoty těchto neznámých. Poté se řeší odpovídající problémy lineárního programování.

Určení hranic, ve kterých musí ležet hodnoty neznámých v problému celočíselného programování, lze zapsat následovně:

V praxi jsou v mnoha případech hranice neznámých hodnot již zahrnuty v systému omezení problému celočíselného programování, nebo je lze určit na základě ekonomického obsahu problému. V opačném případě můžeme předpokládat, že spodní mez je , a horní mez je , kde M- poměrně velké kladné číslo.

Jak vám metoda větvení a vazby umožňuje upřesnit hranice přijatelné hodnoty neznámý?

Nejprve je řešen problém lineárního programování odpovídající celočíselnému programovacímu problému, řekněme, pomocí simplexové metody. Nechť je nalezen optimální plán v této úloze a hodnota kterékoli z jeho souřadnic je zlomkové číslo. Poté budete muset vytvořit dva nové problémy lineárního programování. Jak to udělat?

Označme celočíselnou část souřadnice jako . V jednom z nových problémů lineárního programování bude dolní hranicí hodnoty souřadnice číslo , tedy celočíselná část hodnoty souřadnice zvýšená o jednu. Bude se psát takto:

.

V jiném nová úloha lineárního programování, horní mez hodnoty souřadnice bude celočíselnou částí samotné hodnoty souřadnice. Bude to napsáno takto:

Z prvního problému lineárního programování se tak „rozvětvily“ dva nové problémy, ve kterých se změnily hranice přípustných hodnot jedné neznámé. Při řešení každého z těchto problémů jsou možné tři případy:

• optimální plán není celé číslo,
• optimální plán je celočíselný,
• problém nemá řešení.

Pouze v prvním případě je možné „větvit“ nové úkoly výše uvedeným způsobem. Ve druhém a třetím případě se „větvení“ zastaví.

Při každé iteraci řešení celočíselného programovacího problému je vyřešen jeden problém. Představme si pojem: seznam problémů lineárního programování, které je třeba vyřešit. Ze seznamu vyberte problém, který má být vyřešen v odpovídající iteraci. Při dalších iteracích se seznam mění, protože v něm již nejsou zahrnuty vyřešené problémy a místo nich jsou do seznamu zahrnuty nové úkoly, které „odbočily“ z předchozích úkolů.

Aby se omezilo „větvení“, to znamená, že se snížil počet problémů, které je třeba vyřešit, je při každé iteraci nutné určit spodní hranici maximální hodnota cílová funkce. To se provádí následovně:

Podle algoritmu pro řešení celočíselného programovacího problému metodou větve a vazby, na každém p Iterace vyžaduje 4 kroky.

Příklad 2 Vyřešte následující problém celočíselného programování pomocí metody větvení a vazby. Najděte maximum účelové funkce

pod systémem omezení

Řešení. Předpokládejme, že jsou dány nebo určeny následující hranice optimálních hodnot neznámých:

.

Jelikož je úkol zadán v normální forma, má celočíselný design a dolní mez maximální hodnoty účelové funkce.

Seznam úkolů k řešení obsahuje 1. úkol:

Iterace 1.

Krok 1. Používáním simplexní metodařešení prvního problému bylo získáno:

Protože nalezený plán není celé číslo, následuje krok 4.

Krok 4. Protože optimální plán má zlomkovou souřadnici 1,2, pak . Aplikováním hranic na hodnoty neznámých 1. problému získáme nové problémy. Ve 2. úloze je dolní mez pro , a ve 3. úloze je horní mez pro .

Rovnice v celých číslech jsou algebraické rovnice se dvěma nebo více neznámými proměnnými a celočíselnými koeficienty. Řešení takové rovnice jsou všechny celočíselné (někdy přirozené nebo racionální) sady hodnot neznámých proměnných, které splňují rovnici. Takové rovnice se také nazývají diofantina, na počest starověkého řeckého matematika, který studoval některé typy takových rovnic před naším letopočtem.

Za moderní formulaci diofantických úloh vděčíme francouzskému matematikovi. Byl to on, kdo před evropskými matematiky nastolil otázku řešení neurčitých rovnic pouze v celých číslech. Nejznámější rovnicí v celých číslech je poslední Fermatova věta: rovnice

nemá nenulová racionální řešení pro všechna přirozená n > 2.

Teoretický zájem o rovnice v celých číslech je poměrně velký, protože tyto rovnice úzce souvisejí s mnoha problémy v teorii čísel.

V roce 1970 to dokázal leningradský matematik Jurij Vladimirovič Matiyaševič obecná metoda, který umožňuje řešit libovolné diofantické rovnice v celých číslech v konečném počtu kroků, neexistuje a existovat nemůže. Z toho vyplývá pro odlišné typy rovnic, zvolte si vlastní metody řešení.

Při řešení rovnic v celých číslech a přirozená čísla Lze zhruba rozlišit následující metody:

způsob třídění možností;

aplikace euklidovského algoritmu;

reprezentace čísel ve formě pokračování (pokračování) zlomků;

faktorizace;

řešení rovnic v celých číslech jako čtverec (nebo jiný) s ohledem na jakoukoli proměnnou;

reziduální metoda;

metoda nekonečného sestupu.

Problémy s řešením

1. Řešte rovnici x 2 – xy – 2y 2 = 7 v celých číslech.

Zapišme rovnici ve tvaru (x – 2y)(x + y) = 7.

Protože x, y jsou celá čísla, najdeme řešení původní rovnice jako řešení následujících čtyř systémů:

1) x – 2y = 7, x + y = 1;

2) x – 2y = 1, x + y = 7;

3) x – 2y = –7, x + y = –1;

4) x – 2y = –1, x + y = –7.

Po vyřešení těchto soustav získáme řešení rovnice: (3; –2), (5; 2), (–3; 2) a (–5; –2).

Odpověď: (3; –2), (5; 2), (–3; 2), (–5; –2).

a) 20x + 12y = 2013;

b) 5x + 7y = 19;

c) 201x – 1999y = 12.

a) Protože pro libovolné celočíselné hodnoty x a y levá strana rovnice je dělitelná dvěma a pravá ruka je liché číslo, pak rovnice nemá řešení v celých číslech.

Odpověď: neexistují žádná řešení.

b) Nejprve některé vybereme konkrétní řešení. V tomto případě je to jednoduché, např.

x 0 = 1, y 0 = 2.

5x 0 + 7y 0 = 19,

5(x – x 0) + 7(y – y 0) = 0,

5(x – x 0) = –7(y – y 0).

Protože čísla 5 a 7 jsou relativně prvočísla

x – x 0 = 7k, y – y 0 = –5k.

Takže obecné řešení je:

x = 1 + 7k, y = 2 – 5k,

kde k je libovolné celé číslo.

Odpověď: (1+7k; 2–5k), kde k je celé číslo.

c) Hledání konkrétního řešení výběrem je v tomto případě značně obtížné. Použijme euklidovský algoritmus pro čísla 1999 a 201:

GCD(1999, 201) = GCD(201, 190) = GCD(190, 11) = GCD(11, 3) = GCD(3, 2) = GCD(2, 1) = 1.

Napišme tento proces v opačném pořadí:

1 = 2 – 1 = 2 – (3 – 2) = 2 2 – 3 = 2 (11 – 3 3) – 3 = 2 11 – 7 3 = 2 11 – 7 (190 – 11 17) =

121 11 – 7 190 = 121 (201 – 190) – 7 190 = 121 201 – 128 190 =

121·201 – 128(1999 – 9·201) = 1273·201 – 128·1999.

To znamená, že dvojice (1273, 128) je řešením rovnice 201x – 1999y = 1. Potom dvojice čísel

x 0 = 1273 12 = 15276, y 0 = 128 12 = 1536

je řešením rovnice 201x – 1999y = 12.

Obecné řešení této rovnice bude zapsáno ve tvaru

x = 15276 + 1999 k, y = 1536 + 201 k, kde k je celé číslo,

nebo po změně označení (používáme, že 15276 = 1283 + 7 1999, 1536 = 129 + 7 201),

x = 1283 + 1999n, y = 129 + 201n, kde n je celé číslo.

Odpověď: (1283+1999n, 129+201n), kde n je celé číslo.

3. Řešte rovnici v celých číslech:

a) x3 + y3 = 3333333;

b) x 3 + y 3 = 4 (x 2 y + xy 2 + 1).

a) Protože x 3 a y 3 při dělení 9 může dát pouze zbytky 0, 1 a 8 (viz tabulka v části), pak x 3 + y 3 může dát pouze zbytky 0, 1, 2, 7 a 8. Ale číslo 3333333 při dělení 9 dává zbytek 3. Původní rovnice tedy nemá řešení v celých číslech.

b) Přepišme původní rovnici ve tvaru (x + y) 3 = 7(x 2 y + xy 2) + 4. Protože krychle celých čísel při dělení 7 dávají zbytky 0, 1 a 6, ale ne 4, pak rovnice nemá řešení v celých číslech.

Odpověď: Neexistují žádná celočíselná řešení.

a) v prvočíslech rovnice x 2 – 7x – 144 = y 2 – 25y;

b) v celých číslech platí rovnice x + y = x 2 – xy + y 2.

a) Řešte tuto rovnici jako kvadratickou rovnici vzhledem k proměnné y. Dostaneme

y = x + 9 nebo y = 16 – x.

Protože pro liché x je číslo x + 9 sudé, pak jediný pár prvočísla, který splňuje první rovnost, je (2; 11).

Protože x, y jsou jednoduché, pak z rovnosti y = 16 – x máme

2 x 16,2 na 16.

Prohledáváním možností najdeme zbývající řešení: (3; 13), (5; 11), (11; 5), (13; 3).

Odpověď: (2; 11), (3; 13), (5; 11), (11; 5), (13; 3).

b) Považujte tuto rovnici za kvadratická rovnice vzhledem k x:

x 2 – (y + 1) x + y 2 – y = 0.

Diskriminant této rovnice je –3y 2 + 6y + 1. Je kladný pouze pro následující hodnoty y: 0, 1, 2. Pro každou z těchto hodnot získáme z původní rovnice kvadratickou rovnici pro x , což je snadno řešitelné.

Odpověď: (0; 0), (0; 1), (1; 0), (1; 2), (2; 1), (2; 2).

5. Je tam? nekonečné číslo trojice celých čísel x, y, z takové, že x 2 + y 2 + z 2 = x 3 + y 3 + z 3?

Zkusme vybrat trojice, kde y = –z. Pak se y 3 a z 3 vždy navzájem zruší a naše rovnice bude vypadat takto

x 2 + 2 y 2 = x 3

nebo jinak,

x 2 (x–1) = 2y 2 .

Aby dvojice celých čísel (x; y) splnila tuto podmínku, stačí, aby číslo x–1 bylo dvojnásobkem druhé mocniny celého čísla. Takových čísel je nekonečně mnoho, totiž všechna jsou to čísla ve tvaru 2n 2 +1. Dosazením tohoto čísla do x 2 (x–1) = 2y 2 dostaneme po jednoduchých transformacích:

y = xn = n(2n2+1) = 2n3+n.

Všechny takto získané triplety mají tvar (2n 2 +1; 2n 3 +n; –2n 3 – n).

Odpověď: existuje.

6. Najděte celá čísla x, y, z, u taková, že x 2 + y 2 + z 2 + u 2 = 2xyzu.

Číslo x 2 + y 2 + z 2 + u 2 je sudé, tedy mezi čísly x, y, z, u sudé číslo lichá čísla.

Pokud jsou všechna čtyři čísla x, y, z, u lichá, pak x 2 + y 2 + z 2 + u 2 je dělitelné 4, ale 2xyzu není dělitelné 4 - nesoulad.

Pokud jsou právě dvě z čísel x, y, z, u lichá, pak x 2 + y 2 + z 2 + u 2 není dělitelné 4, ale 2xyzu je dělitelné 4 – opět nesoulad.

Proto jsou všechna čísla x, y, z, u sudá. Pak to můžeme napsat

x = 2x 1 , y = 2y 1 , z = 2z 1 , u = 2u 1 ,

a původní rovnice bude mít tvar

x 1 2 + y 1 2 + z 1 2 + u 1 2 = 8x 1 y 1 z 1 u 1 .

Nyní si všimněte, že (2k + 1) 2 = 4k(k + 1) + 1 při dělení 8 dává zbytek 1. Pokud jsou tedy všechna čísla x 1 , y 1 , z 1 , u 1 lichá, pak x 1 2 + y 1 2 + z 1 2 + u 1 2 není dělitelné 8. A pokud jsou právě dvě z těchto čísel lichá, pak x 1 2 + y 1 2 + z 1 2 + u 1 2 není dělitelné ani 4. To znamená

x 1 = 2x 2, y 1 = 2y 2, z 1 = 2z 2, u 1 = 2u 2,

a dostaneme rovnici

x 2 2 + y 2 2 + z 2 2 + u 2 2 = 32x 2 y 2 z 2 u 2 .

Zopakováním stejné úvahy znovu zjistíme, že x, y, z, u jsou pro všechna přirozená n dělitelná 2 n, což je možné pouze pro x = y = z = u = 0.

Odpověď: (0; 0; 0; 0).

7. Dokažte, že rovnice

(x – y) 3 + (y – z) 3 + (z – x) 3 = 30

nemá řešení v celých číslech.

Použijme následující identitu:

(x – y) 3 + (y – z) 3 + (z – x) 3 = 3 (x – y) (y – z) (z – x).

Pak lze původní rovnici zapsat jako

(x – y)(y – z)(z – x) = 10.

Označme a = x – y, b = y – z, c = z – x a výslednou rovnost zapišme ve tvaru

Navíc je zřejmé, že a + b + c = 0. Je snadné ověřit, že až do permutace z rovnosti abc = 10 vyplývá, že čísla |a|, |b|, |c| se rovnají buď 1, 2, 5 nebo 1, 1, 10. Ale ve všech těchto případech je pro jakoukoli volbu znamének a, b, c součet a + b + c nenulový. Původní rovnice tedy nemá celočíselná řešení.

8. Řešte rovnici 1 v celých číslech! + 2! + . . . + x! = y2.

To je zřejmé

pokud x = 1, pak y 2 = 1,

pokud x = 3, pak y2 = 9.

Tyto případy odpovídají další páryčísla:

xi = 1, yi = 1;

x2 = 1, y2 = –1;

x3 = 3, y3 = 3;

x 4 = 3, y 4 = –3.

Všimněte si, že pro x = 2 máme 1! + 2! = 3, pro x = 4 máme 1! + 2! + 3! + 4! = 33 a ani 3 ani 33 nejsou druhé mocniny celých čísel. Pokud x > 5, pak, od

5! + 6! + . . . +x! = 10n,

můžeme to napsat

1! + 2! + 3! + 4! + 5! + . . . +x! = 33 + 10n.

Protože 33 + 10n je číslo končící na 3, není to druhá mocnina celého čísla.

Odpověď: (1; 1), (1; –1), (3; 3), (3; –3).

9. Rozhodněte se následující systém rovnice v přirozených číslech:

a 3 – b 3 – c 3 = 3abc, a 2 = 2(b + c).

3abc > 0, pak a 3 > b 3 + c 3;

tedy máme

Když sečteme tyto nerovnosti, dostaneme to

Vezmeme-li v úvahu poslední nerovnost, získáme to z druhé rovnice soustavy

Ale druhá rovnice systému také ukazuje, že a je sudé číslo. Tedy a = 2, b = c = 1.

Odpověď: (2; 1; 1)

10. Najděte všechny dvojice celých čísel x a y splňující rovnici x 2 + x = y 4 + y 3 + y 2 + y.

Rozložením obou stran této rovnice dostaneme:

x(x + 1) = y(y + 1)(y 2 + 1),

x(x + 1) = (y 2 + y) (y 2 + 1)

Taková rovnost je možná, pokud se levá a pravá strana rovnají nule nebo jsou součinem dvou po sobě jdoucích celých čísel. Když tedy určité faktory přirovnáme k nule, získáme 4 páry požadovaných hodnot proměnných:

xi = 0, yi = 0;

x2 = 0, y2 = –1;

x3 = –1, y3 = 0;

x 4 = –1, y 4 = –1.

Součin (y 2 + y)(y 2 + 1) lze považovat za součin dvou po sobě jdoucích nenulových celých čísel, pouze když y = 2. Proto x(x + 1) = 30, odkud x 5 = 5, x 6 = -6. To znamená, že existují další dva páry celých čísel, které splňují původní rovnici:

x5 = 5, y5 = 2;

x 6 = –6, y 6 = 2.

Odpověď: (0; 0), (0; –1), (–1; 0), (–1; –1), (5; 2), (–6; 2.)

Problémy bez řešení

1. Řešte rovnici v celých číslech:

a) xy = x + y + 3;

b) x 2 + y 2 = x + y + 2.

2. Řešte rovnici v celých číslech:

a) x 3 + 21y2 + 5 = 0;

b) 15x 2 – 7y 2 = 9.

3. Řešte rovnici v přirozených číslech:

a) 2x + 1 = y2;

b) 3 2 x + 1 = y 2.

4. Dokažte, že rovnice x 3 + 3y 3 + 9z 3 = 9xyz v racionálních číslech má jednoznačné řešení

5. Dokažte, že rovnice x 2 + 5 = y 3 v celých číslech nemá řešení.

6 odpovědí

Postupujte podle tohoto příkladu: předpokládejme, že rovnice jsou:

7 = x + 3r + 4z + 9w 12 = 4x + 2y + 3z + 7w

Existují 2 rovnice a 4 neznámé. Jako parametry můžete nastavit 2 neznámé, takže systém bude mít tolik rovnic, kolik je neznámých:

7 - (4z + 9w) = x + 3y 12 - (3z + 7w) = 4x + 2y

X a y budeme používat jako neznámé. Lze to vyřešit a ponechat w a z jako parametry v lineárním řešení:

X = (22 - 3w - z)/10 y = (16 - 29w - 13z)/10

Nyní musíte učinit čitatele dělitelnými 10, jmenovatelem. Pokud existuje řešení, můžete zkontrolovat všechny parametry od 1 do 10.

Obecně uděláte toto:

• Parametry zvolte tak, aby bylo neznámých tolik jako rovnic. Zkuste ponechat neznámé, které generují nejmenší absolutní hodnotu pro determinant (v příkladu to bylo 10, ale výběr y a z by byl lepší, protože by to bylo |det|=3)
• Rozhodni se lineární systém a vytvořit odpověď v závislosti na parametrech
• Zkontrolujte hodnoty parametrů od 1 do absolutní hodnota det (pokud existuje řešení, najdete ho v tomto bodě), dokud nebude existovat celočíselné řešení pro všechny neznámé (proto předtím zvolíte nejmenší hodnotu determinantu) a zkontrolujte, zda je kladné (toto nebylo znázorněno v příklad).

Promiň, jestli je hrubou silou na poslední krok, ale alespoň je možné minimalizovat rozsah testu. Možná Nejlepší způsob vyřešit konečný systém diofantických rovnic, ale neznám žádnou metodu.

UPRAVIT1

Existuje metoda, jak se vyhnout hrubému vynucení poslední části. Opět v příkladu musíte udělat:

22 = 3w + z (shodné, mod 10) 16 = 29w + 13z (shodné, mod 10)

Aplikace modulu:

2 = 3w + z (shodné, mod 10) 6 = 9w + 3z (shodné, mod 10)

Systém kongruence můžete vytvořit trojúhelníkový (Gaussova eliminace) vynásobením kongruence jejím inverzním modulem 10 a sečtením do ostatních. Inverze k 9 modulo 10 je -1, takže vynásobíme poslední kongruenci:

2 = 3w + z (kongruentní, mod 10) -6 = -9w + -3z (kongruentní, mod 10)

Ekvivalent:

2 = 3w + z (kongruentní, mod 10) 4 = w + 7z (kongruentní, mod 10)

Poté vynásobte -3 a přidejte k prvnímu:

2 - 3*4 = 3w + z -3w - 21z (kongruentní, mod 10) 4 = w + 7z (kongruentní, mod 10)

Ekvivalent:

10 = -20z (kongruentní, mod 10) 4 = w + 7z (kongruentní, mod 10)

Pak řešíte shora dolů (tento příklad se zdá být pravdivý pro jakoukoli hodnotu z). Může existovat určitý stupeň volnosti, pokud máte více parametrů než kongruencí, ale jsou ekvivalentní a můžete nastavit redundantní parametry na jakoukoli hodnotu, nejlépe nejmenší hodnotu, rovno 1.

Pokud je ještě něco nejasného, ​​dejte mi vědět!

Pokud správně chápu problém, máte více balíků, každý s jiným poštovným. Toto poštovné chcete zaplatit z množství známek, které máte. Problém můžete vyřešit celým programováním. Níže uvedené řešení řeší všechny balíčky najednou. Budete mít počet proměnných rovný numPackages * numStampDenominations (pravděpodobně nepohodlné pro velké množství balíčky).

Omezení rovnosti vypadá jako Aeqx = beq. Matice Aeq pro dva balíčky se čtyřmi značkami (numVarsnumPackages) vypadá takto:

21 .68 .47 .01 .00 .00 .00 .00 .89 * x = .00 .00 .00 .00 .21 .68 .47 .01 .50

První řádek jsou omezující koeficienty (hodnoty razítka) pro dávku 1. Nenulové koeficienty jsou hodnoty razítka. Proměnná null spojená s jinými balíčky se neřeší.

Druhá sada omezení (nerovnost) se týká skupiny značek, které mám. Omezení nerovnosti vypadá jako A * x = b. Matice A pro 4 razítka a 8 proměnných (numPackages * numStampDenominations) vypadá takto:

1 0 0 0 1 0 0 0 10 0 1 0 0 0 1 0 0 10 * x<= 0 0 1 0 0 0 1 0 10 0 0 0 1 0 0 0 1 20

Nákladová funkce je f"*x, která představuje celkový počet kostek. Její koeficienty jsou jednoduše jednotky zadané jako sloupcový vektor.

V Matlabu běží skript, který řeší problém popsaným způsobem. Pravděpodobně bude formulován v podstatě stejně v oktávách, které GNU nabízí, podobně jako Matlab. Matlab nebo Octave pro vás nemusí být tím správným řešením, ale alespoň vám řeknou, co funguje, a poskytnou vám sandbox pro vývoj řešení.

% Hodnota každého razítka dostupného jako matice 4x1 sv = [.21; 0,68; 0,47; 01]; % Počet každého razítka dostupného jako matice 4x1 sq = ; % Počet demonstrací m = velikost (sv, 1); % Poštovné požadované pro každý balík jako matice 4x1 % -- pravděpodobně přečteno ze souboru poštovné = [.89;.50;1.01;.47;.47]; % Počet balíků -- pouze počet řádků poštovného packageCount = size(postage, 1); % Počet proměnných je m*packageCount numVar = m*packageCount; % dolní hranice -- nulová razítka dané nominální hodnoty lb = zeros(numVar,1); % horní mez -- použijte omezení pro horní mez ub = ; % Funkce nákladů -- minimalizujte počet použitých známek % min(f"*x) f = jedničky(numVar,1); % omezení celého čísla intcon = 1:numVar; % Vytvořte matici omezení poštovného Aeq = zeros(numVar, packageCount ); for i = 1:packagePocet prvni = i*m - 3 posledni = prvni + 3; pro r = 1:m pro j = 1:m c = (j-1)*m + 1; A(c,r) = 1; ", beq, lb, ub)

Zkusil bych následující přístup (všimněte si, že jsem se s tímto problémem nikdy nemusel vypořádat, takže tuto odpověď berte jako pokus o vyřešení problému s vámi namísto skutečné analytické odpovědi).

Jednoduše najdete řešení, jako by to byl normální systém, takže můžete najít nekonečně mnoho řešení:

Příklad:

Y=x+3

pak reálná dvojice čísel (2,5) je možné skutečné řešení pro tento systém, jakmile máte nekonečně mnoho řešení, jednoduše omezíte podmnožinu řešení, která jsou produkována celými čísly.

Samozřejmě máte omezení, v našem případě má řešení pouze 1 volnou proměnnou, takže všechna řešení můžeme napsat takto:

(x, x+3)

Údiv:

Pokud je tam někde iracionální číslo, neexistují žádná celočíselná řešení:

(x, x+pi) => ani 1. ani 2. číslo zde nemůže být zároveň celé

Takže můžete najít celočíselná řešení právě tehdy, pokud je vaše „nekonečně mnoho řešení“ omezeno na celá čísla nebo racionální čísla.

Řekněme, že máte následující vektor:

(3x, (2/5)y, y, x, x+y)

Pak by celé řešení mohlo být:

X = 3 y = 10/2

Pokud máte pocit, že odpověď pro vás není vhodná, řekněte: Smažu ji, abych nezískal bonusové body.

V řadě ekonomických problémů souvisejících s problémy lineárního programování musí být prvky řešení vyjádřeny v celých číslech. V těchto úlohách proměnné znamenají počet jednotek nedělitelných produktů.

Problém celočíselného programování je formulován takto:

Najděte takový plán řešení X=(x 1 , X 2 ,…, X n ) , ve kterém lineární funkce nabývá maximální nebo minimální hodnoty s výhradou omezení

problém je řešen pomocí metod lineárního programování. Pokud se ukáže, že proměnné optimálního řešení nejsou celočíselné, pak pomocí řezných metod nebo metody výčtu celočíselných řešení.

Větev a vázané koncepty .

Metoda větvené a vázané spočívá v uspořádaném hledání možností a zvažování pouze těch, které se podle určitých kritérií ukáží jako slibné, a vyřazení neperspektivních možností.

Metoda větvení a vazby je následující: set přípustná řešení(plány) se nějakým způsobem dělí na podmnožiny, z nichž každá je opět rozdělena na podmnožiny stejným způsobem. Proces do té doby pokračuje. Optimální celočíselné řešení původního problému dosud nebylo získáno.

Název větvené a vázané metody pochází ze skutečnosti, že v procesu řešení problému je postupně „větvena“ a nahrazena jednoduššími. Proces řešení může pokračovat ve formě stromu, jehož čísla v uzlech (vrcholech) označují plán řešení problému (požadované proměnné).

5. 2 Grafická metoda řešení úloh celočíselného programování.

Pokud v problému lineárního programování existují dvě proměnné a v systému omezení jsou nerovnosti, lze to vyřešit graficky bez požadavku na celočíselné proměnné.

Pokud je optimální řešení tohoto problému celé číslo, pak je optimální pro původní problém.

Pokud výsledné optimální řešení není celé číslo, pak se zkonstruuje další lineární omezení. Má následující vlastnosti:

Mělo by být lineární;

Měl by odříznout nalezený optimální neceločíselný plán;

Neměl by zkracovat žádný celočíselný plán.

Algoritmus pro grafické řešení úlohy

celočíselné programování.

Sestrojte souřadnicový systém x 1 0x 2 a vyberte měřítko.

Najděte oblast proveditelných řešení (ADS) systému omezení problému.

Sestrojte účelovou funkci, která je úrovňovou čarou, a označte na ní normální směr.

Posuňte přímku objektivní funkce ve směru normály přes ODR tak, aby se změnila ze sečny na tečnu k ODF a prošla bodem nejvzdálenějším od počátku. Tento bod bude extrémním bodem, tzn. řešení problému.

Pokud se ukáže, že přímka účelové funkce je rovnoběžná s jednou ze stran ODP, pak v tomto případě je extrém dosaženo ve všech bodech odpovídající strany a problém lineárního programování bude mít nekonečný počet řešení .

Najděte v něm souřadnice, extrémní body a hodnotu účelové funkce. Pokud získané hodnoty nejsou celé číslo, přejděte k dalšímu kroku.

Vyberte oblast s celočíselnými hodnotami na těchto souřadnicích.

Určete nové souřadnice a vytvořte graf.

Najděte body s celočíselnými hodnotami požadované proměnné, dosaďte do rovnice účelovou funkci a najděte její hodnotu. Maximum ze získaných hodnot účelové funkce bude řešením problému.