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

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

Решение задачи методом ветвей и границ 4 страница






 

Задача №3:

Добавляется ограничение x1≤4

Выразим допустимый базис в форме Таккера:

x5=-3-(-x1-2x2+0x3+0x4)

x6=-9-(-2x1+0x2+0x3+2x4)

x7=-5-(-x1-x2+x3+2x4)

x8=-2-(-x1+0x2+2x3-x4)

x9=4-(x1+0x2+0x3+0x4)

Целевая функция в форме Таккера:

Y=0-(4x1+x2-3x3+2x4)

Таблица 2.1.47

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 -3 -1 -2              
X6 -9 -2                
X7 -5 -1 -1              
X8 -2 -1     -1          
X9                    
Y       -3            

Используем двойственный симплекс-метод. Вводим в базис x1, выводим из базиса x6

Таблица 2.1.48

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 3/2   -2   -1   -1/2      
X1 9/2       -1   -1/2      
X7 -1/2   -1       -1/2      
X8 5/2       -2   -1/2      
X9 -1/2           1/2      
Y -18     -3            

Используем двойственный симплекс-метод. Вводим в базис x2, выводим из базиса x7

Таблица 2.1.49

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
X5 5/2     -2 -3   1/2 -2    
X1 9/2       -1   -1/2      
X2 1/2     -1 -1   1/2 -1    
X8 5/2       -2   -1/2      
X9 -1/2           1/2      
Y -37/2     -2     3/2      

Решение данной задачи: Решения нет.

 

Т.к. список задач, подлежащих решению пуст, то можно сделать вывод о том, что решение задачи целочисленного программирования завершено.

 

Ответ: Y=-18;X=(5;1;1;0;4;1;0;1;0;0)

 

Блок-схема решения:

Ответ: Y=-18;X=(5;1;1;0;4;1;0;1;0;0)

 







Дата добавления: 2015-09-07; просмотров: 286. Нарушение авторских прав; Мы поможем в написании вашей работы!



Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

В эволюции растений и животных. Цель: выявить ароморфозы и идиоадаптации у растений Цель: выявить ароморфозы и идиоадаптации у растений. Оборудование: гербарные растения, чучела хордовых (рыб, земноводных, птиц, пресмыкающихся, млекопитающих), коллекции насекомых, влажные препараты паразитических червей, мох, хвощ, папоротник...

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

Выработка навыка зеркального письма (динамический стереотип) Цель работы: Проследить особенности образования любого навыка (динамического стереотипа) на примере выработки навыка зеркального письма...

Тактические действия нарядов полиции по предупреждению и пресечению групповых нарушений общественного порядка и массовых беспорядков В целях предупреждения разрастания групповых нарушений общественного порядка (далееГНОП) в массовые беспорядки подразделения (наряды) полиции осуществляют следующие мероприятия...

Механизм действия гормонов а) Цитозольный механизм действия гормонов. По цитозольному механизму действуют гормоны 1 группы...

Алгоритм выполнения манипуляции Приемы наружного акушерского исследования. Приемы Леопольда – Левицкого. Цель...

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