Целочислено програмиране

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

Изпратете добрата си работа в базата знания е лесно. Използвайте формата по-долу

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

Публикувано наhttp://www.allbest.ru/

Федерална държавна образователна бюджетна институция за висше образование

при правителството на България

Катедра "Математика и информатика"

Направление: Държавна и общинска администрация

Лектор: чл. пр. Рязанцева Е.А.

Ученик: Кирина Валерия Андреевна

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

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

Целочисленото програмиране възниква през 50-60-те години на нашия век от нуждите на практиката – оснначин в трудовете на американските математици J. Dantzig и R. Gomory. Първоначално целочисленото програмиране се развива независимо от геометрията на числата въз основа на теорията и методите на математическата оптимизация, предимно линейното програмиране. Въпреки това през последните години изследванията в тази насока все повече се извършват с помощта на математиката на целите числа.

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

Цялочислено програмиране. Основни понятия.

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

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

Препоръки за формулиране и решение на CR:

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

2.За разлика от общите проблеми с LP, добавянето на нови ограничения, особено тези, включващи целочислени променливи, обикновено намалява времето за решаване на проблеми с процесора;

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

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

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

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

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

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

- трябва да е линеен;

- трябва да отреже намерения оптимален нецелочислен план;

-не трябва да прекъсва никакъв план с цели числа.

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

най-близкото цяло число, което не превишава съответно xj и zj.

3. Добавяме съставеното ограничение към тези в симплексната таблица, като по този начин получаваме разширен проблем. За да се получи референтен план за този проблем, е необходимо да се въведе в основата векторът, за който стойността е минимална. И ако за този вектор стойността u = min, тогава тя се получава от допълнителен ред, ако zkj 0, тогава в следващата симплексна таблица ще се получи референтен план. Ако стойността на и не съответства на допълнителния ред, тогава е необходимо да се премине към M-проблема (въвеждане на изкуствена променлива в ограничението Gomory).

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

Разклонения и граници

Методът на разклоненията и границите е предложен за първи път от Land и Doig през 1960 г. за решаване на общия проблем на целочисленото линейно програмиране (Land A.H., Doig A.G. Автоматичен метод за решаване на проблеми с дискретно програмиране // Econometrica. V28, 1960).

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

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

Ако всички корени на решението не са цели (в противен случай се намира оптималното цяло число), разклоняваме проблема на две, като за всеки от проблемите въвеждаме допълнителни ограничения върху една от променливите xiai, xibi, където ai е най-голямото цяло число, което не превишава xi, а bi е най-малкото цяло число, по-голямо от xi, например с корена на първоначалния проблем x2=2.3 add. ограничението в единия клон ще бъде x22, а в другия - x23.

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

Клон се счита за задънена улица, ако:

а) няма осъществимо решение на следващия проблем с LP;

б) текущото решение (стойността на целевата функция) е по-лошо от вече намереното целочислено решение; алгоритъм за математическо програмиране

в) текущата LP задача е подзадача на предварително изчислената задача.

Алгоритъм за циклично целочислено програмиране

Помислете за следния проблем с линейно програмиране:

Забележете, че xn+1., хn+m са слаби променливи, а x1…., хn са начални променливи на задача (2). Ако наред с ограниченията (2) изискваме всички хj, (j'=1,…, m) да са цели числа, тогава задачата ще се нарича задача за целочислено програмиране. Има голям брой проблеми, особено комбинаторни, които могат да бъдат формулирани като задачи за целочислено програмиране.

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

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

Следният целочислен алгоритъм има следните свойства:

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

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

3) допълнителните ограничения (хиперравнини) минават през поне една целочислена точка, макар и не непременно вътре в изпъкналата обвивка;

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

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

Обикновено ограниченията на проблема (2) се включват в тривиалните отношения xj= - (-Xj) (j'=1,…, n), а проблемът в матрична форма приема формата: x = A (-xn), (3)

където x е вектор колона с компоненти X 0, x1,…, xn, xn+1,…, xn+m A е съответната матрица с размер (n + m + 1) * (n + 1) и (-xn) е вектор с компоненти (1, - x1, - x2,…, - xn), които са неосновни променливи на изходната таблица. Проблем с целочислено програмиране може да бъде написан и като таблица.

причинипредставянето на променливи като (-x1), (-x2,……, (-xn)) е чисто историческо, но се е превърнало в обичайна практика в целочисленото програмиране. Ще използваме bj(j = 0, 1,…, n), за да обозначим j-та колона на текущата таблица и aij (i = 0, 1,…, n + m; j = 0, 1,…, n), за да обозначим елемента на 1-ви ред и 7-ма колона на таблицата. Предполага се, че всички a, ij в оригиналната таблица са цели числа. Следователно всички слаби променливи xn+1,…, Xn+m също трябва да бъдат неотрицателни цели числа.

При представянето на алгоритъма за решаване на цели числа ще следваме работата на Гомори. Първо, проблемът с целочисленото програмиране се разглежда като линейна програма и алгоритъмът го решава с помощта на директен или двоен симплексен метод. В края на алгоритъма aij?0 (i = 1,……, n + m) и a0j? 0 (j' = 1,…, n). (За да получим оригиналното двойно допустимо решение, въвеждаме допълнително ограничение xn+m+1 == M - X1 - x2 - ... - xn? 0, където M е достатъчно голяма константа, и правим една итерация с този ред и лексикографски минималната колона като водеща.) Ако ai0? 0 и цяло число за всички i, тогава се получава оптималното решение на проблема с целите числа. В този случай решението се получава веднага, без използване на целочислени ограничения. Ако ai0? 0, но не всички цели числа, нека добавим още едно към ограниченията (1). Новото ограничение е написано в долната част на таблицата, така че вече не е директно допустимо, т.е. ai0