КАТЕГОРИИ:


Алгоритъм за решаване на ZLTSP

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

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

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

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

Пример: В разтвор на проблема с оптимизиране на симплекс метод се получи основен разтвор:

1 = х 2 - х 1 + 4 4 х 5

3 3 3

х = 2 8 - х 5

х 3 = 18 + 4 х + х 5

Z = 25 Януари - 2 х 4 - х 1 5

3 3 3

X = (2; 8; 18; 0; 0) Z = 25 Яну.

03 март

Този основен разтвор е оптимизирана.

Въпреки това, решението не отговаря X състояние пълнотата, тъй като първото уравнение на променливата х 1 = 2 / 3-1 / 3 х + 4 4/3 х 5, получен без цяло число в оптималното решение (2/3).

Дали правилно прекъсване, като допълнително ограничение.

2/3 + 1/3 х 4 - х 5 4/3 ≤0 (1)

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

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

2/3 = 0 + 2/3 = 2/3

1/3 = 0 + 1/3 = 1/3

-4/3 = -2 + 2/3 = 2/3,

ако това неравенство при в (1) може да се запише като:

2/3 + 1/3 4 -2 / 3 х 5 ≤0 (2) е редовно подрязване.

Въвеждането на допълнителен число променлива х 6 ≥ 0, ние получаваме което е еквивалентно на неравенството (2), уравнението:

2/3 + 1/3 4 -2 / + 3 5 х 6 = 0

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

<== предишната лекция | Следващата лекция ==>
| Алгоритъм за решаване на ZLTSP

; Дата на добавяне: 01.06.2014; ; Отзиви: 103; Нарушаването на авторски права? ;


Ние ценим Вашето мнение! Беше ли полезна публикува материал? Да | не



ТЪРСЕНЕ:


Вижте също:



ailback.ru - Edu Doc (2013 - 2017) на година. Не е авторът на материала, и предоставя на студентите възможност за безплатно обучение и употреба! Най-новото допълнение , Ал IP: 11.45.9.148
Page генерирана за: 0.049 сек.