Model lineárního programování v obchodování. Teoretické aspekty lineárního programování. Matematický popis modelu lineárního programování

Matematické programování("plánování") je odvětví matematiky, které se zabývá vývojem metod pro nalezení extrémních hodnot funkce, jejíž argumenty podléhají omezením. Idea lineární programování vznikl v roce 1939, kdy vyšla brožura Leonida Vitalieviče Kantoroviče. Matematické metody organizace a plánování výroby." Americký matematik A. Danzig v roce 1947 vyvinul velmi účinnou specifickou metodu pro numerické řešení úloh lineárního programování (tzv. simplexní metoda ).

Další prezentace materiálu předpokládá, že studenti studovali teorii lineárního programování v kurzu matematiky. Proto se doporučuje spojit čtení této kapitoly s prohlížením prezentací. Elektronické verze prezentací jsou umístěny ve složce „Lineární programování“. Část materiálu je zároveň určena k obnovení znalostí získaných v kurzu matematiky a část k jejich rozšíření a prohloubení s důrazem na aplikované schopnosti teoretických modelů.

Teorie lineárního programování

Obecné vyjádření problému

Myšlenka lineárního programování je prezentována ve formátu prezentace, elektronická verze které se nacházejí v souboru „Idea - Linear Programming“.

Geometrická interpretace a metoda grafického řešení

Pro řešení problémů lineárního programování je vhodné použít grafickou metodu:

1. Řešit úlohy se dvěma proměnnými, kdy jsou omezení vyjádřena nerovnicemi.

2. Řešení problémů s mnoha proměnnými za předpokladu, že jejich kanonický zápis neobsahuje více než dvě volné proměnné.

Geometrická metodařešení problémů lineárního programování jsou prezentována v prezentačním formátu - soubor “Geometric LP method”

2.2. simplexní metoda, obecné charakteristiky, kritérium optimality pro přípustný základní plán

Grafická metodařešení úlohy lineárního programování ukazuje, že optimální řešení této úlohy je vždy spojeno s rohovým bodem prostoru řešení (v matematice se také nazývá extrémní bod sestavy ). Tohle je klíčová myšlenka při vývoji společného algebraická simplexová metoda vyřešit jakýkoli problém lineárního programování.

Přechod od geometrické metody řešení úlohy lineárního programování k simplexní metodě spočívá v algebraickém popisu krajních bodů prostoru řešení. Chcete-li implementovat tento přechod, musíte nejprve převést problém lineárního programování do standardní (kanonické) podoby:

· přeměnit nerovnosti omezení na rovnosti zavedením dalších proměnných;

· převést volné proměnné na nezáporné;

· transformovat problém maximalizace na problém minimalizace.

Standardní forma úlohy lineárního programování je nezbytná, protože nám umožňuje získat základní řešení(pomocí systému rovnic generovaných omezeními). Toto (algebraické) základní řešení zcela určuje všechny (geometrické) extrémní body prostoru řešení. Simplexová metoda umožňuje efektivně najít optimální řešení mezi všemi základními.

Své znalosti o řešení úloh simplexovou metodou si můžete obnovit pomocí prezentace „Simplexová metoda“.

Dvojité problémy

Jakýkoli problém lineárního programování má dvojí povahu. Pravidlo pro konstrukci duálního problému:

Pokud je původní problém na max, pak je duální problém na min a naopak.

V duálním problému existuje tolik proměnných, kolik je omezení v původní formulaci. V tomto případě proměnné odpovídají omezením a naopak.

Kurzy Objektivní funkce duálního problému jsou pravé strany omezení původního problému.

Matici omezujících koeficientů duálního problému získáme transpozicí matice omezujících koeficientů původního problému.

Pravé strany omezení duálního problému jsou koeficienty účelové funkce původního problému.

Omezení nerovnosti původního problému odpovídají nezáporným proměnným duálního problému a omezení rovnosti odpovídají proměnným libovolného znaménka a naopak.

Věta 1: Pokud má původní problém optimální plán x*, pak má duální problém také optimální plán y* a hodnoty funkcí na těchto plánech jsou stejné: f(x*)=g(y* ).

Věta 2: Jestliže původní a duální problémy mají plány, pak mají také optimální plány a f(x*)=g(y*).

Kritéria optimalizace pro duální problémy:

Znak 1: Pokud původní a duální problémy mají plány X a Y a f(X)=g(Y), pak jsou tyto plány optimální.

Definice: Omezení umístěná na stejném řádku v diagramu dvojice duálních problémů se nazývají konjugované.

Znak 2: Aby plány X a Y původního a duálního problému byly optimální, je nutné a postačující, aby na těchto plánech byla alespoň jedna z každé dvojice konjugovaných omezení rovnost.

Druhá vlastnost umožňuje při znalosti optimálního plánu jednoho z úkolů najít optimální plán jiného úkolu.

Hlavní ustanovení duálního problému jsou uvedena v prezentacích „Teorie duality“ a „ Duální problém».

Přepravní úkoly

Dopravní problém je jedním z nejběžnějších problémů speciálního lineárního programování. První přísná výroba dopravní problém patří F. Hitchcockovi a první přesná metodařešení vyvinuli L. V. Kantorovich a M. K. Gavurin.

Pod názvem „problém s dopravou“ se skrývá široký kruh problémy s jednotným matematickým modelem. Tyto úlohy patří k úlohám lineárního programování a lze je řešit pomocí simplexní metody. Matice systému omezení dopravního problému je však natolik unikátní, že byly vyvinuty speciální metody k jejímu řešení. Tyto metody jako simplexní metoda, dovolte nám najít iniciálu referenční roztok a poté jeho vylepšením získat optimální řešení.

Pojem „přepravní úkoly“ označuje širokou škálu úkolů nejen dopravního charakteru. To, co mají společné, je zpravidla rozdělení zdrojů, které drží m výrobci (dodavatelé), podle n spotřebitelé těchto zdrojů. Existují dva typy dopravních problémů: podle nákladové kritérium(plán dopravy je optimální při dosažení minimálních nákladů na jeho realizaci) a podle časového kritéria(plán je optimální, pokud je na jeho realizaci vynaloženo minimum času).

Nejběžnější úkoly související s dopravou jsou:

· Připojení spotřebitelů zdrojů k producentům;

· propojení výchozích míst s cílovými místy;

· vzájemné propojení dopředných a zpětných toků nákladu;

· jednotlivé úkoly optimální zatížení průmyslové vybavení;

· optimální distribuce objemy průmyslové výroby mezi výrobními závody atd.

Příkazy úloh typu transport, algoritmy pro jejich řešení a příklady praktické využití prezentováno ve třech prezentacích:

1. „Zobecněný dopravní problém (λ-problém).“

2. „Problém s uzavřenou dopravou. Metoda potenciálů“.

3. "Složité formulace dopravního problému."

Ekonomické aplikace

Různé ekonomické aplikace matematické modelování Uvažujme metody lineárního programování na příkladech formulace konkrétních formulací aplikovaných problémů (vypůjčených z kurzu přednášek A. P. Diyazitdinové).

Problém 1

Pro udržení normálních životních funkcí musí člověk zkonzumovat minimálně 120 konvenčních jednotek bílkovin (arb. jednotek), tuků – minimálně 70 a vitamínů – minimálně 10 konvenčních jednotek denně. Jednotky Jejich obsah v každé jednotce produktů P 1 a P 2 je rovno (0,2; 0,075; 0) a (0,1; 0,1; 0,1) arb. Jednotky

Cena 1 jednotka. produkt P 1-2 rub., P 2–3 rub.

Sestavte matematický model problému, který vám umožní organizovat výživu tak, aby její náklady byly minimální a tělo dostávalo potřebné množství živin.

Problém 2

Osobní a rychlíky odjíždějí z bodu A do bodu B každý den. Údaje o organizaci dopravy jsou následující:

Kolik rychlých a osobních vlaků musí být vytvořeno k přepravě největší počet cestující?

Problém 3

Čtyři sklady zeleniny zásobují každý den tři obchody bramborami. Prodejny podaly nabídky na 17, 12 a 32 tun. Sklady zeleniny mají kapacitu 20, 20, 15 a 25 tun. Tarify (v jednotkách za 1 tunu) jsou uvedeny v následující tabulce:

Problém 4

Existují dva sklady pro hotové výrobky: A 1 a A 2 se zásobami homogenního nákladu 200 a 300 tun. Tento náklad musí být doručen třem spotřebitelům V 1 , V 2 a V 3 v množství 100, 150 a 250 tun. Náklady na přepravu 1 tuny nákladu ze skladu A 1 spotřebitelů V 1 , V 2 a V 3 se rovná 5, 3,6 jednotkám a ze skladu A 2 ke stejným spotřebitelům – 3, 4, 2 jednotky. respektive.

Vytvořte plán přepravy, který minimalizuje celkové náklady na přepravu.

Problém 5

Při výkrmu by každé zvíře mělo dostat alespoň 9 jednotek. bílkoviny, 8 jednotek. sacharidů a 11 jednotek. protein. Pro sestavení jídelníčku se používají dva druhy krmiv, uvedené v následující tabulce.

Cena 1 kg krmiva prvního druhu je 4,00, druhého 6,00.

Vytvořte si denní výživový plán s minimálními náklady.

Problém 6

Farma má následující zdroje: plocha - 100 jednotek, pracovní síla - 120 jednotek, trakce - 80 jednotek. Farma vyrábí čtyři druhy produktů: P 1 , P 2 , P 3 a P 4. Organizaci výroby charakterizuje následující tabulka:

Vypracujte plán výroby, který farmě zajistí maximální zisk.

Úkol 7.

Dílna vyrábí dva typy transformátorů. K výrobě obou typů transformátorů se používá železo a drát. Celková zásoba železa je 3 tuny, drát - 18 tun. Jeden transformátor prvního typu spotřebuje 5 kg železa a 3 kg drátu a jeden transformátor druhého typu 3 kg železa a 2 kg drátu. Za každý prodaný transformátor prvního typu získá závod zisk 3 jednotky, z druhého - 4 jednotky.

Vypracujte plán výroby transformátorů, které závodu zajistí maximální zisk.

Problém 8

Státní statek vyčlenil tři pozemky o výměře 5000, 8000 a 9000 hektarů pro pěstování žita, pšenice a kukuřice. Průměrný výnos v centech na 1 hektar polí je uveden v následující tabulce:

Plodiny	Pole
já	II	III
žito
pšenice
kukuřice

Za 1 cent žita obdrží státní statek 2 CU, za 1 cent pšenice – 2,8 CU, za 1 cent kukuřice – 1,4 CU. Kolik hektarů a na jakých plochách by měl státní statek věnovat každé plodině, aby měl maximální výnos, je-li podle plánu povinen dodat minimálně 1900 tun žita, 158 000 tun pšenice a 30 000 tun kukuřice?

Problém 9

Směs je vyrobena ze tří výrobků – I, II, III. Směs musí obsahovat minimálně 6 jednotek. chemická látka A, 8 jednotek. – látky B a nejméně 12 jednotek. látky C. Struktura chemických látek je uvedena v následující tabulce:

Produkt	Chemický obsah v 1 jednotce. produkty	Cena 1 jednotka. produkty
A	V	S
já
II
III		1,5		2,5

Vytvořte co nejlevnější směs.

Problém 10

Škola pořádá soutěž o nejlepší nástěnné noviny. Jeden student dostal následující úkol:

koupit akvarelovou barvu za cenu 30 rublů. za krabičku, barevné tužky za 20,00. na krabici, pravítka za 12 rublů, poznámkové bloky za 10 rublů;

Musíte si koupit alespoň tři krabice barev, tolik sešitů, kolik je krabic tužek a barev dohromady, ne více než pět pravítek. Na nákupy je přiděleno nejméně 300 rublů.

V jakém množství má student nakoupit uvedené položky, aby celkový počet položek byl minimální?

Problém 11

K dispozici jsou tři specializované opravny motorů. Jejich výrobní kapacity se rovnají 100, 700, 980 oprav ročně, resp. V pěti oblastech obsluhovaných těmito dílnami je potřeba oprav 90, 180, 150, 120, 80 motorů ročně. Náklady na přepravu jednoho motoru z okresů do dílen jsou následující:

Okresy	Workshopy
	4,5	3,7	8,3
	2,1	4,3	2,4
	7,5	7,1	4,2
	5,3	1,2	6,2
	4,1	6,7	3,1

Naplánujte počet oprav pro každou dílnu pro každou oblast, abyste minimalizovali celkové náklady na dopravu.

Problém 12

Ropná rafinerie odebírá čtyři polotovary: 400 tisíc litrů alkylátu, 250 tisíc litrů krakovaného benzínu, 350 tisíc litrů benzínu pro přímou destilaci a 100 tisíc litrů izopentonu. V důsledku smíchání těchto čtyř složek v různých poměrech vzniknou tři třídy leteckého benzínu: benzín A-2:3:5:2, benzín B-3:1:2:1, benzín C-2:2:1 :3. Náklady na 1 000 litrů těchto typů benzínu jsou charakterizovány čísly 120 rublů, 100 rublů, 150 rublů.

Vypracujte plán výroby různých druhů leteckého benzinu na základě podmínky získání maximálních nákladů na všechny produkty.

Problém 13

Pro účast v soutěžích musí sportovní klub postavit družstvo složené ze sportovců kategorie I. a II. Soutěže se konají v Bugu, vysoké sponě a skoku dalekém. 5 sportovců se musí zúčastnit běhu, 8 sportovců ve skoku dalekém a ne více než 10 ve skoku vysokém Počet bodů garantovaných sportovci v každé kategorii je uveden v tabulce:

Rozdělte sportovce do týmů tak, aby součet bodů týmu byl největší, pokud je známo, že pouze 10 sportovců v týmu má první kategorii.

Problém 14

Kožešinová farma chová černé a hnědé lišky a polární lišky. Na kožešinové farmě je 10 000 klecí. V jedné kleci mohou být buď 2 lišky nebo 1 polární liška. Podle plánu by na farmě mělo být minimálně 3000 lišek a 6000 lišek polárních. Za jeden den je nutné dát každé lišce 4 jednotky potravy a každé polární lišky – 5 jednotek. Farma nemůže mít více než 200 000 jednotek krmiva denně. Z prodeje jedné kůže lišky obdrží farma zisk 10,00 az prodeje jedné kůže polární lišky - 5,00.

Kolik lišek a polárních lišek by se mělo chovat na farmě, abyste získali co největší zisk?

Problém 15

K dispozici jsou dva výtahy, které skladují 4 200 a 1 200 tun obilí. Obilí je potřeba dopravit do tří pekáren v množství 1000, 2000 a 1600 tun každé. Vzdálenost od výtahu k pekárně je uvedena v následující tabulce:

Náklady na přepravu 1 tuny produktu na 1 km jsou 25 CU. Naplánujte si přepravu obilí, abyste minimalizovali přepravní náklady.

Problém 16

Ze dvou jakostí benzinu se vytvoří dvě směsi - A a B. Směs A obsahuje 60 % benzinu 1. třídy a 40 % 2. třídy; směs B – 80 % 1. stupeň a 20 % 2. stupeň. Cena 1 kg směsi A je 10 eur a směsi B 12 eur.

Vytvořte si plán tvorby směsí, které budou mít za následek maximální příjem, pokud je k dispozici 50 tun benzinu 1. stupně a 30 t benzinu druhého stupně.

Problém 17

Existují dvě půdně-klimatické zóny, jejichž výměra je 0,8 a 0,6 milionu hektarů. Údaje o výnosech zrna jsou uvedeny v tabulce:

Určete velikost osevních ploch ozimých a jarních plodin nutných k dosažení maximálního produkčního výnosu v hodnotovém vyjádření.

Problém 18

Závod vyrábí čtyři druhy výrobků. Z prodeje 1 ks. Za každý produkt získá závod zisk 2, 1, 3, 5, resp. Na výrobu produktů se vynakládají tři druhy zdrojů: energie, materiály a práce.

Údaje o technologický postup jsou uvedeny v následující tabulce:

Plánujte výrobu tak, aby zisk z jejich prodeje byl co největší.

Výše diskutované modely lze klasifikovat jako statické modely lineárního programování, protože v nich byl pevný časový interval. Pokud je potřeba najít řešení pro jiný časový interval, pak je potřeba znovu zadat data do modelu a provést nová optimalizace. Jinými slovy, ve výše uvedeném přístupu se předpokládalo, že všechny časové intervaly jsou nezávislé a pro každý časový interval musí být vyřešen jeho vlastní optimalizační problém.
V dynamické modely Chování systému je uvažováno v několika časových intervalech a hledání řešení se provádí jednou, optimalizuje se chování modelu ve všech časových intervalech najednou.
Dynamické modely jsou realističtější a mnohé přiměřeněji popisují výrobní situace. Závislost rozhodování na chování systému v čase činí dynamické modely výhradně užitečná metoda ekonomická analýza, ale ve své formulaci jsou mnohem složitější než statické, obsahují zpravidla velké množství proměnných a vyžadují určitou zručnost při sestavování tabulkového modelu.
Jako příklad uveďme prakticky významný model řízení zásob (jiný název pro tento model je vícefázové modely řízení zásob). Pro obecnost výsledků nebudeme parametrům přiřazovat číselné hodnoty. Po sestavení modelu bude možné specifikovat explicitní hodnoty parametrů a získat numerické řešení.

Příklad 3.10
Představte si chemickou společnost, která vyrábí polyuretan. Výrobce má objednávky na dodávky polyuretanu v množství d i tun měsíčně na další čtyři měsíce (i=1,2,…,4). Náklady na výrobu jedné tuny polyuretanu nechť jsou C i tisíc rublů a maximální objem výroby polyuretanu za měsíc je omezen a rovná se K i tunám za měsíc. Výrobní společnost má možnost skladovat výrobky ve skladu a náklady na skladování jedné tuny výrobků za měsíc jsou n i tisíc rublů. V počátečním období byla zásoba polyuretanu ve skladu L 0 tun. Manažer společnosti potřebuje sestavit měsíční plán výroby polyuretanu, který zajistí plnění zakázek s minimálními náklady na výrobu a skladování produktu.
Řešení
Všimněte si, že pokud by nebylo možné skladovat produkty ve skladu, pak by se úkol rozdělil na čtyři nezávislé statické úkoly a ztratil by pro nás veškerý význam.
Vytvořme rovnici materiálové bilance, která nám umožní vypočítat množství výrobků uložených na skladě během i-tého měsíce. Nechť x i je množství vyrobeného polyuretanu i-tý čas doba. Pak během prvního měsíce bude zásoba ve skladu rovna L 1 = L 0 +x 1 -d 1. Inventář druhého měsíce

Pokračováním v tomto procesu je snadné jej získat obecný vzorec inventář pro libovolný časový interval:

. (3.24)
Poté, co jsme odvodili rovnici (3.24), která popisuje chování zásob, je snadné zapsat matematický model problému:

(3.25)
Uvedený problém (3.25) je typickým problémem lineárního programování a lze jej pomocí programu poměrně snadno vyřešit Hledání řešení. Použití číselných hodnot jednotkových výrobních nákladů

a požadovaný objem dodávek a výrobní kapacity po měsících
Je třeba sestavit optimální plán výroby polyuretanu, pokud k 1. lednu byla zásoba polyuretanu ve skladu 15 tun.

Tabulkový modelúkoly řízení zásob
Tabulkový model úlohy po nalezení optimálního řešení je na Obr. 21.

Rýže. 21. Tabulkový model problému dynamické programování

Je třeba říci několik slov o zprávě o stabilitě pro tento model, která je znázorněna na obr. 22.

Rýže. 22. Zpráva o stabilitě pro dynamický model

Pokud se použije jednoduché omezení hodnoty optimalizovaných proměnných (v našem případě x i ≤ K i), pak se ve zprávě o udržitelnosti stínové ceny pro tato omezení umístí do sloupce normalizovaných nákladů a informace o přijatelném rozsahu stínu ceny za tato omezení se nezobrazují. Pokud tedy v lednu zvýšíte výrobní kapacitu o jednu tunu, celkové náklady se sníží o 1,7 tisíc rublů.
Vyžaduje další vysvětlení a sloupec Cílový poměr zpráva o udržitelnosti. Dáno zde Excelové hodnoty počítá sám. Význam cílového koeficientu pro proměnnou je ten, že ukazuje, jak moc se bude hodnota cílové funkce zvyšovat se zvyšováním optimální hodnotu variabilní na jednotku.
To lze snadno ověřit v praxi. Optimální hodnota pro výrobu polyuretanu v lednu je 60 tun a celkové náklady jsou 4 776,45 tisíc rublů. Pokud dosadíme jako optimální hodnotu pro leden číslo 61 a přepočteme celkové náklady, dostaneme novou hodnotu - 4 805,50. Rozdíl mezi těmito čísly je přesně roven 29,05 – cílový koeficient pro proměnnou objem výroby v lednu.
Jiné formulace problémů dynamického programování jsou také široce známé. Některé z nich (model výměny zařízení a investiční model) budou probrány v praktických hodinách. Model lineárního programování– včetně modelu lineární funkce cíle definované lineární závislost na několika proměnných a lineární omezení těchto proměnných.

Extrémní výzvy

Připomeňme si to latinské slovo extrém znamená "extrémní". V matematice má dva specifické významy: maximum(zkráceně max) - největší a minimální(zkráceně min) - nejméně. V tomto chápání extrém má více úzký význam, jak optimální, přeloženo z latiny jako „nejlepší“.
Problém najít maximum resp minimální hodnota danou funkci na dané množině se nazývá extrémní problém.
Existují dva typy extrémních problémů – maximální problém a minimální problém. Symbolicky jsou napsány takto:

Je volána funkce f(x). cílová funkce a X - soubor možných řešení. Optimální řešení problémy se nazývá dvojice (x*,f(x*)), kde x* je maximální (minimum) bod a f(x*) je hodnota funkce f v tomto bodě, tedy její maximum ( minimální) hodnotu na sadě X.
Řešení problémů znamená: buď najít optimální řešení; nebo se ujistěte, že optimální řešení neexistuje.
Řešení problému vyžaduje vyřešení tří problémů: 1) problém existence optimálního řešení; 2) problém stanovení nezbytných a dostatečných znaků optimality (tj. charakteristických vlastností, které jsou vlastní maximálním a minimálním bodům); 3) problém numerického výpočtu optimálních řešení.

Příklad č. 1. Sestavte matematický model následujícího problému ekonomické aktivity. Pro tohle:

1. Identifikujte problém a formulujte účel výzkumu.
2. Proveďte popis proměnných ekonomického procesu nebo objektu.
3. Zapište matematickou formulaci cílové funkce.
4. Formulujte omezení vyplývající z podmínek problému a zapište systém omezení.
5. Navrhněte způsob řešení.

Konstruktéři automobilů mají za úkol navrhnout co nejlevnější karoserii listový materiál, sklo a plast. Hlavní charakteristiky materiálů jsou uvedeny v tabulce.

Charakteristika	Materiály
	Kov	Sklenka	Plastický
Náklady (tisíc rublů/m2)	25	20	40
Hmotnost (kg/m2)	10	15	3

Celková plocha karoserie (včetně dveří a oken) musí být 14 m2: z toho nejméně 3,5 m2 a ne více než 5 m2 by mělo být přiděleno pod sklo. Hmotnost těla by neměla přesáhnout 150 kg a hmotnost plastu by neměla přesáhnout 20 % hmotnosti těla. Kovová složka povrchu těla musí být minimálně dvakrát větší než plocha skla. Kolik kovu, skla a plastu by měl použít nejlepší design.

Problém je omezené zdroje pro optimální výsledky.

Popis proměnných.
x 1 - množství kovu, m 2
x 2 - množství skla, m 2
x 3 - množství plastu, m 2

Cílová funkce.

Omezení:

• Celkový povrch těla
  x 1 + x 2 + x 3 ≥ 14
• Požadavky na sklo
  x 2 ≥ 3,5
  x 2 ≤ 5
• Omezení hmotnosti
  10x 1 + 15x 2 + 3x 3 ≤ 150
• Požadavky na hmotnost plastu
  3x 3 ≤ (10x 1 + 15x 2 + 3x 3)*20 %
• Omezení povrchu
  x 1 ≥ 2x 2

Systém omezení.
x 1 + x 2 + x 3 ≥ 14
10x 1 + 15x 2 + 3x 3 ≤ 150
2x 1 + 3x 2 - 2,4x 3 ≥ 0
x 1 - 2x 2 ≥ 0
x 2 ≥ 3,5
x 2 ≤ 5
x 1, x 2, x 2 ≥ 0
F(x) = 25x 1 + 20x 2 + 40x 3 → min

Příklad č. 2. Továrna vyrábí tkaniny ze dvou výrobků. Každá z těchto tkanin prochází sekvenčním zpracováním na třech typech strojů. Níže jsou uvedeny: produktivita každého typu stroje při výrobě tkanin podle článků 1 a 2; celkové kapacity strojový park závodu za jeden pracovní týden; mzdové náklady na obsluhu strojů v minutách pracovní doby za 1 hodinu provozu stroje; cena metru látky za každý artikl. Je také známo, že týdenní pracovní zdroj pro servis strojů je 14 800 hodin.

Typ stroje	Výkon (tisíc hodin)	Mzdové náklady (min/h)	Produktivita, m/h
			Článek 1	Článek 2
1	22	10	20	15
2	40	6	12	6
3	75	6	6	4
Cena 1 m látky (tisíc rublů)			18	25

Je nutné vypracovat týdenní plán výroby tkanin, aby se maximalizoval zisk vyrobených výrobků, pokud je zaplacena 1 hodina ve výši 5400 rublů a 1 hodina prostoje stroje 1. typu je 1800 rublů, 2. typu je 2000 rublů, 3. typu je 1400 rublů . Náklady na suroviny se neberou v úvahu. Při řešení problému je třeba vzít v úvahu, že výstup tkaniny předmětu 1 musí být alespoň 2krát vyšší než výstup tkaniny předmětu 2.

Popis proměnných.
x 1 - výroba tkanin článek 1,m
x 2 - výroba tkanin článek 2,m

y 1 - doba provozu 1. stroje, hod.
y 2 - doba provozu 2. stroje, hod.
y 3 - doba provozu 3. stroje, hod.

yi = x 1/20 + x 2/15
y2 = x 1/12 + x 2/6
y3 = x 1/6 + x 2/4
x 1, x 2, y 1, y 2, y 3 ≥ 0

Omezení:

• podle výstupní struktury
  x 1 ≥ 2x 2
• podle mzdových nákladů
  10/60y 1 + 6/60y 2 +6/60y 3 ≤ 14800
  nebo
  1/6 let 1 + 1/10 let 2 +1/10 let 3 ≤ 14800
• dle dostupných kapacit:
  y 1 ≤ 22 000
  y2 ≤ 40 000
  y 3 ≤ 75 000

Cílová funkce.
Zisk = Výnosy - Náklady = Cena*Množství - Náklady na prostoje stroje - Mzdové náklady
Tržby = 18x 1 + 25x 2
Náklady na prostoje stroje = 1,8 roku 1 + 2 roky 1 + 1,4 roku 3
Mzdové náklady = 5,4 (1/6y 1 + 1/10y 2 +1/10y 3)

F(x) = 18x 1 + 25x 2 - 1,8y 1 - 2y 2 - 1,4y 3 - 5,4(1/6y 1 + 1/10y 2 +1/10y 3)→ max.
nebo
F(x) = 1/50 (900x 1 +1250x 2 -135y 1 -127y 2 -97y 3) → max.

S přihlédnutím
yi = x 1/20 + x 2/15
y2 = x 1/12 + x 2/6
y3 = x 1/6 + x 2/4

my máme:

Systém omezení.
x 1 ≥ 2x 2
1/6(x 1/20 + x 2/15) + 1/10 (x 1/12 + x 2/6) +1/10 (x 1/6 + x 2/4) ≤ 14800
x 1/20 + x 2 /15≤ 22 000
x 1/12 + x 2 /6 ≤ 40 000
x 1/6 + x 2 /4 ≤ 75 000

x 1 ≥ 2x 2
x 1/30+19x 2/360 ≤ 14800
x 1/20 + x 2 /15≤ 22 000
x 1/12 + x 2 /6 ≤ 40 000
x 1/6 + x 2 /4 ≤ 75 000

F(x) = 17,33x 1 +23,91x 2 → max

Příklad č. 3. Podnik má dvě dílny. První dílna zaměstnává 50 pracovníků, 20 z nich má 6. kategorii a 30 má třetí kategorii. Ve druhé dílně má ze 100 pracovníků 50 6. kategorii a zbytek má třetí. Na výrobu 2 druhů dílů je nutné dokončit objednávku. Dělník 6. kategorie stráví výrobou jednoho dílu prvního typu 10 minut a pracovník 3. kategorie 15 minut. Výrobou jednoho dílu druhého typu stráví pracovník 6. kategorie 25 minut a pracovník třetí kategorie 30 minut.
13) vypracovat plán výroby pro každou z dílen na týden, vycházející ze standardní doby trvání pracovního týdne, maximalizovat celkový objem výroby s přihlédnutím k tomu, že potřeba dílů druhého typu je poloviční. stejně jako potřeba dílů prvního typu.
14) Stanovte výrobní plán pro každou z dílen na týden na základě standardní délky pracovního týdne, maximalizujte zisk, s přihlédnutím ke skutečnosti, že pracovník 6. kategorie dostává 300 rublů měsíčně a pracovník 3. kategorie dostává 200 rublů/měsíc, a to přesto, že prodejní cena dílu 1. typu je 20 rublů/kus a druhého typu 34 rublů/kus.

Řešení.
x 11 - počet dílů typu 1 vyrobených pracovníky 6. kategorie za týden,
x 12 - počet dílů typu 2 vyrobených pracovníky 6. kategorie za týden,
x 21 - počet dílů typu 1 vyrobených pracovníky kategorie 3 za týden,
x 22 - počet dílů typu 2 vyrobených pracovníky kategorie 3 za týden,

13) Objektivní funkce
20x 11 + 50x 21 + 30x 12 + 50x 22 = max.

Omezení:
2(x 12 + x 22) ≤ x 11 + x 21

14) Objektivní funkce: Zisk = Výnosy - Náklady = Počet dílů * Prodejní cena - Mzda zaměstnanců
Náklady na mzdy pracovníků se sníží na týdenní, to znamená, že měsíční výdělek vydělíme 4.
F(x) = 20(20x 11 + 50x 21) + 23(30x 12 + 50x 22) - [(20+50)*300 + (30+50)*200]/4 = max.

Omezení:
2(x 12 + x 22) ≤ x 11 + x 21
10/60x 11 + 15/60x 21 + 25/60x 11 + 30/60x 21 ≤ N
N - týdenní časový fond v hodinách.

Lineární programování je jedním z prvních a nejdůkladněji prostudovaných oborů matematického programování. Právě lineární programování bylo úsekem, ze kterého se začala vyvíjet samotná disciplína „matematické programování“. Pojem „programování“ v názvu disciplíny nemá nic společného s pojmem „programování (tj. sestavování programů) pro počítač“, protože disciplína „lineární programování“ vznikla ještě před dobou, kdy se začaly široce používat počítače. při řešení matematických a inženýrských problémů, ekonomických a dalších problémů. Termín „lineární programování“ vznikl jako výsledek nepřesného překladu anglického „linear programming“. Jedním z významů slova „programování“ je vytváření plánů, plánování. Proto, správný překlad„lineární programování“ by nebylo „lineární programování“, ale „lineární plánování“, které přesněji odráží obsah disciplíny. Nicméně termín lineární programování, nelineární programování atp. se staly v naší literatuře obecně akceptovány.

Lineární programování tedy vzniklo po druhé světové válce a začalo se rychle rozvíjet a přitahovalo pozornost matematiků, ekonomů a inženýrů díky možnosti široké praktická aplikace, stejně jako matematická „harmonie“.

Můžeme říci, že lineární programování je použitelné pro konstrukci matematické modely ty procesy, které mohou být založeny na hypotéze lineárního zobrazení reálný svět: ekonomické úkoly, úkoly řízení a plánování, optimální umístění vybavení atd.

Problémy lineárního programování jsou problémy, ve kterých jsou jak účelová funkce, tak omezení ve formě rovností a nerovností lineární. Stručně, problém lineárního programování lze formulovat následovně: najděte vektor hodnot proměnných, které poskytují extrém lineární účelové funkce pod m omezeními ve formě lineárních rovností nebo nerovností.

Lineární programování je nejčastěji používanou optimalizační metodou. Problémy lineárního programování zahrnují následující:

• · racionální použití suroviny a zásoby; problémy optimalizace řezání;
• · optimalizace výrobního programu podniků;
• · optimální umístění a koncentrace výroby;
• · sestavení optimální plán doprava, přepravní práce;
• · řízení zásob;
• · a mnoho dalších spadajících do oblasti optimálního plánování.

Podle amerických expertů tedy asi 75 % z celkového počtu používaných optimalizačních metod tvoří lineární programování. Přibližně čtvrtinu času stráveného na počítači minulé roky provádět vědecký výzkum, se věnoval řešení úloh lineárního programování a jejich četným modifikacím.

Formulace optimalizačního problému předpokládá existenci konkurenčních vlastností procesu, například:

• množství výrobků - spotřeba surovin
• kvantita výrobků - kvalita výrobků

Volba kompromisní varianty pro zadané vlastnosti je postupem řešení optimalizačního problému.

Při nastavování problému s optimalizací musíte:

1. Dostupnost objektu optimalizace a cíl optimalizace. Navíc formulace každého optimalizačního problému by měla vyžadovat extrémní hodnotu pouze jedné hodnoty, tzn. Současně by systému neměla být přiřazena dvě nebo více optimalizačních kritérií, protože Téměř vždy extrém jednoho kritéria neodpovídá extrému jiného. Uveďme příklady.

Typický příklad nesprávné formulace optimalizačního problému:

"Dostat maximální výkon za minimální náklady."

Chyba spočívá v tom, že úkolem je najít optimalitu 2 hodnot, které si ve své podstatě odporují.

Správná formulace problému by mohla být následující:

• a) získat maximální produktivitu při daných nákladech;
• b) získat minimální náklady pro danou produktivitu;

V prvním případě je kritériem optimalizace produktivita a ve druhém náklady.

• 2. Dostupnost optimalizačních prostředků, která je chápána jako možnost výběru hodnot některých parametrů optimalizovaného objektu.
• 3. Možnost kvantitativního posouzení optimalizované hodnoty, neboť pouze v tomto případě je možné porovnat účinky volby určitých kontrolních akcí.
• 4. Zvážení omezení.

Obvykle se optimalizovaná hodnota vztahuje k efektivitě provozu daného objektu (zařízení, dílny, závodu). Optimalizovaná verze provozu objektu musí být posouzena nějakým kvantitativním měřítkem - kritériem optimality.

Kritérium optimality se nazývá kvantifikace optimalizovaná kvalita objektu.

Na základě zvoleného kritéria optimality se sestaví účelová funkce, která představuje závislost kritéria optimality na parametrech ovlivňujících jeho hodnotu. Je určen typ kritéria optimality nebo účelové funkce konkrétní úkol optimalizace.

Optimalizační problém je tedy redukován na nalezení extrému účelové funkce.

V závislosti na jeho formulaci lze vyřešit kterýkoli z optimalizačních problémů různé metody, a naopak – k řešení mnoha problémů lze použít jakoukoli metodu. Metody optimalizace mohou být skalární (optimalizace se provádí podle jednoho kritéria), vektorové (optimalizace se provádí podle mnoha kritérií), vyhledávací (včetně metod pravidelného a náhodného vyhledávání), analytické (metody diferenciální počet, metody variačního počtu atd.), výpočetní (založené na matematické programování, které mohou být lineární, nelineární, diskrétní, dynamické, stochastické, heuristické atd.), pravděpodobnostně teoretické, herně teoretické atd. Problémy s omezeními nebo bez nich lze optimalizovat.

Ekonomický a matematický model každého problému lineárního programování zahrnuje: objektivní funkci, jejíž optimální hodnotu (maximum nebo minimum) je třeba najít; omezení v podobě systému lineární rovnice nebo nerovnosti; požadavek nezápornosti proměnných.

V obecný pohled model je napsán takto:

Objektivní funkce:

V tomto případě mají aij, bi, cj () konstantní hodnoty.

Problém je najít optimální hodnotu funkce (1.1) za podmínek (1.2) a (1.3).

Systém omezení (1.2) se nazývá funkční omezení problému a omezení (1.3) se nazývají přímé.

Vektor, který splňuje podmínky (1.2) a (1.3), se nazývá přípustné řešení (plán) úlohy lineárního programování. Plán, ve kterém funkce (1.1) dosáhne své maximální (minimální) hodnoty, se nazývá optimální.

MATEMATICKÝ POPIS MODELU LINEÁRNÍHO PROGRAMOVÁNÍ

MODEL LINEÁRNÍHO PROGRAMOVÁNÍ

1 Matematický popis modely lineárního programování

2 Metody implementace modelů lineárního programování

3 Problém duálního lineárního programování

Model lineárního programování(LP) nastává, pokud ve studovaném systému (objektu) existují omezení proměnných a účelové funkce lineární.

LP modely se používají k řešení dvou hlavních typů aplikovaných problémů:

1) optimální plánování ve všech oblastech lidské činnosti – sociální, ekonomické, vědecké, technické a vojenské. Například při optimálním plánování výroby: rozdělování finančních, pracovních a jiných zdrojů, zásobování surovinami, řízení zásob atp.

2) dopravní problém (nalezení optimálního plánu pro různé druhy dopravy, optimální plán distribuce různé prostředky podle předmětů pro různé účely a tak dále.)

MATEMATICKÝ POPIS MODELU LINEÁRNÍHO PROGRAMOVÁNÍ

Je potřeba najít nezáporné hodnoty proměnné

uspokojování lineárních omezení ve formě rovností a nerovností

,

Kde - daná čísla,

a poskytnutí extrému lineární účelové funkce

,

kde jsou daná čísla, která se zapisuje ve tvaru

Platné řešení nazývá se jakákoli sbírka , splňující podmínky.

Rozsah možných řešení– soubor všech možných řešení.

Optimální řešení
, pro který .

Poznámky

1. Daný model LP je Všeobecné. Jsou tu také Standard A kanonický formy LP modelů.

2. Podmínky existence implementace modelu LP:

– sada možných řešení není prázdná;

- Objektivní funkce je omezena (alespoň shora při hledání maxima a zdola při hledání minima).

3.LP je založen na dvou větách

Věta 1. hromada G, definovaný systémem omezení formy, je konvexní uzavřená množina ( konvexní mnohostěn s rohovými body - vrcholy.)

Věta 2. Lineární forma , definovaný na konvexním mnohostěnu

j=1,2,…,s

i=s+1,s+2,…, m,

dosáhne extrému v jednom z vrcholů tohoto mnohostěnu.

Tato věta se nazývá teorém lineárního tvaru.

V souladu s Weierstrassovou větou je optimální řešení jedinečné a je globálním extrémem.

Existuje obecný analytický přístup k implementaci modelu LP - simplexní metoda. Při řešení úloh lineárního programování poměrně často neexistuje žádné řešení. To se děje z následujících důvodů.

Ukažme si první důvod na příkladu

Z tohoto důvodu říkají, že omezení jsou neslučitelná. Oblast možných řešení je prázdná množina.

Druhý důvod ilustruje následující příklad:

V v tomto případě, rozsah proveditelných řešení není shora omezen. Rozsah možných řešení není omezen.

V návaznosti na tradice lineárního programování dáme problému LP ekonomickou interpretaci. Nechte nás mít k dispozici m typy zdrojů. Množství typu zdroje j rovná se . Tyto zdroje jsou potřebné pro výrobu n druhy zboží. Množství tohoto zboží označme symboly respektive. Typ jednotky i náklady . Výroba zboží typu i by měla být omezena hodnotami respektive. Pro výrobu jednotky typu výrobku i typ zdroje je spotřebován j. Je nutné stanovit takový plán výroby zboží ( ), aby jejich celkové náklady byly minimální.

Problémy lineárního programování používané k optimalizaci fungování reálných objektů obsahují značné množství proměnných a omezení. To znemožňuje jejich řešení grafické metody. Na velké číslo proměnné a omezení, používají se algebraické metody, které jsou založeny na iterativních výpočetních postupech. V lineárním programování bylo vyvinuto mnoho algebraických metod, lišících se metodami konstrukce počátečního proveditelného řešení a podmínkami pro přechod z jedné iterace do druhé. Všechny tyto metody však vycházejí z obecných teoretických principů.

Shodnost základních teoretických principů vede k tomu, že algebraické metody řešení úloh lineárního programování jsou si do značné míry podobné. Zejména téměř každý z nich vyžaduje předběžnou redukci problému lineárního programování na standardní (kanonickou) formu.

Algebraické metody pro řešení problému LP začínají jeho redukcí na standardní (kanonická) forma:

,

,

i=1,..,n;j=1,..,m.

Jakýkoli problém lineárního programování lze redukovat na standardní forma. Srovnání obecný model s kanonickým modelem nám umožňuje dospět k závěru, že pro převedení problému LP do standardní podoby je nutné zaprvé přejít od systému nerovností k rovnostem a zadruhé transformovat všechny proměnné tak, aby byly nezáporné .

Přechod na rovnosti se provádí přidáním nezáporné zbytkové proměnné na levou stranu omezení pro nerovnosti typu a odečtením nezáporné redundantní proměnné z levé strany pro nerovnosti typu . Například nerovnost při přechodu do standardního tvaru se převede na rovnost , nerovnost - do rovnosti . V tomto případě jsou reziduální i redundantní proměnná nezáporné.

Předpokládá se, že pravá část nerovnosti nejsou negativní. Jinak toho lze dosáhnout vynásobením obou stran nerovnosti „-1“ a změnou jejího znaménka na opačné.

Pokud v původní problém lineárního programování, proměnná není omezena znaménkem, lze ji reprezentovat jako rozdíl dvou nezáporných proměnných , Kde .

Důležitá vlastnost proměnných je to pro jakékoli přijatelné řešení pouze jeden z nich může mít kladnou hodnotu. To znamená, že pokud , Že a naopak. Proto ji lze považovat za reziduální a - za nadbytečnou proměnnou.

Příklad Nechť je dán problém lineárního programování:

,

.

Je třeba jej uvést do standardní podoby. Všimněte si, že první nerovnost původní úlohy má znaménko , proto je nutné do ní zavést reziduální proměnnou. V důsledku toho dostaneme.

Druhá nerovnost má znaménko a pro převod do standardního tvaru vyžaduje po provedení této operace zavedení redundantní proměnné, získáme .

Navíc proměnná není omezena znaménkem. Proto musí být v účelové funkci i v obou omezeních nahrazen rozdílem . Po provedení substituce získáme problém lineárního programování ve standardním tvaru, ekvivalentní původnímu problému:

.

Problém lineárního programování, napsaný ve standardní formě, je problém nalezení extrému účelové funkce na množině vektorů, které jsou řešením systému lineárních rovnic beroucí v úvahu podmínky nezápornosti. Jak je známo, systém lineárních rovnic nemusí mít žádná řešení, mít jediné řešení nebo mít nekonečný počet řešení. Optimalizace účelové funkce je možná pouze v případě, že systém má nekonečno mnoho řešení. Systém lineárních rovnic má nekonečný počet řešení, pokud je konzistentní (hodnost hlavní matice rovna hodnosti rozšířené) a pokud je hodnost hlavní matice menší než počet neznámých.

Nechť je hodnost matice omezovacího systému rovna m. To znamená, že matice má alespoň jednu vedlejší mřádu nerovná nule. Bez ztráty obecnosti můžeme předpokládat, že nezletilá se nachází vlevo horní roh matrice. Toho lze vždy dosáhnout změnou číslování proměnných. Tato nenulová vedlejší hodnosti m se obvykle nazývá základní. Vytvořme systém od prvního m rovnice soustavy a zapište ji takto:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .