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



страница1/5
Дата25.02.2018
Размер482.95 Kb.
#58869
ТипЗадача
  1   2   3   4   5

ЦЕЛОЧИСЛЕНО ЛИНЕЙНО ПРОГРАМИРАНЕ


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

Задачата може да бъде напьлно целочислена или частично целочислена
според това дали ветки или само някои променливи са це-лочислени, а моделите на тези два тип задачи се отнасят съответно към чистomo ЦП или смесеното ЦП (СЦП). Ако целевата функция и огра-ниченията са линейни,

формулирана е задача на целочисленото линейно програмиране (ЦЛП). Най-

често решавани са именно целочислените линейни задачи (ЦЛЗ).
Основните трудности при използуването на алгоритмите на ЦЛП са свързани със значителния разход на машинно време. Затруднения възникват и поради грешки от закръглянето, което се извършва при машинното изпълнение на алгоритмите.
Един от най-простите начини за избягване на тези затруднения е задачата да се реши като задача на непрекъснатото (обикновеното) ЛП и получените оптимални решения да се закрьглят до най-близките цели стойности. Не съшествува обаче гаранция, че такова приблизител-но решение ще удовлетворява ограниченията във вид на неравенства, а ограниченията във вид на равенства винаги ще бъдат нарушени.
Целочислените променливи често означават брой обекти (маши-ни, изделия, хора) и ако закръглените им стойности удовлетворяват ограниченията, те са допустими. Ако променливите обаче имат логически характер (х = ! или 0, дадена работа се включва или не се включва в плана), дробните стойности нямат смисъл в схемите на фор-малната логика, а типичните ограничения във вид на равенства биха били нарушени от закръглените стойности.
Представа за някои области на приложение и за важността на ме-тодите на ЦП дават разгледаните примери по-нататък.

7.1. НЯКОИ ЗАДАЧИ И ПРИЛОЖЕНИЯ НА


ЦЕЛОЧИСЛЕНОТО ПРОГРАМИРАНЕ
Често целочислените задачи възникват по естествен път, напри-мер, когато определяните решения са от типа "да-не". Съществен ин-терес обаче представляват и "изкуствените" задачи, в които изкуствено

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


7.1.1. ЗАДАЧА ЗА ИЗБОР НА ПРОЕКТИ
Обсъждат се п проекта за изпълнение през следващите т годи -ни. В табл.7.1 са представени годишните разходи и очакваният доход за всеки проект, както и достъпните средства през годините на изпъл-нение. Необходимо е да се определи кои от n-те проекта би трябвало да се изпълняват през m-годишния период, ако критерий за избор е сумарният доход.











Разходи за




Таблица 7.1































Проект

Година 1

Година 2




Година m

Доходи































1

с11

с12




c1m

R1



















2

С21

С22




c2m

R2










.




.







.







.













.






















п

Cn1

Сп2

...

Cnrn

Rn































Достъпни

В1

В2

...

Bm










средства



















































Вижда се, че за всеки проект се взема решение от типа "да-не". Такова решение се представя чрез двоичната променлива хj, която се поставя в съответствие на j-тия проект, и чиито стойности 1

или 0 кодират решенията "да" или "не".
Тогава моделът на задачата е от вида Да се максимизира ограниченията

Дробни стойности на xi нямат смисъл, защото стойностите 1,0 кодират

решенията от тип "да-не".
ЗАДАЧА ЗА ПЛАНИРАНЕ ПРИ ПОСТОЯННИ ЕЛЕМЕНТИ НА РАЗХОДИТЕ
Често разходите за производство на j-тия вид продукция в обем xi могат да се представят като сума от постоянна и променлива част


където kj ca постоянни разходи, конто не зависят от количеството хj на продукцията, а сj са разходите за производство на единица продукция. Целта би могла да се запише във вида:


Да се минимизира
където N е броят на видоветепродукция. Целевата функция J не е линейна по xj поради прекъснатостта и в началото на координатна-та система и използуването на ЛП за определяне на стойностите xj e невъзможно.
Преодоляването на това аналитично затруднение е възможно по следния начин. Нека yj ca допълнителни двоични променливи

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



където М > 0 е достатъчно голямо, така че условиетовинаги да се изпълнява. Тогава началната задача се преобразува в задача на СЦП (или в


нова напълно целочислена задача, ако всички xi са целочислени) от следния вид:


Да се минимизира


при ограниченията а) ограниченията на началната задача; б) новите ограничения


Преобразуването е коректно, защото новите ограничения осигуря-ват това, че уj = 1 , когато хj> 0 и тогава kj се включва в целевата Функция. А при xj = 0, когато ограниченията позволяват да се избира

между yj = 0 и yj = 1, изборът уj = 0 осигурява по-малка стойно

J от yj = 1 (тъй като кj > 0) и оптимизиращият алгоритъм ще избере стойността уj= 0.


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

7.1.3. ЗАДАЧА ЗА СЪСТАВЯНЕ НА ПРОИЗВОДСТВЕНО РАЗПИСАНИЕ


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

операция, а aj - продължителността на ней-




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




Вторият тип ограничения отразява факта, че две операции не мо-гат да се изпълняват едновременно на една машина. За операциите i и j

в зависимост съответно от това дали j е преди г, или г е преди j в оптималното решение.


Такива логически ограничения от вида "или-или" пораждат не-изпъкнали пространства на допустимите решения, при конто ЛП е не-приложимо. За преодоляването на тази трудност се въвежда двоичната променлива yj,


Нека М > 0 е достатъчно голямо. Тогава ограничението "или-или" e еквивалентно на следните две одновременны ограничения




Нека оптималното решение е y*ij = 0. Тогава второто ограничение е излишно (в смисъл, че винаги се изпълнява), а първото ограничение е активно. Ако у*ij = 1, първото ограничение е излишно, а второто е активно. Вижда се, че въвеждането на двоичната промеклива уij логическото ограничение се преобразува в обикновени ограничения от


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


където dj моментът от време, когато трябва да завърши изпълнението на j-та операция.


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

нула, x1 = 0.


Нека t е сумарното време за изпълнение на всичките п операции. Гогава моделът на задачата е от вида
Да се минимизира J = t при ограниченията


плюс ограниченията от трите типа, разгледани по-горе.


Въвеждането на спомагателните двоични променливи позволява изразяването на комбинационни отношения. В разгледания пример се оценяват две комбинации - на всички останали ограничения най-на-пред с първото, а след това с второто от двете алтернативни ограничения ("или - или"). Решението от тип "да - не" коя от тези две комбинации е по-добра от гледна точка на стойността на J се представя от променливата уij.
7.1.4. ЗАДАЧА ЗА ИЗБОР НА К ОТ N ОГРАНИЧЕНИЯ
Разглежда се случай, когато е необходимо да се изпълняват K от N ограничения, К < N от вида


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

Ако М > 0 е достатъчно голямо, изпълнението на К от N-те огра-ничения се осигурява от условията



Вижда се, че в десните части на N - К ограничения ще се появяват стойностите di + М и тези ограничения ще станат излишни.


7.1.5. ФУНКЦИИ С N ВЪЗМОЖНИ СТОЙНОСТИ
Нека е необходимо функцията f да има една от N зададени въз-можни

стойности т.е.


f(x1, x2, ..., хп) = d1 или d2, или ..., dN. Това може да бъде постигнато чрез формулиране на задача на ЦП

където



Тези нови условия се включват към ограниченията на решавана-та задача. Подобно на предишния пример, предварително не е известно коя е стойността на функцията и една част от оптимизационния про-цес се състои в избирането на такава стойност сред N-те зададени, при която целевата функция на решаваната задача има най-добра стойност.
По същия начин се решава и задачата за избиране на една от ня-колко възможни стойности на дясната част на дадено ограничение.
7.2. МЕТОДИ ЗА РЕШАВАНЕ НА ЗАДАЧИ НА ЦП
Целочислената природа на променливите в задачите на ЦП за-труднява разработването на ефективни алгоритми, конто търсят оп-тималното решение директно сред допустимите целочислени точки на пространството на решенията. Затрудненията се дължат на много го-лемия брой комбинации от стойности на променливите, конто трябва да се оценят. Поради това, подходът за решаване на целочислени задачи се основава на мощния резултат от непрекъснатото ЛП, че оптимално-то решение се намира в ъглова точка на пространството на решенията.

Тозй подход може да бъде систематизиран по следния начин.


"Отслабват" се ограниченията на началната целочислена задача, като се отстраняват изискванията за целочисленост на променливите. В резултат на това възниква задача на непрекъснатото ЛП.
Решава се "отслабената" задача и се определя непрекъснатото оптимално решение.
Като се започва от непрекъснатото оптимално решение, по-
следователно се въвеждат специални допълнителни ограничения, кои-то отчитат изискванията за целочисленост и деформират допустимата област на отслабената задача дотогава, докато оптималното решение стане целочислено.
Търсенето на целочисленото оптимално решение започва от не-прекъснатото поради това, че твърде често двете оптимални решения са разположени близо едно до друго, което пък позволява целочисленото решение да бъде определено по-бързо.
Същността на подхода е в решаването на последователност от задачи на непрекъснатото ЛП, което от изчислителна гледна точка е по-ефективно от директното търсене на целочислени решения.
Специалните ограничения се построяват, като се използуват два метода: метода на клоните и границите и метода на отсичащите равнини.
И при двата метода добавяните специални ограничения отстраняват части от допустимата облает на отслабената задача, конто не съдържат точки с целочислени координати.
От гледна точка на изчислителни загуби и точност методът на клоните и границите е значително по-ефективен от метода на отсича-щите равнини и е в основата на повечето програмни продукта за решаване на задачи на ЦП. Като цяло обаче (с изключение на някои специални задачи) ефективността на съществуващите методи за решаване на задачи на ЦП е недостатъчна. Ето защо създаването на по-ефективни Методи е област на значителен изследователски интерес.

7.3. МЕТОД НА КЛОНИТЕ И ГРАНИЦИТЕ


Методът е приложим за решаване на двата вида задачи - напълно целочислени и частично целочислени. Същността му ще бъде обяснена с помощта на пример.
Пример 7.1. Разглежда се следната задача на ЦЛП Да се максимизира J = 6x1 + 5х2 при

ограничения



На фиг 7.1. е показано с точки пространството на решенията на задачата на ЦЛП. Пространството на решенията на отслабената задача ЛПО на непрекъснатото ЛП, която възниква след отстраняване на изис-кванията за целочисленост, е четириъгълникът О ABC. Оптималното решение на задачата ЛПО, получено по симплекс-метода, е х*1= 4,40, х*2 — 1, 60, J* =

34,40.
Тъй като решението на ЛПО не е целочислено , пространството на решенията на ЛПО се изменя по такъв начин, че да се подобрят възмо-жностите за определяне на целочислено решение. За целта произволно
се избира една от променливите, която в точката на оптимума на ЛПО не е цело числена, да генерира необходимите изменения. Ако например се избере х 1 ( х * 1 = 4,40), вижда се, че областта 4 < х1 < 5 от простран-ството на решенията на ЛПО не съдържа целочислени решения и може да бъде отстранена. Очевидно, целочислените решения трябва да удо-влетворяват едно от следните две условия което позволява началното пространство ПрЛПО на задачата ЛПО да се замени с две пространства ПрЛП1 и ПрЛП2


ПрЛП1=ПрЛП0 и ограничението (х14), ПрЛП2=ПрЛП0 и ограничението (x1 5).




По този начин отслабената непрекъсната задача ЛПО се заменя с две нови задачи на непрекъснатото ЛП - задачите ЛП1 и ЛП2. На фиг.7.1 пространствата ПрЛП1 и ПрЛП2 са представени съответно от четириъгълника OMNC и триъгълника PAQ, означени са и задачите


ЛП1, ЛП2, породени от новите пространства. Вижда се, че двете про-ранства съдържат всички допустими целочислени решения на начал-ната

ЦЛЗ и в този смисъл са еквивалентни на ПрЛП0.

Тъй като двете нови ограничения х1 4 и x1 5 се изключват взаимно, задачите ЛП1 и ЛП2, които възникват след поотделното въве-ждане на тези ограничения в задачата ЛПО, са различии и се решават поотделно.
Описаното разделяне на текущото пространство на решенията на две взаимно изключващи се подпространства и свързаното с това по-строяване на две нови задачи (подзадачи) на ЛП от началната (текуща-та) задача се означават с понятието разклоняване. На фиг.7.2 е показано разклоняването на ЛПО на двете подзадачи ЛП1 и ЛП2, като клоните се определят от ограниченията х1 4 и х1 5. Процесът на разклоняване се представя чрез дърво, всеки възел на което съответствува на подзадача. Самото дърво се нарича дърво на решението (или дърво на изброяването). Променливата х 1 , използувана за да се извърши разклоняването, се нарича променлива на разклоняването.


Фиг. 7.2

Да предположим, че избираме произволно най-напред да бъде ре-шена подзадачата ЛП1
Да се максимизира J = 6x1 + 5x2 при ограничения


Разликата от ЛПО е тази, че тук е включено ново ограничение което не се удовлетворява от оптималното решение на ЛПО х*1= 4,40. В т.4.4.2 беше представено използуването на дуалния симплекс-метод когато в модела на задачата е необходимо да се добави ново ограничение. Като се приложи описаната процедура, се определя оптималното решение на ЛП1

х*1= 4, х*1 = 2, J* = 34.


Полученото решение е целочислено и подзадачата ЛП1 се означава като оценена (измерена), в смисъл, че тя няма да се разглежда по-ната-тък, тъй като не може да даде по- добро решение.
Целочисленото решение на ЛП1 определя долна граница за опти-малната стойност на целевата функция на задачата на ЦП. Понятието "граница" е следващото важно понятие за разглеждания метод. Гра-ницата позволява да се отстраняват както неперспективни задачи, конто не биха могли да дадат по- добро решение и няма смисъл да бъдат решавани, така и получаваните нови целочислени решения, ако те не са по-добри от съществуващото, което определя границата. В случая долната граница (задачата е за максимизация) е J* — 34. Тъй като оптималното решение на ЛПО J* = 34,40 и коефициентите в целевата функция са цели числа, от ЛПО не може да произлезе задача, която да има по-добро решение от J* = 34. В този смисъл задачата ЛП2 може да бъде отстранена без решаване, като неперспективна, тъй като нейното решение не би могло да бъде по-добро от това на задачата ЛП1 J* = 34. Задачата ЛП2 също е оценена, т.е. няма да се разглежда по-нататък.



Сподели с приятели:
  1   2   3   4   5




©obuch.info 2024
отнасят до администрацията

    Начална страница