Студопедия — Лабораторная работа №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; просмотров: 542. Нарушение авторских прав; Мы поможем в написании вашей работы!



Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

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

Методы анализа финансово-хозяйственной деятельности предприятия   Содержанием анализа финансово-хозяйственной деятельности предприятия является глубокое и всестороннее изучение экономической информации о функционировании анализируемого субъекта хозяйствования с целью принятия оптимальных управленческих...

Образование соседних чисел Фрагмент: Программная задача: показать образование числа 4 и числа 3 друг из друга...

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Меры безопасности при обращении с оружием и боеприпасами 64. Получение (сдача) оружия и боеприпасов для проведения стрельб осуществляется в установленном порядке[1]. 65. Безопасность при проведении стрельб обеспечивается...

Весы настольные циферблатные Весы настольные циферблатные РН-10Ц13 (рис.3.1) выпускаются с наибольшими пределами взвешивания 2...

Хронометражно-табличная методика определения суточного расхода энергии студента Цель: познакомиться с хронометражно-табличным методом опреде­ления суточного расхода энергии...

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