Описание на презентацията на отделни слайдове:
1 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P. Moshchevikin, 2004 Линейно програмиране Към този клас линейно програмиране(75% от задачите, решени от американците) включват задачи, в които целевата функция Wm(x), m=1,2,...,M, ограничения под формата на равенства hk(x)=0, k=1, 2... K, а неравенствата gj(x)>0, j=1,2,...J, са линейни и математическо решение. Възможни теми на задачите на ЛП: рационално използване на суровини и материали; рязане на оптимизационни задачи; оптимизиране на производствената програма на предприятията; оптимално разполагане и концентрация на производството; да състави оптимален план за транспортиране, транспортна експлоатация; управление на инвентара; и много други, принадлежащи към областта на оптималното планиране. Задаване на проблема с LP (дефиниране на индикатора за ефективност, променливи на задачата, настройка на линейната целева функция W(x) да бъде минимизирана или максимизирана, функционални hk(x), gj(x) и регионални xli 2 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P. Moshchevikin, 2004 Пример за проблем с LP Пример - Оптимизиране на местоположението на странична продукция на горско стопанство Горското стопанство разполага с 24 хектара свободна земя под угар и се интересува от извличане на приходи от нея. Може да отглежда разсад от бързорастящо хибридно коледно дърво, което достига зрялост за една година, или гоби, отклонявайки част от земята за пасища. Дръвчетата се отглеждат и продават на партиди от 1000 бр. Необходими са 1,5 ха за отглеждане на една партида дървета и 4 ха за изхранване на един бик. Горският район може да прекарва само 200 часа годишно в страничното си производство. Практиката показва, че обработката, отсичането, отсичането и свързването на една партида дървета отнема 20 часа. Грижата за един бик също отнема 20 часа, за целта горското стопанство има възможност да похарчи 6 хиляди рубли. Годишните разходи за една партида дървета възлизат на 150 рубли. и 1,2 хиляди рубли. за един бик. Вече има сключен договор за доставка на 2 бика. По текущи цени едно коледно дърво ще донесе печалба от 2,5 рубли, един бик - 5 хиляди рубли. 3 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P. Moshchevikin, 2004 Изложение на проблема 1. Като показател за ефективност е препоръчително да се вземе печалбата на операция (годишна печалба от земята в рубли). 2. Като контролирани променливи на задачата трябва да се приемат: x1 - броят на угоените бикове за година; x2 - броят на отглежданите партиди бързорастящи коледни елхи, 1000 бр. всеки на година. 3. Целева функция: 5000 x1 + 2500 x2 max, където 5000 е нетният доход от един бик, rub.; 2500 - нетен доход от една партида дървета (1000 броя за 2,5 рубли). 4. Ограничения: 4.1. По земеползване, ha: 4 x1 + 1,5 x2 24 4.2. Според бюджета, рубли: 1200 x1 + 150 x2 6000 4.3. По трудови ресурси, h: 20 x1 + 20 x2 200 4.4. Задължения по договора, бр.: x1 2 4.5. Граници на площта: x1 0, x2 0 4 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P. Moshchevikin, 2004 Графично решение на проблема с LP Показване на графиката на линиите, съответстващи на следните уравнения, 4 x1 + 1,5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x2 = 200 x1 = 2 x2 = 0 засенчваме областта, в точките на която са изпълнени всички ограничения. Всяка такава точка се нарича допустимо решение, а множеството от всички допустими решения се нарича допустима област. Очевидно решението на задачата LP се състои в намиране на най-доброто решение в допустимата област, което от своя страна се нарича оптимално. В този пример оптималното решение е осъществимо решение, което максимизира функцията W=5000 x1 + 2500 x2. Стойността на целевата функция, съответстваща на оптималното решение, се нарича оптимална стойност на задачата на ЛП. 5 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P.Moshchevikin, 2004 Графично решение на проблема с LP 6 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P. Moshchevikin, 2004 Графично решение на проблема с LP Изброяването на всички ъглови точки от областта на възможните решения води до намиране на максимален доход в размер на 34 хиляди рубли. (W=5000x1+2500x2), които горското стопанство може да извлече чрез отглеждане на 3,6 вола и 6,4 партиди коледни елхи. Целочислените методи (например изброяване) дават x1=3 и x2=6, което води до доход от 30 хиляди рубли, x1=4 и x2=5 води до по-оптимален резултат от 32,5 хиляди рубли, точка x1 =3 и x2=7 води до подобен резултат. Поради голямото измерение на реалните практически задачи на LP, графичният метод се използва рядко, но позволява ясно да се разбере едно от основните свойства на LP - ако има оптимално решение в проблема с LP, тогава поне едно от върхове на допустимата област е оптимално решение. Въпреки факта, че допустимата област на проблема с LP се състои от безкраен брой точки, оптималното решение винаги може да бъде намерено чрез целенасочено изброяване на краен брой от неговите върхове. Симплексният метод за решаване на проблема с LP, разгледан по-долу, се основава на това фундаментално свойство. 7 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P.Moshchevikin, 2004 Решаване на проблема с LP в MS Excel Една от вградените функции на редактора на електронни таблици на MS Excel (необходимо е да поставите отметка в квадратчето по време на инсталирането на MS Office) е „Търсене на решение“ . Този пакет ви позволява бързо да решавате проблеми с линейно и нелинейно програмиране. 8 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P. Moshchevikin, 2004 Проблемът на LP в стандартна форма Проблемът LP в стандартна форма с m ограничения и n променливи има следната форма: W = c1x1 + c2x2 + ... + cnxn min (max) под ограниченията a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 В матрична форма W = cx min (max) при ограничения Ax = b; x0; b0, където A е матрица с размерност m*n, x е вектор колона от променливи с размерност n*1, b е вектор колона на ресурси с размерност m*1, с е вектор ред от оценки на LP задача 1*n. 9 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P.Moshchevikin, 2004 Трансформация на неравенства Ограниченията на неравенствата могат да бъдат трансформирани в равенства чрез въвеждане на така наречените остатъчни или излишни променливи. Уравнението от предишния пример 4x1 + 1,5x2 24 може да бъде преобразувано в равенство, като се използва неотрицателната остатъчна променлива 4x1 + 1,5x2 + x3 = 24. Променливата x3 е неотрицателна и съответства на разликата между дясното и лявото страни на неравенството. По подобен начин x1 2 може да се трансформира чрез въвеждане на излишна променлива x4: x1 - x4 = 2. 10 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P. Moshchevikin, 2004 г. по знак на променливи Трансформация на променливи без знак Променливи, които приемат както положителни, така и отрицателни стойности, трябва да бъдат заменени с разликата на две неотрицателни: x = x+ - x-; x+0; x- 0. Пример. 3x1+4x2+5x3+4x4 max 2x1+x2+3x3+5x4 5 5x1+3x2+x3+2x4 20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 = знак -3x1-4x2+5x3-4x4 min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; x4 = знак ; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+x8 -x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 min 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x7 = 15 x1,x2,x3,x4,x5,x6,x70; x8 заменен с x4 11 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P. Moshchevikin, 2004 Симплексен LP метод Симплексният метод е итеративна процедура за решаване на LP проблеми, написани в стандартна форма, системата от уравнения, в която и с помощта на елементарни операции върху матрици се свежда до канонична форма: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. Променливите x1, x2,...,xm, влизащи с единични коефициенти само в едно уравнение на системата и с нулеви коефициенти в останалите, се наричат основни. В каноничната система всяко уравнение съответства на точно една основна променлива. Останалите n-m променливи (xm+1, ...,xn) се наричат небазисни променливи. За да се доведе системата до канонична форма, могат да се използват два вида елементарни операции върху низове: Умножение на всяко уравнение на системата с положително или отрицателно число. Добавяне към всяко уравнение на друго уравнение на системата, умножено по положително или отрицателно число. 12 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P. Moshchevikin, 2004 Simplex-method LP Записване на проблема под формата на уравнения x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. се записва идентично под формата на матрици 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . .. . . .. . .. . .. .. 0 0 .. 1 am,m+1 .. ams .. amn xn bm 13 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P. Moshchevikin, 2004 Алгоритъм на симплексния метод 1. Изберете първоначално допустимо основно решение. Базово решение е решение, получено с нулеви стойности на неосновни променливи, т.е. xi=0, i=m+1,...,n. Базовото решение се нарича допустимо основно решение, ако стойностите на основните променливи, включени в него, са неотрицателни, т.е. xj = bj 0, j=1,2,...,m. В този случай целевата функция ще приеме следната форма: W=cbxb=c1b1+c2b2+...+cmbm. Попълваме началната таблица на симплексния метод: 14 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P.Moshchevikin, 2004 Алгоритъм на симплексния метод 2. Изчислете вектора на относителните оценки c, като използвате правилото за точков продукт cj = cj - cbSj, където cb е векторът на оценките на основните променливи; Sj е j-тата колона на коефициентите aij в каноничната система, съответстваща на разглеждания базис. Допълваме началната таблица с c - линия. 15 слайд
Описание на слайда:
Теория за вземане на решения PetrSU, A.P. Moshchevikin, 2004 Алгоритъм на симплексния метод). Намерено решение. 4. В противен случай е необходимо да се въведе небазисна променлива xr с най-голяма стойност cj в базата вместо една от основните променливи (виж таблицата). 16 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P. Moshchevikin, 2004 Алгоритъм на симплексния метод 5. Използвайки правилото за минималното съотношение min(bi/air), ние определяме променливата xp, получена от основата. Ако коефициентът air е отрицателен, тогава bi/air=. В резултат на това пресечната точка на колоната, съдържаща входната неосновна променлива xr, и реда, съдържащ изходната основна променлива xp, ще определи позицията на водещия елемент на таблицата. 6. Прилагаме елементарни трансформации за получаване на ново приемливо базово решение и нова таблица. В резултат на това опорният елемент трябва да е равен на 1, а останалите елементи на обобщената колона трябва да бъдат зададени на нула. 7. Изчислете нови относителни резултати, като използвате правилото за скаларна трансформация и продължете към стъпка 4. 17 слайд
Описание на слайда:
Теория за вземане на решения на PetrSU, A.P.Moshchevikin, 2004 Пример за решение по симплекс-метод Пример - Оптимизиране на местоположението на странична продукция на горското стопанство 3. Целева функция: 5000 x1 + 2500 x2 max, 4. Ограничения: 4.1. По земеползване, ha: 4 x1 + 1,5 x2 24 4.2. Според бюджета, рубли: 1200 x1 + 150 x2 6000 4.3. По трудови ресурси, h: 20 x1 + 20 x2 200 4.4. Задължения по договора, бр.: x1 2 4.5. Регионални ограничения: x1 0, x2 0 Нека сведем задачата до стандартната форма: 4 x1 + 1,5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6= 2 x1 ... x6 0 Първите три уравнения имат съответно x3, x4, x5 в основната променлива, но в четвъртото то отсъства поради факта, че променливата x6 има отрицателен единичен коефициент. За да редуцираме системата до канонична форма, използваме метода на изкуствените променливи. x1 – x6+x7= 2, въведена изкуствена променлива x7. слайд 2 Методите на линейното програмиране се използват при прогнозни изчисления, при планиране и организиране на производствени процеси. Линейното програмиране е клон на математиката, който изучава методи за изследване и намиране на екстремни стойности на някои линейни функции, чиито аргументи са предмет на линейни ограничения. слайд 3 Такава линейна функция се нарича целева функция, а набор от количествени връзки между променливи, които изразяват определени изисквания на икономически проблем под формата на уравнения или неравенства, се нарича система от ограничения. Думата програмиране е въведена, защото неизвестните променливи обикновено определят програмата или работния план на даден предмет. слайд 4 Множеството от отношения, съдържащи целевата функция и ограниченията върху нейните аргументи, се наричат математически модел на задачата за оптимизация. ЗЛП се изписва в общ вид така: при ограничения слайд 5 Тук - неизвестно, - дадени константи Ограниченията могат да бъдат дадени чрез уравнения. Най-често срещаните задачи са във формата: има ресурси под ограничения. Необходимо е да се определят обемите на тези ресурси, при които целевата функция ще достигне максимум (минимум), т.е. да се намери оптималното разпределение на ограничените ресурси. В този случай има естествени ограничения >0. слайд 6 В този случай екстремумът на целевата функция се търси върху допустимото множество от решения, определени от системата от ограничения, като всички или някои от неравенствата в системата от ограничения могат да бъдат записани под формата на уравнения. Слайд 7 Накратко LLP има формата: под ограничения Слайд 8 За да се състави математически модел на ZLP, е необходимо: 1) да се обозначат променливите; 2) съставете целева функция; 3) запишете системата от ограничения в съответствие с целта на задачата; 4) запишете системата от ограничения, като вземете предвид индикаторите, налични в условието на проблема. Ако всички ограничения на проблема са дадени чрез уравнения, тогава моделът от този тип се нарича каноничен. Ако поне едно от ограниченията е дадено от неравенство, тогава моделът е неканоничен. Слайд 9 проблемът за оптималното разпределение на ресурсите при планирането на продукцията в предприятието (проблемът с асортимента); задачата за максимизиране на продукцията за даден асортимент; проблемът със смесите (дажба, диета и др.); транспортна задача; задачата за рационално използване на наличния капацитет; задача за назначаване. Слайд 10 Да приемем, че предприятието произвежда различни продукти. Производството им изисква различни видове ресурси (суровини, труд и машинно време, спомагателни материали). Тези ресурси са ограничени и възлизат на условни единици в плановия период. Известни са и технологични коефициенти, които показват колко единици от i-тия ресурс са необходими за производството на продукт от j-ти тип. Нека печалбата, получена от предприятието при продажба на единица продукт от j-ти тип, е равна на. В плановия период всички показатели се приемат за постоянни. слайд 11 Необходимо е да се състави такъв план за производство на продукти, при изпълнението на който печалбата на предприятието ще бъде най-голяма. Икономически и математически модел на задачата слайд 12 Целевата функция е общата печалба от продажбата на произведени продукти от всички видове. В този модел на проблема е възможна оптимизация чрез избор на най-печелившите видове продукти. Ограниченията означават, че за нито един от ресурсите общото му потребление за производството на всички видове продукти не надвишава запасите му. слайд 13 Слайд 14 Да приемем, че ще бъдат произведени продукти от тип А, - продукти от тип В и - продукти от тип С. Тогава за производството на такъв брой продукти ще са необходими изразходвани машиночасове на мелнично оборудване. Тъй като общият фонд от работно време на машини от този тип не може да надвишава 120, неравенството трябва да бъде изпълнено слайд 15 Като се аргументираме по подобен начин, можем да съставим система от ограничения слайд 16 Сега нека създадем целева функция. Печалбата от продажбата на продукти от тип A ще бъде 10, от продажбата на продукти от тип B -14 и от продажбата на продукти от тип C-12 Общата печалба от продажбата на всички продукти ще бъде Слайд 17 Така стигаме до следния LLP: Сред всички неотрицателни решения на системата от неравенства се изисква да се намери такова, за което целевата функция приема максимална стойност. Слайд 18 Продуктите на млекопреработвателното предприятие са мляко, кефир и заквасена сметана пакетирани в опаковки. За производството на 1 тон мляко, кефир и заквасена сметана са необходими съответно 1010,1010 и 9450 кг мляко. В същото време цената на работното време при разливането на 1 тон мляко и кефир е 0,18 и 0,19 машиночаса. На опаковането на 1 тон заквасена сметана специалните машини са заети 3,25 часа. Слайд 19 Общо заводът може да използва 136 000 кг мляко за производство на пълномаслени млечни продукти. Основното оборудване може да бъде заето за 21,4 машинни часа, а машините за пакетиране на сметана за 16,25 часа. Печалбата от продажбата на 1 тон мляко, кефир и заквасена сметана съответно е 30, 22 и 136 рубли. Заводът трябва да произвежда най-малко 100 тона бутилирано мляко дневно. Няма ограничения за производството на други продукти. Слайд 20 Необходимо е да се определи какви продукти и в какво количество трябва да произвежда заводът ежедневно, така че печалбата от продажбата му да бъде максимална. Направете математически модел на задачата. слайд 21 Нека заводът произвежда тонове мляко, тонове кефир и тонове сметана. След това му трябва кг мляко. Тъй като растението може да използва не повече от 136 000 кг мляко дневно, неравенството трябва да бъде изпълнено слайд 22 Срокове за опаковане на мляко и кефир и за опаковане на заквасена сметана. Тъй като дневно трябва да се произвеждат поне 100 тона мляко, значи. По отношение на икономиката слайд 23 Общата печалба от продажбата на всички продукти е равна на рубли. Така стигаме до следния проблем: при ограничения Тъй като целевата функция е линейна и ограниченията са дадени от система от неравенства, този проблем е LLP. слайд 24 Има два вида продукти, съдържащи хранителни вещества (мазнини, протеини и др.) Слайд 25 слайд 26 Общата цена на диетата при ограничения, като се вземе предвид необходимия минимум хранителни вещества Слайд 27 Математическо изложение на проблема: направете ежедневна диета, която удовлетворява системата от ограничения и минимизира целевата функция. Най-общо казано, групата задачи за смеси включва проблеми за намиране на най-евтиния набор от определени изходни материали, които осигуряват смес с желани свойства. Получените смеси трябва да съдържат n различни компонента в определени количества, а самите компоненти са съставни части на m изходни материали. Слайд 28 Да въведем означенията: -количеството на j-тия материал, включен в сместа; -цена на материала тип j; е минималното необходимо съдържание на i-тия компонент в сместа. Коефициентите показват специфичното тегло на i-тия компонент в единица от j-тия материал Слайд 29 Целевата функция е общата цена на сместа, а функционалните ограничения са ограниченията върху съдържанието на компонентите в сместа: сместа трябва да съдържа компоненти в обеми не по-малки от посочените. слайд 30 Във фабриката за облекло тъканта може да бъде нарязана по няколко начина, за да се произведат желаните парчета облекло. Нека i-тият тип части се произвеждат с j-тия вариант на рязане и количеството отпадъци в този вариант на рязане е отпадъци. Направете математически модел на задачата. Слайд 31 Решение. Да приемем, че според j-тия вариант се разкрояват стотици тъкани. Тъй като при изрязване на тъканта по j-та опция се получават части от i-тия тип, за всички опции за изрязване от използваните тъкани, общото количество отпадъци за всички опции за изрязване ще бъде Слайд 35 Защита 4. Основният или каноничен LLP е задача, която се състои в определяне на стойността на целевата функция, при условие че системата от ограничения е представена като система от уравнения: слайд 36 Ако е необходимо за удобство или за смисъла на задачата да превключите от една форма на запис към друга, продължете по следния начин. Ако трябва да намерите минимума на функцията, тогава можете да отидете до намирането на максимума, като умножите целевата функция по (-1). Ограничение от тип неравенство може да бъде преобразувано в равенство чрез добавяне на неотрицателна допълнителна променлива към лявата му страна, а ограничение от тип неравенство може да бъде преобразувано в ограничение от равенство чрез изваждане на допълнителна неотрицателна променлива от лявата му страна. Слайд 41 Опорен дизайн се нарича неизроден, ако съдържа m положителни компоненти. В противен случай се нарича изродено. Планът, при който целевата функция на LLP приема своята максимална (минимална) стойност, се нарича оптимален.
Вижте всички слайдове Въведение Линейното програмиране като клон на изследването на операциите има почти четиридесетгодишна история. Въвеждането на компютърните технологии даде значителен тласък на изследванията в тази област на математиката. Бяха разработени редица алгоритми за решаване на проблеми с линейно програмиране, а през следващите години бяха създадени програми и софтуерни пакети, главно за големи компютри. По-голямата част от литературата по линейното програмиране у нас е пуснато през 60-те - 70-те години. Изследванията в тази област (теоретични и приложни) продължават и в момента. Методите на линейното програмиране се оказаха много ефективни за решаване на някои проблеми от областта на изследването на операциите. Ние разбираме думата "програмиране" като планиране и това определя естеството на разглежданите приложения. Основните идеи на линейното програмиране възникват по време на Втората световна война във връзка с търсенето на оптимални стратегии при воденето на военни действия. Оттогава те намират широко приложение в индустрията, търговията и администрацията – както на местно, така и на национално ниво. Тези методи могат да решат много (макар и не всички) проблеми, свързани с ефективното използване на ограничени ресурси. Математическите методи и модели са добре известни, широко разпространени и използвани под различни наименования – математически методи при вземане на решения; методи за изследване на операциите; икономико-математически методи; методи на икономическата кибернетика; методи за оптимално управление, приложна математика в икономиката и организацията на производството и др. В много публикации по тази тема (повече или по-малко изчерпателни) те се разглеждат в различни комбинации. Изследването на операциите е научна дисциплина, която се занимава с разработването и практическото приложение на методи за най-ефективно управление на различни организационни системи. Управлението на всяка система се реализира като процес, който се подчинява на определени закони. Техните знания помагат да се определят условията, необходими и достатъчни за осъществяването на този процес. За да направите това, всички параметри, характеризиращи процеса и външните условия, трябва да бъдат количествено определени и измерени. Следователно целта на изследването на операциите е количествената обосновка на взетите решения относно организацията на управлението. Целта на всяко моделиране е да изследва обекта първо качествено, а след това, с натрупването на информация и развитието на модела, на все по-точни количествени нива. Тези съображения могат да бъдат илюстрирани с прост пример. Имаше (и все още съществува) методът на „теория на вероятностите“ като широк клас математически модели, работещи с понятията „вероятност“, „случайно събитие“, „случайна променлива“, „математическо очакване (средна стойност) на случайна променлива “, „разсейване (разпръскване)” и др. На границата на XIX и XXв. появява се нов обект - комутирана телефонна комуникационна система, с която се свързват понятията "заявление за връзка", "отказ", "време за изчакване на връзката", "комутация" и други характеристики на системата. През 20-те години. А. К. Ерланг свързва този метод и обект; в резултат на това е създаден математически вероятностен модел на процесите в комутируемите телефонни мрежи, който оперира с понятията "поток от поръчки", "средно време на изчакване", "средна дължина на опашката за услуга", "вариация на времето за изчакване", "отказ" вероятност" и др. По-нататъшното развитие на това научно направление показа плодотворността на концептуалната основа на този модел, неговите широки възможности за проектиране. Моделът се разви в метод за изследване на сложни системи - "теория на опашките", чиято терминология и концептуална база бяха абстрахирани от асоциациите с телефонните мрежи и придобиха общотеоретичен характер. И сега могат да бъдат изградени нови модели чрез прилагане на теорията на опашките към други обекти (производствени процеси, компютърни операционни системи, трафик потоци и т.н.). По този начин, от една страна, методът е дефиниран, ако е разработен хомогенен набор от модели, т.е. начини за разглеждане на различни обекти в един аспект, а от друга страна, обектът е известен толкова по-дълбоко, колкото повече обектни модели се разработват . В същото време двойствената природа на модела води до дуализъм на концептуалната основа на моделирането, която включва общи (от „метод”) и специфични (от „обект”) понятия. Изследването на операциите е набор от приложни математически методи, използвани за решаване на практически организационни (включително икономически) проблеми. Това е комплексна научна дисциплина. Кръгът на изследваните от него проблеми не е достатъчно дефиниран. Понякога изследването на операциите се разбира много широко, включвайки редица чисто математически методи, понякога, напротив, много тясно - като практическа техника за решаване на строго определен списък от проблеми с помощта на икономически и математически модели. Основният метод за изследване на операциите е систематичен анализ на целенасочени действия (операции) и обективна (по-специално количествена) сравнителна оценка на възможните резултати от тези действия. Сред най-важните класове проблеми в изследването на операциите са проблемите на управлението на запасите, разпределението и разпределението на ресурсите (проблеми с разпределението), проблеми с опашката, проблеми с подмяната на оборудването, подреждането и координацията (включително теорията на планирането), състезателни (например игри), проблеми с търсенето и др. Сред използваните методи са математическо програмиране (линейно, нелинейно и др.), диференциални и диференциални уравнения, теория на графите, процеси на Марков, теория на игрите, теория на (статистическите) решения, теория за разпознаване на образи и редица други. Смята се, че оперативните изследвания възникват в навечерието на Втората световна война, когато в Англия е създадена група от специалисти на радарна станция за решаване на технически проблеми с помощта на математиката. Те се фокусираха върху сравняването на ефективността на начините за решаване на проблеми, намирането на оптималното решение. Участието в тази група представители на различни специалности предопредели цялостен или, както се казва сега, систематичен подход. В момента в тази насока работят стотици изследователски институции и групи в десетки държави. Обществата за изследване на операциите са организирани от Международната федерация (IFORS). Руски учени Л.В. Канторович, Н.П. Бусленко, Е.С. Вентцел, Н.Н. Воробьов, Н.Н. Моисеев, Д.Б. Юдин и много други. Значителен принос за формирането и развитието на изследването на операциите имат чуждестранни учени Р. Акоф, Р. Белман, Г. Данциг, Г. Кун, Й. Нойман, Т. Саати, Р. Чърчман, А. Кофман и др. Методите за изследване на операциите, като всички математически методи, винаги опростяват, до известна степен, загрубяват проблема, отразявайки нелинейните процеси с линейни модели, стохастичните системи с детерминистични и т.н. Следователно не трябва да се преувеличава стойността на количествените методи за изследване на операциите, нито да го подценяваме. , позовавайки се на примери за неуспешни решения. Известно е едно парадоксално определение, дадено от крупен американски специалист в тази област T. A. Saaty: „Изследването на операциите е изкуството да се дават лоши отговори на практически въпроси, на които се отговаря още по-лошо по други начини.“ ЦЕНТРАЛЕН МЕЖДУРЕГИОНАЛЕН КОЛЕЖ ПО ИНДУСТРИАЛНИ ТЕХНОЛОГИИ И ПРЕДПРИЕМАЧЕСТВО Аз одобрявам Депутат директор по образованието « » 200 Ж . УПРАЖНЕНИЕ за дизайн на курса по предмет "Математически методи" Студент: Сергеев Евгений Анатолиевич. Тема на проекта: "Линейно програмиране, решаване на задачи по симплексния метод". ОБЯСНИТЕЛНА ЗАПИСКА Задачи и тяхното решение: Първа задача: Решете симплексния проблем по метода: F = 2X1 +3X2 → макс 3.1.2 Втора задача: Фирмата произвежда два вида продукти. Видове суровини, техните запаси, разход на суровини за година. д. всеки вид продукт, производствената печалба от продажбата на продуктите са дадени в таблицата: 3.1.3. Трета задача: Компанията произвежда 3 вида продукти, като използва 3 вида суровини. Запасите от суровини, техните норми на потребление и печалбата от продажбата на всеки продукт са показани в таблицата: Как трябва да се планира производството, за да се максимизират печалбите? 3.1.4. Четвърта задача: За производството на 4 вида продукти се използват 3 вида суровини. Запасите от суровини, техните норми на потребление и печалбата от продажбата на всеки продукт са показани в таблицата: Как трябва да се планира производството, за да се максимизират печалбите? 3.
Заключение 4.
Библиография Председател на цикловата комисия/ Баранов В.А. Ръководител на курсов проект/ Карпушкин А.Г. Дата на издаване на заданието: Крайна дата: « » 2007 г. « » 2007 г ПРОСТ МЕТОД Симплексният метод е предложен за първи път от американския учен Дж. Данциг през 1949 г., но през 1939 г. идеите на метода са разработени от руски учен Л В. Канторович. Симплексният метод, който позволява решаването на всяка задача на линейното програмиране, е универсален. Понастоящем се използва за компютърни изчисления, но прости примери, използващи симплексния метод, могат да бъдат решени и ръчно. За прилагане на симплексния метод - последователното подобряване на решението - е необходимо да се овладеят три основни елемент: Начин за определяне на всяко първоначално допустимо основно решение на проблема; Правилото за преход към най-доброто (по-точно, не най-лошото) решение; Критерий за проверка на оптималността на намереното решение. За да се използва симплексният метод, проблемът с линейното програмиране трябва да се сведе до каноничната форма, т.е. системата от ограничения трябва да бъде представена под формата на уравнения. Обикновени изключения в Йордания Да разгледаме система от m линейни уравнения с n неизвестни a11 x1 + a12 x2 + … + a1n xn = b1, am1 x1 + am2 x2 + … + amn xn = bm. Записваме тази система под формата на таблица a11 … a1j … a1n ……………….. ai1 … aij … ain ……………….. am1 … amj … amn Стъпка на обикновено елиминиране на Йордан (OJI), извършена върху дадена таблица с разделящ елемент aij ≠ 0 с I разрешаващ ред и j разрешаваща колона, е операцията за решаване на уравнението bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn по отношение на xj, замествайки това решение в оригиналната система и записвайки новополучената система под формата на нова таблица. Лесно е да проверите как ще изглежда новата маса b11 b12 … a1j … b1n b21 b22 … a2j … b2n ……………….. Ai1 –ai2 … 1… -ain ……………….. bm1 bm2 … amj … bmn където brs = ars aij - arj ais (i ≠ r, j ≠ s), и всички елементи на таблицата трябва да бъдат разделени на aij . По този начин, една стъпка Jordan Elimination (JJI) трансформира оригиналната таблица в нова таблица съгласно схема, състояща се от следните 5 правила: 1) разрешаващият елемент се заменя с един 2) останалите елементи на разрешаващата колона j остават непроменени. 3) останалите елементи на разрешаващия низ i променят само знаците си. 4) останалите елементи на brs се изчисляват по формулата brs = ars aij - arj ais 5) всички елементи на новата таблица са разделени от разрешаващия елемент aij. Пример 1. За маса Изключенията на Джордан правят възможно преминаването от произволно взета декартова система от координатни равнини към нова система, в която координатите на точките са техните отклонения от по-интересна система от равнини за определен проблем. Модифицирани изключения на Jordan Ако оригиналната система от уравнения ai1 x1 + ai2 x2 + … + ain xn = bi, където i = 1,m, запишете като -ai1 (-x1) - ai2 (-x2) - ... - ain (-xn) = bi и направете маса което се получава съгласно правила 1 - 5 на GOG с единствената промяна, че правила 2 и 3 сменят ролите: 1) останалите елементи на разрешителния низ остават непроменени 2) останалите елементи на разрешаващата колона променят само своите знаци Помислете за системата 2X1 + 3X2 - 5X3 = 16 = b1, 3X1 - 2X2 + 4X3 = 36 = b2, 5X1 + 7X2 - 11X3 = 44 = b3. Нека го запишем под формата на таблица Екстремуми на линейна функция Нека разгледаме обща задача за линейно програмиране. Изчислителните методи на LP се основават на следната фундаментална теорема. Теорема. Ако задача на линейно програмиране има оптимално решение (винаги в ограничена област и в неограничена област в зависимост от ограничеността на функцията Z), то съвпада с поне едно от опорните решения на системата от ограничителни уравнения. Според тази теорема, вместо да се изследва безкраен набор от възможни решения, за да се намери желаното оптимално решение сред тях, е необходимо да се изследват само краен брой поддържащи решения. Тази теорема гласи, че има поне едно опорно оптимално решение, но в проблемите може да има няколко опорни оптимални решения (алтернативен оптимум). Следователно схематичната диаграма за решаване на проблеми с линейно програмиране е както следва: 1. С помощта на ZhI ще намерим всички поддържащи решения на системата. a11 x1 + a12 x2 + … + a1n xn = b1, ……................... ak1 x1 + ak2 x2 + … + akn xn = bk, ak+1,1 x1 + ak+1,2 x2 + … + ak+1n xn ≤ bk+1, ……................... am1 x1 + am2 x2 + … + amn xn ≤ bm . 2. Изчислете за всяка от тях стойността на функцията Z, определена от отношението. Z = c1 x1 + c2 x2 + … + cn xn. 3. Избираме крайно Z от тях. Трябва да се отбележи, че може да има много голям брой референтни разтвори, така че е необходимо да се извърши подредено изброяване на референтни разтвори, като се постигне на всяка стъпка от монотонното изменение на функцията Z. Такава идея за последователно подобряване на решението е заложена в основния изчислителен метод за решаване на проблеми с линейно програмиране, наречен симплексен метод. Симплексен метод, базиран на пълни таблици Постановка на проблема за определяне на оптималната гама от продукти Предприятието може да произвежда два вида изделия А и Б, като разполага с ограничен ресурс от железен и стоманен материал за производството им съответно в количества от 350 и 392 кг и оборудване в количество от 408 машиночаса. Данните, представени под формата на таблица, характеризират разходите за всеки от трите вида ресурси, изброени за производството на един продукт А и Б. Необходимо е да се определи колко продукти А и Б трябва да бъдат произведени от предприятието, за да се постигне най-голяма печалба. Въвеждаме необходимите неизвестни X1 и X2, обозначаващи броя на продуктите A и B, които предприятието трябва да произведе. Тогава математически проблемът може да се формулира по следния начин. Сред множеството неотрицателни решения на системата от неравенства 14X1 + 5X2 ≤ 350, (1.1) 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, намери решение, за което функцията Z = 10 X1 + 5 X2 достига най-високата си стойност. Геометрично решение на задачата Първо, нека построим областта на допустимите решения, съответстващи на системата от неравенства. За да направите това, заменете всяко от неравенствата с равенството 14X1 + 5X2 = 350, (1-ва права линия), 14X1 + 8X2 = 392, (2-ри ред), 6X1 + 12X2 = 408, (3-та права линия), изграждане на гранична линия. Като вземем предвид, че X1 ≥ 0 и X2 ≥ 0, получаваме защрихованата част от равнината, която образува многоъгълник от OABCD решения (фиг. 1). След това изграждаме линия на ниво 10X1 + 5X2 = 0 и вектор (10; 5), които са взаимно перпендикулярни. Лесно е да се покаже, че векторът дава посоката на най-голямото увеличение на линейната функция. Наистина ли Z0 \u003d 10X10 + 5X20 \u003d 10 * 0 + 5 * 0 \u003d 0, ZA \u003d 10X1A + 5X2A \u003d 10 * 0 + 5 * 34 \u003d 170, ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 и т.н. От всички линии на ниво избираме две, от които едната минава през точката 0 и дава минималната стойност на функцията Z, а другата минава през точката C и функцията Z за нея приема максималната стойност. Тези линии на ниво се наричат референтни линии. Ориз. 1 Точка C се образува от първата и втората линия. Следователно решаването на системата от уравнения 14Xl + 5X2 = 350, 14X1 + 8X2 = 392, намерете координатите на точка C X1 = 20, X2 = 14, докато Zmax \u003d 10 * 20 + 5 * 14 \u003d 270 рубли. Така максимална печалба от 270 рубли. ще се получи, ако предприятието произвежда 20 продукта от тип А и 14 продукта от тип Б. Намиране на максимума на линейна функция Симплексният метод за решаване на проблеми с линейното програмиране се основава, с някои допълнения, на предишния анализиран метод на последователни елиминации, който е набор от удобни изчислителни алгоритми, базирани на последователно прилагане на идентични (симплексни) трансформации на система от уравнения. Добавяне към лявата страна на неравенствата 14X1 + 5X2 ≤ 350, 14X1 + 8X2 ≤ 392, 6X1 + 12X2 ≤ 408, някаква неотрицателна стойност Yj ≥ 0 (i = 1, 2, 3), (1.2) наречена изравняваща или основна променлива, ние ги превръщаме в уравнения: X1 + 5X2 + Y1 Освен това може да се покаже, че всяко решение на системата от неравенства (1.1) съответства на едно единствено решение на системата от уравнения (1.3) и неравенства (1.2) и обратно. Всяка от променливите Y1, Y2, Y3 е включена само в едно уравнение и зависи от променливите X1 и X2, които наричаме свободни. Система (1.3) съответства на началното допустимо базисно решение X1 = X2 = 0; Y1 = 350; Y2 = 392; Y3 = 408 и Z = 0. Извършваме първото идентично преобразуване на системата от уравнения (1.3). Избираме колоната за разделяне, съответстваща на най-малкия отрицателен елемент в реда Z, тъй като теоретично е установено, че при иначе равни условия може да се очаква по-голямо увеличение на функцията Z. . В пресечната точка на избраната колона и ред има номер на резолюция. Разделяме първото уравнение на разделителното число и записваме полученото уравнение. Умножавайки това уравнение по 14, 6 и -10 и изваждайки съответно 2-ро, 3-то и 4-то уравнения на система (1.3), стигаме до следната система (1.4): X2 + 1/4 Y1 = 25, X2 - 6/14 Y1 + Y3 Такава тъждествена трансформация, при която изборът на разрешаващо число се извършва по посоченото правило, ще наричаме симплекс трансформация. Така симплексната трансформация се извършва съгласно следното правило: 1. Изберете колоната за разрешаване, съответстваща на най-малкия отрицателен елемент в Z - реда. 2. Избира се разрешаващ ред, който съответства на най-малкото положително отношение на елементите от дясната страна на уравненията към съответните елементи на разрешаващата колона. В пресечната точка на разрешаващата колона и разрешаващия ред е разрешаващото число. 3. Елементите на разрешителния низ се разделят на разрешителното число. 4. Елементите на всички останали редове се изчисляват по формулата: От система (1.4) намираме второто допустимо базисно решение Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, което съответства на новата увеличена стойност на функцията Z = 250. По този начин процесът на последователни симплексни трансформации е процес на последователно подобряване на решението. при което: 1. Ако има поне един отрицателен елемент в Z - линията и а) има поне един положителен елемент в разрешаващата колона, тогава решението може да бъде подобрено; б) ако разрешаващият стълб не съдържа положителни елементи, тогава функцията Z нараства неограничено. 2. Ако всички елементи в Z - реда са неотрицателни, тогава оптималното решение е достигнато. Това са достатъчни условия за наличието на оптимален план за решение. В система (1.4) коефициентът при X2 в Z - реда е отрицателен, така че втората колона ще бъде разрешаваща. Откриваме, че вторият ред ще бъде разрешителен. След това извършваме симплексна трансформация на система (1.4) съгласно посоченото правило: X1 + 8/42 Y1 - 5/42 Y2 = 20, X2 - 1/3 Y1 + 1/3 Y2 = 14, 20/7 Y1 - 23/7 Y2 + Y3 = 120, 10/42 Y1 + 20/42 Y2 + Z = 270, (1,5) Тъй като всички елементи в Z-реда са неотрицателни, този план е оптимален. В този случай Yl = Y2 = 0; X1 = 20; X2 = 14 и Zmax = 270. Извършването на симплексни трансформации е свързано с мъчителни и често доста тромави изчисления. Тези изчисления могат да бъдат значително опростени чрез използване на така наречените симплексни таблици за решаване на проблеми. Всяка симплексна трансформация на системата се свежда до преход от една симплексна таблица към друга. Съгласно оригиналната система от уравнения (1.3) съставяме първата симплексна таблица (Таблица 1.1). Таблица 1.1 Първата колона е колоната на основните променливи, втората колона съдържа свободните коефициенти от дясната страна на уравненията (1.3), първият ред съдържа всички променливи, последната колона е контролната колона и коефициентите в нея са равни на сбор от всички коефициенти в реда. От табл. 1.1 имаме първото допустимо решение на система (1.3) X1 = X2 = 0, Y1 = 350, Y2 = 392, Y3 = 408, Z = 0, което съответства на върха O (0,0) на многоъгълника на допустимите решения OABCD (фиг. 1). Преходът към втората симплексна таблица (Таблица 1.2) се извършва съгласно правилото, посочено в този параграф за симплексни трансформации на системи от уравнения, докато разрешаващата променлива X1 отива към основата вместо разрешаващата променлива Y1. 1.2. Таблица 1.2 След попълване на таблицата 1.2 е необходимо да се провери правилността на попълването му, за което обобщаваме коефициента по редове и тази сума трябва да бъде равна на коефициентите в съответните клетки на контролната колона. От табл. 1.2 второто валидно решение би било X1 = 25, X2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 и Z = 250. Лесно се вижда, че тази таблица съответства на система (1.4) и референтното решение X1 = 25, X2 = 0 съответства на върха D(25,0) на многоъгълника на решението. Тъй като в Z-реда има отрицателен елемент, подобряваме решението, за което съставяме симплексна таблица. 1.3. Маса 1. 3
* Забележка. За опростяване на изчисленията трябва да се помни, че в новата таблица на мястото на елементите на разрешаващата колона (с изключение на разрешаващия елемент) има нули. Ако има нули в разрешаващия ред, тогава съответните колони се прехвърлят в новата таблица без промяна: Тъй като в Z - линията няма отрицателни елементи, това решение ще бъде оптимално. Раздел. 1.3 съответства на системата от уравнения (1.5) и оптималното решение Х1 = 20, X2 = 14 и Zmax = 270 и връх C (20,14) на многоъгълника на допустимите решения OABCD. Такива удължени таблици, съдържащи всички променливи в първия ред, благодарение на наличието на контролна колона, ви позволяват да контролирате правилността на попълване на таблиците и да избягвате аритметични грешки. Симплексен метод, базиран на съкратени таблици Разгледайте системата от уравнения (1.3) и я напишете под формата на таблица 1.4 Таблица 1.4 Записваме основните променливи (BP) в първата колона, а свободните променливи (SP) в първия ред. След това преходът към новата таблица 1.5 се извършва съгласно правилото: 1) разменете SP и BP 2) на мястото на разрешаващия елемент има реципрочна на него стойност 3) разделяме елементите на разрешаващата линия на разрешаващото число 4) разделяме елементите на разрешаващата колона на разрешаващата колона и променяме знака 5) останалите елементи се намират както в глава „Намиране на максимума на линейна функция“, правило 4 (правилото на правоъгълниците за OGI). Получаваме таблица 1.5. Таблица 1.6 Получихме оптималния план Zmax = 270 с X1 =20, X2 = 14, а ресурсите на оборудването се оказаха в излишък в размер на 120 машиночаса. Решаване на задача от линейно програмиране Намерете максималната целева функция под ограничения 14x + 5y ≤ 350 Решаване на проблем с помощта на програма Microsoft Excel. Нека присвоим A3 и B3 на стойностите на променливите x и y. В клетка C4 въведете целевата функция В клетки A7:A9 въвеждаме левите части на ограниченията а в клетки B7:B9 - десните части на ограниченията. След това изберете командата Обслужване, Намиране на решение(Инструменти, Solver) и попълнете диалоговия прозорец, който се отваря Намиране на решение ( Solver), както е показано на фиг. 2. След натискане на бутона БягайОтваря се прозорец (Решаване). Резултати от търсенето на решение(Solver Results), който съобщава, че е намерено решение (фиг. 3). Ориз. 2. Намиране на решение Ориз. 3. Резултати от търсенето на решение Геометрично решение на задачата с помощта на програмата MATHCAD 2000. 14x + 5y = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70 7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49 x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34 10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C Ориз. 4. Намерете (x, y) → (20, 14) f(x, y): = 10x + 5y fmin := f(20, 14) Аналитично решение на проблема с помощта на програмата MATHCAD 2000. Аналитичното решение на проблема в MathCAD е много по-просто. Z(x, y): = 10x + 5y 14x + 5x ≤ 360 M:=Максимизиране(z,x,y) M=(20,14)Z(M0,M1)=270 Проблемът за максимизиране на линейна функция при наличие на отрицателни свободни коефициенти Намерете максимума на линейна функция под ограничения X1 – X2 ≤ 3, 2X1 – 3X2 ≤ 6, X1 ≥ 0, X2 ≥ 0. Записваме системата във формата Y1 = -X1 + X2 + 3 ≥ 0 Y2 = X1 + X2 - 5 ≥ 0 Y3 = -2X1 + 3X2 + 6 ≥ 0 Y4 = -X2 + 6 ≥ 0 Да направим маса. Продължаваме да работим с 2-ри ред, тъй като отрицателният елемент не е изчезнал. Ние правим SHMZhI с разрешаващ елемент -2. Получаваме маса. Проблем с минимизиране на линейна функция Свеждане на проблема за минимизиране до проблема за максимизиране на линейна функция Разгледахме решението на задачата за намиране на максимума на линейната функция по симплексния метод W = c1 x1 + c2 x2 + … + cn xn. Въпреки това, в много икономически проблеми се изисква да се намери минимумът на линейна функция. За това е достатъчно да поставите W = -Z = -c1 x1 - c2 x2 - ... - cn xn и решаване на проблема за максимизиране на получената функция W при подходящи ограничения. Тъй като е ясно, че Минимизиране на линейната функция при спазване на ограниченията 7X1 + 2X2 ≥ 14, 5X1 + 6X2 ≤ 30, 3X1 + 8X2 ≥ 24, X1 ≥ 0, X2 ≥ 0. Геометричното решение на задачата на (фиг. 5) и съответства на оптималното решение в точката C (48/11, 15/11) и в същото време Zmin = -21/11. Фиг. 5. Геометрично решение на задачата Въвеждайки изравняващите променливи Yi ≥ 0 и функцията W = -Z = 2X1 - 5X2 → max, записваме задачата във формата. Y1 = 7X1 + 2X2 - 14, Y2 = -5X1 - 6X2 + 30, Y3 = 3X1 + 8X2 - 24, Записваме тази система под формата на таблица. Отърваваме се от отрицателния свободен член в линията Y1 -, правейки SHMZhI с разрешаващия елемент „-50/8“, получаваме таблица. Тъй като няма отрицателни елементи в W - ред и в 1 - колона, получаваме оптималното решение X1 = 48/11, X2 = 15/11, Wmax - 21/11 или Zmin = -Wmax = -21/11 , Практическа част 1.
Решете задачата с помощта на симплексния метод. X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → макс. Решение X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0 X1 + X2 + X4 = 150 Отговор: X1 = 75; X2 = 75; X3 = 0; X4 = 0. Задача номер 1. Фирмата произвежда два вида продукти. Видове суровини, техните запаси, разходни норми на суровини за c.u. всеки вид продукт, производствената печалба от продажбата на продуктите са дадени в таблицата. Решение 2X1 + 2X2 ≤ 17 X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0 2X1 + X2 + X4 = 10 2X1 + 2X2 + X5 =17 Отговор: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7. Задача номер 2. Фирмата произвежда три вида продукти, използвайки три вида суровини. Запасите от суровини, техните разходни норми и печалбата от продажбата на всеки продукт са показани в таблицата. Как трябва да се планира производството, така че печалбата на предприятието да е най-голяма? Решение 2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → макс. 5X1 + 3X2 ≤ 900 2X1 + 3X2 + 7X3 + X4 = 1250 F - 41X1 - 35X2 - 96X3 = 0 X1 + X2 + X5 = 250 5X1 +3X2 + X6 = 900 X1 + 3X2 ≤ 20 F = 2X1 + X2 → макс 2X1 + 2X2 ≤ 17 (-1/3)(-1/3)(2/3) Отговор: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5. Заключение Нека се спрем на най-простите интерпретации на симплексния метод. Алгебричният смисъл на симплексния метод е, че извършвайки еднакви алгебрични трансформации, преминаваме от едно възможно решение към система от алгебрични уравнения към друго подобрено, достигайки оптималното решение на проблема. От геометрична гледна точка идентичните трансформации според симплексния метод са последователни движения от един връх на изпъкнал многоъгълник на решение към съседен, от него към следващия и така нататък до оптималния връх по страните на този многоъгълник . Икономическата същност на симплексния метод се състои в това, че той е метод за последователно подобряване на решенията. Този метод дава възможност, като изберете отправна точка - основен план за действие, постепенно да се придвижите напред и в крайна сметка да постигнете оптимален план, ако, разбира се, такъв съществува. Симплексът е изпъкнал многоъгълник в n-мерно пространство с n + 1 върха, които не лежат на една и съща хиперравнина. Симплексите се отделят в отделен клас, тъй като симплексът е най-простият многоъгълник, съдържащ някакъв обем от n-мерно пространство. Доказано е, че ако съществува оптимално решение, то непременно ще бъде намерено след краен брой стъпки (с изключение на така наречения „изроден проблем“, при който феноменът на „цикъл“, т.е. многократно връщане в същата позиция е възможно). Линейното програмиране е област на математическото програмиране, посветена на теорията и методите за решаване на екстремални проблеми, характеризиращи се с линейна зависимост между променливите. Математическото програмиране (оптимално програмиране) е дял от математиката, който съчетава различни математически методи и дисциплини: линейно програмиране, динамично програмиране, изпъкнало програмиране и др. Общата задача на математическото програмиране е да намери оптималната (максимална или минимална) стойност на целта функция, а стойностите на променливите трябва да принадлежат към някакъв диапазон от приемливи стойности. Списък на използваната литература 1) А. С. Шапкин, Н. П. Мазаева; Математически методи и модели на изследване операции, 2005. 2) Н.Ш. Кремер, Б. А. Путко, И.М. Тришин, М.Н. Фридман; Операционни изследвания в икономика. - ЮНИТИ, 2002г. За да използвате визуализацията на презентации, създайте акаунт в Google (акаунт) и влезте: https://accounts.google.com Решаване на най-простите задачи на линейното програмиране с графичен метод 17.04.2012г. Ако ограничителната система на задача за линейно програмиране е представена като система от линейни неравенства с две променливи, тогава такава задача може да бъде решена геометрично. Задача. Има 14 радиорелейни канала (RRC) и 9 тропосферни канала. На тях е необходимо да се прехвърли информация от 3 вида: A, B, C. Освен това информация A е равна на 600 USD, B - 3000 USD, C - 5500 USD. (Информацията може да се разбира като брой телефонни разговори, трансфер на данни и др.). Възможностите на канала и разходите за поддръжка за всеки канал са дадени в таблицата. Необходимо е да се намери необходимият брой канали от двата типа, необходими за предаване на необходимата информация, така че разходите за работа да бъдат минимални. Видове информация Комуникационни канали Необходимо количество информация, у.е. Тропосферен RRS A 80 40 600 V - 1000 3000 C 300 800 5500 Разходи за поддръжка на един канал, rub. 3000 2000 Етапи на решаване на LLP: Изградете ODR. Изградете градиентен вектор на целевата функция в някаква точка X 0, принадлежаща на ODR - (c 1 ;c 2) . Построете права c 1 x 1 + c 2 x 2 = h, където h е всяко положително число, за предпочитане такова, че начертаната линия минава през многоъгълника на решението. Преместете намерената линия успоредно на себе си по посока на градиентния вектор, докато линията напусне ODR (когато търсите максимума) или в обратната посока (когато търсите минимума). В граничната точка целевата функция достига максимум (минимум) или неограничеността на функцията се установява върху множеството от решения. Определете координатите на максималната (минималната) точка на функцията и изчислете стойността на функцията в тази точка. Тази разработка може да се използва като обобщаващ урок по темата „Системи от неравенства с две променливи“ в 9. клас (алгебра 9, под редакцията на Теляковски) и като урок за повторение по тази тема в 10. клас. ... Материалът е предназначен за напреднали. програмата разглежда алгоритъма за съставяне на основни и референтни графики по различни методи и намиране на оптималното решение ... Работна тетрадка за урок по математика на тема "Проблеми на линейното програмиране" е разработена от мен за едноименния урок по математика (ниво за напреднали). може да се използва както в класна стая, семинар... Вземане на решения при несигурност Ако първият обект има m стратегии, а вторият има n стратегии, тогава казваме, че имаме работа с m x n игра. Помислете за m x n игра. Нека е даден набор от стратегии: за първия играч (Аi), за втория играч (Bj), матрицата на печалбата, където aij е печалбата на първия играч или загубата на втория играч, когато изберат стратегии Аi и Bj, съответно. Всеки от играчите еднозначно избира с вероятност I някаква стратегия, т.е. използва чиста стратегия при избора на решение. В този случай решението на играта ще бъде в чистите стратегии. Тъй като интересите на играчите са противоположни, първият играч се стреми да максимизира печалбата си, а вторият играч, напротив, да минимизира загубата си. Решението на играта е да се определи най-добрата стратегия за всеки играч. Изборът на най-добрата стратегия от един играч се извършва при пълна липса на информация за решението, взето от втория играч.
Линейно програмиране
Примери за задачи, които се свеждат до PAP.
1. Задачата за оптимално разпределение на ресурсите.
Примери
Пример 2
Решение
Проблем със сместа.
Таблица
Решение
Икономико-математически модел на задачата.
Задача за рязане
Основната задача на LP
Надписи на слайдове:
По темата: методически разработки, презентации и бележки
Зареждане...