Студопедия — Лабораторная работа №9. Решение задачи целочисленного программирования методом ветвей и границ
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Лабораторная работа №9. Решение задачи целочисленного программирования методом ветвей и границ






Рассмотрим следующий пример:

 

x(1) + x(2) ® max (4. 13)

2x(1) + 11x(2) £ 38 (4. 14)

x(1) + x(2) £ 7 (4. 15)

4x(1) - 5x(2) £ 5 (4. 16)

x(1) ³ 0 (4. 17)

x(2) ³ 0 (4. 18)

x(1), x(2) - целые. (4. 19)

 

0- ой шаг. Множество X(0, 1) состоит из всех решений задачи (4.13 - 4.19). Для получения оценки x(0, 1) решаем задачу (4.13-4.18). После решения этой задачи симплекс-методом последняя симплекс-таблица будет иметь вид:

 

xb b x(1) x(2) y(1) y(2) y(3)
y(1) x(2) x(1) 1.00 2.56 4.44 0.00 0.00 1.00 0.00 1.00 0.00 1.00 0.00 0.00 -6.00 0.44 0.65 1.00 -0.11 0.11
d 7.00 0.00 0.00 0.00 1.00 0.00

 

Оценка x(0, 1)=7. Решение x(1)=4.44, x(2)=2.56 не является целочисленным. Дерево разбиения примет вид

 

 

x(1)=4.44

x(0, 1)=7

x(2)=2.56

1 - ый шаг. Разбиваем множество X(0, 1) на подмножества X(1, 1), X(1, 2). В качестве переменной, по которой проводим разбиение берем переменную x(1), которая имеет нецелочисленное значение. Можно взять и переменную x(2).

Для подмножества X(1, 1) дополнительное ограничение будет иметь вид x(1) £ 4.

Добавляем его к последней симплекс-таблице подмножества X(0, 1),

получим:

 

xb b x(1) x(2) y(1) y(2) y(3) y(4)
y(1) x(2) x(1) y(4) 1.00 2.56 4.44 -0.44 0.00 0.00 1.00 0.00 0.00 1.00 0.00 0.00 1.00 0.00 0.00 0.00 -6.00 0.44 0.65 -0.56 1.00 -0.11 0.11 -0.11 0.00 0.00 0.00 1.00
d 7.00 0.00 0.00 0.00 1.00 0.00 0.00

 

Решив эту задачу двойственным симплекс-методом, получим таблицу:

 

xb b x(1) x(2) y(1) y(2) y(3) y(4)
y(1) x(2) x(1) y(2) 5.79 2.20 4.00 0.80 0.00 0.00 1.00 0.00 0.00 1.00 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 2.20 -0.20 0.00 0.20 -10.8 0.80 1.00 -1.80
d 6.20 0.00 0.00 0.00 0.00 -0.20 1.80

x(1)=4, x(2)=2.2, x(1, 1)=6.2.

 

Для подмножества X(1, 2) дополнительное ограничение будет иметь вид x(1)³ 5. Добавляем его к последней симплекс-таблице подмножества X(0, 1), получим, что задача не имеет решения, т.е. подмножество X(1, 2)=Æ, x(1, 2)=M (M - достаточно большое число, M ® ¥).Дерево разбиения принимает вид:

x(1)=4.44

 
 


x(0, 1)=7

x(2)=2.56

x(1) £ 4 x(1) ³ 5

x(1)=4

x(1, 1)=6.21 x(2)=2.2 x(1, 2)=M

 

 

На последующих шагах дальнейшему разбиению будет подвергаться подмножество X(1, 1).

 

 

Полное дерево разбиения будет иметь вид

x(1)=4.44

x(0, 1)=7

x(1) £ 4 x(2)=2.56

x(1)=4 x(1) ³ 5

x(1, 1)=6.21 x(1, 2)=M

x(2)=2.2

x(2) £ 2 x(2) ³ 3

x(2, 1)=5 x(2, 2)=5

x(1) £ 3 x(1) ³ 4

x(1)=3

x(3, 1)=5 x(3, 2)=M

x(2)=2

На подмножестве X(3, 1) получаем целочисленное решение x(1)=3, x(2)=2 со значением функционала, равным 5, которое принимаем за рекордное. Все подмножества X(r, t), у которых значения x(r, t) ³ 5, отбраковываем, тогда x(1)=3, x(2)=2 становится оптимальным решением.







Дата добавления: 2014-12-06; просмотров: 544. Нарушение авторских прав; Мы поможем в написании вашей работы!



Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

Что такое пропорции? Это соотношение частей целого между собой. Что может являться частями в образе или в луке...

Растягивание костей и хрящей. Данные способы применимы в случае закрытых зон роста. Врачи-хирурги выяснили...

ФАКТОРЫ, ВЛИЯЮЩИЕ НА ИЗНОС ДЕТАЛЕЙ, И МЕТОДЫ СНИЖЕНИИ СКОРОСТИ ИЗНАШИВАНИЯ Кроме названных причин разрушений и износов, знание которых можно использовать в системе технического обслуживания и ремонта машин для повышения их долговечности, немаловажное значение имеют знания о причинах разрушения деталей в результате старения...

ТЕОРИЯ ЗАЩИТНЫХ МЕХАНИЗМОВ ЛИЧНОСТИ В современной психологической литературе встречаются различные термины, касающиеся феноменов защиты...

Этические проблемы проведения экспериментов на человеке и животных В настоящее время четко определены новые подходы и требования к биомедицинским исследованиям...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия