методи клипинг

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

· Тя трябва да бъде линеен;

· Трябва да се намери за намаляване на не-число оптимално план;

· Не трябва да изрежете една единствена интегрална схема.

Допълнително ограничение, притежаващи тези свойства се казва, че на изключване.

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

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

Един от алгоритмите за решаване на линейното програмиране число (6.59) ... (6.62), предложен от Gomory, въз основа на симплекс метода и използва сравнително прост метод за конструиране на правилното прекъсването.

Фиг. 6.18. Графичен илюстрация на разтвори целочислени

Нека Задачата на линейното програмиране (6.52) ... (6.55) има краен оптимално и в последната стъпка за решаване на симплекс метода, следните уравнения, изразяващи основните променливи по отношение на второстепенни променливи на оптималното решение

така че оптималното решение на проблема (6.52) ... (6,55) е. където например # 946; и - не-число компонент. В този случай може да се докаже, че неравенството

формира на аз-ти уравнението на системата (6,56) има всички свойства правилното подрязване.

Неравенството (6.57) присъства характер. представлява дробна част от номера. номер се нарича еднакви номер в (определени), ако и само ако разликата а - б - цяло число.

цялата част от номер е най-голямото цяло число. не повече от един. Дробна част от броя се дефинира като разликата между това число и цялата част, т.е. , Например, за А = 2; и = -3.

За да реши число задачата на линейното програмиране (6.52) ... (6.55) метод Gomory използва следния алгоритъм:

1. Методът симплекс за решаване на проблема (6.52) ... (6.55), с изключение на условията на цяло число. Ако всички компоненти на оптималния план на цялото, че е оптимално за проблема с число програмиране (6.52) ... (6.55). Ако първият проблем (6.52) ... (6,54) е неразтворим (т.е., има ограничен оптимално или неговите противоречиви условия), вторият проблем (6.52) ... (6,55) е неразтворим.

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

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

и да го превърне в система от ограничения (6,53).

4. Получената разширен Проблемът, решен чрез метода на симплекс. Ако сте намерили най-добрия план ще бъде цяло число, проблемът с число програмиране (6.52) ... (6.55) е решен. В противен случай, върнете се към стъпка. 2 на алгоритъма.

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

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

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

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

не е така, най-общо казано, да напълно неразделна проблем в канонична форма, защото в трансформирани ограничения (6,59)

помощни променливи Xn + аз не подлежат на изискването за пълнота.

Въпреки това, ако всички коефициенти Aij. BI в (6.59) - числа, тогава състоянието на число може да бъде удължен с Xn + I. както това е направено в решаването на примера 6,10.

Напълно число проблем в канонична форма може да се получи, ако (6.59) Aij. дву - рационални числа. За да направите това, умножете (6.59) на общо кратно на знаменателите на коефициентите - Aij. двупосочен (т.е. отидете на цели коефициенти в (6.59)), и едва след това да се въведат допълнителни променливи.

Пример 6.20. Напълно решаване на проблема с число програмиране

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

Ние се реши проблема по метода на симплекс. За яснота, решението илюстрират графично (фиг. 6.19).

Фиг. 6.19. Графичен илюстрация на решаването на проблема

Фиг. 6.19 0KLM - възможно област, ограничена от права проблем (1), (2), (3) и координатните оси; L (2/3; 8) - оптималната точка, но решаване на проблема noninteger; (4) - разтвор директно намеси не е цяло число; 0KNM - възможно област увеличен проблем (6.64 ") N (2, 7) - разтвор оптимално число точка.

Стъпя. Основните променливи; второстепенни променливи.

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

Въпреки X3 решение не отговаря на условието пълнотата (6.55 "). Според първото уравнение с променлива x1. получена стойност не-число в оптималното решение (2/3), е допълнително ограничение (6.57):

Моля, имайте предвид, че в съответствие с (6.56) и (6.57) се вземат дробна част на свободен член на същия знак, който той има в уравнението и дробна част от коефициентите на Х4 второстепенни променливи и X5 - с противоположни знаци.

Тъй като дробна част

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

Чрез въвеждането на допълнителен променлива x6 число ≥ 0, ние получаваме еквивалент неравенството (6.57 ") уравнение

Уравнение (6.58) трябва да бъдат включени в системата на ограничения (6,56 ") на оригиналния каноничен проблема, а след това повторете процеса на решаване на метода за проблем симплекс прилага разширен проблем. В същото време, за да се намали броят на етапите (повторения) се препоръчва да се въведе допълнително уравнение (6.58) в системата, в резултат на което последната стъпка за решаване на проблема (число без условия).

IV стъпка. Основните променливи; второстепенни променливи.

Тъй като функция експресия линеен не е основните променливи с положителни коефициенти, Х5 - оптималното решение.

Така че, Fmax = 25 при оптимално решение число има шест компоненти на смислен смисъл.

За геометрична интерпретация на 0h1h2 равнина (вж. Фиг. 6.19) стреляйки (6.57 ") трябва да бъдат включени в него променливи x4 и х5 изразено от променливи x1 и x2. Ние се получи (виж 2-ри и 3-ти ограничения уравнение (6.56 ") .:

(Вж. Изрезката на линия (4) на фиг. 6.19).