Studopediya

КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

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

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

Нека да е необходимо да се намери решение, X = (х 1, х 2, ... х п), в която линейна функция Тя счита, максимална или минимална стойност на ограниченията

(2.54)

Integer оптимизационни методи могат да се разделят на 3 групи: методи на прекъсване на захранването, комбинаторни методи, приблизителни методи. От стреляйки методи най-често използваният метод на Gomory от комбинаторни техники - браншови и свързания метод. Нека разгледаме метода на алгоритъм, Gomory нарязани.

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

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

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

Нека задачата на линейното програмиране има ограничен оптимално и в последната стъпка за решаване на симплекс метода, уравнения, които изразяват основните променливи х 1, х 2, ... х м от второстепенни х м 1, х m 2, ... х п оптимални решения:

(2.55)

Нека оптималното решение - Non-число компонент. След това неравенство

(2.56)

където {} - фракционна част има свойствата правилно изрязани.

4. Въвеждането на допълнителна неотрицателна променлива неравенство (2.56) се трансформира в уравнение

(2.57)

и е включена в ограниченията на системата (2.54). Това е еквивалентно на добавяне на уравнение (2.57) до (2.55).

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

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

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

Пример 12. Да предположим, че имаме определена сума пари (20 000 стр.) И това може да бъдат изразходвани за закупуване на гориво. Доставчик продава гориво в резервоарите на две различни обеми: големи бъчви от 200 литра и 20 литра бутилки. Цена изпразва: Barrel - 600 стр туба - 100 стр .. Цената на един литър гориво - 25 стр. Необходимо е да се определи оптималния брой на бидони и варели, за броя на литра гориво са били увеличени.



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

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

(2.58)

Решаването на проблема с метод симплекс изключение на целочислени променливи х 1 и х 2, получаваме:

(2.59)

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

Изграждане на правилното прекъсване:

, (2.60)

След добавянето на (2.60) към разтвора (2.59) и въвеждане на допълнителна променлива х 4, имаме:

(2.61)

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

(2.62)

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

не-число решения Building компонент правилното подрязване от уравнението, съответстващ на:

, (2.63)

След прибавяне на (2.63) към разтвора (2.62) и въвеждането на допълнителни 5 на променливата X, имаме:

(2.64)

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

(2.65)

Оптималното решение число: , F макс = 700.

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

Забележка: Не базов променлива х 4 не е включена в експресията на целевата функция на оптимално решение, следователно, неговата вариация не се променя стойността на F макс. Но за да се решение да остане валиден, променливата х 4 може да се настрои от 0 до ½. Само за 4 х = 0, решаването на проблема е цяло число.

Тема 3. Проблемът с транспорта

<== Предишна лекция | На следващата лекция ==>
| Integer програмни проблеми

; Дата: 06.01.2014; ; Прегледи: 170; Нарушаването на авторските права? ;


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



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 11.102.9.22
Page генерирана за: 0.053 сек.