Математически модели на задачи за линейно програмиране. Математически модел на задача за линейно програмиране Общ изглед на модел за линейно програмиране

Държавно висше учебно заведение

професионално образование

"Московски държавен технически университет на името на N.E. Бауман"

Клон Калуга

„Решаване на задача за линейно програмиране с помощта на симплексния метод“

Цел на работата: да изучавате и да се научите да прилагате на практика симплексния метод за решаване на проблеми с директно и двойно линейно програмиране

Теоретична част.

Математическа постановка на задачата за линейно програмиране.

От практиката на разглеждане на проблемите на математическото програмиране следва, че като цяло е почти невъзможно да се решат. Препоръчително е да се разглеждат отделни класове (видове) задачи. За всеки такъв клас е възможно да се формулира алгоритъм за решение, който е приемлив само за този клас задачи. Най-разработените проблеми в математическото програмиране са задачите на линейното програмиране (LP).

В проблемите на линейното програмиране целевата функция е линейна, а ограничителните условия съдържат линейни равенства и линейни неравенства. Променливите могат или не могат да бъдат предмет на изискването за неотрицателност. Една и съща задача за линейно програмиране може да бъде написана в различни форми. Ако всички ограничения са под формата на неравенства, тогава проблемът е написан в стандартна форма. Ако всички негови ограничения, с изключение на

представляват равенства, тогава проблемът за линейно програмиране е написан в канонична форма.

Общ поглед върху задачата за линейно програмиране

Ограничения:

1. Дясната страна на всички ограничения трябва да е неотрицателна . Ако някой от коефициентите< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

2. Всички ограничения трябва да бъдат представени под формата на равенства, следователно, когато се преминава от неравенство към равенство, се използва апаратът от допълнителни променливи.

Ако първоначалните ограничения определят потреблението на някакъв ресурс (знакът ""), тогава променливите трябва да се тълкува като остатък или неизползвана част от ресурс. В този случай това е остатъчна променлива и се въвежда в уравнението със знак „+“.

Ако първоначалните ограничения определят излишъка на някакъв ресурс (знакът ""), тогава се въвежда излишна променлива знак "-".

Променливи:

Всички променливи трябва да са неотрицателни, т.е. .

Ако дадена променлива няма ограничения за знаци, тогава тя трябва да бъде представена като разлика на две неотрицателни променливи: , където . Това заместване трябва да се използва във всички ограничения, съдържащи тази променлива, както и в израза за целевата функция.

Ако такава променлива попада в оптималното решение, тогава

Целева функция:

Да бъде максимизиран или минимизиран.

Система от ограничения под формата на равенства и неравенства образува изпъкнало множество - изпъкнал многостен. Този набор може да бъде ограничен или неограничен. Целевата функция на задача за линейно програмиране също е изпъкнала функция. По този начин проблемът с линейното програмиране е частен случай на проблема с изпъкналото програмиране.

Нека разгледаме системата от ограничения на задачата за линейно програмиране под формата на равенства

(1)

Система (1) от линейни уравнения е последователна, ако има поне едно решение. Система (1) се нарича излишна, ако едно от уравненията може да бъде изразено като линейна комбинация от останалите.

В система (1) броят на променливите (неизвестни n) е по-голям от броя на ограниченията m. Приемаме, че рангът на тази система е равен на m (системата не е излишна) и че системата (1) е последователна. Тогава m променливи от общия им брой образуват базисните променливи, а останалите променливи се наричат небазисни. Ако една система от уравнения има решение, то тя също има базисно решение. Решение на система от уравнения (1) се нарича допустима, ако всички нейни компоненти са неотрицателни.Ако система от линейни уравнения има допустимо решение, то тя има и базисно допустимо решение.Множеството от всички допустими решения на система (1) е изпъкнало множество, т.е. на решенията на задачата за линейно програмиране е изпъкнал.Тъй като това множество е образувано от равнини (хиперравнини), то има формата на изпъкнал полиедър.Основното допустимо решение съответства на крайната точка на изпъкналия многостен (неговото лице или връх). Ако има оптимално решение на проблем с линейно програмиране, тогава има основно оптимално решение.

Целевата функция на задача за линейно програмиране е уравнението на равнина (или хиперравнина за броя на променливите, по-голям от три). Целевата функция на задача за линейно програмиране достига своята максимална или минимална стойност или на върха на изпъкнал многостен, или на едно от лицата му. По този начин решението(ята) на проблема с линейното програмиране се намират във върховете на изпъкнал полиедър и за да го намерят, е необходимо да се изчислят стойностите на целевата функция във върховете на изпъкналия многостен, определени от условията- ограничения на проблема.

Решаване на задача от линейно програмиране с помощта на графичен метод.

Трудността при конструирането на математически модел се състои в идентифицирането на променливите и след това в представянето на целта и ограниченията като математически функции на тези променливи. Ако моделът съдържа само две променливи, тогава проблемът с линейното програмиране може да бъде решен графично. В случай на три променливи, графичното решение става по-малко ясно, а при по-големи стойности на променливите дори невъзможно. Въпреки това, графичното решение ни позволява да направим изводи, които служат като основа за разработване на общ метод за решаване на проблем с линейно програмиране.

Първата стъпка при използване на графичния метод е геометрично представяне на възможните решения, т.е. конструиране на допустима област на решение (ADA), в която всички ограничения на модела са изпълнени едновременно. При получаване на графично решение променливата се нанася по хоризонталната ос и по вертикалната ос. При формирането на ODD е необходимо да се предотврати получаването на неприемливи решения, които са свързани с необходимостта да се изпълни условието за неотрицателност на променливите. Преди изграждането е необходимо да се определят квадрантите, в които ще бъде разположен ОДР. Квадрантите се определят от знаците на променливите и . Условията за неотрицателност на променливите ограничават обхвата на техните допустими стойности до първия квадрант. Ако променливата не е ограничена по знак, тогава регионът е ограничен от първи и втори квадранти, ако , тогава от първи и четвърти квадранти. Други граници на пространството на решението в равнината са изобразени с прави линии, построени с помощта на уравненията на ограниченията, като знакът е заменен със знака "=". В този случай трябва да се вземе предвид следното: десните страни на всички ограничения трябва да са неотрицателни . Ако има някакво ограничение< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.

В резултат на конструкцията се получава многоъгълник, който определя пространството на решението. Ако едно от ограниченията има знака "=", тогава ODD се изражда в сегмент.

Във всяка точка, която принадлежи към региона или границите на многоъгълника на решението, всички ограничения са изпълнени, така че всички решения, съответстващи на тези точки, са валидни. Пространството на решенията съдържа безкраен брой такива точки; въпреки това е възможно да се намери оптимално решение. За да направите това, е необходимо да се конструира в равнината на променливите градиента на целевата функция. Определянето на оптималната точка зависи от проблема, който трябва да бъде решен.

Ако целевата функция дефинира проблем за максимизиране, тогава оптималната точка ще бъде разположена в посока на увеличаване на градиента; ако проблемът с минимизиране е дефиниран, тогава в посока на намаляване на градиента на целевата функция. За да определим оптималната точка, ще преместим целевата функция в посока на увеличаване (намаляване) на градиента, докато се премести в областта на неприемливите решения.

След намиране на оптималната точка в пространството на решението се определят нейните координати и стойността на целевата функция в нея. Правилността на избора на оптималната точка може да се провери чрез изчисляване на целевата функция във върховете на полиедъра на решението. В ZLP областта на допустимите решения винаги е изпъкнало множество, т.е. такова множество, че заедно с всеки две точки, принадлежащи на това множество, отсечката, свързваща тези две точки, също принадлежи на същото множество. Всяка функция расте най-бързо по посока на своя градиент.

Решаване на задача от линейното програмиране чрез симплексния метод.

Директна задача.

Разгледайте проблема с линейното програмиране в канонична форма:

Намерете максимума (минимума) на функция при условия

Предполага се, че решение на този проблем съществува. За да се намери оптималното решение, е необходимо да се намерят изпълними основни решения и от тях да се избере оптималното основно решение.

Симплексният метод е алгебричен метод за решаване на проблеми с линейното програмиране. По време на процеса на изчисление се извършва последователно обхождане на върховете на полиедъра на решението (SDP), като се проверяват условията за оптималност във всеки връх. Освен това всеки преход към съседен връх е придружен от подобряване на целевата функция.

Изчислителни процедури на симплексния метод.

С графичния метод за решаване на LLP оптималното решение винаги съответства на една от ъгловите (екстремни) точки на пространството на решението. Този резултат формира основата за изграждането на симплексния метод. Симплексният метод няма ясно геометрично представяне на пространството на решението.

Симплексният метод прилага подреден процес, при който, започвайки от някаква първоначална възможна ъглова точка, се правят последователни преходи от една възможна крайна точка към друга, докато се намери оптималната точка на решение.

Нека означим: – общия брой променливи в LLP, представени в канонична форма; - брой изходни променливи; - броят на ограниченията, - броят на допълнителните променливи, тогава .

Всеки връх на полиедъра на решението има - ненулеви променливи и () - нулеви променливи.

Ненулевите променливи се наричат основни, нулевите променливи се наричат неосновни.

Нека допълним системата от равенства с равенството на целевата функция и ще приемем, че това е основна променлива, която винаги присъства в основата за всеки връх.

За да се получи решение, се съставя първоначална допустима база, в която базисните променливи трябва да бъдат представени под формата на единични единични вектори. Това означава, че уравненията, представящи даден връх, трябва да включват всяка базисна променлива само в един ред с коефициент, равен на 1.

При избора на начална допустима база за съставяне на симплексна таблица на първата стъпка ST(0) началните променливи са равни на нула и са неосновни; сред въведените допълнителни променливи се избират променливи с коефициенти, равни на единица. Променливите в равенствата (2) - (4) са базисни и са включени в реда - с коефициенти равни на 0. За да се попълни симплексната таблица, е необходимо целевата функция да се преобразува във вида . Така най-накрая получаваме:

Когато съставяте симплексна таблица, спазвайте следните правила:

в най-лявата колона са основните променливи и ;

най-дясната колона съдържа десните части на ограниченията;

Първият ред съдържа променливите в определен ред:

първо, след това неосновни променливи, основните променливи се намират в последните колони преди дясната страна (RF). Нека запишем коефициентите в ST(0):

				АКО
1	0	0	0	0
0	1	0	0
0	0	1	0
0	0	0	1

Оптималността на всеки от върховете се определя от коефициентите на неосновните променливи в реда на текущата симплексна таблица:

За проблем с максимизиране този връх е оптимален, ако всички коефициенти за неосновни променливи в реда – са неотрицателни (>0);

За проблем с минимизиране този връх е оптимален, ако всички коефициенти за неосновни променливи в реда – са неположителни (< 0).

Ако в задача за максимизиране (минимизиране) една неосновна променлива в реда – има коеф.<0(>0), тогава текущата точка не е оптимална и основата трябва да се промени. За да направите това, изберете неосновна променлива, която има най-отрицателния (положителен) коефициент в реда –. Избраната небазисна променлива ще бъде включена в новата база и следователно се нарича включена променлива. Основната променлива, която ще бъде получена от основата, се нарича елиминирана променлива.

Изключената променлива ще бъде базовата променлива, която първа се превръща в „0“ при преместване към съседен връх след въвеждане на включената променлива.

Колоната на включената променлива ще се нарича разрешаваща колона.

Низът на изключената променлива ще се нарича разрешаващ низ.

Пресечната точка на разделящата колона и ред определя разделящия елемент (RE).

За да дефинирате изключена променлива:

разделете десните части на всички основни променливи (с изключение на реда) на съответните положителни коефициенти на разделителната колона;

изберете най-малкото от получените съотношения.

Невъзможно е да се раздели на „0“ и отрицателна стойност, тъй като това води до липса на пресичащ се връх или до връх извън ODR.

За да се премине към съседен връх, е необходимо да се генерира преходна матрица B(0), която ще определи връзката между ST(0) и ST(1): ST(1) = B(0) ST(0).

За произволна квадратна матрица с размерност n, имаща като (n - 1) колони единичните вектори, подредени в съответствие с единичните вектори на единичната матрица, и една произволна колона с ненулев елемент на главния диагонал, обратната матрица се намира по следното правило:

Всеки елемент от j-колона е разделен на RE и променя знака на противоположния, с изключение на разрешаващия елемент.

Изкуствена начална основа. М – метод.

Ако първоначалното ограничение е написано под формата на равенството "=" или има знака "", тогава е невъзможно незабавно да се получи допустимо първоначално основно решение, тъй като при писане на проблема в стандартна форма, след въвеждане на допълнителни променливи, вариант може да възникне, когато получените уравнения не позволяват образуването на първоначална допустима основа под формата на единица единица ред.

В този случай се въвеждат допълнителни изкуствени променливи, за да се намери първоначалната допустима база. Изкуствените променливи не са свързани със съдържанието на проблема; тяхното въвеждане е допустимо само ако съответната изчислителна схема ще осигури оптимално решение, при което всички изкуствени променливи ще бъдат равни на нула.

Променливите R определят първоначалната допустима база от гледна точка на възможен по-нататъшен преход към един от върховете на ODR. За използването на изкуствени променливи в целевата функция се въвежда наказание M. В проблема за максимизиране M е отрицателно (M<<0), в задаче минимизации М положительное (М>>0).

Свойство M: При добавяне (изваждане) с всяка крайна стойност, която определя всяка стойност, която всяка от променливите на оригиналния ZLP може да приеме, нейната стойност (на променливата M) не се променя, а именно,

Формула (1.2), ограничения върху неотрицателността на променливите (да, не) - формула (1.3) (1.1) i = 1,... m (1.2) (1.3) Алгоритъмът за решаване на проблеми с линейно програмиране изисква привеждане на техните формулиране в канонична форма, когато целта функция ...

На практика ограниченията в задача на линейно програмиране често се определят не чрез уравнения, а чрез неравенства.

Нека покажем как можете да преминете от проблем с ограничения на неравенството към основен проблем за линейно програмиране.

Нека има проблем с линейно програмиране с променливи, в който ограниченията, наложени на променливите, имат формата на линейни неравенства. В някои от тях знакът за неравенство може да е различен от други (вторият тип се свежда до първия чрез проста промяна на знака на двете страни). Следователно, ние задаваме всички ограничения на неравенството в стандартна форма:

Необходимо е да се намери набор от неотрицателни стойности, които да удовлетворяват неравенствата (4.1) и в допълнение да минимизират линейната функция:

От така поставената задача е лесно да се премине към основния проблем на линейното програмиране. Наистина, нека въведем следната нотация:

където са някои нови променливи, които ще наречем „допълнителни“. Съгласно условията (4.1) тези допълнителни променливи също трябва да са неотрицателни.

По този начин се сблъскваме с проблем с линейно програмиране в следната формулировка: намерете такива неотрицателни стойности на променливите, че да отговарят на системата от уравнения (4.3) и едновременно с това минимизирайте линейната функция на тези променливи:

Както можете да видите, пред нас е в чист вид основната задача за линейно програмиране (LPLP). Уравненията (4.3) са дадени във вече разрешен вид по отношение на основните променливи, които се изразяват чрез свободни променливи.Общият брой на променливите е равен на , от които „начална” и „допълнителна”. Функцията L се изразява само чрез “началните” променливи (коефициентите на “допълнителните” променливи в нея са равни на нула).

По този начин намалихме проблема на линейното програмиране с ограничения на неравенствата до основния проблем на линейното програмиране, но с по-голям брой променливи, отколкото беше първоначално в проблема.

Пример 1 Има проблем с линейно програмиране с ограничения на неравенството: намерете неотрицателни стойности на променливи, които отговарят на условията

и минимизиране на линейната функция

Необходимо е този проблем да се приведе във формата на ОПЗП.

Решение. Привеждаме неравенствата (4.4) до стандартен вид;

Въвеждаме допълнителни променливи:

Задачата се свежда до намиране на неотрицателни стойности на променливите

удовлетворяващи уравнения (4.6) и минимизиране на линейната функция (4.5).

Показахме как можем да преминем от проблем с линейно програмиране с ограничения на неравенството към проблем с ограничение на равенството (ICP). Винаги е възможен обратният преход - от OLP към задача с ограничения на неравенството. Ако в първия случай сме увеличили броя на променливите, то във втория случай ще го намалим, елиминирайки основните променливи и оставяйки само свободни.

Пример 2. Има проблем с линейно програмиране с ограничения за равенство (LPLP):

и функцията да бъде минимизирана

Изисква се да се напише като задача за линейно програмиране с ограничения на неравенството.

Решение. Тъй като , ние избираме някои две от променливите като свободни. Обърнете внимание, че променливите не могат да бъдат избрани като свободни, тъй като те са свързани с първото от уравненията (4 7): стойността на една от тях е напълно определена от стойността на другата, а свободните променливи трябва да са независими

По същата причина е невъзможно да се изберат променливи като свободни (те са свързани с второто уравнение). Нека изберем свободните променливи и да изразим всички останали чрез тях:

Тъй като условията (4 9) могат да бъдат заменени с неравенства:

Нека преминем в израза на линейната функция L към свободни променливи, замествайки техните изрази (4.9) в L вместо и. ще го получим.

ФЕДЕРАЛНА АГЕНЦИЯ ЗА ОБРАЗОВАНИЕ

Федерална държавна образователна институция „ПСКОВСКИ КОЛЕЖ ПО СТРОИТЕЛСТВО И ИКОНОМИКА“

Предмет "Математически методи"

Проблем с линейно програмиране

Курсова работа

Студент от група 315-ПО

Андреев Дмитрий Александрович

Ръководител на курсовата работа

Василиева Наталия Анатолевна

Псков 2009 г

Въведение

Глава Ι Линейно програмиране

§ 1 Обща постановка на задачата за линейно програмиране

§ 2 Математически модел на задачата за линейно програмиране

§ 3 Канонична форма на задачата за линейно програмиране

Глава ΙΙ Решаване на задачата чрез симплексния метод

§ 1 Постановка на проблема

§ 2 Съставяне на математически модел на задачата

§ 3 Алгоритми за решаване на задачата по симплексния метод

§ 4 Конструиране на изходния еталонен разтвор по метода на Гаус

§ 5 Решение на задачата

Заключение

Литература

Въведение

Понастоящем много проблеми на планирането и управлението в сектори на националната икономика, както и голям брой частни приложни проблеми се решават с помощта на методите на математическото програмиране. Най-развитите методи в областта на решаването на оптимизационни проблеми са методите на линейното програмиране. Тези методи позволяват да се опише с достатъчна точност широк спектър от задачи на търговската дейност, като например планиране на търговския оборот; разполагане на търговската мрежа на града; планиране на доставките на стоки за град или регион; присъединяване на търговски предприятия към доставчици; организиране на рационален транспорт на стоки; разпределение на търговски работници по длъжности; организиране на рационално снабдяване с храни; разпределение на ресурсите; планиране на капиталовите инвестиции; оптимизиране на междусекторните връзки; подмяна на търговско оборудване; определяне на оптималния асортимент от стоки в условия на ограничено пространство; установяване на рационален режим на работа.

В задачите на линейното програмиране критерият за ефективност и функциите в системата от ограничения са линейни.

Ако проблемът с математическото програмиране има времева променлива и критерият за ефективност се изразява чрез уравнения, които описват потока от операции във времето, тогава такъв проблем е проблем на динамичното програмиране.

В много икономически модели връзките между постоянни и променливи фактори могат да се считат за линейни.

Използването на методи за математическо програмиране в търговската дейност включва събирането на необходимата информация от бизнесмен, икономист или финансист и след това формулирането на проблем заедно с математиката. Тъй като методите за математическо програмиране вече са внедрени на компютъра под формата на пакет от стандартни програми, достъпът до тях обикновено е прост, автоматизиран и не създава особени затруднения.

След това работата на модела включва събиране и обработка на информация, въвеждане на обработената информация в компютър, изчисления въз основа на разработени програми за график и накрая издаване на резултати от изчисленията (в удобна за потребителя форма) за тяхното използване в областта на производствени дейности.

Глава Ι Линейно програмиране

§ 1 Обща постановка на задачата за линейно програмиране

Линейното програмиране е клон на математическото програмиране, който изучава методи за решаване на екстремални проблеми, които се характеризират с линейна връзка между променливи и линейна целева функция. За решаване на проблеми с линейно програмиране се съставя математически модел на проблема и се избира метод за решение.

Формулирането на проблема с търговската дейност може да бъде представено под формата на математически модел на линейно програмиране, ако целевата функция може да бъде представена под формата на линейна форма, а връзката с ограничени ресурси може да бъде описана чрез линейни уравнения или неравенства . Освен това се въвежда допълнително ограничение - стойностите на променливите трябва да са неотрицателни, тъй като те представляват величини като оборот, работно време, разходи и други икономически показатели.

Геометричната интерпретация на икономическите проблеми дава възможност да се визуализира тяхната структура, да се идентифицират характеристиките и отваря пътища за изследване на по-сложни свойства. Задача на линейно програмиране с две променливи винаги може да бъде решена графично. Но вече в триизмерното пространство такова решение става по-сложно, а в пространства, чиито измерения са повече от три, графичното решение е, най-общо казано, невъзможно. Случаят с две променливи няма особено практическо значение, но неговото разглеждане изяснява свойствата на проблемите на линейното програмиране, води до идеята за решаването му и прави геометрично ясни методите за решаване и начините за тяхното практическо прилагане.

§ 2 Математически модел на задачата за линейно програмиране

Преди да решим дадена задача, ние съставяме нейния математически модел.

Математическият модел е набор от връзки, състоящи се от линейна целева функция и линейни ограничения върху променлива.

Принципът на съставяне на математически модел.

1. Изберете променливи на задачата.

Променливите на проблема са количествата

Които напълно характеризират икономическия процес, описан в задачата. Обикновено се записва като вектор X = () Освен това )

2. Създайте система за ограничаване на проблема.

Система от ограничения е набор от уравнения и неравенства, които са удовлетворени от променливите на проблема и които следват от ограничените икономически условия на проблема.

Като цяло системата е написана във формата

3. Задайте целевата функция.

Целевата функция е функция Z(X), която характеризира качеството на задачата, чийто екстремум трябва да бъде намерен. Най-общо целевата функция се записва Z(X) =

Че. математическият модел изглежда като намиране на променливите на проблема

отговарящи на системата от ограничения:

и условието за неотрицателност

0 (j = ), което осигурява екстремума на целевата функция Z(Y) =

Допустимо решение на проблем с линейно програмиране е всеки набор от променливи стойности, който удовлетворява система от ограничения и условна неотрицателност.

Множеството от допустимите решения образува областта на допустимите решения на задачата (ADP).

Оптималното решение е осъществимо решение на задача, при която целевата функция достига екстремум.

§ 3 Канонична форма на задачата за линейно програмиране

Математическият модел на задачата трябва да има каноничен вид.

Ако ограничителната система се състои само от уравнение и всички променливи отговарят на условието за неотрицателност, тогава проблемът има канонична форма.

Ако системата има поне едно неравенство или някоя променлива е неограничена при условие за неотрицателност, тогава проблемът има стандартна форма. За да приведете проблема в канонична форма, трябва:

преминете от неравенствата към уравнението, както следва: от лявата страна на неравенствата въвеждаме допълнителна променлива с коефициент (+1) за неравенството (

) и (-1) за неравенство () допълнителни променливи не се налагат с целевата неотрицателност, след което се заменя с разликата на две неотрицателни променливи, тоест: = – (

Общ изглед на каноничната форма:

Глава ΙΙ Решаване на задачата чрез симплексния метод

Симплексният метод е метод за последователно подобряване на плана (решението), най-ефективен и се използва за решаване на всеки проблем с линейно програмиране.

Името на метода идва от латинското simplecx - просто, защото. от първоначалния регионът на възможните решения на проблема имаше най-простата форма. Идеите на метода са предложени от руския математик Л. В. Контарович. през 1939 г. и след това тази идея е развита и развита от Й. Данциг през 1949 г.

Симплексният метод ви позволява или да намерите оптимално решение, или да докажете, че то не съществува в краен брой стъпки.

§ 1 Постановка на проблема

Предприятието използва 3 вида машини в производствения процес: Ι, ІΙ, ІΙІ. В същото време се изразходват суровини, трудови ресурси и се вземат предвид режийните разходи.

Всеки проблем с линейно програмиране може да бъде сведен до проблем с линейно програмиране в канонична форма. За да направите това, в общия случай, трябва да можете да намалите проблема с максимизирането до проблема с минимизирането; преминете от ограничения за неравенство към ограничения за равенство и заменете променливи, които не се подчиняват на условието за неотрицателност. Максимизирането на определена функция е еквивалентно на минимизиране на същата функция, взета с обратен знак, и обратно.

Правилото за привеждане на проблем с линейно програмиране до канонична форма е следното:

ако в първоначалния проблем е необходимо да се определи максимумът на линейна функция, тогава трябва да промените знака и да потърсите минимума на тази функция;
ако дясната страна на ограниченията е отрицателна, тогава това ограничение трябва да се умножи по -1;
ако има неравенства сред ограниченията, тогава чрез въвеждане на допълнителни неотрицателни променливи те се трансформират в равенства;
ако някаква променлива x jняма ограничения за знаци, тогава се заменя (в целевата функция и във всички ограничения) от разликата между две нови неотрицателни променливи:
x 3 = x 3 + — x 3 — , Където x 3 + , x 3 — ≥ 0 .

Пример 1. Намаляване на проблема с линейното програмиране до канонична форма:

min L = 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 – x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Нека във всяко уравнение на системата от ограничения въведем изравняващи променливи x 4, x 5, x 6. Системата ще бъде записана под формата на равенства, а в първото и третото уравнение на системата от ограничения променливите x 4, x 6се въвеждат в лявата страна със знак „+“, а във второто уравнение променливата х 5се въвежда със знак "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободните членове в каноничната форма трябва да са положителни; за да направите това, умножете последните две уравнения по -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 – x 6 = 3.

В каноничната форма на писане на задачи за линейно програмиране всички променливи, включени в системата от ограничения, трябва да са отрицателни. Да приемем, че x 1 = x 1 ' - x 7 , Където x 1 ‘ ≥ 0, x 7 ≥ 0 .

Замествайки този израз в системата от ограничения и целевата функция и записвайки променливите в нарастващ индексен ред, получаваме задача за линейно програмиране, представена в канонична форма:

L min = 2x 1' + x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1 ‘ — x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ‘ + x 2 – x 6 + 2x 7 = 3;
x 1 ‘ ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Условие за оптималност за основния план на каноничната задача на LP. Симплексен метод и неговата сходимост.

Симплексният метод е универсален,тъй като ви позволява да решавате почти всеки проблем с линейно програмиране, написан в канонична форма.

Идеята на симплексния метод последователно подобряване на плана,е, че започвайки от някакво първоначално референтно решение, последователно насочено движениеот еталонните решения на проблема към оптималното.

Стойността на целевата функция не намалява по време на това движение за задачи до максимум.

Тъй като броят на опорните решения е краен, тогава след краен брой стъпки получаваме оптималното опорно решение.

Еталонното решение е основно неотрицателно решение.

Алгоритъм на симплексния метод

1. Математическият модел на проблема трябва да бъде каноничен. Ако е неканоничен, тогава трябва да бъде приведен в каноничен вид.

2. Намерете първоначалното еталонно решение и го проверете за оптималност.
За да направите това, попълнете симплексна таблица 1.
Попълваме всички редове на таблицата на 1-ва стъпка според данните на системата от ограничения и целевата функция.

Възможни са следните случаи при решаване на задачи на максимум:

1. Ако всички коефициенти на последния ред на симплексната таблица Dj³ 0, след това намерено

решение оптимален.

2 Ако поне един коеф Dj £ 0, но за съответната променлива няма нито една положителна оценъчна връзка, тогава решението спираме задачи, тъй като F(X) ® ¥ ,т.е. целевата функция не е ограничена в областта на възможните решения.

Ако поне един коефициент на последния ред е отрицателен и за съответната променлива има поне едно положително оценъчно отношение, тогава трябва да се раздвижите към друго референтно решение.

д акотогава има няколко отрицателни коефициента в последния ред към основната колона с променливи(BP) въведе това променлива, което съответства на най-големият отрицателен коефициент в абсолютна стойност.

5. Ако поне един коефициент Dk< 0 ,Че k - tyколона приемам за водещия.

6. За водеща линияние приемаме този, който съответства минимумсъотношение на безплатни членове бикъм положителни коефициенти водещ, k – тозиколона.

7. Извиква се елементът, разположен в пресечната точка на водещите редове и колона водещ елемент.

Попълване на симплексна таблица 2 :

· попълнете базовата колона с нули и единици

· пренапишете водещия ред, като го разделите на водещия елемент

· ако водещият ред има нули, тогава съответните колони могат да бъдат преместени в следващата симплексна таблица

· ние намираме останалите коефициенти, като използваме правилото "правоъгълник".

Получаваме ново референтно решение, което проверяваме за оптималност:

Ако всички коефициенти на последния ред Dj³ 0, тогава намереното решение максимум.

Ако не, тогава попълнете симплексната таблица на 8-ма стъпка и така нататък.

Ако целевата функция F(X)изисква намиране минимална стойност, тогава критерият оптималност на проблемае неположителни коефициентид j за всички j = 1,2,…n.

Сходимост на симплексния метод. Дегенерация при проблеми с LP. Най-важното свойство на всеки изчислителен алгоритъм е конвергенцията, т.е. възможността за получаване на желаните резултати по време на неговото прилагане (с определена точност) в краен брой стъпки (итерации).

Лесно е да се види, че проблемите с конвергенцията на симплексния метод могат потенциално да възникнат на етапа на избор на стойността на r (раздел 2") в случай, че същите минимални стойности на съотношението

ще бъде постигнато за няколко реда на таблица T (q) едновременно. След това при следващата итерация колона b(β(q+1)) ще съдържа нула елементи.

⇐ Предишен12345Следващ ⇒

Дата на публикуване: 2015-11-01; Прочетено: 4190 | Нарушаване на авторските права на страницата

Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)…

Оптимално решение - задача - линейно програмиране

Страница 1

Оптималното решение на задача с линейно програмиране се постига в една от референтните точки, където най-малко k n, - m променливи са равни на нула.

Използвайки оптималното решение на проблема с линейното програмиране, можете да намерите допустимите промени в DS, при които L остава постоянна.

Ако има оптимално решение на проблем с линейно програмиране, тогава има основно оптимално решение.

Доказано е, че оптималното решение на задача за линейно програмиране се намира на границата на областта на допустимите стойности на контролираните променливи, която е полиедър в n-мерното пространство и се определя от система от линейни ограничения.

Тъй като z е оптималното решение на задача за линейно програмиране с m ограничения, това решение съдържа най-много m строго положителни променливи.

Доказано е, че оптималното решение на проблема с линейното програмиране се намира на границата на областта на допустимите стойности на контролираните променливи, която е полиедър в /-мерното пространство, дефинирано от система от линейни ограничения. Координатите на всеки връх се определят чрез решаване на система от уравнения (ограничения), а при наличие на n контролирани променливи и m ограничения е необходимо да се разреши системата от m уравнения. Комбинацията Cpt n (m - n расте много бързо с увеличаване на типа, така че намирането на решение изисква много голям брой изчисления, недостъпни дори за компютър.

Така че в случая на D 1 оптималното решение на проблема с линейното програмиране автоматично се оказва цяло число.

Както беше показано в част 1, оптималното решение на проблем с линейно програмиране не е непременно цяло число и в същото време има много проблеми, чието естество изисква цяло число. Някои от тези проблеми не изглеждат като задачи за целочислено програмиране, но могат да бъдат формулирани като такива.

Очевидно е, че не всяко основно решение е оптимално решение на проблем с линейно програмиране. Въпреки това, оптималното решение на неизроден проблем трябва винаги да бъде основното решение за системата от уравнения (VIII, 42) и по този начин задачата за намиране на оптималното решение се състои в изброяване само на базисните решения на системата от уравнения (VIII, 42), сред които се намира оптималното.

Очевидно е, че не всяко основно решение е оптимално решение на проблем с линейно програмиране. Въпреки това, оптималното решение на неизроден проблем винаги трябва да бъде базовото решение за системата от уравнения (VIII42) и по този начин задачата за намиране на оптималното решение се състои в търсене само на базисните решения на системата от уравнения (VIII42 ), сред които се намира оптималното.

След няколко итерации на Стъпка 3 може да се появят множество алтернативни оптимални решения на проблема с линейното програмиране.

ЗАДАЧА НА ЛИНЕЙНО ПРОГРАМИРАНЕ

Този вид цикличност понякога се нарича непрекъсната дегенерация. За съжаление, това явление често се среща при проблеми със средни PI с висока размерност. Има и много примери за проблеми с ниска размерност (не повече от 10 променливи и уравнения), които изискват хиляди итерации за постигане на конвергенция.

В тези случаи се използва симплексният метод, който е итеративна (стъпка по стъпка) процедура за определяне на оптималното решение на проблем с линейно програмиране. Изчисленията, използващи симплексния метод, започват с идентифициране на осъществимо решение, след което се търсят други осъществими решения и се проверяват възможностите за тяхното подобряване. Преходът от едно решение към друго продължава, докато нови подобрения вече не са възможни. Стандартните компютърни програми са широко използвани, които използват симплексния метод за решаване на управленски проблеми, които могат да бъдат представени като проблеми с линейно програмиране.

Ако системата от линейни ограничения има специална структура, например, ако формира мрежов модел, тогава на стъпка 2, когато се намира оптималното решение на проблема с линейното програмиране, това обстоятелство може да се използва.

Идеята за пропорционално разпределение е реализирана под формата на двуетапен алгоритъм за изчисление, предложен от I.I. Dikin, който по същество използва свойството на метода на вътрешната точка за генериране на относително вътрешна точка на набор от оптимални решения на линейно програмиране проблем. Това свойство означава, че граничните стойности при неравенствата (2.3.2) - (2.3.4) се постигат само за тези променливи, които имат тези гранични стойности за всяко друго оптимално решение.

Страници: 1 2

Графичен метод за решаване на задача от линейно програмиране

Нека разгледаме ZLP в стандартна форма за случая на две променливи:

(10)

Нека системата от неравенства (10) е последователна (има поне едно решение). Всяко неравенство на тази система геометрично определя полуравнина с гранична линия Условията за неотрицателност определят полуравнини със съответните гранични линии И.

Тъй като системата е последователна, полуравнините, като изпъкнали множества, пресичащи се, образуват обща част, която е изпъкнало множество и е набор от точки, координатите на всяка от които са решение на тази система. Множеството от всички тези точки се нарича полигон за решение.Това може да бъде точка, сегмент, лъч, права линия, затворен многоъгълник или неограничена многоъгълна област.

Решаването на ZLP геометрично представлява търсене на точка в многоъгълника на решението, чиито координати осигуряват максимална (най-малка) стойност на целевата функция. Освен това всички точки на полиедъра са валидно решение.

Да разгледаме т.нар линия на нивоцелева функция z, тоест линията, по която тази функция приема същата фиксирана стойност: или

Алгоритъм за решаване на задача от линейно програмиране с помощта на графичния метод (брой променливи).

1. Построена е многоъгълна област от допустими решения на равнината, съответстваща на ограниченията. След това се конструира градиентният вектор

целева функция zвъв всяка точка от района на възможните решения.

2. Права линия (линия на функционално ниво z), перпендикулярно на вектора на градиента, се движи успоредно на себе си в посоката на вектора на градиента в случай на максимален проблем (и в обратната посока в случай на минимален проблем), докато напусне областта на възможните решения. Граничната точка (или точки) на региона са оптималните точки.

3. За да се намерят координатите на оптималната точка, е необходимо да се реши система от уравнения, която съответства на правите линии, пресечната точка на които образува тази точка.

Формулиране на основните типове задачи на ЛП, изграждане на техните математически модели

Стойността на целевата функция в тази точка ще бъде оптимална, а самите координати на точката ще бъдат решение на проблема с LP .

Пример.Решете задачата геометрично:

Нека построим многоъгълник от всички възможни решения OABCDи насочващия вектор на целевата функция (фиг. 1). Посоката на градиентния вектор показва посоката, в която целевата функция нараства. Тъй като разглежданата задача е да намерим максимума, ние преместваме линията, перпендикулярна на вектора, в посоката на този вектор, успоредна на себе си, докато тази линия напусне областта на възможните решения. На границата на района, в нашия случай в точката СЪС, и ще има решение на проблема. Точка СЪСе в пресечната точка на линии и . Следователно неговите координати се определят чрез решаване на системата от тези уравнения:

от къде т.е. точка СЪСима координати (6, 4).

Максимумът (максималната стойност на целевата функция) е равен на: Отговор:с оптимално решение, т.е. максималната печалба може да бъде постигната чрез производство на 6 единици от първия и 4 единици от втория продукт.

ВЪВЕДЕНИЕ

Съвременната икономическа теория, както на микро, така и на макро ниво, включва математическите модели и методи като естествен, необходим елемент. Използването на математиката в икономиката позволява, първо, да се идентифицират и формално опишат най-важните, съществени връзки между икономическите променливи и обекти: изследването на такъв сложен обект изисква висока степен на абстракция. Второ, от ясно формулирани първоначални данни и връзки, използващи дедуктивни методи, могат да се получат заключения, които са адекватни на обекта, който се изучава, в същата степен, както и направените предпоставки. Трето, методите на математиката и статистиката ни позволяват индуктивно да получим нови знания за даден обект: да оценим формата и параметрите на зависимостите на неговите променливи, които са в най-голямо съответствие със съществуващите наблюдения. И накрая, четвърто, използването на езика на математиката позволява точно и компактно да се представят разпоредбите на икономическата теория, да се формулират нейните концепции и заключения.

Математическите модели, използвани в икономиката, могат да бъдат разделени на класове според редица характеристики, свързани с характеристиките на моделирания обект, целта на моделирането и използваните инструменти: микро- и макроикономически модели, теоретични и равновесни, статистически и динамични.

Същността на методите за оптимизация е, че въз основа на наличието на определени ресурси се избира метод на тяхното използване (разпределение), който осигурява максимума (минимума) на показателя, който ни интересува.

Всички основни раздели на математическото програмиране (планиране) се използват като методи за оптимизация в икономиката.

Математическа дисциплина, която се занимава с изучаването на екстремни (максимални или минимални) проблеми на управлението и планирането и разработването на методи за тяхното решаване, се нарича математическо програмиране.

Като цяло, математическата формулировка на екстремалния проблем се състои в определяне на най-голямата или най-малката стойност на целевата функция
предвид това ,

където и са дадени функции и са някои реални числа.

В зависимост от вида на целевата функция и ограниченията математическото програмиране се разделя на линейно и нелинейно. Повечето

Изследваният клон на математическото програмиране е линейното програмиране.

Определение.

Проблем с линейното програмиране (страница 1 от 3)

Линейно програмиране – науката за методите за използване и намиране на екстремни (най-големи и най-малки) стойности на линейна функция, чиито неизвестни са обект на линейни ограничения.

Тази линейна функция се нарича целева функция, а ограниченията под формата на уравнения или неравенства се наричат система от ограничения.

Определение. Математическият израз на целева функция и нейните ограничения се нарича математически модел на икономически проблем.

Нека разгледаме някои проблеми с линейното програмиране (LPP).

1. Проблем с използването на ресурсите (проблем с планирането на производството).

За производство на различни продукти Фирмата използва три различни вида суровини. Норми за разход на суровини за производството на един продукт , както и общия брой

суровините от всеки вид, които могат да бъдат използвани от предприятието, са дадени в табл.

Съставете производствен план за продукти, в който общата себестойност на всички продукти, произведени от предприятието, е максимална.

Нека изградим математически модел на този проблем.

Нека означим с необходимото производство на продукти, странични продукти,

чрез – продукти.

Тъй като има разходни стандарти за всеки вид суровина, тогава можем да намерим общата цена на всеки вид суровина за производството на всички продукти. От таблицата следва, че общият обем на суровините от тип I ще бъде, II -
,

III –
. И тъй като има ограничения за фонда от суровини, следователно общият обем на всеки вид суровина трябва да бъде не повече от общото количество суровини, т.е.

получаваме следната система от неравенства

(1)

От икономическа гледна точка, променливи може да приема само неотрицателни стойности:

(2)

Цената на всички продукти от този тип ще бъде – – Съответно общата цена на продуктите, произведени от предприятието, ще бъде (3)

Трябва да намерим тази функция. По този начин сред всички неотрицателни решения на система (1) е необходимо да се намери такова, при което функция (3) приема максимална стойност.

Този проблем може лесно да се обобщи за случая на производство на видове продукти, използващи видове суровини (ресурси).

Нека означим с – брой единици продукти, планирани за производство, – запас от – вид ресурси, – специфично потребление на – тия ресурс за производство на – тия продукти. – печалба от продажба на единица продукт – вид.

Тогава икономико-математическият модел на проблема с използването на ресурсите в общата формулировка ще приеме формата: намерете такъв план
изход, който удовлетворява основната система от ограничения

допълнителна система от ограничения

в която е целевата функция

приема максималната стойност.

Коментирайте.За създаване на математически модел на ZLP е необходимо:

– въвеждане на обозначения на променливи;

– въз основа на целта на икономическото изследване, създайте целева функция;

– като се вземат предвид ограниченията при използването на икономически показатели на проблема и техните количествени модели, напишете система от ограничения.

Решаването на проблемите на линейното програмиране се основава на концепциите на аналитичната геометрия в – мерно векторно пространство.

Привеждане на общото ЗЛП в каноничен вид.

Общият изглед на ZLP е следният:

(1)

(2)

(3)

където връзката (1) е целевата функция, (2) е системата от основни ограничения, (3) е системата от допълнителни ограничения.

Съотношения (2) и (3) образуват пълна система от ограничения.

Привеждането на системата от основни ограничения до канонична форма се осъществява чрез въвеждане на допълнителни неотрицателни променливи с коефициенти „+1“, ако има неравенства на формата и „-1“, ако има неравенства на формата. Допълнителни променливи се включват в целевата функция с нулеви коефициенти.

Определение . Казва се, че ZLP е даден в канонична форма, ако неговата система от основни ограничения е представена чрез уравнения.

Определение. Казва се, че PLP е даден в стандартна форма на канонична форма, ако са изпълнени следните условия:

1) системата от основни ограничения е представена с уравнения и всички те са линейно независими;

2) броят на уравненията е по-малък от броя на променливите;

3) проблемът за минимизиране на целевата функция е решен;

4) десните части на системата от главни ограничения са неотрицателни;

5) всички променливи също са неотрицателни.

В повечето методи за решаване на проблеми с линейно програмиране се приема, че системата от ограничения се състои от уравнения и естествени условия за неотрицателността на променливите.

Въпреки това, когато се създават модели за много проблеми, ограниченията се формират главно под формата на система от неравенства, така че е необходимо да можете да преминете от система от неравенства към система от уравнения.

Това може да стане по следния начин:

Нека вземем линейното неравенство

и добавете към лявата му страна определена стойност, така че неравенството да се превърне в равенство

Освен това тази стойност е неотрицателна.

Пример

Приведете проблема с линейното програмиране в канонична форма:

Решение:

Нека преминем към задачата за намиране на максимума на целевата функция.

За да направим това, променяме знаците на коефициентите на целевата функция.

За да преобразуваме второто и третото неравенство на системата от ограничения в уравнения, въвеждаме неотрицателни допълнителни променливи x 4 x 5 (в математическия модел тази операция е отбелязана с буквата D).

Променливата x 4 се въвежда в лявата страна на второто неравенство със знака „+“, тъй като неравенството има формата „≤“.

Променливата x 5 се въвежда в лявата страна на третото неравенство със знака „-“, тъй като неравенството има формата „≥“.

Променливите x 4 x 5 се въвеждат в целевата функция с коефициент. равно на нула.

Записваме проблема в канонична форма:

СИМПЛЕКСЕН МЕТОД ЗА РЕШАВАНЕ НА ЗАДАЧИ НА ЛИНЕЙНО ПРОГРАМИРАНЕ

Този метод е метод за целенасочено изброяване на референтни решения на задача на линейно програмиране. Тя позволява в краен брой стъпки или да се намери оптимално решение, или да се установи, че няма оптимално решение.

Алгоритъм на симплексния метод за решаване на задачи от линейното програмиране

За да разрешите проблем с помощта на симплексния метод, трябва да направите следното:

1. Приведете проблема в канонична форма

Тема 8. Линейно програмиране

Намерете първоначалното решение за поддръжка с „основа на единица“ (ако няма решение за поддръжка, тогава проблемът няма решение поради несъвместимостта на системата от ограничения)

3. Изчислете оценките на векторните декомпозиции въз основа на референтното решение и попълнете таблицата на симплексния метод

4. Ако критерият за уникалност на оптималното решение е изпълнен, тогава решението на задачата приключва

5. Ако условието за съществуване на набор от оптимални решения е изпълнено, тогава всички оптимални решения се намират чрез просто изброяване

Пример за решаване на задача по симплексния метод

Пример 1

Решете задачата, като използвате симплексния метод:

Минимизиране на стойността на функцията

F = 10×1 – 4×3 макс

При наличие на ограничения под формата на неравенства

Привеждаме проблема в каноничен вид.

За да направим това, въвеждаме допълнителна променлива x 5 с коефициент +1 от лявата страна на първото ограничение на неравенството. Променливата x 5 е включена в целевата функция с коефициент нула (т.е. не е включена).

Получаваме:

F = 10×1 – 4×3+0∙x5 макс

При наличие на ограничения под формата на неравенства

Ние намираме първоначалното решение за поддръжка. За да направим това, приравняваме свободните (неразрешени) променливи на нула x1 = x3 = 0.

Получаваме еталонното решение X1 = (0,0,0,5,9/15,6) с единична основа B1 = (A4, A5, A6).

Изчисляваме оценки на разширения на вектори на условия въз основа на референтното решение, използвайки формулата:

Δ k = C b X k - c k

· C b = (c 1 , c 2 , … , c m) - вектор на коефициентите на целевата функция за основните променливи

· X k = (x 1k , x 2k , … , x mk) - вектор на разширение на съответния вектор A k според базата на еталонното решение

· C k - коефициент на целевата функция за променливата x k.

Оценките на векторите, включени в основата, винаги са равни на нула.

Референтното решение, коефициентите на разширение и оценките на разширенията на векторите на условието въз основа на референтното решение са записани в симплексна таблица:

В горната част на таблицата, за по-лесно изчисляване на оценките, са написани коефициентите на целевата функция. В първата колона "B" се записват векторите, включени в основата на еталонното решение. Редът, в който са записани тези вектори, съответства на броя на разрешените неизвестни в уравненията на ограниченията. Във втората колона на таблицата "C b" в същия ред са записани коефициентите на целевата функция за основните променливи. При правилното подреждане на коефициентите на целевата функция в колоната "C b" оценките на единичните вектори, включени в основата, винаги са равни на нула.

В последния ред на таблицата с оценки на Δ k в колоната "A 0" са записани стойностите на целевата функция върху референтното решение Z (X 1).

Първоначалното опорно решение не е оптимално, тъй като в максималния проблем оценките Δ 1 = -2, Δ 3 = -9 за векторите A 1 и A 3 са отрицателни.

Според теоремата за подобряване на опорното решение, ако в максимален проблем поне един вектор има отрицателна оценка, тогава можете да намерите ново опорно решение, при което стойността на целевата функция ще бъде по-голяма.

Нека определим кой от двата вектора ще доведе до по-голямо увеличение на целевата функция.

Увеличението на целевата функция се намира по формулата:

Изчисляваме стойностите на параметъра θ 01 за първата и третата колона по формулата:

Получаваме θ 01 = 6 за l = 1, θ 03 = 3 за l = 1 (Таблица 26.1).

Намираме нарастването на целевата функция при въвеждане на първия вектор в основата

ΔZ 1 = - 6*(- 2) = 12,

и третият вектор ΔZ 3 = - 3*(- 9) = 27.

Следователно, за по-бърз подход към оптималното решение е необходимо да се въведе вектор A3 в основата на референтното решение вместо първия вектор на основата A6, тъй като минимумът на параметъра θ 03 се постига в първия ред ( l = 1).

Извършваме трансформацията на Йордан с елемента X13 = 2, получаваме второто референтно решение

X2 = (0,0,3,21,42,0)

с основа B2 = (A3, A4, A5).

(Таблица 26.2)

Това решение не е оптимално, тъй като вектор A2 има отрицателен резултат Δ2 = - 6.

За да се подобри решението, е необходимо да се въведе вектор A2 в основата на референтния разтвор.

Определяме номера на вектора, получен от основата. За да направим това, изчисляваме параметъра θ 02 за втората колона, той е равен на 7 за l = 2.

Следователно, ние извличаме втория базисен вектор A4 от основата.

Извършваме трансформацията на Йордан с елемента x 22 = 3, получаваме третото опорно решение

X3 = (0,7,10,0,63,0)

B2 = (A3, A2, A5) (Таблица 26.3).

Това решение е единственото оптимално, тъй като за всички вектори, които не са включени в основата, оценките са положителни

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Отговор: max Z(X) = 201 при X = (0,7,10,0,63).

⇐ Предишен123456789Следващ ⇒

Т10. Постановка на задачата за линейно програмиране

Математически моделИкономическият проблем е набор от математически зависимости, които описват икономическия процес.

За да съставите математически модел, трябва:

1. изберете променливи на задачата;

2. създава система от ограничения;

3. задайте целевата функция.

Променливи на задачитесе наричат величините x 1, x 2,..., x n, които цялостно характеризират икономическия процес. Те обикновено се записват като вектор X = (x 1, x 2,…, x n).

Проблемна ограничителна системае набор от уравнения и неравенства, които са удовлетворени от променливите на проблема и които следват от ограничените ресурси и други икономически условия, например положителността на променливите. Като цяло те изглеждат така:

Целевата функция се наричафункция F(X) = f(x 1, x 2,..., x n) от променливи на задачата, която характеризира качеството на задачата и чийто екстремум трябва да бъде намерен.

Обща задача за математическо програмиранесе формулира по следния начин: намерете променливите на задачата x 1, x 2,..., x n, които осигуряват екстремума на целевата функция

F(X) = f(x 1, x 2,…, x n) ® max (min) (2)

и отговарят на системата от ограничения (1).

Ако целевата функция (2) и системата от ограничения (1) са линейни, тогава задачата за математическо програмиране се нарича проблем с линейно програмиране (LPP).

Извиква се вектор X (набор от проблемни променливи). приемливо решение, или плана ZLP, ако удовлетворява системата от ограничения (1). Нарича се допустим план X, който осигурява екстремум на целевата функция оптимално решениеЗЛП.

2. Примери за съставяне на математически модели на икономически проблеми

Изследването на конкретни производствени ситуации води до ZLP, които се интерпретират като проблеми за оптималното използване на ограничените ресурси.

1.Проблем с оптимален производствен план

За производството на два вида продукти T 1 и T 2 се използват три вида ресурси S 1, S 2, S 3. Ресурсните резерви, броят на ресурсните единици, изразходвани за производството на единица продукт, както и печалбата от продажбата на единица продукт са показани в таблицата:

Изисква се да се намери производствен план, който да максимизира печалбата от продажбата му.

Решение.

Да означим x 1, x 2 – броят на единиците продукция, съответно Т 1 и Т 2, планирани за производство. За да ги произведете, ще са ви необходими (x 1 + x 2) единици ресурс S 1, (x 1 + 4x 2) единици ресурс S 2, (x 1) единици ресурс S 3. Потреблението на ресурси S 1 , S 2 , S 3 не трябва да надвишава техните запаси, съответно 8, 20 и 5 единици.

Тогава икономико-математическият модел на проблема може да се формулира по следния начин:

Намерете производствения план X = (x 1, x 2), който удовлетворява системата от ограничения:

и състояние,

при което функцията приема максималната стойност.

Проблемът може лесно да се обобщи за случая на производство на n вида продукти с използване на m вида ресурси.

2.Проблем с оптималната диета

Има два вида храни, K 1 и K 2, съдържащи хранителни вещества S 1, S 2 и S 3. Съдържанието на броя на хранителните единици в 1 kg от всеки вид фураж, необходимия минимум хранителни вещества, както и цената на 1 kg фураж са показани в таблицата:

Необходимо е да се създаде ежедневна диета с минимални разходи, в която съдържанието на всеки вид хранително вещество да не бъде по-малко от установената граница.

Решение.

Нека обозначим x 1, x 2 – количеството фураж К 1 и К 2, включени в дневната диета. Тогава тази диета ще включва (3x 1 + x 2) единици хранително вещество S 1, (x 1 + 2x 2) единици хранително вещество S 2, (x 1 + 6x 2) единици хранително вещество S 3. Тъй като съдържанието на хранителни вещества S 1, S 2 и S 3 в диетата трябва да бъде съответно 9, 8 и 12 единици, икономическият и математическият модел на проблема може да се формулира, както следва:

Създайте дневна дажба X = (x 1, x 2), която отговаря на системата от ограничения:

и състояние,

при което функцията приема минималната стойност.

PAP формуляри за запис

В ZLP се изисква да се намери екстремумът на линейната целева функция:

с ограничения:

и условието за неотрицателност

където a ij, b i, c j ( , ) са дадени постоянни стойности.

Така е записано в ЗЛП общформа. Ако системата от ограничения съдържа само неравенства, тогава LLP се представя в стандартенформа. Каноничен (основен)Формата на нотация ZLP е нотация, когато системата от ограничения съдържа само равенства. Така че горните ZLP са написани в стандартна форма.

Общата, стандартната и каноничната форма на ZLP са еквивалентни в смисъл, че всяка от тях може да бъде пренаписана в различна форма с помощта на прости трансформации. Това означава, че ако има начин за решаване на един от посочените проблеми, тогава може да се определи оптималният план за всеки от проблемите.

За да се премине от една форма на запис на PLP към друга, човек трябва да може да премине от ограничения за неравенство към ограничения за равенство и обратно.

Ограничението за неравенство (£) може да бъде преобразувано в ограничение за равенство чрез добавяне на допълнителна неотрицателна променлива към лявата му страна, а ограничението за неравенство (³) може да бъде преобразувано в ограничение за равенство чрез изваждане на допълнителна неотрицателна променлива от неговата лява страна. Броят на въведените допълнителни неотрицателни променливи е равен на броя на трансформираните ограничения на неравенството.

Вход допълнителните променливи имат известен икономически смисъл. По този начин, ако ограниченията на първоначалния PPP отразяват потреблението и наличността на ресурси, тогава стойността на допълнителната променлива PPP в канонична форма е равна на обема на неизползвания съответен ресурс.

Пример 1. Напишете в каноничната форма на ЗЛП:

с ограничения:

Решение.

Целевата функция остава непроменена:

Системата от неравенства се трансформира в система от равенства:

При решаване на ЗЛП чрез графичния метод е необходим преход от каноничната форма към стандартната форма.

За да приведете ПЧП в стандартна форма, използвайте Метод на Джордан-Гаус SLAU решения. За разлика от метода на Гаус, при който разширената матрица на системата се редуцира до поетапна форма, при метода на Джордан–Гаус, единичната матрица се формира като част от разширената матрица. Следователно тук не се изисква обръщане.

За да конвертирате оригиналния каноничен ZLP в еквивалентен стандартен ZLP:

а) в разширената матрица на ограничителната система е избран ненулев елемент a qp. Този елемент се нарича разрешителени q е i ред и p-та колона се наричат разделителен ред и разделителна колона.

б) разрешителният ред се пренаписва без промяна и всички елементи на разрешителната колона, с изключение на разрешителния, се заменят с нули. Останалите елементи на разширената матрица се определят с помощта на „правилото на правоъгълника“:

Нека разгледаме четири елемента от разширената матрица: елемент a ij, който трябва да бъде трансформиран, разрешаващ елемент a qp и елементи a i p и a qj. За да се намери елементът a ij, трябва да се извади от елемента a ij произведението на елементите a i p и a qj, разположени в противоположните върхове на правоъгълника, разделено на разделящия елемент a qp:

в) в същото време разрешените неизвестни се изключват от целевата функция. За да направите това, коефициентите на целевата функция се записват в последния ред на разширената матрица. Изчисленията вземат предвид, че активиращият елемент в последния ред не може да бъде избран.

Пример 2. Редуцирайте до стандартна форма:

Решение.

Използвайки метода на Йордан–Гаус, свеждаме системата от уравнения-ограничения на ZLP до еквивалентна система от неравенства. Нека изберем третия елемент от първия ред като разрешаващ елемент:

Числото -9, получено в последната колона на последния ред, трябва да бъде записано в целевата функция с обратен знак. В резултат на трансформациите ZLP приема формата:

защото променливите x 2 и x 3 са неотрицателни, след което ги отхвърляме, можем да напишем ZLP в симетрична форма:

В каноничната форма на ZLP целевата функция може да бъде минимизирана или максимизирана. Да преминете от намиране на максимума към намиране на минимума или обратно, достатъчно е да промените знаците на коефициентите на целевата функция: F 1 = - F. Полученият проблем и оригиналният ZLP имат едно и също оптимално решение, а стойностите на целевите функции на това решение се различават само в знак.

Свойства на ЗЛП

1. Множеството от всички възможни решения на системата от ограничения на задача на линейно програмиране е изпъкнало.

Множеството от точки се нарича изпъкнал, ако съдържа целия сегмент, свързващ произволни две точки от това множество.

Според тази дефиниция многоъгълникът на фиг. 1а е изпъкнало множество, но многоъгълникът на фиг. 1b не е, тъй като отсечката MN между двете си точки M и N не принадлежи изцяло на този многоъгълник.

Не само многоъгълниците могат да бъдат изпъкнали множества. Примери за изпъкнали множества са кръг, сектор, сегмент, куб, пирамида и др.

2. Ако ZLP има оптимално решение, тогава линейната функция приема максимална (минимална) стойност в една от ъгловите точки на полиедъра на решението. Ако една линейна функция приема максимална (минимална) стойност в повече от една ъглова точка, тогава тя я приема във всяка точка, която е изпъкнала линейна комбинация от тези точки.

Точка X се нарича изпъкнала линейна комбинацияточки X 1, X 2,…, X n, ако са изпълнени следните условия:

X = α 1 X 1 +α 2 X 2 +…+ α n X n,

α j ≥ 0, Σα j = 1.

Очевидно в специалния случай за n = 2 изпъкнала линейна комбинация от две точки е отсечката, която ги свързва.

3. Всяко допустимо базисно решение от системата от ограничения на каноничната ZLP отговаря на ъглова точка на полиедъра на решението и обратно, на всяка ъглова точка на полиедъра на решението отговаря допустимо базисно решение.

От последните две свойства следва: ако ZLP има оптимално решение, то то съвпада с поне едно от допустимите си базисни решения.

Така екстремумът на линейната ZLP функция трябва да се търси сред крайния брой нейни допустими базисни решения.

2. указания за използване на мат. модели в икономиката.

Математическите модели позволяват да се определят оптималните стойности на неизвестни параметри на икономическите системи, което е важно в процеса на вземане на решения. Математическото програмиране предоставя именно апарата, който позволява да се оптимизира процеса на избор на най-добрите варианти на планове в процеса на управление на икономическите системи.

Използва се в математическата статистика, методите за оптимизация, икономическите методи. кибернетика, експериментални проблеми.

При изучаване на сложни процеси и явления в икономиката много често се използва моделирането - много специфично, специфично отразяване на характеристиките на обекта, който се изучава. Същността му се състои в това, че изследваното явление се възпроизвежда в експериментални условия по модел в различен времеви и пространствен мащаб. Моделът е специално създаден обект, с помощта на който се възпроизвеждат много специфични характеристики на изследваната система с цел нейното изследване. Математическото моделиране е най-модерният и в същото време ефективен метод за получаване на информация за обекта, който се изследва. Това е мощен инструмент за анализ в икономиката. Резултатите от изследване с помощта на модели ще бъдат от практически интерес, когато изграденият модел е достатъчно адекватен на разглежданото явление, т.е. достатъчно добре отразява реалната ситуация.

2. математическото програмиране като наука, неговата структура. Проблеми с оптимизацията. Трудности при прилагането на класическите методи за оптимизация при решаване на икономически задачи.

Математическо програмиранее клон на приложната математика, който разработва теоретични основи и методи за решаване на екстремални проблеми.

Математическото програмиране включва няколко раздела, като основните са следните:

1. Линейно програмиране.Този раздел включва задачи, в които неизвестни променливи влизат в математически зависимости на първа степен.

2. Нелинейно програмиране.Този раздел включва задачи, при които целевата функция и (или) ограниченията може да са нелинейни.

3. Динамично програмиране.Този раздел включва задачи, при които процесът на решаване може да бъде разделен на отделни етапи.

4. Целочислено програмиране.Този раздел включва проблеми, при които неизвестните променливи могат да приемат само цели числа.

5. Стохастично програмиране.Този раздел включва проблеми, които съдържат случайни променливи в целевата функция или ограничения.

6. Параметрично програмиране.Този раздел включва задачи, при които коефициентите за неизвестни променливи в целевата функция или ограниченията зависят от определени параметри.

За решаване на проблеми с математическото програмиране е трудно да се използват класически методи за намиране на екстремум, тъй като в задачите на математическото програмиране целевата функция достига своята екстремна стойност на границата на областта на допустимите стойности на неизвестни променливи и производните не съществуват при граничните точки. Пълното търсене на допустимите точки е невъзможно поради значителния им брой.

3. Концепцията за математически модел, видове математика. модели

Математически моделе абстракция на реално явление или процес, написана с математически символи и изрази. Математическите модели на икономическите процеси и явления се наричат икономико-математически модели

Моделите са разделени на:

1. линеен, в който всички зависимости се описват с линейни отношения,

2. нелинейни, в които има нелинейни зависимости;

3. стохастичен, които отчитат случайния характер на изследваните процеси,

4. детерминистичен, които отчитат средните стойности на всички параметри.

5. динамиченмодели, в които изследваните системи се разглеждат в развитие през няколко периода,

6. статичен, при което факторът време не е отчетен.

7. оптимизациямодели, при които изборът се прави в зависимост от екстремизациянякакъв критерий

8. неоптимизиране, в които няма критерий за оптималност.

9. макромодели(цялата ферма като цяло)

10. микромодели(отделни връзки или процеси на икономиката).

Видове математически модели: линейни, нелинейни, квадратични, целочислени, дискретни, параметрични, дробни линейни, динамични, стохастични

4. Обща постановка на задачи по математическо програмиране.

Нека разгледаме общата формулировка на задачата за математическо програмиране.

Общият проблем на математическото програмиране е да се определи оптималната стойност на целевата функция, а стойностите на променливите трябва да принадлежат към определен диапазон от приемливи стойности. Математически, определянето на оптималното решение се изразява в намиране на екстремума (max или min) на функция от много променливи

Z = f (x1, x2, …, xn)

в даден диапазон от промени в тези променливи

gi (x1, x2,…, xn) Риби (i = 1, 2,…, m),

където Ri е един от знаците ≥, =, ≤.

5. Проблемът за оптимизиране на производствения план. Икономическа постановка и конструиране на математически модел на задачи.

Икономическа декларация:

Фирмата произвежда низползвани видове продукти мвидове суровини. За производството на единица продукт се използва строго определено количество суровина от един или друг вид. Суровините от всеки тип са ограничени в предприятието. Предприятието получава определена печалба от продажбата на единица продукция. Необходимо е да се намери производствен план, при който предприятието ще получи максимална обща печалба.

Математическо твърдение:

Нека j е индексът на вида продукт j = 1, n

i – индекс на вид ресурс i = 1, m

и ij – разходи за суровини аз-ти вид продукция на единица продукция й-ти тип;

Аi – дадено ограничение на наличния обем ресурси от i-ти вид;

Рj – печалбата, получена от продажбата на единица продукт от j-ти вид;

xj – обем на произведената продукция от j-ти вид.

z = Р1x 1 + Р2x 2 + … +Pnx n → макс

а11x 1 + а12x 2 +…+ а1nx n ≤ A1

а21x 1 + а22x 2 +…+ а2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +...+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Проблем с диетата. Икономическа постановка и изграждане на математически модел на проблема.

Икономическа декларация

В някои ферми се угояват животни. Използва се за угояване нвидове фуражи. Съдържанието на хранителни вещества (калций, фосфор и др.) В единица фураж от всеки вид е известно. За пълноценното хранене на животните е необходимо да се консумират хранителни вещества не по-малко от посочените количества. Цената на единица от всеки фураж е известна. Необходимо е да се определи диетата за хранене на животните, при която общите разходи за угояване ще бъдат минимални.

Математическо твърдение:

j – индекс на вида на фуража, j = 1, n

i – индекс на вида на хранителното вещество, i = 1, m

Аi – необходимата дневна консумация на хранително вещество от i тип;

Cj е цената на единица фураж от j-тия вид.

Нека въведем неизвестни променливи:

xj е дневният обем на хранене на животните с j-тия вид храна.

От гледна точка на въведената нотация, този проблем може да бъде написан по следния начин:

а11x1 + а12x2 +…+ а1nxn ≥ A1

а21x1 + а22x2 +…+ а2nxn ≥ A2

…………………………….

am1x1 + аm2x2 +…+ и mnxn ≥Am

xj ≥ 0, j = 1, n

7. Транспортен проблем . Икономическа постановка и изграждане на математически модел на проблема.

Икономическа декларация :

На разположение мдоставчици на хомогенни продукти и нпотребителите на тези продукти. Единичните разходи за доставка на единица продукт от всеки доставчик до всеки потребител са известни. Доставчиците имат ограничени запаси. Известни са и продуктовите нужди на всеки потребител.

Необходимо е да се определи план за транспортиране на продуктите от доставчиците до потребителите, при който общите транспортни разходи ще бъдат минимални.

Математическо твърдение :

Нека въведем обозначенията за посочените параметри:

j – потребителски индекс, j = 1, n

i – индекс на доставчика, i = 1, m

Аi – обем налични продукти от i-тия доставчик;

Вj – обемът на търсенето на продукти на j-ия потребител;

Cij е единичната цена за транспортиране на единица продукт от i-тия доставчик до j-тия потребител.

Нека въведем неизвестни променливи:

xij е обемът на транспортиране на продукти от i-тия доставчик до j-тия потребител.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → мин

Ограничения на проблема.

I. От всеки доставчик можете да изтеглите продукти не повече от наличното количество:

x11 + x12 +...+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Потребността на всеки потребител от продукти трябва да бъде задоволена

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Условие за неотрицателност: xij ≥0, i = 1, m ; j = 1, n

Често е удобно да напишете математическо изявление в свита форма:

, i = 1, m , j = 1, n

8. Проблемът с избора на задачи или задачи. Икономическа постановка и изграждане на математически модел на проблема.

Икономическа декларация :

На разположение нвидове работа и низпълнители. Всеки от изпълнителите може да изпълнява всяка, но само една работа. Цената за изпълнение на всяка работа от всеки изпълнител е уточнена. Необходимо е да се възложат изпълнители на работата по такъв начин, че общите разходи за изпълнение на работата да бъдат минимални.

Математическо твърдение .

Нека въведем обозначенията за дадените параметри.

i – индекс на работа, i = 1, m

j – индекс на изпълнителите, j = 1, n

Cij е цената за извършване на i-тата работа от j-тия изпълнител.

Нека въведем неизвестни променливи. В тази задача неизвестните променливи могат да приемат само две стойности: 0 или 1. Такива променливи се наричат нула.

1 - ако j-тият изпълнител е назначен на i-та работа;

0 - в противен случай.

По отношение на въведената нотация, този проблем ще бъде написан по следния начин:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n -1)x(n-1)(n-1) + Сnnxnn → min

I група ограничения.

Само един изпълнител трябва да бъде назначен за всяка работа:

x11 + x12 +...+ x1n = 1

x21 + x22 +...+ x2n = 1

……………………..

xn1 + xn2 +...+ xnn = 1

II. група ограничения.

Всеки изпълнител може да изпълнява само една работа:

x11 + x21 +...+ xn1 = 1

x12 + x22 +...+ xn2 = 1

……………………..

x1n + x2n +...+ xnn = 1

x ij = (0,1) i = 1, n; j = 1, n

9. Проблем с рязане на материали. Икономическа постановка и изграждане на математически модел на проблема.

Икономическа декларация .

Оригиналният материал със същия размер се доставя за рязане. Тя трябва да бъде нарязана на парчета с определен размер и в определено количество, така че общите отпадъци да са минимални.

Математическо твърдение .

Нека въведем следната нотация:

i – индекс на детайла,

Аi – необходимия брой заготовки от i-тия тип;

j – индекс на опциите за рязане,

Сj – размерът на отпадъците при разкрояване на единица изходен материал по вариант j;

и ij е броят на заготовките от i-тия тип при разкрояване на единица изходен материал по вариант j.

Нека въведем обозначението за неизвестни променливи.

xj е количеството суровина, нарязано по вариант j.

По отношение на въведената нотация, този проблем ще бъде написан по следния начин:

z = С1x1 + С2x2 + … +Сnxn → min

а11x1 + а12x2 +…+ а1nxn = A1

а21x1 + а22x2 +…+ а2nxn = A2

…………………………….

am1x1 + аm2x2 +…+ аmnxn = Am

xj ≥ 0, j = 1, n

Използването на математически модели позволява спестяване на суровини до 20%.

Математическият модел на рязане е изграден на два етапа.

На първия етап се изграждат опциите за рязане, в резултат на което стойностите на броя на опциите n, броят на заготовките от всеки тип, получени с различни опции за рязане (aij), както и стойностите на отпадъците (Cj) се определят.

Изграждането на опции за рязане за единица изходен материал се извършва под формата на следната таблица:

Опция №

Заготовка i1

Заготовка i2

Заготовка im

Заготовките се подреждат по ненарастващ размер. Изграждането на опции се извършва чрез метода на изчерпателно търсене.

10. Общ вид на проблемния модел на ЛП и неговите характеристики

Общата форма на ЗЛП е:

z = С1x1 + … + Сnxn max (мин.)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

В общ вид всеки символ R1, R2,…, Rm означава един от знаците: ≥, = или ≤.

Общата форма на проблемния модел на ЛП има следните характеристики.

1. Системата от ограничения се представя под формата на уравнения (твърди условия) и неравенства (нетвърди условия).

2. Условията за неотрицателност не се налагат на всички променливи

3. Целевата функция клони или към максимум, или към минимум.

11. Стандартна форма на проблемния модел на ЛП и неговите характеристики

Стандартната форма е както следва.

Намерете максимума или минимума на целевата функция z:

z = С1x1 + … + Сnxn → max (min) (1)

Предмет на следните ограничения:

а11 Х1 + а12 Х2 + … + а1n Хn ≤ а1

a21 X1 + a22 X2 + … + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ n

Характеристиките на стандартната форма на проблемния модел на LP са следните:

1. системата от ограничения е представена под формата на неравенства (нетвърди условия)

2. на всички променливи се налагат условия за неотрицателност

3. целевата функция клони към max или min

12. Канонична форма на проблемния модел на ЛП и нейните характеристики

Каноничната форма е:

Намерете минимума на целевата функция z:

z = С1x1 + … + Сnxn → min

Предмет на следните ограничения:

a11 X1 + a12 X2 + … + a1n Xn = a1

a21 X1 + a22 X2 + … + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

Характеристиките на каноничната форма са следните:

1. Системата от ограничения е представена под формата на уравнения (строги условия).

2. На всички променливи се налагат условия за неотрицателност

3. Целевата функция се стреми към

В някои източници целевата функция на проблема LP, представена в канонична форма, клони към максимум. Това се прави за удобство при решаването на проблема с помощта на алгоритъм, предназначен да максимизира целевата функция.

13. Възможен, допустим, оптимален опорен план на проблема, ОДЗ на проблема на ЛП

Определение 1.Стойностите на неизвестните променливи, които отговарят на всички ограничения на проблем с линейно програмиране, се наричат приемливо стойности на променливи или планове .

Определение 2.Наборът от всички планове за проблем с линейно програмиране се нарича домейн на допустимите стойности на променливите ( ОДЗ ).

Определение 3.Планът на задача за линейно програмиране, в която целевата функция приема минималната (или максималната) стойност на ODZ, се нарича оптимален .

14. Видове записи на задачи на LP: разгънати, свити, матрични, векторни.

Моделите на LP задачи могат да бъдат написани в различни форми.

1. Разширен изглед на записа на модела

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

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

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Свит изглед:

Xj ≥ 0, j = 1, n.

3. Модел на задачата LP в матрична форма:

X ≥ 0

Където

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

am1 am2 … amn X3 am

4. Модел на задачата LP във векторна форма:

Където

Х1 a11 a12 a1n a1

X2, a21, a22, a2n, a2

… … … … …

Хn am1 am2 am2 am

15. Преход от стандартната и обща форма на проблемите на LP към каноничната.Комуникационна теорема

За преход от обща или стандартна форма към канонична се използват следните техники.

1. Преобразуване на променливи. Ако някоя променлива Xk е неположителна (Xk ≤ 0), тогава се въвежда нова променлива Xk ", така че Xk " = –Xk. Очевидно е, че Xk " ≥ 0. След това във всяко ограничение и целева функция променливата Xk се заменя с [ – Xk "].

Ако някаква променлива Xt може да приема всякакви стойности, тогава тя се заменя с разликата на две неотрицателни променливи Xt' и Xt'', т.е. приема се, че Xt = Xt' – Xt'', където Xt' 0 ≥ и Xt'' ≥ 0.

2. Трансформация на ограниченията.Ако някое от ограниченията в модела има формата на неравенство, то се преобразува в равенство чрез добавяне (ако неравенството е от тип ≤) или изваждане (ако неравенството е от тип ≥) от лявата му страна. Тези променливи се наричат балансови променливи. Балансовите променливи са включени в целевата функция с нулеви коефициенти. Балансовата променлива приема стойността на индекса последователно след съществуващите. Ако, например, системата от ограничения има 5 променливи, тогава първата балансова променлива ще бъде X6, а втората ще бъде X7 и т.н.

16. Преход от каноничната форма на модела ZLP към стандартната

За да преминете от каноничната форма към стандартната, можете всеки от

уравнения, които трябва да бъдат заменени със система от неравенства:

Друг начин е да се намали системата от уравнения до специална форма и допълнително да се елиминират някои променливи.

Използвайки метода на Йордан-Гаус, ние избираме основната променлива във всяко уравнение. Тази селекция се извършва с помощта на еквивалентни (елементарни) трансформации на Гаус. Те включват:

а) умножаване на всяко уравнение по константа, различна от нула;

б) добавяне към всяко уравнение всяко друго уравнение, умножено по която и да е константа.

Преди трансформация е удобно да напишете оригиналната система от линейни уравнения под формата на матрица или таблица:

Записваме задачата в стандартна форма.

17. Концепцията за полуравнина хиперравнина, опорна хиперравнина.

18. Геометричен интерпретация на системата от ограничения и целевата функция в проблемите на ЛП

19. Изпъкнало множество: крайни (ъглови) точки на множеството. Изпъкнал многостен

ОпределениеМножество M се нарича изпъкнало, ако наред с произволни две точки, принадлежащи на това множество, съдържа и отсечка, която ги свързва.

Изпъкнал комплект

ОпределениеТочка x от множество M се нарича ъглова или крайна точка, ако не е вътрешна за нито един сегмент, изцяло принадлежащ на това множество.

Теорема 1. Всяка точка от сегмента може да бъде представена като изпъкнала комбинация от неговите ъглови точки.

x = λ 1 A + λ 2 V

λ 1, λ 2 ≥ 0 изпъкнала комбинация от точки на ъглови точки A и B

λ 1 + λ 2 = 1

Теорема 2. Всяка точка от изпъкнало затворено множество може да бъде представена като изпъкнала комбинация от неговите ъглови точки.

20. Алгоритъм на графичния метод за решаване на задачи на ЛП

1. Проверява се дали оригиналният ZLP е в стандартна форма; ако не е, тогава проблемът трябва да се преобразува в стандартна форма.

2. Броят на неизвестните променливи се проверява. Ако това число е повече от три, тогава проблемът не може да бъде решен графично (има други ефективни методи за решаване на такива задачи).

3. Диапазонът на допустимите стойности на променливите за ZLP е конструиран.

4. Изгражда се водещ вектор ° С .

5. Първоначалният изокоел се изчертава през ODZ (перпендикулярно на вектора на посоката).

6. Първоначалният изокоел се премества мислено по посока на вектора ° С, ако е определена максималната стойност на целевата функция, или в обратна посока, ако е определена нейната минимална стойност, докато изокоелът стане референция към ODZ. Пресечните точки на еталонния изокоел и ODZ ще бъдат оптималните точки на проблема.

7. За да се определят координатите на оптималната точка, е необходимо да се реши система от съответни линейни уравнения.

8. За да се намери оптималната стойност на целевата функция, е необходимо да се заменят оптималните стойности на променливите в целевата функция и да се изчисли нейната стойност.

20. графичен алгоритъм метод за решаване на LP задачи

Алгоритъм на графичния метод.

1. Чрез последователно конструиране на всяко от условията на системата от ограничения на проблема се осъществява изграждането на ODZ.

2. Насочващият вектор C се конструира с помощта на коефициентите на променливите на целевата функция.

3. Оригиналният изокоел се изчертава перпендикулярно на вектора на посоката през началото на координатите.

4. Първоначалният изокоел се премества мислено в посока на нарастващи стойности на вектора C, ако се определи максималната стойност на целевата функция, или в обратна посока, ако се определи минималната му стойност, докато изокоелът стане референтен към ОДЗ. Пресечните точки на еталонния изокоел и ODZ ще бъдат оптималните точки на проблема.

5. За да се определят координатите на оптималната точка, е необходимо да се реши система от съответни линейни уравнения за онези условия, в пресечната точка на които се намира оптималната точка.

6. За да се намери оптималната стойност на целевата функция, е необходимо да се заменят координатите на оптималната точка в целевата функция и да се изчисли нейната стойност.

23. теореми за обхвата на допустимите стойности на проблема с LP и за целевата функция

ODZ теорема.Областта на възможните решения на проблема с LP е изпъкнало множество (затворено и ограничено в n-мерно пространство)

Теорема 2. За целевата функция на задачата за линейно програмиране.

Целевата функция на ZLP приема оптималната си стойност в една от ъгловите точки на областта на допустимите стойности на променливите. Ако целевата функция приема оптималната си стойност в няколко ъглови точки, тогава тя приема същата стойност във всяка точка, която е изпъкнала комбинация от тези ъглови точки.

24. Теорема за ъгловата точка. Достатъчно и необходимо условие

25. Следствия от теоремата за свойствата на решенията на задачи на ЛП и изводи. Концепцията за референтен план.

Следствия от теоремите.

Определение. Планирайте = (x1,x2,…,xn), чиито положителни координати съответстват на линейно независими вектори, се нарича основен план на ЗЛП .

Следствие 1. Опорният план има най-много m положителни координати.

Ако има точно m положителни координати, тогава такъв опорен план се нарича неизроден, в противен случай изроден.

Следствие 2. Всяка ъглова точка на ODZ е референтен план.

27. Алгоритъм на симплексния метод.

При решаване на задачи на LP по симплексния метод е необходимо да се извърши следната последователност от действия.

1. Проверява се дали задачата LP е в канонична форма. Ако не, тогава е необходимо оригиналният модел да се преобразува в канонична форма.

2. Първоначалният референтен план и стойността на целевата функция за този референтен план са идентифицирани.

3. Построена е началната симплексна таблица.

4. Проверяват се стойностите на оценките за оптималност в индексния ред. Ако няма положителни оценки, тогава оптималното решение се изписва и алгоритъмът приключва работата си. В противен случай се изпълнява точка 5.

5. В основата се въвежда вектор, който съответства на най-голямата положителна оценка. Тази колона се нарича разрешаваща колона.

6. От основата се извлича вектор, който съответства на симплексното съотношение, изчислено по формулата 0< Ө ≤ . Данная строка называется разрешающей строкой.

7. Построена е нова симплексна таблица. Съответно се модифицират колони B и C B. Останалата част от таблицата се попълва от предишната с помощта на трансформации на Гаус, като индексният ред се счита за ред m+1 и също се трансформира с помощта на трансформации на Гаус. Нека да преминем към стъпка 4 от този алгоритъм.

След като съставите всяка таблица, можете да проверите правилността на изчисленията, като използвате формулите за изчисляване на оценките, дадени в предишния параграф.

28. избор на основа и изграждане на изходен опорен план при решаване на задачи по симплексния метод.

29. Симплексни таблици, попълването им. Формули за изчисляване на коефициентите на индексните линии.

30 . Теоремата за оптималност за плана на задача за линейно програмиране е следствие от теоремата за оценка на оптималността при решаване на проблеми с помощта на симплексния метод.

Теорема 1: Ако за някакъв вектор Ā j в системата

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + … + a 1 n X n = a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n = a 2

…………………………………………………..

X m + а mn +1 X m +1 + а mn +2 X m +2 + … + а mn X n = a m

Ако връзката Z j – c j > 0 е изпълнена, тогава планът X B0 не е оптимален и можем да преминем към план X B1, така че Z (X B1) ≤ Z (X B0).

Тук Z j = (C, Ā j) е скаларното произведение на векторите.

С – вектор, състоящ се от коефициенти на основните променливи на целевата функция Z

Ā j е вектор, състоящ се от коефициенти на разширение на съответния вектор в базисни вектори.

c j – коефициент на целевата функция Z за променлива X j

Последица от теореми: Ако за всички вектори Ā 1 , Ā 2 , …, Ā n на някакъв референтен план X отношението Z j – c j е изпълнено< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

По този начин теоремата и следствието позволяват да се определи дали следващият референтен план е оптимален и ако не е, тогава е необходимо да се премине към друг референтен план, в който стойността на целевата функция ще бъде по-малка.

Коментирайте. Теоремата и следствието предполагат, че проблемът е в канонична форма с минимална целева функция. Симплексният метод обаче може да се използва и за максимално решаване на задачи с целева функция. В този случай, когато се анализират стойностите на оценките, се използва тяхното противоположно значение, т.е. планът ще бъде оптимален, ако всички оценки за оптималност не са отрицателни (положителни или отрицателни).

31. Избор на вектора, въведен в базиса и изход от базиса. Симплексна релация.

За да преминете към нов референтен план, ви е необходим един от свободните вектори въведете в основата и изведете някои от базисните вектори. За да го въведем в основата, избираме вектор, който има поне една положителна координата. Нека такъв вектор е вектор A m+1.

разпад -

респ. вектор, кат ще бъде референтен план, ако неговите координати са неотрицателни и броят на положителните координати е равен на m.

Координатите на вектора X1 трябва да са неотрицателни, т.е. .

Ако , тогава тази координата ще бъде неотрицателна.

Нека минимумът във връзка (5) се получи при i = 1, тогава ако вземем

тогава първата координата на вектор 1 хще стане равно на нула.

Отношението (6) се нарича симплексна релация. Така че се преместихме от първоначалния референтен план 0 х(основни вектори A1,A2,…Am) към референтен план 1 х(базисни вектори A2,A3,…,Am,Am+1).

32. разрешителен елемент на масата, нейният избор. Правилото за пълни изключения на Jordan за преизчисляване на симплексна таблица.

33. Правилото на “четириъгълника” за преизчисляване на симплексната таблица

34. Знак за уникалността на оптимален план, набор от оптимални планове и отсъствието на оптимален план при решаване на задача на LP по симплексния метод.

При решаване на задачи по симплексния метод са възможни следните видове оптимални решения:

1. Уникалност . Ако оценките на всички свободни вектори са строго отрицателни, тогава полученият референтен план е оптимален и уникален. (вижте примера в предишния параграф).

2. Алтернативен оптимум (набор от оптимални решения).

Ако сред неположителните оценки на свободните вектори има поне една нула, тогава полученият референтен план ще бъде оптимален, но не и единственият. В този случай можете да преминете към други планове за поддръжка (в основата се въвеждат вектори, които съответстват на нулеви оценки) и след това да напишете общото оптимално решение под формата на изпъкнала комбинация от получените оптимални планове за поддръжка.

3. ZLP няма оптимално решение, тъй като целевата функция не е ограничена отдолу . Ако има положителна оценка в симплексната таблица и всички елементи на тази колона са отрицателни и нула, тогава този вектор може да бъде въведен в основата. Нито един от базисните вектори обаче не може да бъде извлечен от основата. От това следва, че е възможно по-нататъшно намаляване на целевата функция при преминаване към нереферентен план.

4. ЗЛП няма оптимално решение, тъй като системата от ограничения е противоречива. Тъй като при решаването на ZLP с помощта на обичайния симплексен метод трябва да има първоначален референтен план, системата от линейни уравнения със сигурност не е непоследователна. Следователно, такъв случай не може да възникне при решаване по обичайния симплексен метод.

5. Ако ODZ се състои от една точка, тогава решението на такъв проблем е тривиално и може да се получи без използване на симплексния метод.

35. В какви случаи се използва методът на изкуствената основа?

изкуствени.

36. Построяване на М-проблема в метода на изкуствената основа

Ако обаче проблемът с линейното програмиране е в канонична форма, базисните променливи не присъстват във всички уравнения, т.е. оригиналният референтен дизайн липсва. В този случай в тези уравнения, в които няма основни променливи, е необходимо да се добави някаква неотрицателна променлива с коефициент +1. Такава променлива се нарича изкуствени.

Трябва да се добави изкуствена променлива към целевата функция с много голямо положително число (тъй като целевата функция е да се намери минимумът). Това число се обозначава с латинската буква M. Може да се счита за равно на +∞. В тази връзка методът на изкуствената основа понякога се нарича М-метод. Тази трансформация на първоначалния проблем се нарича конструиране на разширен проблем. Ако решавате проблем с целева функция, за да намерите изкуствена променлива, трябва да я добавите към целевата функция с много голямо положително число (тъй като целевата функция е да намерите минимума). Това число се обозначава с латинската буква M. Може да се счита за равно на +∞. В тази връзка методът на изкуствената основа понякога се нарича М-метод. Тази трансформация на първоначалния проблем се нарича конструиране на разширен проблем. Ако даден проблем се решава с целева функция за намиране на максимума, тогава изкуствените променливи се включват в целевата функция с коефициент –M.

По този начин в разширения проблем имаме референтен дизайн (въпреки че някои от базовите променливи са изкуствени).

Изгражда се началната симплексна таблица.

37. конструиране на индексна линия при метода на изкуствената основа

Създава се първоначална симплексна таблица, в която индексният ред е разделен на два реда, тъй като оценките се състоят от два термина. На горния ред се изписва оценъчният член без М, а на долния - коефициентите за М. Знакът на оценката се определя от знака на коефициента за М, независимо от стойността и знака на члена без M, тъй като M е много голямо положително число.

По този начин, за да се определи векторът, който се въвежда в основата, е необходимо да се анализира долната линия на индекса. Ако изкуствен вектор е извлечен от основата, тогава не е необходимо съответната колона в следващите симплексни таблици да се изчислява, ако няма нужда да се получи решение на двойния проблем (вижте следващата тема).

След като всички изкуствени вектори бъдат извлечени от основата, долният ред ще има всички нулеви елементи с изключение на резултатите, съответстващи на изкуствените вектори. Те ще бъдат равни на –1. Такава линия може да бъде премахната от разглеждане и по-нататъшно решение може да се извърши с помощта на обичайния симплексен метод, ако няма нужда да се получи решение на двойствения проблем (вижте следващата тема).

38. Критерий за оптималност при метода на изкуствената основа. Знакът за изграждане на първоначалния справочен план на първоначалния проблем.

39. Алгоритъм за дуалния симплекс метод

Алгоритъм на двойния симплекс метод:

1. попълнете първата симплексна таблица по обичайния начин, без да обръщате внимание на знаците на свободните условия. Смята се, че такъв проблем трябва да има първоначална единица.

2. Изберете водещата линия според най-големия по абсолютна стойност отрицателен елемент от колоната със свободни членове A0

3. Изберете водещата колона според съотношението на най-малката абсолютна стойност на елементите на индексния ред към отрицателните елементи на водещия ред.

4. Преизчислете симплексната таблица, като използвате правилото за пълно елиминиране на Йордан

5. проверява получения план за допустимост. Знак за получаване на приемлив референтен план е липсата на отрицателни елементи в колона A0. Ако в колона A0 има отрицателни елементи, преминете към втората точка. Ако ги няма, тогава те продължават да решават възникналия проблем по обичайния начин.

6. Знак за получаване на оптимално решение с помощта на двойния симплекс метод е критерият за оптималност на конвенционалния симплекс метод.

41. Отворени и затворени транспортни модели. Преход от отворен транспортен модел към затворен.

Видове транспортни задачи.

На разположение мдоставчици на хомогенни продукти с известни запаси от продукти и нпотребители на тези продукти с дадени обеми от потребности. Известни са и единичните разходи за транспорт.

Ако сумата от обемите на запасите от продукти е равна на обема на нуждите на всички потребители, тогава тази задача се нарича затворен транспортен проблем

(т.е. ако ∑ Ai = ∑ Bj), в противен случай се извиква транспортната задача отворен. За да се реши един транспортен проблем е необходимо той да бъде затворен.

Отворен транспортен проблем може да се преобразува в затворен, както следва.

Нека ∑Ai > ∑Bj. В този случай е необходимо да се въведе фиктивен n+1 потребител с обем на нуждите ∑Ai – ∑Bj Единичните разходи за транспорт от доставчици до фиктивния потребител се приемат равни на 0, тъй като в действителност такъв транспорт няма да се осъществи и част от продуктите ще останат при доставчиците.

Ако ∑Bj > ∑Ai . В този случай е необходимо да се въведе фиктивен m+1 доставчик с обем на наличността ∑Bj – ∑Ai . Единичните разходи за транспортиране от фиктивния доставчик до потребителите се приемат равни на 0, тъй като в действителност такъв транспорт няма да бъде извършен и потребителите няма да получат част от продуктите.

42. Методи за конструиране на началното разпределение в транспортната задача: метод на северозападния ъгъл и метод на най-малкия елемент в матрицата.

Северозападен метод за изграждане на референтен план. Според този метод формирането на транспортни стойности започва от северозапад. ъгъл на масата, т.е. от клетка x11. По този метод първо се разпределят стоките на първия доставчик. Нещо повече, първият доставчик първо удовлетворява максимално първия потребител. Тогава, ако доставчикът все още разполага със стоките,

Метод на най-малкия елемент в матрица.

Същността на метода е, че максималното възможно предлагане винаги се поставя в клетката, която съответства на най-ниската тарифа в матрицата.

Първо, правим маркировки (например със знак ▼) в тези клетки на линиите, в които се наблюдава най-ниската цена за линията. След това обикаляме таблицата колона по колона и правим същите бележки в клетките, които съдържат най-ниската цена в колоните.

По-нататъшното разпределение се извършва първо, доколкото е възможно, в клетки с два знака, след това с един и след това задачата се балансира отново до (m + n – 1) запълвания. Ние организираме пълнежите, като се движим през масата отляво надясно и отгоре надолу.

43. Свойства на транспортните задачи

Транспортният проблем има някои свойства, които могат да бъдат отразени от следните теореми.

Теорема 1. Затворен транспортен проблем винаги има решение.

Теорема 2. Ако обемите на запасите от продукти и обемите на нуждите са цели числа, тогава решението на транспортния проблем също ще бъде цяло число.

Теорема 3. системата от ограничения на затворен транспортен проблем винаги е линейно зависима.

От тази теорема следва, че разпределението на затворен транспортен проблем винаги има m + n – 1 основни променливи и (m – 1) (n – 1) променливи за свободно време.

44. Дегенеративно разпределение в транспортни проблеми, премахване на дегенерацията. Зачеркната комбинация.

Разпределението се нарича изродено, ако броят на клетките е по-малък от m + n – 1.

45. Теореми за оптималност на транспортната задача.

Теорема.Ако за някакво разпределение на транспортния проблем вие

изпълнени са условията:

А). ui+vj = сij за заети клетки

б) ui+vj ≤ сij, за свободни клетки,

тогава това разпределение е оптимално.

Величините ui се наричат потенциали на редове, а величините vj се наричат потенциали на колони.

46. Потенциали и методи за тяхното изчисляване.

За да намерите потенциалите на редове и колони, използвайте следното разсъждение, базирано на условие а) от теоремата за оптималност.

Броят на уравненията, базирани на това условие, е равен на m + n – 1, а броят на неизвестните ui и vj е равен на m + n. Че. броят на променливите е по-голям от броя на уравненията и всички уравнения са линейно независими. Решението на такава система от линейни уравнения е несигурно, така че на един от потенциалите трябва да бъде приписана произволна стойност. На практика ui = 0. Получава се система от m + n – 1 уравнения с m + n – 1 неизвестни променливи. Тази система може да бъде решена по всеки метод. На практика, за да се изчислят потенциалите, се разглеждат заетите клетки, за които е известен един от техните потенциали, и въз основа на условие а) на теоремата се изчисляват стойностите на останалите неизвестни потенциали.

47. изчисляване на оценки за оптималност за разпределение на транспортните задачи и критерий за оптималност.

Въз основа на съотношението b) на теоремата можем да напишем следната формула за изчисляване на оценките: δ ij= ui +vj – сij. За да се гарантира, че оценките не се бъркат с обемите на транспортиране, те (оценките) са оградени в кръгове.

Оценките за оптималност в свободните клетки на TZ представляват критерий за оптималност, с помощта на който се проверява оптималността на разпределението. Ако резултатите на всички свободни клетки са по-малки или равни на нула, тогава това разпределение е оптимално.

48. преразпределение на доставките в транспортния проблем

Ако разпределението не е оптимално, тогава е необходимо да се преразпределят доставките.

За преразпределение се изгражда цикъл на преизчисляване. Клетката с най-висок положителен резултат се избира като клетка. Тази клетка е маркирана със знак „+“, т.е. в нея трябва да се запише определено количество доставка. Но тогава балансът в тази колона ще бъде нарушен, следователно една от заетите клетки на тази колона трябва да бъде маркирана със знак „-“, т.е. обемът на предлагането трябва да бъде намален със същата сума. Но тогава балансът за този ред ще се промени, следователно, някоя заета клетка от този ред трябва да бъде маркирана със знак "+". Този процес продължава, докато знакът „-“ бъде поставен в реда, където се намира оригиналната клетка.

За всяка свободна клетка има цикъл на преизчисляване и освен това уникален.

49. преразпределителни вериги, техните видове.

Нека разглежданият транспортен план не е оптимален, т.е. има положителни относителни оценки. След това се взема неблагоприятна клетка (една от неблагоприятните) и за нея се изгражда цикъл на преизчисление, според който след това се преразпределя планираният транспорт. Цикълът е изграден под формата на прекъсната затворена линия, чиито сегменти минават или по колоната, или по линията. В един от ъглите на прекъснатата линия има неблагоприятна клетка, бореща се за продукта, а в останалите ъгли клетките са запълнени, т.е. Когато конструираме цикъл, започваме от клетката кандидат и се връщаме към нея по прекъсната линия, но можем да правим завои само в запълнени клетки (съответстващи на основните променливи). Нека неблагоприятна клетка претендира за продукт Q. За да се избегне дисбаланс в таблицата, е необходимо да се редуват преходите през цикъла

добавете и извадете Q към съществуващия транспорт. Тъй като има четен брой ъгли, в половината от клетките Q ще бъде добавен, а в другата половина ще бъде изваден. Преминаването на цикъла започва по посока на часовниковата стрелка или обратно на часовниковата стрелка от конкуриращата се клетка, поставяйки продукта Q там, след това Q се изважда от съседната клетка, след което се добавя и т.н. Самата стойност на Q е избрана така, че една от клетките да бъде изпразнена, но нито един от запасите не става отрицателен.

За да направите това, Q трябва да бъде избрано равно на най-малкото умалено от клетките, в които Q се изважда. На следващата фиг. 7.1 и 7.2 показваме примери за цикли и правилото за изчисление.

В този случай се изпразват две клетки. Но е необходимо само една клетка да стане взаимно празна. Те правят това: една от изпразващите се клетки се прави празна в новата таблица, а в другата изпразваща се клетка се поставя нула. Тази клетка се счита за основна (попълнена) в новата таблица.

50. Избор на обем на преразпределение.

Определяне на обема на транспортираните продукти. Когато определяме обема на продуктите, преминали през цикъла на преизчисляване, трябва да изхождаме от следните две съображения:

а) след трансформацията клетките на таблицата не трябва да съдържат отрицателни числа;

б) една от заетите клетки трябва да стане свободна.

За да бъдат изпълнени тези условия, е необходимо да се избере обемът на транспортираните продукти, както следва: θ=min (хij) -, където (хij) са обемите на транспортиране от клетките на цикъла на преизчисляване, отбелязани със знака „-“.

θ = min(20;30)=20

θ се добавя към стойностите на клетките, маркирани със знак "+". θ се изважда от стойностите на клетките, маркирани със знака "-". Стойността на захранването на останалите клетки се пренаписва без промени. В резултат на това получаваме следната таблица.

53. Алгоритъм на потенциалния метод.

Алгоритъм:

1. Проверете дали задачата е равна на ако не, тогава в проблема се въвежда фиктивен доставчик или потребител

2. Условието на задачата се записва под формата на транспортна таблица

3. Изгражда се първоначалният опорен план

4. Определят се потенциалите на постовете и потребителите

5. Изчисляват се резултатите от свободните клетки. Ако всички те не са отрицателни, планът е оптимален и трябва да запишете отговора. Транспортна матрица X и определя размера на транспортните разходи. Ако планът не е оптимален, т.е. сред оценките има отрицателни оценки, тогава изберете обещаваща клетка с най-голямата отрицателна стойност. оценка и преминете по размер към следващия.

6. Заредете обещаваща клетка. Форматиране на нов опорен план под формата на трансп.таблица. Отидете на точка 4.

54. Отчитане на разходите за производство и транспорт на продукцията. Транспортен проблем с ограничения на доставките.

При решаването на някои проблеми е необходимо да се вземат предвид разходите не само за транспортиране на товари, но и за производството на транспортирани продукти. За да направите това, в матрицата transp. задачи

Където Cij ‘ е намалената цена за производство на една единица продукция.

Cij „е разходите за транспортиране на една единица продукт.

Проблеми със забраните за доставка.

В някои ситуации продуктите не могат да бъдат транспортирани по никакъв маршрут.

За да направите това, в матрицата на транспортната задача, транспортирането през която е забранено, се въвежда забранителна тарифа М. След това проблемът се решава по обичайния начин, но тази клетка винаги ще съответства на отрицателна оценка за клетката.

55. като се вземат предвид ограниченията върху капацитета на маршрутите, като се вземе предвид задължителният характер на някои доставки в транспортния проблем.

като се вземат предвид ограниченията на капацитета на маршрута.

При някои транспортни задачи по някои маршрути е инсталиран по-малък капацитет от необходимия за задоволяване на търсенето на точката на потребление.

отчитайки необходимостта от определени доставки в транспортния проблем.

В някои случаи проблемът изисква, например, по маршрута Ak Bs да се достави обем от A единици. В този случай задължителната доставка се взема предвид от производствения обем на точка А и обема S Bs и се решава проблемът относно възможността за доставки. След получаване на оптималното решение запасът задължително се добавя към обема на Ak Bs, стоящи в клетката.

56. Възможни изводи с икономич интерпретация на оптимално разпределение за отворени транспортни проблеми.

При получаване на оптималното разпределение е необходимо да се върнете към първоначалния проблем и да вземете съответните икономически решения. заключения. Те са както следва:

1. ако се въведе точка на потребление, това означава, че в анализираната система има прекомерни производствени обеми и без увреждане на разглежданата система е възможно да се намали капацитетът на тези производствени точки със стойността на връзката, която е свързана до фиктивната точка на потребление.

2. ако се въведе фиктивна производствена точка, това означава, че капацитетът на реалните производствени точки не е достатъчен и те трябва да бъдат увеличени. Капацитетът на онези производствени точки, които са най-близо до точките на потребление, свързани с фиктивна производствена точка, се увеличава. Капацитетът на производителя се увеличава със задължителната сума. За да направите това, разгледайте колоната на точката на потребление, която е свързана с фиктивна точка на производство, и намерете най-ниската тарифа в нея. Най-ефективно е да се увеличи капацитетът на производствената точка, съответстващ на тази тарифа, с обвързващата стойност.

57. Концепцията за дуалност. Икономическа формулировка на двойни проблеми на примера на проблема за оптимизиране на производствения план.

Двойният проблем е спомагателен проблем за линейно програмиране, формулиран с помощта на определени правила директно от условията на оригиналния или директен проблем.

Нека има проблем с оптимизирането на производствения план. Изглежда така:

Първоначална задача:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤b 1 | на 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤b 2 | на 2

……………….. |.. (1)

А T 1 x 1 +a T 2 x 2 +...+ a T n x n ≤in 1 | при T

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X = (x 1, x 2,…, x n)

a ij – количеството суровини от i-тия вид, изразходвани за производството на j-тия вид продукт

Двоен проблем

Нека предприятието по някаква причина не може да произвежда продукти. За да намали разходите за престой, една компания може да продаде суровините, с които разполага. На какви цени трябва да се продават суровините?

y i е цената на i-тия вид суровина, налична в предприятието.

a 11 y 1 +a 21 y 2 +…+ a T 1 г T≥s 1

a 12 x 1 + a 22 y 2 +...+ a T 2 x p ≥s 2

……………….. (1’)

А 1стр y 1 +a 2т y 2 +...+ a tpпри T≥s П

y i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. Съответствие между структурните елементи на правата и двойствената задача

Всеки проблем с линейно програмиране може да бъде свързан с

двоен проблем според следните правила:

1. Във всички ограничения на оригиналния проблем, безплатните условия трябва

са отдясно, а членовете с неизвестни са отляво.

2. Ограниченията на неравенството на първоначалния проблем трябва да имат знаци

насочени в една посока.

3. Ако целевата функция в първоначалния проблем е минимизирана, ограниченията на неравенството трябва да бъдат записани със знака „≤“, тогава в двойствения проблем целевата функция ще бъде минимизирана и знаците на ограниченията на неравенството ще бъдат „≥“.

4. Всяко ограничение на първоначалния проблем съответства на променлива в

двоен проблем. Ако една променлива съответства на неравенство, тя е неотрицателна; ако съответства на равенство, тогава тя е променлива без ограничения на знака („произволна“).

5. Коефициентите на променливите в ограниченията на двойствения проблем се получават чрез транспониране на матрицата, съставена от

коефициенти за променливите на първоначалния проблем.

6. Свободните членове на първоначалния проблем са коефициентите на

променливи в целевата функция на двойствения проблем и безплатно

членове в дуалната задача – коефициенти на променливите в

функции на първоначалния проблем Отбележете също, че връзката на дуалността е реципрочна, т.е. двойна задача на двойна задача съвпада с първоначалната.Двойствените двойки задачи се делят на симетрични и асиметрични. В симетрична двойка ограниченията на преките и двойствените задачи са нестроги неравенства и следователно променливите на двете задачи могат да приемат само неотрицателни стойности.

59. Конструиране на двойствени задачи към оригинални задачи, написани в стандартната, канонична и обща форма на модела (конструиране на симетрични и асиметрични двойствени задачи)

Стандартен формуляр (оригинал)

Σ a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Двоен стандарт

Σ a ij y i ≤ c j , j=1,n(1)

y i ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Оригиналният проблем в канонична форма:

Σ a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Двойно каноничен

Σ a ij y i ≤ c j , j=1,n(1)

y i - всякакви (2)

F = Σ b i y i ->max(3)

Нека дадем икономическа интерпретация на двойка двойни проблеми. Нека разгледаме проблема за рационалното използване на ресурсите. Нека предприятието разполага с ресурси b1,b2,…bm, които могат да се използват за производство на n-типа продукти. Нека са известни също цената на единица от j-тип продукт cj (j=1,n) и нормата на потребление на i-тия ресурс (i=1,m) за производството на единица от j-ти продукт – aij Необходимо е да се определи обемът на производството на всеки вид продукт xj ( j=1,n), като се максимизират общите разходи

f= c1x1+...+cnxn (1)

В този случай потреблението на ресурси не трябва да надвишава тяхната наличност:

a11x1+...+a1nxn<=b1 }

…………………….. } (2)

am1x1+...+amnxn<=bm }

Всички известни в своето икономическо значение са неотрицателни:

Xj>=0 (j=1,n). (3)

Обърнете внимание, че този проблем представлява подобна двойна задача.

Асиметрични двойствени проблеми.

Нека вземем ZLP до максимум в канонична форма:

Макс Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Основната и втората теорема за двойствеността (посочете теоремите и обяснете)

Първа теорема за двойственост.

Теорема: ако една от дуалните задачи има оптимален план, то другата е разрешима, т.е. има оптичен план. В този случай екстремните стойности на целевите функции съвпадат (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* ако е в оригинала. проблем, целевата функция е неограничена върху множеството от планове, тогава в двойствения проблем системата от ограничения е непоследователна.

Втората теорема за дуалността и нейната икономическа интерпретация.

За да бъдат оптимални допустимите решения на двойка дуални задачи, е необходимо и достатъчно да е изпълнено следното условие: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Това са условия на допълнителна нетвърдост. От тях следва: ако всяко ограничение на двойна задача се превърне в строго равенство по оптимален план, тогава съответният компонент на опт. план на двойствения проблем трябва да е равен на 0. Ако някой компонент на опт. план е равен на нула, тогава съответното ограничение на двойния проблем се преобразува от оптичния план в строгото равенство xj*>0 следователно (i= от 1 до m)Σaij yi*=cj (производствени разходи = цена) – Ако продуктът е включен в плана за търговия на едро, тогава ако разходи>цени, производствен обем=0 Σaij yi* >cj следователно xj*=0

yi*>0 следователно (j=от 1 до n) Σaij xj*=bi (разпределение на ресурсите = запас от ресурси).

(j=1 до n) Σaij xj*

Смисълът на теоремата се свежда до следното:

Ако оценката на себестойността на разходите за производство на единица продукт = цена, тогава този вид продукт е включен в оптималния план;

Ако разходите надвишават цената, тогава продуктът не трябва да се произвежда;

Ако потреблението на ресурс = запасите, тогава оценката на разходите за този ресурс е положителна. Такива ресурси се наричат оскъдни. Най-дефицитният ресурс има най-висок рейтинг;

Ако ресурсът не е напълно изразходван, тогава неговата оценка на разходите е = 0.

61. Изграждане на оптимален справочен план за двойствената задача с помощта на симплексната таблица на първоначалната задача

Информация от колоните на обратната матрица на линейните трансформации, довели до оптималния резултат. От колоните на матрицата D-1 може да се извлече много полезна информация.

Колона A3: „сенчестата“ цена на ресурс S2 е y01=0, колоната остава

единица и от първия ред можете да прочетете, че x3=9, т.е. при изпълнение на намерения оптимален план първият ресурс ще бъде в излишък и този излишък (недоизползване) ще бъде точно 9 условни единици.

Колона A4: „сенчестата“ цена на ресурса S2 е равна на y02=1, ресурсът ще бъде използван напълно и евентуалното му увеличение ще доведе до увеличение на целевата функция (т.е. доход). И защото y02=1, тогава увеличението на ресурса S2 с 1.u. ще даде добавка към дохода от .Z = y02· .v2 = = 1,1 = 1 (хиляда UAH) (тук .v2 е увеличението на ресурса S2, а .Z е съответното увеличение на дохода). При такова увеличение на ресурса S2 максималният доход вече ще бъде Zmax=58 хил. UAH. + 1 хил. UAH = 59 хил. UAH. На фиг. 6.2 илюстрира тази ситуация, коментар за която ще бъде даден по-долу. От колона A4 също следва, че с увеличаване на ресурса S2 с 1 c.u. за новата оптимална точка производството на стоки T1 ще бъде намалено с ½ тон (в пресечната точка на реда на основната променлива x1 и колона A4 има „-1/2“), а производството на стоки T2 ще се увеличи с 3/2 тона (тъй като в реда с основната променлива x2 в колона A4 имаме „3/2”). Казаното в колона A4 ще бъде коментирано по-долу с помощта на графични конструкции (фиг. 6.2). Колона A5 : „сенчестата“ цена на ресурса S3 е равна на y03 = 2. Това означава, че увеличение на ресурса S3 с 1.u. ще донесе добавка в Z от.Z = y03· .в3 = 2,1 =2(хиляда UAH) и ще бъде Zmax=58 хиляди UAH. + 2 хиляди UAH = 60 хиляди UAH. В същото време, както следва от колона А5 на табл. 3, производството на T1 ще се увеличи с ½ тон, а T2 ще намалее с ½ тон. Запасът от суровини S1 (виж 1-ви ред) ще се увеличи с 3/2 куб.

62. Идеята за метода на динамичното програмиране и неговата геометрична интерпретация. Принципът на оптималност на Белман.

Оптималното решение на задачата с помощта на метода на динамично програмиране се намира въз основа на функционалното уравнение

За да го определите, трябва:

1. напишете функционалното уравнение за последното състояние на процеса (съответства на l=n-1)

fn-1(Sl-1)=оптимум(Rn(Sn-1,Un)+f0(Sn))

2.намерете Rn(Sn-1,Un) от дискретен набор от неговите стойности за някои фиксирани Sn-1 и Un от съответните допустими области (тъй като f0(Sn)=0, тогава f1(Sn-1)= оптимален (Rn( Sn-1,Un)

В резултат след първата стъпка решението Un и съответната стойност на функцията f1(Sn-1) са известни.

3. Намалете стойността на l с единица и напишете съответното функционално уравнение. За l=n-k (k= 2,n) има формата

fk(Sn-k)=оптимум(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4.намерете условно оптимално решение въз основа на израз (2)

5.проверете на какво е равна стойността на l.Ако l=0 изчисляването на условно оптималните решения е завършено и е намерено оптималното решение на задачата за първото състояние на процеса. Ако l не е равно на 0, преминете към стъпка 3.

6. Изчислете оптималното решение на проблема за всяка следваща стъпка от процеса, като се движите от края на изчисленията към началото.

Методът на динамичната програма позволява една задача с много променливи да бъде заменена с редица последователно решавани задачи с по-малък брой променливи. Решението се извършва на стъпки. Основният принцип, на който се основава оптимизацията на многоетапен процес, както и характеристиките на изчислителния метод, е принципът на оптималност на Белман.

Оптималното поведение има свойството, че каквото и да е първоначалното състояние и първоначалното решение, следващите решения трябва да бъдат оптимални спрямо състоянието, произтичащо от първоначалното решение.

Математически се записва като израз на формата:

fn-1(Sl)=оптимум(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1) Оптимално в израза означава максимум или минимум в зависимост от условията на проблема.

63. Изисквания към задачи, решени по метода на ДП

Динамичното програмиране е математически метод за намиране на оптимални решения на многоетапни проблеми. Многоетапният процес е този, който се развива с течение на времето и се разделя на няколко стъпки или етапи.

Една от характеристиките на метода на динамичното програмиране е, че решенията, взети във връзка с многоетапни процеси, се разглеждат не като единичен акт, а като цял комплекс от взаимосвързани решения. Тази последователност от взаимосвързани решения се нарича стратегия.Целта на оптималното планиране е да се избере стратегия, която осигурява най-добър резултат по отношение на предварително избран критерий. Тази стратегия се нарича оптимална.

Друга важна характеристика на метода е независимостта на оптималното решение, взето на следващата стъпка, от праисторията, т.е. за това как оптимизираният процес е достигнал текущото си състояние. Оптималното решение се избира само като се вземат предвид факторите, характеризиращи процеса в момента.

Динамичният програмен метод се характеризира и с факта, че изборът на оптималното решение на всяка стъпка трябва да се прави, като се вземат предвид неговите последствия в бъдеще. Това означава, че докато оптимизирате процеса на всяка отделна стъпка, никога не трябва да забравяте за всички последващи стъпки.

64. Икономическа формулировка и изграждане на математически модел на задача, решена по метода на ДП (на примера на задачата за разпределение на капиталовите инвестиции). Рекурентна връзка на Белман.

Нека първо обясним, че методът на динамично програмиране се прилага основно към онези проблеми, при които оптимизираният процес (или ситуация) се разгръща в пространството или времето, или и двете.

Нека самият процес (ситуация) е толкова сложен, че не е възможно да се оптимизира с известни методи. След това, използвайки метода на динамичното програмиране, КОМПЛЕКСЕН процес (операция, ситуация) се разделя (разделя) на няколко етапа (стъпки). Тази разбивка в много случаи е естествена, но като цяло се въвежда изкуствено. . Например, когато се разглежда всяка игра на шах, всеки ход на всеки играч служи

разделяне на цялата партида на отделни стъпки (етапи). И при военна операция за преследване на една ракета с друга, целият непрекъснат процес трябва да бъде изкуствено разделен на етапи, например след всяка секунда наблюдение. Методът на динамично програмиране позволява оптимизирането на целия сложен процес да бъде заменено с условна оптимизация за всеки етап

(стъпки), последвани от синтез на оптимално управление на целия процес. В този случай методът предвижда, че условната оптимизация на отделна стъпка (етап) се извършва в интерес на първо място на цялата операция.

Всички изчисления, които позволяват да се намери оптималната стойност на ефекта, постигнат в n стъпки, fn(S0), се извършват съгласно формула (1), която се нарича основно функционално уравнение на Белман или рекурентна връзка. При изчисляване на следващата стойност на функцията fn-1 се използва стойността на функцията fn-(l+1), получена на предишната стъпка, и директната стойност на ефекта Rl+1(Sl,Ul+1), постигната в резултат на избор на решението Ul+1 за дадено състояние на системи Sl. Процесът на изчисляване на стойността на функцията fn-1(l=0,n-1)

Извършва се при естествено начално условие f0(Sn)=0, което означава, че след крайното състояние на системата ефектът е нулев.

65. Проблем за разпределение на капиталните вложения (пример).

За да решим задачата за оптимално разпределение на капиталовите инвестиции, ще използваме функционалното уравнение на Белман. Първо, използвайки най-простата ситуация, ще илюстрираме извеждането на функционалното уравнение на Белман и след това, използвайки пример, ще докажем как да използваме това уравнение за решаване на проблема, който ни интересува.

Да започнем с оптималното разпределение на разпределените капиталови инвестиции в размер на K между две предприятия. Отделите за планиране на предприятията, въз основа на техните изчисления, формираха функциите на дохода q(x) за предприятие P1 и h(x) за предприятие P2. Тези функции означават, че ако първото или второто предприятие получи инвестиция в размер на x, тогава първото предприятие

ще бъде получен доходът q(x), а вторият h(x), а стойността x може да приема непрекъснати или известни дискретни стойности от 0 до K.

И така, нека на предприятие P1 бъдат разпределени капиталови инвестиции в размер на x, тогава на предприятие P2 ще бъде разпределена сумата K - x. В този случай доходът q(x) ще бъде получен от първото предприятие, а доходът h(K - x) от второто. Ако капиталовите инвестиции K са разпределени за един период на планиране, тогава общият доход от двете предприятия ще бъде R(K, x) = q(x) + h(K - x). Очевидно x и съответно K - x трябва да бъдат избрани така, че R(K, x) да приеме максималната си стойност, която обозначаваме с F(K):

Този запис е като скелет за по-пълни записи

Функционално уравнение на Белман. НЕКА ЗАВЪРШИМ нашата задача, като разпределим капиталовите инвестиции в два планови периода (два етапа) . Нека първоначално бъде решено да се разпредели сумата x на първото предприятие P1 и x на второто предприятие K. Като цяло доходът ще бъде равен на R(K, x) = q(x) +

h(K - x). Ако имаме предвид, че капиталовите инвестиции са разпределени в 2 периода (2 етапа), тогава в първото предприятие балансът на капиталовите инвестиции ще бъде .x, където , а във второто - .(K - x), където Съответно, доходът за втория период ще бъде q( .x) - за първото предприятие и h[.(K - x)] - за второто. Оптимизацията с помощта на метода на динамично програмиране, като правило, започва от крайния етап. Следователно, нека започнем от втория етап, обозначавайки с F1 максималния възможен доход от две предприятия във втория

сцена. Получаваме

След това добавяме предишния (в нашия случай първи) етап към разглеждания последен (в нашия случай втори) етап и намираме максималния доход от двата етапа заедно:

По същия начин за n етапа получаваме

където Fn-1 е целевата функция, която дава най-добър резултат през последните (n - 1) етапи. Полученото функционално уравнение на Белман е рекурентно по природа, т.е. свързва стойността Fn със стойността Fn-1.

В по-обща схема уравнението на Белман има формата

където , Fn-1 - максимален доход за (n - 1) последните етапи, Fn -

максимален доход за всички n етапа.

66. Концепцията за решаване на проблеми с нелинейно програмиране

Нека проблемът с нелинейното програмиране бъде поставен в следната обща форма: намерете стойности на променливите x1, x2,..., xn, които отговарят на условията:

и довеждат необходимия екстремум (максимум или минимум) на целевата функция

f = f(x1, x2,…, xn), (13.2)

където f(x1, …, xn) и qi(x1, …, xn) (m, 1 i =) са реални нелинейни,

регулярни функции на n реални променливи.

По своите общи свойства проблемите на нелинейното програмиране могат

значително различни от линейните. Например, областта на допустимите решения може вече да не е изпъкнала и екстремумът на целевата функция може да се наблюдава във всяка точка на допустимата област. Методите за решаване на нелинейни проблеми също се различават значително. Нека разгледаме само някои подходи за решаване на тези проблеми.

На първо място, графичният подход е валиден и при решаването на най-простите проблеми на нелинейното програмиране. Така че, ако аргументите на проблема са променливите x1 и x2, тогава първо се конструира област от възможни решения в равнината на тези променливи и след това оптималната точка в областта се определя с помощта на нивата на целевата функция f( x1,x2).

В нелинейното програмиране градиентният подход се използва за решаване на много проблеми. Съществуват редица градиентни методи, чиято същност е да се намери оптимален резултат с помощта на градиента на целевата функция - вектор, указващ посоката на максималното увеличение на целта за въпросната точка. В общия случай процедурата по търсене се извършва в итеративен режим от първоначално избраната точка до точки с най-добър показател. Нека, например,. - регион на осъществими решения

разглеждания проблем и итеративният процес на изчисления започва от точката

След това първо се прави преход по градиента на целевата функция и след това връщане към региона. по градиента до прекъснатата граница на областта O2 O3. На фиг. 13.3 показва, че Ai с нечетни индекси принадлежат към региона, а точките Ai с четни индекси не принадлежат.Когато се приближаваме до оптималната точка Q, посоките на работните градиенти се доближават. Следователно идеалният критерий за спиране на процеса би бил колинеарността на целевия градиент и градиента на нарушената граница.

67. Понятие за параметрично и целочислено програмиране .

Постановка и математически модел на ЗЦЛП.

В задачи с неделими обекти се налагат условия за цялост на променливите. Понякога тези условия се прилагат за всички променливи, понякога за част от променливите. Помислете за напълно целочислен проблем

f=(n,j=1)∑CjXi макс

(n,j=1)∑AijXj=bi, i=1,m

xi-цяло число,j=1,n

Сега, за разлика от общия проблем с линейното програмиране, оптималният план няма непременно да бъде във върха на полиедъра от планове.Съществуват следните методи за решаване на цели числа:

1. Методи на рязане

2.Комбинаторни

3. Приблизителни методи..

Параметричното програмиране е клон на математическото програмиране, посветен на изследването на оптимизационни проблеми, при които условията за осъществимост и целевата функция зависят от някои детерминистични параметри.